成都理工大學(xué)操作系統(tǒng)復(fù)習(xí)(PPT歸納)

1、第一、二章（Ly手工歸納）1簡述操作系統(tǒng)的主要功能答：處理器管理、存儲管理、設(shè)備管理、文件管理、網(wǎng)絡(luò)功能、用戶接口。2操作系統(tǒng)的特征:并發(fā)性、共享性、虛擬性、異步性3操作系統(tǒng)的類型批處理操作系統(tǒng)、分時操作系統(tǒng)、實時操作系統(tǒng)、微機操作系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)、分布式操作系統(tǒng)4程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行是指在邏輯上相互獨立的一組程序在執(zhí)行時間上的相互重疊，即一個程序段的執(zhí)行尚未結(jié)束，另一程序段的執(zhí)行已經(jīng)開始。5程序順序執(zhí)行 順序性，封閉性，可再現(xiàn)性6程序并發(fā)執(zhí)行間斷性，無封閉性，不可再現(xiàn)性7進程的定義進程是可并發(fā)執(zhí)行的程序的一次執(zhí)行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立的基本單位和實體，是一個動態(tài)的

2、概念。8進程的特征動態(tài)性：進程是程序的一次執(zhí)行過程具有生命期；它可以由系統(tǒng)創(chuàng)建并獨立地執(zhí)行，直至完成而被撤消。獨立性：各個進程之間相互獨立，是系統(tǒng)分配資源和能夠被處理機調(diào)度的基本單位。并發(fā)性：進程是可以并發(fā)執(zhí)行的基本單位，從宏觀上看，它們可以“同時”執(zhí)行。由于共享資源，進程間相互約束，相互依賴。異步性：各個進程按照各自獨立的、不可預(yù)知的速度異步向前推進。即進程按異步方式執(zhí)行。9進程三種基本狀態(tài)：執(zhí)行狀態(tài) （Executing）、就緒狀態(tài) （Ready）、阻塞狀態(tài) （Blocked）或等待（Wait）10進程控制塊進程控制塊PCB（Process Control Block）記錄和描述進程的動態(tài)

3、特性，描述進程的執(zhí)行情況和狀態(tài)變化。是進程存在的唯一標(biāo)識。11進程的描述進程標(biāo)識信息：外部標(biāo)識信息 內(nèi)部標(biāo)識信息 進程家族標(biāo)識處理機狀態(tài)信息：通用寄存器 指令計數(shù)器 程序狀態(tài)字（PSW）用戶棧指針進程調(diào)度信息：進程狀態(tài) 進程優(yōu)先級 其它調(diào)度信息 等待事件進程控制信息 ：程序數(shù)據(jù)地址 進程同步及通信 資源清單 鏈接指針12os內(nèi)核 進程運行狀態(tài)操作系統(tǒng)中，為了防止用戶進程對OS及PCB等關(guān)鍵信息的破壞。一個進程在其生命期中有兩種機器運行狀態(tài)：系統(tǒng)態(tài) （核心態(tài)，管態(tài)） 具有較高的訪問權(quán)，可訪問核心模塊。 用戶態(tài) （目態(tài) ） 限制訪問權(quán)。 原語（primitive）是機器指令的延伸，是非進程模塊,不

4、能并發(fā)執(zhí)行。執(zhí)行過程不可中斷，用微代碼實現(xiàn)。13進程控制原語創(chuàng)建語言、阻塞語言、掛起語言、撤銷語言、喚醒語言、激活語言14進程間的約束關(guān)系互斥關(guān)系 進程之間由于競爭使用共享資源而產(chǎn)生的相互約束的關(guān)系。這種因共享資源而產(chǎn)生的制約關(guān)系稱為進程的互斥。 間接相互制約關(guān)系同步關(guān)系 并發(fā)執(zhí)行進程之間通過在執(zhí)行時序上的某種限制而達到相互合作的這種約束關(guān)系稱為進程的同步 直接相互制約關(guān)系15臨界資源與臨界區(qū)臨界資源 （critical source）：凡是以互斥方式使用的共享資源都稱為臨界資源。臨界資源具有一次只允許一個進程使用的屬性。臨界區(qū) （critical section）：每個進程互斥訪問臨界資源的

