操作系統(tǒng)課程設(shè)計

1、<p>　　物理與電子信息工程學(xué)院</p><p>　　《操作系統(tǒng)》課程設(shè)計報告</p><p><b>　　題目：</b></p><p>　　1、 頁面淘汰算法 </p><p>　　2、 磁盤調(diào)度算法 </p><p><b

2、>　　操作系統(tǒng)課程設(shè)計</b></p><p><b>　　設(shè)計目的：</b></p><p>　　掌握基本操作系統(tǒng)理論</p><p>　　根據(jù)操作系統(tǒng)理論算法編寫相應(yīng)的調(diào)度程序</p><p>　　使用多種算法在特定的數(shù)據(jù)下比較其優(yōu)點與缺陷</p><p>　　嘗試改進相應(yīng)數(shù)

3、據(jù)結(jié)構(gòu)，使調(diào)度更加簡易、明顯</p><p>　　鍛煉實踐能力為后繼課程奠定基礎(chǔ)</p><p><b>　　設(shè)計環(huán)境：</b></p><p>　　Windows Xp操作系統(tǒng) 或者Linux（ubuntu 12.04）</p><p>　　Microsoft Visual C++ 6.0 編譯器 或者 GUN G++

4、，Matlab數(shù)學(xué)統(tǒng)計分析軟件</p><p>　　編輯插件：VA View、Vim</p><p>　　Shell運行良好，無特殊異常</p><p>　　設(shè)計內(nèi)容（全部設(shè)計內(nèi)容）：</p><p>　　小組從進程調(diào)度算法實現(xiàn)</p><p><b>　　頁面淘汰算法實現(xiàn)</b></p&g

5、t;<p><b>　　磁盤調(diào)度算法實現(xiàn)</b></p><p>　　實際磁盤管理方式演示實現(xiàn)</p><p>　　二級文件系統(tǒng)設(shè)計實現(xiàn)</p><p>　　經(jīng)過小組參考與討論，最終絕對選定b(頁面淘汰算法實現(xiàn))、c(磁盤調(diào)度算法實現(xiàn))。</p><p><b>　　設(shè)計要求：</b>

6、</p><p>　　頁面淘汰算法實現(xiàn)設(shè)計要求：</p><p>　　設(shè)計隨機頁面序號產(chǎn)生程序，并說明隨機的性能和其性能可能對算法的影響</p><p>　　要求有一定的參數(shù)控制能力，可以用戶自己調(diào)節(jié)隨機性能</p><p>　　編寫頁面淘汰算法本身</p><p>　　結(jié)果數(shù)據(jù)的顯示或提取</p>&l

7、t;p><b>　　結(jié)果數(shù)據(jù)的分析</b></p><p>　　磁盤調(diào)度算法實現(xiàn)設(shè)計要求：</p><p>　　設(shè)計隨機磁道訪問產(chǎn)生程序，并說明隨機的性能和其性能可能對算法的影響</p><p>　　要求有一定的參數(shù)控制能力，可以用戶自己調(diào)節(jié)隨機性能</p><p>　　編寫磁盤調(diào)度算法本身</p>

8、<p>　　結(jié)果數(shù)據(jù)的顯示或提取</p><p><b>　　結(jié)果數(shù)據(jù)的分析</b></p><p><b>　　設(shè)計原理：</b></p><p><b>　　頁面淘汰算法原理：</b></p><p>　　頁面淘汰算法定義與簡介：</p><p

9、>　　在進程運行過程中，若其要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已經(jīng)無空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面淘汰算法或者頁面置換算法（Page-Replacement Algorithms）。置換算法的好壞，將直接影響到系統(tǒng)的性能。</p><p>　　一個好的頁面置換

10、算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不會再訪問的頁面換出，或把那些在較長時間內(nèi)不會再訪問的頁面調(diào)出。目前存在著許多頁面置換算法，它們都試圖更接近于理論上的目標(biāo)。</p><p>　　先進先出（FIFO）頁面置換算法</p><p>　　這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留實踐最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需把一個進程調(diào)入內(nèi)

11、存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進程實際運行的規(guī)律不相適應(yīng)，因為在進程中，有些頁面經(jīng)常被訪問，比如含有全局變量、常用函數(shù)、例程等地頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。具體實現(xiàn)流程圖如下：</p><p>　　注：在 FIFO 算法中，無論有無發(fā)生缺頁或者置換，都需要對每個在內(nèi)存中的頁面的 time值進行增加操作，以保持最先進入的那個頁面

12、的 time 值是最大的；一個新進來的頁面，其time 值設(shè)置為 0。算法也可以通過隊列結(jié)構(gòu)來實現(xiàn)，利用隊列的先進先出（FIFO）特性完成，無需設(shè)置 time 字段。</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)介紹：</b></p><p>　　算法源程序：（見附錄）。</p><p>　　、最佳置換法（OPT）背景與簡介：</p>&

