操作系統(tǒng)課件-孟慶昌【深度薈萃】

1、第1章操作系統(tǒng)引論,1,行業(yè)特制,參考書： 操作系統(tǒng)精髓與設(shè)計原理第五版 William Stalling 著 操作系統(tǒng)原理與設(shè)計 曹先彬 陳蘭香 編 操作系統(tǒng)第二版 孟慶昌 牛欣源 編,2,行業(yè)特制,本章內(nèi)容提要,計算機(jī)硬件結(jié)構(gòu) 什么是操作系統(tǒng) 操作系統(tǒng)概念 操作系統(tǒng)的主要功能 操作系統(tǒng)的地位 操作系統(tǒng)的發(fā)展歷程 操作系統(tǒng)的類型 操作系統(tǒng)的特征 操作系統(tǒng)結(jié)構(gòu)設(shè)計,3,行業(yè)特制,1.1計算機(jī)硬件結(jié)構(gòu),計算機(jī)系統(tǒng)是由硬件和軟件組成的 硬件是軟件建立與活動的基礎(chǔ) 軟件是對硬件進(jìn)行管理和功能擴(kuò)充 計算機(jī)硬件結(jié)構(gòu) 由五大功能部件組成，即：運(yùn)算器、控制器、存儲器、輸入設(shè)備和輸出設(shè)備。 它們經(jīng)由系統(tǒng)總線連

2、接在一起，實(shí)現(xiàn)彼此通信。,4,行業(yè)特制,現(xiàn)代計算機(jī)硬件結(jié)構(gòu),5,行業(yè)特制,1.1.1 處理器,CPU工作的基本周期是： 提取指令，譯碼分析，執(zhí)行指令 每個CPU可以執(zhí)行的指令集是專用的 所有CPU都包含某些寄存器 通用寄存器 專用寄存器 程序計數(shù)器 棧指針 PSW（程序狀態(tài)字） 兩種處理機(jī)執(zhí)行狀態(tài) 核心態(tài) 用戶態(tài),6,行業(yè)特制,1.1.2 存儲器,寄存器 高速緩存 內(nèi)存 磁盤 磁帶,7,行業(yè)特制,1.1.3 I/O設(shè)備,通常由控制器和設(shè)備本身兩部分組成 控制器 設(shè)備 設(shè)備驅(qū)動程序,8,行業(yè)特制,1.1.4 總線,總線分類 數(shù)據(jù)總線 地址總線 控制總線,9,行業(yè)特制,1.2 什么是操作系統(tǒng),1.

3、2.1 操作系統(tǒng)概念 1操作系統(tǒng)作為擴(kuò)展機(jī)器 把硬件細(xì)節(jié)與程序員隔離開，隱藏了底層硬件的特性 功能更強(qiáng)、使用更方便 2操作系統(tǒng)作為資源管理器 監(jiān)視各種資源，隨時記錄它們的狀態(tài)； 實(shí)施某種策略以決定誰獲得資源，何時獲得，獲得多少； 分配資源供需求者使用； 回收資源，以便再分配。 3. 操作系統(tǒng)的用戶觀點(diǎn)和系統(tǒng)觀點(diǎn),10,行業(yè)特制,定義： 操作系統(tǒng)是控制和管理計算機(jī)系統(tǒng)內(nèi)各種硬件和軟件資源，有效地組織多道程序運(yùn)行的系統(tǒng)軟件（或程序集合），是用戶與計算機(jī)之間的接口。,11,行業(yè)特制, 操作系統(tǒng)是系統(tǒng)軟件 基本職能是控制和管理系統(tǒng)內(nèi)各種資源，有效地組織多道程序的運(yùn)行 提供眾多服務(wù)，方便用戶使用，擴(kuò)充硬

4、件功能,12,行業(yè)特制,1.2.2 操作系統(tǒng)的主要功能,1存儲管理 內(nèi)存分配 地址映射 內(nèi)存保護(hù) 內(nèi)存擴(kuò)充,13,行業(yè)特制,1.2.2 操作系統(tǒng)的主要功能,2作業(yè)和進(jìn)程管理 作業(yè)和進(jìn)程調(diào)度 進(jìn)程控制 進(jìn)程通信,14,行業(yè)特制,1.2.2 操作系統(tǒng)的主要功能,3設(shè)備管理 緩沖區(qū)管理 設(shè)備分配 設(shè)備驅(qū)動 設(shè)備無關(guān)性,15,行業(yè)特制,1.2.2 操作系統(tǒng)的主要功能,4文件管理功能 文件存儲空間的管理 文件操作的一般管理 目錄管理 文件的讀/寫管理和存取控制,16,行業(yè)特制,1.2.2 操作系統(tǒng)的主要功能,5用戶接口 程序接口 命令行接口 圖形用戶接口（GUI）,17,行業(yè)特制,1.2.3 操作系統(tǒng)的

5、地位,計算機(jī)系統(tǒng)的層次關(guān)系,18,行業(yè)特制,簡言之，軟件是計算機(jī)執(zhí)行的程序 軟件通?？煞譃槿箢?應(yīng)用軟件 支撐軟件 系統(tǒng)軟件 操作系統(tǒng)是裸機(jī)之上的第1層軟件，它只在核心態(tài)模式下運(yùn)行。 通常把經(jīng)過軟件擴(kuò)充功能后的機(jī)器稱為“虛擬機(jī)”,19,行業(yè)特制,1.3 操作系統(tǒng)的發(fā)展歷程,1.3.1 操作系統(tǒng)的形成 1手工操作階段 2早期批處理階段 早期聯(lián)機(jī)批處理 早期脫機(jī)批處理 3多道批處理系統(tǒng),20,行業(yè)特制,多道批處理系統(tǒng),21,行業(yè)特制,多道程序設(shè)計： 在內(nèi)存中同時存放多道程序，在管理程序的控制下交替地執(zhí)行。這些作業(yè)共享CPU和系統(tǒng)中的其他資源。 并發(fā)：多道程序在CPU上交替運(yùn)行 系統(tǒng)吞吐量： 在一

6、段給定的時間內(nèi)，計算機(jī)所能完成的總工作量。,22,行業(yè)特制,1.3.2 操作系統(tǒng)的發(fā)展,23,行業(yè)特制,1.3.3 推動操作系統(tǒng)發(fā)展的動力,硬件技術(shù)更新 應(yīng)用需求擴(kuò)大,24,行業(yè)特制,1.4 操作系統(tǒng)的類型,5大基本類型 批處理系統(tǒng) 分時系統(tǒng) 實(shí)時系統(tǒng) 網(wǎng)絡(luò)系統(tǒng) 分布式系統(tǒng),25,行業(yè)特制,1.4.1 批處理系統(tǒng),1作業(yè) 是用戶定義的、由計算機(jī)完成的工作單位。它通常包括一組計算機(jī)程序、文件和對操作系統(tǒng)的控制語句。 作業(yè)步 由作業(yè)控制語句明確標(biāo)識的計算機(jī)程序的執(zhí)行過程,26,行業(yè)特制,2工作流程,多道批處理系統(tǒng)中的作業(yè)流程,27,行業(yè)特制,批處理系統(tǒng),3.特點(diǎn) 多道：系統(tǒng)在內(nèi)存中存放多個作業(yè)，并

