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

3.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)

3.11 處理機(jī)調(diào)度的層次

1.高級(jí)調(diào)度

高級(jí)調(diào)度又稱長程調(diào)度或作業(yè)調(diào)度昼牛，它的調(diào)度對(duì)象是作業(yè)佳遂。其主要功能是根據(jù)某種算法決定將外存上處于后備隊(duì)列中的那幾個(gè)作業(yè)調(diào)入內(nèi)存豁延，為他們創(chuàng)建進(jìn)程之拨、分配必要的資源佑笋，并將他們放入就緒隊(duì)列寄狼。高級(jí)調(diào)度主要用于多道批處理系統(tǒng)中寺滚，而在分時(shí)系統(tǒng)中不設(shè)置高級(jí)調(diào)度柑营。

2.低級(jí)調(diào)度

低級(jí)調(diào)度又稱為進(jìn)程調(diào)度或短程調(diào)度，其所調(diào)度的對(duì)象是進(jìn)程或內(nèi)核級(jí)線程村视。其主要功能是根據(jù)某種算法決定就緒隊(duì)列中的那幾個(gè)進(jìn)程獲得處理機(jī)官套，并由處理機(jī)分配給被選中的進(jìn)程。進(jìn)程調(diào)度是最基本的一種調(diào)度蚁孔，在多道批處理虏杰、分時(shí)、實(shí)時(shí)多種類型的OS種都必須配置這級(jí)調(diào)度勒虾。

3.中級(jí)調(diào)度

中級(jí)調(diào)度又稱為內(nèi)存調(diào)度纺阔。引入中級(jí)調(diào)度的主要目標(biāo)是提高內(nèi)存利用率和系統(tǒng)吞吐量。

在上述三種調(diào)度中修然，進(jìn)程調(diào)度的運(yùn)行頻率最高笛钝。

3.1.2 處理機(jī)調(diào)度算法的目標(biāo)

一般而言在一個(gè)操作系統(tǒng)中，應(yīng)如何選擇調(diào)度方式和算法愕宋，在很大程度上取決于操作系統(tǒng)的類型及其設(shè)計(jì)目標(biāo)玻靡。

1.處理機(jī)調(diào)度算法的共同目標(biāo)

1. 資源利用率
2. 公平性
3. 平衡性
4. 策略強(qiáng)制執(zhí)行

2.批處理系統(tǒng)的目標(biāo)

1. 平均周轉(zhuǎn)時(shí)間短
2. 系統(tǒng)吞吐量
3. 處理機(jī)利用率高

3.分時(shí)系統(tǒng)的目標(biāo)

1. 響應(yīng)時(shí)間塊
2. 均衡性

4.實(shí)時(shí)系統(tǒng)的目標(biāo)

1. 截止時(shí)間的保證
2. 可預(yù)測性

3.2作業(yè)與作業(yè)調(diào)度

作業(yè)是用戶提交給系統(tǒng)的一項(xiàng)相對(duì)獨(dú)立的工作。

3.2.1 批處理系統(tǒng)中的作業(yè)

1.作業(yè)和作業(yè)步

1. 作業(yè)中贝。是一個(gè)比進(jìn)程更為廣泛的概念囤捻，不僅包含通常的程序和數(shù)據(jù)，且還應(yīng)配有一份作業(yè)說明書邻寿，系統(tǒng)根據(jù)說明書來對(duì)程序的運(yùn)行進(jìn)行控制蝎土。在批處理系統(tǒng)中视哑，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的
2. 作業(yè)步。在作業(yè)運(yùn)行期間誊涯，每隔作業(yè)都必須經(jīng)過若干個(gè)相對(duì)獨(dú)立挡毅，相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果。將其中每一個(gè)加工步驟稱為一個(gè)作業(yè)步暴构。

2.作業(yè)控制塊

