1、操作系統操作系統Operating Systems3.4 實時調度實時調度 實現實時調度的基本條件實現實時調度的基本條件1.1.必要信息必要信息就緒時間、開始截至時間、完成截至時間、處理時間；就緒時間、開始截至時間、完成截至時間、處理時間；資源要求；優先級；資源要求；優先級； 2.2.系統處理能力強系統處理能力強3.3.采用搶占式機制采用搶占式機制-硬實時任務；截止時間要求；硬實時任務；截止時間要求；4.4.有快速切換機制有快速切換機制-快速響應外部中斷；快速任務分派；快速響應外部中斷；快速任務分派；11miiiPCNPCmiii1處理時間處理時間: : C Ci i; ;周期時間周期時間:

2、: P Pi i系統處理能力系統處理能力例：例：A任務周期為任務周期為10ms，執行，執行5ms； B任務周期為任務周期為15ms, 執行執行10ms (5/10)+(10/15)=35/30，系統處理不了系統處理不了A1B1A2B2任務執行任務執行t任務到達任務到達A1B1A2B2A3051015202530A4B3(A3錯過錯過)討論討論一個實時系統有四個周期性事件，周期分別為一個實時系統有四個周期性事件，周期分別為50、100、300和和250ms。若假設其處理時間分別需要。若假設其處理時間分別需要35、20、10和和x ms，則該系統可調度允許的，則該系統可調度允許的x值最大為多少？值

3、最大為多少？答：答：在單處理機情況下：在單處理機情況下： （35/50+20/100+10/200+x/250） 1 x 16.75ms 11miiiPC實時調度算法的分類實時調度算法的分類非搶占式非搶占式輪轉調度輪轉調度( (同質任務同質任務) )；優先調度優先調度 為時間要求嚴格的任務分配較高優先級為時間要求嚴格的任務分配較高優先級搶占式搶占式時鐘中斷優先；時鐘中斷優先；立即搶占優先立即搶占優先非搶占式輪轉調度算法非搶占式輪轉調度算法輪轉調度輪轉調度( (同質任務同質任務) )；l常用于工業生產的群控系統中常用于工業生產的群控系統中非搶占式優先調度算法非搶占式優先調度算法優先調度優先調度為

4、時間要求嚴格的任務分配較高優先級為時間要求嚴格的任務分配較高優先級 基于時鐘中斷的搶占式優先權調度算法基于時鐘中斷的搶占式優先權調度算法 某實時任務到達后，若優先級高于當前正在執行任務的優某實時任務到達后，若優先級高于當前正在執行任務的優先級，并先級，并不立即搶占不立即搶占當前任務的處理機，而是當前任務的處理機，而是等到時鐘中等到時鐘中斷到來斷到來后調度程序才剝奪當前任務的執行后調度程序才剝奪當前任務的執行立即搶占的優先權調度算法立即搶占的優先權調度算法 一旦有外部中斷，一旦有外部中斷，只要當前任務不在臨界區內只要當前任務不在臨界區內，便，便立即剝立即剝奪奪當前任務的執行，交處理機分配給要求中

5、斷的緊迫任務當前任務的執行，交處理機分配給要求中斷的緊迫任務常用的幾種實時調度算法常用的幾種實時調度算法最早截止時間優先算法最早截止時間優先算法非搶占式和搶占式非搶占式和搶占式EDFEDF算法用于非搶占調度的調度方式算法用于非搶占調度的調度方式 非搶占式調度方式用于非周期實時任務非搶占式調度方式用于非周期實時任務342開始截止時間開始截止時間任務到達任務到達12 3442任務執行任務執行t131通常的優先級調度不能適用于實時系統通常的優先級調度不能適用于實時系統A1B1A2B1A3任務任務執行執行t任務任務到達到達A1B1A2B2A3最后期限最后期限任務任務A A的周期時間為的周期時間為20

6、ms20 ms，每個周期的處理時間為，每個周期的處理時間為10 ms10 ms；任務任務B B的周期時間為的周期時間為50 ms50 ms，每個周期的處理時間為，每個周期的處理時間為25 ms25 ms固定優先級調度固定優先級調度 （A A有較高優先級）有較高優先級）A1A2A30102030405060100708090A4A5A6B3A4B2A5(B1錯過錯過)B1通常的優先級調度不能適用于實時系統通常的優先級調度不能適用于實時系統B1任務任務執行執行t任務任務到達到達A1B1A2B2A3最后期限最后期限任務任務A A的周期時間為的周期時間為20 ms20 ms，每個周期的處理時間為，每個

