操作系統(tǒng)-基本知識點

1、操作系統(tǒng)復習提綱 目錄1.操作系統(tǒng)概述41.1.操作系統(tǒng)的概念41.2.計算機的特征41.2.1.計算機的功能41.3.計算機提供的服務41.4.操作系統(tǒng)的發(fā)展與分類41.5.操作系統(tǒng)的運行環(huán)境 （內(nèi)核態(tài)與用戶態(tài)、中斷、異常、系統(tǒng)調(diào)用）41.6.操作系統(tǒng)體系結(jié)構(gòu)52.進程管理62.1.進程與線程62.1.1.進程概念62.1.2.進程的狀態(tài)與轉(zhuǎn)換62.1.3.進程控制62.1.4.進程組織62.1.5.進程通信（共享存儲、消息傳遞、管道通信）62.1.6.線程概念與多線程模型72.2.處理機調(diào)度72.2.1.調(diào)度的基本概念72.2.2.典型調(diào)度算法82.3.進程同步與互斥82.3.1

2、.進程同步的基本概念82.3.2.實現(xiàn)臨界區(qū)互斥的基本方法：軟件實現(xiàn)方法、硬件實現(xiàn)方法82.3.3.信號量、管程92.3.4.經(jīng)典同步問題102.4.死鎖102.4.1.產(chǎn)生死鎖的原因102.4.2.產(chǎn)生死鎖的必要條件102.4.3.處理死鎖的方法103.內(nèi)存管理113.1.內(nèi)存管理基礎113.1.1.內(nèi)存管理概念113.1.2.程序裝入與鏈接、邏輯地址與物理地址空間、內(nèi)存保護113.1.3.交換與覆蓋113.1.4.連續(xù)分配管理方式113.1.5.非連續(xù)分配管理方式113.2.虛擬內(nèi)存管理113.2.1.虛擬內(nèi)存基本概念113.2.2.請求分頁管理方式123.2.3.頁面置換算法123.2.

3、4.工作集、抖動124.輸入輸出（I/O）管理134.1.I/O管理概述134.2.I/O控制方式134.3.I/O軟件層次結(jié)構(gòu)134.4.I/O調(diào)度概念134.4.1.磁盤訪問時間：134.4.2.磁盤調(diào)度144.5.出錯處理144.6.高速緩存與緩沖區(qū)144.6.1.緩沖引入的原因：144.6.2.緩沖的種類：144.6.3.高速緩存：144.7.假脫機技術(shù)（SPOOLing）144.8.設備分配與回收155.文件管理165.1.文件系統(tǒng)基礎165.1.1.文件概念與邏輯結(jié)構(gòu)165.1.2.文件的結(jié)構(gòu)165.1.3.目錄結(jié)構(gòu)165.1.4.文件共享175.1.5.文件保護：訪問類型、訪問控

4、制175.2.文件系統(tǒng)實現(xiàn)175.2.1.文件系統(tǒng)層次結(jié)構(gòu)175.2.2.目錄實現(xiàn)175.2.3.文件實現(xiàn)175.3.磁盤組織與管理175.3.1.磁盤的結(jié)構(gòu)175.3.2.磁盤調(diào)度算法：先來先服務（FCFS）、最短尋道時間優(yōu)先（SSTF）、電梯算法（SCAN）175.3.3.磁盤的管理171. 操作系統(tǒng)概述1.1. 操作系統(tǒng)的概念計算機操作系統(tǒng)是指控制和管理計算機的軟、硬件資源，以合理組織的計算機的工作流程，方便用戶使用的程序集合。1.2. 計算機的特征A. 并發(fā)性：單處理機并發(fā)（兩個或多個事物在同一時間間隔內(nèi)發(fā)生），多處理機可以并行（兩個或多個事物在同一時刻發(fā)生）。進程是在系統(tǒng)中能夠獨立運