5、那段代碼稱為臨界區(qū)16同步機制的準(zhǔn)則空閑讓進 無進程處于臨界區(qū)內(nèi)時，可讓一個申請進入該臨界區(qū)的進程進入。忙則等待 臨界區(qū)內(nèi)有進程時，申請進入臨界區(qū)的進程必須等待。有限等待 進程進入臨界區(qū)的請求，必須在有限的時間內(nèi)滿足。讓權(quán)等待 等待進入臨界區(qū)的進程，必須立即釋放CPU。17信號量機制 信號量、P、V操作原語 定義：VAR S：Semaphore；P操作（wait 原語） S.value ：= S.Value - 1； 若 S.Value 0 進程繼續(xù)執(zhí)行。 若 S.Value < 0 進程阻塞，并進入等待隊（L）。V操作（Signal原語） S.value ：= S.Value + 1；

6、 若 S.Value > 0 進程繼續(xù)執(zhí)行。 若 S.Value 0 則釋放S等待隊列中的一個進程 ，使之轉(zhuǎn)為就緒狀態(tài)。18進程通信的類型直接通信 發(fā)送進程通過收、發(fā)原語直接將消息發(fā)送到接受進程的消息緩沖區(qū)。間接通信 發(fā)送進程將消息發(fā)送到電子郵箱，接受進程再從中取出消息。第三、四章（Ly手工歸納）1進程調(diào)度的方式非搶占式（非剝奪式）：進程 一旦被調(diào)度 ，就一直占有CPU，直到完成或因發(fā)生某事件而被阻塞（I/O請求）。搶占式（剝奪式）：進程未執(zhí)行完，可由調(diào)度程序剝奪其CPU，另分配給別的進程。搶占的原因有：優(yōu)先級、時間片、短進程等2進程調(diào)度的功能記錄系統(tǒng)中所有進程的執(zhí)行情況、確定分配處理機

7、的原則（調(diào)度算法）、分配處理機給進程、回收處理機、進行進程上下文切換3調(diào)度算法先來先服務(wù)（FCFS）算法、最短CPU運行期優(yōu)先（SCBF）算法、最高優(yōu)先權(quán)（HPF）算法、時間片輪轉(zhuǎn)（RR）算法、多級反饋隊列算法4死鎖的基本概念（1）產(chǎn)生死鎖原因： 競爭資源 、進程推進順序不當(dāng)（2）產(chǎn)生死鎖的必要條件互斥條件：進程互斥使用臨界資源。不剝奪條件：資源只能由占有它的進程釋放，不能被其它進程剝奪。 請求保持條件：進程在申請新資源的同時，保持對某些資源的占有。 環(huán)路等待條件：存在循環(huán)等待鏈，在鏈中每個進程在等待它的前一進程所持有的資源。（3）解決死鎖的方法預(yù)防死鎖：限制并發(fā)進程對于資源的需求，

8、破壞產(chǎn)生死 鎖的必要條件。嚴(yán)格限制死鎖的發(fā)生。避免死鎖：在資源的動態(tài)分配過程中，采用某種算法防止系統(tǒng)進入不安全狀態(tài)，避免死鎖發(fā)生。檢測與解除死鎖：對資源的分配不加限制，系統(tǒng)定時運行“死鎖 檢測”程序，如檢測到死鎖，設(shè)法加以解除。5避免死鎖：在分配資源時，分析計算系統(tǒng)的安全性，避免系統(tǒng)進入不安全狀態(tài)，則可避免死鎖。6系統(tǒng)狀態(tài)安全：存在一個進程序列<P1，P2，。Pn> ，如果系統(tǒng)按此順序為每個進程分配它們所需的最大資源，而不造成死鎖，則稱系統(tǒng)狀態(tài)S（t）安全。7銀行家算法銀行家算法是著名的避免死鎖的算法。其基本思想是： O S 銀行家、進程 借貸的客戶、資源 可周轉(zhuǎn)的借貸資金8程序的

