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

1、第一章 引論1、操作系統(tǒng)定義（P1）操作系統(tǒng)是配置在計(jì)算機(jī)硬件上的第一層軟件，是對(duì)硬件系統(tǒng)的首次擴(kuò)充。是一組控制和管理計(jì)算機(jī)硬件和軟件資源、合理地對(duì)各類作業(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)了對(duì)計(jì)算機(jī)資源的抽象3、 推動(dòng)操作系統(tǒng)發(fā)展的主要?jiǎng)恿Γ≒4）1. 不斷提高計(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)吞吐量大缺點(diǎn)：1. 平

2、均周轉(zhuǎn)時(shí)間長(zhǎng)2. 無交互能力（單道、多道都是）5、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)特征的比較（P12）1. 多路性（實(shí)時(shí)系統(tǒng)的多路性主要表現(xiàn)在系統(tǒng)周期性地對(duì)多路信息的采集、以及對(duì)多個(gè)對(duì)象或多個(gè)執(zhí)行機(jī)制進(jìn)行控制。 分時(shí)系統(tǒng)中的多路性則和用戶有關(guān)，時(shí)多時(shí)少。）2. 獨(dú)立性 3. 及時(shí)性:（實(shí)時(shí)系統(tǒng)對(duì)及時(shí)性的要求更嚴(yán)格,實(shí)時(shí)控制系統(tǒng)以控制對(duì)象要求的開始截止時(shí)間或完成截止時(shí)間來確定。 ）4. 交互性:實(shí)時(shí)系統(tǒng)的交互性僅限于訪問某些專用服務(wù)程序。 5. 可靠性:實(shí)時(shí)系統(tǒng)對(duì)可靠性的要求更高,否則經(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ù)、虛擬存儲(chǔ)器技術(shù)）4. 異步性（進(jìn)程的異步性：進(jìn)程是以人們不可預(yù)知的速度向前推進(jìn)的）7、操作系統(tǒng)的主要功能（P18）1. 處理機(jī)管理功能（進(jìn)程控制（1、進(jìn)程互斥方式：進(jìn)程或者線程在對(duì)臨界資源進(jìn)行訪問時(shí)，應(yīng)采取互斥方式；2、進(jìn)程同步方式：相互合作去完成共同任務(wù)的諸進(jìn)程貨線程）、進(jìn)程通信、調(diào)度（作業(yè)調(diào)度、進(jìn)程調(diào)度）2. 存儲(chǔ)器管理功能 （內(nèi)存分配、內(nèi)存保護(hù)、地址映射、內(nèi)存擴(kuò)充）3. 設(shè)備管理功能（緩沖管理、設(shè)備分配、設(shè)備處理）4. 文件管理功能（文件存儲(chǔ)

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. 非封閉性：多個(gè)程序共享系統(tǒng)資源，因而其狀態(tài)有多個(gè)程序改變，從而失去封閉性。3. 不可再現(xiàn)性：封閉性的失去

5、必然導(dǎo)致不可再現(xiàn)性。3、進(jìn)程及其特征（P37）進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。進(jìn)程是程序的一次執(zhí)行進(jìn)程實(shí)體：由程序段、相關(guān)的數(shù)據(jù)段和PCB構(gòu)成特征：結(jié)構(gòu)特征動(dòng)態(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) （典型事例：請(qǐng)求I/O、申請(qǐng)緩沖空間等）5、 引入掛起狀態(tài)的原因（P39）1. 終端用戶的請(qǐng)求 2. 父進(jìn)程請(qǐng)求 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. 使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。或者說，OS是根據(jù)PCB來對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。2. PCB是進(jìn)程存在與否的唯一標(biāo)志,隨著進(jìn)程的建立而建立,隨著進(jìn)程的撤消而撤消。創(chuàng)建進(jìn)程就是創(chuàng)建PCB。8、 進(jìn)程之間的兩種制約關(guān)系（P48）1. 間接制約競(jìng)爭(zhēng)資源進(jìn)程互斥2. 直接制約相互合作進(jìn)程同步9、 臨界資源（P48）OS中把一次只

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

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

