操作系統(tǒng),原理,徐宗元復習課件

操作系統(tǒng)

“操作系統(tǒng)”，徐宗元，

高等教育出版社，2005年第二版復習考試題型單項選擇題計算填空題

計算題編程填空題問答題復習資料教學專欄教學課程操作系統(tǒng)原理課件學習操作系統(tǒng)原理(發(fā)布日期2004-11.29)復習測試教學專欄課程輔導材料維護“選擇課程”選擇“操作系統(tǒng)原理”下載文件“操作系統(tǒng)原理教學大綱和網上作業(yè)”、“復習大綱”第一章習題選2.操作系統(tǒng)是一種﹎﹎A﹎﹎，在操作系統(tǒng)中采用多道程序設計方式能提高CPU和外部設備的﹎﹎B﹎﹎。一般來說，為了實現(xiàn)多道程序設計，計算機需要有﹎﹎C﹎﹎。A:(1)通用軟件；(2)系統(tǒng)軟件；(3)應用軟件；(4)軟件包。B:(1)利用效率；(2)可靠性；(3)穩(wěn)定性；(4)兼容性。C：(1)更大的內存；(2)更快的外部設備；(3)更快的CPU；(4)更先進的終端；2.A-2B-1C-1習題-1選10.分時系統(tǒng)中，為使多個用戶能夠同時與系統(tǒng)交互，最關鍵的問題是﹎﹎A﹎﹎，當用戶數目為100時，為保證響應不超過2秒；此時的時間片最大應為﹎﹎B﹎﹎。A：(1)計算機具有足夠的運行速度；(2)內存容量應足夠大；(3)系統(tǒng)能及時地接收多個用戶輸入；(4)能在一短的時間內，使所有用戶程序都能運行；(5)能快速進行內外存對換。B：(1)10ms；(2)20ms；(3)50ms；(4)100ms；(5)200ms。10.A-4B-2習題-2選8.在設計分時操作系統(tǒng)時，首先要考慮的是﹎﹎A﹎﹎；在設計實時操作系統(tǒng)時，首先要考慮的是﹎﹎B﹎﹎；在設計批處理系統(tǒng)時，首先要考慮的是﹎﹎C﹎﹎。A、B、C：(1)靈活性和可適應性；(2)交互性和響應時間；(3)周轉時間和系統(tǒng)吞吐量；(4)實時性和可靠性。8.A-2B-4C-3習題-4選17．脫機用戶接口是配置在﹎﹎A﹎﹎操作系統(tǒng)中的，它是由一組﹎﹎B﹎﹎所組成，聯(lián)機用戶接口是由一組﹎﹎C﹎﹎所組成，而程序接口則是由一組﹎﹎D﹎﹎所組成。A：（1）微機；（2）批處理；（3）分時；（4）實時。B、C、D：（1）系統(tǒng)調用；（2）庫函數；（3）鍵盤命令；（4）作業(yè)控制語言。17.A-2B-4C-3D-1第二章習題選10：在操作系統(tǒng)中進程是一個具有一定獨立功能程序在某個數據集合上的一次﹎﹎A﹎﹎，進程是一個﹎﹎B﹎﹎概念，而程序是一個﹎﹎C﹎﹎的概念。在一單處理機中，若有5個用戶進程，在非管態(tài)的某一時刻，處于就緒狀態(tài)的用戶進程最多有﹎﹎D﹎﹎個，最少有﹎﹎E﹎﹎個。

A：(1)并發(fā)活動；(2)運行活動；(3)單獨操作；(4)關聯(lián)操作。B，C：(1)組合態(tài)；(2)關聯(lián)態(tài)；(3)運行態(tài)；(4)等待態(tài)；(5)靜態(tài)；(6)動態(tài)。D，E：(1)1；(2)2；(3)3；(4)4；(5)5；(6)0。2.A-2B-6C-5D-4E-6習題-2選7：從靜態(tài)角度看，進程由﹎﹎A﹎﹎、﹎﹎B﹎﹎和﹎﹎C﹎﹎三部分組成，用戶可通過﹎﹎D﹎﹎建立和撤消進程，通常用戶進程被建立后，﹎﹎E﹎﹎。A：(1)JCB；(2)DCB；(3)PCB；(4)PMT。B:(1)程序段；(2)文件體；(3)I/O；(4)子程序。C：(1)文件描述塊；(2)數據空間；(3)EOF；(4)I/O緩沖區(qū)。D：(1)函數調用；(2)宏指令；(3)系統(tǒng)調用；(4)過程調用。E：(1)便一直存在于系統(tǒng)中，直到被操作人員撤消；(2)隨著作業(yè)運行正?；虿徽＝Y束而撤消；(3)隨著時間片輪轉而撤消與建立；(4)隨著進程的阻塞或喚醒而撤消與建立。4.A-3B-1C-2D-3E-2習題-4選15：對于記錄型信號量，在執(zhí)行一次P操作時，信號量的值應當為﹎﹎A﹎﹎；當其值為﹎﹎B﹎﹎時，進程應阻塞。在執(zhí)行V操作時，信號量的值應當﹎﹎C﹎﹎；當其值為﹎﹎D﹎﹎時，應喚醒阻塞隊列中的進程。A，C：(1)不變；(2)加1；(3)減1；(4)加指定數值；(5)減指定數值。B，D：(1)大于0；(2)小于0；(3)大于等于0；(4)小于等于0。1.A-3B-2C-2D-4習題-5選8：在操作系統(tǒng)中，解決進程間的﹎﹎A﹎﹎兩種基本關系，往往運用對信號量進行﹎﹎B﹎﹎的﹎﹎C﹎﹎，例如，為保證系統(tǒng)數據庫的完整性，可以把信號量定義為某個庫文件（或記錄）的鎖，初值為1，任何進程存取該庫文件（或記錄）之前先對它作一個﹎﹎D﹎﹎，存取之后對它作一個﹎﹎E﹎﹎，從而做到對該文件（或記錄）任一時刻只有一個進程可存取，但要注意使用不當引起的死鎖。A：(1)同步與異步；(2)串行與并行；(3)調度與控制；(4)同步與互斥。B：(1)消息操作；(2)P-V操作；(3)開關操作；(4)讀寫操作。C：(1)通信原語；(2)調度算法；(3)分配策略；(4)進程控制。D、E：(1)聯(lián)機操作；(2)V操作；(3)輸出操作；(4)讀操作；(5)寫操作；(6)P操作；(7)輸入操作。2.A-4B-2C-1D-6E-2

