資源簡介

The Best R&D Courses
處理機調(diào)度
3.1 處理機調(diào)度的層次和調(diào)度算法的目標
　　在多道程序系統(tǒng)中，調(diào)度的實質(zhì)是一種資源分配，處理機調(diào)度是對處理機資源進行分配。處理
機調(diào)度算法是指根據(jù)處理機分配策略所規(guī)定的處理機分配算法。在多道批處理系統(tǒng)中，一個作業(yè)從
提交到獲得處理機執(zhí)行，直至作業(yè)運行完畢，可能需要經(jīng)歷多級處理機調(diào)度，下面先來了解處理機
調(diào)度的層次。
The Best R&D Courses
處理機調(diào)度
3.1.1 處理機調(diào)度的層次
　　1. 高級調(diào)度(High Level Scheduling)
　　2. 低級調(diào)度(Low Level Scheduling)
　　3. 中級調(diào)度(Intermediate Scheduling)
The Best R&D Courses
高級調(diào)度 ( 按照某種規(guī)則，從后備隊列 外存 內(nèi)存 最低 無 創(chuàng)建態(tài) 就緒態(tài)
作業(yè)調(diào)度) 中選擇合適的作業(yè)將其調(diào)入 (面向作業(yè))
內(nèi)存，并為其創(chuàng)建進程
中級調(diào)度 ( 按照某種規(guī)則，從掛起隊列 外存 內(nèi)存 中等 掛起態(tài) 就緒態(tài) (
內(nèi)存調(diào)度) 中選擇合適的進程將其數(shù)據(jù) (面向進程) 阻塞掛起 阻塞態(tài))
調(diào)回內(nèi)存
低級調(diào)度 ( 按照某種規(guī)則，從就緒隊列 內(nèi) 存 CPU 最高 就緒態(tài) 運行態(tài)
進程調(diào)度) 中選擇一個進程為其分配處
理機
The Best R&D Courses
處理機調(diào)度
3.1.2 處理機調(diào)度算法的目標
　　1. 處理機調(diào)度算法的共同目標
　　(1) 資源利用率。為提高系統(tǒng)的資源利用率，應(yīng)使系統(tǒng)中的處理機和其它所有資源都盡可能地保
持忙碌狀態(tài)，其中最重要的處理機利用率可用以下方法計算：
CPU 有效工作時間
CPU 的利用率 = CPU 有效工作時間 CPU 空閑等待時間
The Best R&D Courses
處理機調(diào)度
　　(2) 公平性。公平性是指應(yīng)使諸進程都獲得合理的CPU 時間，不會發(fā)生進程饑餓現(xiàn)象。公平性
是相對的，對相同類型的進程應(yīng)獲得相同的服務(wù)；但對于不同類型的進程，由于其緊急程度或重要
性的不同，則應(yīng)提供不同的服務(wù)。
　　(3) 平衡性。由于在系統(tǒng)中可能具有多種類型的進程，有的屬于計算型作業(yè)，有的屬于I/O型。
為使系統(tǒng)中的CPU和各種外部設(shè)備都能經(jīng)常處于忙碌狀態(tài)，調(diào)度算法應(yīng)盡可能保持系統(tǒng)資源使用的
平衡性。
　　(4) 策略強制執(zhí)行。對所制訂的策略其中包括安全策略，只要需要，就必須予以準確地執(zhí)行，即
使會造成某些工作的延遲也要執(zhí)行。
The Best R&D Courses
處理機調(diào)度
　　2. 批處理系統(tǒng)的目標
　　(1) 平均周轉(zhuǎn)時間短。
　　對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為計算機系統(tǒng)的管理者，則總是希望
能使平均周轉(zhuǎn)時間最短，這不僅會有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿
意。應(yīng)使作業(yè)周轉(zhuǎn)時間和作業(yè)的平均周轉(zhuǎn)時間盡可能短。否則，會使許多用戶的等待時間過長，這
將會引起用戶特別是短作業(yè)用戶的不滿。可把平均周轉(zhuǎn)時間描述為：
1 nT [ T i]n i 1
The Best R&D Courses
處理機調(diào)度
　　為了進一步反映調(diào)度的性能，更清晰地描述各進程在其周轉(zhuǎn)時間中，等待和執(zhí)行時間的具體分
配狀況，往往使用帶權(quán)周轉(zhuǎn)時間，即作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間Ts之比，即
W = T/Ts。而平均帶權(quán)周轉(zhuǎn)時間則可表示為：
W 1
n T
i
n i 1 T s
The Best R&D Courses
處理機調(diào)度
　　(2) 系統(tǒng)吞吐量高。由于吞吐量是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因而它與批處理作業(yè)的
平均長度有關(guān)。事實上，如果單純是為了獲得高的系統(tǒng)吞吐量，就應(yīng)盡量多地選擇短作業(yè)運行。
　　(3) 處理機利用率高。對于大、中型計算機，CPU價格十分昂貴，致使處理機的利用率成為衡量
系統(tǒng)性能的十分重要的指標；而調(diào)度方式和算法又對處理機的利用率起著十分重要的作用。如果單
純是為使處理機利用率高，應(yīng)盡量多地選擇計算量大的作業(yè)運行。由上所述可以看出，這些要求之
間是存在著一定矛盾的。
The Best R&D Courses
處理機調(diào)度
　　3. 分時系統(tǒng)的目標
　　(1) 響應(yīng)時間快。
　　(2) 均衡性。
　　4. 實時系統(tǒng)的目標
　　(1) 截止時間的保證。
　　(2) 可預(yù)測性。
The Best R&D Courses
處理機調(diào)度
　　　　3.2 作業(yè)與作業(yè)調(diào)度
　　在多道批處理系統(tǒng)中，作業(yè)是用戶提交給系統(tǒng)的一項相對獨立的工作。操作員把用戶提交的作
業(yè)通過相應(yīng)的輸入設(shè)備輸入到磁盤存儲器，并保存在一個后備作業(yè)隊列中。再由作業(yè)調(diào)度程序?qū)⑵?br/>從外存調(diào)入內(nèi)存。
The Best R&D Courses
處理機調(diào)度
3.2.1 批處理系統(tǒng)中的作業(yè)
　　1. 作業(yè)和作業(yè)步
　　(1) 作業(yè)(Job)。
　　(2) 作業(yè)步(Job Step)。
The Best R&D Courses
處理機調(diào)度
　　2. 作業(yè)控制塊(Job Control Block，JCB)
　　為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中，為每個作業(yè)設(shè)置了一個作業(yè)控制塊JCB，它是作
業(yè)在系統(tǒng)中存在的標志，其中保存了系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息。通常在JCB中包
含的內(nèi)容有：作業(yè)標識、用戶名稱、用戶賬號、作業(yè)類型(CPU 繁忙型、I/O 繁忙型、批量型、終
端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、作業(yè)運行時間)、資源需求(預(yù)計運行時間、要求內(nèi)存大小等)、
資源使用情況等。
The Best R&D Courses
處理機調(diào)度
　　3. 作業(yè)運行的三個階段和三種狀態(tài)
　　作業(yè)從進入系統(tǒng)到運行結(jié)束，通常需要經(jīng)歷收容、運行和完成三個階段。相應(yīng)的作業(yè)也就有
“后備狀態(tài)”、“運行狀態(tài)”和“完成狀態(tài)”。
　　(1) 收容階段。
　　(2) 運行階段?！　?br/>　　(3) 完成階段。
The Best R&D Courses
處理機調(diào)度
3.2.2 作業(yè)調(diào)度的主要任務(wù)
　　作業(yè)調(diào)度的主要任務(wù)是，根據(jù)JCB中的信息，檢查系統(tǒng)中的資源能否滿足作業(yè)對資源的需求，
以及按照一定的調(diào)度算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配
必要的資源。然后再將新創(chuàng)建的進程排在就緒隊列上等待調(diào)度。因此，也把作業(yè)調(diào)度稱為接納調(diào)度
(Admission Scheduling)。在每次執(zhí)行作業(yè)調(diào)度時，都需做出以下兩個決定。
　　1. 接納多少個作業(yè)
　　2. 接納哪些作業(yè)
The Best R&D Courses
處理機調(diào)度
3.2.3 先來先服務(wù)(FCFS)和短作業(yè)優(yōu)先(SJF)調(diào)度算法
　　1. 先來先服務(wù)(first-come first-served，F(xiàn)CFS)調(diào)度算法
　　FCFS是最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進程調(diào)度。當在作業(yè)調(diào)度中采
用該算法時，系統(tǒng)將按照作業(yè)到達的先后次序來進行調(diào)度，或者說它是優(yōu)先考慮在系統(tǒng)中等待時間
最長的作業(yè)，而不管該作業(yè)所需執(zhí)行時間的長短，從后備作業(yè)隊列中選擇幾個最先進入該隊列的作
業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源和創(chuàng)建進程。然后把它放入就緒隊列。
The Best R&D Courses
處理機調(diào)度
　　2. 短作業(yè)優(yōu)先(short job first，SJF)的調(diào)度算法
　　由于在實際情況中，短作業(yè)(進程)占有很大比例，為了能使它們能比長作業(yè)優(yōu)先執(zhí)行，而產(chǎn)生了
短作業(yè)優(yōu)先調(diào)度算法。
　　1) 短作業(yè)優(yōu)先算法
　　SJF算法是以作業(yè)的長短來計算優(yōu)先級，作業(yè)越短，其優(yōu)先級越高。作業(yè)的長短是以作業(yè)所要求
的運行時間來衡量的。SJF算法可以分別用于作業(yè)調(diào)度和進程調(diào)度。在把短作業(yè)優(yōu)先調(diào)度算法用于作
業(yè)調(diào)度時，它將從外存的作業(yè)后備隊列中選擇若干個估計運行時間最短的作業(yè)，優(yōu)先將它們調(diào)入內(nèi)
存運行。
The Best R&D Courses
處理機調(diào)度
　　2) 短作業(yè)優(yōu)先算法的缺點
　　SJF調(diào)度算法較之FCFS算法有了明顯的改進，但仍然存在不容忽視的缺點：
　　(1) 必須預(yù)知作業(yè)的運行時間。在采用這種算法時，要先知道每個作業(yè)的運行時間。即使是程序
員也很難準確估計作業(yè)的運行時間，如果估計過低，系統(tǒng)就可能按估計的時間終止作業(yè)的運行，但
此時作業(yè)并未完成，故一般都會偏長估計。
　　(2) 對長作業(yè)非常不利，長作業(yè)的周轉(zhuǎn)時間會明顯地增長。更嚴重的是，該算法完全忽視作業(yè)的
等待時間，可能使作業(yè)等待時間過長，出現(xiàn)饑餓現(xiàn)象。
The Best R&D Courses
處理機調(diào)度
　　(3) 在采用FCFS算法時，人—機無法實現(xiàn)交互。
　　(4) 該調(diào)度算法完全未考慮作業(yè)的緊迫程度，故不能保證緊迫性作業(yè)能得到及時處理。
The Best R&D Courses
處理機調(diào)度
3.2.4 優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法
　　1. 優(yōu)先級調(diào)度算法(priority-scheduling algorithm，PSA)
　　我們可以這樣來看作業(yè)的優(yōu)先級，對于先來先服務(wù)調(diào)度算法，作業(yè)的等待時間就是作業(yè)的優(yōu)先
級，等待時間越長，其優(yōu)先級越高。對于短作業(yè)優(yōu)先調(diào)度算法，作業(yè)的長短就是作業(yè)的優(yōu)先級，作
業(yè)所需運行的時間越短，其優(yōu)先級越高。但上述兩種優(yōu)先級都不能反映作業(yè)的緊迫程度。
The Best R&D Courses
處理機調(diào)度
　　2. 高響應(yīng)比優(yōu)先調(diào)度算法(Highest Response Ratio Next，HRRN)
　　在批處理系統(tǒng)中，F(xiàn)CFS算法所考慮的只是作業(yè)的等待時間，而忽視了作業(yè)的運行時間。而SJF
算法正好與之相反，只考慮作業(yè)的運行時間，而忽視了作業(yè)的等待時間。高響應(yīng)比優(yōu)先調(diào)度算法則
是既考慮了作業(yè)的等待時間，又考慮作業(yè)運行時間的調(diào)度算法，因此既照顧了短作業(yè)，又不致使長
作業(yè)的等待時間過長，從而改善了處理機調(diào)度的性能。
The Best R&D Courses
處理機調(diào)度
　　高響應(yīng)比優(yōu)先算法是如何實現(xiàn)的呢 如果我們能為每個作業(yè)引入一個動態(tài)優(yōu)先級，即優(yōu)先級是
可以改變的，令它隨等待時間延長而增加，這將使長作業(yè)的優(yōu)先級在等待期間不斷地增加，等到足
夠的時間后，必然有機會獲得處理機。該優(yōu)先級的變化規(guī)律可描述為：
等待時間 要求服務(wù)時間
優(yōu)先權(quán)
要求服務(wù)時間
The Best R&D Courses
處理機調(diào)度
　　由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先級又相當于響應(yīng)比RP。
據(jù)此，優(yōu)先又可表示為：
R 等待時間 要求服務(wù)時間 響應(yīng)時間P 要求服務(wù)時間 要求服務(wù)時間
The Best R&D Courses
進程調(diào)度
　　　　　3.3 進 程 調(diào) 度
　　進程調(diào)度是OS中必不可少的一種調(diào)度。因此在三種類型的OS中，都無一例外地配置了進程調(diào)度。
此外它也是對系統(tǒng)性能影響最大的一種處理機調(diào)度，相應(yīng)的，有關(guān)進程調(diào)度的算法也較多。
The Best R&D Courses
進程調(diào)度
3.3.1 進程調(diào)度的任務(wù)、機制和方式
　　1. 進程調(diào)度的任務(wù)
　　進程調(diào)度的任務(wù)主要有三：
　　(1) 保存處理機的現(xiàn)場信息。
　　(2) 按某種算法選取進程。
　　(3) 把處理器分配給進程。
The Best R&D Courses
進程調(diào)度
　　2. 進程調(diào)度機制
　　為了實現(xiàn)進程調(diào)度，在進程調(diào)度機制中，應(yīng)具有如下三個基本部分，如圖3-1所示。
　　(1) 排隊器。
　　(2) 分派器。
　　(3) 上下文切換器。
The Best R&D Courses
進程調(diào)度
圖3-1 進程調(diào)度機制
The Best R&D Courses
進程調(diào)度
　　3. 進程調(diào)度方式
　　1) 非搶占方式(Nonpreemptive Mode)
　　在采用這種調(diào)度方式時，一旦把處理機分配給某進程后，就一直讓它運行下去，決不會因為時
鐘中斷或任何其它原因去搶占當前正在運行進程的處理機，直至該進程完成，或發(fā)生某事件而被阻
塞時，才把處理機分配給其它進程。
The Best R&D Courses
進程調(diào)度
　　2) 搶占方式(Preemptive Mode)
　　這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則，去暫停某個正在執(zhí)行的進程，將已分配給該進程的
處理機重新分配給另一進程。在現(xiàn)代OS中廣泛采用搶占方式，這是因為：對于批處理機系統(tǒng)，可以
防止一個長進程長時間地占用處理機，以確保處理機能為所有進程提供更為公平的服務(wù)。在分時系
統(tǒng)中，只有采用搶占方式才有可能實現(xiàn)人—機交互。在實時系統(tǒng)中，搶占方式能滿足實時任務(wù)的需
求。但搶占方式比較復(fù)雜，所需付出的系統(tǒng)開銷也較大。
The Best R&D Courses
進程調(diào)度
3.3.2 輪轉(zhuǎn)調(diào)度算法
　　1. 輪轉(zhuǎn)法的基本原理
　　在輪轉(zhuǎn)(RR)法中，系統(tǒng)將所有的就緒進程按FCFS策略排成一個就緒隊列。系統(tǒng)可設(shè)置每隔一定
時間(如30 ms)便產(chǎn)生一次中斷，去激活進程調(diào)度程序進行調(diào)度，把CPU分配給隊首進程，并令其執(zhí)
行一個時間片。當它運行完畢后，又把處理機分配給就緒隊列中新的隊首進程，也讓它執(zhí)行一個時
間片。這樣，就可以保證就緒隊列中的所有進程在確定的時間段內(nèi)，都能獲得一個時間片的處理機
時間。
The Best R&D Courses
進程調(diào)度
　　2. 進程切換時機
　　在RR調(diào)度算法中，應(yīng)在何時進行進程的切換，可分為兩種情況：① 若一個時間片尚未用完，
正在運行的進程便已經(jīng)完成，就立即激活調(diào)度程序，將它從就緒隊列中刪除，再調(diào)度就緒隊列中隊
首的進程運行，并啟動一個新的時間片。② 在一個時間片用完時，計時器中斷處理程序被激活。如
果進程尚未運行完畢，調(diào)度程序?qū)阉屯途w隊列的末尾。
The Best R&D Courses
進程調(diào)度
　　3. 時間片大小的確定
　　在輪轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很大的
影響。
　　圖3-2示出了時間片大小對響應(yīng)時間的影響，其中圖(a)是時間片略大于典型交互的時間，而圖(b)
是時間片小于典型交互的時間。圖3-3示出了時間片分別為q = 1和q = 4時對平均周轉(zhuǎn)時間的影響。
The Best R&D Courses
進程調(diào)度
圖3-2 時間片大小對響應(yīng)時間的影響
The Best R&D Courses
進程調(diào)度
作業(yè) 進程名 A B C D E 平均
情況 到達時間 0 1 2 3 4
時 間 片 服務(wù)時間 4 3 4 2 4
完成時間 15 12 16 9 17
RR
周轉(zhuǎn)時間 15 11 14 6 13 11.8
q=1
帶權(quán)周轉(zhuǎn)時間 3.75 3.67 3.5 3 3.33 3.46
完成時間 4 7 11 13 17
RR
周轉(zhuǎn)時間 4 6 9 10 13 8.4
q=4
帶權(quán)周轉(zhuǎn)時間 1 2 2.25 5 3.33 2.5
圖3-3 q = 1和q = 4時進程的周轉(zhuǎn)時間
The Best R&D Courses
進程調(diào)度
3.3.3 優(yōu)先級調(diào)度算法
　　1. 優(yōu)先級調(diào)度算法的類型
　　優(yōu)先級進程調(diào)度算法，是把處理機分配給就緒隊列中優(yōu)先級最高的進程。這時，又可進一步把
該算法分成如下兩種。
　　(1) 非搶占式優(yōu)先級調(diào)度算法。
　　(2) 搶占式優(yōu)先級調(diào)度算法。
The Best R&D Courses
進程調(diào)度
　　2. 優(yōu)先級的類型
　　1) 靜態(tài)優(yōu)先級
　　靜態(tài)優(yōu)先級是在創(chuàng)建進程時確定的，在進程的整個運行期間保持不變。優(yōu)先級是利用某一范圍
內(nèi)的一個整數(shù)來表示的，例如0～255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。確定進程優(yōu)先級大小
的依據(jù)有如下三個：
　　(1) 進程類型。
　　(2) 進程對資源的需求。
　　(3) 用戶要求。
The Best R&D Courses
進程調(diào)度
　　2) 動態(tài)優(yōu)先級
　　動態(tài)優(yōu)先級是指在創(chuàng)建進程之初，先賦予其一個優(yōu)先級，然后其值隨進程的推進或等待時間的
增加而改變，以便獲得更好的調(diào)度性能。
The Best R&D Courses
進程調(diào)度
3.3.4 多隊列調(diào)度算法
　　如前所述的各種調(diào)度算法，尤其在應(yīng)用于進程調(diào)度時，由于系統(tǒng)中僅設(shè)置一個進程的就緒隊列，
即低級調(diào)度算法是固定的、單一的，無法滿足系統(tǒng)中不同用戶對進程調(diào)度策略的不同要求，在多處
理機系統(tǒng)中，這種單一調(diào)度策略實現(xiàn)機制的缺點更顯突出，由此，多級隊列調(diào)度算法能夠在一定程
度上彌補這一缺點。
The Best R&D Courses
進程調(diào)度
3.3.5 多級反饋隊列(multileved feedback queue)調(diào)度算法
　　1. 調(diào)度機制
　　多級反饋隊列調(diào)度算法的調(diào)度機制可描述如下：
　　(1) 設(shè)置多個就緒隊列。
　　圖3-4是多級反饋隊列算法的示意圖。
The Best R&D Courses
進程調(diào)度
圖3-4 多級反饋隊列調(diào)度算法
The Best R&D Courses
進程調(diào)度
　　(2) 每個隊列都采用FCFS算法。當新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS
原則等待調(diào)度。當輪到該進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可撤離系統(tǒng)。否則，即它在一
個時間片結(jié)束時尚未完成，調(diào)度程序?qū)⑵滢D(zhuǎn)入第二隊列的末尾等待調(diào)度；如果它在第二隊列中運行
一個時間片后仍未完成，再依次將它放入第三隊列，……，依此類推。當進程最后被降到第n隊列后，
在第n隊列中便采取按RR方式運行。
The Best R&D Courses
進程調(diào)度
　　(3) 按隊列優(yōu)先級調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級隊列中的諸進程運行，僅當?shù)谝魂犃锌臻e
時才調(diào)度第二隊列中的進程運行；換言之，僅當?shù)?～(i-1)所有隊列均空時，才會調(diào)度第i隊列中的進
程運行。如果處理機正在第i隊列中為某進程服務(wù)時又有新進程進入任一優(yōu)先級較高的隊列，此時須
立即把正在運行的進程放回到第i隊列的末尾，而把處理機分配給新到的高優(yōu)先級進程。
The Best R&D Courses
進程調(diào)度
　　2. 調(diào)度算法的性能
　　在多級反饋隊列調(diào)度算法中，如果規(guī)定第一個隊列的時間片略大于多數(shù)人機交互所需之處理時
間時，便能較好地滿足各種類型用戶的需要。
　　(1) 終端型用戶。
　　(2) 短批處理作業(yè)用戶。
　　(3) 長批處理作業(yè)用戶。
The Best R&D Courses
進程調(diào)度
3.3.6 基于公平原則的調(diào)度算法
　　1. 保證調(diào)度算法
　　保證調(diào)度算法是另外一種類型的調(diào)度算法，它向用戶所做出的保證并不是優(yōu)先運行，而是明確
的性能保證，該算法可以做到調(diào)度的公平性。一種比較容易實現(xiàn)的性能保證是處理機分配的公平性。
如果在系統(tǒng)中有n個相同類型的進程同時運行，為公平起見，須保證每個進程都獲得相同的處理機時
間1/n。
The Best R&D Courses
進程調(diào)度
　　在實施公平調(diào)度算法時系統(tǒng)中必須具有這樣一些功能：
　　(1) 跟蹤計算每個進程自創(chuàng)建以來已經(jīng)執(zhí)行的處理時間。
　　(2) 計算每個進程應(yīng)獲得的處理機時間，即自創(chuàng)建以來的時間除以n。
　　(3) 計算進程獲得處理機時間的比率，即進程實際執(zhí)行的處理時間和應(yīng)獲得的處理機時間之比。
　　(4) 比較各進程獲得處理機時間的比率。如進程A的比率最低，為0.5，而進程B的比率為0.8，
進程C的比率為1.2等。
　　(5) 調(diào)度程序應(yīng)選擇比率最小的進程將處理機分配給它，并讓該進程一直運行，直到超過最接近
它的進程比率為止。
The Best R&D Courses
進程調(diào)度
　　2. 公平分享調(diào)度算法
　　分配給每個進程相同的處理機時間，顯然，這對諸進程而言，是體現(xiàn)了一定程度的公平，但如
果各個用戶所擁有的進程數(shù)不同，就會發(fā)生對用戶的不公平問題。
The Best R&D Courses
實時調(diào)度
　　　　　　3.4 實 時 調(diào) 度
　　在實時系統(tǒng)中，可能存在著兩類不同性質(zhì)的實時任務(wù)，即HRT任務(wù)和SRT任務(wù)，它們都聯(lián)系著
一個截止時間。為保證系統(tǒng)能正常工作，實時調(diào)度必須能滿足實時任務(wù)對截止時間的要求。為此，
實現(xiàn)實時調(diào)度應(yīng)具備一定的條件。
The Best R&D Courses
實時調(diào)度
3.4.1 實現(xiàn)實時調(diào)度的基本條件
　　1. 提供必要的信息
　　為了實現(xiàn)實時調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的信息：
　　(1) 就緒時間，是指某任務(wù)成為就緒狀態(tài)的起始時間，在周期任務(wù)的情況下，它是事先預(yù)知的一
串時間序列。
　　(2) 開始截止時間和完成截止時間，對于典型的實時應(yīng)用，只須知道開始截止時間，或者完成截
止時間。
The Best R&D Courses
實時調(diào)度
　　(3) 處理時間，一個任務(wù)從開始執(zhí)行，直至完成時所需的時間。
　　(4) 資源要求，任務(wù)執(zhí)行時所需的一組資源。
　　(5) 優(yōu)先級，如果某任務(wù)的開始截止時間錯過，勢必引起故障，則應(yīng)為該任務(wù)賦予“絕對”優(yōu)先
級；如果其開始截止時間的錯過，對任務(wù)的繼續(xù)運行無重大影響，則可為其賦予“相對”優(yōu)先級，
供調(diào)度程序參考。
The Best R&D Courses
實時調(diào)度
　　2. 系統(tǒng)處理能力強
　　在實時系統(tǒng)中，若處理機的處理能力不夠強，則有可能因處理機忙不過，而致使某些實時任務(wù)
不能得到及時處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實時任務(wù)HRT，它
們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件系統(tǒng)
才是可調(diào)度的：
m
C i 1
i 1 P i
The Best R&D Courses
實時調(diào)度
　　提高系統(tǒng)處理能力的途徑有二：一是采用單處理機系統(tǒng)，但須增強其處理能力，以顯著地減少
對每一個任務(wù)的處理時間；二是采用多處理機系統(tǒng)。假定系統(tǒng)中的處理機數(shù)為N，則應(yīng)將上述的限制
條件改為：
m
C i N
i 1 Pi
The Best R&D Courses
實時調(diào)度
　　3. 采用搶占式調(diào)度機制
　　在含有HRT任務(wù)的實時系統(tǒng)中，廣泛采用搶占機制。這樣便可滿足HRT任務(wù)對截止時間的要求。
但這種調(diào)度機制比較復(fù)雜。
The Best R&D Courses
實時調(diào)度
3.4.2 實時調(diào)度算法的分類
　　可以按不同方式對實時調(diào)度算法加以分類：① 根據(jù)實時任務(wù)性質(zhì)，可將實時調(diào)度的算法分為硬
實時調(diào)度算法和軟實時調(diào)度算法；② 按調(diào)度方式，則可分為非搶占調(diào)度算法和搶占調(diào)度算法。
　　1. 非搶占式調(diào)度算法
　　(1) 非搶占式輪轉(zhuǎn)調(diào)度算法。
　　(2) 非搶占式優(yōu)先調(diào)度算法。
The Best R&D Courses
實時調(diào)度
　　2. 搶占式調(diào)度算法
　　可根據(jù)搶占發(fā)生時間的不同而進一步分成以下兩種調(diào)度算法：
　　(1) 基于時鐘中斷的搶占式優(yōu)先級調(diào)度算法。
　　(2) 立即搶占(Immediate Preemption)的優(yōu)先級調(diào)度算法?！　?br/>　　圖3-5中的(a)、(b)、(c)、(d)分別示出了四種情況的調(diào)度時間。
The Best R&D Courses
實時調(diào)度
圖3-5 實時進程調(diào)度
The Best R&D Courses
死鎖
3.5.2 計算機系統(tǒng)中的死鎖
　　1. 競爭不可搶占性資源引起死鎖
　　通常系統(tǒng)中所擁有的不可搶占性資源其數(shù)量不足以滿足多個進程運行的需要，使得進程在運行
過程中，會因爭奪資源而陷入僵局。
The Best R&D Courses
死鎖
　　我們可將上面的問題利用資源分配圖進行描述，用方塊代表可重用的資源(文件)，用圓圈代表進
程，見圖3-12所示。
The Best R&D Courses
死鎖
圖3-12　共享文件時的死鎖情況
The Best R&D Courses
死鎖
　　2. 競爭可消耗資源引起死鎖
　　現(xiàn)在進一步介紹競爭可消耗資源所引起的死鎖。圖3-13示出了在三個進程之間，在利用消息通
信機制進行通信時所形成的死鎖情況。
The Best R&D Courses
死鎖
圖3-13 進程之間通信時的死鎖
The Best R&D Courses
死鎖
3.5.3 死鎖的定義、必要條件和處理方法
　　1. 死鎖的定義
　　在一組進程發(fā)生死鎖的情況下，這組死鎖進程中的每一個進程，都在等待另一個死鎖進程所占
有的資源。
The Best R&D Courses
死鎖
　　2. 產(chǎn)生死鎖的必要條件
　　雖然進程在運行過程中可能會發(fā)生死鎖，但產(chǎn)生進程死鎖是必須具備一定條件的。綜上所述不
難看出，產(chǎn)生死鎖必須同時具備下面四個必要條件，只要其中任一個條件不成立，死鎖就不會發(fā)生：
　　(1) 互斥條件。
　　(2) 請求和保持條件。
　　(3) 不可搶占條件。
　　(4) 循環(huán)等待條件。
The Best R&D Courses
死鎖
　　3. 處理死鎖的方法
　　目前處理死鎖的方法可歸結(jié)為四種：
　　(1) 預(yù)防死鎖。
　　(2) 避免死鎖。
　　(3) 檢測死鎖。
　　(4) 解除死鎖。
The Best R&D Courses
死鎖
　　　　3.6 預(yù) 防 死 鎖
　　預(yù)防死鎖的方法是通過破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個，以避免發(fā)生死鎖。由于
互斥條件是非共享設(shè)備所必須的，不僅不能改變，還應(yīng)加以保證，因此主要是破壞產(chǎn)生死鎖的后三
個條件。
The Best R&D Courses
死鎖
3.6.1 破壞“請求和保持”條件
　　為了能破壞“請求和保持”條件，系統(tǒng)必須保證做到：當一個進程在請求資源時，它不能持有
不可搶占資源。該保證可通過如下兩個不同的協(xié)議實現(xiàn)：
　　1. 第一種協(xié)議
　　該協(xié)議規(guī)定，所有進程在開始運行之前，必須一次性地申請其在整個運行過程中所需的全部資
源。
The Best R&D Courses
死鎖
　　2. 第二種協(xié)議
　　該協(xié)議是對第一種協(xié)議的改進，它允許一個進程只獲得運行初期所需的資源后，便開始運行。
The Best R&D Courses
死鎖
3.6.2 破壞“不可搶占”條件
　　為了能破壞“不可搶占”條件，協(xié)議中規(guī)定，當一個已經(jīng)保持了某些不可被搶占資源的進程，
提出新的資源請求而不能得到滿足時，它必須釋放已經(jīng)保持的所有資源，待以后需要時再重新申請。
這意味著進程已占有的資源會被暫時地釋放，或者說是被搶占了，從而破壞了“不可搶占”條件。
The Best R&D Courses
死鎖
3.6.3 破壞“循環(huán)等待”條件
　　一個能保證“循環(huán)等待”條件不成立的方法是，對系統(tǒng)所有資源類型進行線性排序，并賦予不
同的序號。
The Best R&D Courses
死鎖
　　　　3.7 避 免 死 鎖
　　避免死鎖同樣是屬于事先預(yù)防的策略，但并不是事先采取某種限制措施，破壞產(chǎn)生死鎖的必要
條件，而是在資源動態(tài)分配過程中，防止系統(tǒng)進入不安全狀態(tài)，以避免發(fā)生死鎖。這種方法所施加
的限制條件較弱，可能獲得較好的系統(tǒng)性能，目前常用此方法來避免發(fā)生死鎖。
The Best R&D Courses
死鎖
3.7.1　系統(tǒng)安全狀態(tài)
　　在死鎖避免方法中，把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)。當系統(tǒng)處于安全狀態(tài)時，可避
免發(fā)生死鎖。反之，當系統(tǒng)處于不安全狀態(tài)時，則可能進入到死鎖狀態(tài)。
　　1. 安全狀態(tài)
　　在該方法中，允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應(yīng)先計算此次資源分配
的安全性。
The Best R&D Courses
死鎖
　　2. 安全狀態(tài)之例
　　假定系統(tǒng)中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3
分別要求4臺和9臺。假設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺
空閑未分配，如下表所示：
進 程 最 大 需 求 已 分 配 可 用
P1 10 5 3
P2 4 2
P3 9 2
The Best R&D Courses
死鎖
　　3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換
　　如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。
The Best R&D Courses
死鎖
3.7.2 利用銀行家算法避免死鎖
　　最有代表性的避免死鎖的算法是Dijkstra的銀行家算法。起這樣的名字是由于該算法原本是為銀
行系統(tǒng)設(shè)計的，以確保銀行在發(fā)放現(xiàn)金貸款時，不會發(fā)生不能滿足所有客戶需要的情況。在OS中也
可用它來實現(xiàn)避免死鎖。
The Best R&D Courses
死鎖
　　1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)
　　為了實現(xiàn)銀行家算法，在系統(tǒng)中必須設(shè)置這樣四個數(shù)據(jù)結(jié)構(gòu)，分別用來描述系統(tǒng)中可利用的資
源、所有進程對資源的最大需求、系統(tǒng)中的資源分配，以及所有進程還需要多少資源的情況。
　　(1) 可利用資源向量Available。
　　(2) 最大需求矩陣Max。
　　(3) 分配矩陣Allocation。
　　(4) 需求矩陣Need。
The Best R&D Courses
死鎖
　　2. 銀行家算法
　　設(shè)Requesti是進程Pi的請求向量，如果Request i[j]=K，表示進程Pi需要K個Rj類型的資源。當
Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：
　　(1) 如果Request i[j]≤Need[i, j]，便轉(zhuǎn)向步驟(2)； 否則認為出錯，因為它所需要的資源數(shù)已
超過它所宣布的最大值。
　　(2) 如果Request i[j]≤Available[j]，便轉(zhuǎn)向步驟(3)； 否則，表示尚無足夠資源，Pi須等待。
The Best R&D Courses
死鎖
　　(3) 系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：
　Available[j] = Available[j] - Request i[j];
　 　Allocation[i, j] = Allocation[i, j] + Request i[j];
　　Need[i, j] = Need[i, j] - Request i[j];
　　(4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源
分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程
Pi等待。
The Best R&D Courses
死鎖
　　3. 安全性算法
　　系統(tǒng)所執(zhí)行的安全性算法可描述如下：
　　(1) 設(shè)置兩個向量：① 工作向量Work，它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，
它含有m個元素，在執(zhí)行安全算法開始時，Work := Available；② Finish：它表示系統(tǒng)是否有足夠
的資源分配給進程，使之運行完成。開始時先做Finish[i] := false；當有足夠資源分配給進程時，
再令Finish[i] := true。
The Best R&D Courses
死鎖
　　(2) 從進程集合中找到一個能滿足下述條件的進程：
　?、?Finish[i]=false;
　　② Need[i, j]≤Work[j];
　　若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。
　　(3) 當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：
　　　　Work[j] = Work[j]+Allocation[i, j];
　　　　Finish[i] =true;
　　　　go to step 2;
　　(4) 如果所有進程的Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全
狀態(tài)。
The Best R&D Courses
死鎖
　　4. 銀行家算法之例
　　假定系統(tǒng)中有五個進程{P0, P1, P2, P3, P4}和三類資源{A, B, C}，各種資源的數(shù)量分別為10、
5、7，在T0時刻的資源分配情況如圖3-15所示。
The Best R&D Courses
死鎖
資源 Max Allocation Need Available
情況
A B C A B C A B C A B C
進 程
P0 7 5 3 0 1 0 7 4 3 3 3 2
(2 3 0)
P1 3 2 2 2 0 0 1 2 2
(3 0 2) (0 2 0)
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
圖3-15 T0時刻的資源分配表
The Best R&D Courses
死鎖
　　(1) T0時刻的安全性：利用安全性算法對T0時刻的資源分配情況進行分析(如圖3-16所示)可知，
在T0時刻存在著一個安全序列{P1, P3, P4, P2, P0}，故系統(tǒng)是安全的。
The Best R&D Courses
死鎖
資源 Max Need Allocation Work+Allocation
情況 Finish
進 程 A B C A B C A B C A B C
P1 3 3 2 1 2 2 2 0 0 5 3 2 true
P3 5 3 2 0 1 1 2 1 1 7 4 3 true
P4 7 4 3 4 3 1 0 0 2 7 4 5 true
P2 7 4 5 6 0 0 3 0 2 10 4 7 true
P0 10 4 7 7 4 3 0 1 0 10 5 7 true
圖3-16 T0時刻的安全序列
The Best R&D Courses
死鎖
　　(2) P1請求資源：P1發(fā)出請求向量Request1(1, 0, 2)，系統(tǒng)按銀行家算法進行檢查：
　?、?Request1(1, 0, 2)≤Need1(1, 2, 2)；
　　② Request1(1, 0, 2)≤Available1(3, 3, 2)；
　?、?系統(tǒng)先假定可為P1分配資源，并修改Available，Allocation1和Need1向量，由此形成的資
源變化情況如圖3-15中的圓括號所示；
　　④ 再利用安全性算法檢查此時系統(tǒng)是否安全，如圖3-17所示。
The Best R&D Courses
死鎖
資源 Work Need Allocation Work+Allocation
情況 Finish
進 程 A B C A B C A B C A B C
P1 2 3 0 0 2 0 3 0 2 5 3 2 true
P3 5 3 2 0 1 1 2 1 1 7 4 3 true
P4 7 4 3 4 3 1 0 0 2 7 4 5 true
P0 7 4 5 7 4 3 0 1 0 7 5 5 true
P2 7 5 5 6 0 0 3 0 2 10 5 7 true
圖3-17 P1申請資源時的安全性檢查
The Best R&D Courses
死鎖
　　(3) P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查：
　?、?Request4(3，3，0)≤Need4(4，3，1)；
　?、?Request4(3，3，0)＞Available(2，3，0)，讓P4等待。
　　(4) P0請求資源：P0發(fā)出請求向量Request0(0，2，0)，系統(tǒng)按銀行家算法進行檢查：
　?、?Request0(0，2，0)≤Need0(7，4，3)；
　　② Request0(0，2，0)≤Available(2，3，0)；
　　③ 系統(tǒng)暫時先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖3-18所示。
The Best R&D Courses
死鎖
資源 Allocation Need Available
情況
進 程 A B C A B C A B C
P0 0 3 0 7 2 3 2 1 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
圖3-18 為P0分配資源后的有關(guān)資源數(shù)據(jù)
The Best R&D Courses
死鎖
　　(5) 進行安全性檢查：可用資源Available(2，1，0)已不能滿足任何進程的需要，故系統(tǒng)進入不
安全狀態(tài)，此時系統(tǒng)不分配資源。
The Best R&D Courses
死鎖
　　 3.8 死鎖的檢測與解除
　　如果在系統(tǒng)中，既不采取死鎖預(yù)防措施，也未配有死鎖避免算法，系統(tǒng)很可能會發(fā)生死鎖。在
這種情況下，系統(tǒng)應(yīng)當提供兩個算法：
　?、?死鎖檢測算法。該方法用于檢測系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖。
　?、?死鎖解除算法。當認定系統(tǒng)中已發(fā)生了死鎖，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來。
The Best R&D Courses
死鎖
3.8.1 死鎖的檢測
　　為了能對系統(tǒng)中是否已發(fā)生了死鎖進行檢測，在系統(tǒng)中必須：① 保存有關(guān)資源的請求和分配信
息；② 提供一種算法，它利用這些信息來檢測系統(tǒng)是否已進入死鎖狀態(tài)。
　　1. 資源分配圖(Resource Allocation Graph)
　　系統(tǒng)死鎖，可利用資源分配圖來描述。
The Best R&D Courses
死鎖
　　2．死鎖定理
　　我們可以利用把資源分配圖加以簡化的方法(圖3-19)，來檢測當系統(tǒng)處于S狀態(tài)時，是否為死鎖
狀態(tài)。簡化方法如下：
　　(1) 在資源分配圖中，找出一個既不阻塞又非獨立的進程結(jié)點Pi。在順利的情況下，Pi可獲得所
需資源而繼續(xù)運行，直至運行完畢，再釋放其所占有的全部資源，這相當于消去Pi的請求邊和分配邊，
使之成為孤立的結(jié)點。在圖3-20(a)中，將P1的兩個分配邊和一個請求邊消去，便形成圖(b)所示的情
況。
The Best R&D Courses
死鎖
圖3-20 資源分配圖的簡化
The Best R&D Courses
死鎖
　　(2) P1釋放資源后，便可使P2獲得資源而繼續(xù)運行，直至P2完成后又釋放出它所占有的全部資
源，形成圖(c)所示的情況，即將P2的兩條請求邊和一條分配邊消去。
　　(3) 在進行一系列的簡化后，若能消去圖中所有的邊，使所有的進程結(jié)點都成為孤立結(jié)點，則稱
該圖是可完全簡化的；若不能通過任何過程使該圖完全簡化，則稱該圖是不可完全簡化的。
The Best R&D Courses
死鎖
3.8.2 死鎖的解除
　　1. 終止進程的方法
　　1) 終止所有死鎖進程
　　這是一種最簡單的方法，即是終止所有的死鎖進程，死鎖自然也就解除了，但所付出的代價可
能會很大。因為其中有些進程可能已經(jīng)運行了很長時間，已接近結(jié)束，一旦被終止真可謂“功虧一
簣”，以后還得從頭再來。還可能會有其它方面的代價，在此不再一一列舉。
The Best R&D Courses
死鎖
　　2) 逐個終止進程
　　稍微溫和的方法是，按照某種順序，逐個地終止進程，直至有足夠的資源，以打破循環(huán)等待，
把系統(tǒng)從死鎖狀態(tài)解脫出來為止。但該方法所付出的代價也可能很大。因為每終止一個進程，都需
要用死鎖檢測算法確定系統(tǒng)死鎖是否已經(jīng)被解除，若未解除還需再終止另一個進程。另外，在采取
逐個終止進程策略時，還涉及到應(yīng)采用什么策略選擇一個要終止的進程。選擇策略最主要的依據(jù)是，
為死鎖解除所付出的“代價最小”。但怎么樣才算是“代價最小”，很難有一個精確的度量。
The Best R&D Courses

展開更多......

收起↑