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

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

2、接在一起，實(shí)現(xiàn)彼此通信。,4,行業(yè)特制,現(xiàn)代計(jì)算機(jī)硬件結(jié)構(gòu),5,行業(yè)特制,1.1.1 處理器,CPU工作的基本周期是： 提取指令，譯碼分析，執(zhí)行指令 每個(gè)CPU可以執(zhí)行的指令集是專用的 所有CPU都包含某些寄存器 通用寄存器 專用寄存器 程序計(jì)數(shù)器 棧指針 PSW（程序狀態(tài)字） 兩種處理機(jī)執(zhí)行狀態(tài) 核心態(tài) 用戶態(tài),6,行業(yè)特制,1.1.2 存儲(chǔ)器,寄存器 高速緩存 內(nèi)存 磁盤 磁帶,7,行業(yè)特制,1.1.3 I/O設(shè)備,通常由控制器和設(shè)備本身兩部分組成 控制器 設(shè)備 設(shè)備驅(qū)動(dòng)程序,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)視各種資源，隨時(shí)記錄它們的狀態(tài)； 實(shí)施某種策略以決定誰獲得資源，何時(shí)獲得，獲得多少； 分配資源供需求者使用； 回收資源，以便再分配。 3. 操作系統(tǒng)的用戶觀點(diǎn)和系統(tǒng)觀點(diǎn),10,行業(yè)特制,定義： 操作系統(tǒng)是控制和管理計(jì)算機(jī)系統(tǒng)內(nèi)各種硬件和軟件資源，有效地組織多道程序運(yùn)行的系統(tǒng)軟件（或程序集合），是用戶與計(jì)算機(jī)之間的接口。,11,行業(yè)特制, 操作系統(tǒng)是系統(tǒng)軟件 基本職能是控制和管理系統(tǒng)內(nèi)各種資源，有效地組織多道程序的運(yùn)行 提供眾多服務(wù)，方便用戶使用，擴(kuò)充硬

4、件功能,12,行業(yè)特制,1.2.2 操作系統(tǒng)的主要功能,1存儲(chǔ)管理 內(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ū)動(dòng) 設(shè)備無關(guān)性,15,行業(yè)特制,1.2.2 操作系統(tǒng)的主要功能,4文件管理功能 文件存儲(chǔ)空間的管理 文件操作的一般管理 目錄管理 文件的讀/寫管理和存取控制,16,行業(yè)特制,1.2.2 操作系統(tǒng)的主要功能,5用戶接口 程序接口 命令行接口 圖形用戶接口（GUI）,17,行業(yè)特制,1.2.3 操作系統(tǒng)的

5、地位,計(jì)算機(jī)系統(tǒng)的層次關(guān)系,18,行業(yè)特制,簡言之，軟件是計(jì)算機(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è)計(jì)： 在內(nèi)存中同時(shí)存放多道程序，在管理程序的控制下交替地執(zhí)行。這些作業(yè)共享CPU和系統(tǒng)中的其他資源。 并發(fā)：多道程序在CPU上交替運(yùn)行 系統(tǒng)吞吐量： 在一

6、段給定的時(shí)間內(nèi)，計(jì)算機(jī)所能完成的總工作量。,22,行業(yè)特制,1.3.2 操作系統(tǒng)的發(fā)展,23,行業(yè)特制,1.3.3 推動(dòng)操作系統(tǒng)發(fā)展的動(dòng)力,硬件技術(shù)更新 應(yīng)用需求擴(kuò)大,24,行業(yè)特制,1.4 操作系統(tǒng)的類型,5大基本類型 批處理系統(tǒng) 分時(shí)系統(tǒng) 實(shí)時(shí)系統(tǒng) 網(wǎng)絡(luò)系統(tǒng) 分布式系統(tǒng),25,行業(yè)特制,1.4.1 批處理系統(tǒng),1作業(yè) 是用戶定義的、由計(jì)算機(jī)完成的工作單位。它通常包括一組計(jì)算機(jī)程序、文件和對操作系統(tǒng)的控制語句。 作業(yè)步 由作業(yè)控制語句明確標(biāo)識的計(jì)算機(jī)程序的執(zhí)行過程,26,行業(yè)特制,2工作流程,多道批處理系統(tǒng)中的作業(yè)流程,27,行業(yè)特制,批處理系統(tǒng),3.特點(diǎn) 多道：系統(tǒng)在內(nèi)存中存放多個(gè)作業(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è)的等待時(shí)間長 沒有交互能力,28,行業(yè)特制,1.4.2 分時(shí)系統(tǒng),1分時(shí)概念和分時(shí)系統(tǒng)的實(shí)現(xiàn)方法 分時(shí)：廣義上，是指對時(shí)間的共享。 在分時(shí)系統(tǒng)中，分時(shí)主要是指若干并發(fā)程序?qū)PU時(shí)間的共享 并行：是指在同一時(shí)刻有兩個(gè)或兩個(gè)以上的活動(dòng)發(fā)生。 時(shí)間片,29,行業(yè)特制,分時(shí)系統(tǒng),2分時(shí)系統(tǒng)的特征和優(yōu)點(diǎn) 基本特征 同時(shí)性 交互性 獨(dú)立性 及時(shí)性 主要優(yōu)點(diǎn) 人機(jī)交互友好 應(yīng)用方便 資源共享,30,行業(yè)特制,1.4.3

