第3章處理機(jī)調(diào)度和死鎖

1、2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院1第3章 處理機(jī)調(diào)度與死鎖o 3.1 處理機(jī)調(diào)度的基本概念o 3.2 調(diào)度算法o 3.3 實(shí)時(shí)調(diào)度o 3.4 產(chǎn)生死鎖的原因和必要條件o 3.5 預(yù)防死鎖的方法o 3.6 死鎖的檢測(cè)與解除 2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院23.1 處理機(jī)調(diào)度的基本概念o 3.1.1 高級(jí)調(diào)度、中級(jí)調(diào)度、低級(jí)調(diào)度o 3.1.2 調(diào)度隊(duì)列模型o 3.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院32021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院43.1.1 高級(jí)、中級(jí)和低級(jí)調(diào)度經(jīng)歷下述三級(jí)調(diào)度:n高級(jí)調(diào)度（H

2、igh Scheduling）n中級(jí)調(diào)度（Intermediate-Level Scheduling）n低級(jí)調(diào)度（Low Level Scheduling）2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院51. 高級(jí)調(diào)度 又稱為作業(yè)調(diào)度、宏觀調(diào)度或長(zhǎng)程調(diào)度。用于決定把后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，為他們分配必要的資源，并創(chuàng)建進(jìn)程。 批處理系統(tǒng) ：分時(shí)系統(tǒng) ：實(shí)時(shí)系統(tǒng) ：需要作業(yè)調(diào)度不需作業(yè)調(diào)度不需作業(yè)調(diào)度2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院61. 高級(jí)調(diào)度執(zhí)行作業(yè)調(diào)度時(shí)，必須作出兩個(gè)決定：o 接納多少作業(yè)每次接納多少作業(yè)進(jìn)入內(nèi)存，取決于多道程序度，即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。

3、o 接納哪些作業(yè)應(yīng)接納哪些作業(yè)從外存調(diào)入內(nèi)存，取決于所采用的調(diào)度算法。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院72. 低級(jí)調(diào)度 通常也稱為進(jìn)程調(diào)度、微觀調(diào)度或短程調(diào)度。進(jìn)程調(diào)度是最基本的一種調(diào)度，在三種OS中都有。用于決定就緒隊(duì)列中哪個(gè)進(jìn)程應(yīng)先獲得處理機(jī)，并將處理機(jī)分配給選中的進(jìn)程。為實(shí)現(xiàn)進(jìn)程調(diào)度，應(yīng)具有如下三個(gè)基本機(jī)制： 排隊(duì)器 分派器 上下文切換2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院82. 低級(jí)調(diào)度進(jìn)程調(diào)度可采用下述兩種調(diào)度方式：o 非搶占方式o 搶占方式搶占的原則有：（1）優(yōu)先權(quán)原則（2）短作業(yè)（進(jìn)程）優(yōu)先原則（3）時(shí)間片原則2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息

4、學(xué)院93. 中級(jí)調(diào)度 中級(jí)調(diào)度又稱為交換調(diào)度、中程調(diào)度或內(nèi)存調(diào)度。 它按一定的算法將外存中已具備運(yùn)行條件的進(jìn)程換入內(nèi)存，而將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換出至外存。運(yùn)行就緒阻塞掛起阻塞掛起就緒創(chuàng)建退出進(jìn)程調(diào)度中級(jí)調(diào)度作業(yè)調(diào)度調(diào)度的層次2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院113.1.2 調(diào)度隊(duì)列模型o 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型o 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型o 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院121. 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 在分時(shí)系統(tǒng)中就緒進(jìn)程組織成FIFO隊(duì)列形式，按時(shí)間片輪轉(zhuǎn)方式運(yùn)行。CPU就 緒 隊(duì) 列阻 塞 隊(duì) 列時(shí)間

