操作系統(tǒng)原理：處理機調度

處理機調度

處理機調度1、功能

對CPU資源進行合理的分配使用，提高處理機利用率，并使各用戶公平地得到處理機資源。

處理機調度2、解決的問題（3W）WHAT：按什么原則分配CPU—進程調度算法（主要內容）WHEN：何時分配CPU—進程調度的時機HOW：如何分配CPU—CPU調度過程（進程的上下文切換）提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內存4.1分級調度1、

作業(yè)的狀態(tài)及其轉換就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調度線程調度進程調度作業(yè)調度（1）提交狀態(tài)：作業(yè)處于從輸入設備進入外存的過程；（2）收容狀態(tài)：作業(yè)的全部信息被輸入到輸入井，尚未被調度執(zhí)行；（3）完成狀態(tài)：作業(yè)運行完畢，所占資源尚未被收回。1、作業(yè)的狀態(tài)及其轉換一個作業(yè)從提交給計算機系統(tǒng)到執(zhí)行結束退出系統(tǒng)，一般都要經(jīng)歷提交、后備、執(zhí)行和完成等4個狀態(tài)。（1）提交狀態(tài)：一個作業(yè)在其處于從輸入設備進入外部存儲設備的過程稱為提交狀態(tài)。4.1分級調度1、作業(yè)的狀態(tài)及其轉換（2）后備狀態(tài)：也稱為收容狀態(tài)。若一個作業(yè)的全部信息已全部被輸入進輸入井，則在它還未被調度去執(zhí)行之前，該作業(yè)處于后備狀態(tài)。4.1分級調度（3）執(zhí)行狀態(tài)：作業(yè)調度程序從后備作業(yè)中選取若干個作業(yè)到內存投入運行。它為被選中作業(yè)建立進程并分配必要的資源，這時，這些被選中的作業(yè)處于執(zhí)行狀態(tài)。1、作業(yè)的狀態(tài)及其轉換4.1分級調度（4）完成狀態(tài)：當作業(yè)運行完畢，但它所占用的資源尚未全部被系統(tǒng)回收時，該作業(yè)處于完成狀態(tài)。1、作業(yè)的狀態(tài)及其轉換4.1分級調度一個作業(yè)從進入系統(tǒng)到運行結束,經(jīng)歷的狀態(tài)包括_________。進入狀態(tài)A就緒狀態(tài)B后備狀態(tài)C運行狀態(tài)D完成狀態(tài)E提交多選題1分2調度的層次提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調度線程調度進程調度作業(yè)調度第1級：作業(yè)調度、宏觀調度、高級調度對外存輸入井上的大量作業(yè)進行選擇，對選擇的作業(yè)分配資源，建立相應進程。作業(yè)執(zhí)行完畢時，回收資源。4.1分級調度提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調度線程調度進程調度作業(yè)調度第2級：交換調度、中級調度將處于外存交換區(qū)中的就緒狀態(tài)或等待狀態(tài)的進程調入內存，或把處于內存就緒狀態(tài)或內存等待狀態(tài)的進程交換導外存交換區(qū)。4.1分級調度2調度的層次提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調度線程調度進程調度作業(yè)調度第3級：進程調度、微觀調度、低級調度選取一個處于就緒狀態(tài)的進程占用處理機，之后，進行上下文切換以便建立與占用處理機進程相適應的執(zhí)行環(huán)境。2調度的層次4.1分級調度提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調度線程調度進程調度作業(yè)調度第4級：線程調度選取一個處于就緒狀態(tài)的線程進入執(zhí)行狀態(tài)。2調度的層次4.1分級調度提交狀態(tài)收容狀態(tài)完成狀態(tài)外存內存就緒等待就緒等待執(zhí)行輸入管理系統(tǒng)交換調度線程調度進程調度作業(yè)調度多道批處理系統(tǒng)存在作業(yè)調度和進程調度；分時系統(tǒng)和實時系統(tǒng)一般只有進程調度、交換調度和線程調度。2調度的層次4.1分級調度一個作業(yè)處于運行狀態(tài),則所屬該作業(yè)的進程可能處于（）狀態(tài)。運行A就緒B等待C(1)或(2)或(3)D提交單選題1分AdmitRunningReadySuspendReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendEventOccursActivateAdmit宏觀調度微觀調度中級調度ActivateSuspendSuspendExitNew2調度的層次4.1分級調度下列有關作業(yè)的敘述中,_________是正確的。作業(yè)一旦被作業(yè)調度選中,即占有了CPUA批處理系統(tǒng)對作業(yè)的控制意圖是靠作業(yè)說明書來實現(xiàn)的,用戶不能控制作業(yè)的執(zhí)行B作業(yè)調度程序從處于等待狀態(tài)的隊列中選取作業(yè)投入運行C作業(yè)一旦被作業(yè)調度選中,該作業(yè)即進入內存D允許多個用戶在各自的終端上同時交互地使用計算機的系統(tǒng)稱為分時操作系統(tǒng)E提交多選題1分3、

