n개의 프로세스(P1, P2, P3, ..., Pn)가 각각의 버스트 시간(Burst Time)과 우선순위 정보와 함께 주어졌다고 가정해 봅시다. 이 글에서는 우선순위 CPU 스케줄링 알고리즘을 활용하여 평균 대기 시간, 평균 반환 시간(Turnaround Time), 그리고 프로세스의 실행 순서를 구하는 방법을 C++ 코드와 함께 자세히 살펴보겠습니다.
대기 시간과 반환 시간이란?
반환 시간(Turnaround Time)은 프로세스가 시스템에 제출된 시점부터 실행이 완료될 때까지 걸린 전체 시간 간격을 의미합니다.
반환 시간 = 프로세스 완료 시간 − 프로세스 제출 시간
대기 시간(Waiting Time)은 반환 시간에서 실제 CPU를 사용한 버스트 시간을 뺀 값으로, 프로세스가 준비 큐에서 실행을 기다린 시간을 나타냅니다.
대기 시간 = 반환 시간 − 버스트 시간
우선순위 스케줄링이란?
우선순위 스케줄링(Priority Scheduling)에서는 모든 프로세스에 0부터 10까지의 우선순위가 부여됩니다. 이때 정수 0은 가장 낮은 우선순위를, 10은 가장 높은 우선순위를 나타냅니다. 우선순위는 운영체제 내부 요인(메모리 요구량, 파일 수 등)에 따라 내부적으로 정의되거나, 운영체제 외부 기준(프로세스 중요도, 사용자 등급 등)에 따라 외부적으로 정의될 수 있습니다.
우선순위 스케줄링은 크게 두 가지 방식으로 나뉩니다.
선점형(Preemptive) 우선순위 스케줄링
새로 도착한 프로세스의 우선순위가 현재 실행 중인 프로세스보다 높다면, 스케줄러는 실행 중인 프로세스로부터 CPU를 강제로 빼앗아(선점하여) 더 높은 우선순위의 프로세스에게 할당합니다.
비선점형(Non-preemptive) 우선순위 스케줄링
새로 도착한 프로세스는 현재 실행 중인 프로세스가 끝날 때까지 기다려야 하며, 스케줄러는 해당 프로세스를 준비 큐(Ready Queue)의 맨 앞에 배치합니다.
우선순위 스케줄링의 단점: 기아 상태(Starvation)
우선순위 스케줄링 알고리즘의 가장 큰 문제점은 무기한 차단(Indefinite Blocking), 즉 기아 상태(Starvation)입니다. 높은 우선순위의 프로세스들이 계속해서 유입되면, 낮은 우선순위의 프로세스는 자원을 할당받지 못하고 무기한 대기하게 될 수 있습니다. 이러한 문제를 완화하기 위해 실제 시스템에서는 오래 대기한 프로세스의 우선순위를 점차 높여주는 '노화(Aging)' 기법이 함께 사용되기도 합니다.
예제
버스트 시간과 우선순위가 서로 다른 4개의 프로세스 P1, P2, P3, P4가 있다고 가정해 보겠습니다. 여기서 0은 가장 낮은 우선순위, 10은 가장 높은 우선순위를 의미합니다.
| 프로세스 | 버스트 시간 | 우선순위 |
|---|---|---|
| P1 | 15 | 2 |
| P2 | 13 | 0 |
| P3 | 10 | 4 |
| P4 | 11 | 1 |
여러 프로세스의 실행 순서는 아래와 같은 간트 차트(Gantt Chart)로 시각적으로 표현할 수 있습니다.
알고리즘
시작
Step 1 -> pid, bt, priority 변수를 포함하는 Process 구조체 생성
Step 2 -> bool compare(Process a, Process b) 함수
return (a.priority > b.priority)
Step 3 -> waitingtime(Process pro[], int n, int wt[]) 함수
wt[0] = 0 설정
i = 1부터 i < n까지 반복
wt[i] = pro[i-1].bt + wt[i-1]
Step 4 -> turnarround(Process pro[], int n, int wt[], int tat[]) 함수
i = 0부터 i < n까지 반복
tat[i] = pro[i].bt + wt[i]
Step 5 -> avgtime(Process pro[], int n) 함수
wt[n], tat[n], total_wt = 0, total_tat = 0 선언 및 초기화
waitingtime(pro, n, wt) 호출
turnarround(pro, n, wt, tat) 호출
"프로세스, 버스트 시간, 대기 시간, 반환 시간" 헤더 출력
i = 0부터 i < n까지 반복
total_wt += wt[i]
total_tat += tat[i]
각 프로세스별 세부 값 출력
평균 대기 시간, 평균 반환 시간 출력
Step 6 -> scheduling(Process pro[], int n) 함수
sort(pro, pro + n, compare) 호출로 우선순위 기준 정렬
i = 0부터 i < n까지 반복하며 실행 순서 출력
avgtime(pro, n) 호출
Step 7 -> int main() 함수
Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}} 선언 및 초기화
n = sizeof pro / sizeof pro[0] 계산
scheduling(pro, n) 호출
종료
C++ 구현 코드
#include<bits/stdc++.h>
using namespace std;
struct Process {
int pid; // 프로세스 ID
int bt; // 필요한 CPU 버스트 시간
int priority; // 해당 프로세스의 우선순위
};
// 우선순위를 기준으로 프로세스 정렬
bool compare(Process a, Process b) {
return (a.priority > b.priority);
}
// 대기 시간 계산 함수
void waitingtime(Process pro[], int n, int wt[]) {
// 첫 번째 프로세스의 대기 시간은 0
wt[0] = 0;
// 대기 시간 계산
for (int i = 1; i < n ; i++ )
wt[i] = pro[i-1].bt + wt[i-1];
}
// 반환 시간 계산 함수
void turnarround( Process pro[], int n, int wt[], int tat[]) {
// bt[i] + wt[i]를 더하여 반환 시간 계산
for (int i = 0; i < n ; i++)
tat[i] = pro[i].bt + wt[i];
}
// 평균 시간 계산 함수
void avgtime(Process pro[], int n) {
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// 모든 프로세스의 대기 시간 계산
waitingtime(pro, n, wt);
// 모든 프로세스의 반환 시간 계산
turnarround(pro, n, wt, tat);
// 프로세스별 상세 정보 출력
cout << "\nProcesses "<< " 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 << " " << pro[i].pid << "\t\t" << pro[i].bt << "\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;
}
// 스케줄링 수행 함수
void scheduling(Process pro[], int n) {
// 우선순위를 기준으로 프로세스 정렬
sort(pro, pro + n, compare);
cout<< "Order in which processes gets executed \n";
for (int i = 0 ; i < n; i++)
cout << pro[i].pid <<" " ;
avgtime(pro, n);
}
// 메인 함수
int main() {
Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}};
int n = sizeof pro / sizeof pro[0];
scheduling(pro, n);
return 0;
}
실행 결과
Order in which processes gets executed 1 3 2 Processes Burst time Waiting time Turn around time 1 10 0 10 3 8 10 18 2 5 18 23 Average waiting time = 9.33333 Average turn around time = 17
결과 해석
실행 결과를 살펴보면, 우선순위가 가장 높은 프로세스 1(우선순위 2)이 먼저 실행되고, 그다음 프로세스 3(우선순위 1), 마지막으로 우선순위가 가장 낮은 프로세스 2(우선순위 0)가 실행됩니다.
- 평균 대기 시간: (0 + 10 + 18) ÷ 3 = 9.33
- 평균 반환 시간: (10 + 18 + 23) ÷ 3 = 17
이처럼 우선순위 스케줄링은 각 프로세스의 중요도에 따라 CPU 자원을 배분하는 직관적인 방식으로, 운영체제의 프로세스 관리를 이해하는 데 필수적인 개념입니다.