5、行并作為資源分配的基本單位。在引入線程的OS中，通常都是把進程作為分配資源的基本單位，把線程作為獨立運行和調(diào)度的基本單位。B. 共享性：即系統(tǒng)中的資源可以共內(nèi)存中多個并發(fā)執(zhí)行的程序共同使用?？煞譃榛コ夤蚕矸绞胶屯瑫r訪問方式。C. 虛擬性：即通過一種技術(shù)把一個物理實體變?yōu)槿舾蓚€邏輯上的對應物。有時分復用技術(shù)（虛擬處理機技術(shù)）和空分復用技術(shù)（虛擬內(nèi)存）。D. 異步性：進程都是以不可預知的速度向前推進。1.2.1. 計算機的功能E. 處理機管理功能進程的創(chuàng)建，撤銷，同步，通信和調(diào)度。F. 存儲器管理功能內(nèi)存的分配，保護，地址映射，和虛擬內(nèi)存功能G. 設備管理功能為用戶進程分配回收I/O設備，完成I/

6、O請求，提高CPU和I/O設備之間的利用率（緩沖管理）。H. 文件管理功能文件存儲空間管理，目錄管理和文件的讀寫保護。I. 操作系統(tǒng)與用戶之間的接口功能可分為用戶接口和程序接口。1.3. 計算機提供的服務1.4. 操作系統(tǒng)的發(fā)展與分類發(fā)展：無操作系統(tǒng)的計算機系統(tǒng)單道批處理系統(tǒng)多道批處理系統(tǒng)分時系統(tǒng)實時系統(tǒng)微機操作系統(tǒng)的發(fā)展：單用戶單任務操作系統(tǒng)單用戶多任務操作系統(tǒng)多用戶多任務操作系統(tǒng)1.5. 操作系統(tǒng)的運行環(huán)境 （內(nèi)核態(tài)與用戶態(tài)、中斷、異常、系統(tǒng)調(diào)用）1.6. 操作系統(tǒng)體系結(jié)構(gòu)J. 傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu)無結(jié)構(gòu)OS，模塊化OS，分層式OSK. 客戶/服務器模式L. 面向?qū)ο蟮某绦蛟O計模式

7、M. 微內(nèi)核OS結(jié)構(gòu)足夠小的內(nèi)核，基于C/S模式，應用“機制與策略相分離”原理，采用面向?qū)ο蠹夹g(shù)。2. 進程管理2.1. 進程與線程1.1.1.2.1.1. 進程概念進程進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。進程實體即是由程序段，相關(guān)的數(shù)據(jù)段和PCB三部分構(gòu)成。程序順序執(zhí)行擁有順序性，封閉性，和可再現(xiàn)性三個特征。2.1.2. 進程的狀態(tài)與轉(zhuǎn)換2.1.3. 進程控制操作系統(tǒng)是根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的，所以說PCB是進程存在的唯一標識。在進程控制塊中主要包含一下四方面的內(nèi)容：A. 進程標識符包含內(nèi)部標識符和外部標識符B. 處理機狀態(tài)通用寄存器，指令計數(shù)器，

8、程序狀態(tài)字PSW，和用戶棧指針C. 進程調(diào)度信息進程狀態(tài)，進程優(yōu)先級D. 進程控制信息程序和數(shù)據(jù)地址，進程同步和通行機制，資源清單，鏈接指針2.1.4. 進程組織目前常用的兩種方式如下：A. 連接方式把具有統(tǒng)一狀態(tài)的PCB鏈接成一個隊列。B. 索引方式把具有統(tǒng)一狀態(tài)的PCB組織為一張索引表。2.1.5. 進程通信（共享存儲、消息傳遞、管道通信）A. 共享存儲：共享又可分為基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式和基于共享存儲區(qū)的通信方式。B. 管道通信：是指由于連接一個讀進程和一個寫進程以實現(xiàn)他們之間的通行。C. 消息傳遞系統(tǒng)：直接消息傳遞方式：Send(receiver,message);Receive(

9、sender,message);間接消息傳遞：Send(mailbox,message);Receive(mailbox,message);2.1.6. 線程概念與多線程模型 線程是比進程更小的能獨立運行的單位。線程有以下三種實現(xiàn)方式：A. 內(nèi)核支持線程B. 用戶級線程C. 組合方式2.2. 處理機調(diào)度1.2.2.2.1. 調(diào)度的基本概念調(diào)度可分為一下三種A. 高級調(diào)度（作業(yè)調(diào)度）主要功能是根據(jù)某種算法，把外存上處于后備隊列中那些作業(yè)調(diào)入內(nèi)存。B. 低級調(diào)度（進程調(diào)度）用于決定就緒隊列中的哪個進程應獲得處理機。C. 中程調(diào)度將那邪惡暫時不能運行的進程調(diào)到外存上等待，而不再浪費寶貴的內(nèi)存資源。1

