銀行家算法等

銀行家算法等課內(nèi)實(shí)驗(yàn)報(bào)告課程名： 操作系統(tǒng)任課教師： 沈超專 業(yè)： 信息管理與信息系統(tǒng)學(xué) 號(hào)：姓 名：二○一六至二○一七 年度第一學(xué)期南京郵電大學(xué) 經(jīng)濟(jì)與管理學(xué)院《操作系統(tǒng) 》課程實(shí)驗(yàn)第 一次實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)內(nèi)容及基本要求：實(shí)驗(yàn)項(xiàng)目名稱：調(diào)度系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)類型：設(shè)計(jì)每組人數(shù)： 1實(shí)驗(yàn)內(nèi)容及要求：實(shí)驗(yàn)內(nèi)容:本次實(shí)驗(yàn)的主要內(nèi)容是模擬調(diào)度系統(tǒng)的實(shí)現(xiàn)，包括高級(jí)、中級(jí)和低級(jí)調(diào)度的管理系統(tǒng)實(shí)現(xiàn)，調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn)以及銀行家算法的設(shè)計(jì)設(shè)計(jì)與實(shí)現(xiàn)。本次實(shí)驗(yàn)主要包括兩部分內(nèi)容：1、模擬具有三級(jí)調(diào)度的計(jì)算機(jī)系統(tǒng)進(jìn)程運(yùn)行過程，設(shè)計(jì)進(jìn)程調(diào)度算法，將其存入進(jìn)程文件中。如：進(jìn)程1：運(yùn)行5秒后有3秒的I/O操作，之后有10秒的運(yùn)行，結(jié)束?？梢詫懗桑骸眕1:r5,io3,r3e;”。編程實(shí)現(xiàn)調(diào)度算法函數(shù)，設(shè)計(jì)優(yōu)先級(jí)、時(shí)間片大小和并發(fā)進(jìn)程個(gè)數(shù)，系統(tǒng)不斷從進(jìn)程文件中讀出進(jìn)程信息，選擇一種進(jìn)程調(diào)度算法，模擬進(jìn)程的運(yùn)行及調(diào)度過程，比較不同算法在周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間上的差異。針對(duì)進(jìn)程文件里面的數(shù)據(jù)為正常、缺項(xiàng)、格式不正確等各種情況，檢測程序的執(zhí)行結(jié)果。2、理解安全性算法和銀行家算法的核心機(jī)制：針對(duì)3類資源、5個(gè)進(jìn)程的情況，設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分別表示每個(gè)進(jìn)程占用各類資源的情況；編程實(shí)現(xiàn)安全性算法函數(shù)，編制主函數(shù)，動(dòng)態(tài)輸入資源的占用情況，進(jìn)程的資源申請(qǐng)，調(diào)用安全性函數(shù)，實(shí)現(xiàn)銀行家算法；輸入可分配和不可分配的請(qǐng)求，測試系統(tǒng)的正確性。實(shí)驗(yàn)要求:進(jìn)程調(diào)度模擬程序根據(jù)一個(gè)進(jìn)程調(diào)度文件，模擬進(jìn)程的各種調(diào)度過程，用適合的表達(dá)方式表示出來。銀行家算法程序提供一個(gè)用戶界面，可以在上邊發(fā)出資源申請(qǐng)命令，系統(tǒng)應(yīng)能給出是否可以接受申請(qǐng)，并且有結(jié)論輸出。思考:1、終端型進(jìn)程流適合使用哪種調(diào)度算法？長批處理作業(yè)適合使用哪種調(diào)度算法？2、動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法的優(yōu)先級(jí)變化率應(yīng)該如何設(shè)置？實(shí)驗(yàn)結(jié)果：進(jìn)程調(diào)度過程的模擬（1）概述選擇一個(gè)調(diào)度算法，實(shí)現(xiàn)處理機(jī)調(diào)度。設(shè)計(jì)要求：1）進(jìn)程調(diào)度算法包括：先來先服務(wù)算法，時(shí)間片輪轉(zhuǎn)算法，最高優(yōu)先數(shù)優(yōu)先優(yōu)先算法，動(dòng)態(tài)優(yōu)先級(jí)算法。2）可選擇進(jìn)程數(shù)量3）本程序包括四種算法，用C或C++語言實(shí)現(xiàn)，執(zhí)行時(shí)在主界面選擇算法（可用函數(shù)實(shí)現(xiàn)），進(jìn)入子頁面后輸入進(jìn)程數(shù)，（運(yùn)行時(shí)間，優(yōu)先數(shù)由隨機(jī)函數(shù)產(chǎn)生），執(zhí)行，顯示結(jié)果。（2）設(shè)計(jì)原理1）先來先服務(wù)算法 FCFS每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。2）時(shí)間片輪轉(zhuǎn)法 RR系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。最高優(yōu)先數(shù)優(yōu)先優(yōu)先算法SPF短進(jìn)程優(yōu)先調(diào)度算法是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)再重新調(diào)度。#include<windows.h>#include<iostream>#include<string.h>usingnamespacestd;#defineP_NUM3//進(jìn)程數(shù)#defineP_TIME2//時(shí)間片長度#defineMIN-9999enumstate//進(jìn)程狀態(tài){ready, //就緒run, //執(zhí)行wait, //阻塞finish //完成};classPcb{public:staticvoidprint(){};~Pcb();protected:char*name;

