银行家算法用于确定是否可以满足所有对资源的请求而不会导致死锁。
m 是资源类型的总数
n 是进程总数
NEED 是一个大小为 m * n 的数组,它定义了每种资源类型的待处理请求。例如:NEEDij = 2 表示进程 i 正在请求 2 项资源 j。
算法如下:
BOOLEAN function SAFESTATE is -- Determines if current state is safe
{ NOCHANGE : boolean;
WORK : array[1..m] of INTEGER = AVAILABLE;
FINISH : array[1..n] of boolean = [false, ..,false];
I : integer;
repeat
NOCHANGE = TRUE;
for I = 1 to N do
if ((not FINISH[i]) and
NEEDi <= WORK) then {
WORK = WORK + ALLOCATION_i;
FINISH[i] = true;
NOCHANGE = false;
}
until NOCHANGE;
return (FINISH == (true, .., true));
}
我的问题是,时间复杂度如何为 0(n * n * m)?更具体地说,m 项如何进入多项式?是因为我们必须对长度为 m 的向量进行逐个元素的比较吗?