進程調(diào)度算法和死鎖解除方法

1、計算機操作系統(tǒng)計算機操作系統(tǒng)主講教師：主講教師：曹建秋 賀清碧賀清碧課程主要內(nèi)容課程主要內(nèi)容操作系統(tǒng)引論（操作系統(tǒng)引論（1 1章）章）進程管理（進程管理（2-32-3章）章）存儲管理（存儲管理（4 4章）章）設(shè)備管理（設(shè)備管理（5 5章）章）文件管理（文件管理（6 6章）章）操作系統(tǒng)接口（操作系統(tǒng)接口（7 7章）章）系統(tǒng)安全性（系統(tǒng)安全性（9 9章）章）* *分布式操作系統(tǒng)分布式操作系統(tǒng)Process Management Process Management 進程管理進程管理u 進程的基本概念與控制進程的基本概念與控制v進程的基本概念進程的基本概念v進程控制進程控制v線程的基本概念線程的基本

2、概念vUNIXUNIX中進程的描述與控制中進程的描述與控制u 進程同步與通信進程同步與通信v進程同步進程同步v經(jīng)典進程的同步問題經(jīng)典進程的同步問題v管程機制管程機制v進程通信進程通信vUNIXUNIX中進程的同步與通信中進程的同步與通信u 處理機調(diào)度與死鎖（第處理機調(diào)度與死鎖（第3 3章）章）第第3 3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 在多道程序環(huán)境下，一個作業(yè)從提交到執(zhí)行，通常都要經(jīng)歷多級調(diào)度，如高級調(diào)度、低級調(diào)度、中級調(diào)度等。而系統(tǒng)的運行性能在很大程序上取決于調(diào)度，因此調(diào)度便成為多道程序的關(guān)鍵。 在多道程序環(huán)境下，由于多個進程的并發(fā)執(zhí)行，改善了系統(tǒng)資源的利用率并提高了系統(tǒng)的處理能力，

3、然而，多個進程的并發(fā)執(zhí)行也帶來了新的問題-死鎖。第第3 3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖u 處理機調(diào)度的基本概念處理機調(diào)度的基本概念u 調(diào)度算法調(diào)度算法u * *實時調(diào)度實時調(diào)度u UNIXUNIX系統(tǒng)中進程的調(diào)系統(tǒng)中進程的調(diào)度度v產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件v預(yù)防死鎖的方法預(yù)防死鎖的方法v死鎖的檢測與解除死鎖的檢測與解除v本章作業(yè)本章作業(yè)3.1 3.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念 在多道程序環(huán)境下，一個作業(yè)從提交直到完成，往往要經(jīng)歷多級調(diào)度。但在不同操作系統(tǒng)中所采用的調(diào)度層次不完全相同。在有的系統(tǒng)中僅采用一級調(diào)度，而在另一些系統(tǒng)中則可能采用兩級或三級

4、調(diào)度，在執(zhí)行調(diào)度時所采用的調(diào)度算法也可能不同。v調(diào)度的層調(diào)度的層次次v調(diào)度隊列模型調(diào)度隊列模型v選擇調(diào)度方式和算法的若干準則選擇調(diào)度方式和算法的若干準則返回目錄一、一、調(diào)度的層次調(diào)度的層次 如圖所示。Process Management進程管理-processes 進程 作業(yè)調(diào)度作業(yè)調(diào)度中級調(diào)度中級調(diào)度運行就緒阻塞 進程調(diào)度進程調(diào)度掛起阻塞掛起就緒創(chuàng)建退出一、一、調(diào)度的層次調(diào)度的層次 一個作業(yè)從提交開始，往往要經(jīng)歷三級調(diào)度：高級調(diào)度高級調(diào)度、低級調(diào)度低級調(diào)度、中級調(diào)度中級調(diào)度。1 1、高級調(diào)度、高級調(diào)度（長程/作業(yè)/宏觀調(diào)度）（1）從外存后備隊列中選擇作業(yè)進入就緒隊列或掛起就緒. （2）在批處

5、理系統(tǒng)中,大多配有作業(yè)調(diào)度,但在分時系統(tǒng)及實時系統(tǒng)中,一般不配置.（3）作業(yè)調(diào)度執(zhí)行頻率很低,通常為幾分鐘一次,甚至更久。Process Management進程管理-processes 進程 一、一、調(diào)度的層次調(diào)度的層次-高級調(diào)度（長程高級調(diào)度（長程/作業(yè)作業(yè)/宏觀調(diào)度）宏觀調(diào)度）u 高級調(diào)度需解決的問題高級調(diào)度需解決的問題（1）主要任務(wù)是從外存后備隊列中選擇多少作業(yè)選擇多少作業(yè)進入就緒隊列或掛起就緒，即允許多少作業(yè)同時在內(nèi)存中運行，它控制著多道程序的“道或度” 。若作業(yè)太多，則可能會影響系統(tǒng)的服務(wù)質(zhì)量（如周轉(zhuǎn)時間太長），若太少，又將導(dǎo)致系統(tǒng)資源利用率和吞吐量的下降。 因此，應(yīng)根據(jù)系統(tǒng)的規(guī)模

6、和運行速度來確定，同時要求I/O型進程與CPU型進程中和調(diào)度。（2）應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存將哪些作業(yè)從外存調(diào)入內(nèi)存，將取決于調(diào)度算法（先來先服務(wù)、短作業(yè)優(yōu)先等）。 Process Management進程管理-processes 進程 2 2、低級調(diào)度（短程、低級調(diào)度（短程/CPU/CPU/進程進程/ /微觀調(diào)度微觀調(diào)度）（1）主要任務(wù)就是從就緒隊列中選擇一個進程來執(zhí)行并分配處理機。（2）是OS中最基本的調(diào)度。（3）調(diào)度頻率非常高，一般幾十毫秒一次。（4）常采用非搶占（非剝奪）方式非搶占（非剝奪）方式和搶占搶占（剝奪剝奪）方式方式兩種。（5）引起進程調(diào)度的因素：v進程正常終止或?qū)С＝K止v正