13、lt;p>　　它是由 Belady 于 1966 年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。但由于人目前還無法預(yù)知一個進程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，但可以利用此算法來評價其它算法。具體流程圖如下：</p><p>　　注：distanc

14、e 用于記錄內(nèi)存物理塊集合中每個頁面距離再次被使用的頁面跨度，缺省值為INT_MAX，如果某個頁面在后續(xù)指令集合中不再出現(xiàn)，則用最大值 INT_MAX 缺省取代；如果頁面再次被使用，則兩次使用所跨的頁面數(shù)，為頁面跨度。用最大頁面跨度表示以后永不使用或未來最長時間內(nèi)不再被訪問。</p><p>　　1.3.1、數(shù)據(jù)結(jié)構(gòu)介紹：</p><p>　　1.3.2、算法源程序：（見附錄）</p

15、><p>　　1.4、最近最久未使用（LRU）頁面置換算法：</p><p>　　最近最久未使用（LRU）置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策的。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU 置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間time,，當(dāng)須淘汰一

16、個頁面時，選擇現(xiàn)有頁面中其time值最大的，即最近最久未使用的頁面予以淘汰。</p><p>　　注：在 LRU 算法中，無論是否發(fā)生缺頁或者置換，除了命中（剛剛被訪問過的頁面）頁面time 值清零之外，其它所有內(nèi)存中的頁面的 time 值都加一，以保證最近剛剛被訪問的頁面的 time 值最小，相應(yīng) time 值最大的頁面就是最近最久沒有被訪問的頁面。 </p><p>　　1.4.1、數(shù)

17、據(jù)結(jié)構(gòu)介紹：</p><p>　　1.4.2、算法源程序：（見附錄）</p><p>　　2、磁盤調(diào)度主要思想</p><p>　　設(shè)備的動態(tài)分配算法與進程調(diào)度相似，也是基于一定的分配策略的。常用的分配策略有先請求先分配、優(yōu)先級高者先分配 等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤類旋轉(zhuǎn)設(shè)備使用不當(dāng)造成的。操作系統(tǒng)中，對磁盤的訪問要求來自多方面，常常需要排隊。這

18、時，對眾多的訪問 要求按一定的次序響應(yīng)，會直接影響磁盤的工作效率，進而影響系統(tǒng)的性能。訪問磁盤的時間因子由3部分構(gòu)成，它們是查找（查找磁道）時間、等待（旋轉(zhuǎn)等待扇 區(qū)）時間和數(shù)據(jù)傳輸時間，其中查找時間是決定因素。因此，磁盤調(diào)度算法先考慮優(yōu)化查找策略，需要時再優(yōu)化旋轉(zhuǎn)等待策略。</p><p>　　平均尋道長度（L）為所有磁道所需移動距離之和除以總的所需訪問的磁道數(shù)（N），即：L=（M1+M2+……+Mi+……+

19、MN）/N 其中Mi為所需訪問的磁道號所需移動的磁道數(shù)。</p><p>　　啟動磁盤執(zhí)行輸入輸出操作時，要把移動臂移動到指定的柱面，再等待指定扇區(qū)的旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進行讀寫，完成信息傳送。因此，執(zhí)行一次輸入輸出所花的時間有：</p><p>　　A、尋找時間——磁頭在移動臂帶動下移動到指定柱面所花的時間。</p><p>　　B、延遲時間——指定

20、扇區(qū)旋轉(zhuǎn)到磁頭下所需的時間。</p><p>　　C、傳送時間——由磁頭進程讀寫完成信息傳送的時間。</p><p>　　其中傳送信息所花的時間，是在硬件設(shè)計就固定的。而尋找時間和延遲時間是與信息在磁盤上的位置有關(guān)。</p><p>　　為了減少移動臂進行移動花費的時間，每個文件的信息不是按盤面上的磁道順序存放滿一個盤面后，再放到下一個盤面上。而是按柱面存放，同一柱

21、面上的各磁道被放滿信息后，再放到下一個柱面上。所以各磁盤的編號按柱面順序（從0號柱面開始），每個柱面按磁道順序，每個磁 道又按扇區(qū)順序進行排序。</p><p>　　2.1、先來先服務(wù)（FCFS，F(xiàn)irst Come First Served）</p><p>　　這是一種最簡單的磁盤調(diào)度算法。它是根據(jù)進程請求訪問磁盤的先后次序進行調(diào)度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次地

22、得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進行優(yōu)化，致使平均尋道時間可能較長。</p><p>　　2.2、SCAN算法</p><p>　　該算法不僅考慮到欲訪問的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮的時磁頭當(dāng)前的移動方向。例如，當(dāng)磁頭正在自里向外移動時，SCAN算法所考慮的下一個訪問對象，應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣的自里向外地

