Thrashing(스레싱)

물리 메모리에는 여러 개의 프로세스가 올라와 있다. 운영체제는 물리 메모리의 공간이 충분하면 프로세스의 요청에 따라 원하는 프레임을 할당하지만, 그렇지 못할 경우 남아있는 프레임을 어떻게 나누어주느냐는 문제에 맞딱뜨린다.

1. Thrashing(스레싱)

1.1 스레싱의 개념

프로그램을 너무 많이 실행시키다보면, 하드디스크의 입출력이 계속되어 프로그램이 정지하는 것 같은 현상을 확인할 수 있다. 처음에는 프로그램이 정상적으로 메모리에 올라오지만, 메모리가 꽉 찬 후에는 새로운 프로그램을 메모리에 올리기 위해 기존 프로그램을 스왑 영역으로 옮기는 횟사가 잦아지기 때문이다. 이와 같이 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태를 스레싱(thrashing)이라고 한다.

1.2 물리 메모리의 크기와 스레싱

스레싱은 메모리의 크기가 일정한 경우 멀티프로그램의 수와 밀접한 관계가 있다. 동시에 실행하는 프로그램의 수를 멀티프로그래밍 정도(degree of mutiprogramming)이라고 하는데, 멀티프로그래밍 정도가 너무 높으면 스레싱이 발생한다.

다음의 그림은 멀티프로그래밍 정도와 CPU 사용률의 관계를 나타낸 것이다. 프로그램의 수가 적을 적을 때는 CPU사용률이 계속 증가하다가 메모리가 꽉차면 CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리에 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 되는데, 이러한 시점을 스레싱 발생 지점(thrashing point)라고 한다.

따라서, 물리 메모리를 늘리면 CPU의 사용률이 높아지고, 컴퓨터는 빨라지게 된다. 컴퓨터는 운영체제를 포함하여 많은 프로그램을 동시에 실행한다. 자주 사용하는 프로세스가 필요로 하는 메모리보다 물리 메모리가 작다면 스레싱 발생 지점에 빨리 도달하여 컴퓨터가 전체적으로 느려진다. 따라서 물리 메모리의 크기를 늘리면 스레싱 발생 지점이 늦춰져서 프로세스를 원만하게 실행할 수 있다.

물리 메모리의 용량을 512MB에서 4GB로 늘리면 스레싱 발생 지점이 늦춰지기 때문에 컴퓨터의 성능이 향상된다. 그런데, 물리 메모리의 용량을 4GB에서 16GB로 늘리면 어떻게 될까?? 대부분의 경우는 빨라지지 않는다. 물리 메모리가 작업하는 데 충분한 크기가 되면 그 이후에는 크기를 늘려도 작업 속도에 영향을 미치지 않는다. 이는 CPU가 한번에 처리하는 양보다 메모리가 너무 커서 그렇다. 가령, 요리사의 도마가 작으면 요리하는 속도는 늦어질 수 밖에 없는데, 도마가 5cm에서 30cm으로 늘어나면 작업 효율이 좋아진다. 그런데 3m가 된다해서 작업 효율이 더 좋아지진 않는 것처럼 말이다.

1.3 스레싱과 프레임 할당

스레싱은 각 프로세스에 프레임을 할당하는 문제와도 연관된다. 실행 중인 여러 프로세스에 프레임(메모리 크기)을 얼마나 나누어주느냐에 따라 시스템의 성능이 달라진다. 어떤 프로세스에는 너무 적은 프레임을 할당하여 페이지 부재(page fault)가 너무 빈번하게 발생하고, 어떤 프로세스에는 너무 많은 프레임을 할당하여 페이지 부재(page fault)를 줄이는 대신 메모리를 낭비한다면 전반적으로 시스템의 성능이 낮아진다. 따라서 남아 있는 프레임을 실행 중인 프로세스에 적절히 나누어주는 정책이 필요하다. 프로세스에 프레임을 할당하는 방식은 크게 정적 할당과 동적 할당으로 구분된다.

2. 정적 할당

정적 할당(static allocation)방식은 프로세스 실행 초기에 프레임을 나누어준 후 그 크기를 고정하는 것으로 균등 할당 방식과 비례 할당 방식이 있다.

