Thrashing

1. Thrashing 이란?

 일반적으로 하나의 프로세스는 실행을 위해 몇 개의 페이지 프레임(Page Frame)을 할당 받는다. 물론 이때 할당받는 프레임의 수는 주기억장치의 크기와 페이지 프레임의 크기에 따라 결정되는 종속적인 문제이기는 하지만 대부분의 경우에는 각 작업에 필요한 충분한 페이지 프레임을 항상 할당 받을 수 있다.

 프로세스에 할당된 프레임의 수가 효율적인 실행을 위해 시스템에 의해 요구되는 최소한의 수보다 적으면 적을수록 페이지 부재율(Page missing fault)는 증가하며, 프로세스의 실행은 늦어지게 된다.

 이와 같이 만일 하나의 프로세스가 어느 정도의 충분한 프레임을 갖고 있지 않다면 페이지 부재가 발생하여 프레임 안에 있는 사용중인 어떤 페이지를 교체해야 하는데, 이러한 페이지 부재가 계속 발생하여 프로세스가 수행되는 시간보다 페이지에 교체되는 시간이 더 많아지는 경우를 Thrashing(스래싱) 이라고 한다.

 위의 그림은 Multi programming 의 정도에 따른 CPU의 처리 효율성을 보여준다. multi programming의 정도가 높아짐에 따라 CPU의 효율성은 어느 한계에 도달할 때 까지 증가하다 일정 Threshold값을 넘어서면, Thrashing이 발생하여 CPU의 효율이 급격하게 감소하는것을 볼 수 있다.

 

 2. Locality(구역성)

 Thrashing 방지를 위해 한 프로세스가 효율적인 수행을 위해 제공받아야할 프레임 수를 알아야할 필요가 있는데, 어떻게 하면 알 수 있을까?

 Locality 란 프로세스가 기억장치 내의 모든 정보를 균일하게 참조하는 것이 아니라, 해당 작업 실행단계 동안 Task의 완성을 위해 반복적으로 호출되는 각 명령어들의 집합체로 구성된 국부적인 부분만을 집중적으로 참조한다 라는 것이다. 쉽게 말하면, 우리가 목적지로 가는 길이 여러개인데 익숙한 길로 자주 간다는 것이다.

 

 컴퓨터공학을 공부해보았다면 위의 사진은 한 번 쯤은 보았을 것이다. 구역성은 시, 공간상에서 공히 나타나는데,

[1] 시간 구역성 (Temporal locality)

 이것은 최근에 참조된 기억장소가 가까운 미래에 계속 참조될 가능성이 높다는 것이다. 예로는 Looping, subroutine, stack, counting 과 totaling에 사용되는 변수들의 경우 시간 구역성이 나타난다.

[2] 공간 구역성 (Spatial locality)

 하나의 기억장소가 참조되면, 그 근처의 기억장소가 계속 참조되는 경향이 있음을 의미한다. 예로는 배열, 순차 코드 실행, 프로그래머들이 관련된 변수들을 근처에 선언하는 경향등이 있다. 대표적으로 캐시메모리는 이런 공간 구역성을 활용한 장치이다.

 

3. Working Set (작업 집합)

앞에서 언급한 구역성 연구의 가장 중요한 결과로는 각 프로세스가 많이 참조하는 페이지들이 main memory 내에 있는 한 프로그램은 효율적으로 실행될 수 있다는 것이다. 이에 근거를 두고 Working Set이론이 Denning에 의해 소개되었다.

Working Set은 쉽게 말해 프로세스에 의해 자주 참조되는 페이지들의 집합이다. 하나의 프로세스가 효율적으로 실행되기 위해서는 프로세스의 작업세트가 주 기억장치 내에 존재해야하며, 그렇지 못할 경우 빈번한 페이지 교체과정으로 Thrashing이라는 바람직하지 못한 현상이 발생한다. 

 

4. Page Missing Fault (페이지 부재율)

 앞서 말했듯 Thrashing은 빈번한 페이지 부재로 인해 페이지 교체 시간이 프로세스의 동작 시간보다 길어지기 때문에 발생한다. 우리가 원하는 것은 페이지 부재를 효율적으로 조절하는 것인데, 페이지 부재율이 너무 높으면 그 프로세스는 더 많은 프레임을 필요로 한다는 것이고, 너무 낮다면 그 프로세스가 너무 많은 프레임을 가지고 있다는 것이다.

 

 따라서 페이지 부재율의 상한과 하한을 정해놓고 페이지 부재율이 상한을 넘으면 그 프로세스에게 다른 프레임을 더 할당해주고, 하한보다 낮으면 그 프로세스로부터 프레임을 회수해야한다. 이렇게 함으로써 Thrashing을 방지하면서 페이지 부재율을 측정하고 조절할 수 있을 것이다. 

 이 과정에서 어느 시점에 이르러 계속 페이지 부재율이 계속 증가되고 유효 프레임이 없게 되면 프로세스 집합 중 어떤 프로세스를 골라 그 프로세스의 실행을 중지시켜야한다. 이렇게 함으로써 프로세스에게 할당된 프레임을 높은 페이지 부재율을 가지는 프로세스에게 분배시킬 수 있을 것이다.