操作系統(tǒng)總復(fù)習(xí)(修訂版)

1、目錄1、 概述 （1） 操作系統(tǒng)的定義，特征，功能 （簡答）（填空）（2） 各種操作系統(tǒng)（3） 多道和中斷2、 進(jìn)程（1） 進(jìn)程概念（2） 進(jìn)程特征、組成、PCB （簡答）（3） 進(jìn)程狀態(tài)及轉(zhuǎn)換 （簡答）（填空）（綜合題：根據(jù)進(jìn)程轉(zhuǎn)換圖，分析調(diào)度算法和狀態(tài)轉(zhuǎn)換）（4） 進(jìn)程與程序 （5） 線程與進(jìn)程3、 進(jìn)程調(diào)度（1） 調(diào)度概念、3級(jí)調(diào)度（2） 各種進(jìn)程調(diào)度算法 （簡答）（填空）（綜合題：表格法，給定調(diào)度算法，求周轉(zhuǎn)時(shí)間）4、 同步互斥 （1） 概念：并發(fā)、同步、互斥、臨界區(qū) （簡答）（6） PV操作：定義、信號(hào)量、取值 （簡答）（填空） （綜合題：PV操作解題）5、 死鎖 （1） 死鎖概念（

2、2） 死鎖原因和條件 （簡答）（填空）（3） 死鎖預(yù)防 （填空）（4） 死鎖避免：銀行家算法 （填空）（綜合題：表格法求是否安全）（5） 資源分配圖、死鎖檢測和恢復(fù) （簡答）（6） 哲學(xué)家進(jìn)餐6、 內(nèi)存管理 （1） 存儲(chǔ)管理概念，多種內(nèi)存管理方法比較（2） 動(dòng)態(tài)分區(qū)的適配算法 （簡答）（3）頁式：頁表、地址轉(zhuǎn)換、位示圖、訪存次數(shù) （填空）（綜合題：計(jì)算邏輯地址、物理地址）（4）段式（5）虛擬分頁、缺頁中斷（6）置換算法 （綜合題：給定置換算法，求缺頁率）7、 I/O和磁盤 （1） I/O控制方式（2） I/O軟件（3） 緩沖、設(shè)備獨(dú)立性（4） 磁盤訪問時(shí)間 （簡答） （填空）（5） 磁盤調(diào)度（

3、綜合題：給定磁道訪問序列，表格法或畫圖法，求尋道時(shí)間）8、 文件 （1） 文件管理概念（2） 文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)（3） 目錄 （簡答）（4） 空閑塊的組織：位示圖【操作系統(tǒng)的定義，特征，功能】操作系統(tǒng)管理軟硬件資源。操作系統(tǒng)的功能：處理器管理、存儲(chǔ)管理、I/O管理、文件管理、接口管理操作系統(tǒng)為程序員提供系統(tǒng)調(diào)用【各種操作系統(tǒng)】分時(shí)操作系統(tǒng)：交互、響應(yīng)時(shí)間基本操作系統(tǒng)：批處理、分時(shí)、實(shí)時(shí)【多道和中斷】多道：提高CPU效率（進(jìn)程并發(fā)運(yùn)行）、提高外設(shè)利用率，使外設(shè)與CPU并行中斷：中止正在運(yùn)行的程序。中斷是否發(fā)生是在一條指令執(zhí)行完進(jìn)行判斷【進(jìn)程概念】進(jìn)程：程序的一次執(zhí)行過程，動(dòng)態(tài)概念。不同進(jìn)程

4、可以對(duì)應(yīng)相同程序。進(jìn)程可以并發(fā)執(zhí)行（交替占用CPU運(yùn)行）。【進(jìn)程特征、組成、PCB】操作系統(tǒng)通過進(jìn)程控制塊PCB來控制進(jìn)程。PCB只由操作系統(tǒng)來創(chuàng)建、修改、訪問。操作系統(tǒng)通過fork()來創(chuàng)建新進(jìn)程：為進(jìn)程分配工作區(qū)和創(chuàng)建PCB。PCB的構(gòu)成?！具M(jìn)程狀態(tài)及轉(zhuǎn)換】進(jìn)程的3個(gè)基本狀態(tài)：就緒、運(yùn)行、等待、阻塞。一個(gè)就緒隊(duì)列、一個(gè)運(yùn)行進(jìn)程、一個(gè)或多個(gè)等待隊(duì)列（判斷什么情況下屬于3種狀態(tài)的哪一種）3狀態(tài)轉(zhuǎn)換圖：可能或不可能的狀態(tài)轉(zhuǎn)換（判斷在不同情況下，進(jìn)程由什么態(tài)轉(zhuǎn)為什么態(tài)狀態(tài)轉(zhuǎn)換的原因）PV操作與進(jìn)程轉(zhuǎn)換： P操作后則調(diào)用者自身狀態(tài)可能運(yùn)行態(tài)到等待態(tài)，V操作后調(diào)用者自身狀態(tài)不變，被喚醒者從等待態(tài)到就緒

