操作系統(tǒng)這門課進(jìn)程調(diào)度幾乎是繞不過去的一道坎而課堂練習(xí)3.3往往就是第一次真正讓你坐下來算數(shù)、畫圖、比較算法的那道題。它看起來只是幾行表格加幾個時間數(shù)字實(shí)際上考的是你對進(jìn)程調(diào)度這件事的整體理解進(jìn)程什么時候被選中、CPU什么時候被讓出去、隊(duì)列里的順序怎么變、一組數(shù)據(jù)算下來誰優(yōu)誰劣。很多同學(xué)卡在這里不是因?yàn)椴粫銣p法而是因?yàn)槟X子里沒有一個清晰的時間軸模型導(dǎo)致每道題都要重新猜一遍規(guī)則。這篇內(nèi)容我想按著“先講清題目在考什么、再把概念和時間量理順、接著手算一遍經(jīng)典算法、最后用代碼把這套邏輯固化下來”的順序展開。適合正在做這道練習(xí)的同學(xué)也適合已經(jīng)學(xué)過但一算就亂的讀者。你會看到完整的推演過程、參數(shù)選擇背后的理由、代碼實(shí)現(xiàn)里幾個容易寫掛的細(xì)節(jié)還有我在做題和寫模擬器時踩過的坑。全文以 Python 模擬為主但核心是思路換成 C、Java 甚至 Excel 手工推演都不影響。1. 這道課堂練習(xí)到底在考什么1.1 把“進(jìn)程調(diào)度”四個字拆開看看到“課堂練習(xí)3.3進(jìn)程的調(diào)度”這個標(biāo)題第一反應(yīng)不應(yīng)該是去找公式而是先問自己調(diào)度這件事到底在調(diào)什么答案是把有限的 CPU 時間分配給多個都想要 CPU 的進(jìn)程。一旦接受了這個前提問題就變成三個必須回答的點(diǎn)誰來排就緒隊(duì)列的組織方式、按什么規(guī)則排調(diào)度算法、什么時候重新排調(diào)度時機(jī)。這三件事只要有一件沒想清楚整道題的結(jié)果就是錯的。課堂練習(xí)之所以把它單獨(dú)拎出來是因?yàn)樗瑫r踩中了兩條主線一條是數(shù)據(jù)結(jié)構(gòu)的應(yīng)用隊(duì)列、優(yōu)先隊(duì)列另一條是操作系統(tǒng)的核心機(jī)制進(jìn)程狀態(tài)遷移。很多教材把它放在進(jìn)程管理這一章的中后段前面剛講完 PCB、進(jìn)程狀態(tài)圖、原語后面緊接著就是調(diào)度算法這個位置絕不是隨便放的。它要你做的是把這些散點(diǎn)串成一條能跑起來的時間線。所以拿到題目第一件事我建議先把題干里的表格抄一遍列出進(jìn)程名、到達(dá)時間、服務(wù)時間有的題叫運(yùn)行時間或 CPU 突發(fā)時間這三列。如果題干還給了優(yōu)先級那就再加一列。抄的過程本身就是一次信息核對很多錯題都源于看錯了某一行的到達(dá)時間或者漏了一個進(jìn)程。別嫌這一步土我做過統(tǒng)計(jì)同一批人里出錯的原因純粹計(jì)算失誤的比例其實(shí)低于看錯數(shù)據(jù)的比例。1.2 老師為什么偏偏在這里設(shè)卡調(diào)度是操作系統(tǒng)的分岔路口進(jìn)程調(diào)度之所以成為設(shè)卡點(diǎn)是因?yàn)樗且粋€典型的“多條路都能走但結(jié)果差很多”的問題。同一個進(jìn)程集合用 FCFS 算出來的平均周轉(zhuǎn)時間可能是 11.8用 SJF 可能降到 9.6用時間片輪轉(zhuǎn)又可能反彈回 13 以上。這組數(shù)字的落差會逼著你思考為什么短作業(yè)優(yōu)先看起來更“聰明”為什么時間片輪轉(zhuǎn)反而變差了它真的差嗎這里其實(shí)藏著一個很重要的認(rèn)知評價(jià)指標(biāo)不同最優(yōu)算法就不同。SJF 在平均等待時間上表現(xiàn)優(yōu)秀但它對長作業(yè)不公平長作業(yè)可能一直排在后面。時間片輪轉(zhuǎn)的平均周轉(zhuǎn)時間看起來不占優(yōu)但它保證每個進(jìn)程都能在有限時間內(nèi)拿到 CPU響應(yīng)更均等。老師出這道題的真正意圖是讓你體會到“沒有免費(fèi)的午餐”每種調(diào)度策略都是在對某類指標(biāo)做優(yōu)化同時犧牲另一類指標(biāo)。理解了這一層你在答題時就不會只盯著一個平均數(shù)字下結(jié)論。我見過不少同學(xué)算出 SJF 平均周轉(zhuǎn)最小就直接寫“SJF 是最好的算法”這種結(jié)論在考試?yán)锖苋菀妆豢鄯忠驗(yàn)樗雎粤藢﹂L作業(yè)的公平性和實(shí)現(xiàn)成本。正確的表述應(yīng)該是“在給定指標(biāo)下 SJF 更優(yōu)但它需要預(yù)知服務(wù)時間且對長作業(yè)不利”。這句話是加分的。1.3 動手前的準(zhǔn)備一張表把參數(shù)對齊真正開始算之前我習(xí)慣先做一張“參數(shù)對齊表”把每個進(jìn)程的關(guān)鍵信息固定下來。以一道常見的五進(jìn)程題目為例進(jìn)程到達(dá)時間服務(wù)時間優(yōu)先級數(shù)字越小越高P1053P2131P3284P4322P5445這張表的作用是后續(xù)所有推演的唯一數(shù)據(jù)來源。我會在草稿紙旁邊留出一塊空白專門畫時間軸標(biāo)出 0、1、2、3……每個整數(shù)時刻上發(fā)生了什么誰到達(dá)了、誰被選中、誰運(yùn)行完。這個習(xí)慣能極大降低“算了后面忘了前面”的概率。對齊數(shù)據(jù)時有兩個細(xì)節(jié)特別容易忽略。第一是到達(dá)時間的邊界到達(dá)時間等于當(dāng)前時刻的進(jìn)程算不算已經(jīng)就緒絕大多數(shù)教材的約定是“到達(dá)時間 ≤ 當(dāng)前時刻”即視為就緒也就是說 t2 到達(dá)的 P3在 t2 這一刻就可以被調(diào)度。第二是同時到達(dá)的處理如果有兩個進(jìn)程在同一時刻到達(dá)題干通常會補(bǔ)充“按進(jìn)程號順序”或者“按先來先服務(wù)”如果沒有說明我一般按進(jìn)程編號小的優(yōu)先并在答題時注明這個假設(shè)——寫清假設(shè)本身就是一種嚴(yán)謹(jǐn)。2. 概念不清就必錯先把三個時間量徹底理順2.1 PCB、進(jìn)程狀態(tài)和調(diào)度隊(duì)列之間的關(guān)系調(diào)度的對象不是一段代碼而是一個 PCB進(jìn)程控制塊。教材里那張狀態(tài)遷移圖三個基本狀態(tài)是就緒、運(yùn)行、阻塞調(diào)度器真正操作的是就緒隊(duì)列從里面挑一個讓它從就緒態(tài)變成運(yùn)行態(tài)當(dāng)它時間片用完或者被更高優(yōu)先級搶占又從運(yùn)行態(tài)退回就緒態(tài)重新進(jìn)入隊(duì)列。這個過程反復(fù)發(fā)生就構(gòu)成了整個調(diào)度的動態(tài)畫面。把這個畫面記住很多題目里的“坑”就自動失效了。比如有一類題會問“進(jìn)程在等待 I/O 時會不會被調(diào)度”答案是不會因?yàn)樗谧枞麘B(tài)根本不在就緒隊(duì)列里。再比如“時間片用完的進(jìn)程去了哪里”答案是回到就緒隊(duì)列尾部在時間片輪轉(zhuǎn)里而不是直接結(jié)束。這些判斷都依賴于你腦子里那幅狀態(tài)遷移圖是否清晰。我在做題時會在草稿紙角落畫一個小三角就緒、運(yùn)行、阻塞然后用箭頭標(biāo)注每次調(diào)度對應(yīng)的遷移。這個動作看起來多余但當(dāng)題目有六七個進(jìn)程、頻繁切換時它能幫你避免把“阻塞”和“就緒”混為一談。尤其是涉及 I/O 的題一個進(jìn)程可能多次進(jìn)出就緒隊(duì)列沒有這張小圖很容易亂。2.2 周轉(zhuǎn)時間、等待時間、帶權(quán)周轉(zhuǎn)時間的算法與記憶法這三個時間量是進(jìn)程調(diào)度練習(xí)的評分核心公式本身很簡單但一混就全錯。我把它拆成一句話記憶周轉(zhuǎn)看頭尾等待扣掉跑的時間帶權(quán)就是周轉(zhuǎn)除以服務(wù)。周轉(zhuǎn)時間 完成時間 ? 到達(dá)時間。它衡量的是從進(jìn)程到達(dá)到它徹底做完一共花了多久包含了它排隊(duì)的全部時間。等待時間 周轉(zhuǎn)時間 ? 服務(wù)時間。它衡量的是這個進(jìn)程在就緒隊(duì)列里干等了多久因?yàn)檎嬲加?CPU 的那部分時間是服務(wù)時間不算等待。帶權(quán)周轉(zhuǎn)時間 周轉(zhuǎn)時間 ÷ 服務(wù)時間它是把周轉(zhuǎn)時間按作業(yè)大小“歸一化”后的結(jié)果。帶權(quán)周轉(zhuǎn)時間為什么要引入因?yàn)閱渭兊闹苻D(zhuǎn)時間對長作業(yè)不公平。一個服務(wù)時間為 20 的進(jìn)程周轉(zhuǎn) 24看起來很久但相對它自身的規(guī)模只多等了 20%一個服務(wù)時間為 1 的進(jìn)程周轉(zhuǎn) 5絕對數(shù)字不大但它是自身規(guī)模的 5 倍用戶體驗(yàn)極差。帶權(quán)周轉(zhuǎn)時間把這種“相對感受”量化了所以平均帶權(quán)周轉(zhuǎn)時間比平均周轉(zhuǎn)時間更能反映調(diào)度對不同規(guī)模作業(yè)的影響。計(jì)算時最容易錯的地方有兩個。一是CPU 空閑時間段的處理如果某個時刻沒有進(jìn)程就緒CPU 是空閑的下一