//進(jìn)程名intallTime;intcpuTime;

//需要運(yùn)行時(shí)間//已用cpu時(shí)間stateprocess;

//進(jìn)程狀態(tài)};classHPcb:publicPcb{public:staticvoidprint();staticvoidhighS();staticintgetFirst();private:intfirstNum;};HPcbhpcb[P_NUM];classFPcb:publicPcb{public:staticvoidprint();staticvoidfcfs();private:intcomeTime;};FPcbfpcb[P_NUM];classRPcb:publicPcb{public:staticvoidprint();staticvoidrr();};RPcbrpcb[P_NUM];voidRPcb::rr(){intii,i=0;intk=0;for(;i<P_NUM;i++){char*ch;ch=newchar[1];cout<<"請(qǐng)輸入第"<<i+1<<"個(gè)進(jìn)程的進(jìn)程名、需要運(yùn)行的時(shí)間："<<endl;cin>>ch;rpcb[i].name=newchar[strlen(ch)+1];strcpy(rpcb[i].name,ch);cin>>rpcb[i].allTime;rpcb[i].cpuTime=0;rpcb[i].process=ready;}do{for(i=0;i<P_NUM;i++){if(rpcb[i].process==ready){ rpcb[i].cpuTime+=P_TIME;rpcb[i].process=run;if(rpcb[i].cpuTime>=rpcb[i].allTime)//該進(jìn)程執(zhí)行完成{rpcb[i].cpuTime-=P_TIME;system("cls");print();Sleep(1000);rpcb[i].process=finish;rpcb[i].cpuTime=rpcb[i].allTime;//防止所用時(shí)間超過總的時(shí)間system("cls");print();Sleep(1000);}else{rpcb[i].cpuTime-=P_TIME;system("cls");print();Sleep(1000);rpcb[i].cpuTime+=P_TIME;rpcb[i].process=ready;}}}for(i=0;i<P_NUM;i++)if(rpcb[i].process!=ready)k++;if(k==2){for(i=0;i<P_NUM;i++)if(rpcb[i].process==run)break;rpcb[i].cpuTime+=P_TIME;rpcb[i].process=run;if(rpcb[i].cpuTime>=rpcb[i].allTime)//該進(jìn)程執(zhí)行完成{rpcb[i].process=finish;rpcb[i].cpuTime=rpcb[i].allTime;//防止所用時(shí)間超過總的時(shí)間system("cls");print();Sleep(1000);}else{system("cls");print();Sleep(1000);rpcb[i].process=run;}}for(ii=0;ii<P_NUM;ii++)// 用于判斷是否還有進(jìn)程未完成if(rpcb[ii].process!=finish)break;}while(ii<P_NUM);// 還有進(jìn)程未完成cout<<"所有進(jìn)程已運(yùn)行完成！ "<<endl;}voidHPcb::highS()//最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法{intii,f,i=0;for(;i<P_NUM;i++){char*ch;ch=newchar[1];cout<<"請(qǐng)輸入第"<<i+1<<"個(gè)進(jìn)程的進(jìn)程名優(yōu)先、需要運(yùn)行的時(shí)間："<<endl;cin>>ch;hpcb[i].name=newchar[strlen(ch)+1];strcpy(hpcb[i].name,ch);cin>>hpcb[i].firstNum>>hpcb[i].allTime;hpcb[i].cpuTime=0;hpcb[i].process=ready;}do{f=getFirst();hpcb[f].cpuTime+=P_TIME;hpcb[f].firstNum--;hpcb[f].process=run;if(hpcb[f].cpuTime>=hpcb[f].allTime)// 該進(jìn)程執(zhí)行完成{hpcb[f].cpuTime-=P_TIME;system("cls");print();Sleep(1000);hpcb[f].firstNum=MIN;hpcb[f].process=finish;hpcb[f].cpuTime=hpcb[f].allTime;// 防止所用時(shí)間超過總的時(shí)間system("cls");print();Sleep(1000);}else{hpcb[f].cpuTime-=P_TIME;//為了輸出改變前的相關(guān)信息hpcb[f].firstNum++;//為了輸出改變前的相關(guān)信息system("cls");print();Sleep(1000);hpcb[f].cpuTime+=P_TIME;hpcb[f].firstNum--;hpcb[f].process=ready;}for(ii=0;ii<P_NUM;ii++)// 用于判斷是否還有進(jìn)程未完成if(hpcb[ii].firstNum!=MIN)break;}while(ii<P_NUM);// 還有進(jìn)程未完成cout<<"所有進(jìn)程已運(yùn)行完成！ "<<endl;}Pcb::~Pcb(){delete[]name;}voidFPcb::fcfs() //先來先服務(wù)算法{inti=0;for(;i<P_NUM;i++){char*ch;ch=newchar[1];cout<<"請(qǐng)輸入第"<<i+1<<"個(gè)進(jìn)程的進(jìn)程名,需要運(yùn)行的時(shí)間："<<endl;cin>>ch;fpcb[i].name=newchar[strlen(ch)+1];strcpy(fpcb[i].name,ch);cin>>fpcb[i].allTime;fpcb[i].comeTime=i+1;fpcb[i].cpuTime=0;fpcb[i].process=ready;}for(i=0;i<P_NUM;i++)//P_NUM 個(gè)進(jìn)程{for(int j=0;j<fpcb[i].allTime;j+=P_TIME)//每個(gè)進(jìn)程所用時(shí)間{fpcb[i].cpuTime+=P_TIME; //第i個(gè)進(jìn)程所用時(shí)間加個(gè)時(shí)間片if(fpcb[i].cpuTime<fpcb[i].allTime)// 第i個(gè)進(jìn)程還未完成fpcb[i].process=run; //將其狀態(tài)設(shè)為就緒態(tài)if(fpcb[i].cpuTime>=fpcb[i].allTime){if((i+1)!=P_NUM)//

