操作系統(tǒng)實(shí)驗(yàn)之調(diào)度算法

1、師大學(xué)數(shù)計(jì) 學(xué)院實(shí)驗(yàn)報(bào)告專業(yè)名稱軟件工程實(shí)驗(yàn)室2 號(hào) 201實(shí)驗(yàn)課程操作系統(tǒng)實(shí)驗(yàn)實(shí)驗(yàn)名稱調(diào)度算法姓名周*學(xué)號(hào)110*同組人員無(wú)實(shí)驗(yàn)日期201346注：實(shí)驗(yàn)報(bào)告應(yīng)包含(實(shí)驗(yàn)?zāi)康?，?shí)驗(yàn)原理，主要儀器設(shè)備和材料，實(shí)驗(yàn)過(guò)程 和步驟，實(shí)驗(yàn)原始數(shù)據(jù)記錄和處理，實(shí)驗(yàn)結(jié)果和分析，成績(jī)?cè)u(píng)定)等七項(xiàng)容。具體容可根據(jù)專業(yè)特點(diǎn)和實(shí)驗(yàn)性質(zhì)略作調(diào)整，頁(yè)面不夠可附頁(yè)。1. 實(shí)驗(yàn)?zāi)康睦斫饣跁r(shí)間片輪轉(zhuǎn)的處理機(jī)調(diào)度算法，更好的掌握算法的思想，結(jié)合實(shí)驗(yàn)理 解算法更直觀，深刻具體。通過(guò)對(duì)時(shí)間片輪轉(zhuǎn)法處理機(jī)的調(diào)度算法的模擬實(shí)驗(yàn)可 以清楚的了解處理機(jī)是如何調(diào)度的，以及加深對(duì)進(jìn)程的執(zhí)行的過(guò)程的了。2. 實(shí)驗(yàn)原理實(shí)現(xiàn)對(duì)時(shí)間片輪轉(zhuǎn)法處理機(jī)調(diào)

2、度算法的模擬，本程序只對(duì)進(jìn)程的運(yùn)行模擬不實(shí)際 啟動(dòng)，而是將其運(yùn)行時(shí)間加一，判斷要求運(yùn)行時(shí)間與已運(yùn)行時(shí)間是否相等，若相等則表示進(jìn)程結(jié)束，進(jìn)程退出調(diào)度，釋放資源。因只需了解其算法故，本實(shí)驗(yàn)只 模擬進(jìn)程的時(shí)間片輪轉(zhuǎn)算法不實(shí)際運(yùn)行進(jìn)程。3. 實(shí)驗(yàn)過(guò)程和步驟(1) 假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來(lái)代表。進(jìn)程控制塊的格式為：進(jìn)程名指針要求運(yùn)行時(shí)間已運(yùn)行時(shí)間狀態(tài)其中，進(jìn)程名一一 作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為 Q1, Q2 Q3, Q4, Q5 指針一 進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址，最后一個(gè)進(jìn)程的指針指出第一個(gè)進(jìn)程的進(jìn)程控制塊首地址。要求

3、運(yùn)行時(shí)間一一假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。已運(yùn)行時(shí)間一一假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為“ 0” 狀態(tài)一一有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R'表示。當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“ E” 表示。(2) 每次運(yùn)行所設(shè)計(jì)的處理器調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的“要求運(yùn)行 時(shí)間”。(3) 把五個(gè)進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出隊(duì)列連接情況。另用一標(biāo)志單 元記錄輪到運(yùn)行的進(jìn)程。例如，當(dāng)前輪到 P2執(zhí)行，則有：(4) 處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運(yùn)行。由于本實(shí)習(xí)是模擬處理器調(diào)度的功能，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：已運(yùn)

