操作系統(tǒng)試題計(jì)算題

1、四、計(jì)算題這是一個(gè)從鍵盤輸入到打印機(jī)輸出的數(shù)據(jù)處理流圖，其中鍵盤輸入進(jìn)程通過(guò)緩沖區(qū)buf1把輸入數(shù)據(jù)傳送給計(jì)算進(jìn)程，計(jì)算進(jìn)程把處理結(jié)果通過(guò)緩沖buf2傳送給打印進(jìn)程。bufl和buf2為臨界資源，試寫出鍵盤輸入進(jìn)程，計(jì)算進(jìn)程及打印進(jìn)程間的同步算法。（10分）輸入進(jìn)程ff計(jì)算進(jìn)程ff打印進(jìn)程解答：從鍵盤輸入到打印機(jī)輸出的數(shù)據(jù)傳送過(guò)程，可以看作是由鍵盤輸入進(jìn)程到計(jì)算進(jìn)程，以及由計(jì)算進(jìn)程到打印輸出進(jìn)程這兩個(gè)數(shù)據(jù)傳送進(jìn)程所組成。其中，對(duì)鍵盤輸入進(jìn)程而言，計(jì)算進(jìn)程是消費(fèi)者進(jìn)程；而對(duì)打印輸出進(jìn)程而言，計(jì)算進(jìn)程又是生產(chǎn)者進(jìn)程。據(jù)此可將它們之間的同步問(wèn)題描述如下：進(jìn)程進(jìn)程進(jìn)程進(jìn)程.設(shè)系統(tǒng)有三種類型的資源，數(shù)量

2、為42,系統(tǒng)中有進(jìn)程進(jìn)程進(jìn)程進(jìn)程進(jìn)程申請(qǐng)（3，2，1）申請(qǐng)（1，0，1,申請(qǐng)（0，1，0,申請(qǐng)（，20，0,請(qǐng)你給出一和防止死鎖的資源剝奪分配策略，完成上述請(qǐng)求序列，并列出資源分配過(guò)程，指明哪些進(jìn)程需要等待，哪些資源被剝奪。（1分0,解：（1分0,申請(qǐng)類資源時(shí)，檢查中有無(wú)可分配的資源：有則分配給；否則將占有的等待原占有的所有資源和新申請(qǐng)的資源剩余資源申請(qǐng)類資源時(shí)，檢查中有無(wú)可分配的資源：有則分配給；否則將占有的等待原占有的所有資源和新申請(qǐng)的資源剩余資源資源全部釋放而進(jìn)入等待狀態(tài)資源分配過(guò)程：進(jìn)程進(jìn)程0，0，1，0,不（滿足的所有資源被剝奪，處于等待進(jìn)程：,0c完成之后，可完成。的所有資源被剝奪

3、，處于等待進(jìn)程：,0c完成之后，可完成。4.設(shè)公共汽車上，司機(jī)和售票員的活動(dòng)分別是司機(jī)：?jiǎn)?dòng)車輛正常行車到站停車售票員：關(guān)車門售票曰開車門下乘客上乘客原語(yǔ)操作實(shí)現(xiàn)它們的在汽車不斷地到站，停車，行使過(guò)程中，這兩個(gè)活動(dòng)有什么同步關(guān)系？并用同步。原語(yǔ)操作實(shí)現(xiàn)它們的解：?jiǎn)?dòng)車輛；正常行車到站停車上乘客關(guān)車門；售票；曰9開車門下乘客5某虛擬存儲(chǔ)器的用戶編程空間共1內(nèi)存為K假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面的頁(yè)號(hào)和物理塊號(hào)的對(duì)照表如下：頁(yè)號(hào)物理塊號(hào)則邏輯地址（）所對(duì)應(yīng)的物理地址是什么？答：邏輯地址）所對(duì)應(yīng)的二進(jìn)制表示形式是：0由于，下劃線部分前的編碼為0表示該邏輯地址對(duì)應(yīng)的頁(yè)號(hào)為查頁(yè)表，得到物理塊號(hào)是

