1、操作系統(tǒng)總結(jié)1、1操作系統(tǒng)基本概念1、1、1操作系統(tǒng)概念計算機系統(tǒng)自下而上可分為：硬件、 操作系統(tǒng)、應(yīng)用程序和用戶；操作系統(tǒng)控制和協(xié)調(diào)各用戶的應(yīng)用 程序?qū)τ布姆峙渑c使用；它是系統(tǒng)軟件1、1、2操作系統(tǒng)的特征1、并發(fā)：兩個或多個事件在同一時間間隔內(nèi)發(fā)生；因此它具 有處理和調(diào)度多個程序同時執(zhí)行的能力；引入進(jìn)程的目的使程序 并發(fā)執(zhí)行；微觀上分時交替執(zhí)行，通過分時實現(xiàn)2、共享：系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)的進(jìn)程共同使 用?？煞譃閮煞N：（1）互斥共享：如打印機、磁帶機等。此資 源被占用，其他進(jìn)程訪問該資源必須等待，這類資源被稱為臨界 資源或獨占資源（2）同時訪問：“同時”往往宏觀上，而微觀 上這些進(jìn)

2、程可能是交替對該資源進(jìn)行訪問，例如磁盤并發(fā)與共享 是操作系統(tǒng)兩個最基本的特征3、虛擬：把物理上實體變化為若干個邏輯上的事物，虛擬 技術(shù)。虛擬處理器、虛擬內(nèi)存、虛擬外部設(shè)備等。可分為時分復(fù) 用技術(shù)（如處理器分時共享）、空分復(fù)用（如虛擬存儲器）4、異步：由于資源有限，多個程序并發(fā)執(zhí)行，進(jìn)程執(zhí)行不 是一貫到底而是走走停停，以不可預(yù)知的速度前行。需要采用同 步機制，使每次運行結(jié)果一致1、1、3操作系統(tǒng)的目標(biāo)與功能操作系統(tǒng)（工人）應(yīng)有：處 理機、存儲器、設(shè)備和文件管理（工人有熟練的技能）；還必須 向用戶（雇主）提供接口；可用來擴充機器（機器有工人后功能 更好的發(fā)揮）1、操作系統(tǒng)作為計算機系統(tǒng)資源的管理者

3、（1）處理機分配 和運行都是以進(jìn)程為基本單位，因而對處理機的管理可歸結(jié)為對 進(jìn)程的管理（2）存儲器管理是為了給多道程序運行提供良好的 環(huán)境，方便用戶使用以及提高內(nèi)存利用率（3）文件管理是操作 系統(tǒng)負(fù)責(zé)管理文件系統(tǒng)（4）設(shè)備管理主要任務(wù)是完成用戶I/O 請求，方便用戶使用各種設(shè)備，并提高設(shè)備利用率（工人負(fù)責(zé)， 雇主不需要關(guān)注）2、操作系統(tǒng)作為用戶與計算機硬件系統(tǒng)之間的接口（1） 命令接口：分為聯(lián)機命令接口（交互式命令接口）適用于分時或 實時系統(tǒng)接口，由一組鍵盤操作命令組成；脫機命令接口（批處 理命令接口）適用于批處理系統(tǒng)，它由一組作業(yè)控制命令（作業(yè) 控制語句）組成，應(yīng)寫一份作業(yè)說明書連同作業(yè)一起

4、提交給系統(tǒng) 聯(lián)機命令：雇主說一句話，工人做一件事并反饋，強調(diào)交互性； 脫機命令：雇主把要做的事寫在清單上，工人按清單逐條完成（2）程序接口：由一組系統(tǒng)調(diào)用命令（廣義指令）組成。是操 作系統(tǒng)提供給應(yīng)用程序使用內(nèi)核功能的接口（3）圖形接口 GUI3、操作系統(tǒng)用作擴充機（虛擬機）工人操作了機器，機器 便有了很大的作用，工人便成了擴充機器1、2操作系統(tǒng)的發(fā)展與分類1、2、1手工操作階段（無操作系統(tǒng)）缺點：（1）用戶獨占 全機（2） CPU利用率低1、2、2批處理階段（操作系統(tǒng)出現(xiàn)）為了解決人機矛盾及 CPU與I/O速度不匹配矛盾1、單道批處理：系統(tǒng)對作業(yè)處理是成批的，但內(nèi)存中始終保 持一道作業(yè)。特征：

5、（1）自動性：一批作業(yè)逐個依次運行（2） 順序性：順序裝入內(nèi)存，順序的被執(zhí)行（3）單道性：內(nèi)存中僅 一道程序在執(zhí)行，只有執(zhí)行完或者發(fā)生異常才調(diào)用下一程序問 題：每當(dāng)運行期間發(fā)出I/O請求，高速的CPU便處于等待低速的 I/O完成狀態(tài)2、多道批處理：裝入多個程序在內(nèi)存中，當(dāng)某一個程序因 I/O請求而暫停運行時，CPU便立即轉(zhuǎn)去運行另一道程序，特點： 多道、宏觀上并行、微觀上串行，需要解決的問題：（1）如何 分配處理器（2）多道程序內(nèi)存分配問題（3） I/O設(shè)備如何分配 （4）如何組織和存放大量數(shù)據(jù)，以便于用戶和保證其安全性和 一致性優(yōu)點：資源利用率高，系統(tǒng)吞吐量大，CPU保持忙碌；缺 點：用戶響

