2011操作系統課程設計報告基于Linux的進程調度模擬程序

1、河南中醫(yī)學院linux操作系統課程設計報告題目：基于Linux的進程調度模擬程序所在院系： 信息技術學院 專業(yè)年級： 2011級 計算機科學與技術 完成學生： 郭姍 指導教師： 阮 曉 龍 完成日期： 201X 年 06 月 22 日請按照課程設計完成日期填寫目 錄1. 課程設計題目概述32. 研究內容與目的43. 研究方法54. 研究報告65. 測試報告/實驗報告76. 課題研究結論87. 總結9目錄是不是更新一下1、課程設計題目概述此處為何出現空行隨著Linux系統的逐漸推廣，它被越來越多的計算機用戶所了解和應用. Linux是一個多任務的操作系統，也就是說，在同一個時間內，可以有多個進程

2、同時執(zhí)行。如果讀者對計算機硬件體系有一定了解的話，會知道我們大家常用的單CPU計算機實際上在一個時間片斷內只能執(zhí)行一條指令，那么Linux是如何實現多進程同時執(zhí)行的呢？原來Linux使用了一種稱為進程調度（process scheduling）的手段，首先，為每個進程指派一定的運行時間，這個時間通常很短，短到以毫秒為單位，然后依照某種規(guī)則，從眾多進程中挑選一個投入運行，其他的進程暫時等待，當正在運行的那個進程時間耗盡，或執(zhí)行完畢退出，或因某種原因暫停，Linux就會重新進行調度，挑選下一個進程投入運行。因為每個進程占用的時間片都很短，在我們使用者的角度來看，就好像多個進程同時運行一樣了。 此處

3、不應有空格本文就是對進程調度進行研究、實驗的。本文首先對Linux系統進行了簡要的介紹, 然后介紹了進程管理的相關理論知識。其次，又介紹最高優(yōu)先數優(yōu)先的調度算法（即把處理機分配給優(yōu)先數最高的進程）、先來先服務算法的相關知識，并對進程調度進行最高優(yōu)先數優(yōu)先的調度算法和先來先服務算法模擬實驗，并對比分析兩種算法的優(yōu)缺點，從而加深對進程概念和進程調度過程/算法的理解設計目的：在多道程序和多任務系統中，系統內同時處于就緒狀態(tài)的進程可能有若干個。也就是說能運行的進程數大于處理機個數。為了使系統中的進程能有條不紊地工作，必須選用某種調度策略，選擇某一進程占用處理機。使得系統中的進程能夠有條不紊的運行，同時

4、提高處理機的利用率以及系統的性能。所以設計模擬進程調度算法（最高優(yōu)先數優(yōu)先的調度算法、先來先服務算法），以鞏固和加深處理進程的概念，并且分析這兩種算法的優(yōu)缺點。關鍵詞：linux 進程調度 調度算法2. 研究內容與目的操作系統由四大功能模塊組成：進程管理、存儲器管理、設備管理和文件管理，進程管理是其中最重要的一個模塊。本文主要研究最高優(yōu)先數優(yōu)先的調度算法、先來先服務算法這兩種調度算法，并且分析比較這兩種算法的優(yōu)缺點。目的：進程是操作系統中最重要的概念，也是學習操作系統的關鍵。通過本次課程設計，要求理解進程的實質和進程管理的機制。掌握進程調度的工作流程以及進程調度的算法，并且分析比較這兩種算法的

5、優(yōu)缺點。3. 研究方法3.1研究方法3.1.1查找資料通過查找資料了解到：（1）優(yōu)先數調度算法簡介優(yōu)先數調度算法常用于批處理系統中。在進程調度中，每次調度時，系統把處理機分配給就緒隊列中優(yōu)先數最高的進程。它又分為兩種：非搶占式優(yōu)先數算法和搶占式優(yōu)先數算法在非搶占式優(yōu)先數算法下，系統一旦把處理機分配給就緒隊列中優(yōu)先數最高的進程后，這個進程就會一直運行，直到完成或發(fā)生某事件使它放棄處理機，這時系統才能重新將處理機分配給就緒隊列中的另一個優(yōu)先數最高的進程。在搶占式優(yōu)先數算法下，系統先將處理機分配給就緒隊列中優(yōu)先數最高的進程度讓它運行，但在運行的過程中，如果出現另一個優(yōu)先數比它高的進程，它就要立即停止