如果第i+1個(gè)進(jìn)程不是最后一個(gè)進(jìn)程 ,便于下一個(gè)程序從就緒狀態(tài)到運(yùn)行狀態(tài){fpcb[i].cpuTime-=P_TIME;system("cls");print();Sleep(1000);fpcb[i].cpuTime+=P_TIME;fpcb[i].cpuTime=fpcb[i].allTime;fpcb[i].process=finish;fpcb[i+1].process=run;system("cls");print();Sleep(1000);}else{fpcb[i].cpuTime-=P_TIME;system("cls");print();Sleep(1000);fpcb[i].process=finish;fpcb[i].cpuTime=fpcb[i].allTime;system("cls");print();Sleep(1000);}}else{fpcb[i].cpuTime-=P_TIME;system("cls");print();Sleep(1000);fpcb[i].cpuTime+=P_TIME;}}}cout<<"所有進(jìn)程已運(yùn)行完成！ "<<endl;}intHPcb::getFirst()// 得到優(yōu)先級(jí)最高的進(jìn)程{intk=0;for(inti=1;i<P_NUM;i++)if(hpcb[k].firstNum<hpcb[i].firstNum)k=i;returnk;}voidHPcb::print(){cout<<"**********************************************"<<endl;cout<<"進(jìn)程名"<<"\t"<<"還需運(yùn)行時(shí)間\t"<<"已用CPU時(shí)間"<<"\t"<<"優(yōu)先級(jí)"<<"\t"<<"狀態(tài)"<<endl;for(inti=0;i<P_NUM;i++){cout<<hpcb[i].name<<"\t\t"<<hpcb[i].allTime-hpcb[i].cpuTime<<"\t\t"<<hpcb[i].cpuTime<<"\t"<<hpcb[i].firstNum<<"\t";switch(hpcb[i].process){阻 塞 態(tài)"<<endl;break;case

