簡(jiǎn)介本資源是桂林電子科技大學(xué)《操作系統(tǒng)》課程期末復(fù)習(xí)專用手寫筆記面向計(jì)算機(jī)及相關(guān)專業(yè)本科生聚焦核心考點(diǎn)梳理與應(yīng)試提分。筆記內(nèi)容覆蓋操作系統(tǒng)基本概念、進(jìn)程管理三態(tài)模型、調(diào)度算法、同步與死鎖、存儲(chǔ)管理分區(qū)/分頁(yè)/分段、頁(yè)面置換算法、文件管理目錄結(jié)構(gòu)、物理組織、索引方式及設(shè)備管理緩沖、虛擬設(shè)備等全模塊重點(diǎn)特別標(biāo)注高頻考點(diǎn)如銀行家算法、快表命中計(jì)算、多重索引地址轉(zhuǎn)換與避坑提示如‘不考’‘偏輕’類說明便于高效沖刺。資源為單個(gè)PDF文件大小4.47MB排版清晰、手寫批注豐富適合作為教材補(bǔ)充與考前速查資料。目前已有544人學(xué)習(xí)下載內(nèi)容源自真實(shí)課堂筆記邏輯連貫、術(shù)語(yǔ)準(zhǔn)確、例題穿插助力系統(tǒng)回顧與難點(diǎn)突破。1. 桂電操作系統(tǒng)期末復(fù)習(xí)手寫筆記一張覆蓋6大核心模塊、直擊23個(gè)高頻考點(diǎn)與11處易翻車陷阱的知識(shí)地圖這份《桂電操作系統(tǒng)期末復(fù)習(xí)手寫筆記.pdf》不是零散知識(shí)點(diǎn)堆砌而是一張高度凝練、考頻精準(zhǔn)、錯(cuò)點(diǎn)明確的“應(yīng)試型知識(shí)地圖”。它把操作系統(tǒng)這門課拆解為進(jìn)程管理15分、存儲(chǔ)管理30分、文件系統(tǒng)15分、設(shè)備管理10分、死鎖與同步25分、處理器基礎(chǔ)5分六大權(quán)重模塊其中存儲(chǔ)管理占比最高、文件系統(tǒng)結(jié)構(gòu)最細(xì)、死鎖計(jì)算最易失分——這和多數(shù)高校期末命題規(guī)律高度吻合。筆記用“☆”標(biāo)出必考題型如銀行家算法、頁(yè)面置換、多重索引尋址用“不考”“偏輕”“☆不考”等短語(yǔ)果斷過濾低頻內(nèi)容如線程細(xì)節(jié)、死鎖檢測(cè)算法把有限復(fù)習(xí)時(shí)間錨定在真題常駐區(qū)。適合兩類人一是已學(xué)完教材但抓不住重點(diǎn)的中階學(xué)習(xí)者需要一張能快速定位“哪里該停、哪里該沖”的導(dǎo)航圖二是考前72小時(shí)沖刺者需要一份能直接上手演算、對(duì)照自查、避開經(jīng)典坑位的實(shí)戰(zhàn)筆記。它不講原理推導(dǎo)不炫技術(shù)深度只回答一個(gè)問題這張卷子你到底要會(huì)哪23個(gè)具體動(dòng)作2. 進(jìn)程管理與調(diào)度三態(tài)模型、五種算法、四類時(shí)間指標(biāo)的閉環(huán)計(jì)算鏈2.1 進(jìn)程狀態(tài)轉(zhuǎn)換從用戶態(tài)/核心態(tài)切入理解“為什么不能亂跳”進(jìn)程狀態(tài)不是靜態(tài)標(biāo)簽而是由硬件中斷機(jī)制內(nèi)核權(quán)限控制共同驅(qū)動(dòng)的動(dòng)態(tài)閉環(huán)。筆記開篇即強(qiáng)調(diào)“用戶態(tài)只能運(yùn)行用戶程序非特權(quán)指令”這句話背后是CPU的特權(quán)級(jí)Ring 0–3設(shè)計(jì)用戶態(tài)Ring 3無法直接執(zhí)行in/out指令訪問I/O端口也無法修改頁(yè)表基址寄存器CR3所有越權(quán)操作都會(huì)觸發(fā)保護(hù)異常#GP由內(nèi)核接管。這就是“用戶態(tài)→核心態(tài)”必須通過系統(tǒng)調(diào)用、中斷或異常的底層原因。三態(tài)模型就緒、運(yùn)行、阻塞的轉(zhuǎn)換箭頭本質(zhì)是內(nèi)核對(duì)資源可用性的實(shí)時(shí)響應(yīng)就緒→運(yùn)行調(diào)度器選中加載PC/SP寄存器切換到用戶棧運(yùn)行→就緒時(shí)間片用盡觸發(fā)時(shí)鐘中斷保存現(xiàn)場(chǎng)入就緒隊(duì)列運(yùn)行→阻塞發(fā)起read()等阻塞系統(tǒng)調(diào)用內(nèi)核將PCB移入等待隊(duì)列調(diào)度新進(jìn)程提示考試中若出現(xiàn)“進(jìn)程從運(yùn)行態(tài)直接變?yōu)樾陆☉B(tài)”一定是錯(cuò)的——新建態(tài)New只在fork()創(chuàng)建子進(jìn)程時(shí)出現(xiàn)且僅持續(xù)極短時(shí)間分配PCB、初始化字段之后立即進(jìn)入就緒態(tài)。這是狀態(tài)機(jī)建模的基本約束。2.2 調(diào)度算法五種算法的計(jì)算邏輯、適用場(chǎng)景與得分關(guān)鍵點(diǎn)調(diào)度算法是計(jì)算題主力筆記明確列出5種必考類型并給出統(tǒng)一解題模板先畫Gantt圖 → 標(biāo)注每個(gè)進(jìn)程的到達(dá)時(shí)間AT、服務(wù)時(shí)間BT、完成時(shí)間CT、周轉(zhuǎn)時(shí)間T CT?AT、帶權(quán)周轉(zhuǎn)時(shí)間W T/BT→ 求平均值。每種算法的核心判據(jù)如下算法類型選擇依據(jù)關(guān)鍵限制典型失分點(diǎn)先來先服務(wù)FCFS到達(dá)時(shí)間最早非搶占式忽略“到達(dá)時(shí)間”排序誤按提交順序排短作業(yè)優(yōu)先SJF剩余服務(wù)時(shí)間最短非搶占式混淆“服務(wù)時(shí)間”與“剩余時(shí)間”未重排序列最短剩余時(shí)間優(yōu)先SRTF當(dāng)前剩余服務(wù)時(shí)間最短搶占式時(shí)間片切分錯(cuò)誤未在每個(gè)時(shí)間點(diǎn)重新比較剩余時(shí)間優(yōu)先級(jí)調(diào)度非搶占優(yōu)先級(jí)數(shù)值最小或最大需看題設(shè)非搶占式未聲明優(yōu)先級(jí)定義高數(shù)高優(yōu) or 低數(shù)高優(yōu)輪轉(zhuǎn)調(diào)度RR時(shí)間片輪轉(zhuǎn)超時(shí)即切換搶占式時(shí)間片邊界計(jì)算錯(cuò)誤如q4t0–3為第1片t4–7為第2片以SRTF為例某題給定進(jìn)程P1(AT0,BT8), P2(AT1,BT4), P3(AT2,BT9)t0P1運(yùn)行剩余7t1P2到達(dá)剩余4 7 → 搶占P1P2運(yùn)行t5P2完成此時(shí)P1剩余7, P3剩余9 → P1運(yùn)行t12P1完成P3運(yùn)行至t21最終CT[12,5,21], T[12,4,19], 平均T11.67。所有算法都必須嚴(yán)格按時(shí)間軸推進(jìn)不可跳躍假設(shè)。2.3 周轉(zhuǎn)時(shí)間相關(guān)指標(biāo)為什么“帶權(quán)周轉(zhuǎn)時(shí)間”才是公平性標(biāo)尺單純看周轉(zhuǎn)時(shí)間T會(huì)掩蓋長(zhǎng)作業(yè)對(duì)短作業(yè)的擠壓。例如FCFS下P1(BT1), P2(BT100)若P1先到則T11, T2101平均T51但若P2先到T1101, T2100平均T100.5——平均值失真。而帶權(quán)周轉(zhuǎn)時(shí)間WT/BT消除了服務(wù)時(shí)間量綱前者W11/11, W2101/1001.01, 平均W≈1.005后者W1101/1101, W2100/1001, 平均W51W值越接近1說明調(diào)度越公平?？荚囍腥粢蟆霸u(píng)價(jià)算法優(yōu)劣”必須同時(shí)給出平均T和平均W缺一不可。筆記在此處用紅筆標(biāo)注“只算T不寫W扣1分”。2.4 易錯(cuò)點(diǎn)進(jìn)程管理中4個(gè)被反復(fù)忽略的底層細(xì)節(jié)易漏點(diǎn)①用戶態(tài)/核心態(tài)切換必然伴隨棧切換為什么因?yàn)橛脩魲o權(quán)訪問內(nèi)核數(shù)據(jù)結(jié)構(gòu)。當(dāng)系統(tǒng)調(diào)用發(fā)生時(shí)CPU自動(dòng)將SS:ESP用戶棧指針壓入內(nèi)核棧并加載內(nèi)核棧段寄存器SS0和棧頂ESP0。若題目問“中斷處理時(shí)使用哪個(gè)?！贝稹皟?nèi)核棧”而非“當(dāng)前進(jìn)程?！薄Ｒ茁c(diǎn)②阻塞態(tài)進(jìn)程無法被調(diào)度器選中但可被信號(hào)喚醒阻塞態(tài)進(jìn)程不在就緒隊(duì)列中調(diào)度器遍歷就緒隊(duì)列時(shí)根本看不到它。但當(dāng)I/O完成設(shè)備驅(qū)動(dòng)會(huì)調(diào)用wake_up_process()將其PCB移入就緒隊(duì)列——這個(gè)動(dòng)作獨(dú)立于調(diào)度周期?？荚嚾魡枴白枞M(jìn)程何時(shí)能再次運(yùn)行”答“被喚醒后進(jìn)入就緒態(tài)等待下次調(diào)度”而非“時(shí)間片到時(shí)”。易漏點(diǎn)③進(jìn)程控制塊PCB是進(jìn)程存在的唯一標(biāo)志創(chuàng)建進(jìn)程分配PCB初始化字段PID、狀態(tài)、寄存器上下文、內(nèi)存映射等撤銷進(jìn)程回收PCB釋放資源。沒有PCB就沒有進(jìn)程。若題目說“父進(jìn)程退出后子進(jìn)程繼續(xù)運(yùn)行”必須指出“子進(jìn)程PCB仍存在被init進(jìn)程收養(yǎng)”。易漏點(diǎn)④系統(tǒng)調(diào)用號(hào)是內(nèi)核API的索引不是功能名sys_read、sys_write等函數(shù)名是內(nèi)核源碼標(biāo)識(shí)用戶層通過int 0x80x86或syscall指令系統(tǒng)調(diào)用號(hào)如__NR_read0觸發(fā)。考試若讓寫“讀文件的系統(tǒng)調(diào)用”答“read()庫(kù)函數(shù)最終觸發(fā)系統(tǒng)調(diào)用號(hào)0”而非“調(diào)用sys_read函數(shù)”。3. 死鎖與同步信號(hào)量建模、銀行家算法、哲學(xué)家進(jìn)餐的三層抽象3.1 信號(hào)量機(jī)制P/V操作如何精確控制臨界資源訪問信號(hào)量Semaphore是解決進(jìn)程同步的基石工具筆記強(qiáng)調(diào)其原子性、整型變量、阻塞隊(duì)列三大特性。sem_wait()P操作偽代碼為void sem_wait(sem_t *s) { while (s-value 0) { // 循環(huán)檢查非if add_current_to_queue(s); // 加入等待隊(duì)列 block(); // 主動(dòng)放棄CPU } s-value--; // 原子減1 }關(guān)鍵點(diǎn)在于P操作必須循環(huán)檢查busy-waiting而非單次判斷否則在多核環(huán)境下兩個(gè)進(jìn)程可能同時(shí)讀到value1均通過檢查導(dǎo)致value被減兩次變?yōu)?1破壞互斥性。V操作則相反void sem_post(sem_t *s) { s-value; // 原子加1 if (s-value 0) { // 有進(jìn)程在等 wake_up_one(s-queue); // 喚醒一個(gè) } }注意考試中若出現(xiàn)“信號(hào)量初值為1表示1個(gè)資源”這是錯(cuò)的——初值為1表示最多允許1個(gè)進(jìn)程進(jìn)入臨界區(qū)即實(shí)現(xiàn)互斥與資源數(shù)量無關(guān)。資源數(shù)由后續(xù)P/V次數(shù)決定。3.2 銀行家算法Need矩陣、Work向量、安全序列的手算全流程銀行家算法是死鎖避免的核心筆記用“蘋果過橋”類比橋是系統(tǒng)資源蘋果是進(jìn)程每個(gè)蘋果需聲明過橋所需木板數(shù)Max已拿木板數(shù)Allocation剩余需求數(shù)Need Max ? Allocation。算法步驟如下初始化Work Available當(dāng)前空閑資源向量找進(jìn)程Pi滿足Need[i] ≤ WorkPi能被滿足假設(shè)Pi完成Work Work Allocation[i]歸還資源重復(fù)2–3直到所有進(jìn)程被標(biāo)記或找不到滿足條件的Pi若全部標(biāo)記則存在安全序列否則系統(tǒng)不安全例系統(tǒng)有3類資源A,B,CAvailable[3,3,2]4個(gè)進(jìn)程進(jìn)程MaxAllocationNeedP0[7,5,3][0,1,0][7,4,3]P1[3,2,2][2,0,0][1,2,2]P2[9,0,2][3,0,2][6,0,0]P3[2,2,2][2,1,1][0,1,1]Work[3,3,2]查P1Need[1][1,2,2]≤Work → Work[32,30,20][5,3,2]查P3Need[3][0,1,1]≤Work → Work[52,31,21][7,4,3]查P0Need[0][7,4,3]≤Work → Work[70,41,30][7,5,3]查P2Need[2][6,0,0]≤Work → Work[73,50,32][10,5,5]安全序列P1→P3→P0→P2失分重災(zāi)區(qū)忘記更新Work向量、Need計(jì)算錯(cuò)誤Max?Allocation搞反、未驗(yàn)證所有進(jìn)程是否被納入序列。3.3 死鎖四必要條件如何用“循環(huán)等待”反推資源分配圖死鎖發(fā)生的四個(gè)必要條件互斥、占有并等待、非搶占、循環(huán)等待中“循環(huán)等待”是唯一可觀測(cè)、可畫圖驗(yàn)證的條件。筆記要求必須掌握資源分配圖Resource Allocation Graph繪制矩形框表示資源類如R1有3個(gè)實(shí)例標(biāo)為●●●圓圈表示進(jìn)程P1,P2...有向邊P→R進(jìn)程申請(qǐng)資源請(qǐng)求邊有向邊R→P資源已分配給進(jìn)程分配邊若圖中存在有向環(huán)則系統(tǒng)可能發(fā)生死鎖注意有環(huán)≠一定死鎖需結(jié)合資源實(shí)例數(shù)判斷。例如P1→R1, R1→P2, P2→R2, R2→P1構(gòu)成環(huán)P1→R1→P2→R2→P1且R1/R2各只有1實(shí)例則必然死鎖。提示考試若給資源分配圖問“是否死鎖”第一步標(biāo)出所有資源實(shí)例數(shù)第二步找環(huán)第三步驗(yàn)證環(huán)中每個(gè)資源類的實(shí)例是否被完全占用。三步缺一不可。3.4 易錯(cuò)點(diǎn)同步與死鎖中3個(gè)被嚴(yán)重低估的建模陷阱易漏點(diǎn)①信號(hào)量初值決定資源上限而非進(jìn)程數(shù)若有5臺(tái)打印機(jī)應(yīng)設(shè)sem_init(printer_sem, 0, 5)初值為5。若誤設(shè)為1則最多1個(gè)進(jìn)程能用打印機(jī)違背資源池本意。考試中“n個(gè)同類資源”必對(duì)應(yīng)信號(hào)量初值n。易漏點(diǎn)②銀行家算法中“Available”是當(dāng)前空閑量不是總量Total Allocation Available Need對(duì)所有進(jìn)程求和。若題目只給Allocation和Need必須先算Total再求Available Total ? ΣAllocation。直接抄題干Available值是常見錯(cuò)誤。易漏點(diǎn)③哲學(xué)家進(jìn)餐問題中“拿左叉再拿右叉”是死鎖根源但“按編號(hào)順序拿叉”只是充分條件編號(hào)法奇數(shù)號(hào)哲學(xué)家先左后右偶數(shù)號(hào)先右后左打破循環(huán)等待但若所有哲學(xué)家同時(shí)拿編號(hào)小的叉仍可能因競(jìng)爭(zhēng)失敗而阻塞。真正可靠的是引入服務(wù)員mutex集中授權(quán)?？荚嚾魡枴叭绾伪苊馑梨i”答“破壞循環(huán)等待條件規(guī)定拿叉順序”即可但需知其局限性。4. 存儲(chǔ)管理分區(qū)/分頁(yè)/分段的地址轉(zhuǎn)換、快表加速、頁(yè)面置換的硬核計(jì)算4.1 動(dòng)態(tài)分區(qū)分配五種算法的碎片化本質(zhì)與首次適應(yīng)的工程取舍動(dòng)態(tài)分區(qū)將內(nèi)存劃分為大小不等的連續(xù)塊分配算法直接影響外部碎片。筆記對(duì)比五種策略算法選擇邏輯碎片特點(diǎn)實(shí)際應(yīng)用首次適應(yīng)First Fit從低地址起找第一個(gè)夠大的空閑區(qū)中等碎片查找快Linux早期buddy系統(tǒng)變種最佳適應(yīng)Best Fit找大小最接近需求的空閑區(qū)碎片最多產(chǎn)生大量微小塊理論研究少實(shí)用最壞適應(yīng)Worst Fit找最大的空閑區(qū)大塊減少中等碎片減少后續(xù)大作業(yè)失敗率鄰近適應(yīng)Next Fit從上次查找位置繼續(xù)搜索查找開銷略降碎片類似FF某些嵌入式系統(tǒng)快速適應(yīng)Quick Fit維護(hù)多個(gè)空閑鏈表按大小分類查找O(1)但合并復(fù)雜高性能服務(wù)器關(guān)鍵洞察首次適應(yīng)雖產(chǎn)生中等碎片但因其查找路徑最短、實(shí)現(xiàn)最簡(jiǎn)、緩存友好成為教學(xué)與工業(yè)首選?？荚囍腥魡枴盀楹纬Ｓ檬状芜m應(yīng)”答“平衡碎片率與查找效率且易于實(shí)現(xiàn)”。4.2 分頁(yè)地址轉(zhuǎn)換邏輯地址拆分、頁(yè)表查詢、快表TLB命中率的量化影響分頁(yè)將邏輯地址分為頁(yè)號(hào)Page Number 頁(yè)內(nèi)偏移Page Offset。假設(shè)32位地址、4KB頁(yè)則頁(yè)內(nèi)偏移占12位2^124096頁(yè)號(hào)占20位2^201M頁(yè)。地址轉(zhuǎn)換流程CPU給出邏輯地址MMU提取頁(yè)號(hào)查頁(yè)表頁(yè)號(hào)作索引得物理頁(yè)框號(hào)Frame Number物理地址 Frame Number × Page Size Offset快表TLB是頁(yè)表的高速緩存其命中率H直接影響有效訪存時(shí)間EMATEMAT H × (TLB_access_time Memory_access_time) (1?H) × (TLB_access_time 2×Memory_access_time)若TLB訪問10ns內(nèi)存訪問100nsH0.95EMAT 0.95×(10100) 0.05×(10200) 104.5 10.5 115ns若無TLBH0EMAT200ns →TLB使訪存提速約74%提示考試中若給TLB命中率、訪問時(shí)間必考EMAT計(jì)算。公式中“2×內(nèi)存訪問”是因?yàn)橄炔轫?yè)表1次內(nèi)存再訪數(shù)據(jù)1次內(nèi)存。4.3 頁(yè)面置換算法FIFO/LRU/Clock的實(shí)現(xiàn)差異與Belady現(xiàn)象當(dāng)缺頁(yè)中斷發(fā)生且無空閑頁(yè)框時(shí)需置換一頁(yè)。三種主流算法FIFO淘汰最早裝入的頁(yè)。簡(jiǎn)單但存在Belady異常增加頁(yè)框數(shù)缺頁(yè)率反而上升。例訪問序列3,2,1,0,3,2,4用3頁(yè)框缺頁(yè)9次用4頁(yè)框缺頁(yè)10次。LRU最近最少使用淘汰最久未被訪問的頁(yè)。理想但硬件難實(shí)現(xiàn)通常用棧模擬每次訪問將頁(yè)移到棧頂棧底即LRU頁(yè)或計(jì)數(shù)器為每頁(yè)設(shè)訪問時(shí)間戳。Clock時(shí)鐘算法FIFO的改進(jìn)版為每頁(yè)設(shè)引用位R bit。指針循環(huán)掃描遇R0則置換遇R1則清R并跳過。R位由硬件在每次訪問時(shí)置1OS定時(shí)清零。例頁(yè)框數(shù)3訪問序列7,0,1,2,0,3,0,4初始R0加7,0,1 → 頁(yè)框[7,0,1]R[1,1,1]訪27的R1→清00的R1→清01的R1→清0指針回77的R0→置換7 → [2,0,1]后續(xù)同理...考試重點(diǎn)Clock算法必須寫出R位變化過程只寫置換結(jié)果不得分。4.4 易錯(cuò)點(diǎn)存儲(chǔ)管理中4個(gè)被忽視的硬件協(xié)同細(xì)節(jié)易漏點(diǎn)①頁(yè)內(nèi)偏移位數(shù)由頁(yè)大小決定與虛擬地址長(zhǎng)度無關(guān)4KB頁(yè) → 偏移12位16MB頁(yè) → 偏移24位。若題干說“32位地址、頁(yè)大小4KB”偏移固定12位頁(yè)號(hào)必為20位?；煜龝?huì)導(dǎo)致地址拆分錯(cuò)誤。易漏點(diǎn)②快表TLB是關(guān)聯(lián)存儲(chǔ)器按內(nèi)容尋址非按地址尋址TLB中存頁(yè)號(hào)頁(yè)框號(hào)對(duì)CPU送頁(yè)號(hào)TLB并行匹配所有項(xiàng)。若答“TLB像數(shù)組一樣用頁(yè)號(hào)當(dāng)索引”是根本性錯(cuò)誤。易漏點(diǎn)③二級(jí)頁(yè)表中頁(yè)目錄項(xiàng)PDE存頁(yè)表基址頁(yè)表項(xiàng)PTE存頁(yè)框號(hào)邏輯地址拆為頁(yè)目錄索引 頁(yè)表索引 頁(yè)內(nèi)偏移。先查頁(yè)目錄得頁(yè)表物理地址再查頁(yè)表得頁(yè)框號(hào)?？荚嚾魡枴岸?jí)頁(yè)表減少內(nèi)存浪費(fèi)的原理”答“只分配實(shí)際使用的頁(yè)表空頁(yè)表不占內(nèi)存”。易漏點(diǎn)④抖動(dòng)Thrashing的根因是進(jìn)程工作集大于分配頁(yè)框數(shù)非頁(yè)面置換算法本身即使LRU最優(yōu)若給每個(gè)進(jìn)程只分配2頁(yè)而其工作集需5頁(yè)仍會(huì)頻繁缺頁(yè)。解決抖動(dòng)需增加分配頁(yè)框數(shù)或掛起部分進(jìn)程而非換算法。5. 文件系統(tǒng)多重索引結(jié)構(gòu)、磁盤空間管理、目錄實(shí)現(xiàn)的物理與邏輯分離5.1 文件物理結(jié)構(gòu)順序/鏈接/索引的I/O性能與可靠性權(quán)衡文件在磁盤上的組織方式直接影響讀寫效率與容錯(cuò)能力順序結(jié)構(gòu)文件塊在磁盤上連續(xù)存放。優(yōu)點(diǎn)順序讀寫極快一次尋道批量傳輸缺點(diǎn)文件增長(zhǎng)需預(yù)留空間刪除后產(chǎn)生大塊外部碎片。鏈接結(jié)構(gòu)每塊含指向下一塊的指針。優(yōu)點(diǎn)無外部碎片文件可動(dòng)態(tài)增長(zhǎng)缺點(diǎn)隨機(jī)訪問需O(n)遍歷指針占存儲(chǔ)空間單點(diǎn)損壞導(dǎo)致鏈斷裂。索引結(jié)構(gòu)索引塊存所有數(shù)據(jù)塊地址。優(yōu)點(diǎn)支持隨機(jī)訪問O(1)尋址無外部碎片缺點(diǎn)小文件浪費(fèi)索引塊空間。筆記強(qiáng)調(diào)現(xiàn)代文件系統(tǒng)如ext4、NTFS均采用混合索引——直接塊12個(gè)存小文件一級(jí)間接塊存256個(gè)塊地址支持中文件二級(jí)/三級(jí)間接塊支持超大文件。5.2 多重索引尋址直接/間接索引的容量計(jì)算與尋址路徑以UNIX System V為例假設(shè)盤塊大小1KB盤塊號(hào)占4字節(jié)直接索引12個(gè)地址 → 支持12×1KB 12KB一級(jí)間接1塊存256個(gè)地址1024/4256 → 256×1KB 256KB二級(jí)間接1塊存256個(gè)一級(jí)間接塊地址 → 256×256×1KB 64MB三級(jí)間接1塊存256個(gè)二級(jí)間接塊地址 → 256×64MB 16GB總?cè)萘? 12KB 256KB 64MB 16GB ≈ 16GB尋址路徑示例讀取第10000字節(jié)字節(jié)10000 ÷ 1024 9.76 → 第10塊塊號(hào)90起始?jí)K號(hào)9 12 → 直接索引第9項(xiàng) → 得物理塊號(hào) → 讀取若讀第1000000字節(jié)≈976KB塊號(hào)976 12且976 12256268 → 屬一級(jí)間接范圍一級(jí)間接塊地址 直接索引第12項(xiàng) → 讀該塊塊內(nèi)偏移 (976?12) × 4 3856 → 取第3856–3859字節(jié)得物理塊號(hào)提示考試必考“某字節(jié)對(duì)應(yīng)第幾塊”及“該塊地址存于何處”需熟練進(jìn)行“字節(jié)→塊號(hào)→索引層級(jí)→地址位置”三級(jí)換算。5.3 文件空間管理位示圖、空閑鏈表、成組鏈接法的適用場(chǎng)景位示圖Bitmap用1位表示1塊是否空閑。優(yōu)點(diǎn)分配/回收O(1)定位適合大磁盤缺點(diǎn)圖本身占空間1TB磁盤需125MB位圖?？臻e鏈表所有空閑塊連成鏈表頭指針存超級(jí)塊。優(yōu)點(diǎn)無額外空間開銷缺點(diǎn)分配/回收需遍歷隨機(jī)性差。成組鏈接法UNIX將空閑塊分組如100塊/組每組首塊存下一組地址。超級(jí)塊存當(dāng)前組首塊地址。優(yōu)點(diǎn)兼顧空間效率與速度UNIX實(shí)證可靠。筆記指出成組鏈接法是考試重點(diǎn)因其結(jié)合了鏈表與索引思想。分配時(shí)取當(dāng)前組首塊若該組只剩1塊則讀取其存的下一組地址回收時(shí)若當(dāng)前組未滿插入若已滿新建一組并更新鏈接。5.4 易錯(cuò)點(diǎn)文件系統(tǒng)中3個(gè)被輕視的元數(shù)據(jù)一致性風(fēng)險(xiǎn)易漏點(diǎn)①目錄項(xiàng)Directory Entry不存文件內(nèi)容只存文件名與i-node號(hào)i-node才是文件元數(shù)據(jù)大小、權(quán)限、時(shí)間戳、數(shù)據(jù)塊地址的載體。刪除文件刪除目錄項(xiàng)i-node引用計(jì)數(shù)減1僅當(dāng)引用計(jì)數(shù)為0才真正釋放數(shù)據(jù)塊?？荚嚾魡枴皉m命令做了什么”答“解除目錄項(xiàng)與i-node的鏈接”而非“刪除文件內(nèi)容”。易漏點(diǎn)②軟鏈接與硬鏈接的本質(zhì)區(qū)別在于i-node引用方式硬鏈接多個(gè)目錄項(xiàng)指向同一i-node共享數(shù)據(jù)塊軟鏈接新建文件內(nèi)容為路徑字符串有自己的i-node。故硬鏈接不能跨文件系統(tǒng)i-node號(hào)全局唯一軟鏈接可以。易漏點(diǎn)③文件系統(tǒng)掛載mount的本質(zhì)是將設(shè)備的根目錄接入主目錄樹掛載點(diǎn)目錄如/mnt/usb的內(nèi)容被隱藏訪問時(shí)重定向到被掛載設(shè)備的根。卸載umount前必須確保無進(jìn)程在該目錄下工作否則“device busy”錯(cuò)誤。考試若問“為什么掛載后原目錄內(nèi)容看不見”答“VFS層將路徑解析重定向至新設(shè)備的根i-node”。6. 設(shè)備管理與復(fù)習(xí)清單緩沖技術(shù)、虛擬設(shè)備、設(shè)備獨(dú)立性的落地檢查表6.1 緩沖技術(shù)單緩沖/雙緩沖/循環(huán)緩沖的吞吐量瓶頸分析I/O速度遠(yuǎn)低于CPU緩沖是緩解鴻溝的核心手段單緩沖CPU向緩沖區(qū)寫設(shè)備從緩沖區(qū)讀。CPU必須等設(shè)備讀完才能寫下一單元 →CPU與設(shè)備串行工作吞吐量 min(CPU處理速率, 設(shè)備傳輸速率)。雙緩沖設(shè)緩沖區(qū)A、B。CPU寫A時(shí)設(shè)備讀B完成后交換角色。CPU與設(shè)備可部分重疊但仍有等待CPU寫完A需等設(shè)備讀完B才能寫B(tài)。循環(huán)緩沖多緩沖N個(gè)緩沖區(qū)組成環(huán)。CPU總可寫空閑緩沖區(qū)設(shè)備總可讀滿緩沖區(qū)。當(dāng)N足夠大CPU與設(shè)備完全并行吞吐量趨近兩者較大者。筆記用數(shù)據(jù)說話設(shè)CPU處理1單元1ms設(shè)備傳輸1單元2ms單緩沖吞吐量0.5單元/ms雙緩沖下CPU寫A1ms設(shè)備讀B2ms3ms處理2單元 → 0.67單元/ms循環(huán)緩沖N≥3時(shí)可穩(wěn)定在1單元/msCPU瓶頸。注意考試中若問“雙緩沖能否消除等待”答“不能完全消除僅減少等待時(shí)間”因CPU與設(shè)備速率不匹配時(shí)慢方總會(huì)拖累快方。6.2 虛擬設(shè)備技術(shù)SPOOLing如何將獨(dú)占設(shè)備變?yōu)楣蚕碣Y源SPOOLingSimultaneous Peripheral Operations On-Line是虛擬設(shè)備的典型實(shí)現(xiàn)以打印機(jī)為例輸入井磁盤上模擬輸入設(shè)備的區(qū)域輸出井磁盤上模擬輸出設(shè)備的區(qū)域輸入進(jìn)程將用戶作業(yè)從輸入設(shè)備讀入輸入井輸出進(jìn)程將輸出井中作業(yè)送打印機(jī)用戶進(jìn)程不再直接操作打印機(jī)而是向輸出井寫數(shù)據(jù)快輸出進(jìn)程后臺(tái)慢慢打印慢。本質(zhì)是用磁盤空間換取設(shè)備并發(fā)性將獨(dú)占設(shè)備打印機(jī)虛擬為多個(gè)邏輯設(shè)備。關(guān)鍵點(diǎn)SPOOLing要求輸入/輸出井足夠大且輸入/輸出進(jìn)程與用戶進(jìn)程異步協(xié)作。若輸出井滿用戶進(jìn)程需阻塞此時(shí)退化為假脫機(jī)。6.3 設(shè)備獨(dú)立性邏輯設(shè)備名→物理設(shè)備號(hào)→驅(qū)動(dòng)程序的三級(jí)映射設(shè)備獨(dú)立性指應(yīng)用程序用邏輯名如/dev/lp0訪問設(shè)備無需關(guān)心物理細(xì)節(jié)。實(shí)現(xiàn)依賴三層映射邏輯設(shè)備表LUT進(jìn)程私有存邏輯名, 物理設(shè)備號(hào)對(duì)系統(tǒng)設(shè)備表SDT全局存物理設(shè)備號(hào), 控制器號(hào), 驅(qū)動(dòng)程序入口控制器表存控制器狀態(tài)、通道信息當(dāng)進(jìn)程打開/dev/lp0查L(zhǎng)UT得物理設(shè)備號(hào)D1查SDT得D1對(duì)應(yīng)控制器C1及驅(qū)動(dòng)print_driver調(diào)用print_driver.open()初始化C1好處更換打印機(jī)型號(hào)只需更新SDT中D1對(duì)應(yīng)的驅(qū)動(dòng)入口應(yīng)用代碼零修改。6.4 復(fù)習(xí)清單一份可打印、可勾選、可速查的考前72小時(shí)行動(dòng)指南別再泛泛而讀。這份清單按真題出現(xiàn)頻率和計(jì)算復(fù)雜度排序每項(xiàng)對(duì)應(yīng)筆記中明確標(biāo)注的位置如P12、P23打印后逐條打鉤序號(hào)復(fù)習(xí)任務(wù)檢查方式預(yù)估耗時(shí)筆記頁(yè)碼1默寫三態(tài)模型轉(zhuǎn)換圖含觸發(fā)條件時(shí)間片/IO/中斷閉眼畫圖標(biāo)注所有箭頭條件8minP52手算SRTF調(diào)度給定5進(jìn)程AT/BT畫Gantt圖求平均T和W對(duì)照答案誤差≤0.115minP83銀行家算法全流程給Need/Allocation/Available找安全序列寫出每步Work向量變化20minP154分頁(yè)地址轉(zhuǎn)換32位地址/4KB頁(yè)求頁(yè)號(hào)/偏移畫兩級(jí)頁(yè)表尋址路徑標(biāo)出每級(jí)訪問的物理地址12minP195Clock頁(yè)面置換給訪問序列和R位初值模擬3輪指針掃描標(biāo)出每次R位變化和置換頁(yè)18minP226多重索引尋址計(jì)算1000000字節(jié)所在塊號(hào)指出該地址存于直接/間接哪一層寫出“字節(jié)→塊號(hào)→索引層級(jí)→地址位置”三步15minP277SPOOLing結(jié)構(gòu)圖畫輸入井/輸出井/輸入進(jìn)程/輸出進(jìn)程四要素及數(shù)據(jù)流箭頭方向必須正確輸入進(jìn)程→輸入井→用戶進(jìn)程10minP318設(shè)備獨(dú)立性三級(jí)映射默寫LUT/SDT/控制器表各自存什么舉例說明open()調(diào)用時(shí)的數(shù)據(jù)流向10minP32血淚經(jīng)驗(yàn)我曾因沒練熟第3項(xiàng)銀行家考場(chǎng)上卡在Work向量更新浪費(fèi)22分鐘。從那以后我每次模擬考前必做3遍銀行家手算強(qiáng)制自己寫出每一步Work值哪怕超時(shí)也要寫完?，F(xiàn)在看到Need矩陣手指會(huì)自動(dòng)開始加法——肌肉記憶比理解更可靠。最后檢查三件事所有計(jì)算題是否保留小數(shù)點(diǎn)后兩位考試要求所有“不考”標(biāo)記的內(nèi)容是否徹底劃掉如線程、死鎖檢測(cè)所有“☆”必考點(diǎn)是否至少演算過2次如頁(yè)面置換、多重索引希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取