[OS/운영체제] 페이지 교체 (Page Replacement) - (3)

스레싱 (Thrashing)

충분한 프레임을 갖지 못한 프로세스는 페이지를 충족하기 위해 페이지 결함을 일으킬 것이다. 이 때, 몇 페이지를 교체해야 한다. 하지만 모든 페이지가 사용 중이었기 때문에, 교체된 페이지들은 바로 즉시 페이지 결함을 다시 발생시킬 것이다.

이런 과정이 반복되면 페이지를 교체하는 시간이 실제로 페이지가 실행되는 시간보다 길어지게 되는데, 이를 스레싱(Thrashing)이라 한다.

Thrashing

CPU의 사용률이 낮다면, 새로운 프로세스를 생성해 멀티프로그래밍의 정도를 높여 CPU의 사용률을 높이려 할 것이다. 하지만 이것이 어느 정도를 넘으면 스레싱이 발생해 오히려 다시 사용률이 떨어져 스레싱이 발생한다. 이 경우에는 다시 멀티프로그래밍의 정도를 낮춰야 한다.

 

Working Set Model

스레싱을 예방하기 위해서는 프로세스들에게 필요한 만큼의 프레임만을 제공해야 한다. 하지만 프로세스가 프레임을 얼마나 필요로 하는지 어떻게 알 수 있을까? 이러한 접근을 프로세스 실행의 지역성 모델(Locality Model)이라 정의한다.

지역성 모델은 프로세스가 실행될 때, 한 지역에서 다른 지역으로 옮겨간다고 생각한다. 지역(Locality)이란 현재 사용되는 페이지들의 집합을 말한다. 프로그램은 겹칠 수 있는 여러 다른 지역으로 구성되어 있다고 이해할 수 있다.

Working-Set은 △으로 표기되는 Time Window로 정의된다. 최근에 참조된 △개의 페이지를 Working-Set이라 한다. 만약 페이지가 현재 사용 중인 페이지라면 Working-Set에 존재할 것이고, 그렇지 않다면 △의 시간동안 다시 참조되지 않을 것이다. 즉 Working-Set은 프로그램의 지역성을 추정하는 것이다.

Working-Set Model

따라서 Working-Set 모델에서 가장 중요한 것은 Time Window의 크기(△)가 될 것이다. 만약 우리가 Working-Set의 크기인 WSSi를 계산할 수 있다면, 필요한 프레임의 총량 D를 다음과 같이 정의할 수 있다.

만약 △의 크기가 너무 작다면 지역을 충분히 나타낼 수 없고, 너무 크다면 다른 지역과 중첩될 수 있다.

운영체제는 각 프로세스의 Working-Set 크기를 모니터링하여 Working-Set의 크기를 수용할 수 있을 만큼 프레임을 할당한다. 만약 새 프로세스를 수용할 만큼 빈 프레임이 존재하면 새 프로세스를 실행해주며, 반대로 각 프로세스의 Working-Set 크기의 총합(D)이 사용가능한 프레임 수를 초과하면 하나의 프로세스를 중지한다.

 

페이지 결함 빈도 (PFF, Page-Fault Frequency)

페이지 결함률의 상한, 하한을 정의해 프로세스의 페이지 결함률이 상한보다 높으면 프레임을 추가 할당하고, 하한보다 낮다면 프레임을 비운다.

Page-Fault Frequency

만약 페이지 결함률이 상한보다 높지만 추가로 할당할 프레임이 더 이상 없는 경우, 프로세스 하나를 일시 중단해야 한다.

 

※ 본 게시글은 『Operating System Concepts』 를 참고하여 작성되었습니다.