用java语言,模拟实现操作系统的银行家算法。
先来看看我理解的银行家算法的程序流程图:
详细设计
1.先选用储存进程和系统资源的数据结构,两者我都是用链表的形式储存的。(其实系统资源用数组比较好,因为它基本上都是修改,没有增加和删除。)。选用链表之后就是创建链表类的属性,系统资源的属性有名字、系统总资源和可用资源。进程类链表的属性是进程名字、最大需要资源的链表头节点和当前占有资源的链表头节点。
2.然后是设计菜单。
大概设计成这样就行,然后用switch语句执行每一个选项的方法。
前四个选项的输入,主要就是初始化所有属性,给属性赋值就行了。
第七个选项,也是遍历两个链表,查看属性就行了。我重点说一下,5和6的两个算法。
3.安全性检测,因为是检测,所以进入方法之后,首先赋值进程链表和资源的链表。然后创建一个判断当前进程链表是否有可以被满足的进程的方法。传入进程链表的头节点,如果当前可用资源可以满足此链表的某一个进程节点,就将此节点占用的资源加到可用资源上。然后删除此节点,再次调用此方法,看是否能满足某一个节点。如果可用资源数对每一个进程的节点都不满足,说明当前没有安全序列。如果每次都能满足,每次都删除节点,当头节点为null的时候,证明所有节点都释放完毕,安全序列已经生成。
4.开始请求资源,这是银行家算法的核心,因为是试分配,所以还是要复制两条链表,然后系统对某一个进程进行资源请求,可以分为五种情况。
①.请求的资源大于系统可用资源,做一个判断打印一下就可以;
②.请求的资源大于此进程尚需的资源数,做一个判断打印一下就可以;
③.请求的资源满足条件,减少系统可用资源,增加请求资源进程的占有资源,在此状态下调用安全性检测方法,系统不处于安全状态。(因为是在复制链表中进行的,所以不用再次赋值,直接舍弃复制的链表)
④.请求的资源满足条件,减少系统可用资源,增加请求资源进程的占有资源,在此状态下调用安全性检测方法,系统处于安全状态,系统资源进行真实分配,将复制链表的值,赋给真实链表。
⑤.系统资源请求加上进程之前所占有的资源,刚好每种资源等于它的最大需求量,此进程得到满足,释放所有资源,将可用资源增加,此进程在真实链表中被删除。
源代码如下:
import java.util.Scanner;
class Resource{
String name;
int num;
int Available;
Resource rNext;
public Resource(String name,int num){
this.name = name;
this.num = num;
}
}
class Process{
String name;
Resource maxNeed;
Resource already;
Process pNext;
public Process(String name){
this.name = name;
}
}
public class 测试3{
static int T = 0; //用来控制检测安全序列的变量
//输入资源的种类和数量
static void Alloctionadd(Resource res,Process pro){
Resource cur = res;
int i = 1;
while(cur!=null){
Process tmp = pro;
int count = 0;
while(tmp!=null){
Resource tmp2 = tmp.already;
for(int j=1; j<i; j++){
tmp2 = tmp2.rNext;
}
count += tmp2.num;
tmp = tmp.pNext;
}
cur.Available = cur.num-count;
cur = cur.rNext;
i++;
}
}
static Resource addResource(Resource res,String str,int num){
if(res == null){
res = new Resource(str,num);
return res;
}
Resource cur = res;
while(cur.rNext!=null){
cur = cur.rNext;
}
cur.rNext = new Resource(str,num);
return res;
}
static Resource InitResource(){
Resource res = null;
Scanner sc = new Scanner(System.in);
System.out.println("资源的数量为:");
int a=sc.nextInt();
for(int i=1; i<=a; i++){
System.out.println("第"+i+"个资源的名称是:");
String b=sc.next();
System.out.println("第"+i+"个资源的资源总数是:");
int c=sc.nextInt();
res = addResource(res,b,c);
}
return res;
}
//输入进程的数量
static Process addProcess(Process pro,String str){
if(pro == null){
pro = new Process(str);
return pro;
}
Process cur = pro;
while(cur.pNext!=null){
cur = cur.pNext;
}
cur.pNext = new Process(str);
return pro;
}
static Process InitProcess(int num){
Process pro = null;
for(int i=1; i<=num; i++){
pro = addProcess(pro,"S"+i);
}
return pro;
}
//进程最大需求资源个数
static void MaxNeed(Process pro,Resource res){
Scanner sc = new Scanner(System.in);
Resource cur2 = null;
Process cur = pro;
while(cur!=null){
int i = 1;
cur2 = res;
while(cur2!=null){
System.out.println(cur.name+"进程的第"+i+"个资源的最大需求量是:");
int num = sc.nextInt();
cur.maxNeed = addResource(cur.maxNeed,cur2.name,num);
cur2 = cur2.rNext;
i++;
}
cur = cur.pNext;
}
}
//t0时刻已经分配的资源
static void Already(Process pro,Resource res){
Scanner sc = new Scanner(System.in);
Resource cur2 = null;
Process cur = pro;
while(cur!=null){
int i = 1;
cur2 = res;
while(cur2!=null){
System.out.println(cur.name+"进程的第"+i+"个资源的已经分配量是:");
int num = sc.nextInt();
cur.already = addResource(cur.already,cur2.name,num);
cur2 = cur2.rNext;
i++;
}
cur = cur.pNext;
}
}
//安全性检测
static Process copyProcess(Process pro){
Process pro2 = null;
Process cur = pro;
while(cur!=null){
pro2 = addProcess(pro2,cur.name);
cur = cur.pNext;
}
Process cur2 = pro2;
cur = pro;
while(cur!=null){
cur2.already = copyResource(cur.already,pro2);
cur2.maxNeed = copyResource(cur.maxNeed,pro2);
cur2 = cur2.pNext;
cur = cur.pNext;
}
return pro2;
}
static Resource copyResource(Resource res,Process pro){
Resource res2 = null;
Resource cur = res;
while(cur!=null){
res2 = addResource(res2,cur.name,cur.num);
cur = cur.rNext;
}
cur = res;
Resource cur2 = res2;
while(cur!=null){
cur2.Available = cur.Available;
cur = cur.rNext;
cur2 = cur2.rNext;
}
return res2;
}
static Process IsSecurity(Process pro,Resource res){
Process cur1 = pro;
Process pre = cur1;
Resource cur2 = null;
while(cur1!=null){
Resource tmp1 = cur1.maxNeed;
Resource tmp2 = cur1.already;
cur2 = res;
while(cur2!=null){
if(cur2.Available < tmp1.num - tmp2.num){ // 可用资源是否小于 需要资源
break;
}
tmp1 = tmp1.rNext;
tmp2 = tmp2.rNext;
cur2 = cur2.rNext;
}
if(cur2 == null){ //走完了所有资源 都满足需求
cur2 = res;
tmp2 = cur1.already;
while(cur2!=null){
cur2.Available += tmp2.num;
cur2 = cur2.rNext;
tmp2 = tmp2.rNext;
}
System.out.println(cur1.name);
return pre;
}
pre = cur1;
cur1 = cur1.pNext;
T++;
}
return null;
}
static int SecurityCheck(Process pro,Resource res){
Process pro2 = copyProcess(pro);
Resource res2 = copyResource(res,pro2);
while(pro2!=null) {
T = 0;
Process pre = IsSecurity(pro2, res2);
if(pre == null){
System.out.println("没有安全序列!!");
return 0;
}
if(pre == pro2 && T == 0){ //T如果没+过 说明返回的是头节点
pro2 = pro2.pNext;
continue;
}
pre.pNext = pre.pNext.pNext;
}
return 1;
}
//开始请求资源
static int NewRequires(Process pro,Resource res){
int count = 0;
Scanner sc = new Scanner(System.in);
Process pro2 = copyProcess(pro);
Resource res2 = copyResource(res,pro2);
Resource tmp = res2;
System.out.println("第几个进程需要请求资源?");
int a=sc.nextInt();
Process cur = pro2;
for(int i=1; i<a; i++){
cur = cur.pNext;
}
Resource cur2 = cur.already;
Resource max = cur.maxNeed;
for(int j=1; cur2!=null; j++){
System.out.println("请输入第"+j+"个资源新请求的个数:");
int b=sc.nextInt();
cur2.num += b;
if(cur2.num > max.num){
System.out.println("请求超出最大资源需求,请求出错!");
return 0;
}
tmp.Available -= b;
if(tmp.Available < 0){
System.out.println("已有资源"+tmp.name+"不足,请求错误!");
return 0;
}
max = max.rNext;
tmp = tmp.rNext;
cur2 = cur2.rNext;
}
Resource cur3 = res;
cur = pro;
Process cur1 = pro2;
Process pre = null;
for(int i=1; i<a; i++){
pre = cur;
cur = cur.pNext;
cur1 = cur1.pNext;
}
Resource cur4 = cur.already;
if(SecurityCheck(pro2,res2) == 1) {
while (res2 != null) {
cur3.Available = res2.Available;
cur4.num = cur1.already.num;
if(cur4.num != cur1.maxNeed.num){
count = 1;
}
cur3 = cur3.rNext;
res2 = res2.rNext;
cur4 = cur4.rNext;
cur1.already = cur1.already.rNext;
cur1.maxNeed = cur1.maxNeed.rNext;
}
if(count == 0){
cur3 = res;
cur4 = cur.already;
while(cur3!=null){
cur3.Available += cur4.num;
cur3 = cur3.rNext;
cur4 = cur4.rNext;
}
if(pre == null){
return 1;
}else{
pre.pNext = pre.pNext.pNext;
}
}
}
return 0;
}
//查看进程和资源
static void check(Resource res,Process pro){
Resource cur = res;
Process cur2 = pro;
System.out.println("系统每个资源的总数: "+" 可用资源数");
while(cur!=null){
System.out.println(cur.name+" : "+cur.num+"、"+cur.Available);
cur = cur.rNext;
}
System.out.println("系统每个进程的信息:");
while(cur2!=null){
System.out.print(cur2.name+" : ");
Resource cur3 = cur2.maxNeed;
System.out.print("各资源最大需求数 :");
while(cur3!=null){
System.out.print(cur3.num+"、");
cur3 = cur3.rNext;
}
System.out.print(" 各资源当前拥有数 :");
cur3 = cur2.already;
while(cur3 !=null){
System.out.print(cur3.num+"、");
cur3 = cur3.rNext;
}
cur2 = cur2.pNext;
System.out.println();
}
}
static void menu(){
Scanner sc = new Scanner(System.in);
Resource res = null;
Process pro = null;
int a = 1;
while(a!=0)
{
System.out.println("1.输入资源的种类和数量");
System.out.println("2.输入进程的数量");
System.out.println("3.输入每个进程的最大需求个数");
System.out.println("4.输入t0时刻每个进程已经分配的资源个数");
System.out.println("5.安全性检测");
System.out.println("6.开始请求资源");
System.out.println("7.查看当前系统的资源和进程");
System.out.println("0.退出程序");
System.out.println("请输入您需要的服务:");
a=sc.nextInt();
switch(a){
case 1:
res = InitResource();
break;
case 2:
System.out.println("进程的总个数为:");
int num = sc.nextInt();
pro = InitProcess(num);
break;
case 3:
MaxNeed(pro,res);
break;
case 4:
Already(pro,res);
Alloctionadd(res,pro);
break;
case 5:
SecurityCheck(pro,res);
break;
case 6:
if(NewRequires(pro,res) == 1){
pro = pro.pNext;
}
break;
case 7:
check(res,pro);
break;
case 0:
System.out.println("正常退出!");
break;
default:
System.out.println("输入错误,请重新输入");
break;
}
}
}
public static void main(String[] args) {
menu();
}
}