FPF和RR調(diào)度算法

1、鄭州輕工業(yè)學(xué)院本科實(shí)驗(yàn)報(bào)告設(shè)計(jì)題目： 實(shí)現(xiàn)FPF和RR調(diào)度算法 學(xué)生姓名： 李洋 系 別： 計(jì)算機(jī)與通信工程學(xué)院 專 業(yè)： 網(wǎng)絡(luò)運(yùn)維 班 級(jí)： 13-03 學(xué) 號(hào)： 521507110314 指導(dǎo)教師： 吳慶崗 2021 年 11 月 18 日一、實(shí)驗(yàn)?zāi)康木帉?xiě)程序，實(shí)現(xiàn)FPF和RR算法，模擬進(jìn)程調(diào)度過(guò)程，加深對(duì)作業(yè)調(diào)度的理解。二、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)FPF和RR調(diào)度算法。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)PCB，進(jìn)程就緒隊(duì)列 算法實(shí)現(xiàn)與模擬排序、調(diào)度 輸出調(diào)度結(jié)果，展示調(diào)度過(guò)程并解釋三、實(shí)驗(yàn)要求1. 設(shè)計(jì)進(jìn)程控制塊(PCB)的數(shù)據(jù)結(jié)構(gòu) 應(yīng)包含實(shí)驗(yàn)必須的數(shù)據(jù)項(xiàng)，如進(jìn)程ID、需要的效勞時(shí)間、進(jìn)入系統(tǒng)時(shí)間、完成時(shí)間、周轉(zhuǎn)時(shí)間、

2、優(yōu)先權(quán)、進(jìn)程狀態(tài)R-運(yùn)行，W-等待，以及實(shí)驗(yàn)者認(rèn)為有必要的其他數(shù)據(jù)項(xiàng)。2. 實(shí)現(xiàn)排序算法將就緒隊(duì)列中的進(jìn)程排序 RR：只需在開(kāi)始時(shí)排序，按FCFS策略將進(jìn)程依次插入就緒隊(duì)列。開(kāi)始運(yùn)行后不再需要排序，按RR策略將每一個(gè)剛剛運(yùn)行完一個(gè)時(shí)間片的進(jìn)程插入到隊(duì)尾。 FPF：每次調(diào)度前排序，按計(jì)算所得的動(dòng)態(tài)優(yōu)先權(quán)排成有序隊(duì)列，最高優(yōu)先權(quán)排進(jìn)程在隊(duì)首，優(yōu)先權(quán)相同的進(jìn)程按FCFS策略排隊(duì)。3. 實(shí)現(xiàn)RR調(diào)度過(guò)程模擬每個(gè)進(jìn)程用一個(gè)PCB表示，按FCFS策略排成就緒隊(duì)列，按照固定的周期循環(huán)調(diào)度。選擇隊(duì)首的進(jìn)程，將其從就緒隊(duì)列移出，修改其狀態(tài)為R。經(jīng)過(guò)一個(gè)時(shí)間片，如果正在執(zhí)行的進(jìn)程沒(méi)有執(zhí)行完，修改其狀態(tài)為W，插入到

3、就緒隊(duì)列尾部。如果執(zhí)行完畢，計(jì)算其周轉(zhuǎn)時(shí)間。進(jìn)行下一次調(diào)度去往第步，直到就緒隊(duì)列為空。4. 實(shí)現(xiàn)FPF調(diào)度過(guò)程模擬每個(gè)進(jìn)程用一個(gè)PCB表示。計(jì)算動(dòng)態(tài)優(yōu)先權(quán)，按優(yōu)先權(quán)上下排入就緒隊(duì)列，如果相同，那么按FCFS排隊(duì)。系統(tǒng)開(kāi)始時(shí)調(diào)度，每個(gè)進(jìn)程結(jié)束時(shí)進(jìn)行調(diào)度。選擇隊(duì)首的作業(yè)，將其從后備隊(duì)列移出計(jì)算選中作業(yè)的周轉(zhuǎn)時(shí)間進(jìn)程運(yùn)行過(guò)程，在本實(shí)驗(yàn)中，無(wú)需實(shí)現(xiàn)，可認(rèn)為就緒隊(duì)列上的進(jìn)程一但被調(diào)度程序選出，就順利運(yùn)行結(jié)束進(jìn)行下一次調(diào)度去往第步5.實(shí)現(xiàn)結(jié)果輸出 輸出進(jìn)程狀態(tài)表，展示調(diào)度過(guò)程 初始進(jìn)程狀態(tài)未調(diào)度時(shí) 每次調(diào)度后的進(jìn)程狀態(tài)6.撰寫(xiě)實(shí)驗(yàn)報(bào)告 包含實(shí)驗(yàn)要求中14項(xiàng)內(nèi)容，要求有設(shè)計(jì)圖結(jié)構(gòu)圖/流程圖和源代碼。 注明使