7、且在外存上還保存大量的后備作業(yè)。 成批：系統(tǒng)按批次調(diào)度作業(yè)，而在系統(tǒng)運(yùn)行過程中不允許用戶和機(jī)器之間發(fā)生交互作用。 批處理系統(tǒng)的主要優(yōu)點(diǎn)： 系統(tǒng)資源利用率高 系統(tǒng)吞吐量大 明顯缺點(diǎn)： 用戶作業(yè)的等待時間長 沒有交互能力,28,行業(yè)特制,1.4.2 分時系統(tǒng),1分時概念和分時系統(tǒng)的實(shí)現(xiàn)方法 分時：廣義上，是指對時間的共享。 在分時系統(tǒng)中，分時主要是指若干并發(fā)程序?qū)PU時間的共享 并行：是指在同一時刻有兩個或兩個以上的活動發(fā)生。 時間片,29,行業(yè)特制,分時系統(tǒng),2分時系統(tǒng)的特征和優(yōu)點(diǎn) 基本特征 同時性 交互性 獨(dú)立性 及時性 主要優(yōu)點(diǎn) 人機(jī)交互友好 應(yīng)用方便 資源共享,30,行業(yè)特制,1.4.3

8、 實(shí)時系統(tǒng),1實(shí)時系統(tǒng)的引入 實(shí)時系統(tǒng) 具有實(shí)時特性，能夠支持實(shí)時控制系統(tǒng)工作的操作系統(tǒng)。 重要特征：對時間有嚴(yán)格限制和要求 三種典型應(yīng)用形式 過程控制系統(tǒng) 信息查詢系統(tǒng) 事務(wù)處理系統(tǒng),31,行業(yè)特制,2實(shí)時系統(tǒng)與分時系統(tǒng)的差別 交互性 實(shí)時性 可靠性,32,行業(yè)特制,實(shí)時系統(tǒng),3實(shí)現(xiàn)方式 硬式實(shí)時系統(tǒng) 對時間嚴(yán)格約束 軟式實(shí)時系統(tǒng) 對時間限制稍弱一些,33,行業(yè)特制,1.4.4 網(wǎng)絡(luò)操作系統(tǒng),1計算機(jī)網(wǎng)絡(luò)的特征 分布性 自治性 互連性 可見性,34,行業(yè)特制,2網(wǎng)絡(luò)操作系統(tǒng) 服務(wù)器 客戶機(jī) 網(wǎng)絡(luò)操作系統(tǒng)實(shí)現(xiàn)網(wǎng)絡(luò)通信、資源共享和保護(hù)， 以及提供網(wǎng)絡(luò)服務(wù)和網(wǎng)絡(luò)接口等 本地操作系統(tǒng)完成本地資源的管

9、理和服務(wù)功能 客戶-服務(wù)器模式 Sun公司的NFS Novell公司的Netware 5.0 Microsoft公司的Windows NT Server 4.0 IBM公司的LAN Server 4.0 SCO公司的UNIX Ware 7.1 自由軟件Linux,35,行業(yè)特制,3網(wǎng)絡(luò)操作系統(tǒng)的特性 接口一致性 資源透明性 操作可靠性 處理自主性 執(zhí)行并行性,36,行業(yè)特制,1.4.5 分布式操作系統(tǒng),分布式系統(tǒng)特點(diǎn) 透明性 靈活性 可靠性 高性能 可擴(kuò)充性,37,行業(yè)特制,1.4.6 其他操作系統(tǒng),1.個人機(jī)系統(tǒng) Windows XP、Windows Vista、UNIX、Linux 2.多

10、處理器系統(tǒng) 對稱多處理（SMP）系統(tǒng) 增加吞吐量 提高性能/價格比 提高可靠性 3嵌入式系統(tǒng),38,行業(yè)特制,1.5 操作系統(tǒng)的特征,（1）并發(fā) 兩個或多個活動在同一給定的時間間隔中進(jìn)行。 （2）共享 計算機(jī)系統(tǒng)中的資源被多個進(jìn)程所共用。 （3）不確定性 系統(tǒng)中各種事件發(fā)生順序的不可預(yù)測性。,39,行業(yè)特制,1.6 操作系統(tǒng)結(jié)構(gòu)設(shè)計,1.6.1 整體系統(tǒng) 任意調(diào)用，耦合緊密， 實(shí)現(xiàn)的效率高 結(jié)構(gòu)關(guān)系不清晰， 系統(tǒng)的可靠性降低,模塊調(diào)用示意圖,40,行業(yè)特制,1.6.2 層次式系統(tǒng),THE操作系統(tǒng)的層次結(jié)構(gòu) 具有整體系統(tǒng)的長處 新優(yōu)點(diǎn)結(jié)構(gòu)關(guān)系清晰，提高系統(tǒng)的可靠性、可移植性和可維護(hù)性。,41,行

11、業(yè)特制,1.6.3 虛擬機(jī)結(jié)構(gòu),帶CMS的VM/370結(jié)構(gòu),通過共享物理機(jī)器資源來實(shí)現(xiàn) 主要優(yōu)點(diǎn) 同時運(yùn)行多個操作系統(tǒng) 系統(tǒng)安全,有效地保護(hù)系統(tǒng)資源 提供良好的工作環(huán)境 組建虛擬網(wǎng)絡(luò),42,行業(yè)特制,1.6.4 客戶-服務(wù)器系統(tǒng),客戶-服務(wù)器系統(tǒng)模型 微內(nèi)核,43,行業(yè)特制,客戶-服務(wù)器系統(tǒng),適于在分布式系統(tǒng)中應(yīng)用,分布式系統(tǒng)中的客戶-服務(wù)器模型,44,行業(yè)特制,第2章 進(jìn)程和線程,45,行業(yè)特制,本章內(nèi)容提要,進(jìn)程概念 進(jìn)程的狀態(tài)和組成 進(jìn)程管理 線程 進(jìn)程的同步和通信 經(jīng)典進(jìn)程同步問題 管程 進(jìn)程通信,46,行業(yè)特制,2.1 進(jìn)程概念,2.1.1 多道程序設(shè)計 1順序程序活動的特點(diǎn) 順序性

12、 封閉性 可再現(xiàn)性 2多道程序設(shè)計 程序并發(fā)執(zhí)行 提高系統(tǒng)資源利用率 增加作業(yè)吞吐量,47,行業(yè)特制,多道程序設(shè)計,3程序并發(fā)執(zhí)行的特征 失去封閉性 程序與計算不再一一對應(yīng) 并發(fā)程序在執(zhí)行期間相互制約,48,行業(yè)特制,2.1.2 進(jìn)程概念,1進(jìn)程概念的引入 多道程序并發(fā)執(zhí)行所引發(fā)的一系列新情況,49,行業(yè)特制,2進(jìn)程概念,進(jìn)程最根本的屬性是動態(tài)性和并發(fā)性 進(jìn)程定義：程序在并發(fā)環(huán)境中的執(zhí)行過程 進(jìn)程和程序的區(qū)別 （1）動態(tài)性 （2）并發(fā)性 （3）非對應(yīng)性 （4）異步性,50,行業(yè)特制,進(jìn)程概念,3進(jìn)程的基本特征 （1）動態(tài)性 （2）并發(fā)性 （3）調(diào)度性,51,行業(yè)特制,2.2 進(jìn)程的狀態(tài)和組成,

