1、操作系統(tǒng)內(nèi)容要點,操作 系統(tǒng),基本概念,處理機管理,設(shè)備管理,用戶接口,存儲管理,文件管理,操作系統(tǒng)定義 OS的目標(biāo) OS的作用 OS的特征 OS的主要功能 OS的基本類型,程序的執(zhí)行 進程的特征和定義 進程的狀態(tài) 進程的管理 進程的同步和通信 進程和線程 進程調(diào)度 死鎖,I/O系統(tǒng) I/O控制方式 緩沖技術(shù) I/O軟件組成 設(shè)備獨立性 設(shè)備分配 驅(qū)動程序 虛設(shè)備技術(shù) 通道技術(shù) 磁盤調(diào)度,文件基本概念 文件的邏輯結(jié)構(gòu) 文件的物理結(jié)構(gòu) 文件目錄 外存空間管理 文件共享與保護 數(shù)據(jù)一致性,用戶接口 作業(yè)基本概念 批處理系統(tǒng)作業(yè)管理 分時系統(tǒng)作業(yè)管理,程序的裝入與鏈接 存儲管理任務(wù) 動態(tài)分區(qū)分配 交

2、換技術(shù) 頁式存儲管理 段式存儲管理 段頁式 虛擬存儲技術(shù),第二、三章 進程管理,1、進程和線程的概念 2、進程的基本狀態(tài)及狀態(tài)轉(zhuǎn)換的原因 3、PCB的作用 4、進程控制的原語操作 5、進程互斥、臨界區(qū)、進程同步的基本概念、同步準(zhǔn)則 6、記錄型信號量 7、信號量的應(yīng)用 8、經(jīng)典進程同步問題；生產(chǎn)者與消費者問題 9、進程間通信的原理和實現(xiàn)方法 信箱,進程 進程狀態(tài)及轉(zhuǎn)換 進程控制塊 進程控制 進程特征,共享內(nèi)存 消息緩沖隊列 Send/Receive原語 信箱,調(diào)度的層次 調(diào)度算法的準(zhǔn)則 算法： 先來先服務(wù) 短作業(yè)(進程)優(yōu)先 時間片輪轉(zhuǎn) 基于優(yōu)先權(quán) 高響應(yīng)比優(yōu)先 實時調(diào)度算法（EDF）,進程同步

3、 進程互斥 臨界資源 進程同步機制 信號量 P、V操作 生產(chǎn)者與消費者問題 讀者寫者問題 哲學(xué)家進餐問題,死鎖的原因 產(chǎn)生死鎖的必要條件 死鎖預(yù)防 死鎖避免 死鎖檢測和解除 安全狀態(tài) 銀行家算法（避免）,多道程序設(shè)計,進程基本概念,進程同步互斥,進程間通信,進程調(diào)度,死鎖,順序執(zhí)行 并發(fā)執(zhí)行 前趨圖,進程 管理,第二、三章 進程管理的典型問題,進程的三種基本狀態(tài)及其轉(zhuǎn)變原因。 進程互斥、臨界資源 三種經(jīng)典同步問題及其變型 同步約束條件的分析，信號量的初值的設(shè)定 單緩沖區(qū)的一個生產(chǎn)者一個消費者同步問題 單緩沖區(qū)的一個生產(chǎn)者多個消費者同步問題 多個生產(chǎn)者多個消費者多個緩沖區(qū)的同步問題,頁式存儲管理

4、 段式存儲管理 段頁式存儲管理,虛擬存儲器 虛擬存儲技術(shù) 程序局部性原理 請求分頁管理 請求分段管理 頁面置換算法 抖動（顛簸）,用戶程序劃分 邏輯地址 內(nèi)存空間劃分 內(nèi)存分配 管理考慮 硬件支持 地址映射過程,程序裝入與鏈接 對換技術(shù) 覆蓋技術(shù),寄存器 高速緩存 內(nèi)存 磁盤緩存 磁盤,單一連續(xù)分配 分區(qū)分配（固定、動態(tài)） 動態(tài)重定位分區(qū)分配,存儲器的層次結(jié)構(gòu),連續(xù)分配方式,離散分配方式,虛擬存儲管理,其他,存儲 管理,第四、五章 存儲管理的重點、難點,重定位的基本概念：為什么要引入 如何提高內(nèi)存利用率：離散分配、對換機制、動態(tài)鏈接、虛擬存儲器、存儲器共享 動態(tài)分區(qū)分配方式：分配、回收算法 基

