1、设计题目： 银行家算法 一、一、设计目的设计目的 本课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练， 通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统基础理 论和重要算法的理解，加强学生的动手能力。 二、二、设计内容设计内容 1 1）概述）概述 用 C 或 C+语言编制银行家算法通用程序，并检测所给状态的系统安全性。 1. 算法介绍：数据结构： 1） 可利用资源向量 Available； 2） 最大需求矩阵 Max； 3） 分配矩阵 Allocation； 4） 需求矩阵 Need 2. 功能介绍 模拟实现 Dijkstra 的银行家算法以避免死锁的出现，分两部
2、分组成： 第一部分：银行家算法（扫描）； 第二部分：安全性算法。 2 2）设计原理）设计原理 一银行家算法的基本概念一银行家算法的基本概念 1、死锁概念。 在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利 用率， 提高系统的吞吐量， 但可能发生一种危险死锁。 所谓死锁(Deadlock), 是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程 处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中， 每个进程都无限等待被该组进程中另一进程所占有的资源， 因而永远无法得到的 资源，这种现象称为进程死锁，这一组进程就称为死锁进程。
3、2、关于死锁的一些结论： 参与死锁的进程最少是两个 （两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 1 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 3、资源分类。 永久性资源： 可以被多个进程多次使用（可再用资源） 可抢占资源 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗 性资源） “申请-分配-使用-释放”模式 4、产生死锁的四个必要条件：互斥使用（资源独占）、不可强占（不可剥夺）、 请求和保持（部分分配，占有申请）、循环等待。 1) 互斥使用（
4、资源独占） 一个资源每次只能给一个进程使用。 2) 不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源， 资源只能由占有者自愿 释放。 3) 请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有 （只有这样才是动态 申请，动态分配）。 4) 循环等待 存在一个进程等待队列 P1 , P2 , , Pn, 其中 P1 等待 P2 占有的资源，P2 等待 P3 占有的资源，Pn 等待 P1 占有 的资源，形成一个进程等待环路。 5、死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破 坏产生死锁的四个必要条件之一。 破坏“不可
5、剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得 到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 破坏“请求和保持”条件。 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程 所要资源均可满足时才给予一次性分配。 2 破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号， 进程在申请资源时必须严格按资源编号的递增次序 进行，否则操作系统不予分配。 6安全状态与不安全状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列 P1，Pn，则系统处于安 全状态。一个进程序列P1，Pn是安全的，如果对于每一个进程 Pi
6、(1i n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj (j n; coutAvailablej; /输入数字的过程. Workj=Availablej; /初始化 Workj，它的初始值就是当前 可用的资源数 coutAllocationij; coutMaxij; if(Maxij=Allocationij) /若最大需求大于已分配，则计 算需求量 Needij = Maxij-Allocationij; else Needij=0;/Max 小于已分配的时候，此类资源已足够不需再申 请 cout=Needij 条件二 pl=i; /存储安全序列 Finishi=1; /i 进程标志为可分配 for (j=0; jk; coutk; coutRequestj; coutAvailablej|