4、行時(shí)間+1來(lái)模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過(guò)一個(gè)單位的時(shí)間。當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須置上該進(jìn)程可以運(yùn)行的時(shí)間片值，以及恢復(fù)進(jìn)程的現(xiàn)場(chǎng)， 讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行滿一個(gè)時(shí)間片(5) 進(jìn)程運(yùn)行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個(gè)輪到運(yùn)行的進(jìn)程。同時(shí)，應(yīng)判斷該進(jìn)程的要求運(yùn)行時(shí)間與已運(yùn)行時(shí)間，若該進(jìn)程的要求運(yùn)行時(shí)間工已運(yùn)行時(shí)間，則表示它尚未執(zhí)行結(jié)束，應(yīng)待到下一輪時(shí)再運(yùn)行。若該進(jìn)程的要求運(yùn)行時(shí)間二已運(yùn)行時(shí)間，則表示它已經(jīng)執(zhí)行結(jié)束，應(yīng)指導(dǎo)它的狀態(tài)修 改成“結(jié)束”(巳且退出隊(duì)列。此時(shí)，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到 前面一個(gè)進(jìn)程的指針位置。(6

5、)若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上 面的(4)和(5)的步驟，直到所有的進(jìn)程都成為“結(jié)束”狀態(tài)。 (7)在所設(shè) 計(jì)的程序中應(yīng)有顯示或打印語(yǔ)句，能顯示或打印每次選中進(jìn)程的進(jìn)程名以及運(yùn)行 一次后進(jìn)程隊(duì)列的變化。(8)為五個(gè)進(jìn)程任意確定一組“要求運(yùn)行時(shí)間”，啟動(dòng) 所設(shè)計(jì)的處理器調(diào)度程序，顯示或打印逐次被選中的進(jìn)程名以及進(jìn)程控制塊的動(dòng) 態(tài)變化過(guò)程。本程序主要是實(shí)現(xiàn)對(duì)時(shí)間片輪轉(zhuǎn)法調(diào)度算法的模擬，假定系統(tǒng)有五個(gè)進(jìn)程將五個(gè)進(jìn)程按順序拍成循環(huán)隊(duì)列，處理器按順序選擇進(jìn)程執(zhí)行，當(dāng)執(zhí)行后若沒(méi)有結(jié)束 則進(jìn)程的優(yōu)先級(jí)變?yōu)樽畹拖抡撗h(huán)時(shí)再運(yùn)行，若結(jié)束則退出隊(duì)列。程序先用void In itPCB(Proc &am

6、p;H) void In itPCB(Proc &H) void In itPCB(Proc &H) void In itPCB(Proc &H)函數(shù)從鍵盤輸入讀取進(jìn)程需要運(yùn)行的時(shí)間和初始化隊(duì)列及進(jìn)程控制塊PCB調(diào)用時(shí)間片輪轉(zhuǎn)函數(shù)void SJP_SimulatovoidSJP_Simulatovoid SJP_Simulatovoid SJP_Simulator(Proc r(Proc r(Proc r(Proc &H)&H)&H)&H) 模擬執(zhí)行時(shí)間片處理機(jī)對(duì)進(jìn)程的調(diào)度，然后調(diào)用 void Disp In fo(Proc H) voi

7、d Disp In fo(Proc H) void DispI nfo(Proc H)void DispI nfo(Proc H)函數(shù)輸出每次執(zhí)行的結(jié)果。進(jìn)程的數(shù)據(jù)結(jié)構(gòu)如下：typedef struct PNode struct PNode *n ext;char n ame10;int AII_Time;int Run time;char state;* Proc;int ProcNum;主函數(shù)main()調(diào)用各個(gè)子函數(shù)實(shí)現(xiàn)本程序的功能如：數(shù)據(jù)初始化InitPCB(H),輸出此刻的進(jìn)程狀態(tài)DispI nfo(H)，時(shí)間片輪轉(zhuǎn)法，SJP_Simulator(H)子函數(shù)的說(shuō)明如下：初始化就緒隊(duì)列

