7.2. 교체 기법 (Replacement strategies)

김민우·2022년 6월 4일

목록 보기

14/14

가상 메모리 관리자의 입장에서 비어 있는 메모리가 많을수록 일은 쉬워진다. 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)
- 한 번 참조한 영역을 곧 다시 참조하는 특성

1. Fixed allocation

각 프로세스에게 고정된 페이지 프레임을 주는 기법이다.
Fixed allocation을 활용한 다양한 알고리즘에 대해 알아보자

1.1 MIN(OPT, B0 algorithm)

1966년 Belady에 의해 제시
Minimize page fault frequency (proved)
- Optimal solution

기법
- 앞으로 가장 오랫동안 참조되지 않을 page 교체
- Tie-breaking rule : page 번호가 가장 큰/작은 페이지 교체

실현 불가능한 기법 (Unrealizable)
- Page reference string을 미리 알고 있어야 함
교체 기법의 성능 평가 도구로 사용 됨

Example

Number of page faults = 6

1.2 Random Algorithm

무작위로 교체할 page 선택
Low overhead
No policy
Random Algorithm 또한 성능 평가의 기준이 될 수 있다.
- ex. 어떠한 알고리즘 X가 Random Algorithm보다 못하다면?

1.3 FIFO Algorithm

First In First Out : 가장 오래된 page를 교체
Page가 적재 된 시간을 기억하고 있어야 함
자주 사용되는 page가 교체 될 가능성이 높음
- Locality에 대한 고려가 없음
FIFO anomaly (Belady's anomaly)
- FIFO 알고리즘의 경우, 더 많은 page frame을 할당 받음에도 불구하고 page fault의 수가 증가하는 경우가 있음

Example
Number of Page faults = 10

💡 Belady's Anomaly

일반적으로 캐시의 크기가 커지면 캐시 히트율이 증가하는 것을 기대할 수 있지만, FIFO를 사용하는 경우에는 더 안좋아진다. (그림을 보면, 페이지의 수를 하나 증가시켰음에도 불구하고 Page fault의 수가 오히려 1개 더 늘었다.)
이러한 현상을 일반적으로 Belady's Anomaly라고 부른다.

1.4 LRU Algorithm

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

LRU의 단점
- 참조 시 마다 시간을 기록해야 함 (Overhead)
But, 간소화된 정보 수집으로 해소 가능 (ex. 정확한 시간 대신 순서만 기록)
- Loop 실행ㅇ 필요한 크기보다 작은 수의 page frame이 할당 된 경우, page fault 수가 급격히 증가함
- ex. loop를 위한 |Ref.string| = 4 / 할당된 page frame이 3개
- Allocation 기법에서 해결해야 함

Example

1.5 LFU (Least Frequently Used) Algorithm

가장 참조 횟수가 적은 Page를 교체
- Tie-breaking rule : LRU
Page 참조 시 마다, 참조 횟수를 누적 시켜야 함
Locality 활용
- LRU 대비 적은 overhead
단점
- 최근 적재된 참조가 될 가능성이 높은 page가 교체 될 가능성이 있음
- 참조 횟수 누적 overhead가 존재
ex
Number of page faults = 7

1.6 NUR (Not Used Recently) Algorithm

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)

1.7 Clock Algorithm

Clock Algorithm은 NRU 알고리즘을 실제로 구현한 알고리즘이다.

IBM VM/370 OS에서 실질적으로 사용된 알고리즘
Reference bit (Use bit) 사용함
- 주기적인 초기화 없음
Page frame 들을 순차적으로 가리키는 pointer(시계바늘)를 사용하여 교체될 page 결정

페이지를 교체해야 할 때 운영체제는 현재 바늘이 가리키고 있는 페이지 P의 use bit가 1인지 0인지 검사한다.
만약 1이라면 페이지 P는 최근에 사용되었으며 바람직한 교체 대상이 아니라는 것을 뜻한다.
P의 use bit는 0으로 설정되어 있는, 즉 최근에 사용된 적이 없는 페이지를 찾을 때까지 반복된다.
요약하자면 다음과 같다.

Pointer를 돌리면서 교체 page 결정
1.1 현재 가리키고 있는 page의 reference bit(r) 확인
1.2 r = 0 인 경우, 교체 page로 결정
1.3 r = 1 인 경우, reference bit 초기화 후 (r -> 0) pointer 이동
먼저 적재된 page가 교체될 가능성이 높음 (FIFO와 유사)
Reference bit를 사용하여 교체 페이지 결정 (LRU or NUR 과 유사)

Example

1.8 Second Chance Algorithm

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

1.9 Other Algorithms

Additional-reference-bits algorithm
- LRU approximation
- 여러 개의 reference bit를 가짐
- 각 time-interval에 대한 참조 여부 기록
- history register for each page

MRU (Most Recently Used) algorihm
- LRU와 정반대 기법
MFU (Most Frequently Used) algorithm
- LFU와 정반대 기법

2. Variable Allocation

할당하는 페이지 프레임수가 고정된 것이 아니라 가변적이다.
Variable allocation은 다음과 같다.

2.1 Working Set (WS) Algorithm

1968년 Denning이 제안
Working set?
- Process가 특정 시점에 자주 참조하는 page들의 집합
- 최근 일정시간 동안(Δ)조된 page들의 집합
- 시간에 따라 변함
- W(t, Δ)
- The working set of a process at time t
- Time interval [t-Δ, t] 동안 참조된 pages들의 집합
- Δ : Window size, system parameter