9、基本單位3. 可并發(fā)執(zhí)行4. 共享進(jìn)程資源第三章 處理機(jī)調(diào)度與死鎖1、高級(jí)調(diào)度（P84）又稱為作業(yè)調(diào)度。即從外存的后備隊(duì)列中選擇一個(gè)作業(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)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息2、 低級(jí)調(diào)度（P86）又稱進(jìn)程調(diào)度或短程調(diào)度，即從就緒隊(duì)列中選擇一個(gè)進(jìn)程進(jìn)入運(yùn)行狀態(tài)（非搶占方式、可搶占方式）。調(diào)度的對(duì)象是進(jìn)程（多批道處理、分時(shí)、實(shí)時(shí)三種類型的OS中都有）3、 中級(jí)調(diào)度（P87）中程調(diào)度為了提高內(nèi)存利用率和系統(tǒng)吞吐量（引入目的），為此，應(yīng)使那些暫

10、時(shí)不能運(yùn)行的進(jìn)程不再占用內(nèi)存資源，而將它們調(diào)至外存。適當(dāng)時(shí)機(jī)再將其調(diào)回內(nèi)存。這種調(diào)度稱為中級(jí)調(diào)度。4、 進(jìn)程調(diào)度的兩種方式（P86）1、非搶占方式（一旦給進(jìn)程分配處理機(jī)，一直讓他運(yùn)行下去，直到完成再把處理機(jī)分配給其他進(jìn)程）2、搶占方式（允許調(diào)度程序根據(jù)某些原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一個(gè)進(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í)間快、截止時(shí)間的保證、優(yōu)先權(quán)準(zhǔn)則）2. 面向系統(tǒng)的準(zhǔn)則（系統(tǒng)吞吐量高、處理機(jī)利用率好、

11、各類資源的平衡利用）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í)間8、針對(duì)各種調(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、多級(jí)反饋隊(duì)列調(diào)度算法的原理、性能該算法用于進(jìn)程調(diào)度，主要是為解決前面各種進(jìn)程調(diào)度算法存在的各種不同問題而設(shè)計(jì)的一種考慮綜合因素的調(diào)度算法。其思想如下：1、設(shè)置多個(gè)就緒隊(duì)列，不同隊(duì)列具有不同優(yōu)先級(jí)，第一個(gè)隊(duì)列優(yōu)先級(jí)最高，以后次之。給不同隊(duì)列分配不同大小的

12、時(shí)間片，第一個(gè)隊(duì)列最小，以后次之（皆為前者的二倍）。有的系統(tǒng)也將最后一級(jí)隊(duì)列不劃分時(shí)間片。2、當(dāng)有一個(gè)新進(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)前一級(jí)隊(duì)列為空時(shí)才調(diào)度下一級(jí)隊(duì)列中的進(jìn)程。算法采用搶占式調(diào)度策略。執(zhí)行的進(jìn)程在規(guī)定的時(shí)間片內(nèi)為執(zhí)行完畢，則進(jìn)入下一級(jí)隊(duì)列的隊(duì)尾，新進(jìn)程則進(jìn)入第一級(jí)隊(duì)列的隊(duì)尾。性能：（較好的性能，能滿足各種類型的用戶）1、終端型作業(yè)用戶2、短批處理作業(yè)用戶3、長(zhǎng)批處理作業(yè)用戶11、死鎖、產(chǎn)生死鎖原因、必要條件（P103）死鎖

13、是指兩個(gè)或多個(gè)進(jìn)程由于資源競(jìng)爭(zhēng)而造成的一種僵局，若無外力作用，這些進(jìn)程將永遠(yuǎn)無法向前推進(jìn)。產(chǎn)生死鎖的原因：1. 競(jìng)爭(zhēng)資源（可剝奪和非剝奪性資源、競(jìng)爭(zhēng)非剝奪性資源、競(jìng)爭(zhēng)臨時(shí)性資源）2. 進(jìn)程推進(jìn)順序非法（請(qǐng)求和釋放資源的順序不當(dāng)）必要條件：1. 互斥條件：進(jìn)程間必須互斥使用某些資源才可能產(chǎn)生死鎖。2. 請(qǐng)求保持條件：進(jìn)程已經(jīng)占有至少一個(gè)資源，但又提出了新的資源請(qǐng)求。3. 不剝奪條件：進(jìn)程已經(jīng)獲得的資源不能被剝奪。4. 環(huán)路等待條件：在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源環(huán)形鏈。12、處理死鎖的基本方法（P105）1. 預(yù)防死鎖：通過設(shè)置某些限制條件，破壞四個(gè)必要條件中的一個(gè)或幾個(gè)。該方法比較簡(jiǎn)單，但

14、由于限制條件過于嚴(yán)格，往往導(dǎo)致系統(tǒng)資源利用率和吞吐量低。2. 避免死鎖：不需事先預(yù)防，但在資源的動(dòng)態(tài)分配時(shí)，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖。該方法比較難于實(shí)現(xiàn)，但往往可獲得較高資源利用率和系統(tǒng)吞吐量。3. 死鎖的檢測(cè)與解除：允許系統(tǒng)產(chǎn)生死鎖，但能及時(shí)檢測(cè)出來，并通過某些措施解除。該方法實(shí)現(xiàn)難度最大，但往往可獲得較好的資源利用率和系統(tǒng)吞吐量。13、預(yù)防死鎖的方法（P106）預(yù)防死鎖的方法是使四個(gè)必要條件中的第2、3、4個(gè)條件不能成立，來避免發(fā)生死鎖。至于必要條件1，因?yàn)樗怯稍O(shè)備固有性能決定的，不僅不能改變，還應(yīng)加以保證。（互斥條件破壞不了）1. 摒棄“請(qǐng)求和保持”條件：資源靜態(tài)