13、2.2.1 進(jìn)程的狀態(tài)及其轉(zhuǎn)換 1進(jìn)程的基本狀態(tài) 運(yùn)行狀態(tài)（Running） 就緒狀態(tài)（Ready） 阻塞狀態(tài)（Blocked）,52,行業(yè)特制,進(jìn)程的5種基本狀態(tài)及其轉(zhuǎn)換,53,行業(yè)特制,2進(jìn)程狀態(tài)的轉(zhuǎn)換,（1）新建就緒 （2）就緒運(yùn)行 （3）運(yùn)行阻塞 （4）阻塞就緒 （5）運(yùn)行就緒 （6）運(yùn)行終止,54,行業(yè)特制,2.2.2 進(jìn)程描述,1進(jìn)程映像 進(jìn)程映像通常就由程序、數(shù)據(jù)集合、棧和PCB等4部分組成,進(jìn)程映像模型,55,行業(yè)特制,進(jìn)程描述,2進(jìn)程控制塊的組成 進(jìn)程控制塊（PCB） 也稱進(jìn)程描述塊（Process Descriptor），它是進(jìn)程組成中最關(guān)鍵的部分，其中含有進(jìn)程的描述信息和

14、控制信息，是進(jìn)程動態(tài)特性的集中反映，是系統(tǒng)對進(jìn)程施行識別和控制的依據(jù)。,56,行業(yè)特制,進(jìn)程描述,進(jìn)程控制塊應(yīng)包含的主要內(nèi)容： 進(jìn)程名 特征信息 進(jìn)程狀態(tài)信息 調(diào)度優(yōu)先權(quán) 通信信息 現(xiàn)場保護(hù)區(qū) 資源需求 進(jìn)程實(shí)體信息 族系關(guān)系 其他信息,57,行業(yè)特制,進(jìn)程描述,3進(jìn)程控制塊的作用 每個進(jìn)程有惟一的進(jìn)程控制塊 操作系統(tǒng)根據(jù)PCB對進(jìn)程實(shí)施控制和管理 進(jìn)程的動態(tài)、并發(fā)等特征是利用PCB表現(xiàn)出來的 PCB是進(jìn)程存在的唯一標(biāo)識,58,行業(yè)特制,2.2.3 進(jìn)程隊(duì)列,1線性方式,PCB線性隊(duì)列示意圖,59,行業(yè)特制,進(jìn)程隊(duì)列,2鏈接方式,PCB鏈接隊(duì)列示意圖,60,行業(yè)特制,PCB索引結(jié)構(gòu)示意圖,3索

15、引方式,進(jìn)程隊(duì)列,61,行業(yè)特制,2.3 進(jìn) 程 管 理,2.3.1 進(jìn)程圖 進(jìn)程圖（Process Graph）是描述進(jìn)程族系關(guān)系的有向樹,進(jìn)程創(chuàng)建的層次關(guān)系,62,行業(yè)特制,2.3.2 進(jìn)程創(chuàng)建,引發(fā)創(chuàng)建進(jìn)程的事件： 調(diào)度新作業(yè) 用戶登錄 操作系統(tǒng)提供特定服務(wù) 派生新進(jìn)程,63,行業(yè)特制,進(jìn)程創(chuàng)建,創(chuàng)建新進(jìn)程時要執(zhí)行創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用（如UNIX/Linux系統(tǒng)中的fork） 其主要操作過程有如下四步： （1）申請一個空閑的PCB （2）為新進(jìn)程分配資源 （3）將新進(jìn)程的PCB初始化 （4）將新進(jìn)程加到就緒隊(duì)列中,64,行業(yè)特制,#include #include #include int

16、 main(int argc,char *argv) int pid; pid = fork(); /* 創(chuàng)建一個子進(jìn)程*/ if (pid 0) /* 出現(xiàn)錯誤。進(jìn)程ID號不可能小于0 */ fprintf(stderr, Fork Failed); /* 輸出出錯消息Fork Failed */ exit(-1); /* 程序終止，返回碼-1*/ else if (pid = 0) /* 下面是子進(jìn)程執(zhí)行*/ execlp( /bin/ls, ls,NULL); /* 執(zhí)行目錄/bin下面的ls命令*/ else /* 下面是父進(jìn)程執(zhí)行*/ wait(NULL); /* 父進(jìn)程等待子進(jìn)程完

17、成*/ printf( Child Complete ); /* 輸出子進(jìn)程完成的信息*/ exit(0); /* 終止*/ ,65,行業(yè)特制,2.3.3 進(jìn)程終止,導(dǎo)致進(jìn)程終止的三種情況： 正常終止 異常終止 外部干擾,66,行業(yè)特制,進(jìn)程終止,終止進(jìn)程的主要操作過程如下： 找到指定進(jìn)程的PCB 終止該進(jìn)程的運(yùn)行 回收該進(jìn)程所占用的全部資源 終止其所有子孫進(jìn)程，回收它們所占用的全部資源。 將被終止進(jìn)程的PCB從原來隊(duì)列中摘走,67,行業(yè)特制,2.3.4進(jìn)程阻塞,進(jìn)程阻塞的過程如下： 立即停止當(dāng)前進(jìn)程的執(zhí)行 現(xiàn)行進(jìn)程的CPU現(xiàn)場保存 現(xiàn)行狀態(tài)由“運(yùn)行”改為“阻塞” 轉(zhuǎn)到進(jìn)程調(diào)度程序,68,行業(yè)

18、特制,2.3.5 進(jìn)程喚醒,喚醒原語執(zhí)行過程如下： 把阻塞進(jìn)程從相應(yīng)的阻塞隊(duì)列中摘下 將現(xiàn)行狀態(tài)改為就緒狀態(tài)，然后把該進(jìn)程插入就緒隊(duì)列中 如果被喚醒的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級更高，則設(shè)置重新調(diào)度標(biāo)志,69,行業(yè)特制,2.4 線程,2.4.1 線程概念 現(xiàn)代操作系統(tǒng)中，進(jìn)程只作為資源擁有者，而調(diào)度和運(yùn)行的屬性賦予新的實(shí)體線程。 線程（Thread）是進(jìn)程中實(shí)施調(diào)度和分派的基本單位,70,行業(yè)特制,線程概念,1線程的組成 每個線程有一個thread結(jié)構(gòu)，即線程控制塊，用于保存自己私有的信息，主要由以下4個基本部分組成： 一個唯一的線程標(biāo)識符 一組寄存器 兩個棧指針 一個私有存儲區(qū),thread結(jié)

19、構(gòu)示意圖,71,行業(yè)特制,線程的組成,線程必須在某個進(jìn)程內(nèi)執(zhí)行 一個進(jìn)程可以包含一個線程或多個線程,單線程和多線程的進(jìn)程模型,72,行業(yè)特制,2線程的狀態(tài) 運(yùn)行狀態(tài) 就緒狀態(tài) 阻塞狀態(tài) 終止?fàn)顟B(tài),73,行業(yè)特制,3線程的管理 線程創(chuàng)建 線程終止 線程等待 線程讓權(quán),74,行業(yè)特制,4線程和進(jìn)程的關(guān)系 一個進(jìn)程可以有多個線程，但至少要有一個線程；而一個線程只能在一個進(jìn)程的地址空間內(nèi)活動。 資源分配給進(jìn)程，同一進(jìn)程的所有線程共享該進(jìn)程的所有資源。 處理機(jī)分配給線程，即真正在處理機(jī)上運(yùn)行的是線程。 線程在執(zhí)行過程中需要協(xié)作同步。不同進(jìn)程的線程間要利用消息通信的辦法實(shí)現(xiàn)同步。,75,行業(yè)特制,5引入線

