• 운영체제 10장 - 가상 메모리 (1) - 기본
• 운영체제 10장 - 가상 메모리 (2) - 요구 페이징, copy-on-write

에서 이어지는 글입니다.

가상 메모리

10.4 페이지 교체

전체 10 페이지 중 실제로는 5페이지만을 사용하는 프로세스가 있다면, 요구 페이징을 통해 사용되지 않는 나머지 5페이지를 로드하는 I/O를 피할 수 있다.

아래 내용에서 계속 전체 10 페이지 중 실제로는 5페이지만을 사용하는 프로세스 를 기준으로 설명을 진행한다.

만약 40 프레임을 사용할 수 있는 시스템이 있다고 하자.
10페이지를 모두 로드해야 하는 상황이였다면 4개의 프로세스를 사용할 수 있겠지만, 요구 페이징을 사용한다면 10개 중 5개는 사용되지 않으므로 8개의 프로세스를 사용할 수 있다.

그러면 그보다 더 많은 프로세스를 실행하게 되면 어떻게 될까? 메모리 초과 할당(over-allocating) 이 발생한다.
만약 10개의 페이지 중 5개만을 사용하는 6개의 프로세스를 실행시킨다면, 10개의 프레임은 남겨놓으면 높은 CPU 활용률과 처리율을 얻을 수 있다.

“Utilization” is the amount of time the CPU spends doing useful work.
“Throughput” is the number of results per unit time produced.
https://www.quora.com/What-is-the-CPU-utilization-and-throughput

그러나 이 때 10 페이지를 모두 사용해야 하는 상황이 일어나면 어떻게 될까?
시스템에서는 40 프레임만 사용할 수 있는데 60 프레임을 필요로 하게 된다.

사실 메모리는 프로그램 페이지를 위해서만 사용되지는 않는다. I/O를 위한 버퍼도 상당한 양의 메모리를 사용한다. 따라서 얼마만큼의 메모리를 I/O 용도로 할지도 중요한 문제이다.

어떤 시스템은 I/O 버퍼로 정해진 비율만큼의 메모리를 할당하고,
어떤 시스템은 프로세스들과 I/O 서브시스템 양쪽이 전체 메모리를 대상으로 할당 경쟁을 벌이도록 하기도 한다.

메모리 초과 할당은 다음과 같이 발생된다.
페이지 폴트가 발생하였을 때, 운영체제는 필요로 하는 페이지가 보조저장장치에 저장된 위치를 알아내지만 가용한 프레임 목록에 가용한 프레임이 없음을 발견한다.

이 시점에서 운영체제는 몇 가지 선택을 할 수 있다.

1. 프로세스를 종료할 수 있다. (하지만 좋은 선택은 아니다.)
2. 기본 스와핑을 사용하여 프로세스를 스왑아웃하여 모든 프레임을 비우고 다중 프로그래밍 정도를 줄일 수 있다. (하지만 이도 오버헤드가 크므로, 기본 스와핑은 더이상 사용되지 않는다.)
3. 페이지 스와핑과 페이지 교체를 결합한다.

10.4.1 기본적인 페이지 교체

페이지 교체는 다음과 같이 진행된다.

만약 빈 프레임이 없다면 현재 사용되고 있지 않은 프레임을 찾아서 그것을 비운다. 그 프레임의 내용을 스왑 공간에 쓰고 그 페이지가 메모리에 이제는 존재하지 않는다는 것을 나타내기 위해, 페이지 테이블을 변화시킴으로써 프레임을 비어 있게 한다. 이후 비워진 프레임을 페이지 폴트를 발생시킨 프로세스에서 사용할 수 있게 된다.

1. 보조저장장치에서 필요한 페이지의 위치를 알아낸다.
2. 빈 페이지 프레임을 찾는다.
     2.1. 비어 있는 프레임이 있다면 그것을 사용한다.
     2.2. 비어 있는 프레임이 없다면 희생될 프레임(victim)을 선정하기 위하여 페이지 교체 알고리즘을 수행한다.
     2.3. 희생될 페이지를 보조저장장치에 기록하고(필요한 경우), 관련 테이블을 수정한다.
3. 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정한다.
4. 페이지 폴트가 발생한 시점에서부터 프로세스를 계속한다.

빈 프레임이 없는 경우 디스크에 두 번 접근해야 한다. (한 번은 프레임을 비울 때, 다른 한 번은 읽어 들일 때) 따라서 페이지 폴트 처리 시간이 2배 소요되며 그에 따라 실질 접근 시간도 증가한다.

