(完整版)中國科大操作系統(tǒng)復(fù)習(xí)題解

1、第1章 操作系統(tǒng)引論1.什么是 馮?諾依曼計算機工作模型？馮?諾依曼計算機工作模型或存儲程序工作模型:1)存儲器用來容納程序和數(shù)據(jù)；2)程序由指令組成，并和數(shù)據(jù)一起存儲在計算機內(nèi)存中;3)指令按順序、轉(zhuǎn)跳和循環(huán)三種基本方式組織;4)機器一起動，就能按照程序指定的邏輯順序把指令從存儲器中讀出來逐條解釋執(zhí)行，動完成程序所描述的處理工作;5)指令指針(CS:IP)指示當(dāng)前執(zhí)行指令，執(zhí)行完成指針會自動調(diào)整到下一條指令6)當(dāng)前指令指針指向的內(nèi)存中程序，被認為擁有機器控制權(quán);7)任何計算機都擁有自己的一套基本指令系統(tǒng)，高級語言程序最終需經(jīng)專門的編譯程序， 翻譯為基本機器指令;2.簡述 OS 的定義、作用和

2、主要功能。1)定義：是計算機系統(tǒng)的一個系統(tǒng)軟件；a)是一些具有如下功能的程序模塊的集合；b)能有效地組織和管理計算機硬件和軟件資源c)能合理組織計算機的工作流程，控制程序的執(zhí)行；d)能透明地向用戶提供各種服務(wù)功能， 使用戶能夠靈活、 方便地使用計算機， 計算機系統(tǒng)能高效地運行。2)操作系統(tǒng)的作用a)作為計算機系統(tǒng)資源的管理者；b)作為用戶與計算機硬件系統(tǒng)之間的接口；c)用作擴充計算機硬件系統(tǒng)；3)操作系統(tǒng)的功能： 處理機管理(進程與線程管理)：主要任務(wù)是對內(nèi)存進行分配、保護和擴充；具體是：a)進程控制：負責(zé)進行的創(chuàng)建、撤銷和狀態(tài)轉(zhuǎn)換b)進程同步：對并發(fā)執(zhí)行的多進程進行協(xié)調(diào)c)進程通信：負責(zé)完成

3、進程間的信息交換d)進程調(diào)度：按一定的算法進行CPU分配存儲管理：主要任務(wù)是對內(nèi)存進行分配、保護和擴充；具體為：a)內(nèi)存分配：按一定的策略為每道程序分配內(nèi)存b)內(nèi)存保護：保證各程序在自己的內(nèi)存區(qū)域內(nèi)運行不受其它并發(fā)執(zhí)行程序影響。c)內(nèi)存擴充：為允許大型作業(yè)或多作業(yè)并發(fā)運行，必須借助虛擬存儲技術(shù)來獲得更大“虛擬”內(nèi)存設(shè)備管理：是OS中最龐雜、最瑣碎部分；具體為：a）設(shè)備分配：按一定原則對設(shè)備進行分配。為使設(shè)備能與主機并行工作，需大量采用 緩沖技術(shù)和虛擬技術(shù)b）設(shè)備傳輸控制：實現(xiàn)物理設(shè)備的I/O操作，包括啟動、中斷處理和結(jié)束處理等操作。 文件管理：OS中負責(zé)信息使整個管理部分稱為文件系統(tǒng)；a）文件

4、的存儲空間管理（分配、回收）b）目錄管理：目錄是為方便文件管理而采用的基本數(shù)據(jù)結(jié)構(gòu)，它能提供“按名存取” 功能。c）文件操作管理：實現(xiàn)文件的基本操作，包括打開、關(guān)閉、讀、寫等。d）文件保護：提供文件安全保護的有關(guān)功能和設(shè)施。3.比較：單道批處理 OS 多道批處理 OS 分時 OS 和實時 OS 的基本特征。單道批處理OS:單道批處理系統(tǒng)監(jiān)督程序駐留內(nèi)存；自動加載外部作業(yè)，實現(xiàn)系統(tǒng)的自動、不間斷連續(xù)運行 但當(dāng)當(dāng)前執(zhí)行程序有I/O服務(wù)請求時，CPU仍要空閑特征：自動性、順序性和單道性多道批處理OS多道批處理系統(tǒng)多道程序設(shè)計技術(shù)用戶提交作業(yè)先在外存排隊，然后由作業(yè)調(diào)度程序按一定的算法從隊列中選擇若干

5、 作業(yè)載入內(nèi)存，并允許它們并發(fā)（交替）執(zhí)行；引入多道程序設(shè)計技術(shù)后，可帶來如下的好處；提高系統(tǒng)（CPU內(nèi)存和I/O設(shè)備）的利用率；充分發(fā)揮CPU與外設(shè)并行工作的能力;提高系統(tǒng)的吞吐率；特征：多道性、無序性和調(diào)度性優(yōu)缺點及需要解決的問題分時OS:分時操作系統(tǒng)形成和發(fā)展的動力：實現(xiàn)人機交互；共享或充分利用主機；便于用戶上機分時OS實現(xiàn)要解決的關(guān)鍵問題：及時接受多路卡；每個終端配備可暫存用戶命令的緩沖區(qū)及時處理 所有用戶作業(yè)要直接進入內(nèi)存； 每個用戶（作業(yè)）應(yīng)在較短的時間內(nèi)得到響應(yīng)處理的“時間片”； 分時系統(tǒng)的實現(xiàn)方法單道分時處理系統(tǒng) 具有“前臺”和“后臺”的分時系統(tǒng) 支持多道程序設(shè)計的分時系統(tǒng)特征