20、程的好處 易于調(diào)度 提高并發(fā)性 開銷少 利于充分發(fā)揮多處理器的功能,76,行業(yè)特制,2.4.2線程的實(shí)現(xiàn),在用戶空間實(shí)現(xiàn) 優(yōu)點(diǎn)：切換速度快；調(diào)度算法可專用 ；可運(yùn)行在任何操作系統(tǒng)上 缺點(diǎn)：阻塞問題；多處理器利用問題 在核心空間實(shí)現(xiàn) 優(yōu)點(diǎn)：克服了用戶級線程方式的兩個主要缺陷；本身也可以是多線程的 缺點(diǎn)：控制轉(zhuǎn)移開銷大 組合方式,77,行業(yè)特制,2.5 進(jìn)程的同步和通信,進(jìn)程間的相互關(guān)系主要分為如下三種形式： 互斥競爭同一資源而發(fā)生相互制約 同步協(xié)同完成一項(xiàng)任務(wù) 通信交換信息,78,行業(yè)特制,2.5.1 進(jìn)程的同步與互斥,1同步 同步進(jìn)程通過共享資源來協(xié)調(diào)活動，在執(zhí)行時間的次序上有一定約束。雖然彼

21、此不直接知道對方的名字，但知道對方的存在和作用。在協(xié)調(diào)動作的情況下，多個進(jìn)程可以共同完成一項(xiàng)任務(wù)。,79,行業(yè)特制,2互斥 在邏輯上這兩個進(jìn)程本來完全獨(dú)立，毫無關(guān)系，只是由于競爭同一個物理資源而相互制約。 它們的運(yùn)行不具有時間次序的特征,80,行業(yè)特制,互斥示例 假定進(jìn)程Pa負(fù)責(zé)為用戶作業(yè)分配打印機(jī)，進(jìn)程Pb負(fù)責(zé)釋放打印機(jī)。系統(tǒng)中設(shè)立一個打印機(jī)分配表，由各個進(jìn)程共用。 打印機(jī)分配表（初始情況） 打印機(jī)分配表（出錯情況）,81,行業(yè)特制,競爭條件（Race Condition） 兩個或多個進(jìn)程同時訪問和操縱相同的數(shù)據(jù)時，最后的執(zhí)行結(jié)果取決于進(jìn)程運(yùn)行的精確時序。,82,行業(yè)特制,2.5.2 臨界資

22、源和臨界區(qū),1臨界資源和臨界區(qū) 臨界資源（Critical Resource） 一次僅允許一個進(jìn)程使用的共享資源 臨界區(qū)（Critical Section），簡稱CS區(qū) 在每個進(jìn)程中訪問臨界資源的那段程序,83,行業(yè)特制,2進(jìn)程的一般結(jié)構(gòu),典型進(jìn)程的一般結(jié)構(gòu),84,行業(yè)特制,3臨界區(qū)進(jìn)入準(zhǔn)則 單獨(dú)進(jìn)入 獨(dú)占該區(qū) 限時退出 主動讓權(quán),進(jìn)程A和進(jìn)程B互斥使用臨界區(qū)的過程,85,行業(yè)特制,2.5.3 互斥實(shí)現(xiàn)方式,1利用硬件方法解決進(jìn)程互斥問題 禁止中斷 進(jìn)入臨界區(qū)之后立即關(guān)閉所有的中斷 專用機(jī)器指令 TSL（Test and Set Lock，即測試并上鎖）的指令：TSL RX，LOCK 匯編代碼

23、示例 enter_region: TSL REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RET leave_region: MOVE LOCK,#0 RET,86,行業(yè)特制,2原語 是機(jī)器指令的延伸，往往是為完成某些特定的功能而編制的一段系統(tǒng)程序。原語操作也稱做“原子操作”（atomic action），即一個操作中的所有動作要么全做，要么全不做。 執(zhí)行原語操作時，要屏蔽中斷，以保證其操作的不可分割性。,87,行業(yè)特制,3利用軟件方法解決進(jìn)程互斥問題 可為每類臨界區(qū)設(shè)置一把鎖，該鎖有打開和關(guān)閉兩種狀態(tài)。 關(guān)鎖原語lock (W): while (

24、W=1); W=1; 開鎖原語unlock (W): w=0;,88,行業(yè)特制,進(jìn)程A lock(W); 打印信息S; CS區(qū) unlock(W); ,進(jìn)程B lock(W); 打印信息S; CS區(qū) unlock(W); ,用鎖實(shí)現(xiàn)進(jìn)程互斥 設(shè)系統(tǒng)中有一臺打印機(jī)，有兩個進(jìn)程A和B都要使用它，以變量W表示鎖，預(yù)先把它的值置為0。,89,行業(yè)特制,2.5.4 信號量,1整型信號量 P操作最初源于荷蘭語proberen，表示測試；V操作源于荷蘭語verhogen，表示增加。 在有些書上將P操作稱做wait或者DOWN操作，將V操作稱做signal或者UP操作。 對信號量的操作有以下限制： 信號量可以

25、初始化為一個非負(fù)值。 只能由P和V兩個操作來訪問信號量。,90,行業(yè)特制,整型信號量,P和V操作都是原語 偽代碼形式 P(S) V(S) while(S0); S+; S-; 實(shí)現(xiàn)互斥的偽代碼形式 do P(mutex); 臨界區(qū) V(mutex); 其他代碼區(qū) while(1);,91,行業(yè)特制,信號量,2結(jié)構(gòu)型信號量 結(jié)構(gòu)型信號量又稱計數(shù)信號量，簡稱信號量 一般是由兩個成員組成的數(shù)據(jù)結(jié)構(gòu)。其中一個成員是整型變量，表示該信號量的值；另一個是指向PCB的指針。 typedef struct int value; struct PCB *list; semaphore;,92,行業(yè)特制,結(jié)構(gòu)型信

26、號量,信號量的值與相應(yīng)資源的使用情況有關(guān) 信號量的一般結(jié)構(gòu)及PCB隊(duì)列,93,行業(yè)特制,對信號量的操作有如下嚴(yán)格限制： 信號量可以賦初值，且初值為非負(fù)數(shù)。 在使用過程中，信號量的值可以修改，但只能由P和V操作來訪問，不允許通過其他方式來查看或操縱信號量。,結(jié)構(gòu)型信號量,94,行業(yè)特制,P、V操作的定義 void P(semaphore S) void V(semaphore S) S.value-; S.value+； if(S.value0) if (S.value=0) 把這個進(jìn)程加到S.list隊(duì)列； 從S.list隊(duì)列中移走進(jìn)程Q； block( )； wakeup(Q)； 在具體實(shí)現(xiàn)

27、時應(yīng)注意，P, V操作都應(yīng)作為一個整體實(shí)施，不允許分割或相互穿插執(zhí)行,結(jié)構(gòu)型信號量,95,行業(yè)特制,結(jié)構(gòu)型 信號量3二值信號量 一種特例，它的值只能在0和1之間選擇,typedef struct enumfalse,truevalue; /*枚舉量*/ struct PCB *list; B_semaphore; void P_B(B_semaphore S) if (S.value=true) S.value=false; else 把該進(jìn)程放入S.list隊(duì)列; block( ); ,void V_B(B_semaphore S) if(S.list=NULL) S.value=true;

28、 else 從S.list隊(duì)列中移走進(jìn)程Q; wakeup(Q); ,96,行業(yè)特制,2.5.5 信號量的一般應(yīng)用,1用信號量實(shí)現(xiàn)進(jìn)程互斥 打印機(jī)分配表的互斥使用 Pa: Pb: P(mutex) P(mutex) 分配打印機(jī) 釋放打印機(jī) （讀寫分配表） （讀寫分配表） V(mutex) V(mutex) ,97,行業(yè)特制,用信號量實(shí)現(xiàn)進(jìn)程互斥,利用信號量實(shí)現(xiàn)互斥的一般模型是： 進(jìn)程P1 進(jìn)程P2 進(jìn)程Pn P(mutex); P(mutex); P(mutex); 臨界區(qū) 臨界區(qū) 臨界區(qū) V(mutex); V(mutex); V(mutex); ,98,行業(yè)特制,用信號量實(shí)現(xiàn)進(jìn)程互斥,注意

