페이지 대치 알고리즘

페이지 부재와 프레임 개수
참조 문자열을 이용한 페이지 부재 횟수와 프레임 개수와의 관계.
참조문자열은 메모리를 참조하는 페이지를 의미함.

프레임 수가 증가하면 페이지 부재수가 감소함.
- 위의 참조 문자열에 대해 세 개 또는 그 이상의 프레임을 가진 경우, 총 3번의 페이지 부재 발생.
- 한 프레임만 이용할 수 있는 경우 각 참조마다 페이지 대치가 필요하며 결과적으로 11번의 부재 발생.
[그림 8-17] 페이지 부재와 프레임 개수 그래프.
- 프레임 수가 증가함에 따라 페이지 부재의 수가 최소한도의 수준으로 내려감.

※ 페이지 대치 알고리즘을 확인하기 위해 아래 참조 문자열을 프레임이 3개인  메모리에 사용함.

선입선출(FIFO, First-In-First-Out) 대치 알고리즘
각 페이지가 메모리 안으로 들어간 시간을 이용.
가장 오래된 페이지부터 우선 대치시킴.
페이지 부재 발생 시, 즉 제거해야 할 페이지 선택 후 보조기억장치로 이동 교체시키고 페이지 테이블의 타당/비타당 비트를 변경함.
새로운 페이지에 대한 페이지 테이블 항목 변경 후 FIFO 큐의 마지막 위치에 삽입.

선입선출 큐(FIFO Queue)에 의해 메모리의 모든 페이지가 관리됨.
큐의 헤드부분에 있는 페이지를 먼저 대치함.
큐에 있는 페이지가 메모리로 들어갈 때 큐의 끝 페이지가 삽입.
큐의 크기는 사용 가능한 메모리 프레임의 수에 해당됨.
[그림 8-19] 선입선출(FIFO) 대치 알고리즘의 실행
- 세 개의 프레임을 사용할 수 있다 가정하고 앞의 참조 문자열을 실행, 페이지 부재는 15번 발생함.

※ 알고리즘의 이해가 쉽고 프로그램의 작성이 쉬움.

문제점.
벨레디의 변이(Belady’s Anomaly) 발생.
- 할당되는 프레임의 수가 증가해도 페이지 부재율이 증가하는 현상.
- 이로 인해 최적 페이지 대치 알고리즘을 추구하는 경향 발생.
아래의 참조 문자열을 적용하여 문제점 확인.

최적(Optimal) 페이지 대치 알고리즘
모든 알고리즘 중 페이지 부재율이 가장 낮음.
‘앞으로 가장 오랜 기간 동안 사용하지 않을 페이지를 대치하라’는 사상을 표현.
고정된 프레임 수에 대해 가능한 가장 낮은 페이지 부재율이 보장됨.
[그림 8-22] 최적 페이지 대치 알고리즘.
- 앞의 참조 문자열을 적용한 경우, 총 9번의 페이지 부재가 발생함.

최근 최소사용(LRU, Least Recently Used) 알고리즘
과거의 데이터를 이용, 미래를 예측하기 위한 통계적 개념.
메모리의 지역성을 이용한 알고리즘으로 각 페이지에 마지막으로 사용된 시간을 연관시킴.
페이지 대치 시, 오랫동안 사용하지 않은 페이지를 선택.
- 시간적으로 거꾸로 찾는 최적 페이지 대치 알고리즘이라 할 수 있음.
[그림 8-23] 최근 최소사용(LRU) 알고리즘.
- 앞의 참조 문자열 적용 시, 12번의 페이지 부재를 일으킴.
- 처음 5번의 부재 처리 과정은 최적 대치 알고리즘과 같으나, 이후 페이지 4에 대한 참조가 일어날 때  메모리 속 페이지 중 가장 늦게 사용한 페이지 2를 선택하여 대치함.
- 만약 페이지 2에 부재 발생 시, {0, 3, 4} 중 가장 늦게 사용한 페이지 3으로 대치함.

계수기를 이용한 순서 결정 방법.
각 페이지 테이블 항목과 사용시간 레지스터를 연관, 프로세서에 논리 클록이나 계수기를 덧붙여 프레임의 순서 결정.
- 페이지에 대한 참조가 있을 때마다 클록은 증가함.
클록 레지스터의 내용은 페이지의 해당 페이지 테이블에 있는 사용시간 레지스터에 복사되어 각 페이지의 최소 참조에 대한 시간을 가짐.
- 가장 작은 시간 값을 가진 페이지는 대치됨.
페이지 탐색과 페이지 테이블의 변화 과정을 유지해야 하는 부담을 고려해야 함.

