가상메모리 관리:교체 기법

MoOrY·2022년 11월 29일

운영체제

목록 보기

20/20

가상메모리의 관리 기법 중 하나인 Replacement Strategies(교체기법)에 대해 서술한다.
교체기법은 지역성을 기준으로 작동한다.

Locality 지역성
프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상
공간적 지역성: 참조한 영역과 인접한 영역을 참조하는 특성
시간적 지역성: 한번 참조한 영역을 곧 다시 참조하는 특성

Fixed allocation

MIN(OPT, B0) algorithm
Random algorithm
FIFO(First in First Out) algorithm
LRU(Least Recently Used) algorithm
LFU(Least Frequently Used) algorithm
NUR(Not Used Recently) algorithm
Clock algorithm
Second chance algorithm

각 프로세스에게 정해진 수의 페이지 프레임을 제공하는
Fixed allocation에서의 Replacement 기법이다.

MIN algorithm (OPT algorithm)

page fault 발생을 최소화시키는 증명된 알고리즘이다.
최적의 방법을 찾을 수 있는 Optimal(최적의) solution이다.

앞으로 가장 오랫동안 참조되지 않을 page를 교체한다.

하지만 page reference string을 미리 알고 있어야 하므로 실현 불가능한 기법이다.
why? 프로그램의 실행 순서는 항상 바뀌고 예상할 수 없기 때문
미래를 미리 알고 실행할 수 있다고 가정한 algorithm이다.

그럼에도 배우는 이유는 교체기법의 성능 평가 도구로 사용되기 때문
최적의 수를 알 수 있다면, 새로 만든 algorithm의 성능을 평가할 수 있다.

현재 시점Current time에 w페이지를 읽으려 한다. 하지만 page frame이 꽉차서 교체해야 한다.
이때 page reference string을 참고하여 가장 마지막에 참조 할 페이지 y를 교체한다.

예를 보면 다음과 같다.
5번 페이지 참조 시점에서(Time 6) 교체가 이루어져야 하는데, 가장 마지막에 참조하는 6번을 교체한다.

Time6에선 앞으로 참조하지 않을 1번 혹은 2번 둘 중 하나를 교체해야 한다.
1번과 2번 모두 우열을 가릴 수 없는 동점이므로, 규칙을 정해 선택한다.
이를 tie breaking rule이라고 하며, 규칙은 정하기 나름이다.
이번엔 숫자가 작은 1을 선택한다고 가정한다.

최종적으론 다음과 같이 수행되며, 성능지표인 page faults 발생수는 6이다.

Random Algorithm

무작위로 교체할 page를 선택하는 기법이다.
overhead가 적고 policy정책이 없다.
왜 사용하냐 싶지만 Random Algorithm 역시 성능 평가 도구로 사용된다.

ex) 새 알고리즘을 만들었는데 Random Algorithm보다 성능이 안좋네...

FIFO Algorithm

First in First Out
적재된 지 가장 오래된 page를 교체한다.
페이지가 적재 된 시간을 기억하고 있어야 한다.

지역성에 대한 고려가 없으므로 자주 사용되는 page가 교체될 가능성이 높다.
더 많은 page frame을 할당받아도 page fault의 수가 더 증가하는 경우의 수가 발생할 수 있다.
이를 FIFO anomaly라고 한다.

위 상황에서 가장 먼저 적재된 z 페이지를 교체한다.

예제 상황으론 다음과 같다.
성능지표가 10이므로 6이였던 MIN aglorithm에 비해 성능이 좋지 않다는 점을 알 수 있다.

떨어지는 성능을 개선하기 위해 page frame을 더 준다면 어떻게 될까?

메모리를 더 줬지만, page fault의 발생수가 오히려 늘어났다.
이러한 현상을 FIFO anomaly라고 하며,
더 많은 page frame을 할당받음에도 불구하고 page fault의 수가 더 증가하는 경우의 수가 발생하는 경우이다.

왜 이런 현상이 생길까? 지역성을 고려하지 않았으므로