8、void InitPCB(Proc &H) cout<<"請(qǐng)輸入總進(jìn)程個(gè)數(shù)："；cin> >ProcNum;int Num=ProcNum;H=(Proc)malloc(sizeof(PNode);H-> next=NULL;Proc p=H;coutvv"總進(jìn)程個(gè)數(shù)為"vvProcNumvv"個(gè)，請(qǐng)依次輸入相應(yīng)信息nn"while(Num-) p=p->n ext=(Proc)malloc(sizeof(PNode);coutvv"進(jìn)程總運(yùn)行時(shí)間已運(yùn)行時(shí)間:"cin&g

9、t; >p->n ame>>p->AII_Time>>p->R un ed_Time;p->state='R'p-> next=NULL;p->n ext=H->n ext; /void DispI nfo(Proc H)Proc p=H->n ext;do if (p->state != 'E')cout«"進(jìn)程名:"<<p->name«"t 總運(yùn)行時(shí)間："vvp->AII_Time<&l

10、t;"t 已運(yùn)行時(shí)間:"<<p->Runed_Time<<"t 狀態(tài):"<<p->state<<endl;p=p->n ext;else p=p->n ext; while (p != H-> next);/時(shí)間片輪轉(zhuǎn)法VoidSJP_Simulator(Proc&H) cout«e ndlvv"STARTn"int flag=ProcNum;int roun d=0;Proc p=H->n ext;while (p->All_

11、Time > p->R un ed_Time)roun d+;cout«e ndl«"Ro und "vvround<<"-正在運(yùn)行"<<p->name<<<<"進(jìn)程"<<endl;p->R un ed_Time+;DispI nfo(H);if (p->All_Time = p->R un ed_Time) p->state='E'flag-;cout<<p->name«

12、;"進(jìn)程已運(yùn)行結(jié)束,進(jìn)程被刪除!n"p=p- >n ext;while(flag&&p->AII_Time=p->R un ed_Time)p=p->n ext;cout«endlvv"END -n"調(diào)試分析調(diào)試分析調(diào)試分析調(diào)試分析：本次試驗(yàn)主要是實(shí)現(xiàn)處理器按照時(shí)間片輪轉(zhuǎn)法實(shí)現(xiàn)調(diào)度，按照設(shè)計(jì)思想是在設(shè)定的時(shí)間片某一進(jìn) 程在時(shí)間片運(yùn)行，當(dāng)時(shí)間片到后，進(jìn)入下一個(gè)進(jìn)程再次按照時(shí)間片輪 轉(zhuǎn)法調(diào)度，就按照這個(gè)循環(huán)一直運(yùn)行下去，如果某一個(gè)進(jìn)程時(shí)間結(jié)束 就跳出隊(duì)列，跳向下一個(gè)進(jìn)程，直到所有的進(jìn)程都結(jié)束，本程序結(jié)束。 運(yùn)

13、行程序后，實(shí)現(xiàn)了上述所有的功能，雖然只是簡(jiǎn)單的實(shí)現(xiàn)，但是也 符合了本次課程設(shè)計(jì)的基本要求。在時(shí)間片上，進(jìn)程是按照這個(gè)實(shí)行調(diào)度的，直到所有進(jìn)程都結(jié)束了，那么本程序就結(jié)束.使用說(shuō)明使用說(shuō)明使用說(shuō)明使用說(shuō)明：程序中數(shù)據(jù)的輸入格式為：1）輸入進(jìn)程總數(shù)2）輸入各進(jìn)程信息3）進(jìn)程信息的輸入格式為：進(jìn)程名總運(yùn)行時(shí)間已運(yùn)行時(shí)間4）輸入結(jié)束回車運(yùn)行5）結(jié)果分析與實(shí)驗(yàn)體會(huì)結(jié)果分析與實(shí)驗(yàn)體會(huì)結(jié)果分析與實(shí)驗(yàn)體會(huì)結(jié) 果分析與實(shí)驗(yàn)體會(huì)6）時(shí)間片輪轉(zhuǎn)算法中，系統(tǒng)將所有的就緒程序按先來(lái)先服務(wù)的原則 排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把 CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一 個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，調(diào)度程序停止該進(jìn)程的執(zhí)行，并

14、將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的 隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。實(shí)驗(yàn)21、實(shí)驗(yàn)?zāi)康模簯?yīng)用銀行家算法驗(yàn)證進(jìn)程安全性檢查及分配資源。2、 實(shí)驗(yàn)容：編制模擬銀行家算法的程序，并以以下例子驗(yàn)證程序的 正確性。3、實(shí)驗(yàn)步驟：1）根據(jù)算法流程圖編制可執(zhí)行程序2）用以下兩個(gè)例子驗(yàn)證程序的正確性。3）按照上述兩個(gè)例子，輸出執(zhí)行的結(jié)果。#i nclude<iostream.h>#defi ne N 20#defi ne M 20int f（int aNM,i nt bNM,i nt m,i nt k） int j;for(j=0;j<m;j+)if(ak-1j

