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

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

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

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

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

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

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

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

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

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

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

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