9、裝入絕對裝入方式：直接用物理地址編制程序?？芍囟ㄎ谎b入方式（靜態(tài)重定位）：重定位將邏輯地址轉(zhuǎn)換為物理地址的過程，也稱為地址變換或地址映射。動態(tài)運行時裝入方式（動態(tài)重定位）：在作業(yè)運行過程中進行地址轉(zhuǎn)換，將程序的地址（邏輯地址）轉(zhuǎn)換為內(nèi)存的物理地址。進程在內(nèi)存中的地址是可變的，并可動態(tài)申請內(nèi)存空間。9連續(xù)分配存儲管理方式固定分區(qū)分配：分區(qū)長度和個數(shù)將不再變化。建立內(nèi)存分配表記錄分區(qū)分配的情況。動態(tài)分區(qū)分配：根據(jù)用戶實際需要，動態(tài)的分配連續(xù)空間。建立已分配分區(qū)表及未分配分區(qū)表。 回收分區(qū)采用拼接技術(shù)。  緊湊技術(shù)10分區(qū)分配算法首次適應(yīng)算法FF：未分配分區(qū)按地址從小到大排列。分

10、配時順序查找，選擇第一個滿足要求的分區(qū)進行分配。最差適應(yīng)算法：按空閑區(qū)大小升序排列，分配時順序查找，選擇第一個滿足要求的最小分區(qū)進行分配。最佳適應(yīng)算法BF：按空閑區(qū)大小升序排列，分配時順序查找，選擇第一個滿足要求的最小分區(qū)進行分配。11離散分配存儲管理方式 頁式存儲管理、段式存儲管理、段頁式存儲管理12實存管理方案的主要問題：要求作業(yè)一次裝入，造成內(nèi)存資源的浪費。、用戶編程的地址空間（邏輯空間）不能超過實際的內(nèi)存空間，無法運行很大的應(yīng)用程序。13虛擬存儲管理的基本思想：（1）用大容量的外存來對內(nèi)存空間進行邏輯擴充擴充，為用戶提供一個比實際內(nèi)存空間大得多的虛擬內(nèi)存空間。（2）基于程序的

11、局部性原理，采用 “部分裝入”、“部分交換” 的策略。14請求分頁管理（1）內(nèi)存分配：將地址空間連續(xù)劃分為大小相等的頁面，將內(nèi)存空間也劃分為與頁面大小相等的物理塊（頁框），作業(yè)的頁面部分裝入，不連續(xù)存放。僅存在很少的頁內(nèi)零頭。(2)地址變換:通過頁表進行地址變換，其地址結(jié)構(gòu)為：請求分頁系統(tǒng)中的頁表,頁描述子：15請求式分頁存儲管理16頁面置換算法最佳置換算法（Optimal）:理論算法，所選擇的淘汰頁面，是永不訪問的或在最長時間內(nèi)不再被訪問的頁面。FIFO算法:是一種最簡單的淘汰算法，首先淘汰在內(nèi)存中駐留時間最長的頁面。算法依據(jù)是：作業(yè)按頁號依次裝入 ，一般相鄰頁面間邏輯關(guān)系最密切，故最早調(diào)入