調度時間周期（1）長期(long-term)：將進程投入“允許執(zhí)行”進程緩沖池中，或送到“退出”進程緩沖池中。進程狀態(tài)：New

Readysuspend,Running

Exit,它將控制多道程序的程度，執(zhí)行頻率相對較低。4.1分級調度3、

調度時間周期（2）中期(medium-term)：將進程的部分或全部加載到內存中。進程狀態(tài)：Ready

Readysuspend,Blocked

Blockedsuspend。4.1分級調度3調度時間周期（3）短期(short-term)：也稱分派程序（dispatcher）選擇哪個進程在處理機上執(zhí)行。進程狀態(tài)：Ready

Running。（4）I/O調度：選擇哪個I/O等待進程，使其請求可以被空閑的I/O設備進行處理。4.1分級調度3調度時間周期用于調度的隊列圖

批作業(yè)CPU釋放短程調度就緒隊列就緒、掛起隊列阻塞、掛起隊列阻塞隊列事件等待事件發(fā)生交互用戶長程調度中程調度4.1分級調度4OS類型劃分調度

（1）批處理調度－－應用場合：大中型主機集中計算，如工程計算、理論計算（流體力學）（2）分時調度、實時調度：通常沒有專門的作業(yè)調度（3）多處理機調度4.1分級調度5作業(yè)與進程的關系（1）作業(yè)是用戶向計算機提交任務的任務實體。（2）進程是計算機為完成用戶任務而設置的執(zhí)行實

體，是系統(tǒng)分配資源的基本單位。（3）一個作業(yè)有多個進程組成4.1分級調度5作業(yè)與進程的關系創(chuàng)建根進程創(chuàng)建子進程為子進程分配資源系統(tǒng)系統(tǒng)或根進程系統(tǒng)或根進程作業(yè)提交時作業(yè)后備狀態(tài)執(zhí)行狀態(tài)完成狀態(tài)4.1分級調度1作業(yè)調度的功能（1）記錄系統(tǒng)中各作業(yè)的狀況系統(tǒng)為每個作業(yè)建立一個JCB記錄作業(yè)信息，系統(tǒng)通過JCB感知作業(yè)的存在。作業(yè)名作業(yè)類型資源要求資源使用情況優(yōu)先級（數(shù)）當前狀態(tài)其它作業(yè)進入后備狀態(tài)時，系統(tǒng)為其建立JCB；作業(yè)進入完成狀態(tài)后，系統(tǒng)撤銷其JCB。4.1分級調度作業(yè)在系統(tǒng)中存在與否的唯一標志是()。源程序A作業(yè)說明書B作業(yè)控制塊C目的程序D提交單選題1分1作業(yè)調度的功能（2）記錄系統(tǒng)中各作業(yè)的狀況作業(yè)名作業(yè)類型資源要求資源使用情況優(yōu)先級（數(shù)）當前狀態(tài)其它用戶提供，系統(tǒng)將其轉換為系統(tǒng)可識別的作業(yè)標識符計算型（CPU時間多）、管理型（I/O量大）、圖形設計型（高速圖形顯示）執(zhí)行時間、內外存量、外設、軟件工具等進入系統(tǒng)/開始執(zhí)行/已執(zhí)行時間、內存地址、外設數(shù)目決定作業(yè)調度順序，用戶給定/系統(tǒng)動態(tài)產(chǎn)生作業(yè)的當前狀態(tài)處于后備狀態(tài)時，可被調度4.1分級調度