23、訪問，直至再無更外的磁道需要訪問時，才將磁臂換向為自外向里移動。這時，同樣也是每次選擇這樣的進程來調(diào)度，即要訪問的磁道在當(dāng)前位置內(nèi)距離最近者，這樣，磁頭又逐步地從外向里移動，直至再無更里面的磁道要訪問，從而避免了出現(xiàn)“饑餓”現(xiàn)象。由于在這種算法種磁頭移動的規(guī)律頗似電梯的運行，因而又常稱之為電梯調(diào)度算法。</p><p>　　2.3、CSCAN算法</p><p>　　單向掃描調(diào)度算法（CS

24、CAN）是SCAN進 行了改進。掃描調(diào)度算法（SCAN）存在這樣的問題：當(dāng)磁頭剛從里向外移動過某一磁道時，恰有一進程請求訪問此磁道，這是該進程必須等待，待磁頭從里向 外，然后再從外向里掃描完所有要訪問的磁道后，才處理該進程的請求，致使該進程的請求被嚴(yán)重地推遲。為了減少這種延遲，CSCAN算法規(guī)定磁頭只做單向移 動。[1]例如，磁頭只自里向外移動，當(dāng)磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構(gòu)

25、成循環(huán)，進行掃描。</p><p>　　2.4、最短尋道時間優(yōu)先(ShortestSeekTimeFirst，SSTF)</p><p>　　該算法選擇這樣的進程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時間最短，但這種調(diào)度算法卻不能保證平均尋道時間最短。SSTF算法的平均每次磁頭移動距離，明顯低于FCFS的距離。SSTF較之FCFS有更好的尋道性能，故過去一度被廣泛采

26、用過。</p><p>　　2.5、程序流程圖：（可見附錄圖，此圖為截圖，不清晰）</p><p>　　2.5、各個算法的比較：</p><p><b>　　數(shù)據(jù)收集與統(tǒng)計分析</b></p><p>　　小組采用隨機函數(shù)生成足夠大的數(shù)據(jù)量，并且采用Matlab數(shù)學(xué)統(tǒng)計分析軟件進行繪圖與分析，探索算法之間變量與因變量的關(guān)

27、系。</p><p>　　注：Matlab源代碼附表。</p><p>　　1、磁盤調(diào)度算法分析</p><p>　　數(shù)據(jù)內(nèi)容分別存儲在“disk隊列”與“disk移動距離”純文本文件中。</p><p>　　我們以數(shù)列長度為橫坐標(biāo)(x)，移動距離為縱坐標(biāo)(y)，采取matlab作圖工具分析得下圖：</p><p>　

28、　根據(jù)上圖，可以很明顯地看出FSFC算法是平均總移動距離最長的，它的Y軸差等值為2000，而其它三個圖像為500。</p><p>　　現(xiàn)在，我們假定它們存在線性的關(guān)系。對四種算法做出線性擬合。</p><p><b>　　假設(shè)方程為：。</b></p><p>　　其中Y為總移動距離，X為隊列長度，那么其斜率就可以抽象為它線性范圍內(nèi)的平均移動

29、長度。</p><p>　　在FCFS算法中，可得斜率為165.4，置信區(qū)間為[162.3,168.5]；</p><p>　　在SCAN算法中，可得斜率為44.0，置信區(qū)間為[42.3,45.7]；</p><p>　　在CSACN算法中，可得斜率為56.9，置信區(qū)間為[55.1,58.8]；</p><p>　　在SSFT算法中，可得斜率

30、為42.2，置信區(qū)間為[40.7.43.7]。</p><p>　　從上述直觀的斜率數(shù)據(jù)可以顯然得出，SSFT算法和SCAN算法似乎是最優(yōu)的。但是從全隊列的平均等待時間來看，CSCAN算法是為了解決SCAN算法長久的等待時間而設(shè)定的，它消除了一部分頁面長期等待的障礙。FCFS算法是最古老的算法，當(dāng)然它等待時間是最少的，移動距離也是不可調(diào)和的缺陷。具體的隊列等待時間，會在附表中給出分析。</p>&l

31、t;p>　　2、頁面置換算法數(shù)據(jù)分析</p><p>　　a)小組從定內(nèi)存容量為基礎(chǔ);</p><p>　　b)以隊列長度為自變量;</p><p>　　c)以置換次數(shù)為因變量。</p><p>　　2.1、當(dāng)隊列長度最大為10時：</p><p>　　FIFO 、LRU 、OPT 、擬合的一次函數(shù)為：</

32、p><p>　　=*0.7261 + 0.4504 ;</p><p>　　=*0.7242 + 0.4588;</p><p>　　=*0.6799 + 0.5793。</p><p>　　2.2、當(dāng)隊列長度最大為20時：</p><p>　　FIFO 、LRU 、OPT 、擬合的一次函數(shù)為：</p>&l

