1、題型：填空，選擇，簡答，算法（進程同步，銀行家，調(diào)度，頁面置換算法，動態(tài)分區(qū)分配回收算法）第一章1什么是操作系統(tǒng)？操作系統(tǒng)在計算機系統(tǒng)中的位置、作用。2操作系統(tǒng)的類型，各自的特點及區(qū)別。3操作系統(tǒng)的特征：并發(fā)、共享、虛擬、異步4操作系統(tǒng)發(fā)展過程脫機輸入輸出技術(shù) 批處理 多道程序設計技術(shù)，概念、特點，好處 分時系統(tǒng)第二章1程序及其執(zhí)行：程序并發(fā)執(zhí)行的條件2進程定義、進程的組成，為什么說PCB是進程存在的唯一標志？進程和程序的區(qū)別與聯(lián)系。PCB的組織方式。3進程的三種基本狀態(tài)及轉(zhuǎn)換4什么是掛起？為什么引入掛起？具有掛起狀態(tài)的進程狀態(tài)及轉(zhuǎn)換原因5進程的控制：概念，實現(xiàn)，基本的進程控制的功能第三章1同

2、步、互斥概念2臨界資源、臨界區(qū)：概念，如何實現(xiàn)臨界區(qū)的互斥訪問。 臨界區(qū)互斥四條準則：空閑讓進、忙則等待、有限等待、讓權(quán)等待。3. 互斥的加鎖實現(xiàn)4信號量 概念 信號量的P、V操作：功能，定義 信號量的應用：描述前趨圖、實現(xiàn)互斥、同步、生產(chǎn)者消費者問題，讀者寫者問題。5進程通信： 直接通信方式的基本思想、過程-消息緩沖通信第四章 調(diào)度與死鎖1調(diào)度類型及模型；進程調(diào)度的方式、時機2調(diào)度算法3死鎖問題 概念，原因，必要條件，預防及避免方法第五章1編譯、鏈接、裝入、重定位 （概念及如何實現(xiàn)）2連續(xù)分配單一連續(xù)、固定、動態(tài)分區(qū)分配 各自的實現(xiàn)方式。內(nèi)存的分配、回收算法3分頁分頁式系統(tǒng)的基本原理、地址變

3、換過程（基本的和具有快表的）4分段引入的原因。分段的原理。分段共享的實現(xiàn)方法。5分段與分頁區(qū)別與聯(lián)系6段頁式存儲的基本原理第六章 虛擬存儲器概念1虛擬存儲器的概念、實現(xiàn)原理、特征2請求式分頁式系統(tǒng)頁表的變化 地址變換過程 頁面置換算法填空題：1進程從就緒到運行狀態(tài)的轉(zhuǎn)換由 程序完成；從運行到就緒狀態(tài)的轉(zhuǎn)換的 主要原因是 。2操作系統(tǒng)的三種基本類型是 、 和 。3程序可并發(fā)執(zhí)行的條件是 。4從結(jié)構(gòu)上講，進程由 、 和 組成。 5同步機制應遵循的準則是 、 、 、 。 6產(chǎn)生死鎖的四個必要條件是 、 、 、和 。7在沒有快表的分頁存儲管理系統(tǒng)中，取一條指令（或操作數(shù)）需訪問兩次內(nèi)存的原因是 。8在

4、頁式管理系統(tǒng)中，地址空間是 維的，而在段式管理系統(tǒng)中，地址空間是 維的。9操作系統(tǒng)的基本特征是 、 、 。10從用戶的源程序進入系統(tǒng)到變成內(nèi)存可執(zhí)行程序，所經(jīng)歷的主要處理階段有_，_，和_。11靜態(tài)重定位在_時進行，而動態(tài)重定位在_時進行。 12虛擬存儲器所具有的基本特征是_，_，_和 _。 13一般說來，用戶程序中所使用的地址是_,而內(nèi)存中各存儲單元的地址是_。14I/O系統(tǒng)的結(jié)構(gòu)分為兩類： 和 。15I/O控制方式的發(fā)展經(jīng)歷了四個階段，分別是 、 、 、和 。答案：1調(diào)度、時間片完2批處理系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)3Bernstein條件4程序段、數(shù)據(jù)段、進程控制塊 5空閑讓進、忙則等待、有

