3.1處理機調(diào)度相關基本概念
處理機調(diào)度
1高級調(diào)度：又稱作業(yè)調(diào)度或長程調(diào)度，接納調(diào)度（主要在早期批處理階段，處理在外存上的作業(yè)）
系統(tǒng)運行并不一定存在高級調(diào)度
2.低級調(diào)度：也稱為進程調(diào)度蚯涮、微觀調(diào)度或短程調(diào)度
最基本的一種調(diào)度粗俱，在批處理系統(tǒng)、分時系統(tǒng)泽腮、實時系統(tǒng)中都有
3.中級調(diào)度
引入目的：提高內(nèi)存利用率和系統(tǒng)吞吐量
5.選擇調(diào)度方式和調(diào)度算法的若干準則
1）面向用戶的準則：周轉時間短患民、響應時間快、均衡性垦梆、截止時間的保證匹颤、優(yōu)先權準則
2）面向系統(tǒng)的準則：系統(tǒng)吞吐量高、處理機利用率好托猩、各類資源的平衡利用
二印蓖、調(diào)度算法
1.先來先服務調(diào)度算法FCFS（非搶占方式）
按照作業(yè)提交【┬龋或進程變?yōu)榫途w狀態(tài)的先后次序分派CPU赦肃，新作業(yè)只有當當前作業(yè)或進程執(zhí)行完或阻塞才獲得CPU運行
不利于段作業(yè)（進程）
不足：段作業(yè)C的帶權周轉時間高達100長作業(yè)D的帶權周轉時間僅為1.99；有利于CPU繁忙型的作業(yè)公浪，而不利于I/o繁忙的作業(yè)
???????? 2.短作業(yè)（進程）有限調(diào)度算法SJF/SPF
此算法能有效的降低作業(yè)的平均等待時間他宛，提高系統(tǒng)吞吐量
方式：分搶占和非搶占兩種方式，上例為簡單的非搶占式欠气。
不足：1.對短作業(yè)有利厅各，但同時造成了對長作業(yè)的不利。2.由于作業(yè)（進程）的長短含主觀因素预柒，不一定能真正做到短作業(yè)優(yōu)先队塘。3.未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)的及時處理宜鸯。
3.高優(yōu)先權優(yōu)先調(diào)度算法HPF
1）分非搶占式和搶占式優(yōu)先權算法（關鍵點：新作業(yè)產(chǎn)生時）
2）優(yōu)先權的類型
靜態(tài)優(yōu)先權：創(chuàng)建進程時確定憔古，整個運行期間保持不變
動態(tài)優(yōu)先權：創(chuàng)建進程時賦予的優(yōu)先權，可隨進程的推進或隨其等待時間的增加而改變
3）高響應比優(yōu)先調(diào)度算法HRRN
HRRN為每個作業(yè)引入動態(tài)優(yōu)先權淋袖，使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a提高
1.同時到達的作業(yè)優(yōu)先權相同（若等待時間t相同鸿市，利于短作業(yè)；長作業(yè)的優(yōu)先級隨等待時間的增加而提高）
2.實行時間相同的作業(yè)适贸，優(yōu)先權的高低決定于其等待時間的長短灸芳，也就是先來先服務
什么時候計算各進程的響應比優(yōu)先權？
調(diào)度選擇時：作業(yè)完成時拜姿、新作業(yè)完成時（搶占烙样、非搶占）、時間片完成時蕊肥、進程阻塞時
3.基于時間片的輪轉調(diào)度算法RR
（1）時間片輪轉算法
時間片長度???????????????? 過長：FCFS??? 過短：頻繁切換
（2）多級反饋隊列算法FB
1.設置多個就緒隊列谒获，各隊列有不同的優(yōu)先級蛤肌，優(yōu)先級從第一個隊列依次降低
2.賦予各隊列進程執(zhí)行時間片大小不同，優(yōu)先權越高批狱，時間片越短
三裸准、實時調(diào)度
1.系統(tǒng)能夠在限定的響應時間內(nèi)提供所需水平的服務
2.計算的正確性不僅取決于程序的邏輯正確性，也取決于結果產(chǎn)生的時間赔硫，如果系統(tǒng)的時間約束條件得不到滿足炒俱，將會發(fā)生系統(tǒng)出錯
基本條件：
1）提供必要的信息
就緒時間、開始截止時間爪膊、完成截止時間权悟、處理時間、資源要求推盛、優(yōu)先級
2）系統(tǒng)能力足夠強
3）采用搶占式調(diào)度機制
4）具有快速切換機制
搶占式調(diào)度算法：1峦阁、基于時鐘：某高優(yōu)先級任務到達后并不立即搶占，耘成，而等下一個時鐘中斷時搶占榔昔。2、立即搶占：一旦出現(xiàn)外部中斷瘪菌，只要當前任務未處于臨界區(qū)撒会，就立即搶占處理機。
最早截止時間優(yōu)先EDF控嗜、最低松弛度優(yōu)先LLF（主要用于搶占調(diào)度方式中）
四茧彤、產(chǎn)生死鎖的原因和必要條件
多道程序系統(tǒng)借助并發(fā)執(zhí)行改善資源利用率，提高系統(tǒng)吞吐量疆栏，但可能發(fā)生一種危險——死鎖（指多個進程在運行過程中曾掂，因爭奪資源而造成的一種僵局。當進程處于這種狀態(tài)時壁顶，若無外力作用珠洗，它們都將無法再向前推進）
饑餓：指一個進程無休止地等待
產(chǎn)生死鎖的原因：1.競爭資源???? 2.進程間推進程序非法（請求和釋放資源的順序不當）
產(chǎn)生死鎖的必要條件：互斥條件、請求和保持條件若专、不剝奪條件许蓖、環(huán)路等待條件
死鎖避免屬于動態(tài)策略
預防死鎖：
①摒棄“請求和保持”條件：所有進程開始運行前，必須一次性的申請其在整個運行過程所需的全部資源（AND）调衰。算法簡單膊爪、易于實現(xiàn)且很安全。但缺點是資源浪費嚴重嚎莉、或進程延遲運行米酬。
②摒棄“不剝奪”條件：允許進程先運行，但當提出的新要求不被滿足時必須釋放它已保持的所有資源趋箩，待以后需要時再重新申請赃额。實現(xiàn)比較復雜且付出很大代價加派。可能會造成前功盡棄跳芳，反復申請和釋放等情況芍锦。
③摒棄“環(huán)路等待”條件：將所有資源按類型進行線性排隊，賦予不同序號飞盆。所有進程對資源的請求必須嚴格按照資源序號遞增的次序提出娄琉，這樣在所形成的資源分配圖中，不可能會出現(xiàn)環(huán)路吓歇。
2.避免死鎖
安全狀態(tài)：沒有死鎖车胡；不安全狀態(tài)：可能會產(chǎn)生死鎖
安全序列：只要系統(tǒng)按此進程列分配資源，就能使每個進程都順利完成照瘾。
3.銀行家算法避免死鎖
死鎖的解除：1.剝奪進程。2.撤銷進程
