




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖1 1第三章 處理機調(diào)度與死鎖3.1 處理機調(diào)度的基本概念3.2 作業(yè)調(diào)度3.3 進程調(diào)度3.4 死鎖 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖2 23.1 處理機調(diào)度的基本概念 處理機資源是計算機系統(tǒng)中最重要的資源,它的調(diào)度處理機資源是計算機系統(tǒng)中最重要的資源,它的調(diào)度策略,常常表示操作系統(tǒng)的某種特征,其算法的優(yōu)劣直接策略,常常表示操作系統(tǒng)的某種特征,其算法的優(yōu)劣直接影響整個系統(tǒng)的性能。影響整個系統(tǒng)的性能。 處理機調(diào)度需要解決三個問題:處理機調(diào)度需要解決三個問題:(1) (1) 處理機分配的策略,即需要確定處理機的調(diào)度算法;處理機分配的策略,即需要確定處理機的調(diào)
2、度算法;(2) (2) 什么時候分配處理機,即需要確定處理機的調(diào)度時機;什么時候分配處理機,即需要確定處理機的調(diào)度時機;(3) (3) 如何分配處理機,即需要給出處理機的調(diào)度過程。如何分配處理機,即需要給出處理機的調(diào)度過程。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖3 3一、處理機的分級調(diào)度:一、處理機的分級調(diào)度:1 1、作業(yè)調(diào)度(高級調(diào)度):、作業(yè)調(diào)度(高級調(diào)度): 按一定原則選擇按一定原則選擇若干個后備作業(yè)若干個后備作業(yè)調(diào)入主存調(diào)入主存,分配資,分配資源,并建立相應(yīng)的進程,投入運行。當(dāng)該作業(yè)執(zhí)行完畢源,并建立相應(yīng)的進程,投入運行。當(dāng)該作業(yè)執(zhí)行完畢時,還負責(zé)回收資源。時,還負責(zé)回收資源。 在每次執(zhí)
3、行作業(yè)調(diào)度時,都須做出以下兩個決定。在每次執(zhí)行作業(yè)調(diào)度時,都須做出以下兩個決定。 1) 1) 接納多少個作業(yè)接納多少個作業(yè) 2) 2) 接納哪些作業(yè)接納哪些作業(yè) 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4 42 2、進程調(diào)度(低級調(diào)度):、進程調(diào)度(低級調(diào)度): (線程調(diào)度)(線程調(diào)度) 按照某種策略從進程就緒隊列中選擇按照某種策略從進程就緒隊列中選擇一個就緒進程一個就緒進程,使,使其其占有處理機占有處理機運行。運行。進程調(diào)度方式:進程調(diào)度方式: 1 1)非搶占式調(diào)度方式非搶占式調(diào)度方式 當(dāng)有重要或緊迫的進程進入就緒隊列時,仍然讓正在執(zhí)當(dāng)有重要或緊迫的進程進入就緒隊列時,仍然讓正在執(zhí)行的進程繼續(xù)執(zhí)行
4、,直到該進程完成任務(wù)終止運行或發(fā)生某行的進程繼續(xù)執(zhí)行,直到該進程完成任務(wù)終止運行或發(fā)生某種等待事件而進入阻塞狀態(tài)時,才主動放棄占有的處理機,種等待事件而進入阻塞狀態(tài)時,才主動放棄占有的處理機,把處理機分配給重要或緊迫的就緒進程,以使其運行。把處理機分配給重要或緊迫的就緒進程,以使其運行。優(yōu)點:優(yōu)點:實現(xiàn)簡單、系統(tǒng)開銷小。實現(xiàn)簡單、系統(tǒng)開銷小。 適用于大多數(shù)的批處理系統(tǒng)環(huán)境。適用于大多數(shù)的批處理系統(tǒng)環(huán)境。 缺點:缺點:難以滿足緊急任務(wù)的要求難以滿足緊急任務(wù)的要求立即執(zhí)行,因而可能造立即執(zhí)行,因而可能造成難以預(yù)料的后果。顯然,在要求比較嚴格的實時系統(tǒng)中,成難以預(yù)料的后果。顯然,在要求比較嚴格的實時
5、系統(tǒng)中,不宜采用這種調(diào)度方式。不宜采用這種調(diào)度方式。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖5 5 2 2)搶占式調(diào)度方式搶占式調(diào)度方式 當(dāng)重要或緊迫的進程一到,便把正在執(zhí)行的進程占當(dāng)重要或緊迫的進程一到,便把正在執(zhí)行的進程占有的處理機強行剝奪下來,并轉(zhuǎn)給這個優(yōu)先級比它更高有的處理機強行剝奪下來,并轉(zhuǎn)給這個優(yōu)先級比它更高的重要或緊迫的就緒進程,使其運行。的重要或緊迫的就緒進程,使其運行。 搶占的原則:搶占的原則: (1) (1) 優(yōu)先權(quán)原則優(yōu)先權(quán)原則 (2) (2) 短作業(yè)短作業(yè)( (進程進程) )優(yōu)先原則優(yōu)先原則 (3) (3) 時間片原則時間片原則 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖6 63
6、3)交換調(diào)度(中級調(diào)度)(均衡調(diào)度):)交換調(diào)度(中級調(diào)度)(均衡調(diào)度): 按照給定的原則實現(xiàn)按照給定的原則實現(xiàn)進程進程在主存和外存交換區(qū)之間的在主存和外存交換區(qū)之間的換進換出換進換出,以解決內(nèi)存緊張問題,特別是具有虛擬存儲器,以解決內(nèi)存緊張問題,特別是具有虛擬存儲器的系統(tǒng)中。的系統(tǒng)中。 引入中級調(diào)度的主要目的引入中級調(diào)度的主要目的: : 是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。 為此,應(yīng)使那為此,應(yīng)使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源,而將它些暫時不能運行的進程不再占用寶貴的內(nèi)存資源,而將它們調(diào)至外存上去等待。們調(diào)至外存上去等待。 操作系統(tǒng) 第三章 處理
7、機調(diào)度與死鎖7 7二、調(diào)度隊列模型二、調(diào)度隊列模型 1. 1. 僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型 僅具有進程調(diào)度的調(diào)度隊列模型僅具有進程調(diào)度的調(diào)度隊列模型 就 緒 隊 列阻 塞 隊 列進程調(diào)度CPU進程完成等待事件交互用戶事件出現(xiàn)時間片完 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖8 82. 具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型 具有高、低兩級調(diào)度的調(diào)度隊列模型具有高、低兩級調(diào)度的調(diào)度隊列模型 就 緒 隊 列進程調(diào)度CPU進程完成等待事件 1作業(yè)調(diào)度事件1出現(xiàn)時間片完等待事件 2事件2出現(xiàn)等待事件 n事件n出現(xiàn)后 備 隊 列 操作系統(tǒng) 第三章 處理機調(diào)度
8、與死鎖9 93. 3. 同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型 具有三級調(diào)度時的調(diào)度隊列模型具有三級調(diào)度時的調(diào)度隊列模型 就緒隊列進程調(diào)度CPU就緒,掛起隊列中級調(diào)度阻塞,掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn) 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖1010三、三、 選擇調(diào)度方式和調(diào)度算法的若干準則選擇調(diào)度方式和調(diào)度算法的若干準則 面向用戶的準則面向用戶的準則 (1) (1) 作業(yè)周轉(zhuǎn)時間短。作業(yè)周轉(zhuǎn)時間短。 (2) (2) 響應(yīng)時間快。響應(yīng)時間快。 (3) (3) 截止時間的保證。截止時間的保證。 (4) (4) 優(yōu)先
9、權(quán)準則。優(yōu)先權(quán)準則。2.2.面向系統(tǒng)的準則面向系統(tǒng)的準則 (1) (1) 系統(tǒng)吞吐量高。系統(tǒng)吞吐量高。 (2) (2) 處理機利用率好。處理機利用率好。 (3) (3) 各類資源的平衡利用。各類資源的平衡利用。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖11113.2 作業(yè)調(diào)度一、作業(yè)的組織 程序程序 作業(yè)由三部分組成作業(yè)由三部分組成 數(shù)據(jù)數(shù)據(jù) 作業(yè)說明書作業(yè)說明書 (說明用戶的控制意圖)(說明用戶的控制意圖) 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖1212作業(yè)控制塊作業(yè)控制塊(JCBJCB):為了管理和調(diào)度已進入系統(tǒng)的各個作為了管理和調(diào)度已進入系統(tǒng)的各個作業(yè)業(yè),系統(tǒng)設(shè)置的用于記錄作業(yè)的基本情況的數(shù)據(jù)結(jié)構(gòu)
10、系統(tǒng)設(shè)置的用于記錄作業(yè)的基本情況的數(shù)據(jù)結(jié)構(gòu)。作業(yè)控制塊作業(yè)控制塊(JCBJCB)的主要內(nèi)容的主要內(nèi)容:(1)(1)作業(yè)的基本情況作業(yè)的基本情況 用戶名、作業(yè)名、作業(yè)的狀態(tài)和使用的語言等。用戶名、作業(yè)名、作業(yè)的狀態(tài)和使用的語言等。(2)(2)作業(yè)的控制要求作業(yè)的控制要求 控制方式、類型、優(yōu)先數(shù)、操作順序和出錯處理等??刂品绞?、類型、優(yōu)先數(shù)、操作順序和出錯處理等。(3)(3)作業(yè)的資源要求作業(yè)的資源要求 作業(yè)建立的時間、要求運行的時間、最遲完成的時間、作業(yè)建立的時間、要求運行的時間、最遲完成的時間、需要的主存容量、外設(shè)的種類及數(shù)量和資源使用情況。需要的主存容量、外設(shè)的種類及數(shù)量和資源使用情況。二、
11、作業(yè)控制塊二、作業(yè)控制塊 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖1313作業(yè)名作業(yè)名資源要求資源要求估計執(zhí)行時間估計執(zhí)行時間最遲完成時間最遲完成時間要求的主存量要求的主存量要求外設(shè)的類型及臺數(shù)要求外設(shè)的類型及臺數(shù)要求文件量和輸出量要求文件量和輸出量資源使用情況資源使用情況進入系統(tǒng)時間進入系統(tǒng)時間開始執(zhí)行時間開始執(zhí)行時間已執(zhí)行時間已執(zhí)行時間主存地址主存地址外設(shè)臺號外設(shè)臺號類型類型控制方式控制方式作業(yè)類型作業(yè)類型優(yōu)先級優(yōu)先級狀態(tài)狀態(tài)作業(yè)控制塊作業(yè)控制塊聯(lián)機和脫機聯(lián)機和脫機 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖1414 一個作業(yè)從提交給計算機系統(tǒng)到執(zhí)行結(jié)束退出系統(tǒng),一一個作業(yè)從提交給計算機系統(tǒng)到執(zhí)行結(jié)束退
12、出系統(tǒng),一般都要經(jīng)歷般都要經(jīng)歷4 4個狀態(tài):個狀態(tài):提交、后備(收容)、執(zhí)行和完成。提交、后備(收容)、執(zhí)行和完成。1 1)提交狀態(tài):)提交狀態(tài):通過終端設(shè)備向計算機的磁盤輸入作業(yè)信息通過終端設(shè)備向計算機的磁盤輸入作業(yè)信息時所處的狀態(tài)。時所處的狀態(tài)。2 2)后備狀態(tài):)后備狀態(tài):作業(yè)的全部信息已輸入到磁盤的一個專用區(qū)作業(yè)的全部信息已輸入到磁盤的一個專用區(qū)( (輸入井輸入井) )中等待作業(yè)調(diào)度時所處的狀態(tài)。中等待作業(yè)調(diào)度時所處的狀態(tài)。3 3)執(zhí)行狀態(tài):)執(zhí)行狀態(tài):在后備作業(yè)隊列中的作業(yè)一旦被作業(yè)調(diào)度程在后備作業(yè)隊列中的作業(yè)一旦被作業(yè)調(diào)度程序選中,為它分配了必要的資源,并且建立了進程序選中,為它分
13、配了必要的資源,并且建立了進程, , 開始開始處理時所處的狀態(tài)。處理時所處的狀態(tài)。4 4)完成狀態(tài):)完成狀態(tài):作業(yè)完成其全部任務(wù)后,進程撤消作業(yè)完成其全部任務(wù)后,進程撤消, , 做善后做善后處理時的作業(yè)狀態(tài)稱為完成狀態(tài)。處理時的作業(yè)狀態(tài)稱為完成狀態(tài)。三、作業(yè)的狀態(tài) 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖1515四、作業(yè)狀態(tài)的轉(zhuǎn)換 作業(yè)的狀態(tài)及其轉(zhuǎn)換作業(yè)的狀態(tài)及其轉(zhuǎn)換 執(zhí)執(zhí)行行 進程調(diào)度進程調(diào)度 內(nèi)存內(nèi)存 線程調(diào)度線程調(diào)度運運行行等等待待就就緒緒外存外存 就就緒緒等等待待提提交交后后備備完完成成作業(yè)輸入作業(yè)輸入 作業(yè)調(diào)度作業(yè)調(diào)度 交換調(diào)度交換調(diào)度 作業(yè)調(diào)度作業(yè)調(diào)度 執(zhí)執(zhí)行行 操作系統(tǒng) 第三章 處理
14、機調(diào)度與死鎖1616五、作業(yè)調(diào)度的功能 作業(yè)調(diào)度的主要任務(wù):作業(yè)調(diào)度的主要任務(wù):完成作業(yè)從后備狀態(tài)到運行狀態(tài)和完成作業(yè)從后備狀態(tài)到運行狀態(tài)和從運行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。從運行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。1 1)記錄系統(tǒng)中各作業(yè)的狀況)記錄系統(tǒng)中各作業(yè)的狀況。 作業(yè)調(diào)度程序應(yīng)包括以下功能:作業(yè)調(diào)度程序應(yīng)包括以下功能: 作業(yè)調(diào)度程序為了挑選一個作業(yè)投入運行,并且在運作業(yè)調(diào)度程序為了挑選一個作業(yè)投入運行,并且在運行中對它實施管理,它必須掌握該作業(yè)進入系統(tǒng)時的有關(guān)行中對它實施管理,它必須掌握該作業(yè)進入系統(tǒng)時的有關(guān)情況并隨時記錄該作業(yè)在各運行階段的變化。為此,系統(tǒng)情況并隨時記錄該作業(yè)在各運行階段的變化。為此,
15、系統(tǒng)為每一個已進入系統(tǒng)的作業(yè)分配一個為每一個已進入系統(tǒng)的作業(yè)分配一個作業(yè)控制塊作業(yè)控制塊JCBJCB(Job (Job Contrl block)Contrl block)。每個作業(yè)的。每個作業(yè)的JCBJCB在該作業(yè)進入后備狀態(tài)時在該作業(yè)進入后備狀態(tài)時由系統(tǒng)建立在該作業(yè)退出系統(tǒng)時由系統(tǒng)撤消。每個作業(yè)由系統(tǒng)建立在該作業(yè)退出系統(tǒng)時由系統(tǒng)撤消。每個作業(yè)在各階段的情況在各階段的情況( (包括分配的資源和作業(yè)狀態(tài)等包括分配的資源和作業(yè)狀態(tài)等) )都記錄在都記錄在它的它的JCBJCB中。中。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖17172) 2) 按一定的調(diào)度算法,從后備作業(yè)中挑選出一個或幾個作按一定的調(diào)度
16、算法,從后備作業(yè)中挑選出一個或幾個作業(yè)運行。業(yè)運行。 系統(tǒng)中處于后備狀態(tài)的作業(yè)較多,幾十個甚至幾百個,系統(tǒng)中處于后備狀態(tài)的作業(yè)較多,幾十個甚至幾百個,處于運行狀態(tài)的作業(yè)只是有限的幾個如最多不超過處于運行狀態(tài)的作業(yè)只是有限的幾個如最多不超過4 4個或個或8 8個。個。作業(yè)調(diào)度程序的一個重要職能就是在適當(dāng)?shù)臅r候按一定的調(diào)作業(yè)調(diào)度程序的一個重要職能就是在適當(dāng)?shù)臅r候按一定的調(diào)度原則從后備作業(yè)中挑選出若干個作業(yè)投入運行。度原則從后備作業(yè)中挑選出若干個作業(yè)投入運行。3) 3) 為被選中的作業(yè)做好執(zhí)行前的準備工作。為被選中的作業(yè)做好執(zhí)行前的準備工作。 為該作業(yè)建立相應(yīng)的進程,并且為這些進程提供所需的為該作業(yè)
17、建立相應(yīng)的進程,并且為這些進程提供所需的資源,如內(nèi)存和外部設(shè)備等。資源,如內(nèi)存和外部設(shè)備等。4) 4) 在作業(yè)執(zhí)行結(jié)束時做善后處理工作。在作業(yè)執(zhí)行結(jié)束時做善后處理工作。 輸出如運行時間、作業(yè)執(zhí)行情況等必要信息,回收該作輸出如運行時間、作業(yè)執(zhí)行情況等必要信息,回收該作業(yè)所占用的全部資源,撤消與該作業(yè)有關(guān)的全部進程和該作業(yè)所占用的全部資源,撤消與該作業(yè)有關(guān)的全部進程和該作業(yè)的作業(yè)控制塊。業(yè)的作業(yè)控制塊。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖1818六、作業(yè)調(diào)度目標與性能衡量 (1 1)公平性)公平性(2 2)均衡使用資源)均衡使用資源(3 3)較高的吞吐量)較高的吞吐量(4 4)較快的響應(yīng)時間)較快
18、的響應(yīng)時間1.1.調(diào)度目標調(diào)度目標 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖1919(1 1)周轉(zhuǎn)時間)周轉(zhuǎn)時間T Ti i = = 完成時刻完成時刻TcTci i 提交時刻提交時刻TsTsi i = = 等待時間等待時間TwTwi i + + 運行時間運行時間 TrTri i對于進入系統(tǒng)的對于進入系統(tǒng)的n n個作業(yè)而言,個作業(yè)而言,平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間T T為為用于衡量不同調(diào)度算法對同一作業(yè)流的調(diào)度性能用于衡量不同調(diào)度算法對同一作業(yè)流的調(diào)度性能:平均周轉(zhuǎn)時間越小,該作業(yè)調(diào)度算法的性能越好。平均周轉(zhuǎn)時間越小,該作業(yè)調(diào)度算法的性能越好。 2.2.調(diào)度性能衡量指標調(diào)度性能衡量指標iiiTnT11n
19、操作系統(tǒng) 第三章 處理機調(diào)度與死鎖2020(2)(2)帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間Wi = TiWi = TiTriTri它能說明作業(yè)它能說明作業(yè)i i的相對等待時間。的相對等待時間。 平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間 用于衡量同一調(diào)度算法對不同作業(yè)流的調(diào)度性能:用于衡量同一調(diào)度算法對不同作業(yè)流的調(diào)度性能:平均帶權(quán)周轉(zhuǎn)時間越小,作業(yè)調(diào)度算法對該作業(yè)流的調(diào)度平均帶權(quán)周轉(zhuǎn)時間越小,作業(yè)調(diào)度算法對該作業(yè)流的調(diào)度性能越好。性能越好。 對于批處理系統(tǒng),主要依據(jù)平均周轉(zhuǎn)時間和平均帶對于批處理系統(tǒng),主要依據(jù)平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間來作為衡量調(diào)度算法性能的指標;而對于分權(quán)周轉(zhuǎn)時間來作為衡量調(diào)度算法性能的指標
20、;而對于分時系統(tǒng)和實時系統(tǒng),外加平均響應(yīng)時間作為衡量調(diào)度算時系統(tǒng)和實時系統(tǒng),外加平均響應(yīng)時間作為衡量調(diào)度算法性能的指標。法性能的指標。 niSiiTTnW11Wi 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖2121七、作業(yè)調(diào)度算法 按作業(yè)來到的先后次序進行調(diào)度。這種算法優(yōu)先考慮按作業(yè)來到的先后次序進行調(diào)度。這種算法優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè),而不管它要求運行時間的在系統(tǒng)中等待時間最長的作業(yè),而不管它要求運行時間的長短。長短。優(yōu)點:優(yōu)點:容易實現(xiàn);容易實現(xiàn);缺點:缺點:沒有考慮各個作業(yè)運行特征和資源要求的差異,系沒有考慮各個作業(yè)運行特征和資源要求的差異,系統(tǒng)效率較低。統(tǒng)效率較低。1.1.先來先服
21、務(wù)調(diào)度算法(先來先服務(wù)調(diào)度算法(FCFSFCFS) 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖2222例:先來先服務(wù)調(diào)度算法(單位:小時,并以十進制計)例:先來先服務(wù)調(diào)度算法(單位:小時,并以十進制計)作業(yè)作業(yè)提交時間提交時間運行時間運行時間開始時間開始時間完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.0010.50 2.00 4 3 9.00 0.1010.5010.60 1.60 16 4 9.50 0.2010.6010.80 1.30 6.5平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間T T1.7251.725平均帶
22、權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間W W6.8756.875 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖23232. 2. 短作業(yè)優(yōu)先調(diào)度算法(短作業(yè)優(yōu)先調(diào)度算法(SJFSJF) 此算法總是優(yōu)先調(diào)度要求運行時間最短的作業(yè)。此算法總是優(yōu)先調(diào)度要求運行時間最短的作業(yè)。優(yōu)點:優(yōu)點:易于實現(xiàn),效率比較高。易于實現(xiàn),效率比較高。缺點:缺點:只照顧短作業(yè)而不考慮長作業(yè)的利益。只照顧短作業(yè)而不考慮長作業(yè)的利益。 如果系統(tǒng)不斷地接受新的短作業(yè)。則有可能較長作業(yè)如果系統(tǒng)不斷地接受新的短作業(yè)。則有可能較長作業(yè)長時間等待而不能運行。長時間等待而不能運行。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖2424例:短作業(yè)優(yōu)先調(diào)度算法(單位:小時
23、,并以十進制計)例:短作業(yè)優(yōu)先調(diào)度算法(單位:小時,并以十進制計)作業(yè)作業(yè)提交時間提交時間運行時間運行時間開始時間開始時間完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.3010.80 2.30 4.6 3 9.00 0.1010.0010.10 1.10 11 4 9.50 0.2010.1010.30 0.80 4平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間T T1.551.55平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間W W5.155.15 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖25253. 3. 響應(yīng)比高者優(yōu)先調(diào)度算法響應(yīng)比
24、高者優(yōu)先調(diào)度算法 響應(yīng)比是指作業(yè)的響應(yīng)時間與作業(yè)估計運行時間的比響應(yīng)比是指作業(yè)的響應(yīng)時間與作業(yè)估計運行時間的比值。值。執(zhí)執(zhí)行行時時間間響響應(yīng)應(yīng)時時間間響響應(yīng)應(yīng)比比 選擇原則是優(yōu)先選取響應(yīng)比值最大的作業(yè)。即兼顧等選擇原則是優(yōu)先選取響應(yīng)比值最大的作業(yè)。即兼顧等待時間長和運行時間短的作業(yè),它是待時間長和運行時間短的作業(yè),它是FCFSFCFS和和SJFSJF算法的結(jié)合。算法的結(jié)合。響應(yīng)比響應(yīng)比1 1作業(yè)等待時間作業(yè)等待時間/ /執(zhí)行時間執(zhí)行時間 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖2626 作業(yè)作業(yè)提交時間提交時間運行時間運行時間開始時間開始時間完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間
25、1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.1010.60 2.10 4.2 3 9.00 0.1010.0010.10 1.10 11 4 9.50 0.2010.6010.80 1.30 6.5例:響應(yīng)比高者優(yōu)先調(diào)度算法(單位:小時,并以十進制計例:響應(yīng)比高者優(yōu)先調(diào)度算法(單位:小時,并以十進制計) )平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間T T1.6251.625, 平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間W W5.6755.675 響應(yīng)比響應(yīng)比1 1作業(yè)等待時間作業(yè)等待時間/ /執(zhí)行時間執(zhí)行時間例如:當(dāng)作業(yè)例如:當(dāng)作業(yè)3 3結(jié)束時,結(jié)束時,Rp2= 1Rp2= 1作
26、業(yè)等待時間作業(yè)等待時間/ /可執(zhí)行時間可執(zhí)行時間=1+(10.10-8.50)/0.5=1+3.2=1+(10.10-8.50)/0.5=1+3.2Rp4= 1Rp4= 1作業(yè)等待時間作業(yè)等待時間/ /可執(zhí)行時間可執(zhí)行時間=1+(10.10-9.50)/0.2=1+3=1+(10.10-9.50)/0.2=1+3 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖2727 這種算法是根據(jù)確定的優(yōu)先數(shù)來選取作業(yè),每次總是選這種算法是根據(jù)確定的優(yōu)先數(shù)來選取作業(yè),每次總是選擇優(yōu)先級最高的作業(yè)。擇優(yōu)先級最高的作業(yè)。 4.4.最高優(yōu)先級優(yōu)先調(diào)度算法最高優(yōu)先級優(yōu)先調(diào)度算法規(guī)定用戶作業(yè)優(yōu)先數(shù)的方法規(guī)定用戶作業(yè)優(yōu)先數(shù)的方法:
27、 :1 1)由用戶自己提出作業(yè)的優(yōu)先數(shù)。)由用戶自己提出作業(yè)的優(yōu)先數(shù)。有的用戶為了自己的作業(yè)有的用戶為了自己的作業(yè)盡快被系統(tǒng)選中就設(shè)法提高自己作業(yè)的優(yōu)先數(shù),這時系統(tǒng)可以盡快被系統(tǒng)選中就設(shè)法提高自己作業(yè)的優(yōu)先數(shù),這時系統(tǒng)可以規(guī)定優(yōu)先數(shù)越高則需付出的計算機使用費就越多,以作限制。規(guī)定優(yōu)先數(shù)越高則需付出的計算機使用費就越多,以作限制。2 2)由系統(tǒng)綜合有關(guān)因素來確定用戶作業(yè)的優(yōu)先數(shù)。)由系統(tǒng)綜合有關(guān)因素來確定用戶作業(yè)的優(yōu)先數(shù)。 例如,根據(jù)作業(yè)的緩急程度、作業(yè)計算時間的長短、等待例如,根據(jù)作業(yè)的緩急程度、作業(yè)計算時間的長短、等待時間的多少、資源申請情況等來確定優(yōu)先數(shù)。確定優(yōu)先數(shù)時,時間的多少、資源申請
28、情況等來確定優(yōu)先數(shù)。確定優(yōu)先數(shù)時,各因素的比例應(yīng)根據(jù)系統(tǒng)設(shè)計目標來分析這些因素在系統(tǒng)中的各因素的比例應(yīng)根據(jù)系統(tǒng)設(shè)計目標來分析這些因素在系統(tǒng)中的地位而決定。地位而決定。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖28283.3 進程調(diào)度進程調(diào)度:進程調(diào)度:就是系統(tǒng)按照某種算法把就是系統(tǒng)按照某種算法把CPUCPU動態(tài)地分配給某一就動態(tài)地分配給某一就緒進程。進程調(diào)度工作是通過進程調(diào)度程序來完成的。緒進程。進程調(diào)度工作是通過進程調(diào)度程序來完成的。一、調(diào)度/分派結(jié)構(gòu)調(diào)度程序:調(diào)度程序:將進程插入就緒隊列,按一定原則保持隊列結(jié)構(gòu);將進程插入就緒隊列,按一定原則保持隊列結(jié)構(gòu);分派程序:分派程序:將進程從就緒隊列中移
29、出,建立它執(zhí)行的機器狀態(tài)。將進程從就緒隊列中移出,建立它執(zhí)行的機器狀態(tài)。進程切換進程切換:把一個進程讓出處理機,由另一個進程占用處理機把一個進程讓出處理機,由另一個進程占用處理機的調(diào)度過程稱為的調(diào)度過程稱為“進程切換進程切換”。 分派程序首先將正在執(zhí)行的進程的分派程序首先將正在執(zhí)行的進程的CPUCPU現(xiàn)場信息保存在該進現(xiàn)場信息保存在該進程程PCBPCB的現(xiàn)場保護區(qū)中,再從被調(diào)度選中的進程的現(xiàn)場保護區(qū)中,再從被調(diào)度選中的進程PCBPCB的現(xiàn)場保護的現(xiàn)場保護區(qū)中取出它的區(qū)中取出它的CPUCPU現(xiàn)場信息恢復(fù)?,F(xiàn)場信息恢復(fù)。CPUCPU現(xiàn)場信息由程序狀態(tài)寄存現(xiàn)場信息由程序狀態(tài)寄存器、程序計數(shù)器以及若干
30、通用寄存器的內(nèi)容組成。器、程序計數(shù)器以及若干通用寄存器的內(nèi)容組成。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖29291.1.記錄系統(tǒng)中所有進程的執(zhí)行情況。記錄系統(tǒng)中所有進程的執(zhí)行情況。 二、進程調(diào)度功能 記錄系統(tǒng)中所有進程的有關(guān)情況,對進程控制塊記錄系統(tǒng)中所有進程的有關(guān)情況,對進程控制塊PCBPCB的內(nèi)的內(nèi)容作相應(yīng)的登記、修改,記錄進程的狀態(tài)特征。容作相應(yīng)的登記、修改,記錄進程的狀態(tài)特征。2.2.按照一定調(diào)度策略選擇一個占有處理機的就緒進程。按照一定調(diào)度策略選擇一個占有處理機的就緒進程。 在處理機空閑時根據(jù)一定的原則選擇一個進程去運行,在處理機空閑時根據(jù)一定的原則選擇一個進程去運行,同時確定獲得處理
31、機的時間。同時確定獲得處理機的時間。3.3.實施處理機的分配和回收實施處理機的分配和回收( (進行進程上下文切換進行進程上下文切換)?;厥栈厥? :正在運行的進程由于某種原因讓出處理機,該進程的狀正在運行的進程由于某種原因讓出處理機,該進程的狀態(tài)改為態(tài)改為“阻塞阻塞”,插入到相應(yīng)隊列中,保留該進程的,插入到相應(yīng)隊列中,保留該進程的CPUCPU現(xiàn)場?,F(xiàn)場。分配分配: :根據(jù)調(diào)度原則選擇進程去運行,把選中進程從就緒隊列中根據(jù)調(diào)度原則選擇進程去運行,把選中進程從就緒隊列中移出移出, ,改狀態(tài)為改狀態(tài)為“運行運行”,把,把CPUCPU控制權(quán)交給被選中的進程,將控制權(quán)交給被選中的進程,將選中進程的有關(guān)選
32、中進程的有關(guān)PCBPCB現(xiàn)場信息,分別送到相應(yīng)的寄存器中?,F(xiàn)場信息,分別送到相應(yīng)的寄存器中。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖3030三、進程調(diào)度時機 1 1)正在執(zhí)行的進程完成其任務(wù)而正在執(zhí)行的進程完成其任務(wù)而運行完畢運行完畢。 2 2)執(zhí)行中的進程由于執(zhí)行中的進程由于請求某個事件的發(fā)生請求某個事件的發(fā)生,比如,比如I/OI/O請求,請求,等待所需要的信號、信件的到來等而自己調(diào)用等待所需要的信號、信件的到來等而自己調(diào)用阻塞阻塞原語將自原語將自己阻塞起來,進入相應(yīng)的等待隊列。己阻塞起來,進入相應(yīng)的等待隊列。 3 3)在分時系統(tǒng)中,當(dāng)進程使在分時系統(tǒng)中,當(dāng)進程使用完規(guī)定的時間片用完規(guī)定的時間片
33、。 4 4)在在采用可搶占采用可搶占調(diào)度方式的系統(tǒng)中,當(dāng)具有更高優(yōu)先級的調(diào)度方式的系統(tǒng)中,當(dāng)具有更高優(yōu)先級的進程要求使用處理機。進程要求使用處理機。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖3131四、進程調(diào)度算法 采用最高優(yōu)先級優(yōu)先調(diào)度算法時,系統(tǒng)對每個進程確采用最高優(yōu)先級優(yōu)先調(diào)度算法時,系統(tǒng)對每個進程確定一個優(yōu)先數(shù),進程的優(yōu)先數(shù)用于表示進程的重要性及運定一個優(yōu)先數(shù),進程的優(yōu)先數(shù)用于表示進程的重要性及運行的優(yōu)先性。調(diào)度時,系統(tǒng)把處理機分配給優(yōu)先級最高的行的優(yōu)先性。調(diào)度時,系統(tǒng)把處理機分配給優(yōu)先級最高的就緒進程。如果就緒進程具有相同的優(yōu)先數(shù),則再按先來就緒進程。如果就緒進程具有相同的優(yōu)先數(shù),則再按先
34、來先服務(wù)的次序分配處理機。先服務(wù)的次序分配處理機。 先來先服務(wù)調(diào)度算法是按照進程進入就緒隊列的先后先來先服務(wù)調(diào)度算法是按照進程進入就緒隊列的先后次序來選擇進程分配處理機。次序來選擇進程分配處理機。(一)最高優(yōu)先級優(yōu)先調(diào)度算法 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖3232系統(tǒng)確定優(yōu)先數(shù)的方法: 1.1.靜態(tài)優(yōu)先數(shù)法:靜態(tài)優(yōu)先數(shù)法:靜態(tài)優(yōu)先數(shù)是在創(chuàng)建進程時系統(tǒng)為其確靜態(tài)優(yōu)先數(shù)是在創(chuàng)建進程時系統(tǒng)為其確定的,并且在進程的生命期內(nèi)不再改變。定的,并且在進程的生命期內(nèi)不再改變。 確定靜態(tài)優(yōu)先數(shù)的原則:確定靜態(tài)優(yōu)先數(shù)的原則:1 1)按進程類型。)按進程類型。系統(tǒng)進程的優(yōu)先級高于用戶進程的優(yōu)先級。系統(tǒng)進程的優(yōu)先
35、級高于用戶進程的優(yōu)先級。 2 2)按進程使用的資源。)按進程使用的資源。進程所使用的資源越多,進程的優(yōu)進程所使用的資源越多,進程的優(yōu)先級越低;反之,則進程的優(yōu)先級越高。先級越低;反之,則進程的優(yōu)先級越高。 3 3)按進程的估計運行時間。)按進程的估計運行時間。進程的估計運行時間越長,進進程的估計運行時間越長,進程的優(yōu)先級越低;反之,則進程的優(yōu)先級越高。程的優(yōu)先級越低;反之,則進程的優(yōu)先級越高。 4 4)由用戶指定。)由用戶指定。有些系統(tǒng)可以按收費標準不同,設(shè)置不同的有些系統(tǒng)可以按收費標準不同,設(shè)置不同的優(yōu)先級別,可以由用戶指定。優(yōu)先級別,可以由用戶指定。 靜態(tài)優(yōu)先級法實現(xiàn)起來比較簡單,但不能反
36、映系統(tǒng)以及進程靜態(tài)優(yōu)先級法實現(xiàn)起來比較簡單,但不能反映系統(tǒng)以及進程在運行過程中的動態(tài)變化情況,系統(tǒng)管理效果顯然不佳。在運行過程中的動態(tài)變化情況,系統(tǒng)管理效果顯然不佳。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖33332. 2. 動態(tài)優(yōu)先數(shù)法。動態(tài)優(yōu)先數(shù)法。動態(tài)優(yōu)先數(shù)是指在系統(tǒng)創(chuàng)建進程時,根動態(tài)優(yōu)先數(shù)是指在系統(tǒng)創(chuàng)建進程時,根據(jù)系統(tǒng)資源的使用情況和進程的當(dāng)前特點確定一個優(yōu)先數(shù),據(jù)系統(tǒng)資源的使用情況和進程的當(dāng)前特點確定一個優(yōu)先數(shù),然后,在進程運行過程中再根據(jù)情況的變化動態(tài)調(diào)整進程的然后,在進程運行過程中再根據(jù)情況的變化動態(tài)調(diào)整進程的優(yōu)先數(shù)。優(yōu)先數(shù)。 調(diào)整進程優(yōu)先數(shù)的原調(diào)整進程優(yōu)先數(shù)的原則:則: 1 1)進
37、程占有處理機的時間越長,則進程的優(yōu)先級越低;進程)進程占有處理機的時間越長,則進程的優(yōu)先級越低;進程的等待時間越長,則進程的優(yōu)先級越高。的等待時間越長,則進程的優(yōu)先級越高。 2 2)根據(jù)進程所執(zhí)行的程序的輕重緩急程度,調(diào)整進程的優(yōu)先)根據(jù)進程所執(zhí)行的程序的輕重緩急程度,調(diào)整進程的優(yōu)先數(shù)。數(shù)。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖3434優(yōu)先權(quán)的變化規(guī)律:優(yōu)先權(quán)的變化規(guī)律: (1) (1) 如果進程(作業(yè))的等待時間相同,則要求服如果進程(作業(yè))的等待時間相同,則要求服務(wù)的時間愈短,其優(yōu)先權(quán)愈高,因而該算法有利于短進務(wù)的時間愈短,其優(yōu)先權(quán)愈高,因而該算法有利于短進程(作業(yè))。程(作業(yè))。 (2)
38、(2) 當(dāng)要求服務(wù)的時間相同時,進程(作業(yè))的優(yōu)當(dāng)要求服務(wù)的時間相同時,進程(作業(yè))的優(yōu)先權(quán)決定于其等待時間,等待時間愈長,其優(yōu)先權(quán)愈高,先權(quán)決定于其等待時間,等待時間愈長,其優(yōu)先權(quán)愈高,因而它實現(xiàn)的是先來先服務(wù)。因而它實現(xiàn)的是先來先服務(wù)。 (3) (3) 對于長進程(作業(yè)),進程(作業(yè))的優(yōu)先級對于長進程(作業(yè)),進程(作業(yè))的優(yōu)先級可以隨等待時間的增加而提高,當(dāng)其等待時間足夠長時,可以隨等待時間的增加而提高,當(dāng)其等待時間足夠長時,其優(yōu)先級便可升到很高,其優(yōu)先級便可升到很高, 從而也可獲得處理機(進入主從而也可獲得處理機(進入主存)。存)。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖3535(二)時
39、間片輪轉(zhuǎn)調(diào)度算法 在分時系統(tǒng)中,為了滿足系統(tǒng)對響應(yīng)時間的要求,通在分時系統(tǒng)中,為了滿足系統(tǒng)對響應(yīng)時間的要求,通常采用時間片輪轉(zhuǎn)調(diào)度算法。常采用時間片輪轉(zhuǎn)調(diào)度算法。 1. 簡單輪轉(zhuǎn)法(固定時間片輪轉(zhuǎn)法) 在這種調(diào)度算法中,系統(tǒng)把所有就緒進程按到達的先在這種調(diào)度算法中,系統(tǒng)把所有就緒進程按到達的先后順序形成一個就緒隊列,就緒隊列中的所有進程按時間后順序形成一個就緒隊列,就緒隊列中的所有進程按時間片依次輪流獲得處理機。片依次輪流獲得處理機。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖3636 時間片的大小應(yīng)根據(jù)進程要求系統(tǒng)給出應(yīng)答的時間和進時間片的大小應(yīng)根據(jù)進程要求系統(tǒng)給出應(yīng)答的時間和進入系統(tǒng)的進程數(shù)來決定
40、。可以表示為:入系統(tǒng)的進程數(shù)來決定。可以表示為: N NT Tq q 其中,其中,q q是時間片的大小,是時間片的大小,T T是系統(tǒng)的響應(yīng)時間,是系統(tǒng)的響應(yīng)時間,N N是進入系統(tǒng)是進入系統(tǒng)的進程數(shù)。的進程數(shù)。 簡單輪轉(zhuǎn)法的優(yōu)點是簡單、方便,但由于采用固定時間簡單輪轉(zhuǎn)法的優(yōu)點是簡單、方便,但由于采用固定時間片的方式,調(diào)度欠靈活,服務(wù)質(zhì)量不夠理想。可以通過以下片的方式,調(diào)度欠靈活,服務(wù)質(zhì)量不夠理想??梢酝ㄟ^以下兩個方面加以改進:兩個方面加以改進:1 1)將固定時間片方式改為可變時間片方式;)將固定時間片方式改為可變時間片方式;2 2)將單就緒隊列改為多就緒隊列。)將單就緒隊列改為多就緒隊列。 操作
41、系統(tǒng) 第三章 處理機調(diào)度與死鎖37372. 可變時間片輪轉(zhuǎn)法 時間片可變會給系統(tǒng)帶來好處。如果要求系統(tǒng)快速應(yīng)時間片可變會給系統(tǒng)帶來好處。如果要求系統(tǒng)快速應(yīng)答,則時間片小一些,這樣可使輪轉(zhuǎn)一遍的總時間減少而答,則時間片小一些,這樣可使輪轉(zhuǎn)一遍的總時間減少而可對進程盡快應(yīng)答。如果進程數(shù)少,則時間片可以大一些,可對進程盡快應(yīng)答。如果進程數(shù)少,則時間片可以大一些,這樣可減少進程調(diào)度的次數(shù),提高系統(tǒng)效率。這樣可減少進程調(diào)度的次數(shù),提高系統(tǒng)效率。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖3838可變時間片輪轉(zhuǎn)法中,可采取如下措施調(diào)整時間片:可變時間片輪轉(zhuǎn)法中,可采取如下措施調(diào)整時間片: 1) 1) 固定周期輪轉(zhuǎn)
42、法。固定周期輪轉(zhuǎn)法。 在這種方法中,每一輪調(diào)度中所得的時間片在這種方法中,每一輪調(diào)度中所得的時間片q q值的大值的大小僅在這一輪調(diào)度中有效。系統(tǒng)的響應(yīng)時間小僅在這一輪調(diào)度中有效。系統(tǒng)的響應(yīng)時間T T固定,在每一固定,在每一輪調(diào)度中,根據(jù)當(dāng)前就緒隊列中的進程數(shù)輪調(diào)度中,根據(jù)當(dāng)前就緒隊列中的進程數(shù)n n計算這一輪調(diào)度計算這一輪調(diào)度的時間片:的時間片:q qT/ n T/ n , 然后進行輪轉(zhuǎn),每個進程可獲得然后進行輪轉(zhuǎn),每個進程可獲得這一輪的一個時間片這一輪的一個時間片q q。在此期間所到達的進程暫不進入。在此期間所到達的進程暫不進入就緒隊列,等此次輪轉(zhuǎn)完畢再一并進入。系統(tǒng)根據(jù)此時就緒就緒隊列,等
43、此次輪轉(zhuǎn)完畢再一并進入。系統(tǒng)根據(jù)此時就緒隊列的進程數(shù)重新計算時間片隊列的進程數(shù)重新計算時間片q q,然后開始下一輪循環(huán)。,然后開始下一輪循環(huán)。 2) 2) 時間片的大小取決于優(yōu)先級的高低時間片的大小取決于優(yōu)先級的高低,優(yōu)先級高的進程分,優(yōu)先級高的進程分得的時間片較大,優(yōu)先級低的進程分得的時間片較小。得的時間片較大,優(yōu)先級低的進程分得的時間片較小。 3) 3) 短作業(yè)的時間片較小,短作業(yè)的時間片較小,長作業(yè)的時間片較大。長作業(yè)的時間片較大。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖39393.多級反饋輪轉(zhuǎn)法(多重時間片輪轉(zhuǎn)調(diào)度算法) 調(diào)度算法的實施過程如下:調(diào)度算法的實施過程如下: 1. 1. 設(shè)置多
44、個就緒隊列,設(shè)置多個就緒隊列,并為各個就緒隊列賦予不同的優(yōu)先并為各個就緒隊列賦予不同的優(yōu)先級。第一個就緒隊列的優(yōu)先級最高,第二個就緒隊列的優(yōu)先級。第一個就緒隊列的優(yōu)先級最高,第二個就緒隊列的優(yōu)先級次之,其余各個就緒隊列的優(yōu)先級逐個降低。級次之,其余各個就緒隊列的優(yōu)先級逐個降低。2.2.賦予各個就緒隊列中進程賦予各個就緒隊列中進程的時間片也各不相同,優(yōu)先級越的時間片也各不相同,優(yōu)先級越高的就緒隊列中的進程的時間片越小,反之,優(yōu)先級越低的高的就緒隊列中的進程的時間片越小,反之,優(yōu)先級越低的就緒隊列中的進程的時間片越大。就緒隊列中的進程的時間片越大。 3.3.當(dāng)一個新被創(chuàng)建的進程當(dāng)一個新被創(chuàng)建的進程
45、進入就緒隊列后,首先將它加入第進入就緒隊列后,首先將它加入第一個就緒隊列的隊尾,按先來先服務(wù)的原則排隊等待調(diào)度。一個就緒隊列的隊尾,按先來先服務(wù)的原則排隊等待調(diào)度。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4040 當(dāng)輪到該進程執(zhí)行時,如能在該時間片內(nèi)完成,則該進當(dāng)輪到該進程執(zhí)行時,如能在該時間片內(nèi)完成,則該進程將被撤消;如果在一個時間片結(jié)束時該進程尚未完成,調(diào)程將被撤消;如果在一個時間片結(jié)束時該進程尚未完成,調(diào)度程序則將該進程轉(zhuǎn)入第二個就緒隊列的隊尾,按先來先服度程序則將該進程轉(zhuǎn)入第二個就緒隊列的隊尾,按先來先服務(wù)的原則排隊等待調(diào)度;如果它在第二個就緒隊列中運行一務(wù)的原則排隊等待調(diào)度;如果它在第二
46、個就緒隊列中運行一個時間片后仍未完成,再以同樣的方法將它轉(zhuǎn)入第三個就緒個時間片后仍未完成,再以同樣的方法將它轉(zhuǎn)入第三個就緒隊列的隊尾,隊列的隊尾, 如此下去。如此下去。4.4.僅當(dāng)?shù)谝粋€就緒隊列空閑時,僅當(dāng)?shù)谝粋€就緒隊列空閑時,調(diào)度程序才調(diào)度第二個就緒調(diào)度程序才調(diào)度第二個就緒隊列中的進程運行;僅當(dāng)?shù)陉犃兄械倪M程運行;僅當(dāng)?shù)? 1至第至第i i1 1個就緒隊列均為空時,個就緒隊列均為空時,才會調(diào)度第才會調(diào)度第i i個就緒隊列中的進程運行。個就緒隊列中的進程運行。如果處理機正在第如果處理機正在第i i個就緒隊列中為某進程服務(wù)時,又有新進程進入優(yōu)先級較高個就緒隊列中為某進程服務(wù)時,又有新進程進入優(yōu)先
47、級較高的就緒隊列時,則此時新進程將搶占正在運行進程的處理機,的就緒隊列時,則此時新進程將搶占正在運行進程的處理機,即由調(diào)度程序把正在運行的進程放回到第即由調(diào)度程序把正在運行的進程放回到第i i個就緒隊列的隊個就緒隊列的隊尾,然后將處理機重新分配給新進程。尾,然后將處理機重新分配給新進程。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4141多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至CPU至CPU至CPU至CPU(時間片: S1 S2 S3) 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖42423.4 死鎖 一、死鎖的概念死鎖:死鎖:各并發(fā)進程彼此互相等
48、待對方所擁有的資源,且這各并發(fā)進程彼此互相等待對方所擁有的資源,且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成系統(tǒng)中一些進程處于無休止的等待狀態(tài),資源。從而造成系統(tǒng)中一些進程處于無休止的等待狀態(tài),在無外力作用的情況下,這些進程永遠也不能繼續(xù)前進。在無外力作用的情況下,這些進程永遠也不能繼續(xù)前進。我們稱這種現(xiàn)象為我們稱這種現(xiàn)象為死鎖死鎖。例:例:系統(tǒng)中只有一臺輸入機系統(tǒng)中只有一臺輸入機R1R1和一臺打印機和一臺打印機R2R2可供進程可供進程P1P1和和P2P2共享。共享。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4343進程進程P
49、1 P1 進程進程P2P2 請求資源請求資源R1 R1 請求資源請求資源R2R2 請求資源請求資源R2 R2 請求資源請求資源R1R1 釋放資源釋放資源R1 R1 釋放資源釋放資源R2 R2 釋放資源釋放資源R2 R2 釋放資源釋放資源R1R1 R1R1R2R2 兩個進程死鎖的典型情況兩個進程死鎖的典型情況 死鎖死鎖R1R2 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4444 進程在同步和通信的過程進程在同步和通信的過程當(dāng)中也會產(chǎn)生死鎖。當(dāng)中也會產(chǎn)生死鎖。 例如,在生產(chǎn)者例如,在生產(chǎn)者消費者消費者問題中,若把生產(chǎn)者進程中兩問題中,若把生產(chǎn)者進程中兩個個P P操作的順序顛倒如下圖所示:操作的順序顛倒如下
50、圖所示: 生產(chǎn)者進程生產(chǎn)者進程Pi Pi 生產(chǎn)一個產(chǎn)品生產(chǎn)一個產(chǎn)品 產(chǎn)品送入緩沖區(qū)產(chǎn)品送入緩沖區(qū) P(avail) P(avail) P(mutex)P(mutex) V(mutex) V(mutex) V(full)V(full) 在這種情況下,當(dāng)緩沖區(qū)在這種情況下,當(dāng)緩沖區(qū)都已放滿了產(chǎn)品時,生產(chǎn)者仍都已放滿了產(chǎn)品時,生產(chǎn)者仍可執(zhí)行可執(zhí)行P(mutex)操作,于是操作,于是該生產(chǎn)者掌握了對緩沖區(qū)的存該生產(chǎn)者掌握了對緩沖區(qū)的存取 控 制 權(quán) , 當(dāng) 它 繼 續(xù) 執(zhí) 行取 控 制 權(quán) , 當(dāng) 它 繼 續(xù) 執(zhí) 行P(avail)P(avail)操作時,由于沒有空操作時,由于沒有空緩沖區(qū),該生產(chǎn)者被
51、阻塞,并緩沖區(qū),該生產(chǎn)者被阻塞,并在在avail上等待。上等待。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4545若此時有一個消費者到達,盡管緩沖區(qū)中有產(chǎn)品,消費者在若此時有一個消費者到達,盡管緩沖區(qū)中有產(chǎn)品,消費者在執(zhí)行執(zhí)行P(full)P(full)操作時通過,但緊接著執(zhí)行操作時通過,但緊接著執(zhí)行P(mutex)P(mutex)操作時,將操作時,將因緩沖區(qū)已被阻塞的生產(chǎn)者所占有,而使消費者無法獲得緩因緩沖區(qū)已被阻塞的生產(chǎn)者所占有,而使消費者無法獲得緩沖區(qū)的存取控制權(quán)而被阻塞。此時,出現(xiàn)了生產(chǎn)者和消費者沖區(qū)的存取控制權(quán)而被阻塞。此時,出現(xiàn)了生產(chǎn)者和消費者之間僵死的局面,亦即發(fā)生了死鎖。之間僵死的局
52、面,亦即發(fā)生了死鎖。二、產(chǎn)生死鎖的原因 產(chǎn)生的產(chǎn)生的根本原因根本原因是系統(tǒng)能夠提供的資源數(shù)少于需要該是系統(tǒng)能夠提供的資源數(shù)少于需要該資源的進程數(shù)資源的進程數(shù)( (系統(tǒng)資源不足系統(tǒng)資源不足) )。 1 1)對資源的分配策略(請求順序)不當(dāng))對資源的分配策略(請求順序)不當(dāng) ; 2 2)進程推進順序非法。)進程推進順序非法。 死鎖起因是并發(fā)進程的資源競爭。死鎖起因是并發(fā)進程的資源競爭。 可剝奪性資源可剝奪性資源 非剝奪性資源非剝奪性資源 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4646 P1P1和和P2P2都占用都占用R1R1 P1 P1和和P2P2都占用都占用R2R2 P2P2的進展的進展 P1P1的
53、進展的進展 占用占用R1 R1 占用占用R2 R2 釋放釋放R1 R1 釋放釋放R2 R2 請求請求R1 R1 請求請求R2 R2 請求請求R1R1 請求請求R2 R2 釋放釋放R1R1 釋放釋放R2R2 占用占用R1 R1 1 1 2 2 3 3 占用占用R2R2下面用圖示來說明進程下面用圖示來說明進程P1P1和和P2P2的三種可能的進展情況:的三種可能的進展情況: 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4747三、死鎖存在的必要條件1 1)互斥條件。)互斥條件。進程對其所要求的資源進行排它性控制,進程對其所要求的資源進行排它性控制,即一次只有一個進程可以使用一個資源。即一次只有一個進程可以使用
54、一個資源。2 2)不剝奪條件。)不剝奪條件。進程所獲得進程所獲得的資源在未被釋放之前,不能被的資源在未被釋放之前,不能被其它進程強行剝奪。其它進程強行剝奪。3 3)占有且等待條件)占有且等待條件。進程每。進程每次申請它所需要的一部分資源,次申請它所需要的一部分資源,在進程等待分配其它資源的同時,在進程等待分配其它資源的同時,可以占有已分配的資源??梢哉加幸逊峙涞馁Y源。 P1P1P2P2 R1 R1 R2 R2被占有被占有 被占有被占有 請求請求 請求請求 4 4)環(huán)路條件。)環(huán)路條件。在發(fā)生死鎖時,必然存在一個進程資源的在發(fā)生死鎖時,必然存在一個進程資源的循環(huán)等待鏈,循環(huán)等待鏈, 操作系統(tǒng) 第
55、三章 處理機調(diào)度與死鎖4848四、解決死鎖的方法(一)死鎖的防止(一)死鎖的防止( (預(yù)防預(yù)防) ) 1 1破壞互斥條件破壞互斥條件 為了破壞資源使用的互斥條件,就要允許多個進程同為了破壞資源使用的互斥條件,就要允許多個進程同時訪問共享資源。但是這種方法受到資源本身固有特性的時訪問共享資源。但是這種方法受到資源本身固有特性的限制,對某些資源是行不通的。例如打印機,就不允許多限制,對某些資源是行不通的。例如打印機,就不允許多個進程在其運行期間交替打印數(shù)據(jù),打印機只能互斥使用。個進程在其運行期間交替打印數(shù)據(jù),打印機只能互斥使用。而文件,可能允許多個進程對其進行讀訪問,但只允許互而文件,可能允許多個
56、進程對其進行讀訪問,但只允許互斥地寫訪問。因此,互斥條件難以破壞。斥地寫訪問。因此,互斥條件難以破壞。 死鎖的防止是通過設(shè)置某些嚴格的限制條件,以破壞死鎖的防止是通過設(shè)置某些嚴格的限制條件,以破壞產(chǎn)生死鎖的必要條件來防止死鎖的發(fā)生。產(chǎn)生死鎖的必要條件來防止死鎖的發(fā)生。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖4949 2 2破壞不剝奪條件破壞不剝奪條件 該策略規(guī)定,一個已保持了某些資源的進程,若新的資該策略規(guī)定,一個已保持了某些資源的進程,若新的資源要求不能立即得到滿足,它必須釋放已保持的所有資源。源要求不能立即得到滿足,它必須釋放已保持的所有資源。以后再需要時重新申請。這意味著,一個進程已占有的資
57、源,以后再需要時重新申請。這意味著,一個進程已占有的資源,在運行過程中可能暫時地釋放,或說被剝奪。在運行過程中可能暫時地釋放,或說被剝奪。問題:問題:1 1)這種防止死鎖的策略實現(xiàn)起來比較復(fù)雜;)這種防止死鎖的策略實現(xiàn)起來比較復(fù)雜;2 2)一個資源在使用一段時間后被釋放,可能會造成前階段)一個資源在使用一段時間后被釋放,可能會造成前階段工作的失效,即使采取某些防范措施,也還會使前后兩次運工作的失效,即使采取某些防范措施,也還會使前后兩次運行的信息不連續(xù)。行的信息不連續(xù)。3 3)該策略還可能由于反復(fù)地申請和釋放資源,使進程的執(zhí))該策略還可能由于反復(fù)地申請和釋放資源,使進程的執(zhí)行無限推遲。這不僅延
58、長了進程的周轉(zhuǎn)時間,還增加了系統(tǒng)行無限推遲。這不僅延長了進程的周轉(zhuǎn)時間,還增加了系統(tǒng)開銷,又降低了系統(tǒng)吞吐量。開銷,又降低了系統(tǒng)吞吐量。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖5050 3 3破壞占有且等待條件破壞占有且等待條件-資源的靜態(tài)分配策略資源的靜態(tài)分配策略 系統(tǒng)要求所有進程一次性地申請其所需的全部資源。若系統(tǒng)要求所有進程一次性地申請其所需的全部資源。若系統(tǒng)有足夠的資源分配給該進程時,便一次把所有其所需的系統(tǒng)有足夠的資源分配給該進程時,便一次把所有其所需的資源分配給該進程。這樣,該進程在整個運行期間,便不會資源分配給該進程。這樣,該進程在整個運行期間,便不會再提出任何資源要求,從而使請求條
59、件不成立。但在分配時再提出任何資源要求,從而使請求條件不成立。但在分配時只要有一種資源要求不能滿足,則已有的其它資源也全部不只要有一種資源要求不能滿足,則已有的其它資源也全部不分配給該進程,該進程只能等待。由于等待期間的進程不占分配給該進程,該進程只能等待。由于等待期間的進程不占有任何資源,因此,破壞了必要條件之有任何資源,因此,破壞了必要條件之3 3,防止了死鎖發(fā)生。,防止了死鎖發(fā)生。 破壞占有且等待條件破壞占有且等待條件-資單請求方式分配資源資單請求方式分配資源優(yōu)點:優(yōu)點:簡單、易于實現(xiàn),且很安全。簡單、易于實現(xiàn),且很安全。 操作系統(tǒng) 第三章 處理機調(diào)度與死鎖5151缺點:缺點:1 1)資
60、源嚴重浪費。)資源嚴重浪費。 一個進程一次獲得其所需的全部資源且獨占,其中可一個進程一次獲得其所需的全部資源且獨占,其中可能有些資源很少使用,甚至在整個運行期間都未使用,這能有些資源很少使用,甚至在整個運行期間都未使用,這就嚴重地惡化了系統(tǒng)資源利用率:就嚴重地惡化了系統(tǒng)資源利用率:2 2)進程延遲運行。)進程延遲運行。 僅當(dāng)進程獲得其所需全部資源后,方能開始運行,但僅當(dāng)進程獲得其所需全部資源后,方能開始運行,但可能有許多資源長期被其它進程占用,致使進程推遲運行,可能有許多資源長期被其它進程占用,致使進程推遲運行,這往往要經(jīng)過很長的時延。這往往要經(jīng)過很長的時延。 操作系統(tǒng) 第三章 處理機調(diào)度與死
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 賀州昭平縣中考數(shù)學(xué)試卷
- 護理溝通心理學(xué)
- 核按鈕2024數(shù)學(xué)試卷
- 人工智能時代的文學(xué)創(chuàng)作-生成式文學(xué)與人類作者的互動-洞察及研究
- 貴州的初二數(shù)學(xué)試卷
- 2025-2030中國油氣設(shè)備用高速發(fā)電機行業(yè)市場發(fā)展趨勢與前景展望戰(zhàn)略研究報告
- 2025-2030中國橋梁鋼板行業(yè)市場發(fā)展現(xiàn)狀及發(fā)展趨勢與投資研究報告
- 邯鄲中考數(shù)學(xué)試卷
- 江蘇6下數(shù)學(xué)試卷
- 中班健康課:我會保護自己
- 2025年廣東省中考英語試題卷(含答案解析)
- 2025年吉林省中考物理試卷真題及答案詳解(精校打印版)
- 浙江省城市體檢工作技術(shù)導(dǎo)則(試行)
- 義務(wù)教育歷史課程標準(2022年版)
- 防火封堵施工方案(新版)
- 真空度正壓和負壓關(guān)系及負壓中MPa和Pa對應(yīng)關(guān)系
- 大面積地面荷載作用附加沉降量計算
- 山東省普通初中小學(xué)音樂、美術(shù)、衛(wèi)生設(shè)備配備標準
- 景陵峪_構(gòu)造報告_構(gòu)造地質(zhì)學(xué)
- 浸塑作業(yè)與檢驗
評論
0/150
提交評論