5、限等待、讓權(quán)等待 6互斥條件、請求和保持條件、不可剝奪條件、環(huán)路等待條件7頁表在內(nèi)存8、一、二9并發(fā)、共享、虛擬、異步10編譯、鏈接、裝入11裝入、運行12離散性、多次性、對換性、虛擬性13邏輯地址、物理地址 14微型機I/O系統(tǒng) 、主機I/O系統(tǒng) 15程序I/O方式、中斷驅(qū)動I/O控制方式、直接存儲器訪問DMA控制方式、I/O通道控制方式選擇題一：1 操作系統(tǒng)的主要功能是管理計算機系統(tǒng)中的 。A程序 B數(shù)據(jù) C文件 D資源2 產(chǎn)生死鎖的基本原因是 和進程推進順序非法。 A資源分配不當 B系統(tǒng)資源不足 C作業(yè)調(diào)度不當 D進程調(diào)度不當3 在操作系統(tǒng)中， 是競爭和分配計算機系統(tǒng)資源的基本單位。A程

6、序 B進程 C作業(yè) D用戶4 動態(tài)重定位是在作業(yè)的 中進行的。 A編譯過程 B裝入過程 C連接過程 D執(zhí)行過程5 實時系統(tǒng)中的進程調(diào)度，通常采用 算法。 A先來先服務 B時間片輪轉(zhuǎn) C搶占式的優(yōu)先級調(diào)度 D短作業(yè)優(yōu)先 6若信號量的初值為3，當前值為-2，則表示有 個等待進程。 A2 B3 C4 D5 7死鎖的避免是根據(jù) 采取措施實現(xiàn)的。 A配置足夠的系統(tǒng)資源 B使進程的推進順序合理 C破環(huán)死鎖的四個必要條件之一 D防止系統(tǒng)進入不安全狀態(tài)8設有3個作業(yè)，其運行時間分別為2小時，5小時，3小時，假定它們同時到達，并在同一臺處理機上以單道方式運行，則平均周轉(zhuǎn)時間最小的執(zhí)行順序是 。 AJ1,J2,J

7、3 BJ3,J2,J1 CJ2,J1,J3 DJ1,J3,J2 9最佳適應算法的空白區(qū)是 。 A按大小遞減順序排列 B按大小遞增順序排列 C按地址由小到大排列 D按地址由大到小排列10分頁式虛擬存儲管理系統(tǒng)中，頁面的大小與可能產(chǎn)生的缺頁中斷次數(shù) 。 A成正比 B成反比 C無關(guān) D成固定比值選擇題一答案：1D 2B 3B 4D 5C 6A 7D 8D 9B 10C 選擇題二：1操作系統(tǒng)核心部分的主要特點是 。A、一個程序模塊 B、常駐內(nèi)存 C、有頭有尾的程序 D、串行執(zhí)行2可重定位內(nèi)存的分區(qū)分配目的為 。A、解決碎片問題 B、便于多作業(yè)共享內(nèi)存 C、回收空白區(qū)方便 D、便于用戶干預3邏輯地址就是

8、 。A、用戶地址 B、相對地址 C、物理地址 D、絕對地址4原語是 。A、一條機器指令 B、若干條機器指令組成C、一條特定指令 D、中途能打斷的指令5進程和程序的一個本質(zhì)區(qū)別是 。A 前者為動態(tài)的，后者為靜態(tài)的； B 前者存儲在內(nèi)存，后者存儲在外存；C 前者在一個文件中，后者在多個文件中；D 前者分時使用CPU,后者獨占CPU。6某進程在運行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時該進程的狀態(tài)將 。A從就緒變?yōu)檫\行； B從運行變?yōu)榫途w；C從運行變?yōu)樽枞?D從阻塞變?yōu)榫途w7進程控制塊是描述進程狀態(tài)和特性的數(shù)據(jù)結(jié)構(gòu)，一個進程 。A可以有多個進程控制塊 B可以和其他進程共用一個進程控制塊；C可以沒有進

