CPU Scheduling - Scheduling Algorithm_1

Scheduling Algorithm, 스케쥴링 알고리증

 

First-Come, First-Served Scheduling(이하 FCFS)

 

가장 단순한 형태의 알고리즘으로 First-In, First-Out(FIFO) Queue에 의해서 구현된다.

 

FCFS는 말그대로 먼저 처리를 요청한 Process를 먼저 처리하는 방식으로 Process의 PCB를 Linked List로 연결시켜

 

CPU의 상태가 대기상태로 바뀌면 현재의 PCB를 제거하고 다음 PCB에게 CPU를 제어권을 넘긴다.

 

FCFS의 경우 단순하고 구현하기 쉽지만 Average Waiting Time(평균 대기 시간)면에서 보면 비효율적이다.

 

예를 들어보자. 만일 아래와 그림과 같이 순서대로 Process P1, P2, P3가 수행을 요청해 왔다고 보자.

 

이때 각 Process의 CPU Burst-Time은 아래와 같다.

 

 

 

 

그리고 Grantt Chart와 각 process 별로 Waiting Time은 아래와 같다.

 

 

 

따라서 Average Waiting Time은 (0+24+27)/3 = 17 milliseconds 이다.

 

만일 도착 순서가 P2, P3, P1일 경우의 Grantt Chart는 아래와 같다.

 

 

 

이때 Average Waiting Time은 (0+3+6)/3 = 3 milliseconds이다.

 

위의 두개의 Average Waiting Time을 보면 알 수 있는이 FCFS의 경우 Process의 CPU Burst-Time의 변동이

 

 크면 클수록  Average Waiting Time의 변동도 커짐을 알 수 있다.

 

만일 하나의 큰 CPU-Bound Process와 다수의 적은 I/O-Bound Process가 있을때 다수의 I/O-Bound Process들은

 

CPU 사용기간이 짧기 때문에 Ready Queue에서 CPU-Bound Process의 종료를 기다리는 현상이 일어난다.

 

이는 짧은 Process들을 먼저 처리하는 것과 비교할 때 CPU 및 I/O장치에 대한 이용률이 떨어지는데 이러한 현상을

 

Convoy Effect라고 한다.

 

FCFS의 경우 프로세스가 종료, I/O Request, 또는 스스로 CPU에 대한 제어권을 놓지 않으면 다른 Process가

 

CPU의 제어권을 가져갈 수 없기 때문에 Non-Preemptive방식이다.