7、在執(zhí)行的進程因某種原因而阻塞v在引入時間片的系統(tǒng)中，時間片用完。v在搶占調(diào)度方式中，就緒隊列中某進程的優(yōu)先權(quán)變得比當(dāng)前正執(zhí)行的進程高。非搶占式進程調(diào)度、搶占式進程調(diào)度非搶占式進程調(diào)度、搶占式進程調(diào)度u 非搶占方式非搶占方式：一旦把處理機分配給某進程后，便讓該進程一直執(zhí)行一直執(zhí)行，直到該進程完成或因某事件而被阻塞，才再把處理機分配給其它進程，決不允許某進程搶占已分配出去的處理機。 實現(xiàn)簡單，系統(tǒng)開銷小，常用于批處理系統(tǒng)；但不利于處理緊急任務(wù)，故實時、分時系統(tǒng)不宜采用。u 搶占方式搶占方式: : 允許調(diào)度程序根據(jù)某種原則（時間片、優(yōu)先權(quán)、短進程優(yōu)先），停止正在停止正在執(zhí)行的進程，而將處理機重新分配

8、給另一進程。 有利于處理緊急任務(wù)，故實時與分時系統(tǒng)中常采用。3 3、中級調(diào)度（中程、中級調(diào)度（中程/ /交換調(diào)度交換調(diào)度）Process Management進程管理-processes 進程 在內(nèi)存和外存對換區(qū)之間按照給定的原則和策略選擇進程對換選擇進程對換，以解決內(nèi)存緊張問題，從而提高內(nèi)存的利用率和系統(tǒng)吞吐量，常用于分時系統(tǒng)或具有虛擬存儲器的系統(tǒng)中。返回本節(jié)二、二、調(diào)度隊列模型調(diào)度隊列模型 在OS中的任何一種調(diào)度中，都將涉及到進程隊列，由此形成了三種類型的調(diào)度隊列模型。v僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型v具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型v

9、同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型Process Management進程管理-processes 進程 返回本節(jié)1 1、僅有進程調(diào)度的調(diào)度隊列模型、僅有進程調(diào)度的調(diào)度隊列模型就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列進程調(diào)度進程調(diào)度時間片完時間片完CPU進程完成進程完成等待事件等待事件事事件件出出現(xiàn)現(xiàn)交互用戶交互用戶返回2 2、具有高級和低級調(diào)度的調(diào)度隊列模型、具有高級和低級調(diào)度的調(diào)度隊列模型就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列時間片完時間片完后后備備隊隊列列進程調(diào)度進程調(diào)度CPU進程完成進程完成事事件件出出現(xiàn)現(xiàn)等待事件等待事件1等待事件等待事件2等待事件

10、等待事件n作業(yè)作業(yè)調(diào)度調(diào)度返回3 3、同時具有三級調(diào)度的調(diào)度隊列模型、同時具有三級調(diào)度的調(diào)度隊列模型就就 緒緒 隊隊 列列就就 緒緒 掛掛 起起 隊隊 列列時間片完時間片完阻阻 塞塞 隊隊 列列后后備備隊隊列列進程調(diào)度進程調(diào)度CPU進程完成進程完成事事件件出出現(xiàn)現(xiàn)等待事件等待事件作業(yè)作業(yè)調(diào)度調(diào)度阻阻 塞塞 掛掛 起起 隊隊 列列中程調(diào)度中程調(diào)度返回三、三、選擇調(diào)度方式和算法的若干準則選擇調(diào)度方式和算法的若干準則 在一個操作系統(tǒng)的設(shè)計中，應(yīng)如何選擇調(diào)度方式和算法，在很大程度上取決于操作系統(tǒng)的類型及其目標，選擇選擇調(diào)度方式和算法的準則有：u 面向用戶的準則面向用戶的準則v周轉(zhuǎn)時間短v響應(yīng)時間快v截

11、止時間的保證v優(yōu)先權(quán)準則u 面向系統(tǒng)的準則面向系統(tǒng)的準則v系統(tǒng)吞吐量v處理機利用率好v各類資源平衡利用Process Management進程管理-processes 進程 u 最優(yōu)準則最優(yōu)準則v 最大的CPU利用率v 最大的吞吐量v 最短的周轉(zhuǎn)時間v 最短的等待時間v 最短的響應(yīng)時間返回本節(jié)3.2 3.2 調(diào)度算法調(diào)度算法u 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法u 短作業(yè)短作業(yè)/ /進程優(yōu)先調(diào)度算法進程優(yōu)先調(diào)度算法u 時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法u 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法u 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法u 多級隊列調(diào)度算法多級隊列調(diào)度算法u 多級反饋隊列調(diào)度算法多級

12、反饋隊列調(diào)度算法返回目錄 進程調(diào)度的核心問題就是采用什么樣的算法將處理機分配給進程，常用的進程調(diào)度算法有：一、先來先服務(wù)調(diào)度算法一、先來先服務(wù)調(diào)度算法FCFSu 基本思想:按照進程進入就緒隊列的先后次序來分配處理機。 一般采用非剝奪的調(diào)度方式。u Example:進程名 到達時間 服務(wù)時間 A 0 1 B 1 100 C 2 1 D 3 100u 該調(diào)度的Gantt圖為:u 平均周轉(zhuǎn)時間:(1-0)+(101-1)+(102-2)+(202-3)）/4=100u 平均等待時間:(0-0)+(1-1)+(101-2)+(102-3)/4 = 49.5Process Management進程管理-

13、 CPU Scheduling CPU調(diào)度DBCA0 1 2 3 101 102 202 0 1 2 3 101 102 202 一、一、FCFSFCFS調(diào)度算法（續(xù)）調(diào)度算法（續(xù)）u 改變到達順序改變到達順序: : 進程名進程名 到達時間到達時間 服務(wù)時間服務(wù)時間 A A 0 1 0 1 B B 1 1 100100 D D 2 100 2 100 C C 3 3 1 1u 該調(diào)度的該調(diào)度的GanttGantt圖為圖為: :u 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間: :（(1-0)+(101-1)+(202-3)+(201-2)(1-0)+(101-1)+(202-3)+(201-2)）/4=124.2

14、5/4=124.25u 平均等待時間平均等待時間: (: (0(0-0)-0)+ +(1-1)(1-1)+ +(201-3)+(101-2)(201-3)+(101-2)/4 = )/4 = 74.2574.25Process Management進程管理- CPU Scheduling CPU調(diào)度ABDC周轉(zhuǎn)周轉(zhuǎn)T100100124.25124.25等待等待T49.549.574.2574.250 1 2 3 101 201 202 0 1 2 3 101 201 202 FCFSFCFS調(diào)度算法存在的問題調(diào)度算法存在的問題 從表面上，先來先服務(wù)于所有作業(yè)是公平的，即按照它們到來的先后次序進