스택을 이용한 순서 결정 방법.
순서 결정을 위해 페이지 번호를 스택(Stack)에 넣어 관리.
페이지가 참조될 때마다 페이지 번호를 스택의 꼭대기(Top)에 둠.
- 꼭대기에 있는 페이지 번호는 가장 최근 사용한 페이지가 되며, 밑바닥(Bottom)에 있는 페이지  번호는 가장 늦게 사용한 페이지가 되어 페이지 부재 시 교체됨.
필드 비교, 업데이트, 계수기 등의 처리 과정은 생략되나, 스택의 중간에서 항목을 가져오므로 이중 링크의 조작이 필요하여 오버헤드를 증가시킬 수 있음.
- 헤드와 꼬리 포인터를 가진 이중 연결리스트를 사용하여 해결 가능.
- 탐색시간을 감소시킬 수 있음.

[그림 8-24] 최근의 페이지를 참조한 스택.
- a 이전의 스택 정보는 꼭대기에 가장 최근에 사용한 페이지 2가 있으며, 밑 바닥에는 가장 오래 전에  사용한 페이지 4를 유지하고 있음.
- b 이전의 스택에서는 꼭대기에 있는 페이지가 최근 사용한 페이지 7로 교체됨.

최근 최소사용 근접 알고리즘
시스템은 하드웨어의 지원 대신 참조 비트(Reference Bit)의 형태로 지원.
처음 모든 bit는 0으로 초기화한 후 사용자 프로세스가 수행될 때 참조된 각 페이지와 관련된 bit를 1로 변환, 어느 페이지가 사용되었는지 조사하여 확인 가능.
부분적인 순서 정보를 활용하여 최근 최소사용 알고리즘에 근사하게 대치 가능한 알고리즘 구현 가능.

부가된 참조비트 알고리즘.
각 페이지에 8bit(1byte) 정보에 일정한 간격으로 참조 비트를 기록.
8bit Shift Register를 이용하여 순서 정보를 얻음.
- 각 페이지에 대한 참조비트(1)를 최상위 bit(8bit 위, 가장 왼쪽)로 삽입 이동하고 나머지 bit들은  한 비트씩 오른쪽으로 이동시켜 가장 낮은 자리 bit는 제거함.
8bit Shift Register는 최근 8번의 기간 동안 페이지 사용의 기록 정보를 유지함.
- Shift Register의 값이 ‘00000000’인 경우 8번의 기간 동안 단 한 번도 사용되지 않음을 의미함.
- ‘11000100(19610)’은 ‘01110111(11910)’보다 최근 사용되었음을 의미함.

[그림 8-25] 부가된 참조비트 예.
- ‘00001011(11)’이 가장 사용빈도가 낮아 페이지 대치 대상임.

8bit를 부호 없는 정수로 해석할 경우 가장 낮은 bit를 가진 페이지는 최근 최소사용(LRU) 페이지(오랫동안 미사용 페이지)이며, 대치 가능함.
참조 비트의 내용이 동일한 경우 발생 가능.
- 모든 페이지 프레임이 갖는 참조 비트의 값이 유일하지 않기 때문에 발생함.
작은 정수값을 갖는 프레임이 두 개 이상 있는 경우 희생자 선정 시점에서 문제 발생.
- 희생자를 선정하지 않는 경우는 문제 없음.
- 가장 작은 정수값을 갖는 프레임 모두를 희생자로 선택하거나 FIFO의 원칙에 따라 하나를 희생자로  선택함.

시계(2차적 기회 대치) 알고리즘.
선입선출(FIFO) 대치 알고리즘을 기반으로 함.
최근 최소사용(LRU) 알고리즘과 성능은 비슷하나 과부하가 적음.
- 각 프레임의 사용여부를 나타내는 참조(사용)비트를 추가.
- 페이지가 메모리 내의 프레임에 처음 적재되었을 때 1로 설정한 후, 참조될 때마다 다시 1로 설정.
- 프레임들은 원형 버퍼(큐)로 구성되고 각각 관련 포인터를 가짐.
- 페이지 교체 시 포인터는 교체된 버퍼 다음 프레임을 가리키도록 설정.
운영체제가 페이지 교체 시기에 참조비트가 0인 프레임을 찾기 위해 원형 버퍼 검색.
- 프레임의 참조비트가 ‘1’이면 ‘0’으로 조정하고 현재 시간으로 고침.
- 수정한 페이지에 2차적 기회를 주고 다음 검사 시까지  대치시키지 않음.
- 모든 사용비트가 1인 경우 각 페이지에 2차적 기회를 주며  포인터는 전체 큐를 한 바퀴 돌 수도 있음.
- 처음 시작한 위치에서 중단하고 그 프레임을 교체대상으로  선택.
모든 bit가 1인 경우 2차적 알고리즘은 선입선출(FIFO)대치와 같아짐.
- 사용비트가 1인 프레임을 통과하는 과정을 제외하면  선입선출(FIFO) 대치 알고리즘과 비슷함.
- 원형으로 배치된 것처럼 보여 시계 알고리즘이라고 함.

