時(shí)間片輪轉(zhuǎn)進(jìn)程調(diào)度模擬算法的實(shí)現(xiàn)

1、武漢理工大學(xué)華夏學(xué)院課程設(shè)計(jì)報(bào)告書課程名稱： 操作系統(tǒng)原理 題 目：時(shí)間片輪轉(zhuǎn)進(jìn)程調(diào)度模擬算法的實(shí)現(xiàn) 系 名： 信息工程系 專業(yè)班級： 計(jì)算機(jī)1132班 姓 名： 李杰 學(xué) 號： 10210413209 指導(dǎo)教師: 司曉梅 2015年 6 月 26日武漢理工大學(xué)華夏學(xué)院信息工程系課 程 設(shè) 計(jì) 任 務(wù) 書課程名稱： 操作系統(tǒng)原理課程設(shè)計(jì) 指導(dǎo)教師： 司曉梅 班級名稱：計(jì)算機(jī)1131-2 開課系、教研室： 自動(dòng)化與計(jì)算機(jī) 一、課程設(shè)計(jì)目的與任務(wù)操作系統(tǒng)課程設(shè)計(jì)是操作系統(tǒng)原理課程的后續(xù)實(shí)踐課程，旨在通過一周的實(shí)踐訓(xùn)練，加深學(xué)生對理論課程中操作系統(tǒng)概念，原理和方法的理解，加強(qiáng)學(xué)生綜合運(yùn)用操作系統(tǒng)原理

2、、Linux系統(tǒng)、C語言程序設(shè)計(jì)技術(shù)進(jìn)行實(shí)際問題處理的能力，進(jìn)一步提高學(xué)生進(jìn)行分析問題和解決問題的能力，包含系統(tǒng)分析、系統(tǒng)設(shè)計(jì)、系統(tǒng)實(shí)現(xiàn)和系統(tǒng)測試的能力。學(xué)生將在指導(dǎo)老師的指導(dǎo)下，完成從需求分析，系統(tǒng)設(shè)計(jì)，編碼到測試的全過程。二、課程設(shè)計(jì)的內(nèi)容與基本要求1、課程設(shè)計(jì)題目 時(shí)間片輪轉(zhuǎn)進(jìn)程調(diào)度模擬算法的實(shí)現(xiàn)2、課程設(shè)計(jì)內(nèi)容用c/c+語言實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)的進(jìn)程調(diào)度模擬算法。要求：1 至少要有5個(gè)以上進(jìn)程2 進(jìn)程被調(diào)度占有CPU后，打印出該進(jìn)程正在運(yùn)行的相關(guān)信息提示:時(shí)間片輪轉(zhuǎn)調(diào)度算法中，進(jìn)程調(diào)度程序總是選擇就緒隊(duì)列中的第一個(gè)進(jìn)程，也就是說按照先來先服務(wù)原則調(diào)度，但一旦進(jìn)程占用處理機(jī)則僅使用一個(gè)時(shí)間片。

3、在使用完一個(gè)時(shí)間片后，進(jìn)程還沒有完成其運(yùn)行，它必須釋放出處理機(jī)給下一個(gè)就緒的進(jìn)程，而被搶占的進(jìn)程返回到就緒隊(duì)列的末尾重新排隊(duì)等待再次運(yùn)行。1）進(jìn)程運(yùn)行時(shí)，只打印出相關(guān)提示信息，同時(shí)將它已經(jīng)運(yùn)行的時(shí)間片加1就可以了。2）為進(jìn)程設(shè)計(jì)出PCB結(jié)構(gòu)。PCB結(jié)構(gòu)所包含的內(nèi)容，有進(jìn)程名、進(jìn)程所需運(yùn)行時(shí)間、已運(yùn)行時(shí)間和進(jìn)程的狀態(tài)以及指針的信息等。 3、設(shè)計(jì)報(bào)告撰寫格式要求：1設(shè)計(jì)題目與要求 2 設(shè)計(jì)思想 3系統(tǒng)結(jié)構(gòu) 4 數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖 5 使用說明書（即用戶手冊）：內(nèi)容包含如何登錄、退出、讀、寫等操作說明6 運(yùn)行結(jié)果和結(jié)果分析（其中包括實(shí)驗(yàn)的檢查結(jié)果、程序的運(yùn)行情況）7 自我評價(jià)與總結(jié) 8

