[운영체제] Working Set Algorithm - Variable allocation

운영체제 - 한빛아카데미

운영체제에 대해 공부한 내용에 대해 정리해보았습니다.

KOREATECH 김덕수 교수님의 자료와 한밭대학교 임경태 교수님의 강의를 참고하였습니다.

---

이번 포스팅에서 다룰 내용은 Variable allocation 가상 메모리 관리 중 Working Set Algorithm입니다.

---

Working set, Window size

 

여기서 Working Set이란 Process가 특정 시점에 자주 참조하는 Page들의 집합 즉, 최근 일정시간$(\Delta)$동안 참조된 Page들의 집합을 의미합니다.

Working set은 $W(t,\Delta)$로 나타내어집니다.

여기서 $t$는 특정 시점을 의미하고 $\Delta$는 Window size를 의미합니다.

→$\Delta$ = Window size

정리하자면 Working set은 특정 시점 $t$와 Window size$\Delta$에 대하여 $[t-\Delta, t]$사이에 참조되는 Page들의 집합을 의미합니다. $t$가 시점을 의미하기 때문에 Working set은 가변적입니다.
이러한 Working set을 메모리에 유지하는 것이 Working set Algorithm입니다.

위같은 특성으로 인해 Working set은 Locality에 기반을 두었다는 것을 알 수 있습니다.

→ Locality 기반 : Page fault rate 감소, 시스템 성능 향상

Working set에서 최대로 참조할 수 있는 페이지 수는 $\Delta + 1$개이고, 최소로 참조할 수 있는 페이지 수는 $1$개입니다.

(Window size는 고정, Working set의 크기는 변함)

window size 와 working set size의 관계

위 그래프는 window size와 working set size의 관계를 나타낸 그래프입니다. Working set Algorithm은 Locality에 기반을 둔 알고리즘이기 때문에 window size와 working set size가 정비례하지 않기 때문에 위와 같은 형태를 갖습니다.

 

 

---

Working set algorithm 성능평가

 

total cost = page fault 비용 $\times$ page fault 횟수 + 평균 page frame 수 $\times$ 초당 필요한 page frame비용$\times$ 시간

 

ex)

Time interval [1,10]

page fault 수 = 5

평균 할당 page frame 수 = 3.2

cost(page fault) = 50

cost(page frame) = 10

→  Total cost = 5$\times$50+3.2$\times$10$\times$10 = 570

 

평가 : 10초동안 평균 3.2개의 page frame을 할당받은 상태로 5번의 page fault가 발생했다.

 

Working set algorithm 특성 및 단점

특성

• 적재되는 page가 없더라도, 메모리를 반납하는 page가 존재할 수 있음.
• 새로 적재되는 page가 있더라도, 교체되는 page가 없을 수 있음.

단점

• Working set을 관리해야 하므로 overhead가 발생한다.
• page fault가 없더라도 residence set을 지속적으로 관리해야 한다.

window size와 lifetime, page fault rate의 관계

위 그래프는 window size와 lifetime, page fault rate의 관계를 나타낸 그래프입니다.

window size가 커지면 working set size가 커지므로 page의 lifetime이 길어집니다.

lifetime이 길어지면 해당 페이지를 메모리에 유지하기 위한 비용이 많이듭니다.

동시에 page fault rate는 줄어들게 됩니다.

 

따라서 적정한 기준으로 window size를 결정해야 합니다.