Paging

Virtual Page

Physical Frame

• 페이징을 활용하여 frame과 page를 매핑한다.

• frame
  - 물리 메모리를 fixed_size_block 으로 쪼갠 것
  

• page
  - 논리(logical) 메모리를 same_size_block으로 분할한 것
  

이때, logical 메모리의 경우에는 메모리에 순서대로 올라올 필요가 없다.

페이징을 위해서는 page number와 page offset이 필요하다.

• page number는 페이지 테이블에서의 인덱스 역할을 하고
• page offset은 페이지 테이블에서 page number를 통해 물리 메모리에 접근한 뒤, 프레임의 시작점에서의 거리를 나타낸다.

이때, 페이지 size는 하드웨어에 따라 다르지만, 반드시 2의 배수여야만 한다.

logical address space가 2^m 이고, page size가 2^n 승이면, logical address space의 상위 m - n bit는 page number를 지정하고, 하위 n 비트는 page offset을 지정한다.

page allocation은 다음 그림과 같이 수행된다. free frame list에서 free frame을 골라서 페이지들이 할당되는 것을 볼 수 있다. 앞서 설명했듯이 이들은 상위 주소부터 순서대로 할당되지는 않는다.

Page table & Supplementary Page Table

이때 물리 메모리 주소와 가상 메모리 주소간의 매핑을 담당하는 것이 페이지 테이블이다.

페이지 테이블을 관리하기 위해서, 페이지 테이블로의 포인터는 각 프로세스의 PCB에 다른 레지스터들과 함께 저장된다.
(PCB는 프로세스 별로 커널 스택에 저장된다)

이를 수행하는 PTBR이라는 레지스터를 통해서, 현재 page table의 physical address의 시작점을 가리킨다.

이 PTBR을 활용하면 페이지 테이블의 위치를 빠르게 파악할 수 있기에 컨텍스트 스위치가 빠르나, 메모리를 두번 접근해야 하기 때문에 접근에 있어 시간적 부담이 존재한다.

page table entry를 접근하는 것과, 페이지 테이블을 통해 얻어낸 값으로 실제 data에 접근하는 두번의 접근이 필요하다.

Translaction Lookaside Buffer - TLB

따라서, TLB라는 캐시 역할의 하드웨어를 두어서 접근에 대한 부담을 줄인다. 이를 그림으로 표현하면 다음과 같다.

만약 찾고자 하는 페이지가 TLB안에 포함돼 있으면 TLB hit라 표현하고, 그렇지 않은 경우에는 TLB miss라고 표현한다.

페이지 테이블에서 protection bit를 통해서 메모리에 대한 보호를 수행할 수 있다.

페이지 테이블에 valid / invalid bit를 추가해서, 해당 페이지를 사용할 수 있는지를 확인한다.

valid 비트가 표시돼있다면, 해당 page table 인덱스가 접근이 가능하면서, 실제 메모리에 올라와 있다는 뜻이다.

반대로 invalid 하다면, 해당 page table의 인덱스가 접근 불가능하거나, 해당 부분이 현재 메모리가 아닌 Disk에 존재한다는 뜻이다.

따라서 page fault 발생시(실행시켜야 할 page가 실제 메모리에 올라와 있지 않음),
1. cpu는 운영체제에게 이 사실을 알려서 운영체제가 trap 발생시킴
2. CPU는 디스크에서 해당 부분을 찾아서 실제 메모리의 비어있는 frame에 올리고,
3. page table의 해당 부분 bit를 Valid로 갱신하고,
4. 원래의 작업을 재개한다.

전체적인 흐름은 다음과 같다.

페이지 테이블 구조화

페이지 테이블을 구성하는 방식은 다음 세가지가 있다.
1. Hierarchical page table
2. Hashed page table
3. Inverted page table

첫번째로 계층적 테이블이다. 페이지 테이블이 너무 커지는 것을 대비해서, 페이지 테이블의 layer를 여러개 둔다.

이렇게 하면

• page number에 대한 lookup이 빨라지고,
• 메모리에 사용되지 않는 영역이 많을 시 페이지 테이블이 적은 공간을 차지할 수 있고
• 각각의 섹션(code, data, stack)이 독립적으로 다뤄질 수 있는 장점이 있다.

다음은 Hashed table이다. 해시함수를 통해 페이지테이블을 구성한다.

얘는 일반적인 페이지 테이블이나 계층적 테이블보다 훨씬 적은 공간을 차지한다.
이는 모든 피지컬 프레임에 대해서 one-entry만이 존재하기 때문이다.(공간)

또한, 다음으로 살펴볼 inverted table보다 lookup또한 (시간) 빠르다.
따라서 inverted table의 공간적 장점과 일반 page table의 시간적 장점을 합친것과 같은 효과를 낸다.
출처

마지막은 Inverted page table이다.
어떤 프로세스가 어떤 페이지를 갖고 있는지를 저장한다.

얘는 많은 물리 메모리를 차지하지 않는다는 장점이 있지만, 메모리 참조를 하는 과정에서 시간이 오래걸린다는 단점도 있다.

Supplementary Page Table

• include/vm/vm.h의 빈 구조체의 주석에는 다음과 같이 쓰여있다.

/* Representation of current process's memory space.
 * We don't want to force you to obey any specific design for this struct.
 * All designs up to you for this. */
struct supplemental_page_table {
};

현재 프로세스의 메모리 공간을 표현하는 페이지 테이블이라는데, 아직 확실하지 않다.
supplementary라고 써놓은 것을 보니, pml4 페이지 테이블로는 부족한 부분을 보충하는 역할을 한다고 추측이 든다.

몇가지 블로그 글을 종합한 결과에 따르면, 얘의 역할은
1. physical memory의 값이 바뀌어서 page fault가 발생할 시 커널은 supplement 페이지 테이블에서 오류가 발생한 페이지를 조회해서, 원래 physical memory에 들어있어야할 데이터가 무엇인지 확인 하게 하는 역할.
2. 첫번째 이유에서 이어지는데, 물리 메모리의 실제 값을 알아야 어떤 데이터를 free할지 결정할 수 있기 때문에 프로세스가 종료될 때 커널이 얘를 참조해서 어떤 리소스를 free 시킬지 결정하게 하는 역할.
3. page-table은 물리 주소a를 가리키고 있지만, 다른 페이지 테이블도 같은 물리주소 a를 가리킬 수 있기 때문에, 하나의 프로세스가 어떠한 physical 메모리를 참조하고 있는지에 대한 정보가 필요해서, 이 정보를 기록하는 역할
... 이라고 하는데 구현을 하면서 더 자세히 봐야 할듯 하다.

해시테이블을 사용한다고 한 것으로 보아선 위에서 설명한 Hashed page Table structure를 사용하는 듯 하다.

Memory Management Unit - MMU

• logical(가상)주소를 물리적 주소로 변환해주는 하드웨어 장치.
• mmu안의 relocation 레지스터 값이, 메모리에 보내질 당시에 유저에 의해 생성된 모든 값에 더해짐.
  - 유저 프로그램은 항상 논리적적 주소만을 다루기 때문에, 모든 값에 더해도 괜찮다.

또한 얘는 메모리를 보호하는 역할도 수행한다. 이는 limit 레지스터를 활용해, 참조할 수 없는 값을 참조하려 할때, trap을 발생시킴으로서 이뤄진다.

전체적인 큰 그림을 정리해보면 다음과 같다.