实验二 时间片轮转
【实验目的】
通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。
【实验内容】
问题描述：
设计程序模拟进程的时间片轮转RR调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别利用不同的时间片大小q，采用时间片轮转RR进程调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
程序要求如下：
1）进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；输入时间片大小q。
2）要求时间片轮转法RR调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；
3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；
4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。
源程序
在VisualC++6.0中实现
//RR算法
#include<iostream.h>
#include<iomanip.h>
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int QElemType;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q);
Status DestroyQueue(LinkQueue &Q);
Status EnQueue(LinkQueue &Q,QElemType e);
int DeQueue(LinkQueue &Q,QElemType e);
bool QueueEmpty(LinkQueue &Q);
static const int MaxNum=100;
int
n,q,ArrivalTime[MaxNum],ServiceTime[MaxNum],FinishedTime[MaxNum],WholeTime[MaxNum];
double WeightWholeTime[MaxNum],Average_WT=0,Average_WWT=0;
LinkQueue Q;
void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q);
void main(){
cout<<"请输入进程总数n的值(0<n<=100):"<<endl;
cin>>n;
while(n<0||n>100){
cout<<"你输入的n的值不正确，请重新输入！"<<endl;
cin>>n;
}
cout<<"请依次输入各个进程的到达时间："<<endl;
for(int i=0;i<n;i++)
cin>>ArrivalTime[i];
cout<<"请依次输入各个进程的服务时间："<<endl;
for( i=0;i<n;i++)
cin>>ServiceTime[i];
cout<<"请输入时间片q的值(0<q<=200):"<<endl;
cin>>q;
while(q<0||q>200){
cout<<"你输入的q值不正确，请重新输入！"<<endl;
cin>>q;
}
RR(ArrivalTime,ServiceTime,n,q,Q);//调用RR算法
}
//RR算法的具体实现
void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q){
int countTime=0,e;
int STime[MaxNum],pushed[MaxNum];
for(int i=0;i<n;i++)
{STime[i]=ServiceTime[i];pushed[i]=0;}
InitQueue(Q);
EnQueue(Q,0);pushed[0]=1;
int time=0;
while(QueueEmpty(Q)==false)
{
e=DeQueue(Q,e);
if(STime[e]>q)
{STime[e]=STime[e]-q;
countTime+=q;}
else
{countTime+=STime[e];STime[e]=0;FinishedTime[e]=countTime;
}
while(time<countTime){
if(STime>0){
cout<<"时刻"<<setw(2)<<time<<":进程"<<e<<"正在运行"<<endl;
}
time++;
}
for(i=1;i<n;i++)
{
if(STime!=0&&i!=e&&ArrivalTime[i]<countTime&&pushed[i]==0||STime!=0&&i!=e&&ArrivalTime[i]==countTime)
{
EnQueue(Q,i);pushed[i]=1;
}
}
if(STime[e]>0)//判断进程e是否已执行完
{
EnQueue(Q,e);
}
}
for(i=0;i<n;i++){//求周转时间和带权周转时间
WholeTime[i]=FinishedTime[i]-ArrivalTime[i];
WeightWholeTime[i]=(double)(WholeTime[i]*1.000000/ServiceTime[i]);
Average_WT+=WholeTime[i];
Average_WWT+=WeightWholeTime[i];
}
Average_WT/=n;//求平均周转时间
Average_WWT/=n;//求平均带权周转时间
//----------------输出----------------
cout<<"完成:"<<" ";
for(i=0;i<n;i++)
cout<<setw(8)<<FinishedTime[i]<<" ";
cout<<endl;
cout<<"周转:"<<" ";
for(i=0;i<n;i++)
cout<<setw(8)<<WholeTime[i]<<" ";
cout<<endl;
cout<<"带权："<<" ";
for(i=0;i<n;i++)
cout<<setw(8)<<setiosflags(ios::fixed)<<setprecision(2)<<WeightWholeTime[i]<<" cout<<endl;
cout<<"平均周转时间为："<<Average_WT<<endl;
cout<<"平均带权周转时间为:"<<Average_WWT<<endl;
DestroyQueue(Q);
}
//初始化链队列Q
Status InitQueue(LinkQueue &Q){
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
//销毁链队列Q
Status DestroyQueue(LinkQueue &Q){
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
//入队
Status EnQueue(LinkQueue &Q,QElemType e){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL; ";
Q.rear->next=p;
Q.rear=p;
return OK;
}
//出队，并用e返回出队节点的元素值 int DeQueue(LinkQueue &Q,QElemType e){ QueuePtr p;
if(Q.front==Q.rear) return ERROR; p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) {Q.rear=Q.front;} free(p);
return e;
}
//判断链队列Q是否为空
bool QueueEmpty(LinkQueue &Q){ if(Q.front==Q.rear)
return true;
else return false;
}
实例运行截图
实验三 银行家算法
【实验目的】
通过这次实验，加深对进程死锁的理解，进一步掌握进程资源的分配、死锁的检测和安全序列的生成方法。
【实验内容】
问题描述：
设计程序模拟预防进程死锁的银行家算法的工作过程。假设有系统中有n个进程P1, … ,Pn，有m类可分配的资源R1, … ,Rm，在T0时刻，进程Pi分配到的j类资源为Allocationij个，它还需要j类资源Need ij个，系统目前剩余j类资源Workj个，现采用银行家算法进行进程资源分配预防死锁的发生。
程序要求如下：
1）判断当前状态是否安全，如果安全，给出安全序列；如果不安全给出理由。
2）对于下一个时刻T1，某个进程Pk会提出请求Request(R1, … ,Rm)，判断分配给P k进程请求的资源之后。
3）输入：进程个数n，资源种类m，T0时刻各个进程的资源分配情况（可以运行输入，也可以在程序中设置）；
4）输出：如果安全输出安全的进程序列，不安全提示信息。
源程序
在VisualC++6.0中实现
#include <stdio.h>
#include <stdlib.h>
/*----------------------常量定义--------------------*/
#define F 0
#define T 1
#define n 5 //进程数量
#define m 3 //资源种类数量
/*--------------------------------------------------*/
/*--------------------数据结构定义------------------*/
int Available[m]={3,5,2}; //可用资源
int Work[m]; //工作向量
int Finish[n]; //用以判断系统是否有足够资源分给相应进程
void Recycle(); //若进程运行完资源回收
int backDos(); //判断所有进程是否运行完，完后返回操作系统 /*--------------------------------------------------*/
/*-----------------------进程-----------------------*/
struct PCB
{
int flag; //状态标志，是否运行完
int Max[m]; //资源最大需求量
int Allocation[m]; //已分配资源
int Need[m]; //还需要的资源
int Request[m]; //请求资源量
}P[n];
/*-----------------------函数声明--------------------*/
int tryAdminister(int num);//试分配
void safeCheck(int num); //安全性检查
void Print(); //状态输出
/*主函数(只需改变n、m和下面的初始数组便可形成新的进程量，资源量和状态)*/ int main()
{
int i, j, num;
int total[n][m]={{4,3,1},{3,3,2},{4,1,7},{7,4,3},{5,3,3}};
int have[n][m]={{0,2,1},{1,0,1},{0,1,3},{3,2,1},{0,2,0}};
int want[n][m]={{4,1,0},{2,3,1},{4,0,4},{4,2,2},{5,1,3}};
for (i=0;i<n;i++) //初始化进程资源分配状态
for (j=0;j<m;j++)
{
P[i].flag = F;
P[i].Max[j]=total[i][j];
P[i].Allocation[j]=have[i][j];
P[i].Need[j]=want[i][j];
}
Print(); //状态输出
while (scanf("%d",&num)!=EOF)
{
printf("输入进程%d对这三类资源的需求向量(用空格隔开):\n",num);
scanf("%d %d %d",&P[num].Request[0],&P[num].Request[1],&P[num].Request[2]);
if(&P[num].Request[0]<0||&P[num].Request[1]<0||&P[num].Request[2]<0){ printf("非法请求!\n\n");
return F;
}
if (tryAdminister(num)==T)
safeCheck(num);
Recycle(); //资源回收
if(backDos()==T) //所有进程完则返回操作系统 return 0;
Print();
}
return 0;
}
/*--------------------------------------------------------------------*/
/*----------------------------试分配函数-----------------------------*/
int tryAdminister(int num) //试分配
{
int j;
for (j=0;j<m;j++)
if (P[num].Request[j]>P[num].Need[j])
{
printf("非法请求!\n\n");
return F;
}
else if (P[num].Request[j]>Available[j])
{
printf("%d号资源不够,无法分配，进程%d等待。\n\n",j,num); return F;
}
for (j=0;j<m;j++)
{
Available[j] = Available[j] - P[num].Request[j];
P[num].Allocation[j] = P[num].Allocation[j] + P[num].Request[j]; P[num].Need[j] = P[num].Need[j] - P[num].Request[j];
}
return T;
}
/*-------------------------------安全性检查函数-------------------------------*/ void safeCheck(int num)
{
int i,j;
int l[n],k; //安全序列
for (j=0;j<m;j++) //初始化工作向量
Work[j]=Available[j];
for (i=0;i<n;i++) //初始化判断向量
{
Finish[i]=F;
l[i]=0;
}
k=0;
for (i=0;i<n;i++)
{
if (Finish[i]==F)
{
for (j=0;j<m;j++)
if (P[i].Need[j]>Work[j])break;
if (j==m) //如果分配成功
{
for (j=0;j<m;j++)
Work[j]=Work[j]+P[i].Allocation[j];
Finish[i]=T;
l[k]=i;
k++; //安全序列
i=-1; //就重新查找下一个可分配成功的进程 }
}
}
for (i=0;i<n;i++)
if (Finish[i]==F)
{
printf("分配不成功，系统将处于不安全状态.\n\n");
for (j=0;j<m;j++) //若分配不成功将进程num恢复到初始时刻状态 {
Available[j] = Available[j] + P[num].Request[j];
P[num].Allocation[j] = P[num].Allocation[j] - P[num].Request[j]; P[num].Need[j] = P[num].Need[j] + P[num].Request[j]; }
break;
}
if (i==n)
{
printf("系统安全，一个进程安全序列如下:\n");
for (i=0;i<n;i++)
if (i!=n-1)
printf("P%d——>",l[i]);
else
printf("P%d\n\n",l[i]);
}
}
/*------------------------------------状态输出-----------------------------*/
void Print()
{
int i;
printf("此时资源分配情况：\n");
printf("********************************************************************\n");
printf("\t最大需求\t已分配\t\t需要分配\t可用资源\n");
for (i=0;i<n;i++) //输出进程资源分配状态
{
printf("P%d\t%d %d %d\t\t",i,P[i].Max[0],P[i].Max[1],P[i].Max[2]);
printf("%d %d %d\t\t",P[i].Allocation[0],P[i].Allocation[1],P[i].Allocation[2]); printf("%d %d %d\t\t",P[i].Need[0],P[i].Need[1],P[i].Need[2]);
if (i==0)
printf("%d %d %d\n",Available[0],Available[1],Available[2]);
else printf("\n");
}
printf("********************************************************************\n"); printf("输入下一时刻需要分配的进程号:\n");
}
/*-------------------------------资源回收--------------------------------*/
void Recycle()
{
int i,j;
for (i=0;i<n;i++)
{
for (j=0;j<m;j++)
if (P[i].Need[j]!=0)break;
if (j==m)
{
if (P[i].flag==F)
{
//若进程已得到所有资源并运行完则回收资源
printf("进程P%d已运行完;\n\n",i);
for (j=0;j<m;j++)
{
Available[j] = Available[j]+P[i].Allocation[j]; P[i].Allocation[j]=0;
}
P[i].flag=T;
}
}
}
}
/*-------------------------所有进程运行完就返回操作系统----------------------*/ int backDos()
{
int i;
for(i=0;i<n;i++)
if(P[i].flag!=T)return F;
printf("所有进程已经运行完，程序结束!\n");
return T;
}
实例运行截图
