1、 衡陽(yáng)師范學(xué)院工科課程設(shè)計(jì) -操作系統(tǒng)課程設(shè)計(jì)報(bào)告 題 目： 優(yōu)先數(shù)調(diào)度算法的實(shí)現(xiàn) 學(xué) 號(hào)： 14450139 姓 名： 魯向陽(yáng) 班 級(jí)： 14級(jí)物聯(lián)網(wǎng)班 指導(dǎo)教師： 陳瓊老師 日 期： 2016年 12月 25 目錄1.概述21.1設(shè)計(jì)目的21.2運(yùn)行環(huán)境31.3任務(wù)分配32.需求分析42.2題目?jī)?nèi)容42.2設(shè)計(jì)思想說(shuō)明42.3數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)63.算法的設(shè)計(jì)73.1頭文件聲明73.2定義各種變量73.3相關(guān)函數(shù)的定義73.4程序運(yùn)行流程圖103.5方案設(shè)計(jì)流程圖113.6進(jìn)程控制塊PCB結(jié)構(gòu)123.7進(jìn)程控制塊鏈結(jié)構(gòu)124.實(shí)例135.總結(jié)146.附錄16參考文獻(xiàn)241.概述1.1設(shè)

2、計(jì)目的 在操作系統(tǒng)中調(diào)度算法的實(shí)質(zhì)是一種資源的分配，因而調(diào)度算法是指“根據(jù)系統(tǒng)資源分配策略所規(guī)定的資源分配算法”。對(duì)于不同的操作系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。為了照顧緊迫作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)調(diào)度算法。作為進(jìn)程調(diào)度算法時(shí)，該算法是把處理機(jī)分配給就緒隊(duì)列優(yōu)先權(quán)最高的進(jìn)程。這可以分為搶占式優(yōu)先權(quán)算法和非搶占式優(yōu)先權(quán)算法。對(duì)于最高優(yōu)先權(quán)調(diào)度算法，其關(guān)鍵在于：它是使用靜態(tài)優(yōu)先權(quán)還是動(dòng)態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。動(dòng)態(tài)優(yōu)先權(quán)擁有其特有的靈活優(yōu)點(diǎn)，同時(shí)，若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程，將因其動(dòng)態(tài)優(yōu)先權(quán)變得高而優(yōu)先獲得處理機(jī)

3、，此即FCFS算法。若所有的就緒進(jìn)程具有各不相同優(yōu)先權(quán)初值，那么，對(duì)于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠長(zhǎng)的時(shí)間后，其優(yōu)先權(quán)便可能升為最高，從而獲得處理機(jī)。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以一定速率下降，則可防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期壟斷處理機(jī)。1.2運(yùn)行環(huán)境硬件機(jī)器：pc計(jì)算機(jī)語(yǔ)言：C+（使用自己學(xué)習(xí)的）編譯環(huán)境：visual studio 20101.3任務(wù)分配 1）理解掌握進(jìn)程調(diào)度實(shí)現(xiàn)所涉及到的主要問(wèn)題：如何組織進(jìn)程、如何實(shí)現(xiàn)處理機(jī)調(diào)度。進(jìn)程控制塊的作用和結(jié)構(gòu)，進(jìn)程控制塊的鏈表組織。進(jìn)程調(diào)度程序包含從進(jìn)程就緒隊(duì)列選擇并摘取進(jìn)程、給該進(jìn)程分配處理機(jī)。2）設(shè)計(jì)進(jìn)程控制塊相關(guān)數(shù)據(jù)結(jié)

4、構(gòu)，進(jìn)程狀態(tài)躍遷的相關(guān)模擬；3）實(shí)現(xiàn)優(yōu)先調(diào)度算法模擬程序設(shè)計(jì)、編碼及調(diào)試。2.需求分析2.2題目?jī)?nèi)容編寫(xiě)程序，采用優(yōu)先權(quán)調(diào)度算法實(shí)現(xiàn)單處理機(jī)系統(tǒng)對(duì)進(jìn)程的調(diào)度過(guò)程。2.2設(shè)計(jì)思想說(shuō)明模擬動(dòng)態(tài)優(yōu)先權(quán)算法，在主函數(shù)中選擇采用搶占式進(jìn)程調(diào)度算法，再調(diào)用優(yōu)先調(diào)度算法完成模擬。1.設(shè)定系統(tǒng)中有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊（PCB）表示，隊(duì)列的每一個(gè)結(jié)點(diǎn)都是一種結(jié)構(gòu)體，結(jié)構(gòu)體名稱(chēng)定義為進(jìn)程模塊。2.進(jìn)程控制塊包含如下信息：進(jìn)程編號(hào)、需要運(yùn)行時(shí)間、已用CPU時(shí)間等等。3.在每次運(yùn)行設(shè)計(jì)的處理調(diào)度程序之前，由終端輸入五個(gè)進(jìn)程的“進(jìn)入就緒隊(duì)列時(shí)間”和“要求運(yùn)行時(shí)間”。4.進(jìn)程的進(jìn)入就緒隊(duì)列時(shí)間及需要的運(yùn)行

