操作系統(tǒng)課件第三章3講述

1、第三章 處理機調(diào)度與死鎖 第三章第三章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 3.1 3.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念 3.2 3.2 調(diào)度算法調(diào)度算法 3.3 3.3 實時調(diào)度實時調(diào)度 3.4 3.4 多處理機系統(tǒng)中的調(diào)度多處理機系統(tǒng)中的調(diào)度 3.5 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 3.6 3.6 預防死鎖的方法預防死鎖的方法 3.7 3.7 死鎖的檢測與解除死鎖的檢測與解除 第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課一、選擇題(1)在三種基本類型的操作系統(tǒng)中，都設置了_，在批處理系統(tǒng)中還應設置_，在分時系統(tǒng)中除了_，通常還設置了_。A.剝奪調(diào)度

2、B.作業(yè)調(diào)度C.進程調(diào)度D.中級調(diào)度CBCD第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課一、選擇題(2)我們?nèi)绻麨槊恳粋€作業(yè)只建立一個進程，則為了照顧短作業(yè)用戶，應采用_；為照顧緊急作業(yè)的用戶，應采用_；為能實現(xiàn)人機交互作用采用_；而能使短作業(yè)、長作業(yè)及交互作業(yè)用戶都比較滿意時，應采用_。A.FCFS調(diào)度算法B.短作業(yè)優(yōu)先調(diào)度算法C.時間片輪轉法D.多級反饋隊列調(diào)度算法E.基于優(yōu)先權調(diào)度算法BECD第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課一、選擇題(3)產(chǎn)生死鎖的基本原因是_和_，產(chǎn)生死鎖的四個必要條件是互斥條件，_，不剝奪條件和_。A.資源分配不當B.競爭資源 C.作業(yè)調(diào)度不

3、當D.資源的獨占性A.進程推進順序不當B.進程調(diào)度不當 C.系統(tǒng)中進程太多D.CPU運行不快A.請求和阻塞條件B.請求和釋放條件 C.請求和保持條件D.釋放和阻塞條件A.線性增長條件B.環(huán)路等待條件 C.無序釋放條件D.有序請求條件BACB第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課一、選擇題(4)實際操作系統(tǒng)，要兼顧資源的使用效率和安全可靠，對資源的分配策略，往往采用_策略。A.預防死鎖B.避免死鎖C.檢測死鎖D.三者的混合(5)在下列死鎖的解決辦法中，屬于預防死鎖策略的是_。A.銀行家算法B.資源有序分配法C.死鎖檢測法D.資源分配圖化簡法DB第三章 處理機調(diào)度與死鎖 第三章第三章習

4、題課習題課二、填空題(1)資源的一次分配法和有序分配法分別破壞了產(chǎn)生死鎖的必要條件中的_和_，它們屬于_，而銀行家算法屬于_。(2)作業(yè)調(diào)度是從_中選出一_作業(yè)，為它們分配_，并為它們創(chuàng)建_。請求和保持條件環(huán)路等待條件預防死鎖避免死鎖后備作業(yè)隊列批資源進程第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課二、填空題(3)最有利于提高系統(tǒng)吞吐量的作業(yè)調(diào)度算法是_；能對緊急作業(yè)進行及時處理的調(diào)度算法是_；能較好的滿足短作業(yè)用戶要求，又能適當?shù)恼疹欓L作業(yè)，以及照顧作業(yè)到達次序的調(diào)度算法是_。(4)在高響應比優(yōu)先的調(diào)度算法中，當各個作業(yè)的等待時間相同時，_將得到優(yōu)先調(diào)度；當各個作業(yè)要求的運行時間相同時

5、，_將得到優(yōu)先調(diào)度。短作業(yè)優(yōu)先算法高優(yōu)先權優(yōu)先算法高響應比優(yōu)先算法短作業(yè)最先到達者等待時間最長者第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課三、應用題1.設有三道作業(yè)，它們的提交時間和運行時間如下表：作業(yè)號提交時刻(時)運行時間(小時) 1 10.002 2 10.101 3 10.25 0.25求：試給出下面兩種調(diào)度算法下，作業(yè)的執(zhí)行順序、平均周轉時間和平均帶權周轉時間。(1)先來先服務FCFS調(diào)度算法(2)短作業(yè)優(yōu)先SJF調(diào)度算法第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課5.32.63平均12313.2513.000.2510.2532.92.9013.0012.00110.

