操作系統(tǒng)試驗(yàn)講義

本文格式為Word版，下載可任意編輯——操作系統(tǒng)試驗(yàn)講義《操作系統(tǒng)》試驗(yàn)講義

第一章試驗(yàn)?zāi)康呐c要求

1.1試驗(yàn)?zāi)康?/p>

操作系統(tǒng)課程是計(jì)算機(jī)類(lèi)相關(guān)專(zhuān)業(yè)的一門(mén)必修的專(zhuān)業(yè)基礎(chǔ)課，該課程以經(jīng)典操作系統(tǒng)基本原理和概念為框架，詳細(xì)介紹了操作系統(tǒng)對(duì)計(jì)算機(jī)系統(tǒng)軟、硬件進(jìn)行管理的理論和技術(shù)，是一門(mén)理論性較強(qiáng)的課程。

操作系統(tǒng)試驗(yàn)是幫助學(xué)生理解操作系統(tǒng)理論，模擬實(shí)現(xiàn)操作系統(tǒng)部分管理功能的重要的實(shí)踐性教學(xué)環(huán)節(jié)，是培養(yǎng)學(xué)生分析問(wèn)題和解決問(wèn)題能力的有效手段。通過(guò)試驗(yàn)，加深學(xué)生對(duì)講授的相關(guān)理論知識(shí)的理解，使學(xué)生能夠?qū)⒗碚撆c實(shí)踐相結(jié)合。

1.2試驗(yàn)要求

在上機(jī)試驗(yàn)前要求學(xué)生應(yīng)事先做好準(zhǔn)備工作，以提高上機(jī)試驗(yàn)的效率。準(zhǔn)備工作至少應(yīng)包括：

（1）熟練把握一種高級(jí)程序設(shè)計(jì)語(yǔ)言及上機(jī)調(diào)試程序的方法；（2）復(fù)習(xí)并把握與試驗(yàn)相關(guān)的教學(xué)內(nèi)容；

（3）準(zhǔn)備好上機(jī)所需的程序，手編程序應(yīng)書(shū)寫(xiě)整齊，并經(jīng)人工檢查無(wú)誤后才能上機(jī)，以提高上機(jī)效率；

（4）對(duì)運(yùn)行程序中可能出現(xiàn)的問(wèn)題應(yīng)事先做出估計(jì)，對(duì)程序中自己有疑問(wèn)的地方，應(yīng)作上記號(hào)，以便在上機(jī)時(shí)給予注意；

（5）準(zhǔn)備好調(diào)試和運(yùn)行程序的數(shù)據(jù)；

試驗(yàn)終止后寫(xiě)出試驗(yàn)報(bào)告，試驗(yàn)報(bào)告內(nèi)容包括：試驗(yàn)題目、試驗(yàn)?zāi)康?、試?yàn)內(nèi)容、試驗(yàn)要求及源程序、試驗(yàn)結(jié)果、試驗(yàn)體會(huì)。

其次章試驗(yàn)內(nèi)容

試驗(yàn)1模擬處理器調(diào)度1.處理器調(diào)度算法

處理器調(diào)度算法有7種，本試驗(yàn)要求使用先進(jìn)先出（FIFO）調(diào)度算法或最短作業(yè)優(yōu)先（SJF）調(diào)度算法模擬實(shí)現(xiàn)操作系統(tǒng)對(duì)處理器調(diào)度的方法。

FIFO調(diào)度算法是依照作業(yè)到達(dá)系統(tǒng)或進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來(lái)調(diào)度作業(yè)或進(jìn)程占有處理器，一旦一個(gè)作業(yè)或進(jìn)程占有處理器，它就一直運(yùn)行下去，直到該作業(yè)或進(jìn)程完成了其工作或因等待某事件的發(fā)生而不能繼續(xù)運(yùn)行才釋放處理器。