為了管理和調(diào)度作業(yè)跪呈，在多道批處理系統(tǒng)中，為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊JCB取逾，它是作業(yè)在系統(tǒng)中存在的標(biāo)志耗绿，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。常在JCB中包含的內(nèi)容有： 作業(yè)標(biāo)識(shí)砾隅、用戶名稱误阻、用戶賬號(hào)、作業(yè)類型（CPU繁忙型琉用、I/O繁忙型堕绩、批量型策幼、終端型）邑时、作業(yè)狀態(tài)、調(diào)度信息（優(yōu)先級(jí)特姐、作業(yè)運(yùn)行時(shí)間）資源需求（預(yù)計(jì)運(yùn)行時(shí)間晶丘、要求內(nèi)存大小等）、資源使用情況等唐含。

每當(dāng)一個(gè)作業(yè)進(jìn)入系統(tǒng)時(shí)浅浮，便由“作業(yè)注冊(cè)”程序?yàn)楦淖鳂I(yè)建立一個(gè)作業(yè)控制塊JCB。

3.作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)

作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束捷枯，通常需要經(jīng)歷收容滚秩、運(yùn)行和完成三個(gè)階段。相應(yīng)的作業(yè)也就有“后備狀態(tài)”淮捆、“運(yùn)行狀態(tài)”郁油、和“完成狀態(tài)”

• 收容階段：操作員把用戶提交的作業(yè)通過某種輸入方式或SPOOLing系統(tǒng)輸入到硬件，再為改作業(yè)建立JCB攀痊，并把它放入作業(yè)后備隊(duì)列種桐腌。相應(yīng)的，此時(shí)作業(yè)的狀態(tài)為“后備狀態(tài)”苟径。
• 運(yùn)行階段：當(dāng)作也備作業(yè)調(diào)度選中后案站，便為它分配必要的資源和建進(jìn)程，并將其放入就緒隊(duì)列棘街，一個(gè)作業(yè)從第一次進(jìn)入就緒狀態(tài)開始蟆盐，直到它運(yùn)行結(jié)束前承边，在此期間都稱為運(yùn)行狀態(tài)。
• 完成階段：當(dāng)作業(yè)完成舱禽、或發(fā)生異常情況而提前結(jié)束時(shí)炒刁，作業(yè)便進(jìn)入完成階段，相應(yīng)的作業(yè)狀態(tài)被稱為“完成狀態(tài)”誊稚。

3.2.2作業(yè)調(diào)度的任務(wù)

作業(yè)調(diào)度的主要內(nèi)容是翔始，根據(jù)JCB中的信息，檢查系統(tǒng)中的資源能否滿足作業(yè)對(duì)資源的需求里伯，以及按照一定的調(diào)度算法城瞎，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存并為他們創(chuàng)建進(jìn)程、分配必要的資源疾瓮。然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上等待調(diào)度脖镀。因此也把作業(yè)調(diào)度稱為接納調(diào)度。在每次執(zhí)行作業(yè)調(diào)度時(shí)狼电，都需要做出兩個(gè)決定：

1. 接納多少作業(yè)
2. 接納哪些作業(yè)

3.2.3作業(yè)調(diào)度算法

1.先來先服務(wù)（first-come first-service蜒灰，F(xiàn)CFS）調(diào)度算法

FCFS是最簡單的調(diào)度算法，該算法既可以用于作業(yè)調(diào)度肩碟，也可以用于進(jìn)程調(diào)度

2.短作業(yè)優(yōu)先（short job first强窖，SJF）的調(diào)度算法

SJF是以作業(yè)的長短來計(jì)算優(yōu)先級(jí)，作業(yè)越短削祈，其優(yōu)先級(jí)越高翅溺。

缺點(diǎn)：

1. 必須預(yù)知作業(yè)的運(yùn)行時(shí)間
2. 對(duì)長作業(yè)非常不利
3. 在采用SJF算法時(shí)，人——機(jī)無法實(shí)現(xiàn)交互
4. 該調(diào)度算法完全未考慮作業(yè)的緊迫程度髓抑，故不能保證緊迫性作業(yè)能及時(shí)得到處理

3.優(yōu)先級(jí)調(diào)度算法（priority-scheduling algorithm咙崎，PSA）

