💾

09 : Paging

course

last review

2023/04/13

mastery

rookie

progress

not started

date

2023/03/28

4 more properties

Previous chapter

08 : Segmentation

Main QUEST : Virtualizing with Page

Simple Example and Outline

Address Translation

Example

Questions You may have

Where Are Page Tables Stored?

Example

What’s Actually in the Page Table?

The Content of Page Table Entry

Isn’t It Too Slow?

Understanding How Things Work Together

세그멘테이션을 한마디로 요약하면 “가상메모리를 가변 크기의 조각으로 분할하는 것”이다.

불행하게도, 태생적인 문제를 가지고 잇다.

•

공간을 다양한 크기의 청크로 분할할 때 공간 자체가 단편화(fragmented)될 수 있고, 할당은 점점 더 어려워진다.

만약 공간을 동일 크기의 조각으로 분할한다면 어떨까?

프로세스의 주소공간을 몇개의 가변 크기의 논리 세그먼트로 나누는게 아니라 고정크기의 단위로 나누는 것이다!

우리는 이 각각의 고정 크기 단위를 페이지(page)라고 부른다.

이에 부응하듯 물리 메모리도 페이지 프레임(page frame)이라는 고정크기의 슬롯 배열이라고 생각할 수 있다. 마치 B&B를 보는 것 같다. 그렇지 않나?

Main QUEST : Virtualizing with Page

세그멘테이션의 단편화 문제를 해결하기 위해 페이지를 사용하여 어떻게 메모리를 가상화할 수 있을까? 기본적인 기법은 무엇이며, 시공간 오버헤드를 최소로 하는 방법은?

Simple Example and Outline

왼쪽은 총 크기가 64byte이며, 4개의 16byte 페이지로 구성된 Address Space다.

물리 메모리는 18.2에 나타낸 바와 같이, 고정 크기의 슬롯들로 구성된다.

8개의 페이지 프레임, 128바이트의 물리메모리라고 가정하자.

FEATURES

•

가상 주소 공간의 페이지들이 물리 메모리 전체에 분산 배치되어있다.

•

운영체제가 자기자신을 위해 물리 메모리의 일부를 사용한다.

페이징이 가지는 장점은 세그멘테이션에 비해 매우 많다.

유연성 개선

프로세스가 주소공간을 어떻게 사용하는지와는 상관없이 효율적인 주소공간 지원이 가능하다.

힙과 스택이 커지는 방향을 고려하지 않아도 되는 것이다.

단순함

64바이트 주소 공간을 8페이지 물리 메모리에 배치하기를 원한다고 할 때, OS는 비어있는 네개의 페이지만 찾으면 끝이다.

물론 OS는 이를 위해 어느 공간이 비어있는지 리스트업을 해야할 것.

Address space의 각 가상 페이지에 대해 물리 메모리가 어디에 매핑되어있는지를 기록하기 위해 OS는 페이지 테이블(Page table)이라는 자료구조를 유지한다.

페이지 테이블의 가장 큰 존재의의는 VP → PF로 주소 변환을 하는 용도이다.

페이지 테이블은 (VP0→PF3),(VP1→PF7),(VP2→PF5),(VP3→PF2)라는 항목을 가진다.

페이지 테이블은 프로세스마다 존재한다는 사실을 기억하자.

다른 프로세스를 실행해야한다면, 그 프로세스를 위한 다른 페이지 테이블이 필요하다.

페이지 프레임과 페이지 테이블에 대해 이해를 마쳤으니, 이제 주소 변환을 어떻게 하는지 알아봦.

Address Translation

주소변환을 위해 가장 먼저 필요한 것은 Virtual Address를 가상 페이지 넘버 (Virtual Page Number, VPN)와 오프셋으로 분할해야한다.

위 예시에서 주소공간의 전체크기는 64바이트이다.

주소를 위한 비트사이즈는 6비트가 필요하다.(

2^6 = 64

)

