가상 메모리 관리 #2 - Replacement Strategies(Fixed allocation - MIN, Random, FIFO, LRU, LFU, NUR, Clock, Second chance)

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

• 프로그램 : 4번 페이지
• array A : 6번 페이지
• array B : 7번 페이지
• array C : 8번 페이지
• ONE, n : 9번 페이지
• reference string w : 4949 44 (47484644)^1000
  - 4949 : loop 전
  - 44 : loop 시작
  - 47484644 : loop 1000번 반복
• 메모리 참조중 5개 page만을 집중적으로 접근 ( 4, 6, 7, 8, 9번 페이지 ) 
  => locality

---

Replacement Strategies

• Fixed allocation : 프로세스에 고정된 수의 page 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에 의해 제시
• Minimize page fault frequency (proved)
  • Optimal solution
• 기법
  • 앞으로 가장 오랫동안 참조되지 않을 page 교체
    • Tie-breaking rule : page 번호가 가장 큰/작은 페이지 교체
• 실현 불가능한 기법 (Unrealizable)
  • Page reference string을 미리 알고 있어야 함
• 교체 기법의 성능 평가 도구로 사용 됨

• 가장 오래 교체되지않을 y를 교체한다.

 

Example

• 4 page frames for the process, initially empty
• w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5

• time 6 : 가장 나중에 참조될 6번 페이지 교체 6 -> 5
• time 12 : 이후에 1, 2는 참조되지 않는다 -> 규칙에 의해 교체(ex. 작은 번호 교체) 1 -> 6
• 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 page frames for the process, initially empty
• w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5

• Number of page faults = 10

Example (FIFO Anomaly)

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

• 자원 추가 (page frame 추가) 했음에도 page fault 는 오히려 증가하는 경우가 있다.

---

LRU (Least Recently Used) Algorithm

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

단점

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

Example

• 4 page frames for the process, initially empty
• w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5

• time 6 : 가장 오래 참조되지 않은 2 교체 2 -> 5
• time 8 : 가장 오래 참조되지 않은 6 교체 6 -> 2
• time 12 : 가장 오래 참조되지 않은 2 교체 2 -> 6
• Number of page faults = 7

---

LFU (Least Frequently Used) Algorithm

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

• 참조횟수가 가정 적은 y 교체

 

Example

• 4 page frames for the process, initially empty
• w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5

• time 6 : tie-breaking rule : LRU로 설정 2번 페이지 교체 2->5
• Number of page faults = 7

 

---

NUR (Not Used Recently) Algorithm

• 최근에 사용하지 않은 페이지 교체
• LRU approximation scheme
  • LRU 보다 적은 overhead로 비슷한 성능 달성 목적
• Bit vector 사용
  • Reference bit vector (r), Update bit vector (m)
• 교체 순서 
  1. (r, m) = (0, 0)
  2. (r, m) = (0, 1)
  3. (r, m) = (1, 0)
  4. (r, m) = (1, 1)

• 주기적으로 reference bit 가 reset
• 교체 우선 : reference bit 판단  -> update bit 판단

---

Clock Algorithm

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

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

Example

• 4 page frames for the process, initially it has a, b, c, d
• w = c a d b e b a b c d

• time 5 : reference bit 가 1이면 0으로 초기화 후 이동
  a/0 -> b/0 -> c/0 -> d/0 -> a/0이므로 교체 e/1 
  pointer는 b/0을 가리킨다.
• time 6 : b참조 b/1
• time 7 : b/1이므로 초기화 b/0 -> c/0이므로 교체 a/1
  pointer는 d/0을 가리킨다.
• time 8 : b참조 b/1
• time 9 : d/0이므로 교체 c/1, pointer는 e/1을 가리킨다.
• time 10 : 모두 참조중이므로 e/0 -> b/0 -> a/0 -> c/0 -> e/0이므로 교체 d/1
  pointer는 b/0을 가리킨다.

---

Second Chance Algorithm

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

Example

• 4 page frames for the process, initially it has a, b, c, d
• w = c aW d bW e b aW b c d (W는 write operation - update bit -> 1 )

• time 5 : reference bit가 1이면 0으로 초기화 후 다음으로, reference bit가 0일 때 update bit 확인 1이면 write back 후 0으로 초기화 후 다음으로, 둘다 0이면 교체
  a/01 -> a/01 -> c/00 -> d/00 -> a/00 -> b/00 -> c/00이므로 교체 e/10
  pointer는 d/00을 가리킨다.

---

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와 정반대 기법

---

강의

www.youtube.com/watch?v=xLovOdiRtjI&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=34

www.youtube.com/watch?v=ICq6zoZ0vUQ&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=35