6、 ：多路性、獨立性和交互性；實時OS：實時OS的引入目的（主要應(yīng)用領(lǐng)域）1）實時控制實時信息處理要求對信息進行及時處理2）實時任務(wù)的類型按是否有周期性劃分； 按截止時間要求嚴格與否劃分（硬、軟任務(wù)）；3）實時系統(tǒng)的基本特征具有多路性、獨立性、交互性、及時性和可靠性等特征.補充題： 試從交互性、 及時性和可靠性方面， 將分時系統(tǒng)與實時系統(tǒng)進行比較分時系統(tǒng)和實時系統(tǒng)在交互性、及時性和可靠性方面存在較大差別：（1）從交互性方面來看，分時系統(tǒng)的目的是滿足多用戶交互的血藥，因此，交互性是分時 系統(tǒng)的一個關(guān)鍵問題，用戶可以通過終端與系統(tǒng)進行人機對話。而實時系統(tǒng)中的交互性 僅限于訪問系統(tǒng)中的某些專用服務(wù)程序

7、，其交互性受到了限制。（2）從及時性方面來看，在分時系統(tǒng)中它指的是系統(tǒng)的響應(yīng)時間是以人能夠接受的等待時 間為標(biāo)準(zhǔn)的，一般為2-3秒；而在實時系統(tǒng)中則是以控制過程或信息處理中能夠接受的 延遲為準(zhǔn)，往往是秒級、百毫秒級甚至毫秒級或更低，是實時系統(tǒng)的關(guān)鍵因素之一。（3）從可靠性方面來看，在實時系統(tǒng)中的人任何差錯都可能帶來巨大的損失，為此，往往 需要采取多級容錯措施來保證系統(tǒng)和數(shù)據(jù)的安全可靠。分時系統(tǒng)也有可靠性要求但相對 較低。4.簡述目前研究/學(xué)習(xí) OS 的兩種主要觀點（虛擬觀點和資源管理觀點）。1）虛擬觀點：是對OS種由頂向下的俯視。裝有OS的計算機極大地擴展了原有計算機的功能。把包含由各種硬件、

8、復(fù)雜底層操作 細節(jié)隱藏起來，使得用戶的操作和使用，由復(fù)雜變得簡單，由低級操作變?yōu)楦呒壊僮鳎?把基本功能擴展為多種功能。在裸機上裝上OS后，對用戶來說好像是得到了一個擴展的，使用更方便的計算機。2）資源觀點：是目前對OS描述的主要觀點，是一種對OS功能位置由底向上的觀察的觀點。把資源分為軟、硬件資源，硬件資源又包括CPU主存、輸入輸出設(shè)備。相應(yīng)的OS就有處理機管理、內(nèi)存管理、設(shè)備管理，和針對軟信息資源一文件的磁盤管理/文件管理5.為什么說 OS 極大擴展了計算機的功能？裝有OS的計算機極大地擴展了原有計算機的功能，原因如下：OS把包含由各種硬件、復(fù)雜底層操作細節(jié)隱藏起來，使得用戶的操作和使用，由

9、復(fù)雜變得簡單，由低級操作變?yōu)楦呒壊僮?，把基本功能擴展為多種功能。在裸機上裝上OS后，對用戶來說好像是得到了一個擴展的，使用更方便的計算機。第2章進程的描述與控制1.針對：1）單任務(wù) OS 環(huán)境下程序順序執(zhí)行，2）多任務(wù) OS 環(huán)境下的多道程序并發(fā)執(zhí)行，試分析它們分別具有哪些特征？為什么？1）單任務(wù)OS環(huán)境下程序順序執(zhí)行：單任務(wù)環(huán)境下的“可執(zhí)行”程序未執(zhí)行前的程序是可執(zhí)行格式的二進制程序文件，通常被持久存儲在外存（磁盤）中；程序被加載到主存并獲得CPU控制權(quán)后，將按其中指令所規(guī)定的邏輯順序被依次執(zhí)行；邏輯順序結(jié)構(gòu)：順序、選擇、重復(fù)（循環(huán)）通?？刹捎没蛞肭膀?qū)圖節(jié)點+有向邊，來描述程序中不同單元或

10、程序段之間的關(guān)系；以實模式執(zhí)行，具有最大的權(quán)限，可存取控制所有計算機軟硬資源；程序執(zhí)行具有以下基本特點：順序性封閉性（結(jié)果）可再現(xiàn)性。2）多任務(wù)OS環(huán)境下的多道程序并發(fā)執(zhí)行：多道程序并發(fā)執(zhí)行情況示例i -本例中，程序片段S1與S2可并發(fā)執(zhí)行并發(fā)可有效提高系統(tǒng)的吞吐量 多道程序并發(fā)執(zhí)行的特征：間斷性（切換執(zhí)行）S2失去封閉性（共享系統(tǒng)的資源）卜結(jié)果不可再現(xiàn)性 為有效管理和調(diào)度多道并發(fā)執(zhí)行程序 須引入可完整描述每道執(zhí)行中程序的數(shù)據(jù)結(jié)構(gòu)，該思想逐步進化完善進程（process）概念。2.深入理解進程的概念，試說明進程的基本特征及現(xiàn)代OS中引入進程的意義。提示：進程是現(xiàn)代 OS 最重要的概念之一，是為

11、了能有效管理（正在被并 發(fā)執(zhí)行的）每道程序而必須引入的特別概念，或特別數(shù)據(jù)結(jié)構(gòu)。進程的基本特征：用戶空間是進程的一個最主要特征!獨立性： 每個進程具有自己相對獨立的地址空間，除非通過進程通信手段，否則不能相互影響 結(jié)構(gòu)性進程空間是結(jié)構(gòu)化的、分段組織的；動態(tài)性 是或包含可在其地址空間中活動的執(zhí)行體對象 并發(fā)性，也稱異步性在同一個計算機系統(tǒng)中允許同時存在多個進程，微觀上它們可能是交替執(zhí)行；但宏觀 上看，則似乎在同時獨立運行。操作系統(tǒng)引入進程的意義：進程是現(xiàn)代OS最重要的概念之一 進程的管理、切換及調(diào)度，與保護模式密切相關(guān)， 需要有保護模式知識，才能清晰 理解進程的實現(xiàn)機制和實現(xiàn)過程。執(zhí)行進程切換的

