[OS] 가상 메모리 관리(2) - 페이지 교체 기법들

1. Fixed allocation의 경우

Page Frame 수가 고정되어 있는 경우에 사용 가능한 알고리즘들을 소개한다.

​

1) Min Algorithm

- Minimize page fault, Optimal solution

- 앞으로 가장 오랫동안 참조되지 않을 Page를 교체

- Page reference string을 미리 알고 있어야 하기 때문에 실현 불가능한 기법

- 교체 기법의 성능 평가 도구로 사용됨

- Tie-breaking rule이 필요할 수 있음

※ Tie-breaking rule : 우선 순위가 동일할 경우 그들을 구분할 규칙

​

2) Random Algorithm

- 교체할 Page를 무작위로 선택

- Overhead가 낮음

​

3) FIFO Algorithm

- 가장 오래된 Page를 교체

- Page가 적재된 시간을 기억하고 있어야 함

- 자주 사용되는 Page가 교체될 수 있음

- Locality가 고려되지 않음

- FIFO anomaly(Belady's anomaly) 발생 가능

※ Belady's anomaly : 더 많은 page frame을 할당 받음에도 불구하고 page fault의 수가 증가하는 이례

​

4) LRU(Least Recently Used) Algorithm

- 가장 오랫동안 참조되지 않은 Page를 교체

- Locality가 고려됨

- Page 참조 시마다 시간을 기록하기 때문에 Overhead가 크지만, 순서만 기록하는 방법으로 해소 가능함

- Loop 실행의 경우에 page fault가 참조 시마다 발생할 수 있음

- 성능이 좋기 때문에 실제로 가장 많이 활용됨

​

5) LFU(Least Frequently Used) Algorithm

- 가장 참조 횟수가 적은 Page를 교체

- Locality가 고려됨

- Page 참조 시마다 참조 횟수를 누적시키기 때문에 Overhead가 큼

- Tie-breaking rule이 필요할 수 있음

​

6) NUR(Not Used Recently) Algorithm

- LRU의 Overhead를 줄이기 위해 고안된 기법

- 최근에 사용되지 않은 Page를 교체

- Reference bit vector(r), Update bit vector(m) 사용{교체 우선 순서 : (0, 0)>(0, 1)>(1, 0)>(1, 1)}

※ r : 최근에 주기적 초기화가 발생했는지에 대한 여부를 알 수 있으며, 0은 참조된지 어느 정도 시간이 지난 상태임

※ m : Page frame에 적재된 이후의 업데이트 여부를 알 수 있으며, 0은 추가적인 참조가 일어나지 않은 상태임

​

​7) Clock Algorithm

(1) 특징

- Page frame들을 순차적으로 가리키는 pointer(시계 바늘)를 사용하여 교체될 Page를 결정

- 먼저 적재된 page가 교체될 가능성이 높음

​​- Reference bit(r)만 사용

 

(2) 한 Page당 동작

Page가 성공적으로 할당될 때까지 아래 과정을 반복한다.

<1> 해당 Page가 Page Frame에 적재되어 있는가?

▣ True : 적재된 Page의 r값을 1로 설정, <3>으로 이동
▣ False : <2>로 이동

<2> 현재 pointer가 가리키는 Page의 r값은?

▣ r=0 : 해당 Page를 교체하고 r값을 1로 설정, <3>으로 이동
▣ r=1 : r값을 0으로 초기화, <3>으로 이동

<3> 현재 pointer가 가리키는 page frame에 변화가 일어났는가? (페이지 교체 혹은 비트 값 변경)

▣ True : Pointer 이동
▣ False : Pointer 고정

 

​8) Second Chance Algorithm

(1) 특징

- Clock Algorithm에 Update bit(m)를 추가

- 2번의 기회 부여

 

(2) 한 Page당 동작

Page가 성공적으로 할당될 때까지 아래 과정을 반복한다.

<1> 해당 Page가 Page Frame에 적재되어 있는가?

▣ True : 적재된 Page의 r값을 1로 설정, m값 설정 후 <3>으로 이동
▣ False : <2>로 이동

