操作系统(实验报告)银行家算法姓名:*****学号:*****专业班级:*****学验日期:2011/11/22指导老师:***一、实验名称:利用银行家算法避免死锁二、实验内容:需要利用到银行家算法,来模拟避免死锁:设计M个进程共享N类资源,M个进程可以动态的申请资源,并可以判断系统的安全性,进行打印出,相应的安全序列和分配表,以及最后可用的各资源的数量。
三、实验目的:银行家算法是一种最有代表性的避免死锁的算法,在避免死锁的方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。
为实现银行家算法,系统必须设置若干数据结构,所以通过编写一个模拟动态资源分配的银行家算法程序,进一步深入理解死锁,产生死锁的必要条件,安全状态等重要的概念,并掌握避免死锁的具体实施方法。
四、实验过程1.基本思想:我们可以把操作系统看成是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。
操作系统按照银行家制定的规则为进程分配资源,当进程申请到资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。
当进程在执行中继续申请资源时,先测试该进程已占用的资源与本次申请的资源数之和是否超过了该进程对资源的最大需求量。
若超过则拒绝分配资源,若没有超过再测试系统现资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。
安全状态就是如果存在一个由系统中所有进程构成的安全序列P1……则系统处于安全状态。
安全状态是没有死锁发生。
而不安全状态则是不存在这样一个安全序列,从而一定会导致死锁。
2.主要数据结构:(1)可利用资源向量Available.这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类的资源的分配和回收而动态地改变,如果Available[j]=K,则表示系统中现有Rj类资源K个。
(2)最大需求矩阵Max.这是一个n*m的矩阵,定义了系统中n 个进程中的每一个进程对m类资源的最大需求。
如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K.(3)分配矩阵Allocation.这也是一个n*m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。
如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。
(4)需求矩阵Need。
这也是一个n*m的矩阵,用以表示每一个进程尚需的各类资源数。
如果Need[i,j]=K,则表示进程i,还需要Rj类资源K个,方能完成其任务。
而且上述的矩阵间存在下述的关系:Need[i,j]=Max[i,j]-Allocation[i,j]3.输入输出每次开始运行程序,则要求用户开始输入可用资源量Allocation,最大需求矩阵Max,及已分配的资源,然后根据上述的公式计算出需求矩阵Need,最后用循环将此时的状态输出,若此状态是安全的,则可以要用户继续输入请求各个资源的数量,经安检后,若仍是安全的,予以分配,并打印出,若不安全,则不予以分配,将原状态输出。
4. 程序流程图5.截屏安全实例:不安全实例:6.源程序:package com.bank;import java.util.Scanner;class init{public boolean Run = true, flag = true;public int m, n;public int num[];public int count=0;public int available[];public int max[][];public int allocation[][];public int need[][];public int work[];public boolean finish[];public int request[];public init() {available = new int[15];max = new int[15][15];allocation = new int[15][15];need = new int[15][15];work = new int[15];request = new int[15];finish = new boolean[15];num=new int[15];}public void Input() {System.out.println("请输入进程的个数");Scanner reader = new Scanner(System.in);int x=reader.nextInt();n = x;//} catch (Exception e) {}System.out.println("请输入资源类型个数");x=reader.nextInt();m = x;System.out.println("请输入每种资源可用的数量");for (int i = 0; i < m; i++){available[i] = reader.nextInt();}System.out.println("请输入每个进程对每种资源的最大需求");for (int i = 0; i < n; i++){ System.out.println();for (int j = 0; j < m; j++){max[i][j] = reader.nextInt();}}while (Run){ flag = true;System.out.println("请输入每个进程已经分配的各种类型资源的数量");for (int i = 0; i < n; i++){System.out.println();for (int j = 0; j < m; j++) {allocation[i][j] = reader.nextInt();}}for (int i = 0; i < n; i++) //计算need的值for (int j = 0; j < m; j++)need[i][j] = max[i][j] - allocation[i][j];for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (need[i][j] < 0){flag = false;System.out.println("第"+ (i + 1) + "行第"+ (j + 1)+ "列输入有错误。
");}}}if (flag == false) {System.out.println("以上错误的值不应该大于“最大需求”矩阵相应位置的值。
");System.out.println("请重新输入:\n");continue;} elseRun = false;}}public void Output() {System.out.println("系统状态如下:\n\n");System.out.println("各个进程最大资源数:");for(int i=0;i<n;i++){System.out.print("P"+(i+1)+":");for(int j=0;j<m;j++){System.out.print(max[i][j]+" ");}System.out.println();}System.out.println();System.out.println("各个进程已经分配资源数:");for(int i=0;i<n;i++){System.out.print("P"+(i+1)+":");for(int j=0;j<m;j++){System.out.print(allocation[i][j]+" ");}System.out.println();}System.out.println("各个进程还需要资源数:");for(int i=0;i<n;i++){System.out.print("P"+(i+1)+":");for(int j=0;j<m;j++){System.out.print(need[i][j]+" ");}System.out.println();}System.out.println("目前各资源可用的数量分别为:");for (int j = 0; j < m; j++)System.out.print(available[j]+" ");System.out.println();}}class Security {public init io;public boolean Run = true;public int k=0;public Security(init io) {this.io=io;}public boolean Isless(int a[][], int i, int b[]) { int j;for (j = 0; j < io.m; j++) {if (a[i][j] > b[j])return false;}return true;}// 检验系统是否处于安全性状态public boolean check() {for (int i = 0; i < io.m; i++)//对work进行初始化io.work[i] = io.available[i];for (int i = 0; i < io.n; i++)//对finish进行初始化io.finish[i] = false;while (Run) {for (int i = 0; i < io.n; i++){k++;//用以控制Run的值,以便对while进行控制if (io.finish[i] == false && Isless(io.need, i, io.work) == true){k--;io.finish[i] = true;for (int j = 0; j < io.m; j++){io.work[j] = io.work[j] + io.allocation[i][j];}io.num[io.count]=i+1;io.count++;}}if(k==io.n){Run=false;}else{Run = true;k=0;}}for (int i = 0; i < io.n; i++){if (io.finish[i] == false){System.out.println("系统处于不安全状态,找不到一个安全序列。