操作系統(tǒng)課程設計報告進程調度算法

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

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

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

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

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

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

7、; /*調用destroy ，將進程插入阻塞隊列*/void wakeup ; /*動態(tài)優(yōu)先權的進程調度算法喚醒進程，插入就緒隊列*/void wakeup1 ; /*輪轉法的進程調度算法喚醒進程，插入就緒隊列*/void proc_priority ; /*優(yōu)先權調度算法模擬*/void proc_loop ; /*輪轉法調度算法模擬*/void update pcb *pcb ; /*更新進程信息*/pcb *ready_queue,*block_queue,*idleprocess; /*就緒隊列，阻塞隊列及閑逛進程指針變量*/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ù)用于測試程序*/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; /*輸出進程屬性信息*/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 /動態(tài)優(yōu)先權調試算法將item插入到隊列中,使得插入后，隊列中

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

13、 pushback_queue pcb *queue,pcb *item /將item插入到隊列的尾部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 /對queue中的結點進行排序，按照優(yōu)先級從大到小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; /*動態(tài)優(yōu)先權的進程調度生成進程屬性信息，插入進程就緒隊列,顯示進程信息*/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 ;/將新生成進程插入到就緒隊列尾部pri

15、nt newp ;cout "t建立： creating - readyn" ; /*輪轉法的進程調度生成進程屬性信息，插入進程就緒隊列,顯示進程信息*/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 ;/將新生成進程插入到就緒隊列尾部print newp ;cout "

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

17、進程pcb各字段值*/idleprocess pcb * malloc sizeof pcb ;idleprocess- id 0;idleprocess- state 0;idleprocess- cputime 0;idleprocess- priority 0;idleprocess- alltime 1;idleprocess- next null;/閑逛進程放入就緒隊列idleprocess- next ready_queue- next;ready_queue- next idleprocess; /也可假定初始時系統(tǒng)中只有一個idle進程/輸入初始時進程的個數(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 "就緒隊列初始化成功" endl;:print_init ready_queue ;cout endl; /*調用destroy ，將進程插入阻塞隊列*/void block pcb *pcb /將pcb插入

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

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

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

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

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

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

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

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

27、akeup /隨機喚醒一個阻塞進程/這里采取的方法是遍歷阻塞隊列，每訪問一個，就產生一個隨機數(shù)/如果該隨機數(shù)對20求余恰好是1，則當前結點被喚醒，就要納入就緒隊列if block_queue- next 0 /此時沒有被阻塞的進程，無所謂喚醒return;pcb *q,*p;/下面遍歷阻塞隊列，q永遠指向p的前驅while true q block_queue;p q- next;while p && rand %20! 1 q p;p p- next; if p! 0 /p就是要喚醒的進程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 /隨機喚醒一個阻塞進程/這里采取的方法是遍歷阻塞隊列，每訪問一個，就產生一個隨機數(shù)/如果該隨機數(shù)對20求余恰好是1，則當前結點被喚醒，就要納入就緒隊列if block_queue- next 0 /此時沒有被阻塞的進程，無所謂喚醒return;pcb *q,*p;/下面遍歷阻塞隊列，q永遠指向p的前驅while true q block_queue;p q- next;while p &&

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

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

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