Paging

Paging

Physical memory를 fixed sized block (frame)으로 나눈다.

Logical memory를 같은 크기의 block인 page로 나눈다.

 

frame과 page는 같은 것으로 physical memory인지 logical memory인지를 구분하기 위해 달리 표현하는 것이다.

 

운영체제는 모든 free frame들을 기록해야 한다.

 

---

Page Table

목적

아래의 문제들을 해결하기 위해 page table을 사용한다.

• 운영체제와 하드웨어는 매핑 정보를 가지고 있어야 한다.
• 너무 많은 relocation register를 필요로 할 수 있다.
  • Relcoation register는 virtual address space의 최대 page 수 만큼 필요하다.

 

Page Table

Page table은 page-to-frame의 mapping 정보가 저장되어있는 메모리 상의 공간을 말한다.

각 프로세스의 page table은 main memory에 저장된다.

 

두 개의 register가 page table의 위치를 표현하기 위해 사용된다.

이를 이용함으로써 수많은 relocation register를 사용하지 않아도 된다.

• PTBR
  • page table base register
  • page table의 위치를 저장한다.
• PTLR
  • page table length register
  • page table의 크기를 저장한다.

 

Logical Address

CPU가 생성하는 주소는 page number와 page offset으로 나눠진다.

• page number(p)
  
  • frame의 위치를 찾는데 사용된다.
  • page table에서 각 frame의 base address를 포함하는 index로 사용된다.
• page offset(d)
  • 찾은 frame 내부에서의 위치를 찾는데 사용된다.

 

page number와 page offset의 길이는 page의 크기에 의해서 결정된다.

 

32bit machine에서 page 크기가 4KB(=$2^12$bytes) 라고 하자.

page offset을 표현하기 위해서는 12개의 bit가 필요하다.

남은 20개의 bit는 page number를 위해 사용된다.

 

Page Table Entry

아래 처럼 page table에서 해당하는 entry에 있는 frame number를 이용해서 page-to-frame mapping을 한다.

실제에서는 page number에 대한 별도의 entry는 필요하지 않다.

 

Address Translation Architercture

page offset은 page 내부에서의 상대적인 위치이기 때문에 교체될 필요 없다.

따라서 page number만 page table을 이용해서 translation을 해서 frame number로 바꾼다.

 

page table은 physical memory 내부에 저장되어 있다.

 

---

TLB (Translation Look-Asside Buffer)

Page table은 main memory에 위치한다.

 

따라서 매 instruction 실행 마다 최소 2번의 memory access가 필요하다.

Page table을 이용한 translation을 위해서 한번, data나 instruction을 실제로 가져오기 위해서 한 번이 필요하다.

 

그런데 요즘 system에서 page table은 매우 크므로, register를 이용해서 빠르게 찾기가 힘들다.

 

이러한 문제를 해결하기 위해서 TLB (Translation Look-Aside Buffer)를 이용한다.

TLB는 special small hardware cache로, TLB를 이용하면 한 번의 memory access만 하면 된다.

 

TLB에는 빈번하게 사용되는 mapping 정보가 저장되어있다.

page number가 연속적으로 증가하지 않기 때문에 page number를 기록하는 column이 필요하다.

 

Address Translation

CPU가 주소를 내보내면 TLB에서 먼저 찾는다.

TLB에 원하는 page number가 있다면 frame number로 교체한다.

만약 TLB에 원하는 page number가 없다면 page table로 접근해서 frame number를 찾는다.

 

Effective Memory Access Time

hit rate = H, TLB search time = T, Memory access time = M 이라고 하자.

 

이 때 effective memory access time

= H * (T + M) + (1-H) * (T + M + M)

= T + M + (1-H) * M

이 된다.

 

hit rate(H)가 증가하면 effective access time이 감소한다.

따라서 TLB에서 얼만큼 내가 원하는 정보를 유지하느냐가 성능에 큰 영향을 미친다.

 

---

Memory Protection, Memory Sharing

page table에 추가적인 bit를 이용해서 memory protection과 sharing을 쉽게 구현할 수 있다.

 

Memory Protection

valid-invalid bit을 이용해서 memory protection을 구현한다.

• valid : 해당 page가 실제로 physical memory가 할당 되어있고 유효하다.
• invalid : not valid

 

Memory Sharing

물리적으로 frame은 하나로 두고, 해당 frame을 공유하고자하는 프로세스의 page table에 frame을 mapping하면 쉽게 sharing 할 수 있다.

프로세스의 page table에 해당 frame number를 기록하면 된다.

 

---

Page Table Structure

3 종류의 page table structure가 있다.

그 중 hierarchical paging이 가장 많이 사용된다.

• hierarchical paging
• hased page tables
• inverted page tables

 

Hierarchical Paging

page table의 크기가 클 때 여러 개의 작은 page table로 쪼갠다.

쪼개진 page table에 대해서 page table을 유지한다.

 

원래의 page table의 크기가 $2^32$bytes 이고, page의 크기가 $2^12$bytes 라고 하자.

page table은 $2^20$개의 entry를 가지고 있다.

 

각 entry의 크기가 4 bytes라고 하면 각 프로세스는 4MB의 page table을 가지게 된다.

page table은 main memory에 contiguous하게 저장되야한다.

그런데 이는 너무 크고, 애초에 paging의 목적은 non-contiguous 하게 메모리를 관리하는 것이었기 때문에 paging의 목적에도 위배가 된다.

 

이를 해결하기 위해서 page table을 여러 개의 작은 page table로 쪼갠다.

그리고 쪼개진 page table에 대해서 paging을 한다.

 

2-level paging은 원래 page number가 20bit 였다면 이를 10bit 씩 2개로 쪼갠다.

 

outer page table로부터 inner page table의 위치를 찾아낸다.

찾아진 inner page table로 부터 우리가 원하는 frame number를 찾는다.

 

Hased Page Tables

hasing을 사용해서 page table을 구현한다.

초기에 제안된 방법으로 현재는 잘 사용되지 않는 방법이다.

 

logical address를 hasing 하고, 이에 대한 linked list로 page를 연결한다.

 

Inverted Page Table

방향을 뒤집은 page table로, frame number로 부터 page number를 찾아간다.

inverted page table의 index는 frame number가 된다.

 

hierarchical page table과 hashed page table은 프로세스 별로 page table이 존재한다.

프로세스 별로 logical address space가 다르기 때문이다.

 

inverted page table은 page number만 기록하면 되기 때문에 system에 page table이 한개만 존재한다.

프로세스마다 동일한 page number가 존재할 수 있기 때문에 pid도 같이 기록한다.

 

다음과 같이 동작한다.