OS - Main Memory part 2

TLB(Translation Look aside Buffer)

• page table을 사용함에 있어 메모리 접근 횟수를 줄이기 위해 사용한다.

• 자주 사용되는 메모리에 대한 정보를 Cache에 넣어 관리한다.
  - CPU 안의 MMU에 상주한다.
  

• (Temporal) Locality를 이용한다.

• Fully associative cache

  Associative Memory

  • Parallel하게 search한 후, 짝을 이루는 값을 도출한다.
  • CAM(Content Addressable Memory)

• Cache tag는 logical page number이며, value는 PTEs이다.

• MMU는 PTE + offset으로 물리 주소를 계산한다.

• TLB miss가 나면 page table을 참조한다.

  • Fault를 발생시켜 OS가 개입할 수도 있지만, 현재의 System은 CPU의 MMU가 처리한다.

Memory protection

• Page table에 valid / invalid bit로 표현한다.
• Page number에 해당하는 값이 invalid이면 fault를 발생시켜 메모리를 보호
  • 참조할 수 없는 영역의 메모리를 참조 : Memory protection fault

Page Table Entries (PTEs)

• Valid bit (V) says whether or not the PTE can be used : 1bit
• Reference bit (R) says whether the page has been accessed : 1bit
• Modify bit (M) says whether or not the page is dirty : 1bit
• Protection bits (Prot) control which operations are allowed on the page : 2bit
  • 해당 frame이 READ/WRITE/EXECUTE가 가능한지를 표시한다.

Page table structure

• Page table의 공간적 overhead가 너무 크다
  • 메모리를 적게 쓰더라도 최악의 경우를 가정하여 table을 크게 만든다.

Overhead를 줄이는 방법

• Observation : 실제로 사용하는 address space의 부분만을 mapping에 사용한다
  • Page table structure를 동적으로 확장 가능하게 만든다.

Hierarchical page tables

• page number를 2단계로 나눈다.
• page number로 다시 page number를 찾고 다시 frame nubmer를 찾아 offset을 더하는 방법

Single-level의 경우

• 항상 4MB가 필요하다.

Two-level paging의 경우

• 메모리를 많이 사용하는 경우

• Outer page table : int의 경우 4KB 필요

• Page table : 4MB 필요
  → Single-level보다 성능이 나쁘다
  

• 메모리를 적게 사용하는 경우

• Outer page table : 4KB 필요

• Page table : 4KB 필요

• 필요할 때마다 동적으로 추가한다.
  → Single-level page보다 효율적

Hash page table

• 성능상의 문제로 사용되지 않는다
  

• Hash table의 값이 같은 것을 순차적으로 기록하고 linked list로 연결한다
  → 오버헤드가 커서 사용하지 않는다.

Inverted page table

• 성능상의 문제로 사용되지 않는다
  
• Page table에 frame별로 프로세스와 page number를 저장한다.
• Physical memory마다 하나만 있으면 되지만, 모든 프로세스를 검사해야 하므로 성능상의 문제가 생긴다.

Shared page

• Page가 shared memory를 만들기에 적합하다.
  

• page가 공통적으로 사용하는 부분은 중복되지 않게 메모리에 올려 메모리 효율을 올릴 수 있다.

Advantages of paging

• 쉽게 physical memory에 할당할 수 있다.
  • Frame의 free list에 physical memory를 할당하면 된다.
• External fragmentation이 발생하지 않는다.
• Page를 share하기 좋다.
• Memory protection도 쉽게 이루어진다.
• Page가 같은 사이즈를 갖고 있으며, invalid를 통하여 page out된 것을 쉽게 찾을 수 있다.

Disadvantages of paging

• Internal fragmentation을 가지고 있다.
• 2번의 메모리 참조가 필요하다 → TLB로 해결

Segmentation

• Logical address를 고정 크기로 page를 나누면 READ / WRITE 등 이용이 달라지는 부분이 존재한다.
  • 의미 있는 단위로 분할 : code segment / data segment / stack segment / extra로 분할
• segment 단위로 contiguous allocation
  - External fragmentation 문제 발생
  

Advantages of Segmentation

• 줄어들거나 커지는 데이터 구조를 다루기 쉽다.
• Protection bit(WRITE/READ/EXECUTE)를 보호하기 쉽다.
• Segment를 share하기 쉽다.
• Internal fragmentation이 발생하지 않는다.

Disadvantages of Segmentation

• External fragmentation이 발생한다.
• Segment table을 크게 유지하여야 한다.
• Cross-segment address : segment를 공유하려면 같은 segment 번호를 가져야 한다.

Paging vs. Segmentation

Segmentation with Paging

• 의미 있는 단위로 나누기 위해 segment 단위로 나눈다.
• Segment를 고정 크기의 page로 분할한다.
  • External fragmentation이 발생하지 않는다.
• CR3 register : MMU가 사용하는 레지스터, Page directory의 시작 주소를 찾아간다.
  
• Selector : segmentation
• Directory : outer page
  • Two – level paging

IA-32 PAE

• Page-table을 3단계로 하여 64GB까지 Physical memory를 사용 가능하게 했다.

x86-64

• 4 level page table / 48-bits addressing
• Can also use PAE (up to 52-bits physical address)

ARM

• Segmentation 없이 multiple page size로 문제를 해결한다.