【文章內(nèi)容簡介】 隊(duì)列調(diào)度算法 則不必事先知道各進(jìn)程所需要的執(zhí)行時(shí)間，而且還可以滿足各種進(jìn)程的需要，因而它是目前公認(rèn)的一種較好的進(jìn)程調(diào)度算法。 55 ? 首先 應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)作業(yè)賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，以后各隊(duì)列依次降低； ? 其次 ，每個(gè)隊(duì)列的進(jìn)程執(zhí)行的時(shí)間片大小各不相同。進(jìn)程所在的隊(duì)列優(yōu)先權(quán)越高，時(shí)間片越短，如第 i+1隊(duì)列的時(shí)間片是第 i隊(duì)列的 2倍 56 （續(xù)） ? 第三， 當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一個(gè)隊(duì)列的末尾，按先來先服務(wù)的原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行的時(shí)候，若能在此時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果未能在一個(gè)時(shí)間片內(nèi)完成，調(diào)度程序便將其調(diào)度進(jìn)入第二個(gè)隊(duì)列的末尾；如果它仍不能在第二個(gè)隊(duì)列中完成，則轉(zhuǎn)入第三個(gè)隊(duì)列 … 57 （續(xù)） ? 第四， 僅當(dāng)?shù)谝粋€(gè)隊(duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二個(gè)隊(duì)列中的程序運(yùn)行；僅當(dāng)?shù)?1至第 (i1)個(gè)隊(duì)列均為空時(shí)，才會(huì)調(diào)度第 i個(gè)隊(duì)列中的進(jìn)程運(yùn)行。 ? 當(dāng)處理機(jī)正在為第 i個(gè)隊(duì)列中的某進(jìn)程服務(wù)時(shí)，若又有新進(jìn)程進(jìn)入優(yōu)先權(quán)高的隊(duì)列，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在執(zhí)行的進(jìn)程放回第 i個(gè)隊(duì)列末尾，重新將處理機(jī)分配給新進(jìn)程。 58 死鎖問題 死鎖的定義和產(chǎn)生條件 ? 在多道程序系統(tǒng)中，我們借助于多道程序的并發(fā)執(zhí)行來提高系統(tǒng)的資源利用率和吞吐量，但進(jìn)程并發(fā)可能會(huì)帶來一種危險(xiǎn) —— 死鎖。 ? 所謂死鎖是指 多個(gè)進(jìn)程 在運(yùn)行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵局的時(shí)候，若沒有外力的干預(yù)，它們都將無法再向前推進(jìn)。 59 死鎖問題 死鎖的定義和產(chǎn)生條件 ? 死鎖的定義 1： 在系統(tǒng)中某個(gè)進(jìn)程提出資源申請(qǐng)后，使得 若干進(jìn)程在沒有外力的作用的情況下永遠(yuǎn)不能前進(jìn)，這種現(xiàn)象稱為 死鎖 。處于死鎖狀態(tài)的進(jìn)程稱為死鎖進(jìn)程。 60 死鎖問題 死鎖的定義和產(chǎn)生條件 ? 死鎖定義 2 指兩個(gè)或兩個(gè)以上的進(jìn)程因競爭系統(tǒng)資源或相互通信而處于永久阻塞狀態(tài)，每一個(gè)都在等待另一個(gè)進(jìn)程釋放資源而被封鎖，若無外力作用下，這些進(jìn)程都無法向前推進(jìn) ? 死鎖大多由于并發(fā)進(jìn)程共享臨界資源引起的。死鎖 與時(shí)間相關(guān) ，不易重現(xiàn)。 61 死鎖問題 死鎖的定義和產(chǎn)生條件 ? 死鎖不僅在計(jì)算機(jī)系統(tǒng)中，在生活中也常見。 ? 死鎖 與 饑餓 不同 ? 生活舉例 62 ?產(chǎn)生死鎖的根本原因 ? 一是系統(tǒng)提供的資源有限，不能滿足每個(gè)進(jìn)程的需要； ? 二是多道程序運(yùn)行時(shí)，進(jìn)程推進(jìn)順序不合理 63 ?死鎖產(chǎn)生的 4個(gè)必要條件 ? 雖然在多道程序環(huán)境下可能會(huì)發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件。 64 死鎖產(chǎn)生的 4個(gè)必要條件 —— 死鎖引例： 兩個(gè) 并發(fā)進(jìn)程 P P2運(yùn)行中都要使用 臨界資源：文件 F和磁帶機(jī) T,就可能會(huì)發(fā)生死鎖： P1（ ） P2（ ） {…… {…… 申請(qǐng)文件 F； 申請(qǐng)磁帶機(jī) T； 申請(qǐng)磁帶機(jī) T； 申請(qǐng)文件 F； …… …… 釋放磁帶機(jī) T； 釋放文件 F； 釋放文件 F； 釋放磁帶機(jī) T …… } } 65 ?死鎖產(chǎn)生的 4個(gè)必要條件 （ 1）互斥使用條件 在一段時(shí)間里，一個(gè)資源只能由一個(gè)進(jìn)程獨(dú)占使用，若別的進(jìn)程也要求該資源，則必須等待直至占有資源的進(jìn)程釋放該資源 66 ?死鎖產(chǎn)生的 4個(gè)必要條件 （ 2）保持和等待條件 指進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程進(jìn)入阻塞狀態(tài)，但又對(duì)自己已經(jīng)獲得的資源保持不放，即 允許進(jìn)程在 不釋放其已分得資源的情況下 ，請(qǐng)求并等待分配新的資源 67 ?死鎖產(chǎn)生的 4個(gè)必要條件 （ 3）不剝奪條件 進(jìn)程所獲得的資源在未使用完之前，不能被其它進(jìn)程強(qiáng)行奪走，而只能由其自行釋放 （ 4）環(huán)路等待條件 在系統(tǒng)中存在一個(gè)等待進(jìn)程的集合： P0正在等待一個(gè) P1占用的資源， P1正在等待一個(gè) P2占用的資源， …… ， Pn正在等待一個(gè) P0占用的資源。 68 ?死鎖產(chǎn)生的 4個(gè)必要條件 注意： 這 4個(gè)條件是死鎖產(chǎn)生的 必要條件 ， 不是充分條件 。 換句話說，如果發(fā)生了死鎖，那么這 4個(gè)條件一定同時(shí)成立；反之，這 4個(gè)條件同時(shí)成立，卻不一定會(huì)產(chǎn)生死鎖。 這里可能出判斷題： （ 1） 如一組進(jìn)程正在循環(huán)等待資源，它們一定會(huì)發(fā)生死鎖嗎？ （ 2）一組進(jìn)程發(fā)生了死鎖，它們一定在循環(huán)等待資源嗎？ 69 ?關(guān)于死鎖的進(jìn)一步說明 1）死鎖是進(jìn)程之間的一種特殊關(guān)系，是由資源競爭引起的僵局關(guān)系。死鎖至少要涉及兩個(gè)進(jìn)程。 2）當(dāng)出現(xiàn)死鎖時(shí)要先弄清被鎖的是哪些進(jìn)程，因競爭哪些資源引起 3）在多數(shù)情況下所說的死鎖，是指系統(tǒng)內(nèi)的一些而不是全部進(jìn)程被鎖，它們是因?yàn)楦偁幠承┒皇侨抠Y源而進(jìn)入死鎖。若系統(tǒng)的全部進(jìn)程都被鎖，稱系統(tǒng)處于 癱瘓狀態(tài) 。 70 解決死鎖的基本方法 解決死鎖的基本方法有三種 （注意填空）： ? 死鎖的預(yù)防 ? 死鎖的避免 ? 死鎖的檢測與恢復(fù) 71 （ 1） ? 死鎖的預(yù)防主要是打破造成死鎖的 4個(gè)必要條件之一： （ 1）破壞 “ 互斥 ” 條件 （ 2）破壞 “ 占用并等待 ” 條件 （ 3）破壞 “ 不可剝奪 ” 條件 （ 4）破壞 “ 循環(huán)等待 ” 條件 72 （ 2） （ 1）破壞 “ 互斥 ” 條件 該條無法做到。因?yàn)橛?jì)算機(jī)系統(tǒng)中大多數(shù)資源必須互斥使用，所以無法使互斥條件不成立而防止死鎖，相反還必須嚴(yán)格遵守互斥使用資源的要求。 易出判斷題、填空題、選擇題。 73 （ 3） （ 2）破壞 “ 占用并等待 ” 條件 可以采用 靜態(tài)分配策略 。 ? 靜態(tài)分配就是要求每一個(gè)進(jìn)程在開始執(zhí)行前就一次性申請(qǐng)它所需要的 全部資源 。 ? 僅當(dāng)系統(tǒng)能滿足進(jìn)程全部資源要求并把資源分配給進(jìn)程后，該進(jìn)程才能開始執(zhí)行，否則，只要有一種資源不能滿足，即使其它資源空閑也不分配，讓該進(jìn)程等待。在等待期間，該進(jìn)程不占有任何資源。 ? 這種策略也稱 “ 預(yù)分配資源法 ” ， 該方法實(shí)現(xiàn)簡單，但降低了資源的利用率。 74 （ 5） ? （ 3）破壞 “ 不可剝奪 ” 條件 方法：進(jìn)程需要的資源不是一次性分配給它，而是在運(yùn)行的過程中，它需要的時(shí)候才進(jìn)行分配。當(dāng)一個(gè)進(jìn)程已占有了某些資源，又申請(qǐng)新的資源而不能立即得到滿足時(shí)，該進(jìn)程將被剝奪已占有的全部資源，進(jìn)入阻塞狀態(tài)。只有在進(jìn)程重新獲得 了原有資源和新資源后，才能繼續(xù)執(zhí)行。 75 （ 5） （ 3）破壞 “ 不可剝奪 ” 條件（續(xù)） 目前這種分配策略只能用于主存空間和處理器資源的分配，而對(duì)打印機(jī)、磁帶機(jī)等不能采取這種分配策略。 76 （ 6） （ 4）破壞 “ 環(huán)路等待 ” 條件 可采用 按序分配資源策略， 具體做法是： ? 把系統(tǒng)中所有的資源都按類型順序排列，并對(duì)每類資源確定一個(gè)序號(hào)，如掃描儀、輸入機(jī)、打印機(jī)、磁盤的編號(hào)依次為 4，每個(gè)進(jìn)程對(duì)資源的申請(qǐng)要嚴(yán)格按照序號(hào)遞增的次序進(jìn)行。 ? 一個(gè)進(jìn)程申請(qǐng)資源時(shí)，要先申請(qǐng)編號(hào)小的資源，才能申請(qǐng)編號(hào)大的資源；釋放資源則正好相反，要先釋放編號(hào)大的，再釋放編號(hào)小的資源。這樣系統(tǒng)中就不會(huì)產(chǎn)生進(jìn)程等待環(huán)路，從而破壞了循環(huán)等待條件。 77 （ 6） ? （ 4）破壞 “ 循環(huán)等待 ” 條件 這種預(yù)防死鎖的方法雖然較前面兩種資源利用率高，但也存在下面問題： （ a）資源編號(hào)不容易合理化，從而造成資源浪費(fèi)。如進(jìn)程 P使用的資源是 r4， r1， r3， r7，當(dāng)它申請(qǐng) r4時(shí)必先申請(qǐng)資源 r r3，造成資源浪費(fèi)。 （ b）按編號(hào)申請(qǐng)資源的的方法限制了用戶簡單自主地編程。 （ c）當(dāng)系統(tǒng)增加新的設(shè)備類型時(shí)，要重新對(duì)系統(tǒng)資源進(jìn)行合理編號(hào)，但這樣做很困難。 78 解決死鎖的策略 2—— 死鎖的避免（ 1） 死鎖的避免是指通過某種算法，當(dāng)系統(tǒng)分配資源時(shí)始終能做出是否分配的正確選擇，從而避免死鎖。 目前運(yùn)用的避免死鎖的算法是 的 銀行家算法 79 （ 2） 銀行家算法的思想是： 假如一家銀行擁有資金 2021萬，現(xiàn)有 10家公司向其貸款進(jìn)行籌建，每家均需 300萬才能建成。如果這家銀行將 2021萬的資金平均貸給這 10家公司，則每家公司可得到 200萬的貸款，都不能籌建成功，也就不能還貸，這 10家公司都將 “ 死鎖 ” 。 若給其中的 4家各貸 300萬， 另 4家各貸 200萬，這樣還有 2家公司得不到貸款，不能開工建設(shè)，但有 4家可籌建完成，這 4家公司運(yùn)營所得的利潤可向銀行還貸，銀行可利用還貸的資金繼續(xù)向其它公司貸款，從而保證了所有公司籌建成功投入運(yùn)營。 80 （ 2）