银行家算法（单项资源）
文中给出了单项资源的银行家算法。本文给出的是多种资源的银行家算法。在本质上，单项资源的银行家算法和多种资源的银行家算法没有什么区别，只是书写起来有一点点不同（用C的语法，如果用C++的语法几乎可以写得一模一样）。有关银行家算法的问题大家可以看银行家算法（单项资源） 内容，在此不在赘述。此处只给出源码供大家参考。
不过里面有一个定义
// 定义RES_VECTOR向量，便于程序的理解 typedef int RES_VECTOR[MAX_RESOURCES];这个问题大家可以看typedef使用大全1(数组)
#include " StdAfx.h " #include " Afx.h " #define MAX_PROCESSES 100 // 最大进程数目 #define MAX_RESOURCES 10 // 最多资源数目 // 定义RES_VECTOR向量，便于程序的理解 typedef int RES_VECTOR[MAX_RESOURCES]; // 该程序完成的是银行家算法的核心算法部分，即：判断当前的状态是否 // 是安全的。根据银行家算法，在一个进程提出资源请求时，系统为了避 // 免死锁要对该行为进行判断。如果该行为导致后续系统状态安全，则系 // 统自动满足该请求；否则，如果该行为导致后续系统状态不安全，显然 // 系统要禁止当前的请求，也就是要阻塞请求资源的进程。而该程序就是 // 能判断一个状态[预分配状态]是否是安全状态，判断安全状态的函数是 // M_SafeTest，其他的都是辅助函数，所以采用了static来修饰。// writed by Houjian Tang // 判断系统状态是否安全 int M_SafeTest( int nPn, int nRn, const RES_VECTOR * pVA, const RES_VECTOR * pVM, RES_VECTOR vT, int * safety_seq); // 获得一个“能执行完”进程 static int M_PreExcute( int nPn, int nRn, const RES_VECTOR * pVA, const RES_VECTOR * pVM, const RES_VECTOR vL, const int * finished); // 向量比较 static int LessEqul( int nRn, const RES_VECTOR Va, const RES_VECTOR Vb); // 计算向量之差 static void GetSub(RES_VECTOR v, int nRn, const RES_VECTOR va, const RES_VECTOR vb); // 计算向量之和 static void GetAdd(RES_VECTOR v, int nRn, const RES_VECTOR va, const RES_VECTOR vb); // 算法测试函数 void Test_BanksAlgorithm_multi(); // 比较两个向量的大小，如果pA<=pB小于等于，返回非0, 否则返回0值 static int LessEqul( int nRn, const RES_VECTOR Va, const RES_VECTOR Vb) ... { int i; for (i=0; i<nRn; i++) ...{ if (Va[i] > Vb[i]) return FALSE; } return TRUE;} // 计算向量减法，即v=va-vb static void GetSub(RES_VECTOR v, int nRn, const RES_VECTOR va, const RES_VECTOR vb) ... { int i; for (i=0; i<nRn; i++) v[i] = va[i] - vb[i];} // 计算向量加法，即v=va+vb static void GetAdd(RES_VECTOR v, int nRn, const RES_VECTOR va, const RES_VECTOR vb) ... { int i; for (i=0; i<nRn; i++) v[i] = va[i] + vb[i];} // 查找一个可执行完进程，并返回进程编号，返回 -1 表示没有进程可以执行 // nPn ---- 进程数目 // nRn ---- 资源数目 // pVA ---- 进程已申请资源数 // pVM ---- 进程请求的最大资源数 // vL ---- 当前剩余的资源数目 // finished ---- “能执行完”标志 static int M_PreExcute( int nPn, int nRn, const RES_VECTOR * pVA, const RES_VECTOR * pVM, const RES_VECTOR vL, const int * finished) ... { RES_VECTOR vQ; // 还需要的资源数 int i; // 在每一个进程中查找一个可以运行完的进程 for (i=0; i<nPn; i++) ...{ GetSub(vQ, nRn, pVM[i], pVA[i]); if (!finished[i] && // 第一个条件：进程没有执行完 LessEqul(nRn, vQ, vL)) // 第二个条件：剩余资源可以满足该进程的执行 return i; } return -1;} // 判断当前的状态是否安全，同时给出安全序列 // 返回值：返回当前能够执行完的进程数目。 // nPn ---- 进程数目 // pA ---- 进程已申请资源数 // pM ---- 进程请求的最大资源数 // nT ---- 系统中所有资源数 // safety_seq ---- 进程执行的安全序列 int M_SafeTest( int nPn, int nRn, const RES_VECTOR * pVA, const RES_VECTOR * pVM, RES_VECTOR vT, int * safety_seq) ... { int nFN = 0; // 已执行完的进程数量 int *finished = new int[nPn]; // 进程能执行完标志 int i; // 系统剩余资源数 RES_VECTOR vL; for (i=0; i<nRn; i++) vL[i] = vT[i]; // 初始化“能运行完”标志和系统剩余资源数 for (i=0; i<nPn; i++) ...{ finished[i] = FALSE; // 初始化进程"能执行完"标志 GetSub(vL, nRn, vL, pVA[i]); // 初始化系统剩余资源数 } // 主循环，每次找一个进程，找不到则终止退出 while (nFN < nPn) ...{ // 找到一个“可执行完”进程 int nPid = M_PreExcute(nPn, nRn, pVA, pVM, vL, finished); if (nPid >= 0) // 查找成功 ...{ GetAdd(vL, nRn, vL, pVA[nPid]); // 修改剩余资源数 safety_seq[nFN++] = nPid; // 添加到安全序列 finished[nPid] = TRUE; // 修改进程执行完标志 } else ...{ // 如果查找失败，则直接退出 break; } } delete []finished; return nFN;} // 算法测试函数 void Test_BanksAlgorithm_multi() ... { RES_VECTOR T = ...{6, 3, 4, 2}; // 系统拥有的资源数#define PN 5 // 系统中进程数#define RN 4 // 系统中拥有的资源种类数 // 进程已申请资源数 RES_VECTOR VA[PN] = ...{ ...{3, 0, 1, 1}, ...{0, 1, 0, 0}, ...{1, 1, 1, 0}, ...{1, 1, 0, 1}, ...{0, 0, 0, 0} }; // 进程最大需求资源数 RES_VECTOR VM[PN] = ...{ ...{4, 1, 1, 1}, ...{0, 2, 1, 1}, ...{4, 2, 1, 0}, ...{1, 1, 1, 1}, ...{2, 1, 1, 0} }; int SQ[PN]; // 安全序列 int fn = M_SafeTest(PN, RN, VA, VM, T, SQ); if (fn == PN) ...{ printf("Status Safety! Safety Sequence: "); for (int i=0; i<fn; i++) printf("%c ", 'A'+SQ[i]); printf(" "); } else printf("Status Unsafety! ");}