習題-6選1：在操作系統(tǒng)中處理機管理由作業(yè)管理和進程管理兩部分組成，作業(yè)管理把作業(yè)流分成提交、后備、運行、完成四個狀態(tài)，進程管理把進程分成就緒、執(zhí)行、阻塞三個基本狀態(tài)。作業(yè)由提交狀態(tài)到后備狀態(tài)由﹎﹎A﹎﹎完成，由后備狀態(tài)到運行狀態(tài)由﹎﹎B﹎﹎完成，進程由就緒狀態(tài)到執(zhí)行狀態(tài)由﹎﹎C﹎﹎，用戶進程的祖先進程由﹎﹎E﹎﹎建立的。A，B，C，D，E：(1)作業(yè)調度程序；(2)進程調度程序；(3)存儲管理程序；(4)輸入輸出程序；(5)假脫機（SPOOLing）處理程序；(6)交通程序；(7)設備管理程序。選12：操作系統(tǒng)的主要性能參數：﹎﹎A﹎﹎指的是單位時間內系統(tǒng)處理的作業(yè)量。﹎﹎B﹎﹎指的是從作業(yè)或命令的輸入到其結束的間隔時間，在分析性能時常用其倒數。﹎﹎C﹎﹎指的是在一個給定的時間內，系統(tǒng)的一個指定成份被使用的時間比例。A，B，C：(1)周轉時間；(2)處理時間；(3)消逝時間；(4)利用率；(5)生產率；(6)吞吐量。1.A-5B-1C-2D-12.A-6B-1C-4習題-8選18：產生死鎖的基本原因是﹎﹎A﹎﹎和﹎﹎B﹎﹎，產生死鎖的四個必要條件是互斥條件﹎﹎C﹎﹎，不剝奪條件和﹎﹎D﹎﹎。A：(1)資源分配不當；(2)系統(tǒng)資源不足；(3)作業(yè)調度不當；(4)資源的獨占性。B：(1)進程推進順序非法；(2)進程調度不當；(3)系統(tǒng)中進程太多；(4)CPU運行太快。C：(1)請求和阻塞條件；(2)請求和釋放條件；(3)請求和保持條件；(4)釋放和阻塞條件；(5)釋放和請求條件。D：(1)線性增長條件；(2)環(huán)路條件；(3)無序釋放條件；(4)有序請求條件；(5)無序請求條件。5.A-2B-1C-3D-2習題-9選19：預防死鎖的論述中，﹎﹎A﹎﹎條是正確的論述。(1)由于產生死鎖的基本原因是系統(tǒng)資源不足，因而預防死鎖的有效方法，是根據系統(tǒng)規(guī)模，配置足夠的系統(tǒng)資源。(2)由于產生死鎖的另一種基本原因是進程推進順序不當，因而預防死鎖的有效方法，是使進程的推進順序合法。(3)因為只要系統(tǒng)不進入不安全狀態(tài)，便不會產生死鎖，故預防死鎖的有效方法，是防止系統(tǒng)進入不安全狀態(tài)。(4)可以通過破壞產生死鎖的四個必要條件之一或其中幾個的方法，來預防發(fā)生死鎖。6.A-4第三章習題選4：靜態(tài)重定位是在作業(yè)的﹎﹎A﹎﹎中進行的，動態(tài)重定位是在作業(yè)的﹎﹎B﹎﹎中進行的。A，B：（1）編譯過程；（2）裝入過程；（3）修改過程；（4）執(zhí)行過程。選5：在首次適應算法中，要求空閑分區(qū)按﹎﹎A﹎﹎順序鏈接成空閑分區(qū)鏈；在最佳適應算法中是按﹎﹎B﹎﹎順序形成空閑分區(qū)鏈；最壞適應算法是按﹎﹎C﹎﹎順序形成空閑分區(qū)鏈。A，B，C：（l）空閑區(qū)首址遞增；（2）空閑區(qū)首址遞減；（3）空閑區(qū)大小遞增；（4）空閑區(qū)大小遞減。A-2B-4A-1B-3C-4習題-3選3：由固定分區(qū)方式發(fā)展為分頁存儲管理方式的主要推動力是﹎﹎A﹎﹎；由分頁系統(tǒng)發(fā)展為分段系統(tǒng)，進而又發(fā)展為段頁式系統(tǒng)的主要動力分別是﹎﹎B﹎﹎和﹎﹎C﹎﹎。A，B，C：（l）提高內存利用率；（2）提高系統(tǒng)吞吐量；（3）滿足用戶需要；（4）更好地滿足多道程序運行的需要。（5）既滿足用戶需要，又提高內存利用率。8.A-1B-3C-5習題-4選16：虛擬存貯管理系統(tǒng)的基礎是程序的局部性理論。此理論的基本含義是﹎﹎A﹎﹎。局部性有兩種表現(xiàn)形式：時間局限性和﹎﹎B﹎﹎。它們的意義分別為﹎﹎C﹎﹎和﹎﹎D﹎﹎。根據局部性理論，Denning提出了﹎﹎E﹎﹎。A、B，①程序執(zhí)行時對主存和訪問是不均勻的②代碼的順序執(zhí)行③變量的連續(xù)訪問④指令的局部性⑤數據的局部性⑥空間局部性C、D：①最近被訪問的單元，很可能在不久的將來還要被訪問②最近被訪問的單元，很可能在它附近的單元也即將被訪問③結構化程序設計，很少出現(xiàn)轉移語句④程序中循環(huán)語句的執(zhí)行時間一般很長⑤程序中使用的數據局部于各子程序E：①Cache結構的思想②工作集理論③最近最少使用（LRU）頁面置換算法④先進先出頁面置換算法1.A-1B-6C-1D-2E-2習題-5選7：在請求分頁內存管理的頁表表項中，其中狀態(tài)位供﹎﹎A﹎﹎時參考；修改位供﹎﹎B﹎﹎時參考；訪問位供﹎﹎C﹎﹎時參考；外存始址供﹎﹎D﹎﹎時參考。A，B，C，D：（l）分配頁面；（2）置換算法；（3）程序訪問；（4）換出頁面；（5）調入頁面。選9：在請求調頁系統(tǒng)中，凡未裝入過內存的頁都應從﹎﹎A﹎﹎調入；已運行過的頁主要是從﹎﹎B﹎﹎調入，有時也可以從﹎﹎C﹎﹎調入。A，B，C：（1）系統(tǒng)區(qū)；（2）文件區(qū)；（3）對換區(qū)；（4）頁面緩沖池。3.A-3B-4C-2D-54.A-2B-3C-4第四章習題選1：在I/O設備控制的發(fā)展過程中，最主要的推動因素是﹎﹎A﹎﹎，提高I/O速度和設備利用率，在OS中主要依靠﹎﹎B﹎﹎功能。使用戶所編制的程序與實際使用的物理設備無關是由﹎﹎C﹎﹎功能實現(xiàn)的。A：（1）提高資源利用率；（2）提高系統(tǒng)吞吐量；（3）減少主機對I/O控制的干預；（4）提高CPU與I/O設備的并行操作程度。B,C：（1）設備分配；（2）緩沖管理；（3）設備管理；（4）設備獨立性；（5）虛擬設備。選8：通道是一種特殊的﹎﹎A﹎﹎，具有﹎﹎B﹎﹎能力。A：（1）I/O設備；（2）設備控制器；（3）處理機；（4）I/O控制器。B：（1）執(zhí)行I/O指令集；（2）執(zhí)行CPU指令集；（3）傳輸I/O命令；（4）運行I/O進程。

