当前位置： 首页 > news >正文

操作系统--用JavaScript实现银行家算法

news 来源：原创 2024/5/7 0:50:41

银行家算法产生背景

   银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

   在多道程序系统中，虽然借助于多个进程的并发执行来改善系统的利用率，提高系统的吞吐量，但可能发生一种危险—死锁。死锁就是多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，如无外力作用，他们将无法再向前进行，如再把信号量作为同步工具时，多个Wait和Signal操作顺序不当，会产生进程死锁。 

   然而产生死锁的必要条件有互斥条件，请求和保持条件，不剥夺条件和环路等待条件。在预防死锁的几种方法中，都施加了较强的限制条件，在避免死锁的方法中，所施加的条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，便可避免死锁。 

银行家算法数据结构

假设有n个进程m类资源，则有如下数据结构：

    可利用资源向量Available。这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj类资源K个。

    最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。

   分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源 当前已分配给每一进程的资源数。如果Allocation[i，j]=K，则表示 进程i当前已分得Rj类资源的数目为K。

    需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

    上述三个矩阵存在如下关系：Need[i,j]= Max[i，j]- Allocation[i，j]

结构框图

源代码

1.HTML部分

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
		<meta charset="utf-8" />
		<link rel="stylesheet" href="css/banker.css" type="text/css"/>
		<title>BankerAlgorithmSystem</title>
		
	</head>
	<body>
		<center>
			<h1>银行家算法</h1>
			<div id="input">
				请输入进程数：<input type="text" id="t_process" name="t_process"/>
				<br />
				请输入资源数：<input type="text" id="t_resource" name="t_resource" />
				<br /><br /> <br />
				<input type="button" id="b_ok" value="确定" name="b_ok" onClick="onClickOK()" />
				<br />
			</div>
			<div id="d_display" style="display: none;">
			    <div class="d_table" id="d_table"></div>
			    <br /><br />
			    <input type="button" id="b_ok2" value="提交检查" name="b_ok2" οnclick="onClickOK2()"/>
			    <input type="button" id="b_ok3" value="请求资源" name="b_ok3" οnclick="Banker()" />
			    <div class="output" id="output"></div>
			    <div class="output" id="outputlist"></div>
			    <div class="output" id="output2"></div>
			</div> 
		</center>
		<script src="js/banker.js" type="text/javascript"></script>
	</body>
</html>

2.JavaScript部分

var num_process; //记录进程数
var num_resource;//记录资源数
var max = new Array();//最大资源数
var need = new Array();//资源需求数
var work = new Array();//资源可用数
var work2 = new Array();//用于记录每次进程调用的Work数
var available = new Array();//可利用资源数
var allocation = new Array();//已分配资源
var request = new Array();//请求资源数
var finish = new Array();//是否已完成
var safe = new Array();//安全序列
var fg = false;    //更新Available标志
var o = 0;

//动态创建表格（第一个表格）
function CreateTable(){
	var tabletext = "";
	tabletext = "</br>系统资源的总数依次是：";
	for(i=0;i<num_resource;i++)
	{
		tabletext += " " + available[i] + "    ";
	}
	tabletext += "<p><p/><hr/>";
	tabletext += "请输入各个进程的最大需求数(Max)和已分配数(Allocation)</br>";
	tabletext += "<table border=1 cellspacing=1 width=80% style='text-align:center;border-collapse:collapse;border-width:thin;border-style:solid;margin:0;'><tr><td>资源</td><td colspan="+num_resource+">Max</td><td colspan="+num_resource+">Allocation</td colspan="+num_resource+"><td colspan="+num_resource+">Need</td colspan="+num_resource+"><td colspan="+num_resource+">Available</td></tr>";
	tabletext += "<tr>"+"<td>进程</td>";
	for(i=0;i<4;i++)
	{
		for(j=0;j<num_resource;j++)
		{
			tabletext += "<td>"+String.fromCharCode((65+j))+"</td>";
		}
	}
	tabletext += "</tr>";
    for(i=0;i<num_process;i++)
    {
        tabletext += "<tr><td>P"+i+"</td>";
        for(j=0;j<4;j++)
        {
            for(x=0;x<num_resource;x++)
            {
                tabletext += "<td class='numtd'><input type=text id=e"+i+j+x+" class= 'numtext'"; 
                if(j==2||j==3)
                {
                	tabletext += " readonly=\"readonly\" "
                }
                tabletext += "></td>";
            }  
        }
        tabletext += "</tr>";
    }
    tabletext += "</table>";
	document.getElementById("d_table").innerHTML += tabletext;
}

