簡(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專業(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 這類自命題科目真正愛(ài)考的是“進(jìn)程在等 I/O 時(shí)被調(diào)度走誰(shuí)保存了它當(dāng)時(shí)的現(xiàn)場(chǎng)”這類問(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í)行”這句話沒(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 完成這類阻塞叫自愿阻塞等待到就緒由外部事件完成后喚醒運(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ù)用戶態(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)的線程切換不用換它進(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)、用戶不可寫(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è)所以優(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)程切換昂貴、線程切換廉價(jià)然后拿這句話去解釋所有性能問(wèn)題。這句話只在特定前提下成立。直接開(kāi)銷是保存恢復(fù)寄存器、切換內(nèi)核棧、更新 PCB 狀態(tài)這部分對(duì)進(jìn)程和線程差不多量級(jí)很小。真正的差距在地址空間進(jìn)程切換要換頁(yè)表基址TLB 里緩存的地址翻譯全部作廢Cache 里的數(shù)據(jù)也大面積失效回到用戶態(tài)后要重新預(yù)熱。我一般會(huì)這么理解切換成本由“換不換地址空間”決定不由“是不是線程”決定。同一個(gè)進(jìn)程里兩個(gè)線程如果跑在不同核上、訪問(wèn)的數(shù)據(jù)八竿子打不著Cache 該失效還是失效反過(guò)來(lái)如果兩個(gè)進(jìn)程共享大量?jī)?nèi)存頁(yè)切換后的預(yù)熱代價(jià)也沒(méi)那么夸張。看到“多開(kāi)線程更快”這種結(jié)論先問(wèn)一句快在哪是切換省了還是并發(fā)度上去了。3. 虛擬內(nèi)存為什么邏輯地址必須和物理地址解耦分頁(yè)這件事教材上一句話就能說(shuō)完把邏輯地址空間切成固定大小的頁(yè)映射到物理頁(yè)框。但真正理解了以后你會(huì)發(fā)現(xiàn)虛擬內(nèi)存解決的從來(lái)不是“內(nèi)存不夠”而是三個(gè)更棘手的問(wèn)題進(jìn)程之間不能互相踩內(nèi)存、程序不能依賴自己被加載到哪個(gè)物理位置、內(nèi)存可以比物理內(nèi)存小。這一章沿著一次地址翻譯的全過(guò)程走把頁(yè)表項(xiàng)、缺頁(yè)、置換算法串起來(lái)。3.1 一次地址翻譯的完整旅程CPU 執(zhí)行一條訪存指令發(fā)出的是邏輯地址。MMU 把它切成兩部分低位是頁(yè)內(nèi)偏移高位是頁(yè)號(hào)。先查 TLB命中就直接拼出物理地址發(fā)到總線上沒(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 未命中可能要訪存兩次甚至四次這也是 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è)這兩類異常的處理路徑完全不同修改位臟位表示這一頁(yè)被寫(xiě)過(guò)沒(méi)有它決定了換出時(shí)要不要寫(xiě)回磁盤這是純性能優(yōu)化沒(méi)寫(xiě)過(guò)就不用寫(xiě)回訪問(wèn)位表示這一頁(yè)最近被訪問(wèn)過(guò)它是 Clock 置換算法的唯一輸入。這幾位里臟位的性價(jià)比最高。操作系統(tǒng)在頁(yè)面換出時(shí)如果臟位是 0直接把頁(yè)框回收就行臟位是 1就得先寫(xiě)磁盤再回收一次 I/O 的時(shí)間夠 CPU 跑幾十萬(wàn)條指令。所以“讀多寫(xiě)少”的映射文件、代碼段換出成本遠(yuǎn)低于被頻繁寫(xiě)的堆內(nèi)存。3.3 LRU 為什么在硬件里做不出來(lái)Clock 怎么近似理論上最優(yōu)的置換算法是換掉未來(lái)最久不會(huì)被訪問(wèn)的那一頁(yè)這顯然無(wú)法實(shí)現(xiàn)退一步換掉過(guò)去最久沒(méi)被訪問(wèn)的那頁(yè)就是 LRU。LRU 在軟件里好寫(xiě)在硬件里幾乎做不了它要求每次訪存都更新時(shí)間戳或調(diào)整鏈表這個(gè)開(kāi)銷比訪存本身還大而且要在 MMU 里實(shí)現(xiàn)沒(méi)法靠編譯器優(yōu)化。硬件只能提供一個(gè)訪問(wèn)位。Clock 算法就把所有頁(yè)框串成一個(gè)環(huán)配一個(gè)指針需要換頁(yè)時(shí)看指針指向的頁(yè)訪問(wèn)位是 1 就清成 0 并跳過(guò)是 0 就選它換出。這個(gè)“給一次免死機(jī)會(huì)”的動(dòng)作本質(zhì)是用一個(gè) bit 近似“最近有沒(méi)有被訪問(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è)面訪問(wèn)序列frames是可用頁(yè)框數(shù)返回值是缺頁(yè)次數(shù)。fifo用一個(gè)普通列表模擬先進(jìn)先出隊(duì)列l(wèi)ru用OrderedDict維護(hù)訪問(wèn)順序命中就move_to_end挪到隊(duì)尾淘汰時(shí)彈隊(duì)頭。第三行輸出就是著名的 Belady 異常FIFO 在 4 個(gè)頁(yè)框時(shí)缺頁(yè)次數(shù)比 3 個(gè)頁(yè)框還多。原因是 FIFO 不滿足“棧式算法”性質(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è)大概率裝不滿平均浪費(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)銷。段頁(yè)式是兩者的組合先按邏輯分成段每段再分頁(yè)邏輯結(jié)構(gòu)保住了物理分配也整齊了代價(jià)是一次訪存要查段表再查頁(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 和磁盤調(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 : 磁盤塊大小字節(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à)是訪問(wèn)最后一個(gè)塊要多讀幾次間接塊每一次都是實(shí)打?qū)嵉?I/O。這本質(zhì)上是“小文件快、大文件能裝”的折中而不是追求兩種都最優(yōu)。4.2 三種物理結(jié)構(gòu)的取舍順序結(jié)構(gòu)把文件放在連續(xù)塊上尋道最少、支持隨機(jī)訪問(wèn)缺點(diǎn)是兩個(gè)外部碎片以及文件增長(zhǎng)時(shí)后面可能沒(méi)位置了只能整體搬家。鏈接結(jié)構(gòu)把文件切成塊用指針串起來(lái)沒(méi)有碎片、隨便增長(zhǎng)但只能順序訪問(wèn)想讀最后一塊得從頭走一遍而且指針占空間中間一個(gè)塊壞了整條鏈就斷。索引結(jié)構(gòu)給每個(gè)文件配索引塊索引塊里存所有塊的地址隨機(jī)訪問(wèn)和增長(zhǎng)都支持代價(jià)是多了一層索引塊開(kāi)銷小文件可能為了幾百字節(jié)專門占一個(gè)索引塊。FAT 是鏈接結(jié)構(gòu)的一個(gè)變體把整條鏈的指針集中到內(nèi)存里的一張表尋道時(shí)查表就行本質(zhì)上是用內(nèi)存換訪問(wèn)速度。這三種結(jié)構(gòu)沒(méi)有絕對(duì)優(yōu)劣選哪個(gè)取決于“這個(gè)文件系統(tǒng)主要跑什么負(fù)載”日志類順序?qū)懚嘤面溄幼凅w數(shù)據(jù)庫(kù)類隨機(jī)讀多用索引。4.3 空閑空間管理位圖與成組鏈接位圖用 1 bit 標(biāo)記一個(gè)塊是否被占用查找連續(xù)的空閑塊特別快因?yàn)檫B續(xù)的 bit 可以一次掃描一大片。代價(jià)是占空間1TB 磁盤、4KB 塊一共 2 億多個(gè)塊位圖就是 32MB 左右這部分通常常駐內(nèi)存?？臻e鏈表把空閑塊本身串成鏈幾乎不額外占空間但想找一段連續(xù)空間就得遍歷。成組鏈接是折中方案把空閑塊按組串起來(lái)每組的第一塊記錄下一組的塊號(hào)和數(shù)量分配時(shí)一次能拿到一批既省空間又不用全程遍歷。這幾種方案的取舍都能用一句話概括拿空間換查找速度還是拿查找速度換空間。4.4 DMA 到底省了什么磁盤調(diào)度又在省什么I/O 控制方式有三種。程序查詢是 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)成“讓磁盤變快”。DMA 省的是 CPU 搬運(yùn)數(shù)據(jù)的時(shí)間磁盤本身的機(jī)械尋道一點(diǎn)沒(méi)變快。區(qū)分這兩件事很重要I/O 響應(yīng)時(shí)間由磁盤決定CPU 占用率由控制方式?jīng)Q定題目問(wèn)哪個(gè)就答哪個(gè)。磁盤調(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. 排查清單五類“看著會(huì)、一做就錯(cuò)”的翻車現(xiàn)場(chǎng)復(fù)習(xí)到后期卡住人的往往不是不懂而是懂了個(gè)大概然后在細(xì)節(jié)上翻車。下面五條是這類筆記里反復(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)?；コ饬恐槐Ｗo(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)象是磁盤調(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ù)自檢的框架。我在看這類材料時(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à)是一次磁盤 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ù)含量。從那以后我每次看這類知識(shí)點(diǎn)梳理都會(huì)強(qiáng)迫自己先合上筆記把狀態(tài)遷移圖畫(huà)一遍、把關(guān)鍵參數(shù)算一遍再翻回去對(duì)答案對(duì)不上的地方才是真正要補(bǔ)的洞。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取