《课程设计实用版本》由会员分享，可在线阅读，更多相关《课程设计实用版本（16页珍藏版）》请在金锄头文库上搜索。
1、目 录一、设计目的.1二、设计内容.1三、设计原理.1四、算法实现.1五、流程图.1六、源程序.2七、运行示例及结果分析.2八、心得体会.2九、参考资料.2- 1 -银行家算法一、设计目的银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。所以通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法. 二、设计内容1.1. 算法中用到的
2、数据结构算法中用到的数据结构1.11.1 数据结构的说明数据结构的说明1 1. 可利用资源向量 Available ，它是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available（j）=k，标是系统中现有 Rj 类资源 k 个。2 2. 最大需求矩阵 Max，这是一个 nm 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 Max（i，j）=k，表示进程 i 需要 Rj 类资源的最大数目为 k。3 3. 分配矩阵 Allocation，这是
3、一个 nm 的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果 Allocation（i，j）=k，表示进程 i 当前已经分到 Rj 类资源的数目为 k。Allocation i表示进程 i 的分配向量，有矩阵 Allocation 的第 i 行构成。- 2 -4 4. 需求矩阵 Need，这是一个 nm 的矩阵，用以表示每个进程还需要的各类资源的数目。如果 Need（i，j）=k，表示进程 i 还需要 Rj 类资源 k 个，才能完成其任务。Need i表示进程 i 的需求向量，由矩阵 Need 的第 i 行构成。上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-
4、Allocation（i，j） ；1.21.2 银行家算法银行家算法Request i 是进程 Pi 的请求向量。Request i （j）=k 表示进程 Pi 请求分配 Rj 类资源 k 个。当 Pi 发出资源请求后，系统按下述步骤进行检查：1 1.如果 Request i Need，则转向步骤 2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。2 2.如果 Request i Available，则转向步骤 3；否则，表示系统中尚无足够的资源满足 Pi 的申请，Pi 必须等待。3 3.系统试探性地把资源分配给进程 Pi，并修改下面数据结构中的数值：Available = A
5、vailable - Request iAllocation i= Allocation i+ Request iNeed i= Need i - Request i4 4.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程 Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。2.2. 主要的常量变量主要的常量变量#define W 10 /最大进程数W=10#define R 20 /最大资源总数R=20 int AVAILABLER; /可利用资源向量int MAXWR; /最大需求矩阵int ALLOCATIO
6、NWR; /分配矩阵int NEEDWR; /需求矩阵int RequestR; /进程请求向量 void changdata(int k);/进程请求资源数据改变int chksec(int s); /系统安全性的检测- 3 -3.3. 主要模块（函数和数据）主要模块（函数和数据）void inputdata(); /数据输入 void showdata(); /数据显示 void changdata(int k); /进程请求资源数据改变void restoredata(int k); /数据恢复int chksec(int s); /系统安全性的检测int chkmax(int s);
7、/检测最大需求 void bank(); /检测分配的资源是否合理三、设计原理我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2)顾客可以分歧贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配
8、资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 - 4 -四、算法实现初初始始化化由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵 MAX、分配矩阵 ALLOCATION、需求矩阵 NEED 赋值。 银银行行家家算算法法Requ
9、est i 是进程 Pi 的请求向量。Request i （j）=k 表示进程 Pi 请求分配Rj 类资源 k 个。当 Pi 发出资源请求后，系统按下述步骤进行检查：1 1.如果 Request i Need，则转向步骤 2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。2 2.如果 Request i Available，则转向步骤 3；否则，表示系统中尚无足够的资源满足 Pi 的申请，Pi 必须等待。3 3.系统试探性地把资源分配给进程 Pi，并修改下面数据结构中的数值：Available = Available - Request iAllocation i= Alloc
10、ation i+ Request iNeed i= Need i - Request i4 4.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程 Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。安安全全性性检检查查算算法法(1)设置两个工作向量 Work=AVAILABLE;FINISH (2)从进程集合中找到一个满足下述条件的进程， FINISH=false; NEED#include #define FALSE 0 #define TRUE 1 #define W 10 /最大进程数W=10#define
11、R 20 /最大资源总数R=20int M ; int N ; int ALL_RESOURCEW; int AVAILABLER; /可利用资源向量int MAXWR; /最大需求矩阵int ALLOCATIONWR; /分配矩阵int NEEDWR; /需求矩阵int RequestR; /进程请求向量 void inputdata(); /数据输入 void showdata(); /数据显示 void changdata(int k);/进程请求资源数据改变void restoredata(int k); /数据恢复int chksec(int s); /系统安全性的检测int chk
12、max(int s); /检测最大需求 void bank(); /检测分配的资源是否合理 void main() int i,j;inputdata(); for(i=0;i=M) coutM;if (MW) coutW);coutN;if (NR)coutR);coutALL_RESOURCEi;coutMAXij;if (MAXijALL_RESOURCEj)coutALL_RESOURCEj);coutALLOCATIONij;if (ALLOCATIONijMAXij)coutMAXij);cout=M) couti; if(i=M)coutRequestj;if(RequestjNEEDij) coutAVAILABLEj) coutflag; 七、运行示例及结果分析八、心得体会九、参考资料参考文献格式例：1.中国科学院南京土壤研究所西沙群岛专案组我国西沙群岛的土壤和鸟粪- 15 -矿北京：科学出版社，19772.傅承义,陈运泰,祁贵中地球物理学基础北京：科学出版社，19854773.华罗庚，王元论一致分布与近似分析：数论方法（） 中国科学，1973(4)：3393574.赵均宇略论辛亥革命前后的章太炎光明日报，1977 03-24(4)