5、時(shí)間人為地指定.進(jìn)程的運(yùn)行時(shí)間以時(shí)間片為單位進(jìn)行計(jì)算。5.將五個(gè)進(jìn)程按給定進(jìn)程的時(shí)間片從小到大連成就緒隊(duì)列，當(dāng)?shù)谝粋€(gè)進(jìn)程進(jìn)去的時(shí)候，它就執(zhí)行當(dāng)前進(jìn)程，在執(zhí)行的過(guò)程中，可能有另一個(gè)進(jìn)程進(jìn)入，進(jìn)入之后，當(dāng)前的進(jìn)程就會(huì)進(jìn)行更新，更新它所有的信息，就把它放入運(yùn)行隊(duì)列，使當(dāng)前運(yùn)行的剩余時(shí)間為零，為零之后就把當(dāng)前的資源釋放掉，這時(shí)候就從就緒隊(duì)列里面取出進(jìn)程的隊(duì)頭，作為當(dāng)前運(yùn)行的進(jìn)程。尋找的過(guò)程中，采用的是隊(duì)列的遍歷，每遍歷一個(gè)進(jìn)程的時(shí)候，就對(duì)當(dāng)前進(jìn)程的剩余時(shí)間進(jìn)行更新并記錄這個(gè)隊(duì)頭。6.處理機(jī)調(diào)度總是選隊(duì)列首進(jìn)程運(yùn)行。進(jìn)程每運(yùn)行一次剩余時(shí)間減“1”，同時(shí)將已運(yùn)行時(shí)間加“1”。7.進(jìn)程運(yùn)行一次后，若要求運(yùn)行

6、時(shí)間不等于已運(yùn)行時(shí)間，則再將它加入就緒隊(duì)列；否則將其狀態(tài)置為“結(jié)束”,且退出就緒隊(duì)列。8.“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面6，7步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。9.在設(shè)計(jì)的程序中有輸入語(yǔ)句，輸入5個(gè)進(jìn)程的“進(jìn)入就緒隊(duì)列時(shí)間”和“要求運(yùn)行時(shí)間”，也有顯示或打印語(yǔ)句，能顯示或打印進(jìn)程的平均等待時(shí)間和平均周轉(zhuǎn)時(shí)間。10.最后，為五個(gè)進(jìn)程任意確定一組“進(jìn)入就緒隊(duì)列時(shí)間”和“要求運(yùn)行時(shí)間”，運(yùn)行并調(diào)試所設(shè)計(jì)的程序，顯示或打印出逐次被選中進(jìn)程的進(jìn)程序號(hào)。2.3數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)設(shè)定系統(tǒng)中有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊（PCB）表示，隊(duì)列的每一個(gè)結(jié)點(diǎn)都是一種結(jié)構(gòu)體，結(jié)構(gòu)體名稱(chēng)定義為進(jìn)程模塊。

7、建立好進(jìn)程控制模塊之后，進(jìn)程就已按時(shí)間片從小到大的順序排成了就緒隊(duì)列。typedef struct nodechar name10; /進(jìn)程標(biāo)志符int prio; /進(jìn)程優(yōu)先數(shù)int cputime; /進(jìn)程占用cpu時(shí)間int needtime; /進(jìn)程到完成還要的時(shí)間char state; /進(jìn)程的狀態(tài)struct node *next; /鏈指針PCB;3.算法的設(shè)計(jì)3.1頭文件聲明#include<stdio.h>/*標(biāo)準(zhǔn)io庫(kù)*/#include<stdlib.h>/*該文件包含了C語(yǔ)言標(biāo)準(zhǔn)庫(kù)函數(shù)的定義*/#include<string.h>/*

