操作系統(tǒng)課程設(shè)計(jì)報(bào)告進(jìn)程調(diào)度算法

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告_進(jìn)程調(diào)度算法 1實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)優(yōu)先權(quán)法和輪轉(zhuǎn)算法的模擬加深對(duì)進(jìn)程概念和進(jìn)程調(diào)度過(guò)程的理解，掌握進(jìn)程狀態(tài)之間的切換，同時(shí)掌握進(jìn)程調(diào)度算法的實(shí)現(xiàn)方法和技巧。2實(shí)驗(yàn)內(nèi)容1用c+語(yǔ)言來(lái)實(shí)現(xiàn)對(duì)n個(gè)進(jìn)程采用優(yōu)先權(quán)優(yōu)先算法以及輪轉(zhuǎn)算法的進(jìn)程調(diào)度。2每個(gè)用來(lái)標(biāo)識(shí)進(jìn)程的進(jìn)程控制塊pcb用結(jié)構(gòu)來(lái)描述，包括以下字段：（1）進(jìn)程標(biāo)識(shí)id，其中0為閑逛進(jìn)程，用戶進(jìn)程的標(biāo)識(shí)數(shù)為1，2，3。（2）進(jìn)程優(yōu)先級(jí)priority，閑逛進(jìn)程（idle）的優(yōu)先級(jí)為0，用戶進(jìn)程的優(yōu)先級(jí)大于0，且隨機(jī)產(chǎn)生，標(biāo)識(shí)數(shù)越大，優(yōu)先級(jí)越高。（3）進(jìn)程占用的cpu時(shí)間cputime，進(jìn)程每運(yùn)行一次，累計(jì)值等于4。（4）進(jìn)程總共需

2、要運(yùn)行時(shí)間alltime，利用隨機(jī)函數(shù)產(chǎn)生。（5）進(jìn)程狀態(tài)，0就緒態(tài)；1運(yùn)行態(tài)；2阻塞態(tài)。（6）隊(duì)列指針next，用來(lái)將多個(gè)進(jìn)程控制塊pcb鏈接為隊(duì)列。3優(yōu)先數(shù)改變的原則（1）進(jìn)程在就緒隊(duì)列中每呆一個(gè)時(shí)間片，優(yōu)先數(shù)增加1。（2）進(jìn)程每運(yùn)行一個(gè)時(shí)間片，優(yōu)先數(shù)減3。4在調(diào)度前，系統(tǒng)中擁有的進(jìn)程數(shù)pcb_number由鍵盤輸入，經(jīng)初始化后，所有的進(jìn)程控制塊pcb鏈接成就緒隊(duì)列。5為了清楚地觀察諸進(jìn)程的調(diào)度過(guò)程，程序應(yīng)將每個(gè)時(shí)間片內(nèi)的進(jìn)程的情況顯示出來(lái)， 3實(shí)驗(yàn)步驟進(jìn)程調(diào)度的思想（1）當(dāng)系統(tǒng)空閑（就緒隊(duì)列為空）時(shí)，系統(tǒng)運(yùn)行閑逛進(jìn)程，否則運(yùn)行其他進(jìn)程，發(fā)生變遷1（就緒運(yùn)行）。（2）在運(yùn)行進(jìn)程（包括閑逛進(jìn)

3、程）的過(guò)程中，可能發(fā)生變遷2（運(yùn)行阻塞），即將運(yùn)行進(jìn)程插入到阻塞隊(duì)列（閑逛進(jìn)程不能被阻塞），可能有其他新的進(jìn)程創(chuàng)建pcb，還可能喚醒阻塞隊(duì)列中的某些進(jìn)程pcb，發(fā)生變遷3（阻塞就緒），即從阻塞隊(duì)列中移出并插入就緒隊(duì)列中。（3）時(shí)間片運(yùn)行結(jié)束后，若進(jìn)程累計(jì)占用cpu時(shí)間大于等于進(jìn)程需要運(yùn)行的時(shí)間，則進(jìn)程執(zhí)行結(jié)束，釋放其pcb。若進(jìn)程累計(jì)占用cpu時(shí)間小于進(jìn)程需要運(yùn)行時(shí)間，發(fā)生變遷4（運(yùn)行就緒），即將當(dāng)前運(yùn)行的進(jìn)程插入就緒隊(duì)列中。程序流程圖動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度算法模擬流程2輪轉(zhuǎn)法進(jìn)程調(diào)度算法模擬流程程序代碼/*以下程序在c+環(huán)境調(diào)試通過(guò)*/#define null 0#include #inclu

