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

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告學(xué)院名稱： 信 息 科 學(xué) 與 工 程 學(xué) 院專業(yè)班級(jí)： 信息管理與信息系統(tǒng) 08-1班姓 名： 學(xué) 號(hào)： 0801051316 2010年12月28日目錄一、 進(jìn)程調(diào)度算法-41、設(shè)計(jì)目的-41.1目的-41.2說明-42、任務(wù)及要求-42.1 設(shè)計(jì)任務(wù)-42.2 設(shè)計(jì)要求-43、算法及數(shù)據(jù)結(jié)構(gòu)-5 3.1算法的總體思想-53.2先到先服務(wù)功能模塊-5 3.2.1功能-53.2.2數(shù)據(jù)結(jié)構(gòu)-53.2.3算法-53.3最短作業(yè)優(yōu)先調(diào)度算法模擬-6 3.3.1功能演示模塊-63.3.2數(shù)據(jù)結(jié)構(gòu)-73.3.3算法-73.4優(yōu)先級(jí)調(diào)度算法演示-9 3.4.1功能演示 -93.4.

2、2算法-93.5輪轉(zhuǎn)法調(diào)度算法演示-103.5.1功能演示-103.5.2算法-114、實(shí)驗(yàn)分析-134.1實(shí)驗(yàn)過程中遇到的問題-134.2結(jié)果分析-13 4.2.1先到先服務(wù)算法-134.2.2最短作業(yè)優(yōu)先調(diào)度算法-14 4.2.3優(yōu)先級(jí)調(diào)度算法-154.2.4輪轉(zhuǎn)法調(diào)度算法-16附：一些函數(shù)的算法代碼-17二、銀行家算法-221、設(shè)計(jì)目的-222、任務(wù)及要求-222.1 設(shè)計(jì)任務(wù)-222.2 設(shè)計(jì)要求-223、算法及數(shù)據(jù)結(jié)構(gòu)-223.1算法的總體思想-223.2功能模塊演示-22 3.2.1操作步驟-223.2.2數(shù)據(jù)結(jié)構(gòu)-23 3.2.3算法-23 3.2.3.1輸入函數(shù)-233.2.3

3、.2尋找滿足所需資源數(shù)小于可得資源數(shù)的進(jìn)程函數(shù)-243.2.3.3 判斷系統(tǒng)是否安全函數(shù)-253.2.3.4主函數(shù)（包含輸出界面函數(shù)）-264、實(shí)驗(yàn)分析-274.1實(shí)驗(yàn)結(jié)果-274.2結(jié)果分析-28 4.2.1判斷系統(tǒng)是否處于安全狀態(tài)-284.2.2發(fā)出request請(qǐng)求之后-29三、頁置換算法-301、設(shè)計(jì)目的-301.1目的-301.2說明-302、任務(wù)及要求-302.1 設(shè)計(jì)任務(wù)-302.2 設(shè)計(jì)要求-303、算法及數(shù)據(jù)結(jié)構(gòu)-303.1算法的總體思想-303.2fifo頁置換算法功能模塊-303.2.1功能-303.2.2數(shù)據(jù)結(jié)構(gòu)-313.2.3算法-313.3最優(yōu)頁置換算法功能模塊-3

4、43.3.1功能-343.3.2算法-343.4lru頁置換算法功能模塊-363.4.1功能-363.4.2算法-363.5最近最少使用頁置換算法功能模塊-39 3.5.1功能-393.5.2算法-394、 實(shí)驗(yàn)分析-434.1實(shí)驗(yàn)過程中遇到的問題-434.2結(jié)果分析-43 4.2.1fifo頁置換算法-43 4.2.2最優(yōu)頁置換算法-434.2.3lru頁置換算法 -444.2.4最近最少使用頁置換算法 -45附：一些函數(shù)的算法代碼-45 進(jìn)程調(diào)度算法一、設(shè)計(jì)目的1.1目的 通過先到先服務(wù)算法、優(yōu)先權(quán)法、最短作業(yè)優(yōu)先調(diào)度算法與輪轉(zhuǎn)調(diào)度算法的模擬加深對(duì)進(jìn)程概念和進(jìn)程調(diào)度過程的理解，了解各種算法