A-3B-3C-48.A-3B-1習題-1選5:假定把磁盤上一個數據塊中信息輸入到一單緩沖的時間T為100us，將緩沖區(qū)中數據傳送到用戶區(qū)的時間M為50us,而CPU對這一塊數據進行計算的時間C為50us，這樣，系統(tǒng)對每一塊數據的處理時間為﹎﹎A﹎﹎；如果將單緩沖改為雙緩沖，則系統(tǒng)對每一塊數據的處理時間為﹎﹎B﹎﹎。A,B：（1）50us;(2)100us;(3)150us;(4)200us;(5)250us。5.A-3B-2習題-4（4） SPOOLing系統(tǒng)是建立在分時系統(tǒng)中。（5） SPOOLing系統(tǒng)是虛擬存儲技術的體現(xiàn)。（6） SPOOLing系統(tǒng)是在用戶程序要讀取數據時起動輸入進程輸入數據。（7） 當輸出設備忙時，SPOOLing系統(tǒng)中的用戶程序暫停執(zhí)行，待I/O空閑時再被喚醒，去執(zhí)行輸出操作。（8） SPOOLing系統(tǒng)實現(xiàn)了對I/O設備的虛擬，只要輸入設備空閑，SPOOLing可預先將輸入數據從設備傳輸到輸入井中供用戶程序隨時讀取。（9） 在SPOOLing系統(tǒng)中，用戶程序可以隨時將輸出數據送到輸出井中，待輸出設備空閑時再執(zhí)行數據輸出操作。6.A-8B-9