4、 附錄：程序清單，注意加注釋（包括關(guān)鍵字、方法、變量等），在每個(gè)模塊前加注釋；三、課程設(shè)計(jì)步驟及時(shí)間進(jìn)度和場地安排本課程設(shè)計(jì)將安排在第17周, 現(xiàn)代教育技術(shù)中心。具體安排如下：時(shí)間設(shè)計(jì)內(nèi)容第一天下發(fā)任務(wù)書，學(xué)生查閱資料第二天系統(tǒng)設(shè)計(jì)和原型開發(fā)第三天-第四天系統(tǒng)功能實(shí)現(xiàn)第五天系統(tǒng)調(diào)試、測試、打包和驗(yàn)收課程設(shè)計(jì)集中時(shí)間安排：周次星期一星期二星期三星期四星期五第17周第2-3節(jié)第2-3節(jié)第2-3節(jié)第2-3節(jié)第3-6節(jié)地點(diǎn)現(xiàn)教現(xiàn)教現(xiàn)教現(xiàn)教現(xiàn)教四、課程設(shè)計(jì)考核及評分標(biāo)準(zhǔn)課程設(shè)計(jì)考核將綜合考慮學(xué)生的系統(tǒng)設(shè)計(jì)方案、運(yùn)行結(jié)果、課程設(shè)計(jì)報(bào)告書的質(zhì)量、態(tài)度、考勤、答辯情況等各因素。具體評分標(biāo)準(zhǔn)如下：（1）設(shè)計(jì)方案

5、正確，具有可行性、創(chuàng)新性； 30分（2）系統(tǒng)開發(fā)效果較好； 20分（3）設(shè)計(jì)報(bào)告規(guī)范、課程設(shè)計(jì)報(bào)告質(zhì)量高、參考文獻(xiàn)充分 20分（4）課程設(shè)計(jì)答辯時(shí)，問題回答正確； 20分（5）態(tài)度認(rèn)真、刻苦鉆研、遵守紀(jì)律； 10分 按上述五項(xiàng)分別記分后求和，總分按五級制記載最后成績。優(yōu)秀（10090分），良好（8089分），中等（7079分），及格（6069分），不及格（059分）一、 設(shè)計(jì)題目與要求：進(jìn)程時(shí)間片輪轉(zhuǎn)調(diào)度算法。要求：用C+語言編寫程序完成單處理機(jī)的進(jìn)程調(diào)度，要求采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。實(shí)驗(yàn)具體要求包括：首先確定作業(yè)控制塊的內(nèi)容和組成方式；然后完成作業(yè)調(diào)度；最后編寫主函數(shù)，并對所做工作進(jìn)行測試。

6、二、 設(shè)計(jì)思想：在多道程序系統(tǒng)中，一個(gè)作業(yè)被提交后必須經(jīng)過處理機(jī)調(diào)度后，方能獲得處理機(jī)執(zhí)行。對調(diào)度的處理又都可采用不同的調(diào)度方式和調(diào)度算法。調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。三、 系統(tǒng)結(jié)構(gòu)處理機(jī)管理模擬系統(tǒng)由創(chuàng)建進(jìn)程、運(yùn)行程序和顯示結(jié)果三部分組成。而它們又分別包括輸入進(jìn)程信息、創(chuàng)建結(jié)點(diǎn)和插入結(jié)點(diǎn)三個(gè)步驟。系統(tǒng)功能說明：創(chuàng)建進(jìn)程模塊在輸入進(jìn)程頁面輸入要?jiǎng)?chuàng)建的進(jìn)程數(shù)，輸入后逐個(gè)將進(jìn)程信息錄入插入到就緒隊(duì)列中，完成進(jìn)程的創(chuàng)建過程。運(yùn)行程序模塊：此模塊實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)調(diào)度算法，從就緒隊(duì)列中取出進(jìn)程結(jié)點(diǎn)，并模擬運(yùn)行該進(jìn)程，反復(fù)循環(huán)，直至進(jìn)程全部運(yùn)行結(jié)束。每次運(yùn)行進(jìn)程后，將運(yùn)行信息存

7、入到文件中，實(shí)現(xiàn)信息的持久化。方便信息的記錄，系統(tǒng)功能的分析和出錯(cuò)時(shí)便于檢查錯(cuò)誤?，F(xiàn)實(shí)結(jié)果模塊：從文件讀入進(jìn)程運(yùn)行的結(jié)果，在圖形界面下操作，提供友好的用戶操作方式，方便直觀了解進(jìn)程呢過的調(diào)度過程，便于數(shù)據(jù)的分析和研究。算法描述：1、在創(chuàng)建進(jìn)程界面將進(jìn)程信息錄入，將進(jìn)程控制塊進(jìn)行包裝，插入到循環(huán)隊(duì)列中；2、當(dāng)運(yùn)行程序時(shí)，每次從就緒隊(duì)列隊(duì)首取出一個(gè)進(jìn)程，判斷是P進(jìn)程是否到達(dá)。到達(dá)則運(yùn)行該進(jìn)程；3、若P進(jìn)程為首次運(yùn)行，則記錄進(jìn)程開始運(yùn)行時(shí)間；4、運(yùn)行完P(guān)進(jìn)程后，輸入進(jìn)程運(yùn)行信息，并將此進(jìn)程移動(dòng)至隊(duì)尾；5、若循環(huán)隊(duì)列長度大于1，則返回執(zhí)行B，否則結(jié)束程序。四、數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖 type