12、相關(guān)代碼，被統(tǒng)稱為OS的進程調(diào)度模塊1） 通常被運行在比 “進程”更高的層級上；2） 現(xiàn)代OS的調(diào)度代碼，通常不是一個集中的模塊， 而是由分散在內(nèi)核多個位置的 若干代碼片段構(gòu)成；3.在引入進程的OS中，進程與（二進制可執(zhí)行）程序這兩個概念的區(qū)別與聯(lián)系。 進程與程序的區(qū)別：程序是靜態(tài)的,是有序代碼的集合,是進程的定義和說明對應(yīng)著一個持久外存文件， 具有外存文件的性質(zhì)（創(chuàng)建/復(fù)制/刪除.）。進程是動態(tài)的、暫時的，是程序的一次執(zhí)行，通常不能在計算機之間遷移。 進程與程序的組成不同：進程組成包括代碼段、數(shù)據(jù)段和控制塊。 多進程實體可以同時存放在內(nèi)存中并發(fā)執(zhí)行，而程序不能正確并發(fā)執(zhí)行。 進程是一個能夠獨

13、立運行、 獨立分配資源的和獨立接受調(diào)度的基本單位。 而程序不能在 多道程序環(huán)境下獨立運行。進程與程序不是意義對應(yīng)的關(guān)系。進程與程序密切關(guān)聯(lián)：通過多次加載執(zhí)行， 一個程序可對應(yīng)多個進程； 通過調(diào)用關(guān)系， 一個進程可涉及多個程 序。4. 理解 PCB 數(shù)據(jù)結(jié)構(gòu)中的主要屬性域及作用。一個已被掛起的進程，它的PCB是否會被交換到外存？ PCB 被保存在系統(tǒng)空間可交換區(qū)、系統(tǒng)空間不可交換區(qū)，還是進程用戶空間？1）PCB數(shù)據(jù)結(jié)構(gòu)的主要屬性域及作用：PCB是操作系統(tǒng)內(nèi)核中一種數(shù)據(jù)結(jié)構(gòu)，主要表示進程狀態(tài)，是在系統(tǒng)空間不可交換區(qū)中。PCB主要內(nèi)容：進程描述信息：PID,NAME, USERID,PROCESS

14、GROUP處理器現(xiàn)場保護信息：CPU內(nèi)部各寄存器；進程控制信息：當(dāng)前狀態(tài)、優(yōu)先級、代碼執(zhí)行入口地址、程序外存地址、運行統(tǒng)計 信息（執(zhí)行時間、調(diào)度次數(shù)、頁面調(diào)度）；資源占用信息列表，打開資源對象句柄表；用于進程間同步與通信的相關(guān)信息字段；指向進程虛空間使用分配描述表指針（PCB-AddressSpace ）；（注意，因頁目錄/頁表占空間 較大，雖位于系統(tǒng)空間但不能安排在核心，即?PCB頁掛起進程頁表可能會被SWAP1U外存！）PCB的主要作用：與進程有關(guān)的信息被集中存儲在這個數(shù)據(jù)結(jié)構(gòu)中，它將程序變成了可并發(fā)執(zhí)行的進程。2） 個已經(jīng)被掛起的進程，它的PCB會被SWA交換到外存。5.什么是進程的運行

15、、就緒、阻塞和掛起狀態(tài)？試描述進程的五狀態(tài)、七狀態(tài) 轉(zhuǎn)移變化圖。1）進程的狀態(tài)：運行狀態(tài)：一個進程已得到CPU其程序正在CPU上執(zhí)行；就緒狀態(tài)：進程已獲得除CPU以外的所有必要資源，只要得到CPU便可立即執(zhí)行；阻塞狀態(tài)：正在執(zhí)行的進程因為某種事件（如I/O請求）的發(fā)生二暫時無法繼續(xù)執(zhí)行，只有 等相應(yīng)的事件完成后才能去競爭CPU掛起狀態(tài)：其實質(zhì)是使進程不能繼續(xù)執(zhí)行，及時掛起后的進程處于就緒狀態(tài)，它也不能參與CPU的競爭。2）進程的五狀態(tài)轉(zhuǎn)移變化圖：Riiiiiiin遼3）進程的七狀態(tài)轉(zhuǎn)移變化圖: 單掛起：6.請描述實現(xiàn)進程創(chuàng)建和進程結(jié)束的內(nèi)部基本處理流程。進程創(chuàng)建的基本過程：?申請空白PCB（創(chuàng)

16、建內(nèi)核進程對象）?為新進程分配資源?創(chuàng)建進程地址空間框架；?創(chuàng)建進程打開對象句柄表；?加載并映射新進程映像到進程用戶空間，包括分配部分物理內(nèi)存頁;?在進程用戶空間中分配進程運行環(huán)境控制塊（PEB）；?初始化進程PCB和PEB?將新進程狀態(tài)置為“就緒”，并插入就緒隊列。 進程的終止/退出(EXIT()創(chuàng)建仆紅縮扌迅N 苗掛起壬H 起ra應(yīng)丁n隧桂起聽雙掛起:扛?根據(jù)被終止進程標(biāo)識，從PCB隊列中檢索出該進程PCB從中讀出進程狀態(tài)；?若被終止進程處于執(zhí)行狀態(tài)，應(yīng)立即中止該進程的執(zhí)行?修改該進程的狀態(tài)到終止?fàn)顟B(tài)，并立即申請再調(diào)度；?若還有子孫進程，還應(yīng)將它們終止或過繼；?釋放進程擁有的所有資源；?釋