15、分配2. 摒棄“不剝奪”條件：資源的動(dòng)態(tài)分配 3. 摒棄“環(huán)路等待”條件：資源有序分配14、安全狀態(tài)（P107） 所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1, P2, ，Pn)(稱P1, P2, , Pn序列為安全序列)，來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。 15、銀行家算法P( 109 )16、死鎖定理（P113）S狀態(tài)是死鎖的充分條件是，當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的。該充分條件被稱為死鎖定理第四章 存儲(chǔ)器管理1、程序裝入的方式（P119）1. 絕對(duì)裝入方式：完全

16、按照目標(biāo)程序中所給定的地址裝入內(nèi)存，即目標(biāo)程序中使用的是絕對(duì)地址。該絕對(duì)地址既可在編譯或匯編是給出，也可由程序員直接賦予。2.可重定位裝入方式：通常是把在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位 。又因?yàn)榈刂纷儞Q通常是在裝入時(shí)一次完成的，以后不再改變，故稱為靜態(tài)重定位3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式：在這種方式下動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此， 裝入內(nèi)存后的所有地址都仍是相對(duì)地址。 顯然為使指令的執(zhí)行不受影響，進(jìn)行這種地址的動(dòng)態(tài)轉(zhuǎn)換，就必須有專門的硬件機(jī)構(gòu)解決2、重定位、靜態(tài)重定位

17、、動(dòng)態(tài)重定位（P119）重定位：我們把裝入時(shí)對(duì)目標(biāo)程序中的指令地址和數(shù)據(jù)地址的修改過程稱為重定位。靜態(tài)重定位：如果重定位是在裝入時(shí)由裝入程序一次性完成的，則稱為靜態(tài)重定位。動(dòng)態(tài)重定位：在這種方式下動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。3、 內(nèi)存的連續(xù)分配方式有哪些？（P121）1. 單一連續(xù)分配（單道）2. 固定分區(qū)分配3. 動(dòng)態(tài)（可變式）分區(qū)分配4. 可重定位分區(qū)分配4、 動(dòng)態(tài)分區(qū)分配算法（P123）1. 首次適應(yīng)算法2. 循環(huán)首次適應(yīng)算法3. 最佳適應(yīng)算法4. 最壞適應(yīng)算法5. 快速適應(yīng)算

18、法5、 對(duì)換技術(shù)（P129）對(duì)換技術(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ù)，是指通過移動(dòng)內(nèi)存中作業(yè)的位置，把原先分散的小分區(qū)拼接成一個(gè)大分區(qū)的方法。在每次拼接后，都必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位7、 基本分頁管理原理、地址變換過程P( 130)8、 分段系統(tǒng)的基本原理、地址變換過程P( 136 )9、 分頁與分段的主要區(qū)別（P138）1. 頁是信息的物理單位，分頁是為了實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存利用率，分頁是由于系

