【正文】 每個部分稱為一個 作業(yè)步 。1 第 4章 處理機(jī)調(diào)度與死鎖 2 關(guān)于作業(yè)的幾個基本概念 概念 ： 用戶在一次計算或一次事務(wù)處理過程中，要求計算機(jī)系統(tǒng)所做 工作的總稱 。作業(yè)由 程序、數(shù)據(jù)、作業(yè)說明書 構(gòu)成。在作業(yè)運(yùn)行期間，各作業(yè)步之間存在著相互聯(lián)系，往往上一個作業(yè)步的結(jié)果作為下一個作業(yè)步的輸入。 作業(yè)說明書有兩部分內(nèi)容： 作業(yè)情況描述 （如用戶名、作業(yè)名、用戶帳號、使用語言、作業(yè)步驟、控制方式、優(yōu)先級、專用文件、時間限制、有關(guān)注釋等）和 作業(yè)對資源的需求描述 （如參數(shù)設(shè)置、系統(tǒng)配置、空間需求、輸入輸出設(shè)備、估計運(yùn)行時間等） 5 關(guān)于作業(yè)的幾個基本概念 概念 （ JCB）： 作業(yè)控制塊是作業(yè)存在的 唯一標(biāo)志 ，是系統(tǒng)為管理作業(yè)所設(shè)置的一個數(shù)據(jù)結(jié)構(gòu)，存放了管理和控制作業(yè)所必須的信息。通常的 科學(xué)計算 就屬于 CPU繁忙型的作業(yè)。 目前大多數(shù)的事務(wù)處理都屬于 I/O繁忙型作業(yè) 7 關(guān)于作業(yè)的幾個基本概念 ? 作業(yè)是操作系統(tǒng)中最古老的名詞之一，作業(yè)管理的功能是所有操作系統(tǒng)的基本功能。 8 ? 作業(yè)的建立過程 ? 作業(yè)的建立是指把作業(yè)所包含的全部程序和數(shù)據(jù)輸入到計算機(jī)的外部輔存中，并為作業(yè)申請一個作業(yè)控制塊（ JCB）的過程。當(dāng)作業(yè)完成后，系統(tǒng)會撤銷其 JCB，同時釋放系統(tǒng)占用的資源。 包括作業(yè)名、作業(yè)狀態(tài)、作業(yè)優(yōu)先級和作業(yè)類型。 包括要求運(yùn)行的時間、最遲結(jié)束時間、所需主存空間、所需外設(shè)的種類和數(shù)量等。 包括作業(yè)進(jìn)入系統(tǒng)的時間、開始運(yùn)行時間、已經(jīng)運(yùn)行時間和內(nèi)存地址等。那么應(yīng)該選擇哪些作業(yè)讓它們先執(zhí)行呢？ ? 操作系統(tǒng)根據(jù)允許并發(fā)執(zhí)行的作業(yè)道數(shù)和一定的算法，從 作業(yè)后備隊列 中選取若干作業(yè)裝入內(nèi)存，使它們能夠獲得處理器運(yùn)行，這項工作稱為 作業(yè)調(diào)度 ，完成這項工作的程序稱為作業(yè)調(diào)度程序。 ? 收容狀態(tài) ：又稱后備狀態(tài)。 13 ?高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度） 運(yùn)行狀態(tài)： 外存上的作業(yè)被選中調(diào)入內(nèi)存，為其分配必要的資源，建立 一組相應(yīng)的進(jìn)程 后，作業(yè)就由后備狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)。 完成狀態(tài)： 作業(yè)正常完成或因錯誤而終止運(yùn)行時進(jìn)入完成狀態(tài)。 14 ?高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度） ? 高級調(diào)度又稱作業(yè)調(diào)度或長程調(diào)度， 它的功能是按照某種原則從后備作業(yè)隊列中選取若干作業(yè)進(jìn)入主存 ? 用于決定把外存中處于后備隊列中的哪些作業(yè)調(diào)入內(nèi)存 ， 并為它們建立進(jìn)程，分配必要的資源，然后再將新建立的進(jìn)程排在就緒隊列上，準(zhǔn)備執(zhí)行。 15 ?高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度 ） ? 在批處理系統(tǒng)中， 作業(yè)進(jìn)入系統(tǒng)后是先駐留在外存 上的，需要有作業(yè)調(diào)度的過程，以便將其分批地裝入內(nèi)存。 16 ?高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度） 每次執(zhí)行作業(yè)調(diào)度時都必須作出決定： 1）接納多少個作業(yè) 即允許多少個作業(yè)同時在內(nèi)存中運(yùn)行。 最 簡單的 是先來先服務(wù)調(diào)度算法，即較早調(diào)入外存的先調(diào)入內(nèi)存。 ? 引入 中級調(diào)度的主要目的，是 為了提高內(nèi)存利用率和系統(tǒng)吞吐量。 18 ? 當(dāng)這些進(jìn)程重又具備運(yùn)行條件，且內(nèi)存又稍有空閑時，由中級調(diào)度決定把外存上的那些又具備運(yùn)行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒，掛在就緒隊列上等待進(jìn)程調(diào)度。 20 低級調(diào)度 ? 進(jìn)程調(diào)度是最基本的調(diào)度， 在三種基本類型的 OS中，都必須配備這一級調(diào)度 ? 進(jìn)程調(diào)度可采用兩種調(diào)度方法： 1）非搶占方式 2）搶占方式 21 1）非搶占方式 一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或發(fā)生某事件而被阻塞時，才把處理機(jī)分配給其它進(jìn)程，絕不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。 搶占的原則有： ①優(yōu)先權(quán)原則 ②短作業(yè)（進(jìn)程）優(yōu)先原則 ③時間片原則 24 ?三種調(diào)度的運(yùn)行頻率 ? 在三種調(diào)度中， 進(jìn)程調(diào)度 的頻率最高，在分時系統(tǒng)中通常是 10100ms便進(jìn)行一次進(jìn)程調(diào)度，因而進(jìn)程調(diào)度算法不能太復(fù)雜，以免占用太多 CPU的時間。作業(yè) i的帶權(quán)周轉(zhuǎn)時間為： Wi=Ti/Tri 其中 Ti為作業(yè) i的周轉(zhuǎn)時間， Tri為作業(yè) i的實際運(yùn)行時間 ： 多個作業(yè)帶權(quán)周轉(zhuǎn)時間的平均值 W=（ W1+W2+…… + Wn） /n 28 常用的作業(yè)調(diào)度算法 （ FCFS）： ? 按作業(yè)到達(dá)系統(tǒng)的先后順序進(jìn)行調(diào)度。 ? 這種算法簡單，易于實現(xiàn)，但效率低， 對短作業(yè)不利。 29 例 .有三個作業(yè)按下表的時間提交給系統(tǒng)，按照先來先服務(wù)的調(diào)度算法計算它們的 平均周轉(zhuǎn)時間 T和平均帶權(quán)周轉(zhuǎn)時間W 作業(yè)號 提交時刻 運(yùn)行長度 1 10： 00 2小時 2 10： 06 1小時 3 10:15 ?按照 先來先服務(wù) 的原則，可以計算出各個作業(yè)在系統(tǒng)中的開始時刻、結(jié)束時刻，以及各自在系統(tǒng)中的周轉(zhuǎn)時間。 ? 這種算法易于實現(xiàn)，效率也比較高，能獲得理想的 作業(yè)平均周轉(zhuǎn)時間 。但未考慮作業(yè)的等待時間，有可能使執(zhí)行時間長的長時間處于等待， 對長作業(yè)極為不利 。 即作業(yè)調(diào)度的次序為： 作業(yè) 1作業(yè) 3作業(yè) 2作業(yè) 4 40 按響應(yīng)比高者優(yōu)先算法調(diào)度作業(yè)： 根據(jù)前面導(dǎo)出的表，可計算出 4個作業(yè)的 平均周轉(zhuǎn)時間 T和平均帶權(quán)周轉(zhuǎn)時間 W為： T=（ 2+++） /4= W=（ +++） /4= 41 進(jìn)程調(diào)度 ? 通常把正準(zhǔn)備進(jìn)入內(nèi)存的任務(wù)稱為作業(yè)，而作業(yè)被選中調(diào)入內(nèi)存后，系統(tǒng)便要為作業(yè)建立 一組進(jìn)程 ，這組進(jìn)程協(xié)同運(yùn)行，共同完成作業(yè)。 42 進(jìn)程調(diào)度 ? 進(jìn)程管理的主要功能是把處理機(jī)分配給進(jìn)程，并協(xié)調(diào)各個進(jìn)程之間的相互關(guān)系。 ? 進(jìn)程調(diào)度程序的功能 是根據(jù)一定的調(diào)度原則，確定處理機(jī)應(yīng)分配給就緒進(jìn)程中的哪一個，何時分配，分配時間的長短等。 43 進(jìn)程調(diào)度的方式 ? 剝奪式： 當(dāng)系統(tǒng)按照某種原則發(fā)現(xiàn)一個比現(xiàn)運(yùn)行的進(jìn)程更合適、更應(yīng)該占用 CPU的進(jìn)程時，系統(tǒng)將強(qiáng)迫處于運(yùn)行狀態(tài)的進(jìn)程將 CPU的使用權(quán)交給這個更合適的進(jìn)程。 ? 非剝奪式： 一旦某個進(jìn)程占用了 CPU，除非是由于它自身的原因自動放棄 CPU，否則它將一直運(yùn)行下去直到完成。 ? 該算法采用 非剝奪調(diào)度方式 ，即一旦某個進(jìn)程占據(jù)處理機(jī)，就一直運(yùn)行下去，直到該進(jìn)程完成其工作或因等待某一事件而不能繼續(xù)執(zhí)行時才釋放處理機(jī) 46 １．先來先服務(wù)調(diào)度算法（續(xù)） ? 若采用先來先服務(wù)調(diào)度算法，并且一個運(yùn)行時間長的進(jìn)程先占有了處理機(jī)，則會使很多晚到的運(yùn)行時間短的進(jìn)程等待時間過長， 引起短進(jìn)程用戶的不滿。 47 進(jìn)程的調(diào)度算法： ? 是一種最常用的進(jìn)程調(diào)度算法，其基本思想是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程 ? 進(jìn)程的優(yōu)先權(quán)用于表示進(jìn)程的重要性及運(yùn)行的優(yōu)先性。 ? 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程的時候確定的，確定之后在整個進(jìn)程的運(yùn)行期間不再改變。進(jìn)程索取的資源越多，估計的運(yùn)行時間越長，進(jìn)程的優(yōu)先級就會越低；進(jìn)程的類型不同，優(yōu)先權(quán)也不同，如 聯(lián)機(jī)用戶進(jìn)程的優(yōu)先權(quán)高于脫機(jī)用戶進(jìn)程的優(yōu)先權(quán) 等。 ? 動態(tài)優(yōu)先權(quán)一般根據(jù)進(jìn)程占有 CPU時間的長短、進(jìn)程等待 CPU時間的長短等因素確定 ? 占有處理機(jī)的時間越長，則優(yōu)先級越低；等待時間越長，則優(yōu)先級越高。 ? 非剝奪優(yōu)先權(quán)調(diào)度 的思想是一旦把處理機(jī)分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程就一直運(yùn)行下去，直到由于其自身的原因主動讓出處理機(jī)，才將處理機(jī)分配給另一個更高優(yōu)先權(quán)的進(jìn)程。在進(jìn)程運(yùn)行期間，一旦出現(xiàn)了另一個優(yōu)先權(quán)更高的進(jìn)程時，進(jìn)程調(diào)度就停止原進(jìn)程的運(yùn)行，將處理機(jī)分配給新出現(xiàn)的高優(yōu)先級進(jìn)程。當(dāng)該運(yùn)行進(jìn)程用完規(guī)定的時間片，就被迫釋放處理機(jī)給下一個處于就緒隊列中的第一個進(jìn)程。只有當(dāng)它需要的 I/O操作完畢之后，才能重新返回到就緒隊列的尾部，等待時機(jī)成熟再投入運(yùn)行。 ? 如果時間片足夠大 ，以至于所有進(jìn)程都能在一個時間片內(nèi)執(zhí)行完畢 ， 則時間片輪轉(zhuǎn)調(diào)度算法就退化成先來先服務(wù)調(diào)度算法。因此時間片的大小應(yīng)選擇適當(dāng)。如短進(jìn)程優(yōu)先算法僅照顧了短進(jìn)程而忽略了長進(jìn)程；而且若未指明進(jìn)程的長度，則短進(jìn)程優(yōu)先調(diào)度就無法使用。 55 ? 首先 應(yīng)設(shè)置多個就緒隊列，并為各個作業(yè)賦予不同的優(yōu)先級。進(jìn)程所在的隊列優(yōu)先權(quán)越高，時間片越短，如第 i+1隊列的時間片是第 i隊列的 2倍 56 （續(xù)） ? 第三， 當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一個隊列的末尾，按先來先服務(wù)的原則排隊等待調(diào)度。 ? 當(dāng)處理機(jī)正在為第 i個隊列中的某進(jìn)程服務(wù)時，若又有新進(jìn)程進(jìn)入優(yōu)先權(quán)高的隊列，則此時新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在執(zhí)行的進(jìn)程放回第 i個隊列末尾，重新將處理機(jī)分配給新進(jìn)程。 ? 所謂死鎖是指 多個進(jìn)程 在運(yùn)行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵局的時候，若沒有外力的干預(yù)，它們都將無法再向前推進(jìn)。處于死鎖狀態(tài)的進(jìn)程稱為死鎖進(jìn)程。死鎖 與時間相關(guān) ，不易重現(xiàn)。 ? 死鎖 與 饑餓 不同 ? 生活舉例 62 ?產(chǎn)生死鎖的根本原因 ? 一是系統(tǒng)提供的資源有限，不能滿足每個進(jìn)程的需要； ? 二是多道程序運(yùn)行時，進(jìn)程推進(jìn)順序不合理 63 ?死鎖產(chǎn)生的 4個必要條件 ? 雖然在多道程序環(huán)境下可能會發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件。 68 ?死鎖產(chǎn)生的 4個必要條件