操作系統(tǒng)重點知識總結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、4. 最壞適應(yīng)算法5. 快速適應(yīng)算法5、 對換技術(shù)（P129）對換技術(shù)，是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進程或進程所需的程序和數(shù)據(jù)調(diào)入內(nèi)存的方法。6、 緊湊或拼接技術(shù)（P127）緊湊技術(shù)，是指通過移動內(nèi)存中作業(yè)的位置，把原先分散的小分區(qū)拼接成一個大分區(qū)的方法。在每次拼接后，都必須對移動了的程序或數(shù)據(jù)進行重定位7、 基本分頁管理原理、地址變換過程P( 130)8、 分段系統(tǒng)的基本原理、地址變換過程P( 136 )9、 分頁與分段的主要區(qū)別（P138）1. 頁是信息的物理單位，分頁是為了實現(xiàn)離散分配方式，以消減內(nèi)存的外

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

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

21、PU與I/O設(shè)備間速度不匹配的矛盾。 2. 減少對CPU的中斷頻率， 放寬對CPU中斷響應(yīng)時間的限制。 3. 提高CPU和I/O設(shè)備之間的并行性。 4、 設(shè)備獨立性應(yīng)用程序獨立于具體使用的物理設(shè)備叫設(shè)備獨立性，也稱為設(shè)備無關(guān)性。5、 SPOOLING原理、組成、特點、共享打印機原理（P190）SPOOLING原理：在聯(lián)機情況下實現(xiàn)的外圍操作與CPU對數(shù)據(jù)的處理同時進行，稱為假脫機操作，又叫Spooling。Spooling系統(tǒng)的組成：1. 輸入井和輸出井2. 輸入緩沖區(qū)和輸出緩沖區(qū)（為了緩和CPU與磁盤之間速度不匹配的矛盾）3.  輸入進程和輸出進程4. 請求打印隊列SPOOLing

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

23、算法：計算平均尋道長度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)文件：即記錄式文件；記錄的長度分為定長記錄和變長記錄2. 無結(jié)構(gòu)文件：即流式文件（被看成字符流）。3、 文件的物理結(jié)構(gòu)及分類（P213）文件的物理結(jié)構(gòu)直接與外存分配方式有關(guān)。可分為：1. 連續(xù)分配方式時的順序式文件結(jié)構(gòu)。2. 鏈接

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

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

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

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

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

29、nal(a); signal(b); 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; en

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

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

32、);Until fasleend桌上有一個盤子，每次只能放一個水果，爸爸專向盤中放蘋果，媽媽專向盤中放橘子，兒子專等吃盤里的桔子，女兒專等吃盤里的蘋果。只要盤子空，爸爸媽媽可向盤中放水果，僅當(dā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、);           put orange();           signal(so);         until false endSon:begin repaet        wait(so);   &#

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

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

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

38、RO和PUT，共用兩個緩沖區(qū)BUF1和BUF2。假設(shè)BUF1中最多可放8個信息，BUF2中最多可放5個信息。GET進程負(fù)責(zé)不斷地將信息送入BUF1中，PRO進程負(fù)責(zé)從BUF1中取出信息進行處理，并將處理結(jié)果送到BUF2中，PUT進程負(fù)責(zé)從BUF2中讀取結(jié)果并輸出。試用wait、signal原語（P、V操作）實現(xiàn)GET，PRO，PUT進程之間的同步算法。1、 var：mutex1，mutex2，empty1，empty2，full11，full2：=1，1，8，5，0，0；GET:begin（ repeat wait(empty1); wait(mutex1); 送入BUF1；; signal(

39、mutex1); signal(full); until 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 fa

40、lseend【分析】設(shè)置資源信號量和互斥信號量如下： 信號量Aempty表示貨架A的空位數(shù)，其初值為8； 信號量Afull表示貨架A上存放的車架數(shù)，其初值為0； 信號量Bempty表示貨架B的空位數(shù)，其初值為20； 信號量Bfull表示貨架B上存放的車輪數(shù)，其初值為0； 信號量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:int

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

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

43、右邊筷子，然后再拿左邊筷子。（1） var chopstick: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; beginre

44、peat swait(chopsticki，chopstick(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(chopst

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

46、countB的互斥訪問，mutex用來實現(xiàn)對獨木橋的互斥使用。 (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

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

48、調(diào)度算法 短作業(yè)(進程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度該算法的特點如下： 能有效降低作業(yè)平均等待時間 能提高系統(tǒng)吞吐量 對長作業(yè)不利 未考慮作業(yè)的緊迫程度，因而不能保證緊迫型作業(yè)或進程得到及時處理。由于作業(yè)或進程的長短是根據(jù)用戶所提供的估計執(zhí)行時間而定，因

49、而不免存在差異。3.高優(yōu)先權(quán)優(yōu)先調(diào)度算法1) 非搶占式優(yōu)先權(quán)算法2) 搶占式優(yōu)先權(quán)算法【例3-3】設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)優(yōu)先調(diào)度算法，進程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計算型作業(yè)序列（表中所列進程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高）： (1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。 (2)計算平均周轉(zhuǎn)時間。平均周轉(zhuǎn)時間=(50+30+55+55)/4=47.5(分鐘)3). 高響應(yīng)比優(yōu)先調(diào)度算法(只使用作業(yè)調(diào)度) 優(yōu)先權(quán)=（等待時間+要求服務(wù)時間）/要求服務(wù)時間=響應(yīng)時間/要求服務(wù)時間=Rp算法特點： (1) 如果作業(yè)的等待時間相同，則要

50、求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高， 從而也可獲得處理機。 【例3-4】設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應(yīng)比優(yōu)先調(diào)度算法，進程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計算型作業(yè)序列（假設(shè)表中所列進程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高）： (1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。 (2)計算平均周轉(zhuǎn)時間。平均周轉(zhuǎn)時間=(7

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

52、求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。Needi,j=Maxi,j-Allocationi,j 2. 銀行家算法 設(shè)Requesti是進程Pi的請求向量，如果Requestij=K，表示進程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查： (1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 (3) 系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)

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

54、示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi=false; 當(dāng)有足夠資源分配給進程時， 再令Finishi=true。 2) 從進程集合中找到一個能滿足下述條件的進程： Finishi=false; Needi,jWorkj； 若找到,執(zhí)行步驟(3);否則，執(zhí)行步驟(4)。(3) 當(dāng)進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Workj=Workj+Allocationi,j;Finishi=true;go to step 2; (4) 如果所有進程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 4. 銀行家算法之例 假定系統(tǒng)中有五個進程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖 3-15 所示。 圖 3-15 T0時刻的資源分配表 (1) T0時刻的安全性： 圖 3-16 T0時刻的安全序列 (2) P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1