[OS] 페이지 교체 알고리즘 - FIFO

서론

이번 글에서는 페이지 교체 알고리즘 중 가장 단순한 알고리즘인 FIFO(First In First Out) 알고리즘의 동작 원리를 알아보고자 한다.

FIFO(First In First Out) Algorithm

페이지 교체 알고리즘에서 FIFO는 가장 먼저 메모리에 적재된 페이지를 먼저 내보내는 방식의 알고리즘이다.

 

FIFO 알고리즘이 가지는 특징은 다음과 같다.

 

• 단순하며 구현하기가 쉽다.
• 지역성(Locality)을 고려하지 않는다. 사용 패턴 분석을 하는 것이 아니라 단순히 오래된 것을 교체한다.
• 메모리를 늘렸을 때 성능이 안좋아질 수 있다.
• 들어온 시간 혹은 순서를 Queue에 저장함으로써 구현할 수 있다.

예제를 통해서 FIFO 알고리즘을 이해해보자.

 

• 페이지 프레임은 3개로 구성되어 있으며 초기 페이지 프레임은 모두 비어있다.
• 참조 페이지 번호 순서 : [2, 3, 2, 1, 5, 2, 3, 5]
• 다음과 같은 조건이 있을 때 페이지 결함(Page fault)가 일어나는 횟수는?
  • 페이지 결함(Page fault) : CPU가 접근하려는 페이지가 주기억장치에 존재하지 않는 경우를 페이지 결함이 일어났다고 말한다.

Access	Hit/Miss	Evict (교체되는 페이지 번호)	Resulting Cache State
2	Miss		2
3	Miss		2, 3
2	Hit		2, 3
1	Miss		2, 3, 1
5	Miss	2	3, 1, 5
2	Miss	3	1, 5, 2
3	Miss	1	5, 2, 3
5	Hit		5, 2, 3

먼저, 페이지 결함이 일어나는 경우는 다음과 같다.

• 비어있는 프레임에 페이지 번호가 들어가는 경우 (프레임에 이미 해당 번호가 존재한다면 결함이 일어나지 않는다)
• 프레임이 모두 차있는 경우에는 들어갈 참조 페이지 번호가 프레임 내에 존재하지 않는 경우

위 조건을 기반으로 페이지 결함 횟수를 구해보면 6회가 나온다. 이제 어떻게 6이 나왔는지 과정을 살펴보자.

 

• 첫 번째에 들어온 2는 페이지 프레임이 비어있으므로 페이지 결함이 발생한다. (1회)
• 두 번째에 들어온 3는 페이지 프레임이 비어있으므로 페이지 결함이 발생한다. (2회)
• 세 번째에 들어온 2는 프레임은 비어있지만, 프레임 내에 첫 번째에서 들어온 2가 존재하므로 결함이 발생하지 않는다.
• 네 번째에 들어온 1은 페이지 프레임이 비어있고 프레임 내에 1이 존재하지 않으므로 페이지 결함이 발생한다. (3회)
• 다섯 번째에 들어온 5는 페이지 프레임이 꽉 차있으며 프레임 내에 5가 존재하지 않으므로 페이지 결함이 발생한다. (4회)
  • FIFO 알고리즘에 의하여 가장 먼저 들어온 2가 제거되고 5가 적재된다.
• 여섯 번째에 들어온 2는 페이지 프레임이 꽉 차있으며 프레임 내에 2가 존재하지 않으므로 페이지 결함이 발생한다. (5회)
  • FIFO 알고리즘에 의하여 가장 오래된 3이 제거되고 2가 적재된다.
• 일곱 번째에 들어온 3은 페이지 프레임이 꽉 차있으며 프레임 내에 3이 존재하지 않으므로 페이지 결함이 발생한다. (6회)
  • FIFO 알고리즘에 의하여 가장 오래된 1이 제거되고 3이 적재된다.
• 마지막으로 들어온 5는 페이지 프레임이 꽉 차있지만 프레임 내에 5가 존재하므로 페이지 결함이 발생하지 않는다.

 

다음 글에서는 페이지 교체 알고리즘인 LRU(Least Recently Used) 알고리즘에 대해 알아볼 예정이다.