最近在復(fù)習(xí)操作系統(tǒng)看到“時(shí)間關(guān)系圖”相關(guān)的題目總是有點(diǎn)發(fā)怵尤其是那些涉及進(jìn)程同步、死鎖、銀行家算法的綜合題。題目給出一堆進(jìn)程的到達(dá)時(shí)間、運(yùn)行時(shí)間、需要的資源然后讓你畫(huà)甘特圖、計(jì)算周轉(zhuǎn)時(shí)間、分析安全序列……步驟一多就容易亂。本文就把這類題的解題思路徹底理清從核心概念到實(shí)戰(zhàn)畫(huà)圖手把手帶你搞定操作系統(tǒng)中的各種“時(shí)間關(guān)系圖”難題。無(wú)論你是正在備考期末的學(xué)生還是想鞏固底層知識(shí)的開(kāi)發(fā)者掌握這套分析方法不僅能應(yīng)對(duì)考試更能深刻理解操作系統(tǒng)調(diào)度資源的邏輯。下面我們就從最基礎(chǔ)的“進(jìn)程調(diào)度時(shí)間圖”開(kāi)始一步步拆解。1. 核心概念什么是操作系統(tǒng)中的“時(shí)間關(guān)系圖”在操作系統(tǒng)的語(yǔ)境里“時(shí)間關(guān)系圖”并不是一個(gè)單一的圖表而是一類用于描述進(jìn)程或線程隨著時(shí)間推移其狀態(tài)、資源占用和調(diào)度情況的圖形化表示方法的統(tǒng)稱。它本質(zhì)上是將抽象的操作系統(tǒng)調(diào)度算法和并發(fā)控制過(guò)程轉(zhuǎn)化為直觀的時(shí)間線視圖。這類圖主要解決幾個(gè)核心問(wèn)題調(diào)度可視化CPU時(shí)間是如何分配給各個(gè)進(jìn)程的如先來(lái)先服務(wù)FCFS、短作業(yè)優(yōu)先SJF、時(shí)間片輪轉(zhuǎn)RR同步與互斥多個(gè)進(jìn)程在訪問(wèn)臨界資源時(shí)如何避免沖突如信號(hào)量、管程死鎖分析資源分配是否會(huì)導(dǎo)致系統(tǒng)進(jìn)入僵局如銀行家算法性能評(píng)估通過(guò)計(jì)算周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均等待時(shí)間等指標(biāo)量化調(diào)度算法的優(yōu)劣。最常見(jiàn)的“時(shí)間關(guān)系圖”包括甘特圖 (Gantt Chart)最常用用橫條表示進(jìn)程占用CPU的時(shí)間段X軸是時(shí)間。用于展示調(diào)度順序和計(jì)算時(shí)間指標(biāo)。時(shí)序圖 (Timing Diagram)或狀態(tài)轉(zhuǎn)換圖展示進(jìn)程在“運(yùn)行”、“就緒”、“阻塞”等狀態(tài)間的切換時(shí)刻和原因。資源分配圖 (Resource-Allocation Graph)用于死鎖檢測(cè)用圓圈表示進(jìn)程方框表示資源箭頭表示申請(qǐng)或占用關(guān)系。安全序列圖配合銀行家算法展示系統(tǒng)的一種可能的安全推進(jìn)路徑。理解這些圖是分析復(fù)雜調(diào)度和同步問(wèn)題的基礎(chǔ)。接下來(lái)我們以最常見(jiàn)的進(jìn)程調(diào)度為例看看如何從題目信息一步步畫(huà)出清晰的時(shí)間關(guān)系圖。2. 環(huán)境與工具準(zhǔn)備解題需要什么解這類題不需要復(fù)雜的編程環(huán)境核心是思路和工具。這里列出你需要的“軟硬件”清晰的思路這是最重要的“工具”。你需要理解調(diào)度算法的規(guī)則。紙和筆或白板初期強(qiáng)烈推薦手動(dòng)畫(huà)圖。在紙上標(biāo)記時(shí)間點(diǎn)、進(jìn)程狀態(tài)變化有助于理清邏輯。繪圖工具可選用于整理和驗(yàn)證ProcessOn / Draw.io在線流程圖工具畫(huà)甘特圖、時(shí)序圖非常方便。Excel / WPS表格利用單元格填充顏色來(lái)模擬甘特圖方便計(jì)算時(shí)間。文本編輯器簡(jiǎn)單的文本對(duì)齊也能畫(huà)出簡(jiǎn)易甘特圖。基礎(chǔ)知識(shí)確保你熟悉以下關(guān)鍵術(shù)語(yǔ)后續(xù)我們會(huì)反復(fù)用到到達(dá)時(shí)間 (Arrival Time)進(jìn)程進(jìn)入就緒隊(duì)列的時(shí)刻。運(yùn)行時(shí)間/服務(wù)時(shí)間 (Burst Time)進(jìn)程需要占用CPU的總時(shí)間。完成時(shí)間 (Completion Time)進(jìn)程運(yùn)行結(jié)束的時(shí)刻。周轉(zhuǎn)時(shí)間 (Turnaround Time) 完成時(shí)間 - 到達(dá)時(shí)間。帶權(quán)周轉(zhuǎn)時(shí)間 (Weighted Turnaround Time) 周轉(zhuǎn)時(shí)間 / 運(yùn)行時(shí)間。等待時(shí)間 (Waiting Time) 周轉(zhuǎn)時(shí)間 - 運(yùn)行時(shí)間。也等于在就緒隊(duì)列中等待的總時(shí)間時(shí)間片 (Time Quantum)輪轉(zhuǎn)調(diào)度中每個(gè)進(jìn)程一次能運(yùn)行的最大時(shí)間單位。我們的“實(shí)戰(zhàn)環(huán)境”就是一道典型的調(diào)度題目。下面我們進(jìn)入核心環(huán)節(jié)。3. 核心算法與畫(huà)圖步驟拆解面對(duì)一道調(diào)度題遵循固定的步驟可以極大降低出錯(cuò)率。我們以先來(lái)先服務(wù)(FCFS)和時(shí)間片輪轉(zhuǎn)(RR)為例講解通用解題流程。3.1 第一步提煉題目信息并制表拿到題目不要急著畫(huà)圖。先把所有進(jìn)程的信息整理成表格。假設(shè)題目如下有4個(gè)進(jìn)程P1, P2, P3, P4其到達(dá)時(shí)間和服務(wù)時(shí)間如下表所示。請(qǐng)分別給出FCFS和RR時(shí)間片q4調(diào)度算法下的甘特圖并計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間P105P213P328P436首先我們?cè)瓨訌?fù)制這個(gè)表格并預(yù)留出計(jì)算結(jié)果的列。初始信息表進(jìn)程到達(dá)時(shí)間(AT)服務(wù)時(shí)間(BT)完成時(shí)間(CT)周轉(zhuǎn)時(shí)間(TAT)等待時(shí)間(WT)帶權(quán)周轉(zhuǎn)時(shí)間(WTAT)P105P213P328P4363.2 第二步根據(jù)調(diào)度規(guī)則畫(huà)甘特圖對(duì)于FCFS先來(lái)先服務(wù)規(guī)則嚴(yán)格按照進(jìn)程到達(dá)就緒隊(duì)列的先后順序進(jìn)行調(diào)度且非搶占式一個(gè)進(jìn)程開(kāi)始后除非自己放棄CPU否則會(huì)一直運(yùn)行完。時(shí)間0只有P1到達(dá)調(diào)度P1。P1運(yùn)行5個(gè)單位從時(shí)間0運(yùn)行到時(shí)間5。在P1運(yùn)行期間P2(AT1), P3(AT2), P4(AT3)陸續(xù)到達(dá)在就緒隊(duì)列中排隊(duì)。時(shí)間5P1結(jié)束。就緒隊(duì)列中有P2, P3, P4按到達(dá)順序。調(diào)度最先到達(dá)的P2。P2運(yùn)行3個(gè)單位從時(shí)間5到時(shí)間8。時(shí)間8P2結(jié)束。調(diào)度P3。P3運(yùn)行8個(gè)單位從時(shí)間8到時(shí)間16。時(shí)間16P3結(jié)束。調(diào)度P4。P4運(yùn)行6個(gè)單位從時(shí)間16到時(shí)間22。FCFS甘特圖時(shí)間軸: 0 5 8 16 22 |----|----|--------|---------| 進(jìn)程: P1 P2 P3 P4注|----|表示一個(gè)進(jìn)程的執(zhí)行區(qū)間對(duì)于RR時(shí)間片輪轉(zhuǎn)q4規(guī)則將所有就緒進(jìn)程排成一個(gè)隊(duì)列每次調(diào)度隊(duì)首進(jìn)程運(yùn)行一個(gè)時(shí)間片。若進(jìn)程在時(shí)間片內(nèi)未運(yùn)行完則將其放回就緒隊(duì)列末尾。是搶占式調(diào)度。 我們需要模擬一個(gè)時(shí)間點(diǎn)一個(gè)時(shí)間點(diǎn)的推進(jìn)時(shí)間0就緒隊(duì)列[P1]。調(diào)度P1。P1運(yùn)行1個(gè)時(shí)間片4個(gè)單位。運(yùn)行到時(shí)間4時(shí)P1剩余BT1。此時(shí)P2(1), P3(2), P4(3)均已到達(dá)。就緒隊(duì)列變?yōu)閇P2, P3, P4, P1]P1被放到隊(duì)尾。時(shí)間4調(diào)度隊(duì)首P2。P2運(yùn)行1個(gè)時(shí)間片4個(gè)單位但其BT只有3所以在時(shí)間7提前結(jié)束。期間無(wú)新進(jìn)程到達(dá)。P2完成后就緒隊(duì)列為[P3, P4, P1]。時(shí)間7調(diào)度P3。P3運(yùn)行1個(gè)時(shí)間片4個(gè)單位到時(shí)間11剩余BT4。就緒隊(duì)列變?yōu)閇P4, P1, P3]。時(shí)間11調(diào)度P4。P4運(yùn)行1個(gè)時(shí)間片4個(gè)單位到時(shí)間15剩余BT2。就緒隊(duì)列變?yōu)閇P1, P3, P4]。時(shí)間15調(diào)度P1。P1剩余BT1運(yùn)行1個(gè)單位在時(shí)間16結(jié)束。就緒隊(duì)列為[P3, P4]。時(shí)間16調(diào)度P3。P3剩余BT4運(yùn)行1個(gè)時(shí)間片4個(gè)單位到時(shí)間20剩余BT0結(jié)束。就緒隊(duì)列為[P4]。時(shí)間20調(diào)度P4。P4剩余BT2運(yùn)行2個(gè)單位在時(shí)間22結(jié)束。RR (q4) 甘特圖時(shí)間軸: 0 4 7 11 15 16 20 22 |----|----|----|----|----|----|----| 進(jìn)程: P1 P2 P3 P4 P1 P3 P4 (4) (3) (4) (4) (1) (4) (2)括號(hào)內(nèi)表示該時(shí)間段實(shí)際運(yùn)行的長(zhǎng)度3.3 第三步根據(jù)甘特圖填表計(jì)算這是最關(guān)鍵的一步所有時(shí)間指標(biāo)都從甘特圖中來(lái)。FCFS計(jì)算結(jié)果完成時(shí)間CT直接從甘特圖結(jié)束點(diǎn)讀取。P1: 5, P2: 8, P3: 16, P4: 22。周轉(zhuǎn)時(shí)間TAT CT - ATP1: 5-05, P2: 8-17, P3: 16-214, P4: 22-319。等待時(shí)間WT TAT - BTP1: 5-50, P2: 7-34, P3: 14-86, P4: 19-613。 也可以從甘特圖上看進(jìn)程在就緒隊(duì)列中的等待總和結(jié)果一致帶權(quán)周轉(zhuǎn)時(shí)間WTAT TAT / BTP1: 5/51.0, P2: 7/3≈2.33, P3: 14/81.75, P4: 19/6≈3.17。平均值平均周轉(zhuǎn)時(shí)間 (571419)/4 11.25平均帶權(quán)周轉(zhuǎn)時(shí)間 (1.02.331.753.17)/4 ≈ 2.06RR (q4) 計(jì)算結(jié)果計(jì)算時(shí)需注意完成時(shí)間是進(jìn)程最后一次執(zhí)行結(jié)束的時(shí)間點(diǎn)。完成時(shí)間CTP1: 16, P2: 7, P3: 20, P4: 22。周轉(zhuǎn)時(shí)間TAT CT - ATP1: 16-016, P2: 7-16, P3: 20-218, P4: 22-319。等待時(shí)間WT TAT - BTP1: 16-511, P2: 6-33, P3: 18-810, P4: 19-613。 也可以計(jì)算WT 進(jìn)程總共在就緒隊(duì)列中的時(shí)間。例如P1在0-4運(yùn)行然后等待了4-15共11個(gè)單位確實(shí)為11帶權(quán)周轉(zhuǎn)時(shí)間WTAT TAT / BTP1: 16/53.2, P2: 6/32.0, P3: 18/82.25, P4: 19/6≈3.17。平均值平均周轉(zhuǎn)時(shí)間 (1661819)/4 14.75平均帶權(quán)周轉(zhuǎn)時(shí)間 (3.22.02.253.17)/4 ≈ 2.66通過(guò)對(duì)比可以發(fā)現(xiàn)對(duì)于這組數(shù)據(jù)FCFS的平均周轉(zhuǎn)時(shí)間11.25優(yōu)于RR的14.75但FCFS的等待時(shí)間方差大P4等了很久而RR的響應(yīng)特性更好每個(gè)進(jìn)程都能較快獲得CPU。4. 綜合實(shí)戰(zhàn)含資源分配的死鎖與銀行家算法時(shí)間關(guān)系圖更復(fù)雜的應(yīng)用是在進(jìn)程同步和死鎖避免中。這里我們看一個(gè)經(jīng)典的銀行家算法題目它要求我們找出安全序列這本身就是一種特殊的“時(shí)間關(guān)系圖”——安全推進(jìn)圖。題目一個(gè)系統(tǒng)有A、B、C三類資源數(shù)量分別為(10, 5, 7)。 有5個(gè)進(jìn)程P0~P4在T0時(shí)刻的資源分配情況如下進(jìn)程最大需求 Max已分配 Allocation需求 Need (Max-Allo)A B CA B CA B CP07 5 30 1 07 4 3P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1T0時(shí)刻可用資源 Available (3, 3, 2)。問(wèn)系統(tǒng)是否處于安全狀態(tài)若是給出一個(gè)安全序列。解題步驟這就是在畫(huà)一個(gè)邏輯上的資源分配時(shí)間圖列出已知條件表題目已給出。初始化工作向量Work Available (3, 3, 2)Finish [false, false, false, false, false](表示進(jìn)程是否可完成)尋找安全序列 我們模擬系統(tǒng)按某種順序分配剩余資源給進(jìn)程使其完成并釋放資源的過(guò)程。第一輪查找比較每個(gè)進(jìn)程的Need[i]是否小于等于當(dāng)前Work。P0: Need(7,4,3) Work(3,3,2) →不滿足P1: Need(1,2,2) Work(3,3,2) →滿足。假設(shè)分配資源給P1它完成后會(huì)釋放其占用的Allocation(2,0,0)。所以更新Work Work Allocation(P1) (3,3,2)(2,0,0) (5,3,2)Finish[1] true安全序列暫為[P1]第二輪查找(Work(5,3,2), Finish[1]true)P0: (7,4,3) (5,3,2) → 不滿足P2: (6,0,0) (5,3,2)注意65 (A資源不滿足)→ 不滿足P3: (0,1,1) (5,3,2) →滿足。Work (5,3,2) (2,1,1) (7,4,3)Finish[3] true安全序列更新為[P1, P3]P4: (4,3,1) (5,3,2)注意45, 33, 12→滿足。 這里P3和P4都滿足選擇任意一個(gè)即可我們按順序選了P3。如果選P4會(huì)得到另一個(gè)安全序列。第三輪查找(Work(7,4,3), Finish[1]true, Finish[3]true)P0: (7,4,3) (7,4,3) →滿足。Work (7,4,3) (0,1,0) (7,5,3)Finish[0] true安全序列更新為[P1, P3, P0]P2: (6,0,0) (7,4,3) →滿足。Work (7,4,3) (3,0,2) (10,4,5)Finish[2] true安全序列更新為[P1, P3, P0, P2]P4: (4,3,1) (7,4,3) →滿足。Work (7,4,3) (0,0,2) (7,4,5)Finish[4] true安全序列更新為[P1, P3, P0, P2, P4]檢查此時(shí)所有Finish[i] true。得出結(jié)論存在一個(gè)安全序列P1 - P3 - P0 - P2 - P4序列不唯一。因此系統(tǒng)處于安全狀態(tài)。這個(gè)逐步查找的過(guò)程就是在腦海中描繪一幅資源隨時(shí)間推移在不同進(jìn)程間流轉(zhuǎn)的“安全關(guān)系圖”。每一步的Work向量變化都代表了系統(tǒng)狀態(tài)在安全路徑上的一次推進(jìn)。5. 常見(jiàn)問(wèn)題與排查思路在解題和實(shí)際理解中經(jīng)常會(huì)遇到一些混淆點(diǎn)和錯(cuò)誤。這里總結(jié)一個(gè)排查清單問(wèn)題現(xiàn)象常見(jiàn)原因解決思路與正確理解畫(huà)RR甘特圖時(shí)進(jìn)程執(zhí)行順序混亂忽略了新到達(dá)的進(jìn)程會(huì)插入就緒隊(duì)列末尾或者時(shí)間片用完后進(jìn)程重新排隊(duì)的規(guī)則。1. 維護(hù)一個(gè)“就緒隊(duì)列”變量隨時(shí)間推進(jìn)動(dòng)態(tài)更新。2. 在每個(gè)調(diào)度點(diǎn)時(shí)間片結(jié)束或進(jìn)程完成按規(guī)則更新隊(duì)列完成則移除未完成則放到隊(duì)尾新到達(dá)的插入隊(duì)尾。3. 總是調(diào)度隊(duì)首進(jìn)程。計(jì)算出的等待時(shí)間與預(yù)期不符錯(cuò)誤地將“等待時(shí)間”理解為“首次等待時(shí)間”或者用錯(cuò)了公式。牢記公式WT TAT - BT。這是最可靠的。TAT和BT都容易從甘特圖獲得。等待時(shí)間就是進(jìn)程在就緒隊(duì)列中所有等待時(shí)間的總和。銀行家算法中找不到安全序列1. 計(jì)算Need矩陣出錯(cuò)Max - Allocation。2. 比較Need Work時(shí)沒(méi)有對(duì)每一種資源逐一比較。3. 在某一輪查找中有多個(gè)進(jìn)程滿足條件時(shí)選擇不同可能導(dǎo)致最終結(jié)果不同可能安全可能不安全但若系統(tǒng)安全至少存在一條路徑。1. 仔細(xì)復(fù)核Need矩陣的計(jì)算。2. 比較向量時(shí)必須保證每一個(gè)分量都滿足Need[i][j] Work[j]。3. 如果按進(jìn)程編號(hào)順序查找找不到可以嘗試不同的查找順序如從需求最小的進(jìn)程開(kāi)始但考試中通常按P0,P1,...順序查找即可。若所有順序都找不到則系統(tǒng)不安全。混淆“非搶占”和“搶占”對(duì)SJF短作業(yè)優(yōu)先或優(yōu)先級(jí)調(diào)度算法分不清其搶占和非搶占版本。非搶占一旦進(jìn)程開(kāi)始就運(yùn)行到結(jié)束或主動(dòng)阻塞。搶占當(dāng)有新更短/更高優(yōu)先級(jí)進(jìn)程到達(dá)時(shí)可能搶占當(dāng)前進(jìn)程的CPU。關(guān)鍵題目一定會(huì)說(shuō)明是“非搶占SJF”還是“可搶占的SJF又稱最短剩余時(shí)間優(yōu)先SRTF”。死鎖檢測(cè)中資源分配圖畫(huà)錯(cuò)混淆“申請(qǐng)邊”和“分配邊”的方向或者對(duì)“可化簡(jiǎn)”的過(guò)程理解不清。分配邊從資源節(jié)點(diǎn)指向進(jìn)程節(jié)點(diǎn)Rj - Pi表示資源Rj的一個(gè)實(shí)例已分配給Pi。申請(qǐng)邊從進(jìn)程節(jié)點(diǎn)指向資源節(jié)點(diǎn)Pi - Rj表示Pi正在申請(qǐng)一個(gè)Rj的實(shí)例。化簡(jiǎn)找一個(gè)既不阻塞申請(qǐng)的資源都能滿足又不是孤立的進(jìn)程去掉它的所有邊模擬其完成并釋放資源。重復(fù)此過(guò)程若所有進(jìn)程都可被化簡(jiǎn)則無(wú)死鎖否則不可化簡(jiǎn)的進(jìn)程組成了死鎖集合。6. 最佳實(shí)踐與工程思維將解題技巧升華可以培養(yǎng)出在真實(shí)系統(tǒng)設(shè)計(jì)和分析中非常有用的工程思維。從“畫(huà)圖”到“建模”解題時(shí)畫(huà)甘特圖本質(zhì)是為并發(fā)系統(tǒng)建立一個(gè)離散事件仿真模型。時(shí)間軸是狀態(tài)變化的驅(qū)動(dòng)。在實(shí)際中你可以用類似的思想去分析分布式任務(wù)調(diào)度、消息隊(duì)列的消費(fèi)延遲等問(wèn)題。指標(biāo)權(quán)衡思維不同的調(diào)度算法優(yōu)化不同的指標(biāo)FCFS公平但平均等待時(shí)間長(zhǎng)SJF平均等待時(shí)間最短但可能“餓死”長(zhǎng)作業(yè)RR響應(yīng)快但上下文切換開(kāi)銷(xiāo)大。在實(shí)際系統(tǒng)如Web服務(wù)器、操作系統(tǒng)內(nèi)核中調(diào)度器的設(shè)計(jì)都是多種策略的混合與權(quán)衡。理解每種算法的代價(jià)和收益是關(guān)鍵。安全性與性能的平衡銀行家算法是保守的死鎖避免策略它保證系統(tǒng)絕不會(huì)進(jìn)入不安全狀態(tài)但可能導(dǎo)致資源利用率降低因?yàn)榧词褂匈Y源也可能因?yàn)闀?huì)導(dǎo)致不安全而拒絕分配。在工程上有時(shí)為了性能可能會(huì)采用死鎖檢測(cè)與恢復(fù)的策略而不是完全避免。邊界條件與極端情況在解題時(shí)要特別注意邊界。例如進(jìn)程到達(dá)時(shí)間和時(shí)間片結(jié)束時(shí)間重合時(shí)如何調(diào)度通常的處理是“到達(dá)”事件優(yōu)先于“時(shí)間片用完”事件被處理即新到達(dá)的進(jìn)程先進(jìn)入隊(duì)列然后再處理當(dāng)前進(jìn)程因時(shí)間片到期而重新排隊(duì)。再如所有進(jìn)程同時(shí)到達(dá)AT相同時(shí)FCFS按什么順序通常按進(jìn)程ID順序但題目應(yīng)說(shuō)明。工具輔助驗(yàn)證對(duì)于復(fù)雜場(chǎng)景可以用簡(jiǎn)單的代碼來(lái)驗(yàn)證你的手算結(jié)果。例如寫(xiě)一個(gè)Python腳本模擬RR調(diào)度器輸入進(jìn)程列表和時(shí)間片輸出甘特圖和各項(xiàng)指標(biāo)。這不僅能驗(yàn)證答案更能加深對(duì)算法動(dòng)態(tài)過(guò)程的理解。# 一個(gè)非常簡(jiǎn)化的RR調(diào)度模擬思路非完整代碼 class Process: def __init__(self, pid, arrival, burst): self.pid pid self.arrival arrival self.burst burst self.remaining burst def simulate_rr(processes, quantum): time 0 queue [] # ... 模擬邏輯按時(shí)間推進(jìn)管理隊(duì)列分配時(shí)間片 ... # 輸出每個(gè)進(jìn)程的開(kāi)始、結(jié)束時(shí)間7. 總結(jié)與學(xué)習(xí)路線通過(guò)本文的梳理希望你對(duì)“操作系統(tǒng)時(shí)間關(guān)系圖”類題目不再畏懼。我們來(lái)回顧一下核心鏈路明確問(wèn)題類型是單純調(diào)度還是涉及同步PV操作或是死鎖檢測(cè)/避免銀行家算法提取與制表無(wú)條件把所有已知信息整理到表格中這是分析的基石。理解算法規(guī)則這是畫(huà)圖的依據(jù)。非搶占/搶占時(shí)間片多大資源分配規(guī)則是什么按時(shí)間步推進(jìn)這是畫(huà)圖的核心動(dòng)作。像調(diào)試程序一樣一步一步模擬系統(tǒng)的狀態(tài)變化。對(duì)于調(diào)度題關(guān)注“調(diào)度點(diǎn)”進(jìn)程到達(dá)、結(jié)束、時(shí)間片用完對(duì)于銀行家算法關(guān)注“查找輪次”。依圖計(jì)算指標(biāo)所有答案都基于你畫(huà)出的圖或推導(dǎo)出的序列。公式要記牢TATCT-AT, WTTAT-BT。交叉檢查計(jì)算完成后快速用常識(shí)判斷。平均周轉(zhuǎn)時(shí)間是否合理等待時(shí)間是否非負(fù)安全序列是否真的能讓所有進(jìn)程完成要真正掌握僅看一遍是不夠的。建議你找3-5道經(jīng)典綜合題涵蓋FCFS、SJF非搶占/搶占、RR、銀行家算法、死鎖檢測(cè)按照上述步驟完整地做一遍。對(duì)比不同算法用同一組進(jìn)程數(shù)據(jù)分別用FCFS、SJF、RR計(jì)算對(duì)比各項(xiàng)指標(biāo)理解其設(shè)計(jì)哲學(xué)和適用場(chǎng)景。嘗試編程模擬用你熟悉的語(yǔ)言實(shí)現(xiàn)一個(gè)簡(jiǎn)單的調(diào)度模擬器這是將理論轉(zhuǎn)化為實(shí)踐的最佳方式。操作系統(tǒng)是計(jì)算機(jī)的基石而進(jìn)程管理與調(diào)度是其核心。吃透這些時(shí)間關(guān)系圖不僅能讓你在考試中游刃有余更能為你日后理解高性能服務(wù)器、并發(fā)編程框架乃至分布式系統(tǒng)打下堅(jiān)實(shí)的基礎(chǔ)。