6、應(yīng)時間長，不提供人機交互1、2、3分時操作系統(tǒng)實現(xiàn)的關(guān)鍵：如何使用戶能與自己的 作業(yè)進(jìn)行交互，即當(dāng)用戶在自己終端上鍵入命令時，系統(tǒng)應(yīng)能及 時接收并處理該命令，再將結(jié)果返回給用戶。特征：（1）同時 性：多個終端使用一臺計算機（2）交互性：進(jìn)行人-機對話（3）獨立性：互不干擾，感覺自己在獨占全機（4）及時性： 在很短時間內(nèi)得到響應(yīng)1、2、4實時操作系統(tǒng)（1）硬實時系統(tǒng)：某個動作必須絕 對地在規(guī)定時間內(nèi)完成，如飛行器的飛行自動控制系統(tǒng)（2）軟 實時系統(tǒng)：偶爾運行違反時間規(guī)定，不會引起永久性損害，如飛 機票務(wù)系統(tǒng)特點：及時性和可靠性1、2、5網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)網(wǎng)絡(luò)操作系統(tǒng)特 點：網(wǎng)絡(luò)中各種資

7、源的共享以及各臺計算機之間的通信分布式操 作系統(tǒng)特點：分布性和并行性。若干臺計算機協(xié)同完成同一任務(wù)1、2、6個人計算機操作系統(tǒng)1、3操作系統(tǒng)運行環(huán)境1、3、1操作系統(tǒng)的運行機制操作系統(tǒng)中通常CPU執(zhí)行內(nèi)核 程序和用戶自編的系統(tǒng)外層程序，前者管理后者，管理程序要執(zhí) 行一些特權(quán)指令，例如I/O指令、置中斷指令、存取用于內(nèi)存保 護(hù)的寄存器等。劃分了用戶態(tài)（目態(tài)）和核心態(tài)（管態(tài)）一些與 硬件關(guān)聯(lián)緊密的模塊，如時鐘管理、中斷處理等處于最底層，其 次是運行較高的程序，如進(jìn)程管理、存儲器管理等，這兩部分構(gòu) 成了操作系統(tǒng)內(nèi)核，工作在核心態(tài)，內(nèi)核包括：1、時鐘管理：時鐘是最關(guān)鍵的設(shè)備，一個功能是計時，二是 通過

8、時鐘中斷管理，實現(xiàn)進(jìn)程的切換，例如，在分時操作系統(tǒng) 中，采用時間片輪轉(zhuǎn)調(diào)度實現(xiàn)2、中斷機制：為了提高多道程序運行環(huán)境中CPU的利用 率，主要針對外部設(shè)備，例如鍵盤信息輸入、進(jìn)程管理和調(diào)度、 系統(tǒng)調(diào)用等，現(xiàn)代操作系統(tǒng)是靠中斷驅(qū)動的軟件中斷機制中只有 一小部分屬于內(nèi)核，負(fù)責(zé)保護(hù)和恢復(fù)中斷現(xiàn)場信息，轉(zhuǎn)移控制權(quán) 到相關(guān)處理程序，這樣可以減少中斷處理時間，提高系統(tǒng)并行處 理能力。3、原語：操作系統(tǒng)底層必然是一些可被調(diào)用的公用小程 序，各自完成規(guī)定的操作。特點：（1）處理操作系統(tǒng)底層（2） 具有原子性，操作一氣呵成（3）運行時間短，調(diào)用頻繁定義原 語的直接方法是關(guān)閉中斷，讓其所有動作不可分割的執(zhí)行4、系統(tǒng)

9、控制的數(shù)據(jù)結(jié)構(gòu)及處理：為實現(xiàn)有效管理，需要基 本操作：（1）進(jìn)程管理（2）存儲器管理（3）設(shè)備管理核心態(tài) 指令實際上包括系統(tǒng)調(diào)用指令和一些針對時鐘、中斷和原語的操 作指令1、3、2中斷和異常概念系統(tǒng)不允許用戶程序?qū)崿F(xiàn)核心態(tài)功 能，而它們又必須使用這些功能，在核心態(tài)建立一些“門”，通 過中斷或異常，運行用戶態(tài)的CPU會立即進(jìn)入核心態(tài)，通過硬件 實現(xiàn)的；提高資源利用率就需要在程序并未使用某種資源的時 候，把它對那種資源的占有權(quán)釋放，此行為需要中斷實現(xiàn)中斷 （也稱外中斷），指來自CPU執(zhí)行以外的時間的發(fā)生，如設(shè)備發(fā) 出的I/O結(jié)束中斷、時鐘中斷，這類中斷與當(dāng)前處理機運行程序 無關(guān)。異常（也稱內(nèi)中斷或

