페이지 대치 알고리즘

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

프레임 ;수가 ;증가하면 ;페이지 ;부재수가 ;감소함.
; ; ; ;- ;위의 ;참조 ;문자열에 ;대해 ;세 ;개 ;또는 ;그 ;이상의 ;프레임을 ;가진 ;경우, ;총 ;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개로 ;변경시키면서 ;실행.
; ; ; ;- ;적은 ;수의 ;프레임을 ;사용할 ;경우 ;차이가 ;크게 ;나타남.