가상메모리
물리적 메모리 크기의 한계를 극복하기 위해 나온 기술로 실행에 필요한 일부만 메모리에 로드하고 나머지는 디스크에 보관.
→ 필요한 page만 메모리에 올리는 것을 Demand Paging
Demand Paging
실제로 필요한 page만 메모리에 올리는 것.
CPU 이용률과 처리율이 높아지고, 더 많은 사람들이 수용할 수 있다.
page table에서 해당 page가 메모리에 있는 지를 나타내는 valid-invalid bit를 사용한다.
valid-invalid = 현재 페이지가 메모리에 있다면 1, 없다면 0
→ page entry가 invalid로 초기화되어 있고, 주소 변환시 bit가 invalid로 되어있다면 page fault라는 오류 발생
Page Fault
CPU가 접근하려는 페이지가 메모리에 없는 경우 발생. 즉 valid bit이 0인 경우
- 해당 페이지가 메모리에 있는지 valid bit 확인
- valid bit가 0이라면 CPU에 인터럽트 신호를 보내어 운영체제 내부에 해당 ISR로 점프
- 해당 ISR에서 backing store(디스크)를 탐색하여 해당 프로세스의 페이지를 찾음
- 비어있는 프레임에 할당 → 비어있지 않다면 Page Replacement
- 새로운 Page를 할당했으니 해당 Page의 valid-invalid bit을 업데이트 한다.
- 다시 명령어로
Page Replacement
Page fault가 발생하여 새로운 페이지를 디스크에서 가져와서 Memory에 저장해야하는데 만약 모든 메모릭 사용중이라면 이 중 하나를 다시 backing store로 보내고 새로운 페이지를 메모리에 올려야 한다(page in)
→ 이 과정을 Page Replacement라 하고 이때 Page out된 페이지를 Victim Page라고 한다.
Victim Page
Victim page를 선정할 때 메모리에 올라간 페이지 중 CPU에 수정(modify)되지 않는 페이지를 고르는 것이 효율적으로 보인다. 수정되지 않은 페이지는 page-out이 될 때 backing store에 쓰기(write) 연산을 할 필요가 없어서 시간이 덜 소요된다.
수정되었는지를 판단하기 위해 페이지 테이블에 modified bit(=dirty bit)을 추가하여 검사한다. 해당 페이지가 수정되었다면 비트를 1로 주고, 수정되지 않으면 0으로 둔다. victim을 선정할 때 최대한 수정되지 않은 페이지를 선택한다.
Page Replacement Algorithm
page referenece : 1 2 3 4 1 2 5 1 2 3 4 5
OPT(Optimal Algorithm)
: Optimal Algorithm은 가장 먼 미래에 참조되는 page를 대체하는 방법 → 항상 최적의 결과를 가짐
미래의 참조를 모두 알고 있어야 하므로 실제로는 사용하기 힘들다.
FIFO(First in First out) Algorithm
: FIFO 알고리즘은 제일 먼저 들어온 것을 먼저 쫒아내는 방법
모든 page가 평등하게 frame에 거주하며, 구현하기 쉽다는 장점이 있지만 어떤 page는 항상 필요할 수 있는데, 그런 경우에도 replace를 시킨다는 단점
FIFO는 frame이 늘어나도 page fault가 감소하지 않고 오히려 늘어나는 경우가 존재하는 Belady’s anomaly 현상이 발생
→ 일반적으로 frame이 증가하면 page fault가 감소하지만 특정 구간에서 오히려 증가하는 경우가 발생한다.
LRU(Least Recently Used) Algorithm
: 가장 오래전에 참조된 것을 지우는 방법
Optimal에 근접한 방법이며, Belady’s anomaly가 발생하지 않는다. 다만 구현하기가 어렵고 빈도를 고려하지 않는다는 단점.
연결 리스트로 LRU를 구현하면 O(1)만에 page를 찾고 삽입할 수 있다. 가장 최근에 참조된 page를 가장 앞으로 옮기는 방식으로 연결 리스트 구현하면 replace가 발생할 때 가장 뒤에 page를 바꿔주면 된다.
FIFO보다 우수하고, OPT 보다는 그렇지 못함
LFU(Least Frequently Used) Algorithm
: 참조 횟수가 가장 적은 page를 지우는 방법
- 최적 페이지 교체하지 못함
MFU(Most Frequently Used) Algorithm
: 참조 횟수가 가장 적은 페이지가 최근 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정
Allocation of Frames
여러개의 프로세스가 메모리 할당을 해야할 경우에 프로세스마다 균일하게 할당하거나 특정 기준에 따라 할당하는 방법으로 나뉜다
균일 : frame수/프로세스 수
특정 기준: 프로세스의 크기나 우선순위에 따라서 크거나 우선순위가 높다면 더 많은 frame 할당
프로세스가 Page Fault를 발생시켰을 때 대체될 frame 그룹에 따라 Global replacement/Local replacement로 나뉨
Global Replacement : Replace할 때 다른 프로세스에 할당된 frame을 빼앗아올 수 있음.
→ 일반적으로 더 좋은 처리량을 가지고 있으므로 흔하게 사용되는 방법
Local Replacement : 자신에게 할당된 frame내에서만 교체하는 방법
→ 알고리즘을 프로세스마다 독자적으로 운영하는 경우 가능한데 쉬고 있는 메모리를 사용할 수 없어서 비효율적
