[운영체제] RR(Round-Robin)라운드 로빈, Priority Scheduling +(실습 Round-Robin, Priority c++ 코드 제공)

Round-Robin과 Priority를 c++로 한 번 공부해 볼 것이다.

 

Round-Robin이란?

라운드 로빈 스케줄링(Round Robin Scheduling, RR)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘이다.

 

Priority이란?

 우선순위 스케줄링(Priority Scheduling)는 프로세스의 중요도에 따라 순위를 매겨 처리한다. 프로세스의 의미에 따라 우선순위를 주고 높은 프러세스를 스케줄링하는 방법이다.

---

Round-Robin.cpp 코드

// C++로 구현했습니다.
#include <iostream>
#include <cstdio>
#define NUM_PROC 1000
#define SWITCH_OVERHEAD 1
#define TIME_QUANTUM 2
using namespace std;
// Function to find the waiting time for all
// processes
int findWaitingTime(int n, int bt[], int wt[], int rt[], int quantum)
{
 	// Make a copy of burst times bt[] to store remaining
 	// burst times.
 	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 (rem_bt[i] == bt[i]) // first running quantum
 			rt[i] = t + SWITCH_OVERHEAD; // response time
 			// If burst time of a process is greater than 0
 			// then only need to process further
 			if (rem_bt[i] > 0) {
 				done = false; // There is a pending process
				 printf("%5d: SWITCHING %5d\n", t, SWITCH_OVERHEAD);
 				t = t + SWITCH_OVERHEAD;
 			if (rem_bt[i] > quantum) {
 				printf("%5d: proc(%3d) %5d\n", t, i, quantum);
 				// Increase the value of t i.e. shows
 				// how much time a process has been processed
				t += quantum;
 				// Decrease the burst_time of current process
 				// by quantum
 				rem_bt[i] -= quantum;
 			} // If burst time is smaller than or equal to
			 // quantum. Last cycle for this process
 			else {
				 printf("%5d: proc(%3d) %5d\n", t, i, rem_bt[i]);
				 // 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
 				rem_bt[i] = 0;
 				}
 			} // if
 	} // for
	 // If all processes are done
 	if (done == true)
 		break;
 }
 	return t; // Completion time
}
// Function to calculate turn around time
void findTurnAroundTime(int n, int bt[], int wt[], int tat[])
{
 	// calculating turnaround time by adding
 	// bt[i] + wt[i]
 	for (int i = 0; i < n ; i++)
 		tat[i] = bt[i] + wt[i];
}
// Function to calculate average time
void findavgTime(int n, int bt[], int quantum)
{
	 int wt[n], tat[n], total_wt = 0, total_tat = 0;
	 int rt[n], total_rt = 0; // response time
	 int ct; // completion time
	 // Function to find waiting time of all processes
	 ct = findWaitingTime(n, bt, wt, rt, quantum);
	 // Function to find turn around time for all processes
	 findTurnAroundTime(n, bt, wt, tat);
	 printf("Switching Time = %d\n", SWITCH_OVERHEAD);
	 printf("Time Quantum = %d\n", TIME_QUANTUM); printf("ProcessID Arrival Time Burst Time Waiting Time Turnaround Time Response Time\n");
	 for (int i = 0 ; i < n ; i++) {
 		total_wt = total_wt + wt[i];
 		total_tat = total_tat + tat[i];
 		total_rt = total_rt + rt[i];
 		int compl_time = tat[i] + 0;
 		printf(" %5d %7d %7d %7d %7d %7d\n",
 		i, 0, bt[i], wt[i], tat[i], rt[i]);
 	}
 	printf("Avg. Waiting Time = %9.2f\n", (float)total_wt / (float)n);
 	printf("Avg. Turnaround Time = %9.2f\n", (float)total_tat / (float)n);
 	printf("Avg. Response Time = %9.2f\n", (float)total_rt / (float)n);
 	printf("Completion Time = %6d\n", ct);
	printf("Thoughput(#Jobs/Time)= %9.2f\n", (float)n / (float)ct);
}
int inputData(int burst_time[])
{
 	int i = 0;
 	int num;
	do {
 		num = scanf("%d", &burst_time[i]);
 		if (num <= 0) // End-of-file or zero data
 			break;
 		i++;
 	} while (1);
 return i;
}
// Driver code
int main()
{
 	// Burst time of all processes
 	int burst_time[NUM_PROC];
 	int n;
 	n = inputData(burst_time);
	// Time quantum
 	int quantum = TIME_QUANTUM;
 	findavgTime(n, burst_time, quantum);
 return 0;
}

