가상 메모리(feat.2)

프레임 할당 알고리즘

가상 메모리 시스템의 가장 간단한 구조
메모리 크기가 128K 인 단일 사용자 마이크로 컴퓨터 시스템에서(페이지 크기는 1K), 이 중 운영체제가 35K 를 차지한다면 남은 93K 는 사용자 프로세스를 위해 남는다.
순수 요구 페이징 방법 적용 시, 프레임 93개 모두 사용 가능 프레임 리스트에 포함 사용자가 프로세스 수행을 시작하면 페이지 부재가 발생한다. 93번까지의 페이지 부재는 사용 가능 페이지 리스트에서 대기 중인 페이지를 모두 사용하게 된다. 따라서 94번째 발생한 페이지 부재 해결을 위한 해결 방법이 필요하다.

사용 가능 페이지가 없을 때, 페이지 부재 해결 방법

페이지 대치 알고리즘을 사용
기억 장소 내에 있는 페이지 93개 중 하나를 선택하여 교체하며, 이 때 페이지 대치 알고리즘을 호출한다.
사용되지 않는 경우 사용자 페이지로 변환 시켜 사용한다.
사용 가능 리스트(93개 중)에서 프레임 3개를 확보, 페이지 부재 발생 시 항상 사용 가능 프레임이 존재하도록 한다.

최소 프레임 수

할당해야 할 최소 프레임 수 존재
각 프로세스에 할당되는 프레임 수 가 줄어들면서 페이지 부재율은 올라가며, 수행 속도는 저하된다. 성능 저하를 막기 위해 할당해야 할 최소 프레임 수가 존재한다.
최소 프레임 수는 명령어 구조에 의해 정의
수행 중인 명령이 끝나기 전에 페이지 부재 현상 발생 시 그 명령을 다시 시작해야 한다. 하나의 명령어 실행을 위해 명령어가 참조하는 모든 페이지를 수용할 수 있는 충분한 프레임이 필요하다. 한 프로세스 당 최소 프레임 수는 컴퓨터 구조에 의해 정의되나, 최대 수는 유효 실제 기억 장소의 양으로 정의된다.

균일과 비례할당 알고리즘

균일 할당: 프로세스 n개의 프레임 m개를 할당할 때, 각 프로세스에 똑같이 프레임 m/n개씩 나눈다.
비례 할당: 균일 할당 방법의 문제점을 해결하기 위해 사용된다.
균일과 비례 할당 기법 모두 다중 프로그램 정도에 따라 할당되는 양이 변하며, 우선 순위를 고려하지 않는다.

부하 제어(Load Control)

메인 메모리에서 실행할 프로세스의 개수 결정
메인 메모리에 적재되어 실행되는 프로세스의 개수를 '다중 프로그래밍 수준’이라 한다.
메모리 관리를 위해 매우 중요하다.
너무 적은 수의 프로세스가 메인 메모리에서 실행된다면 프로세스들의 보류 상태가 자주 발생, 빈번한 교체가 발생 많은 프로세스가 메인 메모리에 적재되면 각 프로세스의 적재집합을 구성하는 평균 페이지 수가 적어 페이지 부재가 자주 발생, 스레싱 현상을 일으킨다.

스레싱

페이지 교환이 계속 일어나는 현상
어떤 프로세스가 프로세스 수행에 보내는 시간보다 페이지 교환에 보내는 시간이 더 크면 ‘스레싱을 하고 있다’ 말한다.

발생원인

운영체제는 항상 프로세서의 효율성(이용률)을 감시하여 운영
이용률이 떨어지면 이를 높이기 위해 새로운 프로세스를 도입, 다중 프로그래밍의 정도를 높인다.
새로운 프로세스가 수행 중인 프로세스의 페이지를 빼앗아서 수행을 시작할 경우 더 많은 페이지 부재 발생 프로세서가 요구하는 최소한의 수보다 페이지 프레임 수가 적으면 적을수록 페이지 부재율이 증가한다. 페이지 부재가 많이 일어날수록 프로세스가 페이징 처리 장치를 기다리는 시간이 길어지므로 프로세스의 효율성은 떨어진다. 페이지 부재로 프로세서의 이용률 감소 시 스레싱이 발생하여 시스템의 처리율은 낮아지고 페이지 부재는 늘어나 유효 메모리 액세스 시간이 증가, 페이지 교체시간이 낭비된다.

