Thrashing

만약 프로세스가 충분한 페이지가 없다면 page-fault rate는 매우 높을 것이다

-> 낮은 CPU 이용율, OS는 멀티프로그래밍의 정도를 올려야 한다고 생각할 것이고.. 시스템에 다른 프로세스들이 추가되

Thrashing이란?

- 프로세스가 페이지를 swapping (in, out) 하느라 바쁜 상태. 따라서 프로세스는 여기에 대부분의 시간을 쓰게 됨

위 그림을 보면 갑자기 CPU 이용율이 낮아지는 부분이 Thrashing

프로세스가 여러 개 들어오면 페이지가 많아져서 instruction transfer 시간이 높아지..

To prevent Thrashing

- 프로세스는 필요한 만큼의 프레임을 제공받아야 한다!

- 필요한 만큼을 어떻게 아느냐? Locality model of process execution

* Locality - 자주 함께 사용되는 페이지들의 집합

* 프로세스는 한 지역에서 다른 곳으로 이동

* 지역성은 오버랩될 수 있다

- 옆 그림을 보면 메모리 주소 30~32에 오버랩된 모습 볼 수 있다

Working-Set model

- based on locality

- 프로세스가 잘 동작하기 위한 최소 페이지 개수

* Δ = working-set window : page reference의 고정된 수

* WSi = 프로세스 Pi의 working-set : 가장 최근 Δ에 참조된 페이지 집합. 만약 페이지가 활발히 사용되고 있다면 -> Working-set

* WSSi = WSi의 크기 : 만약 Δ 너무 작으면 모든 locality를 포함 못함. 너무 크면 여러 locality를 포함할 것. 무한대에 수렴하게 크면 모든 프로그램을 포함할 것

* D = 프레임의 총 demand = ΣWSSi

* 만약 D>m(페이지 프레임 갯수) -> Thrashing 이므로 프로세스 중 하나 종료해야.

- 그럼 어떻게 working set 계속?

* Approximate with interval timer + reference bit

* 예를 들어 Δ가 10000 reference이면 

메모리에 각 페이지 당 2 bit keep

타이머는 모든 5000 reference 뒤에 interrupt

만약 메모리에 있는 빗 중 하나가 1이면 -> page in working set