最大需求与当前持有量

算法需要知道系统资源总量、当前空闲量、各进程已取得的资源及声明的最大需求。剩余需求等于最大需求减去已分配量;多类资源时要逐类比较,不能把不同种类简单加成一个总数。

Dijkstra以等价资源单位说明安全性:即使某个请求没有超过当前空闲量,分配后也可能让所有进程都还缺少进一步资源,而没有一个能先完成归还。请求必须同时满足声明范围、当前供给和分配后安全状态等条件。

参考:[1] [2]

用假想完成顺序检验安全性

安全检查先把当前空闲量作为工作余量,找一个剩余需求不超过工作余量的未完成进程。假想它得到所需资源、完成并归还后,把它原先持有的资源加回工作余量;重复直到所有进程都可完成,或再也找不到合适对象。

这里允许剩余需求恰好等于工作余量。例如共有4单位,两进程最大各需3单位,当前分别持有2和1单位,空闲1单位;第一进程再得1便能完成并归还,随后第二进程也可完成。检查找到的是可行次序,不要求实际调度只能严格按这个次序运行。

参考:[1] [2]

不安全不等于已经死锁

分配请求可先在副本状态中试算,只有试算仍安全才真正提交;否则等待更合适的状态。不安全意味着无法依声明的最大需求保证完成,不等于进程此刻一定已经死锁,因为实际后续需求可能小于上界。

这种方法依赖可用的需求上界、遵守声明的申请行为以及完成后归还资源的模型。检查和延迟分配有成本,过大的保守上界也会减少可利用的并发;它不是适用于所有动态工作负载的通用调度器,更不能在发生任意锁等待后直接套用资源数字就得到保证。

参考:[1] [2]