操作系統(tǒng)課程設(shè)計(jì)報(bào)告 處理機(jī)調(diào)度問題

1、 操作系統(tǒng)課程設(shè)計(jì) 學(xué)號： 1233050169 姓名： 安心 專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 課程： 操作系統(tǒng) 指導(dǎo)教師： 時(shí)間： 2015/3/9 成績： 目錄目錄11設(shè)計(jì)題目與要求21.1設(shè)計(jì)目的21.2設(shè)計(jì)要求22 總體設(shè)計(jì)思想22.1總體設(shè)計(jì)思想23 功能設(shè)計(jì)43.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)43.2程序清單4 3.3運(yùn)行結(jié)果74. 設(shè)計(jì)心得95. 參考資料9附錄10程序源代碼：10一設(shè)計(jì)題目與要求 課題：理機(jī)調(diào)度模擬程序：選擇一個(gè)調(diào)度算法，實(shí)現(xiàn)處理機(jī)調(diào)度。1.設(shè)計(jì)目的：在多道程序和多任務(wù)系統(tǒng)中，系統(tǒng)內(nèi)同時(shí)處于就緒狀態(tài)的進(jìn)程可能有若干個(gè)。也就是說能運(yùn)行的進(jìn)程數(shù)大于處理機(jī)個(gè)數(shù)。為了使系統(tǒng)中的進(jìn)程能有條不

2、紊地工作，必須選用某種調(diào)度策略，選擇一進(jìn)程占用處理機(jī)。要求學(xué)生設(shè)計(jì)一個(gè)模擬處理機(jī)調(diào)度算法，以鞏固和加深處理機(jī)調(diào)度的概念。2.設(shè)計(jì)要求：1）進(jìn)程調(diào)度算法包括：時(shí)間片輪轉(zhuǎn)法，短作業(yè)優(yōu)先算法，最高響應(yīng)比優(yōu)先算法。2）可選擇進(jìn)程數(shù)量3）本程序包括三種算法，可用C語言實(shí)現(xiàn)，執(zhí)行時(shí)在主界面選擇算法（可用函數(shù)實(shí)現(xiàn)），進(jìn)入子頁面后輸入進(jìn)程數(shù)及每個(gè)進(jìn)程的運(yùn)行時(shí)間，每個(gè)進(jìn)程的優(yōu)先數(shù)由隨機(jī)函數(shù)產(chǎn)生且優(yōu)先數(shù)隨等待時(shí)間而變化，執(zhí)行，顯示結(jié)果。二總體設(shè)計(jì)思想(1)進(jìn)程的創(chuàng)建：由系統(tǒng)為某個(gè)進(jìn)程設(shè)置一個(gè)進(jìn)程控制塊PCB，用于對進(jìn)程進(jìn)行控制和管理。進(jìn)程任務(wù)完成，由系統(tǒng)收回其PCB，該進(jìn)程便消亡。(2)進(jìn)程的三種狀態(tài)：運(yùn)行、就緒

3、、完成。進(jìn)程的三種狀態(tài)可以通過設(shè)計(jì)三個(gè)鏈隊(duì)列來實(shí)現(xiàn)：finish為完成隊(duì)列的頭指針，ready為就緒隊(duì)列的頭指針，tail為循環(huán)輪轉(zhuǎn)法隊(duì)列的尾指針。因?yàn)槊恳粫r(shí)刻，CPU只能運(yùn)行一個(gè)進(jìn)程，所以運(yùn)行隊(duì)列只有一個(gè)run指針指向當(dāng)前運(yùn)行進(jìn)程。(3)進(jìn)程調(diào)度的功能：按照一定的策略從就緒隊(duì)列的多個(gè)進(jìn)程中選取一個(gè)進(jìn)程，使其獲得CPU而運(yùn)行。動(dòng)態(tài)優(yōu)先數(shù)調(diào)度算法： 思想：為每一個(gè)進(jìn)程設(shè)一個(gè)優(yōu)先數(shù)，它總是把處理機(jī)給就緒隊(duì)列中具有最高優(yōu)先級的進(jìn)程。初始的進(jìn)程優(yōu)先數(shù)是隨機(jī)產(chǎn)生的，隨著進(jìn)程的運(yùn)行對優(yōu)先數(shù)進(jìn)行調(diào)整，每次運(yùn)行時(shí)都是從就緒隊(duì)列中選取優(yōu)先數(shù)最大的進(jìn)程運(yùn)行，所以將就緒隊(duì)列按照優(yōu)先數(shù)的大小從高到低排序，這樣，每次取

