操作系统课程设计报告
题目:银行家算法设计
学 院: 专 业: 班 级: 学 生: 学 号: 指导教师: 1
摘 要
银行家算法是一个用来预防系统进入死锁状态的算法,用它可以判断系统的安全性,如果系统当前处于安全状态,则可以为申请资源的进程分配资源,如果不是安全状态,则不能为申请资源的进程分配资源。
银行家算法执行过程中,首先判断申请资源的进程所申请的资源数目是否合法,若是合法的,则可以为其进行试分配,再利用安全性算法求出安全序列,·如果存在安全序列,则说明可以给申请资源的进程分配资源,分配成功,继续为其它进程服务。如果找不到安全序列,则说明为该进程分配资源后系统会进入不安全状态,所以不能为该进程分配资源,使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法,则不需要进行试分配,直接使其进入阻塞状态,处理其他申请资源的进程。
论文首先对算法的设计从总体上进行了分析,然后分析各个细节,再对算法分模块设计,并对各个模块的算法思想通过流程图表示,分块编写代码,并进行调试和测试,最后进行组装测试及系统测试,使其成为一个可以用来判断系统安全状态的程序。
2
银行家算法的原理、思想及小结
1,银行家算法的思路
先对用户提出的请求进行合法性检查,即检查请求的是不大于需要的,是否不大于可利用的。若请求合法,则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全,则分配,否则,不分配,恢复原来状态,拒绝申请。也可以释放进程所占用的一些资源再进行分配资源、安全性检查。
2, 银行家算法的数据结构
主要用到的数据结构:
最大需求矩阵max[][],为n*m的矩阵,定义了n个进程的每个进程对m类资源的最大需求。
已分配矩阵allocation[][],为n*m的矩阵,定义了系统中每一类资源当前分配给每一进程的资源数。
仍需求矩阵need[][]=max[][]-allocation[][]。
可利用资源向量available[],为含有m个元素的数组,每个元素代表一类可利用资源数目。
申请各类资源向量request[]、释放各类资源向量release[]。 工作向量work[]、布尔向量finish[]。
程序模块:
public static void main(String[] args) //系统的主函数 3
public MainFrame() //进入页面
public Banker() //初始化
private boolean safe() //利用安全性算法进行安全性检测
public void update_table1() //打印输出各进程资源分配情况 public void update_table2() //利用银行家算法对申请资源进行判定并打印检测过程情
public void requestresource() //定义请求资源函数
public void releaseresource()/ /定义释放资源函数
各模块间的调用关系:
主函数void main()
要调用: MainFrame()、Banker()
银行家算法函数Banker()
要调用:safe()、update_table1()、update_table2()、requestresource()、releaseresource()
3, 银行家算法
(1).如果request [j] [i]<= need[j][i],则转(2);否则,出错。
(2).如果request [j] [i]<= available[j][i],则转(3);否则,
出错。
(3).系统试探分配资源,修改相关数据:
available[i]-=request[j][i];
allocation[j][i]+=request[j][i];
need[j][i]-=request[j][i];
4
4, 安全性检查算法
(1)设置向量:
工作向量work,它表示系统可提供给进程继续运行所需的各类资源数目,在执行安全性算法开始时work=allocation。
布尔向量finish表示系统是否有足够的资源分配给每个进程,使之运行完成。开始时finish[i]=false;当有足够的资源分配给进程时,再令finish[i]=true。
(2)在进程中查找符合以下条件的进程:
条件1:finish[i]=false;
条件2:need[i][j]<=work[i][j]
若找到,则执行步骤(3)否则,执行步骤(4)
(3)当进程获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
work[il[j]= work[i][j]+ allocation[i][j];
finish[i]=true;
goto step 2;
(4)最后循环检查是否所有的finish[i]=true都满足,如果是,则返回true表示系统处于安全状态,否则,返回false表示系统处于不安全状态。本系统还根据现实需要增加了进程释放资源的功能,系统中进程不仅可以向系统申请资源还可以把自己已获得的资源释放出来供其他进程使用。
5
5
6
7
6, 测试用例及结果截图
测试用例:
某系统有R1、R2和R3共3种资源,在T0时刻P0、P1、P2和P3这4个进程对资源的占用和需求情况见下表,此刻系统的可用资源为(1,1,1)。
进程 已分配资源量 资源最大需求量
R1 R2 R3 R1 R2 R3
P0 1 2 3 1 4 4
P1 2 3 4 3 3 5
P2 3 1 2 4 2 3
P3 2 0 1 2 1 2
取了4种不同的例子,来测试系统的主要功能是否能实现:
进程i request[i] 检测结果
a. 1 1 0 1 (request>need) 系统资源不足,申请被拒绝 b. 0 0 2 0 (request>available) 系统资源不足,申请被拒绝 c. 1 0 0 1 存在安全序列
d. 0 1 0 1 不存在安全序列
e. 释放进程
测试结果截图:
8
再次点击添加会出现:
a:
9
b:
c:
d:
10
7, 小结:
在银行家算法这个系统之中,所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储,比如最大需求量max[][]、已分配资源数allocation[][]、仍需求资源数need[][]、以及系统可利用的资源数、申请各类资源等数组。
数据结构虽然重要但却只是基础,而最主要的用以实现系统功能的应该有两个部分,一是用银行家算法来判断,二是用安全性算法来检测系统的安全性。 在本程序代码中,银行家算法用Banker( )函数来实现。首先,输入欲申请资源的进程以及其所申请的资源数,存放在request数组中。然后,判断进程请求的资源数是否大于其所需的资源数,若大于则报错并返回,若不大于则继续判断它是否大于系统在此刻可利用的资源数,同样,如果大于则报错并返回,如果不大于则进行预分配,之后再调用安全型算法safe检查。同时,我们还可以选择释放资源后再调用安全型算法safe检查。
安全性检测我们是用safe( )函数来实现的。首先,finish[]为布尔型,默认是false,即该进程未完成。而work——即该系统中可以用来工作的资源数——最开始为系统最初可以用的资源数。然后,我们从第一个进程开始判断该进程未完成且其所需求的资源量不大于该系统中可以用来工作的资源量这个条件是否成立,即finish[]=false且need[][]<=work[]是否成立。成立的话则将当前在工作的资源量与该进程已分配的资源量相加,存放于当前可用来工作的资源量当中,即work[]=work[]+allocation,并将finish[]的值改为true否则便将此进程的优先级减一,排在队位,然后开始往后循环。待所有的进程循环完毕,我们再次判断是否还存在进程的finish[]=false,如果仍存在,则说明系统没有安全序列,处于不安全状态,不可以进行分配;否则,系统处于安全状态,将预分配变为实际分配,求出安全序列并且将实际分配后的资源分配情况打印输出。
除此之外,在程序当中,我们也得强调一下对输入的合法性的判断。比如,我们输入的欲申请资源的进程号没有在系统已存在的进程当中,或者进程号定义为整型,但是却错输成字母等情况,我们需要对这些情况进行判断,让程序报错返回而并非因错误而中断。
这样的情况处理起来比较麻烦,相当于对每次输入针对各种不同的情况都得做 11
判断。我也没有涵盖全部的输入,仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断,并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些——比如进程号本来设定就是整型,因此对输入的是字母的判别,因比较复杂而未能加上。
总之,银行家算法是避免死锁的主要方法,其思路在很多方面都非常值得我们来学习借鉴。
12
附录:
MainFrame.java :
package BC;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;
import javax.swing.UIManager.LookAndFeelInfo;//导入的swing的界面管理器
public class MainFrame extends JFrame implements ActionListener//定义类MainFrame继承JFrame类实现ActionListener接口
{
private static final long serialVersionUID = 1L;//序列化,实现序列化类的不同版本间的兼容性
private JPanel imagePanel;;//设置背景面板
private JLabel label1;//设置私人标签
private JButton button;//设置按钮
private ImageIcon background;//设置背景
public MainFrame()
{
super("操作系统课程设计");
ImageIcon buttonIcon = new ImageIcon("a.gif", "a background of button");
Font f =new Font("楷体",1,80);//设置字体
Font f1=new Font("黑体",1,20);
label1=new JLabel("银行家算法系统");
label1.setFont(f);
label1.setForeground(Color.red); //设置字体颜色
button=new JButton("点击进入",buttonIcon);
13
button.setFont(f1);
button.setContentAreaFilled(false);//设置按钮对背景面板透明
button.addActionListener(this);
background = new ImageIcon("2.jpg");// 背景图片
JLabel label = new JLabel(background);// 把背景图片显示在一个标签里面
// 把标签的大小为宽800、高800,位置设置相对于背景面板坐标为(0,0)
label.setBounds(0,0,800,600); // 把内容窗格转化为JPanel,否则不能用方法setOpaque()来使内容窗格透明
imagePanel=(JPanel) this.getContentPane();
imagePanel.setOpaque(false);// 内容窗格默认的布局管理器为BorderLayout
imagePanel.setLayout(new FlowLayout());
imagePanel.add(label1);//把标签、按钮添加到背景面板上
imagePanel.add(button);
this.getLayeredPane().setLayout(null); // 把背景图片添加到分层窗格的最底层作为背景 this.setBounds(300, 100, 800, 600); //设坐标(300,150),宽800,高600
this.getLayeredPane().add(label, new Integer(Integer.MIN_VALUE));
this.setDefaultCloseOperation(EXIT_ON_CLOSE);//设置默认的关闭操作
this.setVisible(true);//设置可见
}
public void actionPerformed(ActionEvent e) //事件的发生的对象为按钮
{
if(e.getSource()==button)
{
}
public static void main (String[] args)
{
try{ for(LookAndFeelInfo info : UIManager.getInstalledLookAndFeels()){ new Banker(); }
14
} } if("Nimbus".equals(info.getName())){ } UIManager.setLookAndFeel(info.getClassName());//设置java窗体 break; catch(Exception e1) {}
new MainFrame();
}
}
Banker.java:
package BC;
import java.awt.*;
import java.awt.event.*;
import java.util.ArrayList;
import javax.swing.*;
import javax.swing.table.DefaultTableCellRenderer;
import javax.swing.table.DefaultTableModel;
public class Banker extends JFrame implements ActionListener {
private static final long serialVersionUID = 1L;
private JTable table1,table2;
private JPanel p0,p1,p11,p12,p13,p14,p2,p3,p31,p32,p33,p34,p4,p5; private JLabel t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11;
private JButton b1,b2,b3,b4,b5,b6;
private TextField text01,text02,text03,text04,text05,text06;//编辑框 private JTextField[] text1,text2,text3,text4,text5;//进程组的数据 DefaultTableModel tablemodel,tablemodel1;
15
ArrayList<Integer> list ;
int[][] max,allocation,need;//最大需求、已分配资源数、仍需资源数 int[] available;//可利用资源数
int[] request,work,release;
boolean[] finish; //标志一个进程是否可以得到其所需要的资源 int m,n,index=0;
public Banker()
{
p0.setLayout(new GridLayout(5,1)); p1.setLayout(new GridLayout(4,1)); p3.setLayout(new GridLayout(4,1)); p1.add(p11); p1.add(p12); p1.add(p13); p1.add(p14); p1.setBackground(Color.CYAN);//设置背景颜色 super("银行家算法系统"); p0=new JPanel(); p1=new JPanel(); p11=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(); p4=new JPanel(); p5=new JPanel();
16
p11.setBackground(Color.CYAN); p12.setBackground(Color.CYAN); p13.setBackground(Color.CYAN); p14.setBackground(Color.CYAN); p3.add(p31); p3.add(p32); p3.add(p33); p3.add(p34); p3.setBackground(Color.pink); p31.setBackground(Color.pink); p32.setBackground(Color.pink); p33.setBackground(Color.pink); p34.setBackground(Color.pink); p0.add(p1); p0.add(p2); p0.add(p3); p0.add(p4); p0.add(p5); p0.setBackground(Color.pink);//设置颜色 p2.setBackground(Color.pink);//设置颜色 p4.setBackground(Color.pink);//设置颜色 p5.setBackground(Color.pink);//设置颜色 t1=new JLabel("进程数"); t2=new JLabel("资源数"); t2.setForeground(Color.red); //设置字体颜色 t3=new JLabel("进程号"); t3.setForeground(Color.red); //设置字体颜色 t4=new JLabel("已分配资资源:"); t4.setForeground(Color.red); //设置字体颜色 t5=new JLabel("资源最大需求:"); t1.setForeground(Color.red); //设置字体颜色 17
t5.setForeground(Color.red); //设置字体颜色 t6=new JLabel("可用资源:"); t6.setForeground(Color.red); //设置字体颜色 t7=new JLabel("请求资源进程号"); t7.setForeground(Color.red); //设置字体颜色 t8=new JLabel("请求资源为"); t8.setForeground(Color.red); //设置字体颜色 t9=new JLabel("释放资源"); t9.setForeground(Color.red); //设置字体颜色 t10=new JLabel("安全序列"); t10.setForeground(Color.red); //设置字体颜色 t11=new JLabel("释放资源进程号"); t11.setForeground(Color.red); //设置字体颜色 b1=new JButton("确定"); b1.setBackground(Color.yellow); //按钮颜色 b1.setForeground(Color.blue); //设置字体颜色 b2=new JButton("添加"); b2.setBackground(Color.yellow); //按钮颜色 b2.setForeground(Color.blue); //设置字体颜色 b3=new JButton("确定"); b3.setBackground(Color.yellow); //按钮颜色 b3.setForeground(Color.blue); //设置字体颜色 b4=new JButton("请求"); b4.setBackground(Color.yellow); //按钮颜色 b4.setForeground(Color.blue); //设置字体颜色 b5=new JButton("开始检测"); b5.setBackground(Color.yellow); //按钮颜色 b5.setForeground(Color.blue); //设置字体颜色 b6=new JButton("释放"); b6.setBackground(Color.yellow); //按钮颜色 b6.setForeground(Color.blue); //设置字体颜色 text1=new JTextField[6]; 18
text2=new JTextField[6];
text3=new JTextField[6];
text4=new JTextField[6];
text5=new JTextField[6];
for(int i=0;i<5;i++) { text1[i]=new JTextField(4); text2[i]=new JTextField(4); text3[i]=new JTextField(4); text4[i]=new JTextField(4); text5[i]=new JTextField(4); } text01=new TextField(4); text02=new TextField(4); text03=new TextField(4); text04=new TextField(4); text05=new TextField(4); text06=new TextField(20); String[] columnNames1= {"进程号", "allocation","max","need","available"};
tablemodel=new DefaultTableModel(columnNames1,0);
table1 = new JTable (tablemodel);
table1.setPreferredScrollableViewportSize(new Dimension(700, 200));//设置表格的大table1.setRowHeight (20);//设置高度
table1.doLayout ();
DefaultTableCellRenderer r = new DefaultTableCellRenderer(); 小
r.setHorizontalAlignment(JLabel.CENTER);//设置位置 table1.setDefaultRenderer(Object.class,r); JScrollPane pane1 = new JScrollPane (table1); p11.add(t1); p11.add(text01); p11.add(t2); p11.add(text02);
19
p11.add(b1); p12.add(t3); p12.add(text03); p12.add(b2); p13.add(t4);
for(int i=0;i<5;i++) p13.add(text1[i]); p14.add(t5);
for(int i=0;i<5;i++) p14.add(text2[i]); p2.add (pane1); p31.add(t6);
for(int i=0;i<5;i++) p31.add(text3[i]); p31.add(b3); p32.add(t7); p32.add(text04); p32.add(t8);
for(int i=0;i<5;i++) p32.add(text4[i]); p32.add(b4); p33.add(t11); p33.add(text05); p33.add(t9);
for(int i=0;i<5;i++) p33.add(text5[i]); p33.add(b6); p34.add(b5);
20
String[] columnNames2= {"进程号", "work","need","allocation","work+allocation","finish"}; tablemodel1=new DefaultTableModel(columnNames2,0); table2 = new JTable (tablemodel1); table2.setPreferredScrollableViewportSize(new Dimension(700, 200)); table2.setRowHeight (20); table2.doLayout (); DefaultTableCellRenderer r1 = new DefaultTableCellRenderer(); r1.setHorizontalAlignment(JLabel.CENTER);//设置位置 table2.setDefaultRenderer(Object.class,r1); JScrollPane pane2 = new JScrollPane (table2); p4.add (pane2); p5.add(t10); p5.add(text06); b1.addActionListener(this); b2.addActionListener(this); b3.addActionListener(this); b4.addActionListener(this); b5.addActionListener(this); b6.addActionListener(this);
list = new ArrayList<Integer>();
this.setContentPane (p0);
this.setVisible(true);
this.pack();
this.setLocation(300, 10);//设置位置
this.setDefaultCloseOperation(JFrame.HIDE_ON_CLOSE);
}
public void actionPerformed(ActionEvent e)//实现功能 {
if(e.getSource()==b1)//实现添加进程功能 21
{
try{
{ }
try{ JOptionPane.showMessageDialog(this,"进程数不能为空"); return; m= Integer.parseInt(text01.getText()); }catch(NumberFormatException e1)
n = Integer.parseInt(text02.getText());
}catch(NumberFormatException e1)
{ } JOptionPane.showMessageDialog(this,"资源数不能为空"); return;
max= new int[m][n]; //创建最大资源需求量数组 need=new int[m][n]; //创建需要资源量数组
allocation = new int[m][n]; //创建已获资源量数组 available = new int[n]; //可利用资源向量 request = new int[n]; //申请各类资源向量 release=new int[n]; //释放各类资源向量 for(int i=0;i<5-n;i++)//进程数增加
p13.remove(text1[4-i]);
for(int i=0;i<5-n;i++) for(int i=0;i<5-n;i++) p31.remove(text3[4-i]); p31.updateUI(); for(int i=0;i<5-n;i++) p14.updateUI(); p14.remove(text2[4-i]); p13.updateUI();
22
p32.remove(text4[4-i]); p32.updateUI(); for(int i=0;i<5-n;i++) p33.remove(text5[4-i]); p33.updateUI(); work=new int[n];//创建可提供的各类资源量向量 String str[]={"","","","","",""}; for(int i=0;i<m;i++) tablemodel1.addRow(str); } if(e.getSource()==b2)//定义按钮b2的功能 { String name[]=new String[m]; if(index>=m) { } try{ for(int j=0;j<n;j++) { allocation[index][j]=Integer.parseInt(text1[j].getText()); max[index][j]=Integer.parseInt(text2[j].getText()); need[index][j]=max[index][j]-allocation[index][j]; JOptionPane.showMessageDialog(this,"进程个数已满"); return; } }catch(Exception f){} name[index]="P"+index; strd[0]=name[index]; String strd[]={"","","","",""}; 23
");
} for(int j=0;j<n;j++) { } strd[1]+=allocation[index][j]+" "; for(int j=0;j<n;j++) { strd[2]+=max[index][j]+" "; } for(int j=0;j<n;j++) { strd[3]+=need[index][j]+" "; } strd[4]=" "; tablemodel.addRow(strd); index++; if(e.getSource()==b3)//定义按钮b3的功能 { try{ for(int i=0;i<n;i++) { } }catch(NumberFormatException f) { JOptionPane.showMessageDialog(this,"可用资源不能为空,请重新输入return; available[i]=Integer.parseInt(text3[i].getText()); work[i]=available[i]; } 24
} String str=""; for(int i=0;i<n;i++) str+=available[i]+" "; tablemodel.setValueAt(str, 0, 4); if(e.getSource()==b4)//定义按钮b4的功能 { } if(e.getSource()==b5)//定义按钮b5的功能 { } if(e.getSource()==b6)//定义按钮b6的功能 { for(int i=0;i<n;i++) list.clear(); safe(); for(int i=0;i<table1.getRowCount();i++) tablemodel1.removeRow(0); update_table2(); for(int i=0;i<n;i++) { } requestresource(); try{ request[i]=Integer.parseInt(text4[i].getText()); }catch(NumberFormatException f1) { } JOptionPane.showMessageDialog(this,"请求资源不能 为空,请重新输 return; 入"); 25
}
} { } releaseresource(); try{ release[i]=Integer.parseInt(text5[i].getText()); }catch(NumberFormatException f1) { } JOptionPane.showMessageDialog(this,"释放资源不能 为空,请重新输 return; 入");
private boolean safe()//安全序列检查 {
boolean finish=false; for(int i=0;i<m;i++) int j=0; { while(j<m) { boolean can =true; //进程完成标识 for(int k=0;k<n;k++) { if(need[j][k]>available[k]) can=false; } if(can&&!list.contains((Object)j)) list.add(j); for(int k=0;k<n;k++) available[k]+=allocation[j][k]; { }
26
}
} j++; if(j>=m) break; if(i==m-1) { break; }
if(list.size()==m)
{
}
}
public void update_table1()//打印输出各进程资源分配情况 {
int index1=Integer.parseInt(text04.getText());
String str[]={"","",""};
for(int k=0;k<n;k++) str[2]+=available[k]+" "; for(int k=0;k<n;k++) str[1]+=need[index1][k]+" "; tablemodel.setValueAt(str[1], index1, 3); for(int k=0;k<n;k++) str[0]+=allocation[index1][k]+" "; tablemodel.setValueAt(str[0], index1, 1); return finish; for(int k=0;k<n;k++) available[k]=work[k]; finish=true;
27
tablemodel.setValueAt(str[2], 0, 4); }
public void update_table2()//打印检测过程情况 {
if(safe())
{
} for(int k=0;k<n;k++) str[4]+=available[k]+" "; str[5]="True"; tablemodel1.addRow(str); for(int k=0;k<n;k++) available[k]=work[k]; text06.setText(temp); for(int k=0;k<n;k++) available[k]+=allocation[x][k]; for(int k=0;k<n;k++) str[3]+=allocation[x][k]+" "; for(int k=0;k<n;k++) str[2]+=need[x][k]+" "; for(int k=0;k<n;k++) str[1]+=available[k]+" "; String temp = ""; for(Integer x:list) temp += ("P"+x + ","); String str[]={"","","","","",""}; str[0]="P"+x; { }
28
else
{
text06.setText("不存在安全序列"); JOptionPane.showMessageDialog(this, "系统处于不安全状态,不能分配资源!!"); return;
}
}
public void requestresource()//定义请求资源函数
{
int index1=Integer.parseInt(text04.getText());
for(int i=0;i<n;i++)
{
if(request[i]<=need[index1][i]&&request[i]<=available[i])
{
work[i]-=request[i];
allocation[index1][i]+=request[i];
need[index1][i]-=request[i];
if(safe())
{
update_table1();
}
else
{
work[i]+=request[i];
}
}
else
{
JOptionPane.showMessageDialog(this, "系统资源不足,申请被拒绝!
return;
}
29 ");
}
}
public void releaseresource()//定义释放资源函数 {
int index2=Integer.parseInt(text05.getText()); for(int i=0;i<n;i++)
{
available[i]+= release[i];
work[i]+=release[i];
allocation[index2][i]-=release[i];
need[index2][i]+=release[i];
}
update_table1();
}
}
30
参考文献
[1] 汤小丹,梁红兵,哲凤屏,汤子瀛.计算机操作系统. 西安:西安电子科技大学出版社,
2007.
[2] 严蔚敏,吴伟民.数据结构. 北京:清华大学出版社,2006.
[3] 赵莉,杨国梁,孙喁喁,徐飞. Java程序设计教程. 西安:西安科技大学出版社,2009.
[4] /view/32d7df73f242336c1eb95efa.html (百度文库:银行家算
法报告)
[5] /default.asp?id=204
31 银行家算法模拟实现) (志文工作室: