[운영체제-김덕수 교수님] 가상 메모리 관리(4/6) - 교체 전략 - 고정 할당(2/2)

Least Frequently Used) Algorithm

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

‏‏‎

• 위에 상황에선 y 를 빼는 알고리즘이다.

‏‏‎ ‎

예시

NUR(Not Used Recently) Algorithm

• LRU approximation scheme
  • LRU 보다 적은 overhead 로 비슷한 성능 달성 목적
• Bit vector 사용
  • Reference bit vector (r), Update bit vector (m)
• 교체 순서

1.(0,0)

2.(0,1)

3.(1,0)

4.(1,1)

앞에 1 은 참조가 된 것을 나타내는 참조 비트이다.

3,4 번 보다 1,2, 번을 값을 스왑할 가능 성이 높다

뒤에 비트는 Update bit vector, 이다. 수정이 되었는지 확인한다.

0은 수정이 안되었다는 것이고, 1은 수정이 된 것인데,

우리는 내릴 데이터를 찾고 있으므로, write-back 을 하지 않을 것을 찾아야하니까 0이 우선순위가 있다

따라서 교체 순서는 1 -> 2 -> 3 -> 4 이다

 

Clock Algorithm

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

‏‏‎ ‎

예

포인트는 4 Time 번째에 있다.

4Time 에서 새로운 e 라는 녀석이 들어와야 할 때 - a를 보면 1 이니까 다음으로 넘어가면서 0으로 바꿈

• b 를 보면 1 이니까 다음으로 넘어가면서 0으로 바꿈
• c 를 보면 1 이니까 다음으로 넘어가면서 0으로 바꿈
• d 를 보면 1 이니까 다음으로 넘어가면서 0으로 바꿈
• a를 보니 0이니까 a를 교체 이런식이다.

하나만 더해보자면 6time -> 7 time 을 봅시다.

• b가 있으니까 참조 카운트만 올려서 b/1
• c로 넘어갈 때 b 가 1 이니까 b/0 로 변경
• c 는 0 이니까 교체하고 a를 넣고 1 대입 -> a/1

‏‏‎ ‎

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) 후 이동

클락 알고리즘과 비슷한데, reference bit를 0으로 만들고 다시 돌아서 update bit 도 0으로 만들어야한다. 해보면 잘 알 수 있다.

‏‏‎ ‎

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