5、片完進(jìn)程調(diào)度等待事件進(jìn)程完成交互用戶事件出現(xiàn)2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院132. 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型CPU就 緒 隊(duì) 列時(shí)間片完進(jìn)程調(diào)度等待事件1進(jìn)程完成后備隊(duì)列等待事件2等待事件n事件1出現(xiàn)事件2出現(xiàn)事件n出現(xiàn)作業(yè)調(diào)度2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院143. 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型CPU就 緒 隊(duì) 列時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成后備隊(duì)列等待事件事件出現(xiàn)作業(yè)調(diào)度批量作業(yè)交互型作業(yè)中級(jí)調(diào)度就緒、掛起隊(duì)列事件出現(xiàn)阻 塞、掛 起 隊(duì) 列掛起阻 塞 隊(duì) 列掛起中級(jí)調(diào)度2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院153.1.3 選擇調(diào)度方式和調(diào)度

6、算法的若干準(zhǔn)則o 面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短n平均周轉(zhuǎn)時(shí)間Tn平均帶權(quán)周轉(zhuǎn)時(shí)間（W= T(周轉(zhuǎn))/Ts(CPU執(zhí)行)響應(yīng)時(shí)間快截止時(shí)間的保證優(yōu)先權(quán)準(zhǔn)則o 面向系統(tǒng)的準(zhǔn)則 系統(tǒng)吞吐量高 處理機(jī)利用率好 各類資源的平衡利用練習(xí)1o 設(shè)有4個(gè)作業(yè)同時(shí)到達(dá)，每個(gè)作業(yè)執(zhí)行時(shí)間均為2h，它們?cè)谝慌_(tái)處理器上按單道方式運(yùn)行，則平均周轉(zhuǎn)時(shí)間為（ ） A. 1h B. 5h C. 2.5h D.8hB2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院173.2 調(diào)度算法o 3.2.1 FCFS與SJF/SPF調(diào)度算法o 3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法o 3.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法2021-10-14阜陽(yáng)師

7、范學(xué)院計(jì)算機(jī)與信息學(xué)院183.2.1 FCFS與SJF/SPF調(diào)度算法1. 先來(lái)先服務(wù)調(diào)度算法(FCFS) 按進(jìn)程申請(qǐng)CPU（就緒）的次序processRun timeP127P23P35P1P2P3 0 27 30 352021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院19 FCFS實(shí)例 下表列出了A、B、C、D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開(kāi)始執(zhí)行的時(shí)間及各自的完成時(shí)間，計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。FCFS（First Come First Serve)2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院20作業(yè)名 到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A

8、01B1100C21D3100FCFS（First Come First Serve)0111110110011011021001001022021991.992021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院21FCFS的特點(diǎn): o FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)（進(jìn)程）o 比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè)FCFS（First Come First Serve)2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院222. 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間完成時(shí)間 SJF帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間完成時(shí)間 FCFS42534服務(wù)時(shí)間43210到達(dá)時(shí)間平均

9、EDCBA作業(yè)名 作業(yè)情 況調(diào)度算法4417621210214115.518143.592.8441982.6718163.2631.51392.2582.12021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院232 . 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJF調(diào)度算法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：有效降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量缺點(diǎn)：(1) 對(duì)長(zhǎng)作業(yè)不利(2) 不能保證緊迫性作業(yè)（進(jìn)程）的及時(shí)處理(3) 不一定能真正做到短作業(yè)優(yōu)先2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院243.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法1. 優(yōu)先權(quán)調(diào)度算法的類型 為照顧緊迫性作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)