9、程控制塊； D只能有惟一的進程控制塊。8在一般操作系統(tǒng)中必不可少的調(diào)度是 。A高級調(diào)度； B中級調(diào)度； C作業(yè)調(diào)度； D進程調(diào)度。9把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存的物理地址的過程稱作 。A編譯； B連接； C運行； D重定位。10文件目錄的主要作用是 。A、按名存取 B、提高速度 C、節(jié)省空間 D、提高外存利用率11UNIX操作系統(tǒng)是著名的 。A多道批處理系統(tǒng)； B分時系統(tǒng)； C實時系統(tǒng)； D分布式系統(tǒng)12在運行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時該進程的狀態(tài)將 。A從就緒變?yōu)檫\行； B從運行變?yōu)榫途w；C從運行變?yōu)樽枞?D從阻塞變?yōu)榫途w選擇題二答案：1B 2A 3B 4B 5A 6C 7D 8D 9D

10、 10A 11. B 12C選擇題三：1下列進程狀態(tài)的轉(zhuǎn)換中，哪一個是不正確的（ ）。A.就緒®運行 B.運行®就緒C.就緒®阻塞 D.阻塞®就緒2某進程由于需要從磁盤上讀入數(shù)據(jù)而處于阻塞狀態(tài)。當系統(tǒng)完成了所需的讀盤操作后，此時該進程的狀態(tài)將（ ）。A從就緒變?yōu)檫\行 B從運行變?yōu)榫途wC從運行變?yōu)樽枞?D從阻塞變?yōu)榫途w3若P、V操作的信號量S初值為2，當前值為-1，則表示有（ ）個等待進程。A0個 B1個 C2個 D3個4把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存的物理地址的過程稱作（ ）。A編譯 B連接 C運行 D重定位5在分頁存儲管理系統(tǒng)中，從頁號到物理塊號的地址映射是通過

11、（ ）實現(xiàn)的。A段表 B頁表 CPCB DJCB6在以下存貯管理方案中，不適用于多道程序設計系統(tǒng)的是( )。A.單用戶連續(xù)分配 B.固定式分區(qū)分配C.可變式分區(qū)分配 D.頁式存貯管理7在可變式分區(qū)分配方案中，某一作業(yè)完成后，系統(tǒng)收回其主存空間，并與相鄰空閑區(qū)合并，為此需修改空閑區(qū)表，造成空閑區(qū)數(shù)減1的情況是( )。A. 無上鄰空閑區(qū)，也無下鄰空閑區(qū) B. 有上鄰空閑區(qū)，但無下鄰空閑區(qū)C. 有下鄰空閑區(qū)，但無上鄰空閑區(qū)D. 有上鄰空閑區(qū)，也有下鄰空閑區(qū)8在分段管理中, ( )。A 以段為單位分配, 每段是一個連續(xù)存儲區(qū)B 段與段之間必定不連續(xù)C 段與段之間必定連續(xù)D每段是等長的9消息緩沖通信是利

12、用（ ）為基礎來實現(xiàn)進程間的數(shù)據(jù)交換。A文件系統(tǒng) B內(nèi)存緩沖區(qū) C高速緩沖存儲器 D硬件10采用最佳適應分配算法時，應將空閑區(qū)按（ ）順序進行連接。A地址遞增 B由小到大 C地址遞減 D由大到小選擇題三答案：12345678910CDBDBADABB一、解答題：1 什么是操作系統(tǒng)？它有什么基本特征？答：操作系統(tǒng)是為了達到方便用戶和提高資源利用率的目的而設計的，控制和管理計算機硬件和軟件資源，合理的組織計算機工作流程的程序的集合，它具有并發(fā)、共享、虛擬、異步性四個基本特征。2（1）描述進程的三種基本狀態(tài)，盡可能清楚地解釋處于不同狀態(tài)的進程在性質(zhì)上的區(qū)別。答：進程的三個基本狀態(tài)有：、就緒狀態(tài)：是指

