메모리 관리 기법은 프로세스가 생성될 때 프로세스의 주소공간이 반드시 실제 메모리에 존재해야 한다. 따라서 실제 메모리보다 더 큰 프로세스는 실행시킬 수 없다. 그러나 가상 메모리(virtual memory)는 실제 메모리보다 더 큰 프로세스의 실행을 가능케 하는 메모리 관리 기법이다.
일반적으로 가상 메모리를 지원하는 시스템에서는 디스크와 같은 보조 기억 장치의 일부분을 마치 실제 메모리처럼 활용한다. 프로세스의 전체 주소공간은 가상 메모리에 유지하면서 프로세스 실행에 필요한 부분만을 실제 메모리에 적재시킴으로써 프로세스를 실행 시킨다. 따라서 사용자는 실제 메모리보다 더 큰 메모리가 존재하는 것처럼 느끼게 된다. 가상 메모리 주소공간과 실제 메모리 주소 공간이 서로 다름을 유의해야 한다.
실제 메모리 주소 공간은 하나이지만 프로세스마다 자신의 가상 메모리 주소 공간이 존재한다.
가상 메모리의 주소를 물리 메모리의 주소인 물리 주소(physical address)와 구별하여 가상 주소(virtual address)라고 부른다. 따라서 프로세스가 실행되는 과정에서 가상 주소는 물리 주소로 변환되어야 한다.
가상 메모리에서 주소 변환 과정은 페이징(paging)혹은 세그멘테이션(segmentation)기법을 적용할 수 있다. 가상 메모리를 지원하는 운영체제에서는 실행 중인 프로세스의 전체 페이지 혹은 세그멘트가 실제 메모리에 반드시 존재하는 것이 아니기 때문에 이들에 대한 실제 메모리의 존재 여부를 파악할 수 있는 정보가 추가적으로 필요하다.
ex)해당 페이지의 실제 메모리 존재여부에 대한 정보를 유지하기 위해 페이지 사상 테이블에 존재 비트를 추가한다.
가상 메모리를 위한 페이지 사상 테이블
페이지 사상 테이블의 존재 비트는 해당 페이지의 실제 메모리 존재 여부를 나타내고 있다. 존재 비트가 1이면 해당 페이지가 메모리에 적재되어 있음을 의미하고 존재 비트가 0이면 해당 페이지가 메모리에 부재함을 의미한다.
만약 실제 메모리에 존재하지 않은 프로세스의 일부분(페이지 혹은 세그멘트를 참조하려고 할 경우에는 시스템 오류가 발생하게 된다. 이러한 시스템 오류를 페이지 부재(page fault) 혹은 세그멘트 부재(segment fault)라고 부른다. 가상 메모리를 지원하기 위하여 이러한 오류를 처리할 수 있는 운영체제의 기능이 요구된다.
가상 메모리 기법에서는 디스크와 같은 보조 기억 장치를 이용하여 사용자에게 가상의 연속적인 메모리 공간을 지원함으로써 실제 메모리 크기보다 더 큰 프로세스를 실행시킬 수 있는 장점이 있다. 그러나 프로세스의 일부만이 실제 메모리에 적재된 상태에서 프로세스가 실행되기 때문에 프로세스의 실행 속도가 저하되는 단점이 있다.
가상 메모리를 효과적으로 관리하기 위해 고려되는 사항
반입 정책(fetch policy) : 언제 필요한 프로세스의 일부분을 가상 메모리로부터 설계 메모리로 가져올 것인가?
교체 정책(replacement policy) :실제 메모리 공간이 부족할 경우, 어느 부분을 교체할 것인가?
할당 정책(allocation policy) : 각 프로세스마다 얼마 만큼의 실제 메모리 공간을 할당할 것인가?
가상 메모리를 지원하는 시스템에서는 프로세스의 가상 메모리 주소공간과 실제 메모리 주소 공간이 분할되어야 한다.
분할 방법은 일정한 크기로 고정 분할하는 페이징 기법과 가변 크기로 분할하는 세그멘테이션 기법을 적용할 수 있다.
반입 정책
반입 정책에는 페이지 참조 요구가 발생했을 때 반입을 시도 하는 요구 페이징(demand paging)과 페이지 참조를 미리 예상하여 반입하는 예상 페이징(anticipoatory paging)이 있다.
요구 페이징
요구 페이징은 프로세스가 실행되는 과정에서 참조하려는 페이지에 대한 페이지 부재 오류가 발생할 때 가상 메모리로부터 해당 페이지를 실제 메모리로 적재하는 것이다. 따라서 프로세스의 실행이 시작되며 맨 처음 참조하는 페이지부터 페이지 부재 오류가 발생하게 될 것이다.
페이지 부재 오류가 발생하게 되면 제어가 운영체제로 넘어가며 운영체제에셔는 해당 페이지를 가상 메모리로부터 실제 메모리에 적재한다. 운영체제 내부에서 이러한 기능을 담당하는 루틴을 페이저(pager)라고 부른다.
페이저에 의해 페이지 부재를 처리하는데 소요되는 시간은 가상 메모리를 지원하는데 발생하는 오버헤드로써 시스템 성능에 직접적인 영향이 있다.
유효 접근 시간은 페이지 부재가 발생하지 않을 경우에는 실제 메모리 접근 시간과 같다. 그러나 부재가 발생하지 않을 경우에는 실제 메모리 접근 시간과 같다. 그러나 페이지 부재가 발생하게 되면 보조 기억장치로부터 해당 페이지를 적재한 후 페이지 부재 처리 루틴을 수행하는데 소요되는 시간이 된다.
페이지 부재율을 p(0<= p <= 1)라고 할 때 요구 페이징 시스템에서 메모리에 접근하는데 소요되는 유효 접근 시간은 다음과 같다.
유효 접근 시간 = (1-p) x 실제 메모리 접근 시간 + p x 페이지 부재 처리 시간
ex) 실제 메모리 접근 시간이 100nsec이고 페이지 부재 처리 시간이 25msec인 요구 페이징 시스템에서 1,000번 메모리 접근에 1번의 페이지 부재가 발생할 경우 유효 접근 시간은 아래와 같이 계산
유효 접근 시간 = (1-p) x 100 + p x 25,000,000
= 100 + 24,999,900 x 0.001
≒ 25,000(nsec) -> 대략 25,000(nsec)
페이지 부재율 (p)이 1/1,000 임에도 불구하고 유효 접근 시간은 대략 25,000ns으로써 실제 메모리 접근 시간(100ns)에 비해 250배 증가됨을 알 수 있다. 따라서 요구 페이징 시스템에서 페이지 부재율을 낮게 유지하는 것이 매우 중요하다.
예상 페이징
예상 페이징 기법은 참조하려는 페이지를 미리 예측하여 해당 페이지를 메모리에 적재하는 반입 정책으로써 '선페이징(prepaging)'이라고도 부른다. 만약 올바른 예측으로 참조 페이지들을 한번에 미리 반입할 수 있다면 요구 페이징 보다 프로세스의 실행 시간을 크게 감소시킬 수 있을 것이다. 그러나 프로세스가 실행되는 과정에서 참조 페이지를 미리 예측하기란 매우 어려운 일이며, 요구 페이징에서는 반입된 페이지의 참조를 확신할 수 있지만 예상 페이징에 의해 반입된 페이지의 참조는 확신할 수 없다.
일반적으로 프로세스가 실행되는 과정에서 메모리 주소 공간이 전체를 균일하게 참조하지 않고 일부분을 집중적으로 참조하는 경향이 있다. 이러한 경향을 '참조의 지역성(locality)'라고 부른다. 참조의 지역성에는 '시간적 지역성(emporal locality)'과 '공간적 지역성(spatial locality)'이 있다. 시간적 지역성은 일정 시간동안 동일한 주소 공간을 반복적으로 참조하는 경향으로써 프로세스가 반복분과 같은 명령어를 처리할 경우에 나타난다. 반면 공간적 지역성은 일정 시간동안 동일한 주소 공간을 반복적으로 참조하는 경향으로써 프로세스가 반복문과 같은 명령어를 처리할 경우에 나타난다. 반면 공간적 지역성은 일정 시간 동안 인저보딘 주소 공간을 연속적으로 참조하는 경향으로써 프로세스가 배열의 초기화와 같은 명령어를 처리할 경우에 나타난다.
참조의 지역성은 최근에 참조된 페이지들 혹은 참조하려는 페이지와 인접한 페이지들이 가까운 장래에 참조될 가능성이 높다고 볼 수 있다. 따라서 예상 페이징 기법은 프로세스가 실행되는 과정에서 어떤 페이지가 참조될 경우 인접한 페이지들도 한번에 반입한다. 그러나 이러한 예측이 잘못될 수도 있기 때문에 대부분의 가상 메모리 시스템에서는 요구 페이징 기법을 사용하고 있다.
교체 정책
페이징 기법을 이용한 가상 메모리 시스템에서 실제 메모리의 빈 공간이 없는 상황에서 페이지 부재가 발생할 경우 실제 메모리에 적재된 임의의 페이지에 해당되는 프레임을 가상 메모리로 내보내야 한다. 이러한 상황에서 어떤 페이지의 프레임을 그 대상으로 선택해야 할 것인가에 대한 결정을 위한 교체 정책은 가상 메모리 시스템의 성능에 직접적인 영향을 미치기 때문에 매우 중요하다.
교체 정책이 가상 메모리 시스템의 성능에 미치는 영향은 프로세스가 실행되는 과정에서 페이지들의 참조 순서와 프로세스에게 할당된 프레임 수에 따라 다르게 평가될 수 있다.
ex) 350, 254, 148, 075, 328, 232, 485, 386, 238, 184 의 경우 페이지의 크기가 100바이트라고 가정하면 프로세스의 페이지가 참조되는 순서는 다음과 같으며 이 순서를 페이지의 참조 열(reference string)이라고 부른다.
(3, 2, 1, 0, 3, 2, 4, 3, 2, 1)
선입 선출(FIFO : First-In First-Out) 교체
선입 선출(FIFO : First-In First-Out)은 가장 간단한 교체 정책으로써 시간적으로 가장 먼저 실제 메모리에 적재된 페이지를 교체의 대상으로 선택한다. 다시 말해서 가장 오랫동안 실제 메모리에 적재된 페이지를 교체의 대상으로 선택하는 것이다.
FIFO 페이지 교체 기법
처음 3개의 페이지(3, 2, 1) 참조에 대한 페이지 부재 발생으로 3개의 페이지가 3개의 프레임에 각각 적재된다. 그러나 4번째 페이지(0)가 참조되는 시점에서는 빈 프레임이 없으므로 가장 먼저 적재된 페이지(3)가 교체 대상으로선택된다. 동일한 방법으로 교체할 경우 총 10회 페이지 참조 중에서 8회 페이지 부재가 발생할 수 있음을 알 수 있다. 따라서 페이지 부재율은 80%가 된다.
일반적으로 프로세스 당 프레임 할당량이 증가할수록 페이지 부재율은 감소되는 것이 정상적이나 선입선출 알고리즘에서는 프로세스당 프레임 할당량이 증가하여도 오히려 페이지 부재율은 증가하는 현상 발생할 수도 있음을 유의해야한다. 이러한 현상을 "Belady의 이상현상" 이라고 부른다.
ex)
최적(OPT: Optimal) 교체
Belady는 페이지 부재율을 최소화할 수 있는 최적의 교체 정책을 제안하였다. 이 정책은 시간적으로 가장 오랫동안 참조되지 않은 페이지를 교체의 대상으로 선택한다. 적재된 페이지들 중에서 더 이상 필요없는 페이지 혹은 가장 나중에 참조될 페이지를 교체의 대상으로 선택하는 것이다.
최적 페이지 교체 기법
처음 3개의 페이지(3, 2, 1) 참조에 대한 페이지 부재 발생으로 3개의 페이지가 3개의 프레임에 각각 적재된다. 그러나 4번재 페이지(0)가 참조되는 시점에서는 빈 프레임이 없으므로 가장 오랫동안 참조되지 않을 페이지(1)가 교체 대상으로 선택된다 동일한 방법으로 교체할 경우 페이지 부재율은 60%로써 FIFO 교체정책보다 낮아짐을 알 수 있다.
OPT 교체 정책을 구현하기 위해서는 페이지 참조에 대한 예측이 필요하다, 그러나 정확한 예측은 불가능하기 때문에 실제로 OPT 교체 정책을 구현할 수 없지만 이론적으로 다른 교체정책들을 비교 평가하는데 중요한 척도로서 의미가 있다.
LRU(Least Recently Used) 교체
LRU정책은 페이지 참조의 시간적 역성을 고려하여 FIFO 교체정책에서 Belady의 이상현상을 해결하고 OPT 교체정책의 예측에 대한 문제점을 개선하기 위하여 제안된 것이다 .이 정책은 어떤 페이지가 참조되면 가까운 장래에 그 페이지가 또 다시 참조된다는 시간적 지역성을 고려하여 가장 최근에 참조되지 않은 페이지를 교체의 대상으로 선택한다. 적재된 페이지들 중에서 가장 오래 전에 참조된 페이지를 교체의 대상으로 선택하는 것이다.
LRU 교체 기법
처음 3개의 페이지(3, 2, 1) 참조에 대한 페이지 부재 발생으로 3개의 페이지가 3개의 프레임에 각각 적재된다. 그러나 4번째 페이지(0)가 참조되는 시점에서는 빈 프레임이 없음으로 가장 최근에 참조되지 않은 페이지(3)가 교체 대상으로 선택된다. 동일한 방법으로 교체할 경우 페이지 부재율은 80%가 된다.
일반적으로 LRU 교체정책은 FIFO 교체정책보다 평균적으로 페이지 부재율이 개선되기 때문에 가장 널리 사용되고 있다. 그러나 LRU 교체 정책을 구현하기 위해서는 페이지가 참조된 순서를 효과적으로 유지, 관리할 필요가 있다. 이를 위하여 운영체제에서는 다음과 같은 방법으로 참조 순서를 유지 관리한다.
계수기(Counter)를 이용하는 방법
계수기를 이용하는 방법은 정확한 페이지 참조시간 대신에 상대적인 시간으로 참조 순서를 유지 관리한다. 이를 위하여 프로세스의 페이지 사상 테이블에 페이지 참조 순서를 기록하기 위한 계수기 부분을 추가한다.
ex) CPU 내부의 레지스터를 이용하여 페이지가 참조될 때마다 레지스터 값을 1씩 증가시켜 그 값을 페이지 사상 테이블의 계수기 부분에 기록하도록 한다. 따라서 계수기 값이 작을 수록 가장 최근에 참조되지 않은 페이지임을 의미한다. 페이지 교체가 요구될 때마다 프로세스의 페이지 사상 테이블에서 적재된 페이지들의 계수기 부분을 비교하여 가장 작은 값의 페이지를 교체 대상으로 선택한다.
이 방법을 사용할 경우 페이지가 참조될 때마다 계수기 값을 갱신하여야 하며, 페이지 교체 때마다 프로세스의 페이지 사상 테이블을 검색해야 하기 때문에 오버헤드가 존재한다. 또한 계수기 값이 증가함에 따라 CPU 내부의 레지스터의 오버플로우(overflow)도 고려해야 한다.
스택(Stack)을 이용하는 방법
프로세스의 페이지 개수만큼 스택(stack) 구조의 자료구조를 이용한다. 페이지가 참조될 때마다 그 페이지 번호를 스택의 맨 위로 이동함으로써 가장 최근에 참조되지 않은 페이지가 스택의 맨 아래에 유지되도록 한다. 따라서 항상 스택의 맨 아래에 존재하는 페이지를 교체 대상으로 쉽게 선택할 수 있다.
ex) 페이지 참조열(3, 2, 1, 0, 3, 2, 4, 3, 2, 1)일 경우 A, B 시점에서의 스택 상태
LRU 교체 기법을 위한 스택
페이지가 참조될 때마다 그 페이지를 스택의 위로 옮김으로써 스택의 바닥에는 항상 최근에 참조되지 않은 페이지가 존재한다. 따라서 페이지 교체가 요구되면 스택의 바닥에 존재하는 페이지를 교체 대상 페이지로 선택한다.
이 방법을 사용할 경우 페이지가 참조될 때마다 스택의 내용을 검색하여 해당 페이지를 제거하여 스택의 맨 위로 옮기고 나머지 스택을 적절하게 수정해야 하기 때문에 스택을 이중 연결 리스트(doubly linked list) 형태로 구현하는 것이 유리하다.
결국 LRU 교체 정책에서는 페이지의 참조 순서를 유지, 관리 하기 위하여 페이지가 참조될 때마다 페이지 사상 테이블 혹은 스택을 갱신해야하는 오버헤드가 존재한다. 이러한 오버헤드를 개선하기 위해서는 하드웨어의 지원이 요구된다.
LRU 근사( LRU Approximation) 교체
LRU 근사 교체 정책은 LRU 교체 정책에서 페이지의 참조 순서를 유지, 관리하기 위한 오버헤드를 개선하기 위하여 하드웨어의 지원을 이용한 페이지 교체 정책으로써 다음과 같은 것들이 있다.
참조 비트(reference bits)
프로세스의 페지이 자상 테이블에 페이지 참조 비트를 추가한다. 참조 비트는 일정 주기 동안 페이지가 참조될 때마다 1로 설정된다. 페이지 교체가 요구될 때 운영체제는 참조 비트가 0인 페이지들 중에서 FIFO 방식으로 교체하는 것이다. 또한 모든 페이지의 참조 비트가 1이 되는 경우를 방지하기 위하여 운영체제는 주기적으로 모든 페이지의 참조 비트를 0으로 리셋한다.
참조 비트가 0인 페이지는 페이지 일정 주기 동안 한번도 참조되지 않았음을 의미한다. 따라서 페이지의 일정 주기 동안 참조 순서는 정확히 알 수 없지만 참조 여부는 판단할 수 있다. 참조 순서를 보다 정확하게 유지하기 위하여 참조 비트를 추가할 수 있다.
ex) 8비트의 참조 비트를 사용할 경우 클럭 인터럽트를 이용하여 운영체제에서 1초 간격으로 참조 비트 값을 오른쪽으로 이동시킨다. 이 경우 참조 비트 값이 00000000인 페이지는 최근 8초동안 한 번도 참조되지 않았음을 의미하고 참조 비트의 값이 11111111인 페이지는 최근 8초동안 매초마다 한 번 이상 참조되었음을 의미한다. 따라서 최근 8초동안의 참조 이력을 유지할 수 있으며 페이지 교체가 요구될 때 적재된 페이지들 중에서 참조 비트의 값이 가장 작은 페이지를 교체 대상으로 선택할 수 있다.
이차 기회(second chance)
이차 기회 기법은 FIFO 교체정책에 한 개의 참조 비트를 추가하여 LRU 교체 정책의 효과를 기대하는 방법이다.
페이지가 처음으로 적재될 때 참조 비트의 초기 값은 1로 설정된 후 그 페이지가 참조될 때마다 1로 설정한다. 페이지 교체가 요구될 때 FIFO 방식으로 진행하면서 참조 비트를 검사하여 참조 비트가 0일 경우에만 교체한다. 만약 참조 비트가 1일 경우 그 페이지는 교체하지 않고 참조 비트를 0으로 변경한 후 다음 페이지의 참조 비트를 검사한다.
참조 비트가 1인 페이지에게 한 번의 기회를 주는 점만 제외하면 FIFO 교체 정책과 동일하다. 참조 비트가 1인 페이지는 참조 비트가 0인 페이지보다 최근에 사용되었음을 의미함으로 보다 최근에 사용된 페이지에게 이차 기회를 줌으로써 LRU 교체 정책의 효과가 있음을 알 수 있다.
메모리에 적재된 모든 페이지들을 참조 비트와 함께 환영 큐(circular queue)로 연결하여 적재된 순서를 유지함으로써 페이지 교체가 요구될 때 FIFO 방식으로 교체 대상 페이지를 선정한다.
이차 기회(Second Chance)
다음 희생자로 선정된 페이지의 참조 비트가 1이기 때문에 그 페이지를 곧바로 교체하지 않고 단순히 참조 비트의 값을 0으로 변경한 후 계속해서 FIFO 방식으로 참조 비트가 0인 페이지를 다음 희생자로 선정한다. 극단적으로 모든 페이지의 참조 비트가 1일 경우에는 환형 큐를 한 바퀴 순회하게 되어 결국 FIFO 방식에 의해 첫 번째 선정되었던 페이지가 교체될 것이다. 이 방식은 시계 바늘이 도는 거소가 유사하기 때문에 "클럭(clock) 방식"이라고도 부른다.
참조 및 변경 비트
실제 메모리에 적재된 페이지들 중에서 그 내용이 변경되지 않은 페이지는 가상 메모리의 내용과 동일하기 때문에 변경된 페이지보다 교체하는데 소요되는 시간이 짧다. 이러한 사실을 고려하기 위하여 프로세스의 페이지 사상 테이블에 페이지 참조 비트(reference bit)와 변경 비트(modified bit)를 추가한다.
페이지 부재로 인해 실제 메모리에 적재될 때 참조 비트와 변경 비트의 초기 값은 운영체제에 의해서 0으로 설정되고 페이지가 참조 혹은 변경될 때 각각 1로 설정된다. 따라서 실제 메모리에 적재된 페이지들의 비트 조합(참조, 변경)은 다음 4가지의 경우에 속하게 된다.
(0, 0) - 최근에 참조되지 않고 변경되지 않은 상태
(0, 1) - 최근에 참조되지 않고 변경된 상태
(1, 0) - 최근에 참조되고 변경되지 않은 상태
(1, 1) - 최근에 참조 및 변경된 상태
페이지 교체가 요구되면 참조 및 변경 비트를 비교하여 그 값이 가장 작은 페이지를 교체 대상 페이지로 선택한다. 이 방법은 참조 비트가 1인 페이지는 참조 비트가 0인 페이지보다 최근에 사용되었음을 의미함으로 참조 비트에 변경 비트를 추가한 LRU 근사 기법임을 알 수 있다.
계수(Counting) 기법
계수 기법은 페이지가 참조된 횟수를 고려하여 교체 대상 페이지를 선택하는 기법으로써 다음과 같은 방법이 있다.
LFU(Least Frequently Used)
LFU기법은 참조된 횟수를 비교하여 가장 적게 참조된 페이지를 교체 대상 페이지로 선택하는 것으로써 NFU 기법이라고 부른다.
MFU(Most Frequently Used)
MFU기법은 참조된 횟수를 비교하여 가장 많이 참조된 페이지를 교체 대상 페이지로 선택하는 것이다.
지역(Local) 혹은 전역(Global) 교체
프로세스가 실행되는 과정에서 그 프로세스에게 할당된 프레임의 수는 변하지 않는다.
이러한 방식을 지역(local)교체라고 한다.
전역(global)교체는 시스템의 모든 프로세스에게 할당된 프레임 중에서 교체 대상 페이지를 선택할 수 있기 때문에 그 프로세스에게 할당된 프레임의 수는 증가하게 되며 다른 프로세스는 상대적으로 감소하게 된다.
전역교체는 다른 프로세스의 실행 속도에 직접적인 방향을 미치게 됨으로 시스템 전체의 상태를 고려해야 한다.
할당 정책
가상 메모리 시스템에서 할당 정책은 프로세스마다 얼마만큼의 실제 메모리 공간을 할당할 것인가를 결정하는 것이다. 일반적으로 프로세스당 실제 메모리의 공간을 많이 할당하게 되면 페이지 부재율은 낮아지지만 다중 프로그래밍의 정도가 낮아지기 때문에 CPU 이용률이 떨어지게 된다.
프로세스당 실제 메모리의 공간을 너무 적게 할당하게 되면 반대 현상이 발생하게 될 것이다. 따라서 가상 메모리 시스템에서 할당 정책은 시스템의 성능에 직접적인 영향을 미치기 때문에 아래의 사항을 고려해 결정해야 한다.
균등 혹은 비례 할당
제한된 프레임을 프로세스들에게 할당하는 방법에는 균등 할당과 비례 할당이 있다.
균등 할당은 모든 프로세스에게 실제 메모리 공간을 균등하게 할당하는 것이다.
ex) 실제 메모리 공간이 m개의 프레임으로 구성되어있고 프로세스가 n개일 경우 각각의 프로세스에게 m/n 개의 프레임을 균등하게 할당하는 것이다. 이 방법은 간단하지만 프로세스의 크기를 고려하지 않기 때문에 실제 메모리 공간의 이용이 비효율적이다.
비례 할당은 프로세스의 크기에 따라 비례적으로 할당하는 것이다.
ex) 실제 메모리 공간이 m개의 프레임으로 구성되어 있고 i개의 페이지로 구성된 프로세스(P1)과 j개의 페이지로 구성된 (P2)가 있을 경우 i / (i+j) * m 개의 프레임과 j / (i+j) * m개의 프레임을 P1, P2에게 각각 할당하는 것이다.
이러한 방법들은 다중 프로그래밍의 정도에 따라 할당량을 동적으로 조정해야하는 오버헤드가 있다. 또한 프로세스의 우선순위와 전혀 관계없이 결정된다. 따라서 프로세스의 크기와 우선순위를 고려하여 비례적으로 할당량을 결정할 수 있다.
스레싱
스레싱이란 "프로세스가 진행하는 과정에서 페이지 부재가 너무 자주 발생하여 프로세스의 실제 처리 시간보다 페이지 부재 처리 시간이 더 많이 소요되는 현상"을 말한다. 이러한 현상은 시스템 성능의 급격한 저하를 초래하게 된다.
스래싱 원인
일반적으로 다중 프로그래밍의 정도가 증가함에 따라 CPU 이용률도 증가한다. 따라서 다중 프로그래밍을 지원하는 시스템에서는 CPU 이용률을 최대화하기 위하여 CPU 이용률이 떨ㅇ어지게 되면 새로운 프로세스를 메모리에 적재하여 다중 프로그래밍의 정도를 높이게 된다.
시스템에서 페이지 부재가 자주 발생하게 되면 디스크 입ㅊ출력에 의해 CPU 이용률은 점점 떨어지게 될 것이고 운영체제는 CPU의 이용률을 향상시키기 위하여 또 다른 프로세스를 적재하게 될 것이다. 이러한 상황이 반복될 경우 다중프로그래밍의 정도가 증가함에 따라 CPU 이용률이 어느정도 증가하다 갑자기 저하되는 현상이 발생하게 된다.
다중 프로그래밍의 정도가 증가함에 따라 CPU의 이용률도 최대값이 될 때까지 증가할 것이다. 그러나 다중 프로그래밍의 정도가 너무 증가하게 되면 프로세스당 사용 가능한 프레임의 수가 감소하기 때문에 페이지 부재가 점점 더 자주 발생하게 되어 프로세스의 실제 처리시간보다 페이지 부재 처리 시간이 더 많이 소요되는 스래싱 현상이 발생하게 될 것이다.
스래싱 방지책
스래싱 현상을 방지하기 위한 가장 좋은 방법은 프로세스가 필요로 하는 프레임을 충분히 할당하는 것이다. 그러나 가상 메모리를 지원하는 시스템에서는 프로세스가 필요로 하는 프레임을 충분히 할당할 수 없기 때문에 운영체제는 스래싱 현상이 발생하지 않을 정도의 프레임 수를 항상 유지해야 할 필요가 있다.
워킹 셋(working set)
워킹 셋 기법은 참조의 지역성(locality)이론에 근거하여 프로세스가 실행되는 과정에서 어떤 페이지들을 주로 사용하고 있는가를 추적하여 이러한 페이지들을 메모리에 유지함으로써 스래싱 현상을 방지하려는 것이다. 워킹 셋이란 최근 일정시간 동안 프로세스가 참조하는 페이지들의 집합이다.
워킹 셋을 이용하여 스래싱 현상을 방지하기 위해서 운영체제는 프로세스가 실행되는 과정에서 워킹 세트를 유지관리하여야 한다. 정확한 워킹 세트를 유지하는데 중요한 요소는 일정 시간의 결정이다. 많약 시간이 너무 짧으면 참조의 지역성을 충분히 반영하지 못하게 되고 너무 길면 필요 이상의 프레임을 할당하게 될 것이다. 또한 운영체제는 프로세스의 워킹 셋이 적재된 상태에서만 그 프로세스를 실행시키고 페이지 부재가 발생할 경우 워킹셋에 포함된 페이지를 교체하지 않아야 한다.
페이지 부재 빈도(PFF)
페이지 부재 빈도(Page Fault Frequency)기법은 페이지 부재가 발생하는 빈도를 측정하여 스래싱 현상을 방지하는 것이다. 이를 위해서 운영체제는 페이지 부재의 빈도 상한선과 하한선을 설정하고 시스템에서 페이지 부재가 발생하는 빈도 수를 주기적으로 측정한다.
측정된 페이지 부재 빈도 수가 상한도에 도달하게 되면 스래싱 현상이 발생할 위험이 있음을 의미한다. 따라서 운영체제는 메모리에 적재된 임의의 프로세스를 스왑 아웃시켜 다중 프로그래밍의 정도를 떨어뜨림으로서 스래싱 현상을 방지한다.
측정된 페이지 부재 빈도 수가 하한선에 도달하게 되면 너무 많은 프레임이 할당되고 있음을 의미하기 때문에 새로운 프로세스를 스왑 인 시킴으로써 다중 프로그래밍의 정도를 증가 시킨다.
페이지 부재 빈도를 측정하여 페이지 부재율을 직접적으로 제어하는 스래싱 방지책은 워킹 셋을 이용한 스래싱 방지책보다 적극적인 기법이다.
교체 정책과 할당 정책은 서로 영향을 미치게 된다.
ex) 스래싱을 방지하기 위한 기법들은 전역 교체가 가능하여야 할 것이다. 따라서 가상 메모리를 지원하기 위한 교체 정책과 할당 정책은 상호 연관성이 있음을 유의하여야 한다.
기타 고려사항
페이지 크기
페이징 기법에서 페이지 크기는 시스템 성능과 직접적인 관계가 있다. 이론적으로 페이지의 최소 크기는 가장 긴 CPu 명령어 길이에 해당되고 최대 크기는 사용 가능한 실제 메모리의 주소공간에 해당될 것이다 .그러나 일반적으로 0.5KB ~ 4KB 정도로 사용되고 있으며 시스템의 특성과 주로 실행되는 프로세스의 크기에 따라 다르게 결정된다.
페이지 크기를 결정할 때 우선적으로 고려해야할 사항은 PMT 크기이다. PTM 크기는 페이지 크기가 작을수록 커진다.
ex) 4MB 가상 메모리에서 0.5KB 페이지가 8192개가 존재하지만 4KB 페이지는 오직 1024개 존재한다. 따라서 PMT 크기를 줄이기 위해서는 페이지 크기를 크게 설정하는 것이 보다 유리하다. 그러나 페이지 크기를 크게 설정하게 되면 마지막 페이지에서 발생하는 내부 단편화에 의한 낭비가 커지게 된다.
페이지 크기를 결정할 때 고려해야할 또 다른 사항은 페이지를 읽거나 쓰기 위하여 디스크를 접근하는데 소요되는 시간이다. 디스크를 접근하는데 걸리는 시간은 기본적으로 탐색시간, 회전 지연시간 그리고 전송 시간으로 구성된다. 전송 시간은 페이지 크기에 비례하기 때문에 페이지 크기가 작을수록 유리하다. 그러나 탐색시간과 회전 지연 시간은 페이지 크기와 무관하며 전송 시간에 비해 훨씬 많은 시간이 소요된다.
페이지를 읽거나 쓰기 위하여 디스크를 접근하는데 소요되는 총 시간은 페이지 크기를 크게 설정하는 것이 유리하다.
페이지 크기를 결정할 때 고려해야 할 다른 사항은 페이지 부재율이다. 페이지 부재율은 페이지 크기가 작을수록 높아진다. 따라서 페이지 부재율을 줄이기 위해서는 페이지 크기를 크게 설정하는 것이 유리하다.
페이지의 크기를 크게 혹은 작게 설정함에 따라 각자의 장단점이 있다.
페이지 크기를 작게 설정할 경우의 특성
다중 프로그래밍의 정도가 높아진다.
PMT 크기가 커진다.
내부 단편화에 의한 메모리 낭비가 줄어든다.
페이지 부재율이 증가한다.
프로그램 구조
페이징 기법에 의한 가상 기억장치 관리에서 프로그램의 구조는 페이지 부재율과 관계가 있다.
자신의 프로그램이 운영체제에 의해 어떻게 참조될 것인지를 고려하여 프로그램 구조를 결정할 경우보다 빠르게 실행시킬 수 있을 것이다.
페이지 잠금
페이징 기법에 의한 가상 메모리 관리에서 프로세스의 입출력 요구가 발생하였을 경우 데이터를 저장하기 위한 프로세스의 주소 공간이 포함된 페이지 잠금(page lock)의 필요성이 있다.
어떤 프로세스가 입력장치로부터 입력을 요구하였을 경우 프로세스는 입력이 완료될 때까지 기다리게 된다. 입력장치로부터 입력된 데이터는 이를 요청한 프로세스의 주소 공간으로 전달된다. 이때 입력 데이터를 저장해야 할 프로세스의 주소 공간이 포함된 페이지가 스왑아웃 되면 곤란하게 된다. 이러한 어려움을 해결하기 위해 두 가지 방법이 있는데 첫번째는 프로세스의 입출력 요구에 의한 데이터 이동은 반드시 커널 영역을 통하여 이루어지도록 하는 것이다.
ex) 데이터를 입력할 경우 입력된 데이터를 커널 영역에 저장한 후 다시 프로세스의 주소 공간으로 이동시킨다. 따라서 입출력 데이터를 저장하기 위한 프로세스의 주소 공간이 포함된 페이지의 스왑아웃이 가능하지만 커널 영역과 프로세스의 주소 공간 사이의 데이터 이동에 의한 오버헤드가 있다.
두번째는 페이지의 잠금 비트를 이용하여 특정 페이지에 대한 스왑아웃을 방지하는 것이다. 이를 위하여 모든 프레임마다 잠금 비트를 부여하고 잠금 비트가 설정된 페이지는 페이지 교체 대상에서 제외한다. 따라서 프로세스의 입출력 요구가 발생할 경우 입출력 데이터를 저장하기 위한 프로세스의 주소 공간에 해당된 프레임의 잠금 비트를 설정함으로써 그 페이지가 입출력 작업이 완료되기 전에 스왑 아웃 되는 것을 방지할 수 있다.