10、先（HPF）調(diào)度算法。它分為兩種：o 非搶占式優(yōu)先權(quán)算法o 搶占式優(yōu)先權(quán)調(diào)度算法2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院253.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法2. 優(yōu)先權(quán)的類型o 靜態(tài)優(yōu)先權(quán)：在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變,又稱優(yōu)先數(shù)。1) 動(dòng)態(tài)優(yōu)先權(quán)：在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院263. 高響應(yīng)比優(yōu)先調(diào)度算法(HRRN) 為每個(gè)作業(yè)引入動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率a提高，則可解決問(wèn)題。見(jiàn)下式： 優(yōu)先權(quán)=(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間 響應(yīng)時(shí)間/

11、要求服務(wù)時(shí)間 3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法練習(xí)2o 一個(gè)作業(yè)8：00到達(dá)系統(tǒng)，估計(jì)運(yùn)行時(shí)間為1h。若10:00開(kāi)始執(zhí)行該作業(yè)，其響應(yīng)比是（ ） A. 2 B.1 C.3 D.0.5C例題1o 設(shè)有4個(gè)作業(yè)J1、J2、J3、J4，它們的到達(dá)時(shí)間和計(jì)算時(shí)間如表所示。若這4個(gè)作業(yè)在一臺(tái)處理器上按單道方式運(yùn)行，采用高響應(yīng)比優(yōu)先調(diào)度算法，試寫出各作業(yè)的執(zhí)行順序、各作業(yè)的周轉(zhuǎn)時(shí)間及平均周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間 計(jì)算時(shí)間J18：00120minJ28：3040minJ39：0025minJ49：3030min解析：優(yōu)先權(quán)（響應(yīng)比）=(等待時(shí)間+要求服務(wù)時(shí)間)/要求 服務(wù)時(shí)間響應(yīng)時(shí)間/要求服務(wù)時(shí)間作業(yè)提交時(shí)間

12、開(kāi)始時(shí)間執(zhí)行時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間J18：008：00120min10：00120minJ28：3010：2540min11：05155minJ39：0010：0025min10：2585minJ49：3011：0530min11：35125min例題2o 在一個(gè)批處理系統(tǒng)中，有兩個(gè)作業(yè)進(jìn)程。有一個(gè)作業(yè)序列，其到達(dá)時(shí)間及估計(jì)運(yùn)行時(shí)間如表所示。系統(tǒng)作業(yè)采用最高響應(yīng)比優(yōu)先調(diào)度算法，進(jìn)程的調(diào)度采用短進(jìn)程優(yōu)先的搶占式調(diào)度算法作業(yè)到達(dá)時(shí)間 估計(jì)運(yùn)行時(shí)間J110：0035minJ210：1030minJ310：1545minJ410：2020minJ510：3030min例題2o （1）列出各作業(yè)的執(zhí)行時(shí)間

13、（即列出每個(gè)作業(yè)運(yùn)行的時(shí)間片段，如作業(yè)i的運(yùn)行時(shí)間序列為10：00-10：40）o （2）計(jì)算這批作業(yè)的平均周轉(zhuǎn)時(shí)間。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院32J110:00J4:20m10:10J2到達(dá)到達(dá)J210:35J1完成完成J4進(jìn)內(nèi)存進(jìn)內(nèi)存分析：分析：J3J4J510:55J4完成完成J3進(jìn)內(nèi)存進(jìn)內(nèi)存J1:10mJ1:25m11:25J2完成完成J5進(jìn)內(nèi)存進(jìn)內(nèi)存J2:30mJ5:30m11:55J5完成完成12:40J3完成完成J3:45m例題3o 有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用搶占式優(yōu)先級(jí)調(diào)度算法，作業(yè)的運(yùn)行情況如表所示，

14、其中作業(yè)的優(yōu)先數(shù)即為進(jìn)程的優(yōu)先數(shù)，優(yōu)先數(shù)越小，優(yōu)先級(jí)越高。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院33作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先數(shù)J18：0040min5J28：2030min3J38：3050min4J48：5020min6（1）列出所有作業(yè)進(jìn)入內(nèi)存的時(shí)間及結(jié)束的時(shí)間（2）計(jì)算平均周轉(zhuǎn)時(shí)間2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院34J18:00J1:20m8:20J2到達(dá)到達(dá)J28:30分析：分析：J3J48:50J2完成完成J4進(jìn)入進(jìn)入J1:20mJ2:10m9:10J1完成完成J3進(jìn)內(nèi)存進(jìn)內(nèi)存J3:50mJ4:20m10:00J3完成完成10:20J4完成完成J2:20

15、m2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院353.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法(RR) 在分時(shí)系統(tǒng)中，為保證能及時(shí)響應(yīng)用戶的請(qǐng)求，必須采用基于時(shí)間片的輪轉(zhuǎn)式進(jìn)程調(diào)度算法。在早期，分時(shí)系統(tǒng)中采用的是簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法，進(jìn)入90年代后，廣泛采用多級(jí)反饋隊(duì)列調(diào)度算法。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院36u將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列。u每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。u在一個(gè)時(shí)間片結(jié)束時(shí)，將其送到就緒隊(duì)列的末尾，并通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。一、時(shí)間片輪轉(zhuǎn)算法1. 基本原理2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院

16、372. 時(shí)間片長(zhǎng)度的確定v時(shí)間片長(zhǎng)度變化的影響過(guò)長(zhǎng)退化為FCFS算法。過(guò)短用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加。對(duì)響應(yīng)時(shí)間的要求：T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片)一、時(shí)間片輪轉(zhuǎn)算法2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院382021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院39二、多級(jí)反饋隊(duì)列調(diào)度算法 實(shí)施過(guò)程如下：（1） 應(yīng)設(shè)置多個(gè)隊(duì)列并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)最高，依次降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也不相同，優(yōu)先權(quán)越高，時(shí)間片越短。1. 調(diào)度算法2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院40多級(jí)反饋隊(duì)列調(diào)度算法 就緒

