資源管理技術(shù)BasicsofComputerSoftware答辯人：XXX

進(jìn)程與處理機(jī)管理8.2進(jìn)程概念

進(jìn)程調(diào)度死鎖進(jìn)程：就是程序的一次執(zhí)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。進(jìn)程管理也被稱為處理機(jī)管理。處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源，所以它管理的好壞在很大程度上直接影響系統(tǒng)的效率。處理機(jī)管理又分兩個(gè)部分：作業(yè)管理和進(jìn)程管理。進(jìn)程管理是由程序管理進(jìn)化而來，是和程序管理密不可分的。進(jìn)程概念

進(jìn)程調(diào)度死鎖進(jìn)程與程序的主要區(qū)別進(jìn)程具有并發(fā)性，而程序沒有并發(fā)性進(jìn)程和程序不是一一對應(yīng)的：一個(gè)程序可對應(yīng)多個(gè)進(jìn)程即多個(gè)進(jìn)程可執(zhí)行同一程序；但一個(gè)進(jìn)程只能對應(yīng)1個(gè)程序。對應(yīng)關(guān)系進(jìn)程是動(dòng)態(tài)的，而程序是靜態(tài)的動(dòng)態(tài)性進(jìn)程有一定的生命期，是程序在數(shù)據(jù)集上的一次執(zhí)行，生命周期不會(huì)跨越系統(tǒng)運(yùn)行周期；而程序是指令的集合，是永存的生命周期性進(jìn)程是競爭計(jì)算機(jī)資源的基本單位，程序不是資源競爭進(jìn)程概念

進(jìn)程調(diào)度死鎖進(jìn)程的特征多個(gè)進(jìn)程實(shí)體在一段時(shí)間內(nèi)能夠并發(fā)執(zhí)行并發(fā)性不同進(jìn)程在邏輯上相互獨(dú)立，有各的運(yùn)行軌跡異步性進(jìn)程的實(shí)質(zhì)是程序的一次執(zhí)行，因此進(jìn)程是動(dòng)態(tài)的動(dòng)態(tài)性每個(gè)進(jìn)程都是一個(gè)獨(dú)立運(yùn)行的基本單位，也是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位獨(dú)立性系統(tǒng)為每個(gè)進(jìn)程配置了一個(gè)進(jìn)程控制塊PCB。因此，從結(jié)構(gòu)上看，每個(gè)進(jìn)程都由程序段、數(shù)據(jù)段以及PCB這三部分組成結(jié)構(gòu)性進(jìn)程概念

進(jìn)程調(diào)度死鎖就緒狀態(tài)已經(jīng)獲得投入運(yùn)行所必需的一切資源，一旦分配到CPU，就可以立即執(zhí)行運(yùn)行狀態(tài)進(jìn)程獲得了CPU及其它一切所需資源，正在CPU上運(yùn)行著等待狀態(tài)由于資源得不到滿足，進(jìn)程運(yùn)行受阻，處于暫停狀態(tài)，等待資源分配后，再投入運(yùn)行進(jìn)程狀態(tài)運(yùn)行狀態(tài)等待狀態(tài)

就緒狀態(tài)

進(jìn)程調(diào)度

等待資源時(shí)間用完獲得資源進(jìn)程概念

進(jìn)程調(diào)度死鎖進(jìn)程控制塊PCB1進(jìn)程標(biāo)識符2特征信息3執(zhí)行狀態(tài)信息4通信信息5調(diào)度優(yōu)先數(shù)6現(xiàn)場信息7系統(tǒng)棧8進(jìn)程映像信息9資源占有信息10族系關(guān)系進(jìn)程概念