15、程服務(wù)。但若一個長作業(yè)先到達系統(tǒng)，就會使許多短作業(yè)等待很長的時間，從而引起許多短作業(yè)用戶的不滿。 所以，現(xiàn)在操作系統(tǒng)中，已很少用該算法作為主要調(diào)度策略，尤其是在分時系統(tǒng)和實時系統(tǒng)中。但它常被結(jié)合在其它調(diào)度策略中使用。Process Management進程管理- CPU Scheduling CPU調(diào)度返回二、短作業(yè)二、短作業(yè)/ /進程優(yōu)先調(diào)度算法進程優(yōu)先調(diào)度算法SJF/SPFSJF/SPFu 短作業(yè)優(yōu)先調(diào)度算法（短作業(yè)優(yōu)先調(diào)度算法（SJFSJF）v用于作業(yè)調(diào)度用于作業(yè)調(diào)度v主要任務(wù)是從后備隊列中選擇一個或若干個估計運行主要任務(wù)是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)

16、存運行。時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。u 短進程優(yōu)先調(diào)度算法（短進程優(yōu)先調(diào)度算法（SPFSPF）v用于進程調(diào)度用于進程調(diào)度v主要任務(wù)是從就緒隊列中選出一估計運行時間最短的主要任務(wù)是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它。進程，將處理機分配給它。v可采用搶占（剝奪）或者非搶占（非剝奪）調(diào)度方式?？刹捎脫屨迹▌儕Z）或者非搶占（非剝奪）調(diào)度方式。Process Management進程管理- CPU Scheduling CPU調(diào)度二、二、SJSJ（P P）F F _ _非搶占式非搶占式u 到達順序到達順序: : 進程名進程名 到達時間到達時間 服務(wù)時間服務(wù)時間 A A 0

17、 1 0 1 B B 1 1 100100 D D 2 100 2 100 C C 3 3 1 1u 該調(diào)度的該調(diào)度的GanttGantt圖為圖為: :u 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間: :(1-0)+(101-1)+(102-3)+(202-2)/4=(1-0)+(101-1)+(102-3)+(202-2)/4=100100u 平均等待時間平均等待時間: : (0 0-0)-0)+ +(1-1)(1-1)+ +(101-3)+(102-2)(101-3)+(102-2)/4 = )/4 = 49.549.5Process Management進程管理- CPU Scheduling CPU調(diào)度

18、ABCDFCFSFCFSSPFSPF周轉(zhuǎn)周轉(zhuǎn)T124.25124.25100100等待等待T74.2574.2549.549.50 1 2 3 101 102 202 0 1 2 3 101 102 202 二、短作業(yè)二、短作業(yè)/ /進程優(yōu)先調(diào)度算法進程優(yōu)先調(diào)度算法_ _搶占式搶占式u 到達順序到達順序: : 進程名進程名 到達時間到達時間 服務(wù)時間服務(wù)時間 A A 0 1 0 1 B B 1 1 100100 D D 2 100 2 100 C C 3 3 1 1u 該調(diào)度的該調(diào)度的GanttGantt圖為圖為: :u 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(1-0)+(102-1)+(4-3)+(20

19、2-2)=(1-0)+(102-1)+(4-3)+(202-2)）/4=75.75/4=75.75u 平均等待時間平均等待時間= =( (0-(0-0)+0)+(4-3)(4-3)+ +(3-3)+(102-2)(3-3)+(102-2)/4 = )/4 = 25.2525.25Process Management進程管理- CPU Scheduling CPU調(diào)度ABBCBD0 1 2 3 4 102 202 0 1 2 3 4 102 202 FCFSFCFSSPF-SPF-非非SPF-SPF-搶搶周轉(zhuǎn)周轉(zhuǎn)T124.25124.2510010075.7575.75等待等待T74.2574.

20、2549.549.525.2525.25uEgEg： 進程進程 到達時間到達時間 服務(wù)時間服務(wù)時間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (非搶占式非搶占式) )u平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(7-0)+(12-2)+(8-4)+(16-5)/4=8=(7-0)+(12-2)+(8-4)+(16-5)/4=8u平均等待時間平均等待時間 = (0-0)+(8-2)+(7-4)+(12-5)/4 = 4= (0-0)+(8-2)+(7-4)+(12-5)/4 = 4SPFSPF（非搶占式）調(diào)度（

21、非搶占式）調(diào)度73160812P1P3P2P4Process Management進程管理- CPU Scheduling CPU調(diào)度SPFSPF搶占式調(diào)度搶占式調(diào)度進程進程到達時間到達時間服務(wù)時間服務(wù)時間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (搶占式搶占式) )u平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(16-0)+(7-2)+(5-4)+(11-5)/4=7=(16-0)+(7-2)+(5-4)+(11-5)/4=7u平均等待時間平均等待時間=(11-2)+(5-4)+(4-4)+(7-5)/4

22、= 3=(11-2)+(5-4)+(4-4)+(7-5)/4 = 3P1P3P242110P457P2P116Process Management進程管理- CPU Scheduling CPU調(diào)度FCFSFCFS先來先服務(wù)調(diào)度先來先服務(wù)調(diào)度進程進程到達時間到達時間服務(wù)時間服務(wù)時間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uFCFSFCFSu平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(7-0)+(11-2)+(12-4)+(16-5)/4=8.75=(7-0)+(11-2)+(12-4)+(16-5)/4=8.75u平均等待時

