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