Linux操作系統(tǒng)課程設(shè)計(jì)報(bào)告-時(shí)間片法和優(yōu)先數(shù)法

-.z?操作系統(tǒng)原理?課程設(shè)計(jì)報(bào)告姓名：吳沛儒班級(jí)：B*0907學(xué)號(hào)：9指導(dǎo)教師：胡靜二〇一一年十二月十二日目錄一、?操作系統(tǒng)原理?課程設(shè)計(jì)的目的與要求31、目的32、要求3二、簡述課程設(shè)計(jì)內(nèi)容、主要功能和實(shí)現(xiàn)環(huán)境31.課程設(shè)計(jì)內(nèi)容3三、任務(wù)的分析、設(shè)計(jì)、實(shí)現(xiàn)和討論31、任務(wù)的分析32、任務(wù)的設(shè)計(jì)與實(shí)現(xiàn)5五、附錄11進(jìn)程調(diào)度—優(yōu)先數(shù)法與簡單輪轉(zhuǎn)法?操作系統(tǒng)原理?課程設(shè)計(jì)的目的與要求目的進(jìn)程是操作系統(tǒng)最重要的概念之一，進(jìn)程調(diào)度又是操作系統(tǒng)核心的主要內(nèi)容。本實(shí)習(xí)要求學(xué)生獨(dú)立地用高級(jí)語言編寫和調(diào)試一個(gè)簡單的進(jìn)程調(diào)度程序。調(diào)度算法可任意選擇或自行設(shè)計(jì)。任務(wù)一采用簡單輪轉(zhuǎn)法，任務(wù)二采用優(yōu)先數(shù)法等。本課題可以加深對進(jìn)程調(diào)度和各種調(diào)度算法的理解。要求設(shè)計(jì)一個(gè)有n個(gè)進(jìn)程并發(fā)的進(jìn)程調(diào)度程序。每個(gè)進(jìn)程由一個(gè)進(jìn)程控制塊〔PCB〕表示。進(jìn)程控制塊一般應(yīng)該包含下述信息：進(jìn)程名、進(jìn)程優(yōu)先數(shù)、進(jìn)程需要運(yùn)行的時(shí)間、占用CPU的時(shí)間以及進(jìn)程的狀態(tài)等，且可按調(diào)度算法的不同而增刪。調(diào)度程序應(yīng)包含2種不同的調(diào)度算法，運(yùn)行時(shí)可任意選一種，以利于各種算法的分析比較。算法應(yīng)能顯示或打印各個(gè)進(jìn)程的PID、狀態(tài)〔運(yùn)行狀態(tài)R、等待狀態(tài)W等〕和參數(shù)〔已運(yùn)行時(shí)間等〕的變化情況，便于觀察諸進(jìn)程的調(diào)度過程進(jìn)程是操作系統(tǒng)最重要的概念之一，進(jìn)程調(diào)度又是操作系統(tǒng)核心的主要內(nèi)容。本實(shí)習(xí)要求學(xué)生獨(dú)立地用高級(jí)語言編寫和調(diào)試一個(gè)簡單的進(jìn)程調(diào)度程序。調(diào)度算法可任意選擇或自行設(shè)計(jì)。任務(wù)一采用簡單輪轉(zhuǎn)法，任務(wù)二采用優(yōu)先數(shù)法等。本課題可以加深對進(jìn)程調(diào)度和各種調(diào)度算法的理解。簡述課程設(shè)計(jì)內(nèi)容、主要功能和實(shí)現(xiàn)環(huán)境課程設(shè)計(jì)內(nèi)容進(jìn)程調(diào)度是處理機(jī)管理的核心內(nèi)容。本實(shí)驗(yàn)要求用C語言編寫和調(diào)試一個(gè)簡單的進(jìn)程調(diào)度程序。選用優(yōu)先數(shù)法或簡單輪轉(zhuǎn)法對五個(gè)進(jìn)程進(jìn)展調(diào)度。每個(gè)進(jìn)程處于運(yùn)行R(run)、就緒W(wait)和完成F(finish)三種狀態(tài)之一，并假設(shè)起始狀態(tài)都是就緒狀態(tài)W。為了便于處理，程序進(jìn)程的運(yùn)行時(shí)間以時(shí)間片為單位計(jì)算。各進(jìn)程的優(yōu)先數(shù)或輪轉(zhuǎn)時(shí)間片數(shù)、以及進(jìn)程需要運(yùn)行的時(shí)間片數(shù)，均由偽隨機(jī)數(shù)發(fā)生器產(chǎn)生。通過本實(shí)驗(yàn)可以加深理解有關(guān)進(jìn)程控制塊、進(jìn)程隊(duì)列的概念，并體會(huì)和了解優(yōu)先數(shù)和時(shí)間片輪轉(zhuǎn)調(diào)度算法的具體實(shí)施方法。主要功能本程序可選用優(yōu)先數(shù)法或簡單輪轉(zhuǎn)法對五個(gè)進(jìn)程進(jìn)展調(diào)度。每個(gè)進(jìn)程處于運(yùn)行R(run)、就緒W(wait)和完成F(finish)三種狀態(tài)之一，并假設(shè)起始狀態(tài)都是就緒狀態(tài)W。為了便于處理，程序進(jìn)程的運(yùn)行時(shí)間以時(shí)間片為單位計(jì)算。實(shí)現(xiàn)環(huán)境本次課程設(shè)計(jì)結(jié)合算法的特點(diǎn)，采用Windows操作系統(tǒng)平臺(tái)。開發(fā)工具為MicrosoftVisualC++6.0。任務(wù)的分析、設(shè)計(jì)、實(shí)現(xiàn)和討論任務(wù)的分析本程序可選用優(yōu)先數(shù)法或簡單輪轉(zhuǎn)法對五個(gè)進(jìn)程進(jìn)展調(diào)度。每個(gè)進(jìn)程處于運(yùn)行R(run)、就緒W(wait)和完成F(finish)三種狀態(tài)之一，并假設(shè)起始狀態(tài)都是就緒狀態(tài)W。為了便于處理，程序進(jìn)程的運(yùn)行時(shí)間以時(shí)間片為單位計(jì)算。各進(jìn)程的優(yōu)先數(shù)或輪轉(zhuǎn)時(shí)間片數(shù)、以及進(jìn)程需要運(yùn)行的時(shí)間片數(shù)，均由偽隨機(jī)數(shù)發(fā)生器產(chǎn)生。下面介紹優(yōu)先數(shù)法和簡單輪轉(zhuǎn)法兩種進(jìn)程調(diào)度算法：優(yōu)先數(shù)法。進(jìn)程就緒鏈按優(yōu)先數(shù)大小從高到低排列，鏈?zhǔn)走M(jìn)程首先投入運(yùn)行。每過一個(gè)時(shí)間片，運(yùn)行進(jìn)程所需運(yùn)行的時(shí)間片數(shù)減1，說明它已運(yùn)行了一個(gè)時(shí)間片，優(yōu)先數(shù)也減3，理由是該進(jìn)程如果在一個(gè)時(shí)間片中完成不了，優(yōu)先級(jí)應(yīng)該降低一級(jí)。接著比較現(xiàn)行進(jìn)程和就緒鏈鏈?zhǔn)走M(jìn)程的優(yōu)先數(shù)，如果仍是現(xiàn)行進(jìn)程高或者一樣，就讓現(xiàn)行進(jìn)程繼續(xù)進(jìn)展，否則，調(diào)度就緒鏈鏈?zhǔn)走M(jìn)程投入運(yùn)行。原運(yùn)行進(jìn)程再按其優(yōu)先數(shù)大小插入就緒鏈，且改變它們對應(yīng)的進(jìn)程狀態(tài)，直至所有進(jìn)程都運(yùn)行完各自的時(shí)間片數(shù)。簡單輪轉(zhuǎn)法。進(jìn)程就緒鏈按各進(jìn)程進(jìn)入的先后次序排列，進(jìn)程每次占用處理機(jī)的輪轉(zhuǎn)時(shí)間按其重要程度登入進(jìn)程控制塊中的輪轉(zhuǎn)時(shí)間片數(shù)記錄項(xiàng)〔相當(dāng)于優(yōu)先數(shù)法的優(yōu)先數(shù)記錄項(xiàng)位置〕。每過一個(gè)時(shí)間片，運(yùn)行進(jìn)程占用處理機(jī)的時(shí)間片數(shù)加1，然后比較占用處理機(jī)的時(shí)間片數(shù)是否與該進(jìn)程的輪轉(zhuǎn)時(shí)間片數(shù)相等，假設(shè)相等說明已到達(dá)輪轉(zhuǎn)時(shí)間，應(yīng)將現(xiàn)運(yùn)行進(jìn)程排到就緒鏈末尾，調(diào)度鏈?zhǔn)走M(jìn)程占用處理機(jī)，且改變它們的進(jìn)程狀態(tài)，直至所有進(jìn)程完成各自的時(shí)間片。進(jìn)程控制塊構(gòu)造如下：進(jìn)程ID鏈指針優(yōu)先數(shù)/輪轉(zhuǎn)時(shí)間片數(shù)占用CPU時(shí)間片數(shù)進(jìn)程所需時(shí)間片數(shù)進(jìn)程狀態(tài)進(jìn)程控制塊鏈構(gòu)造如下：TAILTAILRUN1…RHEAD3…W5…W2…W其中：RUN—當(dāng)前運(yùn)行進(jìn)程指針；HEAD—進(jìn)程就緒鏈鏈?zhǔn)字羔?；TAID—進(jìn)程就緒鏈鏈尾指針。任務(wù)的設(shè)計(jì)與實(shí)現(xiàn)算法流程圖：操作過程和結(jié)果分析優(yōu)先數(shù)調(diào)度算法測試數(shù)據(jù)：優(yōu)先數(shù)調(diào)度算法程序運(yùn)行結(jié)果截圖：圖1.1結(jié)果截圖圖1.2結(jié)果截圖簡單輪轉(zhuǎn)調(diào)度算法測試數(shù)據(jù)：簡單輪轉(zhuǎn)調(diào)度算法程序運(yùn)行結(jié)果截圖：圖2.1結(jié)果截圖圖2.2結(jié)果截圖圖2.3結(jié)果截圖思考題的解答和討論通過以上的調(diào)度算法測試數(shù)據(jù),得出以下不同算法的不同調(diào)度性能結(jié)果:算法比較項(xiàng)(時(shí)間輪轉(zhuǎn)法)RR(最高優(yōu)先數(shù))HRP調(diào)度方式搶占式(按時(shí)間片)非搶占式響應(yīng)時(shí)間對于短進(jìn)程提供良好的響應(yīng)時(shí)間提供良好的響應(yīng)時(shí)間開銷低可能高對待進(jìn)程的作法公平對待良好的均衡(進(jìn)程)?操作系統(tǒng)?課程設(shè)計(jì)小結(jié)當(dāng)我在回首這一個(gè)星期的時(shí)候，不因虛度光陰而悔恨，也不因碌碌無為而羞恥。我想，這可能是我一學(xué)期中最豐富而有意義的一個(gè)星期了。從大一開場我的理論知識(shí)就比實(shí)踐知識(shí)好的多，每門課都如此，實(shí)訓(xùn)是我最頭疼的一件事。課本上記得很牢的東西到了實(shí)際操作的時(shí)候感覺都用不上，做個(gè)實(shí)驗(yàn)就手忙腳亂的。所以我感覺，這個(gè)星期的課設(shè)不僅學(xué)到了在理論課上學(xué)不到的知識(shí)，更是讓我對自己的實(shí)踐操作有了信心。本次課程設(shè)計(jì)的題目之一是進(jìn)程調(diào)度——優(yōu)先數(shù)法與簡單輪轉(zhuǎn)法。在多任務(wù)系統(tǒng)中，進(jìn)程調(diào)度是CPU管理的一項(xiàng)核心工作。根據(jù)調(diào)度模式的不同，多任務(wù)系統(tǒng)有兩種類型，即非搶占式和搶占式。其中，優(yōu)先數(shù)法是非搶占式調(diào)度策略，而簡單輪轉(zhuǎn)法是搶占式調(diào)度策略。進(jìn)程調(diào)度算法是系統(tǒng)效率的關(guān)鍵，它確定了系統(tǒng)對資源，特別是對CPU資源的分配策略，因而直接決定著系統(tǒng)最本質(zhì)的性能指標(biāo)，如相應(yīng)速度和吞吐量等。常用的調(diào)度算法有：先進(jìn)先出法，短進(jìn)程優(yōu)先法，時(shí)間片輪轉(zhuǎn)法〔時(shí)間片輪轉(zhuǎn)法還分為可變時(shí)間片輪轉(zhuǎn)法和簡單循環(huán)輪轉(zhuǎn)法〕，優(yōu)先級(jí)調(diào)度法。簡單循環(huán)輪轉(zhuǎn)法中的時(shí)間片q是一個(gè)十分重要的因素，它的計(jì)算公式為q=t/n。q的選擇對進(jìn)程調(diào)度有很大的影響。q取的太大，輪轉(zhuǎn)法就會(huì)退化成先進(jìn)先出算法；而取的太小，則會(huì)導(dǎo)致系統(tǒng)開銷增加，將時(shí)間浪費(fèi)在進(jìn)程切換上。所以q必須取值適中，使就緒隊(duì)列中的所有進(jìn)程都能得到同樣的效勞。但我們這次的實(shí)驗(yàn)中暫時(shí)還沒有考慮到時(shí)間片q對算法的影響，只是測試了這個(gè)調(diào)度策略的算法。這次我們的實(shí)驗(yàn)測試并比較了簡單輪轉(zhuǎn)法和優(yōu)先數(shù)法這兩種調(diào)度策略的性能。不同的算法有它自己不同的長處，簡單輪轉(zhuǎn)法雖然能夠使每個(gè)進(jìn)程可以以相等的速度向前進(jìn)展，但對于緊急進(jìn)程的處理就顯然不及優(yōu)先數(shù)法。可是優(yōu)先數(shù)法的開銷較高，而且可能對于較短而且優(yōu)先級(jí)低的進(jìn)程會(huì)花較長的時(shí)間等待。不過它還是具有良好的均衡性。實(shí)際應(yīng)用中，經(jīng)常是多種策略結(jié)合使用。如時(shí)間片輪轉(zhuǎn)法中也可以適當(dāng)考慮優(yōu)先級(jí)因素，對于緊急的進(jìn)程可以分配一個(gè)長一點(diǎn)的時(shí)間片，或連續(xù)運(yùn)行多個(gè)時(shí)間片等。這樣取長補(bǔ)短，合理利用各種不同算法的優(yōu)勢，讓CPU的運(yùn)行效率大大提高。人們總是在尋找更好的解決方案，讓算法的性能和開銷得到一個(gè)相對較好的平衡。我在尋找這樣的一個(gè)解決方案時(shí)，同學(xué)對我說雖然教師沒有在課上講過這個(gè)策略，但其實(shí)書上有關(guān)于更好的調(diào)度策略。也就是多級(jí)反響隊(duì)列調(diào)度。這種算法可以先用較小的時(shí)間片處理完那些用時(shí)較短的進(jìn)程，而給那些用時(shí)較長的進(jìn)程分配較大的時(shí)間片，以免較長的進(jìn)程頻繁被中斷而影響處理機(jī)的效率。這也就是上面所提到的“多種策略結(jié)合使用，如時(shí)間片輪轉(zhuǎn)法中也可以適當(dāng)考慮優(yōu)先級(jí)因素〞。溫故而知新，可以為師矣。這次編程中所用到的C語言正是我們大一就學(xué)過的計(jì)算機(jī)語言。在平時(shí)的學(xué)習(xí)中和實(shí)訓(xùn)中我們總能用到它。這樣反復(fù)的運(yùn)用和考核，讓我對C語言的認(rèn)識(shí)更進(jìn)了一步。路漫漫其修遠(yuǎn)兮，吾將上下而求索。我們對操作系統(tǒng)的學(xué)習(xí)還有很長的路要走，死鎖只是其中的一小局部。重要的是，我在實(shí)訓(xùn)的這種里學(xué)到了這樣的一種精神，一種知難而上，相信努力和付出能夠帶來好的結(jié)果的精神。這種精神比刻板的知識(shí)點(diǎn)更加重要，能夠指引我走向更寬闊的明天。附錄*include"stdio.h"*include"stdlib.h"*include"string.h"typedefstructnode{charname[10];/*進(jìn)程標(biāo)識(shí)符*/intprio;/*進(jìn)程優(yōu)先數(shù)*/intround;/*進(jìn)程時(shí)間輪轉(zhuǎn)時(shí)間片*/intcputime;/*進(jìn)程占用CPU時(shí)間*/intneedtime;/*進(jìn)程到完成還要的時(shí)間*/intcount;/*計(jì)數(shù)器*/charstate;/*進(jìn)程的狀態(tài)*/structnode*ne*t;/*鏈指針*/}PCB;PCB*finish,*ready=NULL,*tail,*run,*pfcfs,*pfcfs1;/*隊(duì)列指針*/intN;/*進(jìn)程數(shù)*//*將就緒隊(duì)列中的第一個(gè)進(jìn)程投入運(yùn)行*/voidfirstin(){run=ready;/*就緒隊(duì)列頭指針賦值給運(yùn)行頭指針*/run->state='R';/*進(jìn)程狀態(tài)變?yōu)檫\(yùn)行態(tài)*/ready=ready->ne*t;/*就緒對列頭指針后移到下一進(jìn)程*/}/*標(biāo)題輸出函數(shù)*/voidprt1(chara){if(toupper(a)=='P')/*優(yōu)先數(shù)法*/printf("namecputimeneedtimeprioritystate\n");elseif(toupper(a)=='R')printf("namecputimeneedtimecountroundstate\n");}/*進(jìn)程PCB輸出*/voidprt2(chara,PCB*q){if(toupper(a)=='P')/*優(yōu)先數(shù)法的輸出*/printf("%-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);elseif(toupper(a)=='R')/*輪轉(zhuǎn)法的輸出*/printf("%-10s%-10d%-10d%-10d%-10d%-c\n",q->name,q->cputime,q->needtime,q->count,q->round,q->state);}/*輸出函數(shù)*/voidprt(charalgo){PCB*p;prt1(algo);/*輸出標(biāo)題*/if(run!=NULL)/*如果運(yùn)行指針不空*/prt2(algo,run);/*輸出當(dāng)前正在運(yùn)行的PCB*/p=ready;/*輸出就緒隊(duì)列PCB*/while(p!=NULL){prt2(algo,p);p=p->ne*t;}p=finish;/*輸出完成隊(duì)列的PCB*/while(p!=NULL){prt2(algo,p);p=p->ne*t;}getchar();/*壓任意鍵繼續(xù)*/}/*優(yōu)先數(shù)的插入算法*/voidinsert1(PCB*q){PCB*p1,*s,*r;intb;s=q;/*待插入的PCB指針*/p1=ready;/*就緒隊(duì)列頭指針*/r=p1;/*r做p1的前驅(qū)指針*/b=1;while((p1!=NULL)&&b)/*根據(jù)優(yōu)先數(shù)確定插入位置*/if(p1->prio>=s->prio){r=p1;p1=p1->ne*t;}elseb=0;if(r!=p1)/*如果條件成立說明插入在r與p1之間*/{r->ne*t=s;s->ne*t=p1;}else{s->ne*t=p1;/*否則插入在就緒隊(duì)列的頭*/ready=s;}}/*輪轉(zhuǎn)法插入函數(shù)*/voidinsert2(PCB*p2){tail->ne*t=p2;/*將新的PCB插入在當(dāng)前就緒隊(duì)列的尾*/tail=p2;p2->ne*t=NULL;}voidinsert3()/*先來先效勞*/{if(ready==NULL){ready=pfcfs;ready->ne*t=NULL;pfcfs1=pfcfs;}else{pfcfs1->ne*t=pfcfs;pfcfs1=pfcfs1->ne*t;}}/*優(yōu)先數(shù)創(chuàng)立初始PCB信息*/voidcreate1(charalg){PCB*p;inti,time;charna[10];ready=NULL;/*就緒隊(duì)列頭指針*/finish=NULL;/*完成隊(duì)列頭指針*/run=NULL;/*運(yùn)行隊(duì)列指針*/for(i=1;i<=N;i++){p=(structnode*)malloc(sizeof(PCB));printf("請輸入進(jìn)程名稱%d\n",i);scanf("%s",na);printf("請輸入進(jìn)程運(yùn)行時(shí)間\n");scanf("%d",&time);strcpy(p->name,na);p->cputime=0;p->needtime=time;p->state='w';p->prio=50-time;if(ready!=NULL)/*就緒隊(duì)列不空調(diào)用插入函數(shù)插入*/insert1(p);else{p->ne*t=ready;/*創(chuàng)立就緒隊(duì)列的第一個(gè)PCB*/ready=p;}}printf("最高優(yōu)先級(jí)進(jìn)程調(diào)度模擬:\n");printf("************************************************\n");prt(alg);/*輸出進(jìn)程PCB信息*/printf("************************************************\n");run=ready;/*將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行*/ready=ready->ne*t;run->state='R';}/*輪轉(zhuǎn)法創(chuàng)立進(jìn)程PCB*/voidcreate2(charalg){PCB*p;inti,time;charna[10];ready=NULL;finish=NULL;run=NULL;for(i=1;i<=N;i++){p=(structnode*)malloc(sizeof(PCB));printf("請輸入進(jìn)程名稱%d\n",i);scanf("%s",na);printf("請輸入進(jìn)程運(yùn)行時(shí)間\n");scanf("%d",&time);strcpy(p->name,na);p->cputime=0;p->needtime=time;p->count=0;/*計(jì)數(shù)器*/p->state='w';p->round=2;/*時(shí)間片*/if(ready!=NULL)insert2(p);else{p->ne*t=ready;ready=p;tail=p;}}printf("時(shí)間輪轉(zhuǎn)法進(jìn)程調(diào)度模擬\n");printf("************************************************\n");prt(alg);/*輸出進(jìn)程PCB信息*/printf("************************************************\n");run=ready;/*將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行*/ready=ready->ne*t;run->state='R';}/*優(yōu)先數(shù)調(diào)度算法*/voidpriority(charalg){while(run!=NULL)/*當(dāng)運(yùn)行隊(duì)列不空時(shí)，有進(jìn)程正在運(yùn)行*/{run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->prio=run->prio-3;/*每運(yùn)行一次優(yōu)先數(shù)降低3個(gè)單位*/if(run->needtime==0)/*如所需時(shí)間為0將其插入完成隊(duì)列*/{run->ne*t=finish;finish=run;run->state='F';/*置狀態(tài)為完成態(tài)*/run=NULL;/*運(yùn)行隊(duì)列頭指針為空*/if(ready!=NULL)/*如就緒隊(duì)列不空*/firstin();/*將就緒對列的第一個(gè)進(jìn)程投入運(yùn)行*/}else/*沒有運(yùn)行完同時(shí)優(yōu)先數(shù)不是最大，則將其變?yōu)榫途w態(tài)插入到就緒列*/if((ready!=NULL)&&(run->prio<ready->prio)){run->state='W';insert1(run);firstin();/*將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行*/}prt(alg);/*輸出進(jìn)程PCB信息*/}}/*時(shí)間片輪轉(zhuǎn)法*/voidroundrun(charalg){while(run!=NULL){run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->count=run->count+1;if(run->needtime==0)/*運(yùn)行完將其變?yōu)橥瓿蓱B(tài)，插入完成隊(duì)列*/{run->ne*t=finish;finish=run;run->state='F';run=NULL;if(ready!=NULL)firstin();/*就緒對列不空，將第一個(gè)進(jìn)程投入運(yùn)行*/}elseif(run->coun