12、的頁面不被使用的可能性比最近調(diào)入的頁面大。LRU（Least Recently Used）算法: 即最近最久不使用頁面的淘汰算法。算法依據(jù)：在本次缺頁中斷前的近一段時間內(nèi)，未被使用時間最長的頁面，推測在最近的將來，它也不會被使用。需要硬件支持：寄存器或堆棧。LFU（Least Frequently Used）算法: 最不常使用頁面淘汰算法， LRU的近似算法。首先淘汰到當(dāng)前時間為止，被訪問次數(shù)最少的頁面。只要在頁表中增加一個訪問計數(shù)器即可。該頁被訪問時計數(shù)器加 1。缺頁中斷時，淘汰計數(shù)器值最小的頁面。淘汰后，對計數(shù)器清零。17 I/O 系統(tǒng)的結(jié)構(gòu)微機I/O系統(tǒng) :CPU通過總線與設(shè)備控制器相連

13、接，設(shè)備控制器是CPU 與設(shè)備之間的接口。主機I/O系統(tǒng) :使用I/O通道（I/O處理機），實現(xiàn)對設(shè)備控制器的控制。18 I/O系統(tǒng)應(yīng)該由以下部分組成：I/O設(shè)備 設(shè)備控制器 總線或通道19 I/O控制方式 :程序直接控制、中斷控制方式、DMA 控制方式、通道控制方式20緩沖管理（1）為什么引入緩沖技術(shù)：緩解CPU與外設(shè)速度不匹配的問題。、減少CPU中斷響應(yīng)次數(shù)，放寬響應(yīng)時間。、提高CPU與I/O設(shè)備，I/O設(shè)備之間的并行操作能力。 （2）緩沖技術(shù)的基本思想： 在內(nèi)存中開辟一個或多個專用區(qū)域（緩沖區(qū)），作為CPU 與I/O設(shè)備間信息的集散地。（3）緩沖區(qū)的組織：單緩沖區(qū)（single buff

14、er）、雙緩沖區(qū)（double buffer）、循環(huán)緩沖（circular buffer）、緩沖池（buffer pool） 21設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)設(shè)備控制表DCT（Device Control Table）：反映設(shè)備特性，設(shè)備與I/O控制器連接情況?？刂破骺刂票鞢OCT（Controler Control Table）：記錄I/O控制器使用情況及與通道連接情況。（DMA無）通道控制表CHCT（Channel Control Table）：描述通道的使用情況。系統(tǒng)設(shè)備表SDT（System Device Table）：整個系統(tǒng)一張，記錄已連接到系統(tǒng)中的設(shè)備情況，每個設(shè)備在SDT中占一表項。22

15、設(shè)備獨立性：設(shè)備獨立性（device independence）是I/O軟件的一個關(guān)鍵性概念，是指用戶程序獨立于使用的物理設(shè)備。（1）邏輯設(shè)備表：為了實現(xiàn)設(shè)備獨立性，進程使用邏輯設(shè)備名。系統(tǒng)為每個進程建立一張邏輯設(shè)備表LUT（Logical Unit table）。LUT 包括：邏輯設(shè)備名、物理設(shè)備名、驅(qū)動程序地址。通過LUT 實現(xiàn)用戶程序中邏輯設(shè)備名到物理設(shè)備名的映射。（2）使用邏輯設(shè)備名的優(yōu)點：有利于改善資源的利用率。提供了設(shè)備分配的靈活性。為用戶程序提供了與設(shè)備無關(guān)的接口，為I/O重定位提供方便，因此，提高了用戶程序的可適應(yīng)性。23虛擬設(shè)備管理多道程序系統(tǒng)中，進程對設(shè)備的需求頻繁，尤其是