프로세서의 이용률과 다중 프로그래밍의 정도에 따라 다르다.

다중 프로그래밍의 정도가 높아지면 프로세서의 이용률도 최대값이 될 때까지 증가한다.

다중 프로그래밍의 정도가 더욱 커지면 스레싱이 발생, 프로세서의 이용률은 급격히 떨어진다.

프로세서의 이용률을 높이고 스레싱을 중단하려면 다중 프로그래밍의 정도를 낮춰야 한다.

예방

지역 교환 알고리즘이나 우선 순위 교환 알고리즘을 사용하여 제한할 수 있다.
지역 교환 알고리즘 사용 시 프로세스 하나에 스레싱이 발생하더라도 다른 프로세서에서 프레임을 가지고 올 수 없어 다른 프로세스는 스레싱 현상에 빠지지 않는다. 여러 프로세스에서 스레싱이 발생할 경우 프로세스들은 대부분의 시간을 페이징 처리 장치를 기다리는 큐에서 보낸다. 스레싱은 발생하지 않으나 유효 액세스 시간은 증가한다.

지역성(국부성)

실행중인 프로세스에 의해 나타나는 특성
프로세스들은 실행기간 동안 메모리 내의 정보를 균일하게 액세스하는 것이 아닌 페이지 중 일부를 선호하여 지역적인 부분만을 집중적으로 참조하는 현상
프로그램들의 순환(Looping)이나 부 프로그램, 스택, 변수들의 계산과 합계, 배열 순례, 순차적 코드의 실행 등으로 발생
프로그래머들이 관련 있는 변수들을 서로 근처에 배치시키기 때문에 발생한다.
여러 페이지에 대한 프로세스의 메모리 참조 유형

종류

시간 지역성: 참조된 기억장소는 가까운 미래에도 계속 참조될 가능성이 높음을 의미한다.
공간 지역성: 프로세스가 어떤 기억장소를 한 번 참조하면, 이후에 참조한 기억 장치 근처에 있는 기억 장소를 참조할 가능성이 높음을 의미한다.

작업 설정 모델(Working Set Model)

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

프로세스 작업 설정 정의

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

창 크기와 작업 설정

w 가 증가함에 따라 작업 설정의 크기가 변한다. 창의 크기(설정 시간 간격) w 가 커짐에 따라 메인 메모리에 유지하는 작업 설정이 커지나, w가 너무 커지면 메인 메모리의 용량을 초과하므로 작업 설정도 증가하지 않는다.

작업 설정의 가장 중요한 성질은 작업 설정의 크기

각 프로세스는 각 작업 설정 내에 있는 페이지를 실제로 사용하고 있다. 프로세스 i는 wssi 프레임을 필요로 한다. 유효 프레임 (m) 수 보다 많이 요구하게 되면 (d > m ) 스레싱 발생 프로세스가 수행되는 동안, 작업 설정은 계속 변화한다.
a 값이 고정된 경우, 시간이 경과함에 따라 변화되는 작업 설정 크기
대부분의 프로세스에서 작업 설정의 크기가 비교적 변화가 없는 안정기와 급격하게 변화하는 과도기 반복되는 현상을 보인다. 프로세스가 처음 시작되면 새로운 페이지를 참조하므로 작업 설정의 크기가 급격하게 커진다. 지역성의 원리에 의거하여 프로세스는 안정기에 접어들게 되며, 과도기는 프로세스가 다른 지역으로 이동(프로세스의 전환)함을 보여준다.

작업 설정 모델 사용법

운영체제는 각 프로세스의 작업 설정을 감시, 각 프로세스에 작업 설정의 크기에 맞는 충분한 프레임을 할당한다.
여분의 페이지 프레임이 있을 떄는 준비 상태에 있는 다른 프로세스를 불러들인 후 프레임을 할당하여 다중 프로그램의 정도를 증가한다.
모든 프로세스가 갖는 작업 설정 크기의 합이 전체 유효 프레임의 수 보다 커지게 되면, 잠시 중지 시킬 프로세스를 선정하여 페이지를 회수한다. 가능한 다중 프로그래밍의 정도를 높이면서 스레싱을 방지하는 효과를 제공, 프로세서의 효율성을 최적화시킨다.

