Skip to content

Instantly share code, notes, and snippets.

@janryWang

janryWang/index.html

Created January 2, 2015 02:22
Show Gist options
  • Save janryWang/9cd07216fa38711649fa to your computer and use it in GitHub Desktop.
Save janryWang/9cd07216fa38711649fa to your computer and use it in GitHub Desktop.
Download ZIP
Raw
index.html
<!DOCTYPE html>
<html ng-app="BankAlgorithm">
<head>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<meta content="yes" name="apple-mobile-web-app-capable">
<meta content="black" name="apple-mobile-web-app-status-bar-style">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
<link href="http://cdn.bootcss.com/normalize/3.0.1/normalize.css" rel="stylesheet">
<script src="http://cdn.bootcss.com/jquery/2.1.1/jquery.min.js"></script>
<script src="http://cdn.bootcss.com/angular.js/1.3.0-beta.13/angular.min.js"></script>
<meta charset="utf-8">
<title>JS Bin</title>
<style id="jsbin-css">
.content{
margin:10px;
}
.content *{
box-sizing: content-box !important;
}
.content h1,.content h2{
margin: 15px 0;
}
.input textarea {
outline: none;
display: block;
padding: 10px;
min-height: 45px;
width: 100%;
line-height:25px;
letter-spacing: 2px;
font-size: 18px;
resize: none;
box-sizing: border-box !important;
border-radius: 5px;
border: 1px solid #ddd;
height: 150px;
color: #808;
}
.resource-input textarea{
height:20px;
}
.ctrls{
margin-top:20px;
text-align:center;
}
.ctrls button{
box-sizing: border-box !important;
outline:none;
display:block;
width:100%;
color:#fff;
border:none;
background:#59D2D6;
margin:10px 0;
padding:10px 20px;
border-radius:10px;
cursor:pointer;
transition:all 0.15s ease-out;
}
.ctrls button:hover{
background:#CFE5FE;
}
.msg{
margin:20px 0px;
padding:10px;
color:#fff;
border-radius:5px;
display:none;
font-size:12px;
}
.msg.red,.msg.green{
display:block;
}
.red{
background:red;
}
.green{
background:green;
}
.msg li{
margin:5px 0;
}
.safe-orders-input{
display:none;
}
.safe-orders-input.show{
display:block;
}
.safe-orders-input ul{
list-style:none;
outline:none;
display:block;
background:#fff;
padding:10px;
width:94.888%;
resize:none;
border-radius:5px;
border:1px solid #ddd;
min-height:40px;
}
.safe-orders-input ul li{
margin:10px 0;
color:#aaa;
font-size:13px;
}
</style>
</head>
<body ng-controller="main">
<div class="content">
<h1>银行家算法：</h1>
<div class="resource-input input">
<h2>资源初始化(Avaliables)</h2>
<textarea ng-model="ui_avaliables" placeholder="语法：(x,x,x...)"></textarea>
</div>
<div class="process-input input">
<h2>进程初始化(Max)</h2>
<textarea ng-model="ui_max" placeholder="语法：processName:(x,x,x...),换行进行批量初始化"></textarea>
</div>
<div class="allocation-input input">
<h2>资源分配(allocation)</h2>
<textarea ng-model="ui_allocation" placeholder="语法：processName:(x,x,x...),换行进行批量初始化"></textarea>
</div>
<div class="request-input input">
<h2>请求构造(requests)</h2>
<textarea ng-model="ui_request" placeholder="语法：processName:(x,x,x...),换行进行批量请求"></textarea>
</div>
<div ng-class="{'show':bank.safeOrders.length>0}" class="safe-orders-input input">
<h2>安全序列(safeOrders)</h2>
<ul>
<li ng-repeat="order in bank.safeOrders">{{order}}</li>
<li>共{{bank.safeOrders.length}}个安全序列</li>
</ul>
</div>
<div class="msg" ng-if="msg.state != 'pedding'" ng-class="{'green':msg.state=='success','red':msg.state=='falied'}">
{{msg.text}}
</div>
<div class="ctrls">
<button ng-click="submitState();">提交当前时刻下的分配情况</button>
<button ng-click="sendRequest();">进程提交请求</button>
</div>
</div>
<script id="jsbin-javascript">
/**
* 银行家算法：
* 用于进程的调度过程中，检测某进程队列是否会出现死锁情况
* 这样便可以预防死锁
* version:0.0.1
* author:Janry Wang
* email:wangzhili56@126.com
* qq:332397428
*/
var App = angular.module("BankAlgorithm", []);
App.factory("BankAl", function ($q) {
function Bank(resources, processes, allocations) {
var $self = this;
this.states = {
avaliables: {},
maxs: {},
allocations: {},
needs: {},
cache: {}
};
this.processes = {};//进程集合
this.safeOrders = [];//安全序列
this.cache = {};
this.addResources(resources);
this.addProcesses(processes);
this.addAllocations(allocations);
}
angular.extend(Bank.prototype, {
/**
* 将当前状态缓存
*/
_addCache: function () {
for (var name in this.stats) {
this.cache[name] = $.extend(true, {}, this.states[name]);
}
},
/**
* 状态回滚
*/
_rollBack: function () {
for (var name in this.cache) {
this.states[name] = $.extend(true, {}, this.cache[name]);
}
},
/**
* 添加单一资源方法
* name:资源名称
* avaliable:资源数量
*/
addResource: function (name, available) {
this.states.avaliables[name] = available;
return this;
},
/**
* 批量添加资源方法
* resources:资源集合
*/
addResources: function (resources) {
if (!angular.isObject(resources)) return this;
for (var name in resources) {
this.addResource(name, resources[name]);
}
return this;
},
/**
* 批量添加进程方法
* processes:进程集合
*/
addProcesses: function (processes) {
if (!angular.isObject(processes)) return this;
for (var name in processes) {
this.addProcess(name, processes[name]);
}
return this;
},
/**
* 添加单一进程方法
* p_name:进程名称
* p_maxs:进程对所有资源的最大需求数{r_name:r_num}
*/
addProcess: function (p_name, p_maxs) {
this.processes[p_name] = true;
this.states.maxs[p_name] = p_maxs;
for (var r_name in this.states.avaliables) {//遍历所有资源
this.states.allocations[p_name] = this.states.allocations[p_name] || {};
this.states.allocations[p_name][r_name] = this.states.allocations[p_name][r_name] || 0;
this.states.needs[p_name] = this.states.needs[p_name] || {};
this.states.maxs[p_name][r_name] = this.states.maxs[p_name][r_name] || 0;
this.states.needs[p_name][r_name] = this.states.maxs[p_name][r_name] - this.states.allocations[p_name][r_name];
}
return this;
},
/**
* 添加资源分配
* avaliables:分配集合
*/
addAllocations: function (allocations) {
if (!angular.isObject(allocations)) return this;
for (var p_name in allocations) {
for (var r_name in allocations[p_name]) {
this.states.allocations[p_name][r_name] = allocations[p_name][r_name];
this.states.needs[p_name][r_name] = this.states.maxs[p_name][r_name] - this.states.allocations[p_name][r_name];
//this.states.avaliables[r_name] -= this.states.allocations[p_name][r_name];
}
}
return this;
},
/**
* 进程请求多资源方法
* p_name:进程名称
* reqs:请求的资源{r_name:r_num}
*/
request: function (p_name, reqs) {
var ok = 0,
delay = $q.defer(),
$self = this;
if (!angular.isObject(reqs)) {
delay.reject("请求的资源不符合规范");
}
this._addCache();
for (var r_name in reqs) {
if (this._request(p_name, r_name, reqs[r_name])) {
ok++;
}
}
if (ok >= Object.keys(reqs).length) {
this.safeCheck().then(function () {
delay.resolve("安全检测通过：" + p_name + " 请求资源成功！");
}, function () {
delay.reject("安全检测不通过：" + p_name + " 请求资源失败，需要等待！");
});
} else {
this._rollBack();
delay.reject(p_name + " 请求资源失败，需要等待！");
}
return delay.promise;
},
/**
* 进程请求单一资源方法
* p_name:进程名称
* r_name:资源名称
* num:请求的资源数
*/
_request: function (p_name, r_name, num) {
if (!this.processes[p_name]) return false;
if (num <= this.states.needs[p_name][r_name]) {
if (num <= this.states.avaliables[r_name]) {
this.states.avaliables[r_name] -= num;
this.states.allocations[p_name][r_name] += num;
this.states.needs[p_name][r_name] -= num;
return true;
} else {
return false;
}
} else {
return false;
}
return true;
},
//安全性检查
safeCheck: function () {
var delay = $q.defer();
var processes = Object.keys(this.processes);
var allocations = this.states.allocations;
var avaliables = this.states.avaliables;
var p_num = processes.length;
var r_num = Object.keys(avaliables).length;
var needs = this.states.needs;
var safeOrders = [];
//查找安全序列
_findSafeOrder(processes);
if (safeOrders.length > 0) {
this.safeOrders = safeOrders;
delay.resolve();
} else {
delay.reject();
}
return delay.promise;
//求全排列
function permutate(array, callback) {
function p(array, index, callback) {
function swap(a, i1, i2) {
var t = a[i1];
a[i1] = a[i2];
a[i2] = t;
}
if (index == array.length - 1) {
callback(array);
return 1;
} else {
var count = p(array, index + 1, callback);
for (var i = index + 1; i < array.length; i++) {
swap(array, i, index);
count += p(array, index + 1, callback);
swap(array, i, index);
}
return count;
}
}
if (!array || array.length === 0) {
return 0;
}
return p(array, 0, callback);
}
//找安全序列
function _findSafeOrder(_processes) {
permutate(_processes, function (processOrder) {
var p_name, ok, i, r_name, finished = 0, work = Object.create(avaliables);
for (i = 0; i < p_num; i++) {
p_name = processOrder[i];
ok = 0;
for (r_name in work) {
if (needs[p_name][r_name] <= work[r_name]) {
work[r_name] += allocations[p_name][r_name];
ok++;
}
}
if (ok >= r_num) {
finished++;
}
}
if (finished >= p_num) {
safeOrders.push(processOrder.slice());//将副本存入安全序列
}
});
}
}
});
return Bank;
});
//解决用户输入的语法
App.factory("dealInput", function () {
function cleanBlank(input) {
return input.replace(/\s*/g, "");
}
function cleanBrackets(input){
return input.replace(/(\(|\))*/g, "");
}
return function (input, type) {
var res = {}, matched,i,j, tmpMatched, variable, datas;
input = cleanBlank(input);
if (type == "avaliables") {
matched = input.match(/(?:\(|（)(?:\s*(\d+(?:,|，)?)\s*?)+(?:\)|）)/g);
if (matched) {
datas = cleanBrackets(matched[0]).split(/,|，/);
for (i = 0; i < datas.length; i++) {
res["resource_" + i] = datas[i];
}
} else {
throw "表达式语法不规范";
}
} else if (type == "max" || type == "allocation" || type == "requests") {
matched = input.match(/([a-zA-Z$_][a-zA-Z0-9$_]+)\s*(?:\:|：)\s*(?:\(|（)(?:\s*(\d+(?:,|，)?)\s*?)+(?:\)|）)/g);
if (matched && matched.length) {
for (i = 0; i < matched.length; i++) {
tmpMatched = matched[i].split(/:|：/);
variable = tmpMatched[0];
datas = cleanBrackets(tmpMatched[1]).split(/,|，/);
res[variable] = {};
for (j = 0; j < datas.length; j++) {
res[variable]["resource_" + j] = datas[j];
}
}
} else {
throw "表达式语法不规范";
}
}
return res;
};
});
App.controller("main", function ($scope, BankAl, $q, dealInput) {
$scope.currentState = "pedding";
$scope.msg = {
state: "pedding",
text: "等待执行"
};
$scope.ui_avaliables="(3,3,2)";
$scope.ui_max = "p1:(7,5,3)\np2:(3,2,2)\np3:(9,0,2)\np4:(2,2,2)\np5:(4,3,3)";
$scope.ui_allocation = "p1:(0,1,0)\np2:(2,0,0)\np3:(3,0,2)\np4:(2,1,1)\np5:(0,0,2)";
$scope.submitState = function () {
var inputs = {};
try {
if($scope.ui_avaliables && $scope.ui_max && $scope.ui_allocation){
inputs.avaliables = dealInput($scope.ui_avaliables, "avaliables");
inputs.max = dealInput($scope.ui_max, "max");
inputs.allocation = dealInput($scope.ui_allocation, "allocation");
$scope.bank = new BankAl(inputs.avaliables, inputs.max, inputs.allocation);
$scope.bank.safeCheck();
} else {
throw "请先输入相关数据源";
}
} catch (e) {
$scope.msg = {
state: "falied",
text: e.message ? e.message : e
};
}
};
$scope.sendRequest = function () {
var requests, tasks = [];
try {
if($scope.ui_request){
requests = dealInput($scope.ui_request, "requests");
if (!$scope.bank) throw "请先提交当前时刻的分配";
for (var p_name in requests) {
tasks.push($scope.bank.request(p_name, requests[p_name]));
}
$q.all(tasks).then(function (res) {
$scope.msg = {
state: "success",
text: res
};
}, function (res) {
$scope.msg = {
state: "falied",
text: res
};
});
} else {
throw "请先构造请求";
}
} catch (e) {
$scope.msg = {
state: "falied",
text: e.message ? e.message : e
};
}
};
});
</script>
<script id="jsbin-source-css" type="text/css">.content{
margin:10px;
}
.content *{
box-sizing: content-box !important;
}
.content h1,.content h2{
margin: 15px 0;
}
.input textarea {
outline: none;
display: block;
padding: 10px;
min-height: 45px;
width: 100%;
line-height:25px;
letter-spacing: 2px;
font-size: 18px;
resize: none;
box-sizing: border-box !important;
border-radius: 5px;
border: 1px solid #ddd;
height: 150px;
color: #808;
}
.resource-input textarea{
height:20px;
}
.ctrls{
margin-top:20px;
text-align:center;
}
.ctrls button{
box-sizing: border-box !important;
outline:none;
display:block;
width:100%;
color:#fff;
border:none;
background:#59D2D6;
margin:10px 0;
padding:10px 20px;
border-radius:10px;
cursor:pointer;
transition:all 0.15s ease-out;
}
.ctrls button:hover{
background:#CFE5FE;
}
.msg{
margin:20px 0px;
padding:10px;
color:#fff;
border-radius:5px;
display:none;
font-size:12px;
}
.msg.red,.msg.green{
display:block;
}
.red{
background:red;
}
.green{
background:green;
}
.msg li{
margin:5px 0;
}
.safe-orders-input{
display:none;
}
.safe-orders-input.show{
display:block;
}
.safe-orders-input ul{
list-style:none;
outline:none;
display:block;
background:#fff;
padding:10px;
width:94.888%;
resize:none;
border-radius:5px;
border:1px solid #ddd;
min-height:40px;
}
.safe-orders-input ul li{
margin:10px 0;
color:#aaa;
font-size:13px;
}</script>
<script id="jsbin-source-javascript" type="text/javascript">/**
* 银行家算法：
* 用于进程的调度过程中，检测某进程队列是否会出现死锁情况
* 这样便可以预防死锁
* version:0.0.1
* author:Janry Wang
* email:wangzhili56@126.com
* qq:332397428
*/
var App = angular.module("BankAlgorithm", []);
App.factory("BankAl", function ($q) {
function Bank(resources, processes, allocations) {
var $self = this;
this.states = {
avaliables: {},
maxs: {},
allocations: {},
needs: {},
cache: {}
};
this.processes = {};//进程集合
this.safeOrders = [];//安全序列
this.cache = {};
this.addResources(resources);
this.addProcesses(processes);
this.addAllocations(allocations);
}
angular.extend(Bank.prototype, {
/**
* 将当前状态缓存
*/
_addCache: function () {
for (var name in this.stats) {
this.cache[name] = $.extend(true, {}, this.states[name]);
}
},
/**
* 状态回滚
*/
_rollBack: function () {
for (var name in this.cache) {
this.states[name] = $.extend(true, {}, this.cache[name]);
}
},
/**
* 添加单一资源方法
* name:资源名称
* avaliable:资源数量
*/
addResource: function (name, available) {
this.states.avaliables[name] = available;
return this;
},
/**
* 批量添加资源方法
* resources:资源集合
*/
addResources: function (resources) {
if (!angular.isObject(resources)) return this;
for (var name in resources) {
this.addResource(name, resources[name]);
}
return this;
},
/**
* 批量添加进程方法
* processes:进程集合
*/
addProcesses: function (processes) {
if (!angular.isObject(processes)) return this;
for (var name in processes) {
this.addProcess(name, processes[name]);
}
return this;
},
/**
* 添加单一进程方法
* p_name:进程名称
* p_maxs:进程对所有资源的最大需求数{r_name:r_num}
*/
addProcess: function (p_name, p_maxs) {
this.processes[p_name] = true;
this.states.maxs[p_name] = p_maxs;
for (var r_name in this.states.avaliables) {//遍历所有资源
this.states.allocations[p_name] = this.states.allocations[p_name] || {};
this.states.allocations[p_name][r_name] = this.states.allocations[p_name][r_name] || 0;
this.states.needs[p_name] = this.states.needs[p_name] || {};
this.states.maxs[p_name][r_name] = this.states.maxs[p_name][r_name] || 0;
this.states.needs[p_name][r_name] = this.states.maxs[p_name][r_name] - this.states.allocations[p_name][r_name];
}
return this;
},
/**
* 添加资源分配
* avaliables:分配集合
*/
addAllocations: function (allocations) {
if (!angular.isObject(allocations)) return this;
for (var p_name in allocations) {
for (var r_name in allocations[p_name]) {
this.states.allocations[p_name][r_name] = allocations[p_name][r_name];
this.states.needs[p_name][r_name] = this.states.maxs[p_name][r_name] - this.states.allocations[p_name][r_name];
//this.states.avaliables[r_name] -= this.states.allocations[p_name][r_name];
}
}
return this;
},
/**
* 进程请求多资源方法
* p_name:进程名称
* reqs:请求的资源{r_name:r_num}
*/
request: function (p_name, reqs) {
var ok = 0,
delay = $q.defer(),
$self = this;
if (!angular.isObject(reqs)) {
delay.reject("请求的资源不符合规范");
}
this._addCache();
for (var r_name in reqs) {
if (this._request(p_name, r_name, reqs[r_name])) {
ok++;
}
}
if (ok >= Object.keys(reqs).length) {
this.safeCheck().then(function () {
delay.resolve("安全检测通过：" + p_name + " 请求资源成功！");
}, function () {
delay.reject("安全检测不通过：" + p_name + " 请求资源失败，需要等待！");
});
} else {
this._rollBack();
delay.reject(p_name + " 请求资源失败，需要等待！");
}
return delay.promise;
},
/**
* 进程请求单一资源方法
* p_name:进程名称
* r_name:资源名称
* num:请求的资源数
*/
_request: function (p_name, r_name, num) {
if (!this.processes[p_name]) return false;
if (num <= this.states.needs[p_name][r_name]) {
if (num <= this.states.avaliables[r_name]) {
this.states.avaliables[r_name] -= num;
this.states.allocations[p_name][r_name] += num;
this.states.needs[p_name][r_name] -= num;
return true;
} else {
return false;
}
} else {
return false;
}
return true;
},
//安全性检查
safeCheck: function () {
var delay = $q.defer();
var processes = Object.keys(this.processes);
var allocations = this.states.allocations;
var avaliables = this.states.avaliables;
var p_num = processes.length;
var r_num = Object.keys(avaliables).length;
var needs = this.states.needs;
var safeOrders = [];
//查找安全序列
_findSafeOrder(processes);
if (safeOrders.length > 0) {
this.safeOrders = safeOrders;
delay.resolve();
} else {
delay.reject();
}
return delay.promise;
//求全排列
function permutate(array, callback) {
function p(array, index, callback) {
function swap(a, i1, i2) {
var t = a[i1];
a[i1] = a[i2];
a[i2] = t;
}
if (index == array.length - 1) {
callback(array);
return 1;
} else {
var count = p(array, index + 1, callback);
for (var i = index + 1; i < array.length; i++) {
swap(array, i, index);
count += p(array, index + 1, callback);
swap(array, i, index);
}
return count;
}
}
if (!array || array.length === 0) {
return 0;
}
return p(array, 0, callback);
}
//找安全序列
function _findSafeOrder(_processes) {
permutate(_processes, function (processOrder) {
var p_name, ok, i, r_name, finished = 0, work = Object.create(avaliables);
for (i = 0; i < p_num; i++) {
p_name = processOrder[i];
ok = 0;
for (r_name in work) {
if (needs[p_name][r_name] <= work[r_name]) {
work[r_name] += allocations[p_name][r_name];
ok++;
}
}
if (ok >= r_num) {
finished++;
}
}
if (finished >= p_num) {
safeOrders.push(processOrder.slice());//将副本存入安全序列
}
});
}
}
});
return Bank;
});
//解决用户输入的语法
App.factory("dealInput", function () {
function cleanBlank(input) {
return input.replace(/\s*/g, "");
}
function cleanBrackets(input){
return input.replace(/(\(|\))*/g, "");
}
return function (input, type) {
var res = {}, matched,i,j, tmpMatched, variable, datas;
input = cleanBlank(input);
if (type == "avaliables") {
matched = input.match(/(?:\(|（)(?:\s*(\d+(?:,|，)?)\s*?)+(?:\)|）)/g);
if (matched) {
datas = cleanBrackets(matched[0]).split(/,|，/);
for (i = 0; i < datas.length; i++) {
res["resource_" + i] = datas[i];
}
} else {
throw "表达式语法不规范";
}
} else if (type == "max" || type == "allocation" || type == "requests") {
matched = input.match(/([a-zA-Z$_][a-zA-Z0-9$_]+)\s*(?:\:|：)\s*(?:\(|（)(?:\s*(\d+(?:,|，)?)\s*?)+(?:\)|）)/g);
if (matched && matched.length) {
for (i = 0; i < matched.length; i++) {
tmpMatched = matched[i].split(/:|：/);
variable = tmpMatched[0];
datas = cleanBrackets(tmpMatched[1]).split(/,|，/);
res[variable] = {};
for (j = 0; j < datas.length; j++) {
res[variable]["resource_" + j] = datas[j];
}
}
} else {
throw "表达式语法不规范";
}
}
return res;
};
});
App.controller("main", function ($scope, BankAl, $q, dealInput) {
$scope.currentState = "pedding";
$scope.msg = {
state: "pedding",
text: "等待执行"
};
$scope.ui_avaliables="(3,3,2)";
$scope.ui_max = "p1:(7,5,3)\np2:(3,2,2)\np3:(9,0,2)\np4:(2,2,2)\np5:(4,3,3)";
$scope.ui_allocation = "p1:(0,1,0)\np2:(2,0,0)\np3:(3,0,2)\np4:(2,1,1)\np5:(0,0,2)";
$scope.submitState = function () {
var inputs = {};
try {
if($scope.ui_avaliables && $scope.ui_max && $scope.ui_allocation){
inputs.avaliables = dealInput($scope.ui_avaliables, "avaliables");
inputs.max = dealInput($scope.ui_max, "max");
inputs.allocation = dealInput($scope.ui_allocation, "allocation");
$scope.bank = new BankAl(inputs.avaliables, inputs.max, inputs.allocation);
$scope.bank.safeCheck();
} else {
throw "请先输入相关数据源";
}
} catch (e) {
$scope.msg = {
state: "falied",
text: e.message ? e.message : e
};
}
};
$scope.sendRequest = function () {
var requests, tasks = [];
try {
if($scope.ui_request){
requests = dealInput($scope.ui_request, "requests");
if (!$scope.bank) throw "请先提交当前时刻的分配";
for (var p_name in requests) {
tasks.push($scope.bank.request(p_name, requests[p_name]));
}
$q.all(tasks).then(function (res) {
$scope.msg = {
state: "success",
text: res
};
}, function (res) {
$scope.msg = {
state: "falied",
text: res
};
});
} else {
throw "请先构造请求";
}
} catch (e) {
$scope.msg = {
state: "falied",
text: e.message ? e.message : e
};
}
};
});
</script></body>
</html>
Raw
jsbin.howumi.css
.content{
margin:10px;
}
.content *{
box-sizing: content-box !important;
}
.content h1,.content h2{
margin: 15px 0;
}
.input textarea {
outline: none;
display: block;
padding: 10px;
min-height: 45px;
width: 100%;
line-height:25px;
letter-spacing: 2px;
font-size: 18px;
resize: none;
box-sizing: border-box !important;
border-radius: 5px;
border: 1px solid #ddd;
height: 150px;
color: #808;
}
.resource-input textarea{
height:20px;
}
.ctrls{
margin-top:20px;
text-align:center;
}
.ctrls button{
box-sizing: border-box !important;
outline:none;
display:block;
width:100%;
color:#fff;
border:none;
background:#59D2D6;
margin:10px 0;
padding:10px 20px;
border-radius:10px;
cursor:pointer;
transition:all 0.15s ease-out;
}
.ctrls button:hover{
background:#CFE5FE;
}
.msg{
margin:20px 0px;
padding:10px;
color:#fff;
border-radius:5px;
display:none;
font-size:12px;
}
.msg.red,.msg.green{
display:block;
}
.red{
background:red;
}
.green{
background:green;
}
.msg li{
margin:5px 0;
}
.safe-orders-input{
display:none;
}
.safe-orders-input.show{
display:block;
}
.safe-orders-input ul{
list-style:none;
outline:none;
display:block;
background:#fff;
padding:10px;
width:94.888%;
resize:none;
border-radius:5px;
border:1px solid #ddd;
min-height:40px;
}
.safe-orders-input ul li{
margin:10px 0;
color:#aaa;
font-size:13px;
}
Raw
jsbin.howumi.js
/**
* 银行家算法：
* 用于进程的调度过程中，检测某进程队列是否会出现死锁情况
* 这样便可以预防死锁
* version:0.0.1
* author:Janry Wang
* email:wangzhili56@126.com
* qq:332397428
*/
var App = angular.module("BankAlgorithm", []);
App.factory("BankAl", function ($q) {
function Bank(resources, processes, allocations) {
var $self = this;
this.states = {
avaliables: {},
maxs: {},
allocations: {},
needs: {},
cache: {}
};
this.processes = {};//进程集合
this.safeOrders = [];//安全序列
this.cache = {};
this.addResources(resources);
this.addProcesses(processes);
this.addAllocations(allocations);
}
angular.extend(Bank.prototype, {
/**
* 将当前状态缓存
*/
_addCache: function () {
for (var name in this.stats) {
this.cache[name] = $.extend(true, {}, this.states[name]);
}
},
/**
* 状态回滚
*/
_rollBack: function () {
for (var name in this.cache) {
this.states[name] = $.extend(true, {}, this.cache[name]);
}
},
/**
* 添加单一资源方法
* name:资源名称
* avaliable:资源数量
*/
addResource: function (name, available) {
this.states.avaliables[name] = available;
return this;
},
/**
* 批量添加资源方法
* resources:资源集合
*/
addResources: function (resources) {
if (!angular.isObject(resources)) return this;
for (var name in resources) {
this.addResource(name, resources[name]);
}
return this;
},
/**
* 批量添加进程方法
* processes:进程集合
*/
addProcesses: function (processes) {
if (!angular.isObject(processes)) return this;
for (var name in processes) {
this.addProcess(name, processes[name]);
}
return this;
},
/**
* 添加单一进程方法
* p_name:进程名称
* p_maxs:进程对所有资源的最大需求数{r_name:r_num}
*/
addProcess: function (p_name, p_maxs) {
this.processes[p_name] = true;
this.states.maxs[p_name] = p_maxs;
for (var r_name in this.states.avaliables) {//遍历所有资源
this.states.allocations[p_name] = this.states.allocations[p_name] || {};
this.states.allocations[p_name][r_name] = this.states.allocations[p_name][r_name] || 0;
this.states.needs[p_name] = this.states.needs[p_name] || {};
this.states.maxs[p_name][r_name] = this.states.maxs[p_name][r_name] || 0;
this.states.needs[p_name][r_name] = this.states.maxs[p_name][r_name] - this.states.allocations[p_name][r_name];
}
return this;
},
/**
* 添加资源分配
* avaliables:分配集合
*/
addAllocations: function (allocations) {
if (!angular.isObject(allocations)) return this;
for (var p_name in allocations) {
for (var r_name in allocations[p_name]) {
this.states.allocations[p_name][r_name] = allocations[p_name][r_name];
this.states.needs[p_name][r_name] = this.states.maxs[p_name][r_name] - this.states.allocations[p_name][r_name];
//this.states.avaliables[r_name] -= this.states.allocations[p_name][r_name];
}
}
return this;
},
/**
* 进程请求多资源方法
* p_name:进程名称
* reqs:请求的资源{r_name:r_num}
*/
request: function (p_name, reqs) {
var ok = 0,
delay = $q.defer(),
$self = this;
if (!angular.isObject(reqs)) {
delay.reject("请求的资源不符合规范");
}
this._addCache();
for (var r_name in reqs) {
if (this._request(p_name, r_name, reqs[r_name])) {
ok++;
}
}
if (ok >= Object.keys(reqs).length) {
this.safeCheck().then(function () {
delay.resolve("安全检测通过：" + p_name + " 请求资源成功！");
}, function () {
delay.reject("安全检测不通过：" + p_name + " 请求资源失败，需要等待！");
});
} else {
this._rollBack();
delay.reject(p_name + " 请求资源失败，需要等待！");
}
return delay.promise;
},
/**
* 进程请求单一资源方法
* p_name:进程名称
* r_name:资源名称
* num:请求的资源数
*/
_request: function (p_name, r_name, num) {
if (!this.processes[p_name]) return false;
if (num <= this.states.needs[p_name][r_name]) {
if (num <= this.states.avaliables[r_name]) {
this.states.avaliables[r_name] -= num;
this.states.allocations[p_name][r_name] += num;
this.states.needs[p_name][r_name] -= num;
return true;
} else {
return false;
}
} else {
return false;
}
return true;
},
//安全性检查
safeCheck: function () {
var delay = $q.defer();
var processes = Object.keys(this.processes);
var allocations = this.states.allocations;
var avaliables = this.states.avaliables;
var p_num = processes.length;
var r_num = Object.keys(avaliables).length;
var needs = this.states.needs;
var safeOrders = [];
//查找安全序列
_findSafeOrder(processes);
if (safeOrders.length > 0) {
this.safeOrders = safeOrders;
delay.resolve();
} else {
delay.reject();
}
return delay.promise;
//求全排列
function permutate(array, callback) {
function p(array, index, callback) {
function swap(a, i1, i2) {
var t = a[i1];
a[i1] = a[i2];
a[i2] = t;
}
if (index == array.length - 1) {
callback(array);
return 1;
} else {
var count = p(array, index + 1, callback);
for (var i = index + 1; i < array.length; i++) {
swap(array, i, index);
count += p(array, index + 1, callback);
swap(array, i, index);
}
return count;
}
}
if (!array || array.length === 0) {
return 0;
}
return p(array, 0, callback);
}
//找安全序列
function _findSafeOrder(_processes) {
permutate(_processes, function (processOrder) {
var p_name, ok, i, r_name, finished = 0, work = Object.create(avaliables);
for (i = 0; i < p_num; i++) {
p_name = processOrder[i];
ok = 0;
for (r_name in work) {
if (needs[p_name][r_name] <= work[r_name]) {
work[r_name] += allocations[p_name][r_name];
ok++;
}
}
if (ok >= r_num) {
finished++;
}
}
if (finished >= p_num) {
safeOrders.push(processOrder.slice());//将副本存入安全序列
}
});
}
}
});
return Bank;
});
//解决用户输入的语法
App.factory("dealInput", function () {
function cleanBlank(input) {
return input.replace(/\s*/g, "");
}
function cleanBrackets(input){
return input.replace(/(\(|\))*/g, "");
}
return function (input, type) {
var res = {}, matched,i,j, tmpMatched, variable, datas;
input = cleanBlank(input);
if (type == "avaliables") {
matched = input.match(/(?:\(|（)(?:\s*(\d+(?:,|，)?)\s*?)+(?:\)|）)/g);
if (matched) {
datas = cleanBrackets(matched[0]).split(/,|，/);
for (i = 0; i < datas.length; i++) {
res["resource_" + i] = datas[i];
}
} else {
throw "表达式语法不规范";
}
} else if (type == "max" || type == "allocation" || type == "requests") {
matched = input.match(/([a-zA-Z$_][a-zA-Z0-9$_]+)\s*(?:\:|：)\s*(?:\(|（)(?:\s*(\d+(?:,|，)?)\s*?)+(?:\)|）)/g);
if (matched && matched.length) {
for (i = 0; i < matched.length; i++) {
tmpMatched = matched[i].split(/:|：/);
variable = tmpMatched[0];
datas = cleanBrackets(tmpMatched[1]).split(/,|，/);
res[variable] = {};
for (j = 0; j < datas.length; j++) {
res[variable]["resource_" + j] = datas[j];
}
}
} else {
throw "表达式语法不规范";
}
}
return res;
};
});
App.controller("main", function ($scope, BankAl, $q, dealInput) {
$scope.currentState = "pedding";
$scope.msg = {
state: "pedding",
text: "等待执行"
};
$scope.ui_avaliables="(3,3,2)";
$scope.ui_max = "p1:(7,5,3)\np2:(3,2,2)\np3:(9,0,2)\np4:(2,2,2)\np5:(4,3,3)";
$scope.ui_allocation = "p1:(0,1,0)\np2:(2,0,0)\np3:(3,0,2)\np4:(2,1,1)\np5:(0,0,2)";
$scope.submitState = function () {
var inputs = {};
try {
if($scope.ui_avaliables && $scope.ui_max && $scope.ui_allocation){
inputs.avaliables = dealInput($scope.ui_avaliables, "avaliables");
inputs.max = dealInput($scope.ui_max, "max");
inputs.allocation = dealInput($scope.ui_allocation, "allocation");
$scope.bank = new BankAl(inputs.avaliables, inputs.max, inputs.allocation);
$scope.bank.safeCheck();
} else {
throw "请先输入相关数据源";
}
} catch (e) {
$scope.msg = {
state: "falied",
text: e.message ? e.message : e
};
}
};
$scope.sendRequest = function () {
var requests, tasks = [];
try {
if($scope.ui_request){
requests = dealInput($scope.ui_request, "requests");
if (!$scope.bank) throw "请先提交当前时刻的分配";
for (var p_name in requests) {
tasks.push($scope.bank.request(p_name, requests[p_name]));
}
$q.all(tasks).then(function (res) {
$scope.msg = {
state: "success",
text: res
};
}, function (res) {
$scope.msg = {
state: "falied",
text: res
};
});
} else {
throw "请先构造请求";
}
} catch (e) {
$scope.msg = {
state: "falied",
text: e.message ? e.message : e
};
}
};
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment