操作系統(tǒng)實驗之處理機(jī)調(diào)度題目及代碼實現(xiàn)

1、操作系統(tǒng)實驗試題：處理機(jī)調(diào)度及其實現(xiàn)一、實驗試題目的：加深對處理機(jī)調(diào)度的作用和工作原理的理解，實現(xiàn)處理機(jī)并發(fā)執(zhí)行。二、實驗試題要求：試題一：設(shè)計一個按優(yōu)先權(quán)調(diào)度算法實現(xiàn)處理器調(diào)度的程序。試題二：設(shè)計一個按時間片輪轉(zhuǎn)法實現(xiàn)處理器調(diào)度的程序。本實驗試題有兩個題，學(xué)生可選做其中的一題。三、實驗試題報告要求：1. 設(shè)計實現(xiàn)實驗的主要思路或者實驗方案；2. 給出實驗步驟，及實現(xiàn)代碼；3. 撰寫實驗報告并配以實現(xiàn)的插圖；4. 對實驗運行結(jié)果進(jìn)行調(diào)試，分析性能?！咎崾尽浚?）假定系統(tǒng)有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊PCB來代表，進(jìn)程控制塊的格式為：進(jìn)程名指針要求運行時間優(yōu)先數(shù)狀態(tài)其中，l 進(jìn)程名作為進(jìn)

2、程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程名分別為P1，P2，P3，P4，P5。l 指針按優(yōu)先數(shù)的大小把五個進(jìn)程連成隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程中的指針為“0”。l 要求運行時間假設(shè)進(jìn)程需要運行的單位時間數(shù)。l 優(yōu)先數(shù)賦予進(jìn)程的優(yōu)先權(quán)，調(diào)度時總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。l 狀態(tài)可假設(shè)有三種狀態(tài)，“就緒”狀態(tài)（ready）、“運行”狀態(tài)（working）和“結(jié)束”狀態(tài)（finish）。五個進(jìn)程的初始狀態(tài)都為“就緒”，用“R”表示；當(dāng)進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示；當(dāng)進(jìn)程被選中開始運行但尚未結(jié)束時，它的狀態(tài)為“運行”，用“W”表示。（2）在每次運行你所設(shè)計的處

3、理器調(diào)度程序之前，為每個進(jìn)程任意確定它的“優(yōu)先數(shù)”和“要求運行時間”。（3）為了調(diào)度方便，把五個進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊列。用一單元指出隊首進(jìn)程，用指針指出隊列的連接情況。例： 隊首標(biāo)志 K2 K1P1 K2P2 K3P3 K4P4 K5P5 0 K4 K5 K3 K1 2 3 1 2 4 1 5 3 4 2 R R R R R PCB1 PCB2 PCB3 PCB4 PCB5 （4）處理器調(diào)度總是選隊首進(jìn)程運行。采用動態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運行一次優(yōu)先數(shù)就減“1”。由于本實驗是模擬處理器調(diào)度，所以，對被選中的進(jìn)程并不實際的啟動運行，而是執(zhí)行：優(yōu)先數(shù)-1要求運行時間-1來模擬進(jìn)程的

4、一次運行。提醒注意的是：在實際的系統(tǒng)中，當(dāng)一個進(jìn)程被選中運行時，必須恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運行，直到出現(xiàn)等待事件或運行結(jié)束。在這里省去了這些工作。（5）進(jìn)程運行一次后，若要求運行時間¹0，則再將它加入隊列（按優(yōu)先數(shù)大小插入，且置隊首標(biāo)志）；若要求運行時間=0，則把它的狀態(tài)修改成“結(jié)束”（E），且退出隊列。（6）若“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。（7）在所設(shè)計的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名以及運行一次后進(jìn)程隊列的變化。（8）為五個進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運行時間”，啟動所設(shè)計

5、的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。例如，下面的運行結(jié)果示意：INPUT NAME , NEEDTIME AND PRIORITYP1 2 1P2 3 5P3 1 3P4 2 4P5 4 2OUTPUT OF PRIORITY：CPUTIME:0NAME CPUTIME NEEDTIME PRIORITY STATE P1 0 2 1 ready P2 0 3 5 ready P3 0 1 3 ready P4 0 2 4 ready P5 0 4 2 ready CPUTIME:1 P1 0 2 1 ready P2 1 2 4 working P