페이지 폴트 처리 시간이 2배인 이유는 비어 있는 프레임이 있었다면 읽어들이는 작업만 하면 되지만, 그렇지 않았을 경우 비우는 작업도 필요하기 때문

이러한 오버헤드는 변경 비트(modify bit 또는 dirty bit)를 사용해서 감소시킬 수 있다. 페이지가 변경되지 않았다면, 메모리로 읽혀 들어온 후 변경되지 않았다는 것이다. 따라서 해당 페이지를 보조저장장치에 기록할 필요가 없다. 이 기법은 읽기 전용 페이지들에도 적용된다. 이렇게 처리하면 I/O 시간을 반으로 줄일 수 있으므로 페이지 폴트 처리 시간을 많이 줄일 수 있다.

요구 페이징 시스템은 두 가지 중요한 문제를 해결해야 한다.

1. 프레임 할당 알고리즘 : 얼마나 프레임을 할당할지
2. 페이지 교체 알고리즘 : 어떤 기준으로 페이지를 교체할지

페이지 교체 알고리즘의 성능은 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 폴트 발생 횟수를 계산하여 평가한다. 이때 사용되는 메모리 주소 나열을 참조열(reference string)이라 부른다. 참조열은 인공적으로 생성할 수도 있고, 주어진 시스템을 추적하여 매 메모리 참조 시의 주소를 기록할 수도 있다.

먼저 페이지 크기가 주어졌을 때 (페이지 크기는 하드웨어나 시스템에 의해 결정됨) 주소 전체를 고려하기 보다 페이지 번호만을 고려하면 된다. 페이지 p에 대한 참조가 발생하면, 직후에 p에 접근하는 모든 참조는 페이지 폴트를 발생시키지 않는다. 첫 번째 참조 후에 페이지는 메모리에 존재할 것이므로 다음 참조들은 부재 오류를 발생시키지 않을 것이다.

예를들어 다음과 같은 주소열이 있다고 하자.

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103,
0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105

페이지 크기가 100B 라면, 이 열은 다음과 같은 참조열로 줄일 수 있다.

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1

이렇게 줄여지는 이유에 대해서 생각해보면
1 : 0100
4 : 0432
1 : 0101
6 : 0612
1 : 0102, 0103, 0104, 0101
6 : 0611
1 : 0102, 0103, 0104, 0101
6 : 0610
1 : 0102, 0103, 0104, 0101
6 : 0609
1 : 0102, 0105
이렇게 묶여지기 때문이다.

여기서 페이지 폴트 횟수를 알고자 하면 페이지 교체 알고리즘 외에도 이 프로세스가 현재 사용할 수 있는 페이지 프레임 수를 알 필요가 있다.

만약 위 참조열에 대해 3개 이상의 프레임을 가지면 각 페이지의 첫 번째 참조 때마다 한 번씩만 페이지 폴트가 발생되어, 총 3번의 페이지 폴트만 발생된다. 프레임이 하나만 있다면 참조때마다 부재가 발생하므로 총 11번의 페이지 폴트가 발생한다.

일반적으로 가용 페이지 프레임 수와 페이지 폴트율은 아래와 같은 상관관계를 나타낸다.

프레임 수가 증가함에 따라 페이지 폴트 수는 어떤 최솟값으로 떨어진다.

이후로 나오는 10.4.2 - 10.4.5 에서는 페이지 교체 알고리즘들에 대해서 알아본다.
3개의 프레임을 가진 메모리를 가정하고 다음과 같은 페이지 참조열을 사용한다고 가정한다.

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

10.4.2 FIFO 페이지 교체

first-in first-out 알고리즘

fifo 교체 알고리즘은 메모리에 올라온 지 가장 오래된 페이지를 내쫓는다.

3개의 프레임이 비어있는 상태로 시작한다면 처음 3개(7, 0, 1)의 참조는 페이지 폴트를 발생시키고 빈 프레임에 적재된다.
그 다음의 참조(2)는 페이지 7을 교체한다. (7이 가장 먼저 올라왔기 때문)
그 다음의 참조(0)은 이미 메모리 속에 있기 때문에 페이지 폴트를 발생하지 않는다.
그 다음의 참조(3)은 페이지 0을 교체한다. (0이 가장 먼저 올라왔기 때문) …