23、間平均等待時間 =(0+(7-2)+(11-4)+(12-5)/4 =4.75=(0+(7-2)+(11-4)+(12-5)/4 =4.75Process Management進程管理- CPU Scheduling CPU調(diào)度P142110P257P41612P3SPFSPF與與FCFSFCFS的比較的比較FCFSFCFS非搶占非搶占SPFSPF搶占搶占SPFSPF吞吐量吞吐量0-70-7msms1 11 12 2平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間8.758.758 87 7平均等待時間平均等待時間4.754.754 43 3SF(P)FSF(P)F短作業(yè)短作業(yè)/ /進程優(yōu)先調(diào)度的優(yōu)缺點進程優(yōu)先調(diào)度的

24、優(yōu)缺點優(yōu)點：優(yōu)點： 1 1）能有效降低作業(yè)的平均等待時間；）能有效降低作業(yè)的平均等待時間； 2 2）提高吞吐量；）提高吞吐量； 3 3）能有效縮短進程的周轉(zhuǎn)時間；）能有效縮短進程的周轉(zhuǎn)時間；缺點：缺點： 1 1）對長作業(yè)不利；）對長作業(yè)不利； 2 2）不考慮）不考慮作業(yè)的緊迫程度作業(yè)的緊迫程度； 3 3）作業(yè)執(zhí)行時間、剩余時間僅為）作業(yè)執(zhí)行時間、剩余時間僅為估計估計* *； 故故SJ(P)FSJ(P)F算法雖然是優(yōu)化的，但在算法雖然是優(yōu)化的，但在CPUCPU調(diào)度中很難實現(xiàn)。調(diào)度中很難實現(xiàn)。返回三、時間片輪轉(zhuǎn)調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法RRRRProcess Management進程管理- C

25、PU Scheduling CPU調(diào)度 應(yīng)用于分時應(yīng)用于分時OSOS中，能保證及時響應(yīng)用戶的請求，是中，能保證及時響應(yīng)用戶的請求，是早期采用的一種調(diào)度算法；進入早期采用的一種調(diào)度算法；進入9090年代后，廣泛采用多年代后，廣泛采用多級反饋隊列調(diào)度算法。級反饋隊列調(diào)度算法。q時間片輪轉(zhuǎn)法：時間片輪轉(zhuǎn)法：系統(tǒng)將所有原就緒進程按系統(tǒng)將所有原就緒進程按FCFSFCFS的原則，的原則，排成一個隊列，依次調(diào)度，把排成一個隊列，依次調(diào)度，把CPUCPU分配給隊首進程，并令分配給隊首進程，并令其執(zhí)行一個時間片其執(zhí)行一個時間片/CPU/CPU時間，通常為時間，通常為10-10010-100msms。時間片。時間

26、片用完后，該進程將用完后，該進程將被搶占被搶占并插入就緒隊列末尾。并插入就緒隊列末尾。三、時間片輪轉(zhuǎn)調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法RRRR注：注：（1 1）保證了就緒隊列中的所有進程在給定的時間內(nèi)，均能獲）保證了就緒隊列中的所有進程在給定的時間內(nèi)，均能獲得一時間片來執(zhí)行，即系統(tǒng)在給定的時間內(nèi)，響應(yīng)所有用戶得一時間片來執(zhí)行，即系統(tǒng)在給定的時間內(nèi)，響應(yīng)所有用戶的請求。的請求。（2 2）若進程的執(zhí)行時間少于時間片，則自愿釋放）若進程的執(zhí)行時間少于時間片，則自愿釋放CPUCPU。（3 3）時間片將影響：）時間片將影響：q調(diào)度算法（太長調(diào)度算法（太長-FCFS-FCFS）；）；q上下文切換（太短上下文切

27、換（太短-上下文切換頻繁，如下頁上下文切換頻繁，如下頁）；）；q平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間。短時間片增加上下文切換頻率短時間片增加上下文切換頻率周轉(zhuǎn)時間隨時間片變化周轉(zhuǎn)時間隨時間片變化三、時間片輪轉(zhuǎn)調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法例例(1)(1)EGEG：進程進程到達時間到達時間服務(wù)時間服務(wù)時間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uRRRR（時間片為（時間片為1 1）u平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(15-0)+(12-2)+(6-4)+(16-5)/4=9.5=(15-0)+(12-2)+(6-4)+(16-5

28、)/4=9.5u平均等待時間平均等待時間=(8+6+1+7)/4 = 5.5=(8+6+1+7)/4 = 5.5Process Management進程管理- CPU Scheduling CPU調(diào)度P1P2P20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16P4P1P1P1P3P2P1P4P2P4P1P4三、時間片輪轉(zhuǎn)調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法例例(2)(2)EGEG：進程進程到達時間到達時間服務(wù)時間服務(wù)時間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uRRRR（時間片為（時

29、間片為4 4）u平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(12-0)+(8-2)+(9-4)+(16-5)/4=8.5=(12-0)+(8-2)+(9-4)+(16-5)/4=8.5u平均等待時間平均等待時間=(5+2+4+7)/4 = 4.5=(5+2+4+7)/4 = 4.5Process Management進程管理- CPU Scheduling CPU調(diào)度P1P20 4 5 6 7 8 9 10 11 12 13 14 15 16P4P3P1FCFSFCFS非搶占非搶占SPFSPF搶占搶占SPFSPFRR-1RR-1RR-RR-4 4平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間8.758.758 87 79.59.5

30、8.58.5平均等待時間平均等待時間4.754.754 43 35.55.54.54.5Example: RR with Time Quantum = 20Example: RR with Time Quantum = 20ProcessProcessBurst TimeBurst TimeP P1 15353 P P2 2 1717 P P3 36868 P P4 4 2424uGantt : Gantt : uRRRR的平均周轉(zhuǎn)時間比的平均周轉(zhuǎn)時間比SPFSPF長，但響應(yīng)時間要短一些長，但響應(yīng)時間要短一些. .P1P2P3P4P1P3P4P1P3P302037577797117121 13

31、4154 162返回四、優(yōu)先權(quán)調(diào)度算法四、優(yōu)先權(quán)調(diào)度算法Process Management進程管理- CPU Scheduling CPU調(diào)度非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法：系統(tǒng)一旦把處理機分配給就緒隊列中系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直到完成的進程后，該進程便一直執(zhí)行下去，直到完成/ /因發(fā)生因發(fā)生某事件而放棄處理機時，系統(tǒng)方可重新分配處理機。某事件而放棄處理機時，系統(tǒng)方可重新分配處理機。搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法：系統(tǒng)把處理機分配給就緒隊列中優(yōu)先機系統(tǒng)把處理機分配給就緒隊列中優(yōu)先機最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要

32、出現(xiàn)了另一個優(yōu)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要出現(xiàn)了另一個優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當(dāng)前進程的執(zhí)行，重先權(quán)更高的進程，進程調(diào)度程序就立即停止當(dāng)前進程的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。新將處理機分配給新到的優(yōu)先權(quán)最高的進程。非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法例例EGEG：進程進程到達時間到達時間 服務(wù)時間服務(wù)時間 優(yōu)先權(quán)優(yōu)先權(quán)P P1 10.00.0 7 3 7 3 P P2 22.02.0 4 2 4 2 P P3 34.04.0 1 4 1 4 P P4 45.05.0 4 4 1 1uGanttGantt圖圖u平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(7-0)+

33、(15-2)+(16-4)+(11-5)/4=8.5=(7-0)+(15-2)+(16-4)+(11-5)/4=8.5u平均等待時間平均等待時間=(0+9+11+2)/4 = 5.5=(0+9+11+2)/4 = 5.5Process Management進程管理- CPU Scheduling CPU調(diào)度P1P20 2 4 5 7 11 15 16P4P3FCFSFCFSSJF-SJF-非非SJF-SJF-搶搶RR-RR-4 4優(yōu)優(yōu)- -非非平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間8.758.758 84 48.58.59.59.5平均等待時間平均等待時間4.754.754 43 34.54.55.55.5

34、搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法例例EGEG：進程進程到達時間到達時間 服務(wù)時間服務(wù)時間 優(yōu)先權(quán)優(yōu)先權(quán)P P1 10.00.0 7 3 7 3 P P2 22.02.0 4 2 4 2 P P3 34.04.0 1 4 1 4 P P4 45.05.0 4 4 1 1uGanttGantt圖圖u平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(11-0)+(9-2)+(16-4)+(8-5)/4=8.25=(11-0)+(9-2)+(16-4)+(8-5)/4=8.25u平均等待時間平均等待時間=(7+3+11+0)/4 = 5.25=(7+3+11+0)/4 = 5.25Process Management進程管

35、理- CPU Scheduling CPU調(diào)度FCFSFCFSSJF-SJF-非非SJF-SJF-搶搶RR-4RR-4優(yōu)優(yōu)- -非非優(yōu)優(yōu)- -搶搶平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間8.758.758 84 48.58.59.59.58.258.25平均等待時間平均等待時間4.754.754 43 34.54.55.55.55.255.25P1P20 2 4 5 8 9 11 15 16P4P3P2P1優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型Process Management進程管理- CPU Scheduling CPU調(diào)度靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 優(yōu)先權(quán)在創(chuàng)建進程時確定，且在進程的整個運行期間優(yōu)先權(quán)在創(chuàng)建進程時確定，且

36、在進程的整個運行期間保持不變。一般用一整數(shù)表示，小表優(yōu)先級高。保持不變。一般用一整數(shù)表示，小表優(yōu)先級高。動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán) 優(yōu)先權(quán)在創(chuàng)建進程時確定，但在進程的運行期間會發(fā)優(yōu)先權(quán)在創(chuàng)建進程時確定，但在進程的運行期間會發(fā)生變化。生變化。 返回五、高響應(yīng)比優(yōu)先權(quán)調(diào)度算法五、高響應(yīng)比優(yōu)先權(quán)調(diào)度算法Process Management進程管理- CPU Scheduling CPU調(diào)度v優(yōu)先權(quán)的變化為優(yōu)先權(quán)的變化為 PR要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán)PR為響應(yīng)比。為響應(yīng)比。注：注： 1)1)如等待時間相同如等待時間相同, ,則要求服務(wù)時間愈短則要求服務(wù)時間愈短, ,其優(yōu)先權(quán)