1作業(yè)調度的功能（1）記錄系統(tǒng)中各作業(yè)的狀況（2）從后備隊列中選擇一部分作業(yè)投入運行（涉及調度算法）（3）為被選中的作業(yè)做好執(zhí)行前的準備（建立進程、為進程們分配系統(tǒng)資源）（4）作業(yè)執(zhí)行結束時的后處理4.2作業(yè)調度2作業(yè)調度中狀態(tài)的轉換后備作業(yè)隊列空？從中選一作業(yè)審核資源要求資源要求能滿足？分配資源建立進程進程調度否是放棄該作業(yè)否從后備狀態(tài)到執(zhí)行狀態(tài)從執(zhí)行狀態(tài)到完成狀態(tài)回收該作業(yè)占用的資源計算該作業(yè)的執(zhí)行費用撤銷該作業(yè)進程及JCB調度下一個作業(yè)4.2作業(yè)調度3作業(yè)調度目標與性能衡量（1）目標公平性：對所有作業(yè)應該是公平的利用率：應使設備有高的利用率作業(yè)量：每天執(zhí)行盡可能多的作業(yè)響應時間：有快的響應時間4.2作業(yè)調度3作業(yè)調度目標與性能衡量（2）面向用戶的調度性能準則（定量指標）1）周轉時間：作業(yè)從提交到完成所經(jīng)歷的時間。包括：在收容隊列中等待，CPU上執(zhí)行，就緒隊列和阻塞隊列中等待，結果輸出等。主要用在批處理系統(tǒng)中。4.2作業(yè)調度作業(yè)從后備作業(yè)到被調度程序選中的時間稱為()。周轉時間A響應時間B等待調度時間C運行時間D提交單選題1分3作業(yè)調度目標與性能衡量（2）面向用戶的調度性能準則1）周轉時間Ti=作業(yè)完成時刻(Tei)-作業(yè)提交時刻(Tsi)=作業(yè)等待時間(Twi)+作業(yè)執(zhí)行時間(Tri)2）平均周轉時間4.2作業(yè)調度在批處理系統(tǒng)中,周轉時間是（）。作業(yè)運行時間A作業(yè)等待時間和運行時間之和B作業(yè)的相對等待時間C作業(yè)被調度進入內存到運行完畢的時間D提交單選題1分3作業(yè)調度目標與性能衡量（2）

面向用戶的調度性能準則

3）帶權周轉時間帶權周轉時間Wi=Ti/Tri平均帶權周轉時間4.2作業(yè)調度3作業(yè)調度目標與性能衡量（2）

面向系統(tǒng)的調度性能準則吞吐量：單位時間內所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調度算法都有關系，用于批處理系統(tǒng)中。處理機利用率：用于大中型主機。各種設備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時間短）的作業(yè)搭配——大中型主機4.2作業(yè)調度在一個以批處理為主的系統(tǒng)中,為了保證系統(tǒng)的吞吐率,總是要力爭縮短用戶作業(yè)的()。周轉時間A運行時間B提交時間C完成時間D提交單選題1分3作業(yè)調度目標與性能衡量（3）算法本身的調度性能準則易于執(zhí)行執(zhí)行開銷比4.2作業(yè)調度1進程調度的功能（1）記錄所有進程的運行狀況（靜態(tài)和動態(tài)）（2）當進程出讓CPU或調度程序剝奪執(zhí)行狀態(tài)進程占用的CPU時，選擇適當?shù)倪M程分派CPU（3）完成上下文切換4.3進程調度2進程調度的時機（1）正在執(zhí)行的進程執(zhí)行完畢（2）執(zhí)行進程自己調用阻塞原語使自己變?yōu)榈却隣顟B(tài)（3）將睡眠的進程喚醒，將其加入就緒隊列后，執(zhí)行進程調度程序（4）執(zhí)行進程調用P操作，因資源不足被阻塞4.3進程調度2進程調度的時機（5）執(zhí)行進程因I/O被阻塞（6）分時系統(tǒng)中時間片用完（7）系統(tǒng)調用執(zhí)行完畢，從系統(tǒng)程序返回到用戶程序時，進行進程調度（8）可剝奪方式下，就緒隊列中某進程優(yōu)先級高于執(zhí)行進程

