操作系統(tǒng)的重點(diǎn)知識總結(jié)材料

1、些專用服務(wù)程序第一章引論1、操作系統(tǒng)定義（P1）操作系統(tǒng)是配置在計(jì)算機(jī)硬件上的第一層軟 件，是對硬件系統(tǒng)的首次擴(kuò)充。是一組控制和管理計(jì)算機(jī)硬件和軟件資源、合 理地對各類作業(yè)進(jìn)行調(diào)度以及方便用戶使用的程 序的集合。2、操作系統(tǒng)的作用（P2）1. OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口2. OS作為計(jì)算機(jī)系統(tǒng)資源的管理者3. OS實(shí)現(xiàn)了對計(jì)算機(jī)資源的抽象3、 推動操作系統(tǒng)發(fā)展的主要動力（P41. 不斷提高計(jì)算機(jī)資源的利用率2. 方便用戶3. 器件的不斷更新迭代4. 計(jì)算機(jī)體系結(jié)構(gòu)的不斷發(fā)展4、 多道批處理系統(tǒng)的特征及優(yōu)缺點(diǎn)（P8）特征：多道性、無序性、調(diào)度性優(yōu)點(diǎn)：1. 資源利用率高2. 系統(tǒng)吞吐量

2、大缺點(diǎn)：1. 平均周轉(zhuǎn)時(shí)間長2. 無交互能力（單道、多道都是）5、 分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)特征的比較（P121. 多路性（實(shí)時(shí)系統(tǒng)的多路性主要表現(xiàn)在系統(tǒng)周期性地對多路信息的采集、以及對多個對象或 多個執(zhí)行機(jī)制進(jìn)行控制。分時(shí)系統(tǒng)中的多路性則和用戶有關(guān)，時(shí)多時(shí)少。）2. 獨(dú)立性3. 及時(shí)性：（實(shí)時(shí)系統(tǒng)對及時(shí)性的要求更嚴(yán)格 實(shí)時(shí)控制系統(tǒng)以控制對象要求的開始截止時(shí)間或完成截止時(shí)間來確定。）4. 交互性：實(shí)時(shí)系統(tǒng)的交互性僅限于訪問某5. 可靠性：實(shí)時(shí)系統(tǒng)對可靠性的要求更高，否則經(jīng)濟(jì)損失及后果無法預(yù)料。6、 操作系統(tǒng)的基本特征（P14）（并發(fā)、共享、虛擬和異步其中并發(fā)特征是操作系統(tǒng)最重要的特征是其他特征的前提

3、）1. 并發(fā)性2. 共享性（互斥共享方式、同時(shí)訪問方式）3. 虛擬性（時(shí)分復(fù)用技術(shù)（虛擬處理機(jī)技術(shù)、 虛擬設(shè)備技術(shù)）、空分復(fù)用技術(shù)（虛擬磁盤技術(shù)、 虛擬存儲器技術(shù)）4. 異步性（進(jìn)程的異步性：進(jìn)程是以人們不 可預(yù)知的速度向前推進(jìn)的）7、 操作系統(tǒng)的主要功能（P18）1. 處理機(jī)管理功能（進(jìn)程控制（1、進(jìn)程互斥 方式：進(jìn)程或者線程在對臨界資源進(jìn)行訪問時(shí)，應(yīng)采取互斥方式；2、進(jìn)程同步方式：相互合作去完 成共同任務(wù)的諸進(jìn)程貨線程）、進(jìn)程通信、調(diào)度（作 業(yè)調(diào)度、進(jìn)程調(diào)度）2. 存儲器管理功能（內(nèi)存分配、內(nèi)存保護(hù)、地址映射、內(nèi)存擴(kuò)充）3. 設(shè)備管理功能（緩沖管理、設(shè)備分配、設(shè) 備處理）4. 文件管理功能

4、（文件存儲空間的管理、目 錄管理、文件的讀/寫管理和保護(hù)）5. 用戶接口 （命令接口（聯(lián)機(jī)用戶接口、脫 機(jī)用戶接口）、程序接口、圖形接口） 第二章進(jìn)程管理1、程序順序執(zhí)行時(shí)的特征（P34）1. 順序性：嚴(yán)格按照程序所規(guī)定的次序執(zhí)行。2. 封閉性：程序在封閉環(huán)境下運(yùn)行，系統(tǒng)中 所有資源的狀態(tài)只有本程序才能改變它。3. 可再現(xiàn)性：只要初始條件相同，無論怎樣 執(zhí)行，其結(jié)果都是相同的。2、程序并發(fā)執(zhí)行時(shí)的特征（提高了系統(tǒng)吞吐量）（P36）1間斷性：并發(fā)執(zhí)行的實(shí)體之間相互制約， 造成程序的執(zhí)行岀現(xiàn)間斷，而不連續(xù)。2. 非封閉性：多個程序共享系統(tǒng)資源，因而 其狀態(tài)有多個程序改變，從而失去封閉性。3. 不可

5、再現(xiàn)性：封閉性的失去必然導(dǎo)致不可再現(xiàn)性。3、進(jìn)程及其特征（P37進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨(dú)立單位。進(jìn)程是程序的一次執(zhí)行進(jìn)程實(shí)體：由程序段、相關(guān)的數(shù)據(jù)段和 PCB勾 成特征：結(jié)構(gòu)特征動態(tài)性（進(jìn)程最基本的特征）并發(fā)性（引人進(jìn)程的目的：為了使其進(jìn)程實(shí)體 能和其他的進(jìn)程實(shí)體并發(fā)執(zhí)行；而程序（沒有建立 PCB不能并發(fā)執(zhí)行）獨(dú)立性異步性4、進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換圖（P38）1. 就緒（Ready）狀態(tài)2. 執(zhí)行狀態(tài)3. 阻塞狀態(tài)（典型事例：請求I/O、申請緩沖空間等）5、 引入掛起狀態(tài)的原因（P39）1. 終端用戶的請求2. 父進(jìn)程請求3. 負(fù)荷調(diào)節(jié)的需要4. 操作系統(tǒng)的需

