银行家算法

操作系统原理 课程设计 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题     目 银行家算法 学    院 专    业                 姓    名 年    级 2013年12 月25 日 摘要 银行家算法是一个用来预防系统进入死锁状态的算法，用它可以判断系统的安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源，如果不是安全状态，则不能为申请资源的进程分配资源。 银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。 关键字：可用资源最大需求矩阵分配矩阵需求矩阵请求向量试分配安全性算法安全序列 目录 绪论    1 一算法原理 ………………………………………………………….....1 二算法思想    2 2.1 安全性算法的算法思想    2 2.1.1设置两个向量    2 2.1.2安全性检测    2 2.2 银行家算法的算法思想    2 2.2.1 银行家算法的思路    4 2.2.2 银行家算法    3 2.2.3 安全性检查算法    3 三详细设计    4 3.1银行家算法中用到的主要数据结构设计    4 3.2算法整体设计与调用    5 3.3模块设计与时间复杂度分析    6 3.3.1  int check_distribution(int* p,int k)函数    6 3.3.2  int check_safe()银行家算法    6 3.3.3  void print()输出函数    6 3.4程序 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图    7 3.4.1 主函数void main（）函数流程图    7 3.4.2判断试分配函数int check_distribution(int* p,int k)流程图    8 3.4.3银行家算法int check_safe()流程图    8 3.4.4 输出函数void print() 流程图    9 四程序调试、分析与修改    9 4.1分模块调试与分析    9 4.1.1进程信息的输入与输出调试    9 4.1.2 进程请求资源输入出错提示信息处理    11 4.1.3 判断试分配函数int check_distribution(int* p,int k)    11 4.1.4 求安全序列函数int check_safe()    11 五结论    12 附录（源代码）    14 参考文献    24 绪论 银行家算法是避免死锁的一种重要 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 。 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。银行家算法确实能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。 现在的大部分系统都没有采用这个算法，也没有任何关于死锁的检查。  银行家算法 一、银行家算法原理 银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。 不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？ 安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )    我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。 银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 二算法思想 2.1 安全性算法的算法思想 思想:系统在进行资源分配之前，应先计算此次资源分配后状态的安全性。若此次分配后的状态是安全状态，则将资源分配给进程；否则，令进程等待。 2.1.1设置两个向量 （1）工作向量Work[m]: 它表示系统可提供给进程继续运行所需的各类资源数目，  Work初∶=Available; （2） Finish[n]: 它表示系统是否有足够的资源分配给进程，使之运行完成。 false表示未完成， true表示完成。 2.1.2安全性检测 2.2 银行家算法的算法思想 2.2.1 银行家算法的思路 先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。                                                                    2.2.2 银行家算法 进程i发出申请资源请求： (1)调用check_distribution(int* p,int k)检查申请量是否不大于需求量再检查检查申请量是否小于系统中的可利用资源数量：若条件不符重新输入，不允许申请大于需求量。 (2)若以上条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值： Available[i,j]= Available[i,j]- Request i[j]； Allocation[i][j]= Allocation[i][j]+ Request i[j]； need[i][j]= need[i][j]- Request i[j]； (3)进行试分配，执行安全性检查，调用check_safe()函数检查此次资源试分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。 (4)用while 循环语句实现输入字符Y/N判断是否继续进行资源申请。 2.2.3 安全性检查算法 (1)设置向量： 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work[]= Available[]。 Finish[]，它表示系统是否有足够的资源分配给每个进程，使之运行完成。开始时先做Finish[i]=0；当有足够的资源分配给进程时，再令Finish[i]=1。 (2)在进程中查找符合以下条件的进程： 条件1：Finish[i]=0； 条件2：need[i][j]<=Work[j] 若找到，则执行步骤(3)否则，执行步骤(4) (3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work[j]= Work[j]+ Allocation[i][j]； Finish[i]=1； goto step 2； (4)最后循环检查是否所有的Finish[i]=1都满足，如果是，则返回1表示系统处于安全状态，否则，返回0表示系统处于不安全状态。 三 详细设计 3.1银行家算法中用到的主要数据结构设计 (1）进程名向量    char processnema[N];          //进程名 (2）可利用资源向量 int Available[M];  //资源清单——系统中现有各资源空闲个数。 (3）最大需求矩阵  int Max[N][M];      //最大需求矩阵——每个进程对各资源的最大需求数分配矩阵    (4）已分配矩阵    int Allocation[N][M];//分配矩阵——系统给每个进程已分配的各类资源数    (5）需求矩阵      int Need[N][M];    //需求矩阵——每个进程还需要每种资源的个数申请各类资源数量 (6）申请向量      int  Request [M]  //进程申请资源的向量 (7）工作向量        int Work[N][M];      //初始第一个向量为Available[],随寻找安全序列时为其余每个向量赋值，可以防止安全序列未找到而丢了初始状态的值 (8）安全序列向量  int sequence[N]={0};//存放安全序列号 (9）标志向量      int  Finish[N] //求安全序列时记录每个进程是否可以顺利执行        3.2算法整体设计与调用 主函数void main()，首先输入每个进程信息，然后判断是否有进程申请资源，若有，则调用int check_distribution(int* p,int k)函数判断是否可以进行试分配，如果满足试分配条件，调用int check_safe()函数求安全序列，如果可以求出安全序列，则说明分配后系统不会进入不安全状态，正式将资源分配给申请资源的进程，最后用void print()函数输出分配资源后每个进程的信息。如果求不出安全序列，说明分配后系统会处于不安全状态，则不能将资源分配给该进程，让其等待，系统恢复原始状态。如果申请资源的数量不满足条件，则让该进程等待。继续判断其他申请资源的进程。 （1）int check_distribution(int* p,int k)：这个函数用来判断是否可以进行试分配，如果函数结果返回1，说明可以进行试分配，如果行数返回0，说明申请资源的进程申请的资源数目不满足Request []<=need[]或Request []<=available[]条件，不能为该进程进行试分配。 （2）int check_safe()：这个函数用来求安全序列，首先初始化Work[0][i]=Available[i]，然后循环找满足条件 Finish[i]==0&& Need[i][0] <= Work[k][0]的进程，k表示最近执行的进程的进程号，找到后将进程i 加入sequence[]向量，再将Finish[i]=1，表示进程可以顺利执行则Work[k][j]=Work[k-1][j]+Allocation[i][j]，k表示同上。再继续找下一个满足条件的进程。如果单循环结束时每个进程的Finish[i]都等于1，则说明可以找到安全序列，返回1，如果不是每个Finish[i]都等于1，则说明找不到一个安全序列，返回0 ( 3 ) void print()：这个函数用来输出进程信息，按表格形式输出，并且输出顺序和安全序列相同，便于查看进程执行执行过程，并且在执行过程中各矩阵信息变化也很容易跟踪查看。 （4）系统模块，如图所示： 3.3模块设计与时间复杂度分析 3.3.1int check_distribution(int* p,int k)：检查是否可以试分配函数 用for(i=0; i #define N 5  //进程个数 #define M 3  //资源种类数 void print(); int check_safe(); int check_distribution(int* p,int k); char processnema[N];          //进程名 int Request[M];      //请求向量 int Finish[N];            //标记某一个进程是否可以执行 int Work[N][M];      //初始为Available[][],随寻找安全序列而变化，防止安全序列未找到而丢了初始状态的值 int Available[M];  //资源清单——系统中现有各资源空闲个数 int Work_Allocation[N][M]; int Max[N][M];      //最大需求矩阵——每个进程对各类资源的最大需求数 int Allocation[N][M];//分配矩阵——系统给每个进程已分配的各类资源数 int Need[N][M];    //需求矩阵——每个进程还需要每种资源的个数 int sequence[N]={0};//存放安全序列号 void main() { int i=0,j=0,k=0;//记录申请资源的进程的序列号 int flag=0;  //标记输入的进程名是否存在 int safe=0;  //标志系统是否出于安全状态,0表示不安全，1表示安全 int distribution=0;  //标志是否可以进行试分配0表示可以，1表示不可以 char flag1;            //标记是否有进程申请资源    //Need[N][M]=Max[N][M]-Allocation[N][M]; char name;    //要请求资源的进程名 printf("~~~~~~~~~~~银行家算法~~~~~~~~~~~~~\n"); printf("    请分别初始化各矩阵信息      \n"); printf("*请输入各进程的进程名\n");  //进程名连续输入 for(i=0; i