湯子瀛-計(jì)算機(jī)操作系統(tǒng)第四版期末總復(fù)習(xí)課件

操作系統(tǒng)基本概念處理機(jī)管理設(shè)備管理作業(yè)管理用戶接口存儲(chǔ)管理文件管理操作系統(tǒng)定義OS的作用OS特征OS的主要功能OS分類OS結(jié)構(gòu)設(shè)計(jì)多道程序設(shè)計(jì)進(jìn)程基本概念進(jìn)程同步互斥進(jìn)程間通信進(jìn)程調(diào)度死鎖I/O系統(tǒng)I/O控制方式緩沖技術(shù)I/O軟件組成設(shè)備獨(dú)立性設(shè)備分配驅(qū)動(dòng)程序虛設(shè)備技術(shù)通道技術(shù)磁盤調(diào)度文件基本概念文件的邏輯結(jié)構(gòu)文件的物理結(jié)構(gòu)文件目錄外存空間管理文件共享與保護(hù)數(shù)據(jù)一致性用戶接口作業(yè)基本概念批處理系統(tǒng)作業(yè)管理分時(shí)系統(tǒng)作業(yè)管理程序的裝入與鏈接存儲(chǔ)管理任務(wù)動(dòng)態(tài)分區(qū)分配交換技術(shù)頁式存儲(chǔ)管理段式存儲(chǔ)管理段頁式虛擬存儲(chǔ)技術(shù)批處理操作系統(tǒng)分時(shí)系統(tǒng)實(shí)時(shí)操作系統(tǒng)個(gè)人計(jì)算機(jī)操作系統(tǒng)網(wǎng)絡(luò)操作系統(tǒng)分布式操作系統(tǒng)操作系統(tǒng)定義OS功能OS特征OS分類硬件運(yùn)行環(huán)境操作系統(tǒng)設(shè)計(jì)并發(fā)共享虛擬異步有效管理合理調(diào)度使用方便吞吐量時(shí)間片虛機(jī)器操作系統(tǒng)設(shè)計(jì)目標(biāo)操作系統(tǒng)結(jié)構(gòu)設(shè)計(jì)CPU狀態(tài)系統(tǒng)堆棧中斷技術(shù)時(shí)鐘通道地址映射存儲(chǔ)保護(hù)處理機(jī)管理存儲(chǔ)管理設(shè)備管理文件管理用戶接口操作系統(tǒng)基本概念第一章引論1、OS的定義與作用 2、三種基本操作系統(tǒng)的基本原理和異同

多道程序設(shè)計(jì)、時(shí)間片輪轉(zhuǎn)法、及時(shí)性3、OS的特征和功能 4、用戶接口

5、OS的結(jié)構(gòu)設(shè)計(jì)進(jìn)程進(jìn)程狀態(tài)及轉(zhuǎn)換進(jìn)程控制塊系統(tǒng)并發(fā)度進(jìn)程控制進(jìn)程特性可重入程序共享內(nèi)存消息緩沖Send/Receive原語管道通信信箱調(diào)度算法選擇原則算法：先進(jìn)先出時(shí)間片輪轉(zhuǎn)基于優(yōu)先數(shù)高相應(yīng)比優(yōu)先搶占式實(shí)時(shí)調(diào)度技術(shù)進(jìn)程同步進(jìn)程互斥臨界區(qū)進(jìn)程同步機(jī)制信號(hào)量P、V操作生產(chǎn)者與消費(fèi)者問題讀者寫者問題哲學(xué)家進(jìn)餐問題死鎖的有關(guān)結(jié)論產(chǎn)生死鎖的必要條件死鎖預(yù)防死鎖避免死鎖檢測(cè)解除資源分配圖多道程序設(shè)計(jì)進(jìn)程基本概念進(jìn)程同步互斥進(jìn)程間通信進(jìn)程調(diào)度死鎖順序環(huán)境并發(fā)環(huán)境與時(shí)間有關(guān)的錯(cuò)誤不可在現(xiàn)性進(jìn)程管理第二章進(jìn)程管理1、進(jìn)程和線程的概念2、進(jìn)程的基本狀態(tài)及狀態(tài)轉(zhuǎn)換的原因