進(jìn)程調(diào)度死鎖進(jìn)程調(diào)度：由于操作系統(tǒng)管理了系統(tǒng)的有限資源，當(dāng)有多個(gè)進(jìn)程要使用這些資源時(shí)，因?yàn)橘Y源的有限性，必須按照一定的原則選擇進(jìn)程（請求）來占用資源。02可剝奪方式在某些條件下系統(tǒng)可以強(qiáng)制剝奪正在運(yùn)行的進(jìn)程使用處理機(jī)的權(quán)利，將其分配給另一個(gè)合適的就緒進(jìn)程01不可剝奪方式也稱不可搶占方式，一個(gè)進(jìn)程在獲得處理機(jī)后，除非運(yùn)行結(jié)束或進(jìn)入阻塞狀態(tài)等原因主動(dòng)放棄CPU,否則一直運(yùn)行下去相關(guān)概念周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間等待時(shí)間1周轉(zhuǎn)時(shí)間進(jìn)程從創(chuàng)建到執(zhí)行完成所經(jīng)歷的時(shí)間周轉(zhuǎn)時(shí)間T=完成時(shí)間-到達(dá)時(shí)間其值越接近平均運(yùn)行時(shí)間，說明該調(diào)度算法越理想2帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間和運(yùn)行時(shí)間的比值。帶權(quán)周轉(zhuǎn)時(shí)間TW=周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間越接近1，說明該調(diào)度算法越理想。3等待時(shí)間進(jìn)程從創(chuàng)建到執(zhí)行完成所經(jīng)歷的時(shí)間減去占有CPU的時(shí)間等待時(shí)間W=周轉(zhuǎn)時(shí)間-運(yùn)行時(shí)間進(jìn)程概念

進(jìn)程調(diào)度死鎖1.先來先服務(wù)(FCFS)調(diào)度算法進(jìn)程概念

進(jìn)程調(diào)度死鎖當(dāng)一個(gè)大進(jìn)程運(yùn)行時(shí)會(huì)使后到的小進(jìn)程等待很長時(shí)間，這就增加了進(jìn)程平均等待時(shí)間；不能為緊急進(jìn)程優(yōu)先分配CPU。算法思想按照進(jìn)程進(jìn)入就緒隊(duì)列的時(shí)間次序分配CPU。算法特點(diǎn)具有不可搶占性的特點(diǎn)，處在就緒隊(duì)列頭部的進(jìn)程首先獲得CPU，一旦進(jìn)程占用了CPU，一直運(yùn)行到結(jié)束才放棄CPU，除非在運(yùn)行中因等待事件被阻塞而放棄CPU。算法問題1.先來先服務(wù)(FCFS)調(diào)度算法進(jìn)程概念

進(jìn)程調(diào)度死鎖進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P107P224P341P454平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間平均等待時(shí)間運(yùn)行進(jìn)程P1

P2

P3P4

↑0↑7↑11↑12↑1607071711592.25111278812167112.75T=(7+9+8+11)/4=8.75TW=(1+2.25+8+2.75)/4=3.5W=(0+5+7+7))/4=4.75FCFS算法的運(yùn)行時(shí)間軸2.短進(jìn)程優(yōu)先(SPF)調(diào)度算法進(jìn)程概念

進(jìn)程調(diào)度死鎖必須預(yù)知進(jìn)程的運(yùn)行時(shí)間；對長進(jìn)程不利；完全未考慮進(jìn)程的緊迫程度算法思想每次進(jìn)行進(jìn)程調(diào)度時(shí)均選擇運(yùn)行時(shí)間最短的進(jìn)程分配CPU算法特點(diǎn)SPF是以進(jìn)程的運(yùn)行時(shí)間長度作為優(yōu)先級，進(jìn)程運(yùn)行時(shí)間越短，優(yōu)先級越高算法問題進(jìn)程概念

進(jìn)程調(diào)度死鎖進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P107P224P341P454平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間平均等待時(shí)間運(yùn)行進(jìn)程P1

P3P2

P4

