文章目录

• 数据结构.
• 向量.
• 系统安全测试算法.
• 资源请求算法.
• 实例一.
• • 解答.
• 实例二.
• • 解答.

数据结构.

• n：整型，进程数量；
• m：整型，资源类型的种类数；
• Available[m]：一维数组，保存[1…m]每种资源的可用实例数量；
• Max[n][m]：n×m矩阵，Max[i][j]表示i号进程对于j号资源的总需求量；
• Allocation[n][m]：n×m矩阵，Allocation[i][j]表示i号进程已经持有的j号资源数量；
• Need[n][m]：n×m矩阵，Need[i][j]表示i号进程还需要的j号资源数量。

向量.

• 对于两个长度为n的向量 X X X和 Y Y Y，当且仅当 X [ i ] < Y [ i ] X[i]<Y[i] X[i]<Y[i]对于所有的 i ∈ [ 1.. n ] i∈[1..n] i∈[1..n]都成立时，我们说 X < Y . X<Y. X<Y.

系统安全测试算法.

• 用于测试系统此时是否处于安全状态，算法如下：

TestSafety()
{ 
	//1.
	Work[1..m]=Available[1..m];
	//向量Work初始化为当前可用资源实例数向量.

	Finish[1..n]=false;
	//向量Finish每个分量都为false,表示初态都是未完成.

	//2.
	change=true;	//循环控制变量.
	while(change)
	{ 
		//Need[i]表示矩阵的第i行,也就是进程Pi所需资源数向量,
		//若进程Pi未完成,并且需求能够得到满足,就执行Pi,后续
		//释放其中的资源,等价于Work获得Pi已经持有的资源数向量
		//Allocation[i].
		change=false;
		for(int i=1;i<=n;++i)
		{ 
			if(Finish[i]==false && Need[i]<Work) 
			{ 
				Work=Work+Allocation[i];
				Finish[i]=true;
				change=true;
			}
		}
	}
	//不动点算法:只有当Finish和Allocation不再发生改变时,
	//也就意味着所有的进程都已经完成或者剩余进程都无法运行
	//这两种情况之一发生时，才会跳出while循环.

	//3.
	for(int i=1;i<=n;++i)
	{ 
		if(Finish[i]==false)
		{ 
			return false;
		}
	}
	return true;
	//全真为真,一假俱假.
}

资源请求算法.

• Request[n][m]：n×m矩阵，Request[i][j]表示i号进程此时申请的j号资源数量。

if(Request[i]<Need[i])
{ 
	if(Request[i]<Available)
	{ 
		//Simulate allocation.
		Available=Available-Request[i];
		Allocation[i]=Allocation[i]+Request[i];
		Need[i]=Need[i]-Request[i];
		
		if(TestSafety())
		{ 
			Agree Allocation;
			//System safe,just allocate.
		}
		else
		{ 
			Rollback;
			//System unsafe,rollback.
		}
	}
	else
	{ 
		Wait;
		//Cause resource insufficient.
	}
}
else
{ 
	Error;
	//Cause request too many resources.
}

实例一.

• 此时系统是否处于安全状态？
• 如果进程 P 1 P_1 P1​提出资源请求 R e q u e s t 1 = ( 1 , 0 , 2 ) Request_1 =(1, 0, 2) Request1​=(1,0,2)，能满足吗？
• 如果进程 P 0 P_0 P0​提出资源请求 R e q u e s t 0 = ( 0 , 2 , 0 ) Request_0 =(0, 2, 0) Request0​=(0,2,0) ，能满足吗？
• 如果进程 P 4 P_4 P4​提出资源请求 R e q u e s t 4 = ( 3 , 3 , 0 ) Request_4 =(3, 3, 0) Request4​=(3,3,0) ，能满足吗？

解答.

实例二.

2、考虑系统T0时刻的状态如下所示：

• 需求矩阵Need的内容如何？
• 此时刻该系统是否处于安全状态？
• 若此时 P 1 P_1 P1​请求资源 R e q u e s t 1 = ( 0 , 4 , 2 , 0 ) Request_1=(0,4,2,0) Request1​=(0,4,2,0)，系统是否满足其请求？为什么？

解答.