4.3進程調度________可能會引起處理機從一個進程轉到另一個進程。一個進程從運行狀態(tài)變?yōu)榈却隣顟B(tài)A一個進程從運行狀態(tài)變?yōu)榫途w狀態(tài)B一個就緒狀態(tài)進程的優(yōu)先級降低C一個進程運行完成而撤離系統(tǒng)D一個就緒狀態(tài)進程的優(yōu)先級升高E提交多選題1分3進程上下文切換（1）進程上下文組成

由正文段、數(shù)據(jù)段、硬件寄存器的內容以及有關數(shù)據(jù)結構組成。4.3進程調度3進程上下文切換（2）

進程上下文切換步驟決定是否切換以及是否允許切換保存當前執(zhí)行進程的上下文應用調度算法選擇一個處于就緒狀態(tài)的進程恢復或裝配所選進程的上下文，將CPU控制權交給所選進程4.3進程調度4進程調度性能評價（1）定性衡量調度的可靠性調度的簡潔性（2）

定量衡量CPU利用率進程在隊列中的等待時間與執(zhí)行時間之比4.3進程調度一個進程處于等待狀態(tài),則該進程所屬的作業(yè)存在于()中。內存A外存B高速緩存C寄存器D提交單選題1分1先來先服務（FCFS)（2）

算法思想按照作業(yè)或進程變?yōu)榫途w狀態(tài)的先后次序，分派CPU；當前作業(yè)或進程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）在作業(yè)或進程喚醒后（如I/O完成），并不立即恢復執(zhí)行，通常等到當前作業(yè)或進程出讓CPU。4.4調度算法（重點）1先來先服務

（2）FCFS特點比較有利于長作業(yè)，而不利于短作業(yè)；有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。4.4調度算法（重點）2短作業(yè)優(yōu)先(SJF,ShortestJobFirst)

對FCFS算法進行了改進，其目標是減少平均周轉時間。（1）

算法思想對預計執(zhí)行時間短的作業(yè)（進程）優(yōu)先分派處理機。通常后來的短作業(yè)不搶先正在執(zhí)行的作業(yè)4.4調度算法（重點）2短作業(yè)優(yōu)先(SJF,ShortestJobFirst)

（2）

優(yōu)點比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業(yè)的等待時間；提高系統(tǒng)的吞吐量。4.4調度算法（重點）

2短作業(yè)優(yōu)先(SJF,ShortestJobFirst)（3）SJF缺點對長作業(yè)非常不利，可能長時間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準確估計作業(yè)（進程）的執(zhí)行時間，從而影響調度性能。4.4調度算法（重點）作業(yè)調度算法中“短作業(yè)優(yōu)先”調度算法使得()。每個作業(yè)的等待時間較短A作業(yè)的平均等待時間最短B系統(tǒng)效率最高C長作業(yè)的等待時間較短D提交單選題1分

2短作業(yè)優(yōu)先(SJF,ShortestJobFirst)

（4）SJF變形最短剩余時間優(yōu)先SRT(ShortestRemainingTime)：允許比當前進程剩余時間更短的進程來搶占最高響應比優(yōu)先HRRN(HighestResponseRatioNext)：是FCFS和SJF的折衷。響應比R=(等待時間+要求執(zhí)行時間)/要求執(zhí)行時間。4.4調度算法（重點）

3最高響應比優(yōu)先（HRN）

（1）

算法思想及計算響應比最高的作業(yè)優(yōu)先啟動；響應比R=作業(yè)周轉時間Ti/作業(yè)處理時間Tri=(作業(yè)處理時間Tri+作業(yè)等待時間Twi

)/作業(yè)處理時間Tri

=1+(作業(yè)等待時間Twi

/作業(yè)處理時間Tri

)。4.4調度算法（重點）3最高響應比優(yōu)先（HRN）（2）

算法評價

該算法是FCFS和SJF的結合，克服了兩種算法的缺點。優(yōu)點:公平，吞吐率大缺點:增加了計算，增加了開銷4.4調度算法（重點）4時間片輪轉算法(RoundRobin)

（1）

與其它算法分析對比FCFS和SJF算法主要用于宏觀調度；時間片輪轉算法主要用于微觀調度。4.4調度算法（重點）

