银行家算法

银行家算法模拟设计说明书学院名称：计算机与信息工程学院班级名称：计科112学生姓名：吴晨峰、王书航、陈志立、闫晨雨、顾浩学号:201121121、 42011210910、 2011211117、 2011211232、 2011211186题目:银行家算法指导教师姓名：马丽生起止日期：2013年6月3日2013年6月30日目录1选题背景12. 方案论证（或设计理念）12.1. 问题描述12.2. 基本内容22.3银行家算法的算法思想22.4. 银行家算法实现32.5. 银行家算法流程图32.6安全性检测流程图.43. 过程论述53.1数据结构53.2. 函数核心代码.73.3. 事件响应核心代码104. 结果分析124.1. 初始界面124.2. 安全检测界面124.1.请求成功界面145. 结论156. 参考文献157. 附录151.选题背景在实际应用中，一个进程可能要访问并且独占多个资源，而操作系统又在实 际应用中允许多个进程并发执行并共享系统资源，此时就可能出现系统进程永远 被阻塞状态，为了避免上述死锁的出现，银行家调度算法就可以解决这一问题。银行家算法是一个用来预防系统进入死锁状态的算法，用它可以判断系统的 安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源，如果 不是安全状态，则不能为申请资源的进程分配资源。银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合 法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如 果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其 它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安 全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进 程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理 其他申请资源的进程。设计首先对算法的设计从总体上进行了分析，然后分析各个细节，再对算法 分模块设计，并对分块编写代码，并进行调试和测试，最后进行组装测试及系统 测试，使其成为一个可以用来判断系统安全状态的程序。本次课程设计代码用JAVA语言编写的。2方案论证(或设计理念)21问题描述我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理 的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全，银行家规定：(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳 该顾客；(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可 推迟支付，但总能使顾客在有限的时间里得到贷款；(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资 金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时， 要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求 量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源 时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则 拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。2.2基本内容创建用来保存资源和进程的数据结构，本实验用二维数组实现。所要保存 的项目包括进程名称、数目、资源数目、最大需求数目、已分配数目、仍需数目 及当前状态可利用数目。编写格式输出函数，本实验输入的数据以矩阵的方式输出。编写安全状态 判断函数，要求对输入的可用资源数目进行安全性判断，以及对进程提出的请求 进行判断是否符合安全性原则。若存在，则输出一个安全序列(该算法可以实现 所有安全序列的输出)。编写银行家算法函数，要求对资源申请后的系统状态进 行对应的输出，包括正确的情况输出和错误情况输出。在用户输入所有初始化信息后，首先对信息以矩阵形式输出，再输入一组 可用资源数目，此时系统判断是否存在安全序列，若有则输出一个安全路径；若 无，则表示初始化不正确，请重新输入。在已经安全的前提下，某进程提出资源 申请，包括进程名称、申请资源项目，在判断是否安全，进而给出资源分配以及 安全路径，输出分配后系统状态。2.3银行家算法的算法思想先对用户提出的请求进行合法性检查，即检查请求数是否不大于需求数，是 否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安 全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态， 拒绝申请。2.4. 银行家算法实现1. 利用通过requestm和availablem的关系检查申请量是否不大于需 求量再检查检查申请量是否不大于系统中的可利用资源数量：若条件不符重新输 入，不允许申请大于需求量。2. 若以上条件都满足，则系统试探着将资源分配给申请的进程，并修改下面 数据结构中的数值：Availablei,j= Availablei,j- Request ij;Allocationij= Allocationij+ Request ij; needij= needij- Request ij;3进行试分配，执行安全性检查，调用check ()函数检查此次资源试分配后 系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配 作废，恢复原来的资源分配状态，让该进程等待。2.5. 银行家算法流程图银行家算法流程图如图2-1所示：辅入进程亍驗1*辅入資源修说 * 韬入进程11夫需求矩阵伽触已分配矩眸Alloc胡cm和可利用贸逓矩晖A询就宙 I号IMee(i=Max - AIS Kallonll N逋出系统、尸图2-1银行家算法流程图26安全性检测流程图安全检测流程图如图2-2所示：work=availablejmall(TempliJ-l)1?Work j p W ork j+Ailoc ation ij辙出安全序列，幷打印 出当前资源分配情况牺用结束、1fN辅出提示：系统不安全图2-2安全检测流程图3.过程论述3.1数据结构一、基本数据1.进程向量int t1;/进程数2.资源数向量 int t2;/资源数3可利用资源向量int availablem;/资源清单系统中现有各资源空闲个数。4最大需求矩阵int maxmm; /最大需求矩阵每个进程对各资源的最大需求数分配矩阵5.已分配矩阵int allocationmm; /分配矩阵系统给每 个进程已分配的各类资源数6需求矩阵int needmm;/需求矩阵一一每个进程还需要每种资源的个数申请各类资源数量7. 申请向量int request m/进程申请资源的向量8. 工作向量int workmm;/初始第一个向量为Available,随寻找安全序列时为其余每个向量赋值，可以防止安全序列未找到而丢了初始 状态的值9安全序列向量int am = 0;/存放安全序列号10.标志向量int flag/求安全序列时记录每个进程是否可以顺利执行最大需求矩阵Max，它表示当前进程所需最大资源数。需求矩阵Need，它表示当前进程尚需要的各类资源数。可利用资源Available，它表示当前进程还可以利用的各类资源数。 已分配资源Allocation，它表示当前进程已经分配的各类资源数。工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目， 在执行安全性算法开始时，Work= Available。请求资源Request，它表示进程请求的各类资源数。flag是判断进程是否安全变量，当flag=0时说明该分配序列不安全,flag=l 时说明该分配序列安全。二、在进程中查找符合以下条件的进程：Int flag，它表示系统是否有足够的资源分配给每个进程，使之运行完成。 开始时先做flag=0;当有足够的资源分配给进程时，再令flag=1条件 1： flag=l;条件 2： needij=workj若找到，则执行步骤(3)否则，执行步骤(4)3当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源， 故应执行：workj= workj+ allocationij;flag=1;goto step 2;4.最后循环检查是否所有的flag=l都满足，如果是定义一个r,则r返回1 表示系统处于安全状态，否则，r返回0表示系统处于不安全状态。3.2.函数核心代码该算法中主要涉及到了两个主要函数，分别是递归求解安全序列函数和资源 请求函数。递归求解安全序列函数实现的功能是当进程全都安全时，将所有可能的安全 序列输出，代码如下：public void diguisafe(int k,int n)/递归求解安全序列函数int m,a;if(k=n)for (int j=O;jN;j+)/N 为资源种类数Workj = Availablej;if(safe()=1)for (a=0;a;s1 +=Tempa+n;count+;for(int j=0;jN;j+)Workj = Availablej;elsefor (int i=k;i=n;i+)/n 全排歹 Um=Temp k;Tempk=Tempi;Temp i=m;diguisafe(k+1,n);m=Tempk;Tempk=Tempi;Tempi=m;public int safe()/求是否是安全序列int i;for(i=0;iM;i+)if(Small(Tempi-1)=1)CountWork(Tempi-1); continue;elsebreak;if (i=M)/所有进程都安全return 1;elsereturn 0;public void CountWork(int i)/计算工作向量函数for(int j=O;jN;j+)Workj = Workj+Allocationij;public int Small(int i)/判断是否满足分配需求int flag=0;for(int j=0;jN;j+)if(Needij=Workj)flag=1;elseflag=0;break;return flag; 资源请求函数实现的功能主要是尝试性的为进程分配所需资源，代码如下:public void qingqiu()/资源请求函数count=0;/不满足需if(Req_need()=1&Req_ava()=1) 求Changedata();/预分配elses2 =不能分配； text6.setText(s2);public int Req_need()/判断是否满足需要资源函数int flag=O;for(int i=0;iN;i+)if(Needj-1i=Requesti) flag=1;elseflag=0;break;return flag;public int Req_ava() /判断是否满足需要资源函数int flag=0;for(int i=0;iN;i+)if(Availablei=Requesti) flag=1;elseflag=0;break; return flag;/分public void Changedata()配函数String s_available=new String();for (int i=0;iN;i+)/对所有资源进行处理Availablei = Availablei-Requesti;Allocationj-1i = Allocationj-1i+Requesti; Needj-1i = Needj-1i-Requesti;s_available += Availablej+;33事件响应核心代码本部分为事件响应部分，实现了各个模块之间的链接和响应，每个按钮的功 能由本模块提供响应。if (e.getSource()=b2) /添加进程i = Integer.parselnt(text03.getText(); int max,allocation;String s_max,s_need,s_allocation; s_max = new String();s_need = new String(); s_allocation = new String();for(j=0;jN;j+)allocation = Integer.parselnt(text1j.getText(); max = Integer.parselnt(text2j.getText();Maxi-1j = max;Allocationi-1j = allocation;Needi-1j = Maxi-1j-Allocationi-1j;Tempi-1 = i;for(int j=0;jN;j+)s_max += Maxi-1j+;s_allocation += Allocationi-1j+ s_need += Needi-1j+;datai-10= + i;datai-11=s max;datai-12=s allocation;datai-13=s need;table1.repaint();if(e.getSource()=b3)/获取可用资源数int available;String s_available=new String(); for(int j=0;jN;j+)available = Integer.parselnt(text3j.getText(); Availablej = available; s_available += Availablej+;data04 = s_available; tablei.repaint();if(e.getSource()=b5)flag =1;/请求int request;text6.setText();text7.setText();j=Integer.parselnt(text5.getText();for(int i=0;iN;i+)request = Integer.parselnt(text4i.getText(); Requesti = request; qingqiu();if (e.getSource()=b6)/安全检s1=new String();count=0; diguisafe(0,M-1);if(count=0&flag=0)s2 =系统处于不安全状态，不能请求；else if(count=0&flag=1) s2 =系统处于不安全状态，不能分配；elses2=有+count+个安全序列，；text7.setText(s1);text6.setText(s2);flag =0;4. 结果分析41初始界面主要是用于检测系统运行时是否满足需求和可能出现的错误。如图4-1 是系统的初始化界面。42安全检测界面图4-2安全检测界面如图4-2是安全检测界面，按照提示输入一系列的进程，以及进程的需求资 源，已分配资源和尚需资源，系统可用资源。系统可以检测出安全的分配序列。4.1请求成功界面图4-3请求成功界面如图4-3是系统请求资源成功后的界面。若进程的请求经过系统安全性检 测通过之后，便会输出一系列的安全序列。5. 结论银行家算法是通过检查试分配，求安全序列，从而判断是否可以为申请资源 的进程分配资源，从而有效地避免系统进入死锁状态。虽然并非所有的不安全状态都会产生死锁状态，但系统进入不安全状态时， 便可能进而进入死锁状态后，当系统在进行资源管理时，如果对进城申请的资源 分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。 银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试 分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系 统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则 说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状 态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过 这样一个过程，可以有效避免系统进入死锁状态。反之，只要系统处于安全状态, 系统便可避免进入死锁状态。因此，避免死锁的实质在于；如何使系统不进入不 安全状态。6. 参考文献1汤子瀛等.计算机操作系统M.成都：电子科技大学出版社，2005.；2.赵生慧等.Java面向对象程序设计M.北京：中国水利水电出版社， 2010.;学生签名：王书航、吴晨峰、顾浩、陈志立、闫晨雨填表日期：2013年6月30日7. 附录完整代码如下：import java.awt.*;import java.awt.event.*;import javax.swing.*;public class mybanker extends JFrame implements ActionListenerJTable table1;Object data;JPanel p0,pl,pll,pl2,pl3,pl4,p2,p3,p31,p32,p33,p34,p4;JLabel tl,t2,t3,t4,t5,t6,t7,t8,t9;/tl0 输出安全序列省去 JButton b1,b2,b3,b6,b5;TextField text01,text02,text03,text5,text6;JTextField text1,text2,text3,text4;JTextArea text7;String sl,s2=new StringO; p4=new JPanelO;int M,N,i,j;int count=0,flag=0;int Max;int Need;int Allocation;int Available;int Work;int Request;int Temp;/最大需求量/尚需资源数/已分配的资源数/可用资源数/工作向量/请求资源数public mybanker()super(banker); p0=new JPanel(); p1=new JPanel(); pll=new JPanel(); p12=new JPanel(); p13=new JPanel(); p14=new JPanel(); p2=new JPanel(); p3=new JPanel(); p31=new JPanel(); p32=new JPanel(); p33=new JPanel(); p34=new JPanel();p0.setLayout(new GridLayout(4,l);pl.setLayout(new GridLayout(4,l);p3.setLayout(new GridLayout(4,1); pl.add(pll);pl.add(pl2);pl.add(pl3);pl.add(pl4);p3.add(p31);p3.add(p32);p3.add(p33);p3.add(p34);p0.add(p1);p0.add(p2);p0.add(p3);p0.add(p4);t1=new JLabel(进程数);t2=new JLabel(资源数);t3=new JLabel(进程号);t4=new JLabel(已分配资资源：)；t5=new JLabel(资源最大需求：)； t6=new JLabel(可用资源：)；t7=new JLabel(请求资源进程号); t8=new JLabel(请求资源为);t9=new JLabel(安全检测);bl=new JButton(确定);b2=new JButton(添加);b3=new JButton(确定);b5=new JButton(请求);b6=new JButton(安全检测);textl=new JTextField6;text2=new JTextField6;text3=new JTextField6;text4=new JTextField6;for(int i=0;i6;i+)textli=new JTextField(4);text2i=new JTextField(4);text3i=new JTextField(4);text4i=new JTextField(4);text01=new TextField(4);text02=new TextField(4);text03=new TextField(4);text5=new TextField(4);text6=new TextField(50);String columnNamesl= 进程号，资源最大需求,已分配的资源 ,需要的资源,可利用的资源;data =new Object1005;tablel = new JTable (data, columnNamesl); tablel.setPreferredScrollableViewportSize(new Dimension(550, 100);tablel.setRowHeight (20);tablel.doLayout ();JScrollPane panel = new JScrollPane (tablel);text7 = new JTextArea(,6,40);JScrollPane pane2 = new JScrollPane(text7); text7.setEditable(false);pll.add(tl);pll.add(textOl); pll.add(t2);pll.add(text02);pll.add(bl);pl2.add(t3);p12.add(text03);p12.add(b2);pl3.add(t4);for(int i=0;i6;i+)pl3.add(textli); pl4.add(t5);for(int i=0;i6;i+) pl4.add(text2i); p2.add (panel); p31.add(t6);for(int i=0;i6;i+) p31.add(text3i); p31.add(b3);p32.add(t7); p32.add(text5);p32.add(t8);for(int i=0;i6;i+) p32.add(text4i); p33.add(b6);p33.add(b5);p34.add(t9); p34.add(text6); p4.add(pane2);bl.addActionListener(this);b2.addActionListener(this);b3.addActionListener(this);b5.addActionListener(this);b6.addActionListener(this);pO.setBackground (Color.lightGray);setContentPane (p0);this.setVisible(true);this.pack();列函数public void diguisafe(int k,int n)/递归求解安全序int m,a;if(k=n)for(int j=0；jN;j+)/N 为资源种类数Workj = Availablej;if(safe()=l)for(a=0;a;s1 +=Tempa+ + n;count+;for(int j=0;jN;j+)Workj = Availablej;elsefor(int i=k;i=n;i+)/n 全排列m=Tempk;Tempk=Tempi;Tempi=m;diguisafe(k+1,n);m=Tempk;Tempk=Tempi;Tempi=m;public int safe()/求是否是安全序列int i;for(i=0;iM;i+)if(Small(Tempi T)=l)CountWork(Tempi -1); continue;elsebreak;if(i=M)/所有进程都安全return 1;elsereturn 0;public void CountWork(int i)/计算工作向量函数 for(int j=0；jN;j+)Workj = Workj+Allocationi j;public int Small(int i)/判断是否满足分配需求int flag=0;for(int j=0；jN;j+)if(Needij=Workj)flag=1;elseflag=0;break;return flag;public void ChangedataO/预分配函数String s_available=new StringO;for(int i=0;iN;i+)Availablei = Availablei-Requesti;Allocationj-li = Allocationj-li+Requesti;Needj-1 i = Needj-1i-Request i; s_available += Availablej+ ;data04 = s_available;tablel.repaintO;text6.setText();text7.setText();public void qingqiu()/资源请求函数count=0;if(Req_need()=l&Req_ava()=l)/不满足需求ChangedataO;/预分配elses2 =不能分配； text6.setText(s2);public int Req_need()/判断是否满足需要资源函数int flag=0;for(int i=0;i=Requesti) flag=1;elseflag=0;break;return flag;public int Req_ava()/判断是否满足需要资源函数int flag=0;for(int i=0;i=Requesti)flag=l;else flag=0;break;return flag;public void actionPerformed(ActionEvent e)if(e.getSource()=bl)M = Integer.parseInt(text01.getText();N = Integer.parseInt(text02.getText();Max = new intMN;Allocation = new intMN;Need = new intMN;Available = new intN;Request = new intN;Work = new intN;Temp = new intM;if(e.getSource()=b2)i = Integer.parseInt(text03.getText(); int max,allocation;String s_max,s_need,s_allocation;s_max = new String();s_need = new String(); s_allocation = new String(); for(j=0;jN;j+)allocation = Integer.parseInt(textlj.getText(); max = Integer.parseInt(text2j.getText(); Maxi-lj = max;Allocationi-lj = allocation; Needi-lj = Maxi-lj-AllocationiTj;Tempi-1 = i;for(int j=0;jN;j+)s_max += MaxiTj+;s_allocation += Allocationi-lj+ ;s_need += Needi-lj+;datail0 = + i;datai-ll = s_max;datai12 = s_allocation;datai13 = s_need; tablel.repaintO;if(e.getSource()=b3)int available;String s_available=new String();for(int j=0;jN;j+)available = Integer.parseInt(text3j.getText();Availablej = available; s_available += Availablej+ ;data04 = s_available;tablel.repaintO;if(e.getSource()=b5)flag =1；/请求int request;text6.setText();text7.setText();j=Integer.parseInt(text5.getText();for(int i=0;iN;i+)request = Integer.parseInt(text4i.getText();Requesti = request;qingqiuO;if(e.getSource()=b6)/安全序列sl=new StringO;count=0;diguisafe(0,M-l);if(count=0&flag=0)s2 =系统处于不安全状态，不能请求；else if(count=0&flag=l)s2 =系统处于不安全状态，不能分配；elses2=有+count+个安全序列，”；text7.setText(sl);text6.setText(s2);flag =0;public static void main (String args)new mybanker();