5、本分頁存儲管理方式：為什么引入；地址變換機構(gòu)和過程（含具有快表的情況） 基本分段存儲管理方式：為什么引入；地址變換機構(gòu)和過程（含具有快表的情況）；信息的共享和保護 虛擬存儲器的基本概念：為什么要引入；特征；實現(xiàn)虛擬存儲的關(guān)鍵技術(shù) 請求分頁系統(tǒng)的基本原理：頁表機制；地址變換過程；頁面置換算法,第四、五章的典型問題,存儲器管理的基本任務(wù) 動態(tài)重定位的概念、實現(xiàn)方式，什么情況下需要重定位 比較連續(xù)分配與離散分配 基于空閑分區(qū)鏈的內(nèi)存分配與回收算法的應(yīng)用實例：首次適應(yīng)法，循環(huán)首次適應(yīng)法，最佳適應(yīng)法 在某分頁系統(tǒng)中，給定內(nèi)存容量和物理塊大小，計算物理塊的數(shù)量；對給定的進程頁表，將給定的邏輯地址，計算出其

6、對應(yīng)的物理地址并畫出地址變換流程圖。 在某分段系統(tǒng)中對給定的進程段表，將給定的邏輯地址，計算出其對應(yīng)的物理地址并畫出地址變換流程圖。 請求分頁系統(tǒng)過程的各種問題，并用流程圖的方式表示地址變換過程 對給定的問題，按各種頁面置換算法，寫頁面調(diào)入過程，計算和分析缺頁率，并對多種算法的性能作比較分析,設(shè)備管理重要性 設(shè)備獨立性 設(shè)備分類 設(shè)備管理任務(wù) 設(shè)備管理功能,用戶進程 與設(shè)備無關(guān)軟件 設(shè)備驅(qū)動程序 中斷處理程序 設(shè)備控制器,SPOOLing技術(shù) 共享打印機,設(shè)備管理 設(shè)備分配回收 獨占設(shè)備分配 共享設(shè)備分配,基本概念,I/O軟件組成,緩沖技術(shù),設(shè)備處理,虛設(shè)備技術(shù),設(shè)備驅(qū)動程序,設(shè)備 管理,磁盤

7、訪問時間 磁盤調(diào)度 先來先服務(wù) 最短尋道時間優(yōu)先 掃描（電梯算法） CSCAN,磁盤存儲管理,第六章設(shè)備管理的重點、難點,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è)備獨立性 什么是設(shè)備獨立性 如何實現(xiàn)設(shè)備獨立性 設(shè)備驅(qū)動程序,第六章設(shè)備管理的重點、難點,虛擬設(shè)備和SPOOL

8、ing 技術(shù) 什么是虛擬設(shè)備 什么是假脫機（SPOOLing）技術(shù)，SPOOLing系統(tǒng)的組成 如何利用SPOOLing技術(shù)實現(xiàn)共享打印機 磁盤調(diào)度 磁盤調(diào)度的目標(biāo) 磁盤訪問時間的計算 FCFS、SSTF、SCAN、CSCAN 等算法的應(yīng)用及這些調(diào)度算法的演變過程，分別解決了哪些問題；各算法的性能比較,第五章設(shè)備管理的典型問題,各種I/O 控制方式的比較 為什么引入緩沖區(qū) 緩沖如何提高I/O 速度 為什么引入設(shè)備獨立性，如何實現(xiàn) 什么是虛擬設(shè)備，實現(xiàn)虛擬設(shè)備的關(guān)鍵技術(shù) SPOOLing技術(shù)的組成，如何利用SPOOLing 技術(shù)實現(xiàn)共享打印機 設(shè)備處理程序的功能和處理過程 對各種磁盤調(diào)度算法，計