37、愈高其優(yōu)先權(quán)愈高-SPF.SPF.2)2)如要求服務(wù)時間相同如要求服務(wù)時間相同, ,優(yōu)先權(quán)決定于等待時間優(yōu)先權(quán)決定于等待時間-FCFSFCFS。3)3)對長作業(yè)對長作業(yè), ,若等待時間足夠長，優(yōu)先權(quán)也高，也能獲得若等待時間足夠長，優(yōu)先權(quán)也高，也能獲得CPUCPU。返回六、多級隊列調(diào)度算法六、多級隊列調(diào)度算法Process Management進程管理- CPU Scheduling CPU調(diào)度q基本思想基本思想: :根據(jù)作業(yè)的性質(zhì)或類型，將就緒隊列劃分為若干個獨立的隊根據(jù)作業(yè)的性質(zhì)或類型，將就緒隊列劃分為若干個獨立的隊列，每個作業(yè)固定地分屬一個隊列。每個隊列采用一種調(diào)度列，每個作業(yè)固定地分屬一

38、個隊列。每個隊列采用一種調(diào)度算法，不同的隊列可以采用不同的調(diào)度算法。算法，不同的隊列可以采用不同的調(diào)度算法。 如：交互型作業(yè)設(shè)置一隊列如：交互型作業(yè)設(shè)置一隊列-時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法 批處理作業(yè)設(shè)置一隊列批處理作業(yè)設(shè)置一隊列-FCFS-FCFS調(diào)度算法調(diào)度算法q前臺前臺 交互式交互式 - RRRRq后臺后臺 批處理批處理 -優(yōu)先權(quán)、優(yōu)先權(quán)、SPFSPF或或 FCFSFCFS返回q基本思想基本思想： 多級反饋隊列調(diào)度算法是時間片輪轉(zhuǎn)算法和優(yōu)先級多級反饋隊列調(diào)度算法是時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法的綜合和發(fā)展，通過動態(tài)調(diào)整進程優(yōu)先級和時調(diào)度算法的綜合和發(fā)展，通過動態(tài)調(diào)整進程優(yōu)先級和時

39、間片大小，不必事先估計進程的執(zhí)行時間，多級反饋隊間片大小，不必事先估計進程的執(zhí)行時間，多級反饋隊列可兼顧多方面的系統(tǒng)目標，是目前公認的一種較好的列可兼顧多方面的系統(tǒng)目標，是目前公認的一種較好的進程調(diào)度算法。進程調(diào)度算法。七、多級反饋隊列調(diào)度算法七、多級反饋隊列調(diào)度算法七、七、多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法- - -實現(xiàn)思想實現(xiàn)思想就緒隊列1就緒隊列2就緒隊列nCPUCPUCPU完成完成完成（1 1）設(shè)置）設(shè)置多個就緒隊列多個就緒隊列，并為每個隊列賦予，并為每個隊列賦予不同的優(yōu)先級不同的優(yōu)先級。隊列。隊列1 1的優(yōu)先級最高，其余隊列逐個降低。的優(yōu)先級最高，其余隊列逐個降低。（2 2）每

40、個隊列中）每個隊列中進程執(zhí)行時間片的大小進程執(zhí)行時間片的大小也各不相同，進程所在隊列也各不相同，進程所在隊列的優(yōu)先級越高，其相應(yīng)的時間片就越短。的優(yōu)先級越高，其相應(yīng)的時間片就越短。（3 3）當(dāng)一個）當(dāng)一個新進程進入新進程進入系統(tǒng)時，首先將它放入隊列系統(tǒng)時，首先將它放入隊列1 1的末尾，按的末尾，按FCFSFCFS等待調(diào)度。如能完成，便可準備撤離系統(tǒng)，反之由調(diào)度程序?qū)⒌却{(diào)度。如能完成，便可準備撤離系統(tǒng)，反之由調(diào)度程序?qū)⑵滢D(zhuǎn)入隊列其轉(zhuǎn)入隊列2 2的末尾，按的末尾，按FCFSFCFS再次等待調(diào)度，如此下去，進入隊列再次等待調(diào)度，如此下去，進入隊列n n按按RRRR算法調(diào)度執(zhí)行。算法調(diào)度執(zhí)行。（4

