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

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

1. 高級(jí)調(diào)度：高級(jí)調(diào)度稱為作業(yè)調(diào)度乞旦，它的調(diào)度對(duì)象是作業(yè)措拇。主要功能是根據(jù)某種算法钻注，決定將外村上處于后備隊(duì)列中的哪幾個(gè)作業(yè)調(diào)入內(nèi)存篮撑，并將它們放入就緒隊(duì)列
2. 低級(jí)調(diào)度：低級(jí)調(diào)度稱為進(jìn)程調(diào)度逞壁，其所調(diào)度的對(duì)象是進(jìn)程猎莲。主要功能是根據(jù)某種算法绍弟，決定就緒隊(duì)列中的哪個(gè)進(jìn)程獲得處理機(jī)
3. 中級(jí)調(diào)度：也稱為內(nèi)存調(diào)度，主要是為了提高內(nèi)存利用率和系統(tǒng)吞吐量著洼，會(huì)把那些暫時(shí)不能運(yùn)行的進(jìn)程樟遣，調(diào)至外存等待，此時(shí)進(jìn)程的狀態(tài)稱為掛起狀態(tài)

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

1. 資源利用率

2. 平均周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間指從作業(yè)被提交給系統(tǒng)開(kāi)始身笤，到作業(yè)完成為止這段時(shí)間間隔豹悬。但是對(duì)于n個(gè)作業(yè)而言，平均周轉(zhuǎn)時(shí)間可以表示為

3. 平均帶權(quán)周轉(zhuǎn)時(shí)間可以用周轉(zhuǎn)時(shí)間與系統(tǒng)為其服務(wù)的時(shí)間之比來(lái)表示

4. 系統(tǒng)吞吐量：吞吐量是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)

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

3.2.3 先來(lái)先服務(wù)（FCFS）和短作業(yè)優(yōu)先（SJF）調(diào)度算法

1. 先來(lái)先服務(wù)（FCFS）調(diào)度算法：系統(tǒng)將按照作業(yè)到達(dá)的先后順序來(lái)進(jìn)行調(diào)度
2. 短作業(yè)郵箱（SJF）的調(diào)度算法
   • 以作業(yè)的長(zhǎng)短來(lái)計(jì)算優(yōu)先級(jí)液荸，作業(yè)越短優(yōu)先級(jí)越高
   • 但是主要缺點(diǎn)為：必須預(yù)知作業(yè)的運(yùn)行時(shí)間瞻佛；對(duì)長(zhǎng)作業(yè)十分不利

3.2.4 優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法

1. 優(yōu)先調(diào)度算法（PSA）：基于作業(yè)的緊迫程度，由外部賦予作業(yè)相應(yīng)的優(yōu)先級(jí)
2. 高響應(yīng)比優(yōu)先調(diào)度算法（HRRN）：綜合考慮了作業(yè)的等待時(shí)間和作業(yè)的運(yùn)行時(shí)間確定優(yōu)先級(jí)莹弊，主要是根據(jù)作業(yè)等待時(shí)間延長(zhǎng)而增加優(yōu)先級(jí)涤久，因此相應(yīng)比可以表示為：

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

1. 進(jìn)程調(diào)度方式
   • 非搶占式：一旦把處理機(jī)分配給某進(jìn)程后，就一直讓它運(yùn)行下去
   • 搶占方式：允許程序根據(jù)某種原則忍弛，去暫停某個(gè)正在執(zhí)行的進(jìn)程

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

1. 基本原理：系統(tǒng)根據(jù)FCFS策略响迂，將所有的就緒進(jìn)程排成一個(gè)就緒隊(duì)列，并可以設(shè)置每隔一段時(shí)間間隔即產(chǎn)生一次中斷细疚，激活系統(tǒng)中的進(jìn)程調(diào)度程序蔗彤，完成一次調(diào)度
2. 進(jìn)程切換時(shí)機(jī)
   • 若一個(gè)時(shí)間片尚未用完川梅，正在運(yùn)行的進(jìn)程便已經(jīng)完成了，就立即激活調(diào)度程序然遏，將其刪除贫途，并從就緒隊(duì)列隊(duì)首選取進(jìn)程運(yùn)行，開(kāi)始一個(gè)新的時(shí)間片
   • 在一個(gè)時(shí)間片用完時(shí)待侵，計(jì)時(shí)器中斷處理程序被激活丢早，如果進(jìn)程尚未完成運(yùn)行，調(diào)度程序?qū)阉屯途w隊(duì)列的末尾秧倾。

