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