10、陷入Trap）,源自CPU執(zhí)行指令內(nèi)部 的事件，有非法操作碼、地址越界、算術(shù)溢出、虛存缺頁1、3、3系統(tǒng)調(diào)用（運行在核心態(tài)）用戶在程序中調(diào)用操作 系統(tǒng)所提供的一些子功能?？煞譃樵O(shè)備管理、文件管理、進(jìn)程控 制、進(jìn)程通信和內(nèi)存管理，顯然系統(tǒng)調(diào)用運行在核心態(tài)用戶態(tài)轉(zhuǎn) 入核心態(tài)例子：（1）系統(tǒng)調(diào)用（2）中斷（3）用戶執(zhí)行了錯誤 狀態(tài)（4）用戶程序企圖執(zhí)行特權(quán)指令用戶態(tài)轉(zhuǎn)為核心態(tài)會用到訪 管指令，訪管指令是在用戶態(tài)使用的，不可能是特權(quán)指令1、4操作系統(tǒng)體系結(jié)構(gòu)1、4、1大內(nèi)核與微內(nèi)核大內(nèi)核將操作系統(tǒng)主要功能模塊都 作為一個緊密聯(lián)系的整體運行在核心態(tài)微內(nèi)核將程序中最基本的 功能（如進(jìn)程管理）保留在內(nèi)核，而

11、將那些不需要在核心態(tài)執(zhí)行 的執(zhí)行的功能移到用戶態(tài)執(zhí)行，從而降低內(nèi)核設(shè)計復(fù)雜性；微內(nèi) 核有效的分離了內(nèi)核與服務(wù)，服務(wù)與服務(wù)，使得他們之間接口更 加清晰。微內(nèi)核最大問題是性能的問題，因為需要頻繁的在核心 態(tài)和用戶態(tài)之間進(jìn)行切換，操作系統(tǒng)執(zhí)行開銷大。因此有的操作 系統(tǒng)將那些頻繁使用的系統(tǒng)服務(wù)又移回到內(nèi)核第2章進(jìn)程管理2、1進(jìn)程與線程2、1、1進(jìn)程概念與特征1、進(jìn)程的概念：更好的描述和控制程序的并發(fā)執(zhí)行，實現(xiàn)操 作系統(tǒng)并發(fā)和共享；進(jìn)程控制塊（PCB）,系統(tǒng)利用PCB描述進(jìn)程基本情況和運行狀態(tài)，創(chuàng)建進(jìn)程就是創(chuàng)建PCB；進(jìn)程是系統(tǒng)進(jìn)行資 源分配和調(diào)度的一個獨立單位2、進(jìn)程的特征：動態(tài)性、并發(fā)性、獨立性（凡

12、未建立PCB 的程序都不能作為獨立單位運行）、異步性（操作系統(tǒng)必須配置 相應(yīng)進(jìn)程同步機制）、結(jié)構(gòu)性2、1、2進(jìn)程的狀態(tài)與轉(zhuǎn)換（1）運行狀態(tài)：進(jìn)程在單處理 機上運行，每個時刻最多一個進(jìn)程運行（2）就緒狀態(tài)：獲得除 處理機外的所有所需資源，一旦得到處理機便開始運行（3）阻 塞狀態(tài)（等待狀態(tài)）：進(jìn)程等待某一事件而暫停運行（如等待某 資源可用或I/O完成）（4）創(chuàng)建狀態(tài)：申請一個空白PCB,向其 中填寫控制和管理進(jìn)程信息，系統(tǒng)為該進(jìn)程分配運行所需資源， 最后把該進(jìn)程轉(zhuǎn)入就緒狀態(tài)（5）結(jié)束狀態(tài)：系統(tǒng)先置改進(jìn)程為 結(jié)束狀態(tài)，然后回收釋放資源基本狀態(tài)轉(zhuǎn)換：（1）就緒-運 行：獲得處理機（分配處理機時間片）（

13、2）運行-就緒：時間 片用完，讓出處理機，此外在可剝奪系統(tǒng)中，有更高級進(jìn)程就緒 時，進(jìn)程讓出處理機轉(zhuǎn)化為就緒狀態(tài)（3）運行-阻塞：進(jìn)程請 求某一資源（如外設(shè)）的使用或等待某一事件的發(fā)生（I/O完成） （4）阻塞-就緒：進(jìn)程等待事件到來，如I/O結(jié)束或中斷結(jié) 束，中斷處理程序?qū)⑦M(jìn)程由阻塞變?yōu)榫途w注：運行-阻塞是主動 行為，阻塞-就緒是被動行為2、1、3進(jìn)程控制一般把進(jìn)程控制用的程序段稱為原語1、進(jìn)程的創(chuàng)建：允許一個進(jìn)程創(chuàng)建另一個進(jìn)程（父子進(jìn) 程），操作系統(tǒng)中終端用戶登錄系統(tǒng)、作業(yè)調(diào)度、系統(tǒng)提供服 務(wù)、用戶程序的應(yīng)用請求都會引起進(jìn)程的創(chuàng)建，創(chuàng)建如下：（1） 為新進(jìn)程分配一個唯一的標(biāo)識號，并申請一塊