16、獨占設(shè)備數(shù)量有限、效率低，故引入虛擬設(shè)備管理技術(shù)。基本思想：用大容量的快速設(shè)備（磁盤）模擬慢速度的獨占設(shè)備，把一臺物理上的獨占設(shè)備變?yōu)檫壿嬌系亩嗯_共享設(shè)備。24 SPOOLing 技術(shù)SPOOLing是一種典型的虛擬設(shè)備技術(shù)， SPOOLing 是Simultaneous Peripheral Operations On Line （外圍設(shè)備同時聯(lián)機操作）的縮寫，是用程序模擬脫機I/O的功能，故又稱為假脫機技術(shù)。25SPOOLing系統(tǒng)的組成：1）輸入井、輸出井2）輸入進程、輸出進程 3）I/O緩沖區(qū)26設(shè)備處理：設(shè)備處理程序又稱為設(shè)備驅(qū)動程序，它是I/O進程與設(shè)備控制器之間的通信程序。設(shè)備驅(qū)

17、動程序是IOCS的主體。驅(qū)動程序執(zhí)行步驟：（1）服務(wù)請求校驗：確定請求的操作，檢驗硬件支持。（2）確認(rèn)設(shè)備狀態(tài)：確定設(shè)備（狀態(tài)寄存器）是否可用。（3）啟動I/O請求 ：若確認(rèn)設(shè)備狀態(tài)可用，啟動I/O。（4）中斷處理：CPU處理I/O過程的中斷。驅(qū)動程序應(yīng)保存處理器的當(dāng)前狀態(tài)，以便進程重新執(zhí)行。（5）I/O請求完成:驅(qū)動程序識別I/O完成，將控制返回IOCS，將被中斷的進程置為就緒。27磁盤存儲器管理: 主要討論移動頭磁盤的調(diào)度算法：磁盤的訪問時間（P173） 尋道時間Ts (Seek Time) Ts = m n + S m 常數(shù)（一般0.2，高速小于0.1） S 磁盤啟動時間 n 磁頭移動磁

18、道數(shù) 旋轉(zhuǎn)延時Tr (Rotational Delay) Tr 1/(2r) r 磁盤每秒轉(zhuǎn)數(shù)。 數(shù)據(jù)傳輸時間Tt (Transfer Time)Tt = b/ rN28磁盤存儲器管理常用的調(diào)度算法 先來先服務(wù)（FCFS）:按照申請服務(wù)的先后次序。未考慮尋道優(yōu)化。 最短尋道優(yōu)先算法（SSTF）:優(yōu)先選擇離磁頭最近的請求。未考慮磁頭來回擺動。可能出現(xiàn)老進程的“饑餓”現(xiàn)象。 掃描算法（SCAN）:既考慮請求與磁頭的距離，又考慮磁頭移動的方向；又稱為：電梯法。 循環(huán)掃描算法（C-SCAN）:規(guī)定磁頭單向移動，即將最小磁道號與最大磁道號構(gòu)成循環(huán)，進行循環(huán)掃描。29磁盤存儲器管理提高磁盤I/O速度的技術(shù)

19、磁盤高速緩存（Disk Cache):把磁盤I/O緩沖區(qū)叫做磁盤高速緩存（Disk Cache），磁盤I/O緩沖區(qū)仍然是內(nèi)存中的一個區(qū)域。其工作原理類似Cache Memory。提前讀（Read Ahead)與延后寫（Write Postponing）RAID技術(shù)第六章（Ly手工歸納）1文件邏輯結(jié)構(gòu)：文件結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。文件結(jié)構(gòu)決定了對文件的訪問方式及檢索速度。從用戶的觀點討論文件的組織形式，即文件的邏輯結(jié)構(gòu)。無結(jié)構(gòu)的字符流文件（如程序、文本文件）有結(jié)構(gòu)的記錄式文件（如數(shù)據(jù)庫文件）（1）按照記錄長度 · 定長記錄 · 變長記錄（2）按照存取方式：順序文件（串結(jié)構(gòu)