5、的屬性，掌握進(jìn)程狀態(tài)之間的切換，同時(shí)掌握進(jìn)程調(diào)度算法的實(shí)現(xiàn)方法和技巧。 1.2說明 （1）由于沒有搞懂阻塞狀態(tài)，所以本程序沒有使用阻塞狀態(tài) （2）閑逛進(jìn)程的概念在本程序中也未使用 （3）priority、cputime、alltime均使用隨機(jī)函數(shù)產(chǎn)生 （3）對(duì)隨機(jī)數(shù)的產(chǎn)生使用了一些限制 a先到先服務(wù)算法、最短作業(yè)優(yōu)先調(diào)度算法、優(yōu)先級(jí)算法中一個(gè)進(jìn)程執(zhí)行完畢以后，保證至少有一個(gè)進(jìn)程已到達(dá) b輪轉(zhuǎn)法中選定第一個(gè)到達(dá)的進(jìn)程，將其調(diào)到鏈表首位，對(duì)其執(zhí)行第一輪輪轉(zhuǎn)后；保證其他的進(jìn)程都到達(dá) c本程序沒有滿座進(jìn)程在就緒隊(duì)列中每呆一個(gè)時(shí)間片，優(yōu)先數(shù)增加1的條件二、任務(wù)及要求2.1 設(shè)計(jì)任務(wù) 1、用先到先服務(wù)算

6、法、優(yōu)先權(quán)法、最短作業(yè)優(yōu)先調(diào)度算法與輪轉(zhuǎn)調(diào)度算法模擬進(jìn)程調(diào)度過程2、理解進(jìn)程調(diào)度的機(jī)理3、比較各種調(diào)度算法的優(yōu)缺點(diǎn)2.2 設(shè)計(jì)要求1、用c語言來實(shí)現(xiàn)對(duì)n個(gè)進(jìn)程的進(jìn)程調(diào)度。2、采用多道程序設(shè)計(jì)3、在調(diào)度前，系統(tǒng)中擁有的進(jìn)程數(shù)pcb_number由鍵盤輸入，經(jīng)初始化后，所有的進(jìn)程控制塊pcb鏈接成就緒隊(duì)列。 4、每個(gè)用來標(biāo)識(shí)進(jìn)程的進(jìn)程控制塊pcb用結(jié)構(gòu)來描述，包括以下字段： （1）進(jìn)程優(yōu)先數(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)生，優(yōu)先數(shù)越大，優(yōu)先級(jí)越高。 （3）cputime，