14、空白的PCB （2）為 進(jìn)程分配資源，為新進(jìn)程的數(shù)據(jù)和程序以及用戶棧分配必要的內(nèi) 存空間，如資源不足，不是分配失敗，而是“等待狀態(tài)”（3） 初始化PCB,包括初始化標(biāo)志信息，初始化處理機狀態(tài)信息和初始 化處理機控制信息，以及設(shè)置進(jìn)程優(yōu)先級2、進(jìn)程的終止：正常結(jié)束異常結(jié)束（如存儲區(qū)越界、 保護(hù)錯、非法指令、特權(quán)指令錯、I/O故障）外界干預(yù)；進(jìn)程終 止步驟：（1）根據(jù)終止進(jìn)程的標(biāo)識符，檢索PCB （2）若被終止 進(jìn)程處于運行狀態(tài)，立即終止進(jìn)程執(zhí)行，把處理機資源分配給其 他進(jìn)程（3）若該進(jìn)程有子進(jìn)程，應(yīng)將其終止（4）將該進(jìn)程所 擁有資源全部歸還給操作系統(tǒng)（或父進(jìn)程）（5）將該PCB從隊 列（鏈表）中

15、刪除3、進(jìn)程的阻塞與喚醒：如請求資源失敗、等待某種操作完 成、新數(shù)據(jù)尚未到達(dá)，系統(tǒng)自動執(zhí)行阻塞原語（Block）,是一個 主動行為，也只有運行狀態(tài)的進(jìn)程才能阻塞，阻塞原語：（1） 找到此PCB（2）若該進(jìn)程為運行狀態(tài)，保護(hù)其現(xiàn)場，將其轉(zhuǎn)化為 阻塞狀態(tài)（3）將該PCB插入相應(yīng)事件等待隊列中若期待的事件 出現(xiàn)，調(diào)用喚醒原語（Wakeup）,被動行為，喚醒原語：（1） 在該事件的等待隊列中找到相應(yīng)PCB （2）將其從等待隊列中移出，并置就緒狀態(tài)（3）把該PCB插入就緒隊列中，等待調(diào)度程 序調(diào)度4、進(jìn)程的切換：任何進(jìn)程都是在操作系統(tǒng)內(nèi)核的支持下運 行的，進(jìn)程切換：（1）保存處理機上下文，包括程序計數(shù)器

16、和 其他寄存器（2）更新PCB （3）把進(jìn)程的PCB移入相應(yīng)的隊列中 （4）選擇另一個進(jìn)程，更新其PCB（5）更新內(nèi)存管理的數(shù)據(jù)結(jié) 構(gòu)（6）恢復(fù)處理機上下文2、1、4進(jìn)程的組織（組成）1、進(jìn)程控制塊（PCB）：常駐內(nèi)存，包括進(jìn)程描述信息、進(jìn) 程控制和管理信息、資源分配清單和處理機相關(guān)信息2、程序段：多個進(jìn)程可以運行同一程序3、數(shù)據(jù)段2、1、5進(jìn)程的通信（高級通信方式）1、共享存儲：通信進(jìn)程之間存在一個共享空間，通過對這片 空間進(jìn)行讀寫操作實現(xiàn)進(jìn)程信息交換。需要使用同步互斥工具（如PV操作），操作系統(tǒng)只提供通信進(jìn)程可共享的存儲空間和同 步互斥工具。進(jìn)程運行期間不能訪問其他進(jìn)程空間，而進(jìn)程中的 線

17、程是共享進(jìn)程的注：簡單理解：甲和乙中間有個大布袋，甲和 乙交換物品通過大布袋進(jìn)行，而不能直接交換2、消息傳遞：進(jìn)程間的消息是以格式化的信息為單位的， 進(jìn)程之間通過操作系統(tǒng)提供的發(fā)送消息和接收消息兩個原語進(jìn)行 數(shù)據(jù)交換（1）直接通信方式：發(fā)送進(jìn)程直接把消息發(fā)送給接收 進(jìn)程，并將它掛在接收進(jìn)程的消息緩沖區(qū)隊列上，接收進(jìn)程從消 息緩沖隊列中取得消息。（2）間接通信方式：發(fā)送進(jìn)程將消息 發(fā)送到中間實體（信箱）接收進(jìn)程從信箱中取得消息，廣泛應(yīng)用 于計算機網(wǎng)絡(luò)簡單理解：甲要告訴乙一些事情，就要寫信，然后 通過郵差交給乙，直接通信就是郵差把信直接送到乙手里，間接 通信就是乙家門口有個郵箱，郵差把信放到郵箱里

18、。3、管道通信：消息傳遞的一種特殊方式，“管道”是指用 于連接一個讀進(jìn)程和一個寫進(jìn)程以實現(xiàn)通信的一個共享文件 （pipe）,為協(xié)調(diào)雙方通訊，必須有互斥、同步和確定對方存 在；從管道讀數(shù)據(jù)是一次性操作，數(shù)據(jù)一旦被讀取，它就從管道 中被拋棄，釋放空間以便寫更多數(shù)據(jù)，某一時刻只能單向傳輸2、1、6線程概念和多線程模型1、線程的基本概念：引入線程是為了減小程序在并發(fā)執(zhí)行時 所付出的時空開銷，提高操作系統(tǒng)的并發(fā)性能。線程是一個基本 的CPU執(zhí)行單元，也是程序執(zhí)行流的最小單元。是被系統(tǒng)獨立調(diào) 度和分派的基本單位，不擁有系統(tǒng)資源。同一進(jìn)程中多個線程可 并發(fā)執(zhí)行。引入線程后進(jìn)程只作為除CPU以外系統(tǒng)資源的分配