4、用的編程語(yǔ)言和環(huán)境?？记绊氈?實(shí)驗(yàn)中注重實(shí)現(xiàn)算法本質(zhì)高優(yōu)先權(quán)優(yōu)先FPF，時(shí)間片輪轉(zhuǎn)RR。 兩個(gè)算法可以選做一個(gè)，量力而行，鼓勵(lì)多做。 FPF算法也適用于作業(yè)調(diào)度。關(guān)于作業(yè)調(diào)度和進(jìn)程調(diào)度的區(qū)別，只要求概念上理解清楚，不要求實(shí)現(xiàn)。#include <stdio.h>#include <stdlib.h>struct PCB char p_name20; int p_priority; int p_needTime; int p_runTime; char p_state; struct PCB* next;void HighPriority();void RoundRobi

5、n();void Information();char Choice();struct PCB* SortList(PCB* HL);int main() Information(); char choice = Choice(); switch(choice) case '1': system("cls"); HighPriority(); break; default: break; system("pause"); return 0;void Information() printf(" 按回車鍵進(jìn)入演示程序")

6、; getchar(); system("cls");char Choice() printf("nn"); printf(" 1.演示最高優(yōu)先數(shù)優(yōu)先算法。"); printf(" 按1繼續(xù):"); char ch = getchar(); return ch; system("cls");void HighPriority() struct PCB *processes, *pt; /pt作為臨時(shí)節(jié)點(diǎn)來(lái)創(chuàng)立鏈表，使用for語(yǔ)句，限制進(jìn)程數(shù)為5個(gè) processes = pt = (struct

7、 PCB*)malloc(sizeof(struct PCB); for (int i = 0; i != 5; +i) struct PCB *p = (struct PCB*)malloc(sizeof(struct PCB); printf("進(jìn)程號(hào)No.%d：n", i); printf("輸入進(jìn)程名："); scanf("%s", p->p_name); printf("輸入進(jìn)程優(yōu)先數(shù)："); scanf("%d", &p->p_priority); printf(

8、"輸入進(jìn)程運(yùn)行時(shí)間："); scanf("%d", &p->p_needTime); p->p_runTime = 0; p->p_state = 'W' p->next = NULL; pt->next = p; pt = p; printf("nn"); getchar(); /接受回車 /processes作為頭結(jié)點(diǎn)來(lái)存儲(chǔ)鏈表 processes = processes->next; int cases = 0; struct PCB *psorted = proces

9、ses; while (1) +cases; pt = processes; /對(duì)鏈表按照優(yōu)先數(shù)排序 /psorted用來(lái)存放排序后的鏈表 psorted = SortList(psorted); printf("The execute number: %dnn", cases); printf("* 當(dāng)前正在運(yùn)行的進(jìn)程是：%sn", psorted->p_name); psorted->p_state = 'R' printf("qname state super ndtime runtimen"); p

10、rintf("%st%ct%dt%dt%dtnn", psorted->p_name, psorted->p_state, psorted->p_priority, psorted->p_needTime, psorted->p_runTime); pt->p_state = 'W' psorted->p_runTime+; psorted->p_priority-; printf("* 當(dāng)前就緒狀態(tài)的隊(duì)列為：nn"); /pt指向已經(jīng)排序的隊(duì)列 pt = psorted->next;

11、 while (pt != NULL) printf("qname state super ndtime runtimen"); printf("%st%ct%dt%dt%dtnn", pt->p_name, pt->p_state, pt->p_priority, pt->p_needTime, pt->p_runTime); pt = pt->next; /pt指向已經(jīng)排序的鏈表，判斷鏈表是否有已用時(shí)間啊等于需要時(shí)間的 pt = psorted; struct PCB *ap; ap = NULL; /ap指向pt

12、的前一個(gè)節(jié)點(diǎn) while (pt != NULL) if (pt->p_needTime = pt->p_runTime) if (ap = NULL) pt = psorted->next; psorted = pt; else ap->next = pt->next; ap = pt; pt = pt->next; if (psorted->next = NULL) break; getchar(); struct PCB* SortList(PCB* HL) struct PCB* SL; SL = (struct PCB*)malloc(sizeof(struct PCB); SL = NULL; struct PCB* r = HL; while (r != NULL) struct PCB* t = r->next; struct PCB* cp = SL; struct PCB* ap = NULL; whi