第一篇:操作系统实验报告-利用银行家算法避免死锁
计算机操作系统实验报告
题 目 利用银行家算法避免死锁
一、实验目的:
1、加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。
2、要求编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并采用银行家算法,有效的防止和避免死锁的发生。
二、实验内容:
用银行家算法实现资源分配:
设计五个进程{p0,p1,p2,p3,p4}共享三类资源{A,B,C}的系统,例如,{A,B,C}的资源数量分别为10,5,7。进程可动态地申请资源和释放资源,系统按进程的申请动态地分配资源,要求程序具有显示和打印各进程的某一个时刻的资源分配表和安全序列;显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。
三、问题分析与设计:
1、算法思路:
先对用户提出的请求进行合法性检查,即检查请求是否大于需要的,是否大于可利用的。若请求合法,则进行预分配,对分配后的状态调用安全性算法进行检查。若安全,则分配;若不安全,则拒绝申请,恢复到原来的状态,拒绝申请。
2、银行家算法步骤:
(1)如果Requesti<or =Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2)如果Request<or=Available,则转向步骤(3);否则,表示系统中尚无足够的资源,进程必须等待。
(3)系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值:
Available=Available-Request[i];
Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。
3、安全性算法步骤:(1)设置两个向量
①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目,执行安全算法开始时,Work=Allocation;②布尔向量Finish。它表示系统是否有足够的资源分配给进程,使之运行完成,开始时先做Finish[i]=false,当有足够资源分配给进程时,令Finish[i]=true。
(2)从进程集合中找到一个能满足下述条件的进程:
①Finish[i]=false ②Need (3)当进程P获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行: Work=Work+Allocation;Finish[i]=true;转向步骤(2)。 (4)如果所有进程的Finish[i]=true,则表示系统处于安全状态;否则,系统处于不安全状态。 4、流程图: 系统主要过程流程图 银行家算法流程图 安全性算法流程图 5、主要数据结构 假设有M个进程N类资源,则有如下数据结构: int max[M*N] M个进程对N类资源的最大需求量 int available[N] 系统可用资源数 int allocated[M*N] M个进程已经得到N类资源的资源量 int need[M*N] M个进程还需要N类资源的资源量 int worked[] 系统提供给进程继续运行所需的各类资源数目 四、源代码 import java.awt.*;import javax.swing.*;import java.util.*;import java.awt.event.*;import javax.swing.border.*; public class OsBanker extends JFrame { // 界面设计 JLabel labelInfo;JLabel labelInfo1;int resourceNum, processNum;int count = 0;JButton buttonRequest, buttonSetInit, button, button1, buttonsearch,button2;JTextField tf1, tf2;JTextField[] textAvailable;JTextField[][] textAllocation;JTextField[][] textNeed;JTextField textProcessName;JTextField[] textRequest;int available[];int max[][];int need[][];int allocated[][];int SafeSequence[];int request[];boolean Finish[];int worked[];boolean flag = false;JFrame f1;JFrame f2;JFrame f3;JTextArea jt; void display(){ Border border = BorderFactory.createLoweredBevelBorder(); Border borderTitled = BorderFactory.createTitledBorder(border, “按钮区”); textAvailable = new JTextField[5]; textAllocation = new JTextField[6][5]; textNeed = new JTextField[6][5]; textProcessName = new JTextField(“"); textProcessName.setEnabled(false); textRequest = new JTextField[5]; tf1 = new JTextField(20); tf2 = new JTextField(20);labelInfo = new JLabel(”请先输入资源个数和进程个数(1~6),后单击确定“);JPanel contentPane;contentPane =(JPanel)this.getContentPane();contentPane.setLayout(null);contentPane.setBackground(Color.pink);labelInfo.setBounds(50, 10, 300, 40);labelInfo.setOpaque(true);labelInfo.setForeground(Color.red);labelInfo.setBackground(Color.pink);contentPane.add(labelInfo, null);JLabel b1 = new JLabel(”资源个数:“);b1.setForeground(Color.blue);JLabel b2 = new JLabel(”进程个数:“);b2.setForeground(Color.blue);b1.setBounds(50, 80, 80, 30);contentPane.add(b1, null);tf1.setBounds(180, 80, 170, 30);contentPane.add(tf1, null);b2.setBounds(50, 150, 80, 30);contentPane.add(b2, null);tf2.setBounds(180, 150, 170, 30);contentPane.add(tf2, null);button1 = new JButton(”确定“);button = new JButton(”重置“);button1.setBounds(80, 200, 80, 30);contentPane.add(button1, null);button.setBounds(220, 200, 80, 30);contentPane.add(button, null);this.setSize(400, 300);this.setResizable(false);this.setTitle(”银行家算法(SXJ)“);this.setLocationRelativeTo(null);this.setDefaultCloseOperation(EXIT_ON_CLOSE);this.setVisible(true);f1 = new JFrame();labelInfo1 = new JLabel(”请先输入最大需求和分配矩阵,然后单击初始化“);JPanel contentPane1;contentPane1 =(JPanel)f1.getContentPane();contentPane1.setLayout(null);contentPane1.setBackground(Color.pink);labelInfo1.setOpaque(true);labelInfo1.setBounds(75, 10, 400, 40); labelInfo1.setBackground(Color.pink); labelInfo1.setForeground(Color.blue); contentPane1.add(labelInfo1, null); JLabel labelAvailableLabel = new JLabel(”AllResource:“); JLabel labelNeedLabel = new JLabel(”MaxNeed:“); JLabel labelAllocationLabel = new JLabel(”allocated:“); JLabel labelRequestLabel = new JLabel(”request process:“); labelNeedLabel.setBounds(75, 90, 100, 20); // x,y,width,height contentPane1.add(labelNeedLabel, null); labelAllocationLabel.setBounds(75, 240, 100, 20); contentPane1.add(labelAllocationLabel, null); labelAvailableLabel.setBounds(75, 70, 100, 20); contentPane1.add(labelAvailableLabel, null); labelRequestLabel.setBounds(75, 400, 100, 20); contentPane1.add(labelRequestLabel, null); JLabel[] labelProcessLabel1 = { new JLabel(”进程1“), new JLabel(”进程2“),new JLabel(”进程3“), new JLabel(”进程4“), new JLabel(”进程5“),new JLabel(”进程6“)}; JLabel[] labelProcessLabel2 = { new JLabel(”进程1“), new JLabel(”进程2“),new JLabel(”进程3“), new JLabel(”进程4“), new JLabel(”进程5“),new JLabel(”进程6“)}; JPanel pPanel1 = new JPanel(), pPanel2 = new JPanel(), pPanel3 = new JPanel(), pPanel4 = new JPanel(); pPanel1.setLayout(null); pPanel2.setLayout(null); /* * pPanel4.setLayout(null);pPanel4.setBounds(440,120,90,270); * pPanel4.setBorder(borderTitled); */ buttonSetInit = new JButton(”初始化“); buttonsearch = new JButton(”检测安全性“); button2 = new JButton(”重置“); buttonRequest = new JButton(”请求资源“); buttonSetInit.setBounds(420, 140, 100, 30); contentPane1.add(buttonSetInit, null); buttonsearch.setBounds(420, 240, 100, 30); contentPane1.add(buttonsearch, null); button2.setBounds(420, 340, 100, 30); contentPane1.add(button2, null); buttonRequest.setBounds(420, 425, 100, 30); contentPane1.add(buttonRequest, null); for(int pi = 0;pi < 6;pi++){ labelProcessLabel1[pi].setBounds(0, 0 + pi * 20, 60, 20);labelProcessLabel2[pi].setBounds(0, 0 + pi * 20, 60, 20);} pPanel1.setBounds(75, 120, 60, 120);pPanel2.setBounds(75, 270, 60, 120);for(int pi = 0;pi < 6;pi++){ pPanel1.add(labelProcessLabel1[pi], null);pPanel2.add(labelProcessLabel2[pi], null);} contentPane1.add(pPanel1);contentPane1.add(pPanel2);contentPane1.add(pPanel4);for(int si = 0;si < 5;si++)for(int pi = 0;pi < 6;pi++){ textNeed[pi][si] = new JTextField(); textNeed[pi][si] .setBounds(150 + si * 50, 120 + pi * 20, 50, 20); textNeed[pi][si].setEditable(false); textAllocation[pi][si] = new JTextField(); textAllocation[pi][si].setBounds(150 + si * 50, 270 + pi * 20,50, 20); textAllocation[pi][si].setEditable(false);} for(int si = 0;si < 5;si++){ textAvailable[si] = new JTextField();textAvailable[si].setEditable(false);textAvailable[si].setBounds(150 + si * 50, 70, 50, 20);textRequest[si] = new JTextField();textRequest[si].setEditable(false);textRequest[si].setBounds(150 + si * 50, 430, 50, 20);contentPane1.add(textAvailable[si], null);contentPane1.add(textRequest[si], null);} for(int pi = 0;pi < 6;pi++)for(int si = 0;si < 5;si++){ contentPane1.add(textNeed[pi][si], null); contentPane1.add(textAllocation[pi][si], null);} textProcessName.setBounds(80, 430, 50, 20);contentPane1.add(textProcessName, null);f1.setSize(550, 500); f1.setResizable(false); f1.setTitle(”银行家算法(SXJ)“); f1.setLocationRelativeTo(null); f1.setDefaultCloseOperation(EXIT_ON_CLOSE); // f1.setVisible(true); f1.setVisible(false); f2 = new JFrame(”安全序列显示框“); jt = new JTextArea(75, 40); jt.setBackground(Color.pink); jt.setForeground(Color.blue); JScrollPane scrollPane = new JScrollPane(jt);// 加滚动条 scrollPane.setBorder(BorderFactory.createLoweredBevelBorder());// 边界 (f2.getContentPane()).add(scrollPane); f2.setSize(450, 400); f2.setResizable(false); f2.setDefaultCloseOperation(EXIT_ON_CLOSE); f2.setVisible(false); buttonSetInit.setEnabled(false); buttonRequest.setEnabled(false); buttonsearch.setEnabled(false); button1.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ // labelInfo.setText(”请先初始化allocated和Maxneed,后单击初始化按钮“); f1.setVisible(true); buttonSetInit.setEnabled(true); resourceNum = Integer.parseInt(tf1.getText()); processNum = Integer.parseInt(tf2.getText()); for(int i = 0;i < processNum;i++){ for(int j = 0;j < resourceNum;j++){ textNeed[i][j].setEditable(true); textAllocation[i][j].setEditable(true); textAvailable[j].setEditable(true); } } } }); buttonSetInit.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ Init(); buttonsearch.setEnabled(true); } }); buttonsearch.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ count = 0;SafeSequence = new int[processNum];worked = new int[resourceNum];Finish = new boolean[processNum];copyVector(worked, available);Safety(0);jt.append(”安全序列数量:“ + count);if(flag){ labelInfo1.setText(”当前系统状态:安全“); f2.setVisible(true); buttonRequest.setEnabled(true); textProcessName.setEnabled(true); for(int i = 0;i < resourceNum;i++){ textRequest[i].setEditable(true); } } else { labelInfo1.setText(”当前系统状态:不安全“);} buttonSetInit.setEnabled(false);} });buttonRequest.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ count = 0; for(int i = 0;i < processNum;i++){ Finish[i] = false; } jt.setText(”“); flag = false;RequestResource();} });button2.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ /* * tf1.setText(”“);tf2.setText(”“); */ f2.setVisible(false); jt.setText(”“); for(int i = 0;i < processNum;i++){ } for(int j = 0;j < resourceNum;j++){ textNeed[i][j].setText(”“); textAllocation[i][j].setText(”“); textAvailable[j].setText(”“); textRequest[j].setText(”“); // textNeed[i][j].setEditable(false); // textAllocation[i][j].setEditable(false); // textAvailable[j].setEditable(false); textRequest[j].setEditable(false); textProcessName.setText(”“); Finish[i] = false; } } flag = false; buttonsearch.setEnabled(false); // labelInfo.setText(”请先输入资源个数和进程个数,后单击确定“);} });button.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ tf1.setText(”“); tf2.setText(”“); f2.setVisible(false); jt.setText(”“);flag = false;} });void copyVector(int[] v1, int[] v2){ for(int i = 0;i < v1.length;i++) v1[i] = v2[i];} void Add(int[] v1, int[] v2){ for(int i = 0;i < v1.length;i++) v1[i] += v2[i];} void Sub(int[] v1, int[] v2){ for(int i = 0;i < v1.length;i++) } v1[i]-= v2[i];boolean Smaller(int[] v1, int[] v2){ boolean value = true;for(int i = 0;i < v1.length;i++) if(v1[i] > v2[i]){ value = false; break; } return value;} public static void main(String[] args){ OsBanker ob = new OsBanker();ob.display();// System.out.println(” “+count);} void Init()// 初始化操作矩阵 { available = new int[resourceNum];for(int i = 0;i < resourceNum;i++){ available[i] = Integer.parseInt(textAvailable[i].getText());} max = new int[processNum][resourceNum];allocated = new int[processNum][resourceNum];need = new int[processNum][resourceNum];for(int i = 0;i < processNum;i++){ for(int j = 0;j < resourceNum;j++){ max[i][j] = Integer.parseInt(textNeed[i][j].getText()); allocated[i][j] = Integer.parseInt(textAllocation[i][j] .getText()); } } for(int i = 0;i < resourceNum;i++) for(int j = 0;j < processNum;j++) need[j][i] = max[j][i]1); request = new int[resourceNum]; for(int i = 0;i < resourceNum;i++){ request[i] = Integer.parseInt(textRequest[i].getText()); } if(!Smaller(request, need[processname])){ labelInfo.setText(”资源请求不符该进程的需求量.“); } else if(!Smaller(request, available)){ labelInfo1.setText(”可用资源不足以满足请求,进程需要等待.“); } else { Sub(available, request); Add(allocated[processname], request); Sub(need[processname], request); copyVector(worked, available); Safety(0); if(flag){ labelInfo1.setText(”可立即分配给该进程!“); } else { labelInfo1.setText(”分配后导致系统处于不安全状态!,不可立即分配"); Add(available, request); Sub(allocated[processname], request); Add(need[processname], request); } } // } } } 五、实验结果: 初始界面: 初始化: 检测安全性: 请求资源: (1)进程2(1,0,2) (2)进程5(3,3,0) (3)进程1(0,2,0) 六、遇到的问题及不足之处: 1、程序编写的时候规定最大资源数和最大进程数均<=6。 2、程序直接初始化了6个进程框,既浪费了内存空间,又对可视化界面的美观造成影响。 3、未对输入异常进行处理:比如在请求资源的第一个方框中只能填入进程的数字编号,当填入的为非整数时,程序会抛出异常。 4、未解决进程名中对字符串的处理,直接固定进程名为数字,用户不能直接输入原有的进程名,造成不好的用户体验。 操作系统实验:银行家算法 姓名:李天玮 班级:软工1101 实验内容: 在windows系统中实现银行家算法程序。 学号:201126630117 实现银行家算法所用的数据结构: 假设有5个进程3类资源,则有如下数据结构: 1.MAX[5,3] 5个进程对3类资源的最大需求量。2.AVAILABLE[3]系统可用资源数。 3.ALLOCATION[5,3]5个进程已经得到3类资源的资源量。4.NEED[5,3]5个进程还需要3类资源的资源量。 银行家算法: 设进程1提出请求Request[N],则银行家算法按如下规则进行判断。(1)如果Request[N]<=NEED[1,N],则转(2);否则,出错。(2)如果Request[N]<=AVALIABLE,则转(3);否则,出错。(3)系统试探非配资源,修改相关数据。 AVALIABLE=AVALIABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST(4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。 安全性检查: (1)设置两个工作向量WORK=AVAILABLE;FINISH[M]=FALSE.(2)从晋城集合中找到一个满足下述条件的进程,FINISH[i]=FALSE NEED<=WORK 如找到,执行(3);否则,执行(4)。 (3)设进程获得资源,可顺利执行,直至完成,从而释放资源。 WORK=WORK+ALLOCATION FINISH[i]=TRUE GOTO(2) (4)如所有进程FINISH[M]=TRUE,则表示安全;否则系统不安全。 1.用init()函数对于数据的初始化 关键代码: #define M 5 #define N 3 void init(){ cout<<“请输入5个进程对3类资源最大资源需求量:”< } cout<<“请输入系统可用的资哩源数:”< { } cin>>AVAILABLE[j];for(int j=0;j cout<<“请输入5个进程已经-的到的3类资源的资源量:”< for(int i=0;i } cout<<“请?输?入?5个?进?程ì还1需è要癮3类え?资哩?源′的?资哩?源′量?:”< } for(int j=0;j }// Stack around the variable 'AVAILABLE' was corrupted.显示数据详细信息 进行测试 输入一号进程号,并给需要申请资源设定为{1,0,2} 检验错误输入时候的报错信息 检验当再次申请0号资源并申请资源数目为{0,2,0}时,系统提示系统不安全申请不成功。 每当验证申请成功后会进行的修改操作: if(flag=='Y'||flag=='y')//进?行D数簓据Y修T改? { changdata(i); } } if(chkerr(0)){ } else showdata();rstordata(i);showdata();else showdata();cout< 实验目的 银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序,进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施方法 二、实验要求 根据银行家算法的基本思想,编写和调试一个实现动态资源分配的模拟程序,并能够有效地防止和避免死锁的发生。 (1)设计思想说明 设计银行家算法是为了避免死锁 三、实验方法内容 1.算法设计思路 银行家算法又称“资源分配拒绝”法,其基本思想是,系统中的所有进程放入进程集合,在安全状态下系统受到进程的请求后试探性的把资源分配给他,现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较,找出剩余资源能满足最大需求量的进程,从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤,最后检查进程的集合为空时就表明本次申请可行,系统处于安全状态,可以实施本次分配,否则,只要进程集合非空,系统便处于不安全状态,本次不能分配给他。请进程等待 2.算法流程图 3.算法中用到的数据结构 数据结构的说明 1.可利用资源向量AVAILABLE。这是一个含有M个元素的数组,其中的每一个元素代表一类可利用的资源数目,其3初始值是系统中所配置的该类全部可哦那个资源的数目,其数值随该类资源的分配和回收而动态的改变。 2.最大需求矩阵MAX。这是一个M*N的矩阵,它定义了系统中N个进程中的每一个进程对M类资源的最大需求。 3.分配矩阵ALLOCATION。这也是一个M*N的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。 4.需求矩阵NEED。这也是一个M*N的矩阵,用以表示每一个进程尚需的各类资源数。5.NEED[R,W]=MAX[R,W]-ALLOCATION[R,W] 4.主要的常量变量 #define W 10 //最大进程数W=10 #define R 20 //最大资源总数R=20 int AVAILABLE[R];//可利用资源向量 int MAX[W][R];//最大需求矩阵 int ALLOCATION[W][R];//分配矩阵 int NEED[W][R];//需求矩阵 int Request[R];//进程请求向量 void changdata(int k);//进程请求资源数据改变 int chksec(int s);//系统安全性的检测 5.主要模块 void inputdata()void showdata()void changdata(int k)void restoredata(int k)int chksec(int s)int chkmax(int s) 四、实验代码 #include void changdata(int k);//进程请求资源数据改变 void restoredata(int k);//数据恢复 int chksec(int s);//系统安全性的检测 int chkmax(int s);//检测最大需求 void bank();//检测分配的资源是否合理 void main(){ int i,j;inputdata();for(i=0;i if(j==0)break;} if(i>=M)cout<<“错误提示:经安全性检查发现,系统的初始状态不安全!!n”< if(M>W)cout< if(N>R)cout< for(j=0;j do{ cin>>ALLOCATION[i][j]; if(ALLOCATION[i][j]>MAX[i][j]) cout< }while(ALLOCATION[i][j]>MAX[i][j]);} } cout< for(j=0;j NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];for(j=0;j for(i=0;i AVAILABLE[j]=0;} } } void showdata(){ int i,j;cout<<“各种资源的总数量,即向量all_resource为:”< cout< for(j=0;j cout< void changdata(int k){ int j;for(j=0;j AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j];} } void restoredata(int k){ int j;for(j=0;j ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j];} } int chksec(int s){ int WORK,FINISH[W];int i,j,k=0;for(i=0;i FINISH[i]=FALSE;for(j=0;j { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) { WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; i=0; }else { i++; } }while(i if(FINISH[i]==FALSE) { return 1; } } return 0;} int chkmax(int s){ int j,flag=0;for(j=0;j if(MAX[s][j]==ALLOCATION[s][j]) { flag=1; AVAILABLE[j]=AVAILABLE[j]+MAX[s][j]; MAX[s][j]=0; } } return flag;} c { int i=0,j=0;char flag='Y';while(flag=='Y'||flag=='y'){ i=-1;while(i<0||i>=M){ cout<<“请输入需申请资源的进程号(从P0到P”< cin>>i;if(i<0||i>=M) cout<<“输入的进程号不存在,重新输入!”< for(j=0;j cin>>Request[j];if(Request[j]>NEED[i][j]) { cout<<“进程P”< cout<<“申请不合理,出错!请重新选择!”< flag='N'; break; } else { if(Request[j]>AVAILABLE[j]) { cout<<“进程P”< cout<<“申请不合理,出错!请重新选择!”< flag='N'; break; } } } if(flag=='Y'||flag=='y'){ changdata(i); if(chksec(i)) { cout< cout<<“该分配会导致系统不安全!!本次资源申请不成功,不予分配!!”< cout< restoredata(i); } else { cout< cout<<“经安全性检查,系统安全,本次分配成功,且资源分配状况如下所示:”< cout< showdata(); if(chkmax(i)) {cout<<“在资源分配成功之后,由于该进程所需的某些资源的最大需求量已经满足,”< cout<<“因此在进程结束后系统将回收这些资源!”< showdata(); } } } cout< 五、实验结果 1.执行结果 2.结果分析 银行家算法就是当接收到一个系统资源的分配后找到一个安全序列,使得进程间不会发生死锁,若发生死锁则让进程等待。 六、实验总结 通过本次银行家算法实验,加深了我对银行家算法的了解,掌握了如何利用银行家算法避免死锁。实验中遇到点问题,通过查阅资料、询问老师顺利解决。通过这次的实践,使我的理论知识更加的牢固。 实验四 死锁 一、实验目的 当系统的总资源数m小于或等于所有进程对对资源的最大需求时,就可能产生 死锁。死锁会引起计算机系统的瘫痪。银行家算法是在实现资源分配时避免死锁的一个著名算法,该算法是在能确保系统处于安全状态时才把资源分配给申请者。通过本实验使学生能进一步理解死锁的概念,并能选择一个算法来避免死锁。 二、实验题目 系统中有m个同类资源被n个进程共享,每个进程对资源的最大需求数分别为S1, S2,…,Sn,且 Max(Si)<=m,(i=1,2,…n)。进程可以动态地申请资源和释放资源。编写一个程序,现银行家算法,当系统将资源分配给某一进程而不会死锁时,就分配之。否则,推迟分配,并显示适当的信息。 三、数据结构 主要数据结构: Struct aa { void Print();//用于打印输出表格的函数 void Input();//用于输入的函数 void tryfenpei(int i);//试分配函数 void refenpei(int i);//恢复数据函数 void checksafe(int s);//安全检测函数 }; 四、银行家算法的流程图 开始初始化资源类数c=3,进程数t=5初始化Available[c],Max[t][c],Allocation[t][c],Need[t][c],Request[c]输入进程数iInt f=0f 五、源代码 #include void Print();//用于打印输出表格的函数 void Input();//用于输入的函数 void tryfenpei(int i);//试分配函数 void refenpei(int i);//恢复数据函数 void checksafe(int s);//安全检测函数 //定义初始化数组 int Available[c], Max[t][c], Allocation[t][c], Need[t][c], Request[c]; int in;//用户选择的进程号 int main(int argc, char *argv[]){ int i;char ch='Y';cout<<“初始化数据如下:”< cout<<“试分配完成!”< cout<<“需要继续实验吗?(y-继续 n终止)”;} else if(ch=='N'||ch=='n'){ cout<<“感谢您的使用,祝您愉快!”< void Print(){ int i,j;cout<<“ 进程个数 : ”< void Input(){ for(int j=0;j { for(int m=0;m void tryfenpei(int i){ for(int f=0;f //安全检测函数 void checksafe(int s){ int Work, flag, temp[t], i,j,l=0,k=0;bool Finish[t];for(i=0;i } if(l==5)//一共有三类资源A B C,一条进程下面的安全性检测只检测了A类。如果A类通过了,那么还要判断B类,C类。否则不用 { for(i=0;i } i=s;//s传递进来赋给i,s是用户输入的进程号(有主函数里的in传递进来)while(i if(Finish[i]==false&&Need[i][j]<=Work){ Work=Work+Allocation[i][j];Finish[i]=true;temp[k]=i;//cout<<“temp=”< 六、执行结果: 七、实验总结 通过本次实验了解到用银行家算法来预防死锁是可靠的,但也是非常保守的,因为它限制了进程对资源的存取,从而降低了进程的并发运行程度。死锁检测并不限制进程对资源的申请,只要有,就分配,但这也可能造成死锁。但由于死锁并不是经常发生的,故大大提高了系统运行的效率。 总之,通过本实验,使我进一步加深理解和掌握银行家算法。 模拟通过银行家算法避免死锁 一、银行家算法产生的背景及目的 1:在多道程序系统中,虽然借助于多个进程的并发执行来改善系统的利用率,提高系统的吞吐量,但可能发生一种危险—死锁。死锁就是多个进程在运行过程中因争夺资源而造成的一种僵局,当进程处于这种僵局状态时,如无外力作用,他们将无法再向前进行,如再把信号量作为同步工具时,多个Wait和Signal操作顺序不当,会产生进程死锁。 然而产生死锁的必要条件有互斥条件,请求和保持条件,不剥夺条件和环路等待条件。在预防死锁的几种方法中,都施加了较强的限制条件,在避免死锁的方法中,所施加的条件较弱,有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统都处于安全状态,便可避免死锁。2:实验目的:让学生独立的使用编程语言编写和调试一个系统分配资源的简单模拟程序,了解死锁产生的原因及条件。采用银行家算法及时避免死锁的产生,进一步理解课堂上老师讲的相关知识点。银行家算法是从当前状态出发,逐个按安全序列检查各客户中谁能完成其工作,然后假定其完成工作且归还全部贷款,再进而检查下一个能完成工作的客户。如果所有客户都能完成工作,则找到一个安全序列,银行家才是安全的。 二:银行家算法中的数据结构 1:可利用资源向量Available。这是一个含有m个元素的数组,其中的每个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态的改变。如果Available[j]=k,z 则表示系统中现有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个。 三、银行家算法及安全性算法 1:银行家算法 设Request[i]是进程Pi的请求向量,若Request[i][j]=k;表示进程需要j类资源k个。当Pi发出资源请求时,系统按下属步骤进行检查;(1)如果Request[i][j]<=Need[i][j];便转向步骤(2),否则认为出错,因为它所需要的资源数已超过他所宣布的最大值。 (2)如果Request[i][j]<=Available[i][j],便转向步骤(3),否则认为尚无足够资源,进程需等待。(3)系统试探着把资源分配给进程,并修改下面数据结构的数据 Available[i][j]=Available[i][j]-Request[i][j];Allocation[i][j]=Allocation[i][j]+Request[i][j];Need[i][j]=Need[i][j]-Request[i][j];(4)系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,已完成此次分配。否则,将本次的试探分配作废,回复原来的资源分配状态,将进程Pi等待。2:安全性算法 (1)设置两个向量; 1:工作向量Work,表示系统可提供给进程运行所需的各类资源数目,它含有m个元素,初始时Work=Available 2:Finish ,表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]=true(2)从进程中找到一个能满需下属条件的进程 1;Finish[i]=false; 2:Need[i][j]<=Work[j];若找到执行步骤(3),否则执行步骤(4) (3)当进程Pi顺利获得资源后,直至完成,并释放分配给它的资源,执行: Work[j]=Work[j]+Allocation[i][j];Finish[i]=true;Go to step(2);(5)如果所有的进程Finish[i]都满足,则表示系统处于安全状态,否则,处于不安全状态。 四、模块设计与分析及整体功能概述 模块设计与分析: 整个银行家算法分为初始化函数Init(),安全性算法函数 safe(),银行家算法函数bank()三部分。初始化函数生成开始时刻系统中的进程和资源情况,安全性算法判断当某进程申请资源时,系统能否处于安全状态。在本实验中,若系统处于安全状态,便生成一个安全进程序列(安全序列可能有多个)。银行家算法函数bank()负责整体的检查与异常判断。整体功能概述: 死锁会引起系统陷入僵局,操作系统必须防止此现象的发生。本实验通过一个动态分配资源的模拟程序,更清楚的理解死锁产生的原因和条件。Dijkstra的银行家算法是最有代表性的避免死锁的方法。运行程序时用户设定系统中进程和可利用资源的种类数目。输入各进程的可利用资源Available,最大需求MAX,已分配资源Allocation,需求资源Need,之后各系统发出资源请求Request,利用实验中的安全性算法判断能否产生一个安全性队列,若能,则给该进程分配成功,否则,不予分配。 五、流程图设计 六、源代码及调试分析 #include // 定义最大进程数 #define MAXn 100 //定义最大资源数 int MAX[MAXm][MAXn]; //最大需求矩阵 int Allocation[MAXm][MAXn]; //已分配矩阵 int Available[MAXn]; //可用资源数组 int Need[MAXm][MAXn]; //需求矩阵 int Request[MAXm][MAXn]; //请求矩阵 int Finish[MAXm]; //存储完成资源分配的进程 int Sequence[MAXm]; //模拟的资源分配序列 int Work[MAXn]; //系统是否有足够的资源分配给进程 int m,n; //m个进程,n个资源 #define False 0 #define True 1 void input();//数据输入函数 int safealg();//安全性算法函数 void banker();//银行家算法函数 void main(){input();safealg();banker();} //*************初始化算法*************** void input(){ int i,j; //************自定义进程数目与资源种类******************* cout<<“***********************************n”;cout<<“*利用银行家算法避免死锁*n”; cout<<“* *n”;cout<<“************************************n”;cout<<“请输入进程的数目:”;cin>>m;cout<<“请输入资源的种类:”;cin>>n;//*****输入每个进程对每种资源的最大需求、已经获得的数量、每种类型资源的数目 cout<<“各进程资源最大需求(Max),按照”< cout<<“P”< for(j=0;j { cin>>MAX[i][j]; if(j==n) cout<<“资源种类数匹配出现错误!”;//当资源配置的种类数大于预先输入的数值时,出错 } } cout<<“各进程当前获得资源(Allocation),按照”< cout<<“P”< for(j=0;j { cin>>Allocation[i][j]; if(j==n) cout<<“资源种类数匹配出现错误!”;//当资源配置的种类数大于预先输入的数值时,出错 Need[i][j]=MAX[i][j]-Allocation[i][j];//需求数等于最大需求减去已经分配数 } } cout<<“系统可用资源(Available):”< cin>>Available[j];//输入各种资源的可利用数 } cout<<“当前时刻的进程分配情况如图:n”;cout<<“进程号-”<<“MAX----”<<“Allocation---”<<“Need--”<<“Available---n”;//显示各进程的资源情况 for(i=0;i cout<<“P”< for(j=0;j cout<<“ ”< for(j=0;j cout<<“ ”< cout<<“ ”; for(j=0;j cout<<“ ”< for(j=0;j cout<<“ ”< cout< } } //*****************银行家算法,为进程分配资源***********// void banker(){ int i,j; int choice; while(1) { cout< cout<<“输入要进行的操作(1:分配资源 2:离开):”; //用户选择 cin>>choice; if(choice==1) //分配资源 { cout<<“从P0到P”< cin>>i; if(i>=m) { cout<<“无此进程号!请重新输入:n”; cin>>i;//重新输入进程号 } cout<<“请输入进程申请的资源(Request):”< for(j=0;j cin>>Request[i][j]; //**********银行家算法进行检查*************// for(j=0;j { if(Request[i][j]>Need[i][j]) { cout<<“申请的资源大于它需要的资源数,请重新输入!n”;//资源申请不合理 continue; } if(Request[i][j]>Available[j]) { //资源申请数目大于可利用数,无法分配,得等待 cout<<“当前系统可用资源不够,请等待!”< continue; } } for(j=0;j { Available[j]=Available[j]-Request[i][j]; //可用资源减少 Allocation[i][j]=Allocation[i][j]+Request[i][j];//所得资源增加 Need[i][j]=Need[i][j]-Request[i][j]; //仍需资源减少 } if(safealg()<0)//安全性算法的返回值 { cout<<“分配不成功,请等待!”; for(j=0;j //把资源恢复成分配之前的状态 { Available[j]=Available[j]+Request[i][j]; Allocation[i][j]=Allocation[i][j]-Request[i][j]; Need[i][j]=Need[i][j]+Request[i][j]; } for(i=0;i { Finish[i]=False;//没有足够的资源分配给该进程 } }//if(safealg()<0) else { cout<<“同意分配请求!”< for(j=0;j Work[j]=Available[j]; cout<<“进程号-”<<“--Work----”<<“Need---”<<“Allocation---”<<“Work+Allocation--” <<“Finish--”< for(i=0;i { cout<<“进程P”< for(j=0;j cout< cout<<“ ”; for(j=0;j cout< cout<<“ ”; for(j=0;j cout< cout<<“ ”; for(j=0;j cout< cout<<“ ”; cout< for(j=0;j Work[j]=Allocation[Sequence[i]][j]+Work[j];//回收该进程所分配的资源 cout< } }//if(safealg()>=0) }//if(choice=1) else if(choice==2) //离开———— break; else cout<<“请输入1或2!”;//只认可1或2 }//while(1)} //*********安全性算法 ************// int safealg(){ int i,j,k,l=0; //int Work[MAXn]; //工作组 //记录序列 for(i=0;i Work[i]=Available[i]; //工作分配初始化为系统可用资源 for(i=0;i //扫描所有进程,预设所有进程不能运行 { Finish[i]=False; } for(i=0;i { // if(Finish[i]==True) { continue; } else //对于未运行的进程,进行如下处理 {/// for(j=0;j { if(Need[i][j]>Work[j])//由于部分资源得不到满足,进程i无法运行 { 的资源 用资源 } break; } } if(j==n)//进程各类资源全部得到满足 { Finish[i]=True; for(k=0;k { Work[k]+=Allocation[i][k];//工作分配加上可 } Sequence[l++]=i; //模拟资源分配序列生成 i=-1; //重新扫描所有进程从i=0开始 } else { //某一资源得不到满足 continue;//试探下一个进程 } }// if(l==m)//都试探完毕 { cout<<“系统安全!”< cout<<“安全序列:”; for(i=0;i //输出安全序列 cout<<“进程P”< cout< return 0;} }// cout<<“系统进入不安全状态!”< 分析:输入各进程的可利用资源Available,最大需求MAX,已分配资源Allocation,需求资源Need,之后各系统发出资源请求Request,利用实验中的安全性算法判断能否产生一个安全性队列,若能,则给该进程分配成功,否则,不予分配。在确定安全序列的过程中,要检测所有进程的Finish[i]的值,每次循环检测完后要重复从第一个进程开始。 七、运行结果 假设输入进程个数为5,资源种类数为3,并以此输入各进程初始时刻的各种资源数量,如下 若再继续申请资源,假设为P4,申请资源(1 2 2) 假设P1 申请资源(2 2 4)有 八、心得体会 经过这次操作系统课程设计,让我受益匪浅,收获颇多。主要体会如下: 1.利用Vc++编译程序编写银行家算法,进一步理解到通过银行家算法避免死锁的思想,同时也理解了系统死锁产生的原因及条件。 2.在实验过程中所有的设计步骤遵循老师教授的程序功能化的思想,分别定义了三个函数,init()初始化函数,safealg()安全性算法函数,bank()银行家算法函数,体现了函数的模块化思想。这样的话,不仅提高了程序的可读性和可操作性,而且还提高了CPU的利用率和内存的利用率,因为程序的运行是局部性的,这种思想对于段页式存储管理系统尤为重要。 3.实验过程中遇到的种种疑难问题通过自己上网查找答案,锻炼了自己纠错能力和搜索有价值信息的能力及自学的能力,并且进一步巩固了自己以前学过的专业知识。第二篇:操作系统银行家算法(避免死锁)实验报告
第三篇:死锁_银行家算法实验报告
第四篇:操作系统银行家算法实验报告
第五篇:操作系统课程设计----模拟银行家算法避免死锁