6、3 0 1 3 ready P4 0 2 4 ready P5 0 4 2 ready CPUTIME:2 P1 0 2 1 ready P2 2 2 4 ready P3 0 1 3 ready P4 1 1 3 working P5 0 4 2 ready CPUTIME:3 P1 0 2 1 ready P2 3 1 3 working P3 0 1 3 ready P4 2 1 3 ready P5 0 4 2 ready CPUTIME:4 P1 0 2 1 ready P2 4 1 3 ready P3 1 0 2 finish P4 3 1 3 ready P5 0 4 2 re

7、ady CPUTIME:5 P1 0 2 1 ready P2 5 1 3 ready P3 1 0 2 finish P4 4 0 2 finish P5 0 4 2 ready CPUTIME:6 P1 0 2 1 ready P2 6 0 2 finish P3 1 0 2 finish P4 4 0 2 finish P5 0 4 2 ready CPUTIME:7 P1 0 2 1 ready P2 6 0 2 finish P3 1 0 2 finish P4 4 0 2 finish P5 1 3 1 working CPUTIME:8 P1 1 1 0 working P2 6

8、 0 2 finish P3 1 0 2 finish P4 4 0 2 finish P5 2 3 1 ready CPUTIME:8 P1 2 1 0 ready P2 6 0 2 finish P3 1 0 2 finish P4 4 0 2 finish P5 3 2 0 working CPUTIME:9 P1 3 0 -1 finish P2 6 0 2 finish P3 1 0 2 finish P4 4 0 2 finish P5 4 2 0 ready CPUTIME:10 P1 3 0 -1 finish P2 6 0 2 finish P3 1 0 2 finish P

9、4 4 0 2 finish P5 5 1 -1 working CPUTIME:11 P1 3 0 -1 finish P2 6 0 2 finish P3 1 0 2 finish P4 4 0 2 finish P5 6 0 -2 finish NAME RoundTime WaitingTimeP1 9 7P2 6 3P3 4 3P4 5 3P5 11 7 第二題：設(shè)計一個按時間片輪轉(zhuǎn)法實現(xiàn)處理器調(diào)度的程序?！咎崾尽浚?）假定系統(tǒng)有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊PCB來代表。進(jìn)程控制塊的格式為：進(jìn)程名指針要求運行時間已運行時間狀態(tài)其中，l 進(jìn)程名作為進(jìn)程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程

10、名分別為Q1，Q2，Q3，Q4，Q5。l 指針進(jìn)程按順序排成循環(huán)隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程的指針指出第一個進(jìn)程的進(jìn)程控制塊首地址。l 要求運行時間假設(shè)進(jìn)程需要運行的單位時間數(shù)。l 已運行時間假設(shè)進(jìn)程已經(jīng)運行的單位時間數(shù)，初始值為“0”。l 狀態(tài)有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。當(dāng)一個進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。（2）每次運行所設(shè)計的處理器調(diào)度程序前，為每個進(jìn)程任意確定它的“要求運行時間”。（3）把五個進(jìn)程按順序排成循環(huán)隊列，用指針指出隊列連接情況。另用一標(biāo)志單元記錄輪到運行的進(jìn)程。例如，當(dāng)前輪到P2執(zhí)行，

11、則有：標(biāo)志單元 K2 K1Q1 K2Q2 K3Q3 K4Q4 K5Q5 K2 K3 K4 K5 K1 2 3 1 2 4 1 0 0 0 0 R R R R R PCB1 PCB2 PCB3 PCB4 PCB5 （4）處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運行。由于本實驗是模擬處理器調(diào)度的功能，所以，對被選中的進(jìn)程并不實際的啟動運行，而是執(zhí)行：已運行時間+1來模擬進(jìn)程的一次運行，表示進(jìn)程已經(jīng)運行過一個單位的時間。請同學(xué)注意：在實際的系統(tǒng)中，當(dāng)一個進(jìn)程被選中運行時，必須置上該進(jìn)程可以運行的時間片值，以及恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運行，直到出現(xiàn)等待事件或運行滿一個時間片。在這時省去了這些工作，僅

