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

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

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

3、.2尋找滿足所需資源數小于可得資源數的進程函數-243.2.3.3 判斷系統(tǒng)是否安全函數-253.2.3.4主函數（包含輸出界面函數）-264、實驗分析-274.1實驗結果-274.2結果分析-28 4.2.1判斷系統(tǒng)是否處于安全狀態(tài)-284.2.2發(fā)出request請求之后-29三、頁置換算法-301、設計目的-301.1目的-301.2說明-302、任務及要求-302.1 設計任務-302.2 設計要求-303、算法及數據結構-303.1算法的總體思想-303.2fifo頁置換算法功能模塊-303.2.1功能-303.2.2數據結構-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、 實驗分析-434.1實驗過程中遇到的問題-434.2結果分析-43 4.2.1fifo頁置換算法-43 4.2.2最優(yōu)頁置換算法-434.2.3lru頁置換算法 -444.2.4最近最少使用頁置換算法 -45附：一些函數的算法代碼-45 進程調度算法一、設計目的1.1目的 通過先到先服務算法、優(yōu)先權法、最短作業(yè)優(yōu)先調度算法與輪轉調度算法的模擬加深對進程概念和進程調度過程的理解，了解各種算法

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

6、法、優(yōu)先權法、最短作業(yè)優(yōu)先調度算法與輪轉調度算法模擬進程調度過程2、理解進程調度的機理3、比較各種調度算法的優(yōu)缺點2.2 設計要求1、用c語言來實現對n個進程的進程調度。2、采用多道程序設計3、在調度前，系統(tǒng)中擁有的進程數pcb_number由鍵盤輸入，經初始化后，所有的進程控制塊pcb鏈接成就緒隊列。 4、每個用來標識進程的進程控制塊pcb用結構來描述，包括以下字段： （1）進程優(yōu)先數id，其中0為閑逛進程，用戶進程的標識數為1，2，3。 （2）進程優(yōu)先級priority，閑逛進程（idle）的優(yōu)先級為0，用戶 進程的優(yōu)先級大于0，且隨機產生，優(yōu)先數越大，優(yōu)先級越高。 （3）cputime，

7、進程每運行一次，累計值等于4。 （4）進程總共需要運行時間alltime，利用隨機函數產生。 （5）進程狀態(tài)，0：就緒態(tài)；1：運行態(tài)；2：完成態(tài)。 （6）隊列指針next，用來將多個進程控制塊pcb鏈接為隊列。3、 算法及數據結構 3.1算法的總體思想 （1）選擇要實現的服務 （2）執(zhí)行選擇的任務 （3）重新提示要選擇的服務，直至選擇退出為止3.2先到先服務功能模塊 3.2.1功能 （1）輸入1選擇先到先服務算法模擬 （2）輸入開始進程個數n，創(chuàng)建n個pcb并加入就緒隊列 （3）調度就緒隊列中第一個到達的進程運行，如果同時到達則選擇優(yōu)先級高的先執(zhí)行 （4）第一個進程執(zhí)行完畢后，接著從就緒隊列中

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

9、; process=(pcb *)malloc(sizeof(pcb); init(process); output(process); int minarrive_time=0;/定義最短到達時間 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;/用于比較到達時間相同情況下比較優(yōu)先級 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)先級小的先處理 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)先調度算法模擬 3.3.1功能演示模塊 （1）輸入2選擇最短作業(yè)優(yōu)先調度算法 （2）輸入開始進程個數n，創(chuàng)建n個pcb并加入就緒隊列 （3）從就緒隊列中選擇區(qū)間時間最小的的進程先執(zhí)行，區(qū)間時間相同的，優(yōu)先級高的先執(zhí)行 （4）第一個進程執(zhí)行完畢后，接著從就緒隊列中選擇區(qū)間時間最小的進程，執(zhí)行之；重復上述步驟，直到本次調度結束。 3.3.2數據結構 struct pcb int id;/進程優(yōu)先數id，其中為閑逛進程 int priority;/進程優(yōu)先級priority int cputime;/進程占用的cpu時間 in

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

13、ime=0,min_usetime=0;/定義最短到達時間和最少使用時間 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)先級小的先處理 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)先級小的先處理 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)先級調度算法演示 3.4.1功能演示 （1）輸入3選擇優(yōu)先級調度算法 （2）輸入開始進程個數n，創(chuàng)建n個pcb并加入就緒隊列 （3）從就緒隊列中選擇優(yōu)先級最高（優(yōu)先數最?。┑倪M程，執(zhí)行之；優(yōu)先級相同的，先到達的先執(zhí)行 （4）第一個進程執(zhí)行完畢后，接著從就緒隊列中選擇優(yōu)先級最高的進程，執(zhí)行之；重復上述步驟，直到本次調度結束。3.4.2算法 void psa() pcb *process1;/重新開辟進程 int remainder=0;/

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

18、rocess1); temp1=temp1-next; while(temp1!=null)/尋找第一個到達的進程 if(temp1-state=0&temp1-arrive_timearrive_time=temp2-arrive_time)/到達時間相同的，優(yōu)先級小的先執(zhí)行 if(temp2-prioritytemp1-priority)/優(yōu)先級小的先處理 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)先級最小的先執(zhí)行 if(temp1-state=0&temp1-prioritypriority=temp2-priority)/優(yōu)先級

20、相同的，先到達的先執(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輪轉法調度算法演示 3.5.1功能演示 （1）輸入4選擇優(yōu)先級調度算法 （2）輸入開始進程個數n，創(chuàng)建n個pcb并加入就緒隊列 （3）

21、每輪轉一次，進程的cputime加4 （4）如果運行時間cputime大于等于alltime，該進程運行完畢，釋放該進程；否則仍在就緒隊列中。 （5）從就緒隊列中選擇最先到達的進程，執(zhí)行之；同時到達的，優(yōu)先級高的先被選擇；將選定的進程調到隊列的首位置 （6）開始第一次輪轉，知道所有進程都執(zhí)行完成。3.5.2算法 void rr() pcb *process1;/重新開辟進程 int minarrive_time=0,max_alltime=0,rrnumber=0;/定義最短到達時間,最大alltime時間,輪轉次數 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)/尋找第一個到達的進程 if(temp1-state=0&temp1-arrive_timearrive_time=temp2-arrive_time)/到達時間相同的，優(yōu)先級小的先執(zhí)行 if(temp2-prioritytemp1-priority)/優(yōu)先級

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)/將第一個到達的進程調制隊首 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、 實驗分析 4.1實驗過程中遇到的問題 a未對進程的到達時間作出限制，導致執(zhí)行的混亂 b輪轉法中未將選定的第一個進程調到鏈表首位置 c亂轉法中將選定的進程調到隊首過程中出現錯誤，導致只輸出部分結果 4.2結果分析 4.2.1先到先服務算法 （1）比較arrive_time可知進程3最先到達，其到達時間是2，故先執(zhí)行進程3； （2）在剩下的3個進程中，進程0和進程1同時到達，到達時間均為4，但是進程1的優(yōu)先級更高，故執(zhí)行進程1； （3）在余下的兩個進程中，進程0先到達，其到達時間為4，所以執(zhí)行進程0； （4）只剩下一個進程2，執(zhí)行之，所以本

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

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

29、 int i; pcb *p; pcb *temp; process-next=null; p=process; int pcnumber; printf(請輸入進程數：); 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.輸出函數 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(此時進程狀態(tài)為:n); else printf(進程初始狀態(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);