3.3.3 優(yōu)先級(jí)調(diào)度算法

• 優(yōu)先級(jí)調(diào)度算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程
• 非搶占式優(yōu)先級(jí)調(diào)度算法
• 搶占式優(yōu)先級(jí)調(diào)度算法

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

• 實(shí)時(shí)調(diào)度必須滿足實(shí)時(shí)任務(wù)對(duì)于截止時(shí)間的要求

3.5 死鎖概述

3.5.2 計(jì)算機(jī)系統(tǒng)中的死鎖

• 造成死鎖的起因有如下幾種可能：
  1. 競(jìng)爭(zhēng)不可搶占性資源引起死鎖
  2. 競(jìng)爭(zhēng)可消耗資源引起死鎖
  3. 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖

3.5.3 死鎖的定義怨酝、必要條件和處理方法

• 如果一組進(jìn)程中的每一個(gè)進(jìn)程都在等待僅有該組進(jìn)程中的其他進(jìn)程才能引發(fā)的事件，那么改組進(jìn)程是死鎖的
• 產(chǎn)生死鎖的條件
  • 互斥條件：進(jìn)程對(duì)所分配到的資源進(jìn)行排他性使用
  • 請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源那先，但又提出新的資源請(qǐng)求农猬，但是該資源被其他進(jìn)程占有
  • 不可搶占條件：進(jìn)程已經(jīng)獲得的資源在未使用完之前不能被搶占
  • 循環(huán)等待條件：在發(fā)生死鎖使，必然存在一個(gè)進(jìn)程—資源的循環(huán)鏈

3.6 預(yù)防死鎖

3.6.1 破壞“請(qǐng)求和保持”條件

• 第一種方法：所有程序在開(kāi)始運(yùn)行之前售淡，必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過(guò)程中所需的全部資源斤葱，只要有一種資源無(wú)法滿足，其余資源也不分配
• 第二種方法：允許一個(gè)進(jìn)程只獲得運(yùn)行初期所需的資源后揖闸，便開(kāi)始運(yùn)行揍堕。進(jìn)程運(yùn)行過(guò)程中再逐步釋放已經(jīng)分配給自己、且已經(jīng)用完的全部資源汤纸。

3.6.2 破壞“不可搶占”條件

• 當(dāng)一個(gè)已經(jīng)保持了某些不可被搶占資源的進(jìn)程鹤啡，提出新的資源得不到滿足時(shí)，必須釋放已經(jīng)保持的所有資源蹲嚣，待以后需要的時(shí)候重新申請(qǐng)

3.6.3 破壞“循環(huán)等待”條件

• 先對(duì)系統(tǒng)所有的資源類型進(jìn)行線性分類递瑰，要求進(jìn)程再請(qǐng)求某類資源時(shí)，必須保證所請(qǐng)求的資源數(shù)量小于當(dāng)前可以被請(qǐng)求的資源數(shù)量

3.7 避免死鎖

3.7.1 系統(tǒng)安全狀態(tài)

• 系統(tǒng)在進(jìn)行資源分配之前隙畜，應(yīng)先計(jì)算此次資源分配的安全性抖部，若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，才可將資源分配給進(jìn)程议惰。
• 所謂安全狀態(tài)就是指系統(tǒng)能按照某種進(jìn)程推進(jìn)順序?yàn)槊總€(gè)進(jìn)程分配其所需要的資源慎颗，直到滿足每個(gè)進(jìn)程對(duì)資源的最大需求
• 以下舉例，可以發(fā)現(xiàn)通過(guò)安全序列<P2,P2,P3>的順序可以完成資源分配言询，因此為安全狀態(tài)

安全狀態(tài)例子

3.7.2 利用銀行家算法避免死鎖