A

MICROPROJECT REPORT
ON
‘Banker’s & Safety algorithm for deadlock detection and avoidance’

SUBMITTED
BY

Roll No Name of Group Members

45 Aniruddha Pawar
45 Prayush Ghule
46 Kunal Pawar

Under Guidance of :
Mrs. A V Kurkute

Diploma Course in Computer Technology

(As per directives of I scheme)

Sinhgad Technical Education Society’s

[Link] CHAVAN POLYTECHNIC, PUNE – 411051.
ACADEMIC YEAR: 2020 – 2021
 Maharashtra State
Board of technical Education

Certificate
This is to certify that Mr. Pawar Aniruddha Prakash with Roll
No. 45 of Fifth Semester of Diploma in Computer Technology
of Institute Sou. Venutai Chavan Polytechnic (Code : 0040) has
successfully completed the Micro-Project in Operating System
(22516) for the academic year 2020-2021.

Place: SVCP, Pune Enrollment No: 1700400169

Date: Exam Seat No:

Mrs. A V Kurkute Mrs. A V Kurkute Dr. M S Jadhav

Subject Teacher Head of the Department Principal
 Maharashtra State
Board of technical Education

Certificate
This is to certify that Mr. Ghule Prayush Sopan with Roll No.
45 of Fifth Semester of Diploma in Computer Technology of
Institute Sou. Venutai Chavan Polytechnic (Code : 0040) has
successfully completed the Micro-Project in Operating System
(22516) for the academic year 2020-2021.

Place: SVCP, Pune Enrollment No: 1700400099

Date: Exam Seat No:

Mrs. A V Kurkute Mrs. A V Kurkute Dr. M S Jadhav

Subject Teacher Head of the Department Principal
 Maharashtra State
Board of technical Education

Certificate
This is to certify that Mr. Pawar Kunal Shravan with Roll No.
46 of Fifth Semester of Diploma in Computer Technology of
Institute Sou. Venutai Chavan Polytechnic (Code : 0040) has
successfully completed the Micro-Project in Operating System
(22516) for the academic year 2020-2021.

Place: SVCP, Pune Enrollment No: 1700400101

Date: Exam Seat No:

Mrs. A V Kurkute Mrs. A V Kurkute Dr. M S Jadhav

Subject Teacher Head of the Department Principal
 Annexure -1
Part A – Micro-Project Proposal
‘Banker’s & Safety algorithm for deadlock detection and avoidance’

1.0 Aim of the Micro-Project

To acquire knowledge of deadlock & algorithms used to detect and avoid deadlock and
how they are implemented in system and there calculations to detect and avoid deadlock
with help of examples.

2.0 Course Outcomes Addressed

 Apply deadlock avoidance and safety algorithms to detect and avoid deadlocks.

3.0 Proposed Methodology

 We will focus on the materials we need, as well as the instructions and sort it out in a manner
which will expedite different responsibilities of the team members.
 Get information about the algorithms and how they are used to detect and avoid deadlock.
 Solve the problems (examples) based on algorithms to detect and avoid deadlock.
 Cross check all the conclusions and answer.
 Prepare a report on the topic.

4.0 Action Plan

Sr. no Details of activity Planned Planned Name of Responsible
start date finish date Team Members
1 Searching the topic for 25/08/2020 15/09/2020 Aniruddha Pawar
micro-project Prayush Ghule
Kunal Pawar
2 Choosing the topic for 15/09/2020 29/09/2020 Aniruddha Pawar
micro-project Prayush Ghule
Kunal Pawar
 3 Searching the information 29/09/2020 13/10/2020 Aniruddha Pawar
on the topic Prayush Ghule
Kunal Pawar
4 Working on the examples of 13/10/2020 27/10/2020 Aniruddha Pawar
the given topic Prayush Ghule
Kunal Pawar

5 Cross checking and 27/10/2020 03/11/2020 Aniruddha Pawar

