核心算法復(fù)試考點(diǎn)全梳理：調(diào)度、頁面置換與死鎖)
考研復(fù)試操作系統(tǒng)算法這東西說難也難說簡單也簡單。難是因為它橫跨了并發(fā)、調(diào)度、內(nèi)存、文件系統(tǒng)、死鎖五座大山每座山里都蹲著幾個繞不開的經(jīng)典問題簡單是因為復(fù)試考來考去就那么幾十道題出題人繞不開那些“祖宗級”的經(jīng)典場景。我當(dāng)年備考時最深的感觸是算法總結(jié)做得越早后期越穩(wěn)。現(xiàn)在回頭看復(fù)試?yán)锊僮飨到y(tǒng)算法題基本上就分成兩大類——一類是要“會算”的比如調(diào)度算法的周轉(zhuǎn)時間、銀行家算法的安全性檢查、頁面置換的缺頁次數(shù)另一類是要“會寫”的比如信號量同步、LRU淘汰策略、生產(chǎn)者消費(fèi)者模型。這篇文章就把這兩條線的核心考點(diǎn)整理成一份可以直接拿來背、拿來練的總結(jié)覆蓋從必背模板到考場踩坑的完整鏈路無論是機(jī)試還是面試都能用上。1. 復(fù)試備考的優(yōu)先級判斷哪些算法必須手撕哪些“看懂了就行”1.1 機(jī)試和面試的考察方式差異先把話說在前面不同學(xué)校對操作系統(tǒng)的考察方式差異非常大。有的學(xué)校機(jī)試只考數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)放在面試環(huán)節(jié)口頭問有的學(xué)校機(jī)試?yán)锞陀幸坏馈澳M銀行家算法”或者“實現(xiàn)LRU頁面置換”的大題還有的學(xué)校直接發(fā)一張卷子讓你手寫代碼。所以復(fù)習(xí)之前第一件事是搞清楚目標(biāo)院校的復(fù)試形式別把精力用錯地方。從我接觸到的歷年情況來看面試?yán)锏牟僮飨到y(tǒng)算法題一般分三個層級概念層問你“什么是饑餓”“什么是抖動”“LRU和FIFO的區(qū)別”這類題不需要寫代碼但需要用語言把邏輯講清楚。計算層給你一組進(jìn)程或頁面訪問序列讓你算平均周轉(zhuǎn)時間、缺頁次數(shù)。這類題在面試中經(jīng)常以“紙筆演算”的形式出現(xiàn)有時候面試官會隔著屏幕讓你一步一步說過程。手撕層給你一個場景讓你直接寫代碼或者偽代碼。最常見的是信號量同步生產(chǎn)者消費(fèi)者、LRU緩存、銀行家算法安全性檢測。這三個層級的復(fù)習(xí)策略完全不同。概念層靠背誦框架計算層靠刷真題練手算速度和準(zhǔn)確率手撕層則需要真正敲代碼不能只看不練。我見過不少同學(xué)把“看懂了”當(dāng)成“會了”結(jié)果機(jī)試上手就卡殼這種教訓(xùn)太常見了。1.2 算法掌握程度分檔表結(jié)合復(fù)試實際考察頻率和難度我把操作系統(tǒng)里的核心算法分成了三檔備考時可以按這個優(yōu)先級分配時間檔次算法或問題掌握要求常見考察形式第一檔必須能手撕生產(chǎn)者-消費(fèi)者模型、信號量P/V操作、LRU頁面置換、銀行家算法安全性檢查能獨(dú)立寫出完整代碼或偽代碼并能解釋每一步含義機(jī)試編程題、面試手寫代碼第二檔必須會算FCFS、SJF、RR調(diào)度、SPF、頁面置換OPT/FIFO/LRU/Clock、磁盤SSTF/SCAN/C-SCAN給定數(shù)據(jù)能快速手算結(jié)果且過程表達(dá)清晰筆試填空題、面試口述計算過程第三檔理解即可動態(tài)分區(qū)分配算法FF/BF/WF、段頁式地址轉(zhuǎn)換、文件系統(tǒng)索引結(jié)構(gòu)、磁盤RAID能說清核心思想、優(yōu)缺點(diǎn)、適用場景面試概念問答這里給一個非常實用的建議第一檔的算法不要只準(zhǔn)備一種實現(xiàn)方式。比如生產(chǎn)者-消費(fèi)者模型至少要能寫出信號量版本如果時間充裕再把條件變量版本也準(zhǔn)備一下因為面試官經(jīng)常會追問“還有沒有別的寫法”。LRU也是光會說“用哈希表加雙向鏈表”不夠得能真的寫出來后面我會單開一節(jié)講代碼實現(xiàn)。2. 并發(fā)與同步經(jīng)典題生產(chǎn)者-消費(fèi)者、讀者-寫者、哲學(xué)家就餐的代碼重點(diǎn)2.1 生產(chǎn)者-消費(fèi)者信號量的核心模板生產(chǎn)者-消費(fèi)者問題是復(fù)試中出現(xiàn)頻率最高的操作系統(tǒng)算法題沒有之一。它包含兩個核心要素互斥訪問緩沖區(qū)、同步協(xié)調(diào)生產(chǎn)與消費(fèi)的節(jié)奏。對應(yīng)到信號量上就是經(jīng)典的“三個信號量”模型mutex管互斥empty記錄空位full記錄滿位。下面這個版本是復(fù)試中最好用的通用模板用類C語言寫的偽代碼機(jī)試時改造成具體語言也非常方便#define N 100 // 緩沖區(qū)大小 semaphore mutex 1; // 互斥信號量 semaphore empty N; // 空閑緩沖區(qū)數(shù)量 semaphore full 0; // 已占用緩沖區(qū)數(shù)量 void producer() { while (1) { // 生產(chǎn)一個產(chǎn)品放入 nextp P(empty); // 申請一個空閑緩沖區(qū) P(mutex); // 進(jìn)入臨界區(qū) // 將 nextp 放入緩沖區(qū) buffer V(mutex); // 退出臨界區(qū) V(full); // 已占用緩沖區(qū)數(shù)量加1 } } void consumer() { while (1) { P(full); // 申請一個已占用緩沖區(qū) P(mutex); // 進(jìn)入臨界區(qū) // 從緩沖區(qū)取出一個產(chǎn)品 V(mutex); // 退出臨界區(qū) V(empty); // 空閑緩沖區(qū)數(shù)量加1 // 消費(fèi)產(chǎn)品 } }這段代碼有幾個地方是面試官最愛追問的提前準(zhǔn)備好答案為什么P(empty)和P(full)一定要放在P(mutex)外面如果反過來先加互斥鎖再檢查資源數(shù)量一旦緩沖區(qū)滿或空持有mutex的進(jìn)程就會在P(empty)或P(full)上阻塞而其他進(jìn)程又進(jìn)不了臨界區(qū)釋放資源這就造成了死鎖。這個點(diǎn)幾乎每次面試都會問到務(wù)必要能講清。P/V操作必須成對出現(xiàn)但不一定在同一進(jìn)程內(nèi)。P(empty)和V(empty)分別出現(xiàn)在生產(chǎn)者和消費(fèi)者中是通過資源共享實現(xiàn)同步的關(guān)鍵。很多初學(xué)者會誤以為信號量操作只能在一個進(jìn)程內(nèi)配對這是一個常見的理解誤區(qū)。機(jī)試時如果用C語言寫需要注意semaphore在C語言里沒有現(xiàn)成類型通常用sem_t如果允許用Python可以直接用threading.Semaphore邏輯和上面完全一致。但我個人的建議是復(fù)試機(jī)試盡量用C語言準(zhǔn)備因為很多學(xué)校的判題環(huán)境對Python多線程支持并不友好。2.2 讀者-寫者讀寫鎖的思想和代碼讀者-寫者問題考察的是對“讀寫鎖”思想的理解。核心規(guī)則是多個讀者可以同時讀寫者必須獨(dú)占讀者和寫者不能同時操作。復(fù)試中最?？嫉陌姹臼恰白x者優(yōu)先”也就是只要有讀者在讀后來的讀者可以無條件進(jìn)入寫者必須等待所有讀者退出。用信號量實現(xiàn)的經(jīng)典代碼如下semaphore rw_mutex 1; // 控制寫者互斥 semaphore mutex 1; // 保護(hù)讀者計數(shù) int read_count 0; // 當(dāng)前讀者數(shù)量 void reader() { while (1) { P(mutex); read_count; if (read_count 1) P(rw_mutex); // 第一個讀者加鎖阻止寫者 V(mutex); // 執(zhí)行讀操作 P(mutex); read_count--; if (read_count 0) V(rw_mutex); // 最后一個讀者解鎖允許寫者 V(mutex); } } void writer() { while (1) { P(rw_mutex); // 執(zhí)行寫操作 V(rw_mutex); } }這段代碼的邏輯核心在于只有第一個讀者和最后一個讀者才需要操作rw_mutex中間的讀者只是增減計數(shù)不需要碰寫者鎖。這個設(shè)計精妙在把“一個寫者對比多個讀者”的互斥關(guān)系通過讀者計數(shù)轉(zhuǎn)換成了“是否有人正在讀”的布爾判斷。面試追問一般有兩個方向一是“這個版本有什么問題”答案是寫者可能被餓死因為只要讀者源源不斷地來寫者就永遠(yuǎn)等不到鎖二是“如何實現(xiàn)寫者優(yōu)先”標(biāo)準(zhǔn)做法是增加一個write_mutex讓寫者排隊優(yōu)先這會復(fù)雜一些但如果能答出來是很加分的表現(xiàn)。2.3 哲學(xué)家就餐與吸煙者問題死鎖避免思路哲學(xué)家就餐問題在復(fù)試中更多是以“問思路”的形式出現(xiàn)而不是要求完整寫代碼。它的經(jīng)典死鎖場景是五個哲學(xué)家同時拿起左邊的叉子導(dǎo)致所有人都無法拿到右邊的叉子。解決思路通常有三個最多允許四位哲學(xué)家同時就餐設(shè)置一個計數(shù)信號量room 4這樣至少有一位哲學(xué)家能拿到兩把叉子吃完后釋放打破循環(huán)等待。要求哲學(xué)家先拿編號較小的叉子給叉子按序編號每人先拿小號再拿大號破壞“循環(huán)等待”條件。借助互斥鎖保證拿叉子動作的原子性取叉子時加鎖這樣不會出現(xiàn)“每人拿一把”的中間狀態(tài)。我建議復(fù)試時重點(diǎn)準(zhǔn)備第一種方案因為它最簡單三句話就能說明白引入一個信號量限制同時就餐人數(shù)為4人死鎖就不會發(fā)生?；卮饡r補(bǔ)一句“這只是破壞死鎖條件中循環(huán)等待的一種方式”會讓面試官覺得你不是死記答案而是真的理解了死鎖成因。吸煙者問題和哲學(xué)家問題類似考察的是三個進(jìn)程與三種資源的匹配關(guān)系思路也是“用互斥信號量保護(hù)資源分配過程”一般面試?yán)锍霈F(xiàn)頻率不高但概率論上有一個“P/V操作描述吸煙者”的經(jīng)典題目建議還是把代碼過一遍。3. 調(diào)度算法與計算題平均周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間怎么算3.1 FCFS、SJF、RR、優(yōu)先級、多級反饋隊列處理機(jī)調(diào)度這塊復(fù)試筆試的計算題占了很大的比重。本科課程和復(fù)試參考書里最常出現(xiàn)的算法有五種先來先服務(wù)FCFS、短作業(yè)優(yōu)先SJF分為搶占式和非搶占式、時間片輪轉(zhuǎn)RR、優(yōu)先級調(diào)度、多級反饋隊列MLFQ。需要明確的是實際復(fù)試題目里“短作業(yè)優(yōu)先”和“短進(jìn)程優(yōu)先”混用的情況很常見計算時都按“運(yùn)行時間短的先執(zhí)行”來處理。而時間片輪轉(zhuǎn)關(guān)鍵的考點(diǎn)是時間片大小的選擇時間片太大就退化成FCFS時間片太小則上下文切換開銷占比過高?；卮疬@類問題時試著用“極端化假設(shè)”來證明思路——把時間片設(shè)成無限大和設(shè)成無限小分別看效果這個推演過程本身就是面試官想聽的。優(yōu)先級調(diào)度需要額外注意“饑餓”問題低優(yōu)先級進(jìn)程可能永遠(yuǎn)無法運(yùn)行。解決方案是老化Aging——隨著等待時間增長逐步提升優(yōu)先級看過的同學(xué)都知道這是《現(xiàn)代操作系統(tǒng)》里的經(jīng)典解法答出來非常加分。多級反饋隊列這個算法在復(fù)試中常以概念題出現(xiàn)它的核心是“優(yōu)先級高的隊列時間片小用完降級新的高優(yōu)先級任務(wù)可以搶占”。最好準(zhǔn)備一個三步描述建立多個不同時間片的隊列、新任務(wù)進(jìn)入最高優(yōu)先級隊列、任務(wù)時間片用完未結(jié)束則降級。這三點(diǎn)說全基本上就拿到分了。3.2 一個完整的計算示例計算題只看概念是不夠的我直接給出一個完整的例子這是復(fù)試?yán)锓浅５湫偷念}目建議自己動手算一遍有四個進(jìn)程 A、B、C、D到達(dá)時間分別為 0、1、2、3運(yùn)行時間分別為 5、3、2、1。分別計算非搶占式 SJF 和時間片為 2 的 RR 調(diào)度的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。非搶占式 SJF調(diào)度順序推導(dǎo)時刻 0 只有 A 到達(dá)A 運(yùn)行5個時間單位到時刻5。此時 B、C、D 都已到達(dá)運(yùn)行時間分別為 3、2、1按短作業(yè)優(yōu)先排序為 D1、C2、B3。所以執(zhí)行順序是 A → D → C → B。A完成時間5周轉(zhuǎn)時間 5-05帶權(quán)周轉(zhuǎn)時間 5/51D完成時間6周轉(zhuǎn)時間 6-33帶權(quán)周轉(zhuǎn)時間 3/13C完成時間8周轉(zhuǎn)時間 8-26帶權(quán)周轉(zhuǎn)時間 6/23B完成時間11周轉(zhuǎn)時間 11-110帶權(quán)周轉(zhuǎn)時間 10/3≈3.33平均周轉(zhuǎn)時間 (53610)/4 6平均帶權(quán)周轉(zhuǎn)時間 (1333.33)/4 ≈ 2.58。時間片為 2 的 RR 調(diào)度用甘特圖推演時刻0 A開始用掉2剩余3時刻2 B進(jìn)入運(yùn)行到4B剩余1時刻4 C進(jìn)入運(yùn)行到6C完成時刻6 D進(jìn)入運(yùn)行到7D完成時刻7 A恢復(fù)運(yùn)行到9A剩余1時刻9 B進(jìn)入運(yùn)行到10B完成時刻10 A進(jìn)入運(yùn)行到11A完成。A完成11周轉(zhuǎn)時間11B完成10周轉(zhuǎn)時間9C完成6周轉(zhuǎn)時間4D完成7周轉(zhuǎn)時間4平均周轉(zhuǎn)時間 (11944)/4 7。對比可以發(fā)現(xiàn)這個例子里 RR 的平均周轉(zhuǎn)時間比 SJF 差這說明在已知運(yùn)行時間的前提下SJF 的周轉(zhuǎn)時間確實有優(yōu)勢RR 的優(yōu)勢在響應(yīng)時間而非周轉(zhuǎn)時間。提示計算周轉(zhuǎn)時間尤其是 RR 調(diào)度一定要畫甘特圖或者時間軸心算非常容易漏恢復(fù)執(zhí)行的時間片。我見過太多考生在這道題上因為少算了最后一段恢復(fù)執(zhí)行而丟分。3.3 面試追問如何證明SJF最優(yōu)關(guān)于 SJF 的最優(yōu)性正確的說法是在非搶占式調(diào)度中SJF 能使平均等待時間最小。證明思路很經(jīng)典用交換論證法假設(shè)調(diào)度序列中存在兩個相鄰進(jìn)程前一個運(yùn)行時間更長而后一個更短交換它們的執(zhí)行順序前者的等待時間減少量大于后者的等待時間增加量因此總體平均等待時間下降。反復(fù)交換直到任意相鄰位置都滿足“短作業(yè)在前”的規(guī)則就是 SJF 的順序。這個證明過程復(fù)試時不需要寫得很長用兩三句話說清“交換相鄰兩項后總等待時間減少”就夠了。但這句話說得好不好直接決定了面試官對這一問的印象分——因為十個考生里八個都在背結(jié)論只有真正理解的人能把“為什么”講明白。4. 內(nèi)存管理分區(qū)分配、頁面置換算法和LRU手寫實現(xiàn)4.1 動態(tài)分區(qū)分配算法對比內(nèi)存管理在復(fù)試筆試中?？嫉氖莿討B(tài)分區(qū)分配算法首次適應(yīng)FF、最佳適應(yīng)BF、最差適應(yīng)WF、循環(huán)首次適應(yīng)NF。別看名字多抓住一個核心維度就全記住了——空閑分區(qū)按什么順序組織、找什么樣的空閑區(qū)。我在復(fù)習(xí)的時候做過一個對比表基本上一張表就能把這幾個算法記牢算法空閑分區(qū)排列方式分配策略優(yōu)點(diǎn)缺點(diǎn)首次適應(yīng)FF按地址遞增找到第一個夠大的就分配地址利用率高、簡單低地址容易產(chǎn)生大量碎片循環(huán)首次適應(yīng)NF按地址遞增且每次從上次位置繼續(xù)找從上次查找位置開始找第一個夠大的分配更均勻避免頻繁掃描可能降低內(nèi)存利用率最佳適應(yīng)BF按容量遞增找最小的夠用分區(qū)保留大塊內(nèi)存產(chǎn)生大量難以利用的小碎片最差適應(yīng)WF按容量遞減找最大的分區(qū)分配碎片較小大分區(qū)被快速切割耗盡面試中這個知識點(diǎn)的追問方向一般是“為什么最佳適應(yīng)不是真的最佳”——因為從名字上看“最佳”容易讓人誤解但它追求的是“每次留下的碎片最小”而大量小碎片反而導(dǎo)致后續(xù)大請求無法被滿足所以從整體看并不最優(yōu)。這個“名不副實”的點(diǎn)是面試官非常喜歡的陷阱復(fù)習(xí)時一定不要只記名字。4.2 頁面置換算法OPT、FIFO、LRU、Clock頁面置換算法是內(nèi)存管理中最核心的計算題考點(diǎn)。四種算法必須掌握OPT最佳置換淘汰未來最長時間不被訪問的頁面理論最優(yōu)但無法實現(xiàn)只用于對比衡量。FIFO先進(jìn)先出淘汰最早進(jìn)入內(nèi)存的頁面實現(xiàn)簡單但可能出現(xiàn)Belady異?！峙涞奈锢韷K數(shù)增加反而缺頁次數(shù)增加。LRU最近最久未使用淘汰最長時間未被訪問的頁面性能接近OPT實現(xiàn)開銷高。Clock時鐘也稱NRU最近未使用給每個頁面加一個引用位指針掃描遇到引用位為0就淘汰為1則置0并繼續(xù)。本質(zhì)是LRU的近似實現(xiàn)開銷遠(yuǎn)低于真正的LRU。這里特別提醒FIFO和LRU在“分配物理塊數(shù)增加時缺頁次數(shù)是否一定不增加”這個問題上表現(xiàn)不同F(xiàn)IFO可能增加Belady異常LRU不會。這一點(diǎn)復(fù)試筆試中經(jīng)常作為辨析題出現(xiàn)。真題計算示例頁面訪問序列1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5物理塊數(shù)3分別求FIFO和LRU的缺頁次數(shù)。FIFO初始內(nèi)存為空前3次必缺頁。按先進(jìn)先出邏輯推演訪問4時淘汰1訪問5時淘汰2后續(xù)訪問1缺頁淘汰3訪問2缺頁淘汰4訪問3缺頁淘汰5訪問4缺頁淘汰1訪問5缺頁淘汰2?？?cè)表摯螖?shù)9次。LRU前3次同樣缺頁。訪問4時淘汰1因為1最久未用訪問5時淘汰21剛被訪問過變新后續(xù)訪問1缺頁淘汰3訪問2缺頁淘汰4訪問3缺頁淘汰5訪問4缺頁這時候需要看內(nèi)存中當(dāng)前是1、2、3訪問4要淘汰最久未使用的1缺頁1訪問5時淘汰2缺頁1?？?cè)表摯螖?shù)10次。這個例子其實非常經(jīng)典也說明LRU“比FIFO更好”的說法不能一概而論要看具體序列。復(fù)試時如果時間緊張不需要把整個序列都背下來但一定要把計算過程從頭到尾推演一遍熟練掌握“每一步淘汰誰”的判斷規(guī)則。4.3 LRU的代碼實現(xiàn)哈希表加雙向鏈表復(fù)試機(jī)試?yán)風(fēng)RU是出現(xiàn)頻率極高的考題很多學(xué)校會直接考“實現(xiàn)一個LRU緩存”的 LeetCode 原題。標(biāo)準(zhǔn)解法是哈希表 雙向鏈表哈希表保證 O(1) 的查找雙向鏈表保證 O(1) 的節(jié)點(diǎn)移動和刪除。// 雙向鏈表節(jié)點(diǎn) typedef struct Node { int key; int value; struct Node *prev; struct Node *next; } Node; // LRU緩存結(jié)構(gòu) #define CAPACITY 3 Node *head, *tail; Node *hashTable[10000]; // 簡化版直接用數(shù)組當(dāng)哈希表 int cacheSize 0;因為篇幅原因這里給的是最核心的偽代碼框架完整實現(xiàn)并不長大致包括三個操作get時若命中則把節(jié)點(diǎn)移到鏈表頭部put時若已存在則更新值并移到頭部若不存在則插入頭部如果容量已滿則刪除尾部節(jié)點(diǎn)。只要“每次訪問都更新到頭部”“淘汰時刪尾部”這兩條規(guī)則寫對核心邏輯就通了。機(jī)試實際寫的時候有幾個非常容易出錯的細(xì)節(jié)提前避坑雙向鏈表一定要設(shè)置虛擬頭尾節(jié)點(diǎn)否則邊界判斷非常容易出錯導(dǎo)致空鏈表時訪問空指針。哈希表的結(jié)構(gòu)體里不能只存value還必須存key因為淘汰尾部節(jié)點(diǎn)時需要通過哈希表刪除對應(yīng)的鍵如果沒有key字段就刪不掉。這是我當(dāng)年第一版代碼里踩過的坑。Python 實現(xiàn)的collections.OrderedDict也支持 LRU 語義但復(fù)試手撕代碼時反而不建議用因為面試官更想看你對底層結(jié)構(gòu)的理解。5. 死鎖與銀行家算法安全性檢查的完整推理過程5.1 死鎖的四個必要條件與處理策略死鎖這一塊在復(fù)試中幾乎從不缺席。四個必要條件是互斥、持有并等待、不可剝奪、循環(huán)等待。這里有一個非常經(jīng)典的復(fù)習(xí)技巧處理策略和必要條件是一一對應(yīng)的。破壞互斥一般做不到因為有些資源本質(zhì)就是互斥的比如打印機(jī)。破壞持有并等待讓進(jìn)程一次性申請所有資源但資源利用率會下降。破壞不可剝奪允許系統(tǒng)強(qiáng)行搶占但可能導(dǎo)致數(shù)據(jù)不一致。破壞循環(huán)等待給資源編號按序申請這正是哲學(xué)家就餐“先拿小號叉子”方案的原理。復(fù)試題里更?？嫉氖恰八梨i避免”也就是銀行家算法。它與“死鎖預(yù)防”的區(qū)別在于預(yù)防是提前破壞條件避免是運(yùn)行過程中動態(tài)判斷安全性。這個對比最好記在心里因為面試官問完概念大概率會跟一句“那預(yù)防和避免有什么區(qū)別”用一句話說清楚就贏了。5.2 銀行家算法的安全性檢查流程銀行家算法的核心是安全性檢查整個流程可以用四步描述維護(hù)三個數(shù)據(jù)結(jié)構(gòu)Available可用資源向量、Max各進(jìn)程最大需求矩陣、Allocation各進(jìn)程已分配矩陣還需要Need Max - Allocation來表示還需資源。尋找一個進(jìn)程滿足Need[i] Available且未完成則假定它執(zhí)行完并釋放所有資源Available Allocation[i]標(biāo)記該進(jìn)程完成。重復(fù)步驟2直到所有進(jìn)程都能完成則系統(tǒng)處于安全狀態(tài)。如果找不到這樣的進(jìn)程則系統(tǒng)處于不安全狀態(tài)。復(fù)試時銀行家算法最常見的考法是手算安全序列。這里有一個我反復(fù)強(qiáng)調(diào)的提醒一個系統(tǒng)處于安全狀態(tài)則一定不會死鎖但一個系統(tǒng)處于不安全狀態(tài)不代表它一定已經(jīng)死鎖。不安全只是“未來可能進(jìn)入死鎖”因為實際執(zhí)行路徑可能并不會真的走到那一步。這個“可能”字咬得特別緊每年都有考生在這里栽跟頭。5.3 手算題目練習(xí)看一個經(jīng)典的手算題系統(tǒng)有 A、B、C 三類資源Available (3, 3, 2)五個進(jìn)程的 Allocation 和 Need 如下表進(jìn)程AllocationNeedP0(0, 1, 0)(7, 4, 3)P1(2, 0, 0)(1, 2, 2)P2(3, 0, 2)(6, 0, 0)P3(2, 1, 1)(0, 1, 1)P4(0, 0, 2)(4, 3, 1)安全性檢查推導(dǎo)過程初始Available (3, 3, 2)。檢查各進(jìn)程P1 的 Need (1,2,2) (3,3,2)滿足假設(shè) P1 執(zhí)行完釋放資源后Available (3,3,2) (2,0,0) (5,3,2)。當(dāng)前 Available (5,3,2)檢查剩余進(jìn)程P3 的 Need (0,1,1) (5,3,2)滿足P3 執(zhí)行完Available (5,3,2) (2,1,1) (7,4,3)。P0 的 Need (7,4,3) (7,4,3)滿足P0 執(zhí)行完Available (7,4,3) (0,1,0) (7,5,3)。P2 的 Need (6,0,0) (7,5,3)滿足P2 執(zhí)行完Available (7,5,3) (3,0,2) (10,5,5)。P4 的 Need (4,3,1) (10,5,5)滿足全部完成。安全序列P1 → P3 → P0 → P2 → P4系統(tǒng)安全。這個推導(dǎo)過程的書寫規(guī)范在筆試?yán)锓浅Ｓ绊懙梅治医ㄗh每一步都明確寫出“哪個進(jìn)程能執(zhí)行、釋放后 Available 變成多少”不要在心算中省略過程。面試口述時也一樣一步一步說面試官能跟上你的思路這本身就是在展示你思維的嚴(yán)謹(jǐn)性。注意銀行家算法機(jī)試如果要求寫代碼核心就是“反復(fù)掃描進(jìn)程集合直到找不到可分配進(jìn)程”實現(xiàn)時用一個finish[]數(shù)組標(biāo)記已完成進(jìn)程即可復(fù)雜度是 O(n2·m)n 是進(jìn)程數(shù)m 是資源類型數(shù)復(fù)雜度本身也經(jīng)常被問到。6. 磁盤調(diào)度與文件系統(tǒng)算法SSTF、SCAN、CSCAN和索引節(jié)點(diǎn)6.1 磁盤調(diào)度算法對比磁盤調(diào)度考察的頻率在考研復(fù)試?yán)锫缘陀趦?nèi)存和并發(fā)但屬于“不能丟分”的送分題。核心算法是這幾個先來先服務(wù)FCFS、最短尋道時間優(yōu)先SSTF、掃描算法SCAN電梯算法、循環(huán)掃描C-SCAN、LOOK和C-LOOK。SSTF選擇離當(dāng)前磁頭最近的請求平均尋道時間短但遠(yuǎn)端的請求可能被餓死。SCAN讓磁頭沿一個方向移動途中處理所有請求到最遠(yuǎn)端后反向避免了饑餓。C-SCAN則只沿一個方向服務(wù)返回時快速空移這樣兩端請求的等待時間更均勻。LOOB 和 C-LOOK 的區(qū)別是不一定移動到最遠(yuǎn)端點(diǎn)只移動到該方向上最遠(yuǎn)的請求位置就反向效率更高。面試的常見追問是“為什么 C-SCAN 的等待時間比 SCAN 更均勻”——因為 SCAN 在反向后的第一個服務(wù)區(qū)間的請求等待時間可能極短而同一批被服務(wù)過的請求要等一圈不同區(qū)域的請求等待時間差異很大C-SCAN 統(tǒng)一了“從頭掃到尾、快速返回”的模式每圈內(nèi)服務(wù)次序更規(guī)則。計算題一般會給一個當(dāng)前磁道號和請求序列讓算磁頭移動的總磁道數(shù)。這種題就是仔細(xì)加細(xì)心畫出移動路徑就不會錯。磁道序列長的時候推薦用表格記錄當(dāng)前磁道、下一目標(biāo)、移動距離和累計距離防止算到最后一步時對不上數(shù)。6.2 文件系統(tǒng)的常見考點(diǎn)文件系統(tǒng)在算法層面的考試內(nèi)容相對固定主要是索引節(jié)點(diǎn)和目錄結(jié)構(gòu)。復(fù)試高頻考點(diǎn)是連續(xù)分配支持隨機(jī)訪問但會產(chǎn)生外部碎片。鏈接分配消除了外部碎片但只能順序訪問。索引分配每個文件維護(hù)一個索引塊支持隨機(jī)訪問是主流方案。IP 節(jié)點(diǎn)的計算題幾乎是每年必出典型問題如下某文件系統(tǒng)索引節(jié)點(diǎn)中有13個地址項其中10個為直接地址項1個一級間接地址項1個二級間接地址項1個三級間接地址項。磁盤塊大小4KB每個磁盤塊號占4B。求單個文件最大長度。計算步驟一個磁盤塊能存放的地址項數(shù)量 4KB / 4B 1024 個。一級間接能尋址 1024 × 4KB 4MB二級間接 1024 × 4MB 4GB三級間接 1024 × 4GB 4TB。最大文件長度 10 × 4KB 4MB 4GB 4TB約等于 4.04TB。這道題的變形在于地址項數(shù)量和塊號字節(jié)數(shù)會變但思路完全一致。我建議把這個模板記牢考試時直接套數(shù)字就行。文件系統(tǒng)這塊的內(nèi)容不太需要寫代碼主要是計算和理解但它每年都能在復(fù)試卷上占據(jù)10分左右的分值不復(fù)習(xí)等于白送分給別人。7. 復(fù)試現(xiàn)場與機(jī)試備考的經(jīng)驗教訓(xùn)7.1 踩過的坑先講一個很多人都會踩的坑只背不練代碼。操作系統(tǒng)算法不像數(shù)據(jù)結(jié)構(gòu)那樣有直觀的“寫錯就運(yùn)行不起來”的反饋很多同學(xué)把代碼背下來就覺得萬事大吉但復(fù)試時面試官會要求在紙上寫或者機(jī)試環(huán)境下沒有提示和自動補(bǔ)全。我強(qiáng)烈建議復(fù)習(xí)期間把第一檔的算法全部手寫三遍以上寫的過程中你會發(fā)現(xiàn)很多細(xì)節(jié)根本沒記住——比如信號量初始化參數(shù)、讀者寫者里 read_count 是誰在保護(hù)、銀行家算法在哪一步更新 Available。第二個坑是以為公平一定是好的。面試中一旦討論到算法優(yōu)劣不要下意識覺得“不讓任何進(jìn)程餓死好的”。比如10道任務(wù)里有1個需要1秒完成、1個需要100秒完成SJF 可以讓平均等待時間最少但會讓長任務(wù)無限等待。真正的答案是“權(quán)衡”——操作系統(tǒng)算法本質(zhì)上都是 trade-off。用這個詞回答問題面試官會覺得你是有真實理解而非背書。第三個坑是忽略陳述的表達(dá)。復(fù)試不是筆試不是算出正確答案就行。很多計算題面試官會讓你現(xiàn)場口算并說出來如果心里會算但說不清楚很容易被誤判為“半懂”。提前練習(xí)“把計算過程講解給別人聽”這個能力比多刷十道題更有價值。7.2 手撕代碼的考場技巧關(guān)于復(fù)試時手寫代碼我總結(jié)幾個親測有效的經(jīng)驗尤其對考場上容易緊張的同學(xué)特別管用先寫函數(shù)簽名和數(shù)據(jù)結(jié)構(gòu)再寫邏輯。很多考生一上來就埋頭寫核心邏輯寫到一半發(fā)現(xiàn)局部變量沒聲明、函數(shù)參數(shù)沒定好涂涂改改卷面非常難看。先搭框架是減小心理壓力的關(guān)鍵一步。用偽代碼不丟分。面試手寫題很多時候沒有編譯器偽代碼反而能更快把算法思想表達(dá)清楚。只要關(guān)鍵邏輯和變量定義清晰面試官通常不會因為語法細(xì)節(jié)扣分。主動解釋每一步的意圖。寫代碼時邊寫邊說“這里用 mutex 保護(hù)緩沖區(qū)”“這里是第一個讀者才加鎖”既展示了你的邏輯又避免了冷場。大部分面試官對“能講代碼”的考生印象分都很高。如果卡住了先講思路再下手寫。很多時候思路說出來你自己就發(fā)現(xiàn)卡點(diǎn)在哪了而且面試官給的提示也會更精準(zhǔn)。悶頭硬寫是最差的選擇。最后再分享一個小技巧是我自己備考后期一直在用的把第一檔算法做成索引卡片每張卡片只寫題目和關(guān)鍵提示詞比如“生產(chǎn)者消費(fèi)者——三個信號量”“LRU——哈希加雙向鏈表”“銀行家——Available推出安全序列”。每天隨機(jī)抽五張對著卡片在紙上花五分鐘寫完一個算法的骨架。堅持兩周機(jī)試時你會發(fā)現(xiàn)這些代碼就像條件反射一樣自然。復(fù)試說到底是一場“穩(wěn)健性”比拼不是比誰掌握的知識更前沿而是比誰在有限時間和高壓力環(huán)境下能把基礎(chǔ)算法穩(wěn)定輸出出來。把上面這些內(nèi)容踏踏實實過一遍操作系統(tǒng)算法這一關(guān)就沒有過不去的道理。 操作系統(tǒng)核心算法復(fù)試考點(diǎn)全梳理：調(diào)度、頁面置換與死鎖
考研復(fù)試操作系統(tǒng)算法這東西說難也難說簡單也簡單。難是因為它橫跨了并發(fā)、調(diào)度、內(nèi)存、文件系統(tǒng)、死鎖五座大山每座山里都蹲著幾個繞不開的經(jīng)典問題簡單是因為復(fù)試考來考去就那么幾十道題出題人繞不開那些“祖宗級”的經(jīng)典場景。我當(dāng)年備考時最深的感觸是算法總結(jié)做得越早后期越穩(wěn)。現(xiàn)在回頭看復(fù)試?yán)锊僮飨到y(tǒng)算法題基本上就分成兩大類——一類是要“會算”的比如調(diào)度算法的周轉(zhuǎn)時間、銀行家算法的安全性檢查、頁面置換的缺頁次數(shù)另一類是要“會寫”的比如信號量同步、LRU淘汰策略、生產(chǎn)者消費(fèi)者模型。這篇文章就把這兩條線的核心考點(diǎn)整理成一份可以直接拿來背、拿來練的總結(jié)覆蓋從必背模板到考場踩坑的完整鏈路無論是機(jī)試還是面試都能用上。1. 復(fù)試備考的優(yōu)先級判斷哪些算法必須手撕哪些“看懂了就行”1.1 機(jī)試和面試的考察方式差異先把話說在前面不同學(xué)校對操作系統(tǒng)的考察方式差異非常大。有的學(xué)校機(jī)試只考數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)放在面試環(huán)節(jié)口頭問有的學(xué)校機(jī)試?yán)锞陀幸坏馈澳M銀行家算法”或者“實現(xiàn)LRU頁面置換”的大題還有的學(xué)校直接發(fā)一張卷子讓你手寫代碼。所以復(fù)習(xí)之前第一件事是搞清楚目標(biāo)院校的復(fù)試形式別把精力用錯地方。從我接觸到的歷年情況來看面試?yán)锏牟僮飨到y(tǒng)算法題一般分三個層級概念層問你“什么是饑餓”“什么是抖動”“LRU和FIFO的區(qū)別”這類題不需要寫代碼但需要用語言把邏輯講清楚。計算層給你一組進(jìn)程或頁面訪問序列讓你算平均周轉(zhuǎn)時間、缺頁次數(shù)。這類題在面試中經(jīng)常以“紙筆演算”的形式出現(xiàn)有時候面試官會隔著屏幕讓你一步一步說過程。手撕層給你一個場景讓你直接寫代碼或者偽代碼。最常見的是信號量同步生產(chǎn)者消費(fèi)者、LRU緩存、銀行家算法安全性檢測。這三個層級的復(fù)習(xí)策略完全不同。概念層靠背誦框架計算層靠刷真題練手算速度和準(zhǔn)確率手撕層則需要真正敲代碼不能只看不練。我見過不少同學(xué)把“看懂了”當(dāng)成“會了”結(jié)果機(jī)試上手就卡殼這種教訓(xùn)太常見了。1.2 算法掌握程度分檔表結(jié)合復(fù)試實際考察頻率和難度我把操作系統(tǒng)里的核心算法分成了三檔備考時可以按這個優(yōu)先級分配時間檔次算法或問題掌握要求常見考察形式第一檔必須能手撕生產(chǎn)者-消費(fèi)者模型、信號量P/V操作、LRU頁面置換、銀行家算法安全性檢查能獨(dú)立寫出完整代碼或偽代碼并能解釋每一步含義機(jī)試編程題、面試手寫代碼第二檔必須會算FCFS、SJF、RR調(diào)度、SPF、頁面置換OPT/FIFO/LRU/Clock、磁盤SSTF/SCAN/C-SCAN給定數(shù)據(jù)能快速手算結(jié)果且過程表達(dá)清晰筆試填空題、面試口述計算過程第三檔理解即可動態(tài)分區(qū)分配算法FF/BF/WF、段頁式地址轉(zhuǎn)換、文件系統(tǒng)索引結(jié)構(gòu)、磁盤RAID能說清核心思想、優(yōu)缺點(diǎn)、適用場景面試概念問答這里給一個非常實用的建議第一檔的算法不要只準(zhǔn)備一種實現(xiàn)方式。比如生產(chǎn)者-消費(fèi)者模型至少要能寫出信號量版本如果時間充裕再把條件變量版本也準(zhǔn)備一下因為面試官經(jīng)常會追問“還有沒有別的寫法”。LRU也是光會說“用哈希表加雙向鏈表”不夠得能真的寫出來后面我會單開一節(jié)講代碼實現(xiàn)。2. 并發(fā)與同步經(jīng)典題生產(chǎn)者-消費(fèi)者、讀者-寫者、哲學(xué)家就餐的代碼重點(diǎn)2.1 生產(chǎn)者-消費(fèi)者信號量的核心模板生產(chǎn)者-消費(fèi)者問題是復(fù)試中出現(xiàn)頻率最高的操作系統(tǒng)算法題沒有之一。它包含兩個核心要素互斥訪問緩沖區(qū)、同步協(xié)調(diào)生產(chǎn)與消費(fèi)的節(jié)奏。對應(yīng)到信號量上就是經(jīng)典的“三個信號量”模型mutex管互斥empty記錄空位full記錄滿位。下面這個版本是復(fù)試中最好用的通用模板用類C語言寫的偽代碼機(jī)試時改造成具體語言也非常方便#define N 100 // 緩沖區(qū)大小 semaphore mutex 1; // 互斥信號量 semaphore empty N; // 空閑緩沖區(qū)數(shù)量 semaphore full 0; // 已占用緩沖區(qū)數(shù)量 void producer() { while (1) { // 生產(chǎn)一個產(chǎn)品放入 nextp P(empty); // 申請一個空閑緩沖區(qū) P(mutex); // 進(jìn)入臨界區(qū) // 將 nextp 放入緩沖區(qū) buffer V(mutex); // 退出臨界區(qū) V(full); // 已占用緩沖區(qū)數(shù)量加1 } } void consumer() { while (1) { P(full); // 申請一個已占用緩沖區(qū) P(mutex); // 進(jìn)入臨界區(qū) // 從緩沖區(qū)取出一個產(chǎn)品 V(mutex); // 退出臨界區(qū) V(empty); // 空閑緩沖區(qū)數(shù)量加1 // 消費(fèi)產(chǎn)品 } }這段代碼有幾個地方是面試官最愛追問的提前準(zhǔn)備好答案為什么P(empty)和P(full)一定要放在P(mutex)外面如果反過來先加互斥鎖再檢查資源數(shù)量一旦緩沖區(qū)滿或空持有mutex的進(jìn)程就會在P(empty)或P(full)上阻塞而其他進(jìn)程又進(jìn)不了臨界區(qū)釋放資源這就造成了死鎖。這個點(diǎn)幾乎每次面試都會問到務(wù)必要能講清。P/V操作必須成對出現(xiàn)但不一定在同一進(jìn)程內(nèi)。P(empty)和V(empty)分別出現(xiàn)在生產(chǎn)者和消費(fèi)者中是通過資源共享實現(xiàn)同步的關(guān)鍵。很多初學(xué)者會誤以為信號量操作只能在一個進(jìn)程內(nèi)配對這是一個常見的理解誤區(qū)。機(jī)試時如果用C語言寫需要注意semaphore在C語言里沒有現(xiàn)成類型通常用sem_t如果允許用Python可以直接用threading.Semaphore邏輯和上面完全一致。但我個人的建議是復(fù)試機(jī)試盡量用C語言準(zhǔn)備因為很多學(xué)校的判題環(huán)境對Python多線程支持并不友好。2.2 讀者-寫者讀寫鎖的思想和代碼讀者-寫者問題考察的是對“讀寫鎖”思想的理解。核心規(guī)則是多個讀者可以同時讀寫者必須獨(dú)占讀者和寫者不能同時操作。復(fù)試中最?？嫉陌姹臼恰白x者優(yōu)先”也就是只要有讀者在讀后來的讀者可以無條件進(jìn)入寫者必須等待所有讀者退出。用信號量實現(xiàn)的經(jīng)典代碼如下semaphore rw_mutex 1; // 控制寫者互斥 semaphore mutex 1; // 保護(hù)讀者計數(shù) int read_count 0; // 當(dāng)前讀者數(shù)量 void reader() { while (1) { P(mutex); read_count; if (read_count 1) P(rw_mutex); // 第一個讀者加鎖阻止寫者 V(mutex); // 執(zhí)行讀操作 P(mutex); read_count--; if (read_count 0) V(rw_mutex); // 最后一個讀者解鎖允許寫者 V(mutex); } } void writer() { while (1) { P(rw_mutex); // 執(zhí)行寫操作 V(rw_mutex); } }這段代碼的邏輯核心在于只有第一個讀者和最后一個讀者才需要操作rw_mutex中間的讀者只是增減計數(shù)不需要碰寫者鎖。這個設(shè)計精妙在把“一個寫者對比多個讀者”的互斥關(guān)系通過讀者計數(shù)轉(zhuǎn)換成了“是否有人正在讀”的布爾判斷。面試追問一般有兩個方向一是“這個版本有什么問題”答案是寫者可能被餓死因為只要讀者源源不斷地來寫者就永遠(yuǎn)等不到鎖二是“如何實現(xiàn)寫者優(yōu)先”標(biāo)準(zhǔn)做法是增加一個write_mutex讓寫者排隊優(yōu)先這會復(fù)雜一些但如果能答出來是很加分的表現(xiàn)。2.3 哲學(xué)家就餐與吸煙者問題死鎖避免思路哲學(xué)家就餐問題在復(fù)試中更多是以“問思路”的形式出現(xiàn)而不是要求完整寫代碼。它的經(jīng)典死鎖場景是五個哲學(xué)家同時拿起左邊的叉子導(dǎo)致所有人都無法拿到右邊的叉子。解決思路通常有三個最多允許四位哲學(xué)家同時就餐設(shè)置一個計數(shù)信號量room 4這樣至少有一位哲學(xué)家能拿到兩把叉子吃完后釋放打破循環(huán)等待。要求哲學(xué)家先拿編號較小的叉子給叉子按序編號每人先拿小號再拿大號破壞“循環(huán)等待”條件。借助互斥鎖保證拿叉子動作的原子性取叉子時加鎖這樣不會出現(xiàn)“每人拿一把”的中間狀態(tài)。我建議復(fù)試時重點(diǎn)準(zhǔn)備第一種方案因為它最簡單三句話就能說明白引入一個信號量限制同時就餐人數(shù)為4人死鎖就不會發(fā)生?；卮饡r補(bǔ)一句“這只是破壞死鎖條件中循環(huán)等待的一種方式”會讓面試官覺得你不是死記答案而是真的理解了死鎖成因。吸煙者問題和哲學(xué)家問題類似考察的是三個進(jìn)程與三種資源的匹配關(guān)系思路也是“用互斥信號量保護(hù)資源分配過程”一般面試?yán)锍霈F(xiàn)頻率不高但概率論上有一個“P/V操作描述吸煙者”的經(jīng)典題目建議還是把代碼過一遍。3. 調(diào)度算法與計算題平均周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間怎么算3.1 FCFS、SJF、RR、優(yōu)先級、多級反饋隊列處理機(jī)調(diào)度這塊復(fù)試筆試的計算題占了很大的比重。本科課程和復(fù)試參考書里最常出現(xiàn)的算法有五種先來先服務(wù)FCFS、短作業(yè)優(yōu)先SJF分為搶占式和非搶占式、時間片輪轉(zhuǎn)RR、優(yōu)先級調(diào)度、多級反饋隊列MLFQ。需要明確的是實際復(fù)試題目里“短作業(yè)優(yōu)先”和“短進(jìn)程優(yōu)先”混用的情況很常見計算時都按“運(yùn)行時間短的先執(zhí)行”來處理。而時間片輪轉(zhuǎn)關(guān)鍵的考點(diǎn)是時間片大小的選擇時間片太大就退化成FCFS時間片太小則上下文切換開銷占比過高?；卮疬@類問題時試著用“極端化假設(shè)”來證明思路——把時間片設(shè)成無限大和設(shè)成無限小分別看效果這個推演過程本身就是面試官想聽的。優(yōu)先級調(diào)度需要額外注意“饑餓”問題低優(yōu)先級進(jìn)程可能永遠(yuǎn)無法運(yùn)行。解決方案是老化Aging——隨著等待時間增長逐步提升優(yōu)先級看過的同學(xué)都知道這是《現(xiàn)代操作系統(tǒng)》里的經(jīng)典解法答出來非常加分。多級反饋隊列這個算法在復(fù)試中常以概念題出現(xiàn)它的核心是“優(yōu)先級高的隊列時間片小用完降級新的高優(yōu)先級任務(wù)可以搶占”。最好準(zhǔn)備一個三步描述建立多個不同時間片的隊列、新任務(wù)進(jìn)入最高優(yōu)先級隊列、任務(wù)時間片用完未結(jié)束則降級。這三點(diǎn)說全基本上就拿到分了。3.2 一個完整的計算示例計算題只看概念是不夠的我直接給出一個完整的例子這是復(fù)試?yán)锓浅５湫偷念}目建議自己動手算一遍有四個進(jìn)程 A、B、C、D到達(dá)時間分別為 0、1、2、3運(yùn)行時間分別為 5、3、2、1。分別計算非搶占式 SJF 和時間片為 2 的 RR 調(diào)度的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。非搶占式 SJF調(diào)度順序推導(dǎo)時刻 0 只有 A 到達(dá)A 運(yùn)行5個時間單位到時刻5。此時 B、C、D 都已到達(dá)運(yùn)行時間分別為 3、2、1按短作業(yè)優(yōu)先排序為 D1、C2、B3。所以執(zhí)行順序是 A → D → C → B。A完成時間5周轉(zhuǎn)時間 5-05帶權(quán)周轉(zhuǎn)時間 5/51D完成時間6周轉(zhuǎn)時間 6-33帶權(quán)周轉(zhuǎn)時間 3/13C完成時間8周轉(zhuǎn)時間 8-26帶權(quán)周轉(zhuǎn)時間 6/23B完成時間11周轉(zhuǎn)時間 11-110帶權(quán)周轉(zhuǎn)時間 10/3≈3.33平均周轉(zhuǎn)時間 (53610)/4 6平均帶權(quán)周轉(zhuǎn)時間 (1333.33)/4 ≈ 2.58。時間片為 2 的 RR 調(diào)度用甘特圖推演時刻0 A開始用掉2剩余3時刻2 B進(jìn)入運(yùn)行到4B剩余1時刻4 C進(jìn)入運(yùn)行到6C完成時刻6 D進(jìn)入運(yùn)行到7D完成時刻7 A恢復(fù)運(yùn)行到9A剩余1時刻9 B進(jìn)入運(yùn)行到10B完成時刻10 A進(jìn)入運(yùn)行到11A完成。A完成11周轉(zhuǎn)時間11B完成10周轉(zhuǎn)時間9C完成6周轉(zhuǎn)時間4D完成7周轉(zhuǎn)時間4平均周轉(zhuǎn)時間 (11944)/4 7。對比可以發(fā)現(xiàn)這個例子里 RR 的平均周轉(zhuǎn)時間比 SJF 差這說明在已知運(yùn)行時間的前提下SJF 的周轉(zhuǎn)時間確實有優(yōu)勢RR 的優(yōu)勢在響應(yīng)時間而非周轉(zhuǎn)時間。提示計算周轉(zhuǎn)時間尤其是 RR 調(diào)度一定要畫甘特圖或者時間軸心算非常容易漏恢復(fù)執(zhí)行的時間片。我見過太多考生在這道題上因為少算了最后一段恢復(fù)執(zhí)行而丟分。3.3 面試追問如何證明SJF最優(yōu)關(guān)于 SJF 的最優(yōu)性正確的說法是在非搶占式調(diào)度中SJF 能使平均等待時間最小。證明思路很經(jīng)典用交換論證法假設(shè)調(diào)度序列中存在兩個相鄰進(jìn)程前一個運(yùn)行時間更長而后一個更短交換它們的執(zhí)行順序前者的等待時間減少量大于后者的等待時間增加量因此總體平均等待時間下降。反復(fù)交換直到任意相鄰位置都滿足“短作業(yè)在前”的規(guī)則就是 SJF 的順序。這個證明過程復(fù)試時不需要寫得很長用兩三句話說清“交換相鄰兩項后總等待時間減少”就夠了。但這句話說得好不好直接決定了面試官對這一問的印象分——因為十個考生里八個都在背結(jié)論只有真正理解的人能把“為什么”講明白。4. 內(nèi)存管理分區(qū)分配、頁面置換算法和LRU手寫實現(xiàn)4.1 動態(tài)分區(qū)分配算法對比內(nèi)存管理在復(fù)試筆試中?？嫉氖莿討B(tài)分區(qū)分配算法首次適應(yīng)FF、最佳適應(yīng)BF、最差適應(yīng)WF、循環(huán)首次適應(yīng)NF。別看名字多抓住一個核心維度就全記住了——空閑分區(qū)按什么順序組織、找什么樣的空閑區(qū)。我在復(fù)習(xí)的時候做過一個對比表基本上一張表就能把這幾個算法記牢算法空閑分區(qū)排列方式分配策略優(yōu)點(diǎn)缺點(diǎn)首次適應(yīng)FF按地址遞增找到第一個夠大的就分配地址利用率高、簡單低地址容易產(chǎn)生大量碎片循環(huán)首次適應(yīng)NF按地址遞增且每次從上次位置繼續(xù)找從上次查找位置開始找第一個夠大的分配更均勻避免頻繁掃描可能降低內(nèi)存利用率最佳適應(yīng)BF按容量遞增找最小的夠用分區(qū)保留大塊內(nèi)存產(chǎn)生大量難以利用的小碎片最差適應(yīng)WF按容量遞減找最大的分區(qū)分配碎片較小大分區(qū)被快速切割耗盡面試中這個知識點(diǎn)的追問方向一般是“為什么最佳適應(yīng)不是真的最佳”——因為從名字上看“最佳”容易讓人誤解但它追求的是“每次留下的碎片最小”而大量小碎片反而導(dǎo)致后續(xù)大請求無法被滿足所以從整體看并不最優(yōu)。這個“名不副實”的點(diǎn)是面試官非常喜歡的陷阱復(fù)習(xí)時一定不要只記名字。4.2 頁面置換算法OPT、FIFO、LRU、Clock頁面置換算法是內(nèi)存管理中最核心的計算題考點(diǎn)。四種算法必須掌握OPT最佳置換淘汰未來最長時間不被訪問的頁面理論最優(yōu)但無法實現(xiàn)只用于對比衡量。FIFO先進(jìn)先出淘汰最早進(jìn)入內(nèi)存的頁面實現(xiàn)簡單但可能出現(xiàn)Belady異?！峙涞奈锢韷K數(shù)增加反而缺頁次數(shù)增加。LRU最近最久未使用淘汰最長時間未被訪問的頁面性能接近OPT實現(xiàn)開銷高。Clock時鐘也稱NRU最近未使用給每個頁面加一個引用位指針掃描遇到引用位為0就淘汰為1則置0并繼續(xù)。本質(zhì)是LRU的近似實現(xiàn)開銷遠(yuǎn)低于真正的LRU。這里特別提醒FIFO和LRU在“分配物理塊數(shù)增加時缺頁次數(shù)是否一定不增加”這個問題上表現(xiàn)不同F(xiàn)IFO可能增加Belady異常LRU不會。這一點(diǎn)復(fù)試筆試中經(jīng)常作為辨析題出現(xiàn)。真題計算示例頁面訪問序列1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5物理塊數(shù)3分別求FIFO和LRU的缺頁次數(shù)。FIFO初始內(nèi)存為空前3次必缺頁。按先進(jìn)先出邏輯推演訪問4時淘汰1訪問5時淘汰2后續(xù)訪問1缺頁淘汰3訪問2缺頁淘汰4訪問3缺頁淘汰5訪問4缺頁淘汰1訪問5缺頁淘汰2?？?cè)表摯螖?shù)9次。LRU前3次同樣缺頁。訪問4時淘汰1因為1最久未用訪問5時淘汰21剛被訪問過變新后續(xù)訪問1缺頁淘汰3訪問2缺頁淘汰4訪問3缺頁淘汰5訪問4缺頁這時候需要看內(nèi)存中當(dāng)前是1、2、3訪問4要淘汰最久未使用的1缺頁1訪問5時淘汰2缺頁1?？?cè)表摯螖?shù)10次。這個例子其實非常經(jīng)典也說明LRU“比FIFO更好”的說法不能一概而論要看具體序列。復(fù)試時如果時間緊張不需要把整個序列都背下來但一定要把計算過程從頭到尾推演一遍熟練掌握“每一步淘汰誰”的判斷規(guī)則。4.3 LRU的代碼實現(xiàn)哈希表加雙向鏈表復(fù)試機(jī)試?yán)風(fēng)RU是出現(xiàn)頻率極高的考題很多學(xué)校會直接考“實現(xiàn)一個LRU緩存”的 LeetCode 原題。標(biāo)準(zhǔn)解法是哈希表 雙向鏈表哈希表保證 O(1) 的查找雙向鏈表保證 O(1) 的節(jié)點(diǎn)移動和刪除。// 雙向鏈表節(jié)點(diǎn) typedef struct Node { int key; int value; struct Node *prev; struct Node *next; } Node; // LRU緩存結(jié)構(gòu) #define CAPACITY 3 Node *head, *tail; Node *hashTable[10000]; // 簡化版直接用數(shù)組當(dāng)哈希表 int cacheSize 0;因為篇幅原因這里給的是最核心的偽代碼框架完整實現(xiàn)并不長大致包括三個操作get時若命中則把節(jié)點(diǎn)移到鏈表頭部put時若已存在則更新值并移到頭部若不存在則插入頭部如果容量已滿則刪除尾部節(jié)點(diǎn)。只要“每次訪問都更新到頭部”“淘汰時刪尾部”這兩條規(guī)則寫對核心邏輯就通了。機(jī)試實際寫的時候有幾個非常容易出錯的細(xì)節(jié)提前避坑雙向鏈表一定要設(shè)置虛擬頭尾節(jié)點(diǎn)否則邊界判斷非常容易出錯導(dǎo)致空鏈表時訪問空指針。哈希表的結(jié)構(gòu)體里不能只存value還必須存key因為淘汰尾部節(jié)點(diǎn)時需要通過哈希表刪除對應(yīng)的鍵如果沒有key字段就刪不掉。這是我當(dāng)年第一版代碼里踩過的坑。Python 實現(xiàn)的collections.OrderedDict也支持 LRU 語義但復(fù)試手撕代碼時反而不建議用因為面試官更想看你對底層結(jié)構(gòu)的理解。5. 死鎖與銀行家算法安全性檢查的完整推理過程5.1 死鎖的四個必要條件與處理策略死鎖這一塊在復(fù)試中幾乎從不缺席。四個必要條件是互斥、持有并等待、不可剝奪、循環(huán)等待。這里有一個非常經(jīng)典的復(fù)習(xí)技巧處理策略和必要條件是一一對應(yīng)的。破壞互斥一般做不到因為有些資源本質(zhì)就是互斥的比如打印機(jī)。破壞持有并等待讓進(jìn)程一次性申請所有資源但資源利用率會下降。破壞不可剝奪允許系統(tǒng)強(qiáng)行搶占但可能導(dǎo)致數(shù)據(jù)不一致。破壞循環(huán)等待給資源編號按序申請這正是哲學(xué)家就餐“先拿小號叉子”方案的原理。復(fù)試題里更?？嫉氖恰八梨i避免”也就是銀行家算法。它與“死鎖預(yù)防”的區(qū)別在于預(yù)防是提前破壞條件避免是運(yùn)行過程中動態(tài)判斷安全性。這個對比最好記在心里因為面試官問完概念大概率會跟一句“那預(yù)防和避免有什么區(qū)別”用一句話說清楚就贏了。5.2 銀行家算法的安全性檢查流程銀行家算法的核心是安全性檢查整個流程可以用四步描述維護(hù)三個數(shù)據(jù)結(jié)構(gòu)Available可用資源向量、Max各進(jìn)程最大需求矩陣、Allocation各進(jìn)程已分配矩陣還需要Need Max - Allocation來表示還需資源。尋找一個進(jìn)程滿足Need[i] Available且未完成則假定它執(zhí)行完并釋放所有資源Available Allocation[i]標(biāo)記該進(jìn)程完成。重復(fù)步驟2直到所有進(jìn)程都能完成則系統(tǒng)處于安全狀態(tài)。如果找不到這樣的進(jìn)程則系統(tǒng)處于不安全狀態(tài)。復(fù)試時銀行家算法最常見的考法是手算安全序列。這里有一個我反復(fù)強(qiáng)調(diào)的提醒一個系統(tǒng)處于安全狀態(tài)則一定不會死鎖但一個系統(tǒng)處于不安全狀態(tài)不代表它一定已經(jīng)死鎖。不安全只是“未來可能進(jìn)入死鎖”因為實際執(zhí)行路徑可能并不會真的走到那一步。這個“可能”字咬得特別緊每年都有考生在這里栽跟頭。5.3 手算題目練習(xí)看一個經(jīng)典的手算題系統(tǒng)有 A、B、C 三類資源Available (3, 3, 2)五個進(jìn)程的 Allocation 和 Need 如下表進(jìn)程AllocationNeedP0(0, 1, 0)(7, 4, 3)P1(2, 0, 0)(1, 2, 2)P2(3, 0, 2)(6, 0, 0)P3(2, 1, 1)(0, 1, 1)P4(0, 0, 2)(4, 3, 1)安全性檢查推導(dǎo)過程初始Available (3, 3, 2)。檢查各進(jìn)程P1 的 Need (1,2,2) (3,3,2)滿足假設(shè) P1 執(zhí)行完釋放資源后Available (3,3,2) (2,0,0) (5,3,2)。當(dāng)前 Available (5,3,2)檢查剩余進(jìn)程P3 的 Need (0,1,1) (5,3,2)滿足P3 執(zhí)行完Available (5,3,2) (2,1,1) (7,4,3)。P0 的 Need (7,4,3) (7,4,3)滿足P0 執(zhí)行完Available (7,4,3) (0,1,0) (7,5,3)。P2 的 Need (6,0,0) (7,5,3)滿足P2 執(zhí)行完Available (7,5,3) (3,0,2) (10,5,5)。P4 的 Need (4,3,1) (10,5,5)滿足全部完成。安全序列P1 → P3 → P0 → P2 → P4系統(tǒng)安全。這個推導(dǎo)過程的書寫規(guī)范在筆試?yán)锓浅Ｓ绊懙梅治医ㄗh每一步都明確寫出“哪個進(jìn)程能執(zhí)行、釋放后 Available 變成多少”不要在心算中省略過程。面試口述時也一樣一步一步說面試官能跟上你的思路這本身就是在展示你思維的嚴(yán)謹(jǐn)性。注意銀行家算法機(jī)試如果要求寫代碼核心就是“反復(fù)掃描進(jìn)程集合直到找不到可分配進(jìn)程”實現(xiàn)時用一個finish[]數(shù)組標(biāo)記已完成進(jìn)程即可復(fù)雜度是 O(n2·m)n 是進(jìn)程數(shù)m 是資源類型數(shù)復(fù)雜度本身也經(jīng)常被問到。6. 磁盤調(diào)度與文件系統(tǒng)算法SSTF、SCAN、CSCAN和索引節(jié)點(diǎn)6.1 磁盤調(diào)度算法對比磁盤調(diào)度考察的頻率在考研復(fù)試?yán)锫缘陀趦?nèi)存和并發(fā)但屬于“不能丟分”的送分題。核心算法是這幾個先來先服務(wù)FCFS、最短尋道時間優(yōu)先SSTF、掃描算法SCAN電梯算法、循環(huán)掃描C-SCAN、LOOK和C-LOOK。SSTF選擇離當(dāng)前磁頭最近的請求平均尋道時間短但遠(yuǎn)端的請求可能被餓死。SCAN讓磁頭沿一個方向移動途中處理所有請求到最遠(yuǎn)端后反向避免了饑餓。C-SCAN則只沿一個方向服務(wù)返回時快速空移這樣兩端請求的等待時間更均勻。LOOB 和 C-LOOK 的區(qū)別是不一定移動到最遠(yuǎn)端點(diǎn)只移動到該方向上最遠(yuǎn)的請求位置就反向效率更高。面試的常見追問是“為什么 C-SCAN 的等待時間比 SCAN 更均勻”——因為 SCAN 在反向后的第一個服務(wù)區(qū)間的請求等待時間可能極短而同一批被服務(wù)過的請求要等一圈不同區(qū)域的請求等待時間差異很大C-SCAN 統(tǒng)一了“從頭掃到尾、快速返回”的模式每圈內(nèi)服務(wù)次序更規(guī)則。計算題一般會給一個當(dāng)前磁道號和請求序列讓算磁頭移動的總磁道數(shù)。這種題就是仔細(xì)加細(xì)心畫出移動路徑就不會錯。磁道序列長的時候推薦用表格記錄當(dāng)前磁道、下一目標(biāo)、移動距離和累計距離防止算到最后一步時對不上數(shù)。6.2 文件系統(tǒng)的常見考點(diǎn)文件系統(tǒng)在算法層面的考試內(nèi)容相對固定主要是索引節(jié)點(diǎn)和目錄結(jié)構(gòu)。復(fù)試高頻考點(diǎn)是連續(xù)分配支持隨機(jī)訪問但會產(chǎn)生外部碎片。鏈接分配消除了外部碎片但只能順序訪問。索引分配每個文件維護(hù)一個索引塊支持隨機(jī)訪問是主流方案。IP 節(jié)點(diǎn)的計算題幾乎是每年必出典型問題如下某文件系統(tǒng)索引節(jié)點(diǎn)中有13個地址項其中10個為直接地址項1個一級間接地址項1個二級間接地址項1個三級間接地址項。磁盤塊大小4KB每個磁盤塊號占4B。求單個文件最大長度。計算步驟一個磁盤塊能存放的地址項數(shù)量 4KB / 4B 1024 個。一級間接能尋址 1024 × 4KB 4MB二級間接 1024 × 4MB 4GB三級間接 1024 × 4GB 4TB。最大文件長度 10 × 4KB 4MB 4GB 4TB約等于 4.04TB。這道題的變形在于地址項數(shù)量和塊號字節(jié)數(shù)會變但思路完全一致。我建議把這個模板記牢考試時直接套數(shù)字就行。文件系統(tǒng)這塊的內(nèi)容不太需要寫代碼主要是計算和理解但它每年都能在復(fù)試卷上占據(jù)10分左右的分值不復(fù)習(xí)等于白送分給別人。7. 復(fù)試現(xiàn)場與機(jī)試備考的經(jīng)驗教訓(xùn)7.1 踩過的坑先講一個很多人都會踩的坑只背不練代碼。操作系統(tǒng)算法不像數(shù)據(jù)結(jié)構(gòu)那樣有直觀的“寫錯就運(yùn)行不起來”的反饋很多同學(xué)把代碼背下來就覺得萬事大吉但復(fù)試時面試官會要求在紙上寫或者機(jī)試環(huán)境下沒有提示和自動補(bǔ)全。我強(qiáng)烈建議復(fù)習(xí)期間把第一檔的算法全部手寫三遍以上寫的過程中你會發(fā)現(xiàn)很多細(xì)節(jié)根本沒記住——比如信號量初始化參數(shù)、讀者寫者里 read_count 是誰在保護(hù)、銀行家算法在哪一步更新 Available。第二個坑是以為公平一定是好的。面試中一旦討論到算法優(yōu)劣不要下意識覺得“不讓任何進(jìn)程餓死好的”。比如10道任務(wù)里有1個需要1秒完成、1個需要100秒完成SJF 可以讓平均等待時間最少但會讓長任務(wù)無限等待。真正的答案是“權(quán)衡”——操作系統(tǒng)算法本質(zhì)上都是 trade-off。用這個詞回答問題面試官會覺得你是有真實理解而非背書。第三個坑是忽略陳述的表達(dá)。復(fù)試不是筆試不是算出正確答案就行。很多計算題面試官會讓你現(xiàn)場口算并說出來如果心里會算但說不清楚很容易被誤判為“半懂”。提前練習(xí)“把計算過程講解給別人聽”這個能力比多刷十道題更有價值。7.2 手撕代碼的考場技巧關(guān)于復(fù)試時手寫代碼我總結(jié)幾個親測有效的經(jīng)驗尤其對考場上容易緊張的同學(xué)特別管用先寫函數(shù)簽名和數(shù)據(jù)結(jié)構(gòu)再寫邏輯。很多考生一上來就埋頭寫核心邏輯寫到一半發(fā)現(xiàn)局部變量沒聲明、函數(shù)參數(shù)沒定好涂涂改改卷面非常難看。先搭框架是減小心理壓力的關(guān)鍵一步。用偽代碼不丟分。面試手寫題很多時候沒有編譯器偽代碼反而能更快把算法思想表達(dá)清楚。只要關(guān)鍵邏輯和變量定義清晰面試官通常不會因為語法細(xì)節(jié)扣分。主動解釋每一步的意圖。寫代碼時邊寫邊說“這里用 mutex 保護(hù)緩沖區(qū)”“這里是第一個讀者才加鎖”既展示了你的邏輯又避免了冷場。大部分面試官對“能講代碼”的考生印象分都很高。如果卡住了先講思路再下手寫。很多時候思路說出來你自己就發(fā)現(xiàn)卡點(diǎn)在哪了而且面試官給的提示也會更精準(zhǔn)。悶頭硬寫是最差的選擇。最后再分享一個小技巧是我自己備考后期一直在用的把第一檔算法做成索引卡片每張卡片只寫題目和關(guān)鍵提示詞比如“生產(chǎn)者消費(fèi)者——三個信號量”“LRU——哈希加雙向鏈表”“銀行家——Available推出安全序列”。每天隨機(jī)抽五張對著卡片在紙上花五分鐘寫完一個算法的骨架。堅持兩周機(jī)試時你會發(fā)現(xiàn)這些代碼就像條件反射一樣自然。復(fù)試說到底是一場“穩(wěn)健性”比拼不是比誰掌握的知識更前沿而是比誰在有限時間和高壓力環(huán)境下能把基礎(chǔ)算法穩(wěn)定輸出出來。把上面這些內(nèi)容踏踏實實過一遍操作系統(tǒng)算法這一關(guān)就沒有過不去的道理。