5、態(tài)【進(jìn)程與程序】進(jìn)程：動(dòng)態(tài)概念，有狀態(tài)，有PCB、棧、程序和數(shù)據(jù)，程序的一次運(yùn)行，可并發(fā)程序：靜態(tài)概念，只有程序和數(shù)據(jù)，并發(fā)會(huì)出錯(cuò)（運(yùn)行結(jié)果不可再現(xiàn)）多個(gè)進(jìn)程可對(duì)應(yīng)同一個(gè)程序?！揪€程與進(jìn)程】線程是輕量級(jí)進(jìn)程。可把一個(gè)進(jìn)程分成幾個(gè)線程執(zhí)行。進(jìn)程是分配資源的單位，線程是調(diào)度和運(yùn)行的基本單位。線程共享進(jìn)程的資源。【調(diào)度概念、3級(jí)調(diào)度】進(jìn)程調(diào)度：從就緒進(jìn)程中選一個(gè)占有CPU運(yùn)行3級(jí)調(diào)度：長程調(diào)度，中程調(diào)度，短程調(diào)度【各種進(jìn)程調(diào)度算法】調(diào)度算法：搶占、非搶占先來先服務(wù) FCFS最短進(jìn)程優(yōu)先 SPN：平均周轉(zhuǎn)時(shí)間最短，估計(jì)運(yùn)行時(shí)間輪轉(zhuǎn) RR：分時(shí)操作系統(tǒng)，及時(shí)響應(yīng)最高響應(yīng)比 HRRN：響應(yīng)比=（等待時(shí)間+

6、服務(wù)時(shí)間）/服務(wù)時(shí)間=等待時(shí)間/服務(wù)時(shí)間+1【概念：并發(fā)、同步、互斥、臨界區(qū)】并發(fā)：一個(gè)時(shí)間間隔內(nèi)多個(gè)進(jìn)程同時(shí)執(zhí)行同步：并發(fā)的進(jìn)程之間存在制約關(guān)系互斥：只允許一個(gè)進(jìn)程訪問，其他進(jìn)程等待臨界資源：只允許一個(gè)進(jìn)程訪問的資源（比如共享變量）臨界區(qū)：對(duì)臨界資源進(jìn)程訪問的一段代碼，互斥訪問【PV操作：定義、信號(hào)量、取值】P（即semWait）：-1，<0阻塞，V(即semSignal)：+1，<=0 喚醒P用于申請(qǐng)資源，測試條件，V用于歸還資源，反饋條件，發(fā)送喚醒消息P調(diào)用后自己可能阻塞，V調(diào)用后自己狀態(tài)不變，被喚醒者等待態(tài)變?yōu)榫途w態(tài)互斥：先P，后V，初值為1. 信號(hào)量：記錄性變量分析：PV

7、操作用于臨界區(qū)，初值為1，若共有n個(gè)進(jìn)程想進(jìn)入臨界區(qū)，則第一個(gè)進(jìn)入臨界區(qū)后，信號(hào)量為0，后來的n-1個(gè)都等待，信號(hào)量為1-n，取值范圍為11-n.分析：允許m個(gè)進(jìn)程使用資源，有n個(gè)并發(fā)進(jìn)程（n>m>1），則信號(hào)量的取值范圍 n-m，m生產(chǎn)者-消費(fèi)者問題【死鎖概念】死鎖：相互等待【死鎖原因和條件】死鎖原因：競爭互斥資源，進(jìn)程推進(jìn)順序不當(dāng)（程序性錯(cuò)誤循環(huán)等待）死鎖條件：互斥、不可搶占、占有且等待、循環(huán)等待【死鎖預(yù)防】互斥不可能禁止破不可搶占：搶占資源破占有且等待：一次性申請(qǐng)所有資源（靜態(tài)資源分配）破循環(huán)等待：定義資源申請(qǐng)的線性順序（有序申請(qǐng)資源）【死鎖避免：銀行家算法】銀行家算法，避免