20、【按照時間順序】順序結(jié)構(gòu)【按照鍵值】）、索引文件、順序索引文件2外存分配方法：（1）連續(xù)分配將文件信息存放在連續(xù)編號的物理塊中。優(yōu)點：結(jié)構(gòu)簡單，存取速度快。缺點：長度事先確定，隨后不允許增加長度。（2）鏈接分配將文件信息存放在非連續(xù)編號的物理塊中。優(yōu)點：插入、刪除方便，文件長度可變。缺點：查找困難。 （3）索引文件：優(yōu)點：可以隨機存取。缺點：增加空間的開銷。3文件控制塊和索引結(jié)點：（1）文件控制塊（FCB）：是用于控制和描述文件的數(shù)據(jù)結(jié)構(gòu)，包括三類信息：基本信息：文件名、文件物理位置、文件的邏輯結(jié)構(gòu)、文件的物理結(jié)構(gòu)。存取控制信息：用戶的存取控制權(quán)（S、O、G、W）。使用信息：文件建立、修改的日

21、期時間，當(dāng)前使用信息。（2）索引結(jié)點：為了提高檢索的速度，減少所需內(nèi)存空間，將文件的描述信息單獨構(gòu)成一個數(shù)據(jù)結(jié)構(gòu)索引結(jié)點。4目錄管理：兩級目錄結(jié)構(gòu)及其特點、樹型（多級）目錄及其特點、路徑名與當(dāng)前目錄。5空閑存儲空間的管理方法：空閑表法、空閑鏈表法、位示圖法、成組鏈接法 6可變分區(qū)存儲管理：（1）可變式分區(qū)是指在作業(yè)裝入時，依據(jù)它對內(nèi)存空間實際的需求量來劃分內(nèi)存的分區(qū)，因此，每個分區(qū)的尺寸與進入它的作業(yè)大小相同。（2）它能有效解決固定式分區(qū)的內(nèi)部碎片問題，是一種較為實用的存儲管理方法。（3）因為在系統(tǒng)運行過程中，內(nèi)存中分區(qū)的數(shù)目和大小都是可變的，所以這種可變式分區(qū)也稱為動態(tài)分區(qū)。7首次適應(yīng)算法：

22、 這種算法把空閑分區(qū)按其在存儲空間中地址遞增的順序鏈接在一起。當(dāng)用戶申請一塊內(nèi)存空間時，從空閑區(qū)鏈表的頭指針開始查找，選擇第一個滿足要求的空閑分區(qū)。如果它不等于作業(yè)大小，將其分成兩部分，一部分給作業(yè)，另一部分仍留在空閑區(qū)鏈表中。8首次適應(yīng)算法：優(yōu)點：是分配和回收算法都比較簡單，查找速度快，因這個算法總是從低地址開始查找，因此留在高地址部分的大空閑區(qū)被劃分機會少，在大作業(yè)到來時容易滿足。缺點：是在低地址部分很快集中了許多非常小的空閑區(qū)，在空閑區(qū)分配時，搜索次數(shù)增加，影響了工作效率。9最佳適應(yīng)算法 ：此種算法把空閑分區(qū)鏈表按分區(qū)大小由小到大進行組織。當(dāng)有作業(yè)申請內(nèi)存時，總是首先找到滿足要求的最接近于作業(yè)大小的空閑分區(qū)。因分區(qū)大小與作業(yè)相近，從而避免將較大的分區(qū)分成兩部分，當(dāng)有較大的作業(yè)要求分配內(nèi)存時，容易得到滿足。 10最差適應(yīng)算法：（1）這種算法要求把空閑區(qū)按從大到小遞減的順序組織成空閑區(qū)鏈表。當(dāng)用戶申請一個存儲區(qū)時，總是檢查空閑區(qū)鏈表的第一個空閑區(qū)是否滿足要求，若不滿足，分配失??；若滿足，則將該空閑區(qū)分配給用戶，然后修改和調(diào)整空閑區(qū)鏈表。（2）優(yōu)點：是查詢簡單，而且每次分配的總是最大的空閑區(qū)，除用戶使用的外，剩余的空閑區(qū)還可能相當(dāng)大，還能裝入較大的程序。缺點：也在于此