4、對首進(jìn)程即可。將進(jìn)程按優(yōu)先數(shù)的大小排列在就緒隊(duì)列中，每次選取就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程首先占用處理機(jī)。優(yōu)先數(shù)由隨機(jī)函數(shù)產(chǎn)生進(jìn)程最初的優(yōu)先數(shù)。優(yōu)先數(shù)的動(dòng)態(tài)變化：進(jìn)程每執(zhí)行一次優(yōu)先數(shù)-1。優(yōu)先數(shù)隨著進(jìn)程的執(zhí)行進(jìn)行調(diào)整，每次執(zhí)行時(shí)都從就緒隊(duì)列中選取優(yōu)先數(shù)最大的進(jìn)程投入運(yùn)行。時(shí)間片輪轉(zhuǎn)調(diào)度算法：思想：將所有進(jìn)程按照先來先服務(wù)的規(guī)則排成一個(gè)隊(duì)列，把CPU分配給就緒隊(duì)列的隊(duì)首進(jìn)程，并規(guī)定它的執(zhí)行時(shí)間（稱此時(shí)間為時(shí)間片），當(dāng)時(shí)間片用完但并未執(zhí)行結(jié)束時(shí)，剝奪該進(jìn)程的執(zhí)行，將其鏈接到就緒隊(duì)列的隊(duì)尾，等待下一次的選擇。將就緒隊(duì)列的隊(duì)首指針投入運(yùn)行。短作業(yè)優(yōu)先調(diào)度算法（不可剝奪式的）思想：根據(jù)估計(jì)運(yùn)行時(shí)間的長短，將

5、各個(gè)進(jìn)程排成一個(gè)就緒隊(duì)列（估計(jì)運(yùn)行時(shí)間最短的進(jìn)程排在隊(duì)首），每次運(yùn)行將隊(duì)首進(jìn)程投入運(yùn)行，直到運(yùn)行結(jié)束，將此進(jìn)程連接到完成隊(duì)列的隊(duì)尾。然后，再將下一個(gè)隊(duì)首進(jìn)程投入運(yùn)行，直到所有的進(jìn)程都運(yùn)行完畢。三功能設(shè)計(jì)1.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) PCB結(jié)構(gòu)體：typedef struct node char name10; /*進(jìn)程時(shí)間輪轉(zhuǎn)時(shí)間片*/ int pid; /*進(jìn)程的標(biāo)號*/ int prio; /*優(yōu)先級*/ int round; /*時(shí)間片*/ int cputime; /*進(jìn)程占用cpu的時(shí)間*/ int runtime; /*進(jìn)程運(yùn)行所用的時(shí)間*/ int waittime; /*進(jìn)程的等待時(shí)間*/

6、 int length; /*進(jìn)程的長度*/ int count; /*計(jì)數(shù)器*/ char state; /*進(jìn)程的狀態(tài)*/ struct node *next;/*鏈指針*/PCB; PCB結(jié)構(gòu)體用于標(biāo)識(shí)進(jìn)程的創(chuàng)建與撤消。鏈指針：PCB *finish,*ready,*tail,*run;.Finish：完成隊(duì)列的首指針，用于標(biāo)識(shí)完成隊(duì)列；Ready：就緒隊(duì)列的首指針，用于標(biāo)識(shí)就緒隊(duì)列；Run：運(yùn)行隊(duì)列的首指針，用于標(biāo)識(shí)運(yùn)行隊(duì)列；Tail：循環(huán)輪轉(zhuǎn)隊(duì)列的尾指針；2.程序清單 （1）Create1（），create2（），create3（）分別為創(chuàng)建進(jìn)程的函數(shù) Create1（ ）：按照優(yōu)先

