处理机调度与死锁课件_第1页
处理机调度与死锁课件_第2页
处理机调度与死锁课件_第3页
处理机调度与死锁课件_第4页
处理机调度与死锁课件_第5页
已阅读5页,还剩78页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

處理機調度與死鎖

3.1處理機調度的基本概念3.1.1高級、中級和低級調度1.高級調度(HighScheduling)

在每次執行作業調度時,都須做出以下兩個決定。

1)接納多少個作業

2)接納哪些作業2.低級調度(LowLevelScheduling)1)非搶佔方式(Non-preemptiveMode)

在採用非搶佔調度方式時,可能引起進程調度的因素可歸結為這樣幾個:①正在執行的進程執行完畢,或因發生某事件而不能再繼續執行;②執行中的進程因提出I/O請求而暫停執行;③在進程通信或同步過程中執行了某種原語操作,如P操作(wait操作)、Block原語、Wakeup原語等。這種調度方式的優點是實現簡單、系統開銷小,適用於大多數的批處理系統環境。但它難以滿足緊急任務的要求——立即執行,因而可能造成難以預料的後果。顯然,在要求比較嚴格的即時系統中,不宜採用這種調度方式。2)搶佔方式(PreemptiveMode)搶佔的原則有:優先權原則。(2)短作業(進程)優先原則。(3)時間片原則。3.中級調度(Intermediate-LevelScheduling)

中級調度又稱中程調度(Medium-TermScheduling)。引入中級調度的主要目的,是為了提高記憶體利用率和系統吞吐量。為此,應使那些暫時不能運行的進程不再佔用寶貴的記憶體資源,而將它們調至外存上去等待,把此時的進程狀態稱為就緒駐外存狀態或掛起狀態。當這些進程重又具備運行條件、且記憶體又稍有空閑時,由中級調度來決定把外存上的哪些又具備運行條件的就緒進程,重新調入記憶體,並修改其狀態為就緒狀態,掛在就緒佇列上等待進程調度。3.1.2調度佇列模型1.僅有進程調度的調度佇列模型圖3-1僅具有進程調度的調度佇列模型2.具有高級和低級調度的調度佇列模型圖3-2具有高、低兩級調度的調度佇列模型就緒佇列的形式。

(2)設置多個阻塞佇列。

圖3-2示出了具有高、低兩級調度的調度佇列模型。該模型與上一模型的主要區別在於如下兩個方面。3.同時具有三級調度的調度佇列模型圖3-3具有三級調度時的調度佇列模型3.1.3選擇調度方式和調度演算法的若干準則1.面向用戶的準則(1)周轉時間短。

可把平均周轉時間描述為:作業的周轉時間T與系統為它提供服務的時間TS之比,即W=T/TS,稱為帶權周轉時間,而平均帶權周轉時間則可表示為:(2)回應時間快。(3)截止時間的保證。(4)優先權準則。2.面向系統的準則系統吞吐量高。(2)處理機利用率好。(3)各類資源的平衡利用。3.2調度算法3.2.1先來先服務和短作業(進程)優先調度演算法1.先來先服務調度演算法圖3-4FCFS和SJF調度演算法的性能2.短作業(進程)優先調度演算法

短作業(進程)優先調度演算法SJ(P)F,是指對短作業或短進程優先調度的演算法。它們可以分別用於作業調度和進程調度。短作業優先(SJF)的調度演算法,是從後備佇列中選擇一個或若干個估計運行時間最短的作業,將它們調入記憶體運行。而短進程優先(SPF)調度演算法,則是從就緒佇列中選出一估計運行時間最短的進程,將處理機分配給它,使它立即執行並一直執行到完成,或發生某事件而被阻塞放棄處理機時,再重新調度。SJ(P)F調度演算法也存在不容忽視的缺點:

(1)該演算法對長作業不利,如作業C的周轉時間由10增至16,其帶權周轉時間由2增至3.1。更嚴重的是,如果有一長作業(進程)進入系統的後備佇列(就緒佇列),由於調度程式總是優先調度那些(即使是後進來的)短作業(進程),將導致長作業(進程)長期不被調度。

(2)該演算法完全未考慮作業的緊迫程度,因而不能保證緊迫性作業(進程)會被及時處理。