33、t;p>　　=*0.8593+0.1831;</p><p>　　=*0.8578+0.1910</p><p>　　=*0.7652+0.5825</p><p>　　2.2、當(dāng)隊列長度的最大值為50時</p><p>　　FIFO 、LRU 、OPT 、擬合的一次函數(shù)為：</p><p>　　=*0.9406

34、 + 0.1381 </p><p>　　=*0.9398 + 0.1595 </p><p>　　=*0.8655 + 0.5429</p><p>　　以下還有100、500分析，便不再給出上圖，在下表中給出系數(shù)：</p><p><b>　　2.4、綜合分析</b></p><p>

35、;　　數(shù)據(jù)總結(jié)：在頁面存在隨機調(diào)度的情況下，從縱向可以看出當(dāng)隊列越長時，置換的次數(shù)就越多，這是合乎常理的；從橫向角度可以得出OPT算法是理論上最優(yōu)的，而FIFO算法在數(shù)據(jù)規(guī)模不大的情況下略高于LRU算法，一旦隊列數(shù)量足夠大就越接近LRU算法。</p><p><b>　　設(shè)計總結(jié)：</b></p><p>　　從上個學(xué)期的操作系統(tǒng)理論課到現(xiàn)在的課程設(shè)計，是一個從理論到

36、實踐的過程，是我們消化理論運用到實際的過程。從周一到周二我們用C++通過面向?qū)ο蟮男问酵瓿闪瞬僮飨到y(tǒng)的頁面淘汰算法和磁盤調(diào)度算法的模擬運行。周三小組通過軟件進行了較為完善的數(shù)據(jù)分析，并生成了圖表，清晰明了地闡述了各種算法的優(yōu)缺點。周四小組搜集很多資料做了較為完善的課程設(shè)計報告。通過這一周的實踐，小組密切配合，培養(yǎng)了團隊合作精神，培養(yǎng)了我們的實際動手能力和理論聯(lián)系實踐的能力，認真細致的完成了此次課程設(shè)計，收獲很大。</p>

37、<p><b>　　附表：</b></p><p>　　DISK.cpp 磁盤調(diào)度算法源文件：</p><p>　　#include <cstdio></p><p>　　#include <cstdlib></p><p>　　#include <queue></p&

38、gt;<p>　　#include <algorithm></p><p>　　#include <ctime></p><p>　　#include <cstring></p><p>　　#include <vector></p><p>　　#include <iost

39、ream></p><p>　　#include <fstream></p><p>　　using namespace std;</p><p>　　/************************************************************************/</p><p>　　/*

40、 Author : Zuo Lingxuan , Chen Yuxi; Adress : Wenzhou Universiy */</p><p>　　/************************************************************************/</p><p>　　/***************************

41、*********************************************/</p><p>　　/* Date : 2012-9-11 ; Design of OS ,FCFS,SCAN,SSCAN,SRT */</p><p>　　/*****************************************************

42、*******************/</p><p>　　//注：SCAN和SSCAN算法默認為向上循環(huán)移動</p><p>　　ofstream out1("disk隊列.txt"),out2("disk移動距離.txt");</p><p>　　#define MAXLEN 20</p><p>

43、;　　#define MAXDISK 500</p><p>　　class DISK{</p><p><b>　　public :</b></p><p>　　vector<int> que; //磁道隊列向量</p><p>　　int start,npos,n; //磁道起點，磁道當(dāng)前位置</p

44、><p>　　int dist; //磁針移動距離</p><p><b>　　DISK(){</b></p><p>　　que.clear();</p><p><b>　　n=0;</b></p><p><b>　　}</b></p>

