[운영체제]FIFO/FCFS (피포/first come first served)정의와 문제 & Convey Effect

운영체제 목차

 

오늘 수업부터 스케줄링 알고리즘을 하나하나 살펴보려고 합니다.

이 FIFO 자료구조 stack에서 많이 보았던 문구죠? 하지만 지금 얘기하는 것은 CPU 스케줄링이에요

 

FIFO(first in first out) = FCFS(first come first served)

 

제일 첫 번째 나오는 알고리즘이 FCFS 또는 FIFO라고 불리는 알고리즘입니다. 말 그대로 들어오는 순서대로 처리하는 알고리즘이예요. A프로세스가 들어오고, B프로세스가 들어오고 하면 A먼저 처리하고 그 다음 B먼저 처리하고 하는거죠. 이게 왜 모든 스케줄링의 알고리즘에 제일 첫 번째로 나올까요?

 

이 알고리즘이 제일 FAIR한 시스템이기 때문이예요. 먼저온 사람이 먼저 할당받는거니 공평하죠! 그렇기 때문에 첫 번째로 나옵니다. (스케줄링 목표에서 FAIR를 다뤘었어요!)

 

그런데 이게 fair하긴 하지만 어떤 특정한 경우에는 적합하지 않은 경우가 많이 있어요. 그렇지만 일반적으로 가장 fair하기 때문에 문제를 제기하지 않는 그런 스케줄링 알고리즘이 FCFS입니다.

 

일상 생활에서 이해하는 FIFO

우리 일상 생활에서는 대부분이 다 FCFS로 처리를 하죠. 

 

슈퍼마켓이라던지 은행이라던지 맥도날드에 간다던지 다 줄서가지고 먼저 온 사람 먼저 서비스를 받는 것이 가장 이상적이고 이 FCFS는 항상 인간의 실생활에 사용되죠

일반적으로 non-preemtive동작을 하기 때문에 starvation이 없다는 그런 장점을 갖고 아주 좋은 알고리즘입니다

하지만 이 알고리즘이 문제가 존재하니까 그 뒤에 발전된 또 다른 알고리즘이 제기됐겠죠?

문제가 존재하는데 간트차트로 FCFS를 분석한뒤 살펴보도록 할게요.

 

Gantt char로 분석하는 FCFS

 

 

Suppose that the processes arrive in the order P1, P2, P3

거의 동시에 1,2,3의 순서로 왔다. 거의 동시에 왔는데 이 순서대로 도착했다라는거예요.

그러니까 1,2,3, 순서로 처리를 하는것이 FIFO입니다.

그런데 이렇게 스케줄링을 하면 P1의 waiting time은(= ready queue에서 기다리는 시간 저번 포스트에서 다뤘었죠!) 얘는 바로 실행되었으니까 0이겠죠. P2는 저P1이 수행되는만큼 기다렸다가 수행을 할거니까 P1의 waiting time은 24예요.

P3는 이만큼 기다렸으니까 P3은 27이 됩니다. (그래프의 그림을 보시면 이해하기 편해요)

 

이 3개의 average waiting time을 구하면 17이 됩니다.

FIFO의 문제?

자, 이 waiting time을 줄여서 스케줄링 하려면 어떻게 해야 할까요?

P1을 제일 뒤로 보내면 되겠죠. P1이 CPU burst time이 커서 다른 프로세스들의 수행 시작점이 다 밀려나고 있잖아요!

P1을 제일 뒤로 보내면 어떻게 되느냐~~

 

P2의 waiting time은 0이고 P3의 waiting time은 3이고 P1의 waiting time이 6이다. 그래서 average waiting time이 3이 돼요!아까는 17이였는데 3이 되잖아요. 그러니까 FCFS가 공평하긴 한데 burst가 큰 프로세스가 먼저 들어오게 되면 average waiting time측면에서는 안좋습니다.

사용자의 만족도가 떨어질 수가 있는거죠.

쉬운 이해를 위해 일상 생활에서 예를 들자면, 여러분이 홈플러스 가면 줄 설 때 바구니를 보고 제일 적게 들어가는 것 뒤에 서잖아요. 그게 waiting time 을 줄이기 위해서 하는거고 그런 것을 해결하기 위해서 소량을 구매하는 사람들 라인을 별도로 주는겁니다.

 

공평하기도 하면서 waiting time을 줄이는 그런 방법들을 우리도 취하고 있다!

 

Convey effect

Convoy Effect is phenomenon associated with the First Come First Serve (FCFS) algorithm, in which the whole Operating System slows down due to few slow processes.

 

 

앞의 내용을 이해했으면 이거는 아는 내용이예요.

내 앞에 엄청 긴 process가 있어서 내 waiting time이 엄청나게 길어지는 그런 현상을 우리가 convoy effect라고 하는 거거든요!

간단명료!

 

요약
- 대기 큐에 도착한 순서에 따라 CPU를 할당한다.

- 일단 프로세스가 CPU를 차지하면 완료될 때까지 수행한다.

- 긴 작업이 짧은 작업을 오랫 동안 기다릴 수 있으며, 중요하지 않은 작업이 중요한 작업을 기다리게 할 가능성이 존재한다.

- 대화식 Real time 시스템에는 부적합햐다.

 

 

다음 포스트에서는 FCFS의 문제점을 보완하기 위해 나온 SJF 알고리즘에 대해 포스팅할게요.