[운영체제] Page Fault Frequency(PFF) algorithm - variable allocation

운영체제 - 한빛아카데미

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

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

---

우선 Page Fault Frequency(PFF) algorithm에 대해 알아보겠습니다.

이전 포스팅에 작성한 Working set algorithm은 page fault가 없어도 항상 working set을 관리해야해서 overhead가 발생합니다.

이 Page Fault Frequency algorithm 은 page fault가 일어나면 resident set을 관리합니다.

pagefault가 일어날 때만 resident set을 관리하기 때문에 WS에 비해 overhead가 적습니다.

 

Page Fault Frequency algorithm

 

residence set size를 page fault rate에 따라서 page fault가 적으면 process에 할당된 page frame수를 감소시키고(memory allocation 감소), page fault가 많으면 process에 page frame을 더 많이 할당합니다.

 

→ pagefault가 자주일어나면 메모리를 더 주고, 자주 일어나지 않으면 메모리를 뺏는다.

 

여기서 "자주"의 기준이 되는 것은 $\tau$ 입니다.

pagefault와 pagefault사이의 시간을 IFT(inter fault time) 이라고 합니다.

• IFT = $t_c - t_(c-1)$
• $t_(c-1)$ : 이전 page fault가 일어난 시간
• $t_(c)$ : 현재 page fault가 일어난 시간

$IFT > \tau$ : pagefault가 자주 일어나지 않음 → 메모리를 빼앗는다 (page frame수를 감소시킨다)

• Residence set ← $(t_(c-1),t_c]$동안 참조 된 page들 만 유지
• 나머지 page들은 메모리에서 내림 = 메모리 할당 감소(or 유지)

$IFT \leq \tau$ : pagefault가 자주 일어남 → 메모리를 더 할당한다.(page frame수를 증가시킨다)

• 기존 page들 유지
• +현재 참조된 page를 추가 적재 = 메모리 할당 증가

 

성능평가는 Working set algorithm과 동일하게 진행된다.

 

 

---

Variable Min algorithm (optimal solution)

Min algorithm과 동일하게 실현 불가능한 기법이지만 optimal solution으로 성능 판단의 기준이 된다.

 

방법

• Page r이 t시간에 참조 되면
• $[t, t+\Delta]$에서 다시 참조되는지 확인한다.
• 참조된다면 page r 유지, 그렇지 않으면 메모리에서 내린다.

여기서 최적의 $\Delta$값은  $\Delta = \frac{R}{U}$ 이다.

• U: 한 번의 참조시간 동안 page를 메모리에 유지하는 비용
• R: page fault발생 시 처리 비용

→ $\Delta $ = page fault 처리비용 / 한 번의 참조시간동안 페이지 유지 비용