41、4）僅當(dāng)隊列）僅當(dāng)隊列1 1為空時，才調(diào)度隊列為空時，才調(diào)度隊列2 2中的進程運行。若隊列中的進程運行。若隊列I I中的中的進程正執(zhí)行，此時有新進程進入優(yōu)先級較高的隊列中，則新進程將進程正執(zhí)行，此時有新進程進入優(yōu)先級較高的隊列中，則新進程將搶占運行搶占運行。原進程轉(zhuǎn)移至下一隊列。原進程轉(zhuǎn)移至下一隊列。返回3.3 3.3 實時系統(tǒng)中的調(diào)度實時系統(tǒng)中的調(diào)度u 在一個實時系統(tǒng)中，在一個實時系統(tǒng)中，時間起著非常重要的作用，即每一個實時進程或任務(wù)都有一個時間約束要求，如：在何時之前必須開始做，在何時之前必須完成等等。在一個實時應(yīng)用系統(tǒng)，可能有多個實時進程或任務(wù)，每個實時任務(wù)都有其可能有多個實時進程或任務(wù)

42、，每個實時任務(wù)都有其時間時間約束，約束，所以需一種新的調(diào)度算法來合理地安排這些實時任務(wù)的執(zhí)行次序，使它們能滿足各個實時任務(wù)的的時間約束條件-實實時調(diào)度時調(diào)度。u 實時調(diào)度：滿足實時任務(wù)各自時間約束條件的調(diào)度稱為實時調(diào)度。一、實現(xiàn)實時調(diào)度的基本條件一、實現(xiàn)實時調(diào)度的基本條件v提供必要的調(diào)度信息（就緒時間、開始截止時間和完成截提供必要的調(diào)度信息（就緒時間、開始截止時間和完成截止時間、處理時間、資源要求、優(yōu)先級）止時間、處理時間、資源要求、優(yōu)先級）v系統(tǒng)處理能力強（限制條件：決定系統(tǒng)是否可調(diào)度，否則系統(tǒng)處理能力強（限制條件：決定系統(tǒng)是否可調(diào)度，否則減少減少C 單機單機: （m-實時任務(wù)數(shù)目，實時任務(wù)

43、數(shù)目，ci每次處理時間，每次處理時間，pi周期時間）周期時間） 多機多機: （N處理機數(shù)目，處理機數(shù)目，ci每次處理時間，每次處理時間，pi周期時間）周期時間）v采用搶占式的調(diào)度機制采用搶占式的調(diào)度機制v具有快速切換機制具有快速切換機制11 miiipcNpcmiii 1二、二、 實時調(diào)度算法的分類實時調(diào)度算法的分類u 按實時任務(wù)性質(zhì)（即對時間約束強強弱程度）按實時任務(wù)性質(zhì)（即對時間約束強強弱程度）v硬實時調(diào)度：必須滿足任務(wù)截止期要求，錯過可能導(dǎo)致嚴重后果。v軟實時調(diào)度算法：期望滿足任務(wù)截止期要求，錯過一般可容忍。u 按調(diào)度方式按調(diào)度方式v非搶占式調(diào)度算法（如下圖所示）非搶占式輪轉(zhuǎn)調(diào)度算法：

44、用于工業(yè)生產(chǎn)的群控系統(tǒng)中。非搶占式優(yōu)先調(diào)度算法：用于有一定時間要求的實時控制系統(tǒng)之中。v搶占式調(diào)度算法 （如下圖所示） 按搶占發(fā)生的時間 基于時鐘中斷搶占的優(yōu)先權(quán)調(diào)度算法立即搶占的優(yōu)先權(quán)調(diào)度算法進程n實時進程進程1進程2實時進程要求調(diào)度調(diào)度實時進程運行調(diào)度時間（a）非搶占輪轉(zhuǎn)調(diào)度）非搶占輪轉(zhuǎn)調(diào)度實時進程要求調(diào)度時鐘中斷到來時調(diào)度調(diào)度時間當(dāng)前進程實時進程（c）基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度）基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度實時進程要求調(diào)度當(dāng)前進程運行完成調(diào)度時間當(dāng)前進程實時進程（b）非搶占優(yōu)先權(quán)調(diào)度）非搶占優(yōu)先權(quán)調(diào)度實時進程要求調(diào)度實時進程搶占當(dāng)前進程，并立即執(zhí)行調(diào)度時間當(dāng)前進程實時進程（d）

45、立即搶占的優(yōu)先權(quán)調(diào)度）立即搶占的優(yōu)先權(quán)調(diào)度實時進程調(diào)度實時進程調(diào)度與實時調(diào)度相關(guān)的幾個概念與實時調(diào)度相關(guān)的幾個概念u 就緒時間：實時任務(wù)產(chǎn)生并可以開始處理的時間。u 開始截止時間：實時任務(wù)最遲開始處理的時間。u 處理時間：實時任務(wù)處理所需要的處理機的時間。u 完成截止時間：實時任務(wù)最遲完成時間。u 發(fā)生周期：周期性實時任務(wù)的發(fā)生間隔時間。u 優(yōu)先級：實時任務(wù)相對緊廹程序。三、常用的幾種實時調(diào)度算法三、常用的幾種實時調(diào)度算法u 最早截止時間優(yōu)先算法（EDF算法）v該算法是根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級。開始截止時間越早，其優(yōu)先級越高。就緒隊列中任務(wù)按其截止時間排列，隊首任務(wù)先分配處理機

46、。v如：u 最低松弛度優(yōu)先算法（LLF算法）2 43143212431開始截止時間任務(wù)執(zhí)行任務(wù)到達最低松弛度優(yōu)先算法（最低松弛度優(yōu)先算法（LLFLLF算法）算法）u 該算法是根據(jù)任務(wù)緊急（或松弛）的程序，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急度越高，其優(yōu)先級越高，并使之優(yōu)先執(zhí)行。該算法主要采用搶占調(diào)度方式，其調(diào)度也即具有完成截止時也即具有完成截止時間的周期性實時任務(wù)的調(diào)度間的周期性實時任務(wù)的調(diào)度u 例：在一個實時系統(tǒng)中，有兩個周期性實時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B只要求每50ms執(zhí)行，執(zhí)行時間為25ms。其最低松弛度優(yōu)先算法調(diào)度如下：A8A7A6A5A4A3A2

