操作系統(tǒng)時間片輪轉(zhuǎn)法進程CPU調(diào)度

1、東莞理工學(xué)院操作系統(tǒng)課程設(shè)計報告學(xué) 院： 計算機學(xué)院 專 業(yè) 班 級： 軟件工程(2)班 學(xué)號姓名評價201241404235蔡煥倫201241404202陳李冠201241404227劉卓銘組 成 員：提交時間： 2014年1月11日 指導(dǎo)教師評閱意見：.項目名稱：設(shè)計一個按時間片輪轉(zhuǎn)法進程CPU調(diào)度的程序一、 設(shè)計目的 操作系統(tǒng)課程設(shè)計是計算機專業(yè)重要的課程，它為學(xué)生提供了一個既動手又動腦，將課本上的理論知識和實際游記結(jié)合起來，獨立分析和解決實際問題的機會。處理機調(diào)度是操作系統(tǒng)中非常重要的部分。為深入理解進程管理部分的功能，設(shè)計調(diào)度算法，模擬實現(xiàn)處理機的調(diào)度。本課程設(shè)計是用時間片輪轉(zhuǎn)算法模

2、擬單處理機調(diào)度。（1）進一步鞏固和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識。（2）培養(yǎng)結(jié)構(gòu)化程序、模塊話程序的方法和能力。（3）提高學(xué)生調(diào)試程序的技巧和軟件設(shè)計的能力。（4）提高學(xué)生分析問題、解決問題以及綜合利用編程語言進行程序設(shè)計的能力。二、環(huán)境條件Windows系統(tǒng)、VMware Workstation、Ubuntu三、設(shè)計內(nèi)容1. 項目背景操作系統(tǒng)（OS）是計算機系統(tǒng)的重要組成部分，是一個重要的系統(tǒng)軟件，它負(fù)責(zé)管理計算機系統(tǒng)的硬、軟件資源和整個計算機的工作流程，協(xié)調(diào)系統(tǒng)部件之間,系統(tǒng)與用戶之間、用戶與用戶之間的關(guān)系。隨著操作系統(tǒng)的新技術(shù)的不斷出現(xiàn)功能不斷增加。操作系統(tǒng)作為一個標(biāo)準(zhǔn)的套裝軟件必須滿足盡可能多

3、用戶的需要，于是系統(tǒng)不斷膨脹，功能不斷增加，并逐漸形成從開發(fā)工具到系統(tǒng)工具再到應(yīng)用軟件的一個平臺環(huán)境。更能滿足用戶的需求。隨著計算機技術(shù)的不斷發(fā)展，人們對于計算機系統(tǒng)性能的要求也越來越高，對于操作系統(tǒng)所使用的算法也在不斷地發(fā)展。OS對調(diào)度分配實質(zhì)是一種資源分配，因而調(diào)度算法要根據(jù)不同的系統(tǒng)資源分配策略所規(guī)定的來分配算法。對于不同的系統(tǒng)目標(biāo)，又必須采用不同的調(diào)度算法。有的算法適合長作業(yè)，有的適合短作業(yè)，有的適合作業(yè)調(diào)度，有的適合進程調(diào)度。操作系統(tǒng)對于各個方面的要求都不得不提到效率的問題，計算機系統(tǒng)的處理機調(diào)度便變得尤為重要。處理機調(diào)度的效率甚至可能成為提高計算機處理速度的瓶頸。處理機調(diào)度就是對系

4、統(tǒng)的資源做出合理的分配，因而，提高處理機的調(diào)度算法也變得尤為重要。2.內(nèi)容設(shè)計一個按時間片輪轉(zhuǎn)法進程CPU調(diào)度的程序。（1）假設(shè)系統(tǒng)有5個進程，每個進程用一個進程控制塊PCB來代表，PCB中包含進程名、鏈接指針、到達時間、估計運行時間、進程狀態(tài)表。其中，進程名即為進程進標(biāo)識。（2）為每一個進程設(shè)計一個要示運行時間和到達時間。（3）按照進程到達的先后順序排成一個循環(huán)隊列，再設(shè)一個隊首指針指向第一個到達的進程首址。（4）執(zhí)行處理機調(diào)度時，開始選擇隊首的第一個進程運行。另外再設(shè)一個當(dāng)前運行進程指針，指向當(dāng)前正運行的進程。（5）由于本實驗是模擬實驗，所以對被選中進程并不實際啟運運行，只是執(zhí)行：a.估計

5、運行時間減1b.輸出當(dāng)前運行進程的名字。用這兩個操作來模擬進程的一次運行。（6）進程運行一次后，以后的調(diào)度則將當(dāng)前指針依次下移一個位置，指向下一個進程，即調(diào)整當(dāng)前運行指針指向該進程的鏈接指針?biāo)高M程，以指示應(yīng)運行進程。同時還尖判斷該進程的剩八運行時間是否為零。若不為零，則等待下一輪的運行；若該進程的剩余運行時間為零，則將該進程的狀態(tài)置為完成態(tài)C，并退出循環(huán)隊列。（7）若就緒 隊列不空，則重復(fù)上述的（5）和（6）步，直到所有進程都運行完為止。（8）在所設(shè)計的調(diào)度程序中，應(yīng)包含顯示或打印語句，以便顯示或打印每次選中進程的名稱及運行一次后隊列的變化情況。四、人員分工學(xué)號姓名工作20124140423