10、.2.2.1.2.2.2.2.1.2.2.1.1. 調(diào)度的基本準則調(diào)度有兩個基本準則：A. 面向用戶的準則a) 周轉(zhuǎn)時間短平均周轉(zhuǎn)時間：T=1ni=1nTi，平均帶權(quán)周轉(zhuǎn)時間W=1ni=1nTiTsb) 響應時間快從鍵盤鍵入信息傳送到處理器的時間，處理機處理的時間，返回到終端顯示器的時間。c) 截至時間保證這是評價實時系統(tǒng)性能的重要指標d) 優(yōu)先權(quán)準則保證緊急作業(yè)得到即時處理B. 面向系統(tǒng)的準則a) 系統(tǒng)吞吐量b) 處理機利用率c) 各類資源的平衡利用2.2.1.2. 調(diào)度方式與時機進程的調(diào)度可以分為一下兩種A. 非搶占式在該模式下，可能引起進程調(diào)度的因素可以歸為一下幾類a) 正在執(zhí)行的進程執(zhí)

11、行完畢，或是發(fā)生某些事件而不能繼續(xù)執(zhí)行。b) 執(zhí)行中的進程提出I/O請求二暫停執(zhí)行c) 執(zhí)行了某種元語B. 搶占式搶占式可以防止某一長進程長時間占用處理機，能為大多數(shù)的進程提供更公平的服務。搶占的調(diào)度方式是基于一定原則的。2.2.1.3. 切換與過程A. 保存處理機的現(xiàn)場B. 按某種算法選取進程C. 把處理器分配給進程2.2.2. 典型調(diào)度算法2.2.2.A. 先來先服務(FCFS)與短作業(yè)（短進程、短線程）(SJ(P)F)優(yōu)先SJ(P)F較FCFS能明顯的提高平均周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，但該算法對長作業(yè)不利，也未考慮作業(yè)的緊迫程度。B. 時間片輪轉(zhuǎn)時間片的取值略大于一次典型交互所需的時間。C

12、. 優(yōu)先級優(yōu)先級法可分為靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級。D. 最高響應比優(yōu)先優(yōu)先權(quán)=等待時間+要求服務時間要求服務時間=響應時間要求服務時間。E. 多級反饋隊列調(diào)度算法2.3. 進程同步與互斥1.3.2.3.1. 進程同步的基本概念A. 兩種制約關(guān)系間接相互制約關(guān)系直接相互制約關(guān)系B. 臨界資源諸進程應采用互斥的方式實現(xiàn)對這種資源的訪問，如打印機等。C. 臨界區(qū)進程中訪問臨界資源的那段代碼稱為臨界區(qū)D. 同步機制原則a) 空閑讓進b) 忙則等待c) 有限等待d) 讓權(quán)等待2.3.2. 實現(xiàn)臨界區(qū)互斥的基本方法：軟件實現(xiàn)方法、硬件實現(xiàn)方法A. 軟件實現(xiàn)方法：a) 單標志法：/*P0進程*/while(t

13、urn!=0);critical section;turn=1;remainder section;/*P1進程*/while(turn!=1);critical section;turn=0;remainder section;兩個進程必須交替訪問臨界區(qū)，違背空閑讓進。b) 雙標志先查法：/*P0進程*/while(flagj);flagi=ture;critical section;flagi=FALSE;remainder section;/*P1進程*/while(flagi);flagj=TURE;critical section;flagj=FLASE;remainder sect