4時間片輪轉算法(RoundRobin)（2）算法設計目標通過時間片輪轉，提高進程并發(fā)性和響應時間特性，從而提高資源利用率4.4調度算法（重點）時間片輪轉法進行進程調度是為了()。多個終端都能得到系統(tǒng)的及時響應A先來先服務B優(yōu)先級較高的進程得到及時響應C需要cpu最短的進程先做D提交單選題1分為了照顧緊迫型作業(yè),應采用()。先來先服務調度算法A短作業(yè)優(yōu)先調度算法B時間片輪轉調度算法C優(yōu)先權調度算法D提交單選題1分4時間片輪轉算法(RoundRobin)（3）算法思想將系統(tǒng)中所有的就緒進程按照FCFS原則，排成一個隊列；每次調度時將CPU分派給隊首進程，讓其執(zhí)行一個時間片；在一個時間片結束時，發(fā)生時鐘中斷；4.4調度算法（重點）

4時間片輪轉算法(RoundRobin)（3）算法思想調度程序據(jù)此暫停當前進程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當前的隊首進程進程可以未使用完一個時間片，就出讓CPU（如阻塞）4.4調度算法（重點）4時間片輪轉算法(RoundRobin)F…DCBACPU阻塞完成超時4.4調度算法（重點）

4時間片輪轉算法(RoundRobin)（4）

時間片長度的確定

1）時間片長度變化的影響過長

退化為FCFS算法，進程在一個時間片內都執(zhí)行完，響應時間長；過短

用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應時間長。4.4調度算法（重點）4時間片輪轉算法(RoundRobin)（4）時間片長度的確定

2）對響應時間的要求T(響應時間)=N(進程數(shù)目)*q(時間片)4.4調度算法（重點）影響時間片輪轉調度算法對進程響應時間的因素有()。內存容量A時間片值的選取B外存容量C交互進程的數(shù)量DIO設備的速度E提交多選題1分下列有關基于時間片的進程調度的敘述中,錯誤的是()。時間片越短,進程切換的次數(shù)越多,系統(tǒng)開銷也越大A當前進程的時間片用完后,該進程狀態(tài)由執(zhí)行態(tài)變?yōu)樽枞麘B(tài)B時鐘中斷發(fā)生后,系統(tǒng)會修改當前進程在時間片內的剩余時間C影響時間片大小的主要因素包括響應時間、系統(tǒng)開銷和進程數(shù)量等。D提交單選題1分5多級隊列算法(Multiple-levelQueue)

本算法引入多個就緒隊列，通過各隊列的區(qū)別對待，達到一個綜合的調度目標4.4調度算法（重點）5多級隊列算法(Multiple-levelQueue)（1）

算法思想根據(jù)作業(yè)或進程的性質或類型的不同，將就緒隊列再分為若干個子隊列；每個作業(yè)固定歸入一個隊列;各隊列的不同處理：不同隊列可有不同的優(yōu)先級、時間片長度、調度策略等。4.4調度算法（重點）5多級隊列算法

(Multiple-levelQueue)4.4調度算法（重點）6優(yōu)先級算法是多級隊列算法的改進，平衡各進程對響應時間的要求。適用于作業(yè)調度和進程調度，可分成搶先式和非搶先式。4.4調度算法（重點）為了照顧緊迫型作業(yè),應采用()。先來服務調度算法A短作業(yè)優(yōu)先調度算法B時間片輪轉調度算法C優(yōu)先權調度算法D提交單選題1分6優(yōu)先級算法

（1）

靜態(tài)優(yōu)先級1）定義：創(chuàng)建進程時就確定，直到進程終止前都不改變。2）評級依據(jù)進程類型（系統(tǒng)進程優(yōu)先級較高）對資源的需求（對CPU和內存需求較少的進程，優(yōu)先級較高）用戶要求4.4調度算法（重點）

6優(yōu)先級算法（2）

動態(tài)優(yōu)先級在創(chuàng)建進程時賦予的優(yōu)先級，在進程運行過程中可以自動改變，以便獲得更好的調度性能。4.4調度算法（重點）6優(yōu)先級算法（2）動態(tài)優(yōu)先級

