[OS] Virtual Memory Management : Replacement Strategy (Variable Allocation)

2. Global Replacement Strategy

모든 프레임의 집합 내에서 교체 대상을 선택하는 기법이다.
(그 대상이 다른 프로세스에 할당된 프레임일지라도)

가변할당 기반의 교체기법이다.
(Variable allocation based replacement)

Working Set 정의

특정 시간에 어떤 프로세스가 집중적으로 접근하는 페이지들의 집합
최근의 시간 구간 delta 동안 참조된 페이지들의 집합

특정 시간 t의 working set W(t, delta)는
t-delta부터 t까지의 시간 구간동안 프로세스에 의해서 참조된 페이지들의 집합이다.
(delta는 시스템 파라미터로서, 윈도우 사이즈이다. 개발자가 결정하는 것이 아닌 시스템이 알아서 결정해주는 값! 시간 구간의 길이의 값이다)

t-delta ~ t까지의 시간동안 참조된 페이지의 집합 = working set W(t, delta)

🌱 Working Set 기법

locality에 기반을 두고 있다.

매 순간마다 그 프로세스의 working set이 항상 메모리에 들어가 있도록 한다.

이 경우 page fault를 줄이고 시스템 성능을 높일 수 있다.

윈도우 사이즈 delta는 성능 측면에서 매우 중요한 시스템 파라미터이다.
윈도우 사이즈 delta를 얼마로 하느냐에 따라 성능이 크게 달라진다.

🌱 가변 할당량

loop-1을 도는 동안, working set = {p0, p1}이다. 이 동안은 page0, page1이 메모리에 들어와있어야 하므로 페이지 프레임 2개 필요
loop-2를 도는 동안, working set = {p2, p3, p4}이다. 이 동안은 page2, page3, page4이 메모리에 들어와있어야 하므로 페이지 프레임 3개 필요
loop-3을 도는 동안, working set = {p6, p7}이다. 이 동안은 page6, page7이 메모리에 들어와있어야 하므로 페이지 프레임 2개 필요

따라서 이 기법은 메모리 할당량(페이지 프레임 할당량)이 계속 바뀌기 때문에 가변 할당량이다.

🌱 working set transition

시간이 지나며 페이지 프레임 할당량이 계속해서 추가되다가, 어느 순간 반납하기도 한다.

특정 시점에서 loop에 들어가서 working set 1 만큼 페이지를 할당받는다.
loop안에 들어감으로써 steady하게 page frame number가 동일하게 된다.

두번째 loop, 세번째 loop, 네번째 loop을 실행하게 된다.

이 사이사이, working set이 바뀌는 구간을 'transition' 이라고 한다.
steady하게 페이지 할당량이 바뀌지 않는 구간이 프로그램 실행시간의 대부분을 차지한다.

🔔 Example

한 프로세스가 페이지를 다섯 개 가지고 있다.
time = 0일때 0, 3, 4번 페이지가 메모리에 들어와 있으며(페이지 프레임을 3개 할당받은 상태) 이 때 0번에 참조한 상태였다.

time = 1부터 time = 10까지의 구간을 추적해보자.

time = 1 : page fault 발생,
t=1-3=-2부터 1까지의 구간동안 참조된 페이지 = {p4, p3, p0, p2} 를 메모리에 유지한다. 2번 페이지는 들어오고 나가는 페이지는 없다.
time = 2 :
(-1부터 2)까지 구간동안 참조된 페이지 = {p3, p0, p2} 를 메모리에 유지
4번 페이지는 사라진다. page fault가 없는데도 나가는 페이지가 생긴 것 !
time = 3 :
(0부터 3)까지 구간동안 참조된 페이지 = {p0, p2, p3} 를 메모리에 유지
그대로 유지된다.
time = 4 :
(1부터 4)까지 구간동안 참조된 페이지 = {p2, p3, p1} 를 메모리에 유지
page fault 발생. p1은 들어오고 p0은 나간다.
time = 5 :
(2부터 5)까지 구간동안 참조된 페이지 = {p2, p3, p1} 를 메모리에 유지
그대로 유지한다.
time = 6 :
(3부터 6)까지 구간동안 참조된 페이지 = {p3, p1, p2, p4}를 메모리에 유지
page fault 발생, p4가 들어온다.
time = 7 :
(4부터 7)까지 구간동안 참조된 페이지 = {p1, p2, p4}를 메모리에 유지
p3이 나간다.
time = 8:
(5부터 8)까지 구간동안 참조된 페이지 = {p2, p4}를 메모리에 유지
p1이 나간다.
time = 9:
(6부터 9)까지 구간동안 참조된 페이지 = {p4, p2, p0}을 메모리에 유지
page fault 발생, p0이 들어온다
time 10:
(7부터 10)까지 구간동안 참조된 페이지 = {p2,p4,p0,p3}을 메모리에 유지
page fault 발생, p3이 들어온다.

🌳 LRU 기법과 Working Set기법의 공통점

최근 참조된 페이지를 메모리에 유지한다는 점에서 locality에 기반하고 있다.

🌳 LRU 기법과 Working Set기법의 차이점

LRU는 고정할당기법, WorkingSet은 가변할당기법이며, 윈도우 사이즈인 delta를 고정시킨다는 점에서 차이가 있다

🌳 Working Set 기법의 성능

가변할당기법은 성능을 판단할 때 page fault만으로 판단하면 안 된다.
메모리 참조 구간동안 페이지 프레임 할당량은 얼마인지도 검사해봐야 한다.

"평균 3.2개의 페이지프레임을 할당받으면서, page fault를 5개 발생시켰다"고 평가해야 한다.

만약 가변할당기법A는 평균 3.2개 페이지 프레임으로 Page fault 5개를 발생시키고, B는 평균 3.7개로 Page Fault 5개를 발생시켰다면 A가 더 잘한 것이다! 더 적은 페이지 프레임을 할당받고 동일한 fault를 발생시켰기 때문.

📌 특징

✔ 들어오는 페이지가 없어도 page fault가 생길 수 있다.

✔ page fault가 발생해서 들어오는 페이지가 있는데 나가는 페이지가 없을 수도 있다.

📌 단점

✔ residence set, 즉 working set이 page fault와 상관 없이 페이지 참조 시마다 update되기 때문에 오버헤드가 된다.

-> 이를 보완해서, page fault가 발생할 때만 residence set을 update하는 'PFF(Page Fault Freqeuncy) 기법'도 있다!
-> 참고: 가변할당 기법의 VMIN 알고리즘은 최적의 기법이며, 미래를 보는 것이기 때문에 현실적이지는 않다.

,