6. 운영체제 - 페이지 교체 알고리즘 - FIFO(First In First Out)

1. 정의

 - 각 페이지가 주기억 장치에 적재 될때, 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

2. 특징

 - 설계 간단

 - 이해하기 쉽다

 - 벨레이디의 모순 : 페이지 프레임수를 늘려도 페이지 부재가 더 많이 일어나는 현상

3. 시험문제

2018년 4월 28일 정보처리기사 - 운영체제

52. 3개의 페이지 프레임(Frame)을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 FIFO 방법을 사용한다면 몇 번의 페이지 부재(Fault)가 발생하는가? (단, 현재 기억장치는 모두 비어 있다고 가정한다.)

요청된 페이지 번호의 순서 : 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2

① 7번 ② 8번

③ 9번 ④ 10번

2	2			x
3	2	3		x
2	2	3		ㅇ
1	2	3	1	x
5	5	3	1	x
2	5	2	1	x
4	5	2	4	x
5	5	2	4	ㅇ
3	3	2	4	x
2	3	2	4	ㅇ
5	3	5	4	x
2	3	5	2	x

 - 이렇게 해주면 총 9번의 페이지 부재가 생긴다. 

 - 이 표를 누워도 되고 아니면 이렇게 세로로 해도 된다.

 - fifo는 먼저 들어온것이 먼저 나가는 구조이다. 

2017년 5월 7일 정보처리기사 - 운영체제

42. 3 개의 페이지 프레임을 갖는 시스템에서 페이지 참조 순서가 1, 2, 1, 0, 4, 1, 3 일 경우 FIFO 알고리즘에 의한 페이지 대치의 최종 결과는?

① 1, 2, 0 ② 2, 4, 3

③ 1, 4, 2 ④ 4, 1, 3

1	1			x
2	1	2		x
1	1	2		ㅇ
0	1	2	0	x
4	4	2	0	x
1	4	1	0	x
3	4	1	3	x

 - 마지막 결과는 4,1,3이다.

2017년 3월 5일 정보처리기사 - 운영체제

55. 4개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어 있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때, FIFO 페이지 교체 알고리즘을 사용할 경우 페이지 결함의 발생 횟수는?

페이지 참조 순서 : 1, 2, 3, 1, 2, 4, 5, 1

① 6회 ② 7회 ③ 8회 ④ 9회

1	1			x
2	1	2		x
3	1	2	3	x
1	1	2	3	ㅇ
2	1	2	3	ㅇ
4	4	2	3	x
5	4	5	3	x
1	4	5	1	x

 - 페이지부재는 총 6회이다

이상으로 fifo 알고리즘 정리 끝

페이지 알고리즘 계산 문제! 숙지 필요

출처

 - 정보처리기사 문제