[Operating System] Memory Management 2

Structure of the Page Table

page table의 특징

• random access
  • 순차정렬되어 있고,
  • 모든 page가 저장되어 있으므로
• memory에 저장되어 있다.

하지만 page table도 1 frame에 저장되지 못 하는 경우가 발생하면 random access가 불가하기 때문에, page table lookup을 위한 search structure가 필요하다.

search structure

Hierarchical paging

• 여러 page table을 사용

Hashed page tables

• hashing function을 통한 p→frame address mapping

Inverted page tables

• 각 frame에 어떤 process의 몇 번 page가 할당되어 있는지를 page table에 저장

Hierarchical paging

Two-Level Page-Table Scheme

problem

page table의 크기가 커 1 frame에 들어가지 않는다.

 

process는 max size의 address space를 할당받기 때문에 32bit address space이고 page size가 4KB이라면, 총 page의 개수는 $2^{20}$이다.

또한 하나의 page를 나타내기 위한 각 entry의 크기는 보통 4bytes이다.

 

따라서 전체 메모리 공간에 대한 page table의 size는 4MB이다.

⇒ 이는 결국 1,024개의 frames이 필요하다

 

이는 다음 두 가지 문제점이 발생

1. page가 각 frame에 별도로 저장되면서 더 이상 연속적인 위치에 저장되지 않기 때문에 page number로 바로 page table에서 random access하는 것이 불가능
   • 내가 찾는 page number에 해당하는 정보를 담고 있는 page가 어디있는지를 알려주는 search structure가 별도로 필요
2. 각 process 별로 4MB를 필요로 하기 때문에 process의 개수가 많아지면 크기가 너무 커지게 된다는 문제점 또한 있다.

solution

1. page table을 위한 page table을 사용
   • Hierarchical paging 기법
2. disk에 memory에 저장
   • disk에 저장한 뒤 memory를 cache형식으로 사용.

Two-level page-table scheme

page table은 1024개의 entry를 가지게 된다.

• 각 entry 당 4bytes를 차지하므로 전체 page table은 4kb의 크기
• 이는 정확히 한 개의 frame에 들어갈 수 있는 크기

위에서 봤던 것처럼 32bit의 경우에는 page가 총 1,024개가 나오므로, outer-page table는 2^10(1,024)개의 index를 가지게 된다.

따라서 다음과 같이 앞 bits 10개를 outer-page table의 index로 사용, 뒤 bits 10개를 page table의 offset으로 사용

 

💡 outer-page table의 entry의 개수가 1,024개이므로 기존 page number에서 1,024를 나누면 해당 page number가 outer-page table의 몇 번째 entry에 있는지 알 수 있고, 나머지 값으로 해당 entry에 포함되는 page table number 중 몇 번째인지 알 수 있다.

단점

level이 올라갈수록 memory access가 증가된다는 문제가 있다.

• k-level page : (k+1)번의 memory operation
• 64bits OS에서는 48bits address space를 사용하기 때문에 4-levels page 사용
  ⇒ TLB를 사용 : TLB 덕분에 level이 높아도 성능 하락이 크게 없다

Hashed page tables

p값을 hashing해 해당 hash값으로 바로 frame address가 나오는 hash table을 사용

1. logical address에서 page num을 얻는다.
2. page num을 hashing해 값을 얻는다.
3. hash table에서 page num hash값에 해당하는 frame address를 얻는다.
4. frame address와 offset을 concat해 physical address를 얻는다.

• hash는 기본적으로 $O(I)$이기 때문에 memory access가 2번밖에 안 일어나 hierarchical paging보다 좋지만, collision이 발생하게 되면 더 많은 memory access가 발생하게 된다.
• collision은 일반적으로 chaining을 사용
• hash값은 일반적으로 uniform, random해야 한다.
• hash bucket이 충분히 커야 collision이 발생하지 않는다.
  • modulo의 n값을 키우면 된다. ⇒ 즉 address space가 충분히 클 경우 유효

Inverted page table

problem

각 process마다 page table이 할당되어야 하기 때문에 필요한 page 외에는 disk에 저장해야 한다.

⇒ locality 때문에 대부분 memory 접근이지만, 그래도 overhead가 존재

solution

inverted page table에서는 위에서 가끔 발생하는 disk operation의 overhead도 제거할 수 있는 방법을 제시

 

기존

각 process의 page table → physical frame

 

inverted paging

page table에서 해당 frame을 몇 번 process의 몇 번 page가 사용하고 있는지를 mapping

• page table을 memory size에 맞춰 page table을 유일하도록 할 수 있다.

1. 기존 cpu에서 logical address 앞에 pid를 concat해 같이 전달
2. pid와 p을 page table에서 searching한다.
3. seach된 block의 위치값이 frame의 위치와 동일하므로 해당 위치를 그대로 반환

drawback

1. pid | p 값을 page table에서 searching해야 한다.
   • memory access가 매우 많아지기 때문에 hashing을 해야 한다.
2. page sharing이 불가능하다.
   • page table에 pid와 p가 여러개 있을 수 없기 때문이다.
   • 여러 개가 있다해도 다시 searching과정이 필요하기 때문에 실질적으로 사용할 수 없다.

remedy

searching cost를 줄이기 위해 hash table과 TLB를 사용해야 한다.

이러한 단점 때문에 일반적으로 hierarchical paging 기법을 사용

Segmentation

page의 경우 의미적인 단위로 분할할 수 없다.

의미적으로 자른다면 특정 기능이나 부분에 대해서만 공유가 가능하다.

segment는 각 process 별 필요한 영역을 할당받는다.

segment는 연속적으로 저장하되 각 segment 간에는 비연속적으로 저장될 수 있다.

• segment 번호(segment-number)와 offset과 segment 번호 별 시작 주소(segment table)가 필요
  ⇒ 기존 paging 기법과 동일

1. logical address에서 segmentation id를 얻는다.
   • logical address에서 segmentation number(segmentation table size?)만큼 나누면 몫이 segmentation number, 나머지가 해당 segmentation s에서의 logical address가 된다.
2. segmentation id를 통해 segmentable table에서 limit와 base값을 얻는다.
3. limit값과 offset을 비교해 오류 체크
4. segment 내부는 contiguous하기 때문에 단순히 base값과 offset을 더해서 최종 physical address를 얻는다.

segmentation architecture

protection

• 의미 단위의 공유가 가능하기 때문에 각 영역별로 접근 관리를 할 수 있다.

sharing

• 필요한 segmentation만 각 process의 segmentation-table에 공유할 수 있다.

allocation

1. dynamic-storage allocation problem이 발생
   • 각 process 별 크기가 다르게 할당되기 때문에!

fragmentation

• external fragmentation은 증가, internal fragmentation은 감소

Segmentation with Paging

segmentation으로 세부 분류한 뒤, 해당 segmentation을 paging기법으로 적재

• external fragmentation은 감소, internal fragmentation은 증가
  ⇒ 일반적인 internal fragmentation보다 조금 더 증가된다.

1. segmentation numer와 STBR값을 더해 segmentable table에서 length와 base를 얻는다.
2. length와 segmentation offset을 비교해 에러 검출
3. segmentation offset을 다시 나눠 page number와 page offset을 구한다.
4. page table base에 p값을 더해 random access해 frame address를 구한다.
5. frame address과 page offset을 concat해 최종 physical address를 구한다.

segmentation with paging + TLB

 

참고

- Operating System Concepts

- 운영체제, 한양대학교 강수용 교수님