ready:cout<<"

就 緒 態(tài)"<<endl;break;case

run:cout<<"

運(yùn) 行 態(tài)"<<endl;break;case

finish:cout<<"

完 成

態(tài)"<<endl;break;}}cout<<""<<endl;cout<<endl;}voidRPcb::print(){cout<<"********************************************"<<endl;cout<<"進(jìn)程名"<<"\t"<<"還需運(yùn)行時(shí)間\t"<<"已用CPU時(shí)間"<<"\t"<<"狀態(tài)"<<endl;for(inti=0;i<P_NUM;i++){cout<<rpcb[i].name<<"\t\t"<<rpcb[i].allTime-rpcb[i].cpuTime<<"\t\t"<<rpcb[i].cpuTime<<"\t";switch(rpcb[i].process){case

wait:cout<<"

阻 塞 態(tài)"<<endl;break;case

ready:cout<<"

就 緒 態(tài)"<<endl;break;case

run:cout<<"

運(yùn) 行 態(tài)"<<endl;break;case

finish:cout<<"

完 成 態(tài)"<<endl;break;}}cout<<""<<endl;cout<<endl;}voidFPcb::print(){cout<<"***********************************************"<<endl;cout<<"進(jìn)程名"<<"\t"<<"還需運(yùn)行時(shí)間\t"<<"已用CPU時(shí)間"<<"\t"<<" 狀態(tài)"<<endl;for(inti=0;i<P_NUM;i++){cout<<fpcb[i].name<<"\t\t"<<fpcb[i].allTime-fpcb[i].cpuTime<<"\t\t"<<fpcb[i].cpuTime<<"\t";switch(fpcb[i].process){case wait:cout<<" 阻 塞 態(tài)"<<endl;break;case ready:cout<<" 就 緒 態(tài)"<<endl;break;case run:cout<<" 運(yùn) 行 態(tài)"<<endl;break;case finish:cout<<" 完 成 態(tài)"<<endl;break;}}cout<<""<<endl;cout<<endl;}voidmain(){charch;cout<<"請(qǐng)選擇算法：\n1.先來先服務(wù)算法\n2.時(shí)間片輪轉(zhuǎn)調(diào)度算法\n3.最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法\n"<<endl;cin>>ch;if(ch=='1')FPcb::fcfs();elseif(ch=='2')RPcb::rr();elseif(ch=='3')HPcb::highS();}安全性算法和銀行家算法的核心機(jī)制銀行家算法原理：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。為保證資金的安全,銀行家規(guī)定:當(dāng)一個(gè)顧客對(duì)資金的最大需求量不超過銀行家現(xiàn)有的資金時(shí)就可接納該顧客;顧客可以分期貸款,但貸款的總數(shù)不能超過最大需求量;當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí),對(duì)顧客的貸款可推遲支付,但總能使顧客在有限的時(shí)間里得到貸款;當(dāng)顧客得到所需的全部資金后,一定能在有限的時(shí)間里歸還所有的資金.操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測試該進(jìn)程本次申請(qǐng)的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。銀行家算法進(jìn)程i發(fā)出請(qǐng)求資源申請(qǐng)，(1)如果Request[j]<=need[i,j],轉(zhuǎn)向步驟(2),否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已經(jīng)超過它所宣布的最大值。(2)如果：Requesti[j]<=available[i,j]，轉(zhuǎn)向步驟(3)，否則表示尚無足夠資源，進(jìn)程i需等待。(3)若以上兩個(gè)條件都滿足，則系統(tǒng)試探著將資源分配給申請(qǐng)的進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：可利用資源向量 Available[i,j]=Available[i,j]- 最大需求矩陣Request[j]；分配矩陣

Allocation[i][j]=Allocation[i][j]+Request[j]

；需求矩陣

need[i][j]=need[i][j]-Request[j]