7、周期的處理時間為10 ms10 ms；任務任務B B的周期時間為的周期時間為50 ms50 ms，每個周期的處理時間為，每個周期的處理時間為25 ms25 ms固定優先級調度固定優先級調度 （B B有較高優先級）有較高優先級）A1A2A30102030405060100708090A4A5A6B3A4B2A5(A1錯過錯過)B1EDFEDF算法用于搶占調度方式算法用于搶占調度方式A1B1A2B1A3任務任務執行執行t任務任務到達到達A1B1A2B2A3最后期限最后期限任務任務A A的周期時間為的周期時間為20 ms20 ms，每個周期的處理時間為，每個周期的處理時間為10 ms10 ms；任務

8、任務B B的周期時間為的周期時間為50 ms50 ms，每個周期的處理時間為，每個周期的處理時間為25 ms25 msA1A2A30102030405060100708090A4A5A6B3A4B2A5B2A4B2A5B1最低松弛度優先（最低松弛度優先（ LLF LLF ）算法）算法松弛度松弛度= =必須完成時間必須完成時間- -本身運行時間本身運行時間- -當前時間當前時間 設有兩個周期性實時任務設有兩個周期性實時任務A A和和B B，分別每，分別每20ms,50ms20ms,50ms執行一執行一次，每次執行次，每次執行10ms,25ms10ms,25ms。則其須完成的時間為：。則其須完成的

9、時間為：A1,A2,A1,A2,和和B1,B2,B1,B2,，A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0利用利用LLFLLF算法進行調度的情況算法進行調度的情況t t1=01=0時，時，A1A1的松弛度的松弛度=20-10-0=10ms=20-10-0=10ms； B1B1的松弛度的松弛度=50-25-0=25ms;=50-25-0=25ms;A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0松弛度松弛度= =必須完成時間必須完成時間- -其本身的運行時間其本身的運行時間- -當前時間當前時間利用利用LLF算法

10、進行調度的情況算法進行調度的情況t8B2(10)松弛度松弛度= =必須完成時間必須完成時間- -其本身的運行時間其本身的運行時間- -當前時間當前時間vt2=10t2=10，A1A1結束，結束，A2A2未到達未到達 vB1B1運行運行松弛度松弛度= =必須完成時間必須完成時間- -其本身的運行時間其本身的運行時間- -當前時間當前時間vt3=30t3=30，A2A2的松弛度的松弛度=40ms-10ms-30ms=0ms=40ms-10ms-30ms=0ms B1 B1的松弛度的松弛度=50ms-5ms-30ms=15ms=50ms-5ms-30ms=15msvA2A2搶占運行搶占運行松弛度松弛

11、度= =必須完成時間必須完成時間- -其本身的運行時間其本身的運行時間- -當前時間當前時間vt4=40t4=40，A3A3的松弛度的松弛度=60ms-10ms-40ms=10ms=60ms-10ms-40ms=10ms B1 B1的松弛度的松弛度=50ms-5ms-40ms=5ms=50ms-5ms-40ms=5msvB1B1運行運行松弛度松弛度= =必須完成時間必須完成時間- -其本身的運行時間其本身的運行時間- -當前時間當前時間vt5=45t5=45，A3A3的松弛度的松弛度=60ms-10ms-45ms=5ms=60ms-10ms-45ms=5ms B2 B2未到達未到達vA3A3運

12、行運行松弛度松弛度= =必須完成時間必須完成時間- -其本身的運行時間其本身的運行時間- -當前時間當前時間vt6=55t6=55，A3A3結束，結束，A4A4未到達未到達 vB2B2運行運行松弛度松弛度= =必須完成時間必須完成時間- -其本身的運行時間其本身的運行時間- -當前時間當前時間vt7=70t7=70，A4A4的松弛度的松弛度=80ms-10ms-70ms=0ms=80ms-10ms-70ms=0ms B2 B2的松弛度的松弛度=100ms-10ms-70ms=10ms=100ms-10ms-70ms=10msvA4A4運行運行松弛度松弛度= =必須完成時間必須完成時間- -其本

13、身的運行時間其本身的運行時間- -當前時間當前時間vt8=80t8=80，A5A5的松弛度的松弛度=100ms-10ms-80ms=10ms=100ms-10ms-80ms=10ms B2 B2的松弛度的松弛度=100ms-10ms-80ms=10ms=100ms-10ms-80ms=10msvB2B2運行（同樣松弛度應先來先服務）運行（同樣松弛度應先來先服務）A1B1A2B2A3A4A5任務到達任務到達最后期限最后期限A1A2A3A4B120304050607010803.5 產生死鎖的原因和必要條件產生死鎖的原因和必要條件死鎖死鎖l在多進程在運行過程中因爭奪資源而造成的一種僵局，當進程處在