correcting the examples Prayush Ghule
Kunal Pawar
6 Preparing the report 03/11/2020 10/11/2020 Aniruddha Pawar
Prayush Ghule
Kunal Pawar
7 Making changes and 10/11/2020 30/11/2020 Aniruddha Pawar
corrections in the report Prayush Ghule
Kunal Pawar
8 Final submission 30/11/2020 30/01/2021 Aniruddha Pawar
Prayush Ghule
Kunal Pawar

5.0 Resources Required

Sr. Name of resource or Specification/Function Qty. Remark

No material
1 Computer System 4 GB RAM, 1
Windows 8.1 OS
2 M. S. Word Text editor 1

3 Browser Google Chrome 1

Names and Roll nos. of Team Members

Sr. no Name Roll no

1 Aniruddha Pawar 45
2 Prayush Ghule 45
3 Kunal Pawar 46
OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

Annexure II
Micro-Project Report
‘Banker’s & Safety algorithm for deadlock detection and avoidance’
1.0 Rationale

In operating system CPU plays more important role of executing processes and
controlling flow of the computing smooth. Deadlocks are the main problems for operating
system tackle with, whenever deadlock occurs execution of processes stops completely. To
overcome (Solve) this deadlock situation there are two algorithms one for avoidance and one
for detection. In further report we are going to see take look at how they are implemented
with the help of examples.

2.0 Aim of the Micro-Project

To acquire knowledge of deadlock & algorithms used to detect and avoid deadlock and
how they are implemented in system and there calculations to detect and avoid deadlock
with help of examples.

3.0 Course Outcomes Achieved

 Applied deadlock avoidance and safety algorithms to detect and avoid deadlocks

4.0 Literature Review

Deadlock is not main threat to the operating system. Deadlocks doesn’t occur more often,
frequency of deadlock occurrence is too less but whenever deadlock occurs system’s
execution stops completely. Most of the systems doesn’t involve by default codes for
deadlock avoidance and detection in system because of deadlock’s rare occurrence and
putting complex code of deadlock avoidance and detection not significantly but affects the
speed of computing. To overcome this situation we can use banker’s & Safety algorithms

SVCP/TYCM Page 7
OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

5.0 Actual Methodology Followed

 We focused on the materials we needed, as well as the instructions and sorted it out in a
manner which will expedite different responsibilities of the team members.
 Gathered information about the algorithms and how they are used to detect and avoid
deadlock.
 Solved examples to better understand Algorithms and their methods.
 Cross checked outputs and answers.
 Prepared a report.
 Checked for any further changes to be done in the project.
 Created the final report of the project.

6.0 Actual Resources Used

Sr. Name of resource or Specification/Function Qty. Remark

No material
1 Computer System 4GB RAM, 1
Windows 10 OS
2 Notepad Text editor 1

3 Browser Google Chrome 1

7.0 Outputs of the Micro-Project

We got detail information about CPU scheduling & algorithms, also the deadlock situation
which is has four necessary conditions ([Link] Exclusion [Link] & Wait [Link]-Preemption
[Link] Wait) if that all conditions hold simultaneously in system then deadlock situation
can occur in the system. There are four ways we can face the deadlock out of four we saw
two methods one is deadlock avoidance and second one is deadlock detection. We also
focused ourselves on other techniques of handling deadlocks.

SVCP/TYCM Page 8
 OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

Banker’s Algorithm Example Solutions

Example 1
Assume that there are 5 processes, P0 through P4 and 4 types of resources. At T0 we have the
following system state:
Max Instances of Resource Type A = 3 (2 allocated + 1 Available)
Max Instances of Resource Type B = 17 (12 allocated + 5 Available)
Max Instances of Resource Type C = 16 (14 allocated + 2 Available)
Max Instances of Resource Type D = 12 (12 allocated + 0 Available)
Given Matrices
Allocation Matrix Max Matrix Available Matrix
(No of the allocated By a Max resources that may Not Allocated
process) be used by a process Resources
A B C D A B C D A B C D
P0 0 1 1 0 0 2 1 0 1 5 2 0
P1 1 2 3 1 1 6 5 2
P2 1 3 6 5 2 3 6 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 5
Total 2 12 14 12