fifo는 이해하기도 쉽고, 프로그래밍하기도 쉽다. 그러나, 성능이 항상 좋지는 않다. 자주 사용되지 않는 페이지가 자주 사용되는 페이지를 교체하게 될 수도 있다. 잘못된 교체 결정은 페이지 폴트율을 높이고 프로세스 실행 속도를 떨어뜨린다.

Belady의 모순

1,2,3,4,1,2,5,1,2,3,4,5

이러한 참조열이 있다고 가정해보자.

프레임이 3개 일 경우에는 페이지 폴트가 9번 발생하지만, 프레임이 4개 일 경우에는 페이지 폴트가 10번 발생한다.

이렇듯 더 많은 프레임을 할당하였지만 오히려 페이지 폴트율이 증가하는 현상을 의미한다. 프레임을 할당하면 성능이 좋아질 것으로 생각하지만 항상 옳지는 않다.

10.4.3 최적 페이지 교체

optimal page replacement

앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체한다.

이 알고리즘은 할당된 프레임 수가 고정된 경우 가장 낮은 페이지 폴트율을 보장한다.

3개의 프레임이 비어있는 상태로 시작한다면 처음 3개(7, 0, 1)의 참조는 페이지 폴트를 발생시키고 빈 프레임에 적재된다.
이 부분까지는 fifo와 동일하다.

이후부터는 어떤것이 가장 오래 사용되지 않는지 확인한 후 교체한다. 그 다음의 참조(2)는 페이지 7을 교체한다. (7은 18번째 참조에서 다시 사용된다.)
그 다음의 참조(0)은 이미 메모리 속에 있기 때문에 페이지 폴트를 발생하지 않는다. 그 다음의 참조(3)은 페이지 1을 교체한다. (1은 14번째 참조에서 다시 사용된다.) …

fifo 알고리즘은 15번의 page fault가 발생하지만, opt 알고리즘은 9번의 page fault를 발생시킨다.

안타깝게도 이 알고리즘의 실제 구현은 어렵다. 왜냐하면, 프로세스가 앞으로 메모리를 어떻게 참조할 것인지 미리 알아야 하기 때문이다. 따라서 최적 페이지 교체 알고리즘은 주로 비교 연구 목적을 위해 사용된다.

10.4.4 LRU 페이지 교체

최적 알고리즘이 불가능하기 때문에, 최적 알고리즘의 근사 알고리즘을 사용한다.

LRU(least recently used) 알고리즘은 가장 오래 사용되지 않은 페이지를 교체한다.

페이지마다 마지막 사용 시간을 유지한다. 페이지 교체 시에 가장 오랫동안 사용되지 않은 페이지를 선택한다.

3개의 프레임이 비어있는 상태로 시작한다면 처음 3개(7, 0, 1)의 참조는 페이지 폴트를 발생시키고 빈 프레임에 적재된다.
이 부분까지는 fifo와 동일하다.

이후부터는 어떤것이 가장 오래 사용되지 않았는지 확인한 후 교체한다. 그 다음의 참조(2)는 페이지 7을 교체한다. (7은 세 프레임 중 가장 이전에 사용되었다.)
그 다음의 참조(0)은 이미 메모리 속에 있기 때문에 페이지 폴트를 발생하지 않는다. (마지막 사용 시간은 갱신한다.)
그 다음의 참조(3)은 페이지 1을 교체한다. (1은 세 프레임 중 가장 이전에 사용되었다.)

계수기나 스택(doubly linked list로 구현)을 통해 갱신할 수 있다.

doubly linked list를 사용하여 LRU 교체 알고리즘을 구현하였다면 재사용되었을 때 위와 같이 스택을 업데이트 하게 된다.

LRU 를 사용하기 위해서는 표준적인 TLB 레지스터 이상의 하드웨어 지원이 있어야 한다. (소프트웨어로 하기 위해서는 인터럽트를 사용해야하고, 그만큼 속도가 저하된다.)

10.4.5 LRU 근사 페이지 교체

LRU가 지원되지 않는 하드웨어를 위한 방식, 참조 비트를 사용하여 페이지 사용 정보를 관리함.

10.4.5.1 부가적 참조 비트 알고리즘