45、<p>　　void getinfo(){</p><p>　　cout<<"起始磁道為: "<<start<<endl;</p><p>　　cout<<"磁道隊列為: "<<endl;</p><p>　　for(vector<int>::i

46、terator it=que.begin();it!=que.end();it++){</p><p>　　cout<<*it<<" ";</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}&

47、lt;/b></p><p>　　void FCFSrunning(){</p><p>　　cout<<"***************FCFS算法:******************************************************"<<endl;</p><p><b>　　d

48、ist=0;</b></p><p>　　npos=start;</p><p>　　getinfo();</p><p>　　vector<int>::iterator it=que.begin();</p><p>　　cout<<"磁盤調(diào)度的路徑為:"<<endl;&l

49、t;/p><p>　　cout<<npos<<"-->";</p><p>　　while (it!=que.end())</p><p><b>　　{</b></p><p>　　dist+=abs(npos-*it);</p><p><b

50、>　　npos=*it;</b></p><p>　　cout<<npos<<"-->";</p><p><b>　　it++;</b></p><p><b>　　}</b></p><p>　　cout<<&quo

51、t;結(jié)束!"<<endl;</p><p>　　cout<<"移動距離為: "<<dist<<" 平均尋道長度："<<double(dist/n)<<endl;</p><p>　　out2<<dist<<" "<<

52、;double(dist*1.0/n)<<endl;</p><p><b>　　}</b></p><p>　　void CSCANrunning(){</p><p>　　cout<<"***************CSCAN算法:**************************************

53、*****************"<<endl;</p><p><b>　　dist=0;</b></p><p>　　npos=start;</p><p>　　getinfo();</p><p>　　vector<int>::iterator it,cit;</p>

54、<p>　　vector<int> cque(que),way;</p><p>　　cout<<"磁盤調(diào)度的路徑為:"<<endl;</p><p>　　cout<<npos<<"-->";</p><p>　　sort(cque.begin(

55、),cque.end());</p><p>　　for(cit=cque.begin();cit!=cque.end() && *cit<start;cit++)</p><p>　　way.push_back(*cit);</p><p><b>　　it=cit;</b></p><p>　　

56、while (it!=cque.end())</p><p><b>　　{</b></p><p>　　dist+=abs(npos-*it);</p><p><b>　　npos=*it;</b></p><p>　　cout<<npos<<"-->&q

57、uot;;</p><p><b>　　it++;</b></p><p><b>　　}</b></p><p>　　it=way.begin();</p><p>　　while (it!=way.end())</p><p><b>　　{</b>

58、</p><p>　　dist+=abs(npos-*it);</p><p><b>　　npos=*it;</b></p><p>　　cout<<npos<<"-->";</p><p><b>　　it++;</b></p>&

59、lt;p><b>　　}</b></p><p>　　cout<<"結(jié)束!"<<endl;</p><p>　　cout<<"移動距離為: "<<dist<<" 平均尋道長度："<<double(dist*1.0/n)<<

60、;endl;</p><p>　　cout<<"*******************************************************************************"<<endl;</p><p>　　out2<<dist<<" "<<double(

61、dist*1.0/n)<<endl;</p><p><b>　　}</b></p><p>　　void SCANrunning(){</p><p>　　cout<<"***************SCAN算法:************************************************

62、*******"<<endl;</p><p><b>　　dist=0;</b></p><p>　　npos=start;</p><p>　　getinfo();</p><p>　　vector<int>::iterator it,cit;</p><p>

63、;　　vector<int> cque(que),way;</p><p>　　cout<<"磁盤調(diào)度的路徑為:"<<endl;</p><p>　　cout<<npos<<"-->";</p><p>　　sort(cque.begin(),cque.end

64、());</p><p>　　for(cit=cque.begin();cit!=cque.end() && *cit<start;cit++)</p><p>　　way.push_back(*cit);</p><p><b>　　it=cit;</b></p><p>　　while (it!

65、=cque.end())</p><p><b>　　{</b></p><p>　　dist+=abs(npos-*it);</p><p><b>　　npos=*it;</b></p><p>　　cout<<npos<<"-->";</

66、p><p><b>　　it++;</b></p><p><b>　　}</b></p><p>　　vector<int>::reverse_iterator it2=way.rbegin();</p><p>　　while (it2!=way.rend())</p>&

67、lt;p><b>　　{</b></p><p>　　dist+=abs(npos-*it2);</p><p>　　npos=*it2;</p><p>　　cout<<npos<<"-->";</p><p><b>　　it2++;</b>

68、;</p><p><b>　　}</b></p><p>　　cout<<"結(jié)束!"<<endl;</p><p>　　cout<<"移動距離為: "<<dist<<" 平均尋道長度："<<double(dist

69、*1.0/n)<<endl;</p><p>　　cout<<"*******************************************************************************"<<endl;</p><p>　　out2<<dist<<" "&

70、lt;<double(dist*1.0/n)<<endl;</p><p><b>　　}</b></p><p>　　bool operator() (int i,int j) { return (i>j);} //內(nèi)部比較函數(shù)</p><p>　　void SSTFrunning(){</p><

71、p>　　cout<<"***************SSFT算法:********************************************************"<<endl;</p><p><b>　　dist=0;</b></p><p>　　npos=start;</p><

72、;p>　　getinfo();</p><p>　　vector<int>::iterator it,cit;</p><p>　　vector<int> cque(que),way;</p><p>　　cout<<"磁盤調(diào)度的路徑為:"<<endl;</p><p&g

73、t;　　cout<<npos<<"-->";</p><p>　　way.clear();</p><p>　　sort(cque.begin(),cque.end());</p><p>　　for(it=cque.begin();it<cque.end() && *it<start;i

74、t++) </p><p>　　//找出當(dāng)前磁道所處范圍</p><p>　　way.push_back(*it);</p><p>　　sort(way.begin(),way.end(),*this);</p><p>　　cit=way.begin();</p><p>　　while(it<cque.en

75、d() || cit<way.end()){</p><p>　　int max=-1;</p><p>　　if(it<cque.end() && (max<0 || max>abs(*it-npos))){</p><p>　　max=abs(*it - npos);</p><p><b&g

76、t;　　}</b></p><p>　　if(cit<way.end() && (max<0 || max>abs(*cit-npos))){</p><p>　　max=abs(*cit-npos);</p><p><b>　　}</b></p><p>　　if(max

77、==abs(*it - npos)){</p><p>　　cout<<*it<<"-->";</p><p><b>　　npos=*it;</b></p><p>　　dist+=max;</p><p><b>　　it++;</b></

78、p><p><b>　　}</b></p><p>　　else if(max==abs(*cit - npos)){</p><p>　　cout<<*cit<<"-->";</p><p>　　npos=*cit;</p><p>　　dist+=

79、max;</p><p><b>　　cit++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<"結(jié)束!"<<endl;</p><p&g

80、t;　　cout<<"移動距離為: "<<dist<<" 平均尋道長度："<<double(dist*1.0/n)<<endl;</p><p>　　cout<<"*****************************************************************

81、**************"<<endl;</p><p>　　out2<<dist<<" "<<double(dist*1.0/n)<<endl;</p><p><b>　　}</b></p><p><b>　　};</b>&

82、lt;/p><p>　　DISK disk;</p><p>　　void init(int p){ //隨機生成隊列函數(shù)</p><p>　　//重新開辟地址空間</p><p>　　DISK *tdisk=new DISK();</p><p>　　disk=*tdisk;</p><p>&l

83、t;b>　　if(!p){</b></p><p>　　disk.n=(rand()%MAXLEN)+1;</p><p>　　disk.start=rand()%MAXDISK;</p><p>　　out1<<disk.n<<" "<<disk.start<<endl;<

84、/p><p><b>　　}</b></p><p><b>　　else{</b></p><p>　　cout<<"請輸入移動磁道隊列長度、起始磁道:>>> ";</p><p>　　cin>>disk.n>>disk.sta

85、rt;</p><p>　　cout<<"請輸入磁道列隊:>>> ";</p><p><b>　　}</b></p><p>　　for(int i=0;i<disk.n;i++){</p><p><b>　　int tpos;</b>&

86、lt;/p><p><b>　　if(!p){</b></p><p>　　tpos=rand()%MAXDISK;</p><p>　　out1<<tpos<<" ";</p><p><b>　　}</b></p><p><

87、b>　　else</b></p><p>　　cin>>tpos;</p><p>　　disk.que.push_back(tpos);</p><p><b>　　}</b></p><p>　　out1<<endl;</p><p><b>

88、;　　}</b></p><p>　　int main(){</p><p>　　srand((unsigned)time(NULL));</p><p>　　//int choice=0,n=500; </p><p>　　int choice;</p><p>　　cout<<"

89、手動輸入請輸入1、自動生成請輸入0>>>> ";</p><p>　　//while(n--){</p><p>　　while(~scanf("%d",&choice)){</p><p>　　init(choice);</p><p><b>　　//分別調(diào)用算法

90、</b></p><p>　　disk.FCFSrunning(); </p><p>　　disk.SCANrunning();</p><p>　　disk.CSCANrunning();</p><p>　　disk.SSTFrunning();</p><p>　　cout<<"

91、;手動輸入請輸入1、自動生成請輸入0>>>> ";</p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　DISK.m 數(shù)據(jù)分析 matla

92、b程序源文件：</p><p>　　que=importdata('que.txt'); </p><p>　　dist=importdata('dist.txt');</p><p><b>　　quet=[];</b></p><p>　　num=size(que);</p>

93、;<p>　　for i=1:num(1)</p><p>　　quet=[quet que(i,:)]; </p><p><b>　　end</b></p><p>　　que=quet(~isnan(quet)); </p><p><b>　　t=1;</b></p>

94、;<p><b>　　n=[];</b></p><p>　　num=size(que);</p><p>　　while t<=num(2) </p><p>　　n=[n que(t)];</p><p>　　t=que(t)+t+2;</p><p><b>

95、;　　end</b></p><p><b>　　fsfc=[];</b></p><p><b>　　scan=[];</b></p><p><b>　　sscan=[];</b></p><p><b>　　sstf=[];</b><

96、;/p><p>　　for i=1:4:2000</p><p>　　fsfc=[fsfc dist(i,1)];</p><p>　　scan=[scan dist(i+1,1)];</p><p>　　sscan=[sscan dist(i+2,1)];</p><p>　　sstf=[sstf dist(i+3,1)

97、];</p><p><b>　　end</b></p><p>　　figure(1);</p><p>　　subplot(2,2,1),plot(n,fsfc,'*r'),title('FCFS');</p><p>　　subplot(2,2,2),plot(n,scan,'

98、;*g'),title('SCAN');</p><p>　　subplot(2,2,3),plot(n,sscan,'*b'),title('CSCAN');</p><p>　　subplot(2,2,4),plot(n,sstf,'*g'),title('SSTF');</p>&l

99、t;p>　　%plot(n',fsfc',n',scan',n',sscan',n',sstf');</p><p>　　%axis auto equal </p><p>　　[a1,b1]=regress(fsfc',n')</p><p>　　[a2,b2]=regress(

100、scan',n')</p><p>　　[a3,b3]=regress(sscan',n')</p><p>　　[a4,b4]=regress(sstf',n')</p><p>　　頁面淘汰算法源文件 PGA.cpp</p><p>　　#include <iostream>&l

101、t;/p><p>　　#include <cstdio></p><p>　　#include <cmath></p><p>　　#include <cstdio></p><p>　　#include <cstdlib></p><p>　　#include <se

102、t></p><p>　　#include <algorithm></p><p>　　#include <queue></p><p>　　#include <ctime></p><p>　　#include <fstream></p><p>　　using

103、namespace std;</p><p>　　/************************************************************************/</p><p>　　/* Author: Zuo Lingxuan ,Chen Yuxi ; Adress : Wenzhou University */</p>

104、<p>　　/************************************************************************/</p><p>　　/************************************************************************/</p><p>　　/* Data:2012-9

105、-11 Design of Os ,FIFO,LRU,OPT */</p><p>　　/************************************************************************/</p><p>　　ofstream out1("pga1.txt"),out2(

106、"pga2.txt");</p><p>　　#define MAXPAGE 10 //頁面ID</p><p>　　#define MAXNUM 500 //最長頁面隊列</p><p>　　int MAXSWITCH; //最大內(nèi)存可保存集合</p><p>　　class PAGEFIFO{</p>

107、<p><b>　　public:</b></p><p>　　queue<int> pgfram; //頁面隊列</p><p>　　vector<int> ddr; //內(nèi)存集合</p><p>　　int lscount; //頁面缺失次數(shù)</p><p>　　int swco

108、unt; //頁面置換次數(shù)</p><p>　　int pgnum;</p><p>　　PAGEFIFO(){</p><p>　　while(!pgfram.empty()){</p><p>　　pgfram.pop();</p><p><b>　　}</b></p>&l

109、t;p><b>　　//清除所有頁面</b></p><p>　　ddr.clear();</p><p>　　//清除在內(nèi)存中的頁面</p><p>　　lscount=0;</p><p>　　swcount=0;</p><p><b>　　};</b></

110、p><p>　　bool isin(int tmppage){ //判斷是否在內(nèi)存中的函數(shù)</p><p>　　for(vector<int>::iterator it=ddr.begin();it!=ddr.end();it++){</p><p>　　if(tmppage==*it)</p><p>　　return true;&

111、lt;/p><p><b>　　}</b></p><p>　　return false; </p><p><b>　　}</b></p><p>　　void infile(){</p><p>　　out1<<pgnum<<endl;</p&g

112、t;<p>　　out2<<lscount<<endl;</p><p><b>　　}</b></p><p>　　void running(){ //運行函數(shù)本身</p><p>　　lscount=swcount=0;</p><p>　　while(!pgfram.empty

113、()){</p><p>　　int tmppage=pgfram.front();</p><p>　　pgfram.pop();</p><p>　　if(!isin(tmppage))</p><p><b>　　{</b></p><p>　　cout<<"當(dāng)前內(nèi)存頁

114、面"<<endl;</p><p>　　if(!ddr.size())</p><p>　　cout<<"尚無頁面";</p><p>　　for(vector<int>::iterator it=ddr.begin();it!=ddr.end();it++) //輸出當(dāng)前內(nèi)存的頁面ID</p&

115、gt;<p>　　cout<<*it<<" ";</p><p>　　cout<<endl;</p><p>　　lscount++;</p><p>　　if(ddr.size()>=MAXSWITCH){ //如果</p><p>　　swcount++;<

116、/p><p>　　ddr.erase(ddr.begin());</p><p><b>　　}</b></p><p>　　ddr.push_back(tmppage);</p><p><b>　　}</b></p><p><b>　　}</b><

117、;/p><p>　　cout<<"置換頁面次數(shù): "<<swcount<<endl;</p><p>　　cout<<"缺失頁面次數(shù): "<<lscount<<endl;</p><p><b>　　infile();</b></p

118、><p><b>　　}</b></p><p><b>　　};</b></p><p>　　class PAGELRU{</p><p><b>　　public :</b></p><p>　　vector<int> pgfram; //頁

119、面隊列</p><p>　　vector< pair<int,int> > ddr; //內(nèi)存集合</p><p>　　int lscount; //頁面缺失次數(shù)</p><p>　　int swcount; //頁面置換次數(shù)</p><p>　　int pgnum;</p><p>　　

120、PAGELRU(){</p><p>　　pgfram.clear();</p><p><b>　　//清除所有頁面</b></p><p>　　ddr.clear();</p><p>　　//清除在內(nèi)存中的頁面</p><p>　　lscount=0;</p><p>

121、;　　swcount=0;</p><p><b>　　};</b></p><p>　　bool isin(int tmppage){ //判斷是否在內(nèi)存中的函數(shù)</p><p>　　for(vector< pair<int,int> >::iterator it=ddr.begin();it!=ddr.end();i

122、t++){</p><p>　　if(tmppage==it->second){</p><p>　　it->first=0;</p><p>　　return true;</p><p><b>　　}</b></p><p><b>　　}</b></p

123、><p>　　return false; </p><p><b>　　}</b></p><p>　　void getddrinfo(){</p><p>　　cout<<"內(nèi)存中的頁面:"<<endl;</p><p>　　if(!ddr.size())

124、</p><p>　　cout<<"尚無頁面";</p><p>　　for(vector< pair<int,int> >::iterator it=ddr.begin();it!=ddr.end();it++)</p><p>　　cout<<it->second<<"

125、; ";</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　void addtime(){ //內(nèi)存中的每一個進程ID時間增加</p><p>　　for(vector< pair<int,int> >::iterator

126、 it=ddr.begin();it!=ddr.end();it++)</p><p>　　it->first++;</p><p><b>　　}</b></p><p>　　void infile(){</p><p>　　out1<<pgnum<<endl;</p>&l

127、t;p>　　out2<<lscount<<endl;</p><p><b>　　}</b></p><p>　　void running(){</p><p>　　lscount=swcount=0;</p><p>　　vector<int>::iterator it=pgf

128、ram.begin();</p><p>　　while(it!=pgfram.end()){</p><p>　　if(!isin(*it)){ //檢查不在內(nèi)存時</p><p>　　pair<int,int> tmp;</p><p>　　tmp.second=*it;</p><p>　　tmp.

129、first=0;</p><p>　　//getddrinfo();</p><p>　　if(ddr.size()>=MAXSWITCH){ //內(nèi)存已滿</p><p>　　sort(ddr.begin(),ddr.end());</p><p>　　ddr.pop_back();</p><p>　　s

130、wcount++;</p><p><b>　　}</b></p><p>　　ddr.push_back(tmp);</p><p>　　lscount++;</p><p>　　getddrinfo();</p><p><b>　　}</b></p>

131、<p>　　addtime();</p><p><b>　　it++;</b></p><p><b>　　}</b></p><p>　　cout<<"置換頁面次數(shù): "<<swcount<<endl;</p><p>　　co

