소개
이 랩에서는 C++ 로 Round Robin 스케줄링 알고리즘을 구현하는 방법을 배웁니다. Round Robin 스케줄링 알고리즘은 선점형 알고리즘으로, 프로세스가 시간 퀀텀 (time quantum) 이라고 하는 고정된 시간 조각 동안 실행됩니다. 프로세스가 시간 퀀텀 내에 실행을 완료하면 종료되고, 그렇지 않으면 준비 큐 (ready queue) 의 끝으로 이동합니다.
새 C++ 파일 생성
먼저, ~/project 디렉토리에 새로운 C++ 파일을 생성합니다. 파일 이름은 round_robin.cpp로 지정할 수 있습니다.
cd ~/project
touch round_robin.cpp필요한 라이브러리 포함
round_robin.cpp 파일에 필요한 라이브러리를 포함합니다.
#include <iostream>
using namespace std;main() 함수 정의
main() 함수를 정의하고 프로세스 ID, burst time (버스트 시간), quantum (퀀텀), 그리고 프로세스 수를 초기화합니다.
int main()
{
// Process IDs (프로세스 ID)
int processes[] = { 1, 2, 3, 4 };
// Burst time of all processes (모든 프로세스의 버스트 시간)
int burst_time[] = { 5, 9, 6, 8 };
// Time quantum (시간 퀀텀)
int quantum = 2;
// Number of processes (프로세스 수)
int n = sizeof processes / sizeof processes[0];
return 0;
}대기 시간 계산 함수 구현
findWaitingTime() 함수는 모든 프로세스의 대기 시간을 찾는 데 사용됩니다. 이 함수는 라운드 로빈 방식으로 프로세스를 반복하도록 정의됩니다.
void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum)
{
// Make a copy of burst times bt[] to store remaining
// burst times. (남은 버스트 시간을 저장하기 위해 버스트 시간 bt[] 의 복사본을 만듭니다.)
int rem_bt[n];
for (int i = 0; i < n; i++)
rem_bt[i] = bt[i];
int t = 0; // Current time (현재 시간)
// Keep traversing processes in round-robin manner
// until all of them are not done. (모든 프로세스가 완료될 때까지 라운드 로빈 방식으로 프로세스를 계속 순회합니다.)
while (1) {
bool done = true;
// Traverse all processes one by one repeatedly (모든 프로세스를 하나씩 반복적으로 순회합니다.)
for (int i = 0; i < n; i++) {
// If burst time of a process is greater than 0
// then only need to process further (프로세스의 버스트 시간이 0 보다 크면
// 추가 처리가 필요합니다.)
if (rem_bt[i] > 0) {
done = false; // There is a pending process (대기 중인 프로세스가 있습니다.)
/* If remaining burst time is greater than
quantum then decrease the time slice
from remaining burst time (남은 버스트 시간이
quantum 보다 크면 남은 버스트 시간에서 시간 슬라이스를 줄입니다.) */
if (rem_bt[i] > quantum) {
// Increase the value of t i.e. shows
// how much time a process has been processed (t 의 값을 증가시킵니다. 즉,
// 프로세스가 처리된 시간을 보여줍니다.)
t += quantum;
// Decrease the burst_time of current process
// by quantum (현재 프로세스의 burst_time 을
// quantum 만큼 감소시킵니다.)
rem_bt[i] -= quantum;
}
/* If remaining burst time is smaller than
or equal to quantum then the remaining
burst time for this process is 0. (남은 버스트 시간이
quantum 보다 작거나 같으면 이 프로세스의 남은
버스트 시간은 0 입니다.) */
else {
// Increase the value of t i.e. shows
// how much time a process has been processed (t 의 값을 증가시킵니다. 즉,
// 프로세스가 처리된 시간을 보여줍니다.)
t += rem_bt[i];
// Waiting time is current time minus time
// used by this process (대기 시간은 현재 시간에서
// 이 프로세스에 사용된 시간을 뺀 값입니다.)
wt[i] = t - bt[i];
// As the process gets fully executed
// make its remaining burst time = 0 (프로세스가 완전히 실행되면
// 남은 버스트 시간을 0 으로 만듭니다.)
rem_bt[i] = 0;
}
}
}
// If all processes are done (모든 프로세스가 완료되면)
if (done == true)
break;
}
}반환 시간 계산 함수 구현
findTurnAroundTime() 함수는 모든 프로세스의 반환 시간을 찾는 데 사용됩니다.
void findTurnAroundTime(int processes[], int n,
int bt[], int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i] (bt[i] + wt[i] 를 더하여 반환 시간을 계산합니다.)
for (int i = 0; i < n; i++)
tat[i] = bt[i] + wt[i];
}평균 시간 계산 함수 구현
findavgTime() 함수는 모든 프로세스의 평균 대기 시간과 평균 반환 시간을 계산하는 데 사용됩니다.
void findavgTime(int processes[], int n, int bt[],
int quantum)
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Function to find waiting time of all processes (모든 프로세스의 대기 시간을 찾는 함수)
findWaitingTime(processes, n, bt, wt, quantum);
// Function to find turn around time for all processes (모든 프로세스의 반환 시간을 찾는 함수)
findTurnAroundTime(processes, n, bt, wt, tat);
// Display processes along with all details (모든 세부 정보와 함께 프로세스 표시)
cout << "Processes "
<< " Burst time "
<< " Waiting time "
<< " Turn around time\n";
// Calculate total waiting time and total turn
// around time (총 대기 시간 및 총 반환 시간 계산)
for (int i = 0; i < n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << i + 1 << "\t\t" << bt[i] << "\t "
<< wt[i] << "\t\t " << tat[i] << endl;
}
cout << "Average waiting time = "
<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n;
}findavgTime() 함수 호출
findavgTime() 함수를 호출하여 프로세스의 평균 대기 시간과 평균 반환 시간을 계산합니다.
int main()
{
int processes[] = { 1, 2, 3, 4 };
// Burst time of all processes (모든 프로세스의 버스트 시간)
int burst_time[] = { 5, 9, 6, 8 };
// Time quantum (시간 퀀텀)
int quantum = 2;
// Number of processes (프로세스 수)
int n = sizeof processes / sizeof processes[0];
// Function to find average time (평균 시간을 찾는 함수)
findavgTime(processes, n, burst_time, quantum);
return 0;
}터미널에서 코드를 실행하려면 ~/project 디렉토리에서 다음 명령을 실행하십시오.
g++ round_robin.cpp -o round_robin && ./round_robin요약
이 Lab 에서는 C++ 로 Round Robin 스케줄링 알고리즘을 구현하는 방법을 배웠습니다. 이 알고리즘은 운영 체제에서 시간 퀀텀 (time quantum) 이라고 하는 시간 조각 동안 프로세스를 스케줄링하는 데 사용됩니다. 또한 일련의 프로세스에 대한 평균 대기 시간과 평균 반환 시간을 계산하는 방법도 살펴보았습니다.