8、 實(shí)時(shí)系統(tǒng),1實(shí)時(shí)系統(tǒng)的引入 實(shí)時(shí)系統(tǒng) 具有實(shí)時(shí)特性，能夠支持實(shí)時(shí)控制系統(tǒng)工作的操作系統(tǒng)。 重要特征：對時(shí)間有嚴(yán)格限制和要求 三種典型應(yīng)用形式 過程控制系統(tǒng) 信息查詢系統(tǒng) 事務(wù)處理系統(tǒng),31,行業(yè)特制,2實(shí)時(shí)系統(tǒng)與分時(shí)系統(tǒng)的差別 交互性 實(shí)時(shí)性 可靠性,32,行業(yè)特制,實(shí)時(shí)系統(tǒng),3實(shí)現(xiàn)方式 硬式實(shí)時(shí)系統(tǒng) 對時(shí)間嚴(yán)格約束 軟式實(shí)時(shí)系統(tǒng) 對時(shí)間限制稍弱一些,33,行業(yè)特制,1.4.4 網(wǎng)絡(luò)操作系統(tǒng),1計(jì)算機(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.個(gè)人機(jī)系統(tǒng) Windows XP、Windows Vista、UNIX、Linux 2.多

10、處理器系統(tǒng) 對稱多處理（SMP）系統(tǒng) 增加吞吐量 提高性能/價(jià)格比 提高可靠性 3嵌入式系統(tǒng),38,行業(yè)特制,1.5 操作系統(tǒng)的特征,（1）并發(fā) 兩個(gè)或多個(gè)活動(dòng)在同一給定的時(shí)間間隔中進(jìn)行。 （2）共享 計(jì)算機(jī)系統(tǒng)中的資源被多個(gè)進(jìn)程所共用。 （3）不確定性 系統(tǒng)中各種事件發(fā)生順序的不可預(yù)測性。,39,行業(yè)特制,1.6 操作系統(tǒng)結(jié)構(gòu)設(shè)計(jì),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) 同時(shí)運(yùn)行多個(gè)操作系統(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è)計(jì) 1順序程序活動(dòng)的特點(diǎn) 順序性