17、隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片：S1 S2 S3)2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院41二、多級(jí)反饋隊(duì)列調(diào)度算法(2) 當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。如它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾。(3）僅當(dāng)?shù)?（i-1）隊(duì)列空閑時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院422. 多級(jí)反饋隊(duì)列調(diào)度算法的性能p 終端型作業(yè)用戶p 短作業(yè)優(yōu)先o 短批處理作業(yè)用戶n 周轉(zhuǎn)時(shí)間較短o 長(zhǎng)批處理作業(yè)用戶二、多級(jí)反饋隊(duì)列調(diào)度

18、算法2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院43補(bǔ)充作業(yè)o 假如有四道作業(yè)，它們的進(jìn)入時(shí)間和運(yùn)行時(shí)間由下表給出，在單道程序環(huán)境下，分別填寫先來(lái)先服務(wù)、短作業(yè)優(yōu)先和RR（3）算法的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院44作業(yè)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間FCFSSJFRR（3）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1042110326432平均2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院45第3章 處理機(jī)調(diào)度與死鎖o 3.3 實(shí)時(shí)調(diào)度o 3.4 產(chǎn)生死鎖的原因和必要條件o

19、3.5 預(yù)防死鎖的方法o 3.6 死鎖的檢測(cè)與解除 2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院463.3 實(shí)時(shí)調(diào)度o 實(shí)時(shí)調(diào)度：n 合理安排就緒實(shí)時(shí)任務(wù)的執(zhí)行次序，滿足每個(gè)實(shí)時(shí)任務(wù)時(shí)間約束條件的調(diào)度o 實(shí)時(shí)任務(wù)：n 具有明確時(shí)間約束的計(jì)算任務(wù)2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院473.3 實(shí)時(shí)調(diào)度o 3.3.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件o 3.3.2 實(shí)時(shí)調(diào)度算法的分類o 3.3.3 常用的幾種實(shí)時(shí)調(diào)度算法2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院483.3.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件o 提供必要的信息o 系統(tǒng)處理能力強(qiáng)o 采用搶占式調(diào)度機(jī)制o 具有快速切換機(jī)制2021-