19、單 元，而線程作為處理機分配單元。線程的切換發(fā)生在同一進(jìn)程內(nèi) 部，只需很少的時空開銷2、線程與進(jìn)程的比較（1）調(diào)度：線程是獨立調(diào)度的基本 單位，進(jìn)程是擁有資源的基本單位，同一進(jìn)程中線程切換不會引 起進(jìn)程切換（2）擁有資源：但線程可以訪問其隸屬的進(jìn)程的資 源，線程基本不擁有資源（3）并發(fā)性：多個線程也可以并發(fā)執(zhí) 行（4）系統(tǒng)開銷：創(chuàng)建和撤銷進(jìn)程的開銷遠(yuǎn)大于創(chuàng)建和撤銷線 程的開銷（5）地址空間和其他資源：某進(jìn)程內(nèi)的線程對于其他 進(jìn)程不可見3、線程的屬性（1）不擁有系統(tǒng)資源，每個線程都有一個 唯一標(biāo)識符和一個線程控制塊，記錄了線程執(zhí)行的寄存器和棧等 （2）不同線程可以執(zhí)行相同程序（3）同一進(jìn)程中各個

20、線程共 享該進(jìn)程所擁有的資源（4）線程是處理機獨立調(diào)度單位，多個 線程可并發(fā)執(zhí)行4、線程的實現(xiàn)方式：用戶級線程和內(nèi)核級線程5、多線程模型（1）多對一：多個用戶級線程映射到一個 內(nèi)核級線程，一個線程被阻塞后整個進(jìn)程都被阻塞；優(yōu)點：效率 高；缺點：多個線程不能并行的運行在多處理機上（2） 一對 一：每個用戶級線程映射到一個內(nèi)核級線程；優(yōu)點：一個線程被 阻塞后允許另一個線程繼續(xù)執(zhí)行，并發(fā)性較強；缺點：創(chuàng)建線程 開銷比較大（3）多對多：集兩者之長2、2處理機調(diào)度2、2、1調(diào)度的概念1、調(diào)度的基本概念：處理機調(diào)度是操作系統(tǒng)設(shè)計的核心問 題。2、調(diào)度的層次（1）作業(yè)調(diào)度（高級調(diào)度）：按一定原則 從外存上處

21、于后備狀態(tài)的作業(yè)中挑選一個（或多個）作業(yè)，給它 們分配內(nèi)存、輸入/輸出設(shè)備等必要資源，并建立相應(yīng)的進(jìn)程，以 使它們獲得競爭處理機的權(quán)利（就是內(nèi)存與外存之間的調(diào)度，每 個作業(yè)只調(diào)入和調(diào)出一次，執(zhí)行效率低）（2）內(nèi)存調(diào)度（中級 調(diào)度）：為了提高內(nèi)存利用率和系統(tǒng)吞吐量。應(yīng)使那些暫時不運 行的進(jìn)程調(diào)至外存等待，此時進(jìn)程稱為掛起狀態(tài)，當(dāng)內(nèi)存有空閑 時將進(jìn)程從外存調(diào)入內(nèi)存，修改狀態(tài)為就緒，掛在就緒隊列上等 待。（3）進(jìn)程調(diào)度（低級調(diào)度）：按照某個策略調(diào)度，頻率大 概幾毫秒一次2、2、2調(diào)度的時機、切換和過程1、進(jìn)程調(diào)度和切換程序是系統(tǒng)內(nèi)核程序。進(jìn)程調(diào)度會引起進(jìn) 程切換（有時不能）2、不能進(jìn)行進(jìn)程調(diào)度和切換

22、的情況：（1）在處理中斷過 程中：是系統(tǒng)工作的一部分，邏輯上不屬于進(jìn)程，不應(yīng)被剝奪處 理機（2）進(jìn)程在操作系統(tǒng)內(nèi)核的臨界區(qū)：進(jìn)入臨界區(qū)需要加 鎖，以防止其他進(jìn)程進(jìn)入，解鎖前不應(yīng)切換到其他進(jìn)程（3）其 他需要完全屏蔽中斷的原子操作過程中：如加鎖、解鎖、中斷現(xiàn) 場保護(hù)、恢復(fù)等如果上述事情發(fā)生，不能立即進(jìn)程調(diào)度與切換， 應(yīng)置系統(tǒng)請求調(diào)度標(biāo)志，等待上述事件完成3、應(yīng)該進(jìn)行進(jìn)程調(diào)度與切換情況：（1）當(dāng)發(fā)生引起調(diào)度 的條件，且當(dāng)前進(jìn)程無法繼續(xù)運行下去，可以馬上進(jìn)程調(diào)度切換（非剝奪調(diào)度）（2）當(dāng)中斷處理結(jié)束或trap處理結(jié)束時，返回 被中斷進(jìn)程的用戶態(tài)程序執(zhí)行現(xiàn)場前，若置上請求調(diào)度標(biāo)志，即 可馬上進(jìn)行進(jìn)程調(diào)

