隊列與處理機(jī)調(diào)度——數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)

1、 目 錄texttexttexttext導(dǎo)入導(dǎo)入 數(shù)據(jù)結(jié)構(gòu)的核心地位數(shù)據(jù)結(jié)構(gòu)的核心地位數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 隊列隊列操作系統(tǒng)操作系統(tǒng) 處理機(jī)調(diào)度處理機(jī)調(diào)度綜合實踐綜合實踐 算法實現(xiàn)算法實現(xiàn)n n ，。a2ana1frontrear 計算機(jī)系統(tǒng)中存儲程序和數(shù)據(jù)，并按照程序計算機(jī)系統(tǒng)中存儲程序和數(shù)據(jù)，并按照程序規(guī)定的步驟執(zhí)行指令的部件。規(guī)定的步驟執(zhí)行指令的部件。 程序是描述處理機(jī)完成某項任務(wù)的指令序列。 指令則是處理機(jī)能直接解釋、執(zhí)行的信息單位。 由于處理機(jī)是單入口資源，任何時刻只能由于處理機(jī)是單入口資源，任何時刻只能有一個任務(wù)得到它的控制權(quán)，只有一個程序在有一個任務(wù)得到它的控制權(quán)，只有一個程序在其上

2、運行，即多任務(wù)只能互斥地使用處理機(jī)。其上運行，即多任務(wù)只能互斥地使用處理機(jī)。 因此需要一個處理機(jī)調(diào)度算法來決定因此需要一個處理機(jī)調(diào)度算法來決定(選擇選擇)哪一個就緒進(jìn)程先運行并使其充分有效地利用哪一個就緒進(jìn)程先運行并使其充分有效地利用處理機(jī)資源。處理機(jī)資源。 周轉(zhuǎn)時間短周轉(zhuǎn)時間短 響應(yīng)時間快響應(yīng)時間快 截止時間的保證截止時間的保證 優(yōu)先權(quán)準(zhǔn)則優(yōu)先權(quán)準(zhǔn)則 即使得單位時間內(nèi)運行盡可能多的作業(yè)，即使得單位時間內(nèi)運行盡可能多的作業(yè)，處理機(jī)盡可能的保持處理機(jī)盡可能的保持“忙碌忙碌”，各種，各種I/O設(shè)備得設(shè)備得以充分利用，并且對所有的作業(yè)都公平合理。以充分利用，并且對所有的作業(yè)都公平合理。 所謂周轉(zhuǎn)時間

3、，是指從作業(yè)被提交給所謂周轉(zhuǎn)時間，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔（稱為作業(yè)周轉(zhuǎn)時間）。隔（稱為作業(yè)周轉(zhuǎn)時間）。 對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為計算機(jī)系統(tǒng)的管理者，則總是希望能使平均周轉(zhuǎn)時間最短，這不僅會有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意。 所謂響應(yīng)時間，是從用戶提交一個請求所謂響應(yīng)時間，是從用戶提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。 所謂截止時間，是指某任務(wù)必須開始執(zhí)行所謂截止時間，是指某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。

4、的最遲時間，或必須完成的最遲時間。 優(yōu)先權(quán)準(zhǔn)則。遵循優(yōu)先權(quán)準(zhǔn)則，可使得優(yōu)先權(quán)準(zhǔn)則。遵循優(yōu)先權(quán)準(zhǔn)則，可使得某些緊急的作業(yè)能得到及時處理。某些緊急的作業(yè)能得到及時處理。處理機(jī)調(diào)度算法1.先來先服務(wù)調(diào)度算法原理：按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選作業(yè)，原理：按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選作業(yè)， 先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。 性能：算法容易實現(xiàn)，效率不高；性能：算法容易實現(xiàn)，效率不高； 不利于短作業(yè)而優(yōu)待了長作業(yè)。不利于短作業(yè)而優(yōu)待了長作業(yè)。 示例：示例： 2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法原理：最短作業(yè)優(yōu)先算法以進(jìn)入系統(tǒng)的作業(yè)所要原理：最短作業(yè)優(yōu)先算法以進(jìn)入系統(tǒng)的作業(yè)所要 求

