가상 메모리 관리자의 입장에서 비어 있는 메모리가 많을수록 일은 쉬워진다. Page Fault가 발생하면 빈페이지 리스트에서 비어 있는 페이지를 찾아서 fault를 일으킨 페이지에게 할당하면 된다.
그러나, 빈 메모리 공간이 거의 없으면 일이 더 복잡해진다. 그런 경우 운영체제는 메모리 압박을 해소하기 위해 다른 페이지들을 강제적으로 페이징 아웃하여 활발히 사용 중인 페이지들을 위한 공간을 확보한다.
내보낼 페이지 선택은 운영체제의 교체 정책(Replacement Strategies) 안에 집약되어 있다.
그렇다면, 내보낼 페이지는 어떻게 결정해야 할까?
교체 정책에 대해 논하기 전에 먼저 해결하고자 하는 문제에 대해서 좀 더 상세히 설명해보자.
시스템의 전체 페이지들 중 일부분만이 메인 메모리에 유지된다는 것을 가정하면, 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있다. 이 캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것이다.
즉, 디스크로부터 페이지를 가져오는 횟수를 최소로 만드는 것이다. (캐시 히트 횟수를 최대로 하는 것도 목표라고 할 수 있다.)
캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간(average memory access time, AMAT) 을 계산할 수 있다.
- AMAT = Tm + (Pmiss * Td)
- Tm : 메모리 접근 비용
- Td : 디스크 접근 비용
- Pmiss : 캐시에서 데이터를 못찾을 확률 (0~1)
- 메모리에서 데이터를 못 찾을 경우에는 디스크로부터 데이터를 가져오는 비용을 추가로 지불해야 한다.
현대 시스템에서 디스크 접근 비용은 너무 크기 때문에 아주 작은 미스가 발생하더라도 AMAT에 큰 영향을 주게 된다.
컴퓨터가 디스크 속도 수준으로 느리게 실행되는 것을 방지하기 위해서는 당연히 미스를 최대한 줄여야 한다.
이를 위해서 최적 교체 정책에 대해서 알아보자!
교체 정책에 대해 알아보기 전에 Locality
에 대해서 다시 한 번 짚고 가자!
Locality
: Process가 Program/Data의 특정 영역을 집중적으로 참조하는 현상
원인
- Loop structure in program
- Array, structure 등의 데이터 구조
공간적 지역성 (Spatial Locality)
- 참조한 영역과 인접한 영역을 참조하는 특성
시간적 지역성 (Temporal locality)
- 한 번 참조한 영역을 곧 다시 참조하는 특성
각 프로세스에게 고정된 페이지 프레임을 주는 기법이다.
Fixed allocation을 활용한 다양한 알고리즘에 대해 알아보자
1966년 Belady에 의해 제시
Minimize page fault frequency (proved)
- Optimal solution
실현 불가능한 기법 (Unrealizable)
- Page reference string을 미리 알고 있어야 함
교체 기법의 성능 평가 도구로 사용 됨
- Example
- Number of page faults = 6
💡 Belady's Anomaly
일반적으로 캐시의 크기가 커지면 캐시 히트율이 증가하는 것을 기대할 수 있지만, FIFO를 사용하는 경우에는 더 안좋아진다. (그림을 보면, 페이지의 수를 하나 증가시켰음에도 불구하고 Page fault의 수가 오히려 1개 더 늘었다.)
이러한 현상을 일반적으로 Belady's Anomaly라고 부른다.
가장 참조 횟수가 적은 Page를 교체
- Tie-breaking rule : LRU
Page 참조 시 마다, 참조 횟수를 누적 시켜야 함
Locality 활용
- LRU 대비 적은 overhead
단점
- 최근 적재된 참조가 될 가능성이 높은 page가 교체 될 가능성이 있음
- 참조 횟수 누적 overhead가 존재
ex
Number of page faults = 7
LRU approximation scheme
- LRU보다 적은 overhead로 비슷한 성능 달성 목적
Bit vector 사용
- Reference bit vector (r), Update bit vector (m)
교체 순서
- (r, m) = (0, 0)
- (r, m) = (0, 1)
- (r, m) = (1, 0)
- (r, m) = (1, 1)
Clock Algorithm은 NRU 알고리즘을 실제로 구현한 알고리즘이다.
페이지를 교체해야 할 때 운영체제는 현재 바늘이 가리키고 있는 페이지 P의 use bit가 1인지 0인지 검사한다.
만약 1이라면 페이지 P는 최근에 사용되었으며 바람직한 교체 대상이 아니라는 것을 뜻한다.
P의 use bit는 0으로 설정되어 있는, 즉 최근에 사용된 적이 없는 페이지를 찾을 때까지 반복된다.
요약하자면 다음과 같다.
Clock Algorithm과 유사
Update bit (m)도 함께 고려 함
- 현재 가리키고 있는 page의 (r, m) 확인
- (0, 0) : 교체 page 결정
- (0, 1) : -> (0, 0), write-back(cleaning) list에 추가 후 이동
- (1, 0) : -> (0, 0) 후 이동
- (1, 1) : -> (0, 1) 후 이동
Example
MRU (Most Recently Used) algorihm
- LRU와 정반대 기법
MFU (Most Frequently Used) algorithm
- LFU와 정반대 기법
할당하는 페이지 프레임수가 고정된 것이 아니라 가변적이다.
Variable allocation은 다음과 같다.
t
Δ
: Window size, system parameterhttps://youtu.be/ByQmerWj1bg?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&t=799