29、點(diǎn)： 在每個程序中用于實(shí)現(xiàn)互斥的P(mutex)和V(mutex)必須成對出現(xiàn)，即先做P，進(jìn)入臨界區(qū)；后做V，退出臨界區(qū)。 互斥信號量mutex的初值一般為1。,99,行業(yè)特制,2用信號量實(shí)現(xiàn)進(jìn)程簡單同步 對緩沖區(qū)的同步使用問題,簡單供者和用者對緩沖區(qū)的使用關(guān)系,100,行業(yè)特制,用信號量實(shí)現(xiàn)進(jìn)程簡單同步,供者和用者間要交換兩個消息： 緩沖區(qū)空 緩沖區(qū)滿 設(shè)置兩個信號量： S1表示緩沖區(qū)是否空（0表示不空，1表示空）。 S2表示緩沖區(qū)是否滿（0表示不滿，1表示滿）。 規(guī)定S1和S2的初值分別為1和0,101,行業(yè)特制,用信號量實(shí)現(xiàn)進(jìn)程簡單同步,供者進(jìn)程 用者進(jìn)程 L1: P(S1) L2: 啟

30、動讀卡機(jī) P(S2) ; 從緩沖區(qū)取出信息 收到輸入結(jié)束中斷 V(S1); V(S2); 加工并且存盤 goto L1; goto L2;,102,行業(yè)特制,用信號量實(shí)現(xiàn)進(jìn)程簡單同步,用P和V操作實(shí)現(xiàn)同步時應(yīng)注意如下三點(diǎn)： 分析進(jìn)程間的制約關(guān)系，確定信號量種類。 信號量的初值與相應(yīng)資源的數(shù)量有關(guān)，也與P, V操作在程序代碼中出現(xiàn)的位置有關(guān)。 同一信號量的P, V操作要“成對”出現(xiàn)，但是，它們分別出現(xiàn)在不同的進(jìn)程代碼中。,103,行業(yè)特制,2.6 經(jīng)典進(jìn)程同步問題,1生產(chǎn)者-消費(fèi)者問題 生產(chǎn)者:能產(chǎn)生并釋放資源的進(jìn)程 消費(fèi)者:單純使用（消耗）資源的進(jìn)程 問題表述 一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程（

31、設(shè)每組有多個進(jìn)程）通過緩沖區(qū)發(fā)生聯(lián)系。生產(chǎn)者進(jìn)程將生產(chǎn)的產(chǎn)品（數(shù)據(jù)、消息等統(tǒng)稱為產(chǎn)品）送入緩沖區(qū)，消費(fèi)者進(jìn)程從中取出產(chǎn)品。 假定緩沖區(qū)共有N個，不妨把它們設(shè)想成一個環(huán)形緩沖池。,104,行業(yè)特制,生產(chǎn)者-消費(fèi)者問題,生產(chǎn)者-消費(fèi)者問題環(huán)形緩沖池,它們應(yīng)滿足如下同步條件： 任一時刻所有生產(chǎn)者存放產(chǎn)品的單元數(shù)不能超過緩沖區(qū)的總?cè)萘浚∟）。 所有消費(fèi)者取出產(chǎn)品的總量不能超過所有生產(chǎn)者當(dāng)前生產(chǎn)產(chǎn)品的總量。,105,行業(yè)特制,生產(chǎn)者-消費(fèi)者問題,設(shè)緩沖區(qū)的編號為0N-1，in和out分別是生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程使用的指針，指向下面可用的緩沖區(qū)，初值都是0。 設(shè)置三個信號量： full：表示放有產(chǎn)品的緩沖

32、區(qū)數(shù)，其初值為0。 empty：表示可供使用的緩沖區(qū)數(shù)，其初值為N。 mutex：互斥信號量，初值為1，表示各進(jìn)程互斥進(jìn)入臨界區(qū)，保證任何時候只有一個進(jìn)程使用緩沖區(qū)。,106,行業(yè)特制,生產(chǎn)者-消費(fèi)者問題,生產(chǎn)者進(jìn)程Producer： 消費(fèi)者進(jìn)程Consumer： while(TRUE) while(TRUE) P(empty); P(full); P(mutex); P(mutex); 產(chǎn)品送往buffer(in); 從buffer(out)中取出產(chǎn)品； in=(in+1)mod N; out=(out+1)mod N; /*以N為模*/ /*以N為模*/ V(mutex); V(mutex

33、); V(full); V(empty); ,107,行業(yè)特制,2讀者-寫者問題 讀者-寫者問題也是一個著名的進(jìn)程互斥訪問有限資源的同步問題。例如，一個航班預(yù)訂系統(tǒng)有一個大型數(shù)據(jù)庫，很多競爭進(jìn)程要對它進(jìn)行讀、寫。允許多個進(jìn)程同時讀該數(shù)據(jù)庫，但是在任何時候如果有一個進(jìn)程寫（即修改）數(shù)據(jù)庫，那么就不允許其他進(jìn)程訪問它 既不允許寫，也不允許讀。,108,行業(yè)特制,讀者-寫者問題,信號量設(shè)置： 讀互斥信號量rmutex 初值為1 寫互斥信號量wmutex 初值為1 rmutex：讀者互斥地訪問readcount wmutex：保證一個寫者與其他讀者/寫者互斥地訪問共享資源,讀計數(shù)器readcount，

34、整型變量，初值為0。,109,行業(yè)特制,讀者-寫者問題,讀者Readers while(TRUE) P(rmutex); readcount=readcount+1; if(readcount=1) P(wmutex); V(rmutex); 執(zhí)行讀操作 P(rmutex); readcount=readcount-1; if(readcount=0) V(wmutex); V(rmutex); 使用讀取的數(shù)據(jù) ,寫者Writers while(TRUE) P(wmutex); 執(zhí)行寫操作 V(wmutex); ,這個算法隱含讀者的優(yōu)先級高于寫者,110,行業(yè)特制,3哲學(xué)家進(jìn)餐問題 五位哲學(xué)家

35、圍坐在一張圓桌旁進(jìn)餐，每人面前有一只碗，各碗之間分別有一根筷子。每位哲學(xué)家在用兩根筷子夾面條吃飯前獨(dú)自進(jìn)行思考，感到饑餓時便試圖占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能強(qiáng)行從鄰座手中拿過筷子，而且必須用兩根筷子進(jìn)餐；餐畢，要把筷子放回原處并繼續(xù)思考問題。,哲學(xué)家進(jìn)餐問題,111,行業(yè)特制,哲學(xué)家進(jìn)餐問題,= #define N 5 #define LEFT (i-1)%N #define RIGHT (i+1)%N #define THINKING 0 #define HUNGRY 1 #define EATING 2 typedef struct /* 定義結(jié)構(gòu)型信號量 */

