南通大學計算機科學與技術(shù)學院操作系統(tǒng)課程設(shè)計報告書班級_計091_姓名_莊林祥_指導教師戴樹貴目錄設(shè)計要求3設(shè)計實現(xiàn)3主界面3A作業(yè)調(diào)度的三個算法3B銀行家算法4C頁面調(diào)度算法5D驅(qū)動調(diào)度算法6實現(xiàn)原理8A作業(yè)調(diào)度的三個算法8一、任務8二、要求8三、原理8四、數(shù)據(jù)結(jié)構(gòu)8五、實現(xiàn)方法11六、運行結(jié)果16B銀行家算法16一、任務16二、要求16三、原理16四、數(shù)據(jù)結(jié)構(gòu)17五、實現(xiàn)方法18六、運行結(jié)果19C頁面調(diào)度算法22一、任務22二、要求22三、原理22四、數(shù)據(jù)結(jié)構(gòu)22五、實現(xiàn)方法25六、運行結(jié)果28D驅(qū)動調(diào)度算法31一、任務31二、要求31三、原理31四、數(shù)據(jù)結(jié)構(gòu)32五、實現(xiàn)方法33六、運行結(jié)果34心得35設(shè)計要求將本學期的四次實驗集成實現(xiàn)A實驗一為作業(yè)調(diào)度的三個算法B實驗二為銀行家算法C實驗三為頁面替換的三個算法D實驗三為驅(qū)動調(diào)度的三個算法設(shè)計實現(xiàn)主功能界面，如圖1圖1A作業(yè)調(diào)度的三個算法點擊作業(yè)調(diào)度算法，如圖11圖11點擊預定義，如圖111圖111點擊自定義，如圖112圖112B銀行家算法點擊銀行家算法，如圖21圖21點擊預定義，如圖211圖211點擊自定義，如圖212圖212C實驗三為頁面替換的三個算法點擊頁面替換算法，如圖31圖31點擊預定義，如圖311圖311點擊自定義，如圖312圖312D實驗三為驅(qū)動調(diào)度的三個算法點擊驅(qū)動調(diào)度算法，如圖41圖41點擊預定義，如圖411圖411點擊自定義，如圖412圖412實現(xiàn)原理A作業(yè)調(diào)度的三個算法一、任務實現(xiàn)作業(yè)調(diào)度的三個算法A先來先服務算法（FCFS）。B最短作業(yè)優(yōu)先算法（SJF）。C響應比最高優(yōu)先者優(yōu)先算法（HRRF）。二、要求1實現(xiàn)對三種算法的模擬實現(xiàn)。2分別計算出三種算法的平均作業(yè)周轉(zhuǎn)時間、平均帶權(quán)作業(yè)周轉(zhuǎn)時間。三、原理A先來先服務算法（FCFS）按作業(yè)到達CPU時間先后順序進行非剝奪式調(diào)度，先到達CPU的作業(yè)先被執(zhí)行。B最短作業(yè)優(yōu)先算法（SJF）忽視作業(yè)的等待時間，按作業(yè)所需要的CPU運行時間長短進行非剝奪式調(diào)度，CPU運行時間短的作業(yè)先被執(zhí)行。C響應比最高優(yōu)先者優(yōu)先算法（HRRF）介乎FCFS算法和SJF算法之間的折中的非剝奪式算法，既考慮作業(yè)的等待時間，又作業(yè)的處理時間。按如下計算方法得出每輪各作業(yè)響應比響應比作業(yè)周轉(zhuǎn)時間/作業(yè)處理時間1作業(yè)等待時間/作業(yè)處理時間從中選出響應比最大的作業(yè)執(zhí)行，再進行下一輪剩下未被執(zhí)行的作業(yè)響應比計算，直到剩余最后一個作業(yè)完止。四、數(shù)據(jù)結(jié)構(gòu)CLASSJOBPUBLICCHARJOBNAME/JOBNAME/作業(yè)名INTID/ORDERTOEXECUTE/執(zhí)行序號FLOATARRIVETIME/到達CPU時間FLOATCPUTIME/作業(yè)處理時間FLOATRESPONSERATIO/響應比（執(zhí)行HRRF算法時起作用）JOBNEXT/指向下一個創(chuàng)建的作業(yè)（不代表到達/CPU時間）JOBORDERNEXT/指向下一個最近的到達CPU的作業(yè)JOB/對象創(chuàng)建時作業(yè)初始化，全部置0或置空JOBNAMENULLID0ARRIVETIME0CPUTIME0RESPONSERATIO0NEXTNULLORDERNEXTNULL結(jié)構(gòu)圖原始鏈表（NEXT指針按創(chuàng)建先后順序排列）五、實現(xiàn)方法將進程中的作業(yè)按到達CPU時間從小到大排列，重新鏈接作業(yè)。新鏈表（ORDERNEXT指針按到達CPU時間從小到大排列）以下用到的作業(yè)順序皆指新鏈表中的作業(yè)順序A先來先服務算法（FCFS）新鏈表中作業(yè)已經(jīng)按作業(yè)按到達CPU時間從小到大排列，只需從第一個作業(yè)（頭結(jié)點）依次調(diào)度至最后一個作業(yè)（尾結(jié)點）。過程示意圖IDJOBNAMEARRIVETIMECPUTIMERESPONSERATIONEXT指針ORDERNEXT指針NULLNULL作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)NULL執(zhí)行第一個作業(yè)執(zhí)行到了最后一個作業(yè)B最短作業(yè)優(yōu)先算法（SJF）S1執(zhí)行一輪查找，篩選出小于已執(zhí)行作業(yè)累加總CPU時間（第一個作業(yè)之前累加CPU時間認為是0）的作業(yè)列。S2從S1中篩選出的作業(yè)列中選出CPU時間（CPUTIME）最小的作業(yè)送去CPU執(zhí)行，完畢后將此作業(yè)累加到總CPU時間。S3重復上述步驟，直至作業(yè)全部執(zhí)行完畢。過程示意圖第一輪查找，只有第一個作業(yè)符合，取出執(zhí)行第二輪查找，篩選出小于已執(zhí)行作業(yè)累加總CPU時間，找出CPU時間最小的作業(yè)，取出執(zhí)行第N輪查找，篩選出小于已執(zhí)行作業(yè)累加總CPU時間，找出CPU時間最小的作業(yè)，取出執(zhí)行最后一輪查找，篩選出小于已執(zhí)行作業(yè)累加總CPU時間，找出CPU時間最小的作業(yè)，取出執(zhí)行C響應比最高優(yōu)先者優(yōu)先算法（HRRF）S1執(zhí)行第一個作業(yè)，完畢后計算剩下的各作業(yè)響應比。S2執(zhí)行S1中響應比最大的作業(yè)，完畢后計算剩下的各作業(yè)響應比。S3重復上述步驟，直至剩余一個作業(yè)。S4執(zhí)行最后一個作業(yè)。作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)NULL作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)NULL作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)NULL作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)NULL作業(yè)過程示意圖先執(zhí)行第一個作業(yè)，完畢后計算剩下的各作業(yè)響應執(zhí)行響應比最大的作業(yè)，完畢后計算剩下的各作業(yè)響應比執(zhí)行響應比最大的作業(yè)，完畢后計算剩下的各作業(yè)響應比重復步驟，執(zhí)行作業(yè)，計算響應比執(zhí)行剩的下最后一個作業(yè)六、運行結(jié)果1第一組測試數(shù)據(jù)，如圖11圖11執(zhí)行FCFS算法，如圖12圖12作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)NULL作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)NULL作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)作業(yè)NULL執(zhí)行SJF算法，如圖13圖13篩選出符合條件的作業(yè)，執(zhí)行CPU時間最小的作業(yè)，如圖14圖14執(zhí)行HRRF算法，如圖15圖15執(zhí)行預選作業(yè)，計算剩余作業(yè)響應比，如圖16圖162第二組測試數(shù)據(jù)，如圖21圖21執(zhí)行FCFS算法，如圖22圖22執(zhí)行SJF算法，如圖23圖23篩選出符合條件的作業(yè)，執(zhí)行CPU時間最小的作業(yè)，如圖24，圖25圖24圖25執(zhí)行HRRF算法，如圖26圖26執(zhí)行預選作業(yè)，計算剩余作業(yè)響應比，如圖27，圖28圖27圖28B銀行家算法一、任務編程實現(xiàn)實現(xiàn)銀行家算法二、要求實現(xiàn)銀行家算法模擬實現(xiàn)。三、原理銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統(tǒng)進入不安全狀態(tài)，則分配，否則等待。為實現(xiàn)銀行家算法，系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全序列是指一個進程序列P1，PN是安全的，如果對于每一個進程PI1IN），它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程PJJI當前占有資源量之和。安全狀態(tài)如果存在一個由系統(tǒng)中所有進程構(gòu)成的安全序列P1，PN，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。不安全狀態(tài)不存在一個安全序列。不安全狀態(tài)不一定導致死鎖。我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。為保證資金的安全，銀行家規(guī)定1當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客；2顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量；3當銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款；4當顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程本次申請的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當前的申請量分配資源，否則也要推遲分配。四、數(shù)據(jù)結(jié)構(gòu)1在程序中使用的資源基本結(jié)構(gòu)及基本方法SOURCE結(jié)構(gòu)圖2每個進程的構(gòu)成PROCESS結(jié)構(gòu)圖3程序中使用到的所有數(shù)據(jù)集合DATA結(jié)構(gòu)圖SOURCEALLOCATIONSOURCECLAIMSOURCECLAIM_ALLOCATIONSOURCECURRENTAVAILINTR2INTR1INTR3VOIDSETSOURCEVOIDADDVOIDSUBBOOLLOWERSOURCESUMPROCESSPSOURCEAVAILABLESOURCEASKINTPLENGTHINTRULERVOIDCLEARPROCESS4初始化或設(shè)置數(shù)據(jù)方法集合DATAINIT結(jié)構(gòu)圖5顯示方法集合DISPLAY結(jié)構(gòu)圖6FINDSAFELIST結(jié)構(gòu)圖五、實現(xiàn)方法在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前，判斷系統(tǒng)是否是安全的；若是，才分配。它是最具有代表性的避免死鎖的算法。設(shè)進程PI提出請求ASKR1,R2,R3，則銀行家算法按如下規(guī)則進行判斷。1如果PI的ASKR1,R2,R3PICLAIMR1,R2,R3ALLOCATIONR1,R2,R3，則轉(zhuǎn)（2；否則，出錯。2如果PI的ASKR1,R2,R3AVAILABLER1,R2,R3，則轉(zhuǎn)（3；否則，出錯。VOIDSETASKVOIDINITLENGTHVOIDINITSUMVOIDINITAVAILVOIDINITPROCESSVOIDDISPLAYAVAILABLEVOIDDISPLAYSOURCEVOIDDISPLAYPROCESSVOIDDISPLAYSAFELISTVOIDDISPLAYRESULTBOOLEXSITSAFELISTBOOLCHECKLISTINTFINDSAFELIST3系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)AVAILABLER1,R2,R3ASKR1,R2,R3PIALLOCATIONR1,R2,R3ASKR1,R2,R3PICLAIMR1,R2,R3ALLOCATIONR1,R2,R3ASKR1,R2,R34系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復原狀，進程等待。六、運行結(jié)果測試數(shù)據(jù)，如圖11圖11執(zhí)行進程P1請求資源ASK1,0,2，如圖12圖12查看一個安全序列詳情，如圖13圖13不查看一個安全序列，如圖14圖14執(zhí)行進程P4請求資源ASK3,3,0，如圖15圖15執(zhí)行進程P0請求資源ASK0,2,0，如圖16圖16不請求資源輸入N，退出C頁面調(diào)度算法一、任務A最優(yōu)替換算法OPTB先進先出調(diào)度算法FIFOC最近最少調(diào)度算法LRU二、要求1實現(xiàn)對頁面替換算法的模擬實現(xiàn)2計算缺頁次數(shù)和缺頁中斷率三、原理目前有許多頁面調(diào)度算法，本實驗主要涉及先進先出調(diào)度算法、最近最少調(diào)度算法、最近最不常用調(diào)度算法。本實驗使用頁面調(diào)度算法時作如下假設(shè)，進程在創(chuàng)建時由操作系統(tǒng)為之分配一個固定數(shù)目物理頁，執(zhí)行過程中物理頁的數(shù)目和位置不會改變。也即進程進行頁面調(diào)度時只能在分到的幾個物理頁中進行。下面對各調(diào)度算法的思想作一介紹。A最優(yōu)替換算法OPT選擇將來最久不被訪問的頁面作為被替換的頁面它就是一種比較好的頁面替換算法。B先進先出調(diào)度算法FIFO先進先出調(diào)度算法根據(jù)頁面進入內(nèi)存的時間先后選擇淘汰頁面，先進入內(nèi)存的頁面先淘汰，后進入內(nèi)存的后淘汰。本算法實現(xiàn)時需要將頁面按進入內(nèi)存的時間先后組成一個隊列，每次調(diào)度隊首頁面予以淘汰。C最近最少調(diào)度算法LRU先進先出調(diào)度算法沒有考慮頁面的使用情況，大多數(shù)情況下性能不佳。根據(jù)程序執(zhí)行的局部性特點，程序一旦訪問了某些代碼和數(shù)據(jù)，則在一段時間內(nèi)會經(jīng)常訪問他們，因此最近最少用調(diào)度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。算法實現(xiàn)時需要為每個頁面設(shè)置數(shù)據(jù)結(jié)構(gòu)記錄頁面自上次訪問以來所經(jīng)歷的時間。缺頁調(diào)度次數(shù)和缺頁中斷率計算缺頁中斷次數(shù)是缺頁時發(fā)出缺頁中斷的次數(shù)缺頁中斷率缺頁中斷次數(shù)/總的頁面引用次數(shù)100四、數(shù)據(jù)結(jié)構(gòu)1頁框結(jié)構(gòu)PAGEFRAME結(jié)構(gòu)圖2頁結(jié)構(gòu)PROCESS結(jié)構(gòu)圖3程序中使用到的所有數(shù)據(jù)集合DATA結(jié)構(gòu)圖4初始化或設(shè)置數(shù)據(jù)方法集合SETBASEINFO結(jié)構(gòu)圖INTIDINTPAGEIDINTIDINTVISITEDCOUNTINTUNVISITEDCOUNTBOOLREPLACEINTSTAYTIMEINTNEXTSITEINTPFLENGTHPAGEFRAMEPFPAGEPINTPLENGTHINTPLENGTHINTPFLOGICRULERINTPAGELACKCOUNTVOIDSETPAGEVOIDSETPAGEFRAME5METHOD結(jié)構(gòu)圖OPT,FIFO,LRU結(jié)構(gòu)如下列圖6OPT，F(xiàn)IFO，LRU結(jié)構(gòu)圖7CONTROL結(jié)構(gòu)圖8顯示方法集合DISPLAY結(jié)構(gòu)圖VOIDDISPLAYLOGICRULERVOIDDISPLAYPAGELISTVOIDDISPLAYPAGELACKVOIDDISPLAYPAGEFRAMETVOIDDISPLAYRESULTINTREPLACEBOOLFINDPAGEINTLONGESTTIMEINTMOSTUNVISITEDVOIDSETPFLOGICRULERINTGETDIEPFVOIDSETPFLOGICRULER（）/方法重寫繼承METHODFIFOFIFOOPTOPTLRULRU五、實現(xiàn)方法A最優(yōu)替換算法OPTY有頁面請求嗎結(jié)束找到了嗎執(zhí)行該頁修改該頁框內(nèi)頁面下一次在序列中位置NEXTSITE調(diào)入當前頁面請求在頁框中查找該頁選出頁框頁面下一次位置最大的頁框，淘汰，替換進當前頁面請求YN開始NB先進先出調(diào)度算法FIFOY有頁面請求嗎結(jié)束找到了嗎執(zhí)行該頁，頁框駐留時間加1調(diào)入當前頁面請求在頁框中查找該頁YN開始N選出頁框頁面駐留時間最大頁框,淘汰,替換進當前請求頁面,頁框駐留時間STAYTIME歸1執(zhí)行該頁，頁框駐留時間STAYTIME加1其他頁框駐留時間STAYTIME加1C最近最少調(diào)度算法LRUY有頁面請求嗎結(jié)束找到了嗎執(zhí)行該頁，頁框駐留時間加1調(diào)入當前頁面請求在頁框中查找該頁YN開始N其它頁框未訪問時間UNVISITEDCOUNT加1選出頁框頁面未訪問時間最大頁框,淘汰,替換進當前頁面請求，頁框未訪問時間UNVISITEDCOUNT歸1執(zhí)行該頁，頁框未訪問時間UNVISITEDCOUNT歸1六、運行結(jié)果測試數(shù)據(jù)，如圖11圖11選擇最佳頁面替換算法，如圖12圖12選擇先進先出頁面替換算法，如圖13圖13最近最少調(diào)度算法，如圖14圖14輸入0，退出D驅(qū)動調(diào)度算法一、任務實現(xiàn)驅(qū)動調(diào)度的三個算法A先入先出算法（FIFO）B電梯調(diào)度算法（ELEVATORALGORITHM）C掃描算法（SCANALGORITHM）二、要求1實現(xiàn)對三種算法的模擬實現(xiàn)。2分別計算出三種算法的經(jīng)過磁道數(shù)。三、原理磁盤驅(qū)動調(diào)度對磁盤的效率有重要影響。磁盤驅(qū)動調(diào)度算法的好壞直接影響輔助存儲器的效率，從而影響計算機系統(tǒng)的整體效率。A先入先出算法（FIFO）總是嚴格按時間順序?qū)Υ疟P請求予以處理。算法實現(xiàn)簡單、易于理解并且相對公平，不會發(fā)生進程餓死現(xiàn)象。但該算法可能會移動的柱面數(shù)較多并且會經(jīng)常更換移動方向，效率有待提高B電梯調(diào)度算法（ELEVATORALGORITHM）總是將一個方向上的請求全部處理完后，才改變方向繼續(xù)處理其他請求。C掃描算法（SCANALGORITHM）總是從最外向最里（或最里向最外）進行掃描，然后在從最里向最外（或最外向最里）掃描。該算法與電梯調(diào)度算法的區(qū)別是電梯調(diào)度在沒有最外或最里的請求時不會移動到最外或最里柱面。四、數(shù)據(jù)結(jié)構(gòu)1在程序中使用的