6、1021212.0010.00210.001帶權周轉時間周轉時間完成時刻開始時刻運行時間提交時刻作業(yè)號(1)先來先服務FCFS調(diào)度算法第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課4.052.38平均8212.2512.000.2510.2533.153.1513.2512.25110.1021212.0010.00210.001帶權周轉時間周轉時間完成時刻開始時刻運行時間提交時刻作業(yè)號(2)短作業(yè)優(yōu)先SJF調(diào)度算法第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課三、應用題2.設有四道作業(yè)，它們的提交時間和運行時間如下表：作業(yè)號提交時刻(時)運行時間(小時) 1 8:00 2.0 2 8

7、:50 0.5 3 9:00 0.1 4 9:50 0.2求：試給出下面三種調(diào)度算法下，作業(yè)的執(zhí)行順序、平均周轉時間和平均帶權周轉時間。(1)先來先服務FCFS調(diào)度算法(2)短作業(yè)優(yōu)先SJF調(diào)度算法(3)高響應比優(yōu)先調(diào)度算法第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課(1)先來先服務FCFS調(diào)度算法6.291.6474.835810:4810:360.29:50416.009610:3610:300.19:0033.3410010:3010:000.58:5021.0012010:008:002.08:001帶權周轉時間周轉時間完成時間開始時間運行時間提交時間作業(yè)號第三章 處理機調(diào)度與死

8、鎖 第三章第三章習題課習題課(2)短作業(yè)優(yōu)先SJF調(diào)度算法4.571.382.342810:1810:060.29:50411.006610:0610:000.19:0033.9311810:4810:180.58:5021.0012010:008:002.08:001帶權周轉時間周轉時間完成時間開始時間運行時間提交時間作業(yè)號第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課(3)高響應比優(yōu)先調(diào)度算法5.091.3754.835810:4810:360.29:50411.006610:0610:000.19:0033.5310610:3610:060.58:5021.0012010:008:0

9、02.08:001帶權周轉時間周轉時間完成時間開始時間運行時間提交時間作業(yè)號2: (70+30)/0.5=2003: (60+6)/0.1=6604: (10+12)/0.2=1102: (76+30)/0.5=2124: (16+12)/0.2=140第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課三、應用題3.假設某系統(tǒng)中有3種資源(R1,R2,R3)，在某時刻系統(tǒng)中共有4個進程，進程(P1,P2,P3,P4)的最大資源需求數(shù)向量和此時已分配的資源數(shù)向量分別為：進程最大資源需求當前已分配到資源P1(3,2,2)(1,0,0)P2(6,1,3)(5,1,1)P3(3,1,4)(2,1,1)

10、P4(4,2,2)(0,0,2)第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課三、應用題系統(tǒng)中當前可用資源向量為(1,1,2)，問：(1) 計算還需要資源數(shù)組；(2) 系統(tǒng)此時是否安全？(4,2,0)(0,0,2)(4,2,2)P4(1,0,3)(2,1,1)(3,1,4)P3(1,0,2)(5,1,1)(6,1,3)P2(1,1,2)(2,2,2)(1,0,0)(3,2,2)P1AvailableNeedAllocationMax第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課truetruetruetrueFinish(1,0,0)(0,0,2)(2,1,1)(5,1,1)Alloc

11、ation(8,3,6)(8,3,4)(6,2,3)(1,1,2)Work(9,3,6)(2,2,2)P1(8,3,6)(4,2,0)P4(8,3,4)(1,0,3)P3(6,2,3)(1,0,2)P2Work + AllocationNeed三、應用題系統(tǒng)中當前可用資源向量為(1,1,2)，問：(1) 計算還需要資源數(shù)組；(2) 系統(tǒng)此時是否安全？第三章 處理機調(diào)度與死鎖 (4,2,0)(0,0,2)(4,2,2)P4(1,0,3)(2,1,1)(3,1,4)P3(1,0,2)(5,1,1)(6,1,3)P2(1,1,2)(2,2,2)(1,0,0)(3,2,2)P1AvailableNee