23、度和切換（剝奪式調(diào)度）進(jìn)程切換往往在調(diào)度 完成后立即發(fā)生，它要求保存原進(jìn)程當(dāng)前切換點的現(xiàn)場信息，恢 復(fù)被調(diào)度進(jìn)程的現(xiàn)場信息，現(xiàn)場切換時，操作系統(tǒng)內(nèi)核將原進(jìn)程 現(xiàn)場信息推入到當(dāng)前進(jìn)程內(nèi)核堆棧來保存他們，并更新堆棧指針2、2、3進(jìn)程調(diào)度方式（有更高級的進(jìn)程要進(jìn)入怎么處理） （1）非剝奪調(diào)度方式（非搶占式）：當(dāng)前進(jìn)程直到完成或發(fā)生 進(jìn)入阻塞，一旦CPU被分配，該進(jìn)程保持CPU直至終止或到阻塞 狀態(tài)；特點實現(xiàn)簡單、開銷小，適用于大多數(shù)批處理系統(tǒng)，不能 用于分時系統(tǒng)和實時系統(tǒng)（2）剝奪調(diào)度方式（搶占式）：有更 為緊迫的進(jìn)程需要執(zhí)行時應(yīng)立即讓出處理機；特點對提高系統(tǒng)吞 吐率和響應(yīng)效率都有明顯好處2、2、4

24、調(diào)度的基本準(zhǔn)則1、CPU利用率：盡量保持CPU忙碌2、系統(tǒng)吞吐量：表示單位時間內(nèi)CPU完成作業(yè)數(shù)量3、周轉(zhuǎn)時間：指從作業(yè)提交到作業(yè)完成所經(jīng)歷的時間，帶 權(quán)周轉(zhuǎn)時間二作業(yè)周轉(zhuǎn)時間/作業(yè)實際運行時間4、等待時間：指進(jìn)程等待處理機時間之和；處理機調(diào)度算 法并不影響作業(yè)執(zhí)行或輸入/輸出操作時間，而只影響作業(yè)在就緒 隊列中等待所花的時間（調(diào)度算法的優(yōu)劣，只需簡單判斷等待時 間）5、響應(yīng)時間：指從用戶提交請求到系統(tǒng)首次產(chǎn)生響應(yīng)所用 的時間（交換式系統(tǒng)中評價準(zhǔn)則）2、2、5典型調(diào)度算法（重點）1、先來先服務(wù)（FCFS）：屬于不可剝奪算法，不能作為分時 和實時系統(tǒng)；特點：算法簡單、效率低；對長作業(yè)有利，對短作

25、 業(yè)不利，有利于CPU繁忙型作業(yè)，不利于I/O繁忙型作業(yè)例：假 設(shè)系統(tǒng)中有4個作業(yè)，它們的提交時間分別是8、8、4、8、8、9,運行時間依次是2、1、0、5、0、2,系統(tǒng)采用FCFS調(diào)度算法，這組作業(yè)的平 均等待時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間見表平均等待時 間 t = （0+1、6+2、2+2、5）/4二1、575平均周轉(zhuǎn)時間T = （2+2、6+2、7+2、7）/4二2、5平均帶權(quán)周轉(zhuǎn)時間W = （1+2、6+5、牡13、 5）/4=5、6252、短作業(yè)優(yōu)先（SJF）：對長作業(yè)不利（會導(dǎo)致饑餓現(xiàn) 象），不能保證緊迫作業(yè)會被及時處理，但平均等待時間和平均 周轉(zhuǎn)時間最少考慮上表中給出的一組

26、作業(yè)，若系統(tǒng)采用短作業(yè)優(yōu) 先調(diào)度算法，其平均等待時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時 間見表平均等待時間t = （0+2、3+1、 4+1）/4=1、175平均周轉(zhuǎn)時間T = （2+3、3+1、9+1、2）/4二2、1平均帶權(quán)周轉(zhuǎn)時間W = （1+3、3+8+6）/4二3、5253、優(yōu)先級調(diào)度算法：既可以作業(yè)調(diào)度也可進(jìn)程調(diào)度（1） 非剝奪式優(yōu)先級調(diào)度算法（2）剝奪式優(yōu)先級調(diào)度算法根據(jù)創(chuàng)建 后優(yōu)先級是否可以改變：靜態(tài)優(yōu)先級（不可改變）、動態(tài)優(yōu)先級 （可改變）4、高響應(yīng)比優(yōu)先：主要用于作業(yè)調(diào)度；響應(yīng)比；等待時間 相同，要求服務(wù)時間越短響應(yīng)比越高（有利于短作業(yè)）；要求服務(wù)時間相同，等待時間越長響應(yīng)比越

