가상 메모리 part 2

프레임 할당 알고리즘

프레임 할당은 가상 메모리 시스템에서 가장 기본이 되는 구조다. 예를 들어 메모리 크기가 128K인 단일 사용자 마이크로컴퓨터 시스템에서 페이지 크기가 1K이고, 이 중 운영체제가 35K를 차지한다면 남은 93K는 사용자 프로세스의 몫이다. 순수 요구 페이징을 적용하면 프레임 93개가 모두 사용 가능 리스트에 들어가고, 사용자가 프로세스를 시작하면 페이지 부재가 발생하기 시작한다. 93번째까지의 페이지 부재는 사용 가능 리스트에서 대기 중이던 페이지를 모두 소진시키므로, 94번째 페이지 부재를 해결할 방법이 별도로 필요해진다.

사용 가능한 페이지가 없을 때의 해결 방법

사용 가능한 페이지가 남아 있지 않으면 페이지 대치 알고리즘을 호출해, 기억 장소에 있는 93개 페이지 중 하나를 선택해 교체한다. 이 페이지가 더는 쓰이지 않는다면 사용자 페이지로 전환해 쓸 수 있다. 사용 가능 리스트에서 프레임 3개 정도를 미리 확보해두면, 페이지 부재가 나더라도 항상 사용 가능한 프레임이 남아 있게 된다.

최소 프레임 수

각 프로세스에 할당되는 프레임 수가 줄어들수록 페이지 부재율은 올라가고 수행 속도는 떨어지므로, 성능 저하를 막기 위해 할당해야 할 최소 프레임 수가 존재한다. 이 최소치는 명령어 구조에 따라 정의된다. 수행 중인 명령이 끝나기 전에 페이지 부재가 나면 그 명령을 처음부터 다시 시작해야 하므로, 명령어 하나를 실행하려면 그 명령어가 참조하는 모든 페이지를 담을 수 있을 만큼 충분한 프레임이 필요하다. 프로세스당 최소 프레임 수는 컴퓨터 구조로 정해지지만, 최대 수는 실제 사용 가능한 기억 장소의 양으로 정해진다.

균일 할당과 비례 할당

균일 할당은 프로세스 n개에 프레임 m개를 나눌 때, 각 프로세스에 똑같이 m/n개씩 배분하는 방식이다. 비례 할당은 균일 할당의 문제점을 보완하기 위해 등장했다. 두 방식 모두 다중 프로그래밍의 정도에 따라 할당량이 달라질 뿐, 프로세스의 우선순위는 고려하지 않는다.

부하 제어(Load Control)

부하 제어는 메인 메모리에서 실행할 프로세스의 개수, 즉 ‘다중 프로그래밍 수준’을 결정하는 문제로 메모리 관리에서 매우 중요하다. 메인 메모리에서 실행되는 프로세스 수가 너무 적으면 프로세스들이 자주 보류 상태에 빠지고 교체가 빈번해지며, 반대로 너무 많으면 각 프로세스의 적재 집합을 구성하는 평균 페이지 수가 줄어들어 페이지 부재가 잦아지고 결국 스레싱을 일으킨다.

스레싱

스레싱은 페이지 교환이 끊임없이 일어나는 현상이다. 어떤 프로세스가 실제 수행보다 페이지 교환에 더 많은 시간을 쓰고 있다면 ‘스레싱을 하고 있다’고 말한다.

발생 원인

운영체제는 항상 프로세서의 이용률을 감시하다가, 이용률이 떨어지면 새로운 프로세스를 도입해 다중 프로그래밍의 정도를 높인다. 그런데 새로운 프로세스가 이미 수행 중인 프로세스의 페이지를 빼앗아 시작하면 더 많은 페이지 부재가 발생한다. 프로세스가 요구하는 최소 프레임 수보다 실제 프레임 수가 적을수록 페이지 부재율은 올라가고, 부재가 잦아질수록 프로세스가 페이징 처리 장치를 기다리는 시간도 길어져 효율이 떨어진다. 이렇게 프로세서 이용률이 떨어지면 스레싱이 발생해 시스템 처리율은 낮아지고 페이지 부재는 늘어나며, 유효 메모리 액세스 시간이 증가해 페이지 교체 시간이 낭비되는 악순환에 빠진다.

프로세서 이용률은 다중 프로그래밍의 정도에 따라 달라진다. 정도가 높아질수록 이용률도 최댓값까지 함께 오르지만, 그 이상으로 커지면 오히려 스레싱이 발생해 이용률이 급격히 떨어진다. 따라서 이용률을 높이고 스레싱을 멈추려면 다중 프로그래밍의 정도를 낮춰야 한다.

