「基于java的实验——银行家算法」.doc

仲恺农业工程学院实验报告纸 东哥实验三 银行家算法一 实验目的：1、 理解死锁概念，以及死锁产生的必要条件。2、 理解银行家算法基本原理。3、 掌握一种资源和多种资源的银行家算法的设计与实现。二 实验内容：1、 设计出管理的资源种类和数量2、 设计出银行家算法的基本数据结构3、 设计出完成该资源的银行家算法4、 设计出简单的进程创建、运行资源需求、结束的过程5、 采用高级语言实现该应用程序三实验步骤和过程1.死锁基本概念所谓死锁: 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。 由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象死锁。2.产生死锁的原因（1.竞争资源引起进程死锁当系统中供多个进程共享的资源如打印机、公用队列的等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。 （2.进程推进顺序不当引起死锁由于进程在运行中具有异步性特征，这可能使P1和P2两个进程按下述两种顺序向前推进。 （3. P或V操作不当、同类资源分配不均或对某些资源的使用未加限制等等。3. 产生死锁的必要条件1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。系统中存在临界资源，进程应互斥地使用这些进程。 2）占有和等待条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。 3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。 4）循环等待条件：指在发生死锁时，必然存在一个进程资源的环形链，即进程集合P0，P1，P2，,Pn中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，Pn正在等待已被P0占用的资源。造成这组进程处于永远的等待状态！4、处理死锁的基本方法1) 预防死锁。 这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但是由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。 2) 避免死锁。 该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 3)检测死锁。 这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。 4)解除死锁。 这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施，有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。5.银行家算法基本原理 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2) 顾客可以分期贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。6.银行家算法的数据结构1）可利用资源向量Available 是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Availablej=K，则表示系统中现有Rj类资源K个。 2）最大需求矩阵Max 这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 3）分配矩阵Allocation 这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的 数目为K。 4）需求矩阵Need。 这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j7、 银行家算法流程图8、运行环境Widows7操作系统，eclipse平台！9.程序设计及测试结果1）本程序是没有窗口界面，比较容易实现,整个命令行执行结果如下截图： 2)部分程序： 初始化各个变量public class Banker int resourceType; / 资源种类 int processCount;/ 进程数量 int max;/ 每个进程的最大需求量 int allocated;/ 已经为每个进程分配的数量 int need; / 各个进程还需要的资源数量 int available;/还可用的资源量 boolean echo = true; BufferedReader dong; /从System.in读数据Init函数的初始化void init() try dong = new BufferedReader(new InputStreamReader(System.in); catch (Exception e) e.printStackTrace(); System.exit(0); System.out.println( 银行家算法); System.out.println( T时刻系统资源分配); System.out.println(请输入资源种类数:); resourceType = readInt();/ 获得输入的资源数量 available = new intresourceType;/ 资源种类数量array System.out.println(请输入资源个数向量,共 + resourceType + 个整数,以空格隔开:n); available = readIntArray();/ 资源种类数量array初始化 System.out.print(请输入进程数量:); processCount = readInt(); / 获得输入的进程数量 max = new intprocessCountresourceType;/ 各进程需要的各类资源的最大数矩阵 allocated = new intprocessCountresourceType; / 各进程已分配的各类资源的数量矩阵 need = new intprocessCountresourceType; / 各进程尚需要的各类资源的数量矩阵 System.out.print(请输入进程的最大资源需求量矩阵(max矩阵,每行 + resourceType + 个整数,以空格分隔,共 + processCount + 行):n); for (int i = 0; i processCount; i+) maxi = readIntArray(); System.out.print(请输入进程的已分配资源量矩阵(allocated矩阵,每行 + resourceType + 个整数,以空格分隔,共 + processCount + 行):n); for (int i = 0; i processCount; i+) allocatedi = readIntArray(); for (int i = 0; i resourceType; i+) for (int j = 0; j processCount; j+) needji = maxji - allocatedji; / 计算出need矩阵 for (int i = 0; i resourceType; i+) for (int j = 0; j processCount; j+) availablei -= allocatedji;/ 重新计算available矩阵 if (availablei 0) System.out.println(警醒:第 + (i + 1) + 个可用资源数不足以分配给进程,请检查资源总量和已分配资源矩阵!); System.exit(0); 四、 实验总结与心得本次实验中