操作系统实验之“银行家算法”

银行家算法”"/>

操作系统实验之“银行家算法”

一、前言

银行家算法主要用于判断内存分配是否安全合理。

1、是否合理

主要是看进程的请求是否小于所需值，以及是否小于现有资源量。这个部分比较简单，根据available,need这两个二维矩阵就可以直接判断。

2、是否安全

主要根据安全性检查算法，主要思路是，对于分配后的available,allocation,need三大矩阵，是否能找到一种顺序能使得所有进程都能运行完。步骤如下：
（一般描述中使用available的副本work作为剩余资源量，笔者源代码中也是这么做的，但为了叙述清楚，这里还是用available矩阵来描述）

（1）在需求矩阵need与可分配矩阵available之间循环比较

如果某进程所有的需要都能被满足，那么就分配给这个进程。等待其运行完后回收其所有资源。

（2）

这样一来，如果能分配，那么我们可用资源只会越来越多。
如果最终所有进程都能运行完，则分配后状态安全；
如果某次循环中没有任何一个进程得到分配，那么我们可以断定下次循环也不会有分配，因此系统会出现死锁，所以系统状态不安全。

二、源代码（带注释）

这里笔者按照ppt上的例子初始化了程序，带有简单的分配界面。
另外由于浅拷贝造成的数据混淆，这里笔者用了两次copy模块中的深拷贝，

#coding:gbkimport copydef request(p,r,n,available,maxnum,allocation,need):if n<=need[p][r]:if n<=available[r]:available_t=copy.deepcopy(available)allocation_t=copy.deepcopy(allocation)need_t=copy.deepcopy(need)available_t[r]-=nallocation_t[p][r]+=nneed_t[p][r]-=nif safe_check(available_t,allocation_t,need_t)==1:print("\n分配成功！")#若某进程分配后需要都已经满足，则回收资源for i in range(5):sum=0for j in range(3):if need_t[i][j]==0:sum+=1if sum>=3:print(i,"所需资源已经全部分配，执行后已回收其所有资源")for j in range(3):available_t[j]+=allocation_t[i][j]allocation_t[i][j]=0print("\n")return [available_t,allocation_t,need_t]else:print("\n安全检查不通过，请求失败！")else:print("\n可分配资源不足，请求失败！")else:print("\n超过需要的资源数目，请求失败！")return [available,allocation,need]def safe_check(available_t,allocation_t,need_t):available_tt=copy.deepcopy(available_t)allocation_tt=copy.deepcopy(allocation_t)need_tt=copy.deepcopy(need_t)work=available_ttprint("初始work队列为：",work)l=len(allocation_tt)l1=len(available_tt)finish=[0]*lsafe_queue=[]flag=0t=0while(flag==0):t+=1finish_t=copy.deepcopy(finish)#i表示进程lst=[[],[],[],[],[],[]]for i in range(l):#sum表示可满足要求的资源种类sum=0if finish[i]==0:#j表示资源for j in range(l1):if need_tt[i][j]<=work[j]:lst[i].append(work[j])sum+=1if sum>=l1:safe_queue.append(i)finish[i]=1#j表示资源for j in range(l1):work[j]+=allocation_tt[i][j]allocation_tt[i][j]=0need_tt[i][j]=0print("第",t+1,"轮,进程",i,"可以得到满足","满足后的work队列为：",work)print("此时的需求队列为：",need_tt)else:lst[i]=[]if finish==[1]*l:flag=1print("\n安全检查通过！分配后安全队列为:")print(safe_queue,"\n")return 1#如果这一轮没有变化，且没有找到终止状态，则说明不安全elif finish_t==finish:print("\n尝试分配策略如下，因不能成功结束，所以不安全：",safe_queue)return 0else:passdef show(available,maxnum,allocation,need):print("\n此时系统状态如下：")print("共有5个进程（0-4），3个资源（0-2），请不要超出范围")print("available:\t",available)print("maxnum:\t\t",maxnum)print("allocation:\t",allocation)print("need:\t\t",need)print("********************************")if __name__=="__main__":available=[3,3,2]maxnum=[[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]allocation=[[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]need=[[7,4,3],[1,2,2],[6,0,0],[0,1,1],[4,3,1]]while(1):print("1、分配资源给进程")print("2、显示当前系统状态")print("3、对当前系统进行安全性检查")try:n=int(input("请按照提示输入序号："))except:print("\n输入一个序号后回车即可！\n")continueif n==1:lst=input("请输入您希望分配的‘进程号,资源号,资源个数’，如‘1,1,2’:").split(",")try:a,b,c=int(lst[0]),int(lst[1]),int(lst[2])except:print("\n请按照格式输入，三个数字，中间以英文逗号分开\n")continue[available,allocation,need]=request(a,b,c,available,maxnum,allocation,need)elif n==2:show(available,maxnum,allocation,need)elif n==3:safe_check(available,allocation,need)else:print("请输入1-3之间的数字")