5、的求的CPU時間為標(biāo)準(zhǔn)，總選取估計計算時時間為標(biāo)準(zhǔn)，總選取估計計算時 間最短的作業(yè)投入運行。間最短的作業(yè)投入運行。 性能：算法易于實現(xiàn)，效率高；性能：算法易于實現(xiàn)，效率高； 弱點是需要預(yù)先知道作業(yè)所需的弱點是需要預(yù)先知道作業(yè)所需的CPU時間；時間； 忽視了作業(yè)等待時間，會出現(xiàn)饑餓現(xiàn)象。忽視了作業(yè)等待時間，會出現(xiàn)饑餓現(xiàn)象。4 47 71212141418184 46 61010111114149 9FCFS和和SJF調(diào)度算法的性能調(diào)度算法的性能4 49 918186 613134 48 816163 39 98 8 3.高優(yōu)先權(quán)優(yōu)先調(diào)度算法原理：根據(jù)確定的優(yōu)先數(shù)來選取作業(yè)，每次總是原理：根據(jù)確定

6、的優(yōu)先數(shù)來選取作業(yè)，每次總是 選擇優(yōu)先數(shù)高的作業(yè)。選擇優(yōu)先數(shù)高的作業(yè)。靜態(tài)優(yōu)先數(shù)法：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，在靜態(tài)優(yōu)先數(shù)法：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，在 整個運行期間不再改變。整個運行期間不再改變。動態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時創(chuàng)立一個優(yōu)先數(shù)，但在其動態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時創(chuàng)立一個優(yōu)先數(shù)，但在其 生命周期內(nèi)優(yōu)先權(quán)可以隨進(jìn)程的推進(jìn)或生命周期內(nèi)優(yōu)先權(quán)可以隨進(jìn)程的推進(jìn)或 隨其等待時間的增加而改變的，以便獲隨其等待時間的增加而改變的，以便獲 得更好的調(diào)度性能。得更好的調(diào)度性能。原理：把原理：把CPU劃分成若干時間片，并且按順序賦劃分成若干時間片，并且按順序賦 給就緒隊列中的每一個進(jìn)程，進(jìn)程

7、輪流占給就緒隊列中的每一個進(jìn)程，進(jìn)程輪流占 有有CPU，當(dāng)時間片用完時，即使進(jìn)程未執(zhí)，當(dāng)時間片用完時，即使進(jìn)程未執(zhí) 行完畢，系統(tǒng)也剝奪該進(jìn)程的行完畢，系統(tǒng)也剝奪該進(jìn)程的CPU，將該，將該 進(jìn)程排在就緒隊列末尾。同時系統(tǒng)選擇另進(jìn)程排在就緒隊列末尾。同時系統(tǒng)選擇另 一個進(jìn)程運行。一個進(jìn)程運行。4.基于時間片的輪轉(zhuǎn)調(diào)度算法簡單輪轉(zhuǎn)法：簡單輪轉(zhuǎn)法： 系統(tǒng)將所有就緒進(jìn)程按系統(tǒng)將所有就緒進(jìn)程按FIFO規(guī)則排隊，按一規(guī)則排隊，按一定的時間間隔把處理機(jī)分配給隊列中的進(jìn)程。這定的時間間隔把處理機(jī)分配給隊列中的進(jìn)程。這樣，就緒隊列中所有進(jìn)程均可獲得一個時間片的樣，就緒隊列中所有進(jìn)程均可獲得一個時間片的處理機(jī)而運行

8、。處理機(jī)而運行。ABCDEABCDEABCEACE(a) q1(b) q412345678910 11 12 13 14 15 16 17tCq=1和和q=4時進(jìn)程的周轉(zhuǎn)時間時進(jìn)程的周轉(zhuǎn)時間1212101018181111171712129 916168 8131311.611.64 47 71212141418184 46 61010111114149 9處理機(jī)模擬調(diào)度算法的實現(xiàn)：處理機(jī)模擬調(diào)度算法的實現(xiàn)：1設(shè)定系統(tǒng)中有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程設(shè)定系統(tǒng)中有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程 控制塊表示?？刂茐K表示。2輸入每個進(jìn)程的輸入每個進(jìn)程的“優(yōu)先數(shù)優(yōu)先數(shù)”和和“要求運行時間要求運行時間

