第次 進(jìn)程調(diào)模擬

1、操作系統(tǒng)課程實(shí)驗(yàn)報(bào)告姓名學(xué)號(hào)系計(jì)算機(jī)科學(xué)與技術(shù)任課教師賀輝指導(dǎo)教師賀輝評(píng)閱教師賀輝實(shí)驗(yàn)地點(diǎn)實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)編號(hào)與實(shí)驗(yàn)名稱(chēng)：第5次 進(jìn)程調(diào)度模擬實(shí)驗(yàn)?zāi)康模哼M(jìn)程調(diào)度是處理機(jī)管理的核心內(nèi)容。通過(guò)本實(shí)驗(yàn)可以加深理解有關(guān)進(jìn)程控制塊（進(jìn)程的概念）、進(jìn)程隊(duì)列的概念及進(jìn)程調(diào)度算法的理解并體會(huì)和了解優(yōu)先級(jí)和時(shí)間片輪轉(zhuǎn)調(diào)度算法的具體實(shí)施辦法。實(shí)驗(yàn)內(nèi)容及要求（詳見(jiàn)實(shí)驗(yàn)講義）：本實(shí)驗(yàn)要求用C語(yǔ)言【也可以是其它你擅長(zhǎng)的程序設(shè)計(jì)語(yǔ)言】編寫(xiě)和調(diào)試一個(gè)簡(jiǎn)單的進(jìn)程調(diào)度模擬程序。須在實(shí)驗(yàn)報(bào)告中給出詳細(xì)算法描述和流程圖。設(shè)計(jì)進(jìn)程控制塊PCB表結(jié)構(gòu)，分別適用于優(yōu)先級(jí)調(diào)度算法和輪轉(zhuǎn)調(diào)度算法。編制兩種進(jìn)程調(diào)度算法：1）優(yōu)先級(jí)調(diào)度；2）輪轉(zhuǎn)調(diào)

2、度建立進(jìn)程就緒隊(duì)列。對(duì)兩種不同算法編制入隊(duì)子程序【重點(diǎn)！】。實(shí)驗(yàn)用到的軟件（：）Vs，word實(shí)驗(yàn)內(nèi)容、關(guān)鍵步驟（流程圖、代碼等）及結(jié)果分析（70分）1.優(yōu)先級(jí)調(diào)度（1）基本思想：為了防止高優(yōu)先級(jí)進(jìn)程無(wú)休止地運(yùn)行下去，調(diào)度程序可以在每個(gè)時(shí)鐘滴答（即每個(gè)時(shí)鐘中斷）降低當(dāng)前進(jìn)程的優(yōu)先級(jí)。（2）實(shí)現(xiàn)：即給每個(gè)進(jìn)程被賦予一個(gè)優(yōu)先級(jí)，允許優(yōu)先級(jí)最高的可運(yùn)行進(jìn)程先運(yùn)行。進(jìn)程之間再以優(yōu)先級(jí)的高低，從高到低進(jìn)行排序，之后開(kāi)始執(zhí)行進(jìn)程，在規(guī)定的時(shí)間片當(dāng)中，如果進(jìn)程能夠執(zhí)行完畢，就從進(jìn)程隊(duì)列當(dāng)中移除該進(jìn)程，否則的話，減小該進(jìn)程的優(yōu)先級(jí)（運(yùn)行一次，優(yōu)先級(jí)-8），插入進(jìn)程隊(duì)列當(dāng)中，整個(gè)進(jìn)程隊(duì)列依舊是按照優(yōu)先級(jí)從高到低

3、的順序進(jìn)行排序，之后繼續(xù)執(zhí)行，判斷進(jìn)程隊(duì)列是否為空，如果不為空，則就緒隊(duì)列的首進(jìn)程投入運(yùn)行。最后直到進(jìn)程隊(duì)列為空，結(jié)束。（3）算法流程圖優(yōu)先級(jí)算法使用優(yōu)先級(jí)算法給新加的五個(gè)進(jìn)程進(jìn)行cpu處理。初始化PCB，輸入進(jìn)程號(hào)及進(jìn)程所需的cpu運(yùn)行時(shí)間各進(jìn)程由安照優(yōu)先級(jí)程度高到低排序（優(yōu)先級(jí)=100-所需cpu運(yùn)行時(shí)間）就緒隊(duì)列為空將首進(jìn)程置入到就緒隊(duì)列中，并運(yùn)行。進(jìn)程狀態(tài)變?yōu)镽。就緒隊(duì)列為空進(jìn)程開(kāi)始運(yùn)行，當(dāng)時(shí)間時(shí)間片使用完，cpu的使用時(shí)間+1,進(jìn)程所需的時(shí)間-1，優(yōu)先級(jí)-8，狀態(tài)置為w。判斷進(jìn)程所需cpu時(shí)間是否等于運(yùn)行時(shí)間。如果等于，那么進(jìn)程被cpu處理完，進(jìn)程狀態(tài)變?yōu)镕，將cpu資源分配給其他進(jìn)

