스케줄링 알고리즘 / FCFS

FCFS ( First-Come-First-Served)

• FIFO (First-In-First-Out) 과 동치
• 말그대로, 먼저 준비된 프로세서를 먼저 처리

특징

1. 간단하고 공정하다.

• 우선순위, 실행시간 등의 다른 요소는 전혀 고려하지 않고 무조건 먼저 준비되면 먼저 실행한다.

2. 실행시간이 긴 프로세스가 먼저 실행되면 대기시간이 길어진다.

• 예를 들어 세개의 프로세스가 있고 각각 실행시간이 24, 3, 3과 같다고 가정해보자. 만약 P1이 가장 먼저 실행되면 P2는 24msec을 기다려야하고 P3는 27msec을 기다려야한다. 때문에 평균 대기시간 (AWT, Average Waiting Time)은 (0+24+27)/3 = 17msec이다. 즉, 앞선 프로세스의 시간이 길어지면 전체 시스템의 평균 대기시간이 길어진다는 단점이 있다.

• 만약 SJF(Shortest Job First)스케줄링 기법이었다면, P3, P2, P1 순으로 실행하여 평균 대기시간 (AWT)는 (0+3+6)/3 = 3msec이였을 것이다. 이러한 결과는 항상 먼저 도착한 프로세스를 먼저 실행시키는 것이 마냥 좋은 것은 아니라는 것을 의미한다.

3. Convoy Effect(호위효과) 발생

• 호위효과란 앞선 프로세스가 실행시간이 길다면 실행시간이 짧은 프로세스들이 실행되지 못해 마치 부하처럼 뒤따라서 기다리고 있다는 것을 가리키는 효과이다. 만약 사람 3명이 화장실에 들어가려고 하는데 2명은 소변을, 1명은 대변을 누기를 희망한다고 가정해보자. 만약 대변을 누고싶은 사람이 가장 먼저 들어가면 2명의 사람은 매우 오랫동안 소변을 참아야한다. 우리는 이 것이 매우 비효율적이라는 것을 알 수 있다.

4. 비선점(Non-Preemptive) 스케줄링 기법이다.

• FCFS 스케줄링은 한 프로세스가 수행 중이라면 그 프로세스가 종료되기 전까지 CPU는 반드시 그 프로세스만 실행 할 수 있는 비선점 스케줄링 기법 중 하나이다.

실습) 위의 그림을 바탕으로 표를 채우시오.

Process ID	Arrival time	Burst Time(BT)	Wating Time(WT)	Turnarround Time(TT)	Normalized TT NTT = (TT/BT)
P1	0	3	0	3	1
P2	1	7	2	9	9/7
P3	3	2	7	9	9/2
P4	5	5	7	12	12/5
P5	6	3	11	14	14/3

NTT : 체감 대기시간
이처럼, FCFS는 실행시간이 긴놈이 앞에 들어오면 평균대기시간이 길어짐을 볼 수 있다.