最終OS實驗報告

1、操作系統實驗報告 學生學院_ 計算機學院_專業(yè)班級_ _網絡工程_學 號 3113006565 學生姓名_ 李康賢_ 指導教師_ 李敏 _ _2015年1 月 2 日 實驗一 進程調度1、 實驗目的用高級語言編寫和調試一個進程調度程序，以加深對進程的概念及進程調度算法的理解。2：實驗內容及要求設計一個有 N個進程共行的進程調度程序。 要求采用最高優(yōu)先數優(yōu)先的調度算法（即把處理機分配給優(yōu)先數最高的進程），時間片輪轉算法，多級反饋隊列調度算法這三種算法。 每個進程有一個進程控制塊（ PCB）表示。進程控制塊可以包含如下信息：進程名、優(yōu)先數、到達時間、需要運行時間、已用CPU時間、進程狀態(tài)等等。 進

2、程的優(yōu)先數及需要的運行時間可以事先人為地指定（也可以由隨機數產生）。進程的到達時間為進程輸入的時間。進程的運行時間以時間片為單位進行計算。 每個進程的狀態(tài)可以是就緒 W（Wait）、運行R（Run）、或完成F（Finish）三種狀態(tài)之一。 就緒進程獲得 CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。 如果運行一個時間片后，進程的已占用 CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間，也就是進程還需要繼續(xù)運行，此時應將進程的優(yōu)先數減1（即降低一級），然后把它插入就緒隊列等待CPU。 每進行一次調度程序都打印一次運行進

3、程、就緒隊列、以及各個進程的 PCB，以便進行檢查。 重復以上過程，直到所要進程都完成為止。3：實驗設計方案及原理 簡單輪轉法：所有就緒進程按 FCFS排成一個隊列，總是把處理機分配給隊首的進程，各進程占用CPU的時間片相同。如果運行進程用完它的時間片后還為完成，就把它送回到就緒隊列的末尾，把處理機重新分配給隊首的進程。直至所有的進程運行完畢。 多級反饋隊列調度算法：當一個新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執(zhí)行時，如能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS

4、原則等待調度執(zhí)行，以此類推。4、程序流程圖（一個實驗有多個算法的應該分別給出） 簡單論轉法 N Y N Y多級反饋： N Y N Y Y N5、各程序之間的調用關系 Main函數進入，調用input方法建立進程控制塊，再調用check方法進程查看函數，running方法中調用sort方法，sort方法實現了簡單論轉法的算法，最后調用disp方法打印進程，直到全部結束; 對于多級反饋隊列調度算法，調用input方法建立進程控制塊，再調用insertProcess方法確定隊列，調用sort方法將進程進行排列，當滿足在第一隊列時間片內可以完成進程時，則在此隊列繼續(xù)執(zhí)行，否則建立一個新隊列，把該進程未

5、完成的部分放到下一個隊列中，直到該隊列所有進程完成時，再去執(zhí)行下一個隊列中的進程。調用check方法查看進程的運行狀態(tài)以及就緒的進程，調用running方法運行，當需要添加新進程時，調用A方法，在A方法中再調用sort方法排列，這樣就可以保證后進的作業(yè)不一定慢完成。從而體現多級反饋隊列調度算法的作用。6、重要數據結構或源程序中疑難部分的說明，需附詳細注釋void running() int i;(ready->rtime)+;ready->etime -;if(ready->rtime = ready->ntime)/ 進程在該隊列的時間時間片內完成，然后銷毀進程des

6、troy();return;else if(ready ->etime = 0)/當時間片用完，剩余部分添加到下一個隊列int time = 2;/時間片翻倍，因為初始時間為1(ready->queue)+;/隊列數比原先加1for(i = 2; i != ready->queue; +i)time *= 2;/以后每增加一條隊列，時間片都為原先2倍ready->etime = time;ready->state='w'/狀態(tài)為等待，僅當前一隊列的全部進程運行完畢在運行sort();調用sort方法重新排列，再重新運行接下來的等級高的進程7、程序運

7、行結果多級反饋：8、結果分析與實驗小結 結果分析：對于簡單論轉法，只需比較進程到達時間以及每個進程運行所需的時間。對于多級反饋隊列算法，由原先的進程1，2先到達，進程1先運行1個時間片，剩余的進程1下降到隊列2，輪到進程2在原隊列運行，剩余的進程2下降到隊列2，當進程1完成后，此時新增加進程3，但是進程3的所需運行時間比進程2小，所以最終結果為進程3先于進程2早完成。這樣就可以保證后進的作業(yè)不一定慢完成。從而體現多級反饋隊列調度算法的作用。小結：簡單輪轉法原理簡單，但是可能產生進程等待時間過長的問題，多級反饋隊列算法則兼顧大小進程，且對進程到達時間也很好兼顧到，時比較好的一種算法。通過此實驗，

8、我感覺了編程的能力是極其重要的，對于實現某些功能，要先分析其邏輯，再慢慢結合編程技巧，一點點把所需要的功能以程序的方法體現出來。很有意義。 實驗二 作業(yè)調度1、 實驗目的本實驗要求學生模擬作業(yè)調度的實現，用高級語言編寫和調試一個或多個作業(yè)調度的模擬程序，了解作業(yè)調度在操作系統中的作用，以加深對作業(yè)調度算法的理解。2、 實驗內容及要求1、為單道批處理系統設計一個作業(yè)調度程序1) 編寫并調試一個單道處理系統的作業(yè)等待模擬程序。2) 作業(yè)調度算法：分別采用先來先服務（FCFS）、響應比高者優(yōu)先（HRNN）的調度算法。 3) 由于在單道批處理系統中，作業(yè)一投入運行，它就占有計算機的一切資源直到作業(yè)完成

9、為止，因此調度作業(yè)時不必考慮它所需要的資源是否得到滿足，它所占用的 CPU時限等因素。4) 每個作業(yè)由一個作業(yè)控制塊JCB表示，JCB可以包含如下信息：作業(yè)名、提交時間、所需的運行時間、所需的資源、作業(yè)狀態(tài)、鏈指針等等。作業(yè)的狀態(tài)可以是等待W(Wait)、運行R(Run)和完成F(Finish)三種狀態(tài)之一。每個作業(yè)的最初狀態(tài)總是等待W。5) 對每種調度算法都要求打印每個作業(yè)開始運行時刻、完成時刻、周轉時間、帶權周轉時間，以及這組作業(yè)的平均周轉時間及帶權平均周轉時間，并比較各種算法的優(yōu)缺點。3、 實驗設計方案及原理首先本次實驗將會選擇單道作業(yè)調度，所以不需要考慮內存分配情況以及磁帶機分配情況，

10、因為在單道調度中，只要作業(yè)被調進內存之后，它就會一直到完成才可以調出內存。在程序中采用先來先服務算法和高響應比優(yōu)先算法，利用switch語句選擇將要采取的方法。對于先來先服務算法，首先按照每個作業(yè)的到達時間，采取先到達先被調度的原則，知道其完成再輪到下一個最先到達的作業(yè)，將其調入內存。對于高響應比優(yōu)先算法，首先將最先到達的作業(yè)先調入內存，當第一個作業(yè)完成時候，在這一刻利用算法計算出剩下的作業(yè)在此時的響應比，只把響應比最高的作業(yè)調入內存。以此類推，每一次完成一個作業(yè)之后都計算剩下的作業(yè)在此刻的響應比，以此調入，知道結束。最后得出平均周轉時間及帶權平均周轉時間。4、 程序流程圖 FCFS算法： N

11、Y5、 HRNN算法： Y N Y N6、 各程序之間的調用關系Main函數開始，當選擇1采用先來先服務算法時，調用FCFS方法，再調用initial方法，建立作業(yè)控制塊隊列,先將其排成先來先服務的模式隊列，根據該方法選擇出最先到達的作業(yè)，調用running方法進行運行，計算作業(yè)運行后的完成時間,周轉時間等等，再調用調用disp()方法,顯示作業(yè)運行情況，當作業(yè)運行結束時調用free方法釋放內存。當采用高響應比算法時，調用HRRN方法，再調用initial方法，建立作業(yè)控制塊隊列,先將其排成先來先服務的模式隊列，在調用super方法計算出每個時刻的各作業(yè)響應比，選擇響應比最大的作業(yè)調用runn

