3.1處理機(jī)調(diào)度相關(guān)基本概念

1乙嘀、處理機(jī)調(diào)度：多道程序環(huán)境下栽烂，動(dòng)態(tài)的把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程使之執(zhí)行咐刨。

2雕拼、三級(jí)調(diào)度：

?高級(jí)調(diào)度（High Scheduling）

?中級(jí)調(diào)度（Intermediate-Level Scheduling）

?低級(jí)調(diào)度（Low Level Scheduling）

3伪阶、高級(jí)調(diào)度

1）決定外存后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存;

2）為它們創(chuàng)建進(jìn)程煞檩、分配必要的資源;

3）將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行栅贴。

4）系統(tǒng)運(yùn)行并不一定存在高級(jí)調(diào)度

4斟湃、低級(jí)調(diào)度

1）是最基本的一種調(diào)度，在三種基本OS中都有檐薯。

2）進(jìn)程調(diào)度方式（重點(diǎn)）

（1）非搶占方式（Non-preemptive?Mode）

? 一旦處理機(jī)分配給某進(jìn)程凝赛，該進(jìn)程一直執(zhí)行。決不允許其他進(jìn)程搶占已分配運(yùn)行進(jìn)程的處理機(jī)坛缕。

（2）搶占方式（PreemptiveMode）

? 允許調(diào)度程序根據(jù)某種原則墓猎，暫停某個(gè)正在執(zhí)行的進(jìn)程，將處理機(jī)重新分配給另一進(jìn)程赚楚。

進(jìn)程調(diào)度方式比較

5毙沾、中級(jí)調(diào)度

1）引入目的：提高內(nèi)存利用率和系統(tǒng)吞吐量。根據(jù)條件將一些進(jìn)程調(diào)出或再調(diào)入內(nèi)存宠页。

2）三種調(diào)度的頻率和復(fù)雜度

進(jìn)程調(diào)度：運(yùn)行頻率最高左胞，算法不能太復(fù)雜，以免占用太多的CPU時(shí)間举户。分時(shí)系統(tǒng)通常10~100ms便進(jìn)行一次烤宙。

作業(yè)調(diào)度：一個(gè)作業(yè)運(yùn)行完畢退出系統(tǒng)時(shí)即觸發(fā)重新調(diào)度一個(gè)新作業(yè)入內(nèi)存，周期較長(zhǎng)俭嘁，大約幾分鐘一次躺枕。因而也允許作業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。

中級(jí)調(diào)度：運(yùn)行頻率基本上介于上述兩種調(diào)度之間。

6屯远、調(diào)度隊(duì)列模型

①僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

②具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型

③同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型

7蔓姚、選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則

1)面向用戶的準(zhǔn)則

（1）周轉(zhuǎn)時(shí)間短：

?總的等待時(shí)間Tw = 在后備隊(duì)列中等待 + 就緒隊(duì)列上等待+阻塞隊(duì)列中等待（等待I/O操作用時(shí)）

?周轉(zhuǎn)時(shí)間T=Ts+Tw

?帶權(quán)周轉(zhuǎn)時(shí)間W= T/Ts

?平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間（n個(gè)作業(yè)求平均）

（2）響應(yīng)時(shí)間快

（3）均衡性

（4）截止時(shí)間的保證

（5）優(yōu)先權(quán)準(zhǔn)則

2)面向系統(tǒng)的準(zhǔn)則

系統(tǒng)吞吐量高：批處理系統(tǒng)的重要指標(biāo)慨丐。

單位時(shí)間內(nèi)所完成的作業(yè)數(shù)坡脐，跟作業(yè)本身（與作業(yè)平均長(zhǎng)度密切相關(guān)）和調(diào)度算法都有關(guān)系；

處理機(jī)利用率好(主要針對(duì)大中型主機(jī))

各類資源的平衡利用(主要針對(duì)大中型主機(jī))