最短作業(yè)優(yōu)先調(diào)度算法是從磁盤(pán)輸入井或就緒隊(duì)列中挑揀所需的運(yùn)行時(shí)間最短的作業(yè)或進(jìn)程占有處理器。該算法具有不可搶占性。

例2-4設(shè)有4道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間如表2-5所示。要求在單道程序環(huán)境下，分別寫(xiě)出采用先進(jìn)先出調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時(shí)的作業(yè)調(diào)度順序。

表2-5

作業(yè)號(hào)提交時(shí)間執(zhí)行時(shí)間110.02.0

210.21.0310.40.5410.50.3

解：（1）采用先進(jìn)先出調(diào)度算法，作業(yè)的調(diào)度順序是：1、2、3、4。（2）采用最短作業(yè)優(yōu)先調(diào)度算法，作業(yè)的調(diào)度順序是：1、4、3、2。2.試驗(yàn)?zāi)康?/p>

通過(guò)本試驗(yàn)?zāi)M實(shí)現(xiàn)操作系統(tǒng)對(duì)處理器調(diào)度方法。3.試驗(yàn)內(nèi)容

使用高級(jí)程序設(shè)計(jì)語(yǔ)言，編寫(xiě)實(shí)現(xiàn)處理器調(diào)度的程序。4.試驗(yàn)要求

仿循例2-4輸入不少于5個(gè)作業(yè)的作業(yè)號(hào)、提交時(shí)間和執(zhí)行時(shí)間，依照先進(jìn)先

出調(diào)度算法或最短作業(yè)優(yōu)先調(diào)度算法編寫(xiě)程序，輸出調(diào)度作業(yè)序列。

5.試驗(yàn)學(xué)時(shí)6學(xué)時(shí)

試驗(yàn)2死鎖的避免——銀行家算法1.銀行家算法

操作系統(tǒng)在若干個(gè)并行進(jìn)程間分派數(shù)量一定的共享資源，既要使每個(gè)進(jìn)程均能滿(mǎn)足其對(duì)資源的要求，使之完成其運(yùn)行任務(wù)，同時(shí)又要使整個(gè)系統(tǒng)不會(huì)產(chǎn)生死鎖所采用的方法，即銀行家算法。銀行家算法是解決資源共享問(wèn)題的一種算法，是研究如何將有限的資源合理分派給多個(gè)進(jìn)程使用，同時(shí)系統(tǒng)又不會(huì)發(fā)生死鎖問(wèn)題的一種算法。

銀行家算法分為單資源銀行家算法和多資源銀行家算法。（1）單資源銀行家算法

假定系統(tǒng)有某種共享資源，其數(shù)量為R，現(xiàn)有三個(gè)進(jìn)程P1、P2、P3同時(shí)申請(qǐng)此資源，系統(tǒng)當(dāng)前可用資源數(shù)量為R0，三個(gè)進(jìn)程已分派此種資源的向量為A=(A1,A2,A3)，各進(jìn)程對(duì)該資源的請(qǐng)求向量為C=(C1,C2,C3)。

單資源銀行家算法是從系統(tǒng)的當(dāng)前狀態(tài)出發(fā)，逐個(gè)檢查各個(gè)進(jìn)程，誰(shuí)能完成其工作（即請(qǐng)求資源數(shù)量不超過(guò)當(dāng)前可用資源的數(shù)量），然后假定其完成了工作且歸還了全部資源，對(duì)該進(jìn)程進(jìn)行標(biāo)記，再進(jìn)而檢查剩余進(jìn)程誰(shuí)又能完成工作……假使所有進(jìn)程均能完成工作，則當(dāng)前系統(tǒng)狀態(tài)安全，可以按進(jìn)程標(biāo)記的順序（即安全序列）分派共享資源R，否則當(dāng)前系統(tǒng)處于擔(dān)憂(yōu)全狀態(tài)。

例2-1用銀行家算法判斷下述每個(gè)狀態(tài)是否安全，假使安全寫(xiě)出安全序列，假使擔(dān)憂(yōu)全說(shuō)明理由。