17、放PCB7.請說明進程與線程的區(qū)別與聯(lián)系。線程擁有獨立的用戶空間嗎？線程可以參 與資源分配嗎？1)進程與線程的區(qū)別與聯(lián)系：a)地址空間： 不同進程的地址空間相互獨立， 而同一進程的各線程共享同一地址空間， 一 個進程中的線程在另一進程中是不可見的。b)通信關(guān)系：進程間通信必須通過OS提供的進程間通信機制，而同一進程的線程間通信 可以通過直接讀寫進程數(shù)據(jù)段如全局變量進行 (仍需要同步互斥機制保證數(shù)據(jù)訪問的一 致性)。c)調(diào)度切換：同一進程中的線程上下文切換比進程上下文切換快得多。d)線程與進程相比的主要優(yōu)點:創(chuàng)建、終止、切換快，系統(tǒng)開銷少；通信方便 由于同進程內(nèi)線程間共享內(nèi)存和文件資源，故可直接

18、進行不通過內(nèi)核的通信； 系統(tǒng)允許的最大線程數(shù)限制弱得多；e)采用多線程的程序設(shè)計技術(shù)， 可以更好提高系統(tǒng)的運行性能 (如吞吐量、 計算速度和響 應(yīng)時間等)。2)線程沒有獨立的用戶空間，同一進程的多個線程位于同一用戶空間： 線程在用戶空間的相關(guān)數(shù)據(jù)結(jié)構(gòu)有自己專有堆棧； 有自己的運行上下文； 有自己的線程環(huán)境塊TEB以及內(nèi)核數(shù)據(jù)結(jié)構(gòu)TCBPEB在用戶空間的位置是固定的，PEB下方就是TEB,進程中有幾個線程就有幾個TEB每個TEB占一個4KB的頁面。3)線程不可以參與資源分配：一個進程內(nèi)可容納多個線程。 進程仍作為參與資源分配的最基本單位， 但把線程作為調(diào) 度的最基本單位，從而達到以小的開銷來提高

19、進程內(nèi)的并發(fā)和共享程度的目的。8. 請說明 windows 系統(tǒng)中與線程描述有關(guān)的數(shù)據(jù)結(jié)構(gòu)，以及線程創(chuàng)建的基本過 程。線程的相關(guān)數(shù)據(jù)結(jié)構(gòu)：線程的內(nèi)核數(shù)據(jù)結(jié)構(gòu)（代表對象）：是ETHREA,是一種調(diào)度對象，它的第一個成份是數(shù)據(jù)結(jié)構(gòu)KTHREAD也稱為TCB;線程在用戶空間的相關(guān)數(shù)據(jù)結(jié)構(gòu)： 有自己專有堆棧； 有自己的運行上下文； 有自己的線程環(huán)境塊TEB；（PEB在用戶空間的位置是固定的，PEB下方就是TEB,進程中有幾個線程就有幾個TEB,每 個TEB占一個4KB的頁面。） 線程的創(chuàng)建： 一般首個線程在進程創(chuàng)建的結(jié)束階段被自動創(chuàng)建 （由父進程代為創(chuàng)建） ；其它線程由進程自 己調(diào)用系統(tǒng)API函數(shù)創(chuàng)建

20、。線程創(chuàng)建的基本過程：創(chuàng)建/初始化ETHREA數(shù)據(jù)結(jié)構(gòu)，并處理好與EPROCES的關(guān)系。 為新線程分配堆棧、創(chuàng)建并初始化執(zhí)行上下文。 在所屬進程的用戶空間中，創(chuàng)建并設(shè)置新線程TEB。進一步設(shè)置目標(biāo)線程的KTHREAD據(jù)結(jié)構(gòu)，包括：設(shè)定新線程在用戶空間執(zhí)行入口始址。ETHREAD數(shù)據(jù)結(jié)構(gòu)中有相關(guān)成份，用來存放相關(guān)地址。將其上下文中的斷點（返回點）設(shè)置成指向內(nèi)核中的一段程序KiThreadStartup，使 得該線程一旦被調(diào)度運行時就從這里開始執(zhí)行。將線程對象標(biāo)插入就緒隊列第3章 存儲管理1.說明存儲管理的主要功能和目標(biāo)。1內(nèi)存分配與回收：為每個進程創(chuàng)建執(zhí)行空間，分配初始所需基本內(nèi)存，并允許進程在

21、執(zhí)行中動態(tài)申請/釋放內(nèi)存；2實現(xiàn)有效的存儲保護與共享；3主存擴充（擴充主存的大?。?引入虛擬存儲技術(shù)，用外存擴充主存數(shù)量，彌補物理內(nèi)存數(shù)量的不足；4提高主存的利用率 采用合理得當(dāng)?shù)乃惴?、策略和?shù)據(jù)結(jié)構(gòu)； 提高計算機資源利用率的根本途徑是采用多道程序設(shè)計技術(shù)，實現(xiàn)并發(fā)共享。2.若采用首次適應(yīng)策略和 FBC 進行空閑分區(qū)管理的動態(tài)分區(qū)分配描述算法。若 將首次適應(yīng)策略改為最壞適應(yīng)策略、最佳適應(yīng)策略或循環(huán)首次適應(yīng)策略，該 如何修改算法？一種典型的動態(tài)分區(qū)分配算法/采用首次適應(yīng)算法和FBC結(jié)構(gòu)long get_block(int x, byte * p) /請求大小為Xint i; long y;i=1

22、;while ( FBCi.size!=0 & FBCi.size=delt) FBCi.size= y;FBCi.addr= FBCi.addr+x;return x;最壞適應(yīng)策略：此處有錯，循環(huán)結(jié)束條件欠妥，最后應(yīng)該給FBC賦值long get_block(int x, byte * p) /請求大小為Xint i,j,max; long y;i=1;j=1;while ( FBCi.size!=0 & FBCi.size=x)availj+=FBCi;i+;min=avail1;for(i=1;i=max) max=availj;if (avali.size =0) p=