132、ut<<"缺失頁面次數(shù): "<<lscount<<endl;</p><p><b>　　infile();</b></p><p><b>　　}</b></p><p><b>　　};</b></p><p>　　c

133、lass PAGEOPT{</p><p><b>　　public:</b></p><p>　　vector<int> pgfram; //頁面隊列</p><p>　　vector< pair<int,int> > ddr; //內(nèi)存集合</p><p>　　int lscou

134、nt; //頁面缺失次數(shù)</p><p>　　int swcount; //頁面置換次數(shù)</p><p>　　int pgnum; //頁面隊列長度</p><p>　　PAGEOPT(){</p><p>　　pgfram.clear();</p><p><b>　　//清除所有頁面</b>

135、;</p><p>　　ddr.clear();</p><p>　　//清除在內(nèi)存中的頁面</p><p>　　lscount=0;</p><p>　　swcount=0;</p><p><b>　　};</b></p><p>　　bool isin(int tmp

136、page){ //判斷是否在內(nèi)存中的函數(shù)</p><p>　　for(vector< pair<int,int> >::iterator it=ddr.begin();it!=ddr.end();it++){</p><p>　　if(tmppage==it->second)</p><p>　　return true;</p&g

137、t;<p><b>　　}</b></p><p>　　return false; </p><p><b>　　}</b></p><p>　　int gettime(vector<int>::iterator it){ //找出當(dāng)前放入內(nèi)存的頁面距離下一次出現(xiàn)的時間</p>&l

138、t;p><b>　　int n=0;</b></p><p>　　int m=*it;</p><p><b>　　it++;</b></p><p>　　while(it!=pgfram.end()){</p><p>　　if(m==*it)</p><p><

139、;b>　　break;</b></p><p><b>　　n++;</b></p><p><b>　　it++;</b></p><p><b>　　}</b></p><p>　　return n?n:INT_MAX; //如果再也沒有出現(xiàn)，返回?zé)o窮大值