27、高（實現(xiàn)FCFS）,兼顧了長 作業(yè)，避免饑餓5、時間片輪轉(zhuǎn)：適用于分時系統(tǒng)：若時間過大，就化為先 來先服務(wù)，若時間片很小，那處理機切換頻繁，處理機開銷增 大，合理選擇時間片大小6、多級反饋隊列（集合前幾種優(yōu)點）：優(yōu)勢：終端型作業(yè) 用戶，短作業(yè)優(yōu)先；短批處理作業(yè)用戶，周轉(zhuǎn)時間短；長批處理 作業(yè)用戶，經(jīng)過前面幾個隊列得到部分執(zhí)行，不會長期得不到處 理2、3進(jìn)程同步2、3、1進(jìn)程同步的基本概念1、臨界資源：一次僅允許一個進(jìn)程使用的資源，如打印機 等，進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)，可以把臨界資 源的訪問過程分為四個部分：（1）進(jìn)入?yún)^(qū)：在進(jìn)入?yún)^(qū)檢查是否 可以進(jìn)入臨界區(qū)，若可以進(jìn)入，則應(yīng)設(shè)置正在

28、訪問臨界區(qū)的標(biāo) 志，以阻止其他進(jìn)程同時進(jìn)入臨界區(qū)（2）臨界區(qū)：進(jìn)程中訪問 臨界資源的那段代碼（3）退出區(qū)：將正在訪問臨界區(qū)標(biāo)志清除 （4）剩余區(qū)：代碼中其余部分2、同步（直接制約關(guān)系）：例如，進(jìn)程A通過緩沖區(qū)向進(jìn) 程B提供數(shù)據(jù)，緩沖區(qū)空時，進(jìn)程B不能獲得數(shù)據(jù)而阻塞，一旦 進(jìn)程A將數(shù)據(jù)輸入緩沖區(qū)，進(jìn)程B被喚醒，反之，緩沖區(qū)滿時， 進(jìn)程A被阻塞，僅當(dāng)進(jìn)程B取走緩沖區(qū)數(shù)據(jù)時，才喚醒進(jìn)程A3、互斥(間接制約關(guān)系)：當(dāng)一個進(jìn)程進(jìn)入臨界區(qū)使用臨 界資源時，另一個進(jìn)程必須等待；為禁止兩個進(jìn)程同時進(jìn)入臨界 區(qū)，同步機制應(yīng)遵循準(zhǔn)則：(1)空閑讓進(jìn)(2)忙則等待(3) 有限等待：對請求訪問的進(jìn)程，應(yīng)保證能在有限的

29、時間進(jìn)入臨界 區(qū)(4)讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時，應(yīng)立即釋放處理 器，防止進(jìn)程忙等待2、3、2實現(xiàn)臨界區(qū)互斥的基本方法1、軟件實現(xiàn)方法：在進(jìn)入?yún)^(qū)設(shè)置和檢查一些標(biāo)志來表明是否 有進(jìn)程在臨界區(qū)，如果已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)循環(huán)檢查 進(jìn)行等待，進(jìn)程離開臨界區(qū)后則在退出區(qū)修改標(biāo)志。(1)單標(biāo) 志法：設(shè)置一個公用整型變量turn,用于指示被允許進(jìn)入臨界區(qū) 的進(jìn)程編號，確保每次只允許一個進(jìn)程進(jìn)入臨界區(qū)；但兩個進(jìn)程 必須交替進(jìn)入臨界區(qū)，如果某個進(jìn)程不再進(jìn)入臨界區(qū)，那么另一 個進(jìn)程也將無法進(jìn)入臨界區(qū)(違背“空閑讓進(jìn)”) POPlwhile(turn != 0)；while(turn !=1)；cri

30、tical section；critical section；turn =1；turn = 0；remainder section； remainder section； (2) 雙標(biāo)志法先檢查：在每個進(jìn) 程訪問臨界資源之前，先查看臨界資源是否被訪問，若被訪問， 該進(jìn)程等待，為此設(shè)置一個如第i個元素值為FALSE, Pi未進(jìn)入臨界區(qū)；優(yōu)點：不用交替進(jìn)入，可以連續(xù)使用(2) Pi 和Pj可能同時進(jìn)入臨界區(qū)，違背“忙則等待 PiPjwhile(flagj) ； while (flag i) ； flagi=true；flagj = true；critical section；critical se

31、ction；flagi = false；flagj = false；remainder section； remainder section； (3) 雙標(biāo)志后檢查法：先設(shè)置自 己的標(biāo)志位true后，再檢測對方標(biāo)志狀態(tài)，若對方標(biāo)志為true, 則進(jìn)程等待，否則進(jìn)入臨界區(qū)；同時執(zhí)行while循環(huán)，發(fā)現(xiàn)雙方 都想進(jìn)入臨界區(qū)，于是互相謙讓，導(dǎo)致“饑餓”現(xiàn)象PiPjflagi =true；flagj=true；while(flagj)；while(flagi)；critical section；critical section；flagi = false；flagj= false；remainder

32、section；remainder section； (4)Peterson , s Algorithm：為了防止兩個進(jìn)程為進(jìn)入臨界區(qū)而無限 等待，又設(shè)置變量tu門1,每個進(jìn)程在設(shè)置自己標(biāo)志后再設(shè)置turn 標(biāo)志，這時，再同時檢測另一個進(jìn)程狀態(tài)標(biāo)志和不允許進(jìn)入標(biāo) 志，這樣可以保證兩個進(jìn)程同時要求進(jìn)入臨界區(qū)只允許一個進(jìn)入； 利用flag解決臨界資源互斥訪問，而利用turn解決“饑餓”現(xiàn) M PiPjflagi = true；turn=j；flagj=true；turn=i；while(flagj&turn=j)；while(flagi&turn= i)；critical section；crit