[그림 8-27] 간단한 시계 알고리즘의 예.
- 메인 메모리 프레임 m개로 구성된 원형 버퍼가 버퍼 내의 페이지 1개를 새로운 페이지 420으로  교체하기 직전의 모습.

시계 알고리즘에 사용비트 추가 시 더 강력한 대치 알고리즘 작성 가능.
- 사용 중인 페이지들은 메인 메모리의 각 프레임과 연관되므로 메인 메모리의 각 프레임의 상태를  나타내는 수정(타당/비타당 비트)를 이용.
- 해당 프레임이 보조기억장치(디스크)에 저장되었는지 확인 가능함.
- 페이지를 가져온 후 수정되지 않았으며 최근에 사용되지 않은 페이지를 찾을 수 있으므로 변경되지  않은 페이지가 우선 교체 대상이 되어 시간을 줄일 수 있음.

최소사용 빈도수(LFU, Least Frequently Used) 알고리즘.
각 페이지마다 참조 횟수에 대한 계수기가 있으며, 가장 작은 수를 가진 페이지를 대치함.
- 많이 사용되는 페이지는 큰 참조 횟수 값을 가짐.
어떤 프로세스의 초기 단계에서 한 페이지가 많이 사용되나 그 후로 다시 사용되지 않을 경우 사용하기 어려움.
- 큰 계수를 가진 페이지가 더 이상 필요하지 않음에도 메모리 속에 계속 남음.
- 계수기를 어떤 일정한 시간 간격으로 하나씩 오른쪽으로 이동, 지수적으로 감소하는 평균 사용수를  형성하여 해결 가능함.

최대사용 빈도수(MFU, most Frequently Used) 알고리즘.
가장 작은 계수를 가진 페이지가 방금 들어온 것으로 아직 사용되지 않아, 앞으로 사용할 확률이 높다고 가정하여 대치 페이지 후보에서 제외시킴.
가장 많이 사용된 페이지(계수가 높은 페이지)를 대치함.

※ LFU, MFU는 구현 시 비용이 많이 들고 최적 페이지 대치에 비해 성능이 떨어져 일반적으로 사용되지 않음.

페이지 버퍼링(Page Buffering).
FIFO 같은 성능 저하를 막기 위해 교체 대상으로 선택된 페이지를 즉시 교체하지 않고 잠시 동안 메인 메모리에 유지함.
포인터 리스트 두 개를 이용, 페이지를 관리하며, 페이지 대치 알고리즘은 FIFO임.
VAX 컴퓨터의 VMS, XP, Mach에서 사용된 방식.
[그림 8-28] 페이지 버퍼링 개념.
- 수정 안 된 가용페이지 리스트. : 메모리에 적재된 후에 수정된 적이 없는 프레임 리스트로 교체 불필요.
- 변경 페이지 리스트 : 메모리에 적재된 후 수정된 프레임의 리스트로 디스크에 재저장해야 하므로 디스크 기록을 대기함.

변경되지 않은 페이지 교체 시, 교체된 페이지는 메모리에 남고 페이지 프레임은 가용 페이지 리스트의 끝에 추가됨.
변경된 페이지 교체 시, 페이지 프레임을 변경 페이지 리스트의 끝에 추가함.

페이지 교체 시.
- 페이지 테이블 내에 있는 항목만 삭제되어 가용 페이지 리스트나 변경 페이지 리스트에 놓임.
- 포인터 리스트의 각 항목은 재배치되는 프레임의 번호 저장.
- 가용 페이지 : 항상 사용 가능한 몇 개의 프레임들을 보유, 페이지를 읽어 들일 수 있는 페이지  프레임의 리스트.

페이지 읽을 때.
- 가용 리스트의 헤드가 가리키는 페이지 프레임(가용 페이지 리스트 상의 첫 페이지)이 사용되고  그 페이지는 없어짐.
- 페이지 부재 발생 시 리스트 두 개를 검색, 원하는 페이지가 아직 메모리에 있는 지 검사함.
- 메모리에 없으면 가용 페이지 리스트의 첫 번째 프레임에 원하는 페이지 적재.

프로세스가 페이지를 참조하면 오버헤드 없이 페이지가 해당 프로세스의 작업에 추가 가능하여 페이지 부재가 해결됨.
변경 페이지 리스트에 있는 프레임은 일괄 처리되어, 입출력 연산 횟수가 감소하므로 디스크 액세스 시간을 줄여줌.

알고리즘의 비교 분석
배르(BAER, 1980년) 발표.
[그림 8-29] 페이지 대치 알고리즘의 비교.
- 분석에 사용한 페이지 크기는 256word이며, 프레임 수를 6, 8, 10, 12, 14개로 변경시키면서 실행.
- 적은 수의 프레임을 사용할 경우 차이가 크게 나타남.