4、（十進(jìn)制），即物理塊地址為：0拼接塊內(nèi)地址,得,即（）。6某段表內(nèi)容如下：段號(hào)段首地址段長(zhǎng)度一邏輯地址為（2，154）的實(shí)際物理地址為多少？答：邏輯地址（2154）表示段號(hào)為2,即段首地址為480K,154為單元號(hào)，則實(shí)際物理地址為480K+154。7、設(shè)系統(tǒng)中有三種類型的資源（A,B,C）和五個(gè)進(jìn)程（P1,P2,P3,P4,P5）,A資源的數(shù)量為17,B資源的數(shù)量為5,C資源的數(shù)量為20。在T0時(shí)刻系統(tǒng)狀態(tài)如表1和表2所示。（共10分）系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。T0時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列。在T0時(shí)刻若進(jìn)程P2請(qǐng)求資源（0,3,4）,是否能實(shí)施資源分配？為什么？在的

5、基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2,0,1）,是否能實(shí)施資源分配？為什么？在的基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（0,2,0）,是否能實(shí)施資源分配？為什么？表1T0時(shí)刻系統(tǒng)狀態(tài)最大資源需求量已分配資源數(shù)量表2T0時(shí)刻系統(tǒng)狀態(tài)剩余資源數(shù)系統(tǒng)中有五個(gè)進(jìn)程PP2、P3、P4、P5,有三種類型的資源：R1、R2、和R3。在T0時(shí)刻系統(tǒng)狀態(tài)如表所示。若采用銀行家算法實(shí)施死鎖避免策略，回答下列問(wèn)題：（共9分，每小題3分）T0時(shí)刻是否為安全狀態(tài)？為什么？若這時(shí)P4請(qǐng)求資源（1,2,0）,是否能實(shí)施資源分配？為什么？3在上面的基礎(chǔ)上，若進(jìn)程P3請(qǐng)求資源（0,1,0），是否能實(shí)施資源分配？為什么?To時(shí)刻系統(tǒng)狀態(tài)已分配資源

6、數(shù)量最大資源需求量剩余資源數(shù)解：（共分，每小題分）T0時(shí)刻是安全的，安全序列為：P1，P4，P5,P2，P3P4請(qǐng)求資源（1,2,0）,根據(jù)銀行家算法，預(yù)分配后系統(tǒng)是安全的，安全序列為：P1,P4,P5,P2,P3P3請(qǐng)求資源（1,1,0）,根據(jù)銀行家算法，預(yù)分配后系統(tǒng)不安全，所以不能實(shí)施資源分配。9一個(gè)進(jìn)程的大小占個(gè)頁(yè)面，每頁(yè)的大小為，系統(tǒng)為它分配了個(gè)物理塊。當(dāng)前進(jìn)程的頁(yè)表如圖所示：（共分）塊號(hào)存在位訪問(wèn)位修改位有那些頁(yè)面不在內(nèi)存？（2分）4單34單3元2的物理地址（用十六進(jìn)制表示）,并說(shuō)明理由。（6分）按頁(yè)號(hào)）,或第3和5按頁(yè)號(hào)）,或第3和5頁(yè)（按序號(hào)）。（2分）C分），缺頁(yè)，換出第三頁(yè)。

7、（分）（2分）10.系統(tǒng)運(yùn)行有三個(gè)進(jìn)程：輸入進(jìn)程、計(jì)算進(jìn)程和打印進(jìn)程，它們協(xié)同完成工作。輸入進(jìn)程和計(jì)算進(jìn)程之間共用緩沖區(qū)計(jì)算進(jìn)程和打印進(jìn)程之間共用緩沖區(qū)。輸入進(jìn)程接收外部數(shù)據(jù)放入中；計(jì)算進(jìn)程從中取出數(shù)據(jù)進(jìn)行計(jì)算，然后將結(jié)果放入f打印進(jìn)程從取出數(shù)據(jù)打印輸出。用算法描述這三個(gè)進(jìn)程的工作情況，并用和原語(yǔ)實(shí)現(xiàn)其同步操作。（共分）解:（共分）解答：輸入進(jìn)程、計(jì)算進(jìn)程和打印進(jìn)程之間的同步問(wèn)題描述如下：end（評(píng)分標(biāo)準(zhǔn)：信號(hào)量設(shè)置2分，輸入進(jìn)程、計(jì)算進(jìn)程、打印進(jìn)程各2分）11在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，有一個(gè)長(zhǎng)度為5頁(yè)的進(jìn)程，假如系統(tǒng)為它分配3個(gè)物理塊，并且此進(jìn)程的頁(yè)面走向?yàn)?3215245325。試用和兩種算法