Va5는 최상위 비트, Va0는 최하위 비트를 나타낸다. 우리는 페이지 크기가 16byte임을 알고있으므로, 오프셋이 4비트, VPN이 2비트로 나뉘어야함을 바로 유추할 수 있다.

프로세스가 가상주소를 생성하면 OS와 하드웨어가 물리주소로 이를 변환해준다.

Example

가상주소가 21이라고 하자.

movl 21, %eax
Assembly
복사

“21”을 바이너리 넘버로 바꾸면 010101이 된다.

VPN와 오프셋으로 분해하면 [01 / 0101] 이 될 것이다.

따라서 가상주소 21은 VP 1페이지의 5번째 바이트이다.

VP = 1일때 페이지 테이블에서 매핑한 물리 프레임 넘버(Physical Frame Number, PFN)은 7(111)이다.

VPN을 PFN으로 교체하여 가상 주소를 변환할 수 있다. 그런 후에 물리 메모리에 탑재 명령어를 실행한다.

오프셋은 변환되지 않는다는 점을 주의하자.

오프셋은 페이지 내에서의 우리가 원하는 위치를 알려주기 때문이다.

즉, 최종 물리 주소는 1110101(117)이 된다.

Questions You may have

이 개요를 염두에 두고 이제 페이징에 관해 몇가지 질문을 해보자.

•

페이지 테이블은 어디에 저장될까?

◦

페이지 테이블의 내용은 무엇이며, 크기는 얼마일까?

•

페이징은 시스템을 느리게 만들지 않을까?

Where Are Page Tables Stored?

페이지 테이블의 크기는 세그먼트 테이블이나 B&B 레지스터에 비해 크기가 매우 커질 수 있다.

Example

4KB크기의 페이지를 가지는 32bit짜리 Address Space를 생각해보자.

페이지당 크기가 4KB이므로, 오프셋의 크기는 2122^{12}212, 즉 12비트이다.

Address Space가 32bit 규격이므로, VPN은 20비트가 될 것이다.

이는 한 프로세스가 관리해야하는 페이지의 수가

2^{20}

개가 된다는 뜻이다(!)

물리주소로의 변환정보(매핑 등등..)와 다른 필요한 정보를 저장하기 위해 페이지 테이블 항목(Page Table Entry, PTE) 마다 대충 4바이트가 필요하다고 가정하자.

그럼 각 페이지 테이블당 4MB정도가 필요할 것이며, 이는 큰 크키다. 프로세스 100개가 실행하면 무려 400메가!

32비트 규격이라서 이정도지, 64비트다? 상상도 하기 싫다.

결론적으로, 페이지테이블은 크기가 메우 크기 때문에 실행중인 페이지 테이블을 저장할 수 있는 회로를 MMU안에 유지하는 건 미친 짓일 것이다.

대신 각 프로세스의 페이지 테이블을 메모리에 저장한다.

당분간 페이지 테이블은 OS가 관리하는 물리 메모리에 상주(VP0)한다고 가정하자.

What’s Actually in the Page Table?

페이지 테이블을 구현하기에 가장 간단한 방법은 아마 선형 페이지 테이블(Linear Page Table)이 될 것이다.

선형 페이지 테이블은 단순한 배열의 형태이다.

OS는 원하는 PFN을 찾기 위해 VPN으로 인덱싱(!)을 하고 그 항목의 페이지 테이블 엔트리를 검색한다.

The Content of Page Table Entry

•

valid bit

◦

이 값이 유효한지 아닌지를 저장한 비트다.

예를 들어 힙과 스택 사이의 모든 공간을 invalid하게 설정하여 해당 메모리에 접근할 시, OS가 트랩을 걸어버리는 구조로 활용이 가능할 것이다.

주소공간의 미사용 페이지를 모두 표시함으로써 이런 페이지들에게 물리 프레임을 할당할 필요를 없앤다.

•

Protection bits

◦

페이지가 rwx가능한지 나타낸다.(1~3비트?)