↑0↑7↑8↑12↑16070718126102.57834412167112.75T=(7+10+4+11)/4=8TW=(1+2.5+4+2.75)/4=2.56W=(0+6+3+7)/4=4FCFS算法的運(yùn)行時(shí)間軸2.短進(jìn)程優(yōu)先(SPF)調(diào)度算法3.最短剩余時(shí)間優(yōu)先算法進(jìn)程概念

進(jìn)程調(diào)度死鎖后提交的大進(jìn)程長期得不到響應(yīng)算法思想每當(dāng)有進(jìn)程加入就緒隊(duì)列時(shí)就需要調(diào)度，如果新到達(dá)的進(jìn)程剩余時(shí)間比當(dāng)前運(yùn)行的進(jìn)程剩余時(shí)間更短，則由新進(jìn)程搶占處理機(jī)。另外，當(dāng)一個(gè)進(jìn)程完成時(shí)也需要調(diào)度。算法特點(diǎn)綜合考慮了剩余時(shí)間和當(dāng)前的短進(jìn)程，算法的幾個(gè)綜合評價(jià)指標(biāo)有所降低算法問題進(jìn)程概念

進(jìn)程調(diào)度死鎖進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P107P224P341P454平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間平均等待時(shí)間運(yùn)行進(jìn)程P1

P2

P3

P2

P4

P1

↑0↑7↑11↑160169162.2927151.2545011711261.5T=(16+5+1+6)/4=7TW=(2.29+1.25+1+1.5)/4=1.51W=(9+1+0+2)/4=3FCFS算法的運(yùn)行時(shí)間軸3.最短剩余時(shí)間優(yōu)先算法↑2↑4↑54.時(shí)間片輪轉(zhuǎn)算法進(jìn)程概念

進(jìn)程調(diào)度死鎖系統(tǒng)的效率與時(shí)間片大小的設(shè)置有關(guān)算法思想和分時(shí)系統(tǒng)類似算法特點(diǎn)時(shí)間片輪轉(zhuǎn)為剝奪式調(diào)度算法，即當(dāng)時(shí)間片用完后，即使當(dāng)前進(jìn)程沒有執(zhí)行結(jié)束，也會(huì)被剝奪CPU。時(shí)間片輪轉(zhuǎn)算法比較適合交互式分時(shí)系統(tǒng)算法問題可將時(shí)間片分成多個(gè)規(guī)格，如10ms,20ms或50ms等。按時(shí)間片大小將就緒進(jìn)程排成多個(gè)隊(duì)列。優(yōu)化方案5.優(yōu)先級調(diào)度算法進(jìn)程概念

進(jìn)程調(diào)度死鎖算法思想系統(tǒng)賦予每個(gè)進(jìn)程一個(gè)優(yōu)先數(shù)，用于表示該進(jìn)程的優(yōu)先級。調(diào)度程序總是從就緒隊(duì)列中挑選一個(gè)優(yōu)先級最高的進(jìn)程，使之占有處理機(jī)02動(dòng)態(tài)優(yōu)先級調(diào)度優(yōu)先級在進(jìn)程運(yùn)行中，可以動(dòng)態(tài)調(diào)整01靜態(tài)優(yōu)先級調(diào)度優(yōu)先級在進(jìn)程創(chuàng)建時(shí)已經(jīng)確定。在進(jìn)程運(yùn)行期間該優(yōu)先數(shù)保持不變靜態(tài)優(yōu)先權(quán)法比較適合于實(shí)時(shí)系統(tǒng)，其優(yōu)先級可根據(jù)事件的緊迫程度事先設(shè)定。動(dòng)態(tài)優(yōu)先級調(diào)度可根據(jù)實(shí)際情況調(diào)整優(yōu)先級，處理更靈活短作業(yè)的進(jìn)程可以賦予較高的優(yōu)先級根據(jù)用戶作業(yè)的申請，設(shè)置進(jìn)程的優(yōu)先級系統(tǒng)進(jìn)程應(yīng)當(dāng)賦予比用戶進(jìn)程高的優(yōu)先級I/O繁忙的進(jìn)程應(yīng)當(dāng)優(yōu)先獲得CPU進(jìn)程概念

