第三章 中斷與處理機(jī)調(diào)度

1、3.2處理器調(diào)度，處理器調(diào)度任務(wù)是控制曹征進(jìn)程對CPU的競爭。也就是說，根據(jù)計劃調(diào)度算法，從準(zhǔn)備隊列中選擇流程，然后將CPU權(quán)限移交給選定流程。確定算法的原則，具有公正性。高資源利用率(尤其是CPU利用率)。對于交互式系統(tǒng)，需要追求響應(yīng)時間(越短越好)。部署系統(tǒng)需要系統(tǒng)吞吐量。1，先到先服務(wù)算法(FCFS)，按流程準(zhǔn)備的順序調(diào)度流程。優(yōu)點(diǎn)：簡單的實施。缺點(diǎn)：未考慮進(jìn)程的優(yōu)先級。2，優(yōu)先級算法(HPF)，優(yōu)先級隊列中優(yōu)先級最高的進(jìn)程優(yōu)先運(yùn)行。優(yōu)先級由優(yōu)先級數(shù)確定。確定優(yōu)先級的方法，靜態(tài)優(yōu)先級方法：創(chuàng)建流程時指定優(yōu)先級，流程運(yùn)行時優(yōu)先級保持不變。動態(tài)優(yōu)先級方法：創(chuàng)建進(jìn)程時創(chuàng)建優(yōu)先級，但優(yōu)先級可以在

2、整個生命周期中動態(tài)變更。如果等待時間較長，則可以更改優(yōu)先級。占用CPU的兩種方法，搶占：當(dāng)優(yōu)先級高于正在運(yùn)行的進(jìn)程準(zhǔn)備就緒時，可以強(qiáng)制剝奪正在運(yùn)行的進(jìn)程的CPU，以用于優(yōu)先級較高的進(jìn)程。不可剝奪(預(yù)占式Non-Preemptive):將進(jìn)程計劃為運(yùn)行后繼續(xù)運(yùn)行，除非它本身無法運(yùn)行。3，循環(huán)旋轉(zhuǎn)算法(RR)，將CPU劃分為時間片，然后按順序?qū)⑺鼈兎峙浣o準(zhǔn)備隊列中的每個進(jìn)程。進(jìn)程將依次占用CPU，如果時間片用完，即使進(jìn)程未運(yùn)行，也將取消進(jìn)程的CPU，并將進(jìn)程置于準(zhǔn)備隊列的末尾。同時，系統(tǒng)選擇另一個要運(yùn)行的進(jìn)程。3，循環(huán)旋轉(zhuǎn)算法(RR)，分時系統(tǒng)中常用的時間表旋轉(zhuǎn)算法。時間切片選擇問題：固定時間切片

3、可變時間切片與時間切片大小相關(guān)的因素：系統(tǒng)響應(yīng)時間準(zhǔn)備過程數(shù)CPU功能、時間切片選擇的兩個極端，以及時間切片值太小。大多數(shù)進(jìn)程不能在一個時間片內(nèi)運(yùn)行。轉(zhuǎn)換頻繁，系統(tǒng)開銷大大增加。時間切片值太大。每個進(jìn)程可以在一個時間片內(nèi)運(yùn)行。循環(huán)旋轉(zhuǎn)算法退化為第一服務(wù)算法，不能充分利用資源。4，反饋隊列算法(FB)，將準(zhǔn)備隊列分為N個階段，徐璐將每個準(zhǔn)備隊列分配給不同的片。隊列級別越高，切片越長，級別越小，切片越短，最后一個級別使用時間切片旋轉(zhuǎn)算法，其他隊列使用先到先得服務(wù)算法。系統(tǒng)在第一個級別保留，如果第一個級別為空，系統(tǒng)將移動到第二個隊列，如果執(zhí)行進(jìn)程用完一個小時片而放棄CPU，系統(tǒng)將移動到下一個級別的隊

4、列。等待進(jìn)程醒過來，進(jìn)入第一級隊列。流程第一次準(zhǔn)備就緒時，將進(jìn)入第一級隊列。4，反饋隊列算法，首先在系統(tǒng)中設(shè)置多個準(zhǔn)備隊列。每個準(zhǔn)備隊列將分配給第一個優(yōu)先級高的隊列和最小的片，徐璐分配給其他片，隨著隊列優(yōu)先級的降低，片將增加。每個隊列都遵循先進(jìn)先出計劃算法。新流程準(zhǔn)備就緒后，進(jìn)入主隊列。進(jìn)程由于等待而放棄CPU，然后進(jìn)入等待隊列，如果發(fā)生等待事件，則返回第一級隊列。優(yōu)先級高的流程準(zhǔn)備就緒后，可以搶占CPU，搶占的流程將返回到第一級隊列的末尾。當(dāng)主隊列為空時調(diào)度輔助隊列的方式。時間片耗盡后，進(jìn)程放棄CPU并返回到下一級別隊列。3.2.2處理器調(diào)度計時，進(jìn)程執(zhí)行完成或因任何錯誤而終止執(zhí)行。進(jìn)程運(yùn)行

