[OS] 10. 가상 메모리 관리 - Replacement Strategies for Fixed Allocation

Software Components

가상 메모리 성능 향상을 위한 관리 기법들

• Allocation strategies 
• Fetch strategies 
• Placement strategies 
• Replacement strategies 
• Cleaning strategies 
• Load control strategies 

 

Locality

프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상

 

원인

• Loop structure in program
• Array, structure등의 데이터 구조

공간적 지역성(Spatial locality): 참조한 영역과 인접한 영역을 참조하는 특성

시간적 지역성(Temporal locality): 한 번 참조한 영역을 곧 다시 참조하는 특성

 

Locality (Example)

가정...

• Paging system
• Page size = 1000 words
• Machine instruction size = 1 word
• 주소 지정은 word단위로 이루어짐
• 프로그램은 4번 page에 continuous allocation 됨
• n = 1000

메모리가 어떻게 접근되는지 확인해보자

• w = 494944(47484644)^1000
• 9000번의 메모리 참조 중 5개의 page만을 집중적으로 접근하게 됨
• 4, 6, 7, 8, 9번 페이지만 집중적으로 접근 => Locality가 있음을 확인

Locallity를 최대로 활용하면 성능을 높일 수 있다.

 

Replacement Strategies

• Fixed allocation (각 프로세스에게 정해진 frame 수를 할당)
  • MIN(OPT, B0) algorithm
  • Random algorithm
  • FIFO(First In First Out) algorithm
  • LRU(Least Recently Used) algorithm
  • LFU(Least Frequently Used) algorithm
  • NUR(Not Used Recently) algorithm
  • Clock algorithm
  • Second chance algorithm
• Variable allocation
  • WS(Working Set) algorithm
  • PFF(Page Fault Frequency) algorithm
  • VMIN(Variable MIN) algorithm

 

Min Algorithm (OPT algorithm)

• 1966년 Belady에 의해 제시됨
• page fault의 빈도수를 최소로 낮추는 것 (optimal solution)
• 기법: 앞으로 가정 오랫동안 참조되지 않을 page교체
  • Tie-breaking rule: page번호가 가장 큰/작은 페이지 교체
• 실현 불가능한 기법 (unrealizble) - Page reference string을 미리 알고 있어야 함
• 교체 기법의 성능 평가 도구(기준)로 사용 됨

• 현재 시점 page W에서 시작
• page frame이 다 차있어 x,y,z중 하나를 교체해야함
• 미래에 참조하는 것을 알면 y를 교체할 것임(y가 가장 마지막에 사용됨) => Min algorithm

Example

4개의 페이지 프레임을 프로세스에게 할당받았다고 하자 (초기에는 비어있음)

w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5

Number of page faults = 6

Random Algorithm

• 무작위로 교체할 page선택
• Low overhead
• No policy

FIFO Algorithm