4、程。重新對(duì)進(jìn)程排序，按照進(jìn)程的優(yōu)先級(jí)高低。如果所有進(jìn)程狀態(tài)都為F，隊(duì)列為空，即表明所有進(jìn)程都被cpu處理完，結(jié)束。（4）步驟說(shuō)明1）char algo;printf("選擇算法：P/R(優(yōu)先級(jí)算法/時(shí)間片輪轉(zhuǎn)算法)；輸入'e'結(jié)束n");scanf_s("%c", &algo);printf("輸入進(jìn)程數(shù)：n");scanf_s("%d", &N);選擇算法，進(jìn)程數(shù)量2）for (i = 1; i <= N; i+)p = (PCB *)malloc(sizeof(PCB);c

5、in >> na;cin >> time;strcpy_s(p->name, na);p->cputime = 0;p->needtime = time;p->state = 'w'p->prio = 100 - time;if (ready != NULL)insert1(p);elsep->next = ready;ready = p;初始化并創(chuàng)建進(jìn)程，排序3）run = ready;ready = ready->next;run->state = 'R'將首進(jìn)程進(jìn)入就緒隊(duì)列4）run-

6、>cputime = run->cputime + 1;run->needtime = run->needtime - 1;run->prio = run->prio - 8;if (ready != NULL)change(run);elserun->next = ready;ready = run;run = ready;ready = ready->next;run->state = 'R'進(jìn)程運(yùn)行及重新排序。5）if (run->needtime = 0)run->next = finish;finish

7、 = run;run->state = 'F'run = NULL;if (ready != NULL)firstin();進(jìn)程處理完，將cpu資源交予其他進(jìn)程。（5）子函數(shù)關(guān)系圖先選擇優(yōu)先級(jí)算法，再輸入進(jìn)程數(shù)傳入create1函數(shù)。再利用create1創(chuàng)建進(jìn)程。將新建進(jìn)程傳入insert1()函數(shù)進(jìn)行從優(yōu)先級(jí)程度高到低排序（優(yōu)先級(jí)=100-所需cpu運(yùn)行時(shí)間）將進(jìn)程傳進(jìn)prt1()函數(shù)輸出信息。將進(jìn)程傳進(jìn)prt()函數(shù)。將進(jìn)程傳進(jìn)prt2()函數(shù)輸出排序后，進(jìn)程的所有信息。跳轉(zhuǎn)到priority()函數(shù)，并傳入?yún)?shù)即進(jìn)程數(shù)量。進(jìn)程開(kāi)始運(yùn)行，時(shí)間片使用完，cpu的使用時(shí)間

8、+1,進(jìn)程所需的時(shí)間-1，優(yōu)先級(jí)-8，狀態(tài)置為w。并判斷進(jìn)程是否被處理完，處理完將cpu資源給予其他進(jìn)程。判斷進(jìn)程所需cpu時(shí)間是否等于運(yùn)行時(shí)間。如果等于，那么進(jìn)程被cpu處理完，進(jìn)程狀態(tài)變?yōu)镕，將cpu資源分配給其他進(jìn)程。將進(jìn)程傳入change（）函數(shù)，重新對(duì)進(jìn)程排序，按照進(jìn)程的優(yōu)先級(jí)高低。（6）結(jié)果結(jié)果分析：和優(yōu)先級(jí)算法結(jié)果一樣。2. 輪轉(zhuǎn)調(diào)度基本思想：每個(gè)進(jìn)程被分配一個(gè)時(shí)間段，稱(chēng)為時(shí)間片，即允許改進(jìn)程在該時(shí)間段中運(yùn)行。如果時(shí)間片結(jié)束時(shí)改進(jìn)程還在運(yùn)行，則將剝奪cpu并分配給另一個(gè)進(jìn)程。如果該進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則cpu立即進(jìn)行切換。實(shí)現(xiàn)：每個(gè)進(jìn)程都會(huì)被分配一個(gè)相同的時(shí)間片，并按照