13、進程已分配到除CPU以外的所有必要的資源，只要能再獲得處理機，便可立即執(zhí)行。、執(zhí)行狀態(tài)：指進程已獲得處理機，其程序正在執(zhí)行。、阻塞狀態(tài)：進程因發(fā)生某事件（如請求I/O、申請緩沖空間等）而暫停執(zhí)行時的狀態(tài)。（2）畫出進程狀態(tài)變化圖，說明進程怎樣從一個狀態(tài)轉(zhuǎn)換到下一個狀態(tài)。答：進程基本狀態(tài)轉(zhuǎn)換圖如下：就緒執(zhí)行狀態(tài)：處于就緒狀態(tài)的進程，當進程調(diào)度程序為之分配了處理機后，該進程便由就緒狀態(tài)變?yōu)閳?zhí)行狀態(tài)。執(zhí)行阻塞狀態(tài)：正在執(zhí)行的進程因發(fā)生某事件而無法執(zhí)行。例如，進程請求訪問臨界資源，而該資源正被其它進程訪問，則請求該資源的進程將由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)。執(zhí)行就緒狀態(tài)：正在執(zhí)行的進程，如因時間片用完而被暫

14、停執(zhí)行，該進程便由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。又如，在搶占調(diào)度方式中，一個優(yōu)先權(quán)高的進程到來后，可以搶占一個正在執(zhí)行優(yōu)先權(quán)低的進程的處理機，這時，該低優(yōu)先權(quán)進程也將由執(zhí)行狀態(tài)轉(zhuǎn)換為就緒狀態(tài)。3現(xiàn)代操作系統(tǒng)一般都提供多進程（或稱多任務）運行環(huán)境，回答以下問題：(1) 為支持多進程的并發(fā)執(zhí)行，系統(tǒng)必須建立哪些關(guān)于進程的數(shù)據(jù)結(jié)構(gòu)？(2) 為支持進程狀態(tài)的變遷，系統(tǒng)至少應提供哪些進程控制原語？(3) 執(zhí)行每一個進程控制原語時，進程狀態(tài)發(fā)生什么變化？相應的數(shù)據(jù)結(jié)構(gòu)發(fā)生什么變化？答：(1) 為支持多進程的并發(fā)執(zhí)行，系統(tǒng)為每個進程建立了一個數(shù)據(jù)結(jié)構(gòu)進程控制塊（PCB），用于進程的管理和控制。(2) 進程控制的主

15、要職責是對系統(tǒng)中的所有進程實施有效的管理，它具有創(chuàng)建新進程、撤銷已有進程、實現(xiàn)進程的狀態(tài)轉(zhuǎn)換等功能。在操作系統(tǒng)的內(nèi)核中，有一組程序?qū)ｉT用于完成對進程的控制，這些原語至少需要包括創(chuàng)建新進程原語、終止進程原語、阻塞進程原語、喚醒進程原語等操作。這些系統(tǒng)服務一般對用戶是開放的，也就是說用戶可以通過相應的接口來使用它們。(3) 進程創(chuàng)建原語：從PCB集合中申請一個空白PCB，將調(diào)用者參數(shù)、以及從執(zhí)行進程獲得的調(diào)用者內(nèi)部標識填入該PCB，設置記賬數(shù)據(jù)。置新進程為“就緒”狀態(tài)。 終止進程原語：用于終止完成任務的進程，收回其所占的資源。消去該進程的PCB。 阻塞原語：將進程從運行態(tài)變?yōu)樽枞麪顟B(tài)。進程被插入等

16、待事件的隊列中，同時修改PCB中相應的表項，如進程狀態(tài)和等待隊列指針等。 喚醒原語：將進程從阻塞態(tài)變?yōu)榫途w狀態(tài)。進程被從阻塞隊列中移出，插入到就緒隊列中，等待調(diào)度，同時修改PCB中相應的表項，如進程狀態(tài)等。4何謂臨界資源、臨界區(qū)？使用臨界資源的諸進程間如何實現(xiàn)對臨界區(qū)的互斥訪問？答：一次僅允許一個進程訪問的資源稱為臨界資源。訪問臨界資源的代碼段稱為臨界區(qū)。對臨界區(qū)必須互斥的訪問。具體實現(xiàn)時，可讓每個進程在進入臨界區(qū)之前，先提出申請，經(jīng)允許后方可進入（進入?yún)^(qū)），進程進入臨界區(qū)執(zhí)行完畢退出時，恢復臨界區(qū)的使用標志為未被訪問標志（退出區(qū)）。通常可采用專門的硬件指令或信號量機制對臨界區(qū)進行管理。使用信

