版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
CH處理機(jī)調(diào)度與死鎖復(fù)習(xí)第一頁,共29頁。1.處理機(jī)調(diào)度的層次及頻率三種調(diào)度:高級(jí)調(diào)度(作業(yè)調(diào)度)、低級(jí)調(diào)度(進(jìn)程調(diào)度)、中級(jí)調(diào)度在上述三種調(diào)度中,進(jìn)程調(diào)度的運(yùn)行頻率最高,在分時(shí)系統(tǒng)中通常是10~100ms便進(jìn)行一次進(jìn)程調(diào)度,因此把它稱為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時(shí)間,進(jìn)程調(diào)度算法不宜太復(fù)雜。作業(yè)調(diào)度往往是發(fā)生在一個(gè)(批)作業(yè)運(yùn)行完畢,退出系統(tǒng),而需要重新調(diào)入一個(gè)(批)作業(yè)進(jìn)入內(nèi)存時(shí),故作業(yè)調(diào)度的周期較長(zhǎng),大約幾分鐘一次,因此把它稱為長(zhǎng)程調(diào)度。由于其運(yùn)行頻率較低,故允許作業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。中級(jí)調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間,因此把它稱為中程調(diào)度。第一頁第二頁,共29頁。2.一個(gè)典型的作業(yè)可分成三個(gè)作業(yè)步:①“編譯”作業(yè)步,通過執(zhí)行編譯程序?qū)υ闯绦蜻M(jìn)行編譯,產(chǎn)生若干個(gè)目標(biāo)程序段;②“連結(jié)裝配”作業(yè)步,將“編譯”作業(yè)步所產(chǎn)生的若干個(gè)目標(biāo)程序段裝配成可執(zhí)行的目標(biāo)程序;③“運(yùn)行”作業(yè)步,將可執(zhí)行的目標(biāo)程序讀入內(nèi)存并控制其運(yùn)行。第二頁第三頁,共29頁。3.低級(jí)調(diào)度的功能低級(jí)調(diào)度用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程(或內(nèi)核級(jí)線程,為敘述方便,以后只寫進(jìn)程)應(yīng)獲得處理機(jī),然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。低級(jí)調(diào)度的主要功能如下:(1)保存處理機(jī)的現(xiàn)場(chǎng)信息。在進(jìn)程調(diào)度進(jìn)行調(diào)度時(shí),首先需要保存當(dāng)前進(jìn)程的處理機(jī)的現(xiàn)場(chǎng)信息,如程序計(jì)數(shù)器、多個(gè)通用寄存器中的內(nèi)容等,將它們送入該進(jìn)程的進(jìn)程控制塊(PCB)中的相應(yīng)單元。(2)按某種算法選取進(jìn)程。低級(jí)調(diào)度程序按某種算法如優(yōu)先數(shù)算法、輪轉(zhuǎn)法等,從就緒隊(duì)列中選取一個(gè)進(jìn)程,把它的狀態(tài)改為運(yùn)行狀態(tài),并準(zhǔn)備把處理機(jī)分配給它。(3)把處理器分配給進(jìn)程。由分派程序(Dispatcher)把處理器分配給進(jìn)程。此時(shí)需為選中的進(jìn)程恢復(fù)處理機(jī)現(xiàn)場(chǎng),即把選中進(jìn)程的進(jìn)程控制塊內(nèi)有關(guān)處理機(jī)現(xiàn)場(chǎng)的信息裝入處理器相應(yīng)的各個(gè)寄存器中,把處理器的控制權(quán)交給該進(jìn)程,讓它從取出的斷點(diǎn)處開始繼續(xù)運(yùn)行。第三頁第四頁,共29頁。4.進(jìn)程調(diào)度方式1)非搶占方式:在采用這種調(diào)度方式時(shí),一旦把處理機(jī)分配給某進(jìn)程后,不管它要運(yùn)行多長(zhǎng)時(shí)間,都一直讓它運(yùn)行下去,決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī),也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成,自愿釋放處理機(jī),或發(fā)生某事件而被阻塞時(shí),才再把處理機(jī)分配給其他進(jìn)程。2)搶占方式:這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程,將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。第四頁第五頁,共29頁。5.搶占調(diào)度方式是基于一定原則搶占調(diào)度方式是基于一定原則的,主要有如下幾條:(1)優(yōu)先權(quán)原則。通常是對(duì)一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時(shí),如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高,便停止正在執(zhí)行(當(dāng)前)的進(jìn)程,將處理機(jī)分配給優(yōu)先權(quán)高的新到的進(jìn)程,使之執(zhí)行;或者說,允許優(yōu)先權(quán)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)。(2)短作業(yè)(進(jìn)程)優(yōu)先原則。當(dāng)新到達(dá)的作業(yè)(進(jìn)程)比正在執(zhí)行的作業(yè)(進(jìn)程)明顯的短時(shí),將暫停當(dāng)前長(zhǎng)作業(yè)(進(jìn)程)的執(zhí)行,將處理機(jī)分配給新到的短作業(yè)(進(jìn)程),使之優(yōu)先執(zhí)行;或者說,短作業(yè)(進(jìn)程)可以搶占當(dāng)前較長(zhǎng)作業(yè)(進(jìn)程)的處理機(jī)。(3)時(shí)間片原則。各進(jìn)程按時(shí)間片輪流運(yùn)行,當(dāng)一個(gè)時(shí)間片用完后,便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時(shí)系統(tǒng)、大多數(shù)的實(shí)時(shí)系統(tǒng),以及要求較高的批處理系統(tǒng)。第五頁第六頁,共29頁。6.選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則:(1)周轉(zhuǎn)時(shí)間短。(2)響應(yīng)時(shí)間快。(3)截止時(shí)間的保證。(4)優(yōu)先權(quán)準(zhǔn)則。面向系統(tǒng)的準(zhǔn)則(1)系統(tǒng)吞吐量高。(2)處理機(jī)利用率好。(3)各類資源的平衡利用。第六頁第七頁,共29頁。7.調(diào)度算法先來先服務(wù)短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法計(jì)算各作業(yè)(或進(jìn)程)的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間以及平均時(shí)間。練習(xí)第七頁第八頁,共29頁。FCFS算法比較有利于長(zhǎng)作業(yè)(進(jìn)程),而不利于短作業(yè)(進(jìn)程)。下表列出了A、B、C、D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開始執(zhí)行的時(shí)間及各自的完成時(shí)間,并計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。第八頁第九頁,共29頁。圖3-4
FCFS和SJF調(diào)度算法的性能
第九頁第十頁,共29頁。8.FCFS調(diào)度算法特點(diǎn)據(jù)此可知,F(xiàn)CFS調(diào)度算法有利于CPU繁忙型的作業(yè),而不利于I/O繁忙型的作業(yè)(進(jìn)程)。CPU繁忙型作業(yè)是指該類作業(yè)需要大量的CPU時(shí)間進(jìn)行計(jì)算,而很少請(qǐng)求I/O。通常的科學(xué)計(jì)算便屬于CPU繁忙型作業(yè)。I/O繁忙型作業(yè)是指CPU進(jìn)行處理時(shí)需頻繁地請(qǐng)求I/O。目前的大多數(shù)事務(wù)處理都屬于I/O繁忙型作業(yè)。第十頁第十一頁,共29頁。9.SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn):(1)該算法對(duì)長(zhǎng)作業(yè)不利,如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16,其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是,如果有一長(zhǎng)作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列),由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程),將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度。(2)該算法完全未考慮作業(yè)的緊迫程度,因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。(3)由于作業(yè)(進(jìn)程)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的,而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間,致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。第十一頁第十二頁,共29頁。由上式可以看出:(1)如果作業(yè)的等待時(shí)間相同,則要求服務(wù)的時(shí)間愈短,其優(yōu)先權(quán)愈高,因而該算法有利于短作業(yè)。(2)當(dāng)要求服務(wù)的時(shí)間相同時(shí),作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間,等待時(shí)間愈長(zhǎng),其優(yōu)先權(quán)愈高,因而它實(shí)現(xiàn)的是先來先服務(wù)。
(3)對(duì)于長(zhǎng)作業(yè),作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高,當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí),其優(yōu)先級(jí)便可升到很高,從而也可獲得處理機(jī)。簡(jiǎn)言之,該算法既照顧了短作業(yè),又考慮了作業(yè)到達(dá)的先后次序,不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得不到服務(wù)。因此,該算法實(shí)現(xiàn)了一種較好的折衷。當(dāng)然,在利用該算法時(shí),每要進(jìn)行調(diào)度之前,都須先做響應(yīng)比的計(jì)算,這會(huì)增加系統(tǒng)開銷。10.高響應(yīng)比優(yōu)先調(diào)度算法中響應(yīng)比及分析第十二頁第十三頁,共29頁。11.實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件提供必要的信息:(1)就緒時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始時(shí)間,在周期任務(wù)的情況下,它就是事先預(yù)知的一串時(shí)間序列;而在非周期任務(wù)的情況下,它也可能是預(yù)知的。(2)開始截止時(shí)間和完成截止時(shí)間。對(duì)于典型的實(shí)時(shí)應(yīng)用,只須知道開始截止時(shí)間,或者知道完成截止時(shí)間。(3)處理時(shí)間。這是指一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)間。在某些情況下,該時(shí)間也是系統(tǒng)提供的。(4)資源要求。這是指任務(wù)執(zhí)行時(shí)所需的一組資源。(5)優(yōu)先級(jí)。系統(tǒng)處理能力強(qiáng)采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制:(1)對(duì)外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請(qǐng)求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng),要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu),還應(yīng)使禁止中斷的時(shí)間間隔盡量短,以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后,便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度,應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)匦?,以減少任務(wù)切換的時(shí)間開銷。第十三頁第十四頁,共29頁。12.常用的幾種實(shí)時(shí)調(diào)度算法1.最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算法2.最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法第十四頁第十五頁,共29頁。13.產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn):(1)競(jìng)爭(zhēng)資源。當(dāng)系統(tǒng)中供多個(gè)進(jìn)程共享的資源如打印機(jī)、公用隊(duì)列等,其數(shù)目不足以滿足諸進(jìn)程的需要時(shí),會(huì)引起諸進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。(2)進(jìn)程間推進(jìn)順序非法。進(jìn)程在運(yùn)行過程中,請(qǐng)求和釋放資源的順序不當(dāng),也同樣會(huì)導(dǎo)致產(chǎn)生進(jìn)程死鎖。第十五頁第十六頁,共29頁。14.產(chǎn)生死鎖的必要條件雖然進(jìn)程在運(yùn)行過程中可能發(fā)生死鎖,但死鎖的發(fā)生也必須具備一定的條件。綜上所述不難看出,死鎖的發(fā)生必須具備下列四個(gè)必要條件。(1)互斥條件:指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用,即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用。如果此時(shí)還有其它進(jìn)程請(qǐng)求該資源,則請(qǐng)求者只能等待,直至占有該資源的進(jìn)程用畢釋放。(2)請(qǐng)求和保持條件:指進(jìn)程已經(jīng)保持了至少一個(gè)資源,但又提出了新的資源請(qǐng)求,而該資源又已被其它進(jìn)程占有,此時(shí)請(qǐng)求進(jìn)程阻塞,但又對(duì)自己已獲得的其它資源保持不放。(3)不剝奪條件:指進(jìn)程已獲得的資源,在未使用完之前,不能被剝奪,只能在使用完時(shí)由自己釋放。(4)環(huán)路等待條件:指在發(fā)生死鎖時(shí),必然存在一個(gè)進(jìn)程——資源的環(huán)形鏈,即進(jìn)程集合{P0,P1,P2,…,Pn}中的P0正在等待一個(gè)P1占用的資源;P1正在等待P2占用的資源,……,Pn正在等待已被P0占用的資源。第十六頁第十七頁,共29頁。15.處理死鎖的基本方法(1)預(yù)防死鎖:該方法是通過設(shè)置某些限制條件,去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件,來預(yù)防發(fā)生死鎖。(2)避免死鎖:它并不須事先采取各種限制措施去破壞產(chǎn)生死鎖的四個(gè)必要條件,而是在資源的動(dòng)態(tài)分配過程中,用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài),從而避免發(fā)生死鎖。(3)檢測(cè)死鎖:這種方法并不須事先采取任何限制性措施,也不必檢查系統(tǒng)是否已經(jīng)進(jìn)入不安全區(qū),而是允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖。但可通過系統(tǒng)所設(shè)置的檢測(cè)機(jī)構(gòu),及時(shí)地檢測(cè)出死鎖的發(fā)生,并精確地確定與死鎖有關(guān)的進(jìn)程和資源;然后,采取適當(dāng)措施,從系統(tǒng)中將已發(fā)生的死鎖清除掉。(4)解除死鎖:這是與檢測(cè)死鎖相配套的一種措施。當(dāng)檢測(cè)到系統(tǒng)中已發(fā)生死鎖時(shí),須將進(jìn)程從死鎖狀態(tài)中解脫出來。第十七頁第十八頁,共29頁。16.安全狀態(tài)所謂安全狀態(tài),是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…,Pn)(稱〈P1,P2,…,Pn〉序列為安全序列),來為每個(gè)進(jìn)程Pi分配其所需資源,直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求,使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列,則稱系統(tǒng)處于不安全狀態(tài)。第十八頁第十九頁,共29頁。安全狀態(tài)之例我們通過一個(gè)例子來說明安全性。假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3,共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī),P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻,進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī),尚有3臺(tái)空閑未分配,如下表所示:第十九頁第二十頁,共29頁。由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源,則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如,在T0時(shí)刻以后,P3又請(qǐng)求1臺(tái)磁帶機(jī),若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3,則系統(tǒng)便進(jìn)入不安全狀態(tài)。因?yàn)榇藭r(shí)也無法再找到一個(gè)安全序列,第二十頁第二十一頁,共29頁。17.利用銀行家算法避免死鎖假定系統(tǒng)中有五個(gè)進(jìn)程{P0,P1,P2,P3,P4}和三類資源{A,B,C},各種資源的數(shù)量分別為10、5、7,在T0時(shí)刻的資源分配情況如圖3-16所示。圖3-16T0時(shí)刻的資源分配表
第二十一頁第二十二頁,共29頁。圖3-17
T0時(shí)刻的安全序列
(1)T0時(shí)刻的安全性:利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析(見圖3-17所示)可知,在T0時(shí)刻存在著一個(gè)安全序列{P1,P3,P4,P2,P0},故系統(tǒng)是安全的。第二十二頁第二十三頁,共29頁。(2)?P1請(qǐng)求資源:P1發(fā)出請(qǐng)求向量Request1(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查:①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③系統(tǒng)先假定可為P1分配資源,并修改Available,Allocation1和Need1向量,由此形成的資源變化情況如圖3-16中的圓括號(hào)所示。第二十三頁第二十四頁,共29頁。④
再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。如圖3-18所示。
圖
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度孟安與配偶離婚協(xié)議:共同財(cái)產(chǎn)分割及子女監(jiān)護(hù)協(xié)議4篇
- 導(dǎo)演與攝影師2025年度合作協(xié)議3篇
- 2025年銷售人員合同范本:旅游產(chǎn)品銷售合作協(xié)議2篇
- 城東小學(xué)2025年度智能調(diào)光窗簾紗窗采購(gòu)合同2篇
- 二零二五年度美發(fā)店員工培訓(xùn)與職業(yè)發(fā)展合同4篇
- 2025年度金融衍生品買賣合同標(biāo)的交易風(fēng)險(xiǎn)管理4篇
- 2025年度綠色能源餐館司爐員專項(xiàng)聘用合同3篇
- 鄭州城市職業(yè)學(xué)院《交通監(jiān)控系統(tǒng)》2023-2024學(xué)年第一學(xué)期期末試卷
- 二零二五版苗木種植保險(xiǎn)產(chǎn)品設(shè)計(jì)與銷售合同4篇
- 2025年度房地產(chǎn)租賃融資合同模板4篇
- 2025春夏運(yùn)動(dòng)戶外行業(yè)趨勢(shì)白皮書
- 《法制宣傳之盜竊罪》課件
- 通信工程單位勞動(dòng)合同
- 2024年醫(yī)療器械經(jīng)營(yíng)質(zhì)量管理規(guī)范培訓(xùn)課件
- 高低壓配電柜產(chǎn)品營(yíng)銷計(jì)劃書
- 2024年4月自考02202傳感器與檢測(cè)技術(shù)試題
- 社會(huì)系統(tǒng)研究方法的重要原則
- 重癥醫(yī)學(xué)科健康宣教手冊(cè)
- 2022版《義務(wù)教育英語課程標(biāo)準(zhǔn)》解讀培訓(xùn)課件
- 五個(gè)帶頭方面談心談話范文三篇
- 互聯(lián)網(wǎng)的發(fā)展歷程
評(píng)論
0/150
提交評(píng)論