• First In First Out (가장 오래된 page를 교체)
• Page가 적재 된 시간을 기억하고 있어야 함
• 자주 사용되는 page가 교체 될 가능성이 높음 - Locality에 대한 고려가 없음
• FIFO anomaly (Belady's anomaly)
  • FIFO 알고리즘은, 더 많은 page frame을 할당 받음에도 불구하고 page fault의 수가 증가하는 경우가 있음

교체하면 z를 교체할 것 (가장 먼저 들어와서)

Example

4개의 페이지 프레임을 프로세스에게 할당받았다고 하자 (초기에는 비어있음)

w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5

Number of page faults = 10

Example(FIFO anomaly)

메모리를 더 줬는데(자원을 늘렸는데) 성능이 하락한다(page fault 증가) => Locallity를 고려하지 않았기 때문

Number of page faults = 9 ,  Number of page faults = 10

 

LRU(Least Recently Used) Algorithm

• 가장 오랫동안 참조되지 않은 page를 교체(Locality고려)
• Page 참조 할 때 마다 시간을 기록해야 함
• Locality에 기반을 둔 교체 기법
• MIN algorithm에 근접한 성능을 보여줌
• 실제로 가장 많이 활용되는 기법

x가 마지막에 참조되었다면 교체 하겠다는 뜻

 

단점

• 참조할 때 마다 시간을 기록해야 함 (Overhead)
  • 간소화된 정보 수집으로 해소 가능 (Ex. 정확한 시간 대신, 순서만 기록)
  • Loop 실행에 필요한 크기보다 작은 수의 page frame이 할당 된 경우, page fault수가 급격히 증가함
    • Ex. loop를 위한 |Ref. String| = 4 / (할당된 page frame이 3개)
    • Allocation기법에서 해결해야 함 (전체 page frame수를 4개로 늘리면 됨)

Example

4개의 페이지 프레임을 프로세스에게 할당받았다고 하자 (초기에는 비어있음)

w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5

Number of page faults = 7

 

LFU(Least Frequently Used) Algorithm

• 가장 참조 횟수가 적은 Page를 교체 (Tie-breaking rule: LRU)
• Page 참조 시 마다, 참조 횟수를 주거 시켜야함
• Locality활용 => LRU 대비 적은 overhead
• 단점
  • 최근 적재된 참조될 가능성이 높은 page가 교체 될 가능서잉 있음
  • 참조 횟수 누적 overhead

Example

4개의 페이지 프레임을 프로세스에게 할당받았다고 하자 (초기에는 비어있음)

w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5

Number of page faults = 7

 

NUR(Not Used Recently) Algorithm

• LRU 보다 적은 overhead로 비슿한 성능 달성 목적
• Bit vector 사용 (Rererence bit vector(r)(참조비트), Update bit vecotr(m)(변형비트))
• 참조 비트와 변형비트의 값에 따라 교체순서가 결정됨
  1. (r, m) = (0, 0)
  2. (r, m) = (0, 1)
  3. (r, m) = (1, 0)
  4. (r, m) = (1, 1)

Clock Algorithm

• NUR을 실제로 적용한 알고리즘 (IBM VM/370 OS)
• Reference bit 사용함 (주기적인 초기화 없음)
• Page frame들을 순차적으로 가리키는 pointer(시계바늘)를 사용하여 교체될 page결정

시계바늘이 돌아가는 알고리즘

reference bit들이 전부 1이면, 해당 시침이 지나갈 때 해당 reference bit를 0으로 바꾸고 다음에 시침이 해당 page를 가르키면 그 때 초기화를 한다.

• Pointer를 돌리면서 교체 page결정
  • 현재 가리키고 있는 page의 reference bit(r) 확인
  • r=0인 경우, 교체 page로 결정
  • r=1인 경우, reference bit 초기화 후 pointer이동
• 먼저 적대된 page가 교체될 가능성이 높음 (FIFO와 유사함)
• Reference bit를 사용하여 교체 페이지 결정 (LRU(or NUR)과 유사) (Locality 반영)

Example

4개의 페이지 프레임을 프로세스에게 할당받았다고 하자, 초기 a, b, c, d를 가지고 있음

w = c a d b e b a b c d

시계바늘이 돌면서 후보를 찾는 알고리즘..

실행 과정

1. Time = 4 ->5일 때 시계침이 a를 가리키다 b를 가리킴 a를 가리킨 시계침은 0으로 바꿈
2. b, c, d를 0으로 바꾸고 a로 오게됨 (a/0, b/0, c/0, d/0)
3. a가 0이므로 교체하고 e가 들어감
4. e를 참조했으니 1로 바뀜
5. Time = 6 에서 b를 참조할 것이므로 b를 0에서 1로 바꿈
6. Time = 7 에서 a를 참조하려고 하였으나 없으므로 참조되지 않은 c를 a로 바꾸고 a를 참조 했으니 1로 바꿈
7. Time = 9, 에서 c를 참조하려고 하였으나 없으므로 참조되지 않은 d를 c로 바꾸고 c를 참조했으니 1로 바꿈
8. Time = 10, 에서 는 1,2,3,4 과정을 수행하여 d/1, b/0, a/0, c/0을 나타냄

 

Second Chance Algorithm

• clock algorithm과 유사
• Update bit(m)도 함께 고려함 => second change algorithm인 이유
  • 현재 가리키고 있는 page의 (r, m) 확인
  • (0, 0): 교체 page로 결정
  • (0, 1): ->(0, 0), write-back (cleaning) list에 추가 후 이동
  • (1, 0): ->(0, 0) 후 이동
  • (1, 1): ->(0, 1) 후 이동

 

Example

4개의 페이지 프레임을 프로세스에게 할당받았다고 하자, 초기 a, b, c, d를 가지고 있음

a^w의 w는 write opration을 의미 (update bit가 1이 되어야 한다)

실행과정

1. Time = 4 -> 5 에서 e가 들어와야 한다. 
2. a/11, b/11, c/10, d/10 에서 reference bit가 1이므로 0으로 바꾼다. => a/01, b/01, c/00, d/00
3. 시계 침이 a로 돌아와서 a/01을 가르킴
4. a/01의 1(update bit)을 write-back 리스트에 넣어준 후 0으로 바꿈
5. b/01의 1을 write-back 리스트에 넣어준 후 0으로 바꿈
6. c는 00이므로 e로 바꾼 후 e/00에서 참조했으므로 e/10으로 바꿈
7. T = 6, b를 읽어야 하므로 b의 reference bit를 1로 바꿈 b/00 -> b/10
8. T = 7, a^w 즉, wrtie operation을 하므로 a/00 -> a/11로 바꿈
9. T = 8, b를 읽으니까 b/00 -> b/10으로 바꿈
10. T = 9, d/00이므로 c/10으로 바꿈
11. T = 10, 1~6과정을 똑같이 수행함. 

 

Other Algorithms

• Additional-reference-bits algorithm
• LRU approximation
• 여러 개의 reference bit를 가짐
  • 각 time-interval에 대한 참조 여부 기록
  • History register for each page
• MRU (Most Recently Used) algorithm - LRU 와 정반대 기법
• MFU (Most Frequently Used) algorithm - LFU와 정반대 기법

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---