//创建安全表格
function chickSafeTable(){
	var tabletext = "";
	tabletext = "<table border=1 cellspacing=1 width=80% style='text-align:center;border-collapse:collapse;border-width:thin;border-style:solid;margin:0;'><tr><td>资源</td><td colspan="+num_resource+">Work</td><td colspan="+num_resource+">Need</td colspan="+num_resource+"><td colspan="+num_resource+">Allocation</td colspan="+num_resource+"><td colspan="+num_resource+">Work+Allocation</td colspan="+num_resource+"><td>Finish</td></tr>";
	tabletext += "<tr>"+"<td>进程</td>";
	for(i=0;i<4;i++)
	{
		for(j=0;j<num_resource;j++)
		{
			tabletext += "<td>"+String.fromCharCode((65+j))+"</td>";
		}
	}
	tabletext += "</tr>";
	for(i=0;i<num_process;i++)
    {
        tabletext += "<tr><td>P"+safe[i]+"</td>";
        for(j=0;j<5;j++)
        {
            for(x=0;x<num_resource;x++)
            {
            	if(j==4&&x==0)
            	{
            		tabletext += "<td id=t"+i+j+x+" class='outtable'></td>"; 
            		break;
            	}
            	else
            	{
            		tabletext += "<td id=t"+i+j+x+" class='outtable'></td>"; 
            	}
            }  
        }
        tabletext += "</tr>";
    }
    tabletext += "</table>";
    document.getElementById("output2").innerHTML += tabletext;
    updataOfSafeList();
}

//更新安全表格（第二个表格）
function updataOfSafeList(){
	//Work
	for(i=0;i<num_process;i++)
    {
        for(j=0;j<num_resource;j++)
        {
            document.getElementById("t"+i+"0"+j).innerHTML = work2[i][j]; 
        }  
    }
    //Need
	for(i=0;i<num_process;i++)
    {
        for(j=0;j<num_resource;j++)
        {
            document.getElementById("t"+i+"1"+j).innerHTML = need[parseInt(safe[i])][j];
        }  
    }
    //Allocation
    for(i=0;i<num_process;i++)
    {
        for(j=0;j<num_resource;j++)
        {
            document.getElementById("t"+i+"2"+j).innerHTML = allocation[parseInt(safe[i])][j];
        }  
    }
    //Work+Allocation
    for(i=0;i<num_process;i++)
    {
        for(j=0;j<num_resource;j++)
        {
            document.getElementById("t"+i+"3"+j).innerHTML = work2[i][j]+allocation[safe[i]][j];
        }  
    }
    //Finish
    for(i=0;i<num_process;i++)
    {
        document.getElementById("t"+i+"4"+"0").innerHTML = finish[safe[i]];
    }
}

//点击第一个按钮
function onClickOK(){
	document.getElementById("input").style.display = "none";
	num_process = parseInt(document.getElementById("t_process").value);
	num_resource = parseInt(document.getElementById("t_resource").value);
	ChickNull(num_process,"请输入进程数:");
	ChickNull(num_resource,"请输入资源数:");
	if(isNaN(num_process&&num_resource))
	{
		alert("请输入数字！");
		return;
	}
	alert(num_process+"个进程"+num_resource+"个资源");
	for(i=0;i<num_resource;i++)
	{
		available[i] = window.prompt("第"+(i+1)+"个资源总数：");
		ChickNull(available[i],"请输入资源总数:");
		if(isNaN(available[i]))
		{
			alert("请输入数字！");
			return;
		}
	}
	CreateTable();
	document.getElementById("d_display").style.display = "";
}

//点击第二个按钮
function onClickOK2()
{
	GetInfo();
	ChickSequence();
	PrintSequence("outputlist");
}

//获得填充数据
function GetInfo()
{
    //获取最大资源数
    for(i=0;i<num_process;i++)
    {
        max[i]=new Array();
        for(j=0;j<num_resource;j++)
        {
            max[i][j]=parseInt(document.getElementById("e"+i+"0"+j).value);
            ChickNull(max[i][j],"请输入最大资源数:");
			if(isNaN(max[i][j]))
			{
				alert("请输入数字！");
				return;
			}
        }  
    }
       
    //获取已分配资源数
    for(i=0;i<num_process;i++)
    {
        allocation[i]=new Array();
        for(j=0;j<num_resource;j++)
        {
            allocation[i][j]=parseInt(document.getElementById("e"+i+"1"+j).value);
            ChickNull(allocation[i][j],"请输入已分配资源数:");
			if(isNaN(allocation[i][j]))
			{
				alert("请输入数字！");
				return;
			}
        }  
    }
}

