python实现银行家算法
① 银行家算法的实现，安全性算法中 这条语句是什么意思Work［j］∶=Work［i］+Allocation［i,j];
work[j]表示当前系统可用的第j类资源，Allocation[i][j]表示当前已经分配给进程i使用的第j类资源数量。
Work[j]= Work[j]+ Allocation[i][j]
这句的意思是目前进程已经利用手上资源完成相关工作了，这些已分配的资源可以重新归还系统了，所以系统可用的第j类资源work[j]就增加了，增加量就是当前进程想要归还的资源量Allocation[i][j]
如有疑惑欢迎追问！
② 银行家算法
什么是银行家算法：
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态
不存在一个安全序列。不安全状态不一定导致死锁。
原理：
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全,银行家规定:
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量;
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
程序举例：
已知进程{P0,P1,P2,P3,P4}，有三类系统资源A、B、C的数量分别为10、5、7，在T0时刻的资源
（1）若进程P1请求资源，发出请求向量Request1（1，0，2），编写程序用银行家算法判断系统能否将资源分配给它；
（2）若进程P2提出请求Request(0，1，0)，用银行家算法程序验证系统能否将资源分配给它。
程序代码：
P1进程提出的请求，可以分配。
P2进程不能分配，因为请求的B类资源超过了它的最大值。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 50
void main()
{
unsigned int Available[MAXSIZE]; //可利用资源向量
unsigned int Max[MAXSIZE][MAXSIZE]; //最大需求矩阵
unsigned int Allocation[MAXSIZE][MAXSIZE]; //已分配矩阵
unsigned int Need[MAXSIZE][MAXSIZE]; //需求矩阵
unsigned int Request[MAXSIZE]; //请求向量
unsigned int Work[MAXSIZE]; //工作向量
bool Finish[MAXSIZE]; //是否有足够资源分配给进程,使之运行完成
unsigned int SafeSequence[MAXSIZE]; //安全序列
int i,j;
int p; //请求资源的进程的下标
int temp = 0; //安全序列下标
int total = 0;
int N;
int M;
printf("请输入进程数N=");
scanf("%d",&N);
printf("请输入资源种类数M=");
scanf("%d",&M);
//用户输入数据,初始化Available数组
printf("初始化可用资源数组:\n");
for(i=0; i<M; i++)
{
printf("\t%c类资源:",65+i);
scanf("%d",&Available[i]);
}
//用户输入数据,初始化Max数组
printf("初始化最大需求数组:\n");
for(i=0; i<N; i++)
{
printf("\tP%d进程最大需要\n",i);
for(j=0; j<M; j++)
{
printf("\t\t%c类资源:",65+j);
scanf("%d",&Max[i][j]);
}
}
//用户输入数据,初始化Allocation数组
printf("初始化已分配资源数组:\n");
for(i=0; i<N; i++)
{
printf("\tP%d进程已分配\n",i);
for(j=0; j<M; j++)
{
printf("\t\t%c类资源:",65+j);
scanf("%d",&Allocation[i][j]);
}
}
//初始化Need数组
for(i=0; i<N; i++)
for(j=0; j<M; j++)
{
Need[i][j] = Max[i][j] - Allocation[i][j];
}
//进程发出资源请求后检查
do
{
printf("资源请求:\n");
printf("\t输入请求资源的进程下标:");
scanf("%d",&p);
printf("\t进程P%d请求\n",p);
//初始化请求向量
for(i=0; i<M; i++)
{
printf("\t\t%c类资源:",65+i);
scanf("%d",&Request[i]);
}
for(i=0; i<M; i++) //检查Request <= Need ?
if(Request[i] > Need[p][i])
{
printf("\t请求的%c类资源数超过它所宣布的最大值!\n",65+i);
break;
}
if(i == M) //通过上层检查,继续检查Request <= Available ?
{
for(i=0; i<M; i++)
if(Request[i] > Available[i])
{
printf("\t尚无足够%c类资源,P%d须等待!\n",65+i,p);
break;
}
}
if(i == M) //尝试分配
{
for(i=0; i<M; i++)
{
Available[i] -= Request[i];
Allocation[p][i] += Request[i];
Need[p][i] -= Request[i];
}
}
}while(i<M);
//初始化Work,Finish向量
for(i=0; i<M; i++)
{
Work[i] = Available[i];
}
for(i=0; i<N; i++)
{
Finish[i] = false;
}
//安全性算法
do
{
total = temp;
for(i=0; i<N; i++)
{
if(Finish[i] == false)
{
for(j=0; j<M; j++)
if(Need[i][j] > Work[j])
{
break;
}
if(j == M) //各类资源都满足Need <= Work
{
for(j=0; j<M; j++)
{
Work[j] += Allocation[i][j]; //释放资源
}
Finish[i] = true;
SafeSequence[temp++] = i; //加入安全序列
}
}
}
}while(total != temp); //所有进程检查一遍之后，如果安全序列有变化，则进行下一轮
//否则说明所有的Finish都为true,或者因没有安全序列退出循环
if(temp == N)
{
printf("安全序列:");
for(temp=0; temp<N; temp++)
{
printf("P%d ",SafeSequence[temp]);
}
}
else
{
printf("系统处于不安全状态!不能分配!\n");
}
getchar();
getchar();
}
这个程序还行，输入有点麻烦，我自己编写的是用文件输入系统描述信息的，但是缺少说明，怕你搞不明白。希望对你有所帮助！
③ 编程实现银行家安全算法
#include <iostream>
using namespace std;
#define MAXPROCESS 50 /*最大进程数*/
#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个资源*/
void Init();
bool Safe();
void Bank();
int main()
{
Init();
Safe();
Bank();
}
void Init() /*初始化算法*/
{
int i,j;
cout<<"请输入进程的数目:";
cin>>m;
cout<<"请输入资源的种类:";
cin>>n;
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;
j--;
continue;
}
}
}
cout<<"请输入各个资源现有的数目:"<<endl;
for(i=0;i<n;i++)
{
cin>>AVAILABLE[i];
}
}
void Bank() /*银行家算法*/
{
int i,cusneed;
char again;
while(1)
{
cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl;
cin>>cusneed;
cout<<"请输入进程所请求的各资源的数量"<<endl;
for(i=0;i<n;i++)
{
cin>>REQUEST[cusneed][i];
}
for(i=0;i<n;i++)
{
if(REQUEST[cusneed][i]>NEED[cusneed][i])
{
cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl;
continue;
}
if(REQUEST[cusneed][i]>AVAILABLE[i])
{
cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl;
continue;
}
}
for(i=0;i<n;i++)
{
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
}
if(Safe())
{
cout<<"同意分配请求!"<<endl;
}
else
{
cout<<"您的请求被拒绝!"<<endl;
for(i=0;i<n;i++)
{
AVAILABLE[i]+=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];
NEED[cusneed][i]+=REQUEST[cusneed][i];
}
}
for(i=0;i<m;i++)
{
FINISH[i]=false;
}
cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl;
cin>>again;
if(again=='y'||again=='Y')
{
continue;
}
break;
}
}
bool Safe() /*安全性算法*/
{
int i,j,k,l=0;
int Work[MAXRESOURCE]; /*工作数组*/
for(i=0;i<n;i++)
Work[i]=AVAILABLE[i];
for(i=0;i<m;i++)
{
FINISH[i]=false;
}
for(i=0;i<m;i++)
{
if(FINISH[i]==true)
{
continue;
}
else
{
for(j=0;j<n;j++)
{
if(NEED[i][j]>Work[j])
{
break;
}
}
if(j==n)
{
FINISH[i]=true;
for(k=0;k<n;k++)
{
Work[k]+=ALLOCATION[i][k];
}
p[l++]=i;
i=-1;
}
else
{
continue;
}
}
if(l==m)
{
cout<<"系统是安全的"<<endl;
cout<<"安全序列:"<<endl;
for(i=0;i<l;i++)
{
cout<<p[i];
if(i!=l-1)
{
cout<<"-->";
}
}
cout<<""<<endl;
return true;
}
}
cout<<"系统是不安全的"<<endl;
return false;
}
我的有解释,你看不明白就找我.QQ:64316016
④ python多线程
有很多的场景中的事情是同时进行的,比如开车的时候,手和脚共同来驾驶汽车,再比如唱歌跳舞也是同时进行的
结果:
• _thread
• threading(推荐使用)
结果:
threading.enumerate() 可查看当前正在运行的线程
结果:
结果:
结果:
结果: 出现资源竞争导致计算结果不正确
(1)当多个线程几乎同时修改某一个共享数据的时候,需要进行同步控制
(2)线程同步能够保证多个线程安全访问资源,最简单的同步机制是引入互斥锁
(3)互斥锁为资源引入一个状态: 锁定/非锁定
(4)某个线程要更爱共享数据时,先将其锁定,此时资源的状态为"锁定", 其他线程不能更改;直到该线程释放资源,将资源状态变为"非锁定"
(5)互斥锁保证了每次只有一个线程进行写入操作,从而保证了多线程情况下数据的正确性
结果: 计算正确
结果:卡住了
在线程间共享多个资源的时候,如果两个线程分别战友一部分资源且同时等待对方资源,就会造成死锁
(1)程序设计时避免(银行家算法)
(2)添加超时时间
⑤ 第三章 银行家算法
（1）各类可利用资源的数量
u向量Available：（i1，i2，…，im），含m个元素，每个元素代表一类可利用的资源数目。
u动态变化的，初始值是系统配置的该类资源的全部数目，值随资源的分配与回收而动态的改变。
u实现：一维数组。Available【j】=K，表示系统中Rj类资源现有可用数量为K个。
（2）每个进程对每类资源的需求
最大需求、已获得的、还需要的
v最大需求矩阵Max
vn*m，系统中n个进程中每个进程分别对m类资源的最大需求。
v取值：根据进程需求赋初始值。
v实现：二维数组。Max【i，j】=K，表示进程 i
需要Rj类资源的最大数目为K。
算法过程：
就是对各进程的Request向量及资源数量进行一系列判断及值操作。
进程Pi发出资源请求后，系统按下述步骤进行检查：
首先是两个基本判断：
（1）IF Requesti[j]<= Need[i,j]
THEN转向步骤2；
ELSE认为出错，所需资源数超过宣布的最大值（自我矛盾)
（2）IF Requesti[j]<= Available[j]
THEN转向步骤3；
ELSE表示尚无足够资源，Pi需等待（现实不满足）
如果上面两步判断都通过了，进入实质的资源分析
（3）系统试探着把资源分配给进程Pi
，并修改相应数据结构的值（假设性操作）：
Available【j】 =
Allocation【i,j】=
Need【i,j】=
（4）系统执行安全性算法，判断新的资源分配状态是否是安全的。
即：找一个安全序列，使这些进程按顺序执行完）如果能够找到，则将假设操作真正实施完成资源分配。
（1）需要一些记录信息的数据结构，设置两个向量：
v工作向量work
算法开始时work=Available;
系统找安全序列的过程需要不断判断和修改当前资源数量，不能直接修改原始数据记录Aailable。
v标志向量Finish
表示每个进程是否有足够的资源使之运行完成。开始时所以进程都设置初值Finish[i]:=false;
找安全序列的过程相当于使所有Finish[i]:=true。
（2）找安全序列的过程
从Finish[i] = false 的进程集合中找一个进程
IFNeed[i,j] <= work[j]
THEN 执行步骤 a;
ELSE 执行步骤 b;
a）假设Pi获得资源顺利执行完，释放出分配给它的资源，修改相应的值：
work【j】 = work【i】+Allocation【i，j】;
Finish【i】= true;
goto step （2）;//返回去继续找下一个进程。
b）当算法不再在（2）、a）步间循环找进程，到达本步时，若所有Finish[i]=true都满足，则表示所有进程都按某个顺序执行完了，系统处于安全状态；否则，系统当前所处的资源分配状态是不安全状态。
⑥ 银行家算法是如何实现的
银行家算法是从当前状态出发，逐个按安全序列检查各客户中谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下一个能完成工作的客户。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。
�7�4 与预防死锁的几种方法相比较，限制条件少，资源利用程度提高了。
�7�4 缺点：该算法要求客户数保持固定不变，这在多道程序系统中是难以做到的；该算法保证所有客户在有限的时间内得到满足，但实时客户要求快速响应，所以要考虑这个因素；由于要寻找一个安全序列，实际上增加了系统的开销.
Banker algorithm 最重要的一点是：保证操作系统的安全状态！这也是操作系统判断是否分配给一个进程资源的标准！那什么是安全状态？举个小例子，进程 P 需要申请 8 个资源（假设都是一样的），已经申请了 5 个资源，还差 3 个资源。若这个时候操作系统还剩下 2 个资源。很显然，这个时候操作系统无论如何都不能再分配资源给进程 P 了，因为即使全部给了他也不够，还很可能会造成死锁。若这个时候操作系统还有 3 个资源，无论 P 这一次申请几个资源，操作系统都可以满足他，因为操作系统可以保证 P 不死锁，只要他不把剩余的资源分配给别人，进程 P 就一定能顺利完成任务。 为什么银行家算法是可行的呢？这里需要严格的证明一下。不管任何时候，操作系统分配资源的时候都可以保证当前接受资源的进程不会陷入死锁，因为操作系统总是可以满足该进程需要的资源的。假设有 n 个进程 {p1, p2, p3, … pn} ，最后一个分配到资源的是 pi ， pi 还需要 mi 个资源，假设此时操作系统还有 m 个资源剩余。那么很显然 m>=mi ！而且如果之后操作系统又把资源分配给其他进程了，假设是 pj ， pj 还需要 mj 个资源，同理可知 m>=mj ！也就是说在所有的进程中，还需要的资源数总是有小于 m 的！这样就可以保证资源数永远不会为 0 ，即使可能暂时性为 0 。另外，还需要保证资源数不会减少！而且，所有已经分配到资源的进程总有一天会归还它所拥有的资源！根据操作系统再分配的时候的状态即可判定。
⑦ 浅析银行家算法
作为避免死锁的一种算法，银行家算法可以说是最为出名的了。这个名字的来源是因为该算法起初是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在操作系统中也可以用它来实现避免死锁。
首先我们要了解银行家算法的本质也即避免死锁的原理。避免死锁作为一种事先预防死锁的策略，原理是在为各个进程分配资源的过程中不允许系统进去不安全状态，以此来避免死锁的发生。所谓安全状态，是指系统能按某种进程推进顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利地完成。此时称该进程推进序列为安全序列，如果无法找到这样一个安全序列，则称系统处于不安全状态。
银行家算法中的数据结构。为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源，所有进程对资源的最大需求，系统中的资源分配以及所有进程还需要多少资源的情况。
(1)可利用资源向量Available。这是一个含有m个元表的数组,其中的每一个元素代表一类可利用的资源数目。其数值随该类资源的分配和回收而动态地改变。如果 Available=K,则表示系统中现有Rj类资源K个。
(2)最大需求矩阵Max。这是一个nxm的矩阵,它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
(3)分配矩阵 Allocation。这也是一个nxm的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,表示进程i当前已分得Rj类资源的数目为K。
(4)需求矩阵Need。这也是一个nxm的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个才能完成。
当一个进程发出请求资源的请求后，如果它所请求的资源大于目前系统可利用资源则不予分配。如果小于可利用资源，则系统试探着把资源分配给该进程，并修改分配之后的资源数值。接着系统执行安全算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给该进程，以完成本次分配。否则，将本次的试探分配作废，恢复原来的资源分配状态，让该进程等待。