14、多進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種僵局狀態時，若無外力作用，它們都將無法再向前推進。于這種僵局狀態時，若無外力作用，它們都將無法再向前推進。產生死鎖的原因產生死鎖的原因 競爭資源競爭資源l當系統中供多個進程共享的資源，其當系統中供多個進程共享的資源，其數目不足數目不足以滿足以滿足諸進程的需要時，會引起諸進程對資源的競爭而產生諸進程的需要時，會引起諸進程對資源的競爭而產生死鎖。死鎖。 進程間推進順序非法。進程間推進順序非法。l進程在運行過程中，請求和釋放資源的順序不當，也進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致產生進程死鎖。同樣會導致產生進程死鎖。 產生

15、死鎖的原因產生死鎖的原因 3個進程共享個進程共享4個同種類型的資源，每個進程最大需要個同種類型的資源，每個進程最大需要2個個資源，請問該系統是否會因為競爭資源而死鎖？資源，請問該系統是否會因為競爭資源而死鎖？ R R系統有同類資源系統有同類資源m個，被個，被n個進程共享，當個進程共享，當mn 和和mn時，每時，每個進程最多可以請求多少個這類資源時，系統一定不會發生個進程最多可以請求多少個這類資源時，系統一定不會發生死鎖？死鎖？當當m n 時時:l每個進程最多申請每個進程最多申請1個這類資源時，系統一定不會發生死鎖個這類資源時，系統一定不會發生死鎖當當mn時時:假設每個進程最多申請假設每個進程最

16、多申請x個這類資源個這類資源l若每個進程申請若每個進程申請x-1個這類資源后，系統還剩下一個資源，個這類資源后，系統還剩下一個資源，就能保證某一個進程能分配到全部就能保證某一個進程能分配到全部x個資源，并能運行到底個資源，并能運行到底，最終釋放這，最終釋放這x個資源。即：個資源。即： n*（x -1） m x(m/n)+1競爭資源引起進程死鎖競爭資源引起進程死鎖 系統中的資源分成兩類系統中的資源分成兩類l可搶占性資源。可搶占性資源。如：如：CPU和主存和主存對于這類資源是不會引起死鎖的對于這類資源是不會引起死鎖的l不可搶占性資源。不可搶占性資源。 如：磁帶機、打印機如：磁帶機、打印機在系統中所

17、配置的不可搶占性資源，由于它們的數量不能在系統中所配置的不可搶占性資源，由于它們的數量不能滿足諸進程運行的需要，會因爭奪這些資源而陷入僵局。滿足諸進程運行的需要，會因爭奪這些資源而陷入僵局。競爭不可搶占性資源競爭不可搶占性資源R1R1R2R2m3m3競爭可消耗資源競爭可消耗資源可消耗資源（可消耗資源（臨時性資源）臨時性資源）l由一個進程產生，被另一進程使用一短暫時間后便無用的資由一個進程產生，被另一進程使用一短暫時間后便無用的資源，故也稱之為消耗性資源源，故也稱之為消耗性資源P1： send(p2,m1)； Receive(p3,m3)； P2： send(p3,m2)； Receive(p1

18、,m1)； P3： send(p1,m3)； Receive(p2,m2)； m2m2m1m1競爭可消耗資源競爭可消耗資源引起進程死鎖引起進程死鎖P1： Receive(p3,m3)；send(p2,m1)P2： Receive(p1,m1)；send(p3,m2)P3： Receive(p2,m2)；send(p1,m3)2. 進程推進順序不當引起死鎖進程推進順序不當引起死鎖 例例: 進程推進順序不當產生死鎖進程推進順序不當產生死鎖設系統有打印機、讀卡機各一臺，被進程設系統有打印機、讀卡機各一臺，被進程1和和P2共享。共享。兩個進程并發執行，按下列次序請求和釋放資源：兩個進程并發執行，按下列

