?
銀行家算法數據結構?
（1）可利用資源向量Available?
是個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目。如果Available[j]=K，則表示系統中現有Rj類資源K個。?
（2）最大需求矩陣Max?
這是一個n×m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K，則表示進程i需要Rj類資源的最大數目為K。?
（3）分配矩陣Allocation?
這也是一個n×m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K，則表示進程i當前已分得Rj類資源的?數目為K。?
（4）需求矩陣Need。?
這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K，則表示進程i還需要Rj類資源K個，方能完成其任務。?
Need[i,j]=Max[i,j]-Allocation[i,j]
銀行家算法?
在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處于安全狀態，便可以避免發生死鎖。?
銀行家算法的基本思想是分配資源之前，判斷系統是否是安全的；若是，才分配。它是最具有代表性的避免死鎖的算法。?
設進程cusneed提出請求REQUEST?[i]，則銀行家算法按如下規則進行判斷。
?(1)如果REQUEST?[cusneed]?[i]<=?NEED[cusneed][i]，則轉（2)；否則，出錯。
?(2)如果REQUEST?[cusneed]?[i]<=?AVAILABLE[i]，則轉（3)；否則，等待。?
?(3)系統試探分配資源，修改相關數據：?
AVAILABLE[i]-=REQUEST[cusneed][i];?
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];?
NEED[cusneed][i]-=REQUEST[cusneed][i];?
(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。?安全性檢查算法?
1)設置兩個工作向量Work=AVAILABLE;FINISH?
2)從進程集合中找到一個滿足下述條件的進程，?FINISH==false;?NEED<=Work;?
如找到，執行（3)；否則，執行（4)?
3)設進程獲得資源，可順利執行，直至完成，從而釋放資源。?Work=Work+ALLOCATION;?Finish=true;?GOTO?2)
4)如所有的進程Finish=?true，則表示安全；否則系統不安全。
#include<iostream> #include<cstdio> #include<vector> #include<ctime> #include<cstring> #include<unistd.h> #include<cstdlib> #define RESTYPE 100 //資源的種類數 #define NTHREAD 50 //線程的數目 using namespace std;pthread_mutex_t mutex;//互斥信號量 pthread_cond_t cond;//條件變量 class BankerAlgorithm {//銀行家算法 public:int nthread;//線程數int restThread;//剩余正在執行的線程數目 int nres;//資源數 int vis[NTHREAD];//標示這個進程有沒有訪問過 int threadFinished[NTHREAD];//標示這個線程是否已經結束 vector<int> resMax[NTHREAD];//每個線程對各類資源的最大的需求量vector<int> resAllocation[NTHREAD];//每個線程當前應經分配到各類資源的情況vector<int> resNeed[NTHREAD];//每個線程還需要每類資源的情況 vector<int> resAvailable;//各類資源的剩余可以利用的 private:void toNeed(){for(int i=0; i<nthread; ++i)for(int j=0; j<nres; ++j)resNeed[i].push_back(resMax[i][j]), resAllocation[i].push_back(0);} bool threadAafetyDetection(int idThread){//線程安全檢測 vector<int> tmpResAvailable(resAvailable);vector<int> threadSafeSequence;//線程安全序列 int cntThread = 0;memset(vis, 0, sizeof(vis));while(threadSafeSequence.size() < restThread){bool findRunThread = false;for(int i=0; i<nthread; ++i)if(!vis[i] && !threadFinished[i]){int j;for(j=0; j<nres; ++j)if(resNeed[i][j] > tmpResAvailable[j]) break;if(j >= nres){//各類所需要的資源的數目 小于或等于各類剩余資源的數目 //該進程可以成功的運行完畢findRunThread = true;vis[i] = 1;threadSafeSequence.push_back(i);for(j=0; j<nres; ++j) tmpResAvailable[j] += resAllocation[i][j];}}if(!findRunThread) break;//找不到下一個可以運行的線程，則退出 }if(threadSafeSequence.size() == restThread){cout<<"此時系統處于安全狀態，存在線程安全序列如下:"<<endl;for(int i=0; i<threadSafeSequence.size(); ++i) cout<<threadSafeSequence[i]<<" ";cout<<endl;return true;} else {cout<<"此時系統處于不安全狀態!!!資源無法分配!!!進程"<<idThread<<"將被阻塞!!!"<<endl;//等到下一次resAvailable更新的時候再將該進程喚醒 return false;}}public:BankerAlgorithm(){}void init(){memset(threadFinished, 0, sizeof(threadFinished));//初始化線程的數目， 資源種類的數目以及每種資源的數目cout<<"請輸入線程的數目和資源的種類數目:"<<endl;cin>>nthread>>nres;restThread = nthread; cout<<"請輸入每種資源的數目:" <<endl;for(int i=0; i<nres; ++i){int k;cin>>k;resAvailable.push_back(k);}cout<<"請輸入每個線程對某類資源最大的需求:"<<endl;for(int i=0; i<nthread; ++i){cout<<"線程"<<i<<"需要的資源:"<<endl; for(int j=0; j<nres; ++j){int k;cin>>k;resMax[i].push_back(k);}}toNeed(); }void returnRes(int idThread){for(int i=0; i<nres; ++i)resAvailable[i] += resAllocation[idThread][i], resAllocation[idThread][i]=0;}int bankerAlgorithm(int idThread, vector<int>res){//進程idThread對資源idRes的請求數量為kfor(int i=0; i<res.size(); ++i){int idRes=i, k = res[i];if(k <= resNeed[idThread][idRes]){if(k > resAvailable[idRes]){//讓進程阻塞cout<<"ERROR!!!線程"<<idThread<<"請求"<<idRes<<"類資源數目大于該類剩余資源的數目!"<<endl<<endl; return 1;}} else {//讓進程重新請求資源 cout<<"ERROR!!!線程"<<idThread<<"請求"<<idRes<<"類資源數目大于所需要的該類資源的數目!"<<endl<<endl; return 2;}}for(int i=0; i<res.size(); ++i){int idRes=i, k = res[i];resAvailable[idRes] -= k;resAllocation[idThread][idRes] += k;resNeed[idThread][idRes] -= k;}//安全性算法的檢測if(!threadAafetyDetection(idThread)){//不能分配資源， 要將idThread這個線程阻塞 for(int i=0; i<res.size(); ++i){int idRes=i, k = res[i];resAvailable[idRes] += k;resAllocation[idThread][idRes] -= k;resNeed[idThread][idRes] += k;}return 3; } cout<<"線程"<<idThread<<"獲得資源:";for(int i=0; i<res.size(); ++i)cout<<" "<<i<<"類:"<<res[i];cout<<endl<<endl;return 0;} };BankerAlgorithm ba;void *thread_hjzgg(void *arg){long long idThread = (long long)arg;//得到線程的標號srand((int)time(0));//開始進行線程資源的請求vector<int> res;for(int i=0; i<ba.nres; ++i){int k = ba.resNeed[idThread][i] == 0 ? 0 : rand() % ba.resNeed[idThread][i]+1;//線程對資源i申請的數目 res.push_back(k);}while(1){if(pthread_mutex_lock(&mutex)!=0){cout<<"線程"<<idThread<<"加鎖失敗!!!"<<endl;pthread_exit(NULL);}bool isAllocationFinished = true;//該線程是否已經將資源請求完畢 for(int i=0; i<ba.nres; ++i) if(ba.resNeed[idThread][i] != 0){isAllocationFinished = false;break;}if(isAllocationFinished){cout<<"線程"<<idThread<<"資源分配完畢!!!進程得到想要的全部資源后開始繼續執行!"<<endl; cout<<"................"<<endl;sleep(1);cout<<"線程"<<idThread<<"執行完畢!!!"<<endl<<endl;--ba.restThread;ba.threadFinished[idThread] = 1;//線程結束 ba.returnRes(idThread);pthread_cond_broadcast(&cond);pthread_mutex_unlock(&mutex);pthread_exit(NULL);}switch(ba.bankerAlgorithm(idThread, res)){case 3://系統會進入不安全狀態，不能進行資源的分配，先進行阻塞 case 1://進程阻塞 pthread_cond_wait(&cond, &mutex);break;case 2://重新分配資源 case 0://資源分配成功, 接著在申請新的資源 res.clear();for(int i=0; i<ba.nres; ++i){int k = ba.resNeed[idThread][i] == 0 ? 0 : rand() % ba.resNeed[idThread][i]+1;//線程對資源i申請的數目 res.push_back(k);}break;default:break;}sleep(1);pthread_mutex_unlock(&mutex);} } int main(){pthread_t tid[NTHREAD];pthread_mutex_init(&mutex, NULL);pthread_cond_init(&cond, NULL);ba.init();for(int i=0; i<ba.nthread; ++i)pthread_create(&tid[i], NULL, thread_hjzgg, (void*)i);for(int i=0; i<ba.nthread; ++i)pthread_join(tid[i], NULL);return 0; } /* 5 3 10 8 6 2 1 3 6 1 1 3 2 2 6 2 1 2 1 1此時系統處于安全狀態，存在線程安全序列如下: 0 1 2 3 4 線程0獲得資源: 0類:2 1類:1 2類:3此時系統處于安全狀態，存在線程安全序列如下: 0 1 2 3 4 線程1獲得資源: 0類:6 1類:1 2類:1ERROR!!!線程2請求0類資源數目大于該類剩余資源的數目!此時系統處于安全狀態，存在線程安全序列如下: 0 1 2 3 4 線程4獲得資源: 0類:2 1類:1 2類:1ERROR!!!線程3請求0類資源數目大于該類剩余資源的數目!線程0資源分配完畢!!!進程得到想要的全部資源后開始繼續執行! ................ 線程0執行完畢!!!線程1資源分配完畢!!!進程得到想要的全部資源后開始繼續執行! ................ 線程1執行完畢!!!線程4資源分配完畢!!!進程得到想要的全部資源后開始繼續執行! ................ 線程4執行完畢!!!此時系統處于安全狀態，存在線程安全序列如下: 2 3 線程3獲得資源: 0類:6 1類:2 2類:1此時系統處于安全狀態，存在線程安全序列如下: 2 3 線程2獲得資源: 0類:3 1類:2 2類:2線程3資源分配完畢!!!進程得到想要的全部資源后開始繼續執行! ................ 線程3執行完畢!!!線程2資源分配完畢!!!進程得到想要的全部資源后開始繼續執行! ................ 線程2執行完畢!!!*/
?
 C. A Problem about Polyline(數學) D. Or Game(暴力，數學))
實現)
)
)
)
 B. Pasha and Phone C. Duff and Weight Lifting)
