急！银行家算法用C语言编写．全部程序．

银行家算法

银行家算法是一种最有代表性的避免死锁的算法。

要解释银行家算法，必须先解释 *** 作系统安全状态和不安全状态。

安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。

那么什么是安全序列呢？

安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

银行家算法：

我们可以把 *** 作系统看作是银行家， *** 作系统管理的资源相当于银行家管理的资金，进程向 *** 作系统请求分配资源相当于用户向银行家贷款。 *** 作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

算法：

n：系统中进程的总数

m：资源类总数

Available: ARRAY[1m] of integer;

Max: ARRAY[1n,1m] of integer;

Allocation: ARRAY[1n,1m] of integer;

Need: ARRAY[1n,1m] of integer;

Request: ARRAY[1n,1m] of integer;

符号说明：

Available 可用剩余资源

Max 最大需求

Allocation 已分配资源

Need 需求资源

Request 请求资源

当进程pi提出资源申请时，系统执行下列

步骤：(“=”为赋值符号，“==”为等号)

step（1）若Request<=Need, goto step（2）；否则错误返回

step（2）若Request<=Available, goto step（3）；否则进程等待

step（3）假设系统分配了资源，则有：

Available=Available-Request;

Allocation=Allocation+Request;

Need=Need-Request

若系统新状态是安全的，则分配完成

若系统新状态是不安全的，则恢复原状态，进程等待

为进行安全性检查，定义数据结构：

Work:ARRAY[1m] of integer;

Finish:ARRAY[1n] of Boolean;

安全性检查的步骤：

step (1):

Work=Available;

Finish=false;

step (2) 寻找满足条件的i：

aFinish==false;

bNeed<=Work;

如果不存在，goto step(4)

step(3)

Work=Work+Allocation;

Finish=true;

goto step(2)

step (4) 若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态

/ 银行家算法， *** 作系统概念(OS concepts Six Edition)

reedit by Johnny hagen，SCAU，run at vc60

/

#include "malloch"

#include "stdioh"

#include "stdlibh"

#define alloclen sizeof(struct allocation)

#define maxlen sizeof(struct max)

#define avalen sizeof(struct available)

#define needlen sizeof(struct need)

#define finilen sizeof(struct finish)

#define pathlen sizeof(struct path)

struct allocation

{

int value;

struct allocation next;

};

struct max

{

int value;

struct max next;

};

struct available /可用资源数/

{

int value;

struct available next;

};

struct need /需求资源数/

{

int value;

struct need next;

};

struct path

{

int value;

struct path next;

};

struct finish

{

int stat;

struct finish next;

};

int main()