20、10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院491. 提供必要的信息o 就緒時(shí)間o 開(kāi)始截止時(shí)間和完成截止時(shí)間o 處理時(shí)間o 資源要求o 優(yōu)先級(jí)2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院502. 系統(tǒng)處理能力強(qiáng) 假如系統(tǒng)中有M個(gè)周期性的硬實(shí)時(shí)任務(wù)，處理時(shí)間為Ci，周期時(shí)間表示為Pi 則單機(jī)系統(tǒng)中必須滿足條件 （ Ci / Pi ）1 多處理機(jī)系統(tǒng) （ Ci / Pi ）N2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院513. 采用搶占式調(diào)度機(jī)制o 硬實(shí)時(shí)任務(wù)： 廣泛采用搶占機(jī)制 o 小的實(shí)時(shí)系統(tǒng)： 可采用非搶占調(diào)度機(jī)制（簡(jiǎn)化調(diào)度程序和對(duì)任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開(kāi)銷）3. 采用搶占式調(diào)度機(jī)制20

21、21-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院52(a) 非搶占式輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度實(shí)時(shí)進(jìn)程搶占當(dāng)前進(jìn)程并立即執(zhí)行(d) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間進(jìn)程 1進(jìn)程 2實(shí)時(shí)進(jìn)程要求調(diào)度進(jìn)程 n實(shí)時(shí)進(jìn)程調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行(b) 非搶占式優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度 當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時(shí)間當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度 時(shí)鐘中斷到來(lái)時(shí)調(diào)度時(shí)間(c) 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時(shí)間實(shí)時(shí)進(jìn)程2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院534. 具有快速切換機(jī)制 (1) 對(duì)外部中斷的快速響應(yīng)能力(2) 快速的任務(wù)分派能力2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息

22、學(xué)院543.3.2 實(shí)時(shí)調(diào)度算法的分類可以按照不同方式對(duì)實(shí)時(shí)調(diào)度算法加以分類：o 根據(jù)實(shí)時(shí)任務(wù)性質(zhì)的不同可分為硬實(shí)時(shí)調(diào)度算法和軟實(shí)時(shí)調(diào)度算法；o 按調(diào)度方式的不同可分為非搶占調(diào)度算法和搶占調(diào)度算法；2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院553.3.3 常用的幾種實(shí)時(shí)調(diào)度算法 o 最早截止時(shí)間優(yōu)先EDF（Earliest Deadline First）算法o 最低松弛度優(yōu)先LLF（Least Laxity First）算法2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院56EDF算法用于非搶占調(diào)度圖示 1 3 4 2t按開(kāi)始截止時(shí)間早晚的排序任務(wù)執(zhí)行任務(wù)到達(dá) 1 3 4 2 1 2 3

23、 4 1. 最早截止時(shí)間優(yōu)先EDF算法 截止時(shí)間越早，其優(yōu)先級(jí)越高2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院572. 最低松弛度優(yōu)先LLF算法o 松弛度=完成截止時(shí)間運(yùn)行時(shí)間當(dāng)前時(shí)間o 任務(wù)的緊急程度愈高，松弛度愈低，優(yōu)先級(jí)愈高。o 要求系統(tǒng)有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列o 該算法主要用于可搶占調(diào)度方式中2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院58LLF算法例tA1 A2 A3 A4 A5 A6B1 B2 0 20 40 60 80 100 120 假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期型實(shí)時(shí)任務(wù)A、B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B要求每50ms執(zhí)行一

24、次，執(zhí)行時(shí)間為25ms；由此可得知AB任務(wù)每次必須完成的時(shí)間分別為A1、A2、A3和B1、B2、B3如下圖：2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院59LLF算法例圖示tt1 t2 t3 t4 t5 t6 t7 t8 0 10 20 30 40 50 60 70 80A1(10) A2(10) A3(10) A4 (10) B1(20) B1 (5) B2(15) B2(10) 2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院603.5 產(chǎn)生死鎖的原因和必要條件o3.5.1 產(chǎn)生死鎖的原因o3.5.2 產(chǎn)生死鎖的必要條件o3.5.3 處理死鎖的基本方法2021-10-14阜陽(yáng)師范學(xué)院計(jì)