3、PCB的作用4、進(jìn)程控制的原語操作 5、進(jìn)程互斥、臨界區(qū)、進(jìn)程同步的基本概念、同步準(zhǔn)則

6、記錄型信號(hào)量7、信號(hào)量的應(yīng)用

8、經(jīng)典進(jìn)程同步問題；生產(chǎn)者與消費(fèi)者問題9、進(jìn)程間通信的原理和實(shí)現(xiàn)方法信箱第二章進(jìn)程管理的典型問題進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)變?cè)?。進(jìn)程互斥、臨界區(qū)三種經(jīng)典同步問題及其變型同步約束條件的分析，信號(hào)量的初值的設(shè)定單緩沖區(qū)的一個(gè)生產(chǎn)者一個(gè)消費(fèi)者同步問題單緩沖區(qū)的一個(gè)生產(chǎn)者多個(gè)消費(fèi)者同步問題多個(gè)生產(chǎn)者多個(gè)消費(fèi)者多個(gè)緩沖區(qū)的同步問題第三章處理機(jī)調(diào)度與死鎖1、處理機(jī)調(diào)度的基本概念和種類

2、選擇調(diào)度算法的準(zhǔn)則，周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間，響應(yīng)時(shí)間3、常見調(diào)度算法，搶占，響應(yīng)比4、 常見的兩種實(shí)時(shí)調(diào)度算法處理死鎖的基本方法5、死鎖產(chǎn)生的原因，四個(gè)必要條件

6、死鎖的預(yù)防7、利用銀行家算法避免死鎖