12、dAllocationMax第三章第三章習題課習題課 (3) 如果進程P2發(fā)出資源請求向量(1,0,1)，系統(tǒng)能否將資源分配給它？ Request2(1, 0, 1)Need2(1, 0, 2) Request2(1, 0, 1)Available2(1, 1, 2)(6,1,2)(0,1,1)(0,0,1)第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課truetruetruetrueFinish(1,0,0)(0,0,2)(2,1,1)(6,1,2)Allocation(8,3,6)(8,3,4)(6,2,3)(0,1,1)Work(9,3,6)(2,2,2)P1(8,3,6)(4,2,

13、0)P4(8,3,4)(1,0,3)P3(6,2,3)(0,0,1)P2Work + AllocationNeed三、應用題 再利用安全性算法檢查此時系統(tǒng)是否安全。存在一個安全序列：P2, P3, P4, P1 第三章 處理機調(diào)度與死鎖 (4,2,0)(0,0,2)(4,2,2)P4(1,0,3)(2,1,1)(3,1,4)P3(1,0,2)(5,1,1)(6,1,3)P2(1,1,2)(2,2,2)(1,0,0)(3,2,2)P1AvailableNeedAllocationMax第三章第三章習題課習題課 (4) 如果進程P1發(fā)出資源請求向量(1,0,1)，系統(tǒng)能否將資源分配給它？ Requ

14、est1(1, 0, 1)Need1(2, 2, 2) Request1(1, 0, 1)Available1(1, 1, 2)(2,0,1)(0,1,1)(1,2,1)不安全狀態(tài)第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課三、應用題4.假設某系統(tǒng)中有4種資源，在某時刻系統(tǒng)中共有5個進程，進程(P0,P1,P2,P3,P4)的最大資源需求數(shù)向量和此時已分配的資源數(shù)向量分別為：進程最大資源需求當前已分配到資源P0(0,0,1,2)(0,0,1,2)P1(2,7,5,0)(2,0,0,0)P2(6,6,5,6)(0,0,3,4)P3(4,3,5,6)(2,3,5,4)P4(0,6,5,2)(

15、0,3,3,2)第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課三、應用題系統(tǒng)中當前可用資源向量為(2,1,0,0)，問：(1) 計算進程還需要請求的資源向量；(2) 系統(tǒng)當前是處于安全狀態(tài)么？(2,1,0,0)Available(0,3,2,0)(2,0,0,2)(6,6,2,2)(0,7,5,0)(0,0,0,0)Need(0,3,3,2)(0,6,5,2)P4(2,3,5,4)(4,3,5,6)P3(0,0,3,4)(6,6,5,6)P2(2,0,0,0)(2,7,5,0)P1(0,0,1,2)(0,0,1,2)P0AllocationMax第三章 處理機調(diào)度與死鎖 第三章第三章習題課

16、習題課三、應用題系統(tǒng)中當前可用資源向量為(2,1,0,0)，問：(1) 計算進程還需要請求的資源向量；(2) 系統(tǒng)當前是處于安全狀態(tài)么？truetruetruetruetrueFinish(0,0,3,4)(2,0,0,0)(0,3,3,2)(2,3,5,4)(0,0,1,2)Allocation(6,7,9,8)(4,7,9,8)(4,4,6,6)(2,1,1,2)(2,1,0,0)Work(6,7,12,12)(6,6,2,2)P2(6,7,9,8)(0,7,5,0)P1(4,7,9,8)(0,3,2,0)P4(4,4,6,6)(2,0,0,2)P3(2,1,1,2)(0,0,0,0)P0

17、Work + AllocationNeed第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課 (3) 當進程P2申請(0,1,0,0)時，系統(tǒng)能立即滿足么？ Request2(0,1,0,0)Need2(6,6,2,2) Request2(0,1,0,0)Available2(2,1,0,0)(2,1,0,0)Available(0,3,2,0)(2,0,0,2)(6,6,2,2)(0,7,5,0)(0,0,0,0)Need(0,3,3,2)(0,6,5,2)P4(2,3,5,4)(4,3,5,6)P3(0,0,3,4)(6,6,5,6)P2(2,0,0,0)(2,7,5,0)P1(0,0,1,2)(0,0,1,2)P0AllocationMax(0,1,3,4)(2,0,0,0)(6,5,2,2)第三章 處理機調(diào)度與死鎖 第三章第三章習題課習題課三、應用題 再利用安全性算法檢查此時系統(tǒng)是否安全。不存在安全序列truetruetrueFinish(0,1,3,4)(2,0,0,0)(0,3,3,2)(2,3,5,4)(0,0,1,2)Allocation(4,6,9,8)(4,3,6,6)(2,0,1,2)(2,0,0,0)Work(6,5,2,2)P2(0,7,5,