25、算機(jī)與信息學(xué)院61關(guān)于死鎖 死鎖是指多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種狀態(tài)時(shí)，若無(wú)外力作用，它們都將無(wú)法再向前推進(jìn)。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院623.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)：o 競(jìng)爭(zhēng)資源1. 進(jìn)程間推進(jìn)順序非法n 可搶占和非搶占性資源n 可重用性（永久性）資源和可消耗性（臨時(shí)性）資源2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院63P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1) P1Rel(R2)D進(jìn)程推進(jìn)順序不當(dāng)引起死鎖2021-1

26、0-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院643.5.2 產(chǎn)生死鎖的必要條件 雖然進(jìn)程在運(yùn)行過(guò)程中可能發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件。可以看出，必須具備以下四個(gè)條件:1. 互斥條件：進(jìn)程所競(jìng)爭(zhēng)的資源必須被互斥使用。2. 請(qǐng)求和保持條件：指進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其他資源保持不放。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院653.5.2 產(chǎn)生死鎖的必要條件 3. 不剝奪條件：指進(jìn)程已獲得的資源，只能在使用完時(shí)由自己釋放。 4. 環(huán)路等待條件：指在發(fā)生死鎖時(shí)，必然存在一個(gè)“進(jìn)程資源”的環(huán)形鏈，環(huán)路

27、中的每一條邊是進(jìn)程在請(qǐng)求另一進(jìn)程已經(jīng)占有的資源。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院663.5.3 處理死鎖的基本方法一、預(yù)防死鎖消除產(chǎn)生死鎖的必要條件二、避免死鎖分配資源時(shí)防止進(jìn)入不安全狀態(tài)三、檢測(cè)死鎖不預(yù)防死鎖，出現(xiàn)死鎖就解除四、解除死鎖與檢測(cè)死鎖配合使用2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院673.6 預(yù)防與避免死鎖的方法o3.6.1 預(yù)防死鎖o3.6.2 系統(tǒng)安全狀態(tài)o3.6.3 利用銀行家算法避免死鎖2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院683.6.1 預(yù)防死鎖1. 摒棄“請(qǐng)求和保持”條件靜態(tài)資源分配法 一次性地申請(qǐng)其在整個(gè)過(guò)程運(yùn)行過(guò)程中所需要的全部資

28、源o優(yōu)點(diǎn)：算法簡(jiǎn)單、易于實(shí)現(xiàn)且很安全o缺點(diǎn)：資源浪費(fèi)嚴(yán)重，進(jìn)程延遲運(yùn)行2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院692. 摒棄“不剝奪”條件o 資源暫時(shí)釋放策略:申請(qǐng)新的資源得不到滿足則暫時(shí)釋放已有的所有資源。從而摒棄了“不剝奪”條件。o 該方法實(shí)現(xiàn)起來(lái)比較復(fù)雜且付出很大代價(jià)?？赡軙?huì)造成前功盡棄，反復(fù)申請(qǐng)和釋放情況。3.6.1 預(yù)防死鎖2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院703. 摒棄“環(huán)路等待”條件o 有序資源分配法：o 與前兩種策略比較，資源利用率和系統(tǒng)吞吐量都有較明顯的改善。o 但也存在嚴(yán)重問(wèn)題：為資源編號(hào)限制新設(shè)備的增加；進(jìn)程使用設(shè)備順序與申請(qǐng)順序相反；限制用戶編程自