6、要6、具有掛起狀態(tài)的進(jìn)程狀態(tài)及其轉(zhuǎn)換圖7、 進(jìn)程控制塊及其作用（P41）PCB是 一種數(shù)據(jù)結(jié)構(gòu)，是進(jìn)程實(shí)體的一部分， 記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況 以及控制進(jìn)程運(yùn)行的全部信息。作用：1. 使一個在多道程序環(huán)境下不能獨(dú)立運(yùn)行的 程序（含數(shù)據(jù)），成為一個能獨(dú)立運(yùn)行的基本單位，一個能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。2. PCB是進(jìn)程存在與否的唯一標(biāo)志，隨著進(jìn)程 的建立而建立,隨著進(jìn)程的撤消而撤消。創(chuàng)建進(jìn)程就是創(chuàng)建PCBoo8、 進(jìn)程之間的兩種制約關(guān)系（P48）1. 間接制約一一競爭資源一一進(jìn)程互斥2. 直接制約一一相互合作一一進(jìn)程

7、同步9、臨界資源（P48）臨界資源。OS中把一次只能被一個進(jìn)程使用的資源成為10、臨界區(qū) （P50）進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。11、 同步機(jī)構(gòu)應(yīng)遵循的規(guī)則（P50）空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待12、利用信號量實(shí)現(xiàn)前驅(qū)關(guān)系算法P（ 54 ）P（ 55 ）13、 經(jīng)典同步算法（生產(chǎn)者消費(fèi)者問題，哲學(xué)家就餐問題和讀者寫者問題）略14、進(jìn)程通信的類型 （P65）_低級：信號量進(jìn)程通信廠共享存儲器系統(tǒng)（基于共享數(shù)1據(jù)結(jié)構(gòu)或存儲區(qū)的通信方式）*高級 消息傳遞系統(tǒng)（直接、間接）管道通信系統(tǒng)（必須提供的協(xié) 調(diào)能力：互斥、同步、確定對方 是否存在）15、線程的定義（P72）現(xiàn)代OS引入的

8、比進(jìn)程更小的可以獨(dú)立運(yùn)行、 調(diào)度的基本單位，是輕型實(shí)體，不擁有資源。16、線程和進(jìn)程比較線程又稱為輕型進(jìn)程，通常一個進(jìn)程都擁有若 干個線程，至少也有一個（多線程OS中的進(jìn)程不是一個可執(zhí)行的實(shí)體）1、調(diào)度：傳統(tǒng)OS中，進(jìn)程是擁有資源的基本 單位，獨(dú)立調(diào)度、分派的基本單位。引入線程后，則把線程作為調(diào)度和分派的基本單位，而進(jìn)程作為 擁有資源的基本單位2、并發(fā)性：引入線程的OS中，進(jìn)程之間可以 并發(fā)執(zhí)行，在一個進(jìn)程中的多個線程之間也可以；這樣使得OS具有更好的并發(fā)性，從而能更加有效 的提高系統(tǒng)資源的利用率和吞吐量3、擁有資源：線程不能擁有資源4、系統(tǒng)開銷：就切換代價(jià)而言，進(jìn)程遠(yuǎn)高于 線程17、線程的屬

9、性 （P73）1. 輕型實(shí)體2. 獨(dú)立調(diào)度和分派的基本單位3. 可并發(fā)執(zhí)行4. 共享進(jìn)程資源第三章處理機(jī)調(diào)度與死鎖1、咼級調(diào)度（P84）又稱為作業(yè)調(diào)度。即從外存的后備隊(duì)列中選擇 一個作業(yè)，為它創(chuàng)建進(jìn)程，分配必要的資源，并將 新進(jìn)程插入主存的就緒隊(duì)列上。注意：分時(shí)系統(tǒng)和 實(shí)時(shí)系統(tǒng)無作業(yè)調(diào)度。JCB （作業(yè)控制塊）；是作業(yè)在系統(tǒng)中存在的標(biāo) 志，其中保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的 全部信息2、低級調(diào)度（P86）又稱進(jìn)程調(diào)度或短程調(diào)度，即從就緒隊(duì)列中選 擇一個進(jìn)程進(jìn)入運(yùn)行狀態(tài)（非搶占方式、可搶占方 式）。調(diào)度的對象是進(jìn)程（多批道處理、分時(shí)、實(shí) 時(shí)三種類型的OS中都有）3、中級調(diào)度（P87）中程調(diào)

10、度為了提高內(nèi)存利用率和系統(tǒng)吞吐量（引入目的），為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占 用內(nèi)存資源，而將它們調(diào)至外存。適當(dāng)時(shí)機(jī)再將其 調(diào)回內(nèi)存。這種調(diào)度稱為中級調(diào)度。4、 進(jìn)程調(diào)度的兩種方式（P86）1、非搶占方式（一旦給進(jìn)程分配處理機(jī)，一 直讓他運(yùn)行下去，直到完成再把處理機(jī)分配給其他 進(jìn)程）2、搶占方式（允許調(diào)度程序根據(jù)某些原則去 暫停某個正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處 理機(jī)重新分配給另一個進(jìn)程 ）5、搶占的原則 （P87）1. 優(yōu)先權(quán)原則2. 短作業(yè)（進(jìn)程）優(yōu)先原則3. 時(shí)間片原則6、操作系統(tǒng)選擇調(diào)度方式和調(diào)度算法的若 干準(zhǔn)則（P90）1. 面向用戶的準(zhǔn)則（周轉(zhuǎn)時(shí)間短、響應(yīng)時(shí)間快、截止