19、次序請求和釋放資源： 進程進程1 進程進程P2 請求讀卡機請求讀卡機 請求打印機請求打印機 請求打印機請求打印機 請求讀卡機請求讀卡機 釋放讀卡機釋放讀卡機 釋放讀卡機釋放讀卡機 釋放打印機釋放打印機 釋放打印機釋放打印機 進程推進順序進程推進順序進程進程1 進程進程P2 請求讀卡機請求讀卡機 請求讀卡機請求讀卡機 請求打印機請求打印機 請求打印機請求打印機 釋放讀卡機釋放讀卡機 釋放讀卡機釋放讀卡機 釋放打印機釋放打印機 釋放打印機釋放打印機 死鎖的基本概念死鎖的基本概念這兩個進程在并發執行過程中，可能會發生死鎖。這兩個進程在并發執行過程中，可能會發生死鎖。大家可以思考一下，如何修改，進程才

20、不會發生大家可以思考一下，如何修改，進程才不會發生死鎖？死鎖？死鎖的基本概念死鎖的基本概念關于死鎖的一些結論關于死鎖的一些結論l參與死鎖的進程參與死鎖的進程最少是兩個最少是兩個l參與死鎖的進程參與死鎖的進程至少有兩個已經占有資源至少有兩個已經占有資源l參與死鎖的所有進程參與死鎖的所有進程都在等待資源都在等待資源l參與死鎖的進程是當前系統中所有參與死鎖的進程是當前系統中所有進程的子集進程的子集注：注：如果死鎖發生，會浪費大量系統資源，甚至導致系統崩如果死鎖發生，會浪費大量系統資源，甚至導致系統崩潰。潰。3.5.33.5.3產生死鎖的必要條件產生死鎖的必要條件互斥條件：互斥條件：l進程互斥使用資源

21、進程互斥使用資源請求和保持條件請求和保持條件：部分分配條件：部分分配條件l申請新資源時不釋放已占有資源申請新資源時不釋放已占有資源不可搶占條件：不可搶占條件：l一個進程不能搶奪其他進程占有的資源一個進程不能搶奪其他進程占有的資源環路條件：環路條件：l存在一組進程循環等待資源存在一組進程循環等待資源S1S1S3S3S2S2處理死鎖的方法處理死鎖的方法預防死鎖。預防死鎖。l破壞產生死鎖的四個必要條件中的一個或幾個條件破壞產生死鎖的四個必要條件中的一個或幾個條件 避免死鎖。避免死鎖。l在資源的動態分配過程中，用某種方法去防止系統進入在資源的動態分配過程中，用某種方法去防止系統進入不安全狀態，從而避免

22、發生死鎖。不安全狀態，從而避免發生死鎖。 檢測死鎖。檢測死鎖。l通過系統所設置的檢測機構，及時地檢測出死鎖的發生通過系統所設置的檢測機構，及時地檢測出死鎖的發生；采取適當措施，從系統中將已發生的死鎖清除掉。；采取適當措施，從系統中將已發生的死鎖清除掉。 解除死鎖。這是與檢測死鎖相配套的一種措施解除死鎖。這是與檢測死鎖相配套的一種措施3.6預防死鎖預防死鎖一種較簡單和直觀的事先預防的方法。一種較簡單和直觀的事先預防的方法。l設置某些限制條件，去破壞產生死鎖的四個必要條件設置某些限制條件，去破壞產生死鎖的四個必要條件中的一個或幾個條件，來預防發生死鎖：中的一個或幾個條件，來預防發生死鎖：互斥條件互

23、斥條件請求和保持條件請求和保持條件不可搶占條件不可搶占條件環路條件環路條件1. 1. 破壞破壞“請求和保持請求和保持”條件條件破壞破壞“請求和保持請求和保持”條件條件l一個進程必須在一個進程必須在執行前執行前就就申請申請它所要的它所要的全部資源全部資源，l直到它所要的資源都得到滿足后才開始執行。直到它所要的資源都得到滿足后才開始執行。優點優點l簡單、易于實現且很安全。簡單、易于實現且很安全。缺點缺點l資源被嚴重浪費，嚴重地惡化了系統資源的利用率；資源被嚴重浪費，嚴重地惡化了系統資源的利用率；l使進程延遲運行，僅當進程在獲得了其所需的全部資使進程延遲運行，僅當進程在獲得了其所需的全部資源后，才能

24、開始運行。源后，才能開始運行。2.2.破壞破壞“不可搶占不可搶占”條件條件破壞破壞“不可搶占不可搶占”條件條件l當進程有新的資源請求時，如果得不到滿足，要先釋當進程有新的資源請求時，如果得不到滿足，要先釋放原先占有的資源，待以后重新申請。放原先占有的資源，待以后重新申請。l等價于等價于“被搶占被搶占”。該方法實現起來比較復雜，要付出很大的代價。該方法實現起來比較復雜，要付出很大的代價。l反復地申請和釋放資源反復地申請和釋放資源l進程的執行被無限地推遲進程的執行被無限地推遲只適用于對主存資源和處理器資源的分配只適用于對主存資源和處理器資源的分配3.3.破壞破壞“環路等待環路等待”條件條件破壞破壞

25、“環路等待環路等待”條件條件l把系統資源按類型排序，進程要按照資源的序號遞增把系統資源按類型排序，進程要按照資源的序號遞增的次序提出資源申請。的次序提出資源申請。優點優點l資源利用率和系統吞吐量都有較明顯的改善。資源利用率和系統吞吐量都有較明顯的改善。存在下述嚴重問題：存在下述嚴重問題：l限制了新類型設備的增加。限制了新類型設備的增加。l造成對資源的浪費。造成對資源的浪費。l必然會限制用戶簡單、自主地編程。必然會限制用戶簡單、自主地編程。 討論討論在哲學家就餐問題中，奇數號先取左手邊的筷子，偶數號先取在哲學家就餐問題中，奇數號先取左手邊的筷子，偶數號先取右手邊的筷子。請說明為何不會產生死鎖。右

26、手邊的筷子。請說明為何不會產生死鎖。3.73.7避免死鎖避免死鎖1. 1. 安全狀態安全狀態l指系統能按某種指系統能按某種進程順序進程順序(P(P1 1，P P2 2，P Pn n) )，來為每個進，來為每個進程程P Pi i分配其所需資源，直至滿足每個進程對資源的分配其所需資源，直至滿足每個進程對資源的最大最大需求需求，使每個進程都可順利地完成。，使每個進程都可順利地完成。l如果系統無法找到這樣一個安全序列，則稱系統處于不如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。安全狀態。當系統進入不安全狀態后，便有當系統進入不安全狀態后，便有可能可能進而進入死鎖狀態。進而進入死鎖狀態。避免

27、死鎖避免死鎖的實質在于：的實質在于：l系統在進行資源分配時，如何使系統不進入不安全狀態系統在進行資源分配時，如何使系統不進入不安全狀態2 2安全狀態之例安全狀態之例假定系統中有三個進程假定系統中有三個進程P1、P2和和P3，共有，共有12臺磁帶機。臺磁帶機。T0時刻是安全的？時刻是安全的？+2-2=12安全狀態之例安全狀態之例假定系統中有三個進程假定系統中有三個進程P1、P2和和P3，共有，共有12臺磁帶機。臺磁帶機。+5-5=02安全狀態之例安全狀態之例假定系統中有三個進程假定系統中有三個進程P1、P2和和P3，共有，共有12臺磁帶機。臺磁帶機。安全序列：安全序列：P2 、P1、P3T0時刻

28、是安全的。時刻是安全的。+7-7=33由安全狀態向不安全狀態的轉換由安全狀態向不安全狀態的轉換如果不按照安全序列分配資源，則系統可能會由安全狀態如果不按照安全序列分配資源，則系統可能會由安全狀態進入不安全狀態。進入不安全狀態。+1-1=23由安全狀態向不安全狀態的轉換由安全狀態向不安全狀態的轉換如果不按照安全序列分配資源，則系統可能會由安全狀態如果不按照安全序列分配資源，則系統可能會由安全狀態進入不安全狀態。進入不安全狀態。+2-2=03由安全狀態向不安全狀態的轉換由安全狀態向不安全狀態的轉換如果不按照安全序列分配資源，則系統可能會由安全狀態如果不按照安全序列分配資源，則系統可能會由安全狀態進

29、入不安全狀態。進入不安全狀態。3由安全狀態向不安全狀態的轉換由安全狀態向不安全狀態的轉換如果不按照安全序列分配資源，則系統可能會由安全狀態如果不按照安全序列分配資源，則系統可能會由安全狀態進入不安全狀態。進入不安全狀態。從給從給P3分配了第分配了第3臺磁帶機開始，系統便又進入了不安全臺磁帶機開始，系統便又進入了不安全狀態。狀態。3.7.23.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖1 1銀行家算法中的數據結構銀行家算法中的數據結構(1) (1) 可利用資源向量可利用資源向量Available Available l每類資源未分配數量向量每類資源未分配數量向量l含有含有m個元素的數組個