7、級調(diào)度算法創(chuàng)建進(jìn)程，用戶輸入進(jìn)程名及進(jìn)程所需的時(shí)間后，創(chuàng)建每個(gè)進(jìn)程的PCB，將每個(gè)進(jìn)程的PCB調(diào)用函數(shù)insert1（）按照優(yōu)先數(shù)從高到低排列到就緒隊(duì)列中。 create2（ ）：按照時(shí)間片調(diào)度算法創(chuàng)建進(jìn)程，用戶輸入進(jìn)程名及進(jìn)程所需的時(shí)間后，創(chuàng)建每個(gè)進(jìn)程的PCB，將每個(gè)進(jìn)程的PCB調(diào)用函數(shù)insert2（ ）將每個(gè)進(jìn)程PCB按照輸入的先后順序插入到就緒隊(duì)列的末尾。 create3（ ）：按照短作業(yè)優(yōu)先調(diào)度算法創(chuàng)建進(jìn)程，用戶輸入進(jìn)程名及進(jìn)程所需的時(shí)間后，創(chuàng)建每個(gè)進(jìn)程的PCB，將每個(gè)進(jìn)程的PCB調(diào)用函數(shù)insert3（ ）：按照作業(yè)估計(jì)執(zhí)行時(shí)間的長短從高到低排列到就緒隊(duì)列中。就緒隊(duì)列創(chuàng)建好后，將隊(duì)

8、列當(dāng)中的第一個(gè)PCB變?yōu)檫\(yùn)行態(tài)“R”，將run 指針指向它，ready指針后移，作為就緒隊(duì)列的新頭指針，然后調(diào)用調(diào)度算法。注意每個(gè)時(shí)刻只能有一個(gè)進(jìn)程處于運(yùn)行態(tài)。（2） insert1（），insert2（），insert3（）分別為插入函數(shù) 這三個(gè)函數(shù)完成的是就緒隊(duì)列的創(chuàng)建和管理。 insert1（）的功能是將未完成且優(yōu)先數(shù)小于其它進(jìn)程的PCB按進(jìn)程優(yōu)先數(shù)的順序插入到就緒隊(duì)列中去。 insert2（）的功能是將執(zhí)行了一個(gè)時(shí)間片且還未完成的進(jìn)程的PCB插入到就緒隊(duì)列的隊(duì)尾。 insert3（）的功能是將未完成且作業(yè)的執(zhí)行時(shí)間小于其它進(jìn)程的PCB按進(jìn)程的作業(yè)的執(zhí)行時(shí)間的長短插入到就緒隊(duì)列中去。（3

9、）priority（）優(yōu)先數(shù)調(diào)度算法假定系統(tǒng)有三個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表，進(jìn)程控制塊的格式為：typedef struct node int pid; /*進(jìn)程的標(biāo)號*/ int prio; /*優(yōu)先級*/ int cputime; /*進(jìn)程占用cpu的時(shí)間*/ int runtime; /*進(jìn)程運(yùn)行所用的時(shí)間*/ char state; /*進(jìn)程的狀態(tài)*/ struct node *next;/*鏈指針*/PCB; （4） roundrun（）時(shí)間片輪轉(zhuǎn)法調(diào)度算法 假定系統(tǒng)有三個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表。進(jìn)程控制塊的格式為： 進(jìn)程名，進(jìn)程占用cpu的