11、時(shí)間的保證、優(yōu)先權(quán)準(zhǔn)則）2. 面向系統(tǒng)的準(zhǔn)則 （系統(tǒng)吞吐量高、處理機(jī) 利用率好、各類資源的平衡利用）7、周轉(zhuǎn)時(shí)間（P92）周轉(zhuǎn)時(shí)間：是指從作業(yè)被提交給系統(tǒng)開始， 到作業(yè)完成為止的這段時(shí)間間隔周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間待權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間 &針對各種調(diào)度算法（先來先服務(wù)，短進(jìn) 程優(yōu)先，優(yōu)先權(quán)），計(jì)算周轉(zhuǎn)時(shí)間、帶權(quán)周 轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間9、吞吐量指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)10、多級反饋隊(duì)列調(diào)度算法的原理、性能該算法用于進(jìn)程調(diào)度，主要是為解決前面各種 進(jìn)程調(diào)度算法存在的各種不同問題而設(shè)計(jì)的一種 考慮綜合因素的調(diào)度算法。其思想如下：1、設(shè)置多個就緒隊(duì)列，

12、不同隊(duì)列具有不同優(yōu) 先級，第一個隊(duì)列優(yōu)先級最高，以后次之。給不同隊(duì)列分配不同大小的時(shí)間片， 第一個隊(duì) 列最小，以后次之（皆為前者的二倍） 。有的系統(tǒng) 也將最后一級隊(duì)列不劃分時(shí)間片。2、當(dāng)有一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放 入第一隊(duì)列的末尾，按FCFS（先來先服務(wù)）原則排 隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如果它能在該 時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；若不能則將它 放在第二列的隊(duì)尾。3、僅當(dāng)前一級隊(duì)列為空時(shí)才調(diào)度下一級隊(duì)列中的進(jìn)程。算法米用搶占式調(diào)度策略。執(zhí)行的進(jìn)程在規(guī)定的時(shí)間片內(nèi)為執(zhí)行完畢，則進(jìn)入下一級隊(duì)列的隊(duì)尾，新進(jìn)程則進(jìn)入第一級隊(duì)列 的隊(duì)尾。性能：（較好的性能，能滿足各種類型的用戶）1、終端

13、型作業(yè)用戶2、短批處理作業(yè)用戶3、長批處理作業(yè)用戶11、 死鎖、產(chǎn)生死鎖原因、必要條件（P103）死鎖是指兩個或多個進(jìn)程由于資源競爭而造 成的一種僵局，若無外力作用，這些進(jìn)程將永遠(yuǎn)無 法向前推進(jìn)。產(chǎn)生死鎖的原因：1. 競爭資源（可剝奪和非剝奪性資源、競爭 非剝奪性資源、競爭臨時(shí)性資源）2. 進(jìn)程推進(jìn)順序非法（請求和釋放資源的順 序不當(dāng)）必要條件：1. 互斥條件：進(jìn)程間必須互斥使用某些資源 才可能產(chǎn)生死鎖。2. 請求保持條件：進(jìn)程已經(jīng)占有至少一個資 源，但又提出了新的資源請求。3. 不剝奪條件：進(jìn)程已經(jīng)獲得的資源不能被 剝奪。4. 環(huán)路等待條件：在發(fā)生死鎖時(shí)，必然存在一個進(jìn)程一一資源環(huán)形鏈。12

14、、 處理死鎖的基本方法（P105）1. 預(yù)防死鎖：通過設(shè)置某些限制條件，破壞 四個必要條件中的一個或幾個 。該方法比較簡單， 但由于限制條件過于嚴(yán)格，往往導(dǎo)致系統(tǒng)資源利用 率和吞吐量低。2. 避免死鎖：不需事先預(yù)防，但在 資源的動 態(tài)分配時(shí)，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)， 從而避免死鎖。該方法比較難于實(shí)現(xiàn)，但往往可獲 得較高資源利用率和系統(tǒng)吞吐量。3. 死鎖的檢測與解除：允許系統(tǒng)產(chǎn)生死鎖， 但能及時(shí)檢測出來，并通過某些措施解除。該方法 實(shí)現(xiàn)難度最大，但往往可獲得較好的資源利用率和 系統(tǒng)吞吐量。13、 預(yù)防死鎖的方法 （P106）預(yù)防死鎖的方法是使四個必要條件中的第2、3、4個條件不能成立，

15、來避免發(fā)生死鎖。至于必要 條件1,因?yàn)樗怯稍O(shè)備固有性能決定的，不僅不 能改變，還應(yīng)加以保證。（互斥條件破壞不了）1. 摒棄“請求和保持”條件：資源靜態(tài)分配2. 摒棄“不剝奪”條件：資源的動態(tài)分配3. 摒棄“環(huán)路等待”條件：資源有序分配14、安全狀態(tài) （P107）所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序（P1, P2,，Pn）（稱P1, P2,Pn序列為安全序列），來為每個進(jìn)程Pi分配其所需資源，直 至滿足每個進(jìn)程對資源的 最大需求，使每個進(jìn)程都 可順利地完成。如果系統(tǒng)無法找到這樣一個安全序 列，則稱系統(tǒng)處于不安全狀態(tài)。15、銀行家算法P（109 ）16、死鎖定理 （P113）S狀態(tài)是死鎖的 充

16、分條件 是，當(dāng)且僅當(dāng)S狀態(tài) 的資源分配圖是不可完全簡化的。該充分條件被稱 為死鎖定理第四章 存儲器管理1、程序裝入的方式（P119）1. 絕對裝入方式：完全按照目標(biāo)程序中所給 定的地址裝入內(nèi)存，即目標(biāo)程序中使用的是絕對地 址。該絕對地址 既可在編譯或匯編是給岀，也可由 程序員直接賦予。2. 可重定位裝入方式：通常是把在裝入時(shí)對目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位。又因?yàn)榈刂纷儞Q通常是在裝入時(shí)一次完成的，以后 不再改變，故稱為靜態(tài)重定位3. 動態(tài)運(yùn)行時(shí)裝入方式：在這種方式下動態(tài) 運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并 不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址， 而是把這種地址轉(zhuǎn)換推遲