15、>bk-1j)return 0;return 1; int g(int aNM,int b,int m,int k)int j;for(j=0;j<m;j+)if(akj>bj)return 0;return 1;int h(int a,int n) for(i nt i=0;i <n ;i+)if(!ai)return 0;return 1;int p(int a,int bNM,int m,int k) int j；for(j=0;j<m;j+)if(aj>bk-1j)return 0;return 1; int q(i nt a,i nt b,i nt

16、 m) int j;for(j=0;j<m;j+)if(aj>bj)retur n 0;return 1;NeedNM,i ntintsafe(i ntFini shN,i ntWorkM,i ntAllocationNM,int n,int m) int i,j,k;int tN;for(i=0;i <n ;i+)ti=1；cout«"安全性檢查!"<<endl;for(i=0;i< n;)if(Fi nishi=0)&&g(Need,Work,m,i) k=i;ti=0;cout<v"p(&q

17、uot;vvk+1vv"):"vve ndl;cout<v"Work"v<mvv":"for(j=0;j<m;j+)cout<vWorkjvv"Workj=Workj+Allocati on ij;Fini shi=1;cout«e ndl; cout<v"Need"v<mvv":"for(j=0;j<m;j+)cout<<Needij<<""cout«e ndl;cout<

18、<"Allocatio n "vvmvv":"for(j=0;j<m;j+)cout«Allocatio n ij<<"cout«e ndl; cout«"(Work+Allocatio n)"<<m<<":" for(j=0;j<m;j+)cout<<Workj<<""cout«e ndl;cout«"Fi ni sh"v<k+1&