<2> 현재 pointer가 가리키는 Page의 (r, m)값은?

▣ (0, 0) : 해당 Page를 교체하고 r값을 1로 설정, m값 설정 후 <3>으로 이동
▣ (0, 1) : m값을 0으로 초기화, Write-back 리스트에 추가 후 <3>으로 이동

▣ (1, 0) : r값을 0으로 초기화, <3>으로 이동

▣ (1, 1) : r값을 0으로 초기화, <3>으로 이동

<3> 현재 pointer가 가리키는 page frame에 변화가 일어났는가? (페이지 교체 혹은 비트 값 변경)

▣ True : Pointer 이동
▣ False : Pointer 고정

 

​​9) Other Algorithms

- Additional-reference-bits Algorithm

- MRU(Most Recently Used) Algorithm

- MFU(Most Frequently Used) Algorithm

​

 

2. Variable Allocation의 경우

Page Frame 수가 고정되어 있지 않은 경우에 사용 가능한 알고리즘들을 소개한다.​

 

1) WS(Working Set) Algorithm

(1) Working set이란?

- 프로세스가 [t-△, △] 동안에 참조하는 Page들의 집합 (대괄호는 양 끝점을 포함)

- W(t, △) [t: 현재 시각, △: 일정 시간(window size, system parameter)]

- 시간에 따라 변함

※ △와 Working set의 크기는 비례한다.

 

(2) 특징

- Locality 기반

- Working set은 메모리에 항상 유지됨

- Page fault rate (thrashing) 감소

 

(3) 예제

 

(4) 성능 평가 : 평균적으로 할당받은 Page frame의 수까지 고려하여 성능을 평가해야 함

※ total cost = cost(page fault) * page fault + cost(page frame) * page frame 

 

(5) 문제점 : Page fault가 없더라도 Working set을 지속적으로 관리하는 Overhead가 발생함

 

2) PFF(Page Fault Frequency) Algorithm

(1) 특징

- Working Set Algorithm에서 Set의 지속적인 관리에 따른 Overhead 발생 문제를 해소하는 기법

- Page fault가 발생했을 때에만 Set을 갱신하기 때문에 Overhead가 낮아짐

- Page fault rate가 높을 때는 Page frame 수를 증가시키고, Page fault rate가 낮을 때는 Page frame 수를 감소시킴

※ τ(tau) : page fault rate 기준

 

(2) 한 Page당 동작

<1> Page fault 발생 시, 이전에 발생한 Page fault와의 시간 차이를 계산 하고 <2>로 이동

<2> 방금 계산한 시간 차이가 τ보다 큰가?

▣ True : 이전 Page fault의 전에 최근 참조된 page들을 메모리에서 내리고, Page frame 수는 유지 혹은 감소

▣ False : Page frame 수를 늘리고 현재 참조된 Page를 추가로 적재

 

(3) 예제

 

(4) 성능 평가 : Working Set Algorithm과 동일

 

3) VMIN(Variable MIN) Algorithm

(1) 특징

- 평균 메모리 할당량과 page fault 발생 횟수를 모두 고려했을 때 최적의 경우를 구하는 기법

- Page reference string을 미리 알고 있어야 하기 때문에 실현 불가능함

- [t, t+△] 을 고려해서 교체할 page를 선택

- 성능 평가 기준으로 사용 가능

 

(2) 한 Page당 동작

Page가 현재 시간 t에 참조 되면, 이 Page가 (t, t+△] 사이에 다시 참조되는지 확인

▣ True : 다음 시간에도 이 Page를 유지

▣ False : 다음 시간으로 넘어갈 때 이 Page를 메모리에서 내림

 

(3) 예제

 

(4) 성능 평가 : Working Set Algorithm과 동일

 

(5) 최적의 성능을 위한 △값

△ = (Page fault 발생 시 처리 비용) / (Page를 메모리에 유지하는 비용)

-> △가 클수록 Page fault는 적게 발생하지만, Page frame 수는 증가하기 때문

 

 

이미지 출처 : 한빛 미디어 운영체제

참고 자료 : 김덕수 교수님 - www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN