最終OS實驗報告

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

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

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

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

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

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

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

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

9、為止，因此調(diào)度作業(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) 對每種調(diào)度算法都要求打印每個作業(yè)開始運行時刻、完成時刻、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間，以及這組作業(yè)的平均周轉(zhuǎn)時間及帶權(quán)平均周轉(zhuǎn)時間，并比較各種算法的優(yōu)缺點。3、 實驗設(shè)計方案及原理首先本次實驗將會選擇單道作業(yè)調(diào)度，所以不需要考慮內(nèi)存分配情況以及磁帶機分配情況，

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

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

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

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

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

15、編寫和調(diào)試存儲管理的模擬程序以加深對存儲管理方案的理解。熟悉虛存管理的各種頁面淘汰算法。2、通過編寫和調(diào)試地址轉(zhuǎn)換過程的模擬程序以加強對地址轉(zhuǎn)換過程的了解。2、 實驗內(nèi)容及要求1：設(shè)計一個請求頁式存儲管理方案。并編寫模擬程序?qū)崿F(xiàn)之。產(chǎn)生一個需要訪問的指令地址流。它是一系列需要訪問的指令的地址。為不失一般性，你可以適當(dāng)?shù)兀ㄓ萌斯ぶ付ǖ胤椒ɑ蛴秒S機數(shù)產(chǎn)生器）生成這個序列，使得 50的指令是順序執(zhí)行的。25的指令均勻地散布在前地址部分，25的地址是均勻地散布在后地址部分。 2：為簡單起見。頁面淘汰算法采用 FIFO頁面淘汰算法，并且在淘汰一頁時，只將該頁在頁表中抹去。而不再判斷它是否被改寫過，也不將

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

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

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

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

20、行監(jiān)督檢查，當(dāng)輸入數(shù)據(jù)有誤時及時制止；同理當(dāng)需要進行釋放內(nèi)存時調(diào)用realse函數(shù)，同時調(diào)用check函數(shù)一起運行。根據(jù)每次輸入輸出都需要打印出當(dāng)前界面，空閑分區(qū)表，空閑分區(qū)鏈等信息。7、 重要數(shù)據(jù)結(jié)構(gòu)或源程序中疑難部分的說明，需附詳細注釋最佳適應(yīng)算法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)/僅當(dāng)空

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

22、配的內(nèi)存分配給作業(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) /*已經(jīng)沒有表目可填寫已分配分區(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)首次適應(yīng)算法bool release(MEM *pm, int base, int size)/釋放內(nèi)存空間8、 MEM 

24、;*p = pm;  /指針p指向結(jié)構(gòu)體分區(qū)鏈表節(jié)點9、  if(!check(pm, base ,size)   return false; 10、    while(p->next)  /鏈表連接，逐漸拓展分配內(nèi)存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、