17、到程序真正要執(zhí)行時(shí)才 進(jìn)行。因此，裝入內(nèi)存后的所有地址都仍是相對 地址。顯然為使指令的執(zhí)行不受影響，進(jìn)行這種 地址的動態(tài)轉(zhuǎn)換，就必須有專門的硬件機(jī)構(gòu)解決2、 重定位、靜態(tài)重定位、動態(tài)重定位（P119）重定位：我們把裝入時(shí)對目標(biāo)程序中的指令地 址和數(shù)據(jù)地址的修改過程稱為重定位。靜態(tài)重定位：如果重定位是在裝入時(shí)由裝入程 序一次性完成的，則稱為靜態(tài)重定位。動態(tài)重定位：在這種方式下動態(tài)運(yùn)行時(shí)的裝入 程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入 模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地 址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。3、 內(nèi)存的連續(xù)分配方式有哪些？（P121）1. 單一連續(xù)分配（單道）2. 固

18、定分區(qū)分配3. 動態(tài)（可變式）分區(qū)分配4. 可重定位分區(qū)分配4、 動態(tài)分區(qū)分配算法（P123）1. 首次適應(yīng)算法2. 循環(huán)首次適應(yīng)算法3. 最佳適應(yīng)算法4. 最壞適應(yīng)算法5. 快速適應(yīng)算法5、對換技術(shù) （P129）對換技術(shù)，是指把內(nèi)存中 暫時(shí)不能運(yùn)行 的進(jìn)程 或者暫時(shí)不用的程序和數(shù)據(jù)調(diào)岀到外存上， 以便騰 岀足夠的內(nèi)存空間， 再把已具備運(yùn)行條件的進(jìn)程 或 進(jìn)程所需的程序和數(shù)據(jù) 調(diào)入內(nèi)存的方法。6、 緊湊或拼接技術(shù)（P127）緊湊技術(shù)，是指通過移動內(nèi)存中作業(yè)的位置，把原 先分散的小分區(qū)拼接成一個大分區(qū)的方法。在每次 拼接后，都必須對移動了的程序或數(shù)據(jù)進(jìn)行重定位7、基本分頁管理原理、地址變換過程P

19、（ 130）8、分段系統(tǒng)的基本原理、地址變換過程P（136 ）9、 分頁與分段的主要區(qū)別（P138）1. 頁是信息的物理單位，分頁是為了實(shí)現(xiàn)離 散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存利用率，分頁是由于系統(tǒng)管理的需要而不是用戶的需 要。段則是信息的邏輯單位，分段的目的是為了能 更好地滿足用戶的需要。2. 頁的大小固定且由系統(tǒng)決定 ；而段的長度 卻不固定，取決于用戶所編寫的程序。3. 分頁的作業(yè)地址空間是一維的，即單一的線性地址空間；而分段的作業(yè)地址空間則是二維的。10、 虛擬存儲器的定義、特征（P143）定義：虛擬存儲器就是僅把作業(yè)的一部分裝入 內(nèi)存便可運(yùn)行的存儲器系統(tǒng)，具體說就是指具有請 求

20、調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進(jìn) 行擴(kuò)充的一種存儲器系統(tǒng)。特性：1. 離散性：即非連續(xù)性，這是實(shí)現(xiàn)虛擬存儲 器管理技術(shù)的前提；2. 多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存；3. 對換性：允許在作業(yè)運(yùn)行過程中換入、換 岀；4. 虛擬性：能夠從邏輯上擴(kuò)充內(nèi)存容量。11、 頁面置換算法：計(jì)算缺頁次數(shù)、置換次 數(shù)、缺頁率、置換率P（150 ）第五章設(shè)備管理1、設(shè)備管理的對象：設(shè)備、設(shè)備控制器、通道2、I/O控制方式及發(fā)展宗旨（P167）I/O系統(tǒng)是用于實(shí)現(xiàn)數(shù)據(jù)的輸入，輸岀及數(shù)據(jù) 存儲的系統(tǒng)I/O控制方式：1. 程序I/O方式（忙等待方式）2. 中斷驅(qū)動I/O方式3. 直接存儲器訪問DMA空制方式

21、4. I/O通道控制方式發(fā)展宗旨：盡量較少主機(jī)對I/O控制的干預(yù)，把主機(jī)從繁 雜的I/O控制事務(wù)中解脫岀來，以便更多的去完成 數(shù)據(jù)處理任務(wù)。3、 緩沖引入的原因（P 仃 2）1. 緩和CPU與 I/O設(shè)備間速度不匹配的矛盾。2. 減少對CPU的中斷頻率， 放寬對CPU中斷 響應(yīng)時(shí)間的限制。3. 提高CPU和 I/O設(shè)備之間的并行性。4、設(shè)備獨(dú)立性應(yīng)用程序獨(dú)立于具體使用的物理設(shè)備叫設(shè)備 獨(dú)立性，也稱為設(shè)備無關(guān)性。5、SPOOLING理、組成、特點(diǎn)、共享打印機(jī)原理（P190）SPOOLING原理：在聯(lián)機(jī)情況下實(shí)現(xiàn)的外圍操 作與CPU對數(shù)據(jù)的處理同時(shí)進(jìn)行，稱為假脫機(jī)操作， 又叫 Spooling 。

22、Spooling系統(tǒng)的組成：1. 輸入井和輸岀井2. 輸入緩沖區(qū)和輸出緩沖區(qū)（為了緩和 CPU 與磁盤之間速度不匹配的矛盾）3. 輸入進(jìn)程和輸岀進(jìn)程4. 請求打印隊(duì)列SPOOLing系統(tǒng)的特點(diǎn)：1. 提高了 I/O的速度。2. 將獨(dú)占設(shè)備改造為共享設(shè)備。3. 實(shí)現(xiàn)了虛擬設(shè)備功能。共享打印機(jī)原理：共享打印機(jī)技術(shù)已被廣泛地用于多用戶系統(tǒng) 和局域網(wǎng)絡(luò)中。當(dāng)用戶進(jìn)程請求打印輸岀時(shí)，SPOOLing系統(tǒng)同意為它打印輸出， 但并不真正立 即把打印機(jī)分配給該用戶進(jìn)程， 而只為它做兩件 事：1. 由輸岀進(jìn)程在輸岀井中為之申請一個空閑磁盤塊區(qū)，并將要打印的數(shù)據(jù)送入其中；2. 輸岀進(jìn)程再為用戶進(jìn)程申請一張空白的用