2.1 균등 할당 방식

균등 할당 방식(equal allocation) 방식은 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당한다. 가령, 사용 가능한 프레임이 12개이고, 프로세스가 3개이면 4개씩 프레임을 각각의 프로세스에 할당해주는 것이다. 설령, 프로세스 1번은 프레임 6개, 프로세스 2번은 프레임 3개, 프로세스 3번은 프레임 9개를 원한다고 해도 말이다.

균등 할당 방식에서는 크기가 큰 프로세스의 경우 필요한 만큼 프레임을 할당받지 못하기 때문에 페이지 부재(page fault)가 빈번하게 발생하고, 크기가 작은 프로세스의 경우 메모리가 낭비된다. 위 그림에서 Process 2는 프레임 3개만 있으면 되는데 4개가 할당되었고, Process 3은 프레임 9개가 필요하지만 절반도 못미치는 4개가 할당되었다.

2.2 비례 할당 방식

비례 할당 방식(proportional allocation)은 프로세스의 크기에 비례하여 프레임을 할당하는 방식이다.

위 그림에서 A, B, C 전체 프로세스의 프레임이 6 + 3 + 9 = 18개 이고, 가용 프레임이 12개이다. 비례 할당 방식에서는 프레임을 프로세스 1에 4개(6x12/18) 프로세스 2에 2개(3x12/18), 프로세스 3에 6개(9x12/18)를 할당한다.

비례 할당은 프로세스의 크기를 고려하지 않는 고정 할당 방식보다 좀 더 현실적인 방식이다. 그러나 다음과 같은 두 가지 문제가 있다.

1. 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못한다. 아무리 작은 프로세스라도 실행 중에 많은 메모리(프레임)를 필요로 하는 경우가 있다. 대표적으로 동영상 플레이어는 프로그램 자체의 크기는 작지만 재생되는 동영상의 크기가 크기 때문에 실행되는 동안 동영상 플레이어보다 몇 십 배 큰 메모리를 필요로 한다. 이때 비례 할당 방식은 프로세스가 실행되면서 필요로 하는 프레임을 유동적으로 반영하지 못한다.

2. 사용하지 않을 메모리를 처음부터 미리 확보하여 공간을 낭비한다. 요구 페이징 방식에서는 아무리 큰 프로세스라도 처음부터 메모리에 모두 올리지 않는데, 비례 할당 방식에서는 큰 프로세스를 실행하면서 당장 필요 없는 프레임을 미리 할당해놓기 때문에 메모리가 낭비된다.

3. 동적 할당 방식

정적 할당 방식은 프로세스를 실행하는 초기에 프레임을 할당하기 때문에 프로세스를 실행하는 동안 메모리 요구를 반영하지 못하는 단점이 있다. 프로세스는 실행 중에 어떨 때는 많은 프레임이 필요하기도 하고, 어떨 때는 적은 프레임만으로 작동하기도 한다. 이렇게 시시각각 변하는 요청을 수용하는 방식이 동적 할당(dynamic allocation)이다. 동적 할당 방식에는 작업집합 모델을 사용하는 방식과 페이지 부재(page fault) 빈도를 사용하는 방식이 있다.

3.1 작업 집합 모델(working set model)

작업 집합 모델(working set model)은 지역성 이론을 바탕으로 하며, 가장 최근에 접근한 프레임이 이후에도 또 참조될 가능성이 높다는 가정에서 출발한다. 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고, 이 집합에 있는 페이지들을 물리 메모리에 유지하여 프로세스의 실행을 돕는다.

위 그림은 작업 집합 모델을 나타낸 것이다. 작업 집합 모델에서 물리 메모리에 유지할 페이지의 크기를 작업집합 크기(working set size)라고 하는데, 이는 작업집합에 들어갈 최대 페이지 수를 의미한다. 위에서는 작업 집합 크기를 5(집합의 원소 개수가 총 5개로 1, 7, 5, 2, 3)로 잡은 것이다.

작업집합에 포함되는 페이지의 범위를 작업집합 윈도우(Working set window, WSW)라고 한다. 현재 시점에 최대 어느 범위까지의 페이지를 살펴볼 것인가를 결정하는 것이 작업 집합 윈도우이다.