23、null;return 0 ;p=availi.addr;y=availi.size-x;if (y=delt) availi.size= y;availi.addr= availi.addr+x;return x;最佳適應(yīng)策略：此處有錯，循環(huán)結(jié)束條件欠妥，最后應(yīng)該給FBC賦值(懶得改了)long get_block(int x, byte * p) /請求大小為Xint i,j,min; long y;i=1;j=1;while ( FBCi.size!=0 & FBCi.size=x)availj+=FBCi;i+;min=avail1;for(i=1;ij;i+) if(avai

24、li=delt) availi.size= y;availi.addr= availi.addr+x;return x;循環(huán)首次適應(yīng)策略：int i ,flag=0; /全局變量long get_block(int x, byte * p) /請求大小為Xlong y;if(flag=0)i=1;flag=1;while ( FBCi.size!=0 & FBCi.size=delt) FBCi.size= y;FBCi.addr= FBCi.addr+x;return x;3.歸納總結(jié)頁式存儲分配與管理的基本特點。頁式分配管理的基本思想：進程使用線性邏輯地址LA（32位、一維、連續(xù)）

25、OS透明地將線性地址分頁，即將32位地址劃分為兩段：p=LA/頁大小;d=LA-P*頁大小OS透明地將物理內(nèi)存也按頁大小（4k）劃分一系列的頁框（frame），并進行依次編號OS通過頁映射表（頁表），將進程地址空間的所有邏輯頁，分別映射加載到不同的、 不必連續(xù)的物理頁框中。頁式分配的特點：優(yōu)點：內(nèi)存分配適應(yīng)性更強；沒有外碎片；每個進程浪費空間不超過1個頁。缺點：仍要求程序一次性地全部裝入內(nèi)存。4.試描述帶有快表的頁式地址變換機制。由于頁表是存放在內(nèi)存中的，CPU每存取一條指令或一個數(shù)據(jù)，都要兩次訪問內(nèi)存，第一次訪問內(nèi)存中的頁表，以得到指令或數(shù)據(jù)所在頁對應(yīng)的內(nèi)存塊號；第二次才可以根據(jù)物理地址存取

26、指令或數(shù)據(jù)，這使得計算機的處理速度降低了近1/2。為了提高存取速度，可在地址變換機構(gòu)中增設(shè)一個具有并行查找能力的高速緩沖寄存器，又稱為“聯(lián)想寄存器”或 “快表”，用以存放當(dāng)前被頻繁訪問的頁面的也好和對應(yīng)的頁表項。在進行地址轉(zhuǎn)換時，地址變換機構(gòu)自動將邏輯地址中的頁號并行地與快表中的所有也好 進行比較，若其中有與此相匹配的頁號，便可以直接從快表中讀出該頁對應(yīng)的物理塊號，并送到物理地址寄存器中。如果在快表中未找到對應(yīng)的頁號，則仍需訪問內(nèi)存中的頁表來進行地址轉(zhuǎn)換，同時還必須將得到的頁表項與頁號一起裝入到快表中，若快表已滿，則還需根據(jù)置換算法淘汰某個快表項，已裝入新內(nèi)容。由于成本的關(guān)系，快表通常做得較小

27、。5.試描述引入目錄頁的、具有兩級頁表的頁式地址變換機制。針對難以找到大的連續(xù)內(nèi)存空間以存放頁表的問題，可利用將頁表進行分頁的辦法，使每個頁面的大小與內(nèi)存物理塊的大小相同，離散地存放在不同的物理塊中，并為之建立一張頁表（外層頁表Outer Page Table）。以32位邏輯地址空間為例， 家丁頁面大小為4kB, 若采用1級頁表結(jié)構(gòu)，須具有20位頁號占1M在采用兩級頁表結(jié)構(gòu)時，再對頁表進行 分頁，使每個頁表中包含210個頁表項，此時邏輯地址結(jié)構(gòu)如下：外層頁號外層頁內(nèi)地址、頁內(nèi)地址1 丿P1P2d3122 2112 1106.說明段式分配管理的基本數(shù)據(jù)結(jié)構(gòu)，以及段式系統(tǒng)的地址變換機制。段式分配與

28、管理的基本思想（地址變換機制）：按程序中的自然分段特性來劃分邏輯空間，形成二維地址空間。 例如，序中主程序、子程序、靜態(tài)變量、堆棧等，都是基于段的。邏輯地址形式：（段號s,段內(nèi)位移d）；低級語言程序中用戶可直接給出該形式地址，高級語言程序在編譯后也可得到這種形式地址。程序加載時，OS為所有的段分配所需內(nèi)存，每個段被分配在一個連續(xù)分區(qū)；但進程中 的各個段可離散分配到主存的不同分區(qū)；在為每個段分配物理內(nèi)存時，采用動態(tài)分區(qū)管理方法。段式分配管理的相關(guān)數(shù)據(jù)結(jié)構(gòu)進程用戶空間段描述表段長|屬性|起始邏輯地址|段表項索引號進程段表（Segment Table,ST）每個進程一張（套），被放置在系統(tǒng)空間段長|

29、段屬性（保護碼）|段基址進程局部描述符表（Local Descriptor Table, LDT）描述可變分區(qū)的空閑段表（FBT或FBC_ hh用戶空間 中的一個 邏輯段加載/映射需借助:FBT或FBC7.什么是局部性原理？試說明虛擬存儲管理實現(xiàn)的基本思想、技術(shù)優(yōu)勢和特征。1）局部性原理：程序在執(zhí)行過程中的一個較短時期，所執(zhí)行的指令地址和操作數(shù)地址，將局限于一定區(qū)域內(nèi)。程序執(zhí)行活動具有：時間局部性和空間局部性。2）虛擬存儲管理實現(xiàn)的基本思想：程序裝入時，不必將其全部讀入內(nèi)存，只需將當(dāng)前執(zhí)行需要的部分頁（或段）裝入內(nèi)存，就可讓程序開始執(zhí)行。在程序執(zhí)行過程中，如需訪問尚未在內(nèi)存的邏輯地址單元（缺頁