19、統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，分段的目的是為了能更好地滿足用戶的需要。 2. 頁的大小固定且由系統(tǒng)決定；而段的長(zhǎng)度卻不固定， 取決于用戶所編寫的程序。3. 分頁的作業(yè)地址空間是一維的，即單一的線性地址空間； 而分段的作業(yè)地址空間則是二維的。10、 虛擬存儲(chǔ)器的定義、特征（P143）定義：虛擬存儲(chǔ)器就是僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行的存儲(chǔ)器系統(tǒng)，具體說就是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。特性：1. 離散性：即非連續(xù)性，這是實(shí)現(xiàn)虛擬存儲(chǔ)器管理技術(shù)的前提；2. 多次性：一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存；3. 對(duì)換性：允許在作業(yè)運(yùn)行過程中換

20、入、換出；4. 虛擬性：能夠從邏輯上擴(kuò)充內(nèi)存容量。11、 頁面置換算法：計(jì)算缺頁次數(shù)、置換次數(shù)、缺頁率、置換率P( 150 )第五章 設(shè)備管理1、設(shè)備管理的對(duì)象：設(shè)備、設(shè)備控制器、通道2、 I/O控制方式及發(fā)展宗旨（P167）I/O系統(tǒng)是用于實(shí)現(xiàn)數(shù)據(jù)的輸入，輸出及數(shù)據(jù)存儲(chǔ)的系統(tǒng)I/O控制方式：1. 程序I/O方式（忙等待方式）2. 中斷驅(qū)動(dòng)I/O方式3. 直接存儲(chǔ)器訪問DMA控制方式4. I/O通道控制方式發(fā)展宗旨：盡量較少主機(jī)對(duì)I/O控制的干預(yù)，把主機(jī)從繁雜的I/O控制事務(wù)中解脫出來，以便更多的去完成數(shù)據(jù)處理任務(wù)。3、 緩沖引入的原因（P172）1. 緩和CPU與I/O設(shè)備間速度不匹配的矛盾

21、。 2. 減少對(duì)CPU的中斷頻率， 放寬對(duì)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對(duì)數(shù)據(jù)的處理同時(shí)進(jìn)行，稱為假脫機(jī)操作，又叫Spooling。Spooling系統(tǒng)的組成：1. 輸入井和輸出井2. 輸入緩沖區(qū)和輸出緩沖區(qū)（為了緩和CPU與磁盤之間速度不匹配的矛盾）3.  輸入進(jìn)程和輸出進(jìn)程4. 請(qǐng)求打印隊(duì)列SPOOLing系統(tǒng)的特點(diǎn)：1. 提高了I/O的速

22、度。2. 將獨(dú)占設(shè)備改造為共享設(shè)備。 3. 實(shí)現(xiàn)了虛擬設(shè)備功能。共享打印機(jī)原理：共享打印機(jī)技術(shù)已被廣泛地用于多用戶系統(tǒng)和局域網(wǎng)絡(luò)中。 當(dāng)用戶進(jìn)程請(qǐng)求打印輸出時(shí)， SPOOLing系統(tǒng)同意為它打印輸出， 但并不真正立即把打印機(jī)分配給該用戶進(jìn)程， 而只為它做兩件事： 1. 由輸出進(jìn)程在輸出井中為之申請(qǐng)一個(gè)空閑磁盤塊區(qū)， 并將要打印的數(shù)據(jù)送入其中；2. 輸出進(jìn)程再為用戶進(jìn)程申請(qǐng)一張空白的用戶請(qǐng)求打印表，并將用戶的打印要求填入其中， 再將該表掛到請(qǐng)求打印隊(duì)列上。6、磁盤訪問時(shí)間包括什么？（P193）1. 尋道時(shí)間Ts2. 旋轉(zhuǎn)延遲時(shí)間T3. 傳輸時(shí)間Tt7、 磁盤調(diào)度算法：計(jì)算平均尋道長(zhǎng)度P ( 19

23、4 )第六章 文件管理1、文件文件是指由創(chuàng)建者所定義的、 具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件兩種。在有結(jié)構(gòu)的文件中，文件由若干個(gè)相關(guān)記錄組成；而無結(jié)構(gòu)文件則被看成是一個(gè)字符流。文件在文件系統(tǒng)中是一個(gè)最大的數(shù)據(jù)單位，它描述了一個(gè)對(duì)象集。2、 文件的邏輯結(jié)構(gòu)及分類（P208）文件的邏輯結(jié)構(gòu)分為兩大類：1. 有結(jié)構(gòu)文件：即記錄式文件；記錄的長(zhǎng)度分為定長(zhǎng)記錄和變長(zhǎng)記錄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.

