时间片轮转RR进程调度算法

操作系统课程的相关实验

• 1.先来先服务FCFS和短作业优先SJF进程调度算法
• 2.时间片轮转RR进程调度算法
• 3.预防进程死锁的银行家算法
• 4.动态分区分配算法
• 5.虚拟内存页面置换算法
• 6.磁盘调度算法

6个实验相关的代码下载地址：http://download.csdn.net/detail/houchaoqun_xmu/9865648

时间片轮转RR进程调度算法

一、概念介绍和案例解析

• 时间片轮转法 - 基本原理：

  在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。

• 时间片轮转法 - 时间片大小的确定：

  在时间片轮转算法中，时间片的大小对系统性能有很大的影响，如选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而增加系统的开销；反之，如选择太长的时间片，使得每个进程都能在一个时间片内完成，时间片轮转算法便退化为FCFS算法，无法满足交互式用户的需求。一个较为可取的大小是，时间片略大于一次典型的交互所需要的时间。这样可使大多数进程在一个时间片内完成。

• 案例解析：

（如上gif图是由GifCam软件制作）

所下图所示为q=1和q=4时各进程的平均周转时间和带权平均周转时间，图中的RR(Round Robin)表示轮转调度算法。

二、实验介绍

• 问题描述：

  设计程序模拟进程的时间片轮转RR调度过程。假设有n个进程分别在T₁, … ,T_n时刻到达系统，它们需要的服务时间分别为S₁, … ,S_n。分别利用不同的时间片大小q，采用时间片轮转RR进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。

• 程序要求：

1）进程个数n；每个进程的到达时间T₁,… ,T_n和服务时间S₁,… ,S_n；输入时间片大小q。

2）要求时间片轮转法RR调度进程运行，计算每个进程的周转时间和带权周转时间，并且计算所有进程的平均周转时间和带权平均周转时间；

3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；

4）输出：要求输出计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。

三、程序设计：

• 本程序采用文件流的输入方式，将进程的到达时间、服务时间进行赋值。
• 本程序采用数据结构的形式，将进行定义为一个数据结构：

typedef struct  {char name;int ArrivalTime;int ServiceTime;int FinishedTime;int WholeTime;double WeightWholeTime;}RR;

• 本程序采用while循环对队列进行相应的处理，采用嵌套的for循环对q>1的情况做处理，将满足进程的到达时间小于当前时间的进程都进入队列。
• 队列思想：分两部分处理，当队首的服务时间小于或者等于0的时候，将队首元素出队列，反之，将队首元素插入到队尾（注意，要先将新到来的进程插入队尾后，再将队首元素插入队尾）。
• 各个进程的结束时间的处理：本程序在队列过程处理中，将进程的执行时间情中，然后，在后续的处理过程中，利用while循环，按照一遇到重复的进程名就更新的原则进行处理，如下：

for (int i=0;i<finalProcessNumber;i++){count = 0;cout<<setw(3)<<processMoment[i]<<setw(3)<<endl;while(RRarray[count].name!=processMoment[i] && count<n){count++;}RRarray[count].FinishedTime = time;if (i<finalProcessNumber - 1){cout<<setw(3)<<time<<"时刻"<<" --> "<<setw(2)<<time + processTime[i+1]<<"时刻"<<setw(3);time += processTime[i+1];}}

四、实验结果分析

• 时间片q=1，输入数据如下：

进程个数 = 5
时间片 q = 1
进程名字 = A B C D E
到达时间 = 0 1 2 3 4
服务时间 = 4 3 5 2 4

• 时间片q=4，输入数据如下：

进程个数 = 5
时间片 q = 4
进程名字 = A B C D E
到达时间 = 0 1 2 3 4
服务时间 = 4 3 5 2 4

• 练习题 and 程序实现：本文分享一道习题，建议读者先手动算一遍，验证程序的准确性！

用时间片轮转法RR调度进程A、B、C、D和E，时间片q分别为2和4，完成下面的表格：

程序实现结果如下：

• q = 1：

• q = 4：

五、实验源码