8、死鎖。安全狀態(tài)一定不死鎖。不安全狀態(tài)可能死鎖。死鎖一定是不安全狀態(tài)。綜合題【資源分配圖、死鎖檢測和恢復(fù)】死鎖定理：無環(huán)，一定不死鎖。單資源實(shí)例，有環(huán)就死鎖。多資源實(shí)例，有環(huán)不一定死鎖。死鎖恢復(fù)：取消進(jìn)程（終止進(jìn)程），搶占資源，進(jìn)程回滾【哲學(xué)家進(jìn)餐】哲學(xué)家進(jìn)餐問題：絕對(duì)不死鎖：最多進(jìn)4個(gè)人鴿巢原理的應(yīng)用：（1）有同類資源20個(gè)，進(jìn)程3個(gè)，一定不發(fā)生死鎖，則每個(gè)進(jìn)程最多同時(shí)申請(qǐng)7個(gè) 公式：進(jìn)程數(shù)*（最大同時(shí)資源數(shù)申請(qǐng)數(shù)-1）+1<資源總數(shù)。（2）有同類資源20個(gè)，每個(gè)進(jìn)程最多同時(shí)申請(qǐng)4個(gè)，一定不發(fā)生死鎖，則進(jìn)程數(shù)目最多是6個(gè) 公式：進(jìn)程數(shù)*（最大同時(shí)資源數(shù)申請(qǐng)數(shù)-1）+1<資源總數(shù)。

9、【注意：千萬不要背公式，要自己學(xué)會(huì)分析】【存儲(chǔ)管理概念，多種內(nèi)存管理方法比較】多級(jí)存儲(chǔ)：寄存器、高速緩存、主存、輔存（cpu不能直接訪問）存儲(chǔ)管理方式：固定分區(qū)（多道、連續(xù)，全部調(diào)入）動(dòng)態(tài)分區(qū)（多道、連續(xù)，全部調(diào)入）段式、頁式、段頁式（多道、離散，全部調(diào)入）虛擬段式、頁式、段頁式（多道、離散，部分調(diào)入）【動(dòng)態(tài)分區(qū)的適配算法】首次適配，下次適配：按地址排序最佳適配：按容量大小從小到大排序【頁式：頁表、地址轉(zhuǎn)換、訪存次數(shù)】分頁：進(jìn)程邏輯空間分頁，物理內(nèi)存分頁框(塊)，頁和頁框大小相等。頁表：頁號(hào)，頁框號(hào)。一個(gè)進(jìn)程一個(gè)頁表。頁表由操作系統(tǒng)建立地址轉(zhuǎn)換：二進(jìn)制地址則直接拆分；十進(jìn)制地址要計(jì)算。頁號(hào)=i

10、nt(邏輯地址/頁大小) 偏移量=mod(邏輯地址/頁大小) 物理地址=頁框號(hào)號(hào)*頁大小+偏移量訪存次數(shù)：頁式2次緩存，第一次訪問頁表，第二次訪問內(nèi)存，可以用快表減少訪存次數(shù)【段式】分段，段內(nèi)連續(xù)，段間離散，段表【虛擬分頁、缺頁中斷】虛存：部分調(diào)入虛存容量：min（2地址長度，內(nèi)存+外存）缺頁中斷：頁面不在內(nèi)存中，由操作系統(tǒng)調(diào)入所需頁面，返回缺頁中斷的那條指令繼續(xù)執(zhí)行【置換算法】置換：缺頁時(shí)，要調(diào)入新頁，但內(nèi)存已滿，選擇一頁淘汰頁地址流（頁面號(hào)訪問序列）：由邏輯地址訪問序列與頁面大小換算。置換算法：先進(jìn)先出 FIFO最佳置換 OPT最近最少使用 LRU（注：有些書叫最近最久未使用 LRU）時(shí)鐘（CLOCK） （增加使用位）改進(jìn)的時(shí)鐘 （增加使用位 修改位）【I/O控制方式】3種I/O控制方式：程序控制I/O，中斷驅(qū)動(dòng)I/O，直接存儲(chǔ)訪問DMA設(shè)備控制器：CUP與外設(shè)之間的接口【緩沖】緩沖：緩解CPU與外設(shè)的速度差異單緩沖，雙緩沖，循環(huán)緩沖【磁盤訪問時(shí)間】磁盤訪問時(shí)間=尋道時(shí)間+旋轉(zhuǎn)延時(shí)時(shí)間+傳輸時(shí)間【磁盤調(diào)度】磁盤調(diào)度：減少尋道時(shí)間磁盤調(diào)度算法：先進(jìn)先出FIFO、最短服務(wù)時(shí)間優(yōu)先 SSTF（最短尋道優(yōu)先）、SCAN（電梯調(diào)度）、C-SCAN（單向電梯調(diào)度）【文件管理概念】文件：有完整意義的信息集合文件系統(tǒng)：按名存取【文件的邏