操作系统概念阅读笔记7.2

银行家算法

本文总阅读量
Posted by Xiaoxi on January 14, 2016

#银行家算法 ##一: 内容简述 ###1. 目标 多种资源银行家算法的模拟实现 ###3. 背景了解 ####1、死锁概念 在多道程序系统中,虽可借助于多个进程的并发执行,来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程。 ####2、关于死锁的一些结论:

  • 参与死锁的进程最少是两个 (两个以上进程才会出现死锁)
  • 参与死锁的进程至少有两个已经占有资源
  • 参与死锁的所有进程都在等待资源
  • 参与死锁的进程是当前系统中所有进程的子集

注:如果死锁发生,会浪费大量系统资源,甚至导致系统崩溃。 ####3、资源分类。

  • 永久性资源:
    • 可以被多个进程多次使用(可再用资源)
    • 可抢占资源
    • 不可抢占资源
  • 临时性资源:只可使用一次的资源;如信号量,中断信号,同步信号等(可消耗性资源)

  “申请–分配–使用–释放”模式

####4、产生死锁的四个必要条件: 互斥使用(资源独占)、不可抢占(不可剥夺)、请求和保持(部分分配,占有申请)、循环等待。 #####1) 互斥使用(资源独占) 一个资源每次只能给一个进程使用。 #####2) 不可强占(不可剥夺) 资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放。 #####3) 请求和保持(部分分配,占有申请) 一个进程在申请新的资源的同时保持对原有资源的占有(只有这样才是动态申请,动态分配)。 ####4) 循环等待 存在一个进程等待队列 {P1 , P2 , … , Pn}, 其中P1等待P2占有的资源,P2等待P3占有的资源,…,Pn等待P1占有的资源,形成一个进程等待环路。 ####5、死锁预防: 定义:在系统设计时确定资源分配算法,保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。 #####①破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定,一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请 #####②破坏“请求和保持”条件。 要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配。 #####③破坏“循环等待”条件 采用资源有序分配法: 把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。 ####6.安全状态与不安全状态

  1. 安全状态: 如果存在一个由系统中所有进程构成的安全序列P1,…Pn,则系统处于安全状态。一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi(1≤i≤n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和,系统处于安全状态 (安全状态一定是没有死锁发生的)
  2. 不安全状态:不存在一个安全序列,不安全状态不一定导致死锁。

##二:主要内容

  1. 设计思路 用高级语言编制银行家算法通用程序,并检测所给状态的系统安全性。 1.算法介绍:数据结构:

    1. 可利用资源向量 Available; 2.最大需求矩阵Max; 3.分配矩阵Allocation; 4.需求矩阵Need 2.功能介绍

    模拟实现Dijkstra的银行家算法以避免死锁的出现,分两部分组成:

    第一部分:银行家算法(扫描);

    第二部分:安全性算法。

    3.主要代码设计分析

    1. 银行家算法中的数据结构

      (1) 可利用资源向量Available。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。

      (2) 最大需求矩阵Max。这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。

      (3) 分配矩阵Allocation。这也是一个n×m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。

      (4) 需求矩阵Need。这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。
      Need[i,j]=Max[i,j]-Allocation[i,j]


###1.代码与初始化:


#define MAXPROCESS 100                        //最大进程数
#define MAXRESOURCE 100                       //最大资源数
int AVAILABLE[MAXRESOURCE];                   //可利用资源向量
int MAX[MAXPROCESS][MAXRESOURCE];            //最大需求矩阵
int ALLOCATION[MAXPROCESS][MAXRESOURCE];    //分配矩阵
int NEED[MAXPROCESS][MAXRESOURCE];            //需求矩阵
int REQUEST[MAXPROCESS][MAXRESOURCE];        //进程需要资源数
bool FINISH[MAXPROCESS];                        //表示系统是否有足够的资源分配给进程
int p[MAXPROCESS];                             //记录序列
int m, n;                                    //m个进程,n个资源
int i, j;									//遍历变量

void Init()            //初始化算法 初始化银行家算法中所要模拟的各种资源
{
	cout << "请输入进程的数量:";
	cin >> m;
	cout << "请输入资源的类数:";
	cin >> n;
	cout << "请输入每个资源提供的最大数量:";
	for (i = 0; i < n; i++)
		cin >> AVAILABLE[i];
	cout << "请输入每个进程最大需求资源数:(即最大需求矩阵:格式为" << m << "x" << n <<")"<< endl;
	for (i = 0; i<m; i++)
	for (j = 0; j<n; j++)
		cin >> MAX[i][j];
	cout << "请输入每个进程已分配的资源数:(即分配矩阵:格式为" << m << "x" << n << ")" << endl;
	for (i = 0; i<m; i++)
	{
		for (j = 0; j<n; j++)
		{
			cin >> ALLOCATION[i][j];
			NEED[i][j] = MAX[i][j] - ALLOCATION[i][j];
			if (NEED[i][j]<0)
			{
				cout << "对不起!您输入的第" << i + 1 << "个进程所拥有的第" << j + 1 << "个资源数值非法,请重新输入:" << endl;
				cout << "ALLOCATION[" << i + 1 << "][" << j + 1 << "]=";
				j--;
				continue;
			}
		}
	}
	//得到当前资源可利用值
	for (i = 0; i < n; i++)
	for (j = 0; j < m;j++)
	{
		AVAILABLE[j]-=ALLOCATION[i][j];
	}
	IsSafe();//判定初始值是否安全
	print();//输出当前状态
}

###2. 银行家算法 设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:

(1) 如果Requesti[j]≤Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

(2) 如果Requesti[j]≤Available[j],便转向步骤(3);否则, 表示尚无足够资源,Pi须等待。

(3) 系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:

Available[j]=Available[j]-Requesti[j]; Allocation[i,j]=Allocation[i,j]+Requesti[j]; Need[i,j]=Need[i,j]-Requesti[j];

(4) 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则, 将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。 代码:


void Bank()                //银行家算法
{
	int i, pid, number = 0;
	char flag;//标明是否继续分配

	while (1)
	{
		cout << endl;
	enterid:
		cout << "请输入要申请资源的进程ID(注:第1个进程号为0,依次类推):";
		cin >> pid;
		if (pid > m||pid < 0)
		{
			cout << "进程ID输入错误,请重新输入!" << endl;
			goto enterid;
		}
	enternum:
		cout << "请输入进程"<<pid<<"要申请的各资源数量:" << endl;
		for (i = 0; i<n; i++)
		{
			cin >> REQUEST[pid][i];
		}
		for (i = 0; i<n; i++)//验证请求是否合理
		{
			if (REQUEST[pid][i]>NEED[pid][i])//进程ID申请的资源数量大于其所需要的进程数量
			{
				cout << "进程"<<pid<<"所申请的资源"<<i<<"的数量超出其进程实际需求量!请重新输入!" << endl;
				goto enternum;
			}
			if (REQUEST[pid][i]>AVAILABLE[i])//进程ID申请的资源数量大于系统剩余可用数量
			{
				cout << "进程"<<pid<<"所申请的资源"<<i<<"的数量超出系统剩余最大可用量!请重新输入!" << endl;
				goto enternum;
			}
		}
		for (i = 0; i<n; i++)//如果请求合理,分配资源,计算分配后资源数量
		{
			AVAILABLE[i] -= REQUEST[pid][i];//剩余可用数量
			ALLOCATION[pid][i] += REQUEST[pid][i];//已分配数量
			NEED[pid][i] -= REQUEST[pid][i];//还需要的数量
		}
		if (IsSafe())//判定若资源分配后,是否安全。若安全,则同意分配。
		{
			cout << "系统状态安全,可以分配!" << endl;
		}
		else
		{
			cout << "系统状态为不安全,不可分配!" << endl;
			for (i = 0; i<n; i++)//回到原数量
			{
				AVAILABLE[i] += REQUEST[pid][i];
				ALLOCATION[pid][i] -= REQUEST[pid][i];
				NEED[pid][i] += REQUEST[pid][i];
			}
		}
		for (i = 0; i<n; i++)
		{
			if (NEED[pid][i] == 0)//进程pid的资源i分配完毕
			{
				number++;
			}
		}
		if (number == n)//如果该进程各资源都已分配完毕,则释放资源
		{
			for (i = 0; i<n; i++)
			{
				AVAILABLE[i] += ALLOCATION[pid][i];
				ALLOCATION[pid][i] = 0;
				NEED[pid][i] = 0;
			}
			cout << "进程" << pid << "分配完毕,其占有的资源被释放!" << endl;
			print();//输出当前状态
			number = 0;
		}
		for (i = 0; i<m; i++)//分配好了以后将进程的标识FINISH改成false
		{
			FINISH[i] = false;
		}
		cout << "是否继续请求分配资源?(若是,请输入y/Y.否则输入其它)" << endl;
		cin >> flag;
		if (flag == 'y' || flag == 'Y')
		{
			continue;
		}
		break;
	}
}

###3. 安全性算法 系统所执行的安全性算法可描述如下:

(1) 设置两个向量:

① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work=Available;

② Finish向量: 它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]=false; 当有足够资源分配给进程时, 再令Finish[i]=true。