LRU(Least Recently Used) algorithm

가장 오랫동안 참조되지 않은 page를 교체하는 방법이다.

지역성에 기반을 둔 교체기법이며
MIN algorithm에 근접한 성능을 보여주어 실제로 가장 많이 활용되는 기법이다.

page 참조 시마다 시간을 기록해야 하므로 overhead가 존재한다.
이는 정확한 시간 대신 순서만 기록하는 등의 간소화된 정보 수집으로 해소 가능하다.

Loop 실행에 필요한 크기보다 작은 수의 page frame이 할당된 경우
page fault의 수가 급격히 증가하는 문제가 있다.
이는 Allocation 기법에서 해결해야 한다.
ex) page frame을 loop 실행에 필요한 크기만큼 늘려준다.

예제는 다음과 같다.
page faults의 수는 7으로, MIN의 6과 거의 유사한 성능을 보인다.

LFU(Least Frequently Used) algorithm

가장 참조 횟수가 적은 page를 교체하는 기법
즉 가장 적게 사용하는 page를 교체하겠다.

지역성에 기반을 둔 교체기법이며
LRU와 마찬가지로 page를 참조할때마다 참조 횟수를 누적시켜 기록해야 하지만(overhead)
LRU대비 overhead가 적다.

하지만 최근에 적재된, 앞으로 참조될 가능성이 높은 page가 교체될 가능성이 있다.
why? 최근에 적재됐을수록 지금까지 참조된 횟수는 적을 확률이 높으니까

참조 횟수는 메모리에서 내려올 경우 1으로 초기화된다.

참조 횟수가 같을 경우 tie breaking rule은 역시 정하기 나름이지만
일반적으로 가장 오래된 page를 교체한다.

LRU와 LFU의 장단점
LRU는 과거의 기록을 반영하지 못하지만 오버헤드가 작음
LFU는 과거의 기록을 반영하지만 최신의 일어난 변화에 반응이 덜하고 LRU보다 구현이 복잡함
https://velog.io/@taelee/8%EC%9E%A5-%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%99%80-%EC%A0%95%EB%B3%B4%EA%B8%B0%EC%88%A0%EC%9D%98-%EC%9B%90%EB%A6%AC

NUR(Not Used Recently) algorithm

최근에 사용되지 않은 page를 교체한다.
LRU보다 적은 overhead로 비슷한 성능을 달성하기 위한 목적이다.

순서를 기록하지 않고, Bit Vector을 사용한다.

bit vector
참조되었음을 표기하는 reference bit (r)
변경되었음을 표기하는 update bit (m)
두개로 구성되어 있다. (r, m)
r은 일정 주기마다 0으로 초기화되고, m은 메모리에서 나올때 0으로 초기화된다.

교체 순서(우선도)
1. (r,m) = (0,0)
2. (r,m) = (0,1)
3. (r,m) = (1,0)
4. (r,m) = (1,1)
처음에 0,0을 찾고, 없으면 0,1을 찾고를 반복. 검출되면 그 페이지를 교체한다.
r보다는 m이 우선도가 높다.

Clock algorithm

NUR을 실제로 사용한 알고리즘 (NUR은 이론적인 기법인 느낌)
IBM VM/370OS에서 사용하였으며, Reference bit만 사용한다.
단, 주기적인 초기화는 없다.

Page frame들을 순차적으로 가리키는 pointer(시계바늘)을 사용하여 교체될 page를 결정한다.

시계바늘이 돌며 현재 가리키는 page가 교체할 수 있으면 교체하고, 아니면 넘어간다.

Clock algorithm은 reference bit를 주기적으로 0으로 초기화하지 않는데,
그럼 모든 reference bit가 1이면 영원히 돌까?
NO 현재 가리키는 reference bit가 1일때, 0으로 초기화 하고 다음으로 넘어간다.
그러면 한바퀴 돌더라도 다음에 가리켰을땐 0이므로 교체 가능하다.