29、由。r1r2rk.申請(qǐng)次序rm2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院71檢測(cè)可滿足請(qǐng)求 分配 不分配安全不安全系統(tǒng)處于安全狀態(tài)：存在安全進(jìn)程序列;安全不安全死鎖1. 安全狀態(tài)3.6.2 系統(tǒng)安全狀態(tài)o 避免死鎖的實(shí)質(zhì)就是系統(tǒng)在進(jìn)行資源分配時(shí)，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院722. 安全狀態(tài)之例 假定系統(tǒng)中有三個(gè)進(jìn)程A、B和C，共有12臺(tái)磁帶機(jī)。進(jìn)程A總共要求10臺(tái)，B和C分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻,進(jìn)程A、B和C已分別獲得5臺(tái)、2臺(tái)和2臺(tái)，尚有3臺(tái)未分配，如下表所示：進(jìn)程最大需求已分配還需可用ABC10495225273進(jìn)程最大需

30、求已分配還需可用B 4 2 235A 10 5 510C 9 2 712 經(jīng)分析發(fā)現(xiàn)，在T0時(shí)刻系統(tǒng)是安全的，因?yàn)榇藭r(shí)存在一個(gè)安全序列，即只要系統(tǒng)按此進(jìn)程序列分配資源，就能使每個(gè)進(jìn)程都順利完成。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院733. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換o 如果在T0時(shí)刻后，C又請(qǐng)求到一臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給C，則系統(tǒng)便進(jìn)入不安全狀態(tài)。因?yàn)?，此時(shí)再也無(wú)法找到一個(gè)安全序列，結(jié)果導(dǎo)致死鎖。進(jìn)程最大需求已分配還需可用A10553B422C927o 所以，引入安全狀態(tài)的目的在于進(jìn)行資源分配時(shí)，要使系統(tǒng)不發(fā)生死鎖，只要保證當(dāng)前的系統(tǒng)狀態(tài)是安全的，即每次資源

31、分配之后系統(tǒng)都處于安全狀態(tài)。 2C 9 3 6練習(xí)1o 某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，由K個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（ ），不會(huì)發(fā)生死鎖的最大值是（ ）。 A. 2 B. 3 C. 4 D. 5解析：p R類資源共m個(gè)， n個(gè)進(jìn)程互斥使用，每個(gè)進(jìn)程對(duì)R類資源最大需求量為wp 設(shè)：M=n*（w-1）+1p 則m=M絕對(duì)不會(huì)死鎖 練習(xí)1o 某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，由K個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（ ），不會(huì)發(fā)生死鎖的最大值是（ ）。 A. 2 B. 3 C. 4 D. 5CB2021-10-14

32、阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院773.6.3 利用銀行家算法避免死鎖o最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名的。1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)（1）可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其動(dòng)態(tài)初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配與回收而動(dòng)態(tài)的改變。如果Availablej=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。（2）最大需求矩陣Max。這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K

33、,則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。（3）分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K,則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。（4）需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K,則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。上述三個(gè)矩陣間存在的關(guān)系：Needi,j=Maxi,j-Allocationi,j2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院783.6.3 利用銀行家算法避免死鎖o 安全性算法系統(tǒng)所執(zhí)行的安全性算法

34、可描述如下：（1）設(shè)置兩個(gè)向量： 工作向量work：表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開(kāi)始時(shí)，work:=Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finishi:=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi:=true。2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院79安全性檢測(cè)算法FWork:=Available;Finish:=false; 有滿足條件的有滿足條件的j:Finishi=falseNeedj WorkFinishi=true;Work:=Work+Alloca

35、tionjT i ,Finishi=trueTF安全安全不安全不安全賦初值賦初值進(jìn)程是否完成進(jìn)程是否完成資源是否夠用資源是否夠用進(jìn)程獲得資源后，順進(jìn)程獲得資源后，順利完成并釋放資源利完成并釋放資源進(jìn)程是否進(jìn)程是否都完成都完成2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院80（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false;Needi,j=workj;若找到，執(zhí)行步驟3，否則執(zhí)行步驟4。 （3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： workj:= worki+ Allocationi,j ; Finishi:=true; g