9、算訪問次序和平均尋道時間，性能 磁盤訪問時間的組成和計算,文件控制塊 文件目錄 目錄文件 目錄項 樹型目錄結(jié)構(gòu) 目錄查詢技術(shù),文件 文件系統(tǒng) 文件分類 文件操作 文件邏輯結(jié)構(gòu) 外存分配方式,空閑表 空閑鏈表 位示圖,文件目錄,文件基本概念,文件存儲空間的管理,文件共享與保護,文件 管理,第七、八章文件管理的重點、難點,文件的邏輯結(jié)構(gòu)：順序文件、索引文件和索引順序文件 原理和特征 組織方式、訪問方法及各種文件形式的比較 外存分配方式：連續(xù)分配、鏈接分配和索引分配原理、優(yōu)缺點 顯示鏈接FAT、增量式索引分配 目錄管理：目錄管理的要求 文件控制塊（FCB） 索引結(jié)點 目錄結(jié)構(gòu)：單級、兩級和多級 文件

10、磁盤空間管理 空閑表法和空閑鏈法 位示圖法：分配和回收的具體計算,第七、八章 文件管理的典型問題,畫出鏈接分配方式的鏈接情況和FAT 的鏈接情況、FAT長度計算等。 增量式索引分配的的尋址方式、地址轉(zhuǎn)換的計算和索引結(jié)點的地址映射圖（書P259) 對給定的位示圖和文件的分配和回收需求，具體寫出分配過程和回收過程。 目錄管理的要求；目前廣泛采用的目錄結(jié)構(gòu)及其優(yōu)點 說明在樹形目錄結(jié)構(gòu)中線性檢索的過程，并畫出相應(yīng)的流程圖 文件的共享,第九章 操作系統(tǒng)接口,聯(lián)機命令接口 聯(lián)機命令 終端處理程序 命令解釋程序 程序接口 系統(tǒng)調(diào)用與一般過程調(diào)用的區(qū)別 中斷與陷入 圖形用戶接口,一個生產(chǎn)者一個消費者n個緩沖區(qū)

11、,由于只有一個生產(chǎn)者和一個消費者，不會發(fā)生幾個生產(chǎn)者和消費者同時存取同一緩沖單元的情況，故無須設(shè)置互斥信號量。,假定系統(tǒng)有3個并發(fā)進程get 、copy 和put共享緩沖器B1和B2。進程get負(fù)責(zé)從輸入設(shè)備上讀信息，每讀出一條記錄后放到B1中。進程copy從緩沖器B1中取出一條記錄拷貝后存入B2。進程put取出B2中的記錄打印輸出。B1和B2每次只能存放一條記錄。要求3個進程協(xié)調(diào)完成任務(wù)，使打印出來的與讀入的記錄個數(shù)、次序完全一樣。請用記錄型信號量寫出并發(fā)程序。,解：,設(shè)置4個信號量，其中empty1對應(yīng)空閑的緩沖區(qū)1，其初值為1；full1對應(yīng)緩沖區(qū)1中的記錄，其初值為0； empty2對

12、應(yīng)空閑的緩沖區(qū)2，其初值為1；full2對應(yīng)緩沖區(qū)2中的記錄，其初值為0。相應(yīng)進程描述為： get( ) while(ture) 從輸入設(shè)備讀入一條記錄; P(empty1); 將記錄存入緩沖區(qū)1； V(full1); ,copy( ) while(true) P(full1); 從緩沖區(qū)1中取出一條記錄; V(empty1); P(empty2); 將取出的記錄存入緩沖區(qū)2 ； V(full2); ,put( ) while(1) P(full2); 從緩沖區(qū)2中取出一條記錄; V(empty2); 將取出的記錄打印出來； Main( ) parbegin(get,copy,put); ,例

13、,一臺計算機有10臺磁帶機被n個進程競爭，每個進程最多需要3臺磁帶機，那么n最多為_時，系統(tǒng)沒有死鎖的危險？ 解：n最大為4。,補充：關(guān)于死鎖的公式： 當(dāng)一個系統(tǒng)有N個并發(fā)進程，每個進程都需要M個同類資源，那么最少需要多少資源才能避免死鎖的出現(xiàn)？ （M-1）*N+1 注：每個進程分配M-1個資源，然后再加上一個資源，該資源無論給哪個進程都可以保證當(dāng)前系統(tǒng)不會出現(xiàn)死鎖。,例,在銀行家算法中，若出現(xiàn)下述的資源分配情況： ProcessMax AllocationAvailable P00 0 4 40 0 3 21 6 2 2 P12 7 5 01 0 0 0 P23 6 10 101 3 5 4

