운영체제(14) - 가상 메모리 (Virtual Memory)

Virtual Memory

• 운영체제에서 실제 물리 메모리 (RAM)보다 큰 주소 공간을 프로세스에 제공하기 위해 사용되는 기술
• 가상 메모리의 주소와 실제 메모리의 주소는 일치하지 않는다
  • 그렇기에 가상 메모리의 주소와 실제 메모리 주소를 1:1 대응 시켜야 하는데 이걸 해결해주는 것이 MMU(Memory Management Unit)이다.

 

Demand paging

 

• 실제로 필요할 때 page를 메모리에 올리는 것
  1. I / O 양의 감소
  2. Memory 사용량 감소
  3. 빠른 응답 시간
  4. 더 많은 사용자 수용
• Valid / Invalid bit의 사용
  • Invalid의 의미 -> 사용되지 않는 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry가 invalid로 초기화
  • address translation 시에 invalid bit이 set되어 있으면 => page fault
• Invalid page를 접근하면 MMU가 trap을 발생시킴 (page fault trap). Kernel mode로 들어가서 page fault handler가 invoke됨

프레임은 물리 메모리를 일정한 크기로 나눈 블록이고, 페이지는 가상 메모리를 일정한 크기로 나눈 블록이다.

페이지가 하나의 프레임을 할당 받으면, 물리 메모리에 위치할 수 있게 된다.

프로그램을 실행하기 위해 요청한 page가 메모리에 있는지 없는지를 확인하기 위해 page table에 valid-invalid bit를 추가하여 확인한다. 만약 있다면 valid고 없다면 invalid로 세팅된다. 없을 때를 page fault라고 부른다.

page fault가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때, 물리적 메모리에 빈 프레임이 존재하지 않으면 메모리에 이미 있는 페이지 중 하나를 디스크로 쫓아내어 빈 공간을 확보해야한다.

이 작업을 Page replace, 즉 페이지 교체라고 한다!!

Page replace algorithm에는 ....

Optimal Algorithm

• MIN(OPT) : 가장 먼 미래에 참조되는 page를 replace
• 미래의 참조를 어떻게 아는가? Offline algorithm
• 다른 알고리즘의 성능에 대한 upper bound 제공
  
  • 아무리 좋은 알고리즘이어도 이걸 뛰어넘을 수 없다.

FIFO ( First In First Out ) Algorithm

• 먼저 들어온 것을 먼저 내쫓음
• FIFO Anomaly ( Belady's Anomaly) => 프레임의 개수가 많아져도 page - fault가 줄어들지 않고 늘어나느 현상

LRU ( Least Recently Used ) Algorithm

• 가장 오래전에 참조된 것을 지움
• O(1) complexity

LFU ( Least Frequently Used ) Algorithm

• 참조횟수 ( reference count)가 가장 적은 페이지를 지움
• 최저 참조 횟수인 page가 여럿 있는 경우 ....
  • LFU 알고리즘 자체에서는 여러 page중 임의로 선정
• 장점
  • 힙으로 구성시엔 O(log n ) complexity , 아닐시엔 O(n)
  •  장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
• 단점
  • 참고 시점의 최근성을 반영하지 못함
  • LRU보다 구현이 복잡