프로세스 목록과 각 프로세스의 버스트 시간(Burst Time)이 주어졌을 때, 선점형 최단 작업 우선(SJF, Shortest Job First) 스케줄링 방식을 사용하여 각 프로세스의 대기 시간과 반환 시간, 그리고 두 값의 평균을 구해 출력하는 것이 이 글의 목표입니다.
SJF(최단 작업 우선) 스케줄링이란?
최단 작업 우선(SJF) 스케줄링은 대기 큐에서 실행 시간이 가장 짧은 프로세스를 선택해 CPU를 할당하는 작업 스케줄링 알고리즘입니다. SJF는 평균 대기 시간을 최소화하여 시스템 처리량(throughput)을 높일 수 있기 때문에 FIFO(선입선출) 알고리즘보다 더 효율적이고 바람직한 방식으로 평가됩니다.
SJF 알고리즘은 선점형(preemptive)과 비선점형(non-preemptive) 두 가지 방식으로 구현할 수 있습니다. 선점형 방식은 특히 최단 잔여 시간 우선(SRTF, Shortest Remaining Time First) 스케줄링이라고도 불립니다.
선점형 방식에서는 어떤 프로세스가 이미 실행되고 있는 도중에 새로운 프로세스가 도착할 수 있습니다. 이때 새로 도착한 프로세스의 버스트 시간이 현재 실행 중인 프로세스의 남은 버스트 시간보다 짧다면, 스케줄러는 실행 중인 프로세스를 중단(선점)하고 더 짧은 작업을 가진 프로세스에게 CPU를 넘겨줍니다.
완료 시간, 반환 시간, 대기 시간의 정의
- 완료 시간(Completion Time): 프로세스가 실행을 모두 마치는 데 걸린 시간입니다.
- 반환 시간(Turnaround Time): 프로세스가 시스템에 제출된 시점부터 실행이 완료된 시점까지의 전체 시간 간격입니다.
반환 시간 = 완료 시간 − 제출 시간 - 대기 시간(Waiting Time): 반환 시간에서 실제 CPU를 사용한 버스트 시간을 뺀 값으로, 순수하게 대기열에서 기다린 시간을 의미합니다.
대기 시간 = 반환 시간 − 버스트 시간
예제 문제
아래와 같이 버스트 시간과 도착 시간을 가진 5개의 프로세스 P1, P2, P3, P4, P5가 주어졌다고 가정해 보겠습니다.
| 프로세스 | 버스트 시간 | 도착 시간 |
|---|---|---|
| P1 | 4 | 0 |
| P2 | 2 | 1 |
| P3 | 8 | 2 |
| P4 | 1 | 3 |
| P5 | 9 | 4 |
P1의 도착 시간이 0이므로 P1이 가장 먼저 실행되기 시작합니다. 시각 1에 P2가 도착하면, P2의 버스트 시간(2)이 P1의 남은 버스트 시간(3)보다 짧기 때문에 스케줄러는 P1을 선점하고 P2에게 CPU를 할당합니다. 이후에도 같은 원리로 매 시점마다 잔여 버스트 시간이 가장 짧은 프로세스가 실행됩니다.
간트 차트(Gantt Chart)를 기준으로 평균 대기 시간을 계산하면 다음과 같습니다. P1은 4, P2는 1, P3는 7, P4는 3, P5는 15만큼 대기하게 되므로 평균 대기 시간은 아래와 같습니다.
알고리즘
시작
Step 1-> 구조체 Process 선언
pid(프로세스 ID), bt(버스트 시간), art(도착 시간) 변수 선언
Step 2-> findTurnAroundTime(Process proc[], int n, int wt[], int tat[]) 함수
i = 0부터 i < n까지 반복
tat[i] = proc[i].bt + wt[i]
Step 3-> findWaitingTime(Process proc[], int n, int wt[]) 함수
rt[n] 배열 선언
i = 0부터 i < n까지 반복
rt[i] = proc[i].bt (잔여 시간 초기화)
complete = 0, t = 0, minm = INT_MAX로 설정
shortest = 0, finish_time 선언
bool check = false로 설정
While (complete != n) 반복
j = 0부터 j < n까지 반복
만약 (proc[j].art <= t) && (rt[j] < minm) && (rt[j] > 0)라면
minm = rt[j], shortest = j, check = true
만약 check == false라면
t를 1 증가시키고 계속 진행
rt[shortest]를 1 감소 (잔여 시간 감소)
minm = rt[shortest]
만약 minm == 0이라면 minm = INT_MAX
만약 rt[shortest] == 0이라면 (프로세스 실행 완료)
complete 1 증가, check = false
finish_time = t + 1
wt[shortest] = finish_time - proc[shortest].bt - proc[shortest].art
만약 wt[shortest] < 0이면 wt[shortest] = 0
t를 1 증가
Step 4-> findavgTime(Process proc[], int n) 함수
wt[n], tat[n], total_wt = 0, total_tat = 0 선언 및 초기화
findWaitingTime(proc, n, wt) 호출
findTurnAroundTime(proc, n, wt, tat) 호출
i = 0부터 i < n까지 반복
total_wt += wt[i], total_tat += tat[i]
proc[i].pid, proc[i].bt, wt[i], tat[i] 출력
평균 대기 시간(total_wt / n) 출력
평균 반환 시간(total_tat / n) 출력
Step 5-> main() 함수
Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } } 선언
n = sizeof(proc) / sizeof(proc[0])
findavgTime(proc, n) 호출
종료C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
// 각 프로세스를 나타내는 구조체
struct Process {
int pid; // 프로세스 ID
int bt; // 버스트 시간
int art; // 도착 시간
};
// 반환 시간 계산 함수
void findTurnAroundTime(Process proc[], int n, int wt[], int tat[]) {
for (int i = 0; i < n; i++)
tat[i] = proc[i].bt + wt[i];
}
// 모든 프로세스의 대기 시간 계산 함수
void findWaitingTime(Process proc[], int n, int wt[]) {
int rt[n];
for (int i = 0; i < n; i++)
rt[i] = proc[i].bt;
int complete = 0, t = 0, minm = INT_MAX;
int shortest = 0, finish_time;
bool check = false;
while (complete != n) {
for (int j = 0; j < n; j++) {
if ((proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0) {
minm = rt[j];
shortest = j;
check = true;
}
}
if (check == false) {
t++;
continue;
}
// 잔여 시간 감소
rt[shortest]--;
minm = rt[shortest];
if (minm == 0)
minm = INT_MAX;
// 프로세스가 완전히
// 실행된 경우
if (rt[shortest] == 0) {
complete++;
check = false;
finish_time = t + 1;
// 대기 시간 계산
wt[shortest] = finish_time -
proc[shortest].bt -
proc[shortest].art;
if (wt[shortest] < 0)
wt[shortest] = 0;
}
// 시간 증가
t++;
}
}
// 평균 시간을 계산하는 함수
void findavgTime(Process proc[], int n) {
int wt[n], tat[n], total_wt = 0,
total_tat = 0;
// 모든 프로세스의 대기 시간을
// 구하는 함수 호출
findWaitingTime(proc, n, wt);
// 모든 프로세스의 반환 시간을
// 구하는 함수 호출
findTurnAroundTime(proc, n, wt, tat);
cout << "Processes " << " Burst time " << " Waiting time " << " Turn around time\n";
for (int i = 0; i < n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << proc[i].pid << "\t\t" << proc[i].bt << "\t\t " << wt[i] << "\t\t " << tat[i] << endl;
}
cout << "\nAverage waiting time = " << (float)total_wt / (float)n; cout << "\nAverage turn around time = " << (float)total_tat / (float)n;
}
// 메인 함수
int main() {
Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } };
int n = sizeof(proc) / sizeof(proc[0]);
findavgTime(proc, n);
return 0;
}실행 결과
위 코드를 컴파일하여 실행하면 각 프로세스별 버스트 시간, 대기 시간, 반환 시간이 표 형태로 출력되며, 마지막에 전체 프로세스의 평균 대기 시간과 평균 반환 시간이 함께 표시됩니다.