// 操作系统_实验二（RR调度算法）.cpp : 定义控制台应用程序的入口点。//#include <iostream>#include <queue>#include <iomanip>#include <fstream>using namespace std;typedef struct  {char name;int ArrivalTime;int ServiceTime;int FinishedTime;int WholeTime;double WeightWholeTime;}RR;static queue<RR>RRqueue;  //声明一个队列static double AverageWT =0,AverageWWT=0;static int q;  //时间片static int n;  //进程个数static RR RRarray[100];  //进程结构void Input(){//文件读取模式ifstream inData;inData.open("./data4.txt");//data.txt表示q = 4的RR调度算法//data2.txt表示q = 1的RR调度算法inData>>n;inData>>q;for (int i=0;i<n;i++){inData>>RRarray[i].name;}for (int i=0;i<n;i++){inData>>RRarray[i].ArrivalTime;}for (int i=0;i<n;i++){inData>>RRarray[i].ServiceTime;}//用户输入模式//cout<<"****************************************************************"<<endl;//cout<<"please input the number of process n = ";//cin>>n;//cout<<"please input the number of timeSlice q = ";//cin>>q;//cout<<"please input the name of process:"<<endl;//for (int i=0;i<n;i++)//{//cin>>RRarray[i].name;//}//cout<<"please input the ArrivalTime of process:"<<endl;//for (int i=0;i<n;i++)//{//cin>>RRarray[i].ArrivalTime;//}//cout<<"please input the ServiceTime of process:"<<endl;//for (int i=0;i<n;i++)//{//cin>>RRarray[i].ServiceTime;//}cout<<"****************************************************************"<<endl;//输出用户所输入的信息cout<<"The information of processes is the following:"<<endl;cout<<setw(10)<<"processName"<<" ";cout<<setw(10)<<"ArrivalTime"<<" ";cout<<setw(10)<<"ServiceTime"<<" "<<endl;for (int i=0;i<n;i++){cout<<setw(10)<<RRarray[i].name<<" ";cout<<setw(10)<<RRarray[i].ArrivalTime<<" ";cout<<setw(10)<<RRarray[i].ServiceTime<<" "<<endl;}cout<<"****************************************************************"<<endl;}void RRAlgorithm(){char processMoment[100];   //存储每个时间片p对应的进程名称RRqueue.push(RRarray[0]);int processMomentPoint = 0;int CurrentTime=0;int tempTime;   //声明此变量控制CurrentTime的累加时间，当前进程的服务时间小于时间片q的时候，起到重要作用int i=1;  //指向还未处理的进程的下标int finalProcessNumber = 0;   //执行RR算法后，进程的个数int processTime[50];//CurrentTime的初始化if (RRarray[0].ServiceTime>=q){CurrentTime = q;}else{CurrentTime = RRarray[0].ServiceTime;}while(!RRqueue.empty()){for (int j=i;j<n;j++)   //使得满足进程的到达时间小于当前时间的进程都进入队列{if (RRarray[j].name!=NULL && CurrentTime >= RRarray[j].ArrivalTime) {RRqueue.push(RRarray[j]);i++;}}if (RRqueue.front().ServiceTime<q){tempTime = RRqueue.front().ServiceTime;}else{tempTime = q;}RRqueue.front().ServiceTime -= q;   //进程每执行一次，就将其服务时间 -q//将队首进程的名称放入数组中processMoment[processMomentPoint] = RRqueue.front().name;processMomentPoint++;processTime[finalProcessNumber] = tempTime;finalProcessNumber++;if (RRqueue.front().ServiceTime <= 0)  //把执行完的进程退出队列{//RRqueue.front().FinishedTime = CurrentTime;RRqueue.pop();   //如果进程的服务时间小于等于，即该进程已经服务完了，将其退栈}else{//将队首移到队尾RRqueue.push(RRqueue.front());RRqueue.pop();}CurrentTime += tempTime;}//进程输出处理   每个时间段对应的执行的进程cout<<"各进程的执行时刻信息："<<endl;cout<<"  "<<"0时刻 --> "<<setw(2)<<processTime[0]<<"时刻";processTime[finalProcessNumber]=0;int time = processTime[0];int count = 0;for (int i=0;i<finalProcessNumber;i++){count = 0;cout<<setw(3)<<processMoment[i]<<setw(3)<<endl;while(RRarray[count].name!=processMoment[i] && count<n){count++;}RRarray[count].FinishedTime = time;if (i<finalProcessNumber - 1){cout<<setw(3)<<time<<"时刻"<<" --> "<<setw(2)<<time + processTime[i+1]<<"时刻"<<setw(3);time += processTime[i+1];}}cout<<endl;//周转时间、带权周转时间、平均周转时间、带权平均周转时间的计算//1. 周转时间 = 完成时间 - 到达时间//2. 带权周转时间 = 周转时间/服务时间for (int i=0;i<n;i++){RRarray[i].WholeTime = RRarray[i].FinishedTime - RRarray[i].ArrivalTime;RRarray[i].WeightWholeTime = (double)RRarray[i].WholeTime/RRarray[i].ServiceTime;}double x=0,y=0;for (int i=0;i<n;i++){x += RRarray[i].WholeTime;y += RRarray[i].WeightWholeTime;}AverageWT = x/n;AverageWWT = y/n;}void display(){cout<<"******************************************************"<<endl;cout<<"RR调度算法执行后：进程相关信息如下："<<endl;cout<<setw(10)<<"进程名（ID）"<<" ";cout<<setw(10)<<"到达时间"<<" ";cout<<setw(10)<<"服务时间"<<" ";cout<<setw(10)<<"完成时间"<<" ";cout<<setw(10)<<"周转时间"<<" ";cout<<setw(10)<<"带权周转时间"<<endl;for (int i = 0;i<n;i++){cout<<setw(10)<<RRarray[i].name<<" ";cout<<setw(10)<<RRarray[i].ArrivalTime<<" ";cout<<setw(10)<<RRarray[i].ServiceTime<<" ";cout<<setw(10)<<RRarray[i].FinishedTime<<" ";cout<<setw(10)<<RRarray[i].WholeTime<<" ";cout<<setw(10)<<RRarray[i].WeightWholeTime<<" "<<endl;;}cout<<"所有进程的平均周转时间 = "<<AverageWT<<endl;cout<<"所有进程的平均带权周转时间 = "<<AverageWWT<<endl;cout<<"******************************************************"<<endl;}int main(){Input();RRAlgorithm();display();system("pause");return 0;}

（2018.01.08 使用 DEV C++ 的说明）

如果读者们使用的是DEV C++，细节步骤如下：

1）使用DEV C++创建一个source file

2）把代码复制过去

3）把#include "stdafx.h"注释掉

4）把数据文件.txt也复制到根目录下

5）按 F10 直接 run 这个代码即可。

[Warning] NULL used in arithmetic [-Wpointer-arith] 只是对NULL的警告而已，不影响运行程序。

（本人使用 DEV C++ 的运行情况如下所示）