；(4)試分配后，執(zhí)行安全性檢查，調(diào)用check()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程；否則本次試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓該進(jìn)程等待。(5)用do{?}while 循環(huán)語句實(shí)現(xiàn)輸入字符 y/n判斷是否繼續(xù)進(jìn)行資源申請(qǐng)。安全性檢測算法設(shè)置兩個(gè)向量：工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，在執(zhí)行安全性算法開始時(shí)，Work=Available。工作向量Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish[i]=false；當(dāng)有足夠的資源分配給進(jìn)程時(shí)， 再令Finish[i]=true。(2)在進(jìn)程中查找符合以下條件的進(jìn)程：條件1：Finish[i]=false；條件2：need[i][j]<=Work[j] 若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4)(3)當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work[j]=Work[j]+Allocation[i][j]；Finish[i]=true；gotostep(2)；(4)如果所有的Finish[i]=true 都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。流程圖程序源代碼#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<iostream.h>#definem50intno1; //進(jìn)程數(shù)intno2; //資源數(shù)intr;intallocation[m][m],need[m][m],available[m],max[m][m];char

name1[m],name2[m];//定義全局變量voidmain(){voidcheck();voidprint();inti,j,p=0,q=0;charc;intrequest[m],allocation1[m][m],need1[m][m],available1[m];printf("**********************************************\n");printf("* 銀行家算法的設(shè)計(jì)與實(shí)現(xiàn) *\n");printf("**********************************************\n");printf("請(qǐng)輸入進(jìn)程總數(shù):\n");scanf("%d",&no1);printf("請(qǐng)輸入資源種類數(shù):\n");scanf("%d",&no2);printf("請(qǐng)輸入Max矩陣:\n");for(i=0;i<no1;i++)for(j=0;j<no2;j++)scanf("%d",&max[i][j]); //輸入已知進(jìn)程最大資源需求量printf("請(qǐng)輸入Allocation矩陣:\n");for(i=0;i<no1;i++)for(j=0;j<no2;j++)scanf("%d",&allocation[i][j]); //輸入已知的進(jìn)程已分配的資源數(shù)for(i=0;i<no1;i++)for(j=0;j<no2;j++)need[i][j]=max[i][j]-allocation[i][j]; //根據(jù)輸入的兩個(gè)數(shù)組計(jì)算出 need矩陣的值printf("請(qǐng)輸入Available矩陣\n");for(i=0;i<no2;i++)scanf("%d",&available[i]); //輸入已知的可用資源數(shù)print(); //輸出已知條件check();//檢測T0時(shí)刻已知條件的安全狀態(tài)if(r==1)//如果安全則執(zhí)行以下代碼{do{q=0;p=0;printf("\n 請(qǐng)輸入請(qǐng)求資源的進(jìn)程號(hào)(0~4)：\n");for(j=0;j<=10;j++)scanf("%d",&i);if(i>=no1){printf("輸入錯(cuò)誤，請(qǐng)重新輸入：\n");continue;}elsebreak;}while（i）printf("\n請(qǐng)輸入該進(jìn)程所請(qǐng)求的資源數(shù)request[j]:\n");for(j=0;j<no2;j++)scanf("%d",&request[j]);for(j=0;j<no2;j++)if(request[j]>need[i][j])p=1;