①狀態(tài)1

進(jìn)程已分派資源向量請(qǐng)求資源向量P124P243P351P402當(dāng)前共享資源的可分派數(shù)量為：1

解：依照單資源銀行家算法資源的分派狀況如下：進(jìn)程現(xiàn)有資源向量請(qǐng)求資源向量P311P164P283P4122所以狀態(tài)1是安全的，依照單資源銀行家算法資源分派的安全序列為（P3，P1，P2，P4）（注意安全序列不唯一）。

②狀態(tài)2

進(jìn)程已分派資源向量請(qǐng)求資源向量P144P236P353當(dāng)前共享資源的可分派數(shù)量為：2

解：狀態(tài)2是擔(dān)憂(yōu)全狀態(tài)。由于當(dāng)前共享資源的可分派數(shù)量無(wú)法滿(mǎn)足任何一個(gè)進(jìn)程的請(qǐng)求資源數(shù)量，所以，依照單資源銀行家算法可以判斷，共享資源無(wú)法分派給任何一個(gè)進(jìn)程，當(dāng)前系統(tǒng)處于擔(dān)憂(yōu)全狀態(tài)。

（2）多資源銀行家算法

假定系統(tǒng)中有n個(gè)進(jìn)程P1,P2,…Pn,m類(lèi)資源R1,R2,…Rm。系統(tǒng)擁有每類(lèi)資源的向量R=(R1,R2,…Rm)。系統(tǒng)當(dāng)前可用資源向量V=(V1,V2,…Vm)。C11C12…C1m

C21C22…C2m

各進(jìn)程當(dāng)前對(duì)資源的請(qǐng)求矩陣C=……Cn1Cn2…Cnm

A11A12…A1mA21A22…A2m

當(dāng)前資源分派矩陣A=……

An1An2…Anm

多資源銀行家算法是從系統(tǒng)的當(dāng)前狀態(tài)出發(fā)，逐個(gè)檢查各個(gè)進(jìn)程，誰(shuí)能完成其工作（即請(qǐng)求各類(lèi)資源的數(shù)量不超過(guò)當(dāng)前可用資源向量），然后假定其完成了工作且歸還了全部資源，對(duì)該進(jìn)程進(jìn)行標(biāo)記，再進(jìn)而檢查剩余進(jìn)程誰(shuí)又能完成工作……假使所有進(jìn)程均能完成工作，則當(dāng)前系統(tǒng)狀態(tài)安全，可以按進(jìn)程標(biāo)記的順序（即安全序列）分派共享資源R，否則當(dāng)前系統(tǒng)處于擔(dān)憂(yōu)全狀態(tài)。

例2-2用銀行家算法判斷下述狀態(tài)是否安全，假使安全寫(xiě)出安全序列，假使擔(dān)憂(yōu)全說(shuō)明理由。

資源狀況已分派資源請(qǐng)求資源可用資源進(jìn)程R1R2R3R1R2R3R1R2R3P1202111102

P2

010011

P3111310P4110001解：依照多資源銀行家算法資源可進(jìn)行如下分派：資源狀況現(xiàn)有資源請(qǐng)求資源已分派資源

進(jìn)程R1R2R3R1R2R3R1R2R3P4102001110

P1

212111202

P2414011010P3424310111所以當(dāng)前系統(tǒng)狀態(tài)是安全的，依照多資源銀行家算法資源分派的安全序列為（P4，P1，P2，P3）（注意安全序列不唯一）。

2.試驗(yàn)?zāi)康?/p>

通過(guò)本試驗(yàn)?zāi)M實(shí)現(xiàn)操作系統(tǒng)管理有限資源，避免產(chǎn)生死鎖的方法。3.試驗(yàn)內(nèi)容

使用高級(jí)程序設(shè)計(jì)語(yǔ)言，編寫(xiě)實(shí)現(xiàn)銀行家算法（單資源銀行家算法、多資源銀行家算法）的程序。

