處理機(jī)調(diào)度與死鎖

《處理機(jī)調(diào)度與死鎖》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第三章　處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的層次3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則3.3調(diào)度算法3.4實時調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除處理機(jī)調(diào)度與死鎖(SchedulingandDeadlock)教學(xué)目的：在多道程序系統(tǒng)中，一個作業(yè)從提交到執(zhí)行完成，要經(jīng)歷多級調(diào)度，調(diào)度的好壞要影響系統(tǒng)的運行性能，因此調(diào)度是多道系統(tǒng)的關(guān)鍵。為了改善系統(tǒng)資源的利用率和提高系統(tǒng)處理能力，多道程序系統(tǒng)中采用多個進(jìn)程的并發(fā)執(zhí)行，但它也可能發(fā)生死鎖的危險，研究死鎖的原因和產(chǎn)生條件，采用預(yù)防死鎖

2、、避免死鎖、檢測死鎖和解除死鎖等多種方法防止死鎖是多道程序系統(tǒng)重要的研究課題。教學(xué)要求：熟悉處理機(jī)三級調(diào)度概念和處理機(jī)調(diào)度模型，掌握作業(yè)的狀態(tài)和作業(yè)調(diào)度的功能。掌握進(jìn)程調(diào)度的方式和功能，熟悉調(diào)度方式和算法的選擇準(zhǔn)則，掌握各種調(diào)度算法及適合范圍。掌握死鎖的定義和產(chǎn)生死鎖的原因，掌握死鎖的四個必要條件；熟悉預(yù)防死鎖的方法，熟練掌握銀行家算法及其在死鎖避免中的應(yīng)用；掌握資源分配圖的簡化及其死鎖定理，熟悉解除死鎖的方法。3.1處理機(jī)調(diào)度的層次3.1.1高級調(diào)度1．作業(yè)和作業(yè)步(1)作業(yè)(Job)。作業(yè)是一個比程序

3、更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對程序的運行進(jìn)行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。(2)作業(yè)步(JobStep)。通常，在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干個相對獨立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個加工步驟稱為一個作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入。例如，一個典型的作業(yè)可分成三個作業(yè)步：①“編譯”作業(yè)步，通過執(zhí)行編譯程序?qū)υ闯绦蜻M(jìn)行編譯，產(chǎn)生若干

4、個目標(biāo)程序段；②“連結(jié)裝配”作業(yè)步，將“編譯”作業(yè)步所產(chǎn)生的若干個目標(biāo)程序段裝配成可執(zhí)行的目標(biāo)程序；③“運行”作業(yè)步，將可執(zhí)行的目標(biāo)程序讀入內(nèi)存并控制其運行。(3)作業(yè)流。若干個作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，這便形成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個作業(yè)進(jìn)行處理，于是便形成了處理作業(yè)流。作業(yè)調(diào)度作業(yè)運行狀態(tài)外存外存(盤)交換區(qū)作業(yè)后備狀態(tài)作業(yè)提交狀態(tài)作業(yè)完成狀態(tài)終止作業(yè)就緒態(tài)阻塞態(tài)主存進(jìn)程調(diào)度運行態(tài)就緒態(tài)阻塞態(tài)調(diào)出調(diào)進(jìn)作業(yè)的狀態(tài):作業(yè)從進(jìn)入到運行結(jié)束，一般需要經(jīng)歷“提交”、“后備”、“運行”和

5、“完成”四個階段。提交狀態(tài)一個作業(yè)被提交給機(jī)房后正在通過SPOOLing系統(tǒng)進(jìn)行輸入或用戶通過終端向計算機(jī)中鍵入其作業(yè)時所處于的狀態(tài)為提交狀態(tài)。后備狀態(tài)作業(yè)已經(jīng)過SPOOLing系統(tǒng)輸入到磁盤輸入井，等待調(diào)入內(nèi)存運行，此時作業(yè)處于后備狀態(tài)。為了管理和調(diào)度作業(yè)，為每個作業(yè)設(shè)置一個作業(yè)控制塊（JCB）。作業(yè)控制塊記錄了作業(yè)類型和資源要求等有關(guān)信息。作業(yè)控制塊按作業(yè)類型組成一個或多個后備作業(yè)隊列。運行狀態(tài)一個在后備作業(yè)隊列的作業(yè)被作業(yè)調(diào)度程序選中后，分配必要的資源，建立一組相應(yīng)的進(jìn)程后，調(diào)入內(nèi)存，該作業(yè)就進(jìn)入運

6、行狀態(tài)。進(jìn)程各狀態(tài)（進(jìn)程運行態(tài)、內(nèi)存進(jìn)程就緒態(tài)、內(nèi)存阻塞態(tài)、外存進(jìn)程就緒態(tài)、外存進(jìn)程阻塞態(tài)等）都對應(yīng)作業(yè)運行狀態(tài)。完成狀態(tài)當(dāng)進(jìn)程正常運行結(jié)束或因發(fā)生錯誤而終止時，作業(yè)進(jìn)入完成狀態(tài)。終止作業(yè)程序?qū)⒇?fù)責(zé)善后處理。作業(yè)狀態(tài)的轉(zhuǎn)換:作業(yè)調(diào)度作業(yè)調(diào)度程序按一定算法從后備作業(yè)隊列中選一個滿足資源要求的作業(yè)，分配它所要求的資源，建立一組相應(yīng)的進(jìn)程，設(shè)置該進(jìn)程狀態(tài)為就緒態(tài)，并將該進(jìn)程插入內(nèi)存就緒隊列，參加CPU爭奪。終止作業(yè)當(dāng)進(jìn)程正常運行結(jié)束或因發(fā)生錯誤終止時，調(diào)用終止作業(yè)程序，它負(fù)責(zé)將輸出文件緩沖輸出到輸出井，并調(diào)用S

7、POOLing系統(tǒng)輸出進(jìn)程將作業(yè)輸出文件在打印機(jī)輸出。同時回收作業(yè)所使用內(nèi)、外存、I/O設(shè)備等各種資源，最后調(diào)用記帳程序結(jié)清作業(yè)費用。2．作業(yè)控制塊JCB(JobControlBlock)為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個作業(yè)設(shè)置了一個作業(yè)控制塊，如同進(jìn)程控制塊是進(jìn)程在系統(tǒng)中存在的標(biāo)志一樣，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。在JCB中所包含的內(nèi)容因系統(tǒng)而異，通常應(yīng)包含的內(nèi)容有：作業(yè)標(biāo)識、用戶名稱、用戶帳戶、作業(yè)類型(CPU繁忙型、I/O繁忙型、批量型、

8、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、作業(yè)已運行時間)、資源需求(預(yù)計運行時間、要求內(nèi)存大小、要求I/O設(shè)備的類型和數(shù)量等)、進(jìn)入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況等。每當(dāng)作業(yè)進(jìn)入系統(tǒng)時，系統(tǒng)便為每個作業(yè)建立一個JCB，根據(jù)作業(yè)類型將它插入相應(yīng)的后備隊列中。作業(yè)調(diào)度程序依據(jù)一定的調(diào)度算法來調(diào)度它們，被調(diào)度到的作業(yè)將會裝入內(nèi)存。在作業(yè)運行期間，系統(tǒng)就按照J(rèn)CB中的信息對作業(yè)進(jìn)行控制。當(dāng)一個作業(yè)執(zhí)行結(jié)