6、5蔡煥倫設(shè)計調(diào)度算法函數(shù)201241404202陳李冠設(shè)計數(shù)據(jù)結(jié)構(gòu)及調(diào)試代碼201241404227劉卓銘設(shè)計創(chuàng)建進程函數(shù)五、設(shè)計過程1.設(shè)計原理RR調(diào)度算法滿足不同類型作業(yè)的需求，較好實現(xiàn)公平性與資源利用率之間的平衡。對交互型作業(yè)，由于通常較短，這些作業(yè)在第一隊列規(guī)定的時間片內(nèi)完成，可使用戶感到滿意；對短批作業(yè)，開始時在第一隊列中執(zhí)行一個時間片就可完成，便可與交互型作業(yè)一樣獲得快速晌應(yīng)，否則通常也僅需在第二、第三隊列中各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍較短；對長批作業(yè)，它們依次在第一至第n個隊列中輪番執(zhí)行，不必?fù)?dān)心長時間得不到處理2.進程切換時機在RR調(diào)度算法中，應(yīng)在何時進行進程的切換，

7、可分為兩種情況：若一個時間片尚未用完，正在運行的而進程便已經(jīng)完成，就立即激活調(diào)度程序，將它從就緒隊列中刪除，再調(diào)度就緒隊列中隊首的進程運行，并啟動一個新的時間片。在一個時間片用完時，計時器中斷處理程序被激活。如果進程尚未運行完畢，調(diào)度程序就把它送往就緒隊列的末尾。例如 設(shè)四個進程A、B、C和D依次進入就緒隊列（同時到達），四個進程分別需要運行12、5、3和6個時間單位。 圖示RR法時間片q=1和q=4示進程運行情況 算出各進程的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間3.流程圖NNYNYY退 出輸入進程數(shù)輸入進程進程是否輸入完輸入時間片分配給執(zhí)行隊列隊首時間片時間片-1時間片+1時間片是否用完是否所有進程都完成

8、將未完成的插入隊尾NY結(jié) 束將新到進程插入隊尾是否完成服務(wù)時間-1Y開 始是否有新進程到達N3.數(shù)據(jù)結(jié)構(gòu)采用單鏈表的數(shù)據(jù)結(jié)構(gòu)：typedef structchar name10;/進程名int arrtime;/到達時間int worktime;/運行時間DataType;typedef struct nodeDataType data;struct node *next;ListNode;進程名：name，鏈指針：next，到達時間：arrtime，運行時間：worktime。4.算法的設(shè)計（1）創(chuàng)建進程；使用單鏈表的方法，單鏈表中的每個結(jié)點相當(dāng)于一個進程。（2）自定義所需進程數(shù)目int f

