寫的比較挫，注釋給的比較詳細，新手可以看看。
import copyimport rePRoc = dict()def comp(x,y): #x為need，y為available flag=1 for i in range(len(x)): # 若出現need大于available,則flag置0 if x[i] > y[i]: flag=0 return flag#***************************字段錄入*******************************print "Please input the number of resource kind"rec=int(raw_input())num=recprint "Please input process's names each in 1 character:"rec=raw_input()Pname = re.findall('[a-zA-Z]',rec) #將名字存入該listfor x in range(len(Pname)): print "Please input ",num," resources Max value for process "+Pname[x]+":" rec = raw_input() L1 = re.findall('[0-9]+$|[0-9]', rec) # Max列表 L1 = [int(i) for i in L1] if len(L1)!=num: print "Input value error,the numeber of resource is less than expected." exit() print "Please input ",num," resources Allocation value for process "+Pname[x]+":" rec = raw_input() L2 = re.findall('[0-9]+$|[0-9]', rec) # Allocation列表 L2 = [int(i) for i in L2] if len(L2) != num: print "Input value error,the numeber of resource is less than expected." exit() for i in range(num): # 若出現Max小于Allocation if L1[i] < L2[i]: print "Input value error,the value of Max is smaller than allocation!" exit() L3 = [L1[i] - L2[i] for i in range(num)] # Neede列表 L = [L1, L2, L3] # P1的鍵值 proc[Pname[x]] = Lprint " Max Allocation Need"for i in range(len(Pname)): print Pname[i],proc[Pname[i]]print "Please input avaliable resources:"rec=raw_input()A = re.findall('[0-9]+$|[0-9]', rec) #Available列表A = [int(i) for i in A]if len(A) < num: print "Input value error,the numeber of resource is less than expected." exit()Path=[] #初始化Index=[]Alloc=[[0,0,0]] #需要對alloc賦初值，否則頂層alloc為空N=[] #記錄路徑數# # A_tem=A# # Path_tem=Path# # Index_tem=Index# Alloc_tem=[[0,0,0]]# # Pname_tem=Pname# N_tem=N#***************************核心算法*******************************def bank(p, a_f, proc_f,path,index,alloc,n,q): #p為進程的name列表，a_f為可用資源，proc_f為鍵值為三矩陣的字典 if len(p)>=1: for x in p: if comp(proc_f[x][2],a_f)==1: a_f = [a_f[i] + proc_f[x][1][i] for i in range(q)] alloc.append(proc_f[x][1]) #將獲得的allocation值保存 path.append(x) #滿足條件則獲得該節點路徑 index.append(p.index(x)) #獲得x的索引值用于還原 p.remove(x) #若滿足條件則從列表中移除x bank(p, a_f, proc_f, path, index, alloc, n,q) if x==p[len(p)-1]: #當一個循環遍歷至最后一個元素時還原p的配置 if path==[]: #當彈回頂層時，path會為空，需特殊處理 break #該層循環遍歷結束后break else: x=path.pop() #恢復上層遍歷的x的值 p.insert(index.pop(), x) alloc_tem=alloc.pop() #取出上層循環所得資源值 a_f = [a_f[i] - alloc_tem[i] for i in range(q)] #恢復上層遍歷的可用資源值 break #該層循環遍歷結束后break elif len(p)==0: print path n.append('1') p.append(path.pop()) index.pop()# print "Safe path: "bank(Pname, A, proc, Path, Index, Alloc, N, num)N=len(N)if N>1: print "There're",N, "ways in total."elif N==1: print "There's only",N, "way."else: print "There's no way out there. This is not a safe system, and here's an example of a safe system as follow:"#若不安全則直接退出程序 Path = [] # 初始化 Index = [] Alloc = [[0, 0, 0]] # 需要對alloc賦初值，否則頂層alloc為空 N = [] # 記錄路徑數 A=[i+1000 for i in A] print "avaliable resorces:",A bank(Pname, A, proc, Path, Index, Alloc, N, num) N_tem=len(N) print "There're",N_tem, "ways in total." exit()#***************************************進程提出需求***********************************************while len(Pname)>0: while 1: print "Continue?<Y/N>" rec = raw_input() if rec=="N": exit() elif rec=="Y": break else: print "Inpu error." Path = [] # 初始化 Index = [] Alloc = [[0, 0, 0]] # 需要對alloc賦初值，否則頂層alloc為空 N = [] # 記錄路徑數 print "Please input request process:" rec=raw_input() Rname = re.findall('[a-zA-Z]',rec) #將名字存入該list if len(Rname)!=1: #若變量數不為1報錯 print "Input error, inputting more process than expected." continue #則重新輸入 else: Rname=Rname[0] #由list變為字符串 print "Please input request resource:" rec = raw_input() LR = re.findall('[0-9]+$|[0-9]', rec) # Request列表 LR = [int(i) for i in LR] if len(LR) != num: #資源數不符 print "Input value error,the numeber of resource is less than expected." continue #則重新輸入 else: if comp(LR,A)==0: #若avaliable小于request，則重新輸入request print "Input value error,the value of avaliable is smaller than request!" continue if LR==proc[Rname][2]: #若request恰好等于need，運行完成后應彈出相應的process for x in range(num): proc[Rname][2][x] = proc[Rname][2][x] - LR[x] #需求減少 proc[Rname][1][x] = proc[Rname][1][x] + LR[x] #alloc增加 A[x] = A[x] - LR[x] bank(Pname, A, proc, Path, Index, Alloc, N, num) N = len(N) if N > 1: print "There're", N, "ways in total." for x in range(num): A[x]=A[x]+proc[Rname][0][x] #將該進程占有的資源收回 proc.pop(Rname) Pname.remove(Rname) elif N == 1: print "There's only", N, "way." for x in range(num): A[x]=A[x]+proc[Rname][0][x] #將該進程占有的資源收回 proc.pop(Rname) Pname.remove(Rname) else: print "There's no way out there" # 若不安全則不對資源進行操作，回滾 for x in range(num): proc[Rname][2][x] = proc[Rname][2][x] + LR[x] # 回滾 proc[Rname][1][x] = proc[Rname][1][x] - LR[x] # 回滾 A[x] = A[x] + LR[x] else: #若request不等于need，運行完成后應彈出相應的process for x in range(num): proc[Rname][2][x] = proc[Rname][2][x] - LR[x] # 需求減少 proc[Rname][1][x] = proc[Rname][1][x] + LR[x] # alloc增加 A[x]=A[x]-LR[x] bank(Pname, A, proc, Path, Index, Alloc, N, num) N = len(N) if N > 1: print "There're", N, "ways in total." elif N == 1: print "There's only", N, "way." else: print "There's no way out there" # 若不安全則不對資源進行操作，回滾 for x in range(num): proc[Rname][2][x] = proc[Rname][2][x] + LR[x] # 回滾 proc[Rname][1][x] = proc[Rname][1][x] - LR[x] # 回滾 A[x] = A[x] + LR[x] print " Max Allocation Need" for i in range(len(Pname)): print Pname[i], proc[Pname[i]] print "Avaliable resources: ",Aprint "/nAll process are completed."新聞熱點
疑難解答