7、進(jìn)程每運(yùn)行一次，累計(jì)值等于4。 （4）進(jìn)程總共需要運(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，用來將多個(gè)進(jìn)程控制塊pcb鏈接為隊(duì)列。3、 算法及數(shù)據(jù)結(jié)構(gòu) 3.1算法的總體思想 （1）選擇要實(shí)現(xiàn)的服務(wù) （2）執(zhí)行選擇的任務(wù) （3）重新提示要選擇的服務(wù)，直至選擇退出為止3.2先到先服務(wù)功能模塊 3.2.1功能 （1）輸入1選擇先到先服務(wù)算法模擬 （2）輸入開始進(jìn)程個(gè)數(shù)n，創(chuàng)建n個(gè)pcb并加入就緒隊(duì)列 （3）調(diào)度就緒隊(duì)列中第一個(gè)到達(dá)的進(jìn)程運(yùn)行，如果同時(shí)到達(dá)則選擇優(yōu)先級(jí)高的先執(zhí)行 （4）第一個(gè)進(jìn)程執(zhí)行完畢后，接著從就緒隊(duì)列中

8、選擇最先到達(dá)的進(jìn)程，執(zhí)行之；重復(fù)上述步驟，直到本次調(diào)度結(jié)束。 3.2.2數(shù)據(jù)結(jié)構(gòu) struct pcb int id;/進(jìn)程優(yōu)先數(shù)id，其中為閑逛進(jìn)程 int priority;/進(jìn)程優(yōu)先級(jí)priority int cputime;/進(jìn)程占用的cpu時(shí)間 int alltime;/進(jìn)程總共需要運(yùn)行時(shí)間 int state;/進(jìn)程狀態(tài)，：就緒態(tài)；：運(yùn)行態(tài)；。 int arrive_time;/進(jìn)程到達(dá)時(shí)間 int pcnumber;/記錄進(jìn)程數(shù) int rrnumber;/記錄第幾次輪轉(zhuǎn) pcb* next;/ ; 3.2.3算法 void fcfs()/先到先服務(wù)算法 pcb *process

9、; process=(pcb *)malloc(sizeof(pcb); init(process); output(process); int minarrive_time=0;/定義最短到達(dá)時(shí)間 pcb *temp,*temp2; int pcnumber=process-next-pcnumber; temp=process-next;/初始化 while(pcnumber0) temp=process-next; while(temp-state!=0) temp=temp-next; temp2=temp;/用于比較到達(dá)時(shí)間相同情況下比較優(yōu)先級(jí) minarrive_time=temp

10、-arrive_time; temp=temp-next; while(temp!=null) if(temp-state=0&temp-arrive_timearrive_time=temp2-arrive_time) if(temp2-prioritytemp-priority)/優(yōu)先級(jí)小的先處理 minarrive_time=temp-arrive_time;temp2=temp; elseminarrive_time=temp-arrive_time;temp2=temp; temp=temp-next;temp2-state=1;output(process);temp2-state

11、=2;pcnumber-;output(process);3.3最短作業(yè)優(yōu)先調(diào)度算法模擬 3.3.1功能演示模塊 （1）輸入2選擇最短作業(yè)優(yōu)先調(diào)度算法 （2）輸入開始進(jìn)程個(gè)數(shù)n，創(chuàng)建n個(gè)pcb并加入就緒隊(duì)列 （3）從就緒隊(duì)列中選擇區(qū)間時(shí)間最小的的進(jìn)程先執(zhí)行，區(qū)間時(shí)間相同的，優(yōu)先級(jí)高的先執(zhí)行 （4）第一個(gè)進(jìn)程執(zhí)行完畢后，接著從就緒隊(duì)列中選擇區(qū)間時(shí)間最小的進(jìn)程，執(zhí)行之；重復(fù)上述步驟，直到本次調(diào)度結(jié)束。 3.3.2數(shù)據(jù)結(jié)構(gòu) struct pcb int id;/進(jìn)程優(yōu)先數(shù)id，其中為閑逛進(jìn)程 int priority;/進(jìn)程優(yōu)先級(jí)priority int cputime;/進(jìn)程占用的cpu時(shí)間 in

12、t alltime;/進(jìn)程總共需要運(yùn)行時(shí)間 int state;/進(jìn)程狀態(tài)，：就緒態(tài)；：運(yùn)行態(tài)；。 int arrive_time;/進(jìn)程到達(dá)時(shí)間 int pcnumber;/記錄進(jìn)程數(shù) int rrnumber;/記錄第幾次輪轉(zhuǎn) pcb* next;/ ; 3.3.3算法 void sjf() pcb *process1;/重新開辟進(jìn)程 int remainder=0;/其職等于進(jìn)程數(shù)減一，作用為用于第二個(gè)while循環(huán) process1=(pcb *)malloc(sizeof(pcb); init(process1); pcb *temp1,*temp2; int minarrive_t

13、ime=0,min_usetime=0;/定義最短到達(dá)時(shí)間和最少使用時(shí)間 temp1=process1-next;/初始化 while(temp1-state!=0) temp1=temp1-next; minarrive_time=temp1-arrive_time; printf(minarrive_time=%dn,minarrive_time); temp2=temp1; output(process1); temp1=temp1-next; while(temp1!=null) if(temp1-state=0&temp1-arrive_timearrive_time=temp2-a

14、rrive_time) if(temp2-prioritytemp1-priority)/優(yōu)先級(jí)小的先處理 minarrive_time=temp1-arrive_time;temp2=temp1; else minarrive_time=temp1-arrive_time;temp2=temp1; temp1=temp1-next; temp2-state=1; output(process1); temp2-state=2; remainder=process1-next-pcnumber; -remainder; while(remainder0) temp1=process1-next

15、; while(temp1-state!=0) temp1=temp1-next; temp2=temp1; min_usetime=temp1-alltime; while(temp1!=null) if(temp1-state=0&temp1-alltimealltime=temp2-alltime) if(temp2-prioritytemp1-priority)/優(yōu)先級(jí)小的先處理 min_usetime=temp1-alltime;temp2=temp1; else min_usetime=temp1-alltime;temp2=temp1; temp1=temp1-next; tem

16、p2-state=1; output(process1); t emp2-state=2; remainder-; output(process1); 3.4優(yōu)先級(jí)調(diào)度算法演示 3.4.1功能演示 （1）輸入3選擇優(yōu)先級(jí)調(diào)度算法 （2）輸入開始進(jìn)程個(gè)數(shù)n，創(chuàng)建n個(gè)pcb并加入就緒隊(duì)列 （3）從就緒隊(duì)列中選擇優(yōu)先級(jí)最高（優(yōu)先數(shù)最?。┑倪M(jìn)程，執(zhí)行之；優(yōu)先級(jí)相同的，先到達(dá)的先執(zhí)行 （4）第一個(gè)進(jìn)程執(zhí)行完畢后，接著從就緒隊(duì)列中選擇優(yōu)先級(jí)最高的進(jìn)程，執(zhí)行之；重復(fù)上述步驟，直到本次調(diào)度結(jié)束。3.4.2算法 void psa() pcb *process1;/重新開辟進(jìn)程 int remainder=0;/

17、其職等于進(jìn)程數(shù)減一，作用為用于第二個(gè)while循環(huán) process1=(pcb *)malloc(sizeof(pcb); init(process1);/初始化 int minarrive_time=0,min_priority=0;/定義最短到達(dá)時(shí)間,最小優(yōu)先級(jí) pcb *temp1,*temp2; temp1=process1-next;/初始化 while(temp1-state!=0) temp1=temp1-next; minarrive_time=temp1-arrive_time;/初始值為第一個(gè)state不為的arrive_time temp2=temp1; output(p

18、rocess1); temp1=temp1-next; while(temp1!=null)/尋找第一個(gè)到達(dá)的進(jìn)程 if(temp1-state=0&temp1-arrive_timearrive_time=temp2-arrive_time)/到達(dá)時(shí)間相同的，優(yōu)先級(jí)小的先執(zhí)行 if(temp2-prioritytemp1-priority)/優(yōu)先級(jí)小的先處理 minarrive_time=temp1-arrive_time;temp2=temp1; else minarrive_time=temp1-arrive_time;temp2=temp1; temp1=temp1-next; tem

19、p2-state=1; output(process1); temp2-state=2; remainder=process1-next-pcnumber; -remainder; while(remainder0) temp1=process1-next; while(temp1-state!=0) temp1=temp1-next; temp2=temp1; min_priority=temp1-priority; while(temp1!=null)/優(yōu)先級(jí)最小的先執(zhí)行 if(temp1-state=0&temp1-prioritypriority=temp2-priority)/優(yōu)先級(jí)

20、相同的，先到達(dá)的先執(zhí)行 if(temp1-arrive_timearrive_time) min_priority=temp1-priority; temp2=temp1; else min_priority=temp1-priority; temp2=temp1; temp1=temp1-next; temp2-state=1; output(process1); temp2-state=2; remainder-; output(process1); 3.5輪轉(zhuǎn)法調(diào)度算法演示 3.5.1功能演示 （1）輸入4選擇優(yōu)先級(jí)調(diào)度算法 （2）輸入開始進(jìn)程個(gè)數(shù)n，創(chuàng)建n個(gè)pcb并加入就緒隊(duì)列 （3）

21、每輪轉(zhuǎn)一次，進(jìn)程的cputime加4 （4）如果運(yùn)行時(shí)間cputime大于等于alltime，該進(jìn)程運(yùn)行完畢，釋放該進(jìn)程；否則仍在就緒隊(duì)列中。 （5）從就緒隊(duì)列中選擇最先到達(dá)的進(jìn)程，執(zhí)行之；同時(shí)到達(dá)的，優(yōu)先級(jí)高的先被選擇；將選定的進(jìn)程調(diào)到隊(duì)列的首位置 （6）開始第一次輪轉(zhuǎn)，知道所有進(jìn)程都執(zhí)行完成。3.5.2算法 void rr() pcb *process1;/重新開辟進(jìn)程 int minarrive_time=0,max_alltime=0,rrnumber=0;/定義最短到達(dá)時(shí)間,最大alltime時(shí)間,輪轉(zhuǎn)次數(shù) process1=(pcb *)malloc(sizeof(pcb); in

22、it(process1);/初始化 pcb *temp1,*temp2,*temp3; temp1=process1-next;/初始化 temp2=temp1; minarrive_time=temp1-arrive_time; output(process1); temp1=temp1-next; while(temp1!=null)/尋找第一個(gè)到達(dá)的進(jìn)程 if(temp1-state=0&temp1-arrive_timearrive_time=temp2-arrive_time)/到達(dá)時(shí)間相同的，優(yōu)先級(jí)小的先執(zhí)行 if(temp2-prioritytemp1-priority)/優(yōu)先級(jí)

23、小的先處理 minarrive_time=temp1-arrive_time;temp2=temp1; else minarrive_time=temp1-arrive_time;temp2=temp1; temp1=temp1-next; temp1=process1; temp3=process1-next-next; while(temp1-next!=temp2&temp1!=null)/將第一個(gè)到達(dá)的進(jìn)程調(diào)制隊(duì)首 temp1=temp1-next; temp1-next=temp2-next; temp2-next=process1-next; process1-next=temp2

24、; temp1=process1-next; max_alltime=temp1-alltime; temp1=temp1-next; while(temp1!=null) if(temp1-alltimemax_alltime) max_alltime=temp1-alltime; temp1=temp1-next; if(max_alltime%m=0) rrnumber=max_alltime/m; else rrnumber=max_alltime/m+1; while(rrnumber0) temp1=process1-next; while(temp1!=null) if(temp

25、1-cputimealltime) if(temp1-cputime+m=temp1-alltime) temp1-rrnumber+; temp1-state=1; temp1-cputime=temp1-alltime; else temp1-rrnumber+; temp1-state=1; temp1-cputime+=4； else temp1-state=2; temp1=temp1-next; output(process1); rrnumber-; t emp1=process1-next; while(temp1!=null) temp1-state=2; temp1=tem

26、p1-next; output(process1);4、 實(shí)驗(yàn)分析 4.1實(shí)驗(yàn)過程中遇到的問題 a未對(duì)進(jìn)程的到達(dá)時(shí)間作出限制，導(dǎo)致執(zhí)行的混亂 b輪轉(zhuǎn)法中未將選定的第一個(gè)進(jìn)程調(diào)到鏈表首位置 c亂轉(zhuǎn)法中將選定的進(jìn)程調(diào)到隊(duì)首過程中出現(xiàn)錯(cuò)誤，導(dǎo)致只輸出部分結(jié)果 4.2結(jié)果分析 4.2.1先到先服務(wù)算法 （1）比較arrive_time可知進(jìn)程3最先到達(dá)，其到達(dá)時(shí)間是2，故先執(zhí)行進(jìn)程3； （2）在剩下的3個(gè)進(jìn)程中，進(jìn)程0和進(jìn)程1同時(shí)到達(dá)，到達(dá)時(shí)間均為4，但是進(jìn)程1的優(yōu)先級(jí)更高，故執(zhí)行進(jìn)程1； （3）在余下的兩個(gè)進(jìn)程中，進(jìn)程0先到達(dá)，其到達(dá)時(shí)間為4，所以執(zhí)行進(jìn)程0； （4）只剩下一個(gè)進(jìn)程2，執(zhí)行之，所以本

27、次調(diào)度的執(zhí)行順序是：進(jìn)程3-進(jìn)程1-進(jìn)程0-進(jìn)程2 4.2.2最短作業(yè)優(yōu)先調(diào)度算法 （1）比較arrive_time可知進(jìn)程0最先到達(dá)，其到達(dá)時(shí)間是3，故先執(zhí)行進(jìn)程0；進(jìn)程0的執(zhí)行時(shí)間是27，在它執(zhí)行完畢以后其它兩個(gè)進(jìn)程均到達(dá)； （2）比較余下兩個(gè)進(jìn)程的執(zhí)行時(shí)間，進(jìn)程1的執(zhí)行時(shí)間更少為23，故執(zhí)行進(jìn)程1； （3）只剩下一個(gè)進(jìn)程2，執(zhí)行之，所以本次調(diào)度的執(zhí)行順序是：進(jìn)程0-進(jìn)程1-進(jìn)程2 4.2.3優(yōu)先級(jí)調(diào)度算法 （1）比較arrive_time可知進(jìn)程0和進(jìn)程1最先同時(shí)到達(dá)，到達(dá)時(shí)間均為1，但是進(jìn)程1的優(yōu)先級(jí)更高，所以最先執(zhí)行進(jìn)程1； （2）在余下的3個(gè)進(jìn)程中，進(jìn)程3的優(yōu)先級(jí)最高為5，所以執(zhí)行

28、進(jìn)程1； （3）在余下的兩個(gè)進(jìn)程中，進(jìn)程2的優(yōu)先級(jí)更高為6，所以執(zhí)行進(jìn)程2； （4）只剩下一個(gè)進(jìn)程0，執(zhí)行之，所以本次調(diào)度的執(zhí)行順序是：進(jìn)程1-進(jìn)程3-進(jìn)程2-進(jìn)程0 4.2.4輪轉(zhuǎn)法調(diào)度算法 （1）比較arrive_time可知進(jìn)程0和進(jìn)程1最先同時(shí)到達(dá)，到達(dá)時(shí)間均為1，但是進(jìn)程1的優(yōu)先級(jí)更高；由于進(jìn)程0本身就處于隊(duì)首位置，所以不需要將進(jìn)程0調(diào)到隊(duì)首 （2）開始輪轉(zhuǎn)，時(shí)間片為4，由alltime可知進(jìn)程1和進(jìn)程2，經(jīng)過6輪輪轉(zhuǎn)以后，執(zhí)行完畢；進(jìn)程0要經(jīng)過8輪輪轉(zhuǎn)以后執(zhí)行完畢，故本次的輪轉(zhuǎn)一共經(jīng)過8輪輪轉(zhuǎn)附：一些函數(shù)的算法代碼 1.鏈表初始化函數(shù) void init(pcb *process)

29、 int i; pcb *p; pcb *temp; process-next=null; p=process; int pcnumber; printf(請(qǐng)輸入進(jìn)程數(shù)：); scanf(%d,&pcnumber); / n=pcnumber; srand(time(null); for(i=0;inext=null; temp-id=i+1; temp-cputime=0; temp-state=0; temp-pcnumber=pcnumber; temp-rrnumber=0; temp-alltime=rand()%15+15; temp-priority=rand()%9+1; te

30、mp-arrive_time=rand()%5+1; p-next=temp; p=p-next; 2.輸出函數(shù) void output(pcb *process) pcb *temp; pcb *temp1; temp1=process-next; temp=process-next; int i=0; int j=temp1-pcnumber; /static int j=0; while(temp1!=null) if(temp1-state=1) break; temp1=temp1-next; if(temp1!=null) printf(此時(shí)進(jìn)程狀態(tài)為:n); else printf(進(jìn)程初始狀態(tài)為:n); printf( id priority arrive_time alltime staten); while(temp!=null) if(temp-idid-1,temp-id,temp-priority,temp-arrive_time,temp-alltime);