課件文稿助教

計(jì)算機(jī)操作助教 趙玉 按什么原則分配CPU何時(shí)分配CPU 調(diào)度的類型與調(diào)度算實(shí)時(shí)系統(tǒng)中的多處理 處理機(jī)管理的工作是對(duì)CPU 高級(jí)中級(jí)低級(jí) 接納多接納那 內(nèi)外存交換：又稱為“中級(jí)調(diào)度”。從器資源的角接。 非搶占搶占優(yōu)先

用戶該進(jìn)程多半會(huì)出狀至中斷處理 在進(jìn)程（上下文）中切換的用新把進(jìn)程移至合適的隊(duì)列-就緒更新被選中進(jìn)程的從被選中進(jìn)程中重裝入CPU上下 ，就緒隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等－批處外存等待時(shí)間、就緒等待時(shí)間、CPUI/O平均周轉(zhuǎn)時(shí)間、帶權(quán)平均周轉(zhuǎn)時(shí)間 優(yōu)先 作業(yè)在時(shí)間上可以。如：在2小時(shí)內(nèi)完成4個(gè)作處理機(jī)利用率：－－大中型 易于執(zhí)行開(kāi) 不可搶一旦，直到該進(jìn)程自己因調(diào)用原語(yǔ)操作或等待I/O因而進(jìn)入阻塞狀態(tài)，或時(shí)間片用完時(shí)才讓，重新進(jìn)搶占式 先來(lái)先服務(wù)(FCFS,FirstComeFirstService)當(dāng)前作業(yè)或進(jìn)程占用CPU出讓CPU（非搶占方式）有利于CPU繁忙的作業(yè)，不利于I/O繁忙的作 短作業(yè)優(yōu)先(SJF,ShortestJob又稱為“短進(jìn)程優(yōu)先”SPN(ShortestProcessNext)； 優(yōu)點(diǎn)提高缺點(diǎn)對(duì)長(zhǎng) 。 過(guò)短完，上下文切換次數(shù)增加，響應(yīng))*q A04B13C25D32E44 ABCD0123443524A 平均周轉(zhuǎn)時(shí)間＝ EAB 平均周轉(zhuǎn)時(shí)間＝ ABCD01234352 優(yōu)先級(jí)算法(Priority ）用戶要求（緊迫程度 多少 MultipleFeedback)O不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài) 。最終采用最大時(shí)間片來(lái)執(zhí)行，減少調(diào)度為適應(yīng)一個(gè)進(jìn)程在不同時(shí)間段的運(yùn)行特點(diǎn)，I/O 調(diào)度算FCFS,RoundRobin周轉(zhuǎn)時(shí)–長(zhǎng)作業(yè)時(shí)：T(FCFS)<T(響應(yīng)比)<T(RR)（運(yùn)行時(shí)間是主要因素–短作業(yè)時(shí)：T(RR)<T(響應(yīng)比)<T(FCFS)（等待時(shí)間是主要因素 采用搶 時(shí)間片Rate非搶占基于時(shí)立即搶

m