(2) 从进程集合中找到一个能满足下述条件的进程:

① Finish[i]=false;

② Need[i,j]≤Work[j]; 若找到, 执行步骤(3), 否则,执行步骤 (4)。

(3) 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资 源,故应执行:

Work[j]=Work[i]+Allocation[i,j];
 Finish[i]=true;
 go to step 2;  (4) 如果所有进程的Finish[i]=true都满足, 则表示系统处于安全状态;否则,系统处于不安全状态。 

代码:

bool IsSafe() //安全性算法  判定当前状态,工作是否安全  安全则返回true 不安全返回flase
{
	int  l = 0;
	int Work[MAXRESOURCE];							//表示系统可提供给进程继续运行所需的各类资源数目
	for (i = 0; i < n; i++)//对work进行初始化
		Work[i] = AVAILABLE[i];
	for (i = 0; i < m; i++)//对finish进行初始化
	{
		FINISH[i] = false;//先初始化为不安全
	}
	while (l<m)//正常的话,共执行m次
	{
		int flag=0;//0为不安全,1为安全
		for (i = 0; i < m; i++)//对m个进程一次检查
		{
			if (FINISH[i] == true)
			{
				continue;
			}
			for (j = 0; j < n; j++)
			{
				if (NEED[i][j] > Work[j])
				{
					break;
				}
			}
			if (j == n)//表明进程i是安全的,进程i获得资源后,可顺利执行,直至完成,并释放出分配给它的资源
			{
				FINISH[i] = true;//进程i安全
				for (int k = 0; k < n; k++)
				{
					Work[k] += ALLOCATION[i][k];
				}
				p[l++] = i;//记录进程号
				flag = 1;//表示不安全
			}
			else//进程i是不安全的
			{
				continue;
			}
		}
		if (!flag)
		{
			cout << "系统是不安全的" << endl;
			return false;
		}
	}
	cout << "系统是安全的" << endl;
	cout << "安全序列:" << endl;
	for (i = 0; i < l; i++)//显示资源分配给进程的顺序
	{
		cout << p[i];
		if (i != l - 1)
		{
			cout << "-->";
		}
	}
	cout << "" << endl;
	return true;
}