24、索引分配方式時(shí)的索引式文件結(jié)構(gòu)。4、 文件外存分配方式（P213）1. 連續(xù)分配。2. 鏈接分配。3. 索引分配。5、文件目錄，目錄查詢方式文件目錄是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識(shí)系統(tǒng)中的文件及其物理地址，供檢索時(shí)使用，是文件數(shù)據(jù)塊的有序集合。目錄查詢方式：1. 線性檢索法2. Hash方法6、 目錄管理的要求1. 實(shí)現(xiàn)“按名存取”。2. 提高對(duì)目錄的檢索速度。3. 文件共享。4. 允許文件重名。7、文件控制塊為了能對(duì)一個(gè)文件進(jìn)行正確的存取，必須為文件設(shè)置用于描述和控制的數(shù)據(jù)結(jié)構(gòu)，稱之為文件控制塊（包含三大信息：基本信息、存取控制信息、使用信息）8、 索引節(jié)點(diǎn)概念，為什么引入索引節(jié)點(diǎn)？索引節(jié)點(diǎn)：采用將

25、文件名與文件描述信息分開的辦法，將文件描述信息單獨(dú)形成一個(gè)數(shù)據(jù)結(jié)構(gòu)叫索引節(jié)點(diǎn)簡(jiǎn)稱i節(jié)點(diǎn)。引入原因：由于檢索目錄文件只用到文件名，即用不到該文件的描述信息，且在檢索目錄時(shí)索引節(jié)點(diǎn)不用調(diào)入內(nèi)存，從而大大節(jié)省了系統(tǒng)開銷。9、 文件存儲(chǔ)空間的管理方法1. 空閑表法2. 空閑鏈表法3. 位示圖法4. 成組鏈接法 （空閑表法和空閑鏈表法都不適合大型文件系統(tǒng)）10、 成組鏈接法的空閑盤塊組織、分配回收過程(1) 順序掃描位示圖，從中找出一個(gè)或一組其值為“0”的二進(jìn)制位(“0”表示空閑時(shí))。 (2) 將所找到的一個(gè)或一組二進(jìn)制位， 轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)。假定找到的其值為“0”的二進(jìn)制位，位于位示圖的第i行、

26、第j列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算： b=n(i-1)+j 式中， n代表每行的位數(shù)。 (3) 修改位示圖，令mapi,j=1?？臻e盤塊的分配與回收：當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí)，首先檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。 若該盤塊號(hào)已是棧底， 即S.free(0)，這是當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào)。由于在該盤塊號(hào)所對(duì)應(yīng)的盤塊中記有下一組可用的盤塊號(hào)，因此， 須調(diào)用磁盤讀過程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號(hào)棧的內(nèi)容，并把原棧底對(duì)應(yīng)的盤塊分配出去。 在系統(tǒng)回收空閑盤塊時(shí)，將回收盤塊的盤塊號(hào)

27、記入空閑盤塊號(hào)棧的頂部，并執(zhí)行空閑盤塊數(shù)加1操作。當(dāng)棧中空閑盤塊號(hào)數(shù)目已達(dá)100時(shí)， 表示棧已滿，便將現(xiàn)有棧中的100個(gè)盤塊號(hào)， 記入新回收的盤塊中，再將其盤塊號(hào)作為新棧底。 第七章 操作系統(tǒng)接口1、操作系統(tǒng)接口分為用戶接口和程序接口（概念）。用戶接口包括命令接口、圖形接口等。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ù)

28、：域名服務(wù)，目錄服務(wù)，Web服務(wù)3、目錄管理記錄了網(wǎng)絡(luò)中的三大資源物理設(shè)備，網(wǎng)絡(luò)服務(wù)和用戶的名字，屬性和位置。1、進(jìn)程同步互斥問題* 信號(hào)量類型:整型(忙等待)、記錄型、AND型、一般信號(hào)量集解決的問題：1、描述前趨關(guān)系：根據(jù)前趨圖，各邊分別設(shè)置信號(hào)量，初值為0；若某邊從某節(jié)點(diǎn)出發(fā)，在此節(jié)點(diǎn)操作后，對(duì)該邊對(duì)應(yīng)信號(hào)量作signal操作；若某邊指向某節(jié)點(diǎn)，在此節(jié)點(diǎn)操作前，對(duì)該邊對(duì)應(yīng)信號(hào)量作wait錯(cuò)作；Var a,b,c,d,e,f,g,h,i,j: semaphore:=0,0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b);