4、de #include using namespace std;/*以下僅列出動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度算法模擬*/*進(jìn)程pcb結(jié)構(gòu)*/struct pcb int id;/進(jìn)程標(biāo)識(shí)id，其中0為閑逛進(jìn)程，用戶進(jìn)程的標(biāo)識(shí)數(shù)為1，2，3int priority;/進(jìn)程優(yōu)先級(jí)priority，閑逛進(jìn)程（idle）的優(yōu)先級(jí)為0，用戶進(jìn)程的優(yōu)先級(jí)大于0，且隨機(jī)產(chǎn)生，標(biāo)識(shí)數(shù)越大，優(yōu)先級(jí)越高。int cputime;/進(jìn)程占用的cpu時(shí)間cputime，進(jìn)程每運(yùn)行一次，累計(jì)值等于4int alltime;/進(jìn)程總共需要運(yùn)行時(shí)間alltimeint state;/進(jìn)程狀態(tài)，0就緒態(tài)；1運(yùn)行態(tài)；2阻塞態(tài)。struc

5、t pcb *next;/隊(duì)列指針next，用來(lái)將多個(gè)進(jìn)程控制塊pcb鏈接為隊(duì)列 ;typedef struct pcb pcb;void init ; /*產(chǎn)生idle進(jìn)程，輸入用戶進(jìn)程數(shù)目，調(diào)用insert */void print pcb *pcb ; /*輸出進(jìn)程屬性信息*/void print_init pcb *pcb ; /*輸出所有pcb的初始值*/void insert_queue pcb *queue,pcb *item ; /*動(dòng)態(tài)優(yōu)先權(quán)調(diào)試算法將item插入到隊(duì)列中,使得插入后，隊(duì)列中按照優(yōu)先級(jí)從高到低有序*/void insert_queue1 pcb *queue,

6、pcb *item ; /*輪轉(zhuǎn)法將item插入到隊(duì)列末尾*/void pushback_queue pcb *queue,pcb *item ; /*將item插入到隊(duì)列的尾部*/void insert ; /*動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度算法生成進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列*/void insert1 ; /*輪轉(zhuǎn)法的進(jìn)程調(diào)度算法生成進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列*/void run pcb *pcb ; /*運(yùn)行進(jìn)程，隨機(jī)阻塞進(jìn)程、產(chǎn)生新進(jìn)程，插入就緒隊(duì)列，喚醒阻塞進(jìn)程*/void run1 pcb *pcb ; /*輪轉(zhuǎn)法試運(yùn)行參數(shù)pcb所指的進(jìn)程*/void block pcb *pcb

7、; /*調(diào)用destroy ，將進(jìn)程插入阻塞隊(duì)列*/void wakeup ; /*動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度算法喚醒進(jìn)程，插入就緒隊(duì)列*/void wakeup1 ; /*輪轉(zhuǎn)法的進(jìn)程調(diào)度算法喚醒進(jìn)程，插入就緒隊(duì)列*/void proc_priority ; /*優(yōu)先權(quán)調(diào)度算法模擬*/void proc_loop ; /*輪轉(zhuǎn)法調(diào)度算法模擬*/void update pcb *pcb ; /*更新進(jìn)程信息*/pcb *ready_queue,*block_queue,*idleprocess; /*就緒隊(duì)列，阻塞隊(duì)列及閑逛進(jìn)程指針變量*/void main int i 0;while 1 cout

8、 "n please select a number 1,2,0 " ;cout "n 1- priority " ;cout "n 2- loop" ;cout "n 0- exitn" ;cin i;if i 1 cout "nthis is an example for priority processing:n" ;init ;:proc_priority ; else if i 2 cout "nthis is an example for round robin proce

9、ssing:n" ;init ;proc_loop ; else if i 0 exit 1 ; /*輸出所有pcb的初始值，此函數(shù)用于測(cè)試程序*/void print_init pcb *pcb pcb *temp pcb- next;cout "n id priority cputime alltime staten" ;while temp! null cout "n" " " temp- id " " temp- priority " " temp- cputime "

10、; " temp- alltime;if temp- state 0 cout " ready" ;else if temp- state 1 cout " running" ;elsecout " blocked" ;temp temp- next; /*輸出進(jìn)程屬性信息*/void print pcb *pcb pcb *temp;temp pcb;if pcb- id 0 cout "ntthe idle process is running!" ;else cout "n" &