30、元素的數組l如果如果Availablej=KAvailablej=K，則表示系統中現有，則表示系統中現有R Rj j類資源類資源K K個。個。銀行家算法中的數據結構銀行家算法中的數據結構(2) (2) 最大需求矩陣最大需求矩陣MaxMax。一個一個n nm m的矩陣，它定義了系統中的矩陣，它定義了系統中n n個進程中的每一個進程個進程中的每一個進程對對m m類資源的最大需求。如果類資源的最大需求。如果Maxi,j=KMaxi,j=K，則表示進程，則表示進程i i需要需要R Rj j類資源的最大數目為類資源的最大數目為K。Max=Max=M M1111M M1212M M1m1mM M2121M

31、 M2121M M2121M Mn1n1M Mn1n1M Mnmnm銀行家算法中的數據結構銀行家算法中的數據結構(3) 分配矩陣分配矩陣Allocation。也是一個也是一個nm的矩陣，它定義了系統中每一類資源當前已的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。分配給每一進程的資源數。如果如果Allocationi,j=KAllocationi,j=K，則表示進程，則表示進程i i當前已分得當前已分得R j類資源類資源的數目為的數目為K。Allocation=Allocation=A A1111A A1212A A1m1mA A2121A A2121A A2121A An1n1

32、A An1n1A Anmnm銀行家算法中的數據結構銀行家算法中的數據結構(4) 需求矩陣需求矩陣Need。一個一個nm的矩陣，用以表示每一個進程尚需的各類資源的矩陣，用以表示每一個進程尚需的各類資源數。數。如果如果Needi,j=KNeedi,j=K，則表示進程，則表示進程i還需要還需要Rj類資源類資源K個，方個，方能完成其任務。能完成其任務。上述三個矩陣間存在下述關系：上述三個矩陣間存在下述關系：Needi, j=Maxi, j- Allocationi, j Needi, j=Maxi, j- Allocationi, j 2 2銀行家算法銀行家算法(1)(1)設設RequestReque

33、sti ij=Kj=K，表示，表示P Pi i需要需要K K個個R Rj j類資源。類資源。P Pi i發出資源請求發出資源請求RequestRequesti i后，系統按下述步驟進行檢查：后，系統按下述步驟進行檢查：(1)(1)如果如果RequestRequesti ijNeedi,jjNeedi,j，轉向步驟，轉向步驟(2)(2)； 否則認為出錯，因為它所需要的資源數已超過它所宣布的否則認為出錯，因為它所需要的資源數已超過它所宣布的 最大值。最大值。(2)(2)如果如果RequestRequesti ijAvailablejjAvailablej，轉向步驟，轉向步驟(3)(3)； 否則，表

34、示尚無足夠資源，否則，表示尚無足夠資源，P Pi i須等待。須等待。 2 2銀行家算法銀行家算法(2)(2)(3)(3)系統系統試探試探把把資源分配資源分配給進程給進程P Pi i，并，并修改數據結構中的值修改數據結構中的值：Availablej:= Availablej - RequestAvailablej:= Availablej - Requesti ijj；Allocationi,j:= Allocationi,j + RequestAllocationi,j:= Allocationi,j + Requesti ijj；Needi,j:= Needi,j - RequestNeed

35、i,j:= Needi,j - Requesti ijj；(4)(4)執行安全性算法執行安全性算法，檢查此次資源分配后系統是否處于，檢查此次資源分配后系統是否處于安全安全狀態狀態。l若安全，將資源若安全，將資源正式分配正式分配給進程給進程P Pi i；l否則，將本次的否則，將本次的試探分配作廢，恢復原來的資源分配狀試探分配作廢，恢復原來的資源分配狀態，讓進程態，讓進程P Pi i等待等待。3.3.安全性算法安全性算法(1)(1)(1)(1)設置兩向量：設置兩向量：可供進程繼續運行可供進程繼續運行所需各類資源數所需各類資源數的的WorkWork 初始時初始時 Work:=AvailableWor

36、k:=Available。表示資源是否足夠的表示資源是否足夠的FinishFinish， 初始時令初始時令Finishi:=falseFinishi:=false； 資源足夠時再令資源足夠時再令Finishi:=trueFinishi:=true。Workj=KWorkj=K3.3.安全性算法安全性算法(2)(2)(2)(2)尋找一個能滿足下述條件的進程：尋找一個能滿足下述條件的進程： Finishi=falseFinishi=false； Needi,jWorkj;Needi,jWorkj;找到執行步驟找到執行步驟(3)(3)，否則執行步驟，否則執行步驟(4)(4)。(3)(3)進程進程P

