【语法】
一、隐蔽陷阱
三类资源要在五个进程间分配:随手分出去,可能出现每个进程都差一点资源、互相等待的死局——逐种分配方案试到天亮也试不完,有没有一次检查就判定安全的算法?
二、底层原理
银行家算法安全性检查:先算每个进程还需要的资源量,用当前可用资源逐个满足"需求不超过可用"的进程并回收其全部持有,回收扩大的可用量又能解锁下一个。全部进程都能走完则序列安全。
三、正确代码
基础写法(需求矩阵):
local function need(maxs, alloc)
local t = {}
for i = 1, #maxs do
t[i] = {}
for j = 1, #maxs[i] do
t[i][j] = maxs[i][j] - alloc[i][j]
end
end
return t
end
进阶写法(安全序列检查):
local function isSafe(nd, alloc, avail)
local n, done, work = #nd, {}, {}
for j = 1, #avail do work[j] = avail[j] end
local safe, moved = 0, true
while safe < n and moved do
moved = false
for i = 1, n do
if not done[i] then
local ok = true
for j = 1, #work do
if nd[i][j] > work[j] then
ok = false
end
end
if ok then
done[i] = true
safe = safe + 1
for j = 1, #alloc[i] do
work[j] = work[j] + alloc[i][j]
end
moved = true
end
end
end
end
return safe == n
end
四、引擎验证
五进程样例存在安全序列返回 true;调大某进程的需求制造死局后返回 false,与手工推演一致。
五、FAQ
问:名字为何像银行?
答:放贷同理,只放不致无法回收的额度。
问:检查通过再分配?
答:是,每次分配前先跑一遍检查。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【语法算法】 一、一个不报错的偏移 点击地图走路,人物落点总是往右下偏半格;技能点地释放,特效又偏左上小半格。控制台干干净净…
【语法算法】 一、一行代码拆解 pos = pos + (target - pos) math.min(1, k dt) —…
【游戏功能】 一、一次被黑暗淹没的上线 夜间版本上线当晚,客服工单一半是"地图全黑看不见路",另一半是"火把一多就卡成幻灯片…
【游戏功能】 一、先抛一个坑 为什么世界BOSS的血条会一段一段换颜色?打空一段才掉下一段,最后一段永远是红色?如果只是把总…
【游戏功能】 一、一次本可避免的差评 PC 版上线第六天,应用商店冒出一条一星评论:"背包都不能滚轮翻,什么年代了。"复现一…
【游戏功能】 一、先抛一个坑 同样挂一层状态,为什么中毒的怪照跑不误、冰冻的怪却像被拔了电源?再进一步:冰冻到点的瞬间,怪为…