操作系统银行家算法实验报告.doc

实验五 银行家算法 一、实验目的和要求 ①理解死锁概念，银行家算法及安全检测算法。 ②在Linux操作系统下用C++进行编程。 ③利用C++设计实现银行家算法的基本过程。 ④验证银行家算法对于避免HYPERLINK /view/121723.htm死锁的作用。 二、实验方法内容 ①算法设计思路 1．设计进程对各类资源最大申请表示及初值确定。 2．设定系统提供资源初始状况。 3．设定每次某个进程对各类资源的申请表示。 4．编制程序，依据银行家算法，决定其申请是否得到满足。 ②算法流程图如下： 开 始输入资源数 开 始 输入资源数m,及各类资源总数,初始化Available向量 输入进程数n，i=1 输入进程i的最大需求向量max。 i≤n Max≤资源总数 提示错误重新输入 i 加1 任选一进程作为当前进程 输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或给出提示 该进程的Need向量0 该进程已运行结束 Need矩阵为0 所有进程运行都结束 END N Y Y N N Y 初始化Need矩阵 N Y ③算法中用到的数据结构说明 1. 可利用资源向量Available ，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=k，标是系统中现有Rj类资源k个。 2. 最大需求矩阵P，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果P（i，j）=k，表示进程Pi需要Rj类资源的最大数目为k。 3. 分配矩阵Allocation，这是一个n×m的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation（i，j）=k，表示进程Pi当前已经分到Rj类资源的数目为k。Allocation i表示进程Pi的分配向量，有矩阵Allocation的第i行构成。 4. 需求矩阵Need，这是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程Pi还需要Rj类资源k个，才能完成其任务。Need i表示进程i的需求向量，由矩阵Need的第i行构成。 上述三个矩阵间存在关系：Need（i，j）=P（i，j）－ Allocation（i，j）； 5. Request i 是进程Pi 的请求向量。Request i （j）=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查： ①.如果Request i ≤Need，则转向步骤2；否则出错。 ②如果Request i ≤R，则转向步骤3；否则，表示系统中尚无足够的资源满足Pi的申请，Pi必须等待。 ③系统试探性地把资源分配给进程Pi，并修改下面数据结构中的数值： R = R － Request i Allocation I = Allocation I + Request i Need I = Need i － Request i ④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待 6. 主要的常量变量 #define W 10 //最大进程数W=10 #define R 20 //最大资源总数R=20 int AVAILABLE[R]; //可利用资源向量 int MAX[W][R]; //最大需求矩阵 int ALLOCATION[W][R]; //分配矩阵 int NEED[W][R]; //需求矩阵 int Request[R]; //进程请求向量 void changdata(int k); //进程请求资源数据改变 int chksec(int s); //系统安全性的检测 7.主要模块（函数和数据） void inputdata(); //数据输入 void showdata(); //数据显示 void changdata(int k); //进程请求资源数据改变 void restoredata(int k); //数据恢复 int chksec(int s); //系统安全性的检测 in