카테고리 없음
가상 메모리(Virtual Memory)란? - 공룡책
appendonly
2024. 2. 6. 16:53
이 글을 왜 쓰냐?
jhnyang.tistory.com
9장 내용이 없다. 공룡책만을 참조해서 작성하며 사실상 번역에 가깝다. 다음 링크의 글을 참조했다. https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf
가상 메모리의 정의와 이점?
가상 메모리(Virtual Memory)는 프로세스가 메모리에 전부 적재되지 않아도 실행이 가능하도록 해주는 기법이다. 즉, 가상 메모리는 프로그램이 물리 메모리의 크기보다 커도 실행될 수 있다는 이점이 있다. 더불어, 가상 메모리는 프로그래머가 메인 메모리의 크기 한계를 신경 쓰지 않고 매우 큰 프로그램도 만들어서 어느 컴퓨터에서든 실행될 수 있도록 해준다.(32비트 cpu라면 4GB 이하. 그 이상의 주소를 가리키지 못한다.) 가상 메모리는 프로세스들이 파일, 라이브러리 또는 메모리를 공유할 수 있도록 한다.
이 글의 목적
* 가상 메모리의 정의와 이점을 설명한다.
* 요구 페이징에 따라 페이지들이 메모리에 적재되는 방식을 설명한다.
* FIFO, 최적 및 LRU 페이지 교체 알고리즘들을 설명한다.
* 프로세스의 워킹 셋을 설명하며 이를 프로그램의 지역성에 연관 지어 설명한다.
* 리눅스, 윈도우 10과 솔라리스가 어떻게 가상 메모리를 관리하는지 설명한다.
어떤 명령어를 실행하려면 해당 명령어는 물리적 메모리에 존재해야 한다. 간단히 생각해보면 전체 논리적 주소 공간을 물리적 메모리에 적재시키면 될 것이라 생각할 수 있다. 동적 링킹을 통해 메모리 사용량을 절약하여 메모리 제한을 완화할 수 있겠지만, 이는 프로그래머의 몫으로 특별한 주의를 요구한다.
명령어가 물리 메모리에 있어야만 실행이 가능하다면 프로그램의 크기는 물리 메모리의 크기만큼만 존재할 수 있다. 그러나 모든 프로그램이 메모리에 항상 존재해야만 프로세스가 실행 가능한 것은 아니다. 그 예로,
* 에러 또는 예외 상황을 대비한 코드가 프로그램에 있더라도 사실 이 코드가 실행되는 경우는 매우 적다.
* 배열, 리스트 또는 테이블은 실제 사용되는 것보다 더 많은 메모리를 잡고 있을 수 있다. 배열 크기를 100으로 선언했더라도, 10개의 원소만 사용될 수 있듯이.
* 프로그램의 코드 중 일부는 매우 희박하게 접근될 수 있다.
또한, 전체 프로그램이 필요하다 하더라도, 그것이 항상 동시에 존재해야만 하는 것도 아니다. 프로그램의 일부만 메모리에 적재하여 사용한다면 다음의 이점이 존재한다.
* 프로그램은 물리적 메모리의 크기에 제한되지 않는다. 프로그래머는 어떤 크기의 프로그램도 가상 주소 공간을 가리킴으로써 만들 수 있다.
* 각 프로그램이 메모리를 덜 잡아먹음으로써 더 많은 프로그램들이 동시에 실행되어 CPU 활용도 및 처리율을 높이지만 response time(첫 실행 - 도착)이나 turnaround time(종료 - 도착)은 변함이 없다(사용되는 부분만 사용이 된다면).
* 프로그램 일부만 메모리에 적재하므로 디스크 I/O를 줄여 프로그램 실행 속도를 높일 수 있다.
가상 메모리는 논리적 주소 공간을 물리적 메모리와 분리시킴으로써 물리 메모리 크기보다 훨씬 큰 가상 메모리를 제공한다. 프로세스의 가상 주소 공간(Virtual Address Space)이라 함은 프로세스가 논리적(또는 가상의) 관점에서 메모리에 적재된 것을 말한다. 즉, 프로세스는 물리적 메모리가 아닌 특정 논리적 주소에서 시작되며 - 예로, 주소 0 - 물리적 메모리의 불연속적 형태로 위치한 페이지들과 달리 연속적인 형태로 메모리에 존재하는 것처럼 보인다. 논리적 페이지를 물리적 페이지 프레임에 매핑하는 것은 MMU(Memory Management Unit)의 역할이다.
가상 메모리로 논리적 메모리를 물리적 메모리로부터 분리시킴과 더불어, 가상 메모리로 두 개 이상의 프로세스들이 page sharing을 통해 파일이나 메모리를 공유할 수 있다. 이는 다음과 같은 이점이 있다.
* 표준 C 라이브러리 같은 시스템 라이브러리는 가상 주소 공간과의 매핑을 통해 여러 프로세스들이 공유할 수 있다.
* 이와 유사한 방식으로 메모리도 공유할 수 있다. 각 프로세스 관점에서는 자기의 가상 주소 공간에 존재하는 것처럼 보이지만 실제로는 메모리의 물리적 페이지(프레임)들을 공유하고 있는 것이다.
* fork() 시스템 콜을 통해 기존 프로세스를 복사하여 생성할 때 페이지를 공유함으로써 프로세스 생성 속도를 높일 수 있다.
요구 페이징이란?
앞서 언급된 것처럼 전체 프로그램을 디스크에서 읽어 메모리에 적재하는 것보다 당장 필요한 부분들만 메모리에 올리는 것이 좋다. 페이지가 필요할 때만 메모리에 올린다는 것으로 이 방식 또는 기법을 요구 페이징(Demand Paging)이라 부르며 가상 메모리에서 일반적으로 사용된다. 프로그램이 실행되는 동안 페이지가 요청될 때만 메모리로 올리는 것이다. 이로 가상 메모리의 이점 중 하나인 메모리 공간을 더 효율적으로 활용할 수 있다. 또한, 더 많은 프로세스들이 실행될 수 있어 CPU 활용도 및 처리량을 높일 수 있다.
요구 페이징을 쓸 경우, 페이지는 메모리 또는 디스크에 존재하므로 이 둘을 구별할 수 있어야 한다. 이는 유효 비트(valid-invalid bit)를 통해 구별한다. 비트가 valid인 경우 페이지는 유효하며 메모리에 존재한다. 반대로 invalid인 경우 페이지는 가상 주소 공간을 벗어나거나(invalid) 스왑 영역(디스크)에 존재하는 것이다. 페이지의 유효 여부는 페이지 테이블 엔트리에 기록되어 있다. 이때 프로세스가 유효하지 않은 페이지를 접근하는 경우를 페이지 폴트(Page Fault)라고 한다. 페이지 테이블을 참조하여 주소 변환을 하는 도중 페이지 폴트가 발생할 경우 trap을 발생시켜 운영체제를 호출한다. 요청된 페이지를 찾기 위해 운영체제는 다음과 같은 일련의 과정을 수행한다.
1. 테이블을 확인하여 프로세스가 올바른 메모리를 접근한 것인지 점검한다.
2. 올바르지 않은 메모리 접근(엉뚱한 곳을 참조)인 경우 프로세스를 종료시킨다. 올바른 접근이라면 페이지를 디스크로부터 메모리에 가져온다.
3. 비어있는 프레임을 찾는다.
4. 요구된 페이지를 프레임으로 읽어오라는 I/O 요청을 한다.
5. 디스크로부터 페이지를 읽어오면 테이블 및 페이지 테이블을 수정하여 페이지가 메모리에 위치한다는 걸 표시한다.
6. 트랩으로 인해 인터럽트 되었던 명령어를 다시 수행한다. 이떄 메모리에 없었던 페이지가 생겼으므로 정상적으로 페이지를 참조할 수 있다.
* 페이지가 요구되지 않은 이상 절대 읽어오지 않는 방식은 pure demand paging이라고 부른다. 즉, 처음부터 메모리에 존재하는 페이지가 없다.
* 여러 페이지를 돌아다니며 참조하는 경우(예로, 매 명령어마다 여러 페이지에 나뉜 데이터를 이용)에는 페이지 폴트가 많이 발생해서 성능이 저조해지는 게 아니냐고 생각할 수 있지만 참조의 지역성(locality of reference)에 따라 희귀한 경우이다.
* 페이지를 메모리로 가져오고 나서는 명령어를 재수행 해야한다. 즉, 명령어 fetch, decode를 처음부터 다시 해야한다. 예로, C = A + B;를 실행한다고 해보자.
1. 명령어 Fetch 및 Decode
2. Fetch A
3. Fetch B
4. A와 B 더하기
5. 더한 결과를 C에 저장
5번에서 페이지 폴트가 발생하면 1번부터 다시 수행해야 한다. 하지만 결국 하나의 명령어보다 적은 연산들이며 페이지 폴트의 경우에만 발생하므로 큰 문제는 아니다. 이보다 더 큰 문제는 명령어의 원자성을 어겨서 일부 데이터만 변경한 경우라고 하는데 해결 방법으로 이전 값을 레지스터에 저장해두고 페이지 폴트가 발생하면 레지스터 값(예전 값)을 메모리에 다시 반영하는 방법이 있다.
페이지 폴트로 다음의 과정들이 순차적으로 발생한다.
1. 트랩을 발생시켜 OS를 호출
2. 레지스터 및 프로세스 상태를 저장
3. 인터럽트는 페이지 폴트로 인해 발생됨을 확인
4. 유효한 페이지 참조라면 디스크 상 페이지의 위치를 확인
5. 빈 프레임으로 페이지를 읽어오기 위해 디스크에 I/O 요청 (큐에서 대기하다 읽기 요청이 처리되고 페이지가 빈 프레임으로 이동)
6. 5)를 수행하는 동안 CPU 코어들을 다른 프로세스들에 할당
7. 디스크 I/O가 완료되면 인터럽트가 발생
8. 6)에서 수행중이던 다른 프로세스들의 레지스터 및 상태를 저장
9. 인터럽트는 I/O 디바이스로 인해 발생됨을 확인
10. 페이지 테이블 및 다른 테이블들을 수정하여 요청된 페이지가 메모리에 적재됨을 표시함
11. 1~2)의 프로세스가 CPU 코어를 할당 받을 때까지 대기
12. 프로세스의 레지스터, 상태(@ CPU) 및 새로운 페이지 테이블(@ MMU)을 로드하여 명령어를 재수행
요약하면,
1. 페이지 폴트 인터럽트를 서비스 루틴에 따라 처리
2. 페이지를 읽음
3. 프로세스 재시작
윈도우나 리눅스 같은 운영체제들은 초기에 페이지들을 파일 시스템으로 읽어들이고 페이지 교체 시 스왑 영역에 저장한다고 한다. 파일 시스템 읽기보다 스왑 영역 읽기가 더 빠르다고 한다.
Copy-on-Write란?
앞서 요구 페이징에서 전체 프로그램이 아닌 첫 명령어를 포함한 페이지만 메모리에 적재함으로써 프로세스 실행 속도를 높일 수 있었다. 여기서 fork() 시스템 호출 시 페이지를 공유함으로써 프로세스 생성 속도를 높이고 페이지 수를 줄일 수 있다. Copy-on-write는 부모와 자식 프로세스가 페이지(페이지에 Copy-on-write를 표시해야 함. 읽기만 가능한 코드 영역 같은 경우는 불필요.)를 공유하면서 공유하는 페이지에 쓰기 연산을 수행할 때만 페이지를 복사하는 것이다. 위 내용을 요약하면 copy-on-write를 활용한 fork()이다.
페이지 교체 알고리즘이란?
페이지들만 메모리에 존재하는 것이 아니라 I/O 버퍼들, 운영체제 등이 공존한다. 이때 빈 프레임이 없어 페이지를 프레임에 할당하지 못하는 상황이 된다면? 프로세스를 죽이거나 한 프로세스를 swap-out 하여 스왑 영역에 보존함으로써 빈 프레임을 늘릴 수 있다. 하지만 스와핑은 메모리 상의 프로세스를 스왑 영역에 복사하는 오버헤드 때문에 현대 운영체제에서는 사용되지 않는다. 현재는 페이지 교체 알고리즘을 사용하여 빈 프레임을 얻는다. 프레임만 차지하고 쓰이지 않는 페이지를 비우는 것처럼 말이다. 위의 페이지 폴트 서비스 루틴에 페이지 교체 알고리즘을 포함하면 다음과 같다.
1. 디스크 상에서 요청된 페이지를 찾는다.
2. 빈 프레임을 찾는다.
a. 빈 프레임이 있다면, 그걸 사용
b. 빈 프레임이 없다면, 페이지 교체 알고리즘을 통해 victim frame을 선정한다.
c. victim frame을 디스크에 쓰고(쓰기 연산을 했다면); 페이지와 프레임 테이블을 갱신한다.
3. 새로 빈 프레임에 요청된 페이지를 놓고; 페이지와 프레임 테이블을 갱신한다.
4. 페이지 폴트 발생 시점부터 프로세스를 재개한다.
위 과정을 보면 페이지-인, 페이지-아웃으로 인해 페이지 이동이 두 번 발생하는 문제가 있다. 이는 modify bit(또는 dirty bit)로 개선할 수 있다. 페이지 또는 프레임이 수정됐다면 이를 modify bit로 나타낸다. 페이지 교체 시, modify bit를 확인하여 페이지 변경 여부를 확인하고 1) 변경됐다면 페이지를 스왑 영역에 쓰기해야 한다. 2) 변경이 없었다면 그냥 덮어쓰면 된다.(페이지-아웃 생략)
FIFO
가장 단순한 페이지 교체 알고리즘 first-in, first-out(FIFO)이다. 모든 페이지는 메모리에 적재된 시간과 연관되어지며 페이지 교체 시 가장 오래된 페이지를 내보낸다. 그러나 시간을 기록하는 것 대신 FIFO 큐를 이용할 수 있다. 페이지가 메모리에 들어오면 큐의 tail에 삽입한다.
FIFO 알고리즘은 단순하다는 이점이 있으나, 성능이 일관적이지 않다. 예로, 초기화 모듈을 가진 페이지가 오래전에 사용되어서 내보내질 수 있고, 또 자주 사용되는 변수를 가진 페이지더라도 오래전에 메모리에 적재됐다는 이유만으로 내보내질 수도 있다. 이런 예시들이 프로세스를 실행하는데 있어서 문제는 없다. 그러나 페이지 부재율이 증가하고 실행 속도는 저하된다.
FIFO를 사용할 때 프레임 수를 늘린다고 성능이 항상 좋아지는 것은 아니다. 예로, 프로세스에 프레임이 3개만 할당되었을 때보다 4개를 할당했을 때 페이지 부재율이 오히려 증가할 수 있다.
최적 페이지 교체
앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.
당연한 얘기지만 구현하기 어렵거나 불가능하다. 이유는 미래에 페이지를 어떤 패턴으로 접근할지 예측할 수가 있어야 하기 때문이다. 이론적으로 성능이 가장 우수한 알고리즘이다.
LRU 페이지 교체
최적 페이지 교체 알고리즘이 불가능하지만 최적 근접 알고리즘은 가능하다. FIFO와 최적 알고리즘의 차이로 FIFO가 과거에 페이지가 메모리에 오른 시점을 본다면, 최적 알고리즘은 향후 페이지의 사용 시점을 본다는 점이다. 그럼 과거에 페이지를 어떻게 참조했는지를 활용한 알고리즘으로 최적 근접 알고리즘을 만들 수 있을 것이다. 이 중 LRU(Least Recently Used) 알고리즘이 있다. 가장 오랫동안 사용하지 않은 페이지를 교체하는 방식이다.
LRU 알고리즘은 페이지 교체 알고리즘으로 많이 사용되며 성능 또한 좋다. 그렇다면 LRU 알고리즘을 어떻게 구현할 수 있을까? 페이지를 가장 마지막에 사용한 시점을 어떤 식으로 관리할지가 관건이다.
* 카운터: 각 페이지-테이블 엔트리마다 클락(logical clock or counter on the CPU)의 값을 사용할 수 있다. 페이지가 참조될 때마다 클락 레지스터 값이 페이지 테이블 엔트리에 반영된다. 그럼 가장 최근에 참조한 페이지의 클락 값(time-of-use field)이 가장 클 것이다. 반대로, 값이 가장 작은 페이지가 교체 대상이다. 페이지 참조마다 메모리에 있는 페이지 테이블 time-of-use 필드를 업데이트해야 하고 클락의 오버플로우가 발생할 수 있다.
* 스택: 페이지 번호로 구성된 스택을 이용하여 구현할 수 있다. 페이지가 스택에 존재하고 참조된다면, 스택에서 제거된 후 다시 스택의 top으로 이동한다. 중간에서 제거되어야 할 경우 비효율적이므로 head, tail 포인터를 사용하는 이중 연결 리스트로 대체할 수 있다. 변경이 일어날때마다 포인터들을 바꿔야 하는 단점이 있지만 이를 대체할 자료구조는 없는 것 같다. 이때 tail pointer는 교체 대상인 LRU page를 가리키도록 만든다.
LRU 알고리즘은 하드웨어의 지원이 꼭 필요하다. 메모리 참조마다 클락 값이나 스택을 업데이트하기 위해 인터럽트를 발생시켜야 한다면 프로세스 수행 속도가 현저히 느려질 것이다. 이를 하드웨어적으로 구현해야 한다고 한다.
LRU-근사 페이지 교체
참조 비트 시프트 방식
페이지마다 참조 비트(reference bit)가 있으며 페이지를 참조할 때마다 하드웨어에 의해 비트를 1로 설정한다. 나중에 페이지 교체 시 참조 비트를 확인하여 참조되지 않은 페이지를 제거할 수 있으나 참조 순서는 알 수 없다. LRU 페이지 교체 알고리즘에서 카운터의 값처럼 연속적인 값은 아니어도 0,1 두 가지로 구분하므로 LRU-근사로 부르는 것 같다.
추가적인 참조 비트를 사용한다면 페이지 순서를 어느정도 추론 가능하며 이 특징을 활용한 알고리즘이 참조 비트 시프트 방식(additional-reference-bit shift)이다. 각 페이지-테이블 엔트리마다 8비트를 할당한다. 타이머 인터럽트가 발생하여 OS가 제어를 얻을 때마다 이 8비트를 오른쪽으로 1비트씩 시프트를 한다. 그리고 대상(victim) 페이지를 찾을 때 이 비트 값을 참조해서 값이 제일 작은 페이지를 내보낸다. 이 값이 나타내는 건 참조 횟수가 아니다. 참조 비트를 페이지마다 하나만 쓴다면 2차 기회 페이지 교체 알고리즘을 쓴다.
2차 기회 페이지 교체 알고리즘(시계열 알고리즘)
이 알고리즘은 FIFO 교체 알고리즘과 유사하다. 다만 대상 페이지를 고를 때 참조 비트를 고려한다. 참조 비트가 0이라면 교체되며 1이라면 0으로 바꾸고 교체 대상에서 면제해준 뒤 다음 페이지를 확인한다. 이를 구현하기 위해 원형 큐를 사용할 수 있다. 포인터를 하나 만들고 대상 페이지를 가리키도록 만든다. 빈 프레임이 필요해지면 참조 비트가 0인 페이지를 찾을 때까지 포인터는 계속 이동한다. 이동하면서 참조 비트가 1인 경우 0으로 clear한다.
NRU 페이지 교체 알고리즘
참조 비트 뿐만 아니라 modify bit(dirty bit)까지 쓰게 되면 성능을 높일 수 있을 것이다. 예로, (0, 0)이면 참조된 적도 없으며 수정된 적도 없는 페이지이다. 이때 (0, 1) - 변경 비트만 1인 엔트리와 (1, 0) - 참조 비트만 1인 엔트리가 있을 수 있다. 둘 중 (1, 0)인 페이지가 (0, 1)보다 우선순위 낮아 먼저 교체 대상이 된다. 이는 변경 비트가 1인 경우 디스크에 변경 내용을 반영하기 위한 쓰기 연산(I/O)가 필요한 반면, 참조 비트가 1인 경우 그냥 페이지를 덮어쓰거나 디스크에 반영할 필요없이 지우면 되기 때문이다. 만일 모든 페이지가 (1, 1)이라면 모든 페이지의 비트를 (0,0)으로 초기화한다. 만일, 모든 페이지가 동일한 비트(ex. (1, 0))를 갖는다면 메모리 상 위치를 기준으로 제거하는 것 같다.
카운팅-기반 페이지 교체
LFU(Least Frequently Used)
참조 횟수가 가장 적은 페이지를 대상 페이지로 삼는다. 다만, 초기에만 많이 쓰이고 그 이후로는 전혀 사용되지 않는 페이지가 있을 수 있다. 특정 주기마다 비트를 1씩 시프트하여 완화할 수 있다.
MFU(Most Frequently Used)
참조 횟수가 가장 적은 페이지를 최근에 읽은 페이지일 것으로 간주하는 알고리즘이다.
둘 다 보통 사용되지 않는다. NRU에 비해 많은 비트를 요구할 뿐만 아니라 성능도 OPT와 거리가 멀다.
프로세스마다 프레임 할당을 얼마나 할까?
이것도 알고리즘이 있다. 이때 프로세스마다 최소로 할당해주어야 하는 프레임 수가 있다. 이는 컴퓨터 구조마다 다르다. 예로, 명령어가 하나의 주소만 참조한다면 명령어를 넣을 프레임 하나, 참조될 페이지를 위한 프레임 하나로 총 두 개 프레임만 필요하다. 다른 예로, 프레임 16이 프레임 0을 참조하고, 프레임 0이 프레임 23을 참조하는 indirect addressing의 경우 프레임이 최소 세 개 필요하다. 페이지 공유를 하지 않는 이상 프로세스 당 최대 프레임 수는 물리적 메모리에 제한된다. 최소와 최대 프레임 수 사이에서 각 프로세스에 얼마나 프레임을 할당할지는 알고리즘을 통해 결정한다.
할당 알고리즘
가장 단순한 방법은 m개의 프레임들을 n개의 프로세스들에 동일하게 나눠주는 equal allocation(균등) 방식이다. 나누고 남는 프레임들은 free-frame buffer pool(페이지 교체 시 새로 올릴 페이지를 free-frame buffer pool에 적재 후 기존에 프레임을 차지하던 페이지는 디스크에 반영해주어야 한다. 그 전에 free-frame buffer에 있는 페이지를 프로세스가 바로 사용할 수 있다.)로 활용 가능하다. 또, 프로세스 크기별로 프레임을 비균등하게 할당하는 비례 할당이 있다. 크기 뿐만 아니라 프로세스 우선순위에 따라 다르게 할당하는 방법도 있다.
균등 할당이든 비례 할당이든 멀티 프로그래밍 수준이 올라서 새 프로세스가 나타나면 기존의 프로세스들에 할당됐던 프레임을 빼앗길 수 있다. 반대로, 멀티 프로그래밍 수준이 낮아지면 남은 프로세스들에 프레임들을 추가해줄 수 있다.
전역 vs 지역 할당
프로세스에 할당된 프레임 수에 영향을 주는 요소로 페이지 교체가 있다. 페이지 교체 알고리즘은 두 가지 종류로 구분할 수 있다: 전역 교체 및 지역 교체. 전역 교체는 교체할 프레임을 선정할 때 모든 프레임 중에서 고른다. 즉, 다른 프로세스에 할당된 프레임을 교체할 수 있어서 해당 프레임을 사용 중인 프로세스의 프레임을 빼앗는 것과 동일하다. 예로, 우선 순위가 높은 프로세스가 낮은 우선순위 프로세스의 프레임을 교체 대상으로 선택할 수 있게 설계할 수 있다. 지역 교체는 프로세스에 할당된 프레임 중에서만 선정하는 방식이다.
전역 할당의 경우 다른 프로세스에 의해 페이지 교체를 당해버릴 수 있어 프로세스 속도가 오락가락할 수 있다. 지역 교체의 경우 사용되지 않는 프레임이 있더라도 양보할 수 없으므로 성능이 저하될 수 있다. 전역 교체가 성능이 더 좋고 일반적으로 사용된다.
전역 교체의 경우, 빈 프레임이 없을 때까지 기다렸다가 페이지 교체를 시작하는 대신 빈 프레임이 특정 임계치 이하로 떨어지면 페이지 교체를 수행할 수 있다. 이 방식의 목적은 빈 프레임 또는 메모리를 최소의 임계치 이상으로 유지하기 위함이다. 임계치 이하로 떨어지면 커널 루틴(reaper)이 실행(triggered)되어 사용자 프로세스들로부터 프레임을 회수한다. 그리고 최대 임계치에 도달하면 멈춘다.
리눅스는 free memory가 너무 적어지면 out-of-memory(OOM) killer 루틴이 프로세스를 제거함으로써 빈 메모리를 얻는다. 메모리를 많이 잡아먹는 프로세스부터 종료시킨다.
쓰레싱(Thrashing)
만일 프로세스의 워킹셋에 포함된 페이지들을 담을만큼의 프레임이 없다면 페이지-폴트가 금방 발생할 것이다. 프레임이 부족하면 자주 사용되는 페이지도 교체되며 방금 전에 페이지-아웃됐던 페이지가 다시 요청되어 페이지 교체가 일어나는 악상황이 벌어진다. 이런 현상을 쓰레싱(thrashing)이라고 부른다. 프로세스가 실질적으로 작업하는 시간보다 페이지 교체에 들어가는 시간이 더 많을 때 프로세스가 thrashing 중이라 볼 수 있다. 이는 성능에 치명적이다.
원인
전역 페이지 교체 알고리즘을 사용하는 초기 페이징 시스템을 가정하고 예를 들어보겠다. 운영체제는 CPU 사용량(utilization)을 감시하며 사용량이 너무 낮다면 멀티 프로그래밍 정도를 높이기 위해 새 프로세스를 실행한다. 어떤 프로세스에서 프레임이 더 필요하여 페이지 폴트가 계속 발생하며 다른 프로세스들의 프레임들을 빼앗기 시작한다. 이로 다른 프로세스들도 페이지 폴트가 빈번해지며 서로 프레임을 계속 뺏는다. 페이지 교체를 하려면 paging device가 필요하므로 프로세스들이 일제히 paging device의 queue에서 I/O 요청을 기다린다. 프로세스들이 큐에서 대기함으로 인하여 CPU 사용량이 감소한다.
CPU 스케줄러는 CPU 사용량이 감소했으므로 멀티프로그래밍 정도를 높인다. 새로 혹은 다시 실행된 프로세스는 다른 실행중인 프로세스들의 프레임들을 뺏기 시작하고 이전보다 페이지 폴트가 더 많이 발생하며 paging device의 대기 큐는 길어진다. 마찬가지로 CPU 사용량이 더 줄어들고 CPU 스케줄러는 멀티 프로그래밍 정도를 더 높인다. 모든 프로세스들이 대부분의 시간을 페이지 교체에 사용하며 어떤 작업도 매끄럽게 진행되지 못한다.
쓰레싱을 해결하기 위한 방안으로 지역 교체 알고리즘을 생각해볼 수 있다. 지역 교체는 다른 프로세스의 프레임을 뺏지 않는다. 그러나 이 방법도 완전한 해결책은 아니다. 프로세스들이 쓰레싱하면 대다수가 paging device의 큐에서 대기하고 있을 것이다. 비록 쓰레싱하지 않는 프로세스더라도 페이지 폴트가 발생하여 페이지 교체를 할 때 이 긴 대기 큐를 통과해야 한다.
쓰레싱을 좀 더 효율적으로 방지하려면 각 프로세스가 필요한만큼 프레임을 할당해주면 된다. 각 프로세스가 필요한 프레임 수를 측정하는 방법은? 실제 사용중인 프레임 수를 고려해볼 수 있다. 이 접근이 프로세스 실행의 locality model을 정의한다.
locality model에 따르면 프로세스가 실행되면서 locality(지역성)은 계속 변화한다. 지역성은 같이 활발하게 사용되는 페이지들이다. 예로, 함수를 호출하면 새로운 지역성이 정의된다. 해당 함수 내의 변수들, 일부 전역 변수들, 명령어들에 대한 참조가 이루어지며 함수를 종료하면 함수 안의 명령어나 변수들은 해당 시점에서는 더 사용되지 않는다. 추후 다시 호출할 수도 있지만. 아래는 시간에 따른 프로세스의 지역성의 변화를 보여준다.
(a) 시점에서 locality는 {18, 19, 20, 21, 22, 23, 24, 29, 30, 33}이며 (b)에서는 locality가 {18, 19, 20, 24, 25, 26, 27, 28, 29, 31, 32, 33}로 변한다. 일부 페이지들은 겹치기(overlap)도 한다. 따라서 지역성은 프로그램의 구조와 자료구조에 따라 정의된다고 볼 수 있다. 지역성은 캐시 설계의 기반이 되는 성질이기도 하다. 메모리에 랜덤한 접근을 하면 캐시가 무용지물이 된다.
지역성이 갑자기 나온 이유는 프로세스에 프레임을 할당할 때 특정 시점의 지역성을 수용할 수 있을만큼 프레임을 할당할 수 있기 때문이다. 새로운 지역성을 맞이하면 해당 지역성의 페이지들을 프레임에 적재할 때까지 페이지 폴트가 발생하겠지만 다 채우고 나면 그 이후로 지역성을 바꾸기 전까지는 페이지 폴트가 없을 것이다. 프로세스의 특정 시점에서의 지역성을 수용할만큼 프레임을 할당하지 못한다면 현재 자주 사용되는 페이지들을 메모리에 올려놓을 수 없으므로 쓰레싱할 것이다. 이러한 아이디어에 기반한 모델이 워킹-셋 모델이다.
워킹-셋 모델(Working-Set Model)
워킹-셋 모델은 지역성에 기반하며 워킹-셋 윈도우(△)라는 파라미터를 사용한다. 최근 △만큼의 페이지들을 보는 것이 핵심이다. △ 범위 안에 참조된 페이지들의 집합이 워킹-셋이다. 활발하게 참조되는 페이지는 워킹-셋 안에 포함될 것이다. 잘 사용되지 않아서 마지막 사용 이후 △ 시간만큼 지나면 워킹-셋에 없을 것이다. 따라서 워킹-셋이 프로그램의 지역성을 나타낸다고 볼 수 있다.