優(yōu)先級變化案例：在就緒隊列中，等待時間延長則優(yōu)先級提高，保證每個進程都有機會執(zhí)行；進程每執(zhí)行一個時間片，就降低其優(yōu)先級，從而一個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到出讓CPU4.4調度算法（重點）6優(yōu)先級算法（3）動態(tài)優(yōu)先級具體算法1）線性優(yōu)先級調度（SRR,SelfishRoundRobin）是動態(tài)優(yōu)先級算法的一個算法，它通過進程優(yōu)先級的遞增來改進長執(zhí)行時間進程的周轉時間特征4.4調度算法（重點）6優(yōu)先級算法（3）動態(tài)優(yōu)先級具體算法1）線性優(yōu)先級調度算法思想：就緒進程隊列分成兩個。新創(chuàng)建進程隊列：按FCFS方式排成；進程優(yōu)先級按速率a增加享受服務隊列：已得到過時間片服務的進程按FCFS方式排成；進程優(yōu)先級按速率b增加4.4調度算法（重點）6優(yōu)先級算法（3）

動態(tài)優(yōu)先級具體算法1）線性優(yōu)先級調度算法思想新創(chuàng)建進程等待時間的確定：當新創(chuàng)建進程優(yōu)先級與享受服務隊列中最后一個進程優(yōu)先級相同時，轉入享受服務隊列4.4調度算法（重點）

6優(yōu)先級算法（3）動態(tài)優(yōu)先級具體算法1）線性優(yōu)先級調度4.4調度算法（重點）F…DCBACPU阻塞完成享受服務進程隊列IJK…新創(chuàng)建進程隊列6優(yōu)先級算法（3）動態(tài)優(yōu)先級具體算法abTimePrioritySRR算法的優(yōu)先級變化4.4調度算法（重點）6優(yōu)先級算法（4）SRR、FCFS、時間片輪轉算法的關系當b>a>0時，享受服務隊列中永遠只有一個進程；SRR算法退化成FCFS算法；當a>b=0時，SRR算法就是時間片輪轉算法。4.4調度算法（重點）在采用動態(tài)優(yōu)先權的優(yōu)先權調度算法中,如果所有進程都具有相同優(yōu)先權初值,則此時的優(yōu)先權調度算法實際上和()相同。先來先服務調度算法A短作業(yè)優(yōu)先調度算法B時間片輪轉調度算法C長作業(yè)優(yōu)先調度算法D提交單選題1分下列進程調度算法中,()可能會出現(xiàn)進程長期得不到調度的情況。非強占式靜態(tài)優(yōu)先權法A強占式靜態(tài)優(yōu)先權法B時間片輪轉調度算法C非強占式動態(tài)優(yōu)先權法D提交單選題1分7多級反饋隊列算法是時間片輪轉算法和優(yōu)先級算法的綜合和發(fā)展。（1）

優(yōu)點

為提高系統(tǒng)吞吐量和縮短平均周轉時間而照顧短進程；為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程不必估計進程的執(zhí)行時間，動態(tài)調節(jié)4.4調度算法（重點）7多級反饋隊列

（2）算法思想設置多個就緒隊列，分別賦予不同的優(yōu)先級，如逐級降低，隊列1的優(yōu)先級最高。每個隊列執(zhí)行時間片的長度也不同，規(guī)定優(yōu)先級越低則時間片越長，如逐級加倍；4.4調度算法（重點）7多級反饋隊列

（2）算法思想新進程進入內存后，先投入隊列1的末尾，按FCFS算法調度；若在隊列1一個時間片未能執(zhí)行完，則降低投入到隊列2的末尾，同樣按FCFS算法調度；如此下去，降低到最后的隊列，則按“時間片輪轉”算法調度直到完成；4.4調度算法（重點）下列選項中,降低進程優(yōu)先級的合理時機是()。進程的時間片用完A進程剛完成I/O,進入就緒隊列B進程長期處于就緒隊列中C進程從就緒狀態(tài)轉為運行態(tài)D提交單選題1分7多級反饋隊列

（2）算法思想僅當較高優(yōu)先級的隊列為空，才調度較低優(yōu)先級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進程，并把被搶先的進程投入原隊列的末尾。4.4調度算法（重點）

8調度算法性能指標（3）FCFS、RoundRobin和SRR周轉時間比較長作業(yè)時：T(FCFS)<T(SRR)<T(RR)（運行時間是主要因素）；短作業(yè)時：T(RR)<T(SRR)<T(FCFS)（等待時間是主要因素）

。4.4調度算法（重點）1、假設在批處理環(huán)境下有四個作業(yè)，已知它們進入系統(tǒng)的時間、估計運行時間：作業(yè)進入時間估計運行時間（分鐘）JOB18:00120JOB28:5050JOB39:0010JOB49:50204.5調度算法應用舉例要求：

