운영체제#9

LeeMir, 19 April 2021

3강 - Memory Management(이어서)

Problem : Too Large Page Table
  • Multilevel Page Tables
    • Page Table 사이에 계층이 존재
      • 수많은 Second-Level Page Table 위에 Top-Level Page Table 존재
    • 각 Page의 Size는 보통 4KB(2의 12승)
    • 모든 Page가 존재한다면 메모리를 더 비효율적으로 사용하는 것이지만, Table의 valid가 0이면 그 Page는 존재하지 않음
      • 따라서 안쓰는 공간을 없앰으로써 메모리를 더 효율적으로 사용할 수 있음
    • Logical Address
      • P1 - P2 - d
      • P1, P2 : Page Number
      • d : Page Offset
    • Multilevel의 경우 TLB에 Miss가 있는 순간 여러 단계에 걸쳐 모든 Table을 탐색해야하므로 메모리 효율이 더 나빠질 수 있음
  • Inverted Page Tables
    • 한 System에는 Inverted Page Table이 딱 한 개씩만 존재
    • Inverted Page Table에는 pid와 p가 대응되어있음
      • idx 값이 physical memory의 frame number임
    • 그때마다 Page Table을 탐색하면 효율이 떨어져 한번 찾았던 값을 따로 저장
    • TLB에 Miss가 나서 탐색을 해야하는 경우 메모리 효율이 떨어짐
      • Hash Table 사용
Address Space and OS
  • Process의 상단에는 운영체제(OS)에 있는 Code Data를 가리키는 Address가 존재
    • 이 부분은 모든 Process가 공유
  • Process의 내용을 읽다가 시스템 호출과 마주치면 Interrupt를 걸고 상단에 있는 OS Code Data Address로 이동
    • 이 때 입출력(특권 명령)을 수행하기 위해서는 Interrupt 전후로 Kernel Mode <=> User Mode 필요
Page Fault
  • CPU가 Virtual Address를 Physical Address로 바꾸기 위해서 TLB를 탐색했는데, 그 valid 값이 0이었음
    • Main Memory에 적재되어있지 않고 Disk의 Swap영역에 있다는 뜻
  • 이 때 CPU 차원에서는 할 게 없어 Interrupt를 일으킴
  • OS에서 Disk Swap영역을 탐색해 해당하는 Page를 찾아 Main Memory의 빈 Frame에 넣고 Page Table을 수정 후 Page Fault Return
  • 일반적인 Interrupt와 차이점
    • 일반적인 Interrupt는 발생하면 하던 일을 모두 마치고 Interrupt Handler로 이동, 돌아왔을 때에는 다음 일을 수행
    • Page Fault는 하려던 일을 못해서 발생, 돌아오면 하려던 일을 재개
  • 만약 Main Memory가 꽉차있다면, 기존에 있는 Page를 쫓아내고 빈 Frame을 만듦
    • 쫓아내는 기준은 “교체 정책”에 의해 수행
    • 기존에 한 번 쫓아냈던 Page인데 Page Fault로 인해 다시 적재한다면 매우 비효율적인 일
  • Demand Paging
    • 모든 Page를 Main Memory에 적재하지 않고, Page Fault Handler로 Page가 필요할 때(참조될 때)에만 적재
      • Memory 효율 up
Page Replacement Algorithm(페이지 교체 정책)
  • Optimal
    • 어떤 Page를 참조할지 Pattern을 미리 아는 상황에서 가장 참조 덜되는 Page를 쫓아냄
    • Ideal 하지만 실현 불가능, 다른 알고리즘과 효율성을 비교할 때 사용
  • NRU(Not Recently Used), FIFO
    • Reference Bit : 이 Page는 최근에 참조되었음을 표시
    • Modified Bit : 이 Page는 최근에 수정되었음을 표시
      • 만약 수정되었다면 쫓아낼 때 Disk Swap영역에 수정 내용을 적용해야하는 과정이 생김
    • NRU : 최근에 참조되지 않았으면서, 수정되지도 않은 Page부터 쫓아냄
    • FIFO : 가장 오래된 Page부터 쫓아냄
      • 구현하기 단순함
      • Hot Page(자주 참조되는 Page)가 계속 쫓아질 가능성이 있음
  • Second Chance Algorithm
    • FIFO를 따르되 Ref. Bit가 1이면 0으로 초기화 시킨 후 맨 뒤(front => rear)로 보내서 한번 더 기회를 줌
  • The Clock Page Replacement Algorithm
    • Second Chance Algorithm과 동일하나, Circular 구조
  • LRU Page Replacement Algorithm
    • Top : Most recently used (MRU) page
    • Bottom : Least recently used (LRU) page
    • 참조된 Page는 Top으로 이동
    • 항상 Bottom Page를 교체
    • Software적으로 구현하기도 쉬워 기본 Algorithm으로 각광을 받고 있으나 CPU Cache로 하기는 쉽지 않음
      • 행렬로 만들어 가장 최근에 참조된 Page idx의 행을 1로, 열을 0으로 바꾸면 행의 크기에 따라 Top과 Bottom을 구분할 수 있음
  • NFU(Not Frequently Used)
    • 각 Page마다 그 시점의 Ref Bit를 기록 후 Right Shift(Aging 기법이 추가된 것임)
      • Aging을 하지 않는 NFU는 그냥 Ref Bit를 더해주는 형식
    • 1이 많을수록 많이 참조되었다는 뜻
    • Page 값이 가장 작은 것부터 쫓아냄
    • Page가 많을 수록 Memory의 부담이 커짐
  • Working Set Page Replacement
    • 사용한 Page를 Working Set이라는 단위로 묶음
    • Working Set에 속하지 않는 Page를 쫓아냄
    • 운영체제가 주기적으로 Page Fault Frequency를 측정해 프로세스의 Working Set을 측정할 수 있음
      • Page Fault가 너무 많이 일어나면 Working Set(할당 Page 개수)을 늘려주고 적게 일어나면 Working Set을 줄임
  • Global vs Local Page Replacement
    • Global : 교체할 Page의 범위가 모든 프로세스
    • Local : 교체할 Page의 범위가 해당 프로세스
Load Control
  • Thrashing
    • 여러 프로세스가 돌아가는데 각 프로세스에 할당된 Page의 수가 Working Set을 만족 못할 경우, 프로세스가 수행되는 시간보다 Page 교체 시간이 더 많이 발생, Memory 효율성 현저히 떨어짐
      • 주로 프로세스가 많아지면 발생
    • Swapping
      • 몇 개의 프로세스를 골라 Swap Out한 후, 그 프로세스들이 사용하던 Working Set을 다른 프로세스들에게 나눠줘서 다른 프로세스들이 수행될 수 있게 함