정보처리산업기사, 정보처리기사 - FCFS, FIFO, 페이지 교체 알고리즘 집중 탐색!!

※ 공부 내용의 복습 개념으로 정리된 글입니다.

 

FCFS(First Come First Service, 선입 선출) = FIFO(First In First Out)

FCFS는 준비상태 큐(대기 큐, 준비 완료 리스트, 작업준비 큐, 스케쥴링 큐)에 도착한 순서에 따라 차례로 CPU를 할당하는 기법으로, 가장 간단한 알고리즘입니다.

 

큐(자료 구조)의 이해

https://namu.wiki/w/%ED%81%90%28%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%29

선입선출의 자료구조, 대기열이라고도 합니다.

Queue라고도 하는데, Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미합니다.

 

스택과 비슷하지만 조금 다릅니다.

위에서도 나와있듯 '표를 사기 위해 줄을 서는 사람들'을 생각하면 됩니다.

 

하나의 예시를 들어 보도록 하겠습니다.

출처 Freepik  작가 pch.vector

상점의 대기열을 상상해보세요. 
고객들이 들어와서 번호표를 뽑고, 번호 순서대로 서비스를 받는다고 가정합시다. 

첫 번째로 온 고객이 가장 먼저 서비스를 받고, 그 뒤에 온 고객들은 번호표에 표시된 순서대로 대기하게 됩니다. 
이것이 FIFO 알고리즘의 동작 방식과 비슷합니다. 
처음 도착한 데이터가 먼저 처리되고, 그 다음에 도착한 데이터가 순차적으로 처리됩니다.

 

데이터가 들어오는 위치는 가장 뒤(Rear, Back)에 있고, 데이터가 나가는 위치는 가장 앞(Front)에 있어서,

먼저 들어오는 데이터가 먼저 나가게 됩니다.

 

우선순위 큐, 원형 큐 등의 베리에이션이 존재합니다.

입력 동작은 Enqueue, 출력 동작은 Dequeue라고 합니다.

 

※ 베리에이션(variation)

원형의 형태를 변화시키는 동작이나 변화된 결과로, 흔히 베어리에이션, 베리에이션으로 부릅니다.

 

 

페이지 교체 알고리즘

페이지 교체 알고리즘은 주 기억장치인 메모리의 페이지(Page)들 중에서 페이지를 새롭게 들여올지를 결정하는 알고리즘입니다.

메모리에는 한정된 공간만이 존재하기 때문에, 페이지 교체 알고리즘이 필요합니다.

이 알고리즘은 주로 가상 메모리 시스템에서 사용되며, 페이지 부재(Page Fauit)가 발생했을 때 어떤 페이지를 디스크에서 메모리로 가져올지를 결정합니다.

 

※ 페이지 부재에 대해서는 밑에 글에 작성되어 있습니다.

페이지 교체 알고리즘의 동작 방식

페이지 교체 알고리즘은 다양한 방식으로 동작할 수 있습니다.

대표적인 페이지 교체 알고리즘에는 FIFO, LRU, LFU 등이 있습니다.

각 알고리즘은 서로 다른 기준에 따라 페이지를 교체합니다.

 

• FIFO
  • 가장 먼저 메모리에 들어온 페이지를 교체하는 알고리즘으로, 가장 간단한 형태의 페이지 교체 알고리즘입니다.
• LRU
  • 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘으로, 가장 최근에 사용된 페이지를 추적하여 교체합니다.
• LFU
  • 사용 빈도가 가장 적은 페이지를 교체하는 알고리즘으로, 사용 빈도를 추적하여 가장 적게 사용된 페이지를 교체합니다.

 

페이지 부재(Page Fault)

페이지 부재란 실행 중인 프로세스가 메모리에 접근할 때 요청한 페이지가 메모리에 없는 상태를 의미합니다.

즉, 필요한 페이지가 주 메모리에 존재하지 않아 디스크로부터 해당 페이지를 읽어와야 하는 상황을 말합니다.