47、A1160140120100806040200B3B2B1A和和B任務(wù)每次必須完成的時間任務(wù)每次必須完成的時間某時刻的松弛度計算：某時刻的松弛度計算： 松弛度松弛度=必須完成時間必須完成時間-其本身的運行時間其本身的運行時間-當(dāng)前時間當(dāng)前時間 優(yōu)先調(diào)度松弛度小的任務(wù)優(yōu)先調(diào)度松弛度小的任務(wù)利用最低松弛度優(yōu)先算法調(diào)度情況利用最低松弛度優(yōu)先算法調(diào)度情況08070605040302010B2(15)B1(20)A1(10)A2(10)B1(5)A3(10)A4(10)B2(10)t1 t2 t3 t4 t5 t6 t7 t8返回目錄10.2.4 UNIX10.2.4 UNIX中進程的調(diào)度中進程的調(diào)度

48、UNIX是單純的分時系統(tǒng)，無作業(yè)調(diào)度，只設(shè)置有中級調(diào)度和低級調(diào)度。常采用的是多級反饋隊列輪轉(zhuǎn)調(diào)度。u 引起進程調(diào)度的原因引起進程調(diào)度的原因v時鐘中斷處理程序?qū)φ{(diào)度標志runrun的重新置位。v系統(tǒng)執(zhí)行了wait、exit及sleep等系統(tǒng)調(diào)用后。v進程執(zhí)行完系統(tǒng)調(diào)用而從核心態(tài)返回到用戶態(tài)時，出現(xiàn)了更高優(yōu)先級的進程。u 調(diào)度算法調(diào)度算法v動態(tài)優(yōu)先數(shù)輪轉(zhuǎn)調(diào)度算法u 進程優(yōu)先級的分類進程優(yōu)先級的分類v核心優(yōu)先級（分為可中斷和不可中斷）v用戶優(yōu)先級（分成n+1級，0級最高）u 進程優(yōu)先級的計算進程優(yōu)先級的計算基本用戶優(yōu)先數(shù)的時間最近使用優(yōu)先數(shù) 2CPU返回目錄3.5 3.5 死鎖的死鎖的基本概念基本概

49、念 在多道程序系統(tǒng)中，由于多個進程的并發(fā)執(zhí)行，改善了系統(tǒng)資源的利用率并提高了系統(tǒng)的處理能力，然而，多個進程的并發(fā)執(zhí)行也帶來了新的問題-死鎖。u 例：設(shè)有一臺輸入機和一臺輸出機，進程P1和P2需要使用這兩個資源。設(shè)兩個進程的活動分別為：P1的活動：申請輸入機申請輸出機釋放輸出機釋放輸入機P2的活動：申請輸出機申請輸入機釋放輸入機釋放輸出機P1與與P2均因得不到資源而無法繼續(xù)向前推進，這種由于進程競爭資源均因得不到資源而無法繼續(xù)向前推進，這種由于進程競爭資源而引起的僵持稱為死鎖。而引起的僵持稱為死鎖。3.5 3.5 死鎖的死鎖的基本概念基本概念u死鎖死鎖u產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因u產(chǎn)生死鎖的必

50、要條件產(chǎn)生死鎖的必要條件u處理死鎖的基本方法處理死鎖的基本方法返回目錄3.5 3.5 死鎖的死鎖的基本概念基本概念u一、死鎖一、死鎖 指多個進程在運行過程中因爭奪資源而造成的一種僵局（指多個進程在運行過程中因爭奪資源而造成的一種僵局（deadly-deadly-Embrace)Embrace)，若無外力作用，這些進程都將無法向前推進，若無外力作用，這些進程都將無法向前推進。u如圖如圖R1R2P1P2注意：注意：（1 1）參與死鎖的進程數(shù)至少為）參與死鎖的進程數(shù)至少為2 2（2 2）參與死鎖的所有進程均等待資源）參與死鎖的所有進程均等待資源（3 3）參與死鎖的進程至少有兩個占有資源）參與死鎖的進

51、程至少有兩個占有資源（4 4）參與死鎖的進程是系統(tǒng)中當(dāng)前正在運行）參與死鎖的進程是系統(tǒng)中當(dāng)前正在運行進程的一部分。進程的一部分。返回二、產(chǎn)生死鎖的原因二、產(chǎn)生死鎖的原因u資源資源分類分類 操作系統(tǒng)管理著系統(tǒng)內(nèi)所有資源，它負責(zé)分配不同類型的操作系統(tǒng)管理著系統(tǒng)內(nèi)所有資源，它負責(zé)分配不同類型的資源給進程使用，系統(tǒng)中的資源從不同角度可分：資源給進程使用，系統(tǒng)中的資源從不同角度可分： 根據(jù)資源本身的性質(zhì)根據(jù)資源本身的性質(zhì)v可剝奪資源：如主存、可剝奪資源：如主存、CPUCPUv不可剝奪資源：如驅(qū)動器、打印機等不可剝奪資源：如驅(qū)動器、打印機等 根據(jù)資源使用期限根據(jù)資源使用期限v永久性資源：可再次使用，如所有

52、硬件。永久性資源：可再次使用，如所有硬件。v臨時性臨時性資源：消耗性的資源，如消息、信號和數(shù)據(jù)資源：消耗性的資源，如消息、信號和數(shù)據(jù)競爭臨時性資源競爭臨時性資源若按下列順序進行無死鎖產(chǎn)生：若按下列順序進行無死鎖產(chǎn)生：P1：Release(s1);Request(S3);P2：Release(s2);Request(S1);P3：Release(s3);Request(S2);但若按下列順序進行可能產(chǎn)生死鎖：但若按下列順序進行可能產(chǎn)生死鎖：P1： Request(S3); Release(s1); P2： Request(S1) ; Release(s2);P3： Request(S2) ; R