23、戶請求打印表，并將用戶的打印要求填入其中，再將該表掛到請求打印隊(duì)列上。6、 磁盤訪問時(shí)間包括什么？（ P193）1. 尋道時(shí)間Ts2. 旋轉(zhuǎn)延遲時(shí)間Tt3. 傳輸時(shí)間Tt7、磁盤調(diào)度算法：計(jì)算平均尋道長度P（194 ）第六章文件管理1、文件文件是指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和無結(jié)構(gòu) 文件兩種。在有結(jié)構(gòu)的文件中，文件由若干個相關(guān) 記錄組成；而無結(jié)構(gòu)文件則被看成是一個字符流。 文件在文件系統(tǒng)中是一個最大的數(shù)據(jù)單位，它描述 了一個對象集。2、 文件的邏輯結(jié)構(gòu)及分類（P208）文件的邏輯結(jié)構(gòu)分為兩大類：1. 有結(jié)構(gòu)文件：即記錄式文件；記錄的長度 分為定長記錄和變

24、長記錄2. 無結(jié)構(gòu)文件：即流式文件（被看成字符流）。3、 文件的物理結(jié)構(gòu)及分類（P213）文件的物理結(jié)構(gòu)直接與外存分配方式有關(guān)?？?分為：1. 連續(xù)分配方式時(shí)的順序式文件結(jié)構(gòu)。2. 鏈接分配方式時(shí)的鏈接式文件結(jié)構(gòu)。3. 索引分配方式時(shí)的索引式文件結(jié)構(gòu)。4、文件外存分配方式（P213）1. 連續(xù)分配。2. 鏈接分配。3. 索引分配。5、文件目錄，目錄查詢方式文件目錄是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識系統(tǒng)中的 文件及其物理地址，供檢索時(shí)使用，是 文件數(shù)據(jù)塊 的有序集合。目錄查詢方式：1. 線性檢索法2. Hash方法6、目錄管理的要求1. 實(shí)現(xiàn)“按名存取”。2. 提高對目錄的檢索速度。3. 文件共享。4.

25、允許文件重名。7、文件控制塊為了能對一個文件進(jìn)行正確的存取，必須為文 件設(shè)置用于描述和控制的數(shù)據(jù)結(jié)構(gòu)，稱之為文件控 制塊（包含三大信息：基本信息、存取控制信息、 使用信息）8、索引節(jié)點(diǎn)概念，為什么引入索引節(jié)點(diǎn)？索引節(jié)點(diǎn)：采用將文件名與文件描述信息分開 的辦法，將文件描述信息單獨(dú)形成一個數(shù)據(jù)結(jié)構(gòu)叫 索引節(jié)點(diǎn)簡稱i節(jié)點(diǎn)。引入原因：由于檢索目錄文件只用到文件名， 即用不到該文件的描述信息，且在檢索目錄時(shí)索引 節(jié)點(diǎn)不用調(diào)入內(nèi)存，從而大大節(jié)省了系統(tǒng)開銷。9、文件存儲空間的管理方法1. 空閑表法2. 空閑鏈表法3. 位示圖法4. 成組鏈接法（空閑表法和空閑鏈表法都不 適合大型文件系統(tǒng)）10、成組鏈接法的空

26、閑盤塊組織、分配回收100空閑盤塊號棧S.freeTOT011003011400399300'40029939920130198 20299201(1) 順序掃描位示圖，從中找出一個或一組其 值為“ 0”的二進(jìn)制位(“0”表示空閑時(shí))。(2) 將所找到的一個或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進(jìn)制位，位于位示圖的第 i行、第j列，則其 相應(yīng)的盤塊號應(yīng)按下式計(jì)算：b=n(i-1)+j式中，n代表每行的位數(shù)。(3) 修改位示圖，令 mapi,j =1?？臻e盤塊的分配與回收：當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí)，首先檢查空閑盤塊號棧是否上鎖， 如未上鎖，便從棧頂取

27、出一空閑盤塊號，將與之對 應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。若該盤塊號已是棧底， 即S.free(0)，這是當(dāng)前棧中最后一個可分配的盤塊 號。由于在該盤塊號所對應(yīng)的盤塊中記有下一組可 用的盤塊號，因此，須調(diào)用磁盤讀過程，將棧底盤塊號所對應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊 號棧的內(nèi)容，并把原棧底對應(yīng)的盤塊分配岀去。在系統(tǒng)回收空閑盤塊時(shí)，將回收盤塊 的盤塊號記入空閑盤塊號棧的頂部，并執(zhí)行空閑盤 塊數(shù)加1操作。當(dāng)棧中空閑盤塊號數(shù)目已達(dá)100時(shí)，表示棧已滿，便將現(xiàn)有棧中的100個盤塊號，記入新回收的盤塊中，再將其盤塊號作為新棧底。第七章操作系統(tǒng)接口1、操作系統(tǒng)接口分為用戶接口和程序接口(概念

28、)。用戶接口包括命令接口、圖形接口等。2、程序接口程序接口是由一組系統(tǒng)調(diào)用組成。系統(tǒng)調(diào)用是 在OS核心設(shè)置的一組實(shí)現(xiàn)系統(tǒng)功能的子程序(過 程)。第八章網(wǎng)絡(luò)操作系統(tǒng)1、網(wǎng)絡(luò)操作系統(tǒng)的功能數(shù)據(jù)通信，網(wǎng)絡(luò)資源共享，應(yīng)用互操作，網(wǎng)絡(luò) 管理應(yīng)用互操作包括：信息互通性和信息互用性。在Internet 下，主要利用TCP/IP協(xié)議實(shí)現(xiàn)信息的 互通性。2、網(wǎng)絡(luò)操作系統(tǒng)提供的服務(wù)：域名服務(wù)，目錄服務(wù)， Web服務(wù)3、目錄管理記錄了網(wǎng)絡(luò)中的三大資源物理設(shè)備，網(wǎng)絡(luò)服務(wù)和用戶的名字，屬性和位1、進(jìn)程同步互斥問題*信號量類型：整型(忙等待)、記錄型、AND型、一般信號量集解決的問題：1、描述前趨關(guān)系：根據(jù)前趨圖，各邊分