[Link] the need matrix (max-allocation)

Need(i) = Max(i) – Allocated(i) Need Matrix = Max matrix –
Allocation Matrix
(i=0) (0,2,1,0) - (0,1,1,0) = (0,1,0,0)
(i=1) (1,6,5,2) - (1,2,3,1) = (0,4,2,1) A B C D
(i=2) (2,3,6,6) - (1,3,6,5) = (1,0,0,1) P0 0 1 0 0
(i=3) (0,6,5,2) - (0,6,3,2) = (0,0,2,0) P1 0 4 2 1

(i=4) (0,6,5,6) - (0,0,1,4) = (0,6,4,2) P2 1 0 0 1

Ex. Process P1 has max of (1,6,5,2) and allocated by (1,2,3,1) P3 0 0 2 0

Need(p1) = max(p1)- allocated(p1) = (1,6,5,2) – ( 1,2,3,1) = (0,4,2,1) P4 0 6 4 2

SVCP/TYCM Page 9
OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

[Link] the safety algorithm to test if the system is in a safe state or not?
a. We will first define work and finish:
Initially work = available = (1, 5, 2, 0) Finish matrix Work Factor
Finish = False for all processes P0 False 1 5 2 0
P1 False
P2 False
P3 False
P4 False

b. Check the needs of each process [ needs(pi) <= Max(pi)], if this condition is true:
 Execute the process , Change Finish[i] =True
 Release the allocated Resources by this process
 Change The Work Variable = Allocated (pi) + Work
need0 (0,1,0,0) <= work (1,5,2,0)
P0 will release the allocated
Work Factor
P0 will be Finish Matrix resources(0,1,1,0)
1 6 3 0
executed because P0 – 1 True Work = Work
need(P0) <= Work P1 False (1,5,2,0)+Allocated(P0)
P0 will be true P2 False (0,1,1,0) = 1,6,3,0
P3 False
P4 False

Need1 (0,4,2,1) <= work(1,6,3,0) Condition Is False P1 will Not be executed

Need2 (1,0,0,1) <= work(1,6,3,0) Condition Is False P2 will Not be executed

SVCP/TYCM Page 10
OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

Need3 (0,0,2,0) <= work(1,6,3,0) P3 will be executed

Finish matrix
P3 will be P3 will release the allocated
P0 - 1 True
executed because resources(0,6,3,2) Work Factor
P1 False
need(P3)<= Work Work = Work 1 12 6 2
P3 will be True P2 False (1,6,3,0)+Allocated(P3)
P3 - 2 True (0,6,3,2) = 1,12,6,2
P4 False

Need4 (0,6,4,2) <= work(1,12,6,2) P4 will be executed

P4 will be Finish matrix P4 will release the allocated
executed because resources (0,0,1,4) Work Factor
P0 - 1 True
need(P4) <=Work Work = Work 1 12 7 6
P1 False
P4 will be True P2 False (1,12,6,2) + Allocated(P4)
(0,0,1,4) = 1,12,7,6
P3 - 2 True
P4 - 3 True

Need1 (0,4,2,1) <= work(1,12,7,6) P1 will be executed

P1 will be P1 will release the allocated
Finish matrix
executed because resources (1,2,3,1) Work Factor
P0 – 1 True
need(P1)<=Work Work = Work 2 14 10 7
P1 True
P1 will be True (1,12,7,6) + Allocated(P1)
P2 False
(1,2,3,1) = 2,14,10,7
P3 – 2 True
P4 - 3 True

SVCP/TYCM Page 11
 OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

Need1 (1,0,0,1) <= work(2,14,20,7) P1 will be executed

P2 will be P2 will release the allocated
Finish matrix
executed because resources (1,3,6,5) Work Factor
P0 – 1 True
need(P2)<=Work Work = Work 3 17 16 12
P1 True
P2 will be True (2,14,10,7) + Allocated(P1)
P2 True
(1,3,6,5) = 3,17,16,12
P3 – 2 True
P4 - 3 True