53、elease(s3);二、產(chǎn)生死鎖的原因二、產(chǎn)生死鎖的原因u 競爭資源競爭資源競爭非剝奪性資源競爭非剝奪性資源 競爭競爭臨時性臨時性資源資源R1R2P1P2競爭非剝奪性資源競爭非剝奪性資源R1R1代表系統(tǒng)中僅有的一臺打印機代表系統(tǒng)中僅有的一臺打印機R2R2代表系統(tǒng)中僅有的一臺磁帶機代表系統(tǒng)中僅有的一臺磁帶機P1P1、 P2P2代表可共享資源的進程代表可共享資源的進程S3S1S2P1P2P3二、產(chǎn)生死鎖的原因二、產(chǎn)生死鎖的原因u 進程間推進順序非法進程間推進順序非法S S和和Q Q是兩個初值為是兩個初值為1 1的信號量的信號量P P0 0P P1 1P P( (S S););P P( (Q Q)

54、;);P(P(Q Q););P(P(S S);); V(V(S S););V(V(Q Q););V(V(Q Q) )V(V(S S););u 其它原因：如兩進程謙讓即其它原因：如兩進程謙讓即“After You/ After You”After You/ After You”問題。問題。返回三、產(chǎn)生死鎖的必要條件三、產(chǎn)生死鎖的必要條件 產(chǎn)生死鎖必須具備以下四個條件，這四個條件是產(chǎn)生死鎖必須具備以下四個條件，這四個條件是Coffman首先提出的，所以稱為首先提出的，所以稱為Coffman 條件：條件：v互斥條件（資源獨占條件）互斥條件（資源獨占條件）v請求和保持條件（部分分配條件）請求和保持條件

55、（部分分配條件）v不剝奪條件不剝奪條件v循環(huán)等待條件（環(huán)路條件）循環(huán)等待條件（環(huán)路條件）返回四、四、處理死鎖的基本方法處理死鎖的基本方法 目前處理死鎖的基本方法有四種：目前處理死鎖的基本方法有四種：u 鴕鳥算法鴕鳥算法：指像鴕鳥一樣對死鎖視而不見，即不理睬死鎖。指像鴕鳥一樣對死鎖視而不見，即不理睬死鎖。u 預(yù)防死鎖預(yù)防死鎖：指通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的指通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來防止死鎖的發(fā)生。一個或幾個條件，來防止死鎖的發(fā)生。u 避免死鎖避免死鎖：指在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進入不安全指在資源的動態(tài)分

56、配過程中，用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免死鎖的發(fā)生。狀態(tài)，從而避免死鎖的發(fā)生。u 檢測死鎖檢測死鎖：允許系統(tǒng)在運行過程中發(fā)生死鎖，但可設(shè)置檢測機構(gòu)及時檢測死允許系統(tǒng)在運行過程中發(fā)生死鎖，但可設(shè)置檢測機構(gòu)及時檢測死鎖的發(fā)生，并采取適當(dāng)措施加以清除。鎖的發(fā)生，并采取適當(dāng)措施加以清除。u 解除死鎖解除死鎖：當(dāng)檢測出死鎖后，便采取適當(dāng)措施將進程從死鎖狀態(tài)中解脫出來。當(dāng)檢測出死鎖后，便采取適當(dāng)措施將進程從死鎖狀態(tài)中解脫出來。返回3.6 3.6 死鎖的預(yù)防和避免方法死鎖的預(yù)防和避免方法一、死鎖的預(yù)防一、死鎖的預(yù)防 破壞死鎖的四個必要條件（常針對條件破壞死鎖的四個必要條件（常針對條件2,3,4

57、)（1）破壞互斥條件：）破壞互斥條件：即允許多個進程同時訪問資源。但由于資源本身即允許多個進程同時訪問資源。但由于資源本身固有特性限制，有的資源根本不能同時訪問，只能互斥訪問，所以破壞固有特性限制，有的資源根本不能同時訪問，只能互斥訪問，所以破壞互斥條件來預(yù)防死鎖，這不太可能?；コ鈼l件來預(yù)防死鎖，這不太可能。（2）破壞請求和保條件：）破壞請求和保條件：可采用預(yù)先靜態(tài)分配方法，即要求進程在運可采用預(yù)先靜態(tài)分配方法，即要求進程在運行之前一次申請它所需要的全部資源，在它的資源未滿足前，不把它投行之前一次申請它所需要的全部資源，在它的資源未滿足前，不把它投入運行。一旦運行后，這些資源全歸其占有，同時它

58、也不再提出其它資入運行。一旦運行后，這些資源全歸其占有，同時它也不再提出其它資源要求，這樣可以保證系統(tǒng)不會發(fā)生死鎖。此方法雖簡單安全，但降低源要求，這樣可以保證系統(tǒng)不會發(fā)生死鎖。此方法雖簡單安全，但降低了資源利用率，同時必須預(yù)知進程所需要的全部資源。了資源利用率，同時必須預(yù)知進程所需要的全部資源。3.6 3.6 死鎖的預(yù)防和避免方法死鎖的預(yù)防和避免方法一、死鎖的預(yù)防一、死鎖的預(yù)防（3）破壞不可剝奪條件：）破壞不可剝奪條件：即一個已經(jīng)獲得某些資源的進程，若又請求即一個已經(jīng)獲得某些資源的進程，若又請求新的資源時不能得到滿足，則它必須釋放出已獲得的所有資源，以后需新的資源時不能得到滿足，則它必須釋放

59、出已獲得的所有資源，以后需要資源時再請求。也即一個進程已獲得的資源在運行過程中可被剝奪。要資源時再請求。也即一個進程已獲得的資源在運行過程中可被剝奪。從而破壞了該條件。但這種方法實現(xiàn)較復(fù)雜，會增加系統(tǒng)開鎖，降低系從而破壞了該條件。但這種方法實現(xiàn)較復(fù)雜，會增加系統(tǒng)開鎖，降低系統(tǒng)吞吐量。統(tǒng)吞吐量。（4）破壞環(huán)路條件：）破壞環(huán)路條件：可采用可采用有序資源分配方法有序資源分配方法，即將系統(tǒng)中的所有資，即將系統(tǒng)中的所有資源都按類型賦予一個編號，要求每一個進程均嚴格按照編號遞增的次序源都按類型賦予一個編號，要求每一個進程均嚴格按照編號遞增的次序來請求資源，同類資源一次申請完。也就是，只要進程提出請求資源來

60、請求資源，同類資源一次申請完。也就是，只要進程提出請求資源Ri，則在以后的請求中，只能請求則在以后的請求中，只能請求Ri后的資源，這樣不會出現(xiàn)幾個進程請求后的資源，這樣不會出現(xiàn)幾個進程請求資源而形成環(huán)路。該方法雖提高了資源的利用率，但編號難，加重進程資源而形成環(huán)路。該方法雖提高了資源的利用率，但編號難，加重進程負擔(dān)及因使用資源順序與申請順序不同而造成資源浪費。負擔(dān)及因使用資源順序與申請順序不同而造成資源浪費。3.6 3.6 死鎖的預(yù)防和避免方法死鎖的預(yù)防和避免方法u死鎖的避免死鎖的避免 在死鎖預(yù)防的幾種方法中，都施加了較強的限制條件，在死鎖預(yù)防的幾種方法中，都施加了較強的限制條件，嚴重降低了系