//判斷請(qǐng)求是否超過該進(jìn)程所需要的資源數(shù)if(p)printf("請(qǐng)求資源超過該進(jìn)程資源需求量，請(qǐng)求失?。n");else{for(j=0;j<no2;j++)if(request[j]>available[j])q=1;//判斷請(qǐng)求是否超過可用資源數(shù)if(q)printf("沒有做夠的資源分配，請(qǐng)求失敗！\n");else //請(qǐng)求滿足條件{for(j=0;j<no2;j++){available1[j]=available[j];allocation1[i][j]=allocation[i][j];need1[i][j]=need[i][j]; //保存原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)available[j]=available[j]-request[j];allocation[i][j]+=request[j];need[i][j]=need[i][j]-request[j];// 系統(tǒng)嘗試把資源分配給請(qǐng)求的進(jìn)程}print();check(); //檢測分配后的安全性if(r==0) //如果分配后系統(tǒng)不安全{for(j=0;j<no2;j++){available[j]=available1[j];allocation[i][j]=allocation1[i][j];need[i][j]=need1[i][j]; //還原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)}printf("返回分配前資源數(shù)\n");print();}}}printf("\n 你還要繼續(xù)分配嗎？Y orN?\n");//判斷是否繼續(xù)進(jìn)行資源分配c=getche();}while(c=='y'||c=='Y');}voidcheck() //安全算法函數(shù){intk,f,v=0,i,j;intwork[m],a[m];boolfinish[m];r=1;for(i=0;i<no1;i++)finish[i]=false;//初始化進(jìn)程均沒得到足夠資源數(shù)并完成for(i=0;i<no2;i++)work[i]=available[i];//work[i] 表示可提供進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)k=no1;do{for(i=0;i<no1;i++){if(finish[i]==false){f=1;for(j=0;j<no2;j++)if(need[i][j]>work[j])f=0;if(f==1) //找到還沒有完成且需求數(shù)小于可提供進(jìn)程繼續(xù)運(yùn)行的資源數(shù)的進(jìn)程{finish[i]=true;a[v++]=i; //記錄安全序列號(hào)for(j=0;j<no2;j++)work[j]+=allocation[i][j]; //釋放該進(jìn)程已分配的資源}}}k--; //每完成一個(gè)進(jìn)程分配，未完成的進(jìn)程數(shù)就減1}while(k>0);f=1;for(i=0;i<no1;i++) //判斷是否所有的進(jìn)程都完成{if(finish[i]==false){f=0;break;}}if(f==0) //若有進(jìn)程沒完成，則為不安全狀態(tài){printf("系統(tǒng)處在不安全狀態(tài)！ ");r=0;}else{printf("\n 系統(tǒng)當(dāng)前為安全狀態(tài)，安全序列為：\n");for(i=0;i<no1;i++)printf("p%d ",a[i]); //輸出安全序列}}voidprint() //輸出函數(shù){inti,j;printf("\n");printf("************* 此時(shí)刻資源分配情況*********************\n");printf("進(jìn)程名/號(hào)|Need |\n");for(i=0;i<no1;

i++){printf(" p%d/%d ",i,i);for(j=0;j<no2;j++){printf("%d ",max[i][j]);}for(j=0;j<no2;j++){printf("%d ",allocation[i][j]);}for(j=0;j<no2;j++){printf("%d ",need[i][j]);}printf("\n");}printf("\n");printf("各類資源可利用的資源數(shù)為 :");for(j=0;j<no2;j++){printf("%d",available[j]);}printf("\n");}小結(jié)：深刻學(xué)習(xí)了進(jìn)程調(diào)度的三種算法和銀行家算法，對(duì)其有了更深程度的理解，并且更深的理解了操作系統(tǒng)內(nèi)部的運(yùn)算方法，對(duì)此產(chǎn)生了濃厚的興趣，課下也會(huì)深入去學(xué)習(xí)。成績?cè)u(píng)定：該生對(duì)待本次實(shí)驗(yàn)的態(tài)度□認(rèn)真□良好□一般□比較差。本次實(shí)驗(yàn)的過程情況□很好□較好□一般□比較差對(duì)實(shí)驗(yàn)結(jié)果的分析□很好□良好□一般□比較差文檔書寫符合規(guī)范程度□很好□良好□一般□比較差綜合意見：成績

指導(dǎo)教師簽名

日期