(3)由於作業(進程)的長短只是根據用戶所提供的估計執行時間而定的,而用戶又可能會有意或無意地縮短其作業的估計運行時間,致使該演算法不一定能真正做到短作業優先調度。3.2.2高優先權優先調度演算法1.優先權調度演算法的類型非搶佔式優先權演算法

在這種方式下,系統一旦把處理機分配給就緒佇列中優先權最高的進程後,該進程便一直執行下去,直至完成;或因發生某事件使該進程放棄處理機時,系統方可再將處理機重新分配給另一優先權最高的進程。這種調度演算法主要用於批處理系統中;也可用於某些對即時性要求不嚴的即時系統中。2)搶佔式優先權調度演算法在這種方式下,系統同樣是把處理機分配給優先權最高的進程,使之執行。但在其執行期間,只要又出現了另一個其優先權更高的進程,進程調度程式就立即停止當前進程(原優先權最高的進程)的執行,重新將處理機分配給新到的優先權最高的進程。因此,在採用這種調度演算法時,是每當系統中出現一個新的就緒進程i時,就將其優先權Pi與正在執行的進程j的優先權Pj進行比較。如果Pi≤Pj,原進程Pj便繼續執行;但如果是Pi>Pj,則立即停止Pj的執行,做進程切換,使i進程投入執行。顯然,這種搶佔式的優先權調度演算法,能更好地滿足緊迫作業的要求,故而常用於要求比較嚴格的即時系統中,以及對性能要求較高的批處理和分時系統中。2.優先權的類型1)靜態優先權靜態優先權是在創建進程時確定的,且在進程的整個運行期間保持不變。一般地,優先權是利用某一範圍內的一個整數來表示的,例如,0~7或0~255中的某一整數,又把該整數稱為優先數。只是具體用法各異:有的系統用“0”表示最高優先權,當數值愈大時,其優先權愈低;而有的系統恰恰相反。確定進程優先權的依據有如下三個方面:進程類型。(2)進程對資源的需求。(3)用戶要求。2)動態優先權動態優先權是指,在創建進程時所賦予的優先權,是可以隨進程的推進或隨其等待時間的增加而改變的,以便獲得更好的調度性能。例如,我們可以規定,在就緒佇列中的進程,隨其等待時間的增長,其優先權以速率a提高。若所有的進程都具有相同的優先權初值,則顯然是最先進入就緒佇列的進程,將因其動態優先權變得最高而優先獲得處理機,此即FCFS演算法。若所有的就緒進程具有各不相同的優先權初值,那麼,對於優先權初值低的進程,在等待了足夠的時間後,其優先權便可能升為最高,從而可以獲得處理機。當採用搶佔式優先權調度演算法時,如果再規定當前進程的優先權以速率b下降,則可防止一個長作業長期地壟斷處理機。3.高回應比優先調度演算法優先權的變化規律可描述為:由於等待時間與服務時間之和,就是系統對該作業的回應時間,故該優先權又相當於回應比RP。據此,又可表示為:(1)如果作業的等待時間相同,則要求服務的時間愈短,其優先權愈高,因而該演算法有利於短作業。

(2)當要求服務的時間相同時,作業的優先權決定於其等待時間,等待時間愈長,其優先權愈高,因而它實現的是先來先服務。

(3)對於長作業,作業的優先順序可以隨等待時間的增加而提高,當其等待時間足夠長時,其優先順序便可升到很高,從而也可獲得處理機。3.2.3基於時間片的輪轉調度演算法1.時間片輪轉法在早期的時間片輪轉法中,系統將所有的就緒進程按先來先服務的原則,排成一個佇列,每次調度時,把CPU分配給隊首進程,並令其執行一個時間片。時間片的大小從幾ms到幾百ms。當執行的時間片用完時,由一個計時器發出時鐘中斷請求,調度程式便據此信號來停止該進程的執行,並將它送往就緒佇列的末尾;然後,再把處理機分配給就緒佇列中新的隊首進程,同時也讓它執行一個時間片。這樣就可以保證就緒佇列中的所有進程,在一給定的時間內,均能獲得一時間片的處理機執行時間。2.多級回饋佇列調度演算法(1)應設置多個就緒佇列,並為各個佇列賦予不同的優先順序。第一個佇列的優先順序最高,第二個佇列次之,其餘各隊列的優先權逐個降低。該演算法賦予各個佇列中進程執行時間片的大小也各不相同,在優先權愈高的佇列中,為每個進程所規定的執行時間片就愈小。例如,第二個佇列的時間片要比第一個佇列的時間片長一倍,……,第i+1個佇列的時間片要比第i個佇列的時間片長一倍。圖3-5是多級回饋佇列演算法的示意。圖3-5多級回饋佇列調度演算法(2)當一個新進程進入記憶體後,首先將它放入第一佇列的末尾,按FCFS原則排隊等待調度。當輪到該進程執行時,如它能在該時間片內完成,便可準備撤離系統;如果它在一個時間片結束時尚未完成,調度程式便將該進程轉入第二佇列的末尾,再同樣地按FCFS原則等待調度執行;如果它在第二佇列中運行一個時間片後仍未完成,再依次將它放入第三佇列,……,如此下去,當一個長作業(進程)從第一佇列依次降到第n佇列後,在第n佇列中便採取按時間片輪轉的方式運行。(3)僅當第一佇列空閒時,調度程式才調度第二佇列中的進程運行;僅當第1~(i-1)佇列均空時,才會調度第i佇列中的進程運行。如果處理機正在第i佇列中為某進程服務時,又有新進程進入優先權較高的佇列(第1~(i-1)中的任何一個佇列),則此時新進程將搶佔正在運行進程的處理機,即由調度程式把正在運行的進程放回到第i佇列的末尾,把處理機分配給新到的高優先權進程。3.多級回饋佇列調度演算法的性能終端型作業用戶。(2)短批處理作業用戶。(3)長批處理作業用戶。3.3實時調度3.3.1實現即時調度的基本條件1.提供必要的資訊就緒時間。(2)開始截止時間和完成截止時間。(3)處理時間。(4)資源要求。(5)優先順序。2.系統處理能力強

在即時系統中,通常都有著多個即時任務。若處理機的處理能力不夠強,則有可能因處理機忙不過來而使某些即時任務不能得到及時處理,從而導致發生難以預料的後果。假定系統中有m個週期性的硬實時任務,它們的處理時間可表示為Ci,週期時間表示為Pi,則在單處理機情況下,必須滿足下麵的限制條件:

系統才是可調度的。假如系統中有6個硬實時任務,它們的週期時間都是50ms,而每次的處理時間為10ms,則不難算出,此時是不能滿足上式的,因而系統是不可調度的。解決的方法是提高系統的處理能力,其途徑有二:其一仍是採用單處理機系統,但須增強其處理能力,以顯著地減少對每一個任務的處理時間;其二是採用多處理機系統。假定系統中的處理機數為N,則應將上述的限制條件改為:3.採用搶佔式調度機制

當一個優先權更高的任務到達時,允許將當前任務暫時掛起,而令高優先權任務立即投入運行,這樣便可滿足該硬實時任務對截止時間的要求。但這種調度機制比較複雜。對於一些小的即時系統,如果能預知任務的開始截止時間,則對即時任務的調度可採用非搶佔調度機制,以簡化調度程式和對任務調度時所花費的系統開銷。但在設計這種調度機制時,應使所有的即時任務都比較小,並在執行完關鍵性程式和臨界區後,能及時地將自己阻塞起來,以便釋放出處理機,供調度程式去調度那種開始截止時間即將到達的任務。4.具有快速切換機制

該機制應具有如下兩方面的能力:

(1)對外部中斷的快速回應能力。為使在緊迫的外部事件請求中斷時系統能及時回應,要求系統具有快速硬體中斷機構,還應使禁止中斷的時間間隔儘量短,以免耽誤時機(其他緊迫任務)。

(2)快速的任務分派能力。在完成任務調度後,便應進行任務切換。為了提高分派程式進行任務切換時的速度,應使系統中的每個運行功能單位適當的小,以減少任務切換的時間開銷。3.3.2即時調度演算法的分類1.非搶佔式調度演算法非搶佔式輪轉調度演算法。(2)非搶佔式優先調度演算法。2.搶佔式調度演算法基於時鐘中斷的搶佔式優先權調度演算法。(2)立即搶佔(ImmediatePreemption)的優先權調度演算法。圖3-6即時進程調度3.3.3常用的幾種即時調度演算法1.最早截止時間優先即EDF(EarliestDeadlineFirst)演算法圖3-7EDF演算法用於非搶佔調度方式2.最低鬆弛度優先即LLF(LeastLaxityFirst)演算法

