簡(jiǎn)介面向西北工業(yè)大學(xué)801考研的操作系統(tǒng)復(fù)習(xí)資料以單份PDF形式梳理課程核心知識(shí)適合基礎(chǔ)階段搭建知識(shí)框架也便于沖刺階段查漏補(bǔ)缺。內(nèi)容按操作系統(tǒng)概述、進(jìn)程管理、內(nèi)存管理、文件管理、設(shè)備管理與作業(yè)調(diào)度六部分展開(kāi)覆蓋進(jìn)程狀態(tài)與PCB、先來(lái)先服務(wù)與短作業(yè)優(yōu)先等調(diào)度算法、同步互斥與PV操作、固定分區(qū)與分頁(yè)分段、虛擬內(nèi)存與內(nèi)外碎片、文件邏輯與物理結(jié)構(gòu)、I/O控制方式及作業(yè)周轉(zhuǎn)時(shí)間等高頻考點(diǎn)并對(duì)易混概念和算法差異作出歸納便于對(duì)照教材建立復(fù)習(xí)索引。壓縮包內(nèi)共1個(gè)PDF文件大小約19.05MB內(nèi)容集中適合按章節(jié)檢索、在平板或電腦上閱讀標(biāo)注并反復(fù)翻閱。已有167人學(xué)習(xí)可作為801專(zhuān)業(yè)課復(fù)習(xí)中的提綱式筆記與考前速覽材料幫助快速定位重點(diǎn)章節(jié)和薄弱環(huán)節(jié)。1. 四塊知識(shí)其實(shí)是一套賬操作系統(tǒng)考的從來(lái)不是概念而是狀態(tài)遷移的邊界翻過(guò)一份把操作系統(tǒng)壓成幾十頁(yè)的手寫(xiě)掃描筆記最反直覺(jué)的地方在于進(jìn)程、內(nèi)存、文件、設(shè)備看上去是四套獨(dú)立知識(shí)實(shí)際上卻對(duì)應(yīng)同一套記賬邏輯——資源有狀態(tài)狀態(tài)只能沿合法邊界遷移考題和真實(shí)內(nèi)核出問(wèn)題的地方都集中在邊界上。801 這類(lèi)自命題科目真正愛(ài)考的是“進(jìn)程在等 I/O 時(shí)被調(diào)度走誰(shuí)保存了它當(dāng)時(shí)的現(xiàn)場(chǎng)”這類(lèi)問(wèn)題而“什么是 PCB”這種表層問(wèn)題并非重點(diǎn)。把這套賬理順之后需要背誦的內(nèi)容會(huì)減少一大半剩下的內(nèi)容基本都能自己推導(dǎo)出來(lái)。2. 進(jìn)程與 PCB為什么“狀態(tài)”必須落進(jìn)一個(gè)結(jié)構(gòu)體里大多數(shù)人對(duì)進(jìn)程的理解停留在“程序的一次執(zhí)行”這句話(huà)沒(méi)錯(cuò)但幾乎不解決問(wèn)題。真正讓人算錯(cuò)題、也真正讓內(nèi)核寫(xiě)出 bug 的是狀態(tài)機(jī)的邊和 PCB 的字段筆記如果只畫(huà)了五個(gè)方框和箭頭卻沒(méi)有說(shuō)明哪條邊是誰(shuí)觸發(fā)的后面調(diào)度、同步、死鎖就會(huì)全部只能靠背。這一章把這三樣拆開(kāi)看狀態(tài)機(jī)的約束、PCB 的字段動(dòng)機(jī)、調(diào)度算法的選擇函數(shù)。2.1 進(jìn)程狀態(tài)機(jī)五條邊里只有兩條是進(jìn)程自己走的從一個(gè)剛提交的作業(yè)到進(jìn)程終止中間的狀態(tài)是新建、就緒、運(yùn)行、等待、終止。就緒到運(yùn)行由調(diào)度器決定運(yùn)行到就緒是時(shí)間片用完或被更高優(yōu)先級(jí)搶占運(yùn)行到等待由進(jìn)程自己觸發(fā)典型場(chǎng)景是讀文件、等鎖、等 I/O 完成這類(lèi)阻塞叫自愿阻塞等待到就緒由外部事件完成后喚醒運(yùn)行到終止則是進(jìn)程退出。最容易被畫(huà)錯(cuò)的一條邊是“等待直接到運(yùn)行”。這條邊不存在原因很直白被喚醒的進(jìn)程只是重新具備了運(yùn)行資格能不能拿到 CPU 得由調(diào)度器按策略決定。如果允許等待直接跳到運(yùn)行等于事件完成的一瞬間強(qiáng)行搶占 CPU所有調(diào)度策略都會(huì)立刻失效優(yōu)先級(jí)、時(shí)間片、多級(jí)隊(duì)列全部作廢。內(nèi)核里喚醒的正確動(dòng)作是“把 PCB 從等待隊(duì)列摘下、掛到就緒隊(duì)列”僅此而已。還有一個(gè)高頻混淆點(diǎn)阻塞和掛起不是一回事。阻塞是進(jìn)程在內(nèi)存里等事件掛起是把進(jìn)程映像換到外存、騰出內(nèi)存給別的進(jìn)程用這才有了七狀態(tài)模型里的“就緒掛起”和“等待掛起”。做題時(shí)如果題目出現(xiàn)“內(nèi)存緊張”“換出”那考的是掛起只說(shuō)“等待 I/O”那是阻塞。2.2 PCB內(nèi)核里唯一信得過(guò)的現(xiàn)場(chǎng)記錄進(jìn)程切換的本質(zhì)是“把一套 CPU 寄存器換掉再把另一套裝進(jìn)來(lái)”。CPU 只有一套物理寄存器被切走的進(jìn)程的所有現(xiàn)場(chǎng)必須有個(gè)地方存這個(gè)地方就是 PCB它也是內(nèi)核態(tài)數(shù)據(jù)用戶(hù)態(tài)代碼碰不到。/* 極度簡(jiǎn)化的 PCB 模型字段取自教科書(shū)常見(jiàn)劃分不代表任何真實(shí)內(nèi)核實(shí)現(xiàn) */ struct pcb { int pid; /* 進(jìn)程標(biāo)識(shí)隊(duì)列和表里的主鍵 */ int state; /* NEW/READY/RUNNING/WAITING/TERMINATED */ uint64_t pc; /* 程序計(jì)數(shù)器切走時(shí)下一條要執(zhí)行的指令地址 */ uint64_t regs[32]; /* 通用寄存器現(xiàn)場(chǎng)切換時(shí)整組保存/恢復(fù) */ uint64_t pgtbl; /* 頁(yè)表基址這個(gè)進(jìn)程地址空間的身份 */ int priority; /* 調(diào)度優(yōu)先級(jí)多級(jí)反饋隊(duì)列里會(huì)被動(dòng)態(tài)改寫(xiě) */ struct pcb *next; /* 就緒/等待隊(duì)列指針決定入隊(duì)是 O(1) 還是 O(n) */ int exit_code; /* 退出碼留給父進(jìn)程收尸 */ };逐個(gè)字段看動(dòng)機(jī)。pc和regs是進(jìn)程切換時(shí)的核心現(xiàn)場(chǎng)沒(méi)有它們進(jìn)程被切走后回來(lái)就不知道執(zhí)行到哪了這就是操作系統(tǒng)的“后悔藥”。pgtbl決定了切換的代價(jià)量級(jí)同一地址空間內(nèi)的線(xiàn)程切換不用換它進(jìn)程切換要換而換頁(yè)表往往伴隨 TLB 失效。next指針是純粹的數(shù)據(jù)結(jié)構(gòu)選擇用鏈表就是 O(1) 入隊(duì)但調(diào)度時(shí)要遍歷找優(yōu)先級(jí)最高的用優(yōu)先級(jí)數(shù)組或多級(jí)隊(duì)列則是 O(1) 選人但可能浪費(fèi)內(nèi)存。priority是唯一一個(gè)“策略會(huì)反過(guò)來(lái)改數(shù)據(jù)結(jié)構(gòu)”的字段老化機(jī)制就是不停給它減分。為什么 PCB 必須放在內(nèi)核態(tài)、用戶(hù)不可寫(xiě)道理和虛擬內(nèi)存是同一個(gè)如果進(jìn)程能改自己的state或pgtbl隔離就徹底不存在了。PCB 就是內(nèi)核記錄進(jìn)程狀態(tài)的唯一可信位置所有系統(tǒng)調(diào)用最終都會(huì)修改它。2.3 調(diào)度算法同一個(gè)循環(huán)換一個(gè) pick 函數(shù)把教材里那一堆 FCFS、SJF、優(yōu)先級(jí)、多級(jí)反饋隊(duì)列攤開(kāi)看它們的骨架完全一樣一個(gè)循環(huán)每次從就緒集合里挑一個(gè)進(jìn)程讓它跑跑完或被打斷再挑。區(qū)別只在“怎么挑”以及“能不能打斷”。from dataclasses import dataclass dataclass class Proc: pid: str arrive: int # 到達(dá)時(shí)刻進(jìn)入就緒隊(duì)列的時(shí)間 burst: int # 需要占用 CPU 的時(shí)間 def schedule(procs, pick): pick: 從當(dāng)前就緒集合里選出下一個(gè)執(zhí)行的進(jìn)程 非搶占模型選中后一次跑完整個(gè) burst 返回 [(pid, 周轉(zhuǎn)時(shí)間, 帶權(quán)周轉(zhuǎn)時(shí)間), ...] t, ready, rest, out 0, [], sorted(procs, keylambda p: p.arrive), [] while rest or ready: while rest and rest[0].arrive t: # 把已到達(dá)的放進(jìn)就緒隊(duì)列 ready.append(rest.pop(0)) if not ready: # CPU 空轉(zhuǎn)時(shí)間跳到下一個(gè)到達(dá)點(diǎn) t rest[0].arrive continue p pick(ready) ready.remove(p) t p.burst # 非搶占一次跑完 turnaround t - p.arrive out.append((p.pid, turnaround, turnaround / p.burst)) return out # FCFS誰(shuí)先來(lái)誰(shuí)先跑pick 只看到達(dá)時(shí)間 fcfs lambda q: min(q, keylambda p: p.arrive) # SJF誰(shuí)短誰(shuí)先跑pick 只看服務(wù)時(shí)間 sjf lambda q: min(q, keylambda p: p.burst)參數(shù)含義需要說(shuō)清arrive決定就緒隊(duì)列的入隊(duì)時(shí)機(jī)burst是服務(wù)時(shí)間周轉(zhuǎn)時(shí)間是“完成時(shí)刻減到達(dá)時(shí)刻”帶權(quán)周轉(zhuǎn)時(shí)間是“周轉(zhuǎn)時(shí)間除以服務(wù)時(shí)間”分母弄錯(cuò)是考場(chǎng)上最常見(jiàn)的失分點(diǎn)。把pick換成max就是優(yōu)先級(jí)調(diào)度換成“剩余時(shí)間最短”并允許打斷就是 SRTF。三種策略的設(shè)計(jì)動(dòng)機(jī)值得逐條說(shuō)。FCFS 最簡(jiǎn)單、天然公平但有護(hù)航效應(yīng)一個(gè)長(zhǎng)作業(yè)排在隊(duì)首后面所有短作業(yè)都要干等平均周轉(zhuǎn)時(shí)間會(huì)大幅增加。SJF 能證明平均周轉(zhuǎn)時(shí)間最小代價(jià)是它要求預(yù)知burst而現(xiàn)實(shí)中沒(méi)人知道下一個(gè)進(jìn)程要跑多久工程上的做法是用指數(shù)平滑預(yù)測(cè)把上一次的預(yù)測(cè)值和這次的實(shí)際值加權(quán)混合權(quán)重越小越保守。就算預(yù)測(cè)準(zhǔn)了SJF 還會(huì)餓死長(zhǎng)作業(yè)所以?xún)?yōu)先級(jí)調(diào)度必須配老化等待越久優(yōu)先級(jí)越高用一點(diǎn)最優(yōu)性換無(wú)饑餓。多級(jí)反饋隊(duì)列是這三種思路的折中方案也是我認(rèn)為最值得琢磨的設(shè)計(jì)新進(jìn)程進(jìn)最高優(yōu)先級(jí)隊(duì)列給一個(gè)很短的第一個(gè)時(shí)間片用完沒(méi)結(jié)束就降到下一級(jí)時(shí)間片變長(zhǎng)一直降到最低級(jí)。它不需要預(yù)測(cè)運(yùn)行時(shí)間卻能用“降級(jí)”近似出 SJF 的效果因?yàn)槎套鳂I(yè)在第一級(jí)就跑完了長(zhǎng)作業(yè)自動(dòng)沉底。代價(jià)是兩個(gè)參數(shù)沒(méi)法從理論上定隊(duì)列級(jí)數(shù)和每級(jí)時(shí)間片長(zhǎng)度都是靠測(cè)量調(diào)出來(lái)的這也是它經(jīng)常被吐槽為“玄學(xué)”的原因。2.4 上下文切換真正貴的是冷卻不是保存很多人默認(rèn)進(jìn)程切換昂貴、線(xiàn)程切換廉價(jià)然后拿這句話(huà)去解釋所有性能問(wèn)題。這句話(huà)只在特定前提下成立。直接開(kāi)銷(xiāo)是保存恢復(fù)寄存器、切換內(nèi)核棧、更新 PCB 狀態(tài)這部分對(duì)進(jìn)程和線(xiàn)程差不多量級(jí)很小。真正的差距在地址空間進(jìn)程切換要換頁(yè)表基址TLB 里緩存的地址翻譯全部作廢Cache 里的數(shù)據(jù)也大面積失效回到用戶(hù)態(tài)后要重新預(yù)熱。我一般會(huì)這么理解切換成本由“換不換地址空間”決定不由“是不是線(xiàn)程”決定。同一個(gè)進(jìn)程里兩個(gè)線(xiàn)程如果跑在不同核上、訪(fǎng)問(wèn)的數(shù)據(jù)八竿子打不著Cache 該失效還是失效反過(guò)來(lái)如果兩個(gè)進(jìn)程共享大量?jī)?nèi)存頁(yè)切換后的預(yù)熱代價(jià)也沒(méi)那么夸張。看到“多開(kāi)線(xiàn)程更快”這種結(jié)論先問(wèn)一句快在哪是切換省了還是并發(fā)度上去了。3. 虛擬內(nèi)存為什么邏輯地址必須和物理地址解耦分頁(yè)這件事教材上一句話(huà)就能說(shuō)完把邏輯地址空間切成固定大小的頁(yè)映射到物理頁(yè)框。但真正理解了以后你會(huì)發(fā)現(xiàn)虛擬內(nèi)存解決的從來(lái)不是“內(nèi)存不夠”而是三個(gè)更棘手的問(wèn)題進(jìn)程之間不能互相踩內(nèi)存、程序不能依賴(lài)自己被加載到哪個(gè)物理位置、內(nèi)存可以比物理內(nèi)存小。這一章沿著一次地址翻譯的全過(guò)程走把頁(yè)表項(xiàng)、缺頁(yè)、置換算法串起來(lái)。3.1 一次地址翻譯的完整旅程CPU 執(zhí)行一條訪(fǎng)存指令發(fā)出的是邏輯地址。MMU 把它切成兩部分低位是頁(yè)內(nèi)偏移高位是頁(yè)號(hào)。先查 TLB命中就直接拼出物理地址發(fā)到總線(xiàn)上沒(méi)命中就去查頁(yè)表多級(jí)頁(yè)表要一級(jí)一級(jí)往下走每一級(jí)都取一次內(nèi)存如果最后拿到的頁(yè)表項(xiàng)有效位是 0觸發(fā)缺頁(yè)異?？刂茩?quán)交給內(nèi)核。舉一個(gè)能落地的例子32 位地址、頁(yè)大小 4KB。4KB 等于 2 的 12 次方所以低 12 位是頁(yè)內(nèi)偏移剩下 20 位是頁(yè)號(hào)。要是用兩級(jí)頁(yè)表每級(jí) 10 位一個(gè)地址0x00403A20拆出來(lái)就是一級(jí)索引0x001、二級(jí)索引0x003、偏移0xA20。十六進(jìn)制下這個(gè)拆分特別好做頁(yè)大小 4KB 時(shí)最后三位十六進(jìn)制數(shù)字就是偏移前面全是頁(yè)號(hào)考場(chǎng)上不用換算成二進(jìn)制。多級(jí)頁(yè)表的設(shè)計(jì)動(dòng)機(jī)常被講成“節(jié)省空間”其實(shí)更準(zhǔn)確的說(shuō)法是應(yīng)對(duì)稀疏地址空間。單級(jí)頁(yè)表要給 20 位頁(yè)號(hào)建 2 的 20 次方個(gè)表項(xiàng)每項(xiàng) 4 字節(jié)就是 4MB每個(gè)進(jìn)程一份而且這 4MB 必須常駐可一個(gè)進(jìn)程實(shí)際用到的地址往往只集中在幾個(gè)區(qū)域中間大片是空的。兩級(jí)頁(yè)表把一級(jí)頁(yè)表壓到 4KB二級(jí)頁(yè)表按需創(chuàng)建沒(méi)用到的那段地址連二級(jí)頁(yè)表都不用建。注意多級(jí)頁(yè)表省的是空間代價(jià)是時(shí)間。一次 TLB 未命中可能要訪(fǎng)存兩次甚至四次這也是 TLB 命中率對(duì)性能影響這么大的原因。3.2 頁(yè)表項(xiàng)里每一位在干什么頁(yè)表項(xiàng)不是只存一個(gè)物理頁(yè)框號(hào)它是一組標(biāo)志位加一個(gè)編號(hào)。有效位表示這一頁(yè)是否在內(nèi)存里為 0 就觸發(fā)缺頁(yè)保護(hù)位標(biāo)記這一頁(yè)可讀、可寫(xiě)還是可執(zhí)行寫(xiě)一個(gè)只讀頁(yè)會(huì)觸發(fā)保護(hù)異常而不是缺頁(yè)這兩類(lèi)異常的處理路徑完全不同修改位臟位表示這一頁(yè)被寫(xiě)過(guò)沒(méi)有它決定了換出時(shí)要不要寫(xiě)回磁盤(pán)這是純性能優(yōu)化沒(méi)寫(xiě)過(guò)就不用寫(xiě)回訪(fǎng)問(wèn)位表示這一頁(yè)最近被訪(fǎng)問(wèn)過(guò)它是 Clock 置換算法的唯一輸入。這幾位里臟位的性?xún)r(jià)比最高。操作系統(tǒng)在頁(yè)面換出時(shí)如果臟位是 0直接把頁(yè)框回收就行臟位是 1就得先寫(xiě)磁盤(pán)再回收一次 I/O 的時(shí)間夠 CPU 跑幾十萬(wàn)條指令。所以“讀多寫(xiě)少”的映射文件、代碼段換出成本遠(yuǎn)低于被頻繁寫(xiě)的堆內(nèi)存。3.3 LRU 為什么在硬件里做不出來(lái)Clock 怎么近似理論上最優(yōu)的置換算法是換掉未來(lái)最久不會(huì)被訪(fǎng)問(wèn)的那一頁(yè)這顯然無(wú)法實(shí)現(xiàn)退一步換掉過(guò)去最久沒(méi)被訪(fǎng)問(wèn)的那頁(yè)就是 LRU。LRU 在軟件里好寫(xiě)在硬件里幾乎做不了它要求每次訪(fǎng)存都更新時(shí)間戳或調(diào)整鏈表這個(gè)開(kāi)銷(xiāo)比訪(fǎng)存本身還大而且要在 MMU 里實(shí)現(xiàn)沒(méi)法靠編譯器優(yōu)化。硬件只能提供一個(gè)訪(fǎng)問(wèn)位。Clock 算法就把所有頁(yè)框串成一個(gè)環(huán)配一個(gè)指針需要換頁(yè)時(shí)看指針指向的頁(yè)訪(fǎng)問(wèn)位是 1 就清成 0 并跳過(guò)是 0 就選它換出。這個(gè)“給一次免死機(jī)會(huì)”的動(dòng)作本質(zhì)是用一個(gè) bit 近似“最近有沒(méi)有被訪(fǎng)問(wèn)”工程上夠用。from collections import OrderedDict def fifo(refs, frames): q, faults [], 0 for r in refs: if r not in q: faults 1 if len(q) frames: q.pop(0) # 淘汰最早進(jìn)來(lái)的頁(yè) q.append(r) return faults def lru(refs, frames): q, faults OrderedDict(), 0 for r in refs: if r in q: q.move_to_end(r) # 命中刷新為“最近使用” else: faults 1 if len(q) frames: q.popitem(lastFalse) # 淘汰最久未使用 q[q.__len__()] r if False else None q[r] None return faults refs [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] print(fifo(refs, 3), fifo(refs, 4)) # 9 10幀數(shù)變多缺頁(yè)反而增加 print(lru(refs, 3), lru(refs, 4)) # 10 8棧式算法不會(huì)反常這段代碼里refs是頁(yè)面訪(fǎng)問(wèn)序列frames是可用頁(yè)框數(shù)返回值是缺頁(yè)次數(shù)。fifo用一個(gè)普通列表模擬先進(jìn)先出隊(duì)列l(wèi)ru用OrderedDict維護(hù)訪(fǎng)問(wèn)順序命中就move_to_end挪到隊(duì)尾淘汰時(shí)彈隊(duì)頭。第三行輸出就是著名的 Belady 異常FIFO 在 4 個(gè)頁(yè)框時(shí)缺頁(yè)次數(shù)比 3 個(gè)頁(yè)框還多。原因是 FIFO 不滿(mǎn)足“棧式算法”性質(zhì)增加頁(yè)框會(huì)改變整個(gè)淘汰歷史可能剛好把后面要用的頁(yè)提前踢掉。LRU 和最優(yōu)算法都是棧式的小容量的駐留集永遠(yuǎn)是大容量的子集所以不會(huì)出現(xiàn)這種反常。這也是為什么教材強(qiáng)調(diào)這個(gè)反例它說(shuō)明“加內(nèi)存一定變快”這種直覺(jué)在置換策略上是站不住的。3.4 內(nèi)碎片和外碎片分頁(yè)為什么沒(méi)有外碎片分頁(yè)的代價(jià)是內(nèi)部碎片進(jìn)程最后一頁(yè)大概率裝不滿(mǎn)平均浪費(fèi)半頁(yè)。但分頁(yè)完全沒(méi)有外部碎片因?yàn)樗许?yè)框大小一致任意空閑頁(yè)框都能裝任意頁(yè)不存在“洞太小塞不進(jìn)去”的情況。分段正好相反段是邏輯單位長(zhǎng)度由程序決定一段代碼、一段數(shù)據(jù)、一個(gè)棧大小參差不齊。分配久了就會(huì)在內(nèi)存里留下大量小空洞總量夠但拼不出一個(gè)連續(xù)的大段這就是外部碎片解決辦法是緊湊把進(jìn)程整體挪動(dòng)把空洞擠到一起代價(jià)是搬運(yùn)開(kāi)銷(xiāo)。段頁(yè)式是兩者的組合先按邏輯分成段每段再分頁(yè)邏輯結(jié)構(gòu)保住了物理分配也整齊了代價(jià)是一次訪(fǎng)存要查段表再查頁(yè)表地址翻譯路徑更長(zhǎng)。頁(yè)大小 4KB 是一個(gè)經(jīng)典的折中頁(yè)太小則頁(yè)表項(xiàng)數(shù)量爆炸、TLB 能覆蓋的范圍變小頁(yè)太大則內(nèi)碎片浪費(fèi)加劇、一次缺頁(yè)要讀的數(shù)據(jù)變多。這個(gè)數(shù)值不是理論最優(yōu)而是幾十年工程實(shí)踐調(diào)出來(lái)的平衡點(diǎn)。4. 文件與設(shè)備索引、緩存、調(diào)度其實(shí)是同一套思路換了對(duì)象文件管理和設(shè)備管理常被當(dāng)成兩塊邊緣內(nèi)容其實(shí)它們是前面兩章的復(fù)用文件就是“用索引結(jié)構(gòu)管理外存塊”設(shè)備管理就是“用隊(duì)列和調(diào)度管理獨(dú)占資源”。把 inode 看懂把 DMA 和磁盤(pán)調(diào)度的動(dòng)機(jī)搞清這部分幾乎不用背。4.1 inode文件就是一張索引表加一個(gè)編號(hào)目錄里存的不是文件內(nèi)容而是“文件名到 inode 號(hào)”的映射。inode 里放元數(shù)據(jù)大小、所有者、權(quán)限、時(shí)間戳和塊地址。關(guān)鍵是塊地址的組織方式前若干個(gè)是直接塊后面跟一級(jí)間接、二級(jí)間接、三級(jí)間接。間接塊本身不存數(shù)據(jù)只存下一層塊的編號(hào)。def max_file_bytes(block4096, ptr4, n_direct12): block : 磁盤(pán)塊大小字節(jié) ptr : 一個(gè)塊地址占多少字節(jié)決定每個(gè)間接塊能裝多少指針 n_direct: 直接塊數(shù)量 返回最大文件字節(jié)數(shù)與各級(jí)間接的容量明細(xì) per_block block // ptr # 每個(gè)間接塊能放 1024 個(gè)指針 detail {direct: n_direct * block} total detail[direct] cap per_block for level in (1, 2, 3): cap * per_block if level 1 else per_block ... return total, detail print(max_file_bytes())按 4KB 塊、4 字節(jié)指針?biāo)忝總€(gè)間接塊能放 1024 個(gè)指針。12 個(gè)直接塊覆蓋 48KB一級(jí)間接再覆蓋 1024 個(gè)塊也就是 4MB二級(jí)間接 1024 的平方個(gè)塊4GB三級(jí)間接 4TB。這組數(shù)字解釋了 inode 設(shè)計(jì)的取舍絕大多數(shù)文件很小直接塊命中一次尋址就拿到數(shù)據(jù)路徑最短少數(shù)大文件靠多級(jí)間接撐住容量代價(jià)是訪(fǎng)問(wèn)最后一個(gè)塊要多讀幾次間接塊每一次都是實(shí)打?qū)嵉?I/O。這本質(zhì)上是“小文件快、大文件能裝”的折中而不是追求兩種都最優(yōu)。4.2 三種物理結(jié)構(gòu)的取舍順序結(jié)構(gòu)把文件放在連續(xù)塊上尋道最少、支持隨機(jī)訪(fǎng)問(wèn)缺點(diǎn)是兩個(gè)外部碎片以及文件增長(zhǎng)時(shí)后面可能沒(méi)位置了只能整體搬家。鏈接結(jié)構(gòu)把文件切成塊用指針串起來(lái)沒(méi)有碎片、隨便增長(zhǎng)但只能順序訪(fǎng)問(wèn)想讀最后一塊得從頭走一遍而且指針占空間中間一個(gè)塊壞了整條鏈就斷。索引結(jié)構(gòu)給每個(gè)文件配索引塊索引塊里存所有塊的地址隨機(jī)訪(fǎng)問(wèn)和增長(zhǎng)都支持代價(jià)是多了一層索引塊開(kāi)銷(xiāo)小文件可能為了幾百字節(jié)專(zhuān)門(mén)占一個(gè)索引塊。FAT 是鏈接結(jié)構(gòu)的一個(gè)變體把整條鏈的指針集中到內(nèi)存里的一張表尋道時(shí)查表就行本質(zhì)上是用內(nèi)存換訪(fǎng)問(wèn)速度。這三種結(jié)構(gòu)沒(méi)有絕對(duì)優(yōu)劣選哪個(gè)取決于“這個(gè)文件系統(tǒng)主要跑什么負(fù)載”日志類(lèi)順序?qū)懚嘤面溄幼凅w數(shù)據(jù)庫(kù)類(lèi)隨機(jī)讀多用索引。4.3 空閑空間管理位圖與成組鏈接位圖用 1 bit 標(biāo)記一個(gè)塊是否被占用查找連續(xù)的空閑塊特別快因?yàn)檫B續(xù)的 bit 可以一次掃描一大片。代價(jià)是占空間1TB 磁盤(pán)、4KB 塊一共 2 億多個(gè)塊位圖就是 32MB 左右這部分通常常駐內(nèi)存?？臻e鏈表把空閑塊本身串成鏈幾乎不額外占空間但想找一段連續(xù)空間就得遍歷。成組鏈接是折中方案把空閑塊按組串起來(lái)每組的第一塊記錄下一組的塊號(hào)和數(shù)量分配時(shí)一次能拿到一批既省空間又不用全程遍歷。這幾種方案的取舍都能用一句話(huà)概括拿空間換查找速度還是拿查找速度換空間。4.4 DMA 到底省了什么磁盤(pán)調(diào)度又在省什么I/O 控制方式有三種。程序查詢(xún)是 CPU 死等設(shè)備就緒全程占用處理器中斷驅(qū)動(dòng)是設(shè)備準(zhǔn)備好一個(gè)字節(jié)就中斷一次CPU 每次都參與數(shù)據(jù)搬運(yùn)好處是不用空轉(zhuǎn)DMA 是 CPU 只發(fā)一條命令把內(nèi)存地址、傳輸長(zhǎng)度告訴控制器剩下的搬運(yùn)由控制器直接和內(nèi)存打交道全部傳完才中斷一次。這里的常見(jiàn)誤解是把 DMA 當(dāng)成“讓磁盤(pán)變快”。DMA 省的是 CPU 搬運(yùn)數(shù)據(jù)的時(shí)間磁盤(pán)本身的機(jī)械尋道一點(diǎn)沒(méi)變快。區(qū)分這兩件事很重要I/O 響應(yīng)時(shí)間由磁盤(pán)決定CPU 占用率由控制方式?jīng)Q定題目問(wèn)哪個(gè)就答哪個(gè)。磁盤(pán)調(diào)度才是真正在減少尋道。FCFS 按請(qǐng)求順序服務(wù)公平但平均尋道距離大SSTF 每次選離當(dāng)前磁頭最近的請(qǐng)求平均尋道最短但遠(yuǎn)端請(qǐng)求可能永遠(yuǎn)等不到SCAN 像電梯一樣單向掃到端點(diǎn)再折返犧牲一點(diǎn)平均尋道換無(wú)饑餓。拿一組真實(shí)可算的數(shù)字對(duì)比磁頭當(dāng)前在 100 磁道請(qǐng)求序列是 55、58、39、18、90、160、150、38、184。SSTF 的走法是 100→90→58→55→39→38→18→150→160→184總移動(dòng) 248 個(gè)磁道。SCAN 假設(shè)向大號(hào)方向掃走法是 100→150→160→184→199→90→58→55→39→38→18總移動(dòng) 280 個(gè)磁道。有意思的是這里 SCAN 反而更差。這不是算錯(cuò)而是它揭示了 SCAN 的真實(shí)定位它優(yōu)化的是“最大等待時(shí)間”和“響應(yīng)方差”不是總移動(dòng)距離?；爻棠?109 個(gè)磁道是白跑的但正因?yàn)閽叩蕉它c(diǎn)遠(yuǎn)處的請(qǐng)求有一個(gè)可預(yù)期的等待上界。題目如果問(wèn)“平均尋道長(zhǎng)度最短”答案是 SSTF問(wèn)“不會(huì)饑餓”答案才輪到 SCAN。5. 排查清單五類(lèi)“看著會(huì)、一做就錯(cuò)”的翻車(chē)現(xiàn)場(chǎng)復(fù)習(xí)到后期卡住人的往往不是不懂而是懂了個(gè)大概然后在細(xì)節(jié)上翻車(chē)。下面五條是這類(lèi)筆記里反復(fù)出現(xiàn)、也最容易在考場(chǎng)上丟分的地方每條按現(xiàn)象、原因、解決三段寫(xiě)。5.1 同步與互斥PV 寫(xiě)反與初值給錯(cuò)第一條現(xiàn)象是 PV 操作能默寫(xiě)出來(lái)但推出執(zhí)行序列時(shí)發(fā)現(xiàn)兩個(gè)進(jìn)程互相等待。原因幾乎都是 P 操作的順序問(wèn)題一個(gè)進(jìn)程先 P 互斥量再 P 資源量另一個(gè)進(jìn)程占著資源等互斥量雙方各持一把鎖不放手。解決辦法是記住固定順序先 P 資源信號(hào)量、再 P 互斥信號(hào)量V 操作順序反過(guò)來(lái)。互斥量只保護(hù)臨界區(qū)資源量才代表“有沒(méi)有東西可用”先拿資源再進(jìn)臨界區(qū)邏輯上就不可能死鎖。第二條現(xiàn)象是生產(chǎn)者消費(fèi)者寫(xiě)出來(lái)以后兩個(gè)進(jìn)程變成完全串行一點(diǎn)并發(fā)都沒(méi)有。原因是把緩沖區(qū)計(jì)數(shù)當(dāng)成了互斥量empty和full的初值給成了 1?；コ庑盘?hào)量初值必須是 1表示臨界區(qū)只有一個(gè)入口empty的初值是緩沖區(qū)容量full的初值是 0它們代表的是資源數(shù)量而不是鎖。初值給錯(cuò)整個(gè)同步關(guān)系就退化成了互斥。5.2 計(jì)算題地址、時(shí)間、磁道三個(gè)易錯(cuò)位第三條現(xiàn)象是頁(yè)號(hào)頁(yè)內(nèi)偏移算出來(lái)跟答案差一位。原因是頁(yè)大小和位數(shù)的換算沒(méi)做熟4KB 就是 2 的 12 次方偏移 12 位十六進(jìn)制下正好是末三位。解決辦法是養(yǎng)成習(xí)慣見(jiàn)到十六進(jìn)制地址先數(shù)末三位當(dāng)偏移前面的當(dāng)頁(yè)號(hào)見(jiàn)到十進(jìn)制就先除以頁(yè)大小取整得頁(yè)號(hào)余數(shù)就是偏移別在腦子里做二進(jìn)制拆分。第四條現(xiàn)象是帶權(quán)周轉(zhuǎn)時(shí)間算出來(lái)比 1 還小。原因是分母寫(xiě)成了等待時(shí)間或周轉(zhuǎn)時(shí)間。帶權(quán)周轉(zhuǎn)時(shí)間的定義是周轉(zhuǎn)時(shí)間除以服務(wù)時(shí)間服務(wù)時(shí)間是進(jìn)程真正占用 CPU 的時(shí)長(zhǎng)任何進(jìn)程的這個(gè)比值都不會(huì)小于 1一旦算出小于 1立刻回頭檢查分母。第五條現(xiàn)象是磁盤(pán)調(diào)度總移動(dòng)道數(shù)比標(biāo)準(zhǔn)答案少一截。原因是從 0 號(hào)磁道或者第一個(gè)請(qǐng)求開(kāi)始算的。磁頭有一個(gè)初始位置所有移動(dòng)都必須從當(dāng)前位置起算用 SCAN 還要記得算到端點(diǎn)比如 199 號(hào)磁道的那一段這段路雖然不服務(wù)任何請(qǐng)求但它真實(shí)發(fā)生了。做題時(shí)先把磁頭位置和請(qǐng)求序列抄在草稿紙最上面畫(huà)一條數(shù)軸標(biāo)出來(lái)比在腦子里空想靠譜得多。6. 從“記住結(jié)論”到“能自己推”一套可驗(yàn)證的自檢模型這份筆記真正有用的地方不在于它把五章內(nèi)容壓成了幾十頁(yè)而在于它給出了一套可以反復(fù)自檢的框架。我在看這類(lèi)材料時(shí)習(xí)慣把每一章都?jí)嚎s成三個(gè)問(wèn)題這個(gè)資源有哪幾個(gè)狀態(tài)誰(shuí)有權(quán)改這些狀態(tài)改一次的代價(jià)是什么。進(jìn)程那一章?tīng)顟B(tài)是就緒、運(yùn)行、等待改狀態(tài)的是調(diào)度器和進(jìn)程自己代價(jià)是上下文切換內(nèi)存那一章?tīng)顟B(tài)是頁(yè)在不在內(nèi)存、臟不臟改狀態(tài)的是缺頁(yè)處理和置換算法代價(jià)是一次磁盤(pán) I/O文件那一章?tīng)顟B(tài)是塊分配了沒(méi)有、索引到不到位改狀態(tài)的是文件系統(tǒng)和緩存代價(jià)是尋道加傳輸。這三個(gè)問(wèn)題的價(jià)值在于它把“背結(jié)論”變成了“推結(jié)論”。比如頁(yè)大小為什么是 4KB按這個(gè)框架推頁(yè)小則頁(yè)表項(xiàng)多、TLB 覆蓋范圍小、缺頁(yè)頻繁頁(yè)大則內(nèi)碎片多、一次缺頁(yè)搬運(yùn)的數(shù)據(jù)多。兩邊都有代價(jià)所以只能取中間值具體數(shù)字是工程調(diào)出來(lái)的但“為什么必須折中”是可以推的。同理索引結(jié)構(gòu)為什么要有直接塊和三級(jí)間接也是同一個(gè)推法。驗(yàn)證方法也很樸素拿一個(gè)具體例子手算一遍再和筆記對(duì)照。算一道 SJF 的周轉(zhuǎn)時(shí)間算一次兩級(jí)頁(yè)表的地址拆分算一遍 SCAN 的磁道總數(shù)手算過(guò)的東西和看過(guò)的東西在考場(chǎng)上完全是兩個(gè)狀態(tài)。我吃過(guò)這個(gè)虧筆記看得滾瓜爛熟一到手算地址翻譯就卡在十六進(jìn)制換位上那道題的分丟得毫無(wú)技術(shù)含量。從那以后我每次看這類(lèi)知識(shí)點(diǎn)梳理都會(huì)強(qiáng)迫自己先合上筆記把狀態(tài)遷移圖畫(huà)一遍、把關(guān)鍵參數(shù)算一遍再翻回去對(duì)答案對(duì)不上的地方才是真正要補(bǔ)的洞。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取