[OS] Virtual Memory Management : Replacemenet Strategy (Fixed Allocation)
Operating System
1. Local Replacement Strategy
고정할당(Fixed Allocation) 기반의 Replacement
페이지 프레임을 3개 할당 받았는데, 새로운 페이지를 할당받기 위해서는 내가 가진 페이지 중에서 나갈 페이지를 선택해야 한다.
내가 가진 페이지 중 희생양을 선택하는 것이다.
1) MIN Algorithm (OPT, B0 algorithm)
page fault 가 최소화되는 기법이다. (Optimal, 최적의 기법)
즉 고정할당 기반에서 MIN 기법보다 page fault를 더 줄이는 기법은 없다.
MIN 기법은 최적이지만 실제로 구현할 수 없는 기법이다.
각 프로세스의 참조열 string이 미리 알려져 있다는 가정 하에 가능하다. 즉 페이지의 참조 순서를 미리 알 수 있다는 가정 하이기 때문에, 이것은 실제로 구현할 수 없다.
그러나 이 기법은 성능을 측정하는 도구, 성능을 비교하는 도구로서 사용된다.
🔔 Scheme
앞으로 가장 오랫동안 참조되지 않을 페이지를 교체한다.
현재 페이지 프레임 3개를 배당 받고, x, y, z 3개의 페이지를 넣은 상태이다. time=t에 새로운 페이지 w가 접근한다. 이 때 x, y, z중 나갈 페이지를 결정하기 위해 앞으로 가장 오랫동안 참조되지 않을 페이지인 y를 교체한다.
현재 시점부터 앞으로 참조될 미래의 시점까지를 'forward distance'라고 한다. 즉 forward distance(x), forward distance(y), forward distance(z)를 비교하고 최댓값을 교체한다.
만약 forward distance가 동일한 경우 tie-breaking rule을 정해서 page number가 가장 크거나 가장 작은 페이지가 교체된다.
🔔 Example
어떤 프로세스가 4개의 페이지 프레임을 할당 받았다.
페이지는 1, 2, 6, 1, 4, 5, .. 순서로 실행된다.
1번 시점에서 page fault가 발생한다.
2번 시점에서 page fault가 발생한다.
3번 시점에서 page fault가 발생한다.
5번 시점에서 page fault가 발생한다.
6번 시점에서 page fault가 발생한다. 현재 시점 기준으로 1, 2, 6, 4번 페이지 중 가장 먼 페이지인 6번이 교체된다.
12번 시점에서 page fault가 발생한다. 1, 2, 5, 4 중 이후의 참조 시점이 없는 1, 2번은 모두 forward distance 같다. 이 경우 tie-breaking rule을 정해서 고르면 되는데, 만약 작은 번호가 교체된다고 가정하면 1번이 교체된다.
2) Random Algorithm
교체될 페이지를 랜덤하게 선택한다.
좋은 기법은 아니지만 오버헤드가 적고, 기준이 없다.
3) FIFO Algorithm
페이지를 교체할 때, 그 victim을 선정할 때 페이지가 메모리에 로딩된 시점을 기준으로 선정한다.
메모리에 로딩된 지 가장 오래된 페이지를 교체한다.
페이지가 로딩될 때마다 time을 저장하는 TimeStamping을 해야 한다.
(그러나 timestamping 없이 구현하는 방법도 있다)
이 프로세스에 3개의 페이지 프레임이 할당되어 있고 페이지 x, y, z가 들어가 있다. w가 들어오려고 하면, timestamping중 가장 오래된 z가 교체된다.
*현재 메모리에 로딩되어 있는 페이지의 집합을 'residence set'이라고 한다.
📌 단점
자주 사용되는 페이지를 교체할 가능성이 있다. 앞으로도 자주 사용될 수 있는데 메모리에 일찍 들어왔다는 이유로 쫓겨나야 하기 때문에, 추후 page fault를 유발할 수 있다.
🔔 Example
하나의 프로세스가 4개의 페이지 프레임을 할당 받은 상태.
time 1에서 page fault가 발생한다.
time 2에서 page fault가 발생한다.
time 3에서 page fault가 발생한다.
time 5에서 page fault가 발생한다.
time 6에서 page fault가 발생한다. 5번이 접근하는데, 메모리에 로딩된 지 가장 오래된 1번이 교체된다.
time 7에서 page fault가 발생한다. 1번이 접근하므로 가장 오래된 2번이 교체된다.
time 8에서 page fault가 발생한다. 2번이 접근하는데 가장 오래된 6번이 교체된다.
time 12에서 page fault가 발생한다. 6번이 접근하는데 가장 오래된 4번 교체된다.
time 13에서 page fault가 발생한다. 4번이 접근하는데 가장 오래된 5번이 교체된다.
time 14에서 page fault가 발생한다. 5번이 접근하는데 가장 오래된 1번이 교체된다.
page fault rate = 10/14
❗❗ FIFO Anomaly 현상 ❗❗
일반적으로 특정 프로세스에게 메모리 할당량을 적게 주면 page fault횟수가 늘어나고 할당량을 많이 주면 page fault가 적게 발생한다.
fifo는 메모리 할당량을 늘리면 page fault의 횟수가 증가하는 fifo만의 변칙적 현상이 존재한다
프로세스에 페이지프레임 할당량이 3개인 경우보다, 프로세스에 페이지프레임 할댱량이 4개인 경우 page fault가 더 많이 발생한다.
4) LRU (Least Recently Used) Algorithm
참조된 시점을 기준으로 victim을 선정한다.
가장 오랫동안 참조되지 않은 페이지를 선정한다.
✅ 다른 기법과의 차이점
FIFO는 '로딩 시점', LRU는 '참조시점' 기준이다
MIN 기법은 참조시점의 '미래'를, LRU기법은 참조시점의 '과거'를 기준으로 본다.
즉, LRU는 'backward distance'를 계산한다.
페이지 프레임을 3개 할당받고 X, Y, Z가 들어가있는 상황에서, W가 접근했다. 이때는 가장 오래 전에 참조된 페이지 X를 교체한다.
📌 페이지 참조 시점에 대한 TimeStamping이 필요하다.
(그러나 timestamping 없이 구현하는 방법도 있다)
📌 단점
1) time stamping에 대한 오버헤드가 존재한다.
(그러나 이것은 해결가능! time stamping 없이 구현 가능하므로)
2) 특정 프로세스가 메모리를 충분히 할당받지 못한상황이라면, loop에서 굉장히 많은 fault를 발생시킬 수 있다.
loop이 4 페이지에 걸쳐있는데, 페이지프레임이 3개 할당되어 있다면 loop을 돌 때마다 페이지 는 계속 쫓겨나게 된다.
🔔 Example
4개의 프레임이 할당된 상황이다.
1, 2, 3, 5번 시점에서 page fault 발생.
6번 시점에서 page fault 발생. 가장 예전에 참조된 2번 교체
8번 시점에서 page fault 발생. 가장 오래전 참조된 6번 교체
12번 시점에서 page fault 발생. 가장 오래전 참조된 2번 교체.
page fault reate : 7/14
🔔 특징
program locality에 근거하고 있기 때문에 MIN 알고리즘에 근사하는 성능을 보여준다.
높은 성능을 보여주기 때문에 실제 운영체제들에서 사용되는 기법의 근간이 된다.
"최근 참조된 페이지는 유지하고, 오랫동안 참조되지 않은 페이지를 유지하지 않는 것"과 "앞으로 가장 오랫동안 참조되지 않은 페이지를 유지하지 않는 것"은 왜 근사한 성능을 보일까?
Temporal Locality 때문이다. 최근 참조된 것은 앞으로도 temporal locality로 계속 참조될 가능성이 높기 때문이다.
5) LFU (Least Frequently Used) Algorithm
victim page를 선정할 때 프로세스가 실행을 시작한 시점부터 현재까지의 참조 횟수를 기준으로 선정
Counting-based Page Replacement
가장 작은 참조횟수를 가진 페이지를 교체한다.
만약 참조횟수가 동일할 경우, Tie Breaking Rule은 LRU로 한다.
📌 페이지 참조횟수에 대한 기록이 필요하다.
Time Stamping은 아니고 reference count를 누적시키면 되므로 더 빠른 연산이어서 오버헤드가 더 적다.
Program Locality를 일부 반영하고 있다. 참조횟수가 많다는것 자체가 100%는 아니지만 평균적으로 최근에 참조됐을 가능성이 높기 때문이다.
단점
최근 참조되어 로딩된 페이지는 reference count가 낮은데, 이것을 교체할 가능성이 있다.
이런 면이 locality를 반영하지 못하는 면이다.
페이지 프레임 3개가 꽉차 있는 상황에서 W가 들어오려고 할 때, 참조횟수가 가장 적은 Y를 교체한다.
🔔 Example
1, 2, 3, 5번 시점에서 page fault 발생.
6번 시점에서 page fault 발생. 참조횟수 2, 6, 4번이 동일하므로 LRU 기법으로 보면 가장 오래된 2번이 교체된다.
8번 시점에서 page fault 발생. 참조횟수는 5, 6, 4번이 동일하므로 참조된지 가장 오래된 6번이 교체
12번 시점에서 page fault 발생. 5, 2, 4번 모두 참조횟수가 동일하므로 참조된지 가장 오래된 2번이 교체된다.
6) NUR(Not Used Recently) Algorithm
최근에 사용되지 않은 것을 교체하는 알고리즘이다.
LRU 기법에 근사한 기법이다.
Locality에 기반을 두었으며, LRU 기법에 비해서 오버헤드를 줄였다.
하드웨어적으로 지원되는 Reference Bit Vector와 Update Bit Vector을 사용한 기법이다.
메모리의 페이지프레임 3개에 대해 각각 Reference Bit Vector와 Update Bit Vector(Modify Bit)이 있다.
꽉 찬 상태에서 새로운 페이지가 들어오려고 하면, (r, m)을 살펴보고 다음 우선순위에 따라 교체한다.
1순위 (r, m) = (0,0)
2순위 (r, m) = (0,1)
3순위 (r, m) = (1,0)
4순위 (r, m) = (1,1)📌 reference bit이 0이면 우선 교체 대상이다.
reset이 주기적으로 이뤄지는데, 현재 시점 t에서 r이 1이라는 의미는 최근 기간동안 1번은 접근되었다는 의미이다.
📌 reference bit이 같은 상태에서, modify bit이 0인 것을 먼저 교체한다.
update bit이 0인 것을 먼저 교체하는 이유는 update bit이 1인 것은 write back을 해야하는데, write back을 가급적 뒤로 미루자는 의미에서 0인 것을 먼저 교체하는 것이다.
7) Additional Reference-bits Algorithm
(중요X)
Reference Bit을 볼 뿐만 아니라, reference bit의 값을 기록해 놓은 History Register을 만들어서 그 이전에 참조된 시점까지 보면서 교체할 페이지를 선정하는 기법.
예시: 8Bit history register의 값을 기준으로 선정
00000000 : 8번의 주기동안 한번도 참조 X
11111111 : 8번의 주기동안 계속 참조
Page A : 01100100 & Page B : 00110111
-> Page A 는 B보다 최근에 더 많이 사용되었다.
8) Clock Algorithm
Reference bit을 사용하되, 주기적으로 reset이 되지 않도록 설정하는 기법이다.
(update bit은 사용 x)
pointer(시곗바늘)을 사용해서, 포인터가 페이지를 순회하여 선정한다.
다음과 같이 페이지 프레임을 할당 받았다고 생각해보자. 원형으로 프레임을 배치시키고, 각 페이지프레임마다 reference bit를 가지고 있다.
새로운 페이지 w가 접근한 상황에서 한 페이지가 나가야 한다.
포인터가 시계방향으로 순회하며 가리키는 페이지가 reference bit = 0이면 그 페이지가 교체된다. 만약 1이면, 그 페이지는 교체되지 않는다.
다만, reference bit = 1이어서 넘어갈 때에는 그 bit을 0으로 리셋하고 넘어간다.
🔔 Example
초기상태는 a, b, c, d가 들어와있고 모두 reference bit = 1인 상태이다.
time = 1에서 c가 접근했는데 c가 프레임에 있으므로 page fault가 없다. 따라서 포인터는 움직이지 않는다.
...
time = 5에서 e가 접근했는데, page fault 발생. a는 1이니까 0으로 리셋하고 넘어간다. b, c, d 모두 0으로 리셋되고 한바퀴 돌아서 다시 a가 된다. 따라서 a가 교체된다. 포인터는 그 위치가 아니라 다음위치에 두고 종료된다.
Pclock은 들어오는 페이지로, e다.
Qclock은 나가는 페이지(victim)으로, a다.
time = 6에서 b가 이미 있으므로 page fault 발생하지 않지만, reference bit 1로 설정한다.
time = 7에서 page fault 발생. b는 1이므로 0으로 바꾸고 넘어가고, c는 0이므로 c가 나가고 a가 들어온다. 포인터는 d를 가리키고 종료.
time = 8에서 page fault는 없지만 b의 reference bit = 1이 된다.
time = 9에서 page fault 발생. d = 0이므로 교체되고, c가 들어온다. 포인터는 다음인 e를 가리키고 종료.
time = 10 에서 page fault 발생. e = 1이니까 0으로 바꾸고 넘어가고, b, a, c도 0으로 바꾸고 넘어간다. 즉 한바퀴 돌고 다시 e로 돌아와서 e가 교체된다. 포인터는 b를 가리킨다.
📌 특징
FIFO 알고리즘을 닮은 측면이 있다.
메모리 로딩시점으로 오래 로딩된 페이지가 먼저 교체될 가능성이 있기 때문
LRU, NUR 알고리즘을 닮은 측면도 있다.
Reference bit = 1이면 넘어가고 0이면 바로 교체된다는 점에서 locality 반영.
9) Enhanced Clock Algorithm
clock algorithm과 비슷한데, reference bit 뿐만 아니라 update bit까지 함께 본다.
reference bit과 modify bit이 모두 0, 0인 페이지를 만나면 교체된다.
포인터를 clockwise로 돌리면서 선택한다.
r, m이 0, 0이면 교체대상이 된다. 포인터는 한 단계 다음으로 둔다.
r, m이 0, 1이면 modify bit을 0으로 바꾼다. (write-back을 하기 위해 그 페이지를 cleaning list에 올려둔다) 포인터는 한 단계 다음으로 둔다.
r, m이 1, 0이면 0, 0으로 만든다. 포인터는 한 단계 다음으로 둔다.
r, m이 1, 1이면 0, 1로 만든다. 포인터는 한 단계 다음으로 둔다.
🔔 Example
update bit까지 이용하기 때문에, 단순 reference 외의 write하는 경우는 따로 a(^w)와 같이 표기한다.
초기상태 : a, b, c, d가 들어와있고 모두 rm은 10이다.
time = 1 : page fault x
time = 2 : page fault x, write로 a : 11
time = 3 : page fault x
time = 4 : page fault x, write로 b : 11
time = 5 : page fault 0,
a는 11이므로 01로 바꾼다.
b는 11이므로 01로 바꾼다.
c는 10이므로 00으로 바꾼다.
d는 10이므로 00으로 바꾼다.
a는 01이므로 00으로 바꾼다. -> cleaning list (write-back 대상) : 밑줄
b는 01이므로 00으로 바꾼다. -> cleaning list (write-back 대상) : 밑줄
c는 00이므로 교체대상이다. 들어온 e는 참조대상이므로 10이다.
포인터는 d를 가리킨다.
time = 6 : page fault 발생 x. b : 10
time = 7 : page fault 발생 x. write 로 a : 11 (주의: write되면 reference bit도 같이 1이된다!)
time = 8 : page fault 발생 x. b : 10
time = 9 : page fault 발생.
d = 00이므로 교체되어서 c = 10이 들어온다.
포인터는 a를 가리킨다.
time = 10 : page fault 발생.
a는 11이므로 01로 바꾼다.
b는 10이므로 00으로 바꾼다.
e는 10이므로 00으로 바꾼다.
c는 10이므로 00으로 바꾼다.
a는 01이므로 00으로 바꾼다. -> cleaning list (write-back 대상) : 밑줄
b는 00이므로 교체 대상이다. d는 10으로 들어온다.
포인터는 e를 가리킨다.
✅ 기타
LRU의 반대인 MRU(Most Recently Used를 교체하는 알고리즘)도 있지만 사용되진 않는다.
LFU의 반대인 MFU(Most Frequently Used를 교체하는 알고리즘)도 있지만 사용되진 않는다.
🌱 정리
Replacement Strategy를 선택하는 기준은
✔ 해당 기법이 reasonable criteria(locality)를 가지고 있는가
✔ 오버헤드가 적은가
가 중요한 선택 기준이다!