예방을 위해서는 지역 교환 알고리즘이나 우선순위 교환 알고리즘으로 제한을 둘 수 있다. 지역 교환 알고리즘을 쓰면 한 프로세스에서 스레싱이 일어나도 다른 프로세스로부터 프레임을 가져올 수 없어, 그 스레싱이 다른 프로세스로 번지지 않는다. 다만 여러 프로세스에서 동시에 스레싱이 일어나면 대부분의 시간을 페이징 처리 장치를 기다리는 큐에서 보내게 되는데, 이 경우 스레싱 자체는 일어나지 않아도 유효 액세스 시간은 늘어난다.

지역성(국부성)

지역성은 실행 중인 프로세스가 보이는 특성으로, 프로세스들이 실행 기간 동안 메모리 전체를 균일하게 접근하는 것이 아니라 일부 페이지만 집중적으로 참조하는 현상을 말한다. 프로그램의 순환(Looping), 부프로그램, 스택, 변수의 계산과 합계, 배열 순례, 순차적 코드 실행 등에서 나타나며, 프로그래머들이 서로 관련 있는 변수를 가까이 배치하는 습관 때문에도 생긴다. 지역성에는 두 종류가 있다. 시간 지역성은 한 번 참조된 기억 장소가 가까운 미래에도 계속 참조될 가능성이 높다는 뜻이고, 공간 지역성은 어떤 기억 장소를 한 번 참조하면 그 근처의 기억 장소를 참조할 가능성도 높다는 뜻이다.

작업 설정 모델(Working Set Model)

작업 설정 모델은 데닝이 프로그램의 수행 과정을 지역성 개념으로 설명하기 위해 개발했다. 프로세스가 자주 참조하는 페이지 집합을 메모리에 계속 상주시켜, 빈번한 페이지 대치를 줄이는 방법이다. 작업 설정의 크기는 ‘작업 설정 창’으로 구하는데, 매개변수 a를 이용해 ‘현재 시간(t)에서 최근의 일정 시간 단위(a)’를 정의한다. 가장 최근의 a번 페이지 참조를 조사해, 가상 시간 t로부터 프로세스가 참조한 페이지 집합을 나타낸다. 실제로 쓰이고 있는 페이지는 작업 설정에 포함되고, 마지막으로 참조된 뒤 일정 시간 동안 다시 참조되지 않으면 더는 쓰이지 않는 것으로 보고 작업 설정에서 제외된다. 따라서 작업 설정은 프로그램의 지역성을 근사적으로 나타내는 값이며, 최근 참조된 페이지들을 메인 메모리에 유지하면 프로세스가 더 빠르게 실행될 수 있다. 새로운 프로세스는 메인 메모리에 자신의 작업 설정을 담을 공간이 있을 때만 시작될 수 있다.

데닝은 시간 t에서의 작업 설정 WS(t, w)를, 시간 (t-w)부터 t까지 참조한 페이지들의 집합으로 정의했다. 여기서 t는 프로세스가 프로세서를 점유한 현재 시간이고, w는 작업 설정을 계산할 때 과거 어디까지 포함할지를 나타내는 창의 크기다.

창의 크기 w가 커질수록 메인 메모리에 유지해야 하는 작업 설정도 커지지만, w가 지나치게 커지면 메인 메모리 용량을 넘어서므로 더 이상 작업 설정이 커지지 않는다.

작업 설정에서 가장 중요한 성질은 그 크기다. 각 프로세스는 자신의 작업 설정 안에 있는 페이지를 실제로 사용하며, 프로세스 i는 wssi개의 프레임을 필요로 한다. 이 요구량이 유효 프레임 수(m)보다 많아지면(합이 m보다 크면) 스레싱이 발생한다. 프로세스가 수행되는 동안 작업 설정은 계속 변한다. a 값을 고정해두고 관찰하면, 대부분의 프로세스는 작업 설정 크기가 거의 변하지 않는 안정기와 급격히 변하는 과도기를 번갈아 겪는다. 프로세스가 처음 시작될 때는 새로운 페이지를 계속 참조하므로 작업 설정이 급격히 커지다가, 지역성의 원리에 따라 곧 안정기에 접어든다. 과도기는 프로세스가 다른 지역으로 옮겨가는(즉 국면이 전환되는) 시점을 보여준다.