4.試驗(yàn)要求

仿循例2-1和例2-2，利用銀行家算法編程，判斷系統(tǒng)是否處于安全狀態(tài)。要求運(yùn)行程序時(shí)，輸入數(shù)據(jù)包括：進(jìn)程數(shù)量，已分派資源向量（或矩陣），請(qǐng)求資源向量（或矩陣）和可使用資源向量；程序運(yùn)行結(jié)果是：假使系統(tǒng)當(dāng)前狀態(tài)是安全的，則輸出資源分派的安全序列，假使系統(tǒng)當(dāng)前狀態(tài)是擔(dān)憂(yōu)全的，則顯示此次請(qǐng)求資源不能滿(mǎn)足的提醒即可。

5.試驗(yàn)學(xué)時(shí)4/6學(xué)時(shí)試驗(yàn)3模擬存儲(chǔ)分派管理1.存儲(chǔ)分派管理算法

可變分區(qū)的存儲(chǔ)器分派管理算法一般有三種：（1）最正確適應(yīng)法

最正確適應(yīng)法要求空閑分區(qū)按從小到大遞增的順序排列，在進(jìn)行內(nèi)存分派時(shí)，從空閑分區(qū)表首開(kāi)始順序查找，直到找到第一個(gè)能滿(mǎn)足其大小要求的空閑分區(qū)為止，然后，再依照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分派給請(qǐng)求者，剩余的空閑分區(qū)仍留在空閑分區(qū)表中；否則分派失敗。

（2）最先適應(yīng)法

最先適應(yīng)法要求空閑分區(qū)按地址遞增的順序排列，在進(jìn)行內(nèi)存分派時(shí)，從空閑分區(qū)表首開(kāi)始順序查找，直到找到第一個(gè)能滿(mǎn)足其大小要求的空閑分區(qū)為止，然后，再依照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分派給請(qǐng)求者，剩余的空閑分區(qū)仍留在空閑分區(qū)表中；否則分派失敗。

（3）最壞適應(yīng)法

最壞適應(yīng)法要求空閑分區(qū)按大小遞減的次序排列，在進(jìn)行內(nèi)存分派時(shí)，先檢查空閑分區(qū)表中的第一個(gè)空閑分區(qū)，若第一個(gè)空閑分區(qū)小于所要求的大小，則分派失

?。环駝t從該空閑分區(qū)中劃出作業(yè)大小的一塊內(nèi)存空間分派給請(qǐng)求者，剩余的空閑分區(qū)仍留在空閑分區(qū)表中。

例2-3某系統(tǒng)的空閑分區(qū)表如表2-1所示。現(xiàn)有作業(yè)序列：96K、20K、200K，若分別使用最正確適應(yīng)法、最先適應(yīng)法和最壞適應(yīng)法，試問(wèn)哪種算法能夠滿(mǎn)足作業(yè)序列的請(qǐng)求。

表2-1空閑分區(qū)表

分區(qū)號(hào)大小起始地址132K100K210K150K35K200K4218K220K596K530K

解：

①采用最正確適應(yīng)法

分派后的空閑分區(qū)表如表2-2所示。采用最正確適應(yīng)法能夠滿(mǎn)足作業(yè)序列的請(qǐng)求。

表2-2分派后的空閑分區(qū)表

分區(qū)號(hào)大小起始地址112K100K210K150K35K200K418K220K

②采用最先適應(yīng)法

分派96K和20K的作業(yè)后，空閑分區(qū)表如表2-3所示。此時(shí)已經(jīng)沒(méi)有能夠滿(mǎn)足200K作業(yè)大小的空閑分區(qū)，所以采用最先適應(yīng)法不能滿(mǎn)足作業(yè)序列的請(qǐng)求。

表2-3分派后的空閑分區(qū)表

分區(qū)號(hào)大小起始地址112K100K210K150K35K200K4122K220K5