30、或缺段），則OS通過相應(yīng)機制將所缺頁（段）裝入內(nèi)存消除缺頁（段）故障。另一方面，OS還將暫時不用的頁（段）調(diào)出內(nèi)存，以騰出更多的可用內(nèi)存空間。 從用戶的角度看，系統(tǒng)好象提供了比實際內(nèi)存更大的存儲容量這種虛擬擴展的存儲 體系，常被稱為“虛擬存儲器”3）技術(shù)優(yōu)勢：能給用戶提供大于實際物理內(nèi)存的虛擬存儲器， 允許在較小內(nèi)存中執(zhí)行較大進程， 并可 在有限主存中容納更多的并發(fā)進程。32與覆蓋技術(shù)相比，虛擬存儲實現(xiàn)對用戶透明，不影響用戶編程結(jié)構(gòu)，用戶可在高達232的虛空間編制程序。4）特征：離散性；多次性；對換性；虛擬性；5）實現(xiàn)方式： 請求分頁；請求分段；請求段頁式；8.與頁式系統(tǒng)相比，請求分頁系統(tǒng)的頁

31、表項擴展了哪些信息域？請簡要說明它們的作用。 請求分頁的虛存系統(tǒng)需對頁式系統(tǒng)進行如下幾方面的擴充：對頁表的頁表項（PTE）進行擴展，增加一些必要的管理標(biāo)志位（它們占用PTE原先恒為0的低位段，故并不需要擴大PTE的大?。＃ú恍柙黾有碌挠布蛟O(shè)施）增加可有效處理缺頁（故障）的相關(guān)設(shè)施和機制（硬件）增強頁面調(diào)度管理能力（軟件擴展）選用合適的頁面調(diào)入策略、頁面置換策略和頁面置換算法； 增強對系統(tǒng)及各進程駐留頁面集，即“工作集”的有效管理，降低系統(tǒng)缺頁率，提高系 統(tǒng)性能。（軟件擴展）支持自動選取/設(shè)定工作集大小，及動態(tài)維護、修剪工作集。 增加對物理頁框的管理，以支持更有效的頁面調(diào)度和工作集管理（軟件

32、擴展）增加頁框狀態(tài)描述數(shù)據(jù)庫，該庫可直接存儲在相關(guān)頁框中。9.在請求分頁系統(tǒng)中，頁故障中斷有何特點？請描述這類系統(tǒng)的缺頁故障處理機制。 缺頁中斷是一種比較特殊的中斷，體現(xiàn)在：a）在指令執(zhí)行期間產(chǎn)生和處理缺頁中斷b）常規(guī)外部中斷，是在每條指令執(zhí)行完畢后，檢查是否有中斷請求到達。c）一條指令可能產(chǎn)生多次中斷。d）當(dāng)從中斷處理程序返回時，能正確執(zhí)行原先產(chǎn)生缺頁故障的指令。 故障處理的基本過程：當(dāng)發(fā)生缺頁故障時，OS會向外存（頁文件或頁映射文件）發(fā)出讀操作調(diào)入相關(guān)頁面； 頁面調(diào)入I/O操作是同步的， 即線程會進入睡眠等待直到I/O完成（等待事件到來） 被喚醒。對同一進程的多個線程(并發(fā))，若遇到同位置

33、缺頁故障，可串接到同一等待事件中.頁面調(diào)入I/O代碼也必須能識別處理調(diào)入完成后，相關(guān)頁表項的情況變換。10. 在請求分頁系統(tǒng)中，若內(nèi)存分配有固定 / 可變兩種，置換有全局 / 局部置換兩 種，那么，基于分配與置換的組合，可得到哪幾種頁面置換策略？共有四種，分別為： 固定內(nèi)存分配，全局置換策略：采用該策略是， 為進程分配的物理塊數(shù)目在進程的整個生命周期都固定不變， 若進程因調(diào)入 頁面而需要換出某個頁面， 可以從全局進行置換。 雖然比固定內(nèi)存的局部置換好一些， 但是 固定的內(nèi)存限制了整個置換的效果。可變內(nèi)存分配，全局置換策略：采用該策略時， 系統(tǒng)先為每個進程分配一定數(shù)目的物理塊， 當(dāng)進程發(fā)生缺頁時

34、， 若系統(tǒng)中有 空閑的物理塊， 則為其分配一個物理塊并裝入缺頁； 若系統(tǒng)中已沒有空閑的物理塊， 則為其 分配一個物理塊并裝入缺頁； 若系統(tǒng)中已沒有空閑的物理塊， 則從內(nèi)存中選擇一頁換出， 再 裝入缺頁， 被換出的頁可以是系統(tǒng)中任意進程的頁， 這樣，自然又會使那個進程的物理塊減 少，進而使其缺頁率增加。固定內(nèi)存分配，局部置換策略：采用該策略是， 為進程分配的物理塊數(shù)目在進程的整個生命周期都固定不變， 若進程因調(diào)入 頁面而需要換出某個頁面， 則只能患處他自己的內(nèi)存頁面。 由于進程是動態(tài)的， 即使在運行 之前為它分配了適當(dāng)數(shù)目的內(nèi)存塊， 在采用固定分配局部置換策略時， 進程在運行過程中仍 然可能會因