8、分別計(jì)算出程序訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)。（分）解：TOC o 1-5 h z第1頁(yè)2225553第2頁(yè)333222第3頁(yè)11144缺頁(yè)中斷次數(shù)第1頁(yè)222255第2頁(yè)33523第3頁(yè)1144缺頁(yè)中斷次數(shù)=5進(jìn)程A,，通過(guò)個(gè)緩沖區(qū)向進(jìn)程，不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：1每個(gè)發(fā)送進(jìn)程一次發(fā)送一個(gè)消息，寫入緩沖區(qū)，緩沖區(qū)大小與消息長(zhǎng)度一致；2對(duì)每個(gè)消息，1，都需接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)；3個(gè)緩沖區(qū)都滿時(shí)，發(fā)送進(jìn)程等待，沒(méi)有可讀的消息時(shí)，接收進(jìn)程等待。試用和原語(yǔ)操作組織正確的發(fā)送和接收操作。（O）解：13一個(gè)進(jìn)程的大小為5個(gè)頁(yè)面，為它分配了四個(gè)物理塊。當(dāng)前每個(gè)塊的情況如下表所示（都

9、為十進(jìn)制數(shù)，且從0開始計(jì)數(shù)。）。當(dāng)虛頁(yè)4發(fā)生缺頁(yè)時(shí)，使用下列的頁(yè)面置換算法，哪一個(gè)物理塊將被換出？并解釋原因（1分）頁(yè)號(hào)塊號(hào)加載時(shí)間訪問(wèn)時(shí)間訪問(wèn)位修改位算法算法3.算法當(dāng)頁(yè)面的訪問(wèn)串為：4,2421,3”的算法解：1.換出第3號(hào)虛頁(yè)，因?yàn)樗虞d的時(shí)間最早；換出第1號(hào)虛頁(yè)，因?yàn)樗罱罹脹](méi)被訪問(wèn)；換出第1號(hào)虛頁(yè)，因?yàn)樗罱葲](méi)被訪問(wèn)，又沒(méi)被修改；換出第3號(hào)虛頁(yè)，因?yàn)樗x訪問(wèn)點(diǎn)最遠(yuǎn)。14用.整型信號(hào)量描述在哲學(xué)家進(jìn)餐問(wèn)題中，至多允許4個(gè)哲學(xué)家同時(shí)進(jìn)餐的算法。（1,分）解：15考慮一個(gè)有15個(gè)0存儲(chǔ)器單元的系統(tǒng)，如下分配給三個(gè)進(jìn)程進(jìn)程最大占有使用銀行家算法，以確定下面的任何一個(gè)請(qǐng)求是否安全：a第個(gè)進(jìn)

10、程到達(dá)，最多需要個(gè)存儲(chǔ)單元，最初需要個(gè)單元;b第個(gè)進(jìn)程到達(dá)，最多需要個(gè)存儲(chǔ)單元，最初需要個(gè)單元;如果安全給出安全序列；若不安全給出結(jié)果分配簡(jiǎn)表。（分）解：進(jìn)程最大占有尚需可用安全序列為：1、2、3、4所以系統(tǒng)是安全的，可以進(jìn)行分配。進(jìn)程最大占有尚需可用當(dāng)前可用的資源不夠任何一個(gè)進(jìn)程運(yùn)行完畢，所以不安全。16、（8分）在某采用頁(yè)式存儲(chǔ)管理的系統(tǒng)中，所有作業(yè)執(zhí)行時(shí)依次訪問(wèn)的頁(yè)號(hào)是：1,2，3,4，3,1，5,4,6，2，1,2,57,3，2,4假定開始時(shí)先把前4頁(yè)裝入內(nèi)存。要求完成：（1）先進(jìn)先出調(diào)度算法，作業(yè)執(zhí)行過(guò)程中會(huì)產(chǎn)生次缺頁(yè)中斷。依次淘汰的頁(yè)號(hào)是。（2）最近最少使用算法時(shí)，作業(yè)執(zhí)行過(guò)程中會(huì)