該演算法是根據任務緊急(或鬆弛)的程度,來確定任務的優先順序。任務的緊急程度愈高,為該任務所賦予的優先順序就愈高,以使之優先執行。例如,一個任務在200ms時必須完成,而它本身所需的運行時間就有100ms,因此,調度程式必須在100ms之前調度執行,該任務的緊急程度(鬆弛程度)為100ms。又如,另一任務在400ms時必須完成,它本身需要運行150ms,則其鬆弛程度為250ms。在實現該演算法時要求系統中有一個按鬆弛度排序的即時任務就緒佇列,鬆弛度最低的任務排在佇列最前面,調度程式總是選擇就緒佇列中的隊首任務執行。該演算法主要用於可搶佔調度方式中。假如在一個即時系統中,有兩個週期性即時任務A和B,任務A要求每20ms執行一次,執行時間為10ms;任務B只要求每50ms執行一次,執行時間為25ms。圖3-8A和B任務每次必須完成的時間

在剛開始時(t1=0),A1必須在20ms時完成,而它本身運行又需10ms,可算出A1的鬆弛度為10ms;B1必須在50ms時完成,而它本身運行就需25ms,可算出B1的鬆弛度為25ms,故調度程式應先調度A1執行。在t2=10ms時,A2的鬆弛度可按下式算出:

A2的鬆弛度=必須完成時間-其本身的運行時間-當前時間

=40ms-10ms-10ms=20ms

類似地,可算出B1的鬆弛度為15ms,故調度程式應選擇B2運行。在t3=30ms時,A2的鬆弛度已減為0(即40-10-30),而B1的鬆弛度為15ms(即50-5-30),於是調度程式應搶佔B1的處理機而調度A2運行。在t4=40ms時,A3的鬆弛度為10ms(即60-10-40),而B1的鬆弛度僅為5ms(即50-5-40),故又應重新調度B1執行。在t5=45ms時,B1執行完成,而此時A3的鬆弛度已減為5ms(即60-10-45),而B2的鬆弛度為30ms(即100-25-45),於是又應調度A3執行。在t6=55ms時,任務A尚未進入第4週期,而任務B已進入第2週期,故再調度B2執行。在t7=70ms時,A4的鬆弛度已減至0ms(即80-10-70),而B2的鬆弛度為20ms(即100-10-70),故此時調度又應搶佔B2的處理機而調度A4執行。圖3-9利用ELLF演算法進行調度的情況3.4多處理機系統中的調度3.4.1多處理器系統的類型(1)緊密耦合(TightlyCoupted)MPS。這通常是通過高速匯流排或高速交叉開關,來實現多個處理器之間的互連的。它們共用主記憶體系統和I/O設備,並要求將主記憶體劃分為若干個能獨立訪問的記憶體模組,以便多個處理機能同時對主存進行訪問。系統中的所有資源和進程,都由操作系統實施統一的控制和管理。(2)鬆散耦合(LooselyCoupled)MPS。在鬆散耦合MPS中,通常是通過通道或通信線路,來實現多臺電腦之間的互連。每臺電腦都有自己的記憶體和I/O設備,並配置了OS來管理本地資源和在本地運行的進程。因此,每一臺電腦都能獨立地工作,必要時可通過通信線路與其它電腦交換資訊,以及協調它們之間的工作。2.對稱多處理器系統和非對稱多處理器系統(1)對稱多處理器系統SMPS(SymmetricMultiProcessorSystem)。在系統中所包含的各處理器單元,在功能和結構上都是相同的,當前的絕大多數MPS都屬於SMP系統。例如,IBM公司的SR/6000ModelF50,便是利用4片PowerPC處理器構成的。

(2)非對稱多處理器系統。在系統中有多種類型的處理單元,它們的功能和結構各不相同,其中只有一個主處理器,有多個從處理器。3.4.2進程分配方式1.對稱多處理器系統中的進程分配方式

在SMP系統中,所有的處理器都是相同的,因而可把所有的處理器作為一個處理器池(Processorpool),由調度程式或基於處理器的請求,將任何一個進程分配給池中的任何一個處理器去處理。在進行進程分配時,可採用以下兩種方式之一。

1)靜態分配(StaticAssigenment)方式

2)動態分配(DynamicAssgement)方式2.非對稱MPS中的進程分配方式

