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

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

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

3、理器調(diào)度程序之前，為每個(gè)進(jìn)程任意確定它的“優(yōu)先數(shù)”和“要求運(yùn)行時(shí)間”。（3）為了調(diào)度方便，把五個(gè)進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊(duì)列。用一單元指出隊(duì)首進(jìn)程，用指針指出隊(duì)列的連接情況。例： 隊(duì)首標(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)度總是選隊(duì)首進(jìn)程運(yùn)行。采用動(dòng)態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運(yùn)行一次優(yōu)先數(shù)就減“1”。由于本實(shí)驗(yàn)是模擬處理器調(diào)度，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：優(yōu)先數(shù)-1要求運(yùn)行時(shí)間-1來模擬進(jìn)程的

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

5、的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過程。例如，下面的運(yùn)行結(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è)計(jì)一個(gè)按時(shí)間片輪轉(zhuǎn)法實(shí)現(xiàn)處理器調(diào)度的程序?！咎崾尽浚?）假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表。進(jìn)程控制塊的格式為：進(jìn)程名指針要求運(yùn)行時(shí)間已運(yùn)行時(shí)間狀態(tài)其中，l 進(jìn)程名作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程

10、名分別為Q1，Q2，Q3，Q4，Q5。l 指針進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址，最后一個(gè)進(jìn)程的指針指出第一個(gè)進(jìn)程的進(jìn)程控制塊首地址。l 要求運(yùn)行時(shí)間假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。l 已運(yùn)行時(shí)間假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為“0”。l 狀態(tài)有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。（2）每次運(yùn)行所設(shè)計(jì)的處理器調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的“要求運(yùn)行時(shí)間”。（3）把五個(gè)進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出隊(duì)列連接情況。另用一標(biāo)志單元記錄輪到運(yùn)行的進(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)程運(yùn)行。由于本實(shí)驗(yàn)是模擬處理器調(diào)度的功能，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：已運(yùn)行時(shí)間+1來模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過一個(gè)單位的時(shí)間。請(qǐng)同學(xué)注意：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須置上該進(jìn)程可以運(yùn)行的時(shí)間片值，以及恢復(fù)進(jìn)程的現(xiàn)場(chǎng)，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行滿一個(gè)時(shí)間片。在這時(shí)省去了這些工作，僅

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

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

14、對(duì)處理機(jī)調(diào)度的作用和工作原理的理解。（2）進(jìn)一步認(rèn)識(shí)并發(fā)執(zhí)行的實(shí)質(zhì)。二、實(shí)驗(yàn)題目 設(shè)計(jì)一個(gè)按優(yōu)先權(quán)調(diào)度算法實(shí)現(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(" 請(qǐng)輸入進(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("-請(qǐng)輸入進(jìn)程名優(yōu)先級(jí)

18、運(yùn)行時(shí)間 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)先級(jí)運(yùn)行時(shí)間 cpu時(shí)間狀態(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