5、時等待(等待I/O)。分時系統(tǒng)中的時間片已用完。優(yōu)先級高的流程準(zhǔn)備就緒后(可以搶占)。示例：創(chuàng)建新進(jìn)程并等待等待等待進(jìn)程就緒。在進(jìn)程通信中運(yùn)行的進(jìn)程執(zhí)行特定的原語操作(P操作、阻塞原語、喚醒原語)。、3.2.3處理器排程處理、處理轉(zhuǎn)換：一個處理是處理器，另一個處理是處理器占用的處理。進(jìn)程切換允許系統(tǒng)中的每個進(jìn)程占用CPU。流程切換是由于流程狀態(tài)更改而發(fā)生的，流程狀態(tài)更改與中斷的事件相關(guān)。3.2.3處理器調(diào)度進(jìn)程，當(dāng)發(fā)生中斷事件時，當(dāng)前運(yùn)行的進(jìn)程中斷，并在響應(yīng)中斷后處理操作系統(tǒng)中發(fā)生的中斷事件。停止處理后。某些進(jìn)程的狀態(tài)可能會更改，也可能會創(chuàng)建新進(jìn)程。因此，需要隊列協(xié)調(diào)。然后，根據(jù)預(yù)定義的調(diào)度算

6、法，通過從準(zhǔn)備隊列中選擇進(jìn)程來使用CPU。使用CPU的此進(jìn)程可能仍然是中斷的進(jìn)程，也可能是其他進(jìn)程。每次切換進(jìn)程時，只要操作系統(tǒng)控制CPU，就會發(fā)生進(jìn)程切換。例如：當(dāng)超級用戶調(diào)用程序的顯式請求(例如打開文件)時，通常會阻止進(jìn)程。陷阱中的最后一條指令導(dǎo)致錯誤，進(jìn)程進(jìn)入退出狀態(tài)。中斷外部元素影響當(dāng)前命令的執(zhí)行，并將控制發(fā)送到中斷處理程序(IH)。3.2.3處理器調(diào)度流程，現(xiàn)場保存：保存順序，最后一步保存PSW。選擇要運(yùn)行的程序：如果沒有準(zhǔn)備過程，將保留idle (IDLE)，以便在進(jìn)行中收到中斷。現(xiàn)場恢復(fù)：最后一步將還原選定流程的PSW。存儲處理器上下文，包括切換進(jìn)程(上下文)的步驟、程序計數(shù)器和

7、其他寄存器。使用新狀態(tài)和其他信息更新正在運(yùn)行進(jìn)程的PCB。將原始流程移動到相應(yīng)的隊列(準(zhǔn)備、阻止)。選擇要運(yùn)行的其他流程。更新選定進(jìn)程的PCB。從選定進(jìn)程重新加載CPU上下文。2.4任務(wù)，任務(wù)是要求用戶計算(或處理)計算機(jī)的相對獨(dú)立的任務(wù)。工作包括三部分：程序、數(shù)據(jù)和工作手冊。任務(wù)可以分為通常需要按邏輯順序處理的工作單元(或步驟)。這稱為工作階段。2.4任務(wù)，通常在計算機(jī)上運(yùn)行的程序分為三個階段。第一步：編譯第二步：鏈接第三步：運(yùn)行已裝配的執(zhí)行程序。2.4作業(yè)，在作業(yè)執(zhí)行過程中，每個作業(yè)步驟都緊密相關(guān)，前面作業(yè)步驟的執(zhí)行結(jié)果用作下一個作業(yè)步驟的執(zhí)行前提條件。操作、操作步驟、進(jìn)程之間的關(guān)系、用戶