進(jìn)程調(diào)度死鎖分配優(yōu)先級需要考慮的因素6.高響應(yīng)比優(yōu)先調(diào)度算法進(jìn)程概念

進(jìn)程調(diào)度死鎖需要估計(jì)每個(gè)進(jìn)程的運(yùn)行時(shí)間，而且每次調(diào)度時(shí)都要計(jì)算就緒隊(duì)列中所有進(jìn)程的響應(yīng)比，這需要耗費(fèi)不少的CPU時(shí)間算法思想每個(gè)進(jìn)程都擁有一個(gè)動(dòng)態(tài)優(yōu)先數(shù)，該優(yōu)先數(shù)不僅是進(jìn)程運(yùn)行時(shí)間（估計(jì)值）的函數(shù)，還是其等待時(shí)間的函數(shù)RP=響應(yīng)時(shí)間/運(yùn)行時(shí)間=1+等待時(shí)間/運(yùn)行時(shí)間算法特點(diǎn)高響應(yīng)比優(yōu)先調(diào)度算法既照顧了短進(jìn)程，又不使長進(jìn)程等待時(shí)間過長，是先來先服務(wù)調(diào)度算法和短進(jìn)程優(yōu)先調(diào)度算法的一種很好的折中調(diào)度方案算法問題6.高響應(yīng)比優(yōu)先調(diào)度算法進(jìn)程概念

進(jìn)程調(diào)度死鎖時(shí)刻事件和動(dòng)作Rp值動(dòng)作P1P2P3P40P1到，計(jì)算Rp1---P1運(yùn)行2P2到

4P3到

5P4到

7P1結(jié)束，計(jì)算Rp-2.2541.5P3運(yùn)行8P3結(jié)束，計(jì)算Rp-2.5-1.75P2運(yùn)行12P2結(jié)束，計(jì)算Rp---2.75P4運(yùn)行16P4結(jié)束

平均周轉(zhuǎn)時(shí)間：T=(16+5+1+6)/4=7平均帶權(quán)周轉(zhuǎn)時(shí)間：TW=(2.29+1.25+1+1.5)/4=1.51平均等待時(shí)間：W=(9+1+0+2)/4=31.死鎖的定義及產(chǎn)生進(jìn)程概念

進(jìn)程調(diào)度死鎖死鎖現(xiàn)象：每個(gè)進(jìn)程所要求的資源都已被另一個(gè)進(jìn)程占用，出現(xiàn)沒有一個(gè)進(jìn)程能繼續(xù)運(yùn)行，這種情況稱“死鎖”。打印機(jī)進(jìn)程A進(jìn)程B讀卡機(jī)進(jìn)程A申請到打印機(jī)進(jìn)程A需要讀卡機(jī)進(jìn)程B申請到讀卡機(jī)進(jìn)程B需要打印機(jī)例如：進(jìn)程A和B按下面的順序推進(jìn)，導(dǎo)致死鎖。

1.A：申請打印機(jī)

2B：申請讀卡機(jī)

3.A：申請讀卡機(jī)4.B：申請打印機(jī)進(jìn)程概念

進(jìn)程調(diào)度死鎖資源的部分分配需求某類資源的若干進(jìn)程；每次只能申請或被分配其完全需求資源的一部分進(jìn)程間非法交叉推進(jìn)出現(xiàn)相關(guān)進(jìn)程由于資源分配不當(dāng)而出現(xiàn)循環(huán)等待資源獨(dú)占性資源不能共享，外設(shè)只能由一個(gè)進(jìn)程用完才能為其他進(jìn)程所使用資源的不可剝奪性資源的非搶占式分配，一個(gè)進(jìn)程占用外設(shè)時(shí)，另一個(gè)進(jìn)程就不能把它奪過來，只能等待產(chǎn)生死鎖的四個(gè)必要條件進(jìn)程概念