14、ion;檢查對方和設置自己不是一次執(zhí)行的，故可能會違背忙則等待原則。c) 雙標志后查法：/*P0進程*/flagi=ture;while(flagj);critical section;flagi=FALSE;remainder section;/*P1進程*/flagj=TURE;while(flagi);critical section;flagj=FLASE;remainder section;違背空閑讓進d) Petersons Algorithm/*P0進程*/flagi=TURE;turn=j;while(flagj&&turn=j);critical sectio

15、n;flagi=FALSE;remainder section;/*P1進程*/flagj=TURE;turn=I;while(flagi&&turn=j);critical section;flagj=FALSE;remainder section;利用flag解決互斥訪問，利用turn解決“饑餓”現(xiàn)象。B. 硬件實現(xiàn)方法：a) 中斷屏蔽法b) 硬指令法i. TestAndSet指令：while TestAndSet(&lock);critical section;lock=false;remainder section;ii. Swap指令：key=ture; /*

16、local variable*/while(key!=FAlSE)/*lock is a share var*/ Swap(&lock, &key);ritical section;lock=FALSE;remainder section;2.3.3. 信號量、管程A. 整型信號量違背讓權(quán)等待原則。B. 記錄型信號量C. AND型信號量D. 信號量集E. 管程一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行的在該數(shù)據(jù)結(jié)構(gòu)上的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)。2.3.4. 經(jīng)典同步問題A. 生產(chǎn)者-消費者問題：c) 使用記錄型信號量d) 使用and信號量解決e) 利用

17、管程B. 哲學家進餐問題：f) 利用記錄型型號量解決g) 利用AND信號量解決C. 讀者-寫者問題：h) 利用記錄型信號量解決i) 利用信號量集機制解決2.4. 死鎖1.4.死鎖，是指多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種僵持狀態(tài)時，若無外力作用，他們都將無法再向前推進。2.4.1. 產(chǎn)生死鎖的原因A. 競爭資源B. 進程間推進順序非法2.4.2. 產(chǎn)生死鎖的必要條件A. 互斥條件B. 請求和保持條件C. 不剝奪條件D. 環(huán)路等待條件2.4.3. 處理死鎖的方法A. 預防死鎖破壞死鎖的四個必要條件中的一個或多個從而達到預防死鎖的目的。但由于所施加的條件太嚴格可能會導致系

18、統(tǒng)資源利用率和系統(tǒng)吞吐量下降。摒棄“請求和保持”條件摒棄“不剝奪”條件摒棄“環(huán)路等待”條件B. 避免死鎖在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進入不安全狀態(tài)。如銀行家算法。C. 檢測死鎖&解除死鎖資源分配圖死鎖定理：當且僅當該狀態(tài)的資源分配圖是不可完全化簡的時，該狀態(tài)即為死鎖狀態(tài)。死鎖解除：剝奪資源和撤銷進程。3. 內(nèi)存管理3.1. 內(nèi)存管理基礎3.1.1. 內(nèi)存管理概念操作系統(tǒng)的存儲管理，負責對可執(zhí)行存儲器的分配，回收以及提供在存儲層次間數(shù)據(jù)移動的管理機制。3.1.2. 程序裝入與鏈接、邏輯地址與物理地址空間、內(nèi)存保護A. 裝入：a) 絕對裝入方式b) 可重定位裝入方式c) 動