36、oto step 2;（4）如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。安全性算法2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院814. 銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程P0,P1,P2,P3,P4和三類資源A,B,C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖所示。4 3 10 0 24 3 3P40 1 12 1 12 2 2P36 0 03 0 29 0 2P21 2 22 0 03 2 2P13 3 27 4 30 1 07 5 3P0AvailableA B CNeedA B CAllocationA B

37、CMaxA B C 資源情況資源情況進(jìn)程進(jìn)程2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院824. 銀行家算法之例 T0時(shí)刻的安全性：利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析可知，在T0時(shí)刻存在著一個(gè)安全序列P1,P3,P4,P2,P0，故系統(tǒng)是安全的。FalseFalseFalseFalseFalseTrue10 5 70 1 07 4 310 4 7P0True10 4 73 0 26 0 07 4 5P2True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 22 0 01 2 23 3 2P1FinishWork

38、+AllocationA B CAllocationA B CNeedA B CWorkA B C 資源情況資源情況進(jìn)程進(jìn)程2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院833.6.3 利用銀行家算法避免死鎖o 銀行家算法 設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requesti j=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院84Pi請(qǐng)求資源請(qǐng)求資源Requestij Needj請(qǐng)求超量，錯(cuò)返請(qǐng)求超量，錯(cuò)返Requestij Availablej不滿足，等待不滿足，等待Availablej:=Av

39、ailablej-RequestijAllocationi,j:=Allocationi,j+RequestijNeedi,j:=Needi,j-Requestij安全安全確認(rèn)，確認(rèn)，pi繼續(xù)繼續(xù)Availablej:=Availablej+RequestijAllocationi,j:=Allocationi,j-RequestijNeedi,j:=Needi,j+Requestijpi等待等待FTFTTF請(qǐng)求的資源是否超請(qǐng)求的資源是否超出實(shí)際需求出實(shí)際需求是否有足夠的是否有足夠的資源資源暫時(shí)分配資源暫時(shí)分配資源恢復(fù)原來(lái)的資源恢復(fù)原來(lái)的資源分配狀態(tài)分配狀態(tài)2021-10-14阜陽(yáng)師范學(xué)院計(jì)算

40、機(jī)與信息學(xué)院85（1）如果Requestij= Needi,j,便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。（2）如果Requestij= Availablej,便轉(zhuǎn)向步驟3；否則，表示尚無(wú)足夠資源，Pi需等待。 （3）系統(tǒng)試探著把資源分配給進(jìn)程Pi ，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej:= Availablej- Requestij; Allocationi,j:=Allocationi,j+Requestij; Needi,j:=Needi,j-Requestij;（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否出于安全狀態(tài)以決定是否完成本次

41、分配。銀行家算法2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院864. 銀行家算法之例o P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1， 0， 2),系統(tǒng)按銀行家算法進(jìn)行檢查：（1）Request1(1，0，2)=Need1(1，2，2)（2）Request1(1，0，2)=Available1(3，3，2)（3）系統(tǒng)先假定可為P1分配資源，并修改Available、Allocation1和Need1向量。 （4）再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。如下表：2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院87FalseFalseFalseFalseFalse4. 銀行家算法之例 由所

42、進(jìn)行的安全性檢查得知，可以找到一個(gè)安全序列P1,P3,P4,P0,P2,因此，系統(tǒng)是安全的，可以立即將P1所申請(qǐng)的資源分配給它。True10 5 73 0 26 0 07 5 5P2True7 5 50 1 07 4 37 4 5P0True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 23 0 20 2 02 3 0P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA B C 資源情況資源情況進(jìn)程進(jìn)程2021-10-14阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院884. 銀行家算法之例o P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0),系統(tǒng)按銀行家算法進(jìn)行檢查：（1）Request4(3，3，0)=Need4(4，3，1);（2）Request4(3，3，0)=Available(2，3，0),讓P4等待。o P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Request0(0，2，0),