對於非對稱MPS,其OS大多採用主—從(Master-Slave)式OS,即OS的核心部分駐留在一臺主機上(Master),而從機(Slave)上只是用戶程式,進程調度只由主機執行。每當從機空閒時,便向主機發送一索求進程的信號,然後,便等待主機為它分配進程。在主機中保持有一個就緒佇列,只要就緒佇列不空,主機便從其隊首摘下一進程分配給請求的從機。從機接收到分配的進程後便運行該進程,該進程結束後從機又向主機發出請求。3.4.3進程(線程)調度方式

1.自調度(Self-Scheduling)方式

1)自調度機制在多處理器系統中,自調度方式是最簡單的一種調度方式。它是直接由單處理機環境下的調度方式演變而來的。在系統中設置有一個公共的進程或線程就緒佇列,所有的處理器在空閒時,都可自己到該隊列中取得一進程(或線程)來運行。在自調度方式中,可採用在單處理機環境下所用的調度演算法,如先來先服務(FCFS)調度演算法、最高優先權優先(FPF)調度演算法和搶佔式最高優先權優先調度演算法等。2)自調度方式的優點自調度方式的主要優點表現為:首先,系統中的公共就緒佇列可按照單處理機系統中所採用的各種方式加以組織;其調度演算法也可沿用單處理機系統所用的演算法,亦即,很容易將單處理機環境下的調度機制移植到多處理機系統中,故它仍然是當前多處理機系統中較常用的調度方式。其次,只要系統中有任務,或者說只要公共就緒佇列不空,就不會出現處理機空閒的情況,也不會發生處理器忙閑不均的現象,因而有利於提高處理器的利用率。3)自調度方式的缺點瓶頸問題。(2)低效性。(3)線程切換頻繁。2.成組調度(GangScheduling)方式

在成組調度時,如何為應用程式分配處理器時間,

1)面向所有應用程式平均分配處理器時間

2)面向所有線程平均分配處理器時間圖3-10兩種分配處理器時間的方法3.專用處理器分配(DedicatedProcessorAssigement)方式圖3-11線程數對加速比的影響3.5產生死鎖的原因和必要條件3.5.1產生死鎖的原因競爭資源。(2)進程間推進順序非法。1.競爭資源引起進程死鎖可剝奪和非剝奪性資源2)競爭非剝奪性資源3)競爭臨時性資源圖3-12I/O設備共用時的死鎖情況圖3-13進程之間通信時的死鎖2.進程推進順序不當引起死鎖1)進程推進順序合法圖3-14進程推進順序對死鎖的影響2)進程推進順序非法若併發進程P1和P2按曲線④所示的順序推進,它們將進入不安全區D內。此時P1保持了資源R1,P2保持了資源R2,系統處於不安全狀態。因為,這時兩進程再向前推進,便可能發生死鎖。例如,當P1運行到P1:Request(R2)時,將因R2已被P2佔用而阻塞;當P2運行到P2:Request(R1)時,也將因R1已被P1佔用而阻塞,於是發生了進程死鎖。3.5.2產生死鎖的必要條件互斥條件(2)請求和保持條件(3)不剝奪條件(4)環路等待條件3.5.3處理死鎖的基本方法預防死鎖。(2)避免死鎖。(3)檢測死鎖。(4)解除死鎖。3.6預防死鎖的方法3.6.1預防死鎖摒棄“請求和保持”條件2.摒棄“不剝奪”條件3.摒棄“環路等待”條件3.6.2系統安全狀態

1.安全狀態在避免死鎖的方法中,允許進程動態地申請資源,但系統在進行資源分配之前,應先計算此次資源分配的安全性。若此次分配不會導致系統進入不安全狀態,則將資源分配給進程;否則,令進程等待。所謂安全狀態,是指系統能按某種進程順序(P1,P2,…,Pn)(稱〈P1,P2,…,Pn〉序列為安全序列),來為每個進程Pi分配其所需資源,直至滿足每個進程對資源的最大需求,使每個進程都可順利地完成。如果系統無法找到這樣一個安全序列,則稱系統處於不安全狀態。2.安全狀態之例我們通過一個例子來說明安全性。假定系統中有三個進程P1、P2和P3,共有12臺磁帶機。進程P1總共要求10臺磁帶機,P2和P3分別要求4臺和9臺。假設在T0時刻,進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機,尚有3臺空閒未分配,如下表所示:進程最大需求已分配可用P1P2P3104952233.由安全狀態向不安全狀態的轉換

