Process Scheduling - FCFS

FCFS (First - come,First - serverd)

 

FCFS는 말 그대로 맨처음 오는 프로세스를 맨처음에 실행시키는 알고리즘이다.

오는 순서대로 Linked List 자료구조로 FCFS Queue에 Process - PCB를 넣어서 하나하나 차례로 실행시키고 프로세스의 자발적 CPU반납(프로세스의 종료, I/O요청)이 일어나기 전까지 실행시키는 가장 단순한 구조의 알고리즘이다.

구현은 가장 쉽지만, 효율성이 많이 떨어짐.

 

 

 

위와 같이 P1,P2,P3가 차례로 도착하고 각 프로세스의 burst time이 다음과 같다면.

 

 

CPU는 위 사진과 같이 실행할 것이다.

대기시간을 따지면,

P1 = 0 , P2 = 24, P3=27이 되어 평균 대기시간은 0+24+27/3 = 17s 가 된다.

만일, P2 ,P3 ,P1 순으로 도착했으면, 평균 대기시간은 0 + 3 + 6 /3 = 3s 가 된다. 이처럼 FCFS는 효율성이 떨어지고, 만일 여러개의 짧은 I/O CPU bound Process와 하나의 긴 CPU bound Process가 들어온다면, 여러개의 I/O Process들은 Ready Queue에서 CPU bound Process의 종료를 기다린다. 짧은 Process들을 먼저 처리하는 것과 효율성의 차이가 많이 나는데 이러한 문제점을     Convoy Effect    라고 한다.

 

이때의 Turnaround time

P1 = 0 + 24 = 24

P2 = 24 + 3 = 27

P3 = 27+ 3 = 30