19、態(tài)運行時裝入方式B. 鏈接： a) 靜態(tài)鏈接b) 裝入時動態(tài)鏈接c) 運行時動態(tài)鏈接3.1.3. 交換與覆蓋對換可分為整體對換和部分對換。為了實現(xiàn)進程的對換，系統(tǒng)必須實現(xiàn)三方面的功能：對換空間的管理，進程的換入，進程的換出。3.1.4. 連續(xù)分配管理方式 A. 單一連續(xù)分配方式內(nèi)存分為用戶區(qū)和系統(tǒng)區(qū)兩部分。只適用于單用戶單任務系統(tǒng)。B. 固定分區(qū)分配劃分分區(qū)的方法可以有分區(qū)大小相等和分區(qū)大小不等兩種方式。C. 動態(tài)分區(qū)分配a) 數(shù)據(jù)結(jié)構(gòu)：i. 空閑分區(qū)表ii. 空閑分區(qū)鏈b) 分區(qū)分配方法：i. 首次適應算法ii. 循環(huán)首次適應算法iii. 最佳適應算法iv. 最壞適應算法v. 快速適應算法D

20、. 可重定位分區(qū)分配利用動態(tài)運行時，地址的轉(zhuǎn)換是在程序執(zhí)行時完成。故可以使用“緊湊”將多個分散的小分區(qū)拼接成一個大分區(qū)。3.1.5. 非連續(xù)分配管理方式A. 分頁管理方式B. 分段管理方式C. 段頁式管理方式3.2. 虛擬內(nèi)存管理3.2.1. 虛擬內(nèi)存基本概念虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲系統(tǒng)。3.2.2. 請求分頁管理方式A. 硬件支持：a) 頁表機制：頁號物理塊狀態(tài)位訪問字段修改位外存地址b) 缺頁中斷機構(gòu)：與一般中斷相比，缺頁中斷發(fā)生在指令執(zhí)行期間，且在一條指令可能產(chǎn)生多次中斷。c) 地址變換機構(gòu)：加入虛擬存儲管理后的地址變換流程。B.

21、內(nèi)存分配策略和分配算法：a) 最小物理塊數(shù)：保證進程運行的最小物理塊數(shù)量，與硬件平臺有關(guān)。b) 物理塊分配策略：i. 固定分配局部置換ii. 可變分配全局置換iii. 可變分配局部置換c) 物理塊分配算法：i. 平均分配算法ii. 按比例分配算法iii. 考慮優(yōu)先權(quán)的分配算法C. 調(diào)頁策略：a) 時機：iv. 預調(diào)頁策略v. 請求調(diào)頁策略b) 何處：vi. 系統(tǒng)擁有足夠的對換區(qū)vii. 系統(tǒng)缺少足夠的對換區(qū)D. UNIX方式3.2.3. 頁面置換算法A. 最佳置換算法（OPT）B. 先進先出置換算法（FIFO）C. 最近最少使用置換算法（LRU）D. 時鐘置換算法<CLOCK>3.

22、2.4. 工作集、抖動抖動是指頻繁的頁面對換行為，最壞的情況是剛剛換出的頁面馬上又要換入，剛剛換入的頁面馬上又要換出。工作集是指在某段時間內(nèi)，進程要訪問的頁面的集合。為了防止系統(tǒng)出現(xiàn)抖動現(xiàn)象，需要選擇合適的工作集大小。4. 輸入輸出（I/O）管理 4.1. I/O管理概述I/O設備可按如下分類。按設備的使用特性可分為：存儲設備，輸入/輸出設備；按傳輸速率可分為：低速設備、中速設備、高速設備；按信息交換的單位可分為：塊設備、字符設備；按設備的共享屬性可分為：獨占設備、共享設備、虛擬設備；I/O設備與設備控制器間的接口有三種類型信號：數(shù)字信號線、控制信號線、狀態(tài)型號線。I/O通道有三種通

