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