29、別設(shè)置信號量，初值為0;若某邊從某節(jié)點(diǎn)岀發(fā)，在此節(jié)點(diǎn)操作后，對該邊對應(yīng)信號量作signal操作；若某邊指向某節(jié)點(diǎn)，在此節(jié)點(diǎn)操作前，對該邊對應(yīng)信號量作wait錯作；Vara,b,c,d,e,f,g,h,i,j:semaphore:=0,0,0,0,0,0,0,0;beginparbeginbegin S1; signal(a); signal(b); end;begin wait(a); S2; signal(c);signal(d); end;beginwait(b);S3;signal(e);signal(f); end;begin wait(c); S4;signal(g); end;be

30、gin wait(d); S5;signal(h); end;begin wait(e); S6; signal(i); end;begin wait(f); S7; signal(j); end;begin wait(g); wait(h); wait(i); wait(j);S8; end;parendend2、進(jìn)程互斥問題（資源共享）*根據(jù)臨界資源的種類設(shè)置信號量 的個數(shù)，初值為各臨界資源的可用數(shù)量；*在訪問臨界資源前，對對應(yīng)信號量作wait操作；在訪問結(jié)束后作 signal操 作，即將臨界區(qū)放在wait和signal之間。3、進(jìn)程同步（相互合作）*為同步雙方設(shè)置各自的信號量，初 值為其

31、初始狀態(tài)可用的資源數(shù)（故該信號 量稱為資源信號量或私有信號量）；*同步雙方任一進(jìn)程在進(jìn)入臨界區(qū) 之前，應(yīng)先對自己的信號量執(zhí)行wait（己方信號量 ）操作，以測試是否有自己可 用的資源。若有資源可用，則進(jìn)入臨界區(qū)， 否則阻塞；同步雙方任一進(jìn)程離開臨界區(qū)后，應(yīng)對合作 方（對方）的信號量執(zhí)行signal（對方信號量 ）操 作，以通知（若對方處于阻塞狀態(tài)，則喚醒它 ）對方 已有資源可用（對方已可進(jìn)入臨界區(qū)）。*有一個閱覽室，共有100個座位， 讀者進(jìn)入時(shí)必須先在一張登記表上登記， 該表為每一個座位列一表目，包括座號和 讀者姓名等，讀者離開時(shí)要消掉登記的信 息，試用wait,signal原語描述各個進(jìn)程

32、之間的同步互斥關(guān)系。Var s,mutax: semaphore:=100,1;Reader:BeginRepeatWait（s）;Wait（mutex）;登記；Signal（mutex）;閱覽圖書；Wait（mutex）;取消登記；Signal(mutex);Signal(s);Until fasleend桌上有一個盤子，每次只能放一個水果，爸爸 專向盤中放蘋果，媽媽專向盤中放橘子，兒子專等 吃盤里的桔子，女兒專等吃盤里的蘋果。只要盤子 空，爸爸媽媽可向盤中放水果，僅當(dāng)盤中有自己需 要的水果時(shí)，兒子或女兒可從中取岀，請給岀他們 四人之間的同步關(guān)系程序。VAR s,so,sa:semaphor

33、e :=1,0,0;/s 表示盤 空，so表示橘子，sa表示蘋果。parbeginFather:beginrepeatwait(s);put apple(); signal(sa);until falseendMother:beginrepeatwait(s);put orange(); signal(so);until falseendSon:beginrepaetwait(so); eat orange(); signal(s); until falseenddaughter:beginrepeatwait(sa);eat apple(); signal(s); until falseen

34、dparend2 設(shè)公共汽車上有一位司機(jī)和一位售票員， 它們的活動如下：司機(jī)：啟動車輛，行車，到站停車，售票員：售票；到站開門，關(guān)門請分析司機(jī)與售票員之間的同步關(guān)系，如何用PV操作實(shí)現(xiàn)。答：為了安全起見，顯然要求：關(guān)車門后才能 啟動車輛；到站停車后才能開車門。所以司機(jī)和售 票員在到站、開門、關(guān)門、啟動車輛這幾個活動之 間存在著同步關(guān)系。用兩個信號量S1、S2分別表示可以開車和可以開門，S1的初值為1，S2的初值 為0。用PV操作實(shí)現(xiàn)司機(jī)進(jìn)程和售票員進(jìn)程同步的 算法描述如下：司機(jī)：P (S1)；啟動車輛 ；正常行車；到站停車；V (S2)；售票員：P(S2);開車門；關(guān)車門；V ( S1)；生產(chǎn)

35、者消費(fèi)者問題三個進(jìn)程兩個緩沖區(qū)倆倆合作(下頁)；設(shè)自行車生產(chǎn)車間有兩個貨架，貨架A可以存放8個車架，貨架B可以存放20個車輪；又設(shè)有4 個工人，他們的活動是重復(fù)勞動，分別為：工人1加 工一個車架放入貨架 A中；工人2、3分別加工車 輪放入貨架B中(每人每次放入1個車輪)；工人4 從貨架A中取一個車架，再從貨架B中取兩個車輪， 組裝成一輛自行車。試用PV操作實(shí)現(xiàn)四個工人的合作1、系統(tǒng)中有是三個進(jìn)程GET PRO和PUT共用兩個緩沖區(qū)BUF1和BUF2假設(shè)BUF1中最多可放 8個信息，BUF2中最多可放5個信息。GET®程負(fù) 責(zé)不斷地將信息送入 BUF1中，PRO進(jìn)程負(fù)責(zé)從BUF1 中取