8、、操作、操作步驟、操作步驟、進(jìn)程、進(jìn)程、.2.4根據(jù)作業(yè)、系統(tǒng)作業(yè)的處理方式，作業(yè)可以分為以下幾種：脫機(jī)作業(yè)是用戶不能直接與計算機(jī)交互，必須通過操作員干預(yù)的作業(yè)。(后臺任務(wù))聯(lián)機(jī)任務(wù)是用戶通過外圍設(shè)備直接與計算機(jī)系統(tǒng)交互來控制任務(wù)執(zhí)行的任務(wù)，也稱為交互任務(wù)。(前臺作業(yè))聯(lián)機(jī)作業(yè)更多地出現(xiàn)在分時系統(tǒng)中，脫機(jī)作業(yè)更多地出現(xiàn)在批處理系統(tǒng)中。作業(yè)狀態(tài)、作業(yè)在活動期間經(jīng)歷的四種狀態(tài)：1、提交狀態(tài)2、備份狀態(tài)(接受狀態(tài))3、運(yùn)行狀態(tài)(運(yùn)行狀態(tài))4、完成狀態(tài)、作業(yè)狀態(tài)和切換、提交狀態(tài)、備份狀態(tài)、提交狀態(tài)、運(yùn)行和運(yùn)行每個JCBJCB的內(nèi)容因系統(tǒng)而異。什么是作業(yè)調(diào)度，什么是作業(yè)調(diào)度？作業(yè)管理器必須根據(jù)特定策略從

9、備份操作中選擇多個作業(yè)，將它們加載到內(nèi)存中，并分配所需的資源，以便它們可以同時運(yùn)行。這是工作日程。有效：完成從替代狀態(tài)到運(yùn)行狀態(tài)的任務(wù)，完成從運(yùn)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)換。，調(diào)度算法需要實現(xiàn)的目標(biāo)，1，每次盡可能多的運(yùn)行任務(wù)。2、讓處理器保持忙碌。3、充分利用I/o設(shè)備；所有作業(yè)都公平合理。確定調(diào)度算法時要考慮的因素，1，調(diào)度算法必須與系統(tǒng)的總體設(shè)計目標(biāo)相匹配。2.注意系統(tǒng)資源的均衡使用，以確保I/o密集型任務(wù)與CPU密集型任務(wù)一起運(yùn)行。3.進(jìn)入系統(tǒng)的工作必須保證在規(guī)定的截止日期內(nèi)運(yùn)行完畢。測量調(diào)度算法性能的指標(biāo)，平均旋轉(zhuǎn)時間和平均皮帶旋轉(zhuǎn)時間通常在分時系統(tǒng)和實時系統(tǒng)中使用平均響應(yīng)時間來測量調(diào)度策

10、略的優(yōu)劣。1、周轉(zhuǎn)時間作業(yè)I的周轉(zhuǎn)時間定義為Ti=Tsi-Tti。其中Tsi是I作業(yè)完成時間，Tti是作業(yè)提交時間。確定在確定計劃算法時要考慮的因素。工作的旋轉(zhuǎn)時間可分為兩部分。一種是等待時間(從備份狀態(tài)到運(yùn)行狀態(tài))。第一，執(zhí)行時間。Ti=Twi Tri 2，加權(quán)處理時間任意n個任務(wù)(n=1)的平均加權(quán)處理時間，可以用任務(wù)調(diào)度算法，1，第一個服務(wù)調(diào)度算法(first-comefirst-set)表示，例如，提交時間根據(jù)先到先服務(wù)的調(diào)度算法調(diào)度。平均旋轉(zhuǎn)時間和平均加權(quán)旋轉(zhuǎn)時間分別為2.8和5.25。作業(yè)調(diào)度算法、2、短作業(yè)優(yōu)先級調(diào)度算法(Shortest-Job-First，SJF)短作業(yè)優(yōu)先級

11、調(diào)度算法是選擇運(yùn)行時間最短的作業(yè)作為下一個服務(wù)的目標(biāo)。該算法最小化了系統(tǒng)的平均周轉(zhuǎn)時間，因此系統(tǒng)吞吐量高。示例：對于上例中的任務(wù)，使用短任務(wù)優(yōu)先級調(diào)度算法進(jìn)行調(diào)度，計算出的平均周轉(zhuǎn)時間和平均加權(quán)周轉(zhuǎn)時間分別為2.45和3.85。任務(wù)調(diào)度算法，3，最大響應(yīng)比優(yōu)先級調(diào)度算法(highest-response-ratio-next，hrn)最大響應(yīng)比優(yōu)先級調(diào)度算法(HRN)為先到先得服務(wù)調(diào)度算法(FCFS)和短任務(wù)優(yōu)先級假定有四個任務(wù)，其中響應(yīng)率=(等待時間運(yùn)行時間)/運(yùn)行時間=1等待時間/運(yùn)行時間，例如提交時間，運(yùn)行時間使用最大響應(yīng)率優(yōu)先級計劃算法計算平均周轉(zhuǎn)時間和平均加權(quán)周轉(zhuǎn)時間，如下表所示：(其中時間單位是時間，計算為小數(shù))，例如，8點(diǎn)，因為僅提交作業(yè)1，所以系統(tǒng)將作業(yè)1投入運(yùn)行。任務(wù)1運(yùn)行2小時(即10.0點(diǎn))完成。該算法首先由響應(yīng)率高的人調(diào)度，