在優(yōu)先級(jí)調(diào)度算法中則是基于作業(yè)的緊迫程度，由外部賦予作業(yè)相應(yīng)的優(yōu)先級(jí)吨拍，調(diào)度算法是根據(jù)優(yōu)先級(jí)進(jìn)行調(diào)度的褪猛。這樣就可以保證緊迫性作業(yè)優(yōu)先運(yùn)行。

４.高響應(yīng)比優(yōu)先調(diào)度算法（Highest　Response　Ratio　Next羹饰，HRRN）

高響應(yīng)比優(yōu)先調(diào)度算法即考慮作業(yè)的等待時(shí)間伊滋，又考慮了作業(yè)運(yùn)行時(shí)間的調(diào)度算法，因此即兼顧隊(duì)了短作業(yè)严里，又不致長作業(yè)的等待時(shí)間過長新啼，從而改善了處理機(jī)調(diào)度的性能。

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

3.3.1 進(jìn)程調(diào)度的任務(wù)刹碾、機(jī)制和方式

１.進(jìn)程的任務(wù)

1. 保存處理機(jī)的現(xiàn)場信息
2. 按某種算法選取進(jìn)程
3. 把處理器分配給進(jìn)程燥撞。

２.進(jìn)程調(diào)度機(jī)制

• 排隊(duì)器
  • 為了提高進(jìn)程調(diào)度的效率，應(yīng)事先將系統(tǒng)中的所有就緒進(jìn)程按照一定的策略拍成一個(gè)或多個(gè)隊(duì)列，以便調(diào)度程序能最快的找到它物舒。以后每當(dāng)有一個(gè)進(jìn)程轉(zhuǎn)變未就緒狀態(tài)時(shí)色洞，排隊(duì)器便將它插入到相應(yīng)的就緒隊(duì)列
• 分派器
  • 分派器依據(jù)進(jìn)程調(diào)度程序所選定的進(jìn)程，將其從就緒隊(duì)列中取出冠胯，然后進(jìn)行從分派器到新選出進(jìn)程間的上下文切換火诸，將處理機(jī)分配給新選出的進(jìn)程。
• 上下文切換器

３.進(jìn)程調(diào)度方式

1. 非搶占方式
2. 搶占方式
   1. 優(yōu)先權(quán)原則
   2. 短進(jìn)程優(yōu)先原則
   3. 時(shí)間片原則

3.3.2輪轉(zhuǎn)調(diào)度算法

１.輪轉(zhuǎn)法的基本原理

在輪轉(zhuǎn)（RR）法中荠察，系統(tǒng)根據(jù)FCFS策略置蜀，將所有的就緒進(jìn)程排成一個(gè)就緒隊(duì)列，設(shè)置每個(gè)一定時(shí)間間隔（如３０毫秒）即產(chǎn)生一次中斷悉盆，激活系統(tǒng)中的進(jìn)程調(diào)度程序盯荤，完成一次調(diào)度，將CPU分配個(gè)新的的隊(duì)首進(jìn)程（或新到達(dá)的緊迫進(jìn)程）焕盟。由此秋秤，可保證就緒隊(duì)列中的進(jìn)程在一個(gè)確定的時(shí)間段內(nèi)都能獲得一次CPU執(zhí)行。

２.進(jìn)程切換時(shí)機(jī)

• 若一個(gè)時(shí)間片尚未用完脚翘，正在運(yùn)行的進(jìn)程便已經(jīng)完成灼卢，就立即激活調(diào)度程序，將它從就緒隊(duì)列中刪除来农，再調(diào)度就緒隊(duì)列中的隊(duì)首進(jìn)程運(yùn)行鞋真，并啟動(dòng)一個(gè)新的時(shí)間片。
• 在一個(gè)時(shí)間片用完后备图，計(jì)時(shí)器中斷處理程序被激活灿巧。如果進(jìn)程尚未運(yùn)行完畢赶袄，調(diào)度程序?qū)阉瓦M(jìn)就緒隊(duì)列的末尾揽涮。

３.時(shí)間片大小確定