Page and Frame Replacement Alogorithms
page fault가 발생했을 때 빈 frame을 찾아서 할당해야 하는데 만약 빈 frame이 없다면 하나의 frame을 선택하여 page out 시켜야 한다. 이때 어느 frame을 선택할지에 대한 알고리즘을 알아볼 것이다.
가장 최적의 알고리즘 ( Optimal Algorithm )은 오랫동안 사용되지 않을 page를 선택하여 page out 시키는 것이다.
예를 들어 논리 메모리에 "7012030....."처럼 연속적으로 할당돼 있는데 물리 메모리는 3개의 frame만 할당했을 때 어떻게 동작하는지 보자.
처음 3개는 빈 frame을 채우기 위해 할당하고, "2"부터 알고리즘을 통해 page out 시킬 frame을 찾는다.
가령 네 번째 "2"가 들어왔을 때 "7"과 "0"과 "1"중에 누구를 page out 시키냐면, "7"이 제일 뒤에서 호출되기 때문에 "7"을 page out 시킨다.
또한 여섯 번째 "3"이 들어왔을 때는 "1"이 "0"과 "2"보다 뒤에 요청하기 때문에 "1"을 page out 시킨다.
이렇게 동작하면 제일 좋은 알고리즘일 것이다. 하지만 구현할 수 없다. 이유는 우리는 미래의 입력을 알지 못한다.
현실적으로 구현하기에 나온 알고리즘은 LRU ( Least Recently Used )이다.
그전에 이해를 돕기 위해 가장 naive 한 알고리즘으로 First in First out 알고리즘을 보자.
First in First out Algorithm (FIFO)
간단한 예를 보며 이해해보자. 먼저 들어온 놈을 먼저 내보내는 알고리즘이다.
논리 메모리에 "7012030....."처럼 연속적으로 할당돼 있는데 물리 메모리는 3개의 frame만 할당했을 때 어떻게 동작하는지 보자.
먼저 처음 3개는 pure demand paging이 발생한다.
그리고 네 번째 "2"가 들어왔을 때는 page fault가 발생하고, "7"이 제일 먼저 들어왔으니 내보낸다.
다음으로 다섯 번째 "0"이 들어왔다면 이미 frame에 존재하니 page hit이고, page out을 할 필요가 없다. 즉, page fault가 발생하지 않는다.
여섯 번째 "3"이 들어왔다면 두 번째로 들어왔던 "0"을 내보낸다. 바로 다음에 "0"을 호출하는데도 말이다.
이런 식으로 동작하다 보면 15번의 page fault가 발생한다. FIFO는 지역성을 전혀 고려하지 않고 짠 알고리즘이다.
또한 큰 문제가 있는데 상식적으로 생각했을 때 하나의 프로세스에게 할당된 frame의 수가 많을수록 page fault의 발생 빈도가 줄어들 것이다. 이건 당연한 얘기다. (아래 그래프로 나타낼 수 있다.)
하지만 위에서 본 것처럼 frame의 수가 늘어날수록 page fault가 줄어들어야 하는데 어쩔 때는 증가하는 이상한 현상이 발견됐다. 이 현상을 Belady's Anomaly라고 한다.
아래 그래프처럼 frame의 수가 4로 늘어났음에도 불구하고 page fault가 증가했다.
이런 이유 때문에 FIFO는 사용하지 않는다.
LRU ( Least Recently Used )
위에서 최적의 알고리즘은 미래의 입력을 예상해서 가장 늦게 요청하는 page를 먼저 page out 시키는 알고리즘이다.
하지만 우리는 미래의 입력을 알지 못하기 때문에 사용할 수 없다고 했다. 그래서 나오는 것이 LRU알고리즘이다.
간단히 말하면 가장 오래전에 참조했던 page를 page out 시키는 것이다. 즉, 미래의 입력이 아니라 과거의 입력으로 선택하는 알고리즘이다. 조금 더 보자면 계속 정보를 업데이트시키는 것이고 지역성을 고려하는 것이다.
(머신러닝에서 pocket algorithm과 유사한 개념과 cache의 LRU와 같다.)
위와 같은 예를 들어보자
처음 세 개는 똑같이 들어간다.
네 번째 "2"가 들어왔을 때 가장 오래전에 참조했던 "7"을 뺀다.
여섯 번째 "3"이 들어왔을 때 가장 오래전에 참조했던 "1"을 뺀다. 원래는 "0"을 빼는 것이지만 다섯 번째에서 "0"을 참조했기 때문에 업데이트된 것이다.
이런 식으로 동작하면 12번의 page fault가 발생한다. LRU 알고리즘은 Belady's Anomaly 현상에서도 자유하다.
어떻게 구현할 수 있을까?
1. Timer
가장 오래전에 참조했던 page를 버리는 것이니 당연히 timer를 이용하여 구현할 수 있다. 단점은 항상 업데이트를 해줘야 한다는 점과 모든 page table을 검사해야 하기 때문에 cost가 많이 든다.
2. Stack
다른 방법으로는 stack을 이용하는 것이다. stack이란 Last in First out이다. 그러니 가장 오래전에 참조된 애가 제일 먼저 나간다는 의미다.
아래 그림에서는 아래 있을수록 오래됐다는 의미다. 근데 a부분에서 스택이 쌓여있다가 7을 참조했다면 가장 최근에 참조한 7을 위쪽으로 올려줘야 한다. 일종의 우선순위를 올려주는 느낌이다. 그러니 pointer 연산을 통해 7을 가장 위로 올려준다.
SW로는 구현에 어려움이 있기 때문에 HW의 도움을 받아야만 한다. 이에 page flag에서 reference bit를 만들어서 구현한다.
무슨 말이냐면, page가 read or wirte 됐다면 reference bit를 1로 setting 한다. 그리고 운영체제가 시간이 지나면 0으로 clear 해 준다. 이런 방식은 Second-Chance Algorithm이라고 한다.
Second-Chance Algorithm
page가 순환하는 구조로 돼 있고 page out을 시킬 page를 포인터로 찾는다고 하자.
만약 page flaut가 발생했을 때 reference bit가 0인 애를 가리키고 있다면 page out 시키면 된다. 하지만 reference bit가 1로 돼 있는 page라면 reference bit를 0으로 바꾸고 다음으로 이동해서 0을 찾을 때 가지 수행한다. 즉 2번의 기회를 준다는 의미다.
하지만 이런 방법은 우선순위가 고려되지 않는다는 단점이 있고, 시간이 지날수록 0으로 세팅된 page가 점점 줄어들 것이다. 그래서 우선순위를 구별하기 위해 modify bit를 추가한다. 그러면 (0, 0), (0, 1), (1, 0), (1, 1)과 같이 우선순위가 생긴다.
예를 들면, (read, wirte)와 같이 이용하여 시스템의 특성을 고려하여 우선순위를 지정할 수도 있다.
이상이다.
댓글