这篇文章给大家分享的是有关C#如何实现银行家算法的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
1.死锁
死锁,顾名思义,是一种锁住不可自行解开的死局。
在操作系统中,“死锁”用于描述资源分配时,进程互相抢占资源,又因为需求的资源被别的进程抢占,只好互相等待,以至于等待循环中的所有进程均无法正常运行的情况。
死锁形成需要四个条件,这四个条件缺少一个,就不会形成死锁。
死锁的四个条件
1)互斥条件
即对于某资源在一段时间内仅允许一个进程占有使用。
2)占有且等待条件/请求和保持条件
在进程已经占有一个或多个资源的情况下,若它仍申请新的资源,在等待获得新的资源时,进程仍会继续占有旧有资源,不会主动释放。
3)不可抢占条件
直到占有该资源的进程使用完毕之前,其他任何进程均不应该强行抢占该资源。
4)循环等待条件
若干个进程之间形成了一个等待循环。
2.安全状态
若针对目前资源分配情况,系统可以找到某种次序为进程分配资源,使得所有进程能够依次运行成功,则称系统此时的分配状态是安全的,分配资源的次序称为“安全序列”。
安全状态时系统中无死锁,所以所有避免死锁的算法都尽可能地使系统进入安全状态。
值得注意的是,即使是安全状态下的系统,如果资源分配不当,仍然可以使系统变为不安全状态。
3.银行家算法
1)设计思想
在系统中,进程发起一项资源分配请求,由系统检查是否可以满足该分配请求,若可以,应暂时满足该请求,并查看此时系统是否仍是安全状态。
2)程序流程图
可以分为三个功能模块,第一个模块检查需求是否可以被满足,第二个模块检查系统是否安全,第三个模块是主程序,通过调用前两个模块实现资源分配或请求驳回。
3)数据结构
设有m种资源,n个进程。
int[] Available[m] 系统内可用资源
int[,] Max[n,m] 进程对每种资源的最大需求
int[,] Allocation[n,m] 已分配给各个进程的资源
int[,] Need[n,m] 目前各个进程对各个资源的需求数
[显然有Need=Max-Allocation]
int[,] Require[m] 对于各种资源的请求函数
bool[] Finish[n] 进程是否可以成功运行的标志
int[] Work[m] 用于分配资源的向量
[定义:Work=Available-Require]
4)窗体设计
5)窗体代码
using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows.Forms; namespace bank{ public partial class Form1 : Form { public int n = 1;//进程数目 public int m = 1;//资源分类数 int[,] Allocation; int[,] Max; int[] Available; int[,] Need; int[] Require; string order;//输出安全序列 public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { n = Convert.ToInt32( tb_proNum.Text); m = Convert.ToInt32(tb_resouseClass.Text); } private void button2_Click(object sender, EventArgs e) { if (rb_allocation.Checked) { tb_output.Text += "Allocation矩阵\r\n"; string[] str = tb_datainput.Text.Split(' '); Allocation = new int[n, m]; for (int i = 0; i < n; i++) { tb_output.Text+="\r\n"; string[] temp= str[i].Split(','); for (int j = 0; j < m; j++) { Allocation[i, j] = Convert.ToInt32(temp[j]); tb_output.Text += " " + Allocation[i, j]; } } } else if (rb_available.Checked) { tb_output.Text += "\r\nAvailable向量\r\n"; string[] str = tb_datainput.Text.Split(','); Available = new int[m]; for (int i = 0; i < m; i++) { Available[i] = Convert.ToInt32(str[i]); tb_output.Text += " " + Available[i]; } } else//输入max矩阵 { tb_output.Text += "\r\nMax矩阵\r\n"; string[] str = tb_datainput.Text.Split(' '); Max = new int[n, m]; for (int i = 0; i < n; i++) { tb_output.Text+="\r\n"; string[] temp = str[i].Split(','); for (int j = 0; j < m; j++) { Max[i, j] = Convert.ToInt32(temp[j]); tb_output.Text += " " + Max[i, j]; } } } } private void button3_Click(object sender, EventArgs e) { int PID = 0; bool[] finish = new bool[n]; for (int i = 0; i < n; i++) { finish[i] = false; } if (tb_pid.Text == "") ; else PID = Convert.ToInt32(tb_pid.Text) ; int bigger_1 = 0; int bigger_2 = 0; ///计算Need矩阵/// Need = new int[n, m]; tb_output.Text += "\r\nNeed矩阵\r\n"; for (int i = 0; i < n; i++) { tb_output.Text += "\r\n"; for (int j = 0; j < m; j++) { Need[i, j] = Max[i, j] - Allocation[i, j]; tb_output.Text += " " + Need[i, j]; } } ///输入Require/// if (tb_require.Text == "") { Require = new int[m]; for (int i = 0; i < m; i++) { Require[i] = 0; } PID = 0; tb_output.Text += "\r\n检测当前状态是否安全中…\r\n"; if (CheckSecure(Available, finish, Need, Allocation)) { tb_output.Text += "系统目前安全"+"安全序列"+order; } else { tb_output.Text += "系统目前不安全"; } } else { string[] str = tb_require.Text.Split(','); Require = new int[m]; for (int i = 0; i < m; i++) { Require[i] = Convert.ToInt32(str[i]); if (Require[i] > Need[PID, i]) bigger_1++; if (Require[i] > Available[i]) bigger_2++; } ///检查/// if (bigger_1 != 0) { tb_output.Text += "\r\n错误:进程申请的资源多于说明的最大量,系统无法满足\r\n"; } else if (bigger_2 != 0) { tb_output.Text += "\r\n进程" + tb_pid.Text + "暂时阻塞\r\n"; } else { int[] temp_available = Available; int[,] temp_allocation = Allocation; int[,] temp_need = Need; for (int j = 0; j < m; j++) { temp_available[j] -= Require[j]; temp_allocation[PID, j] += Require[j]; temp_need[PID, j] -= Require[j]; } if (CheckSecure(temp_available, finish, temp_need, temp_allocation)) { Available = temp_available; Allocation = temp_allocation; Need = temp_need; tb_output.Text += "\r\n系统处于安全状态,且已经分配完毕\r\n"+"安全序列"+order ; } else { tb_output.Text += "\r\n该请求将导致系统处于不安全状态,已经撤销分配\r\n"; } } } }///检查安全状态/// public bool CheckSecure(int[] work,bool[] finish,int[,] temp_need,int[,] temp_allocation) { int num = 0;//need[i]<=work[i]的个数 order =""; int[] wor = work; bool[] finis = finish; int[,] temp_nee = temp_need; int[,] temp_allocatio = temp_allocation;int K=0;while (K < 10){ for (int i = 0; i < n; i++) { if (!finis[i]) { for (int j = 0; j < m; j++) { if (temp_nee[i, j] <= wor[j]) num++; } if (num == m) { for (int j = 0; j < m; j++) { wor[j] += temp_allocatio[i, j]; } finis[i] = true; order += i; num = 0; } else num = 0; } else if (checkFinish(finis)) return true; } K++;} if (checkFinish(finis)) return true; else return false; } public bool checkFinish(bool[] f) {int num=0; foreach (bool k in f) { if (k) num++; } if (num == f.Length) return true; else return false; } }}
计算效果如下:
3.总结
实现功能
允许输入数据(只输入Available,Max,Allocation即可,Need可以自动计算,矩阵同一行元素之间用“,”隔开,换行时用空格隔开)
使用银行家算法进行安全检查(若未提出请求,则应使进程号与Require后面的textbox内容为空,点击“提出请求”按钮即可检查当前系统安全状态)
输出状态结果
输出安全序列(注:输出的是进程号,默认序号从0开始)
不足之处
未写出完整的约束
不能输出分配成功后的系统状态
交互不够人性化,例如没有在输出文本框中加入滚动条,不方便使用者查看结果
问题
例子中经过程序计算后的need矩阵中出现了负数,不知道是为什么,正在排查错误。
关键点
——向量比较:银行家算法中的向量大小比较与数学中的向量大小比较(范数比较)不同,只有向量a中的所有分量均大于向量b,才可以称为向量a大于向量b。向量比较主要用在检查Require是否合法,本例中使用for循环对于两向量的各个分量进行比较,设置一个初始值为0的信号变量,若任一分量小于对应分量,则将信号变量++,循环结束后只需要检查信号变量是否为0即可知道是否前者大于后者。
——矩阵输入:使用split方法,将字符串按照给定符号(char,char[])分隔开,并赋给一个给定大小的数组,在本例中使用逗号和空格分开了不同列不同行的元素,定义全局变量m与n,在给数组赋值前需要使用mn初始化数组大小。
——使用临时变量代替真实变量,方便恢复变量数值。因为银行家算法中,若资源分配后系统不安全,要求系统必须撤销所有分配,所以使用临时变量可以避免大量的恢复运算,即使经过检查后,系统为安全状态,也只需要将临时变量的值赋给真实变量即可。
感谢各位的阅读!关于“C#如何实现银行家算法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!