29、 end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e);signal(f); end; begin wait(c); S4;signal(g); end; begin 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; parend end 2、進(jìn)程

30、互斥問題（資源共享）* 根據(jù)臨界資源的種類設(shè)置信號(hào)量的個(gè)數(shù)，初值為各臨界資源的可用數(shù)量；* 在訪問臨界資源前，對(duì)對(duì)應(yīng)信號(hào)量作wait操作；在訪問結(jié)束后作signal操作，即將臨界區(qū)放在wait和signal之間。3、進(jìn)程同步（相互合作）* 為同步雙方設(shè)置各自的信號(hào)量，初值為其初始狀態(tài)可用的資源數(shù)(故該信號(hào)量稱為資源信號(hào)量或私有信號(hào)量)；* 同步雙方任一進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對(duì)自己的信號(hào)量執(zhí)行wait(<己方信號(hào)量>)操作，以測(cè)試是否有自己可用的資源。若有資源可用，則進(jìn)入臨界區(qū)，否則阻塞；同步雙方任一進(jìn)程離開臨界區(qū)后，應(yīng)對(duì)合作方 (對(duì)方)的信號(hào)量執(zhí)行signal(<對(duì)方信號(hào)

31、量>)操作，以通知(若對(duì)方處于阻塞狀態(tài)，則喚醒它)對(duì)方已有資源可用(對(duì)方已可進(jìn)入臨界區(qū))。* 有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一個(gè)座位列一表目，包括座號(hào)和讀者姓名等，讀者離開時(shí)要消掉登記的信息，試用wait,signal原語描述各個(gè)進(jìn)程之間的同步互斥關(guān)系。Var s,mutax: semaphore:=100,1;Reader：BeginRepeatWait(s);Wait(mutex);登記；Signal(mutex);閱覽圖書；Wait(mutex);取消登記；Signal(mutex);Signal(s);Until fasleend桌上

32、有一個(gè)盤子，每次只能放一個(gè)水果，爸爸專向盤中放蘋果，媽媽專向盤中放橘子，兒子專等吃盤里的桔子，女兒專等吃盤里的蘋果。只要盤子空，爸爸媽媽可向盤中放水果，僅當(dāng)盤中有自己需要的水果時(shí)，兒子或女兒可從中取出，請(qǐng)給出他們四人之間的同步關(guān)系程序。VAR s,so,sa:semaphore :=1,0,0;/s表示盤空，so表示橘子，sa表示蘋果。parbeginFather:begin   repeat           wait(s);    

33、;       put apple();           signal(sa);         until false endMother:begin repeat           wait(s);  

34、0;        put orange();           signal(so);         until false endSon:begin repaet        wait(so);       e

35、at orange();       signal(s);       until false end daughter:begin repeat         wait(sa);         eat apple();       &

36、#160; signal(s);         until falseendparend2設(shè)公共汽車上有一位司機(jī)和一位售票員，它們的活動(dòng)如下： 司機(jī)：?jiǎn)?dòng)車輛，行車，到站停車，售票員：售票；到站開門，關(guān)門請(qǐng)分析司機(jī)與售票員之間的同步關(guān)系，如何用PV操作實(shí)現(xiàn)。答：為了安全起見，顯然要求：關(guān)車門后才能啟動(dòng)車輛；到站停車后才能開車門。所以司機(jī)和售票員在到站、開門、關(guān)門、啟動(dòng)車輛這幾個(gè)活動(dòng)之間存在著同步關(guān)系。用兩個(gè)信號(hào)量S1、S2分別表示可以開車和可以開門，S1的初值為1，S2的初值為0。用PV操作實(shí)現(xiàn)司機(jī)進(jìn)程和售票員進(jìn)

