Advanced_paging

 

ch8에서 언급했듯, 더 나은 페이징 기법을 위한 몇 가지 사례를 소개한다.

Linear Page Table

• 앞서, 하나의 process는 하나의 Page table을 가질 수 있다고 소개했다.
• 32bit의 주소공간을 가지고, 4KB의 page 크기, 4B의 PTE 크기, 2^20개의 pate table entry 수
• 이러한 공간은 총 4MB라는 Page table의 공간을 할당하게 한다.

• 그런데 문제는, 이 넓은 공간에 사용하지 않는 Invalid entries를 위해서도 자리를 잡고 있어야 한다.

⇒ 이러한 문제를 해결하기 위해 한 가지 접근방법을 생각한다

Hybrid Approach: Paging and Segments

• Segment 별로 page table을 구성하는 방법이다.
• Segmentation
  • Virtual address space를 segment들로 나눈다
  • 각각의 segment는 다양한 길이를 가진다. ( 크기 고정 X)
• Paging:
  • segment의 크기는 다양한 대신, fixed-sized page로 또 각 segment를 쪼갠다.
  • 각 segment는 page table을 가지고 있다.
  • 각 segment는 VPN에 해당되는 page table entry로 가 P.A의 주소를 찾은 후 offset과 함께 찾고자 하는 P.A data를 참조한다.

• 여기서 상위 2비트는 어떤 segment인지를 나타내는 값이다.
• 실제 구현을 Multics의 주소 변환 사례로 살펴보자.
• 만약 Context switch가 발생한다면, 현재 실행중인 process의 각 segment에 해다하는 page table의 주소값을 저장 / 복원해야한다.

 

 

Paging with Segmentation : Pros and Cons

• Procs
  • Linear page table에 비하면 page table의 memory 소비를 줄일 수 있다.
  • Segment가 page 단위 관리되기 때문에, Segment의 확장이 필요하면 그냥 reshuffle할 필요 없이 새 페이지를 할당하면 된다.
  • Sharing의 flexibility가 증가한다
    • 특정 page나 전체 segment를 공유할 수 있다.
• Cons
  • 각 segment마다 page table이 필요하기 때문, 사용량이 적고 희소한 heap같은 경우 메모리 낭비가 발생할 수 있다.
  • External fragmentation이 발생할 수 있다.
    • Page table을 연속적으로 할당해야하기 때문에 메모리 할당과 해제가 반복될 때 external fragmentation이 발생 가능하다.

Multi-level Page Table

• Linear table의 단점을 최소화하기 위해, linear page table 구조를 tree처럼 바꾼 구조이다.
•  

 

 

• 우선, page table을 page size unit으로 쪼갠다.
• 만약 Page table entry의 전체 page invalid 하다면, 그 page를 아예 page table에 할당하지 않는다
• page directory라는 새로운 구조를 이용해 page table의 page가 valid한지 추적한다.
  • page directory는 최상위 레벨 페이지 테이블로, 하위 페이지 테이블 ( 즉, 실제 page table 단위)에 대한 포인터를 저장한다.
• 이때 모든 page table의 크기는 4KB이다.
• 밑의 그림은 Multi-levl page table을 구현한 모식도이다.
•  

 

• Linear page table에서는, page table을 저장하기 위해 4개의 page frame을 사용했지만,
• Multi-level page table에서는 3개의 page frame을 사용하였다.

⇒그렇다면, 이 과정에서 주소변환은 어떻게 이루어지고 왜 각각의 page table의 크기는 모두 4KB로 동일한지 알아보자.

Virtual address translation

• Viltual address는 3가지 파트로 구성되어있다.
•  

• Page directory # : Page directory를 인덱싱 하는 부분이다.
• Page table # : Page directory에서 포인팅 된 Page table로, 이 페이지에 있는 P.A의 page frame주소로 이동하게 된다.
• Offset : 페이지 내의 정확한 주소를 구하기 위해 page frame 주소에 offset을 더해 주소를 참조한다.
• 이때 PTBR은 page directory의 시작 주소를 pointing 하고 있다.
•  

 

• 그럼, 실제 bit수에 대한 예시를 살펴보자.
• 다음과 같은 Hardware가 address translation을 진행한다고 생각하자.
•  