36、岀信息進(jìn)行處理，并將處理結(jié)果送到BUF2中，PUT進(jìn)程負(fù)責(zé)從 BUF2中讀取結(jié)果并輸出。試用 wait、signal 原語(P、V操作)實(shí)現(xiàn) GET PRO PUT進(jìn)程之間的同步算法。1、 var : mutex1，mutex2，empty1，empty2, full11 ，full2 : =1，1，8，5，0，0；GET:begin (repeatwait(empty1);wait(mutex1);送入BUF1;signal(mutex1);signal(full);until falseendPRO:beginrepeatwait(full1);wait(mutex1);從BUF1中取信息

37、加工；signal(mutex1);signal(empty1);wait(empty2);wait(mutex2);將加工后的信息放入 BUF2;signal(mutex2);signal(full2);until falseendPUT:beginrepeatwait(full2);wait(mutex2);從BUF2中取信息輸出；signal(mutex2);signal(empty2);until falseend【分析】設(shè)置資源信號量和互斥信號量如下： 信號量 Aempty表示貨架 A的空位數(shù)，其初值為8 ； 信號量Afull表示貨架A上存放的車架數(shù)，其初值為 0; 信號量Bempt

38、y表示貨架B的空位數(shù)，其初值為20 ； 信號量Bfull表示貨架B上存 放的車輪數(shù)，其初值為 0; 信號量mutex用于互斥(初值 為1 )。Var Aempty,Afull,Bempty,Bfull,mutex :semaphore;Aempty.value:=8;Afull.value:=O;Bempty.value:=20;Bfull.value:=0mutext.value:=1;wheelcount:integer:=0;Beginparbeginworker1:beginrepeat生產(chǎn)一個車架；wait(Aempty);/看看貨架A上是否有空位置車架放到貨架A上;signal(A

39、full);/貨架 A上的車架數(shù)增1，并通知工人4until false;endWorker2 ， 3:beginrepeat生產(chǎn)一個車輪；wait(Bempty);/看看貨架 B上是否有空位置wait(mutex);將車輪放到貨架B 上;signal(mutex);signal(Bfull);/貨架B上的車輪數(shù)增1,并通知工人4until false;endWorker4:beginrepeatwait(Afull);wait(Bfull);wait(Bfull);取一個車架和兩個車輪；signal(Aempty);signal(Bempty);signal(Bempty);組裝一輛自行車;

40、 until false end parendend哲學(xué)家就餐問題(非死鎖算法 ) 至多允許4個哲學(xué)家同時(shí)取左邊的筷子， 這樣能至少保證一個哲學(xué)家能就餐，并在 用畢后釋放他用過的兩只筷子，從而使更 多的哲學(xué)家能夠進(jìn)餐。(請學(xué)生考慮算法 的描述) 僅當(dāng)哲學(xué)家左右兩只筷子均可用時(shí)，才允 許他拿起筷子進(jìn)餐。(用AND言號量機(jī)制) 規(guī)定奇數(shù)號哲學(xué)家先拿左邊筷子，然后再 拿右邊筷子；而偶數(shù)號哲學(xué)家先拿右邊筷 子，然后再拿左邊筷子。(1 ) var chopstick:array0, ，4 ofsemaphore := 1,1,1,1,1;Sm:semaphore := 4;beginrepeatwait

41、(Sm);wait(chopsticki);wait(chopstick(i+1) mod 5);eat;signal(chopsticki);signal(chopstick(i+1) mod 5);signal(Sm);think;until falseEnd(2)var chopstick:array0,，4 ofsemaphore := 1,1,1,1,1;beginrepeatswait(chopsticki, chopstick(i+1)mod 5);eat;ssignal(chopsticki, chopstick(i+1)mod 5);think;until falseend(

42、3) var chopstick:array0, ,4 of semaphore := 1,1,1,1,1;beginrepeatif i mod 2=0then beginwait(chopsticki);wait(chopstick(i+1) mod 5);end;else beginwait(chopstick(i+1) mod 5);wait(chopsticki);end;eat;signal(chopsticki);signal(chopstick(i+1) mod 5);think;until falseEnd讀者寫者問題及變形-獨(dú)木橋問題假定有如下獨(dú)木橋問題：過橋時(shí)，同一方向的

43、 行人可連續(xù)過橋，當(dāng)某一方有人過橋時(shí)，另一方向 的行人必須等待；當(dāng)某一方向無人過橋時(shí)，另一方 向的行人可以過橋。試用信號量機(jī)制解決。答案：(1)將獨(dú)木橋的兩個方向分別標(biāo)記為A和B。用整型變量 countA和countB分別 表示A、 B方向上已在獨(dú)木橋上的行人數(shù)。初值為 0。需要 設(shè)置三個初值都為1的互斥信號量：SA用來實(shí)現(xiàn)對 countA的互斥訪問，SB用來實(shí)現(xiàn)對countB的互斥 訪問，mutex用來實(shí)現(xiàn)對獨(dú)木橋的互斥使用。(2)A方向行人過橋：Begin P(SA);countA=countA+1;if (countA= =1)P(mutex); V(SA);過橋；(SA);countA

44、=countA-1;if(countA= =0)V(mutex);V(SA);EndB方向行人過橋：Begin P(SB); countB=countB+1;if (countB= =1) P(mutex);V(SB);過橋；P(SB);countB=countB-1;if(countB= =0)V(mutex);V(SB);End是從后備隊(duì)列中選擇一個或若干個估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先 （SPF）調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn) 行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即 執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放處理機(jī)調(diào)度算法：1.先來先服務(wù)調(diào)度算法