37、程同步的算法描述如下：司機(jī)： P（S1） ；啟動(dòng)車輛 ；正常行車 ；到站停車；V（S2）； 售票員： 售票； P（S2） ； 開車門； 關(guān)車門； V（S1）；生產(chǎn)者消費(fèi)者問題三個(gè)進(jìn)程兩個(gè)緩沖區(qū)倆倆合作（下頁）；設(shè)自行車生產(chǎn)車間有兩個(gè)貨架，貨架A可以存放8個(gè)車架，貨架B可以存放20個(gè)車輪；又設(shè)有4個(gè)工人，他們的活動(dòng)是重復(fù)勞動(dòng)，分別為：工人1 加工一個(gè)車架放入貨架A中；工人2、3分別加工車輪放入貨架B中（每人每次放入1個(gè)車輪）；工人4從貨架A中取一個(gè)車架，再?gòu)呢浖蹷中取兩個(gè)車輪，組裝成一輛自行車。試用PV操作實(shí)現(xiàn)四個(gè)工人的合作1、系統(tǒng)中有是三個(gè)進(jìn)程GET，PRO和PUT，共用兩個(gè)緩沖區(qū)BUF1和B

38、UF2。假設(shè)BUF1中最多可放8個(gè)信息，BUF2中最多可放5個(gè)信息。GET進(jìn)程負(fù)責(zé)不斷地將信息送入BUF1中，PRO進(jìn)程負(fù)責(zé)從BUF1中取出信息進(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);u

39、ntil false endPRO:begin repeat wait(full1); wait(mutex1); 從BUF1中取信息加工;signal(mutex1);signal(empty1);wait(empty2);wait(mutex2);將加工后的信息放入BUF2;signal(mutex2);signal(full2);until falseendPUT:begin repeat wait(full2);wait(mutex2);從BUF2中取信息輸出;signal(mutex2);signal(empty2); until falseend【分析】設(shè)置資源信號(hào)量和互斥信號(hào)量如

40、下： 信號(hào)量Aempty表示貨架A的空位數(shù)，其初值為8； 信號(hào)量Afull表示貨架A上存放的車架數(shù)，其初值為0； 信號(hào)量Bempty表示貨架B的空位數(shù)，其初值為20； 信號(hào)量Bfull表示貨架B上存放的車輪數(shù)，其初值為0； 信號(hào)量mutex用于互斥（初值為1）。 Var Aempty,Afull,Bempty,Bfull,mutex:semaphore; Aempty.value:=8; Afull.value:=0; Bempty.value:=20;Bfull.value:=0; mutext.value:=1; wheelcount:integer:=0;Begin parbegin w

41、orker1:begin repeat生產(chǎn)一個(gè)車架； wait(Aempty);/看看貨架A上是否有空位置車架放到貨架A上； signal(Afull);/貨架A上的車架數(shù)增1，并通知工人4 until false; end Worker2，3:begin repeat生產(chǎn)一個(gè)車輪； wait(Bempty);/看看貨架B上是否有空位置 wait(mutex);將車輪放到貨架B上； signal(mutex); signal(Bfull);/貨架B上的車輪數(shù)增1，并通知工人4 until false; end Worker4:begin repeat wait(Afull);wait(Bful

42、l);wait(Bfull);取一個(gè)車架和兩個(gè)車輪； signal(Aempty);signal(Bempty);signal(Bempty);組裝一輛自行車； until false end parendend哲學(xué)家就餐問題（非死鎖算法） 至多允許4個(gè)哲學(xué)家同時(shí)取左邊的筷子，這樣能至少保證一個(gè)哲學(xué)家能就餐，并在用畢后釋放他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。（請(qǐng)學(xué)生考慮算法的描述） 僅當(dāng)哲學(xué)家左右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。（用AND信號(hào)量機(jī)制） 規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左邊筷子，然后再拿右邊筷子；而偶數(shù)號(hào)哲學(xué)家先拿右邊筷子，然后再拿左邊筷子。（1） var chopstic

