在實(shí)際計(jì)算機(jī)考研和保研面試中調(diào)度算法是操作系統(tǒng)課程的核心考點(diǎn)也是區(qū)分考生對(duì)系統(tǒng)資源管理理解深度的關(guān)鍵。無論是408統(tǒng)考的選擇題、大題還是面試官追問的“為什么用這個(gè)算法它的缺點(diǎn)是什么”如果只停留在背誦“先來先服務(wù)FCFS”、“短作業(yè)優(yōu)先SJF”等名詞上很難拿到高分。真正理解調(diào)度算法需要串聯(lián)起算法思想、性能指標(biāo)、適用場景、優(yōu)缺點(diǎn)對(duì)比以及面對(duì)具體問題時(shí)的選型邏輯。本文將以“一圖流”為線索但不止于一張圖。我們將從調(diào)度算法的基本目標(biāo)出發(fā)逐步拆解各類算法的核心機(jī)制用具體的進(jìn)程序列和甘特圖演示調(diào)度過程計(jì)算關(guān)鍵指標(biāo)如周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間并深入分析算法背后的權(quán)衡。最后我們會(huì)整理出針對(duì)408考研和面試的高頻考點(diǎn)、易錯(cuò)點(diǎn)以及面對(duì)“進(jìn)程調(diào)度”、“磁盤調(diào)度”等不同場景時(shí)的解題思路。目標(biāo)是讓你不僅能應(yīng)對(duì)考題更能建立起清晰的調(diào)度知識(shí)體系。1. 調(diào)度算法的目標(biāo)與性能指標(biāo)先搞清楚要優(yōu)化什么在討論具體算法之前必須明確調(diào)度是為了解決什么問題以及如何衡量一個(gè)調(diào)度算法的好壞。這是所有分析和比較的起點(diǎn)。1.1 調(diào)度器的核心目標(biāo)操作系統(tǒng)的進(jìn)程調(diào)度器負(fù)責(zé)在就緒隊(duì)列中選擇下一個(gè)要占用CPU的進(jìn)程。其設(shè)計(jì)目標(biāo)往往是相互沖突的需要在其中取得平衡公平性確保每個(gè)進(jìn)程都能獲得合理的CPU時(shí)間份額避免“饑餓”。高效性吞吐量使單位時(shí)間內(nèi)完成的進(jìn)程數(shù)量盡可能多。響應(yīng)性響應(yīng)時(shí)間使交互式進(jìn)程如用戶輸入能盡快得到響應(yīng)提升用戶體驗(yàn)。周轉(zhuǎn)時(shí)間使批處理進(jìn)程從提交到完成的總時(shí)間盡可能短。不同的應(yīng)用場景側(cè)重點(diǎn)不同。例如批處理系統(tǒng)如科學(xué)計(jì)算更關(guān)注吞吐量和周轉(zhuǎn)時(shí)間而交互式系統(tǒng)如桌面操作系統(tǒng)則更關(guān)注響應(yīng)時(shí)間。1.2 關(guān)鍵性能指標(biāo)與計(jì)算公式為了量化評(píng)估算法我們使用以下指標(biāo)。理解并熟練計(jì)算這些指標(biāo)是解題的基礎(chǔ)。假設(shè)有n個(gè)進(jìn)程對(duì)于進(jìn)程i提交時(shí)間(Arrival Time): 進(jìn)程進(jìn)入系統(tǒng)/就緒隊(duì)列的時(shí)間。開始時(shí)間(Start Time): 進(jìn)程首次獲得CPU開始執(zhí)行的時(shí)間。完成時(shí)間(Finish Time): 進(jìn)程執(zhí)行結(jié)束的時(shí)間。服務(wù)時(shí)間/運(yùn)行時(shí)間(Burst Time): 進(jìn)程總共需要占用CPU的時(shí)間長度。等待時(shí)間(Waiting Time): 進(jìn)程在就緒隊(duì)列中等待的總時(shí)間。計(jì)算公式等待時(shí)間 周轉(zhuǎn)時(shí)間 - 服務(wù)時(shí)間或等待時(shí)間 開始時(shí)間 - 提交時(shí)間 中間所有等待時(shí)間。周轉(zhuǎn)時(shí)間(Turnaround Time): 從進(jìn)程提交到完成所經(jīng)歷的總時(shí)間。計(jì)算公式周轉(zhuǎn)時(shí)間 完成時(shí)間 - 提交時(shí)間。帶權(quán)周轉(zhuǎn)時(shí)間(Weighted Turnaround Time): 周轉(zhuǎn)時(shí)間與服務(wù)時(shí)間的比值。它衡量了進(jìn)程的相對(duì)等待程度值越小越接近1表示進(jìn)程的等待時(shí)間相對(duì)其運(yùn)行時(shí)間越短用戶體驗(yàn)越好。計(jì)算公式帶權(quán)周轉(zhuǎn)時(shí)間 周轉(zhuǎn)時(shí)間 / 服務(wù)時(shí)間。系統(tǒng)級(jí)指標(biāo)平均周轉(zhuǎn)時(shí)間(Average Turnaround Time): 所有進(jìn)程周轉(zhuǎn)時(shí)間的平均值。平均帶權(quán)周轉(zhuǎn)時(shí)間(Average Weighted Turnaround Time): 所有進(jìn)程帶權(quán)周轉(zhuǎn)時(shí)間的平均值。平均等待時(shí)間(Average Waiting Time): 所有進(jìn)程等待時(shí)間的平均值。吞吐量(Throughput): 單位時(shí)間內(nèi)完成的進(jìn)程數(shù)。注意在計(jì)算時(shí)務(wù)必區(qū)分“提交時(shí)間”和“開始時(shí)間”。許多算法如FCFS的開始時(shí)間并不等于提交時(shí)間因?yàn)榭赡苄枰却懊娴倪M(jìn)程執(zhí)行完。2. 單核CPU進(jìn)程調(diào)度算法詳解我們通過一個(gè)共同的進(jìn)程序列來演示和比較各個(gè)算法。假設(shè)有以下5個(gè)進(jìn)程先后提交按提交順序?yàn)镻1, P2, P3, P4, P5進(jìn)程提交時(shí)間服務(wù)時(shí)間單位msP108P214P329P435P5422.1 先來先服務(wù)FCFS, First-Come, First-Served算法思想按照進(jìn)程進(jìn)入就緒隊(duì)列的先后順序進(jìn)行調(diào)度。這是一種最簡單的非搶占式調(diào)度算法。調(diào)度過程甘特圖時(shí)間軸(ms): 0 8 12 17 26 28 進(jìn)程執(zhí)行: |---P1---|----P2----|----P3----|----P4----|--P5--|0ms時(shí)只有P1到達(dá)開始執(zhí)行運(yùn)行8ms于8ms完成。8ms時(shí)就緒隊(duì)列中有P2(1ms到達(dá))、P3(2ms到達(dá))、P4(3ms到達(dá))、P5(4ms到達(dá))。按到達(dá)順序選擇P2運(yùn)行4ms于12ms完成。后續(xù)依次調(diào)度P3、P4、P5。計(jì)算指標(biāo)進(jìn)程提交時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1080881.00P214812112.75P3291221192.11P4352126234.60P54226282412.00平均周轉(zhuǎn)時(shí)間 (811192324)/5 17.0 ms平均帶權(quán)周轉(zhuǎn)時(shí)間 (1.002.752.114.6012.00)/5 4.49平均等待時(shí)間 ((0)(7)(10)(18)(22))/5 11.4 msP1等待時(shí)間0 P28-17 P312-210 P421-318 P526-422。優(yōu)缺點(diǎn)與適用場景優(yōu)點(diǎn)實(shí)現(xiàn)簡單公平直觀。缺點(diǎn)**護(hù)航效應(yīng)(Convoy Effect)**明顯。短進(jìn)程可能排在長進(jìn)程后面導(dǎo)致平均等待時(shí)間和周轉(zhuǎn)時(shí)間很長性能差。對(duì)交互式系統(tǒng)不友好。適用場景早期批處理系統(tǒng)或作為其他復(fù)雜調(diào)度算法的基礎(chǔ)組件。2.2 短作業(yè)優(yōu)先SJF, Shortest Job First / 短進(jìn)程優(yōu)先SPN算法思想從就緒隊(duì)列中選擇預(yù)計(jì)運(yùn)行時(shí)間最短的進(jìn)程投入運(yùn)行。這是非搶占式的。如果強(qiáng)調(diào)“下次調(diào)度時(shí)選擇”則是非搶占式如果強(qiáng)調(diào)“新進(jìn)程到達(dá)時(shí)若比當(dāng)前進(jìn)程剩余時(shí)間短就搶占”則是搶占式的短剩余時(shí)間優(yōu)先SRTF。調(diào)度過程非搶占SJF0ms: P1到達(dá)唯一開始執(zhí)行。P1執(zhí)行期間(0-8ms)P2(1ms)、P3(2ms)、P4(3ms)、P5(4ms)陸續(xù)到達(dá)。P1完成后8ms就緒隊(duì)列中有P2(4ms)、P3(9ms)、P4(5ms)、P5(2ms)。選擇服務(wù)時(shí)間最短的P5。后續(xù)每次調(diào)度都從當(dāng)前就緒隊(duì)列中選擇服務(wù)時(shí)間最短的進(jìn)程。時(shí)間軸(ms): 0 8 10 14 19 28 進(jìn)程執(zhí)行: |---P1---|--P5--|--P2--|---P4---|----P3----|調(diào)度順序P1 - P5 - P2 - P4 - P3計(jì)算指標(biāo)進(jìn)程提交時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1080881.00P2141014133.25P3291928262.89P4351419163.20P54281063.00平均周轉(zhuǎn)時(shí)間 (81326166)/5 13.8 ms平均帶權(quán)周轉(zhuǎn)時(shí)間 (1.003.252.893.203.00)/5 2.67對(duì)比FCFS平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間都有顯著改善。優(yōu)缺點(diǎn)與適用場景優(yōu)點(diǎn)理論上能給出最小的平均等待時(shí)間/平均周轉(zhuǎn)時(shí)間對(duì)于給定的一組進(jìn)程。缺點(diǎn)需要預(yù)知進(jìn)程的運(yùn)行時(shí)間這在實(shí)際中很難精確做到通常只能預(yù)測?？赡軐?dǎo)致長進(jìn)程饑餓。如果不斷有短進(jìn)程到達(dá)長進(jìn)程可能永遠(yuǎn)得不到調(diào)度。未考慮進(jìn)程的緊急程度。適用場景批處理系統(tǒng)其中作業(yè)的運(yùn)行時(shí)間可以較準(zhǔn)確估計(jì)。2.3 高響應(yīng)比優(yōu)先HRRN, Highest Response Ratio Next算法思想是FCFS和SJF的一種折中屬于非搶占式調(diào)度。它通過計(jì)算進(jìn)程的“響應(yīng)比”來決定調(diào)度順序。響應(yīng)比越高優(yōu)先級(jí)越高。響應(yīng)比 R (等待時(shí)間 服務(wù)時(shí)間) / 服務(wù)時(shí)間 1 等待時(shí)間/服務(wù)時(shí)間公式含義既考慮了作業(yè)的等待時(shí)間防止長作業(yè)饑餓也考慮了作業(yè)的服務(wù)時(shí)間照顧短作業(yè)。短作業(yè)服務(wù)時(shí)間小容易獲得高R值長作業(yè)等待時(shí)間增長后R值也會(huì)變大從而獲得調(diào)度機(jī)會(huì)。調(diào)度過程基于之前的例子0ms: P1開始執(zhí)行。8ms: P1完成。計(jì)算此時(shí)就緒隊(duì)列中P2, P3, P4, P5的響應(yīng)比P2 等待時(shí)間7 R 1 7/4 2.75P3 等待時(shí)間6 R 1 6/9 ≈ 1.67P4 等待時(shí)間5 R 1 5/5 2.00P5 等待時(shí)間4 R 1 4/2 3.00選擇響應(yīng)比最高的P5。10ms: P5完成。計(jì)算剩余進(jìn)程響應(yīng)比P2 等待時(shí)間9 R 1 9/4 3.25P3 等待時(shí)間8 R 1 8/9 ≈ 1.89P4 等待時(shí)間7 R 1 7/5 2.40選擇P2。后續(xù)同理。時(shí)間軸(ms): 0 8 10 14 19 28 進(jìn)程執(zhí)行: |---P1---|--P5--|--P2--|---P4---|----P3----|在這個(gè)特例中調(diào)度順序與SJF相同但原理不同。HRRN通過動(dòng)態(tài)優(yōu)先級(jí)避免了長進(jìn)程饑餓。優(yōu)缺點(diǎn)與適用場景優(yōu)點(diǎn)兼顧了短作業(yè)和等待時(shí)間長的作業(yè)克服了SJF的長作業(yè)饑餓問題。缺點(diǎn)每次調(diào)度前需要計(jì)算所有就緒進(jìn)程的響應(yīng)比增加了開銷。仍需預(yù)知服務(wù)時(shí)間。適用場景對(duì)公平性和吞吐量都有一定要求的批處理系統(tǒng)。2.4 時(shí)間片輪轉(zhuǎn)RR, Round Robin算法思想專為分時(shí)系統(tǒng)設(shè)計(jì)。將CPU時(shí)間劃分為一個(gè)個(gè)時(shí)間片。就緒隊(duì)列中的進(jìn)程按FCFS順序輪流執(zhí)行一個(gè)時(shí)間片。若進(jìn)程在一個(gè)時(shí)間片內(nèi)未完成則被剝奪CPU重新排到就緒隊(duì)列末尾等待下一輪調(diào)度。這是典型的搶占式調(diào)度。調(diào)度過程假設(shè)時(shí)間片q4ms0ms: P1到達(dá)并開始執(zhí)行。4ms: P1已執(zhí)行4ms剩余4ms時(shí)間片到。此時(shí)P2(1ms到達(dá))、P3(2ms到達(dá))、P4(3ms到達(dá))已到達(dá)。P1被放到隊(duì)列末尾。隊(duì)列順序P2, P3, P4, P1。8ms: P2執(zhí)行4ms完成服務(wù)時(shí)間正好4ms。P3開始執(zhí)行。隊(duì)列P4, P1, P3P3剛被搶占。12ms: P3執(zhí)行4ms剩余5ms時(shí)間片到。P4開始執(zhí)行。隊(duì)列P1, P3, P4P4剛被搶占。16ms: P4執(zhí)行4ms剩余1ms時(shí)間片到。P1開始執(zhí)行。隊(duì)列P3, P4, P1P1剛被搶占。20ms: P1執(zhí)行4ms完成剩余0ms。P3開始執(zhí)行。隊(duì)列P4, P3P3剛被搶占。24ms: P3執(zhí)行4ms剩余1ms時(shí)間片到。P4開始執(zhí)行。隊(duì)列P3, P4P4剛被搶占。25ms: P4執(zhí)行1ms完成。P3開始執(zhí)行。28ms: P3執(zhí)行1ms完成。時(shí)間軸(ms): 0 4 8 12 16 20 24 25 28 進(jìn)程執(zhí)行: |-P1-|-P2-|-P3-|-P4-|-P1-|-P3-|-P4-|-P3-|計(jì)算指標(biāo)過程略復(fù)雜關(guān)注等待時(shí)間各進(jìn)程的等待時(shí)間等于其周轉(zhuǎn)時(shí)間減去實(shí)際占用CPU的時(shí)間服務(wù)時(shí)間。由于頻繁切換平均等待時(shí)間通常比FCFS好但周轉(zhuǎn)時(shí)間可能因時(shí)間片設(shè)置不當(dāng)而變差。時(shí)間片大小的影響時(shí)間片極大→∞退化為FCFS。時(shí)間片極小→0上下文切換開銷極大CPU時(shí)間大量浪費(fèi)在進(jìn)程切換上實(shí)際工作效率極低。合理的時(shí)間片通常設(shè)置為略大于一次典型交互所需的時(shí)間如幾十到幾百毫秒使大多數(shù)交互式進(jìn)程能在一個(gè)時(shí)間片內(nèi)完成同時(shí)保持系統(tǒng)的響應(yīng)能力。優(yōu)缺點(diǎn)與適用場景優(yōu)點(diǎn)公平響應(yīng)快適合交互式系統(tǒng)。缺點(diǎn)平均周轉(zhuǎn)時(shí)間通常較長。上下文切換有開銷。適用場景通用分時(shí)操作系統(tǒng)如Linux、Windows的桌面環(huán)境。2.5 多級(jí)反饋隊(duì)列MLFQ, Multilevel Feedback Queue算法思想綜合了多種調(diào)度算法的思想是實(shí)際操作系統(tǒng)如Unix、Windows中常用的調(diào)度算法。其核心規(guī)則是設(shè)置多個(gè)就緒隊(duì)列每個(gè)隊(duì)列擁有不同的優(yōu)先級(jí)和不同的時(shí)間片大小。優(yōu)先級(jí)越高時(shí)間片通常越小。新進(jìn)程進(jìn)入系統(tǒng)時(shí)放入最高優(yōu)先級(jí)隊(duì)列。每個(gè)隊(duì)列內(nèi)部通常采用RR調(diào)度。進(jìn)程用完當(dāng)前隊(duì)列的一個(gè)時(shí)間片后若未完成則被降級(jí)到下一級(jí)優(yōu)先級(jí)隊(duì)列。進(jìn)程因等待I/O事件而主動(dòng)放棄CPU時(shí)可以提升其優(yōu)先級(jí)或重新放入原隊(duì)列以獎(jiǎng)勵(lì)I(lǐng)/O型進(jìn)程。為了防止低優(yōu)先級(jí)隊(duì)列進(jìn)程饑餓可以定期將所有進(jìn)程重新提到最高優(yōu)先級(jí)隊(duì)列或者讓高優(yōu)先級(jí)隊(duì)列在經(jīng)過一段時(shí)間后讓出CPU給低優(yōu)先級(jí)隊(duì)列。調(diào)度過程示例概念性 假設(shè)有3級(jí)隊(duì)列Q1(優(yōu)先級(jí)高q2ms), Q2(中q4ms), Q3(低q8ms)調(diào)度順序?yàn)镼1-Q2-Q3。P1到達(dá)進(jìn)入Q1執(zhí)行2ms后未完成降級(jí)到Q2。在Q2中P1執(zhí)行4ms后仍未完成降級(jí)到Q3。在Q3中P1按FCFS或大時(shí)間片RR執(zhí)行直到完成。期間若有新進(jìn)程P2到達(dá)它進(jìn)入Q1會(huì)搶占正在Q3中運(yùn)行的P1因?yàn)镼1優(yōu)先級(jí)更高。優(yōu)缺點(diǎn)與適用場景優(yōu)點(diǎn)能較好地區(qū)分CPU密集型和I/O密集型進(jìn)程。I/O密集型進(jìn)程通常能在高優(yōu)先級(jí)隊(duì)列的小時(shí)間片內(nèi)完成計(jì)算并進(jìn)入I/O等待從而保持高優(yōu)先級(jí)獲得快速響應(yīng)。對(duì)短作業(yè)友好可能在高層隊(duì)列就完成。對(duì)長作業(yè)也能保證一定的進(jìn)度最終在低層隊(duì)列執(zhí)行。缺點(diǎn)規(guī)則復(fù)雜參數(shù)隊(duì)列數(shù)量、時(shí)間片大小、優(yōu)先級(jí)調(diào)整策略需要精心調(diào)優(yōu)。適用場景通用操作系統(tǒng)能自適應(yīng)多種類型的進(jìn)程。3. 磁盤調(diào)度算法磁盤調(diào)度算法的目標(biāo)是減少磁頭尋道時(shí)間提高磁盤I/O吞吐量。假設(shè)磁頭初始位于100號(hào)磁道請(qǐng)求隊(duì)列為[55, 58, 39, 18, 90, 160, 150, 38, 184]。3.1 先來先服務(wù)FCFS按請(qǐng)求到達(dá)順序服務(wù)。順序100 - 55 - 58 - 39 - 18 - 90 - 160 - 150 - 38 - 184尋道總距離 |100-55||55-58||58-39||39-18||18-90||90-160||160-150||150-38||38-184| 4531921727010112146 498特點(diǎn)簡單公平但效率可能很低磁頭移動(dòng)距離長。3.2 最短尋道時(shí)間優(yōu)先SSTF, Shortest Seek Time First每次選擇離當(dāng)前磁頭位置最近的請(qǐng)求。從100開始最近的請(qǐng)求是90距離10。順序100 - 90從90開始最近的是58距離32和55距離35選58。順序90 - 58從58開始最近的是55距離3。順序58 - 55從55開始最近的是39距離16。順序55 - 39從39開始最近的是38距離1。順序39 - 38從38開始最近的是18距離20。順序38 - 18從18開始最近的是150距離132和160距離142選150。順序18 - 150從150開始最近的是160距離10。順序150 - 160從160開始最近的是184距離24。順序160 - 184最終順序100 - 90 - 58 - 55 - 39 - 38 - 18 - 150 - 160 - 184尋道總距離 10323161201321024 248特點(diǎn)比FCFS性能好但可能導(dǎo)致“饑餓”。例如如果不斷有請(qǐng)求落在當(dāng)前磁頭附近遠(yuǎn)處的請(qǐng)求可能長期得不到服務(wù)。3.3 掃描算法SCAN電梯算法磁頭向一個(gè)方向移動(dòng)服務(wù)沿途的所有請(qǐng)求直到該方向沒有更多請(qǐng)求然后掉頭。假設(shè)初始方向?yàn)榇诺捞?hào)增加向外。從100開始向外移動(dòng)依次服務(wù)150, 160, 184。到達(dá)最外假設(shè)為199或該方向無請(qǐng)求后掉頭向內(nèi)移動(dòng)依次服務(wù)90, 58, 55, 39, 38, 18。最終順序100 - 150 - 160 - 184 - 90 - 58 - 55 - 39 - 38 - 18尋道總距離 5010249432316120 250特點(diǎn)公平性較好兩端請(qǐng)求的等待時(shí)間差異較大剛離開的方向的請(qǐng)求需要等最久。3.4 循環(huán)掃描算法C-SCANSCAN的變種提供更均勻的等待時(shí)間。磁頭只向一個(gè)方向移動(dòng)如向外服務(wù)沿途請(qǐng)求。到達(dá)終點(diǎn)后立即快速移動(dòng)到另一端起點(diǎn)不服務(wù)請(qǐng)求然后繼續(xù)按原方向移動(dòng)。從100開始向外移動(dòng)服務(wù)150, 160, 184。到達(dá)最外199后快速移動(dòng)到最內(nèi)如0然后繼續(xù)向外服務(wù)18, 38, 39, 55, 58, 90。最終順序100 - 150 - 160 - 184 - (移動(dòng)到0) - 18 - 38 - 39 - 55 - 58 - 90尋道總距離 501024(184-0)1820116332 5010241841820116332 358注意從184到0的移動(dòng)距離是184特點(diǎn)消除了SCAN算法中兩端請(qǐng)求等待時(shí)間的巨大差異對(duì)所有請(qǐng)求的響應(yīng)時(shí)間更均勻。4. 408考研與面試高頻考點(diǎn)及解題思路4.1 選擇題常見陷阱“平均等待時(shí)間最小”的算法理論上非搶占式的SJF/SPN能給出最小的平均等待時(shí)間。但要注意前提是“所有進(jìn)程同時(shí)到達(dá)”或“給定一個(gè)就緒隊(duì)列”。如果進(jìn)程是陸續(xù)到達(dá)的搶占式的SRTF可能更好。時(shí)間片大小的影響時(shí)間片太大→退化為FCFS時(shí)間片太小→上下文切換開銷大。題目?？紝?duì)系統(tǒng)性能響應(yīng)時(shí)間、吞吐量的影響趨勢。饑餓現(xiàn)象SJF/SRTF可能導(dǎo)致長進(jìn)程饑餓SSTF可能導(dǎo)致遠(yuǎn)端磁道請(qǐng)求饑餓。要能識(shí)別出哪種算法在什么場景下會(huì)引起饑餓。調(diào)度算法分類搶占式 vs 非搶占式RR、SRTF、基于優(yōu)先級(jí)的搶占是搶占式FCFS、SJF非搶占、HRRN是非搶占式。搶占式允許操作系統(tǒng)強(qiáng)制收回CPU。適用于批處理 vs 交互式FCFS、SJF、HRRN多用于批處理RR、MLFQ多用于交互式。磁盤調(diào)度算法尋道距離計(jì)算務(wù)必按照算法規(guī)則一步步推導(dǎo)順序再計(jì)算距離。SCAN和C-SCAN要特別注意初始方向和邊界。4.2 大題計(jì)算題解題步驟面對(duì)一道給定了進(jìn)程提交時(shí)間、服務(wù)時(shí)間要求畫出甘特圖并計(jì)算各種平均時(shí)間的題目建議按以下步驟操作確認(rèn)算法類型仔細(xì)讀題明確是FCFS、SJF是否搶占、RR時(shí)間片多大、HRRN中的哪一種。畫出時(shí)間軸從時(shí)間0開始根據(jù)算法規(guī)則確定每個(gè)時(shí)間段由哪個(gè)進(jìn)程執(zhí)行。關(guān)鍵點(diǎn)對(duì)于非搶占算法一個(gè)進(jìn)程開始后除非完成或阻塞否則一直運(yùn)行。對(duì)于RR要嚴(yán)格按時(shí)間片切割和隊(duì)列順序。對(duì)于SJF/HRRN每次調(diào)度點(diǎn)有進(jìn)程完成時(shí)需要重新審視當(dāng)前就緒隊(duì)列中的所有進(jìn)程。填寫進(jìn)程調(diào)度表列出所有進(jìn)程。根據(jù)甘特圖確定每個(gè)進(jìn)程的開始時(shí)間和完成時(shí)間。計(jì)算每個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間完成-提交、帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)/服務(wù)、等待時(shí)間周轉(zhuǎn)-服務(wù) 或 開始-提交中間等待。計(jì)算平均值將所有進(jìn)程的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、等待時(shí)間分別求和再除以進(jìn)程數(shù)。對(duì)比分析如果題目要求比較不同算法可以從平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間、平均等待時(shí)間等指標(biāo)進(jìn)行說明并簡要解釋優(yōu)劣原因。4.3 面試常見問題與回答思路Q: 為什么多級(jí)反饋隊(duì)列調(diào)度算法在實(shí)際操作系統(tǒng)中很常用A: 因?yàn)樗茏赃m應(yīng)多種工作負(fù)載。它通過“降級(jí)”懲罰CPU密集型的長進(jìn)程通過“保持或提升優(yōu)先級(jí)”獎(jiǎng)勵(lì)I(lǐng)/O密集型的交互式進(jìn)程從而在整體上兼顧了響應(yīng)時(shí)間和吞吐量。其多隊(duì)列結(jié)構(gòu)也便于實(shí)現(xiàn)不同優(yōu)先級(jí)的調(diào)度策略。Q: 時(shí)間片輪轉(zhuǎn)算法中時(shí)間片設(shè)置太大或太小會(huì)有什么問題A: 時(shí)間片太大會(huì)退化成FCFS交互式進(jìn)程的響應(yīng)時(shí)間變長。時(shí)間片太小進(jìn)程切換會(huì)非常頻繁大量的CPU時(shí)間浪費(fèi)在保存和恢復(fù)上下文上導(dǎo)致系統(tǒng)吞吐量急劇下降。需要根據(jù)系統(tǒng)負(fù)載和進(jìn)程特點(diǎn)選擇一個(gè)折中的值。Q: 磁盤調(diào)度算法SSTF有什么缺點(diǎn)SCAN如何改進(jìn)它A: SSTF的缺點(diǎn)是可能產(chǎn)生“饑餓”特別是當(dāng)有大量請(qǐng)求集中在磁頭當(dāng)前位置附近時(shí)遠(yuǎn)處的請(qǐng)求可能長期得不到服務(wù)。SCAN電梯算法通過強(qiáng)制磁頭向一個(gè)方向移動(dòng)直到盡頭再回頭保證了所有請(qǐng)求在有限時(shí)間內(nèi)都能被服務(wù)提供了更好的公平性但兩端的請(qǐng)求等待時(shí)間可能較長。Q: 在實(shí)時(shí)操作系統(tǒng)中調(diào)度算法主要考慮什么A: 實(shí)時(shí)系統(tǒng)調(diào)度的核心是保證截止時(shí)間。主要分為兩類硬實(shí)時(shí)必須絕對(duì)滿足截止時(shí)間否則后果嚴(yán)重和軟實(shí)時(shí)盡量滿足偶爾錯(cuò)過可以容忍。常用的有最早截止時(shí)間優(yōu)先EDF和速率單調(diào)調(diào)度RMS。EDF是動(dòng)態(tài)優(yōu)先級(jí)截止時(shí)間越早優(yōu)先級(jí)越高RMS是靜態(tài)優(yōu)先級(jí)周期越短優(yōu)先級(jí)越高。面試官可能會(huì)追問這兩種算法的前提條件和優(yōu)缺點(diǎn)。5. 易錯(cuò)點(diǎn)排查與學(xué)習(xí)建議5.1 常見計(jì)算錯(cuò)誤錯(cuò)誤現(xiàn)象可能原因檢查與糾正方法周轉(zhuǎn)時(shí)間算錯(cuò)混淆了“提交時(shí)間”和“開始時(shí)間”。周轉(zhuǎn)時(shí)間是從提交到完成的總時(shí)間包含了等待時(shí)間。牢記公式周轉(zhuǎn)時(shí)間 完成時(shí)間 - 提交時(shí)間。仔細(xì)從甘特圖上讀取每個(gè)進(jìn)程的完成時(shí)間。等待時(shí)間算錯(cuò)誤以為等待時(shí)間就是“開始時(shí)間-提交時(shí)間”。對(duì)于被搶占的進(jìn)程如RR中間有多次等待。使用最可靠的公式等待時(shí)間 周轉(zhuǎn)時(shí)間 - 服務(wù)時(shí)間?；蛘咦屑?xì)累加進(jìn)程在就緒隊(duì)列中的所有時(shí)間段。RR調(diào)度順序亂時(shí)間片用完時(shí)新到達(dá)的進(jìn)程和剛被剝奪CPU的進(jìn)程誰先入隊(duì)規(guī)則在一個(gè)時(shí)間片結(jié)束時(shí)如果進(jìn)程未完成它會(huì)被放到就緒隊(duì)列末尾。同時(shí)在這個(gè)時(shí)間片內(nèi)新到達(dá)的進(jìn)程也會(huì)按到達(dá)順序排在隊(duì)列末尾。畫圖時(shí)嚴(yán)格按此規(guī)則更新隊(duì)列。SJF/HRRN調(diào)度點(diǎn)遺漏只在0時(shí)刻調(diào)度了一次。關(guān)鍵每次有進(jìn)程完成時(shí)都是一個(gè)調(diào)度點(diǎn)需要重新檢查當(dāng)前就緒隊(duì)列中的所有進(jìn)程根據(jù)算法最短服務(wù)時(shí)間或最高響應(yīng)比選擇下一個(gè)。5.2 學(xué)習(xí)與實(shí)踐建議動(dòng)手畫圖不要只背概念。找?guī)捉M不同的進(jìn)程序列親手畫出FCFS、SJF、RR、HRRN的甘特圖并計(jì)算各項(xiàng)指標(biāo)。這是理解差異最有效的方法。理解本質(zhì)思考每個(gè)算法優(yōu)化了什么犧牲了什么。FCFS追求公平簡單犧牲了效率SJF追求平均時(shí)間最短犧牲了公平和可預(yù)測性RR追求響應(yīng)快犧牲了周轉(zhuǎn)時(shí)間MLFQ追求自適應(yīng)和平衡。聯(lián)系實(shí)際想一想Windows/Linux的任務(wù)管理器為什么前臺(tái)程序響應(yīng)快這背后可能就是優(yōu)先級(jí)調(diào)度或MLFQ在起作用。理解算法如何映射到真實(shí)系統(tǒng)的行為。對(duì)比記憶將進(jìn)程調(diào)度和磁盤調(diào)度算法對(duì)比學(xué)習(xí)。FCFS、SJF(SSTF)的思想是相通的但應(yīng)用場景不同導(dǎo)致細(xì)節(jié)差異。刷題鞏固完成408歷年真題中關(guān)于調(diào)度的所有題目。重點(diǎn)關(guān)注大題的計(jì)算過程并對(duì)照標(biāo)準(zhǔn)答案檢查自己的步驟和結(jié)果。調(diào)度算法不是孤立的知識(shí)點(diǎn)它連接著進(jìn)程管理、I/O系統(tǒng)、系統(tǒng)性能評(píng)估等多個(gè)章節(jié)。通過“一圖流”理清每種算法的執(zhí)行脈絡(luò)再通過計(jì)算和對(duì)比理解其性能特征最后通過真題和模擬題鞏固解題能力就能在考試和面試中牢牢掌握這一重要考點(diǎn)。真正的理解不在于記住一張圖而在于能夠根據(jù)不同的場景和需求推理出調(diào)度行為并評(píng)估其結(jié)果。