6、，并將處理機分配給新的高優(yōu)先數進程。（2）先來先服務算法如果早就緒的進程排在就緒隊列的前面，遲就緒的進程排在就緒隊列的后面，那么先來先服務(FCFS: first come first service)總是把當前處于就緒隊列之首的那個進程調度到運行狀態(tài)。也就說，它只考慮進程進入就緒隊列的先后，而不考慮它的下一個CPU周期的長短及其他因素。基本思想：先來先服務的作業(yè)調度算法：優(yōu)先從后備隊列中，選擇一個或多個位于隊列頭部的作業(yè)，把他們調入內存，分配所需資源、創(chuàng)建進程，然后放入“就緒隊列”一句話結束應該有標點符號。先來先服務的進程調度算法：從“就緒隊列”中選擇一個最先進入隊列的進程，為它分配處理器，

7、使之開始運行原理：按照進程進入就緒隊列的先后順序調度并分配處理機執(zhí)行。先來先服務調度算法是一種不可搶占的算法，先進入就緒隊列的進程，先分配處理機運行。一旦一個進程占有了處理機，它就一直運行下去，直到該進程完成工作或者因為等待某事件發(fā)生而不能繼續(xù)運行時才釋放處理機。、系統只要有按FIFO規(guī)則建立的后備作業(yè)隊列或就緒進程隊列即可，就是一個作業(yè)控制塊JCB或進程控制塊PCB加入隊列時加在相應隊列末尾。、調度退出隊列時從相應隊列首開始順序掃描，將相關的JCB或PCB調度移出相應隊列。3.2實驗方法3.2.1模擬法 根據最高優(yōu)先數優(yōu)先的調度算法、先來先服務算法的進程調度機制的流程，進行模擬這兩種算法的實

8、驗。首行縮進兩字符3.2.2控制法進行實驗時，輸入進程名、優(yōu)先數、到達時間、需要運行時間、已用CPU時間、進程狀態(tài)。3.2.3觀察法觀察實驗的結果，分析進程調度流程。3.2.4比較法通過觀察實驗結果，比較兩種調度算法的優(yōu)缺點。3.3可行性分析（課題理論上的要求、實踐的可操作性、本人能力和現實條件（相關案例、資料等）的許可等內容）3.3.1環(huán)境運行在VMware-workstation-full-10.0.0-上，導入CentOS操作系統，在CentOS操作系統上運行。CentOS操作系統是Linux發(fā)行版之一，它是來自于Red Hat Enterprise Linux依照開放源代碼規(guī)定釋出的源

9、代碼所編譯而成。相對于其他 Linux 發(fā)行版，其穩(wěn)定性值得信賴。因為CentOS操作系統安裝了gcc編譯器，能編譯C語言。3.3.2實踐的可操作性 此處不應有空格在對linux進程調度機制以及調度算法進行深入分析后，根據對于最高優(yōu)先數優(yōu)先的調度算法采用最高優(yōu)先數算法的動態(tài)優(yōu)先數法則控制進程：系統把處理機分配給就緒隊列中優(yōu)先數最高的進程后，如果運行一個時間片后，進程的已占用CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間，也就是進程還需要繼續(xù)運行，此時應將進程的優(yōu)先數減1（即降低一級），然后把它插入就緒隊列等待CPU，而先來先服務

10、是從“就緒隊列”中選擇一個最先進入隊列的進程，為它分配處理器，使之開始運行而制定實驗方案的。 3.3.3本人能力 雖然我對linux的進程調度方面的知識還有很多不知道的知識，但我是在不斷學習的 ，遇到不懂得就通過查資料或請教他人的方法，不斷地學習。為何如此多的換行4. 研究報告4.1最高優(yōu)先數優(yōu)先的調度算法（搶占式）4.1.1實驗原理1、進程調度算法：采用最高優(yōu)先數優(yōu)先的調度算法（即把處理機分配給優(yōu)先數最高的進程）。 2、每個進程有一個進程控制塊（PCB）表示。進程控制塊可以包含如下信息：進程名、優(yōu)先數、需要運行時間、已用CPU時間、進程狀態(tài)等等。 3、進程的優(yōu)先數及需要的運行時間事先人為地指