9、先來(lái)先服務(wù)進(jìn)行排序，允許該進(jìn)程在該時(shí)間段中運(yùn)行。如果在時(shí)間片結(jié)束時(shí)該進(jìn)程還在運(yùn)行，則將剝奪CPU并分配給另一個(gè)進(jìn)程。如果該進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則CPU立即進(jìn)行切換。其中每個(gè)進(jìn)程分配的相同時(shí)間片的大小設(shè)計(jì)為2，一個(gè)進(jìn)程如果在該時(shí)間片當(dāng)中沒(méi)有結(jié)束，則將會(huì)被強(qiáng)制結(jié)束，將CPU分配給下一個(gè)進(jìn)程，該進(jìn)程將會(huì)被插入整個(gè)進(jìn)程隊(duì)列的最后，如果一個(gè)進(jìn)程在規(guī)定的時(shí)間結(jié)束，則將CPU立刻分配給下一個(gè)進(jìn)程，該進(jìn)程從進(jìn)程隊(duì)列中移除。（3）算法流程圖時(shí)間輪轉(zhuǎn)算法先來(lái)先服務(wù)算法初始化PCB，輸入進(jìn)程號(hào)及進(jìn)程所需的cpu運(yùn)行時(shí)間先來(lái)先創(chuàng)建，先排序，后創(chuàng)建的插在隊(duì)列后就緒隊(duì)列為空將首進(jìn)程置入到就緒隊(duì)列中，并運(yùn)行。進(jìn)程

10、狀態(tài)變?yōu)镽。進(jìn)程開(kāi)始運(yùn)行，當(dāng)時(shí)間時(shí)間片使用完，占用cpu時(shí)間+2,進(jìn)程所需的時(shí)間-2，計(jì)數(shù)+1，時(shí)間片長(zhǎng)度不變，狀態(tài)置為w。并將進(jìn)程置于隊(duì)尾。判斷進(jìn)程所需cpu時(shí)間是否等于計(jì)數(shù)*2。如果等于，那么進(jìn)程被cpu處理完，進(jìn)程狀態(tài)變?yōu)镕，將cpu資源分配給其他進(jìn)程。進(jìn)程被插入到隊(duì)尾。如果所有進(jìn)程狀態(tài)都為F，隊(duì)列為空，即表明所有進(jìn)程都被cpu處理完，結(jié)束。（4） 步驟說(shuō)明1）char algo;printf("選擇算法：P/R(優(yōu)先級(jí)算法/時(shí)間片輪轉(zhuǎn)算法)；輸入'e'結(jié)束n");scanf_s("%c", &algo);printf(&q

11、uot;輸入進(jìn)程數(shù)：n");scanf_s("%d", &N);選擇算法，進(jìn)程數(shù)量2）p = (PCB *)malloc(sizeof(PCB);cin >> na;cin >> time;strcpy_s(p->name, na);p->cputime = 0;p->needtime = time;p->count = 0;p->state = 'w'p->round = 2;if (ready != NULL)insert2(p);elsep->next = ready;

12、ready = p;tail = p;初始化并創(chuàng)建進(jìn)程，按照先來(lái)先服務(wù)排序3）run = ready;ready = ready->next;run->state = 'R'將首進(jìn)程進(jìn)入就緒隊(duì)列4）run->cputime = run->cputime + 2;run->needtime = run->needtime - 2;if (run->needtime < 0)run->needtime = 0;run->count = run->count + 1;prt(alg);進(jìn)程運(yùn)行5）if (run->

13、;needtime = 0)run->next = finish;finish = run;run->state = 'F'run = NULL;if (ready != NULL)firstin();elseif (run->count*2 = run->round)run->count = 0;if (ready != NULL)run->state = 'w'insert2(run);firstin();處理過(guò)的或者處理完的都插入隊(duì)尾。當(dāng)所有都為F時(shí)，結(jié)束。（5）子函數(shù)關(guān)系圖選擇輪轉(zhuǎn)調(diào)度算法，再輸入進(jìn)程數(shù)傳入create

14、2函數(shù)。再利用create2創(chuàng)建進(jìn)程。將新建進(jìn)程傳入insert2()函數(shù)。按照進(jìn)程先創(chuàng)建先服務(wù)，進(jìn)行排序。將進(jìn)程傳進(jìn)prt1()函數(shù)輸出信息。將進(jìn)程傳進(jìn)prt()函數(shù)將進(jìn)程傳進(jìn)prt2()函數(shù)輸出排序后，進(jìn)程的所有信息。跳轉(zhuǎn)到roundrun()函數(shù)，并傳入?yún)?shù)即進(jìn)程數(shù)量。進(jìn)程開(kāi)始運(yùn)行，當(dāng)時(shí)間時(shí)間片使用完，占用cpu時(shí)間+2,進(jìn)程所需的時(shí)間-2，計(jì)數(shù)+1，時(shí)間片長(zhǎng)度不變，狀態(tài)置為w。并將進(jìn)程置于隊(duì)尾。并判斷進(jìn)程是否被處理完。將處理完的進(jìn)程，由函數(shù)firstin()將cpu資源給予其他進(jìn)程，改變其他狀態(tài)變?yōu)榫途w狀態(tài)。通過(guò)傳入處理完進(jìn)程到insert2()函數(shù)，并將此進(jìn)程置于隊(duì)尾。（6） 結(jié)果結(jié)

