운영체제 10. 가상 메모리 관리 (4) - Replacement Strategies for Fixed Allocation 2

출처 : https://www.youtube.com/watch?v=ICq6zoZ0vUQ&t=1s

 

 

 

LFU (Least Frequently Used) Algorithm

 

LRU의 경우 참조 시마다 시간을 기록해야해서 overhead가 크다는 문제가 있었다. 그래서 overhead를 줄이고자 등장한 것이 LFU 알고리즘이다.

 

• 가장 참조 횟수가 적은 Page를 교체
  • Tie-breaking rule : LRU
• Page 참조 시 마다, 참조 횟수를 누적시켜야 함
• Locality 활용
  • 과거에 자주 참조했다면 미래에도 자주 참조할 가능성이 높다 
  • LRU 대비 적은 overhead
• 단점
  • 최근 적재된 참조될 가능성이 높은 page가 교체 될 가능성이 있음
  • 참조 횟수 누적 overhead

 

 

이전의 참조 횟수가 x = 27, y = 16, z = 23 일때, 새로 들어온 page w가 들어온다면 어느 것과 교체를 해주어야할까?

가장 참조 횟수가 적은 y와 w가 교체되게 된다.

 

 

• Example
  • 초기 조건은 이전 예시와 동일하다.
  • Time 1 ~ 5 : 이전과 동일하다.
  • Time 6 : 5번이 들어와야하는데 memory에 빈 공간이 없다. memory에 적재된 page들(1, 2, 6, 4번) 중 가장 적게 참조된 page는 2, 4, 6번으로 여러 개가 있다. Tie-breaking rule은 내가 정하기 나름이지만, 여기서는 가장 먼저 들어온 page와 교체하는 방식이라고 가정해보자. 그러면 2번이 5번과 교체된다.
  • Time 7 : 1번이 memory에 적재되어있으므로 page fault가 발생하지 않는다.
  • Time 8 : 2번이 들어와야하는데 메모리에 빈 공간이 없다. 메모리에 적재된 page들(1, 5, 6, 4번) 중 가장 적게 참조된 page는 4, 5, 6번으로 여러 개가 있다. 이 중 가장 오래된 6번이 5번과 교체된다.
  • Time 9 ~ 11 : 해당 reference string들(1, 4, 5)이 memory에 적재되어있으므로 page fault가 발생하지 않는다.
  • Time 12 : 6번이 들어와야하는데 메모리에 빈 공간이 없다. 메모리에 적재된 page들(1, 5, 2, 4번) 중 가장 적게 참조한 2번과 6번을 교체한다.
  • Time 13 ~ 14 : 4번과 5번이 메모리에 적재되어있으므로 page fault가 발생하지 않는다.
• Page fault는 총 7번 발생한다. LRU 알고리즘과 같은 성능을 보여주었다.

 

 

NUR (Not Used Recently) Algorithm

최근에 사용되지 않은 페이지를 교체

 

• LRU approximation scheme
  • LRU보다 적은 overhead로 비슷한 성능 달성 목적
• Bit vector 사용
  • Reference bit vector (r), Update bit vector (m)
  • r = 1 : 최근에 참조되었다. 주기적으로 일정 시간 뒤에 0이 된다.
  • m = 1 : 업데이트가 되었다. 안의 데이터가 수정되었다. 메모리에서 나올 때 0이 된다.
• 교체 순서
  1. (r, m) = (0, 0)
  2. (r, m) = (0, 1)
  3. (r, m) = (1, 0)
  4. (r, m) = (1, 1)
  5. 일정 시간 안에 참조가 안 된 페이지(r = 0)를 먼저 교체하고, r이 동일할 때에는 안의 데이터가 수정이 안된 페이지(m = 0)을 먼저 교체한다.

 

 

t1과 t2가 주기적으로 r을 0으로 초기화하는 지점이다. 이 기간 안에 참조가 되면 Reference bit r이 1로 바뀌게 된다.

 

 

Clock Algorithm

 

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

 

 

시계침이 있고 page들이 원형으로 있다고 가정을 한다. 이 시계침이 돌아가면서 교체할 page를 선택해서, r=0이면 바꾸고, r = 1이면 넘어간다. 이때, 모든 page들의 r이 1이면 안되므로, 시계침이 넘어가면서 해당 page의 reference bit를 0으로 초기화한다.

 

 

• Pointer를 돌리면서 교체 page 결정
  • 현재 가리키고 있는 page의 reference bit (r) 확인
  • r = 0 인 경우, 교체 page로 결정
  • r = 1 인 경우, reference bit 초기화 후 pointer 이동
• 먼저 적재된 page가 교체될 가능성이 높음
  • FIFO와 유사
• Reference bit를 사용하여 교체 페이지 결정
  •  reference bit(최근에 참조를 했느냐)를 확인하기 때문에 locality를 활용한다는 특징을 가짐
  • LRU (or NUR) 과 유사

 

 