11、定。 4、 每個進程的狀態(tài)可以是就緒 W（Wait）、運行R（Run）、或完成F（Finish）三種狀態(tài)之一。 5、進程的運行時間以時間片為單位進行計算。摘抄的部分是不是應該整理一下？ 6、 就緒進程獲得CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。 7、采用最高優(yōu)先數算法的動態(tài)優(yōu)先數法則控制進程：如果運行一個時間片后，進程的已占用CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間，也就是進程還需要繼續(xù)運行，此時應將進程的優(yōu)先數減1（即降低一級），然后把它插入就緒隊列等待CPU。 8、每進行一次調度程序都打印一次運行進

12、程、就緒隊列、以及各個進程的PCB，以便進行檢查。 9、 重復以上過程，直到所要進程都完成為止。4.1.2實驗內容 1、數據結構（1）進程控制塊結構PCB：是struct定義的結構體，定義如下：typedef struct pcbchar qname20;/*進程名*/char state; /*進程狀態(tài)*/int super; /*進程優(yōu)先級*/int ndtime; /*進程需要運行的時間*/int runtime; /*進程已運行的時間*/int cpu; /*進程當前獲得的時間片大小*/PCB;（2） 隊列結點Node，結點儲存PCB信息，定義如下：typedef struct nod

13、ePCB data; /*結點數據*/struct node *next; /*指向下一結點的指針*/Node;（3）由隊列結點Node擴展的隊列Queue,定義如下：typedef struct queueNode *front;/*隊首*/Node *rear;/*隊尾*/Queue;2相關函數（1）判斷一個隊列q是否為空的函數int is_empty(Queue *q);（2）將進程控制塊x加入隊列q的函數void enqueue(PCB x,Queue *q);（3）刪除隊列q的隊首進程，將其值賦給x并修改狀態(tài)的函數void dequeue(PCB *x,Queue *q);該函數將隊

14、列q的隊首進程刪除，由于可能該進程未運行完畢，需進入下一優(yōu)先級隊列， 所以先修改其結構體內成員變量：已運行時間為上次已運行時間加上這次獲得的cpu時間；優(yōu)先級減1（若該進程已是最低優(yōu)先級，則將在主控過程中恢復）；下次獲得的時間片為這次的時間片加1。然后將修改后的進程賦給一個臨時PCB變量x，以便將x插入下一優(yōu)先級隊列。 （4）主函數利用上述的數據結構和函數實現模擬進程調度。排版不正確3. 進程產生模擬通過標準輸入模擬產生進程：先要求輸入進程數目，再依次輸入各個進程的進程名、進程優(yōu)先數、進程需要運行的時間。4.1.3參考代碼#include#include#include#include#def

15、ine PCB_LEN sizeof(PCB)#define NODE_LEN sizeof(Node)#define QUEUE_LEN sizeof(Queue)/*進程控制塊結構PCB*/typedef struct pcbchar qname20;/*進程名*/ char state; /*進程狀態(tài)*/int super; /*進程優(yōu)先級*/int ndtime; /*進程需要運行的時間*/int runtime; /*進程已運行的時間*/int cpu; /*進程當前獲得的時間片大小*/PCB;/*隊列結點，結點儲存PCB信息*/typedef struct nodePCB data

16、; struct node *next;Node;/*實現進程控制塊的隊列*/typedef struct queueNode *front;Node *rear;Queue;/*判斷隊列是否為空*/int is_empty(Queue *q)if(q-front)return 0;elsereturn 1;/*將進程控制塊x加入隊列q*/void enqueue(PCB x,Queue *q) Node *p=(Node *)malloc(NODE_LEN);(p-data).state=x.state;(p-data).super=x.super;(p-data).ndtime=x.ndt