17、號量機制是，可設置一個初值為1的互斥信號量，對每個進程的臨界區(qū)進行如下“改造”：P(mutex);臨界區(qū)V(mutex);即將進程的臨界區(qū)放置在P(mutex)和V(mutex)之間，就可以實現(xiàn)進程對其互斥訪問。2.說明作業(yè)調(diào)度、中級調(diào)度和進程調(diào)度分別完成什么工作，并分析下述問題應由哪一級調(diào)度程序負責。（1）在可獲得處理機時，應將它分給哪個就緒進程。（2）在短期繁重負載下，應將哪個進程暫時掛起。答：高級調(diào)度（作業(yè)調(diào)度）用于決定把外存上處于后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，并將它們創(chuàng)建進程，分配必要的資源，然后，再將新創(chuàng)建的進程排在就緒隊列上，準備執(zhí)行。低級調(diào)度（進程調(diào)度）：它覺得就緒隊列中的哪個進

18、程將獲得處理機，然后由分派程序執(zhí)行把處理機分配給該進程的操作。中級調(diào)度：存儲器管理中的對換功能。（1）進程調(diào)度。（2）中級調(diào)度。什么是虛擬存儲器？敘述實現(xiàn)虛擬存儲器的基本原理。答：虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)，是具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器管理。虛擬存儲器管理通過把主、輔存統(tǒng)一起來管理，給用戶造成一種仿佛系統(tǒng)內(nèi)具有巨大主存供用戶使用的假象。在頁式或段式或段頁式管理的基礎上，僅把作業(yè)的一部分頁或段放在主存中。頁表項或段表象中注明對應的頁或段是在主存還是在輔存，程序執(zhí)行時，當訪問的頁或段不在主存時，根據(jù)頁表項或段表項的指引，

19、從輔存將其調(diào)入內(nèi)存，如果這時已無可用的物理空間，則從主存淘汰若干頁或段。什么是動態(tài)鏈接？用何種內(nèi)存分配方法可以實現(xiàn)這種鏈接技術(shù)？答：動態(tài)鏈接是指當程序運行到需要調(diào)用某一模塊時，再去鏈接，對于未使用的模塊，就可以不必鏈接。采用段式內(nèi)存分配方法可以實現(xiàn)這種技術(shù)。5使用信號量的P、V操作可以實現(xiàn)并發(fā)進程間的互斥。請寫出P操作原語和V操作原語的定義？答：P操作功能是請求系統(tǒng)分配一個單位的資源，定義如下：信號量的值減1，即S=S-1；如果S0，則該進程繼續(xù)執(zhí)行；如果S0，則把該進程的狀態(tài)置為阻塞態(tài)，把相應的PCB連入該信號量隊列的末尾，并放棄處理機，進行等待（直至其它進程在S上執(zhí)行V操作，把它釋放出來為

20、止）。 V操作功能是釋放一個單位的資源，定義如下：S值加1，即S=S+1；如果S0，則該進程繼續(xù)運行； 如果S0，則釋放信號量隊列上的第一個PCB（即信號量指針項所指向的PCB）所對應的進程（把阻塞態(tài)改為就緒態(tài)），執(zhí)行V操作的進程繼續(xù)運行。6什么是死鎖？產(chǎn)生死鎖的四個必要條件是什么？答：所謂死鎖（Deadlock），是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。產(chǎn)生死鎖的四個必要條件是：互斥條件、請求和保持條件、不剝奪條件、環(huán)路等待條件。7簡述死鎖的預防與死鎖的避免的區(qū)別。答：死鎖的預防是系統(tǒng)預先確定一些資源分配策略，進程按規(guī)定申請資源，系統(tǒng)按預先規(guī)定的

21、策略進行分配，從而防止死鎖的發(fā)生。 而死鎖的避免是當進程提出資源申請時系統(tǒng)測試資源分配，僅當能確保系統(tǒng)安全時才把資源分配給進程，使系統(tǒng)一直處于安全狀態(tài)之中，從而避免死鎖。8解決生產(chǎn)者-消費者問題的算法中，若將P(empty)和P(mutex)的次序互換，或?qū)(full)和P(mutex)的次序互換,可能會產(chǎn)生死鎖。請問在什么情況下會產(chǎn)生死鎖？答：解決生產(chǎn)者-消費者問題的算法中，若將P(empty)和P(mutex)的次序互換，在緩沖區(qū)滿的情況下（empty=0,full=n），若生產(chǎn)者先提出申請，獲得對緩沖區(qū)的訪問權(quán)，但申請不到空緩沖塊，在empty處阻塞，這個時候若再來消費者進程，申請不到