작업 설정 모델에서 해결해야 할 문제점

우선 작업 설정이 갖는 과거의 참조가 미래의 참조를 항상 보장하지 않는다.
작업 설정의 크기와 구성 페이지들은 시간 경과에 따라 변한다.
각 프로세스에 대한 작업 설정을 모두 측정한다는 것은 현실적으로 불가능하다.
작업 설정은 프로세스가 실행됨에 따라 삭제, 추가되기도 하므로 변화가 심하다.
각 프로세스가 참조한 페이지 시간과 시간 순서로 된 페이지 큐를 유지해야하므로 작업설정에 의한 메모리 관리는 복잡하다.
작업 설정 창의 크기를 나타내는 매개변수 a 의 최적값이 알려지 있지 않으며, 처리되는 프로세스의 성격에 따라 a 의 최적값은 매우 다양하다.
정확한 참조 대신 프로세스의 페이지 부재율에 관심을 갖고 프로세스 상주 집합의 크기를 늘리는 만큼 페이지 부재율은 낮아지는 효과를 활용한 결과로 많은 운영체제에서 사용된다.

작업 설정 크기에 따른 페이지 프레임 수, 페이지 부재율과의 관계

작업 설정 크기가 너무 작고 페이지 프레임 수가 적으면 페이지 부재율이 높아 프로세스의 실제 작업 페이지들이 메모리에 있지 않고 스레싱 현상을 일으킬 수 있다.
작업 설정 크기가 너무 크고 페이지 프레임 수가 너무 많으면 프로세스의 실제 작업 페이지들 뿐만 아니라 다른 페이지까지 메모리를 차지하여 메모리 낭비가 발생하며 다중 프로그래밍의 정도를 감소 시킬 수 있다.

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

하나의 프로세스가 갖는 페이지 프레임 수에 따라 페이지 부재 비율이 변화 하는 과정을 보여주는 그래프
페이지 부재 빈도 알고리즘은 페이지 참조가 새로운 지역으로 이동하는 과도기에는 제대로 작동하지 않는다.(페이지가 마지막으로 참조된 후 임의의 시간 단위(a)가 경과되기 전까지 그대로이다.)

기타 고려 사항

여러 프로세스가 제한된 수의 프레임 사용을 위해 할당 기준이 필요
전역 대치: 특정 페이지를 점유하고 있는 프로세스에 관계없이 메인 메모리에 있는 모든 페이지는 대치 대상이 된다.
문제점: 한 프로세스의 페이지 부재 처리를 위해 다른 프로세스의 페이지가 제거될 수 있어 각 프로세스의 페이지 부재비율을 조절할 수 없다. 다른 프로세스의 영향을 받기 때문에 프로세스의 실행이 늦어지거나 빨라질 수 있다.
페이지 대치 범위를 모든 프로세스에 적용(리눅스의 대치 전략). 프로세스가 교체할 프레임을 다른 프로세스로부터 획득 성능 분석이 쉽다.
지역 대치: 부재를 일으킨 프로세스의 상주 페이지에서 대치할 페이지를 선택한다.
프로세스를 개별적으로 제한(윈도우 xp의 대치 전략). 각 프로세스에 할당된 프레임들 중에서만 교체할 희생자를 선택 가능 구현이 쉽고 부담이 적다.

프리 페이징

처음에 발생하는 많은 페이지 부재를 방지하기 위한 기법
예상되는 모든 페이지를 사전에 한꺼번에 메모리 내로 가져온다.
프리 페이징에 할당된 메인 메모리 크기와 한 번에 미리 가져올 수 있는 페이지 수 그리고 어떤 페이지를 미리 가져올 지 결정할 수 있는 경험적(공간적, 시간적 지역성에 따라 예상하는)알고리즘이 중요하다.
입출력 인터럽트를 위해 연속된 페이지를 한 번에 메모리로 가져와 입출력을 여러 번 수행하는 요구 페이징 보다 좋은 성능을 보여준다.

문제점

프리 페이징 비용이 그에 상당하는 페이지 부재를 해결하는데 드는 비용보다 적은지 확인이 필요하다.
페이징에 의해 메모리로 돌아온 페이지 중에서 상당 수 는 사용되지 않을 수 있다.

페이지 크기

최적 페이지 크기에 관한 결정
페이지 테이블 구조