3.2常用調(diào)度算法

1房揭、調(diào)度的實(shí)質(zhì)就是一種資源分配备闲。

2、先來(lái)先服務(wù)調(diào)度算法FCFS

1）一種最簡(jiǎn)單的調(diào)度算法捅暴，按先后順序進(jìn)行調(diào)度恬砂。既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度蓬痒。

2）按照作業(yè)提交泻骤，或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序分派CPU；

3）新作業(yè)只有當(dāng)當(dāng)前作業(yè)或進(jìn)程執(zhí)行完或阻塞才獲得CPU運(yùn)行

3梧奢、 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJF/SPF

1）優(yōu)點(diǎn)：

通過(guò)上表可見(jiàn)采用SJF/SPF算法狱掂，平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間都有明顯改善亲轨。SJF/SPF調(diào)度算法能有效的降低作業(yè)的平均等待時(shí)間趋惨，提高系統(tǒng)吞吐量。

2）方式：

分搶占和非搶占兩種方式惦蚊，上例為簡(jiǎn)單的非搶占式器虾。

4、高優(yōu)先權(quán)優(yōu)先調(diào)度算法HPF

1)分兩種方式：

非搶占式優(yōu)先權(quán)算法

搶占式優(yōu)先權(quán)算法? ? ?關(guān)鍵點(diǎn)：新作業(yè)產(chǎn)生時(shí)

2)優(yōu)先權(quán)的類型

靜態(tài)優(yōu)先權(quán)

動(dòng)態(tài)優(yōu)先權(quán)

3）高響應(yīng)比優(yōu)先調(diào)度算法HRRN

優(yōu)先權(quán) =（等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間

? ?? = 響應(yīng)時(shí)間 / 要求服務(wù)時(shí)間

5蹦锋、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法RR

1）分時(shí)系統(tǒng)新需求：及時(shí)響應(yīng)用戶的請(qǐng)求兆沙；采用基于時(shí)間片的輪轉(zhuǎn)式進(jìn)程調(diào)度算法。

2）時(shí)間片輪轉(zhuǎn)算法

（1.將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則莉掂，排成一個(gè)隊(duì)列葛圃。

（2.每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片巫湘。時(shí)間片的長(zhǎng)度從幾個(gè)ms到幾百ms。

（3.在一個(gè)時(shí)間片結(jié)束時(shí)昏鹃，發(fā)生時(shí)鐘中斷尚氛。

（4.調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾洞渤，并通過(guò)上下文切換執(zhí)行當(dāng)前就緒的隊(duì)首進(jìn)程阅嘶。

（5.進(jìn)程阻塞情況發(fā)生時(shí)，未用完時(shí)間片也要出讓CPU

3）多級(jí)反饋隊(duì)列算法FB

（1）特點(diǎn)：多個(gè)就緒隊(duì)列，循環(huán)反饋? ? ? 動(dòng)態(tài)優(yōu)先級(jí)讯柔、時(shí)間片輪轉(zhuǎn)

6抡蛙、總結(jié)1：

各算法進(jìn)行比較

7、總結(jié)2

幾種常用調(diào)度算法的比較

3.3實(shí)時(shí)調(diào)度

一魂迄、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件

1粗截、提供必要的信息

2、系統(tǒng)處理能力足夠強(qiáng)

3捣炬、采用搶占式調(diào)度機(jī)制

4熊昌、具有快速切換機(jī)制

二、實(shí)時(shí)調(diào)度算法的分類

1湿酸、根據(jù)實(shí)時(shí)任務(wù)的性質(zhì)

1）硬實(shí)時(shí)調(diào)度算法

2）軟實(shí)時(shí)調(diào)度算法

2婿屹、按調(diào)度方式

1）非搶占調(diào)度算法

2）搶占調(diào)度算法

3、根據(jù)調(diào)度時(shí)間不同

1）靜態(tài)調(diào)度算法