23、道類型：字節(jié)多路通道、數(shù)組選擇通道、數(shù)組多路通道4.2. I/O控制方式程序I/O方式中斷驅(qū)動I/O控制方式直接存儲訪問（DMA）I/O控制方式I/O通道控制方式4.3. I/O軟件層次結(jié)構(gòu)用戶軟件層：實現(xiàn)與用戶的交互。設備獨立性軟件：負責實現(xiàn)與設備驅(qū)動器的統(tǒng)一接口、設備命名、設備保護以及設備分配與釋放設備驅(qū)動軟件：與硬件直接相關(guān)中斷處理程序：保存被終端進程的CPU環(huán)境，轉(zhuǎn)入中斷處理程序處理后再恢復硬件：執(zhí)行I/O操作4.4. I/O調(diào)度概念磁盤的結(jié)構(gòu)分為：盤片、盤面、磁道、扇區(qū)。磁盤的常見分類為：硬盤和軟盤、單片盤和多片盤、固定磁頭和活動磁頭等。2.2.1.2.2.2.3.2.4.4.4.1

24、. 磁盤訪問時間：A. 尋道時間Ts：把磁臂移動到指定磁道上所經(jīng)歷的時間。Ts=m×n+sm是一個常數(shù)，對一般磁盤而言m=0.2,對于高速磁盤m<0.1，s是磁臂啟動時間約為2ms。B. 旋轉(zhuǎn)延遲時間：指定扇區(qū)移動到磁頭下方所經(jīng)歷的時間：對于15000r/min的硬盤，每轉(zhuǎn)約4ms，則其平均延時時間Tr為2msC. 傳輸時間：把數(shù)據(jù)從磁盤讀出或?qū)懭氲臅r間Tt的大小與每次所讀寫的字節(jié)數(shù)b和旋轉(zhuǎn)速度有關(guān)Tt=brN其中，r為磁盤每秒鐘的轉(zhuǎn)數(shù)；N為一條磁道上的字節(jié)數(shù)。因此，訪問時間Ta可表示為：Ta=Ts+12r+brN4.4.2. 磁盤調(diào)度先來先服務（FCFS, first com

25、e first served）最短尋道時間為優(yōu)（SSTF, shotest seek time first）掃描算法（SCAN）循環(huán)掃描算法（CSCAN）NStepSCAN和FSCAN調(diào)度算法4.5. 出錯處理一般而言錯誤多數(shù)是與設備緊密相關(guān)的，因此對錯的處理應盡可能在接近硬件層面處理，在底層軟件能夠解決的錯誤就不讓高層軟件感知，只有底層軟解決不了的錯誤才通知高層軟件解決。4.6. 高速緩存與緩沖區(qū)4.6.1. 緩沖引入的原因：緩和CPU與I/O設備間的速度不匹配矛盾減少CPU的中斷頻率，放寬對CPU中斷響應時間的限制提高CPU和I/O設備之間的并行性4.6.2. 緩沖的種類：單緩沖雙緩沖循環(huán)

26、緩沖緩沖池4.6.3. 高速緩存：磁盤高速緩存是指利用內(nèi)存中的存儲空間來暫存從磁盤讀出的一系列盤塊中的信息。數(shù)據(jù)交付方式：數(shù)據(jù)交付、指針交付。置換算法：LRU、NRU、LFU等。周期性寫回磁盤4.7. 假脫機技術(shù)（SPOOLing）外圍機操作與CPU對數(shù)據(jù)的處理同時進行，這種在聯(lián)機情況下實現(xiàn)的同時外圍操作稱為SPOOLing或假脫機操作。SPOOLing系統(tǒng)的組成：A. 輸入井和輸出井模擬脫機輸入輸出時的磁盤設備B. 輸入緩沖區(qū)和輸出緩沖區(qū)緩和CPU和磁盤的速度不匹配C. 輸入進程SPi和輸出進程SPo模擬外圍控制機SPOOLing設備的特點：A. 提高了I/O速度B. 將獨占設備改造為共享設備C. 實現(xiàn)了虛擬設備功能4.8. 設備分配與回收系統(tǒng)設備表（SDT）設備控制表（DCT）控制器表（COCT）通道表（CHCT）5. 文件管理5.1. 文件系統(tǒng)基礎5.1.1. 文件概念與邏輯結(jié)構(gòu)由創(chuàng)建者所定義的、具