36、 int value; struct PCB *list; semaphore; int stateN; semaphore mutex=1; /* 互斥進(jìn)入臨界區(qū) */ semaphore sN; /* 每位哲學(xué)家一個信號量 */,112,行業(yè)特制,哲學(xué)家進(jìn)餐問題,void philosopher(int i) while(TRUE) think(); /* 哲學(xué)家在思考問題 */ take_chopstick(i); /* 拿到兩根筷子或者等待 */ eat(); /* 進(jìn)餐 */ put_chopstick(i); /* 把筷子放回原處 */ void take_chopstick(in

37、t i) P(mutex); statei=HUNGRY; test(i); /* 試圖拿兩根筷子 */ V(mutex); P(si); ,113,行業(yè)特制,哲學(xué)家進(jìn)餐問題,void put_chopstick(int i) P(mutex); statei=THINKING; test(LEFT); /* 查看左鄰，現(xiàn)在能否進(jìn)餐 */ test(RIGHT); /* 查看右鄰，現(xiàn)在能否進(jìn)餐 */ V(mutex); void test(int i) if(statei=HUNGRY =,114,行業(yè)特制,打瞌睡的理發(fā)師,4打瞌睡的理發(fā)師問題 理發(fā)店有一名理發(fā)師，一把理發(fā)椅和幾把座椅，等待理

38、發(fā)者可坐在上面。如果沒有顧客到來，理發(fā)師就坐在理發(fā)椅上打盹。當(dāng)顧客到來時，就喚醒理發(fā)師。如果顧客到來時理發(fā)師正在理發(fā)，該顧客就坐在椅子上排隊(duì)；如果滿座了，他就離開這個理發(fā)店，到別處去理發(fā)。,115,行業(yè)特制,打瞌睡的理發(fā)師問題,理發(fā)師和每位顧客都分別是一個進(jìn)程 = #define CHAIRS 5 typedef struct int value; struct PCB *list; semaphore; semaphore customers=0; semaphore barbers=0; semaphore mutex=1; int waiting=0;,116,行業(yè)特制,void bar

39、ber(void) while(TRUE) P(customers); /*如果沒有顧客，則理發(fā)師打瞌睡*/ P(mutex); /*互斥進(jìn)入臨界區(qū)*/ waiting-; V(barbers); /*一個理發(fā)師準(zhǔn)備理發(fā)*/ V(mutex); /*退出臨界區(qū)*/ cut_hair(); /*理發(fā)（在臨界區(qū)之外）*/ ,打瞌睡的理發(fā)師問題,117,行業(yè)特制,打瞌睡的理發(fā)師問題,void customer(void) P(mutex); /*互斥進(jìn)入臨界區(qū)*/ if(waitingCHAIRS) waiting+; V(customers); /*若有必要，喚醒理發(fā)師*/ V(mutex); /

40、*退出臨界區(qū)*/ P(barbers); /*如果理發(fā)師正忙著，則顧客打瞌睡*/ get_haircut(); else V(mutex); /*店里人滿了，不等了*/ ,118,行業(yè)特制,2.7 管 程,管程：一個管程定義一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程在其上執(zhí)行的一組操作，這組操作能使進(jìn)程同步和改變管程中的數(shù)據(jù)。 由管程名稱、局部于管程的共享數(shù)據(jù)的說明、對數(shù)據(jù)進(jìn)行操作的一組過程和對該共享數(shù)據(jù)賦初值的語句四部分組成。,管程的結(jié)構(gòu),119,行業(yè)特制,管 程,管程具有以下三個特性： 管程內(nèi)部的局部數(shù)據(jù)變量只能被管程內(nèi)定義的過程所訪問，不能被管程外面聲明的過程直接訪問。 進(jìn)程要想進(jìn)入管程，必須調(diào)用管程內(nèi)

41、的某個過程。 一次只能有一個進(jìn)程在管程內(nèi)執(zhí)行，而其余調(diào)用該管程的進(jìn)程都被掛起，等待該管程成為可用的。即管程能有效地實(shí)現(xiàn)互斥。,120,行業(yè)特制,管 程,實(shí)現(xiàn)互斥是由編譯程序完成 為解決同步問題，引入兩個條件變量x和y： condition x , y; 操作原語wait(x)：掛起等待條件x的調(diào)用進(jìn)程，釋放相應(yīng)的管程，以便供其他進(jìn)程使用。 操作原語signal(x)：恢復(fù)執(zhí)行先前因在條件x上執(zhí)行wait而掛起的那個進(jìn)程。 管程的職責(zé)與信號量的職責(zé)不同。,帶條件變量的管程結(jié)構(gòu),121,行業(yè)特制,2.8 進(jìn) 程 通 信,進(jìn)程通信進(jìn)程間的信息交換 低級進(jìn)程通信 高級進(jìn)程通信 共享存儲器方式：在內(nèi)存中

42、分配一片空間作為共享存儲區(qū) 消息傳遞方式：以消息（Message）為單位在進(jìn)程間進(jìn)行數(shù)據(jù)交換 直接通信方式 間接通信方式 管道文件方式：寫者向管道文件中寫入數(shù)據(jù)；讀者從該文件中讀出數(shù)據(jù),122,行業(yè)特制,2.8.1 消息傳遞系統(tǒng) 允許進(jìn)程彼此進(jìn)行通信，而不必借助于共享數(shù)據(jù) 提供兩個原語（系統(tǒng)調(diào)用 ） send和receive： send (destination, message) receive (source, message),123,行業(yè)特制,消息傳遞系統(tǒng),消息傳送系統(tǒng)設(shè)計 涉及同步、尋址、格式和排隊(duì)規(guī)則等多項(xiàng)問題 同步 尋址 直接通信方式 對稱尋址 ；非對稱尋址 間接通信方式 信箱

43、公用信箱 共享信箱 私有信箱,124,行業(yè)特制,消息傳送系統(tǒng)設(shè)計,消息格式 取決于消息機(jī)制的目標(biāo)和 在什么系統(tǒng)上運(yùn)行 排隊(duì)規(guī)則 先進(jìn)先出 優(yōu)先權(quán)法 接收方挑選,一般消息格式,125,行業(yè)特制,消息傳遞系統(tǒng),用消息傳遞方式解決生產(chǎn)者-消費(fèi)者問題 #define N 100 /* 緩沖區(qū)個數(shù) */ void producer(void) int item; message m; /* 消息緩沖區(qū) */ while (TRUE) item=produce_item()； /* 生成一些數(shù)據(jù)放入緩沖區(qū) */ receive(consumer, /* 使用數(shù)據(jù)項(xiàng)進(jìn)行操作 */ ,126,行業(yè)特制,2.8

44、.2 客戶-服務(wù)器系統(tǒng)中的通信,1socket 好像一條通信線兩端的接插口 一對進(jìn)程通過網(wǎng)絡(luò)進(jìn)行通信要用一對socket，每個進(jìn)程一個。 三個要素： 網(wǎng)絡(luò)地址表明一個socket用于哪種網(wǎng)絡(luò) 連接類型表明網(wǎng)絡(luò)通信所遵循的模式，主要分為“有連接”和“無連接”模式。 網(wǎng)絡(luò)規(guī)程表明具體網(wǎng)絡(luò)的規(guī)程。一般來說，網(wǎng)絡(luò)地址和連接類型結(jié)合在一起就基本上確定了適用的規(guī)程。,socket通信流程,127,行業(yè)特制,2遠(yuǎn)程過程調(diào)用 遠(yuǎn)程過程調(diào)用（Remote Procedure Call, RPC）是遠(yuǎn)程服務(wù)的一種最常見的形式。 遠(yuǎn)程過程調(diào)用的思想： 允許程序調(diào)用另外機(jī)器上的過程 遠(yuǎn)程過程調(diào)用的具體步驟,128,行

45、業(yè)特制,第3章 死 鎖,129,行業(yè)特制,本章內(nèi)容提要 資源 死鎖概念 死鎖的預(yù)防 死鎖的避免 死鎖的檢測和恢復(fù) 處理死鎖的綜合方式,130,行業(yè)特制,3.1 資源,3.1.1 資源使用模式 申請 使用 釋放,131,行業(yè)特制,3.1.2 可剝奪資源與不可剝奪資源,按占有方式劃分： 可剝奪資源 當(dāng)該資源被某進(jìn)程擁有后，其它進(jìn)程仍可以把它剝奪過去為己所用，并且不會產(chǎn)生任何不良影響。例如，內(nèi)存就是可剝奪資源。 不可剝奪資源 該資源一旦被某進(jìn)程占有，則其它進(jìn)程不能強(qiáng)行搶占，必須由擁有者自動釋放，否則會引起相關(guān)計算的失效。如光盤刻錄機(jī)。 死鎖和不可剝奪資源有關(guān) 按其它方式劃分,132,行業(yè)特制,3.2

46、 死鎖概念,3.2.1 什么是死鎖 1死鎖示例,汽車過窄橋時的沖突,在計算機(jī)系統(tǒng)中，涉及軟件、硬件資源的進(jìn)程都可能發(fā)生死鎖,133,行業(yè)特制,2死鎖定義 死鎖 是指在一個進(jìn)程集合中的每個進(jìn)程都在等待僅由該集合中的另一個進(jìn)程才能引發(fā)的事件而無限期地僵持下去的局面。 計算機(jī)系統(tǒng)產(chǎn)生死鎖的根本原因就是資源有限且操作不當(dāng) 死鎖的危害 系統(tǒng)癱瘓 資源浪費(fèi) ,134,行業(yè)特制,什么是死鎖,有兩個進(jìn)程A和B，競爭兩個資源R和S，這兩個資源都是不可剝奪資源。 進(jìn)程A 進(jìn)程B 申請并占用R 申請并占用S 申請并占用S 申請并占用R 釋放R 釋放S 釋放S 釋放R ,135,行業(yè)特制,什么是死鎖,進(jìn)程推進(jìn)順序?qū)σ?/p>