37、Pi i獲得資源，執行完成后釋放它的資源，故應執行：獲得資源，執行完成后釋放它的資源，故應執行：Workj:= Workj+Allocationi,jWorkj:= Workj+Allocationi,j；Finishi:=trueFinishi:=true；go to step 2go to step 2； (4)(4)如果所有進程的如果所有進程的Finishi=trueFinishi=true都滿足都滿足，則表示系統處于，則表示系統處于安全狀態安全狀態；否則，系統處于；否則，系統處于不安全狀態不安全狀態。 實例說明系統所處的安全或不安全狀態實例說明系統所處的安全或不安全狀態假定系統中有五個

38、進程假定系統中有五個進程P0，P1，P2，P3，P4三類資源三類資源A，B，C 。 lA類資源共有類資源共有10個個lB類資源共有類資源共有5個個lC類資源共有類資源共有7個。個。（1）在時刻）在時刻T0,系統目前資源分配情況如下：系統目前資源分配情況如下：每個進程目前還需資源為每個進程目前還需資源為Need 進程進程 Max Allocation Available A B C A B C A B C P0 7 5 3 0 1 0 3 3 2 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2NeedA B C 7 4 31

39、 2 26 0 00 1 1 4 3 1 進程進程 Work Need Allocation Work=Work+allocation A B C A B C A B C A B C5 3 23 3 21 2 2 2 0 05 3 20 1 1 2 1 17 4 37 4 3P1P3P4P2P04 3 1 0 0 27 4 57 4 56 0 0 3 0 210 4 710 4 74 3 0 0 1 0 10 5 7Need A B C P0 7 4 3 P1 1 2 2 A B C P2 6 0 0P3 0 1 1 A B C P4 4 3 1可以斷言可以斷言T0時刻，系統處于安全狀態時刻，

40、系統處于安全狀態l因為序列因為序列P1,P3,P4,P2,P0能滿足安全性條件。能滿足安全性條件。（2）進程）進程P1申請資源申請資源request1=(1,0,2) ，系統能將資源分，系統能將資源分配給它嗎？配給它嗎？NeedA B C7 4 36 0 00 1 14 3 1 進程進程 Max Allocation Available A B C A B C A B C P0 7 5 3 0 1 0 P1 3 2 2 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2檢查檢查: request1(1,0,2) Need1(1,2,2) and reque

41、st1(1,0,2) Available(3,3,2) 結果滿足條件，試分配。結果滿足條件，試分配。3 0 2 0 2 02 3 0得到新狀態：得到新狀態： 2 0 03 3 21 2 2判定新狀態是否安全判定新狀態是否安全?找到一個進程序列找到一個進程序列 可保證進程可保證進程P1運行完畢并歸還資源運行完畢并歸還資源進程進程 Work Need Allocation work+allocation A B C A B C A B C A B C5 3 22 3 00 2 0 3 0 25 3 20 1 1 2 1 17 4 37 4 3P1P3P4P0P24 3 1 0 0 27 4 57

42、4 57 4 3 0 1 07 5 57 5 56 0 0 3 0 2 10 5 7 A B CP0 7 4 3P1 0 2 0P2 6 0 0P3 0 1 1P4 4 3 1 Need（3）進程）進程P4申請資源申請資源request4=(3,3,0) 檢查檢查: request4(3,3,0) Need4(4,3,1) and request4 (3,3,0) Available(2,3,0) 讓讓P4等待等待NeedA B C7 4 30 2 06 0 00 1 14 3 1 進程進程 Max Allocation Available A B C A B C A B C P0 7 5 3

43、 0 1 0 2 3 0 P1 3 2 2 3 0 2 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2（4） P0請求資源請求資源 request0=(0,2,0);檢查檢查: request0 (0,2,0) Need0(7,4,3) and request0 (0,2,0) Available(2,3,0) 結果滿足條件，試分配。結果滿足條件，試分配。0 3 0 7 2 32 1 0得到新狀態：得到新狀態：NeedA B C7 4 30 2 06 0 00 1 14 3 1 進程進程 Max Allocation Available A B C A

44、 B C A B C P0 7 5 3 0 1 0 2 3 0 P1 3 2 2 3 0 2 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2系統已處于不安系統已處于不安全狀態了。全狀態了。死鎖避免死鎖避免在使用中有許多限制在使用中有許多限制l必須事先聲明每個進程請求的最大資源必須事先聲明每個進程請求的最大資源l進程數不能變化進程數不能變化l所討論的進程必須是無關的所討論的進程必須是無關的它們的執行順序必須沒有任何同步要求的限制它們的執行順序必須沒有任何同步要求的限制l分配的資源數目必須是固定的分配的資源數目必須是固定的3.8死鎖的檢測與解除死鎖的檢測與

