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

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

m

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