15、果分析：和時(shí)間片輪轉(zhuǎn)調(diào)度算法結(jié)果一樣。3.代碼/ ConsoleApplication4.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include "stdio.h"#include "stdlib.h"#include "string.h"#include "ctype.h"#include "conio.h"#include "malloc.h"#include <iostream>using nam

16、espace std;typedef struct nodechar name10;int prio;int round;int cputime;int needtime;int count;char state;struct node *next;PCB;PCB *finish, *ready, *tail, *run;int N;void firstin()run = ready;run->state = 'R'ready = ready->next;void prt1(char a)if (toupper(a) = 'P')printf(&qu

17、ot; 進(jìn)程號(hào) 已占用CPU時(shí)間 所需時(shí)間 優(yōu)先數(shù) 狀態(tài)n");elseprintf(" 進(jìn)程號(hào) 已占用CPU時(shí)間 所需時(shí)間 計(jì)數(shù) 時(shí)間片長(zhǎng)度 狀態(tài)n");void prt2(char a, PCB *q)if (toupper(a) = 'P')printf(" %-10s%-15d%-10d%-7d %cn", q->name,q->cputime, q->needtime, q->prio, q->state);elseprintf(" %-12s%-12d%-12d%-12d%-1

18、2d %-cn", q->name,q->cputime, q->needtime, q->count, q->round, 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;getchar();void insert1

19、(PCB *q)PCB *p1, *s, *r;int b;s = q;p1 = ready;r = p1;b = 1;while (p1 != NULL) && b)if (p1->prio >= s->prio)r = p1;p1 = p1->next;elseb = 0;if (r != p1)r->next = s;s->next = p1;elses->next = p1;ready = s;void insert2(PCB *p2)tail->next = p2;tail = p2;p2->next = NULL

20、;void change(PCB *q)PCB *p1, *s, *r;int b;q->state = 'w's = q;p1 = ready;r = p1;b = 1;while (p1 != NULL) && b)if (p1->prio >= s->prio)r = p1;p1 = p1->next;elseb = 0;if (r != p1)r->next = s;s->next = p1;elses->next = p1;ready = s;void create1(char alg, int N)PC

21、B *p;int i, time;char na10;ready = NULL;finish = NULL;run = NULL;printf("輸入進(jìn)程號(hào)、運(yùn)行時(shí)間：n");for (i = 1; i <= N; i+)p = (PCB *)malloc(sizeof(PCB);cin >> na;cin >> time;strcpy_s(p->name, na);p->cputime = 0;p->needtime = time;p->state = 'w'p->prio = 100 - tim

22、e;if (ready != NULL)insert1(p);elsep->next = ready;ready = p;printf(" 優(yōu)先數(shù)算法輸出信息：n");printf("*n");prt(alg);run = ready;ready = ready->next;run->state = 'R'void create2(char alg, int N)PCB *p;int i, time;char na10;ready = NULL;finish = NULL;run = NULL;printf("

23、輸入進(jìn)程號(hào)、運(yùn)行時(shí)間：n");for (i = 1; i <= N; i+)p = (PCB *)malloc(sizeof(PCB);cin >> na;cin >> time;strcpy_s(p->name, na);p->cputime = 0;p->needtime = time;p->count = 0;p->state = 'w'p->round = 2;if (ready != NULL)insert2(p);elsep->next = ready;ready = p;tail =

24、 p;printf(" 輪轉(zhuǎn)調(diào)度算法輸出信息n");printf("*n");prt(alg);run = ready;ready = ready->next;run->state = 'R'void priority(char alg)while (run != NULL)run->cputime = run->cputime + 1;run->needtime = run->needtime - 1;run->prio = run->prio - 8;if (run->needti

25、me = 0)run->next = finish;finish = run;run->state = 'F'run = NULL;if (ready != NULL)firstin();if (ready != NULL)change(run);elserun->next = ready;ready = run;run = ready;ready = ready->next;run->state = 'R'prt(alg);void roundrun(char alg)while (run != NULL)run->cputime = run->cputime + 2;run->needtime = run->needt