운영체제 [가상메모리 관리 - 고정 메모리 할당 시 교체기법]

Locality

프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상

 

Fixed allocation

Min Alogorithm (OPT alogorithm)

- Minimize page fault frequency
- 앞으로 가장 오랫동안 참조되지 않을 page 교체
- 실현 불가능 --> page reference string을 미리 알고 있어야 함
- 교체 기법의 성능 평가 도구로 사용 됨

Random Algorithm

- 무작위로 교체할 page 선택
- Low overhead
- No policy 
- 성능 평가 도구로 사용

FIFO Algorithm

- 선입선출
- Page가 적재 된 시간을 기억하고 있어야 함
- 자주 사용되는 page가 교체 될 가능성이 높음 (locality 고려 x)
- FIFO anomally --> FIFO 알고리즘 경우, 더 많은 page를 할당 받음에도 더 많은 page fault가 발생하는 현상

LRU (Least Recently Used) Algorithm

- 가장 오랫동안 참조되지 않은 page를 교체
- Page 참조 시 마다  시간을 기록해야 함
- Locality에 기반을 둔 교체 기법
- Min algorithm에 가장 근접 한 성능을 보여줌
- 실제로 가장 많이 활용

단점
- 참조 시 마다 시간을 기록해야 함 (overhead 발생)
- Loop 실행에 필요한 크기보다 작은 수의 page frame이 할당 된 경우, page fault수가 급격히 증가함

LFU (Least Frequently Used) Algorithm

- 가장 참조 횟수가 적은 Page를 교체
- Page 참조 시 마다, 참조 횟수를 누적 시켜야 함
- Locality 활용

단점
- 최근 적재된 참조될 가능성이 높은 page가 교체 될 가능성
- 참조횟수 누적 overhead

NUR (Not Used Recently) Algorithm

- LRU approximation scheme --> LRU 보다 적은 overhead로 비슷한 성능 달성 목적
- Bit vector사용

Clock Algorithm

- Reference bit 사용 (초기화 작업x)
- Page frame들은 순차적으로 가리키는 pointer를 사용하여 교체될 page 결정
- 현재 가리키고 있는 page의 reference bit 확인 0 이면 교체, 1이면 0으로 변경 후 이동
- 먼저 적재된 page가 교체 될 가능성이 높음 (FIFO와 유사)
- Reference bit를 사용하여 교체 페이지 결정 (LRU와 유사)

Second Chance Algorithm

- Clock Algorithm과 유사
- update bit도 함께 고려 함