//得到并填充Need
function GetNeed()
{
    //计算各进程对个资源的需求量
    for(i = 0; i < num_process; i ++)
    {
        need[i]=new Array();
        for(j = 0; j < num_resource; j ++)
        {
            need[i][j] = max[i][j] - allocation[i][j];
        }
    }
    //填充Need
    for(i=0;i<num_process;i++)
    {
        for(j=0;j<num_resource;j++)
        {
            document.getElementById("e"+i+"2"+j).value = need[i][j];
        }  
    }
}

//得到Work
function GetWork()
{
    for(j=0;j<num_resource;j++)
    {
        work[j]=available[j];
    }
}

//得到并填充Available
function GetAvailable(fg)
{
	//计算Available
	if(!fg)
	{
		for(i=0;i<num_resource;i++)
		{
			for(j=0;j<num_process;j++)
			{
				available[i] -= allocation[j][i];
				if(available[i]<0)
				{
					alert("请求失败！无可利用资源");
					return false;
				}
			}
		}
	}
	else
	{
		if(available[i]<0)
		{
			alert("请求失败！无可利用资源");
			return false;
		}
		else
		{}
	}
	//填充Available
	for(i=0;i<num_resource;i++)
    {
        document.getElementById("e"+0+"3"+i).value = available[i];  
    }
    return true;
}

//新请求资源
function Banker()
{
	fg = true;
	var v1 = parseInt(window.prompt("请输入第几个进程请求资源"));
	for(i=0;i<num_process;i++)
	{
		request[i] = new Array();
	}
	for(j=0;j<num_resource;j++)
	{
		request[v1-1][j] = window.prompt("进程P"+(v1-1)+"请求资源"+String.fromCharCode((65+j))+"数量：");
		ChickNull(request[v1-1][j],"请输入进程所请求资源数:");
		if(isNaN(request[v1-1][j]))
		{
			alert("请输入数字！");
			return;
		}
	}
	for(j=0;j<num_resource;j++)
	{
		if(request[v1-1][j]>need[v1-1][j])
		{
			alert("请求资源数大于所需最大值，失败！");
			return;
		}
		
		else if(request[v1-1][j]>available[j])
		{
			alert("请求资源数大于可利用资源量，请等待！");
			return;
		}
		else
		{
			available[j] -= request[v1-1][j];
			var v2 = parseInt(allocation[v1-1][j]);
			var v3 = parseInt(request[v1-1][j]);
			allocation[v1-1][j] = v2+v3;
			need[v1-1][j] -= request[v1-1][j];
		}
	}
	ChickSequence();
	PrintSequence("output2");
}

//获得安全序列
function ChickSequence()
{
	GetNeed();
	GetAvailable(fg);
	GetWork();
	//初始化work2
	for(i=0;i<(num_process+1);i++)
	{
		work2[i] = new Array();
	}
	for(i=0;i<num_resource;i++)
	{
		work2[0][i] = work[i];
	}
	//初始化finish
	for(i=0;i<num_process;i++)
	{
		finish[i] = false;
	}
	o = 0;
	//算法核心！！！
	while(o < num_process)
    {
        flag = false;
        for(i = 0; i < num_process; i ++)
        {
            if(finish[i])
            continue;
            for( j = 0; j < num_resource; j ++)
            {
                if(need[i][j] > work[j])
                break;
            }
            if(j == num_resource)
            {
                flag = true;
                safe[o] = i;
                o++;
                finish[i] = true;
                for(k = 0; k < num_resource; k ++)
                {
                	work[k] += allocation[i][k];
                	work2[o][k] = work[k];
                }             
            }
        }
        if(!flag)
        break;
    }
}

//输出安全序列
function PrintSequence(id)
{
    if(o == num_process)
    {
        html="<hr/>该资源是安全的;安全序列为:";
        for(i=0;i<o;i ++)
        {
            html+="P"+safe[i];
            if(i<o-1)
            html+="->";
        }     
    }
    else 
    {
    	html="<hr/>对不起，该资源状态不安全！";
    	document.getElementById(id).innerHTML = html;
    	return;
    }
    document.getElementById(id).innerHTML = html;
    chickSafeTable();
}

//判断输入是否为空
function ChickNull(text,warning)
{
	if(text.length==0)
	{
	    alert(warning);
		return false;　
	}
　　else if (/\s/.test(text))
　　{
　　		alert("输入不能为空格!");
		return false;　
　　}
	return true;
}

3.css部分

body{
	background-image: url(../img/bg2.jpg);
	background-size:100%;
	background-color:#000000;
	font-family:微软雅黑;
	font-size: 20px;
	color: #FFFFFF;
}

h1{
	font-family:微软雅黑;
	font-size:50px;
	color:#FFFFFF;
}

.numtext{
	border: 0px;
	width: 90%;
	height: 100%;
	text-align: center;
	background: none;
	color: #FFFFFF;
}

.numtd{

}