위 그림에서는 작접 집합 윈도우를 10으로 잡고 범위를 나타내었다. 윈도우에 참조된 10개의 페이지 중 작업집합에는 WS(t1) = {1,7,5,2,3}이 있으며, 이 페이지들은 다음 번 윈도우에 도달할 때까지 물리 메모리에 보존된다. 작업 집합 윈도우에는 현재 시점(t1)부터 시간적으로 가까운 페이지부터 삽입된다는 것을 주의하자.

작업 집합 크기는 작업 집합에 들어갈 최대 페이지 수를 말하지만 얼마나 자주 작업 집합을 갱신할 것인지도 의미한다. 작업집합 크기가 5라는 것은 페이지에 다섯 번 접근할 때마다 작업 집합을 갱신한다는 의미이다.

위 그림은 프로세스가 진행되면서 작업 집합이 어떻게 변하는 지를 보여준다. t1시점에서 t2시점으로 이동하면 10개의 페이지(5 5 5 7 1 3 4 4 3 2)를 살펴보고 작업 집합을 WS(t2)={2,3,4,1,7}로 갱신한다. 원래 두 번째 작업집합 윈도에는 {2,3,4,1,7,5}가 있으나 작업집합의 크기를 5로 설정했기 때문에 t2 시점에 가까운 순서대로 작업집합에 삽입되고, 가장 멀리 있는 5번 페이지는 작업집합에 속하지 못한다. 같은 방법으로 t2에서 5개 페이지를 지난 t3시점에 작업 집합이 WS(t3)={5,3,2,4}로 갱신된다.

작업 집합 모델에서는 작업 집합 윈도우의 크기에 따라 프로세스의 실행 성능이 달라진다. 작업 집합 윈도우를 너무 크게 잡으면 필요 없는 페이지가 메모리에 남아서 다른 프로세스에 영향을 미친다. 반대로 윈도우를 너무 작게 잡으면 필요한 페이지가 스왑 영역으로 옮겨져서 프로세스의 성능이 떨어진다.

또한, 작업 집합 모델은 어떤 프레임을 가져와야하는 지는 알지만, 얼마나 프레임을 할당해야하는 지는 모른다.

3.2 페이지 부재 빈도(page fault frequency, PFF)

작업 집합 모델의 경우 충분한 페이지를 할당하지 않으면 작업 집합에 있는 페이지를 물레 메모리에 유지하기가 힘들다. 작업 집합 모델에서는 어떤 프레임을 물리 메모리에 유지해야 하는 지 알 수있지만 프로세스에 프레임을 얼마나 할당해야 하는지는 알 수 없다. 작업 집합 모델은 프로세스의 성능을 높이는 방법이지만 스레싱 문제를 해결하지는 못한다.

프로세스가 필요로 하는 페이지의 양을 동적으로 결정하는 방법 중 페이지 부재 빈도(page fault frequency)를 이용하는 것이 있다. 이는 페이지 부재 횟수를 기록하여 페이지 부재 비율을 계산하는 방식이다. 페이지 부재 빈도 방식에서는 페이지 부재 비율의 상한선과 하한선을 설정한다. 페이지 부재 비율이 상한선을 초과하면 할당한 프레임이 적다는 것을 의미하므로 프레임을 추가하여 늘린다. 반대로 페이지 부재 비율이 하한선 밑으로 내려가면 메모리가 낭비된다는 의미이므로 할당한 프레임을 회수한다.

위 그림의 upper bound를 넘으면 페이지를 많이 요구하므로 프레임을 더 추가해 늘린다. lower bound 아래로 넘어가버리면 페이지 부재가 적게 발생하므로 너무 많은 프레임을 할당했다는 것을 의미한다. 따라서 프레임을 감소시킨다. 이 boundary사이가 하나의 이상적인 안정기가 된다.

프로세스가 처음 시작될 때는 페이지 할당량을 예측하기가 어렵다. 페이지 부재 빈도 방식은 프로세스를 실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절한다. 즉, 하나의 프로세스에 할당된 프레임 수를 조절한다.