10、時(shí)間，進(jìn)程到完成還需的時(shí)間，時(shí)間片，計(jì)數(shù)器，狀態(tài) 進(jìn)程名作為進(jìn)程的標(biāo)識(shí)，假設(shè)三個(gè)進(jìn)程的進(jìn)程名分別是p1，p2，p3。時(shí)間片時(shí)間片輪轉(zhuǎn)循環(huán)所需的時(shí)間總數(shù)。計(jì)數(shù)器對進(jìn)程執(zhí)行時(shí)間進(jìn)行計(jì)數(shù)。進(jìn)程占用cpu的時(shí)間假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為“0”。 狀態(tài)有三種狀態(tài)，“就緒”狀態(tài)，“運(yùn)行”狀態(tài)和“完成”狀態(tài)。三個(gè)進(jìn)程的初始狀態(tài)都為“就緒”，用“w”表示，當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“完成”，用“F”表示，當(dāng)一個(gè)進(jìn)程正在占用cpu 時(shí)，它的狀態(tài)為“運(yùn)行”狀態(tài)。 每次運(yùn)行所設(shè)計(jì)的時(shí)間片輪轉(zhuǎn)調(diào)度程序之前，為每個(gè)進(jìn)程任意確定它的“要求運(yùn)行時(shí)間”。 把三個(gè)進(jìn)程按先來先服務(wù)的順序排成循環(huán)隊(duì)列，用指針指出

11、隊(duì)列連接情況。時(shí)間片輪轉(zhuǎn)調(diào)度總是選擇ready指針指示的進(jìn)程運(yùn)行。而是執(zhí)行： 進(jìn)程到完成還需的時(shí)間1 進(jìn)程占用cpu的時(shí)間+1計(jì)數(shù)器+1來模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過一個(gè)單位的時(shí)間。（5） shortjob（）短作業(yè)優(yōu)先法調(diào)度算法假定系統(tǒng)有三個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表，進(jìn)程控制塊的格式為：進(jìn)程名， 進(jìn)程占用cpu的時(shí)間， 進(jìn)程到完成還需的時(shí)間， 狀態(tài)進(jìn)程名作為進(jìn)程的標(biāo)識(shí)，假設(shè)三個(gè)進(jìn)程的進(jìn)程名分別為P1，P2，P3。進(jìn)程占用cpu的時(shí)間假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為“0”。狀態(tài)有三種狀態(tài)，“就緒”狀態(tài)，“運(yùn)行”狀態(tài)和“完成”狀態(tài)。三個(gè)進(jìn)程的初始狀態(tài)都為“就緒

12、”，用“w”表示，當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“完成”，用“F”表示，當(dāng)一個(gè)進(jìn)程正在占用cpu 時(shí)，它的狀態(tài)為“運(yùn)行”狀態(tài)。在每次運(yùn)行所設(shè)計(jì)的短作業(yè)優(yōu)先調(diào)度程序之前，為每個(gè)進(jìn)程任意確定它的“要求運(yùn)行時(shí)間”。 為了調(diào)度方便，把三個(gè)進(jìn)程按任意給定的作業(yè)長短進(jìn)行排序。用一單元指出隊(duì)首進(jìn)程，用指針指出隊(duì)列的連接情況。每次取對首進(jìn)程即可。 短作業(yè)調(diào)度總是選隊(duì)首進(jìn)程運(yùn)行。進(jìn)程每運(yùn)行一次，要求運(yùn)行時(shí)間-1進(jìn)程占用cpu的時(shí)間+1來模擬進(jìn)程的一次運(yùn)行。進(jìn)程運(yùn)行一次后，若要求運(yùn)行時(shí)間0，則再將它插入就緒隊(duì)列（按作業(yè)長短插入，且置隊(duì)首標(biāo)志）；若要求運(yùn)行時(shí)間=0，則把它的狀態(tài)修改成“完成”（F），且退出隊(duì)列。