페이지 부재가 발생하면 프로세스의 실행이 멈추고, 운영 체제는 해당 페이지를 디스크에서 메모리로 가져와야 합니다.

 

페이지 부재의 영향

페이지 부재는 시스템의 성능에 부정적인 영향을 미칠 수 있습니다.

페이지 부재가 발생하면 해당 페이지를 디스크에서 읽어와야 하기 때문에 디스크 I/O가 발생하게 됩니다.

디스크 I/O는 메모리 접근보다 훨씬 느리기 때문에 페이지 부재가 자주 발생하면 시스템의 성능이 저하될 수 있습니다.

 

페이지 부재의 해결 방법

페이지 부재를 해결하기 위한 여러 가지 방법이 있습니다.

 

가장 일반적인 방법은 페이지 교체 알고리즘을 사용하여

메모리에 있는 페이지 중 어떤 페이지를 디스크로 내보낼지 결정하는 것입니다.

 

다른 방법으로는

프리 페이징(Prefatching)과 스와핑(Swapping)과 같은 기법들을 사용하여 페이지 부재를 줄이기도 합니다.

 

페이지 교체 알고리즘 문제

다음 지문의 순서로 페이지 참조가 발생할때 FIFO 페이지 알고리즘을 사용하면 최종적으로 페이지에 남아 있는 페이지 번호는?

※ 3개의 페이지를 수용할 수 있는 주기억장치가 있다고 가정, 초기에는 모두 비어있다고 가정합니다.

참조 페이지 번호

1, 2, 3, 1, 2, 4, 1, 2, 5

 

1. 첫번째로 1이 들어옵니다.

처음 상태는 비어 있어 1번째 칸에 1이 들어오고 페이지 부재가 발생합니다.

(현재 상태 : 1, 페이지 부재 : 1)

 

2. 두번째로 2가 들어옵니다.

처음 상태의 1은 앞으로 가고 2가 새로 추가가 되며, 페이지 부재가 발생합니다.

(현재 상태 : 1 2 , 페이지 부재 : 2)

 

3. 세번째로 3이 들어옵니다.

1 2 의 상태에서 뒤에 3이 들어 와 1 2 3 의 형태와 페이지 부재가 일어납니다.

(현재 상태 : 1 2 3 , 페이지 부재 : 3)

 

4. 네번째로 1이 들어옵니다.

네번째로 들어온 1은 이미 존재하기 때문에 페이지 부재가 일어나지 않습니다.

(페이지 부재가 일어나지 않았기 때문에 들어오는 위치도 변하지 않습니다. / 가장 오래된것은 변화가 없기 때문입니다.)

(현재 상태 1 2 3 , 페이지 부재 : 3)

 

5. 다섯번째로 2가 들어옵니다.

다섯번째로 들어오는 2도 이미 존재하기 때문에 페이지 부재가 일어나지 않습니다.

(현재 상태 1 2 3 , 페이지 부재 : 3)

 

6. 여섯번째로 4가 들어옵니다.

여섯 번째로 4가 들어오면서 가장 오래된 1이 나가고 4가 들어가며, 페이지 부재가 발생합니다.

(현재 상태 : 4 2 3, 페이지 부재 : 4)

 

7. 일곱번째로 1이 들어옵니다.

일곱 번째로 1이 들어오면서 가장 오래된 2가 나가고 1이 들어가며, 페이지 부재가 발생합니다.

(현재 상태 : 4 1 3 , 페이지 부재 : 5)

 

8. 여덟번째로 2가 들어옵니다.

여덟번째로 2가 들어오면서 가장 오래된 3이 나가고 2가 들어가며, 페이지 부재가 발생합니다.

(현재 상태 : 4 1 2, 페이지 부재 : 6)

 

9. 아홉번째로 5가 들어옵니다.

아홉번째로 5가 들어오면서 가장 오래된 4가 나가고 5가 들어가며, 페이지 부재가 발생합니다.

(현재 상태 : 5 1 2. 페이지 부재 : 7)

 

결과

현재 상태는 5 1 2 이며 페이지 부재는 7번 일어났습니다.