47、發(fā)死鎖的影響,136,行業(yè)特制,3.2.2 死鎖的條件,產(chǎn)生死鎖的4個必要條件 1互斥條件 2占有且等待條件 3不可搶占條件 4循環(huán)等待條件 只要有一個必要條件不滿足，則死鎖就可以排除。,137,行業(yè)特制,3.2.3 資源分配圖,1資源分配圖的構(gòu)成 由結(jié)對組成： G = (V, E) V是頂點(diǎn)的集合，E是邊的集合。 頂點(diǎn)集合可分為兩部分： P=p1, p2, , pn 由系統(tǒng)中所有活動進(jìn)程組成 R=r1, r2, , rm 由系統(tǒng)中全部資源類型組成 有向邊pi rj稱為申請邊 有向邊rj pi 稱為賦給邊 在資源分配圖中，通常用圓圈表示每個進(jìn)程，用方框表示每種資源類型。,138,行業(yè)特制,2資

48、源分配圖示例 （1）集合P, R和E如下： P=p1, p2, p3 R=r1, r2, r3, r4 E=p1r1, p2r3, r1p2, r2p2, r2p1, r3p3 （2）資源數(shù)量 分別為1，2，1，3 （3）進(jìn)程狀態(tài) 該圖不含環(huán)路，沒有死鎖,資源分配圖示例,139,行業(yè)特制,3環(huán)路與死鎖 如果每類資源的實(shí)體都只有一個，那么圖中出現(xiàn)環(huán)路就說明死鎖了。,140,行業(yè)特制,環(huán)路與死鎖,有死鎖的資源分配圖,有環(huán)路但無死鎖的資源分配圖, 如果每類資源的實(shí)體不止一個，那么資源分配圖中出現(xiàn)環(huán)路并不表明一定出現(xiàn)死鎖。,資源分配圖中存在環(huán)路是死鎖產(chǎn)生的必要條件，但不是充分條件。,141,行業(yè)特制,

49、3.2.4 處理死鎖的方法,利用某些協(xié)議預(yù)防或避免死鎖，保證系統(tǒng)不會進(jìn)入死鎖狀態(tài)。 允許系統(tǒng)進(jìn)入死鎖狀態(tài)，然后設(shè)法發(fā)現(xiàn)并克服它。 完全忽略這個問題，好像系統(tǒng)中從來也不會出現(xiàn)死鎖。,142,行業(yè)特制,3.3 死鎖的預(yù)防,3.3.1 破壞互斥條件 3.3.2 破壞占有且等待條件 預(yù)分資源策略靜態(tài)分配 “空手”申請資源策略不占有資源時才可以申請資源 存在以下4個主要缺點(diǎn) 不可預(yù)測 利用率低 降低并發(fā)性 “饑餓” 現(xiàn)象,143,行業(yè)特制,3.3.3 破壞非搶占條件,隱式搶占方式 搶占等待者資源,144,行業(yè)特制,3.3.4 破壞循環(huán)等待條件,資源有序分配策略 資源編號 設(shè)R=r1, r2, , rm，

50、表示一組資源 定義一對一的函數(shù)F：RN，N是一組自然數(shù)。 如：F（磁帶機(jī)）= 1，F(xiàn)（磁盤機(jī)）= 5，F(xiàn)（打印機(jī)）= 12 依序分配 約定：所有進(jìn)程對資源的申請嚴(yán)格按照序號遞增的次序進(jìn)行。,145,行業(yè)特制,破壞循環(huán)等待條件,先棄大，再取小 一個進(jìn)程申請資源rj，它應(yīng)釋放所有滿足F(ri)F(rj) 關(guān)系的資源ri,這兩種辦法都是可行的，都可排除環(huán)路等待條件,優(yōu)點(diǎn)：資源利用率和系統(tǒng)吞吐量都有很大提高 缺點(diǎn)： 資源請求受限，合理編號困難，增加系統(tǒng)開銷。 暫不使用的資源也需提前申請，增加資源占用時間。,146,行業(yè)特制,3.4 死鎖的避免,排除死鎖的動態(tài)策略。關(guān)鍵是確定資源分配的安全性 3.4.1

51、 安全狀態(tài) 在當(dāng)前分配狀態(tài)下，進(jìn)程的安全序列P1, P2, Pn是： 若對于每一個進(jìn)程Pi（1in），它需要的附加資源可被系統(tǒng)中當(dāng)前可用資源與所有進(jìn)程Pj（ ji）當(dāng)前占有資源之和所滿足，則P1, P2, Pn為一個安全序列。 這時系統(tǒng)處于安全狀態(tài)。 存在安全序列時一定不會有死鎖發(fā)生 死鎖是不安全狀態(tài)中的特例,147,行業(yè)特制,安全狀態(tài),安全狀態(tài)示意 設(shè)系統(tǒng)中共有10臺磁帶機(jī)，有三個進(jìn)程p1, p2和p3，分別擁有3臺、2臺和2臺磁帶機(jī)，而它們各自的最大需求分別是9臺、4臺和7臺磁帶機(jī)。此時，系統(tǒng)已分配了7臺磁帶機(jī)，還有3臺空閑。下表給出三個進(jìn)程在不同時刻占有資源及向前推進(jìn)的情況。,148,行