應用先來先服務、最短作業(yè)優(yōu)先和最高響應比優(yōu)先作業(yè)調度算法，分別計算出作業(yè)的平均周轉時間和帶權的平均周轉時間。4.5調度算法應用舉例（考點）答：（1）先來先服務算法計算結果時間8:0010:0010:5011:0011:20J1120J250J310J4204.5調度算法應用舉例（考點）（2）最短作業(yè)優(yōu)先算法計算結果時間8:0010:0010:1010:3011:20J1120J250J310J4204.5調度算法應用舉例（考點）（3）最高響應比算法計算結果時間8:0010:0010:1011:0011:20J1120J250J310J42070+50,60+10,10+2050102080+50,20+20

50204.5調度算法應用舉例（考點）（4）最短作業(yè)優(yōu)先算法執(zhí)行結果4.5調度算法應用舉例（考點）1．在一個多道程序設計系統(tǒng)中，不采用移動技術的可變分區(qū)方式管理內存。設用戶空間為100K，主存空間采用最先適應分配算法，采用計算機時間短的作業(yè)優(yōu)先算法管理作業(yè)。今有如所示的作業(yè)序列，請分別列出各個作業(yè)的開始執(zhí)行時間、完成時間和周轉時間（忽略系統(tǒng)開銷）。作答正常使用主觀題需2.0以上版本雨課堂可為此題添加文本、圖片、公式等解析，且需將內容全部放在本區(qū)域內。正常使用需3.0以上版本此處添加答案解析答案解析答案解析主觀題10分

1實時調度概述（1）實時計算越來越重要，實時調度是實時系統(tǒng)中最重要的組（2）實時系統(tǒng)，如實時控制、過程控制、機器人、遠程通信等；4.6實時調度（Real-TimeScheduling）1實時調度概述（3）實時計算系統(tǒng)的正確性不僅依賴于計算的邏輯結果，而且依賴于產(chǎn)生結果的時間；（4）通常給一個特定的任務制定一個最后期限，最后期限指定開始時間或結束時間。4.6實時調度（Real-TimeScheduling）

2實時調度分類（1）硬實時任務：必須滿足最后期限的限制，否則產(chǎn)生致命的錯誤；（2）軟實時任務：希望滿足最后期限，但并不是強制的，超過期限，調度完成任務仍有意義；4.6實時調度（Real-TimeScheduling）2實時調度分類（3）一個非周期任務（aperiodictask）有一個必須結束或開始的最后期限；（4）周期任務，期限描述為“每隔周期T一次”。4.6實時調度（Real-TimeScheduling）2實時調度的特點（1）要求更詳細的調度信息：如，就緒時間、開始或完成截止時間；（2）采用搶先式調度；4.6實時調度（Real-TimeScheduling）2實時調度的特點（3）快速中斷響應，在中斷處理時（硬件）關中斷的時間盡量短；（4）快速上下文切換：相應地采用較小的調度單位（如線程）。4.6實時調度（Real-TimeScheduling）

3實時調度算法（1）靜態(tài)表驅動調度；（2）靜態(tài)優(yōu)先級驅動的剝奪調度；（3）動態(tài)分析調度算法；（4）無保障動態(tài)調度算法。4.6實時調度（Real-TimeScheduling）3實時調度算法（1）靜態(tài)表驅動調度算法適用于周期性的實時應用；算法的輸入為：到達時間、運行時間、最后結束時間、任務間的優(yōu)先關系；通過對所有周期性任務的輸入信息分析預測，事先確定一個固定的調度方案，使得能夠滿足所有周期性任務的要求；4.6實時調度（Real-TimeScheduling）3實時調度算法（1）靜態(tài)表驅動調度算法特點有效，但不靈活。因為任何任務要求的任何變化都需要重做調度變種：最早最后期限優(yōu)先4.6實時調度（Real-TimeScheduling）3實時調度算法（2）靜態(tài)優(yōu)先級驅動的剝奪調度

把通用的優(yōu)先級調度算法用于實時系統(tǒng)；

優(yōu)先級的確定是通過靜態(tài)分析完成的；

速率單調算法：任務的優(yōu)先級=任務周期的倒數(shù)，即任務速率；優(yōu)先級最高的任務是周期最短