14、 P30 9 8 40 3 3 2 P40 6 6 100 0 1 4 試問： 1）該狀態(tài)是否安全？ 2）若進程P2提出請求Request（1，2，2，2）后，系統(tǒng)能否將資源分配給它？ 3）如果系統(tǒng)立即滿足P2的上述請求，系統(tǒng)是否立即進入死鎖狀態(tài)？,解： 1）利用安全性算法對上面的狀態(tài)進行分析（如下表所示），找到了一個安全序列P0，P3，P4，P1，P2或P0，P3，P1，P4， P2，故系統(tǒng)是安全的。,2) P2發(fā)出請求向量Request（1，2，2，2）后，系統(tǒng)按照銀行家算法進行檢查： Request2（1，2，2，2）Need2（2，3，5，6）； Request2（1，2，2，2）Av

15、ailable（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) 進行安全性檢查：此時對所有進程，條件Needi Available（0，4，0，0）都不成立，即Available不能滿足任何進程的請求，故系統(tǒng)進入不安全狀態(tài)。因此，當(dāng)進程P2提出請求Request（1，2，2，2）后，系統(tǒng)不能將資源分配給它。 3）系統(tǒng)立即滿足進程P2的請求（1，2，2，2）后，并沒有馬上進入死鎖狀態(tài)。因為，此時上述進程并沒有申請新的資

16、源，并未因得不到資源而進入阻塞狀態(tài)。只有當(dāng)上述進程提出新的請求，并導(dǎo)致所有沒執(zhí)行完的多個進程因得不到資源而阻塞時，系統(tǒng)才進入死鎖狀態(tài)。,例2：已知某分頁系統(tǒng)，主存容量為64K，頁面大小為1K，對一個4頁大的作業(yè)，其0、1、2、3頁分別被分配到主存的2、4、6、7塊中。 （1）將十進制的邏輯地址1023、2500、3500、4500轉(zhuǎn)換成物理地址？ （2）以十進制的邏輯地址1023為例畫出地址變換過程圖？,答： 邏輯地址1023：1023/1K，得頁號為0，頁內(nèi)地址為1023，查頁表找到對應(yīng)的物理塊號為2，故物理地址為21K+1023=3071 邏輯地址2500：2500/1K，得頁號為2，頁內(nèi)

17、地址為452，查頁表找到對應(yīng)的物理塊號為6，故物理地址為61K+452=6596 邏輯地址3500：3500/1K，得頁號為3，頁內(nèi)地址為428，查頁表找到對應(yīng)的物理塊號為7，故物理地址為71K+428=7596 邏輯地址4500：4500/1K，得頁號為4，頁內(nèi)地址為404，因頁號大于頁表長度，故產(chǎn)生越界中斷。,（2）地址變換過程圖,例題,對訪問串1，2，3，4，1，2，5，1，2，3，4，5，指出在駐留集大小分別為3、4時，使用FIFO替換算法的缺頁次數(shù)和缺頁率。結(jié)果說明了什么？,Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3

18、frames (3 pages can be in memory at a time per process) 4 frames FIFO Replacement more frames less page faults ?,先進先出（FIFO）頁面置換算法（續(xù)）,9 page faults,10 page faults,例,一臺計算機有四個頁框，裝入時間、上次引用時間、它們的R（讀）與M（修改）位如下表所示（時間單位：嘀嗒），請問NRU、FIFO、LRU算法將替換哪一頁？,解答,FIFO算法在需要淘汰某一頁時，淘汰最先進入內(nèi)存的頁。在題述條件下，第2頁是最先進入內(nèi)存的頁。故FIFO算法將淘汰