운영체제는 각 프로세스의 작업 설정을 감시해, 그 크기에 맞는 충분한 프레임을 할당한다. 여분의 페이지 프레임이 있으면 준비 상태의 다른 프로세스를 불러들여 다중 프로그래밍의 정도를 높이고, 반대로 모든 프로세스의 작업 설정 크기 합이 전체 유효 프레임 수를 넘어서면 일부 프로세스를 잠시 중지시켜 페이지를 회수한다. 이런 방식으로 다중 프로그래밍의 정도를 최대한 높이면서도 스레싱을 막아, 프로세서 효율을 최적화할 수 있다.

다만 작업 설정 모델에도 몇 가지 한계가 있다. 과거의 참조 패턴이 미래의 참조를 항상 보장하지는 않고, 작업 설정의 크기와 구성 페이지는 시간에 따라 계속 바뀐다. 모든 프로세스의 작업 설정을 정확히 측정하는 것은 현실적으로 불가능하며, 작업 설정은 프로세스가 실행되는 동안 페이지가 삭제되고 추가되기를 반복해 변화가 심하다. 각 프로세스가 참조한 페이지의 시간과 순서를 담은 큐를 유지해야 하므로 메모리 관리 자체도 복잡해지고, 창 크기 매개변수 a의 최적값도 알려져 있지 않아 프로세스의 성격에 따라 크게 달라진다. 그래서 실제로는 정확한 참조 패턴 대신, 상주 집합의 크기를 늘릴수록 페이지 부재율이 낮아진다는 경험적 관계를 활용하는 방식이 많은 운영체제에서 쓰인다.

작업 설정 크기와 페이지 프레임 수, 페이지 부재율 사이에는 균형이 필요하다. 작업 설정과 프레임 수가 너무 작으면 실제 작업 페이지들이 메모리에 다 올라가지 못해 페이지 부재율이 높아지고 스레싱으로 이어질 수 있다. 반대로 너무 크면 실제 작업 페이지 외의 페이지까지 메모리를 차지해 낭비가 생기고, 다중 프로그래밍의 정도가 오히려 줄어들 수 있다.

페이지 부재 빈도(PFF, Page Fault Frequency)

PFF는 프로세스가 가진 페이지 프레임 수에 따라 페이지 부재율이 어떻게 변하는지 보여주는 그래프다. 다만 이 알고리즘은 페이지 참조가 새로운 지역으로 옮겨가는 과도기에는 잘 작동하지 않는데, 페이지가 마지막으로 참조된 후 정해진 시간 단위(a)가 지나기 전까지는 계속 그대로 유지되기 때문이다.

기타 고려 사항

여러 프로세스가 제한된 프레임을 나눠 쓰려면 할당 기준이 필요하다. 전역 대치는 특정 페이지를 누가 점유하고 있는지와 무관하게, 메인 메모리에 있는 모든 페이지를 교체 대상으로 삼는 방식이다(리눅스의 대치 전략). 구현이 쉽고 성능 분석도 간단하지만, 한 프로세스의 페이지 부재를 처리하려다 다른 프로세스의 페이지가 제거될 수 있어 각 프로세스의 페이지 부재율을 개별적으로 조절하기 어렵고, 다른 프로세스의 영향을 받아 실행이 늦어지거나 빨라질 수 있다. 지역 대치는 부재를 일으킨 프로세스 자신의 상주 페이지 중에서만 교체 대상을 고르는 방식이다(윈도우 XP의 대치 전략). 각 프로세스에 할당된 프레임 안에서만 희생자를 고르므로 구현이 쉽고 부담도 적다.

프리 페이징

프리 페이징은 프로세스 시작 초기에 몰리는 많은 페이지 부재를 막기 위해, 앞으로 쓰일 것으로 예상되는 페이지를 미리 한꺼번에 메모리로 가져오는 기법이다. 프리 페이징에 할당할 메인 메모리 크기, 한 번에 미리 가져올 페이지 수, 그리고 어떤 페이지를 가져올지 정하는 경험적 알고리즘(공간적·시간적 지역성에 근거해 예측)이 중요하다. 입출력을 여러 번 나눠서 하는 요구 페이징보다, 연속된 페이지를 한 번에 가져오는 편이 인터럽트 처리 측면에서 더 나은 성능을 낸다.

다만 프리 페이징 비용이 실제로 해결하는 페이지 부재 비용보다 낮은지 확인해야 하고, 미리 가져온 페이지 중 상당수가 결국 쓰이지 않을 수도 있다는 점을 고려해야 한다.

페이지 크기

페이지 크기를 정하는 문제는 최적 페이지 크기를 결정하는 문제와, 그에 맞는 페이지 테이블 구조를 설계하는 문제로 이어진다.