12、ing方法，計算作業(yè)運行后的完成時間,周轉時間等等，再調用調用disp()方法,顯示作業(yè)運行情況，當作業(yè)運行結束時調用free方法釋放內存。最后當全部作業(yè)都運行結束，調用final方法，最后打印作業(yè)的平均周轉時間,平均帶權周轉時間，程序結束，退出程序。6、重要數據結構或源程序中疑難部分的說明，需附詳細注釋void super() /計算隊列中各個作業(yè)的響應比 JCB *padv; padv=ready; do if(padv->state='W'&&(padv->rtime)<=times) /*當作業(yè)狀態(tài)為W（等待）時且其到達時間小于上一作業(yè)

13、完成時間，也就是現在這個時刻 padv->super=(float)(times-padv->rtime+padv->ntime)/padv->ntime; /*計算方法為（等待時間+需要運行的時間）/需要運行的時間，從而得出響應比； padv=padv->next; /指針指向下一個作業(yè)，計算每一個作業(yè)的響應比 while(padv!=NULL); 7、 程序運行結果先來先服務算法： 高響應比算法 8、 結果分析與實驗小結結果分析：對于FCFS算法，由于各個作業(yè)的到達時間為依此遞增，根據先到先服務，所以他們的運行次序為1，2，3，4，5。對于HRRN算法，先將第

14、一個到達的作業(yè)運行，待結束后計算出個作業(yè)的響應比，所以他們的運行次序為1，2，3，5，4. 實驗小結：此次試驗的兩種算法原理比較簡單，說以實現起來不算太難。通過實驗，我可以從程序上更好地深刻了解兩種方法的原理。兩種方法比較，我更加傾向于先來先服務算法，由于其簡單，在一般的練習中他的計算也更加簡單。但是，高響應比算法則是既考慮了作業(yè)等待時間，又考慮作業(yè)運行時間的調度算法，既照顧了短作業(yè)，又不致使長作業(yè)的等待時間過長，從而改善了處理機調度的性能，雖然在考試中它的計算比較復雜。所以，有利必有失，每種算法都有其優(yōu)點，但也有令學生有種比較復雜的感覺。實驗三 儲存管理（最佳適應算法）1、 實驗目的1、通過

15、編寫和調試存儲管理的模擬程序以加深對存儲管理方案的理解。熟悉虛存管理的各種頁面淘汰算法。2、通過編寫和調試地址轉換過程的模擬程序以加強對地址轉換過程的了解。2、 實驗內容及要求1：設計一個請求頁式存儲管理方案。并編寫模擬程序實現之。產生一個需要訪問的指令地址流。它是一系列需要訪問的指令的地址。為不失一般性，你可以適當地（用人工指定地方法或用隨機數產生器）生成這個序列，使得 50的指令是順序執(zhí)行的。25的指令均勻地散布在前地址部分，25的地址是均勻地散布在后地址部分。 2：為簡單起見。頁面淘汰算法采用 FIFO頁面淘汰算法，并且在淘汰一頁時，只將該頁在頁表中抹去。而不再判斷它是否被改寫過，也不將

16、它寫回到輔存。 3：具體的做法可以是： 產生一個需要訪問的指令地址流； 指令合適的頁面尺寸（例如以 1K或2K為1頁）； 指定內存頁表的最大長度，并對頁表進行初始化； 每訪問一個地址時，首先要計算該地址所在的頁的頁號，然后查頁表，判斷該頁是否在主存如果該頁已在主存，則打印頁表情況；如果該頁不在主存且頁表未滿，則調入一頁并打印頁表情況；如果該頁不在主存且頁表已滿，則按 FIFO頁面淘汰算法淘汰一頁后調入所需的頁，打印頁表情況； 逐個地址訪問，直到所有地址訪問完畢。3、 實驗設計方案及原理最佳適應算法循環(huán)首次適應算法每次為作業(yè)分配內存時，總是先把能滿足要求又是最小的空閑分區(qū)分配給作業(yè)，避免大材小用

17、。為了加上尋找，該算法要求將所有的空閑分區(qū)按容量從小到大的順序形成一空閑分區(qū)連。這樣，第一次找到的能滿足要求的空閑分區(qū)必然是最佳的。雖然如此，但是最佳算法并非是最佳的。因為每次分配后所切割下來的剩余部分總是最小的，這樣在儲存器中會留下許多難以利用的碎片。設計結構體分別顯示已分配分區(qū)以及空閑分區(qū)，將空閑分區(qū)按照大小排序起來，其次可以根據要求事先確定最大作業(yè)數以及空閑區(qū)表，每個分區(qū)都根據接下來的算法執(zhí)行相應程序，打印出來，當回收內存時重新比較空閑分區(qū)大小，在下一次作業(yè)需要分配內存時即可將最佳的分區(qū)分配給它。 循環(huán)首次適應算法是首次適應算法的變種。在分配內存空間時，不需要再每次從表頭（鏈首）開始查找

18、，而是從上次找到空閑區(qū)的下一個空閑開始查找，直到找到第一個能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請求大小相等的內存空間分配給作業(yè)。此算法旨在分配平均內存，能使內存中的空閑區(qū)分布得較均勻。在該算法中，首先確定內存總大小，再把主存中所有空閑區(qū)按其物理地址遞增的次序排列。在為作業(yè)分配存儲空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到第一個能滿足要求的空閑區(qū)，從中劃出與請求的大小相等的存儲空間分配給相應的作業(yè)，余下的空閑區(qū)仍留在空閑區(qū)表或鏈中。根據提示需要進行釋放內存或者分配內存。4、 程序流程圖最佳適應算法： 否 是5、 程序流程圖循環(huán)首次適應算法： 否 是 是 是 否6、 各程

19、序之間的調用關系最佳適應算法：首先從main函數開始，輸入總內存大小。根據選擇輸入數字獲取相應操作。在分配內存中，調用F方法，在該方法中先尋找是否還有剩余足夠多的內存，當有時在尋找尋找空間大于該作業(yè)的最小空閑區(qū)，進行分配。當回收內存時，調用H方法進行回收。首先確定回收作業(yè)名字，查找該作業(yè)的已分配分區(qū)，然后回收內存，將作業(yè)名改為0。循環(huán)首次適應算法：首先從main函數開始，調用init方法初始化內存大小和空閑分區(qū)鏈的頭結點，其中在init方法中調用genti方法一起進行。因為開始分配空間內存時需要調用genti方法。黨作業(yè)需要分配內存時，調用allocmem方法進行分配，并且調用check函數進

20、行監(jiān)督檢查，當輸入數據有誤時及時制止；同理當需要進行釋放內存時調用realse函數，同時調用check函數一起運行。根據每次輸入輸出都需要打印出當前界面，空閑分區(qū)表，空閑分區(qū)鏈等信息。7、 重要數據結構或源程序中疑難部分的說明，需附詳細注釋最佳適應算法void F(char J,float xk) /*采用最佳分配算法分配該作業(yè)大小的空間*/ int i,k; float ad; k=-1; for(i=0; i<m; i+) /*尋找空間大于該作業(yè)的最小空閑區(qū)*/ if(free_tablei.length>=xk&&free_tablei.flag=1)/僅當空