8、死鎖的檢測(cè)與解除段式存儲(chǔ)管理頁式存儲(chǔ)管理段頁式存儲(chǔ)管理虛擬存儲(chǔ)器虛擬存儲(chǔ)技術(shù)程序局部性原理虛擬頁式管理虛擬段式管理頁面淘汰算法抖動(dòng)（顛簸）用戶程序劃分邏輯地址內(nèi)存空間劃分內(nèi)存分配管理考慮硬件支持地址映射過程裝入與鏈接對(duì)換技術(shù)覆蓋技術(shù)高速緩存內(nèi)存磁盤系統(tǒng)區(qū)用戶區(qū)內(nèi)存管理分配回收存儲(chǔ)共享存儲(chǔ)保護(hù)內(nèi)存擴(kuò)充地址映射存儲(chǔ)體系存儲(chǔ)管理任務(wù)存儲(chǔ)管理方案虛擬存儲(chǔ)管理其他存儲(chǔ)管理第四章存儲(chǔ)管理的重點(diǎn)、難點(diǎn)重定位的基本概念：為什么要引入如何提高內(nèi)存利用率：離散分配、對(duì)換機(jī)制、動(dòng)態(tài)鏈接、虛擬存儲(chǔ)器、存儲(chǔ)器共享動(dòng)態(tài)分區(qū)分配方式：分配、回收算法基本分頁存儲(chǔ)管理方式：為什么引入；地址變換機(jī)構(gòu)和過程（含具有快表的情況）基本分段存儲(chǔ)管理方式：為什么引入；地址變換機(jī)構(gòu)和過程（含具有快表的情況）；信息的共享和保護(hù)虛擬存儲(chǔ)器的基本概念：為什么要引入；特征；實(shí)現(xiàn)虛擬存儲(chǔ)的關(guān)鍵技術(shù)請(qǐng)求分頁系統(tǒng)的基本原理：頁表機(jī)制；地址變換過程；頁面置換算法第四章的典型問題存儲(chǔ)器管理的基本任務(wù)動(dòng)態(tài)重定位的概念、實(shí)現(xiàn)方式，什么情況下需要重定位比較連續(xù)分配與離散分配基于空閑分區(qū)鏈的內(nèi)存分配與回收算法的應(yīng)用實(shí)例：首次適應(yīng)法，循環(huán)首次適應(yīng)法，最佳適應(yīng)法在某分頁系統(tǒng)中，給定內(nèi)存容量和物理塊大小，計(jì)算物理塊的數(shù)量；對(duì)給定的進(jìn)程頁表，將給定的邏輯地址，計(jì)算出其對(duì)應(yīng)的物理地址并畫出地址變換流程圖。在某分段系統(tǒng)中對(duì)給定的進(jìn)程段表，將給定的邏輯地址，計(jì)算出其對(duì)應(yīng)的物理地址并畫出地址變換流程圖。請(qǐng)求分頁系統(tǒng)過程的各種問題，并用流程圖的方式表示地址變換過程對(duì)給定的問題，按各種頁面置換算法，寫頁面調(diào)入過程，計(jì)算和分析缺頁率，并對(duì)多種算法的性能作比較分析設(shè)備管理重要性設(shè)備獨(dú)立性設(shè)備分類設(shè)備管理任務(wù)設(shè)備管理功能用戶進(jìn)程與設(shè)備無關(guān)軟件設(shè)備驅(qū)動(dòng)程序中斷處理程序SPOOLing技術(shù)共享打印機(jī)設(shè)備管理設(shè)備分配回收獨(dú)占設(shè)備分配共享設(shè)備分配基本概念I(lǐng)/O軟件組成緩沖技術(shù)設(shè)備處理虛設(shè)備技術(shù)設(shè)備驅(qū)動(dòng)程序設(shè)備管理磁盤訪問時(shí)間磁盤調(diào)度先來先服務(wù)最短尋道時(shí)間優(yōu)先掃描（電梯算法）CSCAN磁盤存儲(chǔ)管理第五章設(shè)備管理的重點(diǎn)、難點(diǎn)I/O控制方式：四種I/O方式的基本原理；四種I/O方式由低到高效的演變緩沖管理緩沖的概念，為什么引入緩沖單緩沖如何提高I/O速度，它存在哪些不足，雙緩沖、循環(huán)緩沖又如何提高CPU與I/O設(shè)備的并行性緩沖池是為了解決什么問題而引入，引入緩沖池后系統(tǒng)將如何處理I/O設(shè)備和CPU間的數(shù)據(jù)輸送緩沖池的工作方式及Getbuf和Putbuf過程設(shè)備獨(dú)立性什么是設(shè)備獨(dú)立性如何實(shí)現(xiàn)設(shè)備獨(dú)立性設(shè)備驅(qū)動(dòng)程序第五章設(shè)備管理的重點(diǎn)、難點(diǎn)虛擬設(shè)備和SPOOLing技術(shù)什么是虛擬設(shè)備什么是SPOOLing技術(shù)，SPOOLing系統(tǒng)的組成如何利用SPOOLing技術(shù)實(shí)現(xiàn)共享打印機(jī)磁盤調(diào)度磁盤調(diào)度的目標(biāo)磁盤訪問時(shí)間的計(jì)算FCFS、SSTF、SCAN、CSCAN等算法的應(yīng)用及這些調(diào)度算法的演變過程，分別解決了哪些問題；各算法的性能比較第五章設(shè)備管理的典型問題各種I/O控制方式的比較為什么引入緩沖區(qū)緩沖如何提高I/O速度為什么引入設(shè)備獨(dú)立性，如何實(shí)現(xiàn)什么是虛擬設(shè)備，實(shí)現(xiàn)虛擬設(shè)備的關(guān)鍵技術(shù)SPOOLing技術(shù)的組成，如何利用SPOOLing技術(shù)實(shí)現(xiàn)共享打印機(jī)設(shè)備處理程序的功能和處理過程對(duì)各種磁盤調(diào)度算法，計(jì)算訪問次序和平均尋道時(shí)間，性能磁盤訪問時(shí)間的組成和計(jì)算文件控制塊文件目錄目錄文件目錄項(xiàng)樹型目錄結(jié)構(gòu)目錄項(xiàng)分解法目錄檢索文件文件系統(tǒng)文件分類文件管理功能文件邏輯結(jié)構(gòu)文件物理結(jié)構(gòu)文件存取方式外存空間管理主要數(shù)據(jù)結(jié)構(gòu)文件系統(tǒng)使用文件系統(tǒng)安全、保護(hù)、保密、可靠性、一致性系統(tǒng)打開文件表用戶打開文件表物理塊磁盤結(jié)構(gòu)磁帶文件目錄文件基本概念文件系統(tǒng)實(shí)現(xiàn)存儲(chǔ)介質(zhì)創(chuàng)建、打開、讀寫、關(guān)閉、刪除、拷貝、重命名文件存取控制