19、第2頁。 LRU算法在需要淘汰某一頁時，淘汰最近最久未使用的頁面。在題述條件下，第1頁是最近最久未使用的頁面。故LRU算法將淘汰第1頁。 NRU算法在需要淘汰某一頁時，從那些最近一個時期內(nèi)未被訪問的頁中任選一頁淘汰。在題述條件下，只有第0頁是最近一個時期內(nèi)未被訪問的頁。故NRU算法將淘汰第0頁。,一個磁盤系統(tǒng)，平均尋道時間為12ms，轉(zhuǎn)速為10000轉(zhuǎn)/分，每個磁道有18個扇區(qū)，每個扇區(qū)512個字節(jié)。請問要讀取一個扇區(qū)所花的時間是多少？ 解： TS = 12ms TR = 1/2r = 60100000.5 = 3ms TA=b/rN = 512(10000/60) (18512)= 0.33

20、ms TT = TS + TR + TA =12 + 3 + 0.33 = 15.33ms 答：讀取一個扇區(qū)所花的時間是15.33ms。,例,磁盤調(diào)度,目標(biāo)：減少尋道時間 1、FCFS（Fisrt Come First Served）先來先服務(wù) 特點：公平、簡單，尋道時間長，相當(dāng)于隨機訪問模式。 僅適用于請求磁盤I/O的進程數(shù)目較少的場合。 2、SSTF（Shortest Seek Time First）最短尋道時間優(yōu)先 SSTF比FCFS有更好的尋道性能 饑餓現(xiàn)象 不能保證平均尋道時間最短 ？,圖 5-25 FCFS調(diào)度算法,圖 5-26 SSTF調(diào)度算法,3、SCAN 掃描算法（也稱為電梯

21、算法）。 SSTF存在進程“饑餓現(xiàn)象” SCAN算法： 在移動方向固定的情況下采用了SSTF，以避免饑餓現(xiàn)象 存在請求進程等待延遲現(xiàn)象 4、循環(huán)掃描CSCAN 磁頭單向移動 一個方向讀完，不是象SCAN那樣回頭，而是循環(huán)掃描。 請求延遲時間：2TT+Smax,圖 5-27 SCAN調(diào)度算法示例,圖 5-28 CSCAN調(diào)度算法示例,例,假定盤塊的大小為1KB,硬盤的大小為500MB,采用顯示鏈接分配方式時,其FAT需占用多少存儲空間（FAT表項占2.5個字節(jié)）?如果文件A占用硬盤的11, 12 , 16, 14四個盤塊,試畫出文件A中各盤塊在FAT表中的鏈接情況.,解：此時硬盤共有500M/1

22、K=500K個盤塊， FAT表項共有500K* 2.5B=1250KB,FAT,FCB,圖 混合索引方式,例,存放在某個磁盤上的文件系統(tǒng)，對于采用混合索引分配方式，其FCB中共有13項地址項，第09個地址項為直接地址，第10個地址項為一次間接地址，第11個地址項為二次間接地址，第12個地址項為三次間接地址。如果每個盤塊的大小為512字節(jié)，盤塊號需要3個字節(jié)來描述，則每個盤塊最多存放170個盤塊地址： (1) 該文件系統(tǒng)允許的最大長度是多少？ (2) 將文件的字節(jié)偏移量5000、15000、150000轉(zhuǎn)換為物理塊號和塊內(nèi)偏移量。 (3) 假設(shè)某文件的索引結(jié)點已在內(nèi)存中，但其他信息均在外存，為了

23、訪問該文件中某個位置的內(nèi)容，最多需要幾次訪問磁盤？,文件的最大長度為： 10+170+1702+1703=4942080塊=2471040KB 5000/512得商9，余數(shù)為392。即邏輯塊號為9，塊內(nèi)偏移為392。故可直接從該文件的FCB的第9個地址處得到物理盤塊號，塊內(nèi)偏移為392。 15000/512得商為29，余數(shù)為152。即邏輯塊號為29，塊內(nèi)偏移為152。由于102910+170,而29-10=19，故可從FCB的第10個地址項，即一次間址項中得到一次間址塊；并從一次間址塊的19項中獲得對應(yīng)的物理盤塊號，塊內(nèi)偏移為152。 150000/512得商為292，余數(shù)為496。即邏輯塊號為292，塊內(nèi)偏移為496。由于10+170292，故可從