12、 封閉性 可再現(xiàn)性 2多道程序設(shè)計(jì) 程序并發(fā)執(zhí)行 提高系統(tǒng)資源利用率 增加作業(yè)吞吐量,47,行業(yè)特制,多道程序設(shè)計(jì),3程序并發(fā)執(zhí)行的特征 失去封閉性 程序與計(jì)算不再一一對應(yīng) 并發(fā)程序在執(zhí)行期間相互制約,48,行業(yè)特制,2.1.2 進(jìn)程概念,1進(jìn)程概念的引入 多道程序并發(fā)執(zhí)行所引發(fā)的一系列新情況,49,行業(yè)特制,2進(jìn)程概念,進(jìn)程最根本的屬性是動(dòng)態(tài)性和并發(fā)性 進(jìn)程定義：程序在并發(fā)環(huán)境中的執(zhí)行過程 進(jìn)程和程序的區(qū)別 （1）動(dòng)態(tài)性 （2）并發(fā)性 （3）非對應(yīng)性 （4）異步性,50,行業(yè)特制,進(jìn)程概念,3進(jìn)程的基本特征 （1）動(dòng)態(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)程動(dòng)態(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)程控制塊的作用 每個(gè)進(jìn)程有惟一的進(jìn)程控制塊 操作系統(tǒng)根據(jù)PCB對進(jìn)程實(shí)施控制和管理 進(jìn)程的動(dòng)態(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)程時(shí)要執(zhí)行創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用（如UNIX/Linux系統(tǒng)中的fork） 其主要操作過程有如下四步： （1）申請一個(gè)空閑的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)建一個(gè)子進(jìn)程*/ if (pid 0) /* 出現(xiàn)錯(cuò)誤。進(jìn)程ID號不可能小于0 */ fprintf(stderr, Fork Failed); /* 輸出出錯(cuò)消息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線程的組成 每個(gè)線程有一個(gè)thread結(jié)構(gòu)，即線程控制塊，用于保存自己私有的信息，主要由以下4個(gè)基本部分組成： 一個(gè)唯一的線程標(biāo)識符 一組寄存器 兩個(gè)棧指針 一個(gè)私有存儲(chǔ)區(qū),thread結(jié)

19、構(gòu)示意圖,71,行業(yè)特制,線程的組成,線程必須在某個(gè)進(jìn)程內(nèi)執(zhí)行 一個(gè)進(jìn)程可以包含一個(gè)線程或多個(gè)線程,單線程和多線程的進(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)系 一個(gè)進(jìn)程可以有多個(gè)線程，但至少要有一個(gè)線程；而一個(gè)線程只能在一個(gè)進(jìn)程的地址空間內(nèi)活動(dòng)。 資源分配給進(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)：克服了用戶級線程方式的兩個(gè)主要缺陷；本身也可以是多線程的 缺點(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)活動(dòng)，在執(zhí)行時(shí)間的次序上有一定約束。雖然彼

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

22、源和臨界區(qū),1臨界資源和臨界區(qū) 臨界資源（Critical Resource） 一次僅允許一個(gè)進(jìn)程使用的共享資源 臨界區(qū)（Critical Section），簡稱CS區(qū) 在每個(gè)進(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ū) 限時(shí)退出 主動(dòng)讓權(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），即一個(gè)操作中的所有動(dòng)作要么全做，要么全不做。 執(zhí)行原語操作時(shí)，要屏蔽中斷，以保證其操作的不可分割性。,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)中有一臺(tái)打印機(jī)，有兩個(gè)進(jìn)程A和B都要使用它，以變量W表示鎖，預(yù)先把它的值置為0。,89,行業(yè)特制,2.5.4 信號量,1整型信號量 P操作最初源于荷蘭語proberen，表示測試；V操作源于荷蘭語verhogen，表示增加。 在有些書上將P操作稱做wait或者DOWN操作，將V操作稱做signal或者UP操作。 對信號量的操作有以下限制： 信號量可以

25、初始化為一個(gè)非負(fù)值。 只能由P和V兩個(gè)操作來訪問信號量。,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)型信號量又稱計(jì)數(shù)信號量，簡稱信號量 一般是由兩個(gè)成員組成的數(shù)據(jù)結(jié)構(gòu)。其中一個(gè)成員是整型變量，表示該信號量的值；另一個(gè)是指向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) 把這個(gè)進(jìn)程加到S.list隊(duì)列； 從S.list隊(duì)列中移走進(jìn)程Q； block( )； wakeup(Q)； 在具體實(shí)現(xiàn)

27、時(shí)應(yīng)注意，P, V操作都應(yīng)作為一個(gè)整體實(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)： 在每個(gè)程序中用于實(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)程簡單同步,供者和用者間要交換兩個(gè)消息： 緩沖區(qū)空 緩沖區(qū)滿 設(shè)置兩個(gè)信號量： 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、動(dòng)讀卡機(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)同步時(shí)應(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è)每組有多個(gè)進(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個(gè)，不妨把它們設(shè)想成一個(gè)環(huán)形緩沖池。,104,行業(yè)特制,生產(chǎn)者-消費(fèi)者問題,生產(chǎn)者-消費(fèi)者問題環(huán)形緩沖池,它們應(yīng)滿足如下同步條件： 任一時(shí)刻所有生產(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è)置三個(gè)信號量： full：表示放有產(chǎn)品的緩沖

32、區(qū)數(shù)，其初值為0。 empty：表示可供使用的緩沖區(qū)數(shù)，其初值為N。 mutex：互斥信號量，初值為1，表示各進(jìn)程互斥進(jìn)入臨界區(qū)，保證任何時(shí)候只有一個(gè)進(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讀者-寫者問題 讀者-寫者問題也是一個(gè)著名的進(jìn)程互斥訪問有限資源的同步問題。例如，一個(gè)航班預(yù)訂系統(tǒng)有一個(gè)大型數(shù)據(jù)庫，很多競爭進(jìn)程要對它進(jìn)行讀、寫。允許多個(gè)進(jìn)程同時(shí)讀該數(shù)據(jù)庫，但是在任何時(shí)候如果有一個(gè)進(jìn)程寫（即修改）數(shù)據(jù)庫，那么就不允許其他進(jìn)程訪問它 既不允許寫，也不允許讀。,108,行業(yè)特制,讀者-寫者問題,信號量設(shè)置： 讀互斥信號量rmutex 初值為1 寫互斥信號量wmutex 初值為1 rmutex：讀者互斥地訪問readcount wmutex：保證一個(gè)寫者與其他讀者/寫者互斥地訪問共享資源,讀計(jì)數(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); ,這個(gè)算法隱含讀者的優(yōu)先級高于寫者,110,行業(yè)特制,3哲學(xué)家進(jìn)餐問題 五位哲學(xué)家

35、圍坐在一張圓桌旁進(jìn)餐，每人面前有一只碗，各碗之間分別有一根筷子。每位哲學(xué)家在用兩根筷子夾面條吃飯前獨(dú)自進(jìn)行思考，感到饑餓時(shí)便試圖占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能強(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é)家一個(gè)信號量 */,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)顧客到來時(shí)，就喚醒理發(fā)師。如果顧客到來時(shí)理發(fā)師正在理發(fā)，該顧客就坐在椅子上排隊(duì)；如果滿座了，他就離開這個(gè)理發(fā)店，到別處去理發(fā)。,115,行業(yè)特制,打瞌睡的理發(fā)師問題,理發(fā)師和每位顧客都分別是一個(gè)進(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); /*一個(gè)理發(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 管 程,管程：一個(gè)管程定義一個(gè)數(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è)特制,管 程,管程具有以下三個(gè)特性： 管程內(nèi)部的局部數(shù)據(jù)變量只能被管程內(nèi)定義的過程所訪問，不能被管程外面聲明的過程直接訪問。 進(jìn)程要想進(jìn)入管程，必須調(diào)用管程內(nèi)

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

42、分配一片空間作為共享存儲(chǔ)區(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ù) 提供兩個(gè)原語（系統(tǒng)調(diào)用 ） send和receive： send (destination, message) receive (source, message),123,行業(yè)特制,消息傳遞系統(tǒng),消息傳送系統(tǒng)設(shè)計(jì) 涉及同步、尋址、格式和排隊(duì)規(guī)則等多項(xiàng)問題 同步 尋址 直接通信方式 對稱尋址 ；非對稱尋址 間接通信方式 信箱

43、公用信箱 共享信箱 私有信箱,124,行業(yè)特制,消息傳送系統(tǒng)設(shè)計(jì),消息格式 取決于消息機(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ū)個(gè)數(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，每個(gè)進(jìn)程一個(gè)。 三個(gè)要素： 網(wǎng)絡(luò)地址表明一個(gè)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)程仍可以把它剝奪過去為己所用，并且不會(huì)產(chǎn)生任何不良影響。例如，內(nèi)存就是可剝奪資源。 不可剝奪資源 該資源一旦被某進(jìn)程占有，則其它進(jìn)程不能強(qiáng)行搶占，必須由擁有者自動(dòng)釋放，否則會(huì)引起相關(guān)計(jì)算的失效。如光盤刻錄機(jī)。 死鎖和不可剝奪資源有關(guān) 按其它方式劃分,132,行業(yè)特制,3.2

46、 死鎖概念,3.2.1 什么是死鎖 1死鎖示例,汽車過窄橋時(shí)的沖突,在計(jì)算機(jī)系統(tǒng)中，涉及軟件、硬件資源的進(jìn)程都可能發(fā)生死鎖,133,行業(yè)特制,2死鎖定義 死鎖 是指在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待僅由該集合中的另一個(gè)進(jìn)程才能引發(fā)的事件而無限期地僵持下去的局面。 計(jì)算機(jī)系統(tǒng)產(chǎn)生死鎖的根本原因就是資源有限且操作不當(dāng) 死鎖的危害 系統(tǒng)癱瘓 資源浪費(fèi) ,134,行業(yè)特制,什么是死鎖,有兩個(gè)進(jìn)程A和B，競爭兩個(gè)資源R和S，這兩個(gè)資源都是不可剝奪資源。 進(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個(gè)必要條件 1互斥條件 2占有且等待條件 3不可搶占條件 4循環(huán)等待條件 只要有一個(gè)必要條件不滿足，則死鎖就可以排除。,137,行業(yè)特制,3.2.3 資源分配圖,1資源分配圖的構(gòu)成 由結(jié)對組成： G = (V, E) V是頂點(diǎn)的集合，E是邊的集合。 頂點(diǎn)集合可分為兩部分： P=p1, p2, , pn 由系統(tǒng)中所有活動(dòng)進(jìn)程組成 R=r1, r2, , rm 由系統(tǒng)中全部資源類型組成 有向邊pi rj稱為申請邊 有向邊rj pi 稱為賦給邊 在資源分配圖中，通常用圓圈表示每個(gè)進(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í)體都只有一個(gè)，那么圖中出現(xiàn)環(huán)路就說明死鎖了。,140,行業(yè)特制,環(huán)路與死鎖,有死鎖的資源分配圖,有環(huán)路但無死鎖的資源分配圖, 如果每類資源的實(shí)體不止一個(gè)，那么資源分配圖中出現(xiàn)環(huán)路并不表明一定出現(xiàn)死鎖。,資源分配圖中存在環(huán)路是死鎖產(chǎn)生的必要條件，但不是充分條件。,141,行業(yè)特制,

49、3.2.4 處理死鎖的方法,利用某些協(xié)議預(yù)防或避免死鎖，保證系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)。 允許系統(tǒng)進(jìn)入死鎖狀態(tài)，然后設(shè)法發(fā)現(xiàn)并克服它。 完全忽略這個(gè)問題，好像系統(tǒng)中從來也不會(huì)出現(xiàn)死鎖。,142,行業(yè)特制,3.3 死鎖的預(yù)防,3.3.1 破壞互斥條件 3.3.2 破壞占有且等待條件 預(yù)分資源策略靜態(tài)分配 “空手”申請資源策略不占有資源時(shí)才可以申請資源 存在以下4個(gè)主要缺點(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)等待條件,先棄大，再取小 一個(gè)進(jìn)程申請資源rj，它應(yīng)釋放所有滿足F(ri)F(rj) 關(guān)系的資源ri,這兩種辦法都是可行的，都可排除環(huán)路等待條件,優(yōu)點(diǎn)：資源利用率和系統(tǒng)吞吐量都有很大提高 缺點(diǎn)： 資源請求受限，合理編號困難，增加系統(tǒng)開銷。 暫不使用的資源也需提前申請，增加資源占用時(shí)間。,146,行業(yè)特制,3.4 死鎖的避免,排除死鎖的動(dòng)態(tài)策略。關(guān)鍵是確定資源分配的安全性 3.4.1

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

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

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

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

55、時(shí)，就執(zhí)行下列動(dòng)作： 若RequestiNeedi，表示出錯(cuò)， 如果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í)行安全性算法，查看此時(shí)系統(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個(gè)進(jìn)程A, B, C, D和三類資源R1, R2和R3，各自的數(shù)量分別為

57、9, 3和6個(gè)單位。,T0時(shí)刻資源分配表（安全 ）,資源情況,156,行業(yè)特制,（1）T0時(shí)刻是安全的 存在一個(gè)安全序列B, A, C, D,進(jìn)程,T0時(shí)刻的安全序列,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í)時(shí)進(jìn)程快速響應(yīng) 增加了系統(tǒng)開銷,159,行業(yè)特制,3.5 死鎖的檢測和恢復(fù),死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時(shí)，該機(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í)間變化的數(shù)據(jù)結(jié)構(gòu)，與銀行家算法相似 Available是一個(gè)長度為m的向量 Allocation是一個(gè)nm的矩陣 Request是一個(gè)nm的矩陣，Requesti, j=k，表示進(jìn)程pi正申請k個(gè)rj類資源 仍把矩陣Allocation和Request的行作為向量對待，并分別表示

59、為Allocationi和Requesti,162,行業(yè)特制,對多體資源類的死鎖檢測,檢測算法 簡單地調(diào)查尚待完成的各個(gè)進(jìn)程所有可能的分配序列 令Work和Finish分別表示長度為m和n的向量，初始化 Work：=Available；對于i=1, 2, n 如果Allocationi0，則Finishi：=false；否則Finishi：=true。 尋找一個(gè)下標(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個(gè)進(jìn)程p1, p2, p3, p4和p5，有3類資源R1, R2和R3 ，每類資源的個(gè)數(shù)分別為7, 2, 6。,死鎖檢測示例資源分配情況,可以找到序列p1, p3, p4, p2, p5，對于所有的i都有Finishi=true，系統(tǒng)在T0時(shí)刻沒有死鎖。,資源情況,進(jìn)程,164,行業(yè)特制,假定，進(jìn)程p3現(xiàn)在申請一個(gè)單位的R3資源,由于對所有i=1, 2, 5，Allocationi0，所以Finishi=false。,p3申請一個(gè)單位的R3資源