Operating Systems: Lab 2 Banker’s Algorithm
Deadlock is a set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.
For example, in the dining philosopher problem, if every philosopher picks up the chopstick located on their left, this problem occurs deadlock.
We need to use some policies to avoid or solve the deadlock.
Here is an algorithm to avoid deadlock —— Banker’s Algorithm.
Basic concept
Deadlock is a close connection with the resources. If deadlock occurs, that means resource allocation has some problems.
The resource is anything that must be acquired, used, and released over time—such as the CPU, memory space, I/O device, and so on.
But the resources are limited, so we need to allocate them.
Deadlock occurs have four sufficient conditions:
- Mutual exclusion: One resource only can be used by one process at the same time.
- Hold and wait: The process will hold resources after allocation, if some resources are occupied by another process, it will wait (not released immediately) until the occupied resources are released.
- No preemption: Resources are released only after the process terminates. Resources are not released for process allocation.
- Circular wait: Here a set of processes $P_0,P_1,P_2 \dots P_N$, $P_1$ holds resources which $P_0$ needed, $P_2$ holds resources which $P_1$ needed, and so on. In the end, the resources that $P_N$ needed were held by $P_0$.
Thinking about the dining philosopher problem, every philosopher pikc up the left chopstick.
In order to avoid the deadlock, we proposed the concept of Safe State.
Safe State means each process in the wait queue can be executed by a certain sequence. If they don’t exist a certain sequence, we called it unsafe state.
- Safe State -> no deadlock
- Unsafe State -> may occur deadlock
- Deadlock -> in unsafe state
So, if we want to avoid deadlock, we need to make sure the OS does not in the unsafe state.
Banker’s algorithm is a kind of way to avoid deadlock, the core of the algorithm is to make sure resources can satisfy each process.
Basic Policy in Banker’s Algorithm
The simple policy is to compare the work resource and need resource.
In this algorithm, we need to set four variables(data struct)about each process:
Available: Vector of length $m$. If $available [j] = k$, there are k instances of resource type $R_j$ available
Max: $n \times m$ matrix. If $Max [i,j] = k$, then process $P_i$ may request at most k instances of resource type $R_j$.
Allocation: $n \times m$ matrix. If $Allocation[i,j] = k$ then Pi is currently allocated k instances of $R_j$
Need: $n \times m$ matrix. If $Need[i,j] = k$, then $P_i$ may need k more instances of $R_j$ to complete its task
And we use the finish to mark whether each process is finished or not.
Here describe the core of the algorithm by flowchart:
Algorithm Realize
The implementation of the algorithm relies on five classes, some common methods here will ignore them, and here just instruct some specific methods.
Input from File
In order to simplify the input of data, here we used the CSV file as the input file.
More about the read or write CSV file, please click CSV 文件的读写 – Bulbul to see.
Data Fields
path: the path of the CSV file.data: the data read from the CSV file.
Methods
We read data from the CSV file at first, then we need to get the different number of resources from specific areas. This is correlative with the order in the CSV file.
Resource
All the resources about the process will use this to express.
Data Fields and Constructors
ArrayList<Integer> resource: instead of a vector of the resource. If you want to compare them, you need through thecompare()method.
Three constructors here:
- Empty, non-argument
- Set name
- Used by deep copy
Dyadic Operation Methods
This method provides some way to compare/plus/subtraction the data/
compare(): if and only if the data in the corresponding position is always bigger than this, it will return true, Otherwise it will return false.
plus(): it will plus the data in the corresponding position from other to this. and return the result(use the deep copy).
substraction(): it will make the data in this subtraction the data in other(at the corresponding position) and return the result(use the deep copy).
Process
One process instance instead a process in OS.
Three Resource instance represent respectively max resource,allocation resource and need resource, the PID can identify which process here is.
Other methods are some common accessors, mutators and some template out methods, here is not go into detail here.
Banker’s algorithm
The core of the algorithm!!
No such difference with said before, here just use the queue instead of the finish vector.
Ready Queue
We put all the processes in the ready queue when the resources satisfies the current process, we will remove it from the read queue, and add it allocation resource to the work resource.
For each check, we will traverse the ready queue, if no one process can be satisfied, the program will break and mark it is not safe.
Example
Class Main
public class Main {
public static void main(String[] args) throws Exception {
String path = ".\\data.csv";
FileData file = new FileData(path);
file.getData();
Banker banker = new Banker(file);
banker.out();
if(banker.isSafety())
{
System.out.println("The state is safe!");
System.out.println("And the safe order is:");
banker.outOrder();
}else{
System.out.println("Sorry, the state is not safe!");
}
}
}
/*
* ----------------In Oct.2022----------------
* SDUT Operating Systems: Lab 2 Banker's Algorithm
* By SDUT Bulbul.
* Blog: https://bulbul559.cn
* ----------------In Oct.2022----------------
*/
Class Banker
/*
* The core of the Banker's alogrithm.
*
* isSafety() will check the state id safety or not.
*/
import java.util.*;
public class Banker {
private ArrayList<Process> process;
private ArrayList<Integer> safeOrder;
Resource available;
Banker(FileData file)
{
process = file.getProcessResource();
available = file.getAvailable();
safeOrder = new ArrayList<Integer>();
}
public boolean isSafety()
{
Resource work = available.copy();
ArrayList<Process> readyQueue = new ArrayList<Process>(process);
work.setName("work");
/*
* This loop is terminated if and only if the readyQueue is empty or 'isOK' is false.
*
* 1. readyQueue is empty: it means each process can be satisfied by operating system.
* 2. isOK is false: it means the OS scan the each process in readQueue, but no one of them can be satisfied.
*/
while(readyQueue.size() != 0)
{
boolean isOK = false;
for(int i = 0 ; i < readyQueue.size() ; i++)
{
Process nowProcess = readyQueue.get(i);
Resource need = nowProcess.getNeed();
Resource allocation = nowProcess.getAllocation();
if( work.compare(need) )
{
safeOrder.add(Integer.valueOf(nowProcess.getPID()));
work = work.plus(allocation);
readyQueue.remove(i);
isOK = true;
i--;
}
}
/*
* Is no one process can be satisfied, break the loop.
*/
if( !isOK )
{
break;
}
}
if(readyQueue.size() == 0)
{
return true;
}else{
return false;
}
}
/*
* Deep copy.
*/
public ArrayList<Process> COPY()
{
return new ArrayList<Process>(process);
}
/*
* Some out template.
*/
public void outOrder()
{
for(Integer i : safeOrder)
{
System.out.print(i.intValue() + " ");
}
System.out.println();
}
public void out()
{
System.out.println("The number of process is " + this.process.size());
System.out.println("The number of resources that process needed is " + this.process.get(0).getMax().getResourceCount());
for(Process i:process)
{
i.outNeed();
}
}
}
/*
* ----------------In Oct.2022----------------
* SDUT Operating Systems: Lab 2 Banker's Algorithm
* By SDUT Bulbul.
* Blog: https://bulbul559.cn
* ----------------In Oct.2022----------------
*/
Class FileData
/*
* This class will process the input data.
* 1. Read the data from the csv file
* 2. Recognize the Max, Allocation and Available resource, and load them into process list.
*/
import java.io.*;
import java.util.*;
public class FileData {
private String path;
private ArrayList<String[]> data;
/*
* Constructor will get the file path
*/
FileData() {
this.path = null;
this.data = new ArrayList<String[]>();
}
FileData(String path) {
this.path = path;
this.data = new ArrayList<String[]>();
}
/*
* getData() method can read data form CSV
* And here use the ArraryList to memory them
*/
public void getData() throws Exception {
try {
File file = new File(path);
Scanner in = new Scanner(file);
while (in.hasNextLine()) {
/*
* Use the loop to get all data in the file
* For this lines, we can use split() to divide the data,
* and use the ArrayList to memory them.
*/
String newLine = in.nextLine();
String eachData[] = newLine.split(",");
data.add(eachData);
}
in.close();
/*
* Show the data which program get.
*/
System.out.println("The data read is:");
for (String[] t1 : data) {
for (String s : t1) {
System.out.print(s + "\t");
}
System.out.println();
}
} catch (Exception Error) {
System.out.println("Read data failed: " + Error);
System.exit(0);
}
}
/*
* Load the available resource from ArrayList<String[]> data.
*/
public Resource getAvailable()
{
Resource available = new Resource();
String []dataLine = this.data.get(1);
for(int i = 0 ; i < dataLine.length ; i++)
{
available.add(dataLine[i]);
}
return available;
}
/*
* Load the Max and Allocation resource from ArrayList<String[]> data.
*/
public ArrayList<Process> getProcessResource(){
ArrayList<Process> result = new ArrayList<Process>();
/*
* tagLine is help to recognize the resource is Max or Allocation
*/
String []tagLine = this.data.get(2);
for(int i = 3 ; i < data.size() ; i++)
{
/*
* Because the data structure in CSV file is fixed,
* so we can use the fixed template to get the data.
*/
int PID;
Resource max = new Resource("Max");
Resource allocated = new Resource("Allocation");
String []dataLine = this.data.get(i);
PID = Integer.parseInt(dataLine[0].substring(1, 2));
for(int j = 0; j < dataLine.length ; j++)
{
if(tagLine[j].equals("Max"))
{
max.add(dataLine[j]);
}
if(tagLine[j].equals("Allocation"))
{
allocated.add(dataLine[j]);
}
}
Process newProcess = new Process(PID,max,allocated);
newProcess.setNeed();
result.add(newProcess);
}
return result;
}
}
/*
* ----------------In Oct.2022----------------
* SDUT Operating Systems: Lab 2 Banker's Algorithm
* By SDUT Bulbul.
* Blog: https://bulbul559.cn
* ----------------In Oct.2022----------------
*/
Class Resource
/*
* A instance of this calss is represent one resource about process.
*/
import java.util.*;
public class Resource {
private ArrayList<Integer> resource;
private int resourceCount = 0;
private String name;
/*
* Constructor.
*
* 1. Empty
* 2. Set name
* 3. Used by deep copy
*/
Resource() {
this.resource = new ArrayList<Integer>();
this.resourceCount = 0;
}
Resource(String name) {
this.resource = new ArrayList<Integer>();
this.name = name;
this.resourceCount = 0;
}
Resource(ArrayList<Integer> resource, int resourceCount, String name) {
this.name = name;
this.resource = resource;
this.resourceCount = resourceCount;
}
/*
* There is some dyadic operation methods,
* it provides some way to compare/plus/subtraction the data
*
* compare(): iff the data in the corresponding position is always bigger than 'this',
* it will return true, Otherwise it will return false.
* plus(): it will plus the data in the corresponding position from 'other' to 'this'.
* and return the result(use the deep copy)
* subtraction(): it will make the data in 'this' subtraction the data in 'other'(at the corresponding position)
* and return the result(use the deep copy)
*/
public boolean compare(Resource other)
{
for(int i = 0 ; i < this.resourceCount ; i++)
{
if(this.resource.get(i) < other.get(i))
{
return false;
}
}
return true;
}
public Resource plus(Resource other)
{
ArrayList<Integer> result = new ArrayList<Integer>();
int ans = 0;
for (int i = 0; i < this.resourceCount; i++) {
ans = this.resource.get(i) + other.get(i);
result.add(Integer.valueOf(ans));
}
return new Resource(result, this.resourceCount, this.name);
}
public Resource subtraction(Resource other) {
ArrayList<Integer> result = new ArrayList<Integer>();
int ans = 0;
for (int i = 0; i < this.resourceCount; i++) {
ans = this.resource.get(i) - other.get(i);
result.add(Integer.valueOf(ans));
}
return new Resource(result, this.resourceCount, this.name);
}
/*
* Accessor and mutator methods.
*/
public int getResourceCount() {
return this.resourceCount;
}
public void setName(String name) {
this.name = name;
}
public void setResourceCount(int resourceCount) {
this.resourceCount = resourceCount;
}
/*
* Add an element to the resource list,
* and resource count increase one at the same time.
*/
public void add(String newElement)
{
this.resource.add(Integer.valueOf(newElement));
this.setResourceCount(this.resourceCount + 1);
}
/*
* Get the i-th element from the resource list
*/
public int get(int index) {
return resource.get(index).intValue();
}
/*
* Make a deep copy of the resource.
*/
public Resource copy() {
ArrayList<Integer> _COPY = new ArrayList<Integer>(resource);
return new Resource(_COPY, this.resourceCount, this.name);
}
/*
* Here is a testing method,
* it will output all the data of this instance.
*/
public void out() {
System.out.print(name + "\t");
for (Integer data : resource) {
System.out.print(data + " ");
}
System.out.println();
}
}
/*
* ----------------In Oct.2022----------------
* SDUT Operating Systems: Lab 2 Banker's Algorithm
* By SDUT Bulbul.
* Blog: https://bulbul559.cn
* ----------------In Oct.2022----------------
*/
Class Process
/*
* One instance of this class is represent one process in the OS.
*/
public class Process {
private Resource max;
private Resource allocation;
private Resource need;
private int PID;
/*
* Constructor
*/
Process()
{
this.max = null;
this.allocation = null;
this.need = null;
this.PID = 0;
}
Process(int PID, Resource max, Resource allocation)
{
this.PID = PID;
this.max = max;
this.allocation = allocation;
}
/*
* Accessor and mutator methods
*/
public int getPID()
{
return this.PID;
}
public Resource getMax()
{
return this.max;
}
public Resource getAllocation()
{
return this.allocation;
}
public Resource getNeed()
{
return this.need;
}
public void setMax(Resource resource)
{
this.max = resource;
}
public void setAllocation(Resource resource)
{
this.allocation = resource;
}
public void setNeed()
{
/*
* The need is equals max - allocation.
*/
this.need = this.max.subtraction(this.allocation);
this.need.setName("Need");
}
/*
* Some out template
*/
public void out()
{
System.out.println("PID = "+this.PID);
System.out.println("Max :");
max.out();
System.out.println("Allocation :");
allocation.out();
System.out.println("Need :");
need.out();
}
public void outMax()
{
max.out();
}
public void outAllocation()
{
allocation.out();
}
public void outNeed()
{
need.out();
}
}
/*
* ----------------In Oct.2022----------------
* SDUT Operating Systems: Lab 2 Banker's Algorithm
* By SDUT Bulbul.
* Blog: https://bulbul559.cn
* ----------------In Oct.2022----------------
*/