12、用“已運行時間+1”來表示進(jìn)程已經(jīng)運行滿一個時間片。（5）進(jìn)程運行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個輪到運行的進(jìn)程。同時，應(yīng)判斷該進(jìn)程的要求運行時間與已運行時間，若該進(jìn)程的要求運行時間¹已運行時間，則表示它尚未執(zhí)行結(jié)束，應(yīng)待到下一輪時再運行。若該進(jìn)程的要求運行時間=已運行時間，則表示它已經(jīng)執(zhí)行結(jié)束，應(yīng)指導(dǎo)它的狀態(tài)修改成“結(jié)束”（E）且退出隊列。此時，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到前面一個進(jìn)程的指針位置。（6）若“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面的（4）和（5）的步驟，直到所有的進(jìn)程都成為“結(jié)束”狀態(tài)。（7）在所設(shè)計的程序中應(yīng)有顯示或打印語句

13、，能顯示或打印每次選中進(jìn)程的進(jìn)程名以及運行一次后進(jìn)程隊列的變化。（8）為五個進(jìn)程任意確定一組“要求運行時間”，啟動所設(shè)計的處理器調(diào)度程序，顯示或打印逐次被選中的進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。輸出要求與上述優(yōu)先權(quán)優(yōu)先調(diào)度輸出形式類似。五、思考題（1）處理機(jī)調(diào)度的目的？（2）你實現(xiàn)優(yōu)先權(quán)調(diào)度算法的思想？（3）你采用時間片輪轉(zhuǎn)法實現(xiàn)處理機(jī)調(diào)度的思想？（4）比較效率如何？六、實驗報告（1）實驗題目。（2）程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明。（3）流程圖。（4）實現(xiàn)的核心代碼。（5）按題目要求格式得到的程序運行時的初值和運行結(jié)果。 實驗報告 姓名：鄧濤 實驗內(nèi)容：處理器調(diào)度實驗一、 實驗?zāi)康模?）加深

14、對處理機(jī)調(diào)度的作用和工作原理的理解。（2）進(jìn)一步認(rèn)識并發(fā)執(zhí)行的實質(zhì)。二、實驗題目 設(shè)計一個按優(yōu)先權(quán)調(diào)度算法實現(xiàn)處理器調(diào)度的程序。 三、核心代碼#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct pb char pname5; char status8; int time; int pri; int cputime; struct pb *p; pbc,*pbcp; pbcp creatListHead();void sort(pbcp pbca);void attemper(

15、pbcp pbca);void mallocPbc(pbcp pbca,int num);void printPbc(pbcp pbca);int main() int i,j; pbcp pbcph; pbcph=creatListHead(); printf("-初始化進(jìn)程數(shù)據(jù)塊-nnn"); printf(" 請輸入進(jìn)程塊的數(shù)目： "); scanf("%d",&i); printf("n"); mallocPbc(pbcph,i); printf("-sort-:nnn"); s

16、ort(pbcph); printPbc( pbcph); for(j=0;j<11;j+) printf("-n"); attemper(pbcph); _sleep(1000); return 1;pbcp creatListHead() pbcp pbcph; if(NULL=(pbcph=(struct pb *)malloc(sizeof(pbc) ) printf("pbc head malloc errorn"); else strcpy(pbcph->pname,"head"); pbcph->p=N

17、ULL; pbcph->time=0; pbcph->pri=0; pbcph->cputime=0; strcpy(pbcph->status,"head"); return pbcph; void mallocPbc(pbcp pbca,int num) pbcp pbcptem; int i; for(i=0;i<num;i+) if(NULL=(pbcptem=( pbcp )malloc(sizeof(pbc) printf("pbc malloc errorn"); printf("-請輸入進(jìn)程名優(yōu)先級

18、運行時間 n "); scanf(" %s%d%d",pbcptem->pname,&pbcptem->pri,&pbcptem->time); pbcptem->p=NULL; strcpy(pbcptem->status,"ready"); pbcptem->cputime=0; pbca->p=pbcptem; pbca=pbca->p; void printPbc(pbcp pbca) pbcp pbcptem; pbcptem=pbca->p; while(pbcptem!=NULL) printf("n-進(jìn)程名優(yōu)先級運行時間 cpu時間狀態(tài) n"); printf("-%s %d %d %d %sn",pbcptem->pname,pbcptem->pri,pbcptem->time, pbcptem->cputime,pbcptem->status); pbcptem=pbcptem->p; void sort(pbcp pbca) pbcp p1,p2,p3,p4 ; p4=NULL; while(p4