• Example
  • 프로세스에게 4개의 page frame이 존재하고, 맨 처음 메모리에는 a, b, c, d라는 page가 담겨져 있다. 시침은 frame 0부터 출발한다.
  • reference string ω = c a d b e b a b c d
  • Time 1 ~ 4 : 해당 page가 메모리에 적재되어있으므로 page fault가 발생하지 않는다.
  • Time 5 : e번이 들어와야하는데 메모리에 빈 공간이 없다. 메모리에 적재되어있는 page frame 0~3번까지 한바퀴 살펴보고 해당 page frame의 reference bit를 0으로 초기화한다. 그 다음 가장 먼저 가리키는 page frame 0번인 a를 e와 교체한다. 새로 교체된 frame0의 e는 새로 참조한 것이므로 reference bit는 1이 된다. 다음 시침은 frame1인 b부터 시작한다.
  • Time 6 : b번은 메모리에 적재되어있으므로 page fault는 발생하지 않는다. b가 들어있는 frame1의 reference bit를 1로 만들어준다.
  • Time 7 : a번이 들어와야하는데 메모리에 빈 공간이 없다. 메모리에 적재되어있는 page frame을 frame1인 b부터 살펴본다. 그리고 다음 순서인 frame 2번을 보면서 frame 1의 reference bit를 0으로 초기화한다. frame 2의 reference bit는 0이므로 c와 a를 교체한다. 새로 교체된 frame2의 a는 새로 참조한 것이므로 reference bit는 1이 된다. 다음 시침은 frame3인 d부터 출발한다.
  • Time 8 : b번은 메모리에 적재되어있으므로 page fault는 발생하지 않는다. b가 들어있는 page frame1의 reference bit를 1로 만들어준다.
  • Time 9 : c번이 들어와야하는데 메모리에 빈 공간이 없다. 메모리에 적재되어있는 page frame을 frame3인 d부터 살펴보는데 frame3의 reference bit가 0이므로 d와 c를 교체한다. 새로 교체된 frame3의 c는 새로 참조한 것이므로 reference bit는 1이 된다. 다음 시침은 frame0인 e부터 출발한다.
  • Time 10 : d번이 들어와야하는데 메모리에 빈 공간이 없다. 메모리에 적재되어있는 page frame 중 시침이 가르키고있는 frame 0 ~3번까지 한바퀴 살펴보고 해당 frame의 reference bit를 0으로 초기화한다. 그 다음 가장 먼저 가리키는 page frame 0번인 e를 d와 교체한다. 새로 교체된 frame0의 d는 새로 참조한 것이므로 reference bit는 1이 된다. 다음 시침은 frame1인 b부터 시작한다.

 

 

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

 

 

Clock algorithm의 형태에서 update bit m만 추가로 붙은 형태이다.

 

 

• Example
  • 4개의 page frame이 존재하고, 초기에는 a, b, c, d가 적재되어있다.
  • reference string ω = c a^w d b^w e b a^w b c d. (여기서 지수의 w는 write operation. 즉 update bit m이 1이 되어야한다는 뜻)
  • Time 0 : 맨 처음에는 a, b, c, d가 적재되어있다. 이때 최초로 참조는 되었고 수정은 된 것이 없으므로 모두 (r, m) = (1, 0)이다.
  • Time 1 : c가 참조되었는데 c는 이미 존재하므로 frame 2는 (1, 0) -> (1, 0)이 된다.
  • Time 2 : a가 참조되었는데 a는 이미 존재한다. 그런데 write operation이 있으므로 m이 1이 되어야 한다. 그러므로 frame 0은 (1, 0) -> (1, 1)이 된다.
  • Time 3 : d가 참조되었는데 d는 이미 존재하므로 frame 3는 (1, 0) -> (1, 0)이 된다.
  • Time 4 : b가 참조되었는데 b는 이미 존재한다. 그런데 write operation이 있으므로 m이 1이 되어야 한다. 그러므로 frame 1은 (1, 0) -> (1, 1)이 된다.
  • Time 5 : e가 참조되었는데 e가 메모리에 존재하지 않는다. 시침은 frame 0번을 가리키고 있으므로 frame 0은 (1, 1) -> (0, 1), frame 1은 (1, 1) -> (0, 1), frame 2는 (1, 0) -> (0, 0), frame 3은 (1, 0) -> (0, 0)이 된다. 다시 frame 0부터 (0, 1) -> (0, 0), frame 1은 (0, 1) -> (0, 0), frame 2는 (0, 0)이므로 c와 e가 교체된다. e는 새로 참조된 것이므로 frame 2는 e/10이 되고 시침은 frame 3을 가리키게 된다.
  • Time 6 : b가 참조되었는데 b는 이미 존재하므로 frame 1은 (0, 0) -> (1, 0)이 된다.
  • Time 7 : a가 참조되었는데 a는 이미 존재한다. 그런데 write operation이 있으므로 m이 1이 되어야 한다. 그러므로 frame 0은 (0, 0) -> (1, 1)이 된다.
  • Time 8 : b 가 참조되었는데 b는 이미 존재하므로 frame 1은 (1, 0) -> (1, 0)이 된다.
  • Time 9 : c가 참조되었는데 c가 메모리에 존재하지 않는다. 시침은 frame 3을 가리키고 있는데 frame 3이 (0, 0)이다. 그러므로 frame 3의 d와 c가 교체된다. c는 새로 참조된 것이므로 frame 3은 c/10이 되고 시침은 frame 0을 가리키게 된다.
  • Time 10 : d가 참조되었는데 d가 메모리에 존재하지 않는다. 시침은 frame 0을 가리키고 있으므로 frame 0은 (1, 1) -> (0, 1), frame 1은 (1, 0) -> (0, 0), frame 2는 (1, 0) -> (0, 0), frame 3은 (1, 0) -> (0, 0)이 된다. 다시 frame 0부터 (0, 1) -> (0, 0), frame 1은 (0, 0)이므로 frame 1의 b가 d와 교체된다. d는 새로 참조된 것이므로 frame 1은 d/10이 되고 시침은 frame 2를 가리키게 된다.

 

 

Other Algorithm

 

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

 

 

다음 시간에는 Variable allocation(할당하는 메모리의 크기가 변함)에서는 어떤 replacement strategy를 사용할 수 있는지 알아본다.