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