43、k:array0,4 of semaphore := 1,1,1,1,1; Sm:semaphore := 4;beginrepeat wait(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 of semaphore := 1,1,1,1,1; beginrepeat swait(chopsticki，chopstic

44、k(i+1) mod 5); eat; ssignal(chopsticki，chopstick(i+1) mod 5); think;until falseend（3）var chopstick:array0,4 of semaphore := 1,1,1,1,1;beginrepeat if i mod 2=0 then begin wait(chopsticki); wait(chopstick(i+1) mod 5); end;else begin wait(chopstick(i+1) mod 5); wait(chopsticki); end; eat; signal(chopst

45、icki); signal(chopstick(i+1) mod 5);think;until falseEnd讀者寫者問題及變形-獨(dú)木橋問題假定有如下獨(dú)木橋問題：過橋時(shí)，同一方向的行人可連續(xù)過橋，當(dāng)某一方有人過橋時(shí)，另一方向的行人必須等待；當(dāng)某一方向無人過橋時(shí)，另一方向的行人可以過橋。試用信號(hào)量機(jī)制解決。 答案： (1) 將獨(dú)木橋的兩個(gè)方向分別標(biāo)記為A和B。用整型變量countA和countB分別 表示A、B方向上已在獨(dú)木橋上的行人數(shù)。初值為0。需要設(shè)置三個(gè)初值都為1的互斥信號(hào)量：SA用來實(shí)現(xiàn)對(duì)countA的互斥訪問，SB用來實(shí)現(xiàn)對(duì)countB的互斥訪問，mutex用來實(shí)現(xiàn)對(duì)獨(dú)木橋的互斥使用

46、。 (2) A方向行人過橋： Begin P(SA); countA=countA+1; if (countA= =1) P(mutex); V(SA); 過橋； (SA); countA=countA-1; if(countA= =0) V(mutex); V(SA); End B方向行人過橋： 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 處理機(jī)調(diào)度算法：1. 先來先服務(wù)調(diào)度算法 該算

47、法既可用于作業(yè)調(diào)度又可用于進(jìn)程調(diào)度，用于前者時(shí)，每次調(diào)度都是從外存后備隊(duì)列中選擇一個(gè)或多個(gè)作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后將新建進(jìn)程放入就緒隊(duì)列。用于后者時(shí)，每次調(diào)度時(shí)從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，把處理機(jī)分配給它，使其運(yùn)行。FCFS算法的特點(diǎn)如下：   利于長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）   利于CPU繁忙型作業(yè)（進(jìn)程），而不利于IO型繁忙作業(yè)（進(jìn)程）    作業(yè)平均等待時(shí)間長(zhǎng)     系統(tǒng)吞吐量不高2. 短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法 短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對(duì)短作

48、業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(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ī)時(shí)，再重新調(diào)度該算法的特點(diǎn)如下： 能有效降低作業(yè)平均等待時(shí)間 能提高系統(tǒng)吞吐量 對(duì)長(zhǎng)作業(yè)不利 未考慮作業(yè)的緊迫程度，因而不能保證緊迫型作業(yè)或進(jìn)程得到及時(shí)處理。由于作業(yè)或進(jìn)程的長(zhǎng)短是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定，因而不免存在差異。3.高優(yōu)先權(quán)優(yōu)先調(diào)度算法1) 非搶占式優(yōu)先權(quán)

49、算法2) 搶占式優(yōu)先權(quán)算法【例3-3】設(shè)有一個(gè)最多可有兩道作業(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)越高）：(1)列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。(2)計(jì)算平均周轉(zhuǎn)時(shí)間。平均周轉(zhuǎn)時(shí)間=(50+30+55+55)/4=47.5(分鐘)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í)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 當(dāng)

50、要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。(3) 對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高， 從而也可獲得處理機(jī)?！纠?-4】設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應(yīng)比優(yōu)先調(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)越高）：(1)列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。(2)計(jì)算平均周轉(zhuǎn)時(shí)間。平均周轉(zhuǎn)時(shí)間=(75+30+45+55)/4=51.25(分鐘)3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算

51、法1. 時(shí)間片輪轉(zhuǎn)法利用銀行家算法避免死鎖1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。(2) 最大需求矩陣Max。這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。(3) 分配矩陣Allocation。這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。(4) 需求矩陣Need。這也是一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需

52、的各類資源數(shù)。Needi,j=Maxi,j-Allocationi,j 2. 銀行家算法設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requestij=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej=Availablej-Requestij;

53、Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;(4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。3. 安全性算法 (1) 設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work=Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi=f

54、alse; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi=true。 2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到,執(zhí)行步驟(3);否則，執(zhí)行步驟(4)。(3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Workj=Workj+Allocationi,j;Finishi=true;go to step 2; (4) 如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 4. 銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3,

55、P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 3-15 所示。 圖 3-15 T0時(shí)刻的資源分配表 (1) T0時(shí)刻的安全性： 圖 3-16 T0時(shí)刻的安全序列 (2) P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖 3-15 中的圓括號(hào)所示。 再利用安全性