文件管理第六章文件管理的重點(diǎn)、難點(diǎn)文件的邏輯結(jié)構(gòu)：順序文件、索引文件和索引順序文件原理和特征組織方式、訪問方法及各種文件形式的比較外存分配方式：連續(xù)分配、鏈接分配和索引分配原理、優(yōu)缺點(diǎn)顯示鏈接FAT、混合索引分配目錄管理：目錄管理的要求文件控制塊（FCB）索引結(jié)點(diǎn)目錄結(jié)構(gòu)：單級(jí)、兩級(jí)和多級(jí)文件磁盤空間管理空閑表法和空閑鏈法位示圖法：分配和回收的具體計(jì)算成組鏈接法第六章文件管理的典型問題畫出鏈接分配方式的鏈接情況和FAT的鏈接情況、FAT長度計(jì)算等。混合索引分配的的尋址方式、地址轉(zhuǎn)換的計(jì)算（另見P350）和索引結(jié)點(diǎn)的地址映射圖對(duì)給定的位示圖和文件的分配和回收需求，具體寫出分配過程和回收過程。Unix系統(tǒng)的成組鏈接法目錄管理的要求；目前廣泛采用的目錄結(jié)構(gòu)及其優(yōu)點(diǎn)說明在樹形目錄結(jié)構(gòu)中線性檢索的過程，并畫出相應(yīng)的流程圖文件的共享第七章操作系統(tǒng)接口聯(lián)機(jī)命令接口聯(lián)機(jī)命令終端處理程序命令解釋程序程序接口系統(tǒng)調(diào)用與一般過程調(diào)用的區(qū)別中斷與陷入圖形用戶接口期末試題題型及分值單選題判斷題簡答題計(jì)算題編程題分值分布：第二章（約占22分）第三章（約占20分）第四章（約占20分）第五章（約占15分）第六章（約占18分）其余章（約占5分）司機(jī)和售票員之間的同步關(guān)系司機(jī)只有在售票員關(guān)車門后，才能啟動(dòng)汽車。售票員只有在司機(jī)到站停車后，才能開車門。解：Semaphoreclose=0，stop=0；driver() { /*司機(jī)*/ while(True){ P(close);

啟動(dòng)車輛;

正常行車;

到站停車; V(stop); }}Conductor(){ /*售票員*/ while(True){

關(guān)車門; V(close);

售票; P(stop);

開車門;

上下乘客; }}Main(){parbegin(driver,conductor);}練習(xí)：過十字路口（單道）。進(jìn)程的互斥P1P2P3P4{{{{

通過路口；通過路口；通過路口；通過路口；}}}}P2P3P4P1分析：進(jìn)程P1、P2、P3、P4因競爭十字路口這個(gè)資源而成為互斥關(guān)系。設(shè)：信號(hào)量m表示十字路口資源，初值為1表示資源可用。

intm=1;cobeginp1()//p2()//p3()//p4()coend進(jìn)程的互斥p1(){P(m)；

通過路口；

V(m)；}p2(){P(m)；

通過路口；

V(m)；

}p3(){P(m)；

通過路口；

V(m)；}p4(){P(m)；

通過路口；

V(m)；

}在生產(chǎn)者—消費(fèi)者問題中應(yīng)注意：