17、ime;(p-data).runtime=x.runtime;(p-data).cpu=x.cpu;strcpy(p-data).qname,x.qname);p-next=0;if(q-front)q-rear-next=p;elseq-front=p;q-rear=p;/*刪除隊列q的隊首進程，將其值賦給x并修改狀態(tài)*/void dequeue(PCB *x,Queue *q)Node *p=(Node *)malloc(NODE_LEN); if(is_empty(q)return;/*進入下一優(yōu)先級隊列之前修改狀態(tài)*/x-state=W;/*狀態(tài)改為就緒*/strcpy(x-qname

18、,(q-front-data).qname);/*已運行時間為上次已運行時間加上這次獲得的cpu時間*/x-runtime=(q-front-data).runtime+(q-front-data).cpu;/*優(yōu)先級減1，若該進程已是最低優(yōu)先級，則將在主控過程中恢復*/x-super=(q-front-data).super-1;x-ndtime=(q-front-data).ndtime;/*下次獲得的時間片為這次的時間片加1*/x-cpu=(q-front-data).cpu+1;p=q-front;q-front=q-front-next;free(p);/*主控過程*/void ma

19、in()Queue *queue=NULL;/*設置就緒隊列數組*/Node *wait=(Node *)malloc(NODE_LEN);PCB x;int numberOFcourse,i,j,super,time;int hight=0,num=0;int temp_ndtime,temp_runtime,temp_cpu;char name20;printf(n請輸入進程總個數?);scanf(%d,&numberOFcourse);/*為隊列數組開辟空間，每個數組表示不同的優(yōu)先級隊列*/queue=(Queue *)calloc(numberOFcourse,QUEUE_LEN);/

20、*輸入各進程信息并初始化，并將其加入相應的優(yōu)先級隊列*/for(i=0;ihight)hight=super;printf(n輸入進程運行時間：);scanf(%d,&time);strcpy(x.qname,name);x.state=W; x.super=super;x.ndtime=time;x.runtime=0;x.cpu=1;enqueue(x,&queuesuper-1);printf(nn);/*進程調度過程*/for(i=hight-1;i=0;i-)/*從最高優(yōu)先級隊列開始調度進程，直到該隊列為空，則調度下一優(yōu)先級隊列*/while(!is_empty(&queuei)nu

21、m+;/*調度次數*/printf(按任一鍵繼續(xù).n);getch();printf(The execute number:%dnn,num);/*打印正在運行進程*/(queuei.front)-data).state=R;printf(*當前工作的進程是：%sn,(queuei.front)-data).qname);printf(qname state super ndtime runtimen);printf(%s,(queuei.front)-data).qname); printf(R);printf(%d,(queuei.front)-data).super); printf(%

22、d,(queuei.front)-data).ndtime);printf(%dnn,(queuei.front)-data).runtime);/*計算一個進程運行一個時間片后，還需要運行的時間temp_time*/ temp_ndtime=(queuei.front)-data).ndtime;temp_runtime=(queuei.front)-data).runtime; temp_cpu=(queuei.front)-data).cpu;temp_ndtime=temp_ndtime-temp_runtime-temp_cpu;/*若該進程已運行完畢*/if(temp_ndtime

23、data).qname); (queuei.front)-data).state=F; dequeue(&x,&queuei);/*若該進程未運行完畢*/else dequeue(&x,&queuei);/*將其刪除出當前隊列*/*若原優(yōu)先級不是最低優(yōu)先級，則插入下一優(yōu)先級隊列*/if(i0)enqueue(x,&queuei-1);/*若原優(yōu)先級是最低優(yōu)先級，則插入當前隊列末尾*/else/*由于刪除操作中將優(yōu)先級減1，所以在此恢復*/x.super=x.super+1; enqueue(x,&queuei);/*打印就緒隊列狀態(tài)*/ printf(*當前就緒隊列狀態(tài)為：n);for(j=i

24、;j=0;j-)if(queuej.front)wait=queuej.front;while(wait)printf(qname state super ndtime runtimen); printf(%s,(wait-data).qname); printf(W); printf(%d,(wait-data).super); printf(%d ,(wait-data).ndtime); printf(%dnn,(wait-data).runtime); wait=wait-next; printf(n);/*結束*/printf(進程已經全部完成n);free(wait);free(q

25、ueue);getch();4.2先來先服務算法4.2.1實驗原理先來先服務調度算法按照進程進入就緒隊列的先后順序調度并分配處理機執(zhí)行。先來先服務調度算法是一種不可搶占的算法，先進入就緒隊列的進程，先分配處理機運行。一旦一個進程占有了處理機，它就一直運行下去，直到該進程完成工作或者因為等待某事件發(fā)生而不能繼續(xù)運行時才釋放處理機。4.2.2參考代碼#include #include #include using namespace std; #define MAX 10 char processMAX=; /進程名 int arrivetimeMAX;/達到時間 int servicetimeM