8、一種常用的編譯預(yù)處理指令，在使用到字符數(shù)組時(shí)需要使用*/3.2定義各種變量char name10; /進(jìn)程標(biāo)志符int prio; /進(jìn)程優(yōu)先數(shù)int cputime; /進(jìn)程占用cpu時(shí)間int needtime; /進(jìn)程到完成還要的時(shí)間char state; /進(jìn)程的狀態(tài)struct node *next; /鏈指針3.3相關(guān)函數(shù)的定義/優(yōu)先數(shù)的算法插入算法void insert1(PCB *q)PCB *p1,*s,*r;int b;s=q; /待插入的PCB指針p1=ready; /就緒隊(duì)列頭指針r=p1; /r做p1的前驅(qū)指針b=1;while(p1!=NULL)&&

9、b) /根據(jù)優(yōu)先數(shù)確定插入位置if(p1->prio>=s->prio)r=p1;p1=p1->next;elseb=0;if(r!=p1) /如果條件成立說(shuō)明插入在r與p1之間r->next=s;s->next=p1;elses->next=p1; /否則插入在就緒隊(duì)列的頭ready=s;/優(yōu)先數(shù)調(diào)度算法void priority(char alg)while(run!=NULL) /當(dāng)運(yùn)行隊(duì)列不空時(shí)，有進(jìn)程正在運(yùn)行run->cputime=run->cputime+1;run->needtime=run->needtime-

10、1;run->prio=run->prio-3; /每運(yùn)行一次優(yōu)先數(shù)降低3個(gè)單位if(run->needtime=0) /如所需時(shí)間為0將其插入完成隊(duì)列run->next=finish;finish=run;run->state='F' /置狀態(tài)為完成態(tài)run=NULL; /運(yùn)行隊(duì)列頭指針為空if(ready!=NULL) /如就緒隊(duì)列不空f(shuō)irstin(); /將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行else /沒(méi)有運(yùn)行完同時(shí)優(yōu)先數(shù)不是最大，則將其變?yōu)?就緒態(tài)插入到就緒隊(duì)列if(ready!=NULL)&&(run->prio<

11、ready->prio)run->state='W'insert1(run);firstin(); /將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行prt(alg); /輸出進(jìn)程PCB信息3.4程序運(yùn)行流程圖圖3-13.5方案設(shè)計(jì)流程圖4圖3-23.6進(jìn)程控制塊PCB結(jié)構(gòu)進(jìn)程ID鏈指針優(yōu)先數(shù)占用CPU時(shí)間片數(shù)進(jìn)程所需時(shí)間片數(shù)進(jìn)程狀態(tài)圖3-33.7進(jìn)程控制塊鏈結(jié)構(gòu)圖3-44.實(shí)例圖4-1圖4-25.總結(jié)這次的程序軟件基本上運(yùn)行成功，這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)讓我感觸很深，使我了解到的學(xué)習(xí)不應(yīng)該只局限于課本，因?yàn)檎n本上只是很有限的一部分，所涉及的面也是狹窄的。但是怎樣在有限的范圍內(nèi)學(xué)習(xí)到無(wú)限

12、的知識(shí)呢？那就要懂得自學(xué)，懂得充分利用身邊的資源。應(yīng)該說(shuō)，在這次的課程設(shè)計(jì)中學(xué)到了很多知識(shí)，這并不僅僅包括書(shū)本上的知識(shí)，更重要的是學(xué)會(huì)了如何去和別人交流，怎樣用語(yǔ)言去實(shí)現(xiàn)自己的想法，在這個(gè)過(guò)程中使我懂得了勤學(xué)好問(wèn)的重要性。雖然在我的程序中有一部分是從網(wǎng)上搜索得來(lái)的，但我竭力將所獲得的信息變成自己的資源。在我動(dòng)手上機(jī)操作的同時(shí)，我在了解和看懂的基礎(chǔ)上有所改變和創(chuàng)新，但是在我的程序軟件中還有部分的不足，需要加以更新。同時(shí)，通過(guò)這次課程設(shè)計(jì)，意識(shí)到了自己動(dòng)手實(shí)踐的弱勢(shì)，特別是在編程方面，于是我知道了計(jì)算機(jī)的實(shí)踐操作是很重要的，只有通過(guò)上機(jī)編程才能充分的了解自己的不足。相信通過(guò)這次的課程設(shè)計(jì)，更讓我深