45、解除 3.8.13.8.1死鎖的檢測死鎖的檢測當系統為進程分配資源時，若未采取任何限制性措施，則當系統為進程分配資源時，若未采取任何限制性措施，則系統必須提供檢測和解除死鎖的手段系統必須提供檢測和解除死鎖的手段系統必須做到：系統必須做到： 保存有關資源的請求和分配信息；保存有關資源的請求和分配信息； 提供一種算法，以利用這些信息來檢測系統是否已進入死提供一種算法，以利用這些信息來檢測系統是否已進入死鎖狀態。鎖狀態。 1 1資源分配圖資源分配圖約定約定PiRj為請求邊，表示進程為請求邊，表示進程Pi申請資源類申請資源類Rj中的一個資源中的一個資源得不到滿足而處于等待得不到滿足而處于等待Rj類資源

46、的狀態，該有向邊從進程開始類資源的狀態，該有向邊從進程開始指到方框的邊緣，表示進程指到方框的邊緣，表示進程Pi申請申請Rj類中的一個資源。類中的一個資源。RjPi為分配邊，表示為分配邊，表示Rj類中的一個資源已被進程類中的一個資源已被進程Pi占用，由占用，由于已把一個具體的資源分給了進程于已把一個具體的資源分給了進程Pi，故該有向邊從方框內的，故該有向邊從方框內的某個黑圓點出發指向進程。某個黑圓點出發指向進程。 R Rj jP Pi i2 2死鎖定理死鎖定理可以利用把可以利用把資源分配圖資源分配圖加以簡化的方法，來檢測當系統處于加以簡化的方法，來檢測當系統處于S S狀態時是否為死鎖狀態。狀態時

47、是否為死鎖狀態。l如果能在進程如果能在進程-資源分配圖中消去此進程的所有請求邊和資源分配圖中消去此進程的所有請求邊和分配邊，成為孤立結點。分配邊，成為孤立結點。l如果經一系列簡化，使所有進程成為孤立結點，則該圖是如果經一系列簡化，使所有進程成為孤立結點，則該圖是可完全簡化的可完全簡化的；否則則稱該圖是不可完全簡化的。；否則則稱該圖是不可完全簡化的。S為死鎖狀態的為死鎖狀態的充分條件充分條件是：是：l當且僅當當且僅當S狀態的資源分配圖是不可完全簡化的。狀態的資源分配圖是不可完全簡化的。該充分條件被稱為該充分條件被稱為死鎖定理死鎖定理。資源分配圖的資源分配圖的簡化簡化R1R1R2R2資源分配圖的一

48、個例子資源分配圖的一個例子 R1 R1 R2 R2P1P1P2P2P3P3R3R33.8.23.8.2死鎖的解除死鎖的解除 搶占資源。搶占資源。l從其它進程搶占足夠數量的資源給死鎖進程，以解除從其它進程搶占足夠數量的資源給死鎖進程，以解除死鎖狀態。死鎖狀態。(2) (2) 撤消進程。撤消進程。l最簡單的方法是：使全部死鎖進程都夭折掉；最簡單的方法是：使全部死鎖進程都夭折掉；l稍微溫和一點的方法是：稍微溫和一點的方法是：按照某種順序逐個地撤消進程，直至有足夠的資源按照某種順序逐個地撤消進程，直至有足夠的資源可用，使死鎖狀態消除為止。可用，使死鎖狀態消除為止。一、選擇題一、選擇題(1)產生死鎖的基本原因是產生死鎖的基本原因是_和和_，產生死鎖的，產生死鎖的四個必要條件是互斥條件，四個必要條件是互斥條件，_，不可搶占條件和，不可搶占條件和_。A.資源分配不當資源分配不當B.競爭資源競爭資源 C.作業調度不當作業調度不當D.資源的獨占性資源的獨占性A.進程推進順序不當進程推進順序不當B.進程調度不當進程調度不當 C.系統中進程太多系統中進程太多D.CPU運行不快運行不快A.請求和阻塞條件請求和阻塞條件B.請求和釋放條件請求和釋放條件 C.請求和保持條件請求和保持條件D.釋放和阻塞條件釋放和阻塞條件A.線性增長條件線性增長條件B.環路等待條件環路等待條件