13、若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進(jìn)程都成為“完成”狀態(tài)。 在設(shè)計(jì)的程序中有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化及狀態(tài)。 為三個(gè)進(jìn)程隨機(jī)確定“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過程。（6） 界面設(shè)計(jì)： 主界面：選擇調(diào)度算法； 子界面：輸入進(jìn)程數(shù)，進(jìn)程名及進(jìn)程所需的時(shí)間； 利用c語言中的畫圖函數(shù)及清屏函數(shù)設(shè)計(jì)界面。3運(yùn)行結(jié)果主界面設(shè)計(jì)：（1,2,3算法 4退出）算法1：動(dòng)態(tài)優(yōu)先級算法算法2：時(shí)間片輪轉(zhuǎn)法算法3：短作業(yè)優(yōu)先法四心得體會(huì)及總結(jié)：處理機(jī)調(diào)度問

14、題實(shí)際上是處理機(jī)分配問題。只有那些參與競爭處理機(jī)所必須的資源都已得到滿足的進(jìn)程才能享受競爭處理機(jī)的資格，這時(shí)它們處于內(nèi)存就緒狀態(tài)。這些必須的資源包括內(nèi)存、外設(shè)及有關(guān)數(shù)據(jù)結(jié)構(gòu)等。作業(yè)調(diào)度程序必須先調(diào)用存儲(chǔ)管理、外設(shè)管理，分配資源，讓它們能有競爭資格。為了提高資源利用率，一部分在內(nèi)存中處于就緒、等待狀態(tài)而短期內(nèi)不能執(zhí)行進(jìn)程、作業(yè)換出內(nèi)存，所以外存中除了處于后備狀態(tài)的作業(yè)，還有處于就緒狀態(tài)的作業(yè)。這就需要一定的方法和策略來為這部分作業(yè)分配空間。學(xué)習(xí)完操作系統(tǒng)原理課程后，進(jìn)行的這次全面的綜合訓(xùn)練，通過課程設(shè)計(jì)，使我更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)學(xué)生的動(dòng)

15、手能力，并與編程相結(jié)合應(yīng)用于實(shí)際中。5 參考資料1宗大華，宗濤，陳吉人著 操作系統(tǒng) 北京：人民郵電出版社，20092李愛華，程磊著 面相對象程序設(shè)計(jì)（C+語言） 北京: 清華大學(xué)出版社，20103宋曉宇 ， windows操作系統(tǒng)核心編程實(shí)驗(yàn)教程 中國鐵道出版社4張麗芬 劉利雄 王金玉編著 操作系統(tǒng)實(shí)驗(yàn)教程 清華大學(xué)出版社附錄：程序源代碼#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>typedef struct node char name10;

16、int prio; int round; int cputime; int needtime; int count; char state; struct node *next;PCB;PCB *finish,*ready,*tail,*run;int N;firstin() run=ready; run->state='R' ready=ready->next;int timesj(void) int i,xt; time_t t; srand(unsigned) time(&t); xt = rand() % 10 +1; return xt;void

17、prt1(char a) if(toupper(a)='1') printf(" name cputime needtime priority staten"); else if(toupper(a)='2') printf(" name cputime needtime priority staten"); else printf(" name cputime needtime priority staten");void prt2(char a,PCB *q) if(toupper(a)='

18、1') printf(" %-10s%-10d%-10d%-10d %cn",q->name, q->cputime,q->needtime,q->prio,q->state); else if(toupper(a)='2') printf(" %-10s%-10d%-10d%-10d %cn",q->name, q->cputime,q->needtime,q->prio,q->state); else printf(" %-10s%-10d%-10d%-10

19、d %cn",q->name, q->cputime,q->needtime,q->prio,q->state);void prt(char algo) PCB *p; prt1(algo); if(run!=NULL) prt2(algo,run); p=ready; while(p!=NULL) prt2(algo,p); p=p->next; p=finish; while(p!=NULL) prt2(algo,p); p=p->next; getch(); return;insert1(PCB *q) PCB *p1,*s,*r; i

20、nt b; s=q; p1=ready; r=p1; b=1; while(p1!=NULL)&&b) if(p1->prio>=s->prio) r=p1; p1=p1->next; else b=0; if(r!=p1) r->next=s; s->next=p1; else s->next=p1; ready=s; insert2(PCB *p2) tail->next=p2; tail=p2; p2->next=NULL;insert3(PCB *q) PCB *p1,*s,*r; int b; s=q; p1=re