2）動(dòng)態(tài)調(diào)度算法

4推溃、多處理機(jī)環(huán)境下

1）集中式調(diào)度

2）分布式調(diào)度

3.4 產(chǎn)生死鎖的原因和必要條件

1昂利、死鎖（Deadlock）：指多個(gè)進(jìn)程在運(yùn)行過(guò)程中，因爭(zhēng)奪資源而造成的一種僵局铁坎。當(dāng)進(jìn)程處于這種狀態(tài)時(shí)蜂奸，若無(wú)外力作用，它們都將無(wú)法再向前推進(jìn)厢呵。

2窝撵、請(qǐng)求推進(jìn)的次序與對(duì)非剝奪性資源的爭(zhēng)用都是造成死鎖的原因。

3襟铭、產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)：

1）競(jìng)爭(zhēng)資源碌奉。

2）進(jìn)程間推進(jìn)順序非法。

4寒砖、產(chǎn)生死鎖的必要條件

①互斥條件：進(jìn)程對(duì)所分配到的資源進(jìn)行排他性使用

②請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源赐劣，又提出新的資源請(qǐng)求，而新請(qǐng)求資源被其他進(jìn)程占有只能造成自身進(jìn)程阻塞哩都，但對(duì)自己已獲得的其他資源保持不放魁兼，必然影響其他進(jìn)程。

③不剝奪條件：進(jìn)程已獲得的資源未使用完之前不能被剝奪漠嵌，只能在使用完時(shí)由自己釋放咐汞。

④環(huán)路等待條件

注：四個(gè)條件缺一不可！Ｈ迓埂化撕！

5、處理死鎖的基本方法

事先預(yù)防：

1）預(yù)防死鎖

2）避免死鎖

事后處理：

3）檢測(cè)死鎖

4）解除死鎖

3.5預(yù)防死鎖的方法

預(yù)防死鎖：

1约炎、摒棄“請(qǐng)求和保持”條件

2植阴、摒棄“不剝奪”條件

3蟹瘾、摒棄“環(huán)路等待”條件：有序設(shè)置資源

避免死鎖：

采用避免死鎖的方法則是只施加較弱限制條件，從而獲得令人滿意的系統(tǒng)性能掠手。

銀行家算法：

1憾朴、過(guò)程：就是對(duì)各進(jìn)程的Request向量及資源數(shù)量進(jìn)行一系列判斷及值操作。

進(jìn)程Pi發(fā)出資源請(qǐng)求后喷鸽，系統(tǒng)按下述步驟進(jìn)行檢查：

首先是兩個(gè)基本判斷：

（1）IF

Requesti[j]<= Need[i,j]

? THEN轉(zhuǎn)向步驟2众雷；

? ELSE 認(rèn)為出錯(cuò)，所需資源數(shù)超過(guò)宣布的最大值（自我矛盾)

（2）IF

Requesti[j]<= Available[j]

? THEN轉(zhuǎn)向步驟3魁衙；

? ELSE 表示尚無(wú)足夠資源报腔，Pi需等待（現(xiàn)實(shí)不滿足）

3.6死鎖的檢測(cè)與解除

1、檢測(cè)時(shí)機(jī)：

?當(dāng)進(jìn)程等待時(shí)檢測(cè)死鎖

?定時(shí)檢測(cè)

?系統(tǒng)資源利用率下降時(shí)檢測(cè)死鎖

2剖淀、檢測(cè)算法：

每個(gè)進(jìn)程和資源指定唯一編號(hào)

* 設(shè)置一張資源分配表

?記錄各進(jìn)程與其占用資源之間的關(guān)系

* 設(shè)置一張進(jìn)程等待表

?記錄各進(jìn)程與要申請(qǐng)資源之間的關(guān)系

3纯蛾、死鎖解除：

1）剝奪資源

2）撤銷進(jìn)程

4、

死鎖處理方法比較