{

int row,colum,status=0,i,j,t,temp,processtest;

struct allocation allochead,alloc1,alloc2,alloctemp;

struct max maxhead,maxium1,maxium2,maxtemp;

struct available avahead,available1,available2,workhead,work1,work2,worktemp,worktemp1;

struct need needhead,need1,need2,needtemp;

struct finish finihead,finish1,finish2,finishtemp;

struct path pathhead,path1,path2;

printf("\n请输入系统资源的种类数:");

scanf("%d",&colum);

printf("请输入现时内存中的进程数:");

scanf("%d",&row);

printf("请输入已分配资源矩阵:\n");

for(i=0;i<row;i++)

{

for (j=0;j<colum;j++)

{

printf("请输入已分配给进程 p%d 的 %c 种系统资源:",i,'A'+j);

if(status==0)

{

allochead=alloc1=alloc2=(struct allocation)malloc(alloclen);

alloc1->next=alloc2->next=NULL;

scanf("%d",&allochead->value);

status++;

}

else

{

alloc2=(struct allocation )malloc(alloclen);

scanf("%d,%d",&alloc2->value);

if(status==1)

{

allochead->next=alloc2;

status++;

}

alloc1->next=alloc2;

alloc1=alloc2;

}

}

}

alloc2->next=NULL;

status=0;

printf("请输入最大需求矩阵:\n");

for(i=0;i<row;i++)

{

for (j=0;j<colum;j++)

{

printf("请输入进程 p%d 种类 %c 系统资源最大需求:",i,'A'+j);

if(status==0)

{

maxhead=maxium1=maxium2=(struct max)malloc(maxlen);

maxium1->next=maxium2->next=NULL;

scanf("%d",&maxium1->value);

status++;

}

else

{

maxium2=(struct max )malloc(maxlen);

scanf("%d,%d",&maxium2->value);

if(status==1)

{

maxhead->next=maxium2;

status++;

}

maxium1->next=maxium2;

maxium1=maxium2;

}

}

}

maxium2->next=NULL;

status=0;

printf("请输入现时系统剩余的资源矩阵:\n");

for (j=0;j<colum;j++)

{

printf("种类 %c 的系统资源剩余:",'A'+j);

if(status==0)

{

avahead=available1=available2=(struct available)malloc(avalen);

workhead=work1=work2=(struct available)malloc(avalen);

available1->next=available2->next=NULL;

work1->next=work2->next=NULL;

scanf("%d",&available1->value);

work1->value=available1->value;

status++;

}

else

{

available2=(struct available)malloc(avalen);

work2=(struct available)malloc(avalen);

scanf("%d,%d",&available2->value);

work2->value=available2->value;

if(status==1)

{

avahead->next=available2;

workhead->next=work2;

status++;

}

available1->next=available2;

available1=available2;

work1->next=work2;

work1=work2;

}

}

available2->next=NULL;

work2->next=NULL;

status=0;

alloctemp=allochead;

maxtemp=maxhead;

for(i=0;i<row;i++)

for (j=0;j<colum;j++)

{

if(status==0)

{

needhead=need1=need2=(struct need)malloc(needlen);

need1->next=need2->next=NULL;

need1->value=maxtemp->value-alloctemp->value;

status++;

}

else

{

need2=(struct need )malloc(needlen);

need2->value=(maxtemp->value)-(alloctemp->value);

if(status==1)

{

needhead->next=need2;

status++;

}

need1->next=need2;

need1=need2;

}

maxtemp=maxtemp->next;

alloctemp=alloctemp->next;

}

need2->next=NULL;

status=0;

for(i=0;i<row;i++)

{

if(status==0)

{

finihead=finish1=finish2=(struct finish)malloc(finilen);

finish1->next=finish2->next=NULL;

finish1->stat=0;

status++;

}

else

{

finish2=(struct finish)malloc(finilen);

finish2->stat=0;

if(status==1)

{

finihead->next=finish2;

status++;

}

finish1->next=finish2;

finish1=finish2;

}

}

finish2->next=NULL; /Initialization compleated/

status=0;

processtest=0;

for(temp=0;temp<row;temp++)

{

alloctemp=allochead;

needtemp=needhead;

finishtemp=finihead;

worktemp=workhead;

for(i=0;i<row;i++)

{

worktemp1=worktemp;

if(finishtemp->stat==0)

{

for(j=0;j<colum;j++,needtemp=needtemp->next,worktemp=worktemp->next)

if(needtemp->value<=worktemp->value)

processtest++;

if(processtest==colum)

{

for(j=0;j<colum;j++)

{

worktemp1->value+=alloctemp->value;

worktemp1=worktemp1->next;

alloctemp=alloctemp->next;

}

if(status==0)

{

pathhead=path1=path2=(struct path)malloc(pathlen);

path1->next=path2->next=NULL;

path1->value=i;

status++;

}

else

{

path2=(struct path)malloc(pathlen);

path2->value=i;

if(status==1)

{

pathhead->next=path2;

status++;

}

path1->next=path2;

path1=path2;

}

finishtemp->stat=1;

}

else

{

for(t=0;t<colum;t++)

alloctemp=alloctemp->next;

finishtemp->stat=0;

}

}

else

for(t=0;t<colum;t++)

{

needtemp=needtemp->next;

alloctemp=alloctemp->next;

}

processtest=0;

worktemp=workhead;

finishtemp=finishtemp->next;

}

}

path2->next=NULL;

finishtemp=finihead;

for(temp=0;temp<row;temp++)

{

if(finishtemp->stat==0)

{

printf("\n系统处于非安全状态!\n");

exit(0);

}

finishtemp=finishtemp->next;

}

printf("\n系统处于安全状态\n");

printf("\n安全序列为: \n");

do

{

printf("p%d ",pathhead->value);

}

while(pathhead=pathhead->next);

printf("\n");

return 0;

}

集束搜索（又名定向搜索，Beam Search）——最佳优先搜索算法的优化。

A搜寻算法——图形搜索算法，是最佳优先搜索的范例，从给定起点到给定终点计算出路径。

数据压缩——采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对信息编码的过程，又叫来源编码。

离散微分算法（Discrete differentiation）

哈希算法（Hashing）

堆排序（Heaps）

合并排序（Merge Sort）

梯度下降（Gradient descent）——一种数学上的最优化算法。

牛顿法（Newton's method）——求非线性方程（组）零点的一种重要的迭代法。

欧几里得算法（Euclidean algorithm）——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

动态规划算法（Dynamic Programming）——展示互相覆盖的子问题和最优子架构算法。

Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

二分查找（Binary Search）——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

合并查找算法（Union-find）——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。

期望-最大算法（Expectation-maximization algorithm，又名EM-Training）——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。

快速傅里叶变换（Fast Fourier transform，FFT）——计算离散的傅里叶变换（DFT）及其反转。

最大流量算法（Maximum flow）——该算法试图从一个流量网络中找到最大的流。

LLL算法（Lenstra-Lenstra-Lovasz  lattice reduction）——以格规约（lattice）基数为输入，输出短正交向量基数。

两次筛法（Quadratic Sieve）——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法（仅次于数域筛法Number Field Sieve）。

RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。

求解线性方程组（Solving a system of linear equations）——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法（Gauss-Jordan elimination），或是柯列斯基分解（ Cholesky decomposition）。

Q-learning学习算法——这是一种通过学习动作值函数（action-value function）完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。

Schönhage-Strassen算法——在数学中，Schönhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。

RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。

Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域（ homogenous region），看看它是否属于边缘，还是是一个顶点。

单纯型算法（Simplex Algorithm）——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。

奇异值分解（Singular value decomposition，简称SVD）——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵（以求解最小二乘法问题）、解决超定线性系统（overdetermined linear systems）、矩阵逼近、数值天气预报等等。

维特比算法（Viterbi algorithm）——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

以上就是关于急！银行家算法用C语言编写．全部程序．全部的内容，包括:急！银行家算法用C语言编写．全部程序．、程序员必须掌握哪些算法、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！