21、ady; r=p1; b=1; while(p1!=NULL)&&b) if(p1->needtime<=s->needtime) r=p1; p1=p1->next; else b=0; if(r!=p1) r->next=s; s->next=p1; else s->next=p1; ready=s; void create1(char alg) PCB *p; int i,time,sjt,priost; char na10; ready=NULL; finish=NULL; run=NULL; printf("Ente

22、r name and time of processn"); printf("-n"); for(i=1;i<=N;i+) p=malloc(sizeof(PCB); printf("Enter name%d",i); printf(":"); scanf("%s",na); printf("Random time%d",i); printf(":"); sjt=timesj(); printf("%dn", sjt); printf(&q

23、uot;Random priority%d",i); printf(":"); printf("%dn", 20-sjt); strcpy(p->name,na); p->cputime=0; p->needtime=sjt; p->state='w' p->prio=20-sjt; if(ready!=NULL) insert1(p); else p->next=ready; ready=p; printf(" Display Process Of Priority:n"

24、); printf("-n"); prt(alg); run=ready; ready=ready->next; run->state='R'void create2(char alg) PCB *p; int i,time,sjt; char na10; ready=NULL; finish=NULL; run=NULL; printf("Enter name and time of round processn"); printf("-n"); for(i=1;i<=N;i+) p=malloc(

25、sizeof(PCB); printf("Enter name%d",i); printf(":"); scanf("%s",na); printf("Random time%d",i); printf(":"); sjt=timesj(); printf("%dn", sjt); printf("Random priority%d",i); printf(":"); printf("%dn", 20-sjt); s

26、trcpy(p->name,na); p->cputime=0; p->needtime=sjt; p->round=1; p->state='w' p->count=0; p->prio=20-sjt; if(ready!=NULL) insert2(p); else p->next=ready; ready=p; tail=p; printf(" Display Process Of Roundrobinn"); printf("-n"); prt(alg); run=ready; re

27、ady=ready->next; run->state='R'void create3(char alg) PCB *p; int i,time,sjt; char na10; ready=NULL; finish=NULL; run=NULL; printf("Enter name and time of processn"); printf("-n"); for(i=1;i<=N;i+) p=malloc(sizeof(PCB); printf("Enter name%d",i); printf(

28、":"); scanf("%s",na); printf("Random time%d",i); printf(":"); sjt=timesj(); printf("%dn", sjt); printf("Random priority%d",i); printf(":"); printf("%dn", 20-sjt); strcpy(p->name,na); p->cputime=0; p->needtime=sj

29、t; p->state='w' p->prio=20-sjt; if(ready!=NULL) insert1(p); else p->next=ready; ready=p; printf(" Display Process Of Priority:n"); printf("-n"); prt(alg); run=ready; ready=ready->next; run->state='R'priority(char alg) while(run!=NULL) run->cputim

30、e=run->cputime+1; run->needtime=run->needtime-1; run->prio=run->prio-1; if(run->needtime=0) run->next=finish; finish=run; run->state='C' run=NULL; if(ready!=NULL) firstin(); else if(ready!=NULL)&&(run->prio<ready->prio) run->state='W' inser

31、t1(run); firstin(); prt(alg); roundrun(char alg) while(run!=NULL) run->cputime=run->cputime+1; run->needtime=run->needtime-1; run->count=run->count+1; run->prio=run->prio-1; if(run->needtime=0) run->next=finish; finish=run; run->state='C' run=NULL; if(ready!=

32、NULL) firstin(); else if(run->count=run->round) run->count=0; if(ready!=NULL) run->state='W' insert2(run); firstin(); prt(alg); shorttask(char alg) while(run!=NULL) run->cputime=run->cputime+1; run->needtime=run->needtime-1; run->prio=run->prio-1; if(run->needtime=0) run-&