운영체제 - 가상 메모리 관리

요구 페이징

• 프로세스를 구성하는 모든 페이지를 물리 메모리로 가져오지 않고 프로세스가 요구하는 페이지만 물리 메모리로 가오고 나머지 페이지는 swap 영역에 저장하는 가상 메모리 관리 방법
• 장점 - 메모리 절야그 적은 I/O로 인한 응답속도 향상
• Pre-paging과 비교
  • demand paging - 프로세스가 요구하는 페이지만 물리 메모리로 가져옴
  • Pre-paging - 프로세스가 요구할 것이라고 예상되는 페이지를 미리 물리 메모리로 가져옴
  • 현대 OS는 가상 메모리를 관리하기 위해 pre-paging보다 요구 페이징을 기본으로 사용
• 페이지가 swap 영역에 있는 경우
  • 처음부터 HDD에서 필요한 페이지만 물리 메모리에 올라가고 나머지 페이지는 swap 영역에 저장되는 경우
  • 물리 메모리가 꽉 찼을 경우
• Page table entry(PTE) 구조
  • Page 번호 - 직접 매핑에서는 필요 없으나 연관 매핑에서는 필요
  • frame 번호 - 페이지가 물리 메모리에 있을 경우와 페이지가 swap 영역에 있을 경우로 나뉨
  • flag bit - access bit, modify bit, valid bit, read, write, execute bit
• 페이지 부재 - 프로세스가 요구하는 페이지가 물리 메모리에 없고 swap 영역에 있는 경우
  • 프로세스가 요구하는 페이지의 valid bit = 0인 경우
• 페이지 교체 알고리즘 - Page fault로 인해 프로세스가 요구하는 페이지를 swap in 할 때, 물리 메모리가 꽉 찬 경우라면 대상 페이지를 물리 메모리에서 swap 영역으로 보내고 프로세스가 요구하는 페이지를 swap 영역에서 물리 메모리로 가져옴
  
  • 목적 - 대상 페이지를 잘 선택해서 낮은 page fault rate 제공
• 페이지 교체 알고리즘
  • 간단한 알고리즘 - Random, FIFO
  • 최적 알고리즘 - 최적
  • 최적 근접 알고리즘 - LRU, LFU, NUR

Random 페이지 교체 알고리즘

• 임의로 정한 페이지를 swap out 함
• 알고리즘 성능이 좋지 않음

FIFO 페이지 교체 알고리즘

• 가장 먼저 swap in한 페이지를 가장 먼저 swap out 함
• 단점 - 가장 오래된 페이지도 메모리 상에서 자주 사용될 수 있음 -> page fault rate를 증가시킬 수 있음

최적 페이지 교체 알고리즘

• 미래에 가장 오랫동안 사용되지 않을 페이지를 swap out함
• 단점 - 이론적으로 가장 좋은 성능을 보이지만 미래의 페이지 사용을 예측할 수 없어 실제로 구현 불가능

LRU 페이지 교체 알고리즘

• 최근에 가장 오랫동안 사용되지 않은 페이지를 swap out함
• 성능 - FIFO 페이지 교체 알고리즘보다 우수
• 접근 시간에 기반한 구현
• 단점 - 각 페이지의 접근 시간을 PTE에 저장하기 위한 추가적인 메모리가 요구(메모리 낭비 초래)

LFU 페이지 교체 알고리즘

• Counter에 기반한 구현 - 페이지에 접근하면 CPU의 clock은 해당 페이지의 counter에 복사됨
• 가장 작은 counter를 가진 페이지를 swap out 함
• 단점 - 각 페이지의 counter을 PTE에 저장하기 위한 추가적인 메모리가 요구됨

NUR 페이지 교체 알고리즘

• 각 페이지의 PTE 내의 access bit와 modify bit 사용
• 대상 페이지 선정 순서 - level이 작을 수록 가장 먼저 대상 페이지로 선정되어 swap out됨
• 장점 - 메모리 낭비가 적음

Thrashing

• 많은 프로그램 동시에 물리 메모리에 올림 -> 물리 메모리 부족-> swap 영역으로 보냄 -> 잦은 page fault 발생 -> 잦은 page 교체 발생 -> CPU에 의해 프로그램을 실행하는 것보다 MMU에 의해 잦은 page 교체가 발생하여 CPU 사용률이 급격히 저하