[用C++实现进程安全序列搜索算法]windowC/C++创建新进程
摘要:该文通过分析银行家算法的核心思想,提出了一种在系统某一时刻进程安全序列的搜索算法,并利用面向对象编程语言C#实现了该算法。 关键词:银行家算法;C#语言;安全序列;搜索算法
中图分类号:TP312文献标识码:A文章编号:1009-3044(2012)21-5104-03
Implementation of Search Algorithm for Secured Sequence by C++ Language
ZHANG Fan
(School of Informational Engineering, Zhongzhou University, Zhengzhou 450000, China)
Abstract: Based on the core idea of the banker’s algotithm,an algorithm which searchs all processes for a Secured Sequence at a given time is implemented by C++ language.
Key words: banker’s algorithm; C++ language;secured sequence; search algorithm
在多道程序系统中,可通过多个进程的并发执行来改善系统的资源利用率,提高系统的处理能力。为了避免与时间有关的错误,人们建立了各种同步机构。但是有这样一种种与时间有关的错误需要进一步研究和探讨,这就是死锁问题。所谓死锁是指两个或两个以上进程处于无休止地等待永远不成立的条件的状态。
Dijkstra的银行家算法是最有代表性的避免死锁算法。允许进程动态地申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,便将资源分配给进程;否则,进程进入等待状态。所谓安全状态,是指系统能按某种顺序(P1,P2,…,Pn)来为每个进程分配其所需资源,直至最大需求,使每个进程都可顺序完成。我们称(P1,P2,…,Pn)序列为安全序列。若系统不存在这样一个安全序列,则称系统处于不安全状态。
1算法的设计与流程
1.1算法流程图
如图1所示。
1.2算法的数据结构
1)可利用资源向量Available,它是一个最多含有100个元素的数组,其中的每一个元素代表一类可利用的资源的数目,其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available(j)=k,标是系统中现有j类资源k个。
2)最大需求矩阵Max,这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k,表示进程i需要j类资源的最大数目为k。
3)分配矩阵Allocation,这也是一个n×m的矩阵,它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Alloca tion(i,j)=k,表示进程i当前已经分到j类资源的数目为k。Allocation i表示进程i的分配向量,有矩阵Allocation的第i行构成。
4)需求矩阵Need,这还是一个n×m的矩阵,用以表示每个进程还需要的各类资源的数目。如果Need(i,j)=k,表示进程i还需要j类资源k个,才能完成其任务。Need i表示进程i的需求向量,由矩阵Need的第i行构成。
5)上述三个矩阵间存在关系:Need(i,j)=Max(i,j)-Allocation(i,j);
1.3安全性检测
1)如果Requesti≤Need,则转向步骤2;否则,认为出错,因为它所请求的资源数已超过它当前的最大需求量。
2)如果Requesti≤Available,则转向步骤3;否则,表示系统中尚无足够的资源满足i的申请,i必须等待。
3)系统试探性地把资源分配给进程i,并修改下面数据结构中的数值:
Available = Available - Requesti
Allocationi = Allocationi + Requesti
Needi = Needi - Requesti
4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。如果安全才正式将资源分配给进程i,以完成本次分配;否则,将试探分配作废,恢复原来的资源分配状态,让进程i等待。
2算法的实现
用C++语言编写主体程序如下:
#include
#include
#include
#define False 0
#define True 1
using namespace std;
int Max[100][100]={0};//各进程所需各类资源的最大需求int Avaliable[100]={0};//系统可用资源
char name[100]={0};//资源的名称
int Allocation[100][100]={0};//系统已分配资源
int Need[100][100]={0};//还需要资源
int Request[100]={0};//请求资源向量
int temp[100]={0};//存放安全序列
int Work[100]={0};//存放系统可提供资源
int M=100;//进程的最大数为
int N=100;//资源的最大数为
int safe()//安全性算法