• 이때 virtual address는 30bit이다.
• Page size는 512byte = 2^9이다. (Offset이 9bit이라 512byte)
• VPN은 21bit이고, offset은 9bit이다.
• 이랬던 virtual address가, 만약 Two-levl page table을 implement한다고 생각해보자.

Two-level page tables

• 우선, VPN을 구성하고 있던 21bit가, 7bit의 Page Table index와 14bit의 Page Directory Index로 나누어진다. Offset은 9bit 그대로 유지한다.

 

• 이때 Virtual address는 여전히 30bit이다.
• Page size도 여전히 512 byte = 2^9이다.
• VPN은 21bit이며, Offset도 9bit이다.
• 이 떄, 하나의 page table 총 7bit이다.
  • Page table index가 7bit이므로, PTE는 최대 2^7개있을 수 있기 때문
• page directory entries의 수는 2^14개이다
  • 마찬가지로 Page Directory index의 bit수가 14bit이므로, PDE를 최대 2^14개 나타낼 수 있음
• 이때 하나의 PTE가 가리키는 page table의 크기는 2^7이다.
• number of page directory entiry는 총 2^14개이다.

이를 정리하면 다음과 같다.

 

그렇다면, Level이 2보다 큰 page table은 어떻게 구현될까?

 

 

• 다음과 같은 경우에는, Page directory와 Page table page의 크기가 모두 2^7이 되게 된다.
• 실제 인텔은 어떻게 Multi-level page directory를 구현하는지 살펴보자.
• Intel의 x86_32 아키텍처에서는 각 page당 4KB의 크기를 갖는다( PTE와 PDE에 4B를 할당한다)
• 그렇게 할당하면, 모든 Page directory와 page table의 크기가 4KB로 고정된다.

 

 

 

 

다음은 64bit로 Multi-level page table을 구현한 예시이다.

 

 

• PTE의 size는 8B (64bit 체계이미로)이고, page의 size는 4KB이다.
• 8B짜리 entry가 2^9개 있어 모두 4KB의 형태를 띄고, Linear address에 있는 공간은 Page directory와 page table을 나타내기 위한 4단계의 9bit과, 12bit의 offset으로 이루어져 있다.
• 현재는 52bit으로 물리주소를 확장해 더욱 많은 메모리 사용을 지원한다.

Multi-level page talbe : Pros and Cons

• Pros
  • 희소 주소공간을 지원하면서도 컴팩트하다
    • Page-table 사용중인 주소 공간 비례하여 공간을 차지하기 때문이다.
  • Physical memory을 관리하기 편하다
    • 각각의 page table이 한 페이지에 적합하도록 설계되어있다. ( 모두 4KB )
  • Hardware(MMU)가 주소 변환을 위해 Multi level page table을 탐색하기 더 편하다.
    • Easy for hardware to walk though page tables
  • External fragmentation이 없다
• Cons
  • 주소 변환을 위해서 더 많은 memory access가 필요하다.
    • 1번의 memory 참조를 위해 여러번의 memory 접근이 필요함.
  • linear page table보다 더 복잡한 hardware가 필요하다.

 

 

 

 

=> 이후로 세마포어, 스레딩 등이 나왔는데 이 뒤는 정리할 수가 없었고, 필요도 없었다....

-> 과제 나오면 대가리 박고 꼭 한번 해봐라 머릿속에 개념이 정리가 안되어있으면 못한다.

-> 모르겠으면 xv6 공식 document 3번 정독하자. 

-> 근데 3번 정독해도 아마 모를거니까, 정독하고 코드 1주일 내내 봐라. 그럼 좀 해결된다

-> 1주일동안 코드 1줄도 못짜고  xv6 함수 뭔지 구글링만 하다가 1주일 후부터 깨달음을 얻어 과제를 시작할 수 있을 거다.... 

-> 근데 아마 다하는데 3주는 걸릴거다 그니까 총 1달 걸리는거임

-> 니가 그걸 어떻게 아냐고...? 알고싶지 않았다..... 난 천재가 아니라 1달 걸렸다

 

모든 OS 듣는 사람 화이팅

 

 

**** 이 블로그 포스팅은 연세대학교 정진규 교수님의 운영체제 강의를 듣고 정리한 포스팅임을 밝힙니다. ****