Banker's Algorithm | Safety Algorithm | Resource Request Allocation

The resource allocation algorithm can easily find deadlock situation when cycle exist in the RAG for single instances type resources, but resources allocation algorithm may be fail to recognize deadlock for multiple instances type resources. We use Banker’s algorithm to identify deadlock  in multiple instances type resources. Each process must a priori claim maximum use. We need some data structures as following; here ‘n’ is the number of processes in the system and ‘m’ is the number of resources types.

 

  • Available is a vector of length ‘m’ that defines  number of resources available of each type.

  • Maximum is the n x m matrix that defines maximum demands of each process.

  • Allocation is the n x m matrix that defines the number of resources of each type currently allocated to each process.

  • Need is the n x m matrix that defines remaining resources need of each process.

Safety Algorithm

This algorithm is used to find a system is in safe state or not. Algorithm has overall time complexity is O(mn^2).

(i) Two vectors ‘work’ and ‘finish’ of length m and n respectively. Where,

  • Work = available, and finish[i] = false for i = 0, 1, …., (n-1).

(ii) Find an index i such that

  • Finish[i] = = false

  • Need[i] ≤ work

Else go to step (iv)

(iii) work = work + allocation[i]

Finish[i] = true

Go to step (ii)

(iv) if finish[i] = = true for all i, then the system is in safe state, else system is unsafe state.

 

Resource Request Allocation

‘Request’ is a vector for process Pi, if request[j] = = k, then process Pi wants k instances of resource type Rj.

(i) if request[i] ≤ max_need[i], then go to step(ii) else error as request exceeded maximum needs.

(ii) if request[i] ≤ available, then go to step(ii), else Pi must wait, since resources are not available.

(iii) System pretend to have allocated the requested resources to process Pi by modifying following states;

  • Available = available[i] - request[i] ;

  • Allocation[i] = allocation[i] + Request[i] ;

  • Need[i] = Need[i] - request[i] ;

(iv) if resulting state is safe state, then the resources are allocated to process Pi, else system is in unsafe and process Pi must wait.

 

An Example:

Consider the following example with five processes and three resources of multiple instances:

 

 

Maximum Need

Allocated

Remaining Available

 

A B C

A B C

A B C

P1

3 2 2

2 0 0

3 3 2

P2

9 0 2

3 0 2

 

P3

2 2 2

2 1 1

 

P4

4 3 3

0 0 2

 

 

Solution:

            Remaining need =  Maximum need  - allocated

 

 

Maximum Need

Allocated

Remaining Available

Remaining Need

 

A B C

A B C

A B C

A B C

P1

3 2 2

2 0 0

3 3 2

1 2 2

P2

9 0 2

3 0 2

 

6 0 0

P3

2 2 2

2 1 1

 

0 1 1

P4

4 3 3

0 0 2

 

4 3 1

 

Initially, we have remaining available resources 3, 3, 2 instances of A B C. So, we can satisfy the requirements of either process P1 or P3. If we start with P1 then process P1 gets 1, 2, 2 instances of resources of A B C; completed its execution and releases all 4, 5, 4 now we proceed with process P3, and P4 and then process P2. So, safe sequence is P1, P3, P4 and P2.

Contributor's Info

Created:
0Comment
Synchronization Models | Software Solutions | Hardware Solutions | Solutions Based on Operating System | Solutions Based on Programming Language

IPC is mechanisms an operating system provides to allow processes it manages to share data. provides to allow processes it man There are various synchronization techniques, e.g., software solutions, hardware solutions, Operating system solutions, and compiler based solutions.

Software Solutions

(i) Strict alternation or turn variable or Dekker's algorithm

(ii) Use of flag variable

(iii) Peterson’s algorithm

(iv) Multiple process solution

(v) Barkery’s algorithm

 

Note that Peterson’s algorithm is a combination of strict alternation and use of flag variable techniques. There are some drawbacks of software solutions, e.g., busy waiting is possible, difficult assumption  for memory, complicated to program, blocking a process has more chances than waiting.

 

Hardware Solutions

(i) Test and Set (or Test and Set lock) instruction

(ii) Swap instruction

(iii) Disabling interrupts

 

These mechanisms depends on machine instructions. There are some drawbacks of hardware solutions, e.g., deadlock, starvation and busy waiting may be possible.

 

Solutions Based on Operating System

(i) Counting Semaphore

(ii) Binary Semaphore

 

Semaphore increases complexity when a algorithm require more than one semaphore. Incorrect use of semaphores can cause deadlock and mutual exclusion problem.

 

Solutions Based on Programming Language

(i) Monitor is solution based on compiler.

Contributor's Info

Created:
0Comment