각 페이지에 대해 8비트의 참조 비트를 할당한다. 일정한 시간 간격마다 타이머 인터럽트를 걸어서 운영체제가 참조 비트를 8비트 정보의 최상위 비트로 이동시키고 나머지 비트들은 하나씩 오른쪽으로 이동시킨다. 이 8비트 시프트 레지스터는 가장 최근 8구간 동안의 그 페이지의 사용 기록을 담고 있다.

만약 시프트 레지스터 값이 00000000 이라면 페이지를 8번의 구간동안 한 번도 사용하지 않았다는 뜻이고, 구간마다 최소한 한 번 이상 사용된 페이지는 11111111의 시프트 레지스터 값을 가진다. 레지스터 값이 11000100인 페이지는 01110111인 페이지보다 더 최근에 사용되었다. (맨 왼쪽값이 1이기 때문에)

이 8비트 값을 이용하여 가장 작은 수를 갖는 페이지가 LRU 페이지가 되고 이를 교체할 수 있다.

이 값은 유니크한 값은 아니다.

10.4.5.2 2차 기회 알고리즘

FIFO 교체 알고리즘을 베이스로 한다. 페이지가 선택될 때마다 참조 비트를 확인한다. 참조 비트가 0이면 페이지를 교체하고 1이면 다시 한번 기회를 주고 다음 페이지로 넘어간다. 한 번 기회를 받게 되면 참조 비트는 해제된다.

2차 기회 알고리즘은 순환 큐로 구현할 수 있다.

10.4.5.3 개선된 2차 기회 알고리즘

참조 비트와 변경 비트 두 가지를 함께 사용한다.

1. 0,0 최근에 사용되지도 변경되지도 않은 경우 - 교체하기 가장 좋음.
2. 0,1 최근에 사용되지는 않았지만 변경은 된 이유 - 이 페이지는 뺏어 오려면 디스크에 내용을 기록해야 하므로 교체에 적당하지 않음.
3. 1,0 최근에 사용되었으나 변경은 되지 않은 경우 - 이 페이지는 곧 다시 사용될 가능성이 높음.
4. 1,1 최근에 사용도되었고 변경도 된 경우, 아마 곧 다시 사용될 것이며 뺏으려면 역시 디스크에 그 내용을 먼저 기록해야 함.

2차 기회 알고리즘과의 차이는 I/O 횟수를 줄이기 위해 변경된 페이지에 대해 우선순위를 준다는 것이다.

10.4.6 계수 기반 페이지 교체 (counting based page replace)

• LFU (least frequently used) 알고리즘 : 참조 횟수가 가장 작은 페이지를 교체
• MFU (most frequently used) 알고리즘 : 참조 횟수가 작을수록 최근에 참조된 것이고 앞으로 사용될 것 (??)

이 방식은 잘 사용되지 않는다. 알고리즘을 구현하는데 비용이 많이 들고 최적 페이지 교체 정책을 제대로 근사하지 못하기 때문이다.

제대로 근사하지 못한다. : 예측 정확도가 낮다.

10.4.7 페이지 버퍼링 알고리즘

방법 1.
여러개의 가용 프레임 풀을 가지고 있다가, 페이지 폴트가 발생하면 교체될 페이지를 찾기 전 가용 프레임에 새로운 페이지를 먼저 읽어 들임. 프로세스가 가능한 빨리 시작할 수 있도록 해줌. 이후 교체될 페이지가 다 쓰이고 나면 그 프레임을 가용 프레임 풀에 추가함

방법 2.
변경된 페이지 리스트를 유지함. 페이징 장치에 아무일이 없을때마다 변경된 페이지들을 차례로 보조저장장치에 슨 후 페이지의 변경 비트를 0으로 reset 한다. 그러면 이후에 페이지가 교체될 때 쓰기 작업이 불필요해진다.

방법 3.
가용 프레임 풀을 유지하면서 프레임이 원래 어디에 있던 것인지 기억. 수정(훼손)되지 않았을 경우에는 다시 그대로 가져다 씀.

10.4.8 특수한 어플리케이션에서의 페이지 교체

데이터베이스와 같이 자주 연속적인 댜랑의 읽기 작업 후에 계산과 쓰기 작업을 하는 특수한 트로그램을 위해 파티션을 파일 시스템 구조가 아닌 단순한 논리적인 블록들의 순차적인 배열(raw disk)로써 사용할 수 있게 하기도 한다.

raw disk 에 대한 i/o의 경우 RAW 파티션에 자신만의 특수한 파일 시스템을 구축해서 사용하기 때문에 파일 시스템 서비스를 거치지 않는다.