26、AX;/服務時間 int finishtimeMAX; /完成時間 int turnovertimeMAX;/周轉時間 double avgturnovertime; /平均周轉時間 double powertimeMAX; /帶權周轉時間 double avgpowertime; /平均帶權周轉時間 int init(); void FCFS(); void output(); void showsingle(int* arr,int len); /初始化，并返回進程數 int init() cout 輸入進程隊列名(用單個字母表示一個進程,字母間用tab間隔) endl; int i=0;

27、 while(iMAX) cin.get(processi); if(processi= | processi=/t) continue; if(processi=q | processi=/n) processi=/0; break; i+; int len=strlen(process); cout 依次輸入進程到達時間(時間之間用tab間隔) endl; for(int ix=0; ix arrivetimeix; cout 依次輸入服務時間(時間之間用tab間隔) endl; for(ix=0; ix servicetimeix; return len; void FCFS(int l

28、en) /完成時間的計算 for(int ix=0; ixlen; ix+) finishtimeix=accumulate(servicetime,servicetime+ix+1,0); /周轉時間計算 for(ix=0; ixlen; ix+) turnovertimeix=finishtimeix-arrivetimeix; avgturnovertime=accumulate(turnovertime,turnovertime+len,0)*1.0/len; /帶權周轉時間計算 for(ix=0; ixlen; ix+) powertimeix=turnovertimeix*1.0/

29、servicetimeix; /平均帶權周轉時間 double tmptotal=0.0; for(ix=0; ixlen; ix+) tmptotal+=powertimeix; avgpowertime=tmptotal/len; void output() cout endlendl; cout+endl; int len=strlen(process); /顯示進程序列 for(int ix=0; ixlen; ix+) cout processix /t; cout endl; /顯示到達時間序列 showsingle(arrivetime,len); /顯示服務時間序列 shows

30、ingle(servicetime,len); cout endlendl; /顯示完成時間序列 showsingle(finishtime,len); /顯示周轉時間序列 showsingle(turnovertime,len); cout 平均周轉時間 : avgturnovertime endl; /顯示帶權周轉時間序列 for(ix=0; ixlen; ix+) cout powertimeix /t; cout endl; cout 平均帶權周轉時間: avgpowertime endl; cout +endl; /對int類型的數組進行格式化輸出 void showsingle(i

31、nt* arr,int len) for(int ix=0; ixlen; ix+) cout arrix /t; cout endl; int main() cout /t/t|本程序是先來先服務算法| endl; int len = init(); FCFS(len); output(); system(PAUSE); return 0; 5. 測試報告/實驗報告5.1最高優(yōu)先數優(yōu)先的調度算法5.1.1實驗結果【輸入輸出樣例】請輸入進程總個數?4為何有“？”進程號 NO.0輸入進程名：aa輸入進程優(yōu)先數：2輸入進程運行時間：2進程號 NO.1輸入進程名：vv輸入進程優(yōu)先數：3輸入進程運行時

32、間：2進程號 NO.2輸入進程名：rr輸入進程優(yōu)先數：1輸入進程運行時間：3進程號 NO.3輸入進程名：kk輸入進程優(yōu)先數：2輸入進程運行時間：1按任一鍵繼續(xù).The execute number:1*當前工作的進程是：vvqname state super ndtime runtimevv R 3 2 0*當前就緒隊列狀態(tài)為：qname state super ndtime runtimeaa W 2 2 0qname state super ndtime runtimekk W 2 1 0qname state super ndtime runtimevv W 2 2 1qname sta

33、te super ndtime runtimerr W 1 3 0按任一鍵繼續(xù).The execute number:2*當前工作的進程是：aaqname state super ndtime runtimeaa R 2 2 0*當前就緒隊列狀態(tài)為：qname state super ndtime runtimekk W 2 1 0qname state super ndtime runtimevv W 2 2 1qname state super ndtime runtimerr W 1 3 0qname state super ndtime runtimeaa W 1 2 1按任一鍵繼續(xù).

34、The execute number:3*當前工作的進程是：kkqname state super ndtime runtimekk R 2 1 0進程kk已完成*當前就緒隊列狀態(tài)為：qname state super ndtime runtimevv W 2 2 1qname state super ndtime runtimerr W 1 3 0qname state super ndtime runtimeaa W 1 2 1按任一鍵繼續(xù).The execute number:4*當前工作的進程是：vvqname state super ndtime runtimevv R 2 2 1進

35、程vv已完成*當前就緒隊列狀態(tài)為：qname state super ndtime runtimerr W 1 3 0qname state super ndtime runtimeaa W 1 2 1按任一鍵繼續(xù).The execute number:5*當前工作的進程是：rrqname state super ndtime runtimerr R 1 3 0*當前就緒隊列狀態(tài)為：qname state super ndtime runtimeaa W 1 2 1qname state super ndtime runtimerr W 1 3 1按任一鍵繼續(xù).The execute numb

36、er:6*當前工作的進程是：aaqname state super ndtime runtimeaa R 1 2 1進程aa已完成*當前就緒隊列狀態(tài)為：qname state super ndtime runtimerr W 1 3 1按任一鍵繼續(xù).The execute number:7*當前工作的進程是：rrqname state super ndtime runtimerr R 1 3 1進程rr已完成*當前就緒隊列狀態(tài)為：進程已經全部完成5.1.2結果分析本程序利用標準輸入輸出模擬了進程調度過程。輸入各個進程的優(yōu)先級和需要運行的時間等信息，輸出給出了每進行一次調度的運行進程、就緒隊列、

37、以及各個進程的 PCB信息，每當一個進程完成運行，輸出該進程已完成的信息，最后當所有進程都完成后給出所有進程都完成的信息。因為剛開始vv的優(yōu)先級高，所以它先搶占CPU，運行一個時間單位后，vv的優(yōu)先級數減少1，此時vv的優(yōu)先級與aa、kk相等，但比rr大，所以vv排在就緒隊列kk后面，aa處于運行狀態(tài)；后面的也是這樣分析。從而可以看出：剛開始優(yōu)先數大的先運行，當進程運行一個時間片后，進程的已占用CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間，也就是進程還需要繼續(xù)運行，此時應將進程的優(yōu)先數減1（即降低一級），且此時有和它相等的優(yōu)先

38、數或比它大的優(yōu)先數，則把它插入就緒隊列等待CPU。 通過以上述數據測的最高優(yōu)先數算法，可以看出這種算法的優(yōu)點是可使資源利用率得以提高，公平性好，缺點是系統開銷大，實現比較復雜。5.2先來先服務算法5.2.1實驗結果/*running result: |本程序是先來先服務算法| 輸入進程隊列名(用單個字母表示一個進程,字母間用tab間隔) a b c d e 依次輸入進程到達時間(時間之間用tab間隔) 0 1 2 3 4 依次輸入服務時間(時間之間用tab間隔) 4 3 5 2 4 + a b c d e 0 1 2 3 4 4 3 5 2 4 4 7 12 14 18 4 6 10 11 14 平均周轉時間 :9 1 2 2 5.5 3.5 平均帶權周轉時間:2.8 + 請按任意鍵繼續(xù). . . */ 5.2.2結果分析輸入的a、b、c、d、e