進(jìn)程調(diào)度死鎖死鎖的預(yù)防破壞產(chǎn)生死鎖的4個(gè)必要條件中的任何一個(gè)死鎖的避免躲避死鎖的發(fā)生死鎖檢測與恢復(fù)允許死鎖產(chǎn)生，但能檢測出來并且有能力處理和恢復(fù)010203解決死鎖的辦法進(jìn)程概念

進(jìn)程調(diào)度死鎖破壞資源的部分分配每個(gè)進(jìn)程必須提出它所需要的全部資源，只有完全滿足時(shí)，才能啟動(dòng)進(jìn)程間非法交叉推進(jìn)系統(tǒng)所有資源進(jìn)行編號，并規(guī)定進(jìn)程申請資源時(shí)必須按照資源編號的順序進(jìn)行破壞資源獨(dú)占性采用假脫機(jī)技術(shù)（SPOOLing）可以使非共享設(shè)備變?yōu)楣蚕碓O(shè)備破壞資源的不可剝奪性申請不到資源時(shí)，釋放原先已占有的，進(jìn)入等待，以后再一起申請2.死鎖的預(yù)防提前確定系統(tǒng)資源分配算法，破壞產(chǎn)生死鎖的四個(gè)必要條件中的任何一個(gè)或幾個(gè)，以保證在系統(tǒng)運(yùn)行中不發(fā)生死鎖進(jìn)程概念

進(jìn)程調(diào)度死鎖采用虛擬技術(shù)，使非共享設(shè)備變成共享設(shè)備，以預(yù)防死鎖用戶1用戶2用戶3??????輸出輸出輸出打印打印機(jī)主機(jī)2.死鎖的預(yù)防進(jìn)程概念

進(jìn)程調(diào)度死鎖2.死鎖的預(yù)防系統(tǒng)資源進(jìn)行統(tǒng)一編號。進(jìn)程申請使用資源時(shí)，必須嚴(yán)格按照編號的升序進(jìn)行進(jìn)程A進(jìn)程B進(jìn)程C1、卡片輸入機(jī)（3臺）√√√2、行式打印機(jī)（2臺）√√*3、卡片輸入機(jī)（1臺）√*4、磁帶機(jī)（1臺）進(jìn)程概念

進(jìn)程調(diào)度死鎖3.死鎖的避免

為了避免死鎖的發(fā)生，系統(tǒng)對進(jìn)程提出的每一個(gè)資源請求，先不是真正去分配，而是根據(jù)當(dāng)時(shí)資源的使用情況，按一定的算法去進(jìn)行模擬分配后的結(jié)果。只有當(dāng)探測結(jié)果不會(huì)導(dǎo)致死鎖，才真正接收進(jìn)程提出的這一請求——銀行家算法。銀行家算法的思想:（假定在同類資源的分配上實(shí)行這一算法）系統(tǒng)接到一個(gè)進(jìn)程的資源請求后，就先假定承認(rèn)這一申請，把資源分配給它。然后系統(tǒng)用剩余的資源和每一個(gè)進(jìn)程還需要的資源數(shù)相比，看能否找到這樣的進(jìn)程，系統(tǒng)把資源分配給它后，就能滿足它對資源的最大需求，從而保證其運(yùn)行完畢。如果能就分配給它，系統(tǒng)在其運(yùn)行完后回收其占用的全部資源，就會(huì)有更多的剩余資源數(shù)。再重復(fù)這一過程，直到找不出這樣的進(jìn)程為止。請看下面示例：進(jìn)程已分配數(shù)還需要數(shù)A13B42C53系統(tǒng)剩余2進(jìn)程已分配數(shù)還需要數(shù)A22B42C53系統(tǒng)剩余1例：假定某系統(tǒng)有12臺磁帶機(jī)，A：最大需要量4，B：最大需要量6，C：最大需要量8銀