개요
n개의 프로세스(P1, P2, P3, ..., Pn)와 각 프로세스의 실행 시간인 버스트 타임(Burst Time)이 주어졌을 때, FCFS(First Come, First Served) CPU 스케줄링 알고리즘을 이용해 평균 대기 시간과 평균 반환 시간(Turnaround Time)을 구하는 것이 이 글의 목표입니다.
대기 시간과 반환 시간이란?
반환 시간(Turnaround Time): 프로세스가 시스템에 제출된 시점부터 실행이 완료될 때까지의 전체 시간 간격을 의미합니다.
반환 시간 = 프로세스 완료 시간 − 프로세스 제출 시간
대기 시간(Waiting Time): 반환 시간에서 버스트 타임을 뺀 값으로, 프로세스가 준비 큐에서 CPU 할당을 기다린 시간을 의미합니다.
대기 시간 = 반환 시간 − 버스트 타임
FCFS 스케줄링이란?
FCFS(First Come, First Served)는 FIFO(First In, First Out) 방식이라고도 불리며, 준비 큐에 도착한 순서대로 CPU를 프로세스에 할당하는 CPU 스케줄링 알고리즘입니다.
FCFS는 비선점형(non-preemptive) 방식을 따릅니다. 즉, 한 번 CPU가 특정 프로세스에 할당되면 해당 프로세스가 종료되거나 I/O 인터럽트 등의 이유로 중단될 때까지 CPU를 다른 프로세스에 넘겨주지 않습니다.
예제 1: 간트 차트로 이해하기
세 개의 프로세스 P1, P2, P3가 아래 표와 같은 순서로 도착하며, 도착 시간(Arrival Time)은 모두 0이라고 가정해 보겠습니다.
| 프로세스 | 도착 순서 | 실행 시간(ms) |
|---|---|---|
| P1 | 3 | 15 |
| P2 | 1 | 3 |
| P3 | 2 | 3 |
시스템 내에서 각 프로세스의 대기 시간을 보여주는 간트 차트(Gantt Chart)는 다음과 같습니다.
간트 차트에서 확인할 수 있듯이,
- 프로세스 P2의 대기 시간 = 0ms
- 프로세스 P3의 대기 시간 = 3ms
- 프로세스 P1의 대기 시간 = 6ms
따라서 평균 대기 시간 = (0 + 3 + 6) / 3 = 3ms 입니다.
도착 시간을 0으로 가정했기 때문에 반환 시간과 완료 시간은 서로 같게 됩니다.
예제 2: 입력 및 출력
입력 -: processes = P1, P2, P3
Burst time = 5, 8, 12
출력 -:
Processes Burst Waiting Turn around
1 5 0 5
2 8 5 13
3 12 13 25
Average Waiting time = 6.000000
Average turn around time = 14.333333알고리즘
시작
Step 1 -> 함수 waitingtime(int proc[], int n, int burst_time[], int wait_time[])
wait_time[0] = 0 으로 설정
i = 1 부터 i < n 까지 반복
wait_time[i] = burst_time[i-1] + wait_time[i-1]
반복 종료
Step 2 -> 함수 turnaroundtime(int proc[], int n, int burst_time[], int wait_time[], int tat[])
i = 0 부터 i < n 까지 반복
tat[i] = burst_time[i] + wait_time[i]
반복 종료
Step 3 -> 함수 avgtime(int proc[], int n, int burst_time[])
wait_time[n], tat[n] 배열과 total_wt = 0, total_tat = 0 선언 및 초기화
waitingtime(proc, n, burst_time, wait_time) 호출
turnaroundtime(proc, n, burst_time, wait_time, tat) 호출
i = 0 부터 i < n 까지 반복
total_wt = total_wt + wait_time[i]
total_tat = total_tat + tat[i]
프로세스 번호, 버스트 타임, 대기 시간, 반환 시간 출력
반복 종료
"평균 대기 시간 = total_wt / n" 출력
"평균 반환 시간 = total_tat / n" 출력
Step 4 -> main 함수에서
proc[] = { 1, 2, 3 } 선언
n = sizeof proc / sizeof proc[0] 선언 및 초기화
burst_time[] = { 5, 8, 12 } 선언 및 초기화
avgtime(proc, n, burst_time) 호출
종료C 프로그램 구현
#include <stdio.h>
// 모든 프로세스의 대기 시간을 구하는 함수
int waitingtime(int proc[], int n,
int burst_time[], int wait_time[]) {
// 첫 번째 프로세스의 대기 시간은 0
wait_time[0] = 0;
// 대기 시간 계산
for (int i = 1; i < n ; i++ )
wait_time[i] = burst_time[i-1] + wait_time[i-1] ;
return 0;
}
// 반환 시간을 계산하는 함수
int turnaroundtime( int proc[], int n,
int burst_time[], int wait_time[], int tat[]) {
// burst_time[i] + wait_time[i] 로 반환 시간 계산
int i;
for ( i = 0; i < n ; i++)
tat[i] = burst_time[i] + wait_time[i];
return 0;
}
// 평균 시간을 계산하는 함수
int avgtime( int proc[], int n, int burst_time[]) {
int wait_time[n], tat[n], total_wt = 0, total_tat = 0;
int i;
// 모든 프로세스의 대기 시간을 구하는 함수 호출
waitingtime(proc, n, burst_time, wait_time);
// 모든 프로세스의 반환 시간을 구하는 함수 호출
turnaroundtime(proc, n, burst_time, wait_time, tat);
// 세부 정보와 함께 프로세스 출력
printf("Processes Burst Waiting Turn around \n");
// 총 대기 시간과 총 반환 시간 계산
for ( i=0; i<n; i++) {
total_wt = total_wt + wait_time[i];
total_tat = total_tat + tat[i];
printf(" %d\t %d\t\t %d \t%d\n", i+1, burst_time[i], wait_time[i], tat[i]);
}
printf("Average waiting time = %f\n", (float)total_wt / (float)n);
printf("Average turn around time = %f\n", (float)total_tat / (float)n);
return 0;
}
// 메인 함수
int main() {
// 프로세스 ID
int proc[] = { 1, 2, 3};
int n = sizeof proc / sizeof proc[0];
// 모든 프로세스의 버스트 타임
int burst_time[] = {5, 8, 12};
avgtime(proc, n, burst_time);
return 0;
}실행 결과
Processes Burst Waiting Turn around 1 5 0 5 2 8 5 13 3 12 13 25 Average Waiting time = 6.000000 Average turn around time = 14.333333
FCFS 스케줄링의 장단점
장점: 구현이 매우 간단하고, 먼저 도착한 프로세스부터 처리하므로 공정성이 보장됩니다.
단점: 실행 시간이 긴 프로세스가 먼저 도착하면 뒤의 짧은 프로세스들이 오래 기다려야 하는 호위 효과(Convoy Effect)가 발생하여 평균 대기 시간이 길어질 수 있습니다.