Protection bit가 허용하지 않는 방식으로 접근할 시 OS에 트랩을 건다.

•

Present bit

◦

현재 이 페이지가 어디에 있는지를 나타낸다.(디스크나 피지컬 RAM → swapped out이라고 한다)

•

Dirty bit

◦

해당 메모리에 쓰기 작업이 이루어졌는지 나타내는 비트

•

Reference bit

◦

rwx든 간에 참조가 되었는지 나타내는 비트

보통 valid와 present로 OS가 매핑을 판단한다.

Isn’t It Too Slow?

페이지 테이블의 크기가 메모리 상에서 매우 크게 증가할 수 있다.

movl 21 %eax
Assembly
복사

몇가지 가정을 할 것이다.

•

이 예시에서 하드웨어가 주소 변환을 담당한다고 가정한다.

•

주소21에 대한 참조만 고려한다.

먼저 시스템은 Virtual 주소 21을 정확한 물리 주소 117로 변환해야한다. 다음과 같은 프로세스가 있겠지?

•

VPN21을 PTE에 인덱싱

•

PTE로부터 PFN을 추출

•

VA의 offset + PFN 조합해서 정확한 물리 주소 변환

이렇게 하기 위해서는 해당 프로세스의 페이지 테이블이 어디에 있는지를 반드시 알아야 한다.

당분간 하나의 페이지 테이블 베이스 레지스터(page table base register)가 PT의 시작 주소를 저장한다고 가정하자.

즉, context Switch가 일어날 때마다 이 운영체제는 PTBR을 참조해 다음 테이블이 어디있는지를 확인하는 방식이다.

원하는 PTE의 위치를 찾기 위해 하드웨어는 다음과 같은 연산을 한다.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PTBR + (VPN * sizeof(PTE))
C
복사

Virtual Address는 XX YYYY와 같은 형식으로 구성된다.

VPN은 XX의 값만 의미있으므로, VPN_MASK(11 0000)를 통해 XX만 마스킹을 한다.

이후 SHIFT(4)로 VPN을 LSB쪽으로 정렬하여 정상적인 값을 뽑아낸다.

이 값을 이제 PTE의 인덱스로 사용한다.

offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PFN << SHIFT) | offset
Assembly
복사

offset은 Virtual Address의 YYYY에 해당하는 파트이므로, OFFSET_MASK(00 1111)을 연산하자.

이후 최종 PhysAddr에서 FPN와 offset을 조합하여 물리주소값을 얻으면 된다!

이 과정에서 성능이 느려지는 파트를 참조하자.

모든 메모리 참조에 대해 먼저 페이지 테이블에서 변환정보를 반입해야하기 때문에 반드시 한번의 추가적인 메모리 참조가 필요하다. 메모리 참조는 비용이 비싸고 프로세스가 2배 이상 느려지는 원인이 된다.

PTE = AccessMemory(PTEAddr) //느린 부분 : 페이지테이블이 워낙 커서 캐시에 담기도 힘듦
if (PTE.Valid == False)
		RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
		RaiseException(PROTECTION_FAULT)
else
		offset = VirtualAddress & OFFSET_MASK
		PhysAddr = (PTE.PFN << SHIFT) | offset
		Register = AccessMemory(PhysAddr)
C
복사

Understanding How Things Work Together

컴파일 타임에 정해진 데이터와 코드, 컴파일된 파일은 스토리지에 들어가 있음

실행이 될 때 물리 메모리에 올라와야한다.

필요한 놈들에 한해서 매핑할 것

스택이나 힙 도 존재할 것이고

매핑 테이블 → 메모리 상에 존재(PM)

실행되는 응용프로그램 입장에서는 VM에서 돌고 있다고 생각할 것임.

Fetch Load Store 시 항상 주소가 필요함. → 일단 다 VA이다.

페이지테이블 베이스 레지스터에 있는 매핑 테이블을 기반으로 VA→PA로 변환된다.

Next chapter

10 : Translation-Lookaside Buffer