課件文稿助教

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

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

m

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