Priority.cpp 코드

#include <bits/stdc++.h>
#define NUM_PROC 100
using namespace std;
struct Process {
 int processID;
 int burstTime;
 int tempburstTime;
 int responsetime;
 int arrivalTime;
 int priority;
 int outtime;
 int intime;
};
// It is used to include all the valid and eligible
// processes in the heap for execution. heapsize defines
// the number of processes in execution depending on
// the current time currentTime keeps a record of
// the current CPU time.
void insert(Process Heap[], Process value, int* heapsize,
 int* currentTime)
{
 int start = *heapsize, i;
 Heap[*heapsize] = value;
 if (Heap[*heapsize].intime == -1)
 Heap[*heapsize].intime = *currentTime;
 ++(*heapsize);
 // Ordering the Heap
 while (start != 0 && Heap[(start - 1) / 2].priority >
 Heap[start].priority) {
 Process temp = Heap[(start - 1) / 2];
 Heap[(start - 1) / 2] = Heap[start];
 Heap[start] = temp;
 start = (start - 1) / 2;
 }
}
// It is used to reorder the heap according to
// priority if the processes after insertion
// of new process.
void order(Process Heap[], int* heapsize, int start)
{
 int smallest = start;
 int left = 2 * start + 1;
 int right = 2 * start + 2;
 	if (left < *heapsize && Heap[left].priority < Heap[smallest].priority) smallest = left;
 	if (right < *heapsize && Heap[right].priority < Heap[smallest].priority) smallest = right;
 	// Ordering the Heap
 	if (smallest != start) {
 		Process temp = Heap[smallest];
 		Heap[smallest] = Heap[start];
 		Heap[start] = temp;
 		order(Heap, heapsize, smallest);
 	}
}
// This function is used to find the process with
// highest priority from the heap. It also reorders
// the heap after extracting the highest priority process.
Process extractminimum(Process Heap[], int* heapsize,
 int* currentTime)
{
 Process min = Heap[0];
 	if (min.responsetime == -1)
 		min.responsetime = *currentTime - min.arrivalTime;
 		--(*heapsize);
 	if (*heapsize >= 1) {
 		Heap[0] = Heap[*heapsize];
 		order(Heap, heapsize, 0);
 	}
 return min;
}
// Compares two intervals according to staring times.
bool compare(Process p1, Process p2)
{
 return (p1.arrivalTime < p2.arrivalTime);
}
// This function is responsible for executing
// the highest priority extracted from Heap[].
void scheduling(Process Heap[], Process array[], int n,
 int* heapsize, int* currentTime)
{
 if (heapsize == 0)
 return;
 Process min = extractminimum(Heap, heapsize, currentTime);
 min.outtime = *currentTime + 1;
 --min.burstTime;
 printf("%5d: Proc(%3d)\n",
 *currentTime, min.processID); // If the process is not yet finished
 // insert it back into the Heap*/
 	if (min.burstTime > 0) {
 		insert(Heap, min, heapsize, currentTime);
 	return;
	}
 		for (int i = 0; i < n; i++)
 			if (array[i].processID == min.processID) {
 				array[i] = min;
 				break;
 			}
}
// This function is responsible for
// managing the entire execution of the
// processes as they arrive in the CPU
// according to their arrival time.
void priority(Process array[], int n)
{
 sort(array, array + n, compare);
 int totalwaitingtime = 0, totalbursttime = 0,
 totalturnaroundtime = 0, i, insertedprocess = 0,
 heapsize = 0, currentTime = array[0].arrivalTime,
 totalresponsetime = 0;
 Process Heap[4 * n];
 // Calculating the total burst time
 	// of the processes
	 for (int i = 0; i < n; i++) {
		 totalbursttime += array[i].burstTime;
		 array[i].tempburstTime = array[i].burstTime;
	 }
 	// Inserting the processes in Heap
 	// according to arrival time
 	do {
 		if (insertedprocess != n) {
 			for (i = 0; i < n; i++) {
 				if (array[i].arrivalTime == currentTime) {
 					++insertedprocess;
 					array[i].intime = -1;
 					array[i].responsetime = -1;
 					insert(Heap, array[i], &heapsize, &currentTime);
 				}
			 }
		 } scheduling(Heap, array, n, &heapsize, &currentTime);
 	++currentTime;
 	if (heapsize == 0 && insertedprocess == n)
 		break;
 	} while (1);
 	for (int i = 0; i < n; i++) {
 		totalresponsetime += array[i].responsetime;
 		totalwaitingtime += (array[i].outtime - array[i].intime - array[i].tempburstTime);
		// printf("%d: out:%2d in:%2d exec:%2d\n", array[i].processID, array[i].outtime,
		// array[i].intime, array[i].tempburstTime);
		totalbursttime += array[i].burstTime;
 }
 printf("Total waiting time = %f\n", (float)totalwaitingtime);
 printf("Average waiting time = %f\n",
 ((float)totalwaitingtime / (float)n));
 printf("Average response time = %f\n",
 ((float)totalresponsetime / (float)n));
 printf("Average turnaround time = %f\n",
 ((float)(totalwaitingtime + totalbursttime) / (float)n));
}
int inputData(Process a[])
{
 int i = 0;
 int num;
 	do {
 		num = scanf("%d %d %d", &(a[i].arrivalTime), &(a[i].burstTime),&(a[i].priority));
 		if (num <= 0) // End-of-file or zero data
 			break;
 			a[i].processID = i;
 			i++;
 	} while (1);
 return i;
}
// Driver code
int main()
{
 int n, i;
 Process proc[NUM_PROC];
 n = inputData(proc);
 priority(proc, n);
 return 0;
}