21、閑分區(qū)內存大于所需分配的內存時 if(k=-1|free_tablei.length<free_tablek.length) k=i; if(k=-1) /*未找到可用空閑區(qū)，返回*/ printf("內存不足n"); return; /*開始分配：若空閑區(qū)大小與要求分配的空間差小于msize大小，則空閑區(qū)全部分配； 若空閑區(qū)大小與要求分配的空間差大于msize大小，則從空閑區(qū)劃出一部分分配*/ if(free_tablek.length-xk<=minisize) free_tablek.flag=0; ad=free_tablek.address;/將可以分

22、配的內存分配給作業(yè)，并將該分區(qū)地址表示為作業(yè)地址 xk=free_tablek.length; else free_tablek.length=free_tablek.length-xk; ad=free_tablek.address+free_tablek.length; /*修改已分配區(qū)表*/ i=0; while(used_tablei.flag!=0&&i<n) /*空表目*/ i+; if(i>=n) /*已經沒有表目可填寫已分配分區(qū)*/ printf("錯誤n"); /*修正空閑區(qū)表*/ if(free_tablek.flag=0)

23、/*前面找到的是整個空閑分區(qū)*/ free_tablek.flag=1; else /*前面找到的是某個空閑分區(qū)的一部分*/ free_tablek.length=free_tablek.length+xk; return; else /*修改已分配表*/ used_tablei.address=ad; used_tablei.length=xk; used_tablei.flag=J; return;循環(huán)首次適應算法bool release(MEM *pm, int base, int size)/釋放內存空間8、 MEM 

24、;*p = pm;  /指針p指向結構體分區(qū)鏈表節(jié)點9、  if(!check(pm, base ,size)   return false; 10、    while(p->next)  /鏈表連接，逐漸拓展分配內存11、  if(base + size <= p->next->base)   /上一個空閑分區(qū)的下一個空閑分區(qū)12、

25、  break;  13、  p = p->next;/滿足時分配，指針指向下一個分區(qū)14、    15、  if(base = p->base + p->size)/低地址相鄰，高地址分開 16、   if(p ->next && p->next->base = base + size)17、 /釋放區(qū)上

26、下都相鄰，將鏈表中地址按相連順序一一釋放  18、   p->size += size + p->next->size;  19、   temp = p->next; 20、    p->next = p->next->next;  21、   free(temp); 22、   els

27、e/僅與低地址相鄰    23、 p->size += size;  24、   25、 else if (p->next && p->next->base = base +size)/僅高地址相鄰  26、  p->next->base = base;   p->next->size

28、 += size;  27、 else28、 /*釋放區(qū)上下與空閑區(qū)都不相鄰 ，釋放后指針向前，這樣才可以滿足下一次分配時在前一個分區(qū)的下一個空閑分區(qū)開始查找空閑分區(qū)。*/29、   temp = getMEM(); 30、   temp->size = size; 31、   temp->base = base; 32、   temp->next = p->next;  33、  p->next = temp;  34、     35、