第五章習題1．下列哪一項不是文件系統(tǒng)的功能?﹎﹎A﹎﹎A：（1）文件系統(tǒng)實現(xiàn)對文件的按名存取（2）負責實現(xiàn)數據的邏輯結構到物理結構的轉換（3）提高磁盤的讀寫速度（4）提供對文件的存取方法和對文件的操作選1．(1)按邏輯結構劃分，文件主要有兩類：﹎﹎A﹎﹎和﹎﹎B﹎﹎。UNIX中的文件系統(tǒng)采用﹎﹎B﹎﹎。(2)文件系統(tǒng)的主要目的是﹎﹎C﹎﹎。(3)文件系統(tǒng)中用﹎﹎D﹎﹎管理文件。(4)為了允許不同用戶的文件具有相同的文件名，通常在文件系統(tǒng)中采用﹎﹎E﹎﹎。A，B：(1)網狀文件；(2)只讀文件；(3)讀寫文件；⑷記錄式文件；⑸索引文件；⑹流式文件；C：(1)實現(xiàn)對文件的按名存取；(2)實現(xiàn)虛擬存貯器；(3)提高外圍設備的輸入輸出速度；(4)用于存貯系統(tǒng)文檔。D：(1)堆棧結構；(2)指針；(3)目錄；(4)頁表。E：(1)重名翻譯；(2)多級目錄；(3)約定；(4)路徑。1.A-32.A-4B-6C-1D-3E-2

習題-1選5.下面關于順序文件和鏈接文件的論述中，第﹎﹎A﹎﹎條是正確的論述。(1)順序文件適于建立在順序存儲設備上，而不適合建立在磁盤上。(2)在顯式鏈接文件中是在每個盤塊中設置一鏈接指針，用于將文件的所有盤塊鏈接起來。(3)順序文件必須采用連續(xù)分配方式，而鏈接文件和索引文件則都可采取離散分配方式。(4)在MS-DOS中采用的是隱式鏈接文件結構。選6.下面關于索引文件的論述中，第﹎﹎A﹎﹎條是正確的論述。(1)索引文件中，索引表的每個表項中含有相應記錄的關鍵字和存放該記錄的物理地址。(2)對順序文件進行檢索時，首先從FCB中讀出文件的第一個盤塊號；而對索引文件進行檢索時，應先從FCB中讀出文件索引表始址。(3)對于一個具有三級索引表的文件，存取一個記錄通常要訪問三次磁盤。(4)在文件較大時，無論是進行順序存取還是隨機存取，通常都是以索引文件方式為最快。

5.A-36.A-2

（二）計算填空題/計算題

（1）作業(yè)／進程調度算法—P65例2-1假定在一個處理機上執(zhí)行以下五個作業(yè)：作業(yè)號ABCDE到達時間02468運行時間36452a.畫出采用FCFS調度算法時調度圖，并計算每個作業(yè)的周轉時間和平均周轉時間。b.畫出采用SJF調度算法時調度圖，并計算每個作業(yè)的周轉時間和平均周轉時間。c.寫出采用HRN（響應比高者優(yōu)先）調度算法時選擇的作業(yè)序號和選擇作業(yè)時依據（各作業(yè)響應比）。（時間的另一種表示方法－－10:20為10點20分）例解－1(1)先來先服務調度算法FCFS作業(yè)調度次序的計算：FCFS按照作業(yè)到達的先后次序來選擇作業(yè)，按作業(yè)到達時間的先后次序五個作業(yè)調度次序為A、B、C、D、E。(2)

短作業(yè)優(yōu)先調度算法SJF作業(yè)調度次序的計算：SJF在到達的作業(yè)中挑選所需運行時間最短的作業(yè)進入主存先運行，調度次序如下：T=0：只有作業(yè)A已到達，調度作業(yè)A運行。

T=3：作業(yè)A完成，作業(yè)B已到達，調度作業(yè)B運行。T=9：作業(yè)B完成，作業(yè)C、D、E已全部到達，比較作業(yè)C、D、E的運行時間，按運行時間短的作業(yè)先運行，則調度次序為E、C、D。例解-2(3)高響應比優(yōu)先(HRRN)(作業(yè))調度算法計算：RP＝1＋((調度時間-到達時間)／運行時間)。

T=0：只有作業(yè)A已到達，調度作業(yè)A運行。T=3：作業(yè)A完成，作業(yè)B已到達，調度作業(yè)B運行。T=9：作業(yè)B完成，作業(yè)C、D、E已到達，計算作業(yè)C、D、E響應比RP分別為：1+(9-4)/4、1+(9-6)/5、1+(9-8)/2，作業(yè)C響應比最大調度運行。T=13：作業(yè)C完成，作業(yè)D、E已到達，計算作業(yè)D、E響應比RP分別為：1+(13-6)/5、1+(13-8)/2，作業(yè)E響應比最大調度運行。T=15：作業(yè)E完成，只有作業(yè)D未完成，調度作業(yè)D運行。T=20：作業(yè)D完成。例解調度圖調度圖:到達|ABCDE作業(yè)|↓↓↓↓↓時間|01234567891011121314151617181920FCFS||-----A-----|-----------B-----------|-------C-------|---------D---------|---E---|SJF||-----A-----|-----------B-----------|---E---|-------C-------|---------D---------|HRN||-----A-----|-----------B-----------|-------C-------|---------D---------|---E---|

