簡(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)度六部分展開覆蓋進(jìn)程狀態(tài)與PCB、先來先服務(wù)與短作業(yè)優(yōu)先等調(diào)度算法、同步互斥與PV操作、固定分區(qū)與分頁分段、虛擬內(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)考的從來不是概念而是狀態(tài)遷移的邊界翻過一份把操作系統(tǒng)壓成幾十頁的手寫掃描筆記最反直覺的地方在于進(jìn)程、內(nèi)存、文件、設(shè)備看上去是四套獨(dú)立知識(shí)實(shí)際上卻對(duì)應(yīng)同一套記賬邏輯——資源有狀態(tài)狀態(tài)只能沿合法邊界遷移考題和真實(shí)內(nèi)核出問題的地方都集中在邊界上。801 這類自命題科目真正愛考的是“進(jìn)程在等 I/O 時(shí)被調(diào)度走誰保存了它當(dāng)時(shí)的現(xiàn)場(chǎng)”這類問題而“什么是 PCB”這種表層問題并非重點(diǎn)。把這套賬理順之后需要背誦的內(nèi)容會(huì)減少一大半剩下的內(nèi)容基本都能自己推導(dǎo)出來。2. 進(jìn)程與 PCB為什么“狀態(tài)”必須落進(jìn)一個(gè)結(jié)構(gòu)體里大多數(shù)人對(duì)進(jìn)程的理解停留在“程序的一次執(zhí)行”這句話沒錯(cuò)但幾乎不解決問題。真正讓人算錯(cuò)題、也真正讓內(nèi)核寫出 bug 的是狀態(tài)機(jī)的邊和 PCB 的字段筆記如果只畫了五個(gè)方框和箭頭卻沒有說明哪條邊是誰觸發(fā)的后面調(diào)度、同步、死鎖就會(huì)全部只能靠背。這一章把這三樣拆開看狀態(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)程退出。最容易被畫錯(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)存緊張”“換出”那考的是掛起只說“等待 I/O”那是阻塞。2.2 PCB內(nèi)核里唯一信得過的現(xiàn)場(chǎng)記錄進(jìn)程切換的本質(zhì)是“把一套 CPU 寄存器換掉再把另一套裝進(jìn)來”。CPU 只有一套物理寄存器被切走的進(jìn)程的所有現(xiàn)場(chǎng)必須有個(gè)地方存這個(gè)地方就是 PCB它也是內(nèi)核態(tài)數(shù)據(jù)用戶態(tài)代碼碰不到。/* 極度簡(jiǎn)化的 PCB 模型字段取自教科書常見劃分不代表任何真實(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; /* 頁表基址這個(gè)進(jìn)程地址空間的身份 */ int priority; /* 調(diào)度優(yōu)先級(jí)多級(jí)反饋隊(duì)列里會(huì)被動(dòng)態(tài)改寫 */ 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)沒有它們進(jìn)程被切走后回來就不知道執(zhí)行到哪了這就是操作系統(tǒng)的“后悔藥”。pgtbl決定了切換的代價(jià)量級(jí)同一地址空間內(nèi)的線程切換不用換它進(jìn)程切換要換而換頁表往往伴隨 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ì)反過來改數(shù)據(jù)結(jié)構(gòu)”的字段老化機(jī)制就是不停給它減分。為什么 PCB 必須放在內(nèi)核態(tài)、用戶不可寫道理和虛擬內(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ì)列攤開看它們的骨架完全一樣一個(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誰先來誰先跑pick 只看到達(dá)時(shí)間 fcfs lambda q: min(q, keylambda p: p.arrive) # SJF誰短誰先跑pick 只看服務(wù)時(shí)間 sjf lambda q: min(q, keylambda p: p.burst)參數(shù)含義需要說清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)上最常見的失分點(diǎn)。把pick換成max就是優(yōu)先級(jí)調(diào)度換成“剩余時(shí)間最短”并允許打斷就是 SRTF。三種策略的設(shè)計(jì)動(dòng)機(jī)值得逐條說。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í)中沒人知道下一個(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)性換無饑餓。多級(jí)反饋隊(duì)列是這三種思路的折中方案也是我認(rèn)為最值得琢磨的設(shè)計(jì)新進(jìn)程進(jìn)最高優(yōu)先級(jí)隊(duì)列給一個(gè)很短的第一個(gè)時(shí)間片用完沒結(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ù)沒法從理論上定隊(duì)列級(jí)數(shù)和每級(jí)時(shí)間片長(zhǎng)度都是靠測(cè)量調(diào)出來的這也是它經(jīng)常被吐槽為“玄學(xué)”的原因。2.4 上下文切換真正貴的是冷卻不是保存很多人默認(rèn)進(jìn)程切換昂貴、線程切換廉價(jià)然后拿這句話去解釋所有性能問題。這句話只在特定前提下成立。直接開銷是保存恢復(fù)寄存器、切換內(nèi)核棧、更新 PCB 狀態(tài)這部分對(duì)進(jìn)程和線程差不多量級(jí)很小。真正的差距在地址空間進(jìn)程切換要換頁表基址TLB 里緩存的地址翻譯全部作廢Cache 里的數(shù)據(jù)也大面積失效回到用戶態(tài)后要重新預(yù)熱。我一般會(huì)這么理解切換成本由“換不換地址空間”決定不由“是不是線程”決定。同一個(gè)進(jìn)程里兩個(gè)線程如果跑在不同核上、訪問的數(shù)據(jù)八竿子打不著Cache 該失效還是失效反過來如果兩個(gè)進(jìn)程共享大量?jī)?nèi)存頁切換后的預(yù)熱代價(jià)也沒那么夸張?？吹健岸嚅_線程更快”這種結(jié)論先問一句快在哪是切換省了還是并發(fā)度上去了。3. 虛擬內(nèi)存為什么邏輯地址必須和物理地址解耦分頁這件事教材上一句話就能說完把邏輯地址空間切成固定大小的頁映射到物理頁框。但真正理解了以后你會(huì)發(fā)現(xiàn)虛擬內(nèi)存解決的從來不是“內(nèi)存不夠”而是三個(gè)更棘手的問題進(jìn)程之間不能互相踩內(nèi)存、程序不能依賴自己被加載到哪個(gè)物理位置、內(nèi)存可以比物理內(nèi)存小。這一章沿著一次地址翻譯的全過程走把頁表項(xiàng)、缺頁、置換算法串起來。3.1 一次地址翻譯的完整旅程CPU 執(zhí)行一條訪存指令發(fā)出的是邏輯地址。MMU 把它切成兩部分低位是頁內(nèi)偏移高位是頁號(hào)。先查 TLB命中就直接拼出物理地址發(fā)到總線上沒命中就去查頁表多級(jí)頁表要一級(jí)一級(jí)往下走每一級(jí)都取一次內(nèi)存如果最后拿到的頁表項(xiàng)有效位是 0觸發(fā)缺頁異?？刂茩?quán)交給內(nèi)核。舉一個(gè)能落地的例子32 位地址、頁大小 4KB。4KB 等于 2 的 12 次方所以低 12 位是頁內(nèi)偏移剩下 20 位是頁號(hào)。要是用兩級(jí)頁表每級(jí) 10 位一個(gè)地址0x00403A20拆出來就是一級(jí)索引0x001、二級(jí)索引0x003、偏移0xA20。十六進(jìn)制下這個(gè)拆分特別好做頁大小 4KB 時(shí)最后三位十六進(jìn)制數(shù)字就是偏移前面全是頁號(hào)考場(chǎng)上不用換算成二進(jìn)制。多級(jí)頁表的設(shè)計(jì)動(dòng)機(jī)常被講成“節(jié)省空間”其實(shí)更準(zhǔn)確的說法是應(yīng)對(duì)稀疏地址空間。單級(jí)頁表要給 20 位頁號(hào)建 2 的 20 次方個(gè)表項(xiàng)每項(xiàng) 4 字節(jié)就是 4MB每個(gè)進(jìn)程一份而且這 4MB 必須常駐可一個(gè)進(jìn)程實(shí)際用到的地址往往只集中在幾個(gè)區(qū)域中間大片是空的。兩級(jí)頁表把一級(jí)頁表壓到 4KB二級(jí)頁表按需創(chuàng)建沒用到的那段地址連二級(jí)頁表都不用建。注意多級(jí)頁表省的是空間代價(jià)是時(shí)間。一次 TLB 未命中可能要訪存兩次甚至四次這也是 TLB 命中率對(duì)性能影響這么大的原因。3.2 頁表項(xiàng)里每一位在干什么頁表項(xiàng)不是只存一個(gè)物理頁框號(hào)它是一組標(biāo)志位加一個(gè)編號(hào)。有效位表示這一頁是否在內(nèi)存里為 0 就觸發(fā)缺頁保護(hù)位標(biāo)記這一頁可讀、可寫還是可執(zhí)行寫一個(gè)只讀頁會(huì)觸發(fā)保護(hù)異常而不是缺頁這兩類異常的處理路徑完全不同修改位臟位表示這一頁被寫過沒有它決定了換出時(shí)要不要寫回磁盤這是純性能優(yōu)化沒寫過就不用寫回訪問位表示這一頁最近被訪問過它是 Clock 置換算法的唯一輸入。這幾位里臟位的性價(jià)比最高。操作系統(tǒng)在頁面換出時(shí)如果臟位是 0直接把頁框回收就行臟位是 1就得先寫磁盤再回收一次 I/O 的時(shí)間夠 CPU 跑幾十萬條指令。所以“讀多寫少”的映射文件、代碼段換出成本遠(yuǎn)低于被頻繁寫的堆內(nèi)存。3.3 LRU 為什么在硬件里做不出來Clock 怎么近似理論上最優(yōu)的置換算法是換掉未來最久不會(huì)被訪問的那一頁這顯然無法實(shí)現(xiàn)退一步換掉過去最久沒被訪問的那頁就是 LRU。LRU 在軟件里好寫在硬件里幾乎做不了它要求每次訪存都更新時(shí)間戳或調(diào)整鏈表這個(gè)開銷比訪存本身還大而且要在 MMU 里實(shí)現(xiàn)沒法靠編譯器優(yōu)化。硬件只能提供一個(gè)訪問位。Clock 算法就把所有頁框串成一個(gè)環(huán)配一個(gè)指針需要換頁時(shí)看指針指向的頁訪問位是 1 就清成 0 并跳過是 0 就選它換出。這個(gè)“給一次免死機(jī)會(huì)”的動(dòng)作本質(zhì)是用一個(gè) bit 近似“最近有沒有被訪問”工程上夠用。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)來的頁 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ù)變多缺頁反而增加 print(lru(refs, 3), lru(refs, 4)) # 10 8棧式算法不會(huì)反常這段代碼里refs是頁面訪問序列frames是可用頁框數(shù)返回值是缺頁次數(shù)。fifo用一個(gè)普通列表模擬先進(jìn)先出隊(duì)列l(wèi)ru用OrderedDict維護(hù)訪問順序命中就move_to_end挪到隊(duì)尾淘汰時(shí)彈隊(duì)頭。第三行輸出就是著名的 Belady 異常FIFO 在 4 個(gè)頁框時(shí)缺頁次數(shù)比 3 個(gè)頁框還多。原因是 FIFO 不滿足“棧式算法”性質(zhì)增加頁框會(huì)改變整個(gè)淘汰歷史可能剛好把后面要用的頁提前踢掉。LRU 和最優(yōu)算法都是棧式的小容量的駐留集永遠(yuǎn)是大容量的子集所以不會(huì)出現(xiàn)這種反常。這也是為什么教材強(qiáng)調(diào)這個(gè)反例它說明“加內(nèi)存一定變快”這種直覺在置換策略上是站不住的。3.4 內(nèi)碎片和外碎片分頁為什么沒有外碎片分頁的代價(jià)是內(nèi)部碎片進(jìn)程最后一頁大概率裝不滿平均浪費(fèi)半頁。但分頁完全沒有外部碎片因?yàn)樗许摽虼笮∫恢氯我饪臻e頁框都能裝任意頁不存在“洞太小塞不進(jìn)去”的情況。分段正好相反段是邏輯單位長(zhǎng)度由程序決定一段代碼、一段數(shù)據(jù)、一個(gè)棧大小參差不齊。分配久了就會(huì)在內(nèi)存里留下大量小空洞總量夠但拼不出一個(gè)連續(xù)的大段這就是外部碎片解決辦法是緊湊把進(jìn)程整體挪動(dòng)把空洞擠到一起代價(jià)是搬運(yùn)開銷。段頁式是兩者的組合先按邏輯分成段每段再分頁邏輯結(jié)構(gòu)保住了物理分配也整齊了代價(jià)是一次訪存要查段表再查頁表地址翻譯路徑更長(zhǎng)。頁大小 4KB 是一個(gè)經(jīng)典的折中頁太小則頁表項(xiàng)數(shù)量爆炸、TLB 能覆蓋的范圍變小頁太大則內(nèi)碎片浪費(fèi)加劇、一次缺頁要讀的數(shù)據(jù)變多。這個(gè)數(shù)值不是理論最優(yōu)而是幾十年工程實(shí)踐調(diào)出來的平衡點(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à)是訪問最后一個(gè)塊要多讀幾次間接塊每一次都是實(shí)打?qū)嵉?I/O。這本質(zhì)上是“小文件快、大文件能裝”的折中而不是追求兩種都最優(yōu)。4.2 三種物理結(jié)構(gòu)的取舍順序結(jié)構(gòu)把文件放在連續(xù)塊上尋道最少、支持隨機(jī)訪問缺點(diǎn)是兩個(gè)外部碎片以及文件增長(zhǎng)時(shí)后面可能沒位置了只能整體搬家。鏈接結(jié)構(gòu)把文件切成塊用指針串起來沒有碎片、隨便增長(zhǎng)但只能順序訪問想讀最后一塊得從頭走一遍而且指針占空間中間一個(gè)塊壞了整條鏈就斷。索引結(jié)構(gòu)給每個(gè)文件配索引塊索引塊里存所有塊的地址隨機(jī)訪問和增長(zhǎng)都支持代價(jià)是多了一層索引塊開銷小文件可能為了幾百字節(jié)專門占一個(gè)索引塊。FAT 是鏈接結(jié)構(gòu)的一個(gè)變體把整條鏈的指針集中到內(nèi)存里的一張表尋道時(shí)查表就行本質(zhì)上是用內(nèi)存換訪問速度。這三種結(jié)構(gòu)沒有絕對(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ù)空間就得遍歷。成組鏈接是折中方案把空閑塊按組串起來每組的第一塊記錄下一組的塊號(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)存打交道全部傳完才中斷一次。這里的常見誤解是把 DMA 當(dāng)成“讓磁盤變快”。DMA 省的是 CPU 搬運(yùn)數(shù)據(jù)的時(shí)間磁盤本身的機(jī)械尋道一點(diǎn)沒變快。區(qū)分這兩件事很重要I/O 響應(yīng)時(shí)間由磁盤決定CPU 占用率由控制方式?jīng)Q定題目問哪個(gè)就答哪個(gè)。磁盤調(diào)度才是真正在減少尋道。FCFS 按請(qǐng)求順序服務(wù)公平但平均尋道距離大SSTF 每次選離當(dāng)前磁頭最近的請(qǐng)求平均尋道最短但遠(yuǎn)端請(qǐng)求可能永遠(yuǎn)等不到SCAN 像電梯一樣單向掃到端點(diǎn)再折返犧牲一點(diǎn)平均尋道換無饑餓。拿一組真實(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ù)期的等待上界。題目如果問“平均尋道長(zhǎng)度最短”答案是 SSTF問“不會(huì)饑餓”答案才輪到 SCAN。5. 排查清單五類“看著會(huì)、一做就錯(cuò)”的翻車現(xiàn)場(chǎng)復(fù)習(xí)到后期卡住人的往往不是不懂而是懂了個(gè)大概然后在細(xì)節(jié)上翻車。下面五條是這類筆記里反復(fù)出現(xiàn)、也最容易在考場(chǎng)上丟分的地方每條按現(xiàn)象、原因、解決三段寫。5.1 同步與互斥PV 寫反與初值給錯(cuò)第一條現(xiàn)象是 PV 操作能默寫出來但推出執(zhí)行序列時(shí)發(fā)現(xiàn)兩個(gè)進(jìn)程互相等待。原因幾乎都是 P 操作的順序問題一個(gè)進(jìn)程先 P 互斥量再 P 資源量另一個(gè)進(jìn)程占著資源等互斥量雙方各持一把鎖不放手。解決辦法是記住固定順序先 P 資源信號(hào)量、再 P 互斥信號(hào)量V 操作順序反過來?；コ饬恐槐Ｗo(hù)臨界區(qū)資源量才代表“有沒有東西可用”先拿資源再進(jìn)臨界區(qū)邏輯上就不可能死鎖。第二條現(xiàn)象是生產(chǎn)者消費(fèi)者寫出來以后兩個(gè)進(jìn)程變成完全串行一點(diǎn)并發(fā)都沒有。原因是把緩沖區(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)象是頁號(hào)頁內(nèi)偏移算出來跟答案差一位。原因是頁大小和位數(shù)的換算沒做熟4KB 就是 2 的 12 次方偏移 12 位十六進(jìn)制下正好是末三位。解決辦法是養(yǎng)成習(xí)慣見到十六進(jìn)制地址先數(shù)末三位當(dāng)偏移前面的當(dāng)頁號(hào)見到十進(jìn)制就先除以頁大小取整得頁號(hào)余數(shù)就是偏移別在腦子里做二進(jìn)制拆分。第四條現(xiàn)象是帶權(quán)周轉(zhuǎn)時(shí)間算出來比 1 還小。原因是分母寫成了等待時(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)求開始算的。磁頭有一個(gè)初始位置所有移動(dòng)都必須從當(dāng)前位置起算用 SCAN 還要記得算到端點(diǎn)比如 199 號(hào)磁道的那一段這段路雖然不服務(wù)任何請(qǐng)求但它真實(shí)發(fā)生了。做題時(shí)先把磁頭位置和請(qǐng)求序列抄在草稿紙最上面畫一條數(shù)軸標(biāo)出來比在腦子里空想靠譜得多。6. 從“記住結(jié)論”到“能自己推”一套可驗(yàn)證的自檢模型這份筆記真正有用的地方不在于它把五章內(nèi)容壓成了幾十頁而在于它給出了一套可以反復(fù)自檢的框架。我在看這類材料時(shí)習(xí)慣把每一章都?jí)嚎s成三個(gè)問題這個(gè)資源有哪幾個(gè)狀態(tài)誰有權(quán)改這些狀態(tài)改一次的代價(jià)是什么。進(jìn)程那一章狀態(tài)是就緒、運(yùn)行、等待改狀態(tài)的是調(diào)度器和進(jìn)程自己代價(jià)是上下文切換內(nèi)存那一章狀態(tài)是頁在不在內(nèi)存、臟不臟改狀態(tài)的是缺頁處理和置換算法代價(jià)是一次磁盤 I/O文件那一章狀態(tài)是塊分配了沒有、索引到不到位改狀態(tài)的是文件系統(tǒng)和緩存代價(jià)是尋道加傳輸。這三個(gè)問題的價(jià)值在于它把“背結(jié)論”變成了“推結(jié)論”。比如頁大小為什么是 4KB按這個(gè)框架推頁小則頁表項(xiàng)多、TLB 覆蓋范圍小、缺頁頻繁頁大則內(nèi)碎片多、一次缺頁搬運(yùn)的數(shù)據(jù)多。兩邊都有代價(jià)所以只能取中間值具體數(shù)字是工程調(diào)出來的但“為什么必須折中”是可以推的。同理索引結(jié)構(gòu)為什么要有直接塊和三級(jí)間接也是同一個(gè)推法。驗(yàn)證方法也很樸素拿一個(gè)具體例子手算一遍再和筆記對(duì)照。算一道 SJF 的周轉(zhuǎn)時(shí)間算一次兩級(jí)頁表的地址拆分算一遍 SCAN 的磁道總數(shù)手算過的東西和看過的東西在考場(chǎng)上完全是兩個(gè)狀態(tài)。我吃過這個(gè)虧筆記看得滾瓜爛熟一到手算地址翻譯就卡在十六進(jìn)制換位上那道題的分丟得毫無技術(shù)含量。從那以后我每次看這類知識(shí)點(diǎn)梳理都會(huì)強(qiáng)迫自己先合上筆記把狀態(tài)遷移圖畫一遍、把關(guān)鍵參數(shù)算一遍再翻回去對(duì)答案對(duì)不上的地方才是真正要補(bǔ)的洞。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取