操作系统实验报告
实验二
时间片轮转进程调度算法
学号：
班级：
姓名:
【实验题目】：时间片轮转进程调度算法
【实验目的】
通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。
【实验内容】
问题描述：
设计程序模拟进程的时间片轮转RR调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别利用不同的时间片大小q，采用时间片轮转RR进程调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
程序要求如下：
1）进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；输入时间片大小q。
2）要求时间片轮转法RR调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；
3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；
4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。
实现提示：
用C++语言实现提示：
1）程序中进程调度时间变量描述如下：
int ArrivalTime[100];
int ServiceTime[100];
int PServiceTime[100];
int FinishTime[100];
int WholeTime[100];
double WeightWholeTime[100];
double AverageWT,AverageWWT;
bool Finished[100];
2）进程调度的实现过程如下：
Ø 变量初始化；
Ø 接收用户输入n，T1, … ,Tn，S1, … ,Sn；时间片大小q；
Ø 按照时间片轮转RR算法进行进程调度，计算进程的完成时间、周转时间和带权周转时间；
Ø 计算所有进程的平均周转时间和平均带权周转时间；
Ø 按格式输出调度结果。
实验要求：
1)上机前认真复习时间片轮转RR进程调度调度算法，熟悉进程调度的执行过程；
2)上机时独立编程、调试程序；
3)根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。
【源程序】
头文件RR.h
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#define MaxNum 100
typedef struct pcb //定义进程控制块
{
char Name[MaxNum]; //进程名
int arrivetime; //到达时间
int runtime; //运行时间
int wholetime; //固定运行时间
int FinishTime; //完成时间
double WeightTime; //周转时间
double WeightWholeTime; //带权周转时间
char state; //运行后的状态
struct pcb *next;
}PCB;
//全局变量
int N; //实际进程数
double SumWT; //周转时间之和
double SumWWT; //带权周转时间之和
double AverageWT; //平均周转时间
double AverageWWT; //平均带权周转时间
typedef struct //定义队列，封装头结点，指针分别指向队头和队尾
{
PCB *front,*rear;
}queue;
queue *init() //进程队列置空
{
queue *head;
head=(queue*)malloc(sizeof(queue));
head->front=NULL;
head->rear=NULL;
return head;
}
int empty(queue *head) //检验队列是否为空
{
return (head->front?0:1);
}
queue *append(queue *head,char c[MaxNum],int a,int r,char s) //进程队列入队，往后插入
{
PCB *p;
p=(PCB *)malloc(sizeof(PCB));
strcpy(p->Name,c);
p->arrivetime=a;
p->runtime=r;
p->wholetime=r;
p->state=s;
//p->FinishTime=0;
//p->WeightTime=0;
//p->WeightWholeTime=0;
p->next=NULL;
if(empty(head))
head->front=head->rear=p;
else
{
head->rear->next=p;
head->rear=p;
}
return head;
}
queue *creat(queue *head) //创建进程队列
{
char c[MaxNum];
char s='R';
int a,r,i;
printf("请输入共有几个进程：\n");
scanf("%d",&N);
for(i=1;i<=N;i++)
{
printf("请输入第%d 个进程的进程名:\n",i);
getchar();
gets(c);
printf("请输入第%d 个进程的到达时间:\n",i);
scanf("%d",&a);
printf("请输入第%d 个进程的服务时间:\n",i);
scanf("%d",&r);
head=append(head,c,a,r,s);
}
return head;
}
void print(queue *head) //输入创建的进程队列
{
PCB *p;
p=head->front;
if(!p)
printf("时间片轮转调度队列为空!\n");
while(p)
{
printf("Name=%s arrivetime=%d runtime=%d state=%c",p->Name,p->arrivetime,p->runtime,p->state);
printf("\n");
p=p->next;
}
}
/*******************时间片轮转法调度算法的实现**************************/
void RR(queue *head,int q)
{
int t=head->front->arrivetime, lt=head->rear->arrivetime;
if(head->front->runtime<q)
t=t+head->front->runtime;
else
t=t+q;
/****进程队列为不空才可调度*****/
while(!empty(head))
{
PCB *p1,*p2;
printf("\n时刻 进程 运行后的状态\n");
/*第一种情况：当前运行的时间小于最后一个进程到达时间做一下操作*/
while(t<lt)
{
p1=head->front;
printf("%2d %s",t,p1->Name);
p1->runtime=p1->runtime-q;
//1.运行时间小于0，删除队首
if(p1->runtime<=0)
{
p1->state='C';
printf(" %c\n",p1->state);
p1->FinishTime=t;
p1->WeightTime=p1->FinishTime-p1->arrivetime;
p1->WeightWholeTime=p1->WeightTime/p1->wholetime;
SumWT+=p1->WeightTime;
SumWWT+=p1->WeightWholeTime;
printf("时刻%2d进程%s运行结束,进程%s周转时间=%5.2f,带权周转时间=%5.2f\n",t,p1->Name,p1->Name,p1->WeightTime,p1->WeightWholeTime);
head->front=p1->next;
free(p1);
}
//2.运行时间大于0，向后找位置插入
else
{
printf(" %c\n",p1->state);
p2=p1->next;
while(p2->next && p2->arrivetime != t)
{
p2=p2->next;
}
//此时无新进入队列的进程，有两种情况：1.不用找位置往后插入，队首不变，不做操作
//2.找位置往后插入
if(p2->arrivetime != t)
{
PCB *p3=p1,*p4;
while(p3->next && p3->arrivetime<t)
{
p4=p3;
p3=p3->next;
}
if(p3->arrivetime>t)
{
if(p4!=p1) //p1插在p4后，头为p1->next
{
head->front=p1->next;
p1->next=p4->next;
p4->next=p1;
}
else //不做操作
p4=p3=p2=NULL;
}
else
p4=p3=p2=NULL;
}
//此时有新进入队列的进程时：p1插在新进入队列的进程p2后，队首为p1->next
else
{
head->front=p1->next;
p1->next=p2->next;
p2->next=p1;
}
}
//时刻变化
if(head->front->runtime<q)
t=t+head->front->runtime;
else
t=t+q;
}
/*************第一种情况结束**************/
/******************第二种情况：当期运行的时间大于最后一个进程到达的时间做以下操作*********************/
while(t>=lt)
{
p1=head->front;
printf("%2d %s",t,p1->Name);
p1->runtime=p1->runtime-q;
//1.运行时间小于0，删除队首
if(p1->runtime<=0)
{
p1->state='C';
printf(" %c\n",p1->state);
p1->FinishTime=t;
p1->WeightTime=p1->FinishTime-p1->arrivetime;
p1->WeightWholeTime=p1->WeightTime/p1->wholetime;
SumWT+=p1->WeightTime;
SumWWT+=p1->WeightWholeTime;
printf("时刻%2d进程%s运行结束,进程%s周转时间=%5.2f,带权周转时间=%5.2f\n",t,p1->Name,p1->Name,p1->WeightTime,p1->WeightWholeTime);
//printf("时刻%2d进程%s运行结束",t,p1->pname);
head->front=p1->next;
free(p1);
}
//2.运行时间大于0，直接插在队尾
else
{
printf(" %c\n",p1->state);
//若原队列只有一个进程，不必往队尾插
if(!p1->next)
head->front=p1;
//若原队列有多个进程
else
{
head->front=p1->next;
head->rear->next=p1;
head->rear=p1;
p1->next=NULL;
}
}
//时刻变化，队列为空时不做时刻变化
if(empty(head))
return;
else
{
if(head->front->runtime<q)
t=t+head->front->runtime;
else
t=t+q;
}
}
/*******第二种情况结束*********/
}
}
//主程序Main.cpp
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
void main()
{
queue *head;
int q;
head=init();
head=creat(head);
printf("\n您输入的时间片轮转进程队列为:\n");
print(head);
printf("\n请输入时间片轮转调度的时间片为:");
scanf("%d",&q);
//时间片轮转调度
RR(head,q);
AverageWT=SumWT/N;
AverageWWT=SumWWT/N;
printf("平均周转时间=%5.2f,平均带权周转时间=%5.2f",AverageWT,AverageWWT);
}
【实例运行结果截图】
实例（教材P92-图3-4）
Q=2
Q=4
第二篇：操作系统进程调度算法模拟实验报告
进程调度算法模拟
专业：XXXXX
学号：XXXXX
姓名：XXX
实验日期：20XX年XX月XX日
一、实验目的
通过对进程调度算法的模拟加深对进程概念和进程调度算法的理解。
二、实验要求
编写程序实现对5个进程的调度模拟，要求至少采用两种不同的调度算法分别进行模拟调度。
三、实验方法内容
1. 算法设计思路
将每个进程抽象成一个控制块PCB， PCB用一个结构体描述。
构建一个进程调度类。将进程调度的各种算法分装在一个类中。类中存在三个容器，一个保存正在或未进入就绪队列的进程，一个保存就绪的进程，另一个保存已完成的进程。还有一个PCB实例。主要保存正在运行的进程。类中其他方法都是围绕这三个容器可以这个运行中的PCB展开。
主要用到的技术是STL中的vector以维护和保存进程容器、就绪容器、完成容器。
当程序启动时，用户可以选择不同的调度算法。然后用户从控制台输入各个进程的信息，这些信息保存到进程容器中。进程信息输入完毕后，就开始了进程调度，每调度一次判断就绪队列是否为空，若为空则系统时间加一个时间片。判断进程容器中是否有新的进程可以加入就绪队列。
2. 算法流程图
主程序的框架：
进程调度过程：
3. 算法中用到的数据结构
struct fcfs{ //先来先服务算法从这里开始
char name[10];
float arrivetime;
float servicetime;
float starttime;
float finishtime;
float zztime;
float dqzztime;
}; //定义一个结构体，里面包含的有一个进程相关的信息
4. 主要的常量变量
vector<PCB>m_ProcessQueue;//进程输入队列
vector<PCB>m_WaitQueue;//进程就绪队列
vector<PCB>m_FinishQueue;//完成队列
vector<PCB>::iterator m_iter;//迭代器
PCB m_runProcess;//运行中的进程
int m_ProcessCount;//进程数
float m_RunTime;//运行时间
int m_tagIsRun;//是否在运行标志。表示正在运行，表示没有
float m_TimeSlice;//时间片大小
int m_TimeSliceCount;//指时间片轮转中一次分到的时间片个数
char m_SchedulerAlgorithm;//调度算法
5. 主要模块
void PCBInput();//输入进程信息
void PCBSort();//对进程控制块按照优先级排序(采用冒泡排序)
void ProcessSelect();//若当前就绪队列不为空则根据选择的调度算法开始调度。否则，系统时间加.以等待新的进程到来
void PCBDisplay();//打印当前状况下。就绪队列、完成队列、运行中的进程信息
void ProcessRun();//进程运行一次。运行时间加个时间片。并判断进程是否达到完成条件。若是则ProcessStatus='f'.否则为'w';
void ProcessQueueProcess();//查看当前时间下，有无进程加入。若有则把该进程调入就绪队列
void ProcessDispatch();//进程分派，进程执行完成后决定进程该进入哪个队列(就绪、完成)
void TimePast(){ m_RunTime +=m_TimeSlice; ProcessQueueProcess();}//当前系统时间加个时间片，并检查是否有新的进程加入
void SchedulerStatistics();//调度统计，计算周转时间等
void FCFS();//先来先服务
void SJF();//最短进程优先调度
void RR();//简单时间片轮转
void PD();//最高优先数优先
四、实验代码
#include <cstdlib>
#include <iostream>
#include<iomanip>
using namespace std;
struct fcfs{ //先来先服务算法从这里开始
char name[10];
float arrivetime;
float servicetime;
float starttime;
float finishtime;
float zztime;
float dqzztime;
}; //定义一个结构体，里面包含的有一个进程相关的信息
fcfs a[100];
void input(fcfs *p,int N)
{
int i;
cout<<endl;
printf(" 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)\n\n");
for(i=0;i<=N-1;i++)
{
printf(" 请您输入进程%d的信息:\t",i+1);
scanf("\t\t\t%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);
}
}
void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N)
{
int k;
printf("\n\n调用先来先服务算法以后进程运行的顺序是: ");
printf("%s",p[0].name);
for(k=1;k<N;k++)
{
printf("-->%s",p[k].name);
}
cout<<endl;
printf("\n 具体进程调度信息:\n");
printf("\t进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间\n");
for(k=0;k<=N-1;k++)
{
printf("\t%s\t%-.2f\t %-.2f\t %-.2f\t %-.2f\t %-.2f\t %-.2f\n",p[k].name,p[k].arrivetime,
p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);
}
getchar(); //此处必须要有这个函数，否则就看不到显示器上面的输出，可以看到的结果只是一闪而过的一个框剪
}
void sort(fcfs *p,int N) //排序
{
for(int i=0;i<=N-1;i++)
for(int j=0;j<=i;j++)
if(p[i].arrivetime<p[j].arrivetime)
{
fcfs temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) //运行阶段
{
int k;
for(k=0;k<=N-1;k++)
{
if(k==0)
{
p[k].starttime=p[k].arrivetime;
p[k].finishtime=p[k].arrivetime+p[k].servicetime;}
else
{
p[k].starttime=p[k-1].finishtime;
p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}
}
for(k=0;k<=N-1;k++)
{
p[k].zztime=p[k].finishtime-p[k].arrivetime;
p[k].dqzztime=p[k].zztime/p[k].servicetime;
}
}
void FCFS(fcfs *p,int N)
{
float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;
sort(p,N);
deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);
Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);
getchar();
} //先来先服务算法到此结束
struct sjf{//最短进程优先调度算法从这里开始
char name[10];
float arrivetime; //到达时间
float servicetime; //运行时间
float starttime; //开始时间
float finishtime; //完成时间
};
sjf a1[100];
void input(sjf *p,int N1)//进程信息输入
{
int i;
cout<<endl;
printf(" 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)\n");
for(i=0;i<=N1-1;i++)
{
printf(" 请您输入进程%d的信息:\t",i+1);
scanf("\t\t\t%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);
}
}
void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,int N1)//最终结果输出
{
int k;
printf("\n\t调用最短进程优先调度算法以后进程的调度顺序为:");
printf("%s",p[0].name);
for(k=1;k<N1;k++)
{printf("-->%s",p[k].name);}
cout<<endl;
printf("\n给个进程具体调度信息如下:\n");
printf("\n\t进程名\t到达时间\t运行时间\t开始时间\t完成时间\n");
for(k=0;k<=N1-1;k++)
{
printf(" \t%s\t %-.2f\t\t %-.2f\t\t %-.2f\t\t %-.2f\t\n",p[k].name,p[k].arrivetime,
p[k].servicetime,p[k].starttime,p[k].finishtime);
}
getchar();
}
void sort(sjf *p,int N1)//排序
{
for(int i=0;i<=N1-1;i++)
for(int j=0;j<=i;j++)
if(p[i].arrivetime<p[j].arrivetime)
{
sjf temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)//运行阶段
{ int k;
for(k=0;k<=N1-1;k++)
{
if(k==0)
{
p[k].starttime=p[k].arrivetime;
p[k].finishtime=p[k].arrivetime+float(p[k].servicetime)/60;}
else
{
p[k].starttime=p[k-1].finishtime;
p[k].finishtime=p[k-1].finishtime+float(p[k].servicetime)/60;}
}
}
void sjff(sjf *p,int N1)
{
float arrivetime=0,servicetime=0,starttime=0,finishtime=0;
sort(p,N1);
for(int m=0;m<N1-1;m++)
{if(m==0)
p[m].finishtime=p[m].arrivetime+float(p[m].servicetime)/60;
else
p[m].finishtime=p[m-1].finishtime+float(p[m].servicetime)/60;
int i=0;
for(int n=m+1;n<=N1-1;n++)
{
if(p[n].arrivetime<=p[m].finishtime)
i++;
}
float min=p[m+1].servicetime;
int next=m+1;
for(int k=m+1;k<m+i;k++)
{
if(p[k+1].servicetime<min)
{min=p[k+1].servicetime;
next=k+1;}
}
sjf temp;
temp=p[m+1];
p[m+1]=p[next];
p[next]=temp;
}
deal(p,arrivetime,servicetime,starttime,finishtime,N1);
Print(p,arrivetime,servicetime,starttime,finishtime,N1);
getchar();
}//最短进程优先调度算法到这里结束
char menu()//用来输出相关信息的函数
{
char cse1;
while(1)
{
system("cls");
fflush(stdin);
cout<<endl;
cout<<endl;
cout<<"\t"<<"|| <<<<<<<<<<<<欢<<<<<<<<<<< >>>>>>>>>>>>迎>>>>>>>>>>> ||"<<endl ;
cout<<"\t"<<"|| ||"<<endl ;
cout<<"\t"<<"||"<<"\t 进程调度算法模拟"<<"\t\t"<<"||"<<endl;
cout<<"\t"<<"|| ||"<<endl ;
cout<<"\t"<<"||"<<"\t\t 1.先来先服务调度算法 "<<"\t\t"<<"||"<<endl;
cout<<"\t"<<"|| ||"<<endl ;
cout<<"\t"<<"||"<<"\t\t 2.最短进程优先调度算法"<<"\t\t"<<"||"<<endl;
cout<<"\t"<<"|| ||"<<endl ;
cout<<"\t"<<"|| <<<<<<<<<<<<<<<<<<<<<<<<<您>>>>>>>>>>>>>>>>>>>>>>>>> ||"<<endl ;
cout<<endl;
cout<<endl;
cout<<"\t\t 请输入您的选择（1/2）：";
cse1=getchar();
if(cse1<'1'||cse1>'2')
cout<<"你的输入有错！"<<endl;
else
break;
}
return cse1;
}
int main(int argc, char *argv[])
{
while(1)
{
switch(menu())
{
case '1':
int N;
cout<<endl;
cout<<endl;
printf("\t\t<<---!!!@@@先来先服务调度算法@@@!!!--->>\n");
cout<<endl;
printf("输入进程数目:");
scanf("%d",&N);
input(a,N);
FCFS(a,N);
case '2':
int N1;
cout<<endl;
cout<<endl;
printf("\t\t<<---!!!@@@最短进程优先调度算法@@@!!!--->>\n");
cout<<endl;
printf("输入进程数目: ");
scanf("%d",&N1);
input(a1,N1);
sjf *b=a1;
sjf *c=a1;
sjff(b,N1);
getchar();
}
}
system("PAUSE");
return EXIT_SUCCESS;
}
五、实验结果
1. 执行结果
2. 结果分析
先来先服务调度算法就是根据进程达到的时间为依据，哪一个进程先来那么该进程就会先执行；最短进程优先调度算法则是以每个进程执行所需时间长短为依据，某一个进程执行所需花的时间要短些那么该进程就先执行。以上就是本次进程调度实验的依据。
六、实验总结
通过本次实验了解到算法很重要，又更加明白算法本身可以节约时间，而且不同的函数之间在调用的时候要注意很多的问题。