簡(jiǎn)介這份資源面向操作系統(tǒng)課程學(xué)習(xí)者與備考學(xué)生聚焦銀行家算法這一經(jīng)典死鎖避免策略提供實(shí)驗(yàn)報(bào)告與可運(yùn)行源代碼的完整配套。內(nèi)容圍繞最大需求矩陣、可用資源向量、已分配矩陣與需求矩陣四個(gè)核心數(shù)據(jù)結(jié)構(gòu)展開(kāi)覆蓋初始化、資源請(qǐng)求、安全性檢查、資源分配與釋放等實(shí)驗(yàn)環(huán)節(jié)并涉及進(jìn)程管理、資源分配與模擬循環(huán)等代碼模塊可幫助讀者理解安全序列的構(gòu)造過(guò)程與死鎖預(yù)防機(jī)制。壓縮包共5個(gè)文件包含2個(gè)cpp源文件、1個(gè)h頭文件、1個(gè)txt初始化數(shù)據(jù)文件與1個(gè)docx實(shí)驗(yàn)報(bào)告整體約452KB代碼與文檔相互印證便于對(duì)照閱讀與調(diào)試。目前已有5250人學(xué)習(xí)下載適合需要完成課程實(shí)驗(yàn)、梳理算法實(shí)現(xiàn)細(xì)節(jié)或排查資源分配與安全性檢查問(wèn)題的讀者參考。1. 銀行家算法實(shí)驗(yàn)包從“能跑”到“敢交”的最后一公里如果你正在做操作系統(tǒng)課程設(shè)計(jì)大概率繞不開(kāi)銀行家算法這個(gè)實(shí)驗(yàn)。它不像進(jìn)程調(diào)度那樣能直觀看到時(shí)間片輪轉(zhuǎn)也不像頁(yè)面置換那樣能畫(huà)出缺頁(yè)曲線它的“正確性”幾乎全靠一組組安全性檢查的數(shù)字堆出來(lái)。我見(jiàn)過(guò)太多人把代碼跑通、輸出一個(gè)“安全序列”就交差了結(jié)果答辯時(shí)被問(wèn)“Available 怎么更新的”“Request 超過(guò) Need 為什么直接拒絕”就卡殼。這份“操作系統(tǒng)銀行家算法 實(shí)驗(yàn)報(bào)告源代碼”資源包解決的正是從“代碼能跑”到“報(bào)告能交、答辯能扛”的最后一公里問(wèn)題。它適合正在做 OS 實(shí)驗(yàn)的本科生、需要快速?gòu)?fù)現(xiàn)經(jīng)典算法的自學(xué)者以及想拿一份標(biāo)準(zhǔn)實(shí)現(xiàn)做對(duì)照的開(kāi)發(fā)者。接下來(lái)我會(huì)把這份資源拆開(kāi)講清它的數(shù)據(jù)結(jié)構(gòu)怎么設(shè)計(jì)、安全性檢查怎么落地、報(bào)告里哪些數(shù)字必須對(duì)得上以及我踩過(guò)的那些坑。2. 銀行家算法的數(shù)據(jù)結(jié)構(gòu)與安全性檢查先想清楚再寫(xiě)代碼2.1 為什么這幾個(gè)矩陣決定了整個(gè)實(shí)驗(yàn)的成敗銀行家算法的核心不是代碼有多復(fù)雜而是幾個(gè)矩陣之間的約束關(guān)系必須理清楚。資源包里通常包含 Available、Max、Allocation、Need 四個(gè)核心數(shù)據(jù)結(jié)構(gòu)外加一個(gè) Work 向量和一個(gè) Finish 數(shù)組用于安全性檢查。很多人寫(xiě)代碼時(shí)把 Need 當(dāng)成獨(dú)立輸入這是第一個(gè)翻車點(diǎn)——Need 必須由 Max 減去 Allocation 得到而不是單獨(dú)賦值。一旦 Need 和 Max、Allocation 對(duì)不上后面所有安全性判斷都是錯(cuò)的。我一般會(huì)建議在初始化階段就做一次一致性校驗(yàn)遍歷每個(gè)進(jìn)程的每個(gè)資源檢查Need[i][j] Max[i][j] - Allocation[i][j]是否成立不成立就直接報(bào)錯(cuò)退出。這個(gè)校驗(yàn)花不了幾行代碼但能幫你擋掉后面 80% 的玄學(xué) bug。資源包里的源代碼通常會(huì)在init()或input()函數(shù)里做這件事你拿到代碼后第一件事就是確認(rèn)這個(gè)校驗(yàn)存在。另一個(gè)容易被忽略的是 Available 的語(yǔ)義。Available 表示當(dāng)前系統(tǒng)里每一類資源還剩多少可用它不等于總資源量減去所有進(jìn)程的 Allocation 之和——雖然初始時(shí)刻確實(shí)相等但在進(jìn)程運(yùn)行過(guò)程中Available 會(huì)因?yàn)檫M(jìn)程釋放資源而變化。實(shí)驗(yàn)報(bào)告里如果只寫(xiě)“Available 初始值等于總資源減已分配”而不說(shuō)明它在運(yùn)行中的動(dòng)態(tài)更新邏輯答辯時(shí)很容易被追問(wèn)。2.2 安全性檢查的代碼實(shí)現(xiàn)與參數(shù)說(shuō)明安全性檢查是銀行家算法的心臟它的邏輯是嘗試找一個(gè)安全序列使得每個(gè)進(jìn)程都能在現(xiàn)有可用資源下依次完成。下面這段代碼是資源包里最常見(jiàn)的實(shí)現(xiàn)方式我加了詳細(xì)注釋你可以直接對(duì)照自己的代碼看差異。def is_safe(available, max_need, allocation, n_process, n_resource): 安全性檢查算法 available: 當(dāng)前可用資源向量長(zhǎng)度 n_resource max_need: 最大需求矩陣n_process x n_resource allocation: 已分配矩陣n_process x n_resource 返回: (是否安全, 安全序列) work available[:] # Work 向量初始化為 Available finish [False] * n_process # Finish 全部置 False safe_seq [] # 記錄安全序列 while len(safe_seq) n_process: found False for i in range(n_process): if finish[i]: continue # 計(jì)算 Need[i] Max[i] - Allocation[i] need_i [max_need[i][j] - allocation[i][j] for j in range(n_resource)] # 檢查 Need[i] Work 是否成立 if all(need_i[j] work[j] for j in range(n_resource)): # 模擬進(jìn)程 i 完成釋放其已分配資源 for j in range(n_resource): work[j] allocation[i][j] finish[i] True safe_seq.append(i) found True break if not found: # 找不到可執(zhí)行進(jìn)程系統(tǒng)不安全 return False, [] return True, safe_seq這段代碼的關(guān)鍵參數(shù)有三個(gè)work是動(dòng)態(tài)變化的可用資源副本finish標(biāo)記進(jìn)程是否已加入安全序列safe_seq記錄順序。邏輯上每次找到一個(gè)滿足Need[i] Work的進(jìn)程就假設(shè)它執(zhí)行完成并釋放資源然后繼續(xù)找下一個(gè)。如果某一輪找不到任何可執(zhí)行進(jìn)程說(shuō)明系統(tǒng)不安全。資源包里的源代碼通常還會(huì)在找到安全序列后打印出來(lái)格式類似P1 - P3 - P0 - P2 - P4。這里有個(gè)細(xì)節(jié)安全序列不唯一不同的遍歷順序可能得到不同結(jié)果但只要能找到一個(gè)就說(shuō)明系統(tǒng)安全。實(shí)驗(yàn)報(bào)告里如果只寫(xiě)一個(gè)序列最好注明“其中一種安全序列”避免被質(zhì)疑為什么不是另一個(gè)順序。2.3 資源請(qǐng)求算法Request 怎么處理才不翻車當(dāng)某個(gè)進(jìn)程發(fā)出資源請(qǐng)求 Request 時(shí)銀行家算法要分三步判斷第一Request 是否超過(guò)該進(jìn)程的 Need第二Request 是否超過(guò)當(dāng)前 Available第三試探性分配后系統(tǒng)是否仍安全。這三步缺一不可而且順序不能亂。def request_resources(pid, request, available, max_need, allocation, n_process, n_resource): 處理進(jìn)程 pid 的資源請(qǐng)求 request: 請(qǐng)求向量長(zhǎng)度 n_resource 返回: (是否分配成功, 說(shuō)明信息) # 步驟1檢查 Request Need need_pid [max_need[pid][j] - allocation[pid][j] for j in range(n_resource)] if any(request[j] need_pid[j] for j in range(n_resource)): return False, 請(qǐng)求超過(guò)最大需求 Need拒絕 # 步驟2檢查 Request Available if any(request[j] available[j] for j in range(n_resource)): return False, 請(qǐng)求超過(guò)當(dāng)前可用資源 Available等待 # 步驟3試探性分配 for j in range(n_resource): available[j] - request[j] allocation[pid][j] request[j] # Need 會(huì)隨 Allocation 增加而減少這里不直接改 max_need # 檢查安全性 safe, seq is_safe(available, max_need, allocation, n_process, n_resource) if safe: return True, f分配成功安全序列: {seq} else: # 回滾試探性分配 for j in range(n_resource): available[j] request[j] allocation[pid][j] - request[j] return False, 分配后系統(tǒng)不安全回滾這段代碼里最容易出錯(cuò)的是回滾邏輯。試探性分配之后如果系統(tǒng)不安全必須把 Available 和 Allocation 恢復(fù)到請(qǐng)求前的狀態(tài)否則后續(xù)所有判斷都會(huì)基于錯(cuò)誤的數(shù)據(jù)。資源包里的源代碼一般會(huì)用一個(gè)臨時(shí)副本做試探而不是直接改原數(shù)據(jù)這樣回滾更干凈。如果你拿到的代碼是直接改原數(shù)據(jù)再回滾一定要檢查回滾是否完整——我見(jiàn)過(guò)只回滾 Available 忘了回滾 Allocation 的實(shí)現(xiàn)跑幾輪之后數(shù)據(jù)全亂。3. 實(shí)驗(yàn)報(bào)告怎么寫(xiě)讓數(shù)字和代碼對(duì)得上3.1 報(bào)告里必須出現(xiàn)的三組數(shù)據(jù)實(shí)驗(yàn)報(bào)告不是代碼的翻譯它需要展示你對(duì)算法過(guò)程的理解。資源包里的報(bào)告模板通常會(huì)要求你給出至少三組數(shù)據(jù)初始狀態(tài)表、某一時(shí)刻的安全性檢查過(guò)程、一次資源請(qǐng)求的完整判斷。這三組數(shù)據(jù)必須和你的代碼輸出完全一致否則答辯時(shí)老師一運(yùn)行就露餡。初始狀態(tài)表一般包括 Available、Max、Allocation、Need 四個(gè)矩陣。注意 Need 矩陣不要單獨(dú)編造它必須等于 Max 減 Allocation。我建議在報(bào)告里用表格呈現(xiàn)格式如下進(jìn)程MaxAllocationNeedAvailableP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1這張表是經(jīng)典教材里的例子資源包里的代碼通常也用它做測(cè)試用例。你可以在報(bào)告里寫(xiě)“以教材經(jīng)典用例為例”然后附上你的代碼運(yùn)行截圖。注意截圖里的安全序列要和表格數(shù)據(jù)對(duì)得上比如 P1 - P3 - P0 - P2 - P4 或者 P1 - P3 - P4 - P0 - P2 都是合法的但你不能寫(xiě)一個(gè)代碼根本跑不出來(lái)的序列。3.2 安全性檢查過(guò)程的逐步展開(kāi)報(bào)告里最加分的是把安全性檢查的每一步 Work、Need、Allocation 變化寫(xiě)清楚。比如初始 Work Available (3,3,2)然后依次檢查 P0 到 P4 的 Need 是否小于等于 Work。P0 的 Need 是 (7,4,3)大于 Work跳過(guò)P1 的 Need 是 (1,2,2)小于等于 Work選中 P1Work 變?yōu)?(3,3,2) (2,0,0) (5,3,2)Finish[1] True。接著繼續(xù)找P3 的 Need 是 (0,1,1)小于等于 (5,3,2)選中 P3Work 變?yōu)?(5,3,2) (2,1,1) (7,4,3)Finish[3] True。然后 P0 的 Need (7,4,3) 小于等于 (7,4,3)選中 P0Work 變?yōu)?(7,4,3) (0,1,0) (7,5,3)Finish[0] True。接著 P2 的 Need (6,0,0) 小于等于 (7,5,3)選中 P2Work 變?yōu)?(7,5,3) (3,0,2) (10,5,5)Finish[2] True。最后 P4 的 Need (4,3,1) 小于等于 (10,5,5)選中 P4Work 變?yōu)?(10,5,5) (0,0,2) (10,5,7)Finish[4] True。所有進(jìn)程完成安全序列為 P1 - P3 - P0 - P2 - P4。這段過(guò)程寫(xiě)進(jìn)報(bào)告大概占半頁(yè)紙但它是證明你真的理解算法的關(guān)鍵。資源包里的報(bào)告模板通常會(huì)留出空白讓你填這些數(shù)字你只需要把代碼運(yùn)行時(shí)的中間輸出復(fù)制進(jìn)去就行。如果你的代碼沒(méi)有打印中間過(guò)程建議加幾行print語(yǔ)句把每次 Work 的變化和選中的進(jìn)程輸出出來(lái)。3.3 資源請(qǐng)求的完整判斷案例報(bào)告里還需要一個(gè)資源請(qǐng)求的案例。比如 P1 發(fā)出 Request (1,0,2)判斷過(guò)程是Request (1,0,2) Need[1] (1,2,2)成立Request (1,0,2) Available (3,3,2)成立試探性分配后 Available 變?yōu)?(2,3,0)Allocation[1] 變?yōu)?(3,0,2)然后調(diào)用安全性檢查。如果檢查結(jié)果安全就正式分配如果不安全就回滾并說(shuō)明原因。這個(gè)案例要寫(xiě)清楚每一步的判斷依據(jù)和結(jié)果。資源包里的源代碼通常會(huì)在request_resources函數(shù)里打印這些信息你直接引用即可。注意如果 Request 超過(guò) Need報(bào)告里要寫(xiě)“請(qǐng)求超過(guò)進(jìn)程最大需求拒絕分配”如果超過(guò) Available寫(xiě)“當(dāng)前可用資源不足進(jìn)程等待”如果分配后不安全寫(xiě)“分配后系統(tǒng)進(jìn)入不安全狀態(tài)回滾請(qǐng)求”。這三種情況的措辭要準(zhǔn)確不要混用。4. 避坑與排查銀行家算法實(shí)驗(yàn)里最容易翻車的五個(gè)地方4.1 現(xiàn)象安全序列打印出來(lái)但進(jìn)程編號(hào)重復(fù)原因通常是finish數(shù)組沒(méi)有正確標(biāo)記或者循環(huán)里沒(méi)有跳過(guò)已完成的進(jìn)程。有些實(shí)現(xiàn)用finish[i] 1但判斷時(shí)寫(xiě)if finish[i] 0邏輯是對(duì)的但如果finish初始化時(shí)用了[0] * n而后面誤寫(xiě)成finish [False]就會(huì)導(dǎo)致所有進(jìn)程都被認(rèn)為未完成。解決方法是統(tǒng)一用布爾值或 0/1并在每次選中進(jìn)程后立即標(biāo)記。4.2 現(xiàn)象Request 判斷總是返回“不安全”原因可能是試探性分配后沒(méi)有正確更新 Need。有些實(shí)現(xiàn)把 Need 當(dāng)成獨(dú)立矩陣試探性分配時(shí)只改了 Allocation 和 Available忘了 Need 也要相應(yīng)減少。雖然is_safe函數(shù)里可以用Max - Allocation重新計(jì)算 Need但如果你的代碼在別處直接引用了 Need 矩陣就會(huì)不一致。解決方法是統(tǒng)一用Max - Allocation動(dòng)態(tài)計(jì)算 Need或者試探性分配時(shí)同步更新 Need。4.3 現(xiàn)象Available 在多次請(qǐng)求后變成負(fù)數(shù)原因通常是回滾不完整。試探性分配時(shí)改了 Available 和 Allocation但回滾時(shí)只恢復(fù)了 Available沒(méi)有恢復(fù) Allocation導(dǎo)致下一次請(qǐng)求時(shí) Available 計(jì)算錯(cuò)誤。解決方法是把試探性分配寫(xiě)成一個(gè)獨(dú)立函數(shù)用副本操作失敗時(shí)直接丟棄副本不碰原數(shù)據(jù)。4.4 現(xiàn)象報(bào)告里的安全序列和代碼輸出不一致原因可能是報(bào)告里的數(shù)據(jù)是手算的而代碼用的是另一組測(cè)試用例。解決方法是先用代碼跑出結(jié)果再把結(jié)果復(fù)制到報(bào)告里。如果代碼輸出格式不友好加幾行格式化打印把安全序列和中間 Work 向量都輸出出來(lái)。4.5 現(xiàn)象答辯時(shí)被問(wèn)“為什么安全序列不唯一”答不上來(lái)原因是對(duì)算法理解停留在代碼層面。安全序列不唯一是因?yàn)槊看伪闅v進(jìn)程的順序不同只要找到一個(gè)滿足條件的進(jìn)程就可以繼續(xù)所以可能存在多個(gè)合法序列。解決方法是準(zhǔn)備一個(gè)簡(jiǎn)單例子比如兩個(gè)進(jìn)程互相不依賴先選哪個(gè)都行用這個(gè)例子說(shuō)明不唯一性。5. 進(jìn)階技巧用隨機(jī)測(cè)試驗(yàn)證你的實(shí)現(xiàn)5.1 構(gòu)造隨機(jī)測(cè)試用例手動(dòng)構(gòu)造測(cè)試用例只能覆蓋有限場(chǎng)景我一般會(huì)寫(xiě)一個(gè)隨機(jī)測(cè)試腳本生成多組 Available、Max、Allocation然后跑你的銀行家算法實(shí)現(xiàn)檢查是否滿足幾個(gè)不變量Need 始終等于 Max 減 AllocationAvailable 始終非負(fù)安全序列長(zhǎng)度等于進(jìn)程數(shù)所有進(jìn)程最終 Finish 為 True。下面是一個(gè)簡(jiǎn)單的隨機(jī)測(cè)試框架import random def random_test(n_process, n_resource, trials1000): for t in range(trials): # 隨機(jī)生成總資源量 total [random.randint(5, 15) for _ in range(n_resource)] # 隨機(jī)生成 Allocation保證不超過(guò) total allocation [[0]*n_resource for _ in range(n_process)] for i in range(n_process): for j in range(n_resource): allocation[i][j] random.randint(0, total[j] // n_process) # 計(jì)算已分配總量 allocated [sum(allocation[i][j] for i in range(n_process)) for j in range(n_resource)] # Available total - allocated available [total[j] - allocated[j] for j in range(n_resource)] # 隨機(jī)生成 Max保證 Max Allocation max_need [[0]*n_resource for _ in range(n_process)] for i in range(n_process): for j in range(n_resource): max_need[i][j] allocation[i][j] random.randint(0, available[j]) # 調(diào)用你的 is_safe 函數(shù) safe, seq is_safe(available, max_need, allocation, n_process, n_resource) # 檢查不變量 if safe: assert len(seq) n_process, f安全序列長(zhǎng)度錯(cuò)誤: {seq} # 驗(yàn)證序列確實(shí)安全 work available[:] for pid in seq: need_pid [max_need[pid][j] - allocation[pid][j] for j in range(n_resource)] assert all(need_pid[j] work[j] for j in range(n_resource)), f序列不安全: {seq} for j in range(n_resource): work[j] allocation[pid][j] print(f{trials} 次隨機(jī)測(cè)試全部通過(guò)) random_test(5, 3, 1000)這個(gè)腳本會(huì)生成 1000 組隨機(jī)數(shù)據(jù)每組都驗(yàn)證安全序列的合法性。如果某個(gè)不變量被打破斷言會(huì)直接報(bào)錯(cuò)并告訴你哪一組數(shù)據(jù)出了問(wèn)題。我建議你在提交實(shí)驗(yàn)前跑一遍這個(gè)測(cè)試能擋掉大部分邊界 bug。5.2 用邊界用例補(bǔ)刀隨機(jī)測(cè)試覆蓋的是常規(guī)情況邊界用例還得手動(dòng)構(gòu)造。比如所有進(jìn)程的 Need 都大于 Available系統(tǒng)應(yīng)該返回不安全某個(gè)進(jìn)程的 Need 全為 0它應(yīng)該第一個(gè)被選中Available 全為 0 但所有進(jìn)程 Need 也為 0系統(tǒng)仍然安全。這些用例寫(xiě)進(jìn)報(bào)告里能體現(xiàn)你對(duì)算法邊界的理解。5.3 報(bào)告里的驗(yàn)證章節(jié)怎么寫(xiě)如果你在報(bào)告里加了隨機(jī)測(cè)試可以單獨(dú)寫(xiě)一小節(jié)“算法驗(yàn)證”說(shuō)明你用了多少組隨機(jī)數(shù)據(jù)、覆蓋了哪些不變量、有沒(méi)有發(fā)現(xiàn)反例。這比只貼一段代碼運(yùn)行截圖更有說(shuō)服力。資源包里的報(bào)告模板如果沒(méi)留這個(gè)位置你可以加在“測(cè)試與分析”部分。從那以后我每次做銀行家算法實(shí)驗(yàn)都會(huì)先跑一遍隨機(jī)測(cè)試再寫(xiě)報(bào)告確認(rèn)代碼在各種邊界下都不會(huì)翻車。希望這份拆解能幫你把實(shí)驗(yàn)做得更扎實(shí)需要完整實(shí)驗(yàn)報(bào)告和源代碼的話可以直接獲取資源包對(duì)照使用。本文還有配套的精品資源點(diǎn)擊獲取