프로세스와 각 프로세스의 버스트 시간(Burst Time)이 주어졌을 때, 최단 작업 우선(Shortest Job First, SJF) 비선점형 방식을 적용하여 대기 시간과 반환 시간(Turnaround Time)을 구하고, 그 평균값까지 계산해 출력하는 것이 이번 글의 목표입니다.
SJF(최단 작업 우선) 스케줄링이란?
최단 작업 우선(SJF) 스케줄링은 비선점형(Non-preemptive) 방식을 따르는 작업·프로세스 스케줄링 알고리즘입니다. 스케줄러는 대기 큐에서 완료까지 필요한 시간이 가장 짧은 프로세스를 선택해 CPU를 할당하며, 한번 CPU를 점유한 프로세스는 실행이 끝날 때까지 자원을 반납하지 않습니다.
SJF는 FIFO(선입선출) 알고리즘보다 평균 대기 시간을 줄여 처리량(Throughput)을 높일 수 있기 때문에 이론적으로 더 최적(optimal)에 가까운 알고리즘으로 평가받습니다.
완료 시간, 반환 시간, 대기 시간의 정의
- 완료 시간(Completion Time): 프로세스가 실행을 마치기까지 걸린 시간입니다.
- 반환 시간(Turnaround Time): 프로세스가 제출된 시점부터 실행이 완료된 시점까지의 전체 경과 시간입니다.
반환 시간 = 완료 시간 − 도착 시간 - 대기 시간(Waiting Time): 반환 시간에서 실제 실행 시간(버스트 시간)을 뺀 값으로, 프로세스가 준비 큐에서 기다린 시간을 의미합니다.
대기 시간 = 반환 시간 − 버스트 시간
예제
다음과 같이 P1부터 P5까지 다섯 개의 프로세스와 각각의 버스트 시간이 주어졌다고 가정해 보겠습니다.
| 프로세스 | 버스트 시간 |
|---|---|
| P1 | 4 |
| P2 | 2 |
| P3 | 8 |
| P4 | 1 |
| P5 | 9 |
모든 프로세스 중 버스트 시간이 가장 짧은 것은 P4(1)이므로 P4가 먼저 CPU를 할당받습니다. 이후에는 P2(2), P1(4), P3(8), P5(9) 순서로 실행됩니다.
간트 차트(Gantt Chart)를 기준으로 대기 시간을 계산하면 다음과 같습니다.
- P1의 대기 시간: 3
- P2의 대기 시간: 1
- P3의 대기 시간: 7
- P4의 대기 시간: 0
- P5의 대기 시간: 15
따라서 평균 대기 시간은 (3 + 1 + 7 + 0 + 15) / 5 = 5.2가 됩니다.
알고리즘
시작
Step 1-> swap(int *a, int *b) 함수
temp = *a 설정
*a = *b 설정
*b = temp 설정
Step 2-> arrangeArrival(int num, int mat[][3]) 함수
i=0; i mat[1][j+1]이면,
k=0; k<5; k++ 반복하며
swap(mat[k][j], mat[k][j+1]) 호출 (도착 시간 기준 정렬)
Step 3-> completionTime(int num, int mat[][3]) 함수
temp, val 선언
mat[3][0] = mat[1][0] + mat[2][0]
mat[5][0] = mat[3][0] - mat[1][0]
mat[4][0] = mat[5][0] - mat[2][0]
i=1; i= mat[1][j] && low >= mat[2][j]이면,
low = mat[2][j], val = j 갱신
mat[3][val] = temp + mat[2][val]
mat[5][val] = mat[3][val] - mat[1][val]
mat[4][val] = mat[5][val] - mat[2][val]
k=0; k<6; k++ 반복하며 swap(mat[k][val], mat[k][i]) 호출
Step 4-> main() 함수
num = 3 선언, temp 선언
mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4} 초기화
프로세스 ID, 도착 시간, 버스트 시간 출력
arrangeArrival(num, mat) 호출
completionTime(num, mat) 호출
프로세스 ID, 도착 시간, 버스트 시간, 대기 시간, 반환 시간 출력
종료
C++ 구현 예제
// C++ program to implement Shortest Job first with Arrival Time
#include<iostream>
using namespace std;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void arrangeArrival(int num, int mat[][3]) {
for(int i=0; i<num; i++) {
for(int j=0; j<num-i-1; j++) {
if(mat[1][j] > mat[1][j+1]) {
for(int k=0; k<5; k++) {
swap(mat[k][j], mat[k][j+1]);
}
}
}
}
}
void completionTime(int num, int mat[][3]) {
int temp, val;
mat[3][0] = mat[1][0] + mat[2][0];
mat[5][0] = mat[3][0] - mat[1][0];
mat[4][0] = mat[5][0] - mat[2][0];
for(int i=1; i<num; i++) {
temp = mat[3][i-1];
int low = mat[2][i];
for(int j=i; j<num; j++) {
if(temp >= mat[1][j] && low >= mat[2][j]) {
low = mat[2][j];
val = j;
}
}
mat[3][val] = temp + mat[2][val];
mat[5][val] = mat[3][val] - mat[1][val];
mat[4][val] = mat[5][val] - mat[2][val];
for(int k=0; k<6; k++) {
swap(mat[k][val], mat[k][i]);
}
}
}
int main() {
int num = 3, temp;
int mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4};
cout<<"Before Arrange...\n";
cout<<"Process ID\tArrival Time\tBurst Time\n";
for(int i=0; i<num; i++) {
cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\n";
}
arrangeArrival(num, mat);
completionTime(num, mat);
cout<<"Final Result...\n";
cout<<"Process ID\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n";
for(int i=0; i<num; i++) {
cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\t\t"<<mat[4][i]<<"\t\t"<<mat[5][i]<<"\n";
}
}
실행 결과
위 프로그램을 실행하면 먼저 정렬 전의 프로세스 정보(프로세스 ID, 도착 시간, 버스트 시간)가 출력되고, 이후 SJF 비선점형 스케줄링이 적용된 최종 결과로 각 프로세스의 대기 시간과 반환 시간이 함께 표시됩니다.