1.處理機調(diào)度的基本概念
1）高級調(diào)度：
又稱作業(yè)調(diào)度或長程調(diào)度(Long-Term Scheduling),接納調(diào)度(Admission Scheduling)
作業(yè)調(diào)度決定的細節(jié)
接納多少作業(yè)——取決于多道程序度祥得。應(yīng)根據(jù)系統(tǒng)的規(guī)模和運行速度等情況綜合考慮。
接納哪些作業(yè)——取決于采用的調(diào)度算法蒋得。如先來先服務(wù)级及，短作業(yè)優(yōu)先等
系統(tǒng)運行并不一定存在高級調(diào)度
批處理系統(tǒng)：作業(yè)進入系統(tǒng)后先駐留外存，故需要有作業(yè)調(diào)度额衙。
分時系統(tǒng)：為及時響應(yīng)饮焦，作業(yè)由終端直接送入內(nèi)存，故不需作業(yè)調(diào)度窍侧。
實時系統(tǒng)中县踢，通常也不需作業(yè)調(diào)度。
2）低級調(diào)度：
也稱為進程調(diào)度疏之、微觀調(diào)度或短程調(diào)度（Short-Term Scheduling）。決定內(nèi)存就緒隊列中的哪個進程獲得處理機暇咆，進行分配工作锋爪。是最基本的一種調(diào)度，在三種基本OS中都有爸业。
（1）進程調(diào)度方式
非搶占方式（Non-preemptive Mode）
一旦處理機分配給某進程其骄，該進程一直執(zhí)行。決不允許其他進程搶占已分配運行進程的處理機扯旷。
搶占方式（Preemptive Mode）
允許調(diào)度程序根據(jù)某種原則拯爽，暫停某個正在執(zhí)行的進程，將處理機重新分配給另一進程钧忽。
(2)進程調(diào)度方式比較
（3）中級調(diào)度
又稱交換調(diào)度或中程調(diào)度（Medium-Term Scheduling）
引入目的：提高內(nèi)存利用率和系統(tǒng)吞吐量毯炮。根據(jù)條件將一些進程調(diào)出或再調(diào)入內(nèi)存。
（4）調(diào)度隊列模型
僅有進程調(diào)度的調(diào)度隊列模型： 分時系統(tǒng)
具有高級和低級調(diào)度的調(diào)度隊列模型：批處理系統(tǒng)中耸黑，還需要作業(yè)調(diào)度
同時具有三級調(diào)度的調(diào)度隊列模型
（5）選擇調(diào)度方式和調(diào)度算法的若干準則
① 面向用戶的準則：
周轉(zhuǎn)時間短桃煎、響應(yīng)時間快、均衡性大刊、截止時間的保證为迈、優(yōu)先權(quán)準則
② 面向系統(tǒng)的準則：
系統(tǒng)吞吐量高、處理機利用率好(主要針對大中型主機)缺菌、各類資源的平衡利用(主要針對大中型主機)
2.常用調(diào)度算法
1）先來先服務(wù)調(diào)度算法FCFS
一種最簡單的調(diào)度算法葫辐，按先后順序進行調(diào)度。既可用于作業(yè)調(diào)度伴郁，也可用于進程調(diào)度耿战。
2）短作業(yè)（進程）優(yōu)先調(diào)度算法SJF/SPF（搶占式和非搶占式）
SJF/SPF的不足：
①. 對短作業(yè)有利，但同時造成了對長作業(yè)的不利焊傅。
②.由于作業(yè)（進程）的長短含主觀因素昆箕，不一定能真正做到短作業(yè)優(yōu)先鸦列。
?③.未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進程）的及時處理鹏倘。
3）高優(yōu)先權(quán)優(yōu)先調(diào)度算法HPF （搶占式和非搶占式）
照顧緊迫性作業(yè)薯嗤，使其獲得優(yōu)先處理而引入調(diào)度算法。常用于批處理系統(tǒng)中的作業(yè)調(diào)度算法纤泵，以及多種操作系統(tǒng)中的進程調(diào)度算法
（1）優(yōu)先權(quán)的類型
靜態(tài)優(yōu)先權(quán)：創(chuàng)建進程時確定骆姐，整個運行期間保持不變。一般利用某一范圍的一個整數(shù)來表示捏题，又稱為優(yōu)先數(shù)玻褪。
動態(tài)優(yōu)先權(quán)：創(chuàng)建進程時賦予的優(yōu)先權(quán)可隨進程的推進或隨其等待時間的增加而改變。
（2）進程優(yōu)先權(quán)的確定
進程類型公荧、進程對資源的需求带射、用戶需求
4）高響應(yīng)比優(yōu)先調(diào)度算法HRRN
HRRN為每個作業(yè)引入動態(tài)優(yōu)先權(quán)，使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a提高：
? 優(yōu)先權(quán) =（等待時間+要求服務(wù)時間)/要求服務(wù)時間= 響應(yīng)時間 / 要求服務(wù)時間
（1）同時到達的作業(yè)優(yōu)先權(quán)相同循狰。
（2）當執(zhí)行時間相同的作業(yè)窟社，優(yōu)先權(quán)的高低決定于其等待時間的長短，也就是先來先服務(wù)绪钥。
5）基于時間片的輪轉(zhuǎn)調(diào)度算法RR?
分時系統(tǒng)新需求：及時響應(yīng)用戶的請求灿里；采用基于時間片的輪轉(zhuǎn)式進程調(diào)度算法。
（1）時間片輪轉(zhuǎn)算法
將系統(tǒng)中所有的就緒進程按照FCFS原則程腹，排成一個隊列匣吊。
每次調(diào)度時將CPU分派給隊首進程，讓其執(zhí)行一個時間片寸潦。時間片的長度從幾個ms到幾百ms色鸳。
在一個時間片結(jié)束時，發(fā)生時鐘中斷见转。
調(diào)度程序據(jù)此暫停當前進程的執(zhí)行缕碎，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當前就緒的隊首進程池户。
（2）多級反饋隊列算法FB
設(shè)置多個就緒隊列咏雌，各隊列有不同的優(yōu)先級,優(yōu)先級從第一個隊列依次降低。
?賦予各隊列進程執(zhí)行時間片大小不同, 優(yōu)先權(quán)越高校焦，時間片越短赊抖。
6）幾種常用調(diào)度算法的比較
3.實時調(diào)度
1）實現(xiàn)實時調(diào)度的基本條件
提供必要的信息
系統(tǒng)處理能力足夠強
采用搶占式調(diào)度機制
具有快速切換機制
2）實時調(diào)度算法的分類
非搶占調(diào)度算法
搶占式調(diào)度算法
3）常用的幾種實時調(diào)度算法
（1）最早截止時間優(yōu)先EDF
根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級。截止時間越早寨典，其優(yōu)先級越高氛雪。
（2）最低松弛度優(yōu)先LLF?
根據(jù)任務(wù)緊急（或松弛）的程度，來確定任務(wù)的優(yōu)先級耸成。任務(wù)的緊急程度越高（松弛度值越斜丁）浴鸿，優(yōu)先級就越高。
松弛度= 截止完成時間 – 還需執(zhí)行時間 - 當前時間
可理解為當前時刻到開始截止時刻間的差距弦追，隨著時間的推進岳链，這個差值逐漸變小，任務(wù)越來越緊迫劲件。
4.產(chǎn)生死鎖的原因和必要條件
死鎖（Deadlock）：指多個進程在運行過程中掸哑，因爭奪資源而造成的一種僵局。當進程處于這種狀態(tài)時零远，若無外力作用苗分，它們都將無法再向前推進。
死鎖（Deadlock）: 指進程之間無休止地互相等待!
饑餓（Starvation）:指一個進程無休止地等待牵辣！
1）競爭資源引起進程死鎖
可把系統(tǒng)中的資源分為兩類：
可剝奪和非剝奪性資源
永久性資源和臨時性資源
2）進程推進順序不當引起死鎖
3） 產(chǎn)生死鎖的必要條件
互斥條件：
進程對所分配到的資源進行排他性使用
請求和保持條件：
進程已經(jīng)保持了至少一個資源摔癣，又提出新的資源請求，而新請求資源被其他進程占有只能造成自身進程阻塞纬向，但對自己已獲得的其他資源保持不放择浊，必然影響其他進程。
不剝奪條件：
進程已獲得的資源未使用完之前不能被剝奪罢猪，只能在使用完時由自己釋放近她。
環(huán)路等待條件
4）處理死鎖的基本方法
事先預(yù)防：
（1）預(yù)防死鎖：
（2）避免死鎖：
事后處理：
（3）檢測死鎖
（4）解除死鎖
5.預(yù)防死鎖的方法
1）預(yù)防死鎖
（1）摒棄“請求和保持”條件
（2）摒棄“不剝奪”條件
（3）摒棄“環(huán)路等待”條件
6.死鎖的檢測與解除
當系統(tǒng)為進程分配資源時叉瘩，若未采取任何限制性措施膳帕，則系統(tǒng)必須提供檢測和解除死鎖的手段，為此系統(tǒng)必須：
保存有關(guān)資源的請求和分配信息薇缅；
提供一種算法危彩，以利用這些信息來檢測系統(tǒng)是否已進入死鎖狀態(tài)。
1）死鎖的檢測
檢測時機：
當進程等待時檢測死鎖
定時檢測
系統(tǒng)資源利用率下降時檢測死鎖
2）死鎖定理
利用資源分配圖簡化法來檢測死鎖
3）死鎖檢測算法：
* 每個進程和資源指定唯一編號
* 設(shè)置一張資源分配表
? 記錄各進程與其占用資源之間的關(guān)系
* 設(shè)置一張進程等待表
? 記錄各進程與要申請資源之間的關(guān)系
4）死鎖的解除
當發(fā)現(xiàn)進程死鎖時泳桦，便應(yīng)立即把它們從死鎖狀態(tài)中解脫出來汤徽。常采用的方法是：
剝奪資源：
從其他進程剝奪足夠數(shù)量的資源給死鎖進程以解除死鎖狀態(tài)。
撤銷進程：
最簡單的是讓全部進程都死掉灸撰；溫和一點的是按照某種順序逐個撤銷進程谒府，直至有足夠的資源可用，使死鎖狀態(tài)消除為止浮毯。
5）死鎖處理方法比較