11、產(chǎn)生次缺頁(yè)中斷。依次淘汰的頁(yè)號(hào)是。解:1）先進(jìn)先出調(diào)度算法，作業(yè)執(zhí)行過(guò)程中會(huì)產(chǎn)生_7次缺頁(yè)中斷。依次淘汰的頁(yè)號(hào)是_1、2、3、4、5、6、2_。（4分）（2）最近最少使用算法時(shí)，作業(yè)執(zhí)行過(guò)程中會(huì)產(chǎn)生_8_次缺頁(yè)中斷。依次淘汰的頁(yè)號(hào)是2、3、1、5、4、6、1、5。17、（8分）假定某移動(dòng)磁盤上，處理了訪問(wèn)56號(hào)柱面的請(qǐng)求后，現(xiàn)在正在70號(hào)柱面上讀信息，目前有下面的請(qǐng)求訪問(wèn)磁盤柱面的序列：73,68,100,120,60,108,8，50。請(qǐng)寫出：（1）用最短查找時(shí)間優(yōu)先算法，列出響應(yīng)的次序。（2）用電梯調(diào)度算法，列出響應(yīng)的次序。解：（1）用最短查找時(shí)間優(yōu)先算法，響應(yīng)的次序?yàn)?8、73、60、5

12、0、8、100、108、120。（2）用電梯調(diào)度算法，響應(yīng)的次序?yàn)?3、100、108、120、68、60、50、8。設(shè)某程序大小為460字，并且它有下面的存儲(chǔ)訪問(wèn)序列：10，11，104，170，73，309，185，245，246，434，458，364設(shè)頁(yè)面大小是100字，請(qǐng)給出該訪問(wèn)序列的頁(yè)面走向又設(shè)該程序基本可用內(nèi)存是200字，采用先進(jìn)先出置換算法（FIFO）,求出其缺頁(yè)率如果采用最佳置換算法（OPT）,其缺頁(yè)率又是多少?（注：缺頁(yè)率=缺頁(yè)次數(shù)/訪問(wèn)頁(yè)面總數(shù)）解：（共10分）根據(jù)已知條件頁(yè)面大小是100字,將頁(yè)面訪問(wèn)序列簡(jiǎn)化為：0,0,1,1,0,3,1,2,2,4,4,3（2分）又

13、因?yàn)樵摮绦蚧究捎脙?nèi)存是200字,可知內(nèi)存塊數(shù)為2采用先進(jìn)先出置換算法（FIFO），總共有6次缺頁(yè)，缺頁(yè)率為6/12=50%，具體算法如下：（4分）頁(yè)面走向001103122443塊1003344塊211223缺頁(yè)缺缺缺缺缺缺采用最佳置換算法（OPT），總共有5次缺頁(yè)，缺頁(yè)率為5/12=41.6%，具體算法如下：（4分）頁(yè)面走向001103122443塊100333塊21124缺頁(yè)缺缺缺缺缺19、（10分）在一個(gè)批處理單道系統(tǒng)中，假設(shè)有四道作業(yè)，它們的提交時(shí)間及運(yùn)行時(shí)間在下表中所列，當(dāng)?shù)谝粋€(gè)作業(yè)進(jìn)入系統(tǒng)后開始調(diào)度，假定作業(yè)都是僅作計(jì)算，采用計(jì)算時(shí)間短的作業(yè)優(yōu)先調(diào)度算法，忽略調(diào)度花費(fèi)時(shí)間。作業(yè)進(jìn)

14、入系統(tǒng)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：002小時(shí)28：5030分鐘39：006分鐘49：3012分鐘求出每個(gè)作業(yè)開始時(shí)間、完成時(shí)間及周轉(zhuǎn)時(shí)間并填入表中。（2）計(jì)算四個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間應(yīng)為_88分鐘_.解：（1）每空0.5分，6分。作業(yè)進(jìn)入系統(tǒng)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間8：002小時(shí)8:0010:0012分0鐘8：5030分鐘10:1810:4811分8鐘9：006分鐘10:0010:066分鐘9：3012分鐘10:0610:1848分鐘20（4分）一個(gè)由3個(gè)頁(yè)面（頁(yè)號(hào)為0、1、2），每頁(yè)有2048個(gè)字節(jié)組成的程序，假定在某時(shí)刻調(diào)入8個(gè)物理塊的內(nèi)存，其頁(yè)面的頁(yè)號(hào)和物理塊號(hào)的對(duì)照表如下：邏輯頁(yè)號(hào)主存塊號(hào)041721請(qǐng)根據(jù)頁(yè)表，計(jì)算下列給出的邏輯地址對(duì)應(yīng)的絕對(duì)地址。（1）100（2）2617（3）5196答：（4分）首先根據(jù)邏輯地址查頁(yè)表，得到主存的塊號(hào)，再根據(jù)公式絕對(duì)地址=塊號(hào)x塊長(zhǎng)+頁(yè)內(nèi)地址進(jìn)行計(jì)算。（1）100的頁(yè)號(hào)為0（100/2048=2），頁(yè)內(nèi)地址為