페이지 교체(page replacement)
: 현재 메모리에 적재되어야 하는데 그렇지 못하기 때문에 프레임중 하나를 비우고 이곳에 요청된 페이지를 적재하는 과정을 의미한다. 페이지 폴트는 페이지 폴트 핸들러에 의해서 실행된다.
Victim fram : 비우기로 선택된 프레임
Victim page : 희생 프레임에 들어가있는 페이지
페이지 교체 순서
- 디스크에 필요한 페이지확인
- 프리 프레임을 찾음
- 없다면, 희생 프레임을 선택한다.
- 페이지를 디스크로 부터 읽어 프레임에 저장한다.
- 프로세스 재 실행
페이지 교체가 일어날때 희생 프레임을 어느 프로세스에서 얻어올지에 대해서 2개의 방법이 있다.
- 지역교체 : 각 프로세스는 자신이 사용중이 프레임 중에서 교체할 프레임을 선택
- 전역교체 : 전체 프레임 중에서 교체 대상 프레임을 교체
지역 교체의 경우에는 각 프로세스들의 프레임 수가 불변한다.
전역 교체의 경우에는 각 프로세스의 할당된 프레임 수가 변화한다.
페이지 교체 알고리즘
FIFO : 할당받은지 오래된거 순으로 교체함.
Fifo의 경우 balady의 모순 (balady’s anomaly)가 발생하는데 이는 프레임의 개수를 늘리면 페이지 폴트 수가 낮아져야하지만, 그렇지 않고 늘어나는 경우를 의미한다.
MIN algorithm( optimal algorithm)
: 최적 페이지 교체 알고리즘으로, 가장 오랫동안 사용되지 않을 페이지를 교체하는것으로 페이지폴트률을 최소로 하지만, 현실적으로 실행이 불가능하다. 왜냐면 뭐가 가장 오랫동안 사용되지 않을지 모르기 때문이다. (성능측정의 기준으로 한다
페이지 히트 수가 높아지고 페이지 폴트률이 낮아진다. 최적의 최고의 성능이다.
LRU(least recently used algorithm) = clock algorithm
LRU(최근 최소사용 알고리즘): least recently used algorithm
가장 오랫동안 사용하지 않는 페이지 프레임을 교체 Belady의 모순이 발생하지 않음
각 페이지 프레임 마다 마지막 사용 시간을 유지.
Age counter 혹은 LRU스택으로 구현하게 된다.
단점 : 페이지 마다 마지막 접근 시간을 유지 해야한다.
잦은 메모리 조작이 발생하고, TLB하드웨어 지원이 필요하다.
Age counter란.
각 프레임 마다, 참조시간을 참조될때마다 작성해서 프레임에 카운터 값을 복사해서 넣게 되고,
교체시 페이지 프레임 카운터를 보고 가장 오래전 참조된 프레임을 선택 하는것을 한다.
이를 위해서는 페이지 테이블에 접근해야 하고 메 메모리 참조시 마다 페이지 테이블을 갱신해줘야한다.
하지만 이런 방식은 계속해서 페이지 테이블에 최근 참조 시간을 작성해야하기 때문에 안좋다.
이를 해결한 방법이 스택을 이요한 방법이다.
LRU approximation algorithm : LRU 근접 알고리즘
LRU알고리즘은 계속해서 페이지 접근 시간을 기록해야하기 때문에 이는 매우 비효율 적이다. 따라서 참조 했을때 참조비트의 형태를 통해서 알수 있도록 하였다.
Reference bit(참조비트)
정확한 순서는 알수 없지만 페이지 참조 여부는 확인할수 있는 방법
하지만 위와 같은 근접 알고리즘은 참조비트를 1로 두면 비교가 안되니까
부가된 참조 비트 (additional Reference bit algorithm)
하나의 참조비트 열을 두게 된다.
일정한 시간 간격마다 비트열에 기록하여 대략적인 선후 관계를 알수 있도록 한다.
최상위 비트를 순서로 한다면,
1100 보다 0111이 더 최근에 사용된것.
즉 부가된 참조비트는 매 시간이 아닌 일정한 시간 간격마다 기록하는것
2차기회 알고리즘( second- chance algorithm)
기본적으로 fifo 지만, 각 페이지마다 참조 비트를 둬서 참조비트가 0이면 그냥 바로 교체 하지만 참조비트가 1이라면 한번더 기회를 주는것
Clock algorithm이나, finufo라고 한다.
위에 사진을 보면 1인것이 다음 희생 프레임이지만, 1이기 때문에 0으로 바꿔주고, 0인 다음 프레임을 희생프레임으로 하는것이다.
Enhanced second chance algorithm
참조비트뿐 아니라 변경비트라는것을 두는것이다.
그래서 00 > 01> 10 > 11 순으로 교체됨.
Counting algorithm
각 페이지 프레임에 참조 횟수를 counter에 작성하게 된다.
이 카운터 알고리즘은
- LFU : 사용빈도가 적은 애를 교체
- MFU : 카운터가 큰 애를 교체 ( 이미 충분히 많이썻다고 생각함)
LFU : 가장 참조횟수가 적은 페이지 교체
MFU : 가장 참조 횟수가 많은 페이지 교체
Uploaded by N2T
