운영체제 Thrashing ( Working Set Model, Page-Fault Frequency, PPF )

Thrashing

 

frame을 적게 할당받으면 프로그램을 돌릴 때 계속 page in, page out을 반복하며 수행하게 된다. 즉, 프로세스가 코드를 수행하는 것보다 swapping 하느라 바쁜 것을 Thrashing이라고 한다.

 

이렇게 되면 CPU의 utilization이 낮아진다. 즉, waiting queue에는 page들이 쌓이는데 ready queue는 비어있는 상황이 생긴다. 이런 상황에서 운영체제는 멀티프로그래밍을 하고 있다고 착각하여 계속 새로운 프로세스를 생성한다. 그러면 아래 그래프와 같은 선이 그려진다.

 

 

즉, 할당된 frame보다 프로세스의 크기가 더 클 때 발생한다. 수식으로는 아래와 같다.

 

 

전체 locality size를 계산해서 전체 메모리보다 많아지는 시점에서 하나의 프로세스를 swap out을 시키거나 다른 방법을 통해 thrashing을 막아야 한다.

 

그렇다면 어떻게 전체 locality를 계산할 수 있을까??

2가지 방법이 있는데 하나는 Working set model과 다른 하나는 Page fault frequency 방법이다.

하나씩 알아보자

 

Working - Set - Model 

 

locality(지역성)를 고려해서 만든 모델인데 간단히 말해서 필요한 부분을 집중적으로 참조하는 것이다. 참조하는 것이라 함은, 메모리에 올리는 것이다. 

 

Delta ( Window size )를 지정하여 검사하는데 Delta는 내가 검사하고 싶은 과거의 page의 수를 정한다. 

 

예를 들어 Delta가 10이라고 하면 10개의 page를 검사하는데 특정 시간에 대해서 검사한다.

아래 예를 보면 t1일 때 10개를 검사하는데 10개 중에 중복을 제외한 unique 한 값들의 집합을 Working set이라고 부른다. t1에서 Working set은 {1, 2, 5, 6, 7}이다. Working set은 프로그램이 진행되면서 계속 바뀌어간다.

 

 

Working set을 메모리에 올리면 page fault가 상대적으로 적어져 Thrashing을 저지하는 역학을 할 수 있다. 다시 말해  Working set이란 지역성을 고려한 집합이 된다.

 

Working set size는 Working set에 몇 개가 들어있는지를 나타내는데 너무 작으면 지역성을 나타내기에 너무 어렵다. 

 

이렇게 Working set을 다 더하면 우리가 궁금했던 요구되는 전체 frame이 된다. 즉, 계산된 전체 frame이 할당된 frame보다 크게 되면 Thrashing이 발생한다. 하지만 매번 working set을 계산하기엔 cost가 많이 필요하다 그래서 근사화해서 하는 방법을 사용한다.

 

또 다른 방법으로 thrashing을 통제할 Page fault frequency를 알아보자

 

 

Page-Fault Frequency (PPF)

 

PPF는 page fault의 빈도수를 이용하여 thrashing을 통제하겠다는 말인데, 결국 thrashing이란 page fault가 졸라 많이 일어나서 생기는 거니까 연관도가 높다. 

 

어떻게 통제하느냐, 하면 page fault의 비율에서 일정 기준 이상 올라가거나 내려갔을 때 어떤 조치를 취한다. 즉, 상한선과 하한선을 정한다는 말이다.

 

 

만약 상한선보다 높게 되면 프로세스들이 더 많은 frame을 요구한다고 가정하여 더 많은 frame을 할당해주고, 

만약 하한선보다 낮게 되면 프로세스들이 이미 많은 frame을 가지고 있다고 판단하여 frame을 회수한다.