19、lt;v":"cout«Finishi<<""cout«e ndl;break;else i+;if(g(Need,Work,m,k)for(i=0;i <n ;i+)if(ti) if(g(Need,Work,m,i)coutvv"p("vvi+1vv"):"v<e ndl; cout<v"Work"v<mvv":"for(j=0;j<m;j+)cout<<Workj<<"&qu

20、ot;Workj=Workj+Allocati on ij;Fini shi=1;cout«e ndl;cout<v"Need"v<mvv":"for(j=0;j<m;j+)cout«Needijvv""cout«e ndl;cout«"Allocatio n "vvmvv":"for(j=0;j<m;j+)cout«Allocationij<<""cout«e ndl;cout&

21、lt;<"(Work+Allocatio n)"<<m<<":"for(j=0;j<m;j+)cout<<Workj<<""cout«e ndl;cout«"Fi ni sh"v<i+1<v":"cout«Fi ni shi<<""cout«e ndl;ti=0；else return 0;if(h(Fi nish, n)return 1;else re

22、turn 0;void r(intFi nishN,i ntWorkM,i nt AvailableM,i ntNeedNM,int AllocationNM,int MaxNM,int n,int m)int RequestM; char b; int i,j,k;cout<<"n 要申請(qǐng)資源，請(qǐng)按'y'或'Y',否則按'n'或'N'"<<e ndl;cin> >b;if(b!='y'&&b!=' Y')if(safe(Fi

23、nish,Work,Need,Allocatio n,n ,m)cout«"此時(shí)刻系統(tǒng)安全!n"else coutvv" 此時(shí)刻系統(tǒng)不安全!n" else cout<<"n請(qǐng)輸入申請(qǐng)資源的進(jìn)程編號(hào)(1,2,"<< n<<"):"<<e ndl;cin> >k;while(k >n)cout«"您輸入了錯(cuò)誤的進(jìn)程號(hào),請(qǐng)核查后重新輸入:"<<endl;cin> >k;cout<<

24、"n請(qǐng)輸入進(jìn)程p("<<k<<")申請(qǐng)各類資源的數(shù)量:"<<e ndl;for(j=0; j<m;j+)cin> >Requestj;if(p(Request,Need,m,k) if(q(Request,Available,m) fo5rqAmj+) 宀 Ava=ab-eullAva=ab-e 曰Requess八 A=ocafion?二 uHA-ocafion?二曰+Requess八 Need?1NHNeed?1¥Requess- wokullAva=ab_esOO&AA-宜

25、74;礙=AAend-八 couxA-wKr 迪溢3選*Avai-ab-eAAmAATAcend-八for5r0_Amj+)宀couxAAVai-ab-eljAA JcouxAendrfor (i=0; i<n; i+)for(j=0;jvm;j+) cout«Allocati on ij<<""cout«e ndl;cout<<"n最大需求矩陣 Max"<<n<v"vvm<v": "<<endl;for (i=0; i<n; i+)

26、for(j=0;j<m;j+)cout«Maxijvv""cout«e ndl;cout<<"n 需求矩陣Need"v <n <<""<<m<<": "<<e ndl;for (i=0; i<n; i+)for(j=0;jvm;j+) cout«Needijvv""cout«e ndl;if(safe(Fi nish,Work,Need,Allocatio n,n ,m)cout

27、vv"系統(tǒng)處于安全狀態(tài)!"elsecout<<"n當(dāng)前狀態(tài)不安全!"for (j=0; j<m; j+)Availablej=Availablej+Requestj;Allocatio nk-1j=Allocatio nk-1j-Requestj;Needk-1j=Needk-1j+Requestj;Workj=Availablej;for(i=0; i<n; i+)Fi nishi=0;coutvv"各種資源可利用的數(shù)量Available"vvmvv":"<<e ndl;for

28、(j=0;jvm;j+) cout<<Availablej<<""cout«e ndl;cout<<"n已分配資源Allocatio n "<<m<<": "<<e ndl;for (i=0; i<n; i+)for(j=0;j<m;j+)cout«Allocatio nij<<""cout«e ndl;cout<<"n最大需求矩陣 Max"<<n

29、<v"vvm<v": "<<endl;for (i=0; i<n; i+)for(j=0;j<m;j+)cout«Maxijvv""cout«e ndl;cout<<"n需求矩陣 Need"<< n< v"vvm<v": "<<e ndl;for (i=0; i<n; i+)for(j=0;jvm;j+) cout«Need曲<<""cout&#

30、171;e ndl;coutvv"系統(tǒng)無(wú)足夠的資源滿足進(jìn)程p"vvkvv"的申 請(qǐng),p"vvkvv"必須等待!"<<endl;else coutvv"出錯(cuò)，進(jìn)程所需要的資源數(shù)目已超過(guò)它所宣布的最大值!"<<e ndl;Void mai n()coutvv""<<e ndl;coutvv" 模擬銀行家算法"vve ndl;coutvv""vve ndl;coutvv" 江 之 風(fēng) 海 之 韻"vve n

31、dl;coutvv"QuQu-"<<e ndl;cout«""<<e ndl;int AvailableM; int MaxNM;int Allocati on NM;int NeedNM; int WorkM;int Fi nishN;int i,j,n ,m;cout«"輸入進(jìn)程的數(shù)量："；cin>>m;"<<e ndl;cin>>n;cout«"輸入資源種類數(shù)："coutvv"輸入各種資源可利用的數(shù)量Available"vvmvv": for (j=0; j<m; j+)cin> >Availablej;Workj=Availablej;初始化 Wo