例解-3例解-5作業(yè)／進程調度算法--P102問答題12假定在一個處理機上執(zhí)行以下五個作業(yè)：作業(yè)號到達時間運行時間(分)A04B13C25D32E44a.畫出采用FCFS調度算法時調度圖，并計算每個作業(yè)的周轉時間和平均周轉時間。b.畫出采用SJF調度算法時調度圖，并計算每個作業(yè)的周轉時間和平均周轉時間。c.寫出采用HRN（響應比高者優(yōu)先）調度算法時選擇的作業(yè)序號和選擇作業(yè)時依據（各作業(yè)響應比）。調度算法解－11.先來先服務調度算法FCFS作業(yè)調度次序的計算：FCFS按照作業(yè)到達的先后次序來選擇作業(yè)，按作業(yè)到達時間的先后次序五個作業(yè)調度次序為A、B、C、D、E。調度圖:到達|ABCDE作業(yè)|↓↓↓↓↓時間|0123456789101112131415161718FCFS||------A--------|-----B-----|---------C---------|---D---|-------E-------|調度算法解－22.

短作業(yè)優(yōu)先調度算法SJF作業(yè)調度次序的計算：SJF在到達的作業(yè)中挑選所需運行時間最短的作業(yè)進入主存先運行，調度次序如下：T=0：只有作業(yè)A已到達，調度作業(yè)A運行。T=4：作業(yè)A完成，作業(yè)B、C、D、E已全部到達，比較作業(yè)B、C、D、E的運行時間，按運行時間短的作業(yè)先運行，則調度次序為D、B、E、C。調度圖:

到達|ABCDE作業(yè)|↓↓↓↓↓時間|0123456789101112131415161718SJF||-------A-------|---D---|-----B-----|-------E-------|---------C---------|調度算法解-33.高響應比優(yōu)先(HRRN)(作業(yè))調度算法計算：T=0：只有作業(yè)A已到達，調度作業(yè)A運行。T=4：作業(yè)A完成，作業(yè)B、C、D、E已到達，計算作業(yè)B、C、D、E響應比RP分別為：1+3/3、1+2/5、1+1/2、1+0/4，作業(yè)B響應比最大調度運行。T=7：作業(yè)B完成，作業(yè)C、D、E已到達，計算作業(yè)C、D、E響應比RP分別為：1+5/5、1+4/2、1+3/4，作業(yè)D響應比最大調度運行。T=9：作業(yè)D完成，作業(yè)C、E已到達，計算作業(yè)C、E響應比RP分別為：1+7/5、1+5/4，作業(yè)C響應比最大調度運行。T=14：作業(yè)C完成，只有作業(yè)E未完成，調度作業(yè)E運行。(2)利用銀行家算法避免死鎖—P73例2-3假定系統(tǒng)中有五個進程{P0、P1、P2、P3、P4}和三種類型資源{A、B、C}，每一種資源的數量分別為10、5、7。各進程的最大需求、T0時刻資源分配情況如下所示。

Max AllocationAvailable ABC ABC ABC