33、ical section；flagi=false；flagj = false；remainder section；remainder section； 2、硬件實現(xiàn)方法(1)中斷屏蔽方法：當(dāng)一個進(jìn)程正在使 用它的臨界代碼時，防止其他進(jìn)程進(jìn)入其臨界區(qū)的方法是禁止一 切中斷發(fā)生(關(guān)中斷或屏蔽中斷)，因為CPU只在發(fā)生中斷時引 起進(jìn)程切換；這種方法限制了處理機交替執(zhí)行程序的能力，因此 執(zhí)行效率很低，關(guān)中斷不能交給用戶(2)硬件指令方法 TestAndSet指令：原子操作，執(zhí)行該代碼不允許被中斷，功能是 讀出指定標(biāo)志后把該標(biāo)志設(shè)置為true；可以為每個臨界資源設(shè)置 一個共享布爾變量lock, true

34、表示被占用，初始值為FALSE,進(jìn) 程訪問臨界資源之前，利用TestAndSet檢查和修改標(biāo)志lock,若 有進(jìn)程在臨界區(qū)，則重復(fù)檢查，直到進(jìn)程退出。Swap指令：功能 是交換兩個字節(jié)內(nèi)容為每個臨界資源設(shè)置一個lock,初始為 FALSE,在每個進(jìn)程中設(shè)置一個局部變量key,用于與lock交換信 息，在進(jìn)入臨界區(qū)之前先利用Swap交換lock與key的值，然后 檢查key狀態(tài)，有進(jìn)程在臨界區(qū)時，重復(fù)交換和檢查進(jìn)程，直到 進(jìn)程退出硬件方法優(yōu)點：適用于任意數(shù)目的進(jìn)程，不管是單處理 機還是多處理機，簡單、容易驗證其正確性，可以支持進(jìn)程內(nèi)有 多個臨界區(qū)，只需為每個臨界區(qū)設(shè)置一個布爾變量硬件實現(xiàn)缺 點：

35、進(jìn)程等待進(jìn)入臨界區(qū)時要耗費處理機的時間，不能實現(xiàn)讓權(quán) 等待，從等待進(jìn)程中隨機選擇一個進(jìn)入臨界區(qū)，有的一直選不 上，造成饑餓現(xiàn)象2、3、3信號量只能被兩個標(biāo)準(zhǔn)原語wait(S)和signal(S)訪 問，記為操作和“V”操作信號量：比如記錄資源的數(shù)量， 等待資源的進(jìn)程數(shù)。比如信號量S=3代表資源目前還有3個，沒 有進(jìn)程阻塞；S二-2代表資源已經(jīng)都被占用，且阻塞隊列中等待資 源的進(jìn)程有2個1、整型信號量：用于表示資源數(shù)目的整型量S,申請得到一 個此資源，資源數(shù)就會減1; wait中，只要SCO,就會不斷測 試，因此，該機制并未遵循“讓權(quán)等待”，處于“忙等”狀態(tài) wait (S)申請得到資源 STw

36、hile(S value0)add this process to S、 L；block(S. L)；S、 value一表 示進(jìn)程請求一個該類資源，當(dāng)S、value0,表示該類資源已分配 完畢,因此進(jìn)程調(diào)用block原語，進(jìn)行自我阻塞，放棄處理機， 并插入到該類資源等待隊列S、L中void signal (semaphore S)相當(dāng)于釋放資源 S、value+； if(S、value0) remove a process P from S、L； wakeup(P)； Signal 操 作，表示釋放一個此類資源，若加1后還是S、value S3的前驅(qū)關(guān)系，應(yīng)分別設(shè)置信號量a1、a2o同樣，為了

37、保證S2S5、 S3 S6、S5消費者：一組生產(chǎn)者消費者共享一個初始為空、大小為 n的緩沖區(qū)，只有沒滿，生產(chǎn)者才能把消息放入緩沖區(qū)，否則只能 等待；只有緩沖區(qū)不空，消費者才能從中取得消息，否則必須等 待，緩沖區(qū)只允許一個生產(chǎn)者放入消息或一個消費者取走消息 semaphore mutex =1；臨界區(qū)互斥信號量 semaphore empty = n；空閑緩沖區(qū)semaphore full = 0；緩沖區(qū)初始化為空 producer ()while (1)produce an item in nextp；P(empty)； 獲取空緩沖區(qū)單元 P (mutex) ；add nextp to buffer； V (mutex) ； V(full)； 滿緩沖區(qū) 力口 1 consumer。(while (1)P(full)；獲取滿緩沖區(qū) P(mutex) ； remove an item from buffer； V(mutex) ；V(empty)； 空緩沖區(qū)加 Icosume the item； 注：P操作是要用什么，檢查一下(一操作)，V操作是提供什么 (+操作)例：桌