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個才能完成。
當一個進程發出請求資源的請求後，如果它所請求的資源大於目前系統可利用資源則不予分配。如果小於可利用資源，則系統試探著把資源分配給該進程，並修改分配之後的資源數值。接著系統執行安全演算法，檢查此次資源分配後系統是否處於安全狀態。若安全，才正式將資源分配給該進程，以完成本次分配。否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓該進程等待。