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

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

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

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

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

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

7、（分）（2分）10.系統運行有三個進程：輸入進程、計算進程和打印進程，它們協同完成工作。輸入進程和計算進程之間共用緩沖區計算進程和打印進程之間共用緩沖區。輸入進程接收外部數據放入中；計算進程從中取出數據進行計算，然后將結果放入f打印進程從取出數據打印輸出。用算法描述這三個進程的工作情況，并用和原語實現其同步操作。（共分）解:（共分）解答：輸入進程、計算進程和打印進程之間的同步問題描述如下：end（評分標準：信號量設置2分，輸入進程、計算進程、打印進程各2分）11在一個請求分頁系統中，有一個長度為5頁的進程，假如系統為它分配3個物理塊，并且此進程的頁面走向為23215245325。試用和兩種算法

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

9、為十進制數，且從0開始計數。）。當虛頁4發生缺頁時，使用下列的頁面置換算法，哪一個物理塊將被換出？并解釋原因（1分）頁號塊號加載時間訪問時間訪問位修改位算法算法3.算法當頁面的訪問串為：4,2421,3”的算法解：1.換出第3號虛頁，因為它加載的時間最早；換出第1號虛頁，因為它最近最久沒被訪問；換出第1號虛頁，因為它最近既沒被訪問，又沒被修改；換出第3號虛頁，因為它離訪問點最遠。14用.整型信號量描述在哲學家進餐問題中，至多允許4個哲學家同時進餐的算法。（1,分）解：15考慮一個有15個0存儲器單元的系統，如下分配給三個進程進程最大占有使用銀行家算法，以確定下面的任何一個請求是否安全：a第個進

10、程到達，最多需要個存儲單元，最初需要個單元;b第個進程到達，最多需要個存儲單元，最初需要個單元;如果安全給出安全序列；若不安全給出結果分配簡表。（分）解：進程最大占有尚需可用安全序列為：1、2、3、4所以系統是安全的，可以進行分配。進程最大占有尚需可用當前可用的資源不夠任何一個進程運行完畢，所以不安全。16、（8分）在某采用頁式存儲管理的系統中，所有作業執行時依次訪問的頁號是：1,2，3,4，3,1，5,4,6，2，1,2,57,3，2,4假定開始時先把前4頁裝入內存。要求完成：（1）先進先出調度算法，作業執行過程中會產生次缺頁中斷。依次淘汰的頁號是。（2）最近最少使用算法時，作業執行過程中會

11、產生次缺頁中斷。依次淘汰的頁號是。解:1）先進先出調度算法，作業執行過程中會產生_7次缺頁中斷。依次淘汰的頁號是_1、2、3、4、5、6、2_。（4分）（2）最近最少使用算法時，作業執行過程中會產生_8_次缺頁中斷。依次淘汰的頁號是2、3、1、5、4、6、1、5。17、（8分）假定某移動磁盤上，處理了訪問56號柱面的請求后，現在正在70號柱面上讀信息，目前有下面的請求訪問磁盤柱面的序列：73,68,100,120,60,108,8，50。請寫出：（1）用最短查找時間優先算法，列出響應的次序。（2）用電梯調度算法，列出響應的次序。解：（1）用最短查找時間優先算法，響應的次序為68、73、60、5

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

13、因為該程序基本可用內存是200字,可知內存塊數為2采用先進先出置換算法（FIFO），總共有6次缺頁，缺頁率為6/12=50%，具體算法如下：（4分）頁面走向001103122443塊1003344塊211223缺頁缺缺缺缺缺缺采用最佳置換算法（OPT），總共有5次缺頁，缺頁率為5/12=41.6%，具體算法如下：（4分）頁面走向001103122443塊100333塊21124缺頁缺缺缺缺缺19、（10分）在一個批處理單道系統中，假設有四道作業，它們的提交時間及運行時間在下表中所列，當第一個作業進入系統后開始調度，假定作業都是僅作計算，采用計算時間短的作業優先調度算法，忽略調度花費時間。作業進

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