11、quot; " temp- id " " temp- priority " " temp- cputime " " temp- alltime;if temp- state 0 cout " ready" ;else if temp- state 1 cout " running" ;elsecout " blocked" ; void insert_queue pcb *queue,pcb *item /動(dòng)態(tài)優(yōu)先權(quán)調(diào)試算法將item插入到隊(duì)列中,使得插入后，隊(duì)列中

12、按照優(yōu)先級(jí)從高到低有序pcb *p,*q;q queue;p q- next;while p! 0 &&p- priority item- priority q p;p p- next; if p 0 /在隊(duì)尾插入item- next 0;q- next item; else /在q之后、p之前插入item- next p;q- next item; void insert_queue1 pcb *queue,pcb *item /輪轉(zhuǎn)法將item插入到隊(duì)列末尾pcb *p,*q;q queue;p q- next;item- next 0;q- next item; void

13、 pushback_queue pcb *queue,pcb *item /將item插入到隊(duì)列的尾部pcb *p,*q;q queue;p q- next;while p! 0 q p;p p- next; item- next q- next;q- next item; void sort_queue pcb *&queue /對(duì)queue中的結(jié)點(diǎn)進(jìn)行排序，按照優(yōu)先級(jí)從大到小pcb *temp new pcb;temp- next 0;while queue- next pcb *p;p queue- next;queue- next p- next;:insert_queue t

14、emp,p ; queue- next temp- next;delete temp; /*動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度生成進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列,顯示進(jìn)程信息*/void insert pcb *newp 0;static long id 0;newp new pcb;id+;newp- id id;newp- state 0;newp- cputime 0;newp- priority rand %3+1;newp- alltime rand %3+1;newp- next null;:pushback_queue ready_queue,newp ;/將新生成進(jìn)程插入到就緒隊(duì)列尾部pri

15、nt newp ;cout "t建立： creating - readyn" ; /*輪轉(zhuǎn)法的進(jìn)程調(diào)度生成進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列,顯示進(jìn)程信息*/void insert1 pcb *newp 0;static long id 0;newp new pcb;id+;newp- id id;newp- state 0;newp- cputime 0;newp- alltime rand %3+1;newp- next null;:pushback_queue ready_queue,newp ;/將新生成進(jìn)程插入到就緒隊(duì)列尾部print newp ;cout "

16、;t建立： creating - readyn" ; /*生成n個(gè)進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列,顯示進(jìn)程信息*/void insert int n for int i 1;i n;i+ insert ; /*動(dòng)態(tài)優(yōu)先權(quán)調(diào)度產(chǎn)生idle進(jìn)程，輸入用戶進(jìn)程數(shù)目，調(diào)用insert */void init /為每個(gè)隊(duì)列設(shè)立頭結(jié)點(diǎn)，便于插入刪除操作block_queue new pcb;block_queue- next 0;ready_queue new pcb;ready_queue- next 0;int i,pcb_number -1;idleprocess null; /*設(shè)置閑逛

17、進(jìn)程pcb各字段值*/idleprocess pcb * malloc sizeof pcb ;idleprocess- id 0;idleprocess- state 0;idleprocess- cputime 0;idleprocess- priority 0;idleprocess- alltime 1;idleprocess- next null;/閑逛進(jìn)程放入就緒隊(duì)列idleprocess- next ready_queue- next;ready_queue- next idleprocess; /也可假定初始時(shí)系統(tǒng)中只有一個(gè)idle進(jìn)程/輸入初始時(shí)進(jìn)程的個(gè)數(shù)/while pcb

18、_number 0 / /cout "input the number of the pcb to be started:" ;/cin pcb_number;/ /cout "n id priority cputime alltime state" ;/for i 0;i pcb_number;i+ /insert ;cout "就緒隊(duì)列初始化成功" endl;:print_init ready_queue ;cout endl; /*調(diào)用destroy ，將進(jìn)程插入阻塞隊(duì)列*/void block pcb *pcb /將pcb插入

