操作系統(tǒng)實(shí)驗(yàn)2時(shí)間片輪轉(zhuǎn)和實(shí)驗(yàn)3銀行家算法

實(shí)驗(yàn)二時(shí)間片輪轉(zhuǎn)【實(shí)驗(yàn)?zāi)康摹客ㄟ^這次實(shí)驗(yàn)，加深對進(jìn)程概念的理解，進(jìn)一步掌握進(jìn)程狀態(tài)的轉(zhuǎn)變、進(jìn)程調(diào)度的策略及對系統(tǒng)性能的評價(jià)方法?！緦?shí)驗(yàn)內(nèi)容】問題描述：設(shè)計(jì)程序模擬進(jìn)程的時(shí)間片輪轉(zhuǎn)RR調(diào)度過程。假設(shè)有n個(gè)進(jìn)程分別在T1,…,Tn時(shí)刻到達(dá)系統(tǒng)，它們需要的服務(wù)時(shí)間分別為S1,…,Sn。分別利用不同的時(shí)間片大小q，采用時(shí)間片輪轉(zhuǎn)RR進(jìn)程調(diào)度算法進(jìn)行調(diào)度，計(jì)算每個(gè)進(jìn)程的完成時(shí)間，周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，并且統(tǒng)計(jì)n個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。程序要求如下：1）進(jìn)程個(gè)數(shù)n；每個(gè)進(jìn)程的到達(dá)時(shí)間T1,…,Tn和服務(wù)時(shí)間S1,…,Sn；輸入時(shí)間片大小q。2）要求時(shí)間片輪轉(zhuǎn)法RR調(diào)度進(jìn)程運(yùn)行，計(jì)算每個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間，并且計(jì)算所有進(jìn)程的平均周轉(zhuǎn)時(shí)間，帶權(quán)平均周轉(zhuǎn)時(shí)間；3）輸出：要求模擬整個(gè)調(diào)度過程，輸出每個(gè)時(shí)刻的進(jìn)程運(yùn)行狀態(tài)，如“時(shí)刻3：進(jìn)程B開始運(yùn)行”等等；4）輸出：要求輸出計(jì)算出來的每個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間，所有進(jìn)程的平均周轉(zhuǎn)時(shí)間，帶權(quán)平均周轉(zhuǎn)時(shí)間。源程序在VisualC++6.0中實(shí)現(xiàn)//RR算法#include<iostream.h>#include<iomanip.h>#include<stdio.h>#include<conio.h>#include<malloc.h>#include<stdlib.h>typedefintQElemType;#defineOK1#defineERROR0#defineOVERFLOW-1typedefintStatus;typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}LinkQueue;StatusInitQueue(LinkQueue&Q);StatusDestroyQueue(LinkQueue&Q);StatusEnQueue(LinkQueue&Q,QElemTypee);intDeQueue(LinkQueue&Q,QElemTypee);boolQueueEmpty(LinkQueue&Q);staticconstintMaxNum=100;intn,q,ArrivalTime[MaxNum],ServiceTime[MaxNum],FinishedTime[MaxNum],WholeTime[MaxNum];doubleWeightWholeTime[MaxNum],Average_WT=0,Average_WWT=0;LinkQueueQ;voidRR(int*ArrivalTime,int*ServiceTime,intn,intq,LinkQueue&Q);voidmain(){cout<<"請輸入進(jìn)程總數(shù)n的值(0<n<=100):"<<endl;cin>>n;while(n<0||n>100){ cout<<"你輸入的n的值不正確，請重新輸入！"<<endl; cin>>n;}cout<<"請依次輸入各個(gè)進(jìn)程的到達(dá)時(shí)間："<<endl;for(inti=0;i<n;i++)cin>>ArrivalTime[i];cout<<"請依次輸入各個(gè)進(jìn)程的服務(wù)時(shí)間："<<endl;for(i=0;i<n;i++)cin>>ServiceTime[i];cout<<"請輸入時(shí)間片q的值(0<q<=200):"<<endl;cin>>q;while(q<0||q>200){ cout<<"你輸入的q值不正確，請重新輸入！"<<endl; cin>>q;}RR(ArrivalTime,ServiceTime,n,q,Q);//調(diào)用RR算法}//RR算法的具體實(shí)現(xiàn)voidRR(int*ArrivalTime,int*ServiceTime,intn,intq,LinkQueue&Q){intcountTime=0,e;intSTime[MaxNum],pushed[MaxNum];for(inti=0;i<n;i++){STime[i]=ServiceTime[i];pushed[i]=0;}InitQueue(Q);EnQueue(Q,0);pushed[0]=1;inttime=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<<"時(shí)刻"<<setw(2)<<time<<":進(jìn)程"<<e<<"正在運(yùn)行"<<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)//判斷進(jìn)程e是否已執(zhí)行完 { EnQueue(Q,e); } }for(i=0;i<n;i++){//求周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間 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;//求平均周轉(zhuǎn)時(shí)間Average_WWT/=n;//求平均帶權(quán)周轉(zhuǎn)時(shí)間//----------------輸出----------------cout<<"完成:"<<"";for(i=0;i<n;i++)cout<<setw(8)<<FinishedTime[i]<<"";cout<<endl;cout<<"周轉(zhuǎn):"<<"";for(i=0;i<n;i++)cout<<setw(8)<<WholeTime[i]<<"";cout<<endl;cout<<"帶權(quán)："<<"";for(i=0;i<n;i++)cout<<setw(8)<<setiosflags(ios::fixed)<<setprecision(2)<<WeightWholeTime[i]<<"";cout<<endl;cout<<"平均周轉(zhuǎn)時(shí)間為："<<Average_WT<<endl;cout<<"平均帶權(quán)周轉(zhuǎn)時(shí)間為:"<<Average_WWT<<endl;DestroyQueue(Q);}//初始化鏈隊(duì)列QStatusInitQueue(LinkQueue&Q){ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; returnOK;}//銷毀鏈隊(duì)列QStatusDestroyQueue(LinkQueue&Q){ while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } returnOK;}//入隊(duì)StatusEnQueue(LinkQueue&Q,QElemTypee){QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}//出隊(duì)，并用e返回出隊(duì)節(jié)點(diǎn)的元素值intDeQueue(LinkQueue&Q,QElemTypee){ QueuePtrp; if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p){Q.rear=Q.front;} free(p); returne;}//判斷鏈隊(duì)列Q是否為空boolQueueEmpty(LinkQueue&Q){ if(Q.front==Q.rear) returntrue; elsereturnfalse;}實(shí)例運(yùn)行截圖實(shí)驗(yàn)三銀行家算法【實(shí)驗(yàn)?zāi)康摹客ㄟ^這次實(shí)驗(yàn)，加深對進(jìn)程死鎖的理解，進(jìn)一步掌握進(jìn)程資源的分配、死鎖的檢測和安全序列的生成方法。【實(shí)驗(yàn)內(nèi)容】問題描述：設(shè)計(jì)程序模擬預(yù)防進(jìn)程死鎖的銀行家算法的工作過程。假設(shè)有系統(tǒng)中有n個(gè)進(jìn)程P1,…,Pn，有m類可分配的資源R1,…,Rm，在T0時(shí)刻，進(jìn)程Pi分配到的j類資源為Allocationij個(gè)，它還需要j類資源Needij個(gè)，系統(tǒng)目前剩余j類資源Workj個(gè)，現(xiàn)采用銀行家算法進(jìn)行進(jìn)程資源分配預(yù)防死鎖的發(fā)生。程序要求如下：1）判斷當(dāng)前狀態(tài)是否安全，如果安全，給出安全序列；如果不安全給出理由。2）對于下一個(gè)時(shí)刻T1，某個(gè)進(jìn)程Pk會提出請求Request(R1,…,Rm)，判斷分配給Pk進(jìn)程請求的資源之后。3）輸入：進(jìn)程個(gè)數(shù)n，資源種類m，T0時(shí)刻各個(gè)進(jìn)程的資源分配情況（可以運(yùn)行輸入，也可以在程序中設(shè)置）；4）輸出：如果安全輸出安全的進(jìn)程序列，不安全提示信息。源程序在VisualC++6.0中實(shí)現(xiàn)#include<stdio.h>#include<stdlib.h>/*----------------------常量定義--------------------*/#defineF0#defineT1#definen5//進(jìn)程數(shù)量#definem3//資源種類數(shù)量/*--------------------------------------------------*//*--------------------數(shù)據(jù)結(jié)構(gòu)定義------------------*/intAvailable[m]={3,5,2};//可用資源intWork[m];//工作向量intFinish[n];//用以判斷系統(tǒng)是否有足夠資源分給相應(yīng)進(jìn)程voidRecycle();//若進(jìn)程運(yùn)行完資源回收intbackDos();//判斷所有進(jìn)程是否運(yùn)行完，完后返回操作系統(tǒng)/*--------------------------------------------------*//*-----------------------進(jìn)程-----------------------*/structPCB{intflag;//狀態(tài)標(biāo)志，是否運(yùn)行完intMax[m];//資源最大需求量intAllocation[m];//已分配資源intNeed[m];//還需要的資源intRequest[m];//請求資源量}P[n];/*-----------------------函數(shù)聲明--------------------*/inttryAdminister(intnum);//試分配voidsafeCheck(intnum);//安全性檢查voidPrint();//狀態(tài)輸出/*主函數(shù)(只需改變n、m和下面的初始數(shù)組便可形成新的進(jìn)程量，資源量和狀態(tài))*/intmain(){inti,j,num;inttotal[n][m]={{4,3,1},{3,3,2},{4,1,7},{7,4,3},{5,3,3}};inthave[n][m]={{0,2,1},{1,0,1},{0,1,3},{3,2,1},{0,2,0}};intwant[n][m]={{4,1,0},{2,3,1},{4,0,4},{4,2,2},{5,1,3}};for(i=0;i<n;i++)//初始化進(jìn)程資源分配狀態(tà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();//狀態(tài)輸出while(scanf("%d",&num)!=EOF){printf("輸入進(jìn)程%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"); returnF; }if(tryAdminister(num)==T)safeCheck(num);Recycle();//資源回收if(backDos()==T)//所有進(jìn)程完則返回操作系統(tǒng)return0;Print();}return0;}/*--------------------------------------------------------------------*//*----------------------------試分配函數(shù)-----------------------------*/inttryAdminister(intnum)//試分配{intj;for(j=0;j<m;j++)if(P[num].Request[j]>P[num].Need[j]){printf("非法請求!\n\n");returnF;}elseif(P[num].Request[j]>Available[j]){printf("%d號資源不夠,無法分配，進(jìn)程%d等待。\n\n",j,num);returnF;}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];}returnT;}/*-------------------------------安全性檢查函數(shù)-------------------------------*/voidsafeCheck(intnum){inti,j;intl[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;//就重新查找下一個(gè)可分配成功的進(jìn)程}}}for(i=0;i<n;i++)if(Finish[i]==F){printf("分配不成功，系統(tǒng)將處于不安全狀態(tài).\n\n");for(j=0;j<m;j++)//若分配不成功將進(jìn)程num恢復(fù)到初始時(shí)刻狀態(tài){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("系統(tǒng)安全，一個(gè)進(jìn)程安全序列如下:\n");for(i=0;i<n;i++)if(i!=n-1)printf("P%d——>",l[i]);elseprintf("P%d\n\n",l[i]);}}/*------------------------------------狀態(tài)輸出-----------------------------*/voidPrint(){inti;printf("此時(shí)資源分配情況：\n");printf("********************************************************************\n");printf("\t最大需求\t已分配\t\t需要分配\t可用資源\n");for(i=0;i<n;i++)//輸出進(jìn)程資源分配狀態(tà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)pr