9、”。3為了調(diào)度方便，將五個進(jìn)程按給定的優(yōu)先數(shù)從大為了調(diào)度方便，將五個進(jìn)程按給定的優(yōu)先數(shù)從大 到小連成就緒隊列。用一單元指出隊列首進(jìn)程，到小連成就緒隊列。用一單元指出隊列首進(jìn)程， 用指針指出隊列的連接情況。用指針指出隊列的連接情況。4處理機(jī)調(diào)度總是選隊首進(jìn)程運行。采用動態(tài)優(yōu)先處理機(jī)調(diào)度總是選隊首進(jìn)程運行。采用動態(tài)優(yōu)先 數(shù)算法，進(jìn)程每運行一次優(yōu)先數(shù)就減數(shù)算法，進(jìn)程每運行一次優(yōu)先數(shù)就減“1”，同時，同時 將運行時間減將運行時間減“1”。5若要求運行時間為零，則將其狀態(tài)置為若要求運行時間為零，則將其狀態(tài)置為“結(jié)束結(jié)束”,且且 退出隊列。退出隊列。6運行所設(shè)計程序，顯示或打印逐次被選中進(jìn)程的運行所設(shè)計程

10、序，顯示或打印逐次被選中進(jìn)程的 進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。#include #include struct PCB char name10;int priority,time;struct PCB *next;*k;struct LinkQueue PCB * front;PCB * rear;/隊列初始化隊列初始化LinkQueue init()LinkQueue Q;PCB * p;p=(PCB *)malloc(sizeof(PCB);if(p) Q.front=Q.rear=p;Q.front-next=NULL;return Q; els

11、eprintf(隊列初始化失敗，程序運行終止隊列初始化失敗，程序運行終止! n);exit(0); /插入新進(jìn)程，使優(yōu)先數(shù)從大到小排列插入新進(jìn)程，使優(yōu)先數(shù)從大到小排列LinkQueue sort(LinkQueue Q,PCB *p) PCB * temp1;PCB * temp2;if(Q.rear=Q.front) Q.front-next=p;Q.rear=p; else temp1=Q.front; temp2=temp1-next; while(temp2-priority=p-priority & temp2-next!=NULL) temp1=temp2; temp2=t

12、emp1-next; if(temp2-next=NULL & temp2-priority=p-priority) temp2-next=p; Q.rear=p; else p-next=temp1-next; temp1-next=p; return Q;LinkQueue input(LinkQueue Q) /* 建立進(jìn)程控制塊函數(shù)建立進(jìn)程控制塊函數(shù)*/ int i; for(i=1;iname); printf(n 輸入進(jìn)程優(yōu)先數(shù)輸入進(jìn)程優(yōu)先數(shù):); scanf(%d,&k-priority); printf(n 輸入進(jìn)程運行時間輸入進(jìn)程運行時間:); scanf(%

13、d,&k-time); printf(n); k-next=NULL; Q=sort(Q,k); /* 調(diào)用調(diào)用sort函數(shù)函數(shù)*/ return Q;LinkQueue running(LinkQueue Q)/* 建立進(jìn)程就緒函數(shù)建立進(jìn)程就緒函數(shù)(進(jìn)程運行時間到進(jìn)程運行時間到,置就緒狀態(tài)置就緒狀態(tài)*/ if(k-time=0) printf(運行后進(jìn)程運行后進(jìn)程 %s 已完成已完成 狀態(tài)為狀態(tài)為結(jié)束結(jié)束.n,k-name); free(k); else (k-priority)-; (k-time)-; printf(運行后優(yōu)先數(shù)運行后優(yōu)先數(shù):%d 需要運行時間需要運行時間:%dn

14、,k-priority,k-time); Q=sort(Q,k); /*調(diào)用調(diào)用sort函數(shù)函數(shù)*/ return Q; void check(LinkQueue Q) /* 建立進(jìn)程查看函數(shù)建立進(jìn)程查看函數(shù) */ PCB *pr; pr=(PCB *)malloc(sizeof(PCB);pr=Q.front-next;printf(n * 輸入的五個過程為輸入的五個過程為:n); while(pr!=NULL) printf(n 進(jìn)程名進(jìn)程名:%s 狀態(tài)狀態(tài):就緒就緒 優(yōu)先數(shù)優(yōu)先數(shù):%d 需要運行時間需要運行時間:%dn, pr-name,pr-priority,pr-time); pr=pr-next; void main( ) int h=0;LinkQue