9、lag;cinflag。（3）創(chuàng)建一個進程單鏈表，作為進程隊列，LinkList head;p=(ListNode*)malloc(sizeof(ListNode);head=p;p-next=NULL;在進程數(shù)目之內(nèi)，手動輸入進程，p=(ListNode*)malloc(sizeof(ListNode); ; cinp-data.arrtime; cinp-data.worktime。每輸入一個進程都插進進程隊列，并按arrtime從小到大排序。（4）自定義時間片大小，int RR;cinRR。（5）創(chuàng)建執(zhí)行隊列，LinkList H;ListNode *rear

10、;p=(ListNode*)malloc(sizeof(ListNode); p=NULL; H=p。并且定義一個參考變量flag2!=flag。（6）定義時間軸，初始化時間軸和執(zhí)行隊列。H=head-next; head-next=head-next-next; rear=H; rear-next=NULL;time=H-data.arrtime;rr=RR。（7）當(dāng)flag2!=0時，分配給執(zhí)行隊列隊首一個時間片rr。（8）當(dāng)rr!=0時;rr=rr-1; time=time+1。進程隊列的隊首進程是否到達，若到達，將其插入到執(zhí)行隊列的隊尾。rear-next=head-next; hea

11、d-next=head-next-next; rear=rear-next;rear-next=NULL。執(zhí)行隊列不為空時，執(zhí)行隊列的隊首進程的worktime=worktime-1，判斷是否執(zhí)行完。執(zhí)行完，flag2=flag2-1，該進程退出執(zhí)行隊列。（9）執(zhí)行隊列隊首是否得到過一個完整的時間片，若有則該進程插入到執(zhí)行隊列的隊尾。q=H; H=H-next; rear-next=q; rear=rear-next; rear-next=NULL。（10）執(zhí)行隊列不為空時，轉(zhuǎn)到第（7）步。當(dāng)執(zhí)行隊列和進程隊列都為空時，轉(zhuǎn)到第（6）步。當(dāng)兩隊列都為空時，所有進程運行完，模擬結(jié)束。六、運行結(jié)果七

12、、結(jié)果分析時間片：RR = 3進程名到達時間服務(wù)時間完成時間周轉(zhuǎn)時間a0477b371815c581914首先，將進程a,b,c依次輸入PCB并輸出他們的信息，如圖。定義時間片大小為3，按回車鍵，進程按照到達時間從小到大排序，即先運行進程a，修改其狀態(tài)。進程a運行1次后，剩余時間不為0，則將其調(diào)至隊尾。CPU開始運行隊首的進程b，運行1次后，進程b的剩余時間不為，則將其調(diào)至隊尾。CPU開始運行隊首的進程c，運行1次后，進程c的剩余時間不為0，則將其調(diào)至隊尾。CPU繼續(xù)運行隊首的進程a, 運行1次后，剩余時間為0，則將其狀態(tài)修改為C并從隊列中刪除。CPU繼續(xù)運行隊首的進程c，運行1次后，剩余時間

13、不為0，則將其調(diào)至隊尾。CPU繼續(xù)運行隊首的進程b，運行1次后，剩余時間為0，則將其狀態(tài)修改為C并從隊列中刪除。CPU繼續(xù)運行僅剩下的進程c，運行1次后，剩余時間為0，將其狀態(tài)修改為C并從隊列中刪除。此時隊列為空，執(zhí)行結(jié)束。八、設(shè)計總結(jié)1.總結(jié)通過這次的課程設(shè)計，我對進程調(diào)度算法，特別對輪轉(zhuǎn)調(diào)度算法有了更深的認(rèn)識。在學(xué)期初剛接觸操作系統(tǒng)這門課程時，其實是覺得比較難找到切入點的，更不用談里面的各種各樣的算法。不過后來經(jīng)過了思考，查看各類資料，摸清調(diào)度算法的各項步驟，其實自己都可以用一句話把算法概況。這次課程設(shè)計的語言我們小組采用了C+。此門語言畢竟是大一下學(xué)期學(xué)的，離現(xiàn)在都有些時間了，所以重新用

14、起來會稍顯吃力，不過憑著啃硬骨頭的精神，還有以前遺留下來的編程基礎(chǔ)，通過查閱教科書還是沒有任何問題的。學(xué)如逆水行舟，不進則退。課程設(shè)計是一次讓我重新檢查自己所學(xué)過的知識是否還熟練，是否有所缺漏的機會，并且只要通過自己動手去排除各種困難，最后自己還是獲益匪淺的。2.參考文獻1.李善平，季江民，尹康凱操作系統(tǒng)課程設(shè)計浙江大學(xué)出版社，20092.湯小丹.計算機操作系統(tǒng)（第四版）.西安：西安電子科技大學(xué)出版社 附錄：各程序主要函數(shù)及注釋（用紅色黑體標(biāo)注自己設(shè)計的函數(shù)）#include #include #include typedef structchar name10;int arrtime;int

15、 worktime;DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList head;void create_insert_LinkList(int flag1)/創(chuàng)建進程隊列ListNode *p,*p1,*p2;p=(ListNode*)malloc(sizeof(ListNode);head=p;p-next=NULL;while(flag10)p=(ListNode*)malloc(sizeof(ListNode);/新建結(jié)點cout

16、; coutp-data.arrtime; coutp-data.worktime; cout*next=NULL; p1=head;p2=p1-next;while(p2!=NULL&p2-data.arrtimedata.arrtime)/對新建結(jié)點排序（按arrtime從大到小）p1=p2;p2=p2-next;p1-next=p;p-next=p2;flag1=flag1-1;void pcb_LinkList(int flag2)/進行CPU調(diào)度 LinkList H;ListNode *rear,*p,*q;int RR,rr,time,m,n;p=(List

17、Node*)malloc(sizeof(ListNode);p=NULL;H=p;/創(chuàng)建執(zhí)行隊列coutRR; cout*next; head-next=head-next-next;rear=H; rear-next=NULL;time=H-data.arrtime;while(flag2!=0)n=0; while(rr!=0) rr=rr-1; time=time+1; if(head-next!=NULL)if(head-next-data.arrtimenext; head-next=head-next-next; rear=H; rear-next=NULL;elserear-ne

18、xt=head-next; head-next=head-next-next; rear=rear-next; rear-next=NULL; if(H!=NULL) H-data.worktime=H-data.worktime-1; m=1;/該進程有被執(zhí)行 n=n+1;/該進程（隊首）在這時間片中所有時間 if(H-data.worktime=0)/該進程服務(wù)完，從執(zhí)行隊列中刪除 cout在第time-nsendl; cout進程 運行ns 狀態(tài)：C 完成時間：timeendl;coutnext;flag2=flag2-1;m=0;/新的隊首未被執(zhí)行； n=0; if(m=1)cout在第time-nsendl;cout進程 運行ns 狀態(tài)：R endl;coutnext!=NULL)time=