8、def struct jcb char nameN; int prio; int round; int cputime; int needtime; int count; char state; struct node *next; PCB圖1流程圖五、使用說明（1） 建立一個(gè)進(jìn)程控制塊PCB來代表。PCB包括：進(jìn)程名、鏈接指針、到達(dá)時(shí) 間、估計(jì)運(yùn)行時(shí)間、剩余時(shí)間和進(jìn)程狀態(tài)。進(jìn)程狀態(tài)分為就緒（W）、運(yùn)行（R）和完成（F）。（2） 為每個(gè)進(jìn)程任意確定一個(gè)要求運(yùn)行時(shí)間和到達(dá)時(shí)間。（3） 按照進(jìn)程到達(dá)的先后順序排成一個(gè)循環(huán)隊(duì)列。再設(shè)一個(gè)對首指針指向第一個(gè)到達(dá)進(jìn)程的首址。（4） 執(zhí)行處理機(jī)調(diào)度時(shí)，開始

9、選擇對首的第一個(gè)進(jìn)程運(yùn)行。另外再設(shè)一個(gè)當(dāng)前 運(yùn)行進(jìn)程的指針，指向當(dāng)前正運(yùn)行的進(jìn)程。（5） 執(zhí)行：a)預(yù)計(jì)運(yùn)行時(shí)間減1；b)輸出當(dāng)前運(yùn)行進(jìn)程的名字。（6） 進(jìn)程執(zhí)行一次后，若該進(jìn)程的剩余運(yùn)行時(shí)間為零，則將該進(jìn)程的狀態(tài)置為完成態(tài)F，并退出循環(huán)隊(duì)列；若不為空，則將其移至隊(duì)尾。繼續(xù)在運(yùn)行隊(duì)首的進(jìn)程。（7） 若就緒隊(duì)列不空，則重復(fù)上述的（5）和（6）步驟直到所有進(jìn)程都運(yùn)行完為止。在所設(shè)計(jì)的調(diào)度程序中，要求包含顯示或打印語句。以便顯示或打印每次選操作系統(tǒng)課程設(shè)計(jì)中進(jìn)程的名稱及運(yùn)行一次后隊(duì)列的變化情況。六、運(yùn)行結(jié)果1、輸入數(shù)據(jù)圖2 輸入數(shù)據(jù)2、運(yùn)行結(jié)果示例（1）數(shù)據(jù)輸入完成后的初始狀態(tài)，進(jìn)程標(biāo)識為 x1的進(jìn)

10、程首先得到調(diào)度，運(yùn)行10個(gè)時(shí)間單位。圖3運(yùn)行結(jié)果1（2）進(jìn)程標(biāo)識為x2的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。圖4運(yùn)行結(jié)果2（3）進(jìn)程標(biāo)識為x3的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。圖5運(yùn)行結(jié)果3（4）進(jìn)程標(biāo)識為x4的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。圖6運(yùn)行結(jié)果4(5)進(jìn)程標(biāo)識為x5的進(jìn)程得到調(diào)度，從就緒態(tài)“W” 改為運(yùn)行態(tài) “R”，運(yùn)行10個(gè)時(shí)間單位。圖7運(yùn)行結(jié)果5（6）進(jìn)程標(biāo)識為x1的進(jìn)程再次得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，因進(jìn)程x1只剩下5個(gè)單位時(shí)間，所以進(jìn)程 x1只運(yùn)行5個(gè)單位時(shí)間。圖

11、8運(yùn)行結(jié)果6（7）進(jìn)程標(biāo)識為x2的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。進(jìn)程x1已運(yùn)行完，從運(yùn)行態(tài)“R”改為運(yùn)行結(jié)束狀態(tài)“F”。圖9運(yùn)行結(jié)果7（8）進(jìn)程標(biāo)識為x3的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。圖10運(yùn)行結(jié)果8（9）進(jìn)程標(biāo)識為x4的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。圖11運(yùn)行結(jié)果9（10）進(jìn)程標(biāo)識為x5的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。圖12運(yùn)行結(jié)果10（11）進(jìn)程標(biāo)識為x2的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行5個(gè)時(shí)間單位。進(jìn)程x5已運(yùn)行完，從運(yùn)行態(tài)