22、對緩沖區(qū)的訪問權(quán)，在mutex處阻塞，這時會產(chǎn)生鎖死。將P(full)和P(mutex)的次序互換，在緩沖區(qū)空的情況下（empty=n,full=0），若消費者先提出申請，獲得對緩沖區(qū)的訪問權(quán)，但申請不到滿緩沖塊，在full處阻塞，這個時候若再來生產(chǎn)者進程，申請不到對緩沖區(qū)的訪問權(quán)，在mutex處阻塞，這時會產(chǎn)生鎖死。9消息緩沖通信技術(shù)是一種高級通信機制。請給出消息緩沖通信機制（有限緩沖）的基本工作原理。答：操作系統(tǒng)管理一個用于進程通信的緩沖池，其中的每個緩沖區(qū)單元可存放一條消息。欲發(fā)送消息時，發(fā)送者從中申請一個可用緩沖區(qū),直接將消息送入內(nèi)存公用消息緩沖池，并將它掛接在接收者進程的消息緩沖隊列

23、上，接收進程從消息緩沖隊列中取走消息，并釋放該緩沖區(qū)，每個進程均設置一條消息隊列，任何發(fā)送給該進程的消息均暫存在其消息隊列中。10(1)簡述處理機三級調(diào)度分別完成什么工作？(2)列舉引起進程調(diào)度的時機？(3)分析下述問題應由哪一級調(diào)度程序負責。Ø 在可獲得處理機時,應將它分給哪個就緒進程；Ø 在短期繁重負載下,應將哪個進程暫時掛起。答：(1) 高級調(diào)度：即作業(yè)調(diào)度，用于決定把外存上處于后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程，分配必要的資源，然后，再將新創(chuàng)建的進程排在就緒隊列上，準備執(zhí)行。 低級調(diào)度：即進程調(diào)度，它決定就緒隊列中的哪個進程將獲得處理機，然后由分派程序執(zhí)

24、行把處理機分配給該進程的操作。 中級調(diào)度：實際上就是存儲器管理中的對換功能。(2) 引起進程調(diào)度的時機有：l 正在執(zhí)行進程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行。l 執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行。l 在進程通信或同步過程中執(zhí)行了某種原語操作，如P操作、block原語、wakeup原語等。l 在可剝奪式調(diào)度中，有一個比當前進程優(yōu)先權(quán)更高的進程進入就緒隊列。l 在時間片輪轉(zhuǎn)法中，時間片用完。 (3) Ø 進程調(diào)度；Ø 中級調(diào)度11動態(tài)分區(qū)式管理的常用內(nèi)存分配算法有哪幾種？比較它們各自的優(yōu)缺點。答：(1)首次適應算法：描述算法(叢空閑分區(qū)的組織、如何找兩方面描述)缺點：

25、增加查找可用空閑分區(qū)開銷； 地址不斷劃分，致使留下許多難以利用的、很小的空閑分區(qū)。(2)循環(huán)首次適應算法：描述算法(2分)特點：減少查找開銷，空閑分區(qū)分布的更均勻，但會缺乏大的空閑分區(qū)。(3)最佳適應算法：描述算法(2分)缺點：劃分后剩余的空閑區(qū)最小。12在動態(tài)分區(qū)存儲管理方式中，回收內(nèi)存時，可能出現(xiàn)哪幾種情況？應怎樣處理這些情況？答：在動態(tài)分區(qū)存儲管理方式中，回收內(nèi)存時,系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈中找到相應的插入點，此時可能出現(xiàn)以下四種情況之一： （1）回收區(qū)與插入點的前一個分區(qū)F1相鄰接。此時應將回收區(qū)與插入點的前一分區(qū)合并，不再為回收分區(qū)分配新表項，而只需修改F1區(qū)的大小為兩者之和