12.2《操作系統(tǒng) 》課程實(shí)驗(yàn)第 二次實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)內(nèi)容及基本要求：實(shí)驗(yàn)項(xiàng)目名稱：內(nèi)存分配算法模擬實(shí)現(xiàn)實(shí)驗(yàn)類型：操作每組人數(shù)： 1實(shí)驗(yàn)內(nèi)容及要求：實(shí)驗(yàn)內(nèi)容:本實(shí)驗(yàn)的主要內(nèi)容是實(shí)現(xiàn)存儲(chǔ)管理系統(tǒng)中的內(nèi)存分配、地址變換和虛擬存儲(chǔ)管理中的頁面置換。具體內(nèi)容包括三個(gè)方面：1、掌握動(dòng)態(tài)分區(qū)分配的基本原理，設(shè)計(jì)動(dòng)態(tài)分區(qū)分配系統(tǒng)，可以實(shí)現(xiàn)首次適應(yīng)算法、最壞適應(yīng)算法和最佳適應(yīng)算法進(jìn)行分區(qū)分配。2、理解虛擬存儲(chǔ)器的地址變換過程，設(shè)計(jì)用于模擬快表、頁表、地址變換所用的寄存器的數(shù)據(jù)結(jié)構(gòu)。編制頁表的初始信息文件，舉例說明文件中具有的信息：共有5塊，每塊的狀態(tài)、在內(nèi)存和外存的起始地址等。編程實(shí)現(xiàn)虛擬存儲(chǔ)器地址變換算法程序，動(dòng)態(tài)輸入所要訪問的邏輯地址，變換過程文字描述以及變換后的物理地址；檢查輸入有效、無效地址，測試程序的正確性和錯(cuò)誤處理能力。3、編程實(shí)現(xiàn)LRU算法或CLOCK/改進(jìn)算法等置換算法（二選一），模擬實(shí)現(xiàn)虛擬存儲(chǔ)器的地址變換過程。理解LRU或CLOCK改進(jìn)算法等置換算法；設(shè)計(jì)與算法相關(guān)的數(shù)據(jù)結(jié)構(gòu)，如：LRU的堆?；駽LOCK改進(jìn)算法中的循環(huán)結(jié)構(gòu)；按照最多塊的內(nèi)存分配情況，編程實(shí)現(xiàn)所選算法，動(dòng)態(tài)輸入訪問內(nèi)存的塊號(hào)序列，輸出置換結(jié)果；輸入合法、非法的訪問序列數(shù)據(jù)，檢查程序的正確性和健壯性。實(shí)驗(yàn)要求:虛擬地址變換程序提供邏輯地址輸入界面，形象地表示出變換成物理地址的過程與最后變換成的物理地址。置換算法程序提供內(nèi)存訪問序列的輸入界面，輸出正確的置換過程描述和置換結(jié)果。思考:1、地址變換產(chǎn)生錯(cuò)誤的原因有哪些？2、在頁面置換過程中，為什么會(huì)出現(xiàn)抖動(dòng)的情況？實(shí)驗(yàn)結(jié)果：Clock算法的思想：當(dāng)某一頁首次裝入內(nèi)存中時(shí)，則將該頁框的使用位設(shè)置為1；當(dāng)該頁隨后被訪問到時(shí)（在訪問產(chǎn)生缺頁中斷之后），它的使用位也會(huì)被設(shè)置為1。對(duì)于頁面置換算法，用于置換算法，用于置換的候選頁框集合（當(dāng)前進(jìn)程：局部范圍；整個(gè)內(nèi)存；全局范圍）被看做是一個(gè)循環(huán)緩沖區(qū)，并且有一個(gè)指針與之相關(guān)聯(lián)。當(dāng)一頁被置換時(shí)，該指針被設(shè)置成指向緩沖區(qū)中的下一頁框。當(dāng)需要置換一頁時(shí)，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一頁框。每當(dāng)遇到一個(gè)使用位為1的頁框時(shí)，操作系統(tǒng)就將該位重新置為0；如果在這個(gè)過程開始時(shí)，緩沖區(qū)中所有頁框的使用位均為0時(shí)，則選擇遇到的第一個(gè)頁框置換；如果所有頁框的使用位均為 1時(shí)，則指針在緩沖區(qū)中完整地循環(huán)一周， 把所有使用位都置為0，并且停留在最初的位置上，置換該頁框中的頁。主函數(shù)模塊函數(shù)名稱：

intmain()

功能：顯示主菜單，調(diào)用函數(shù)檢測模塊函 數(shù) 名

稱 ：

boolinblock(intnum)

、boolinblock2(intnum)

功能：檢測讀入的頁號(hào)是否存在內(nèi)存中、檢測頁號(hào)是否在內(nèi)存中并把訪問位和修改位置1修改模塊函數(shù)名稱：boolchange()、intwhichpage() 功能：判斷頁面是否已經(jīng)被修改、判斷內(nèi)存中第幾個(gè)需要被置換 Clock 模塊 函數(shù)名稱：voidCLOCK(intnum)

功能：實(shí)現(xiàn)

Clo