19、到阻塞隊(duì)列pcb- state 2; /*將pcb所指進(jìn)程的狀態(tài)設(shè)置為阻塞*/pcb- cputime- 2; /*設(shè)進(jìn)程執(zhí)行半個(gè)時(shí)間片單位后被阻塞*/*pcb- next null;*/print pcb ;cout " 變遷2：running - blockedn" ;/將pcb插入到阻塞隊(duì)列/按照什么方式插入呢，需要參考喚醒條件/因?yàn)槭请S機(jī)喚醒一個(gè)進(jìn)程，所以我們就簡(jiǎn)單地把它放置在阻塞隊(duì)列的頭部pcb- next block_queue- next;block_queue- next pcb; void update pcb *pcb /就緒隊(duì)列中進(jìn)程的優(yōu)先級(jí)均增加1p

20、cb *temp ready_queue- next;while temp && temp- next /就緒隊(duì)列的最后一個(gè)是閑逛進(jìn)程temp- priority+;temp temp- next; /*動(dòng)態(tài)優(yōu)先權(quán)調(diào)度試運(yùn)行參數(shù)pcb所指的進(jìn)程*/void run pcb *pcb /如果pcb是閑逛進(jìn)程，則不做處理，再次放入就緒隊(duì)列ready_queueif pcb- id 0 :insert_queue ready_queue,pcb ;print pcb ;cout " 變遷1：ready - runningn" else /如果不是閑逛進(jìn)程，則進(jìn)行如

21、下處理pcb- state 1;/*設(shè)置該進(jìn)程的狀態(tài)為"運(yùn)行"*/pcb- cputime+ 4;/*累計(jì)該進(jìn)程占用cpu的時(shí)間*/pcb- priority pcb- priority-3; /*每運(yùn)行一個(gè)時(shí)間片，其優(yōu)先數(shù)減3*/if pcb- priority 1 pcb- priority 1;print pcb ;printf " 變遷1：ready - runningn" ;if rand %3 1 /*pcb不是閑逛進(jìn)程，滿足條件則阻塞此進(jìn)程*/ if pcb- cputime-2 pcb- alltime block pcb ;else /

22、已經(jīng)執(zhí)行完畢，應(yīng)該銷毀進(jìn)程cout endl;cout "t the process no " pcb- id " is completed! 銷毀：running- destroy" endl;delete pcb; else /否則看改進(jìn)程是否執(zhí)行完畢，如果執(zhí)行完，則釋放，否則再次放入就緒隊(duì)列if pcb- cputime pcb- alltime /釋放cout endl;cout "t the process no " pcb- id " is completed! 銷毀：running- destroy"

23、 endl;delete pcb; else /再次放入就緒隊(duì)列,按照優(yōu)先級(jí)有序:insert_queue ready_queue,pcb ; update ready_queue ;/*更新就緒隊(duì)列進(jìn)程優(yōu)先數(shù)*/if rand %5 1 insert 3 ; /*創(chuàng)建3個(gè)新進(jìn)程*/:sort_queue ready_queue ; if rand %7 1 wakeup ; /*喚醒一個(gè)進(jìn)程*/ /*返回當(dāng)前進(jìn)程是否被阻塞，1（已阻塞），0（未阻塞）*/ /*輪轉(zhuǎn)法試運(yùn)行參數(shù)pcb所指的進(jìn)程*/void run1 pcb *pcb /如果pcb是閑逛進(jìn)程，則不做處理，再次放入就緒隊(duì)列read

24、y_queueif pcb- id 0 :insert_queue1 ready_queue,pcb ;print pcb ;cout " 變遷1：ready - runningn" else /如果不是閑逛進(jìn)程，則進(jìn)行如下處理pcb- state 1;/*設(shè)置該進(jìn)程的狀態(tài)為"運(yùn)行"*/pcb- cputime+ 4;/*累計(jì)該進(jìn)程占用cpu的時(shí)間*/if pcb- priority 1 pcb- priority 1;/print pcb ;/ printf " 變遷1：ready - runningn" ;if rand %3 1

25、 /*pcb不是閑逛進(jìn)程，滿足條件則阻塞此進(jìn)程*/ if pcb- cputime-2 pcb- alltime block pcb ;else /已經(jīng)執(zhí)行完畢，應(yīng)該銷毀進(jìn)程cout endl;cout "t the process no " pcb- id " is completed! 銷毀：running- destroy" endl;delete pcb; else /否則看改進(jìn)程是否執(zhí)行完畢，如果執(zhí)行完，則釋放，否則再次放入就緒隊(duì)列if pcb- cputime pcb- alltime /釋放cout endl;cout "t th

