- Ask for the Allocation Matrix, the Max Requirement Matrix, and the Available Resources.
- Calculate the Needs Matrix by subtracting the Allocation Matrix from the Max Requirement Matrix element-wise.
- Compare the current available resources to the Needs table row-wise from top to bottom (this is by choice).
- If each resource need is less than the available resource, note the process.
- Add the allocation of the noted process to the available resources, then return to step 3 and ignore the noted process/es.
- If all the processes have finished. Then the system is safe and can return the sequence of the noted process/es. [END]
- Else, that would mean that the currently available resources cannot accomodate the unfinished process/es.
- Thus, a deadlock is detected. [END]
export function BankersAlgorithm(allocation: number[][], max: number[][], resources: number[]) {
console.log('Initial Allocation:');
console.table(allocation);
console.log('Maximum Requirement:');
console.table(max);
const need = getNeed(allocation, max);
let sequence: number[] = [];
let available_sequence: number[][] = [];
available_sequence.push(resources);
const process_length = available_sequence[available_sequence.length - 1].length;
console.log('Available Resources: ', available_sequence[available_sequence.length - 1]);
console.log('Need Matrix:');
console.table(need);
for (let i = 0; i < need.length; i++) {
let j = 0;
if (!sequence.includes(i)) {
for (j = 0; j < process_length; j++) {
if (need[i][j] > available_sequence[available_sequence.length - 1][j]) {
break;
}
}
if (process_length === j) {
sequence.push(i); //? Add the process ID to the sequence
let new_available = getNewAvailable(
allocation[i],
available_sequence[available_sequence.length - 1]
);
available_sequence.push(new_available);
i = -1;
}
}
}
if (sequence.length !== allocation.length) {
console.log('Deadlock detected');
console.log('Sequence before deadlock:');
console.log('P' + sequence.join(' -> P') + ` -> ? `);
return { available_sequence, need: need, sequence: sequence, status: 2 };
} else {
console.log('No deadlock detected');
console.log('Safe sequence is: ');
console.log('P' + sequence.join(' -> P'));
return { available_sequence, need: need, sequence: sequence, status: 1 };
}
}We get the 3 inputs as parameters for the function and we try to find the Need Matrix.
Namely, getNeed(allocation, max) defined as follows:
const getNeed = (allocation: number[][], max: number[][]) => {
let need: number[][] = [];
for (let i = 0; i < allocation.length; i++) {
need[i] = [];
for (let j = 0; j < allocation[i].length; j++) {
need[i][j] = max[i][j] - allocation[i][j];
}
}
return need;
};This is clearly seen to loop around the two matrices and subtracting it element-wise.
Following the Algorithm, it will now enter the loop in checking the needs of each processes.
If any of the resources cannot be satisfied, then it breaks the loop. Else, the process is noted to the sequence and the available resources is then pushed and
updated using the function getNewAvailable(allocation: number[], resources: number[]) defined as follows:
const getNewAvailable = (allocation: number[], resources: number[]) => {
let available: number[] = [];
for (let i = 0; i < resources.length; i++) {
available[i] = resources[i] + allocation[i];
}
return available;
};Once updated, the loop hits a reset by letting the index to -1 to again check all the processes with the new available resources.
At the end, the implementation will return either status = 1 or status = 2. 1 signifies that the algorithm has found a safe sequence while 2 signifies that the function ended prematurely. Thus, encountered a deadlock.
Here is the complete code of the bankers algorithm where the input for the two matrices and the available resources are handled in the frontend.
// * This is the implementation of the Bankers' Algorithm
// * It takes the inputs of allocation, max, and available matrices as discussed in class
// * with this, the algorithm will check for deadlocks
export function BankersAlgorithm(allocation: number[][], max: number[][], resources: number[]) {
console.log('Initial Allocation:');
console.table(allocation);
console.log('Maximum Requirement:');
console.table(max);
//! Calculate for the need matrix
const need = getNeed(allocation, max);
//! Initialize the final sequence and available sequence
let sequence: number[] = [];
let available_sequence: number[][] = [];
available_sequence.push(resources);
const process_length = available_sequence[available_sequence.length - 1].length;
console.log('Available Resources: ', available_sequence[available_sequence.length - 1]);
console.log('Need Matrix:');
console.table(need);
//? Apply the Bankers's Algorithm line by line
for (let i = 0; i < need.length; i++) {
let j = 0;
if (!sequence.includes(i)) {
for (j = 0; j < process_length; j++) {
if (need[i][j] > available_sequence[available_sequence.length - 1][j]) {
//! Break early if need is greater than available
break;
}
}
//! If equal, then the current available resources can accomodate the process
if (process_length === j) {
sequence.push(i); //? Add the process ID to the sequence
//? Calculate the new available resources which is the sum of the current available resources and the allocation of the process
let new_available = getNewAvailable(
allocation[i],
available_sequence[available_sequence.length - 1]
);
//? Push new value to track the sequence of resources
available_sequence.push(new_available);
i = -1; //? Reset the loop to check for other processes again
}
}
}
if (sequence.length !== allocation.length) {
console.log('Deadlock detected');
console.log("Sequence before deadlock:")
console.log('P' + sequence.join(' -> P') + ` -> ? `);
return { available_sequence, need: need, sequence: sequence, status: 2 };
} else {
console.log('No deadlock detected');
console.log('Safe sequence is: ');
console.log('P' + sequence.join(' -> P'));
return { available_sequence, need: need, sequence: sequence, status: 1 };
}
}
const getNewAvailable = (allocation: number[], resources: number[]) => {
let available: number[] = [];
for (let i = 0; i < resources.length; i++) {
available[i] = resources[i] + allocation[i];
}
return available;
};
//? This function calculates the need matrix
const getNeed = (allocation: number[][], max: number[][]) => {
let need: number[][] = [];
for (let i = 0; i < allocation.length; i++) {
need[i] = [];
for (let j = 0; j < allocation[i].length; j++) {
need[i][j] = max[i][j] - allocation[i][j];
}
}
return need;
};This implementation can be found in the src/lib/bankers/bankers.ts from the sourcecode.