52、業(yè)特制,不安全狀態(tài)示意,若不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)轉(zhuǎn)換為不安全狀態(tài),149,行業(yè)特制,死鎖的避免, 死鎖狀態(tài)是不安全狀態(tài)。 如果系統(tǒng)處于不安全狀態(tài)，并不意味著它就在死鎖狀態(tài)，而是表示存在導(dǎo)致死鎖的危機(jī)。 如果一個進(jìn)程申請的資源當(dāng)前是可用的，但為了避免死鎖，該進(jìn)程也可能必須等待。此時資源利用率會下降。,150,行業(yè)特制,3.4.2 資源分配圖算法,資源類 單體資源類 多體資源類 單體資源類的資源分配圖 除申請邊和賦給邊之外，還要有一種稱為“要求邊”的新邊。要求邊 pi rj表示進(jìn)程pi能夠申請資源rj，有時用虛線表示。,資源分配圖示例,處于不安全狀態(tài)的資源分配圖,151,行

53、業(yè)特制,3.4.3 銀行家算法,“銀行家算法”（Bankers Algorithm）針對多體資源類 設(shè)計思想： 當(dāng)用戶申請一組資源時，系統(tǒng)必須做出判斷：如果把這些資源分出去，系統(tǒng)是否還處于安全狀態(tài)。若是，就可以分出這些資源；否則，該申請暫不予滿足。,152,行業(yè)特制,銀行家算法數(shù)據(jù)結(jié)構(gòu) 令n表示系統(tǒng)中進(jìn)程的數(shù)目，m表示資源分類數(shù)。 Available是一個長度為m的向量，它表示每類資源可用的數(shù)量。Available j=k，表示rj類資源可用的數(shù)量是k。 Max是一個nm矩陣，它表示每個進(jìn)程對資源的最大需求。Maxi, j=k，表示進(jìn)程pi至多可申請k個rj類資源單位。 Allocation是

54、一個nm矩陣，它表示當(dāng)前分給每個進(jìn)程的資源數(shù)目。Allocation i, j=k，表示進(jìn)程pi當(dāng)前分到k個rj類資源。 Need是一個nm矩陣，它表示每個進(jìn)程還缺少多少資源。Need i, j=k，表示進(jìn)程pi尚需k個rj類資源才能完成其任務(wù)。 記號：令X和Y表示長度為n的向量 可以把矩陣Allocation和Need中的每一行當(dāng)做一個向量，并分別寫成Allocationi和Needi。Allocationi表示當(dāng)前分給進(jìn)程pi的資源。,153,行業(yè)特制,1資源分配算法 令Requesti表示進(jìn)程pi的申請向量。Requestij= k，表示進(jìn)程pi需要申請k個rj類資源。當(dāng)進(jìn)程pi申請資源

55、時，就執(zhí)行下列動作： 若RequestiNeedi，表示出錯， 如果RequestiAvailable，則pi等待。 假設(shè)系統(tǒng)把申請的資源分給進(jìn)程pi，則應(yīng)對有關(guān)數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改： Available：= Available Requesti Allocationi：= Allocationi + Requesti Needi：= Needi Requesti 系統(tǒng)執(zhí)行安全性算法，查看此時系統(tǒng)狀態(tài)是否安全。如果是安全的，就實(shí)際分配資源，滿足進(jìn)程pi 的此次申請；否則，若新狀態(tài)是不安全的，則pi等待，對所申請資源暫不予分配，并且把資源分配狀態(tài)恢復(fù)成之前的情況。,154,行業(yè)特制,2安全性算法 令

56、Work和Finish分別表示長度為m和n的向量，最初，置Work：= Available，F(xiàn)inishi：=false，i=1, 2, n。 搜尋滿足下列條件的i值： Finishi=false，且NeediWork。 若沒有找到，則轉(zhuǎn)向。 修改數(shù)據(jù)值： Work：=Work+ Allocationi（pi釋放所占的全部資源） Finishi=true 轉(zhuǎn)向。 若Finishi=true對所有i都成立（任一進(jìn)程都可能是pi），則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。,155,行業(yè)特制,3算法應(yīng)用示例 假定系統(tǒng)中有4個進(jìn)程A, B, C, D和三類資源R1, R2和R3，各自的數(shù)量分別為

57、9, 3和6個單位。,T0時刻資源分配表（安全 ）,資源情況,156,行業(yè)特制,（1）T0時刻是安全的 存在一個安全序列B, A, C, D,進(jìn)程,T0時刻的安全序列,157,行業(yè)特制,（2）進(jìn)程A請求資源 進(jìn)程A發(fā)出請求Request（1, 0, 1）,系統(tǒng)進(jìn)入不安全的狀態(tài) 不能為進(jìn)程A分配所申請的資源,為進(jìn)程A分配資源后的有關(guān)數(shù)據(jù),158,行業(yè)特制,銀行家算法,優(yōu)點(diǎn)： 限制條件少 資源利用程度提高 缺點(diǎn)： 難以保證進(jìn)程數(shù)固定不變 未考慮實(shí)時進(jìn)程快速響應(yīng) 增加了系統(tǒng)開銷,159,行業(yè)特制,3.5 死鎖的檢測和恢復(fù),死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時，該機(jī)構(gòu)能夠檢測到死鎖發(fā)生的

58、位置和原因，且能通過外力破壞死鎖發(fā)生的必要條件，從而使并發(fā)進(jìn)程從死鎖狀態(tài)中解脫出來。,160,行業(yè)特制,3.5.1 對單體資源類的死鎖檢測,等待圖資源分配圖的變形 從資源分配圖中去掉表示資源類的節(jié)點(diǎn)，且把相應(yīng)邊折疊在一起得到的,資源分配圖和對應(yīng)的等待圖,161,行業(yè)特制,3.5.2 對多體資源類的死鎖檢測,采用若干隨時間變化的數(shù)據(jù)結(jié)構(gòu)，與銀行家算法相似 Available是一個長度為m的向量 Allocation是一個nm的矩陣 Request是一個nm的矩陣，Requesti, j=k，表示進(jìn)程pi正申請k個rj類資源 仍把矩陣Allocation和Request的行作為向量對待，并分別表示

59、為Allocationi和Requesti,162,行業(yè)特制,對多體資源類的死鎖檢測,檢測算法 簡單地調(diào)查尚待完成的各個進(jìn)程所有可能的分配序列 令Work和Finish分別表示長度為m和n的向量，初始化 Work：=Available；對于i=1, 2, n 如果Allocationi0，則Finishi：=false；否則Finishi：=true。 尋找一個下標(biāo)i，它應(yīng)滿足條件： Finishi=false且RequestiWork 若找不到這樣的i，則轉(zhuǎn)到。 修改數(shù)據(jù)值： Work：=Work+Allocationi Finishi=true 轉(zhuǎn)向。 若存在某些i（1in），F(xiàn)inish

60、i=false，則系統(tǒng)處于死鎖狀態(tài)。此外，若Finishi=false，則進(jìn)程pi處于死鎖環(huán)中。,163,行業(yè)特制,對多體資源類的死鎖檢測,設(shè)系統(tǒng)中有5個進(jìn)程p1, p2, p3, p4和p5，有3類資源R1, R2和R3 ，每類資源的個數(shù)分別為7, 2, 6。,死鎖檢測示例資源分配情況,可以找到序列p1, p3, p4, p2, p5，對于所有的i都有Finishi=true，系統(tǒng)在T0時刻沒有死鎖。,資源情況,進(jìn)程,164,行業(yè)特制,假定，進(jìn)程p3現(xiàn)在申請一個單位的R3資源,由于對所有i=1, 2, 5，Allocationi0，所以Finishi=false。,p3申請一個單位的R3資源