26、； （2）回收分區(qū)與插入點的后一分區(qū)F2相鄰接。此時也將兩分區(qū)合并形成新的空閑區(qū)，但用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和；（3）回收區(qū)同時與插入點的前、后兩個分區(qū)鄰接。此時將三個分區(qū)合并，使用F1的首址，取消F2的表項； （4）回收區(qū)既不與F1鄰接，也不與F2鄰接。這時應為回收區(qū)單獨建立一新表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址，插入到空閑鏈中的適當位置。13什么是分頁？什么是分段？在存儲管理中，分頁與分段的主要區(qū)別是什么？分頁與分段兩種方法中，哪個更易于實 現(xiàn)共享,為什么？答：分頁是將一個進程的邏輯地址空間分成若干大小相等的部分，每一部分稱作頁面。內(nèi)存劃分成與頁面大小相等的物

27、理塊，進程的任何一頁可放入內(nèi)存的任何一個物理塊中。（2分） 分段是一組邏輯信息的集合，即一個作業(yè)中相對獨立的部分。多個段在內(nèi)存中占有離散的內(nèi)存單元，對每個段，在內(nèi)存占有一連續(xù)的內(nèi)存空間，其內(nèi)存的分配與回收同可變分區(qū)的內(nèi)存分配與回收辦法。（2分） 分頁與分段的主要區(qū)別是：（1） 頁是信息的物理單位。分頁僅僅是由于系統(tǒng)管理的需要，而不是用戶的需要；而段是信息的邏輯單位，它含有一組具有相對完整意義的信息，是出于用戶的需要。（2） 頁的大小固定且由系統(tǒng)確定，把邏輯地址劃分為頁號和頁內(nèi)地址兩部分的功能，由機器硬件實現(xiàn)；而段的長度卻不固定，或由編譯程序在對源程序進行編譯時根據(jù)信息的性質(zhì)來劃分。（3） 分頁

28、的作業(yè)地址空間是一維的，即單一的線性地址空間；而分段的作業(yè)地址空間則是二維的。對于分頁和分段來說，分段更容易實現(xiàn)共享。因為段是一組有一定意義的信息集合，且由于能實現(xiàn)分段的動態(tài)鏈接。 14說明在分段系統(tǒng)中，如何實現(xiàn)信息共享？要求圖示說明。答：對于分段系統(tǒng)，每個段都從0開始編址，并采用一段連續(xù)的地址空間，這樣在實現(xiàn)信息共享與保護時，只需在每個進程的段表中，為所要共享和保護的程序設置一個段表項，記錄共享的段在內(nèi)存的基址和段長。進程1和進程2共享editor的示意圖如下： 15何謂虛擬存儲器？為什么說請求頁式管理可以實現(xiàn)虛擬存儲器？答：虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)。具

29、體的說，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。請求頁式管理是在頁式管理的基本上，僅把作業(yè)的一部分頁放在主存中。頁表項中注明對應的頁是在主存還是在輔存，程序執(zhí)行時，當訪問的頁不在主存時，根據(jù)頁表項的指引，從輔存將其調(diào)入主存，如果這時已無可用的物理空間，則從主存淘汰若干頁。對于這種變化，用戶感覺不到，他會以為作業(yè)的所有部分都存在于主存，這樣可以讓更多的作業(yè)進入主存，提高系統(tǒng)的效率。16虛擬存儲器的基本特征是什么？虛擬存儲器的容量主要受到哪兩方面的限制？答：虛擬存儲器的基本特征是：離散分配，即不必占用連續(xù)的內(nèi)存空間；部分裝入，即每個作業(yè)不是全部一次性地裝入內(nèi)存

30、，而是只裝入一部分；多次對換，即所需的全部程序和數(shù)據(jù)要分成多次調(diào)入內(nèi)存虛擬擴充，即不是物理上而是邏輯上擴充了內(nèi)存容量；虛擬存儲器的容量主要受到指令中表示地址的字長和外存的容量的限制。17為實現(xiàn)請求分頁存儲管理，請求分頁系統(tǒng)中的每個頁表項應含有哪些內(nèi)容? 并說明每個數(shù)據(jù)項的作用。答：頁號： 狀態(tài)位：指出該頁是否已調(diào)入內(nèi)存； 物理塊號：若頁在內(nèi)存，指出該頁在內(nèi)存的物理塊號； 外存地址：若頁在外存，指出該頁在外存上的地址，供調(diào)入該頁時使用訪問字段：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考；修改位：表示該頁在調(diào)入內(nèi)存后是否被修改過。若為1，表明