26、e process no " pcb- id " is completed! 銷毀：running- destroy" endl;delete pcb; else /再次放入就緒隊(duì)列:insert_queue1 ready_queue,pcb ; if rand %5 1 insert 3 ; /*創(chuàng)建3個(gè)新進(jìn)程*/:sort_queue ready_queue ; if rand %7 1 wakeup1 ; /*喚醒一個(gè)進(jìn)程*/ /*返回當(dāng)前進(jìn)程是否被阻塞，1（已阻塞），0（未阻塞）*/ /*喚醒，即從阻塞隊(duì)列中選擇一個(gè)pcb，且插入就緒隊(duì)列中*/void w

27、akeup /隨機(jī)喚醒一個(gè)阻塞進(jìn)程/這里采取的方法是遍歷阻塞隊(duì)列，每訪問(wèn)一個(gè)，就產(chǎn)生一個(gè)隨機(jī)數(shù)/如果該隨機(jī)數(shù)對(duì)20求余恰好是1，則當(dāng)前結(jié)點(diǎn)被喚醒，就要納入就緒隊(duì)列if block_queue- next 0 /此時(shí)沒(méi)有被阻塞的進(jìn)程，無(wú)所謂喚醒return;pcb *q,*p;/下面遍歷阻塞隊(duì)列，q永遠(yuǎn)指向p的前驅(qū)while true q block_queue;p q- next;while p && rand %20! 1 q p;p p- next; if p! 0 /p就是要喚醒的進(jìn)程q- next p- next;break; p- state 0;cout endl;

28、:print p ;cout " 變遷3：blocked- ready" endl;:insert_queue ready_queue,p ; void wakeup1 /隨機(jī)喚醒一個(gè)阻塞進(jìn)程/這里采取的方法是遍歷阻塞隊(duì)列，每訪問(wèn)一個(gè)，就產(chǎn)生一個(gè)隨機(jī)數(shù)/如果該隨機(jī)數(shù)對(duì)20求余恰好是1，則當(dāng)前結(jié)點(diǎn)被喚醒，就要納入就緒隊(duì)列if block_queue- next 0 /此時(shí)沒(méi)有被阻塞的進(jìn)程，無(wú)所謂喚醒return;pcb *q,*p;/下面遍歷阻塞隊(duì)列，q永遠(yuǎn)指向p的前驅(qū)while true q block_queue;p q- next;while p &&

29、rand %20! 1 q p;p p- next; if p! 0 /p就是要喚醒的進(jìn)程q- next p- next;break; p- state 0;cout endl;:print p ;cout " 變遷3：blocked- ready" endl;:insert_queue1 ready_queue,p ; /*優(yōu)先權(quán)優(yōu)先調(diào)度算法*/void proc_priority :sort_queue ready_queue ;/對(duì)queue中的結(jié)點(diǎn)進(jìn)行排序，按照優(yōu)先級(jí)從大到小pcb *temp 0,*running 0; /*running的pcb指針*/int t

30、imes;for times 0;times 10;times+ /找到優(yōu)先級(jí)最高的進(jìn)程，并且從隊(duì)列中刪除cout "本次調(diào)度前：" endl;:print_init ready_queue ;running ready_queue- next; /*running指向就緒隊(duì)列隊(duì)首pcb*/ready_queue- next running- next;cout endl;cout "本次調(diào)度開(kāi)始" endl;:run running ;cout "n本次調(diào)度結(jié)束。" endl; /*輪轉(zhuǎn)法進(jìn)程調(diào)用算法*/void proc_loop

31、 pcb *temp 0,*running 0; /*running的pcb指針*/int times;for times 0;times 10;times+ cout "本次調(diào)度前：" endl;:print_init ready_queue ;running ready_queue- next; /*running指向就緒隊(duì)列隊(duì)首pcb*/ready_queue- next running- next;cout endl;cout "本次調(diào)度開(kāi)始" endl; :run1 running ; cout "n本次調(diào)度結(jié)束。" endl; 圖0 輸入實(shí)現(xiàn)調(diào)度的方法圖1 輸入1 在動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法下執(zhí)行圖2圖3 輸入2 在輪轉(zhuǎn)法調(diào)度算法下執(zhí)行圖44實(shí)驗(yàn)過(guò)程中遇到的問(wèn)題及解決方案對(duì)進(jìn)程調(diào)度的思想理解不夠深刻，不知道如何實(shí)現(xiàn)對(duì)進(jìn)程優(yōu)先級(jí)