35、為內(nèi)存塊太少而頻繁缺頁，或者因為內(nèi)存塊太多而浪費空間?？勺儍?nèi)存分配，局部置換策略：采用該策略時， 為每個進程分配一定數(shù)目的物理塊后， 若某個進程發(fā)生缺頁， 則只能將自己 的某個內(nèi)存頁換出， 。如果進程在運行時頻繁發(fā)生缺頁中斷， 則系統(tǒng)需為該進程分配若干附 加的物理塊，直至其缺頁率減少到適當(dāng)程度為止； 反之， 若一個進程的缺頁率特別低， 則可 以適當(dāng)減少分配給它的物理塊， 但不應(yīng)引起其缺頁率的明顯增加。因此， 可變分配局部置換 策略可以獲得較高的內(nèi)存空間利用率，同時又能保證每個進程有較低的缺頁率。11.簡要說明OPT FIFO、LFU LRU CLOCK及改進CLOCK等置換算法的基本思想，若假

36、設(shè) 系統(tǒng)采用固定分配局部替換的頁面調(diào)入策略，并假設(shè)某進程在創(chuàng)建時，分配到了3個頁面框。試針對如下的該進程相關(guān)頁面引用順序；7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1分別計算采用OPT FIFO和LRU三種算法時的缺頁率。幾種算法的基本思想： 最佳算法(optimal, OPT)選擇未來最長時間不使用頁進行置換(最理想算法)； 先進先出算法(FIFO)選擇最先進入駐留集的頁面進行置換； 最不常用算法(Least Frequently Used, LFU)選擇到至今訪問次數(shù)最少的頁進行置換，要設(shè)置一個頁面訪問計數(shù)器。最近最久

37、未使用算法(Least Rece ntly Used, LRU)?選擇內(nèi)存中至今最久未使用頁面進行置換；是局部性原理的合理近似，性能接近最佳，但硬件開銷較大。時鐘算法(clock)?也稱最近未用算法(Not Recently Used,NRU)，是LRU和FIFO的折衷。每頁框有個使用位(use bit,ub)，若該頁被訪問ub=1。所有駐留頁面組織為類似時鐘的環(huán)形緩 沖池，置換時采用一個類時鐘指針，從當(dāng)前指針位置開始順時針?biāo)阉鳈z查ub=0的頁框，選擇首個遇到的ub=0的頁框進行置換。改進的時鐘算法(結(jié)合訪問位A和修改位M)?第一輪候選對象：A=0AM=0,失敗進入下一輪?第二輪候選對象：A=

38、0AM0,失敗進入下一輪?第三輪，先將所有目標(biāo)駐留頁面框的A復(fù)位，再從滿足A=0A博0的候選頁面框中，進行一輪選擇。70120304230321201701FIFO77700123042223000127缺頁率001123042333011127015/20122304230001222701LRU77701223042203312017缺頁率001203042303212017012/20120304230321201701OPT77722222222222222777缺頁率00000044400000000009/20111333333331111111第 4 章 進程的同步與通信（共享變

39、量是否一定互斥使用）1.了解多進程環(huán)境下資源的概念、分類和特性。概念：Any entity or any abstract machine component ,if it satisfies following charactics:（滿足以下三個特征的任何實體或抽象的計算機元件：）（1）a process must request it from OS（進程需要從操作系統(tǒng)申請它）（2）theprocess must block its exeuti on un til the en tity is allocated to it（資源未分配給進程時，進程處于阻塞狀態(tài)）（3）thecoexi

40、st ing process will compete for resources if they n eed resources（當(dāng)互斥的進程需要資源時，進程之間處于競爭關(guān)系）分類：分類一：（1）可分配，用完要歸還（可歸還）（2）無需分配的抽象資源分類二：（1）可冋時共享資源（2）臨界資源特性：有限性：2什么是臨界區(qū)？請說明臨界區(qū)的代碼模式、同步原則。若不同進程訪問相同 臨界資源R1,它們訪問臨界資源 R1 的代碼一定相同嗎？它們控制進入訪問 臨界資源 R1 代碼區(qū)的同步代碼一定相同嗎？臨界區(qū)定義：每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)（Critical Section）（臨界資源是一次

41、僅允許一個進程使用的共享資源）或定義為 :a segment of code ,that write a shard device（write a shared device，是寫入操作，非讀寫操作），which cannot be wxcuted while the other process arein the resp ond segme nt of code that acess to the same resources代碼模式：/進入臨界區(qū)En terCriticalSecti on（&g_cs）;/對共享資源進行寫入（不是讀寫，）操作/離開臨界區(qū)2.什么是臨界區(qū)？每個進程

42、中訪問臨界資源的那段代碼稱為臨界區(qū)（Critical Section）（臨界資源是一次僅允許一個進程使用的共享資源）請說明臨界區(qū)的代碼模式、同步原則。/臨界區(qū)結(jié)構(gòu)對象CRITICAL_SECTION g_cs;/共享資源char g_cArray10;UINT ThreadProc10(LPVOID pParam)/進入臨界區(qū)EnterCriticalSection(&g_cs);/對共享資源進行寫入操作for (int i = 0; i 10; i+) g_cArrayi = a;Sleep(1); /離開臨界區(qū)LeaveCriticalSection(&g_cs); ret

43、urn 0;UINT ThreadProc11(LPVOID pParam)/進入臨界區(qū)EnterCriticalSection(&g_cs);/對共享資源進行寫入操作for (int i = 0; i 10; i+) g_cArray10 - i - 1 = b; Sleep(1);/離開臨界區(qū)LeaveCriticalSection(&g_cs); return 0;void CSample08View:OnCriticalSection()/初始化臨界區(qū)InitializeCriticalSection(&g_cs);/啟動線程AfxBeginThread(Thr

44、eadProc10, NULL);AfxBeginThread(ThreadProc11, NULL);/等待計算完畢Sleep(300);/報告計算結(jié)果CStri ng sResult = CStri ng(g_cArray);AfxMessageBox(sResult);進程進入臨界區(qū)的調(diào)度原則是：1、如果有若干進程要求進入空閑的臨界區(qū)，一次僅允許一個進程進入。2、任何時候，處于臨界區(qū)內(nèi)的進程不可多于一個。如已有進程進入自己的臨界區(qū)，則 其它所有試圖進入臨界區(qū)的進程必須等待。3、進入臨界區(qū)的進程要在有限時間內(nèi)退出，以便其它進程能及時進入自己的臨界區(qū)。4、 如果進程不能進入自己的臨界區(qū)，則應(yīng)