(１)在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)。(２)對(duì)資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的進(jìn)程中，這樣保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程的同步及交替執(zhí)行。(３)在每個(gè)進(jìn)程中，多個(gè)wait操作順序不能顛倒，而signal操作的次序是無關(guān)緊要的。例一臺(tái)計(jì)算機(jī)有10臺(tái)磁帶機(jī)被n個(gè)進(jìn)程競爭，每個(gè)進(jìn)程最多需要3臺(tái)磁帶機(jī)，那么n最多為_____時(shí)，系統(tǒng)沒有死鎖的危險(xiǎn)？解：n最大為4。例在銀行家算法中，若出現(xiàn)下述的資源分配情況：Process Max Allocation AvailableP0 0044 0032 1622P1 2750 1000 P2 361010 1354 P3 0984 0332 P4 06610 0014 試問：1）該狀態(tài)是否安全？2）若進(jìn)程P2提出請(qǐng)求Request（1，2，2，2）后，系統(tǒng)能否將資源分配給它？3）如果系統(tǒng)立即滿足P2的上述請(qǐng)求，系統(tǒng)是否立即進(jìn)入死鎖狀態(tài)？解：1）利用安全性算法對(duì)上面的狀態(tài)進(jìn)行分析（如下表所示），找到了一個(gè)安全序列{P0，P3，P4，P1，P2}或{P0，P3，P1，P4，P2}，故系統(tǒng)是安全的。資源情況進(jìn)程WorkNeedAllocationWork+AllocationFinishABCDABCDABCDABCDP01622001200321654TrueP31654065203321986TrueP419860656001419910TrueP1199101750100029910TrueP229910235613543121414True2)P2發(fā)出請(qǐng)求向量Request（1，2，2，2）后，系統(tǒng)按照銀行家算法進(jìn)行檢查：Request2（1，2，2，2）≤Need2（2，3，5，6）； Request2（1，2，2，2）≤Available（1，6，2，2）；系統(tǒng)先假定可為P2分配資源，并修改Available，Allocation2和Need2向量：Availabe=（0，4，0，0）Allocation2=（2，5，7，6）Need2=(1,1,3,4) 進(jìn)行安全性檢查：此時(shí)對(duì)所有進(jìn)程，條件Needi≦Available（0，4，0，0）都不成立，即Available不能滿足任何進(jìn)程的請(qǐng)求，故系統(tǒng)進(jìn)入不安全狀態(tài)。因此，當(dāng)進(jìn)程P2提出請(qǐng)求Request（1，2，2，2）后，系統(tǒng)不能將資源分配給它。3）系統(tǒng)立即滿足進(jìn)程P2的請(qǐng)求（1，2，2，2）后，并沒有馬上進(jìn)入死鎖狀態(tài)。因?yàn)椋藭r(shí)上述進(jìn)程并沒有申請(qǐng)新的資源，并未因得不到資源而進(jìn)入阻塞狀態(tài)。只有當(dāng)上述進(jìn)程提出新的請(qǐng)求，并導(dǎo)致所有沒執(zhí)行完的多個(gè)進(jìn)程因得不到資源而阻塞時(shí)，系統(tǒng)才進(jìn)入死鎖狀態(tài)。 例題對(duì)訪問串1，2，3，4，1，2，5，1，2，3，4，5，指出在駐留集大小分別為3、4時(shí)，使用FIFO替換算法的缺頁次數(shù)和缺頁率。結(jié)果說明了什么？先進(jìn)先出（FIFO）頁面置換算法（續(xù)）Referencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)4frames

FIFOReplacement–

Belady’sAnomalymoreframeslesspagefaults1231234125349pagefaults10pagefaults12312351245443一個(gè)磁盤系統(tǒng)，平均尋道時(shí)間為12ms，轉(zhuǎn)速為10000轉(zhuǎn)/分，每個(gè)磁道有18個(gè)扇區(qū)，每個(gè)扇區(qū)512個(gè)字節(jié)。請(qǐng)問要讀取一個(gè)扇區(qū)所花的時(shí)間是多少？

解：

TS=12msTR=1/2r=60÷10000×0.5=3ms

TA=b/rN=(512×60)÷(18×512×1000