a站网址,五莲网站设计,798艺术区,深圳哪家做网站比较好银行家算法数据结构 #xff08;1#xff09;可利用资源向量Available 是个含有m个元素的数组#xff0c;其中的每一个元素代表一类可利用的资源数目。如果Available[j]K#xff0c;则表示系统中现有Rj类资源K个。 #xff08;2#xff09;最大需求矩阵Max 这是一个nm的… 银行家算法数据结构 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)设置两个工作向量WorkAVAILABLE;FINISH 2)从进程集合中找到一个满足下述条件的进程 FINISHfalse; NEEDWork; 如找到执行3)否则执行4) 3)设进程获得资源可顺利执行直至完成从而释放资源。 WorkWorkALLOCATION; Finishtrue; GOTO 2) 4)如所有的进程Finish true则表示安全否则系统不安全。 #includeiostream
#includecstdio
#includevector
#includectime
#includecstring
#includeunistd.h
#includecstdlib
#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];//标示这个线程是否已经结束 vectorint resMax[NTHREAD];//每个线程对各类资源的最大的需求量vectorint resAllocation[NTHREAD];//每个线程当前应经分配到各类资源的情况vectorint resNeed[NTHREAD];//每个线程还需要每类资源的情况 vectorint resAvailable;//各类资源的剩余可以利用的 private:void toNeed(){for(int i0; inthread; i)for(int j0; jnres; j)resNeed[i].push_back(resMax[i][j]), resAllocation[i].push_back(0);} bool threadAafetyDetection(int idThread){//线程安全检测 vectorint tmpResAvailable(resAvailable);vectorint threadSafeSequence;//线程安全序列 int cntThread 0;memset(vis, 0, sizeof(vis));while(threadSafeSequence.size() restThread){bool findRunThread false;for(int i0; inthread; i)if(!vis[i] !threadFinished[i]){int j;for(j0; jnres; j)if(resNeed[i][j] tmpResAvailable[j]) break;if(j nres){//各类所需要的资源的数目 小于或等于各类剩余资源的数目 //该进程可以成功的运行完毕findRunThread true;vis[i] 1;threadSafeSequence.push_back(i);for(j0; jnres; j) tmpResAvailable[j] resAllocation[i][j];}}if(!findRunThread) break;//找不到下一个可以运行的线程则退出 }if(threadSafeSequence.size() restThread){cout此时系统处于安全状态存在线程安全序列如下:endl;for(int i0; ithreadSafeSequence.size(); i) coutthreadSafeSequence[i] ;coutendl;return true;} else {cout此时系统处于不安全状态!!!资源无法分配!!!进程idThread将被阻塞!!!endl;//等到下一次resAvailable更新的时候再将该进程唤醒 return false;}}public:BankerAlgorithm(){}void init(){memset(threadFinished, 0, sizeof(threadFinished));//初始化线程的数目 资源种类的数目以及每种资源的数目cout请输入线程的数目和资源的种类数目:endl;cinnthreadnres;restThread nthread; cout请输入每种资源的数目: endl;for(int i0; inres; i){int k;cink;resAvailable.push_back(k);}cout请输入每个线程对某类资源最大的需求:endl;for(int i0; inthread; i){cout线程i需要的资源:endl; for(int j0; jnres; j){int k;cink;resMax[i].push_back(k);}}toNeed(); }void returnRes(int idThread){for(int i0; inres; i)resAvailable[i] resAllocation[idThread][i], resAllocation[idThread][i]0;}int bankerAlgorithm(int idThread, vectorintres){//进程idThread对资源idRes的请求数量为kfor(int i0; ires.size(); i){int idResi, k res[i];if(k resNeed[idThread][idRes]){if(k resAvailable[idRes]){//让进程阻塞coutERROR!!!线程idThread请求idRes类资源数目大于该类剩余资源的数目!endlendl; return 1;}} else {//让进程重新请求资源 coutERROR!!!线程idThread请求idRes类资源数目大于所需要的该类资源的数目!endlendl; return 2;}}for(int i0; ires.size(); i){int idResi, k res[i];resAvailable[idRes] - k;resAllocation[idThread][idRes] k;resNeed[idThread][idRes] - k;}//安全性算法的检测if(!threadAafetyDetection(idThread)){//不能分配资源 要将idThread这个线程阻塞 for(int i0; ires.size(); i){int idResi, k res[i];resAvailable[idRes] k;resAllocation[idThread][idRes] - k;resNeed[idThread][idRes] k;}return 3; } cout线程idThread获得资源:;for(int i0; ires.size(); i)cout i类:res[i];coutendlendl;return 0;}
};BankerAlgorithm ba;void *thread_hjzgg(void *arg){long long idThread (long long)arg;//得到线程的标号srand((int)time(0));//开始进行线程资源的请求vectorint res;for(int i0; iba.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 i0; iba.nres; i) if(ba.resNeed[idThread][i] ! 0){isAllocationFinished false;break;}if(isAllocationFinished){cout线程idThread资源分配完毕!!!进程得到想要的全部资源后开始继续执行!endl; cout................endl;sleep(1);cout线程idThread执行完毕!!!endlendl;--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 i0; iba.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 i0; iba.nthread; i)pthread_create(tid[i], NULL, thread_hjzgg, (void*)i);for(int i0; iba.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执行完毕!!!*/ 转载于:https://www.cnblogs.com/hujunzheng/p/4820796.html