#input{
	margin-top: 0px;
	margin-right: auto;
	margin-bottom: 0px;
	margin-left: auto;
}

 #b_ok{
 	background-color: #87CEEB;
 	color:#FFFFFF;font-family:微软雅黑;
 	font-weight: 900;
 	font-size: 15px;
 	padding:3px 5px;
 	border-radius:100% ;
 	cursor:pointer;
 	width:100px;
 	height:100px;
 }
 
 #b_ok2,#b_ok3{
 	background-color: #87CEEB;
 	color:#FFFFFF;font-family:微软雅黑;
 	font-weight: 900;
 	font-size: 15px;
 	padding:3px 5px;
 	border-radius:15px ;
 	cursor:pointer;
 	width:100px;
 	height:30px;
 }

#t_process,#t_resource{
	text-align: center;
	background: none;
	color: #FFFFFF;
}

相关文章：

  • js严格模式
  • MySQL数据库——使用聚合函数查询
  • Java Excel 合并单元格 Java Excel 实现尾部添加数据 Java Excel 合并单元格 添加数据 poi excel 合并单元格
  • SSM仓库管理系统毕业设计-附源码061015
  • 猿创征文｜Docker【配置好的镜像】 迁移到【新服务器】上 不需要重新配置环境参数·爽
  • 关于现代化应用和云原生应用
  • R语言矩阵运算：矩阵转置、计算逆矩阵、两个矩阵的相乘、构建nxn对角（单位）矩阵
  • 数据结构————堆
  • 【GNN报告】Mila实验室/蒙特利尔大学朱兆成：基于图神经网络的知识图谱推理
  • ssm大型商场移动导游系统的设计与实现毕业设计源码100853
  • springboot日结工管理小程序毕业设计-附源码070940
  • R语言生成字符串的所有成对组合：使用outer函数和paste函数生成所有字符串的成对组合（笛卡尔积）、自定义指定组合字符串的分隔符
  • 详解模板引擎二
  • Java Spring整合Redis工具类
  • 深入理解 Compose Navigation 实现原理
  • 4. 路由到控制器 - Laravel从零开始教程
  • el-input获取焦点 input输入框为空时高亮 el-input值非法时
  • ES6系统学习----从Apollo Client看解构赋值
  • iOS仿今日头条、壁纸应用、筛选分类、三方微博、颜色填充等源码
  • iOS高仿微信项目、阴影圆角渐变色效果、卡片动画、波浪动画、路由框架等源码...
  • JavaScript创建对象的四种方式
  • javascript面向对象之创建对象
  • leetcode388. Longest Absolute File Path
  • Material Design
  • MyEclipse 8.0 GA 搭建 Struts2 + Spring2 + Hibernate3 （测试）
  • ng6--错误信息小结（持续更新）
  • Perseus-BERT——业内性能极致优化的BERT训练方案
  • spring cloud gateway 源码解析（4）跨域问题处理
  • vue-router的history模式发布配置
  • webpack+react项目初体验——记录我的webpack环境配置
  • Webpack4 学习笔记 - 01：webpack的安装和简单配置
  • -- 查询加强-- 使用如何where子句进行筛选，% _ like的使用
  • 理解IaaS, PaaS, SaaS等云模型 (Cloud Models)
  • 聊聊directory traversal attack
  • 马上搞懂 GeoJSON
  • 那些被忽略的 JavaScript 数组方法细节
  • 前端存储 - localStorage
  • 驱动程序原理
  • 在Docker Swarm上部署Apache Storm：第1部分
  • 分布式关系型数据库服务 DRDS 支持显示的 Prepare 及逻辑库锁功能等多项能力 ...
  • 好程序员大数据教程Hadoop全分布安装（非HA)
  • 曾刷新两项世界纪录，腾讯优图人脸检测算法 DSFD 正式开源 ...
  • # 执行时间 统计mysql_一文说尽 MySQL 优化原理
  • （1）STL算法之遍历容器
  • （4）通过调用hadoop的java api实现本地文件上传到hadoop文件系统上
  • （6）添加vue-cookie
  • （C语言版）链表（三）——实现双向链表创建、删除、插入、释放内存等简单操作...
  • （简单有案例）前端实现主题切换、动态换肤的两种简单方式
  • （十二）springboot实战——SSE服务推送事件案例实现
  • （十五）Flask覆写wsgi_app函数实现自定义中间件
  • (原)记一次CentOS7 磁盘空间大小异常的解决过程
  • （转）Android学习笔记 --- android任务栈和启动模式
  • (转)Java socket中关闭IO流后，发生什么事？（以关闭输出流为例） .
  • （转）大型网站的系统架构
  • （转）甲方乙方——赵民谈找工作