[ 운영체제 ] 쓰레싱(Thrashing)과 작업 공간(Working Set), 지역성(Locality)

메모리 파트에서 중요한 개념을 하나 놓쳐서 급히 쓴다. 쓰레싱과 작업 공간에 대해 자세히 다뤄보자. 두 가지 개념을 완벽하게 이해하는게 이 글의 학습목표!

[1] 쓰레싱 (Thrashing)

쓰레싱을 간단하게 정리하면 'Page Fault가 시스템의 허용 수준을 넘어가는 현상' 으로 요약할 수 있다. Page fault가 많이 발생하는 경우는 두 가지로 나눌 수 있다. 

1) 메모리 허용량보다 더 많은 프로세스를 동시에 실행하려고 할 때

말 그대로 메모리 용량을 초과하는 경우다. 이렇게 되면 많은 프로세스 중에 일부만 메모리 위에 올라가고, 나머지는 저장장치 안에 있게 되므로 스케줄링이 계속 됨에 따라 page fault 가능성이 매우 높아진다. 

2) 스케줄러가 CPU 이용률만 보고 계속해서 새로운 프로세스를 더 많이 실행하려고 할 때

CPU 이용률이 높다는 것은 CPU가 쉬지 않고 일한다는 뜻이다. Page fault가 발생하면 CPU는 아무 일도 하지 않으므로 스케줄러 입장에서는 '어 놀고있네? 새로운 일 줄게~~' 하고 새로운 프로세스를 실행시킨다. 그런데 만약에 현재 프로세스들이 이미 메모리의 많은 부분을 점유하고 있으면 새로 실행되는 프로세스는 충분한 양의 메모리를 할당받을 수 없다. 그러면 메모리를 조금만 할당받은 프로세스들의 page fault rate는 높아질 것이고, 이러한 프로세스에서 page fault가 발생하면 스케줄러는 또다시 CPU가 놀고있다고 판단해서 새로운 프로세스를 실행시킬 것이다. 이러한 악순환이 반복되면 page fault로 인한 오버헤드가 심각해진다. 

 

이렇게 스케줄러가 CPU 이용률만 보고 계속해서 새로운 프로세스를 더 많이 실행하려고 하는데, page fault가 더 많이 발생해서 cpu 이용률이 오히려 떨어지는 현상을 쓰레싱(Thrashing)이라고 한다. 위 그림처럼 일반적으로 동시에 실행되는 프로세스의 개수가 많아질수록 cpu가 놀때 다른 일을 시킬 수 있으므로 cpu 활용률이 높아지는데, 특정 지점부터는 현저히 떨어지게 된다. 떨어지는 지점부터 쓰레싱이 발생했다고 볼 수 있다. 

 

그렇다면 쓰레싱을 해결할 수는 없을까?

 쓰레싱 해결 방법

가장 간단하게 생각할 수 있는 방법은 프로세스에게 충분한 양의 프레임을 할당하는 것이다. 프로세스가 필요한 전체 메모리 양만큼 할당해서 page fault가 발생하지 않도록 하는 방법이다. 하지만 이는 적합한 방법이 아니다. 충분한 메모리를 할당하면 제한된 메모리 내에서 실행될 수 있는 프로세스의 개수가 적어지기 때문이다. 이후의 프로세스는 충분한 프레임을 할당받을 수 없기 때문에 결국에는 똑같은 문제가 발생하게 된다. 

 

프로세스가 필요한 전체 메모리 양 말고, 일부분만을 할당해서 전체를 할당했을때와 유사한 효과를 낼 수 없을까? 있다! 해답은 '지역성'에 있다. 지역성(Locality)은 프로세스가 실행되면서 특정 메모리를 참조하면 일정한 기간동안은 현재 참조하는 메모리 또는 근처에 있는 메모리를 계속 참조하는 특성을 말한다. 이는 대부분의 프로그램이 가지고 있는 특징이다. 예를 들어 어떤 함수가 실행되는 동안에는 그 함수의 로컬변수가 저장되어 있는 스택 메모리 영역이 참조되지, 다른 함수의 스택 메모리 영역은 참조되지 않을 것이다. 참고로 지역성은 Demand paging과 Cache memory가 자연스럽게 효과적으로 동작하는 근본적인 원인이다. 

 

위 그림은 지역성을 아주 잘 나타내는 그래프다. CPU 실행 시간에 따른 메모리 참조 영역을 시각화한 것인데, 특정 구간만을 연속적으로 참조하는 것을 볼 수 있다. 따라서 현재 지역성에 해당하는 일부 페이지만 메모리에 할당하면 '각 프로세스가 필요한 충분한 크기'를 '일부'로 축소할 수 있다. 이렇게 함으로써 똑같이 많은 수의 프로세스를 실행해도 쓰레싱을 방지할 수 있다. 여기서 '지역성에 해당하는 일부 페이지'를 바로 작업 공간(Working Set)이라고 한다. 

[2] 작업 공간 모델 (Working Set Model)

작업 공간 모델은 운영체제가 메모리 관리를 할 때 지역성을 활용하는 모델을 말한다. 운영체제는 프로세스가 필요한 전체 메모리를 할당하는 것이 아니고 일부만 할당하는데, 지역성을 잘 고려해서 현재 시점으로부터 이전에 실행된 일정한 메모리 참조만을 working set으로 구별하고 그 working set을 메모리에 할당한다. 여기서 working set의 구간을 working set window라고 한다. 예를 들어 지역성을 고려한 페이지의 개수를 6개로 하면 working set window는 6이 되는 것이다. 

 

위 그림에서 델타에 해당하는 값이 working set window, 그 페이지 집합을 working set이라고 한다. 과거의 전체 메모리 참조가 아니라 일정한 구간만큼의 내용만을 working set window로 정의하고 이를 계속 이동해가면서 working set의 내용을 변경시키는 구조다. 이렇게 하면 working set에는 현재 프로세스가 실행될 때 필요한 지역성에 해당하는 페이지들만 들어있기 때문에 page fault를 최소화 할 수 있다. Page fault는 working set window가 이동할때만 발생한다. 

 

Working set에 따라 메모리 프레임을 할당하면 page fault가 균일하게 발생하는 것이 아니라 특정 부분에서만 발생하게 된다. 위 그림에서 page fault 값이 급격하게 높아지는 부분이 바로 working set window가 이동하는 지점이다. 이동 후 한동안은 지역성 덕분에 page fault가 발생하지 않음을 확인할 수 있다.