45、讓出CPU避免進程出現(xiàn)“忙等”現(xiàn)象若不同進程訪問相同臨界資源R1,它們訪問臨界資源R1的代碼一定相同嗎？不一定，例如相同的循環(huán)，可以采用i+或者使用i-它們控制進入訪問臨界資源R1代碼區(qū)的同步代碼一定相同嗎？一定相同同步原則：忙碌等待(必須)：對已有進程進入臨界區(qū)時，其他試圖進入臨界區(qū)的進程立即進入臨界區(qū)。 空閑則入(必須)：當(dāng)沒有進程處于臨界區(qū)時，可以允許一個請求進入臨界區(qū)的進程立即進入臨界區(qū)。有限等待(錦上添花)：對要求訪問臨界資源的進程，應(yīng)保證能在有限時間內(nèi)進入臨界區(qū)。讓權(quán)等待(錦上添花)：當(dāng)進程不能進入臨界區(qū)時，應(yīng)釋放處理機。3.請寫出利用1)禁止中斷結(jié)合共享標(biāo)志變量；2)多個共享標(biāo)志

46、變量；3)硬件指令TS; 4) 硬件指令SWAP等四種技術(shù)方案，實現(xiàn)臨界區(qū)同步的算法，并分別舉一例說明它們的應(yīng) 用方法。這些算法都是基于平等競爭的同步實現(xiàn)算法，它們能實現(xiàn)“有限等待”和“讓 權(quán)等待”這兩條原則嗎？1)禁止中斷結(jié)合共享標(biāo)志變量：En ter(lock)Disable in terrupt();While(lock )En able in terrupt()Disable in terrupt ()Lock=true;En able in terrupt()Exit (lock)Disable interrupt();Lock=false;Enable interrupt();2)

47、多個共享標(biāo)志變量：Boolean flagNWhile(1)Flagi=true;Turn=j;While(flagj=true& turn=j)null;Flagi=false;3)硬件指令TS:TS功能描述：Boolean TS(boolean *lock)Boolean old;old=*lock;*lock=true;Return old;應(yīng)用(算法描述)：Lock=false;While (TS(&lock);Lock=false;進程的其他代碼；4)硬件指令SWAP功能描述：Swap(Boolean *a, boolean *b)Boolean temp;Temp=

48、*a;*a=*b;*b=temp;應(yīng)用（算法描述）Pi/Pj（線程）：有全局變量lockPi :有局部變量key例子：P1：While（1）key=true;While（key=true）Swap（&lock,&key）Lock=false;用上面所列出的算法語句，沒有辦法實現(xiàn)【有限等待】和【讓權(quán)等待】，但通過改進的方式 和引入新的算法或許可以利用這四種方法實現(xiàn)【有限等待】和【讓權(quán)等待】4.理解信號量的概念、定義和分類；理解具有睡眠等待機制的信號量實現(xiàn)算法。信號量定義：*是一種最最經(jīng)典，能有效解決進程同步的軟件方法，也是現(xiàn)代OS中最具基本的同步機制。*是一種抽象的OS內(nèi)核數(shù)據(jù)類

49、型（見作業(yè)本）分類：（1） 二元信號量：value 0,1（互斥）（2）一般信號量：value非負具有睡眠等待機制的信號量實現(xiàn)算法：typedef struct /信號量定義int value;LIST_ENTRY queue; semaphore;normal compute section;void P (semaphore s) /wait (semaphore s)/ P操作定義 -s.value; if (s.value 0) 構(gòu)造一個包含進程PID的等待描述塊，插入到信號量的等待隊列s.queue中;調(diào)用阻塞原語，主動放棄CPU進入睡眠等待；void V (semaphore s)

50、 /sig nal(semaphore s) / V操作定義 +s.value;if (s.value =0) 從s.queue中移出第1個等待塊，將對應(yīng)進程狀態(tài)改為就緒態(tài)后5.掌握用信號量解決臨界區(qū)問題、基本同步問題、生產(chǎn)者-消費者問題、讀-寫者問題和哲學(xué)家就餐問題的算法。信號量解決臨界區(qū)問題:Proc_0 Proc_1 while (1) while (1) ;p(mutex);v(mutex);p(mutex);v(mutex);這部分是注解： semaphore mutex=1;ork(proc_O,O);ork(proc_1,O);用信號量解決基本同步問題:proc_A while

51、(1) ;write(x);/produce xV(s1); /sig nal proc_BP(s2);/waitfor proc_Bsig nalread(y);proc_B while (1) P(s1); /waitfor proc_Aread(x);write(y); /produce yV(s2); /sig nal proc_A;注釋部分：semaphore s仁0; s2=0;Ork(proc_A, 0 ); fork(proc_B,0);生產(chǎn)者-消費者問題:Producer。bufType *next, *herewhile (1) ProduceItem( next);P(e

52、mpty); /claim a empty bufP(mutex); /緩沖池操作here=obtain(empty)V(mutex);CopyBuffer(next, here);P(mutex); /緩沖池操作Release(here,fullPool);V(mutex);V(full); /signal a full bufferConsumer() bufType *next, *herewhile (1) P(full); /claim a full bufP(mutex); /緩沖池操作Here=obtain(full)V(mutex);CopyBuffer(here, next);P(mutex); /緩沖池操作Release(here,emptyPool);V(mutex);V(empty); /signal an emptyCon sumeItem( next)注釋部分：bufType bufferN;semaphore mutex=1; / 互斥使用 buffersemaphore full=O; empty=N;讀-寫者問題（讀者優(yōu)