P0753 010P1322200P2 902 302 P3222 211 P4433 002 試問：①T0時刻是否安全？②P1請求資源Request1(1,0,2)是否允許？銀行家算法解-1T0時刻是否安全？從表中可找出一個序列(P1、

P3、P4、

P2、

P0）使各進程順序地一個個地執(zhí)行完成。

Max AllocationNeed WorkWork(Available)+AllocationABCABCABCABC ABC P0753010743=<1047⑤1057 P1322200 122=<332①532 P2 902302 600=<745④1047 P3 222211 011=<532②743 P4 433002 431=<743③745

安全序列為{P1、P3、P4、P2、P0}，T0時刻系統(tǒng)是安全的?？赡苡袔讉€安全序列，只要找出一個安全序列就可以。銀行家算法解-2P1請求資源Request1(1,0,2)可否允許？Request1(1,0,2)≤Need1(1,2,2)，P1請求在最大需求范圍內。Request1(1,0,2)≤Available(3,3,2)，可用資源可滿足P1請求需要。試探把要求的資源分配給進程P1并修改有關數據結構的數值：Available=Available(3，3，2)－Request1(1,0,2)=Available(2,3,0)；Need1=Need1(1,2,2)－Request1(1,0,2)=Need1(0,2,0)；Allocation1=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；利用安全性算法檢查試探將資源分配后狀態(tài)的安全性如下：銀行家算法解-3

MaxAllocationNeed WorkWork(Available)+AllocationABCABCABCABCABC P0753010 743=<1047⑤ 1057 P1322302 020=<230

① 532 P2 902302 600=<745④ 1047 P3 222211 011=<532②743 P4 433002 431=<743③745

因為先分配資源給P1進程符合按安全序列{P1、P3、P4、P2、P0}分配資源，所以試探將資源分配給進程P1后的狀態(tài)是安全的，可將資源分配給進程P1。P102問答題117．試描述避免死鎖的銀行家算法，若系統(tǒng)運行中出現(xiàn)下述資源分配情況進程ALLOCATIONNEEDAVAILABLEABCDABCDABCDP0003200121622P110001750P213542356P303320652P400140656問該系統(tǒng)是否安全？如果進程P2此時提出資源申請（1，2，2，2），系統(tǒng)能否將資源分配給它？解：系統(tǒng)是否安全？找到一個安全序列：P0、P3、P4、P1、P2，因此系統(tǒng)是安全的。

進程WORKNEEDALLOCATIONWORK+AllocationABCDABCDABCDABCDP01622001200321654P1199101750100029910P229910235613543121414P31654065203321986P419860656001419910如果進程P2此時提出資源申請（1，2，2，2），系統(tǒng)能否將資源分配給它？進程P2此時提出資源申請（1，2，2，2），按照銀行家算法進行檢查，Request(1,2,2,2)≤Need(2,3,5,6),且Request(1,2,2,2)≤Available(1,6,2,2),假定先將資源分配給它，重新列出如下表：從表中可以看出，已經不存在安全序列了，所以系統(tǒng)不能將資源分配給它，否則系統(tǒng)會進入不穩(wěn)定狀態(tài)。進程WORKNEEDALLOCATIONWORK+AllocationABCDABCDABCDABCDP0040000120032

P1

17501000

P2

23562576

P3

06520332

P4

06560014

(3)分頁存儲管理系統(tǒng)邏輯地址到物理地址地址變換的計算(P114例3-1)某系統(tǒng)采用頁式存儲器管理,頁長為1K(1024)字,主存大小為10K,其中0塊和1塊為操作系統(tǒng)占用,該作業(yè)分頁后分別裝入到主存的2,4,5塊中去,當前正在運行該作業(yè)。求邏輯地址2500所對應的物理地址為多少？

分頁存儲管理邏輯地址到物理地址地址變換的計算解(1)十進制－－邏輯地址2500頁號=邏輯地址/頁大小=2500/1024=2頁內地址=邏輯地址mod頁大小=2500mod1024=452查頁表頁號2塊號5物理地址=塊號*頁大小+頁內地址=5*1024+452=5572(2)十六進制－－邏輯地址09C4H1KB1024400H∵C00H＞09C4H＞800H頁號22KB2048800H頁內地址＝邏輯地址－該頁頭地址3KB3072C00H＝09C4H－800H＝1C4H4KB40961000H查頁表頁號2塊號55KB51201400H物理地址＝該塊頭地址+頁內地址6KB61441800H

=

1400H+1C4H=15C4HP150選擇題14某虛擬存貯器的用戶編程空間共32個頁面，每頁1KB，主存為16KB。假定某時刻用戶頁表中已調入主存的頁面的虛擬頁號和物理頁表對照表為表一，則下表中與虛擬地址相對應的物理地址為表二（如果主存找不到，即為該頁失效）。虛擬存貯存的功能是由﹎﹎C﹎﹎完成的。在虛擬存貯系統(tǒng)中，采用﹎﹎D﹎﹎提高﹎﹎E﹎﹎的速度。表一虛頁號物理頁號 051102487 表二虛地址 物理地址 0A5C（H）﹎﹎A﹎﹎ 1A5C（H）﹎﹎B﹎﹎ 例題-1供選擇的答案：A，B：①頁失效②1E5C（H）③2A5C（H）④165C（H）⑤125C（H）⑥1A5C（H）C：①硬件②軟件③軟、硬件結合D：①高速輔助存貯器②高速光盤存貯器③快速通道④高速緩沖存貯器E：①連接編輯②虛地址分配③動態(tài)地址翻譯④動態(tài)連接A---(5)B---(1)C---(3)D---(4)E---(3)例題-2解：每頁大小1KB，用16進制表示為400H，由虛地址通過直接映象的地址轉換成物理地址步驟如下：將虛地址分離成頁號p和頁內地址d：頁號p＝（虛地址／頁大?。┤≌剑?A5CH/400H）取整＝2頁內地址d＝虛地址－頁號p×每頁大?。?A5C(H)－2×400(H)＝25C(H)根據頁號查頁表，由頁號p＝2查頁表得物理頁號為4將物理頁號和頁內地址構成物理地址＝物理頁號×頁大?。搩鹊刂罚?×400(H)＋25C(H)＝125C(H)同理虛擬地址1A5CH分離成頁號P＝6和頁內位移15CH.查頁表知該頁不在內存，頁失效產生缺頁中斷調入內存。(4)分頁存儲管理系統(tǒng)CPU存取一個數據的平均時間計算（P115例3-2）一個分頁系統(tǒng)，檢索聯(lián)想存儲器的時間為20ns，訪問內存的時間為100ns，訪問聯(lián)想存儲器的的命中率為90%。則CPU存取一個數據的平均時間為多少？分頁存儲管理系統(tǒng)CPU存取一個數據的平均時間計算解快表命中時CPU存取一個數據的時間為T1＝檢索快表時間＋訪問內存數據時間＝20＋100＝120ns，快表不命中時CPU存取一個數據的時間為T2＝檢索快表時間＋檢索內存中的頁表時間＋訪問內存數據時間＝20＋100＋100＝220ns，則CPU存取一個數據的平均時間為T=命中率*T1+（1－命中率）*T2=0.90*120+0.10*220=130ns，所以訪問時間只增加30%。(5)頁面置換算法（P155問答題12）在一個請求分頁系統(tǒng)中，假如一個作業(yè)的頁面訪問順序為4，3，2，1，4，3，5，4，3，2，l，5，當分配給該作業(yè)的物理塊數M為3時，當分別用先進先出（FIFO）調度算法和最近最久未用（LRU）調度算法時，作業(yè)執(zhí)行過程中會產生多少次缺頁中斷？寫出頁面調度過程。FIFO置換算法解：頁面走向432143543215物理塊432143555211

43214333522

4321444355

缺頁中斷√√√√√√√

√√

(表中物理塊的頁號按調入內存先后次序排序)用FIFO置換算法產生缺頁次數9次。FIFO置換算法解：頁面走向432143543215物*

理塊44*411*15555*5*5

*33*34*4*4*4*4222

*2223333*311

缺頁中斷√√√√√√√

√√

(設置一個循環(huán)替換指針)用FIFO置換算法產生缺頁次數9次。LRU置換算法解：訪問頁序列432143543215

物理塊432143543215

43214354321

4321435432

缺頁中斷√√√√√√√

√√√(表中物理塊的頁號按訪問先后次序排序)用LRU置換算法產生缺頁次數10次。(6)文件系統(tǒng)性能計算（P2075.2.5實例）一個文件系統(tǒng)中有一個20MB大文件和一個20KB小文件,當分別采用二級索引和UNIXSytemV分配方案時(每塊大小為4096B,每塊地址用4B表示)，問:1.各文件系統(tǒng)管理的最大的文件是多少?2.每種方案對大、小二文件各需要多少專用塊來記錄文件的物理地址(說明各塊的用途)?3．如需要讀大文件前面第5.5KB和后面（16M＋5.5KB）信息，則每個方案各需要多少次盤I/O操作?索引分配文件系統(tǒng)管理的最大的文件由于盤塊大小為4KB，每個地址用4B表示（索引表目大?。粋€盤塊可存索引表目數為N＝盤塊大小/索引表目大小=4KB/4B=1K二級索引可管理的最大文件容量為盤塊大小×N×N=4KB×1K×1K＝4GB三級索引可管理的最大文件容量為盤塊大小×N×N×N=4KB×1K×1K×1K＝4TB

UNIX文件系統(tǒng)管理的最大的文件由于盤塊大小為4KB，每個地址用4B表示（索引表目大小），一個盤塊可存索引表目數為N＝盤塊大小/索引表目大小=4KB/4B=1KUNIX混合分配可管理的最大文件為：盤塊大小×(10+N+N×N+N×N×N)=4KB×(10+1K+1K×1K+1K×1K×1K)=40KB＋4MB+4GB＋4TB二級索引分配文件系統(tǒng)專用物理塊:一個盤塊可存索引表目數為N＝盤塊大小/索引表目大小=4KB/4B=1K對大小文件都固定要用二級索引，對20KB小文件，文件有5塊物理塊，需要5個索引表目。用一塊作二級索引塊，另用一塊作主索引塊，共用二塊專用物理塊作索引塊，對于20MB大文件，文件有5K塊物理塊，需要5K個索引表目。用5塊作第二級索引塊，另用一塊作主索引塊，共用六塊專用物理塊作索引塊。UNIX文件系統(tǒng)專用物理塊:對20KB小文件只需在文件控制塊FCB的i_addr[13]中使用前5個表目存放文件的物理塊號，不需專用物理塊。對20MB大文件，F(xiàn)CB的i_addr[13]中使用前10個表目存放大文件前10塊物理塊塊號，用一級索引塊一塊保存大文件接著的1K塊塊號，還要用二級索引存大文件以后的(4K-10)塊塊號，用4塊作第二級索引塊，另用一塊作主索引塊?？偣惨残枰?塊專用物理塊來存放文件物理地址。二級索引分配文件系統(tǒng)讀盤次數:二級索引：為讀大文件前面和后面信息的操作相同，首先進行一次盤I／O讀第一級索引塊，（然后根據它的相對邏輯塊號計算應該讀第二級索引的那塊，第一級索引塊表目號=相對邏輯塊號／1K，對文件前面信息1／1K＝0，對文件后面信息4097／1K＝4，）第二次根據第一級索引塊的相應表目內容又化一次盤I／O讀第二級索引塊，得到信息所在塊塊號，再化一次盤I／O讀出信息所在盤塊，這樣讀取大文件前面或后面信息都只需要3次盤I／O操作。UNIX文件系統(tǒng)讀盤次數:為讀文件地址<40KB的信息，先根據它的相對邏輯塊號，在內存文件控制塊FCB的i_addr[13]第0－9個表目中讀取信息所在塊塊號，而只化費一次盤I／O操作即可讀出該塊信息。為讀（40KB+4MB）＞文件地址≥40KB的信息，先根據i_addr[10]讀一級索引塊，以得到信息所在塊塊號，最后化一次盤I／O讀出信息所在盤塊，這樣總共需要2次盤I／O操作才能讀出文件后面的信息。為讀（40KB+4MB+4GB）＞文件地址≥（40KB+4MB）的信息，先根據i_addr[11]內容化一次盤I／O操作讀出第一級索引塊，再計算信息所在塊的索引塊號在第一級索引塊的表目號為（塊號-9-1024）／1024，根據第一級索引塊表目內容再化費一次盤I／O操作，讀出第二級索引塊，就可以得到信息所在塊塊號，最后化一次盤I／O讀出信息所在盤塊，這樣總共需要3次盤I／O操作才能讀出文件后面的信息。UNIX文件系統(tǒng)讀盤次數－1為讀大文件前面5.5KB信息，先根據它的相對邏輯塊號，在內存文件控制塊FCB的i_addr[13]第二個表目中讀取信息所在塊塊號，而只化費一次盤I／O操作即可讀出該塊信息。為讀大文件后在（16MB＋5。5KB）信息，先根據它的相對邏輯塊號判斷它是在UNIX二級索引管理范圍，先根據i_addr[11]內容化一次盤I／O操作讀出第一級索引塊，再計算信息所在塊的索引塊號在第一級索引塊的表目號為（4097-9-1024）／1024＝3，根據第一級索引塊第3個表目內容再化費一次盤I／O操作，讀出第二級索引塊，就可以得到信息所在塊塊號，最后化一次盤I／O讀出信息所在盤塊，這樣總共需要3次盤I／O操作才能讀出文件后面的信息。P260選擇題13、143．一個文件系統(tǒng)中有一個2MB文件,當分別采用連續(xù)、鏈接、二級索引和UNIXSytemV分配方案時(每塊大小為2048B,每塊地址用4B表示)，問:①.各文件系統(tǒng)管理的最大的文件是多少?（﹎A﹎、﹎B﹎、﹎D﹎、﹎E﹎）②.每種方案對大、小二文件各需要多少專用塊來記錄文件的物理地址?（﹎F﹎、﹎G﹎、﹎I﹎、﹎J﹎）③如需要讀文件第一頁信息，則每個方案各需要多少次盤I/O操作（包括讀信息塊盤I/O操作）?（﹎K﹎、﹎L﹎、﹎N﹎、﹎O﹎）④如需要讀文件最后一頁信息，則每個方案各需要多少次盤I/O操作（包括讀信息塊盤I/O操作）?（﹎P﹎、﹎Q﹎、﹎S﹎、﹎T﹎）習題-1A、B、C、D、E：(1)整個磁盤文件區(qū)；（2）4G；（3）2G；（4）1G；（5）0.5G；（6）40KB＋4MB+4GB＋4TB；（7）；20KB＋2MB+2GB＋2TB；（8）20KB+1MB+0.5G+0.25T；（9）10KB＋1MB+1GB＋1TB；（10）5KB＋0.5MB+0.5GB＋0.5TB；(11)不得而知；F、G、H、I、J、K、L、M、N、O、P、Q、R、S、T：（1）1；（2）2；（3）3；（4）4；（5）0；(6)以上都不是；解：-1一個盤塊可存索引表目數為N＝盤塊大小/索引表目大小=2KB/4B=0.5K=512二級索引可管理的最大文件容量為盤塊大小×N×N=2KB×0.5K×0.5K＝0.5GB=512MB三級索引可管理的最大文件容量為盤塊大小×N×N×N=2KB×0.5K×0.5K×0.5K＝0.25TB=256GBUNIX混合分配可管理的最大文件為：盤塊大小×(10+N+N×N+N×N×N)=4KB×(10+0.5K+0.5K×0.5K+0.5K×0.5K×0.5K)=20KB＋1MB+0.5GB＋0.25TB解：-2對于2MB大文件，文件有2MB/2KB=1K塊物理塊。二級索引需要1K個索引表目，一個盤塊可存索引表目數為512，用2塊作第二級索引塊，另用一塊作主索引塊，共用3塊專用物理塊作索引塊。對UNIX，F(xiàn)CB的i_addr[13]中使用前10個表目存放大文件前10塊物理塊塊號，用一級索引塊一塊保存大文件接著的0.5K塊塊號，還要用二級索引存大文件以后的(0.5K-10)塊塊號，用1塊作第二級索引塊，另用一塊作主索引塊?？偣惨残枰?塊專用物理塊來存放文件物理地址。（三）編程填空題本書的重點—進程本書的難度--利用信號量機制實現(xiàn)進程互斥、同步（P1022.8.5問答題13）有三個共行進程P、Q和R以及一對供存數據的緩沖BufI和BufO，P進程把數據輸入BufI，R進程輸出BufO中的數據。Q地把BufI中的數據變換后送入BufO，在上述假定之下,使三個進程實現(xiàn)最大并行性。試在下述類PASCAL程序中虛線位置分別填上信號量、信號量初值和P、V操作實現(xiàn)三個進程正確的并發(fā)執(zhí)行。

P

Q

BufIBufOR編程填空題-1Programito;varBufI,BufO:buffer;(信號量)﹎fulli,emptyi,﹎﹎﹎﹎﹎﹎:SEMAPHORE:=(信號量初值)﹎0,1﹎﹎﹎﹎﹎﹎﹎；beginparbeginP:beginrepeatinputfromIO;﹎﹎P(emptyi)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎AddtoBufI;﹎﹎V(fulli)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎untilfalse

end;

編程填空題-2

Q:beginrepeat﹎﹎P(fulli)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎RemovefromBufI;﹎﹎V(emptyi)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎transform;﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎AddtoBufO;﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎untilfalseend;編程填空題-3R:beginrepeat﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎RemovefromBufO;﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎Output...;untilfalseend;parendend

習題解-8Programito;varBufI,BufO:buffer;(信號量)﹎emptyI,fullI,emptyO,fullO:SEMAPHORE:=(信號量初值)﹎1,0,1,0﹎；beginparbeginP:beginrepeatinputfromIO;﹎﹎﹎P(emptyI)﹎﹎﹎﹎﹎﹎﹎AddtoBufI;﹎﹎﹎V(fullI)﹎﹎﹎﹎﹎﹎﹎untilfalse

end;

習題解-9

Q:beginrepeat﹎﹎﹎﹎P(fullI)﹎﹎﹎﹎﹎﹎﹎RemovefromBufI;﹎﹎﹎﹎V(emptyI)﹎﹎﹎﹎﹎﹎trans