如果不按照安全序列分配資源,則系統可能會由安全狀態進入不安全狀態。例如,在T0時刻以後,P3又請求1臺磁帶機,若此時系統把剩餘3臺中的1臺分配給P3,則系統便進入不安全狀態。因為,此時也無法再找到一個安全序列,例如,把其餘的2臺分配給P2,這樣,在P2完成後只能釋放出4臺,既不能滿足P1尚需5臺的要求,也不能滿足P3尚需6臺的要求,致使它們都無法推進到完成,彼此都在等待對方釋放資源,即陷入僵局,結果導致死鎖。3.6.3利用銀行家演算法避免死鎖1.銀行家演算法中的數據結構(1)可利用資源向量Available。這是一個含有m個元素的數組,其中的每一個元素代表一類可利用的資源數目,其初始值是系統中所配置的該類全部可用資源的數目,其數值隨該類資源的分配和回收而動態地改變。如果Available[j]=K,則表示系統中現有Rj類資源K個。(2)最大需求矩陣Max。這是一個n×m的矩陣,它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K,則表示進程i需要Rj類資源的最大數目為K。

(3)分配矩陣Allocation。這也是一個n×m的矩陣,它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K,則表示進程i當前已分得Rj類資源的數目為K。

(4)需求矩陣Need。這也是一個n×m的矩陣,用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K,則表示進程i還需要Rj類資源K個,方能完成其任務。Need[i,j]=Max[i,j]-Allocation[i,j]

2.銀行家演算法設Requesti是進程Pi的請求向量,如果Requesti[j]=K,表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求後,系統按下述步驟進行檢查:

(1)如果Requesti[j]≤Need[i,j],便轉向步驟2;否則認為出錯,因為它所需要的資源數已超過它所宣佈的最大值。

(2)如果Requesti[j]≤Available[j],便轉向步驟(3);否則,表示尚無足夠資源,Pi須等待。(3)系統試探著把資源分配給進程Pi,並修改下麵數據結構中的數值:

Available[j]∶=Available[j]-Requesti[j];

Allocation[i,j]∶=Allocation[i,j]+Requesti[j];

Need[i,j]∶=Need[i,j]-Requesti[j];

(4)系統執行安全性演算法,檢查此次資源分配後,系統是否處於安全狀態。若安全,才正式將資源分配給進程Pi,以完成本次分配;否則,將本次的試探分配作廢,恢復原來的資源分配狀態,讓進程Pi等待。3.安全性演算法(1)設置兩個向量:①工作向量Work:它表示系統可提供給進程繼續運行所需的各類資源數目,它含有m個元素,在執行安全演算法開始時,Work∶=Available;②Finish:它表示系統是否有足夠的資源分配給進程,使之運行完成。開始時先做Finish[i]∶=false;當有足夠資源分配給進程時,再令Finish[i]∶=true。(2)從進程集合中找到一個能滿足下述條件的進程:

①Finish[i]=false;②Need[i,j]≤Work[j];若找到,執行步驟(3),否則,執行步驟(4)。

(3)當進程Pi獲得資源後,可順利執行,直至完成,並釋放出分配給它的資源,故應執行:

Work[j]∶=

Work[i]+Allocation[i,j];

Finish[i]∶=

true;

gotostep2;(4)如果所有進程的Finish[i]=true都滿足,則表示系統處於安全狀態;否則,系統處於不安全狀態。4.銀行家演算法之例

假定系統中有五個進程{P0,P1,P2,P3,P4}和三類資源{A,B,C},各種資源的數量分別為10、5、7,在T0時刻的資源分配情況如圖3-15所示。圖3-15T0時刻的資源分配表(1)

T0時刻的安全性:圖3-16T0時刻的安全序列(2)P1請求資源:P1發出請求向量Request1(1,0,2),系統按銀行家演算法進行檢查:

①Request1(1,0,2)≤Need1(1,2,2)

②Request1(1,0,2)≤Available1(3,3,2)

③系統先假定可為P1分配資源,並修改Available,Allocation1和Need1向量,由此形成的資源變化情況如圖3-15中的圓括號所示。

④再利用安全性演算法檢查此時系統是否安全。圖3-17P1申請資源時的安全性檢查(3)P4請求資源:P4發出請求向量Request4(3,3,0),系統按銀行家演算法進行檢查:

①Request4(3,3,0)≤Need4(4,3,1);

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论