12、“R”改為運(yùn)行結(jié)束狀態(tài)“F”。圖13運(yùn)行結(jié)果11(12）進(jìn)程標(biāo)識為x3的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。進(jìn)程x2已運(yùn)行完，從運(yùn)行態(tài)“R”改為運(yùn)行結(jié)束狀態(tài)“F”。圖14運(yùn)行結(jié)果12(13）進(jìn)程標(biāo)識為x4的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行10個(gè)時(shí)間單位。圖15運(yùn)行結(jié)果13 (14）進(jìn)程標(biāo)識為x3的進(jìn)程得到調(diào)度，從就緒態(tài)“W”改為運(yùn)行態(tài)“R”，運(yùn)行5個(gè)時(shí)間單位。進(jìn)程x4已運(yùn)行完，從運(yùn)行態(tài)“R”改為運(yùn)行結(jié)束狀態(tài)“F”。圖16運(yùn)行結(jié)果14（15）所有進(jìn)程都已運(yùn)行完，狀態(tài)都為“F”。圖17運(yùn)行結(jié)果15七、小結(jié)在這次實(shí)驗(yàn)中,我能夠正確分析實(shí)驗(yàn)過程和實(shí)驗(yàn)結(jié)果

13、，思路清晰，能夠比較好的理解進(jìn)程按時(shí)間片輪轉(zhuǎn)算法這一調(diào)度過程，加深了我對進(jìn)程時(shí)間片輪轉(zhuǎn)調(diào)度過程的理解。但是還有很多不足。我自己的C+基礎(chǔ)差，不能夠自己編寫這一調(diào)度算法的程序，只能通過網(wǎng)絡(luò)和同學(xué)、老師的幫忙得到正確的程序編碼；另外一開始輸入進(jìn)程運(yùn)行需要的時(shí)間時(shí)，由于輸入運(yùn)行時(shí)間的數(shù)值較大，導(dǎo)致后面進(jìn)程繁多，但后來及時(shí)改正，走了彎路，也增加了理解。因此以后要加強(qiáng)自己在C+方面的學(xué)習(xí)，能夠理解源程序；并且要多上機(jī)操作，多調(diào)試多嘗試，爭取能理解好了解透。本次實(shí)驗(yàn)題需要詳細(xì)閱讀題目和不斷地嘗試才能找到簡便的過程，能加強(qiáng)學(xué)生的上機(jī)操作能力。八、參考源程序#include <stdio.h>#i

14、nclude <stdlib.h>#include <string.h>#include <iostream.h>typedef struct node char name10; int prio; int round; int cputime; int needtime; int count; char state; struct node *next; PCB;PCB *finish,*ready,*tail,*run; /隊(duì)列指針int N; /進(jìn)程數(shù)void firstin() run=ready; /就緒隊(duì)列頭指針賦值給運(yùn)行頭指針 run->

15、state='R' /進(jìn)程狀態(tài)變?yōu)檫\(yùn)行態(tài) ready=ready->next; /就緒隊(duì)列頭指針后移到下一進(jìn)程/輸出標(biāo)題函數(shù)void prt1(char a) if(toupper(a)='P') /優(yōu)先級法 cout<<" "<<endl; cout<<"進(jìn)程名 占用CPU時(shí)間 到完成還要的時(shí)間 輪轉(zhuǎn)時(shí)間片 狀態(tài)"<<endl;/進(jìn)程PCB輸出void prt2(char a,PCB *q) if(toupper(a)='P') /優(yōu)先級法的輸出 co

16、ut<<q->name<<" "<<q->cputime<<" "<<q->needtime<<" "<< q->round<<" "<<q->state<<endl;/輸出函數(shù)void prt(char algo) PCB *p; prt1(algo); /輸出標(biāo)題 if(run!=NULL) /如果運(yùn)行指針不空 prt2(algo,run); /輸出當(dāng)前正在運(yùn)行的

17、PCB p=ready; /輸出就緒隊(duì)列PCB while(p!=NULL) prt2(algo,p); p=p->next; p=finish; /輸出完成隊(duì)列的PCB while(p!=NULL) prt2(algo,p); p=p->next; getchar(); /按住任意鍵繼續(xù)/時(shí)間片輪轉(zhuǎn)的插入算法void insert(PCB *q) PCB *p1,*s,*r; s=q; /待插入的PCB指針 p1=ready; /就緒隊(duì)列頭指針 r=p1; /*r做pl的前驅(qū)指針 while(p1!=NULL) if(p1->round<=s->round) r

18、=p1; p1=p1->next; if(r!=p1) r->next=s; s->next=p1; else s->next=p1; /否則插入在就緒隊(duì)列的頭 ready=s; /優(yōu)先級創(chuàng)建初void create(char alg) PCB *p; int i,time; char na10; ready=NULL; finish=NULL; run=NULL; cout<<"輸入進(jìn)程名及其需要運(yùn)行的時(shí)間："<<endl; for(i=1;i<=N;i+) p=new PCB; cin>>na; cin>>time; strcpy(p->name,na); p->cputime=0; p->needtime=time; p->state='W' p->round=0; if(ready!=NULL) insert(p); else p->next=ready; ready=p; cout<<"輸入進(jìn)程名及其需