1. (Round-Robin)에서 time quantum을 변화시켰을 때, 평균 response time, 평균

waiting time, throughput, 문맥교환 회수를 비교하시오.

 

평균 response time ->값을 늘리면 평균 response time도 증가한다.

평균waiting time -> 값을 늘리면 평균 대기시간도 감소한다.

throughput -> 값을 늘리면 throughput가 증가합니다. 성능이 좋아진다.

문맥교환 횟수 -> 값이 증가되면 문맥교환 횟수가 감소된다.

 

2. 주어진 (Priority) 스케줄링 프로그램은 preemptive 방식인가, non-preemptive 방식인

가?

-preemptive 방식의 스케줄링을 하고 있다.

 

3. 주어진 (Priority) 스케줄링 프로그램에서 각 프로세스의 우선순위는 정적인가, 아니면

동적으로 변하는가?

- 정적으로 변화한다. 항상 우선순위가 정해져있기 때문이다.

 

4. (Priority)에서 sample-prio1.dat와 sample-prio2.dat는 각 프로세스의 우선순위만 다

르다. 수행 결과를 비교하시오.

sample-prio1.dat

0번이 수행되고 8초가되었을때 0번프로세스가 종료되고, 1번프로세스에게 cpu 제어권을 넘긴다. 11초가 되었을때, 1번프로세스는 종료되고 2번프로세스에게 cpu제어권을 넘긴다. 20초가 되었을때 2번프로세스가 종료되고, 3번프로세스가 cpu제어권을 가져간다. 26초가 되었을때 3번프로세스가 종료되고 프로그램이 끝이난다.

 

sample-prio2.dat

0번이 수행되고 4초가되었을때 1번프로세스가 도착한다. 1번프로세스한테 cpu를 뺏긴다. 5초가되었을때, 2번 프로세스가 도착하고 우선순위가 2이다. 다시한번 2번프로세스가 cpu제어권을 뺏는다. 12초가되었을때 3번프로세스한테 cpu 제어권을 넘긴다. 19초가되었을때 3번프로세스가 끝이나고, 다시 2번프로세스한테 cpu제어권을 넘긴다. 21초가되었을때, 2번프로세스가 종료되고 다시 1번프로세스에게 cpu제어권을 넘긴다. 1번프로세스가 22초에 끝난뒤 마지막으로 다시 0번프로세스에게 cpu제어권을넘겨 26초까지 실행 후 종료가된다.

 

5. (Priority)에서 starvation이 생길 수 있는가? 있다면 그 이유는 무엇인가?

- starvation은 나보다 높은 우선순위를 가진사람이 계속 나타나면 평생 순위가 미뤄질수있다.

non-preemptive 방식으로하여도 starvation은 생길 것 같다.