45、該算法既可用于作業(yè)調(diào)度又可用于進(jìn)程調(diào)度， 用于前者時(shí)，每次調(diào)度都是從外存后備隊(duì)列中選擇 一個或多個作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資 源、創(chuàng)建進(jìn)程，然后將新建進(jìn)程放入就緒隊(duì)列。用 于后者時(shí)，每次調(diào)度時(shí)從就緒隊(duì)列中選擇一個最先進(jìn)入該隊(duì)列的進(jìn)程，把處理機(jī)分配給它，使其運(yùn)行1行時(shí)間-AA1011B11001iaiICO1C11011QGimD310&1021S9棄處理機(jī)時(shí)，再重新調(diào)度A B C D E平均D 123443524FCFS完矗時(shí)間4712 11*610 11149J 225,052-S佝1918613跚對間i S 16 S 9A1 2.S7 3.1 .5 K. 252.1FCFS

46、算法的特點(diǎn)如下：?利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）? 利于CPU繁忙型作業(yè)（進(jìn)程）， 而不利于I / O型繁忙作業(yè)（進(jìn)程）?作業(yè)平均等待時(shí)間長?系統(tǒng)吞吐量不咼2. 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJ（P）F，是指對短作業(yè) 或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè) 調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先 （SJF）的調(diào)度算法，該算法的特點(diǎn)如下：?能有效降低作業(yè)平均等待時(shí)間?能提高系統(tǒng)吞吐量?對長作業(yè)不利?未考慮作業(yè)的緊迫程度，因而不能 保證緊迫型作業(yè)或進(jìn)程得到及時(shí)處理。由于作業(yè)或進(jìn)程的長短是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定，因而不免存在差異。3. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法1）

47、非搶占式優(yōu)先權(quán)算法2）搶占式優(yōu)先權(quán)算法【例3-3】設(shè)有一個最多可有兩道作業(yè)同時(shí)裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計(jì)算型作業(yè)序列(表中所列進(jìn)程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越 高):作業(yè)名到達(dá)吋間估計(jì)坯行時(shí)間進(jìn)程優(yōu)先叛JLio： in20分鐘5.1210:21)30分鐘3J31 (L3U罵分鐘410:502D分鐘6調(diào)度算法，進(jìn)程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算 法，今有如下純計(jì)算型作業(yè)序列(假設(shè)表中所列進(jìn) 程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高)：柞業(yè)名到這時(shí)間估計(jì)運(yùn)行時(shí)間進(jìn)程優(yōu)先數(shù)JI10:1020分鐘5J210:203巧分鐘4J410

48、:506(1) 列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間(2) 計(jì)算平均周轉(zhuǎn)時(shí)間。(1) 列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間(2) 計(jì)算平均周轉(zhuǎn)時(shí)間。作業(yè)塔提交時(shí)間進(jìn)人時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間J11010： 10ti： on血分鐘A210； 2010t 20IV： 5030分鐘J31Q± 3011： 00Lb 25頤分鐘34ID： 5010t 5011：斗 §3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1.時(shí)間片輪轉(zhuǎn)法3) .高響應(yīng)比優(yōu)先調(diào)度算法(只使用作業(yè)調(diào)度)優(yōu)先權(quán)=(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí) 間=響應(yīng)時(shí)間/要求服務(wù)時(shí)間=Rp算法特點(diǎn)：(1) 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈

49、短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因 而它實(shí)現(xiàn)的是先來先服務(wù)。(3)對于長作業(yè)，作業(yè) 的優(yōu)先級可以隨等待時(shí)間的增加而提高，當(dāng)其等待 時(shí)間足夠長時(shí)，其優(yōu)先級便可升到很高，從而也可獲得處理機(jī)。【例3-4】設(shè)有一個最多可有兩道作業(yè)同時(shí)裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應(yīng)比優(yōu)先平均周轉(zhuǎn)時(shí)間=(50+30+55+55)/4=47.5( 分鐘)作業(yè)名到達(dá)吋間調(diào)入時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間JI11):1010:1011:25洱分鐘J210:2010:2010:50卻分鐘J310:3010:5(111:15鮎分

50、鐘J411:151J:45粘分鐘平均周轉(zhuǎn)時(shí)間=(75+30+45+55)/4=51.25( 分鐘)利用銀行家算法避免死鎖1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1) 可利用資源向量 Available 。這是一個含有 m 個元素的數(shù)組，其中的每一個元素代表一類可利用 的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收 而動態(tài)地改變。(2) 最大需求矩陣Max=這是一個nXm的矩陣，它 定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對 m類資源 的最大需求。分配矩陣Allocation 。這也是一個nXm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的費(fèi)源數(shù)" 需

51、求矩陣Need這也是一個nx m的矩陣，用 以表示每一個進(jìn)程尚需的各類資源數(shù)。Need i,j =Max i,j -Allocation i,j 2. 銀行家算法設(shè)Requesti是進(jìn)程P的請求向量，女口果Request i : j =K，表示進(jìn)程 P需要K個R類型 的資源。當(dāng)R發(fā)岀資源請求后，系統(tǒng)按下述步驟進(jìn) 行檢查：(1) 如果 Requesti jw Need i,j ，便轉(zhuǎn)向步驟2;否則認(rèn)為岀錯，因?yàn)樗枰馁Y 源數(shù)已超過它所宣布的最大值。(2)如果 Request i j < Availablej ，便轉(zhuǎn)向步驟(3);否則， 表示尚無足夠資源，P須等待。(3)系統(tǒng)試探著把資源

52、分配給進(jìn)程P，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available j ： =Available j -Request ij ;Allocation i,j : =Allocation i,j +Requesti j ;Need i,j : =Need i,j -Request i j ;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配 后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資 源分配給進(jìn)程Pi，以完成本次分配；否則， 將本 次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓 進(jìn)程Pi等待。3. 安全性算法(1)設(shè)置兩個向量：工作向量Work:它表 示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù) 目，它含有 m個元素，在執(zhí)行安全算法開始時(shí)， Work