31、修改過，淘汰時必須寫回輔存，否則不需要寫回。18簡述具有快表的頁式存儲管理系統(tǒng)的地址變換過程。答：CPU給出有效地址后，地址變換機構(gòu)將頁號與快表中的所有頁號進行比較，若有與此相匹配的頁號，則表示所訪問的頁在快表中，從中讀出物理塊號與頁內(nèi)地址相拼接，得到物理地址；若訪問的頁不在快表中，則要訪問在內(nèi)存中的頁表，從頁表項中讀出物理塊號與頁內(nèi)地址相拼接，得到物理地址，同時，還應將此頁表項寫入快表中，若此時快表已滿，則OS必須找到一個老的且已被認為不再需要的頁表項將它換出。注：具有快表的段式存儲管理系統(tǒng)的地址變換過程。具有快表的段頁式存儲管理系統(tǒng)的地址變換過程。具有快表的請求頁式存儲管理系統(tǒng)的地址變換過

32、程。與上題一樣重要，請自己考慮。19、產(chǎn)生死鎖的原因是什么？答：競爭非剝奪性資源； 進程推進順序不當。20、簡述信號量S的物理含義。答：信號量是對系統(tǒng)中資源及其組織情況的抽象，由一個記錄型(或結(jié)構(gòu)體類型)數(shù)據(jù)表示。它包含兩個數(shù)據(jù)項。第一個為value，表示可用資源數(shù)目：Svalue0時，表示有value個可用資源； Svalue0時，表示資源正好用完； Svalue0時，表示有-value個進程正在等待此類資源。第二個為L，為等待此類資源的進程PCB表鏈。21、什么叫物理地址？什么叫邏輯地址？什么叫地址映射？地址映射分哪幾類？答：物理地址是內(nèi)存中各存儲單元的編號，即存儲單元的真實地址，它是可識

33、別、可尋址并實際存在的。 用戶程序經(jīng)過編譯或匯編形成的目標代碼，通常采用相對地址形式，其首地址為零，其余指令中的地址都是相對首地址而定。這個相對地址就稱為邏輯地址。 為了保證CPU執(zhí)行程序指令時能正確訪問存儲單元，需要將用戶程序中的邏輯地址轉(zhuǎn)換成運行時可由機器直接尋址的物理地址，這一過程稱為地址映射或地址重定位。 地址映射可分為兩類：Ø 靜態(tài)地址映射在程序執(zhí)行之前進行的重定位，在程序裝入內(nèi)存時一次性完成指令中地址的修改。Ø 動態(tài)地址映射裝入主存的程序仍然保持原來的邏輯地址，由邏輯地址到物理地址的轉(zhuǎn)換在程序真正執(zhí)行時進行。22、試述段頁式存儲管理的基本思想答：段頁式存儲管理的

34、基本思想是：Ø 用頁式方法來分配和管理內(nèi)存空間，即把內(nèi)存劃分成若干大小相等的頁面；Ø 用段式方法對用戶程序按照其內(nèi)在的邏輯關(guān)系劃分成若干段；Ø 再按照劃分內(nèi)存頁面的大小，把每一段劃分成若干大小相等的頁面；Ø 用戶程序的邏輯地址由三部分組成：段號、頁號、頁內(nèi)地址Ø 內(nèi)存是以頁為基本單位分配給每個用戶程序的，在邏輯上相鄰的頁面內(nèi)存不一定相鄰。二、考慮有六個協(xié)作的任務：S1、S2、S3、S4、S5、S6，分別完成各自的工作，它們滿足下列條件： 任務S1和S2領先于任務S4，任務S3領先于任務S5，任務S4和S5領先于任務S6；請畫出六個協(xié)作任務合作的前趨圖，并用P、V操作實現(xiàn)，使得在任何可能的情況下它們均能正確工作。答：本題是典型的同步問題。即進程A執(zhí)行完后