MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION,

MUMBAI
A Project Report
On:

‘ Operating System '

DIPLOMA
IN
COMPUTER ENGINEERING
Submitted by :
Omkar Laxman Khandekar
Tejas Pandurang Savardekar
Pratik Shantinath Kapase
Sanket Balkrishna Karade

Department of computer Engineering

Sant Gajanan Maharaj Rural Polytechnic, Mahagaon.

Semester – 5th
Academic year 2024-25

Under the guidance of

Mr. R. B. More
 (MSBTE)
SANT GAJANAN MAHARAJ RURAL HOSPITAL AND RESEARCH CENTRE,
MAHAGAON
“SANT GAJANAN MAHARAJ RURAL POLYTECHNIC”
A/P MAHAGAON, SITE – CHINCHEWADI, TAL – GADHINGLAJ, DIST – KOLHAPUR

CERTIFICATE
This is to certify that the following students of first year of Diploma in Computer
Engineering of Institute ‘SANT GAJANAN MAHARAJ RURAL POLYTECHNIC
MAHAGAON – 416503 (CODE – 0965)’ has completed Micro-project on ‘ Banker’s & Safety
Algorithm for Deadlock Detection and Avoidance ' in Operating System ( Subject code –
22516 ) for academic year 2024-25 as prescribed in the curriculum.

ROLL NO. ENROLLMENT NO. NAME OF STUDENT SIGNATURE

52 2209650067 Omkar Laxman Khandekar

39 2209650052 Tejas Pandurang Savardekar

45 2209650058 Pratik Shantinath Kapase

49 2209650064 Sanket Balkrishna Karade

Date of submission: / /2024

Mr. R. B. More Mr. G. K. Biranagaddi Prof. R. S. Patil

(Project Guide) (Head of 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 micro-project

2 Choosing the topic

for micro-project
 3 Searching the
information on the topic

4 Working on the examples of

the given topic

5 Cross checking and

correcting the
examples
6 Preparing the report

7 Making changes and

corrections in the report

8 Final submission

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 Omkar Laxman Khandekar 52
2 Tejas Pandurang Savardekar 39
3 Pratik Shantinath Kapase 45
4 Sanket Balkrishna Karade 49
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
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.
 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

1. Create 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
 OSY-(22516) Banker’s & Safety algorithm for deadlock detection and avoidance

2. Use 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

P0 will be Work Factor
Finish Matrix resources(0,1,1,0)
executed because 1 6 3 0
P0 – 1 True Work = Work (1,5,2,0)+Allocated(P0)
need(P0) <=
P1 False (0,1,1,0) = 1,6,3,0
Work P0 will be
P2 False
true
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
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

P3 will be Finish matrix

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

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
 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
 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 P2 False 1 P0 True

0 P3 False 4 P1 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
1 P0 True Work Factor Finfish matrix

10 P1 False 1 P0 True

5 P2 False 10 P1 False

2 P3 True 6 P2 False

P4 False 6 P3 True
P4 True
 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
2 P0 False
Work vector Finish
1 P1 False matrix
3 P0 True
1 P2 False
1 P1 False
P3 False
2 P2 False
P3 False
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.