13、刻意識(shí)到學(xué)習(xí)中的弱點(diǎn)，同時(shí)也找到了克服這些弱點(diǎn)的方法，這也是一筆很大的資源。在以后的時(shí)間中，我應(yīng)該利用更多的時(shí)間去上機(jī)實(shí)驗(yàn)，多編寫(xiě)程序，相信不久后我的編程能力都會(huì)有很大的提高。經(jīng)過(guò)這次課程設(shè)計(jì)，通過(guò)對(duì)程序的編制，調(diào)試和運(yùn)行，使我熟悉了各種調(diào)用的數(shù)據(jù)類(lèi)型，在調(diào)試和運(yùn)行過(guò)程中使我更加的了解和熟悉程序運(yùn)行的環(huán)境，提高了我對(duì)程序調(diào)試分析的能力和對(duì)錯(cuò)誤的糾正能力。這次操作系統(tǒng)的程序設(shè)計(jì)，對(duì)于我來(lái)說(shuō)是一個(gè)挑戰(zhàn)。我對(duì)操作系統(tǒng)的學(xué)習(xí)在程序的設(shè)計(jì)中也有所體現(xiàn)。課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí)、發(fā)現(xiàn)、提出、分析和解決實(shí)際問(wèn)題，鍛煉實(shí)踐能力的重要環(huán)節(jié)，是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程。6.附錄#inclu

14、de<stdio.h>#include<stdlib.h>#include<string.h>typedef struct nodechar name10; /進(jìn)程標(biāo)志符int prio; /進(jìn)程優(yōu)先數(shù)int cputime; /進(jìn)程占用cpu時(shí)間int needtime; /進(jìn)程到完成還要的時(shí)間char state; /進(jìn)程的狀態(tài)struct node *next; /鏈指針PCB;PCB *finish,*ready,*tail,*run; /隊(duì)列指針int N; /進(jìn)程數(shù)/將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行void firstin()run=ready;

15、/就緒隊(duì)列頭指針賦值給運(yùn)行頭指針run->state='R' /進(jìn)程狀態(tài)變?yōu)檫\(yùn)行態(tài)ready=ready->next; /就緒列頭指針后移到下一進(jìn)程/標(biāo)題輸出函數(shù)void prt1(char a)printf("進(jìn)程號(hào) cpu時(shí)間 所需時(shí)間 優(yōu)先數(shù) 狀態(tài)n");/進(jìn)程PCB輸出void prt2(char a,PCB *q) /優(yōu)先數(shù)算法輸出printf(" % -10s% -10d% -10d% -10d %cn",q->name,q->cputime,q->needtime,q->prio,q-&g

16、t;state);/輸出函數(shù)void prt(char algo)PCB *p;prt1(algo); /輸出標(biāo)題if(run!=NULL) /如果運(yùn)行標(biāo)題指針不空prt2(algo,run); /輸出當(dāng)前正在運(yùn)行的PCBp=ready; /輸出就緒隊(duì)列PCBwhile(p!=NULL)prt2(algo,p);p=p->next;p=finish; /輸出完成隊(duì)列的PCBwhile(p!=NULL)prt2(algo,p);p=p->next;getchar(); /按任意鍵繼續(xù)/優(yōu)先數(shù)的算法插入算法void insert1(PCB *q)PCB *p1,*s,*r;int b;

17、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->next;elseb=0;if(r!=p1) /如果條件成立說(shuō)明插入在r與p1之間r->next=s;s->next=p1;elses->next=p1; /否則插入在就緒隊(duì)列的頭ready=s;/優(yōu)先數(shù)創(chuàng)建初始PCB信息void create1(char alg)PCB *p;int i,time;ch

18、ar na10;ready=NULL; /就緒隊(duì)列頭文件finish=NULL; /完成隊(duì)列頭文件run=NULL; /運(yùn)行隊(duì)列頭文件printf("輸入進(jìn)程號(hào)和運(yùn)行時(shí)間：n"); /輸入進(jìn)程標(biāo)志和所需時(shí)間創(chuàng)建PCBfor(i=1;i<=N;i+)p=(PCB *)malloc(sizeof(PCB);scanf("%s",na);scanf("%d",&time);strcpy(p->name,na);p->cputime=0;p->needtime=time;p->state='w&#

19、39;p->prio=50-time;if(ready!=NULL) /就緒隊(duì)列不空，調(diào)用插入函數(shù)插入insert1(p);elsep->next=ready; /創(chuàng)建就緒隊(duì)列的第一個(gè)PCBready=p;/clrscr();printf(" 優(yōu)先數(shù)算法輸出信息：n");printf("*n");prt(alg); /輸出進(jìn)程PCB信息run=ready; /將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行ready=ready->next;run->state='R'/優(yōu)先數(shù)調(diào)度算法void priority(char alg)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->next=finish;finish=run;run->st