Ci Rate- 任務(wù)起始時(shí)間執(zhí)行時(shí)間周期截止時(shí)間014411222288EarliestDeadline 任務(wù)起始時(shí)間執(zhí)行時(shí)間周期截止時(shí)間050與單處注重整體運(yùn)行效率（而不是個(gè)別處理機(jī)的利用率多處理 OS數(shù)據(jù)結(jié)構(gòu)時(shí)的互斥（對(duì)于享內(nèi)存系統(tǒng)調(diào)度單 主－從，并分派進(jìn)程給從處理機(jī)執(zhí)處 按控制方式，SMP 靜態(tài)分配(staticassignment)：每個(gè)CPU，進(jìn)程從開(kāi)始執(zhí)行到完成，都在同一個(gè)CPU缺點(diǎn)動(dòng)態(tài)分配(dynamicassignment)：各個(gè)CPU采用一個(gè)公共就 自調(diào)度(self-scheduling)：各個(gè)CPU要對(duì)就緒隊(duì)列的數(shù)據(jù)結(jié)構(gòu)進(jìn)行互斥控制。是最常用變型：MachOS中局部和全局就緒隊(duì)列相結(jié)合，其中局部 瓶頸低效線程切 成組調(diào)度(gang一組處理機(jī)上執(zhí)行，在處理機(jī)時(shí)也同時(shí)對(duì) processorassignment)。 傳統(tǒng)UNIX饋隊(duì)列算法，進(jìn)程優(yōu)先級(jí)分為優(yōu)先級(jí)和用戶優(yōu)先 調(diào)度由0號(hào)進(jìn)程完成（始終在態(tài)執(zhí)行）。時(shí)機(jī)進(jìn)程由態(tài)轉(zhuǎn)入用戶態(tài)時(shí)：在每次執(zhí)行代碼之w或pauxit 于當(dāng)前進(jìn)程時(shí)，設(shè)置該標(biāo)識(shí)。在wakeup,setrun,setpri（設(shè)runin空間換入一個(gè)外存就緒runout 在UNIXSystemV中：進(jìn)程優(yōu)先數(shù)：P_priP_CPU2+PUSER+P_nice+NZERO系統(tǒng)設(shè)置部分：PUSER和NZERO數(shù)的閾值，分別為25和–新創(chuàng)建進(jìn)程的P_CPU值為0，因而具有較高的優(yōu)先 進(jìn)行處理。優(yōu)先級(jí)分為可中斷和不可中斷 分三個(gè)檢查是否作上下文切換（runrun標(biāo)志）和是否允許作上下文切換（對(duì)的各種數(shù)據(jù)結(jié)構(gòu)的操作都已經(jīng)完成，處于正確的狀態(tài)）。如果允許作?；謴?fù) Linux中實(shí)現(xiàn)了三種進(jìn)程調(diào)度策SCHED_OTHERSCHED_RR。輪轉(zhuǎn)（RoundRobin）方式執(zhí)行的實(shí)時(shí)進(jìn) 行隊(duì)列，而是通過(guò)權(quán)重的不同計(jì)算以及其他的一些隊(duì)列操作，在一個(gè)運(yùn)行隊(duì)列中實(shí)現(xiàn)這三種不同的調(diào)度。發(fā)生進(jìn)程調(diào)度時(shí)，調(diào)度程序要在運(yùn)行隊(duì)列中選擇一個(gè)最值得運(yùn)行的進(jìn)程來(lái)執(zhí)行，這個(gè)進(jìn)程便是通選擇的。權(quán)重越大的進(jìn)程越優(yōu)，而對(duì)于相同權(quán)重的 調(diào)度策略為SCHD_調(diào)度策略為SCHED_FIFO的進(jìn)程，在時(shí)間片到，調(diào)度程序并不改變?cè)撨M(jìn)程在運(yùn)行隊(duì)列中的位 程繼承了父進(jìn)程的優(yōu)先級(jí)。prort過(guò)系統(tǒng)調(diào)用sys_setpriority（sys_nicesys_setpriority取代）系統(tǒng)為每個(gè)進(jìn)程預(yù)定的priority為（include/linux/sched.h），200ms prioity來(lái)反映其優(yōu)先級(jí)（可執(zhí)rt_pioity1~99，一般進(jìn)程rt_prortr_pioitysetschedue coune，直至0。由于時(shí)count 計(jì)數(shù)器counersys_idle()時(shí)，將counter值置為-100。 在進(jìn)程運(yùn)行期間，每次發(fā)生時(shí)鐘中斷時(shí)，counter值減，直至為0contcont 調(diào)度的類型（如調(diào)度單位的不同級(jí)別，時(shí)間，不同的OS），性能實(shí)時(shí)調(diào)度：調(diào)度算 死鎖發(fā)生競(jìng)爭(zhēng)資并發(fā)執(zhí)行的順序 資源：CPU，內(nèi)存非 資源：磁帶機(jī) 臨時(shí)性資 競(jìng)爭(zhēng)臨 P2:Rel(R1)P2:P2:Req(R1)P2:P1:Req(R1)P1:Req(R2)P1:Req(R1) ：進(jìn)程已經(jīng)占用的資源，不會(huì)被強(qiáng) 預(yù)防死避免死檢測(cè)死解除死 互斥：設(shè)備請(qǐng)求和保持 申請(qǐng)所有資資源浪運(yùn)行延 ：增加系統(tǒng)開(kāi)環(huán)路等待：影響資源利 在分配如不） 安全狀態(tài)：系統(tǒng)存在一個(gè)序列<p1,p2,..pn>不安全狀 進(jìn)可534292 進(jìn)可524293銀行家算法（Dijkstra, 當(dāng)一個(gè)顧客 的最大需求量不超過(guò)銀行家現(xiàn) 時(shí)可接納顧顧客可以分期，但總 過(guò)最大需求當(dāng)銀行家現(xiàn)有的不能滿足顧客尚需的數(shù)額時(shí)，對(duì)顧客的可推遲支付，但總能使顧客在有限的時(shí)間里得到貸當(dāng)顧客得到所需的全部所有；安全性（能否支持顧客借款，直到全部歸還安全時(shí) ；否則，暫 可利用資源向量最大需求矩陣分配矩陣需求矩陣5processesPthroughP3resourcetypes(10instances),B(5instances),andC(7ABABABABAB0175332032309021220043Thecontentofthematrix.NeedisdefinedtobeMax–Allocation.ABP074P112P260P301P443

AllocationMaxABABAB0175332032309021220043

33537474104105Thesystemisinasafestatesincethesequence<P1,P3,P4,P2,P0>satisfiessafetycriteria.CheckthatRequestAvailable(thatis,(1,0,2)AABABAB0174233002306021010043Executingsafetyalgorithmshowsthatsequence<PP,PPPsatisfiessa