The system is in safe state and the processes will be executed in the following order:
P0, P3, P4, P1, P2
Example 2
If the system is in safe state, can following requests be granted, why or why not? Please also run
the safety algorithm on each request as necessary.
a. P1 requests (2,1,1,0)
We cannot grant this request, because we do not have enough available instances
of resources A.
b. P1 requests (0,2,1,0)
There are enough available instances of the requested resources, do first let’s
Pretend to accommodate the request and see system looks like:
Allocation Max Available Need Matrix
A B C D A B C D A B C D A B C D
P0 0 1 1 0 0 2 1 0 1 3 1 0 P0 0 1 0 0
P1 1 4 4 1 1 6 5 2 P1 0 2 1 1
P2 1 3 6 5 2 3 6 6 P2 1 0 0 1
P3 0 6 3 2 0 6 5 2 P3 0 0 2 0
P4 0 0 1 4 0 6 5 6 P4 0 6 4 2

SVCP/TYCM Page 12
OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

Now we need to run the safety algorithm:

Initially Let’s first look at P0. Need0 (0,1,0,0) is less
than work, so we change the work vector and
Work Factor Finfish matrix
finish matrix as follows:
1 P0 False
3 P1 False Work Factor Finfish matrix
1 P0 True
1 P2 False
4 P1 False
0 P3 False
P4 False 2 P2 False
0 P3 False
P4 False

Need1 (0,2,1,1) is not less than work, so we need to move on P2.

Need1 (1,0,0,1) is not less than work, so we need to move on P3.
Need3 (0,0,2,0) is less than or equal to work Let’s first look at Need4 (0,6,4,2).This is less
Let’s update work and finish: than work, so we can update work and
Finish:
Work Factor Finfish matrix
Work Factor Finfish matrix
1 P0 True
1 P0 True
10 P1 False
10 P1 False
5 P2 False
6 P2 False
2 P3 True
6 P3 True
P4 False
P4 True

SVCP/TYCM Page 13
OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

We can now go back to P1. Need1 (0,2,1,1) is less than work, so work and finish can be updated:

Work Factor Finfish matrix

1 P0 True
14 P1 True
10 P2 False
7 P3 True
P4 True

Finally, Need2 (1,0,0,1) is less than work, so we can also accommodate this. Thus, the system is
in a safe state when the processes are run in the following order:
P0,P3,P4,P1,P2. We therefore can grant the resource request.
Example 3
Assume that there are three resources, A,B, and C. There are 4 processes P0 to P3. At T0
we have the following snapshot of the system:
Allocation Max Available [Link] the need matrix
A B C A B C A B C Need
P0 1 0 1 2 1 1 2 1 1 A B C
P1 2 1 2 5 4 4 P0 1 1 0
P2 3 0 0 3 1 1 P1 3 3 2
P3 1 0 1 1 1 1 P2 0 1 1
P3 0 1 0
[Link] the system in a safe state? Why or why not?
In order to check this, we should run the safety algorithm. Let’s create the work vector and finish
matrix:
Work vector Finish Need0 (1,1,0) is less than work, so let’s go
ahead and update work and finish
matrix
Work vector Finish
2 P0 False matrix
3 P0 True
1 P1 False
1 P1 False
1 P2 False
2 P2 False
P3 False P3 False

SVCP/TYCM Page 14
OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

Need1 (3,3,2) is not less than work, so we have to move on to P2.

Need2 (0,1,1) is less than work, let’s update Need3 (0,1,0) is less than work, we can update
work and finish: work and finish:
Work vector Finish matrix Work vector Finish matrix
6 P0 True 7 P0 True
1 P1 False 1 P1 False
2 P2 True 3 P2 True
P3 False P3 True

We now need to go back to P1. Need1 (3,3,2) is not less than work, so we cannot continue. Thus,
the system is not in a safe state.
8.0 Skills Developed

 We studied Arrays, Functions, & form elements and why they are used.
 We also learnt about the different events and there use in form elements as attribute.

9.0 Applications of this Micro-Project

The application of this micro project is that we can utilize the code to generate dynamically
changing option list.

SVCP/TYCM Page 15