Scribd
Upload
2 views14 pages

Banker’s Algorithm Safety Analysis

The document presents a series of problems related to the Banker’s algorithm for deadlock avoidance in systems with multiple processes and resource types. It details scenarios with varying tape and resource allocations, assessing system safety and the ability to grant resource requests. The analysis concludes with evaluations of safe states and potential deadlocks based on the given resource allocations and requests.

Uploaded by

colonvu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views14 pages

Banker’s Algorithm Safety Analysis

The document presents a series of problems related to the Banker’s algorithm for deadlock avoidance in systems with multiple processes and resource types. It details scenarios with varying tape and resource allocations, assessing system safety and the ability to grant resource requests. The analysis concludes with evaluations of safe states and potential deadlocks based on the given resource allocations and requests.

Uploaded by

colonvu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Chapter 4 problems

Problem 1.
 A system has 16 tapes, and 4 processes P , P , P , P with corresponding requests:
0 1 2 3
 P0 requests at most 10 tapes
 P1 requests at most 4 tapes
 P2 requests at most 9 tapes
 P3 requests at most 5 tapes
 At t , P has 5 tapes, P and P each has 2 tapes , P has 3 tapes
0 0 1 2 3
 4 tapes available
 Is the system safe with Banker’s algorithm?
Max Allocate Need Available
P0 10 5 5 4
P1 4 2 2
P2 9 2 7
P3 5 3 2
P4
Banker :
Step i Work Finish
Init 4 F,F,F,F
1 1 6 F,T,F,F
2 0 11 T,T,F,F
3 2 13 T,T,T,F
4 3 16 T,T,T,T
 SAFE
 At t , P has 7 tapes, P and P each has 2 tapes , P has 3 tapes
1 0 1 2 3
 2 tapes available
 Is the system safe with Banker’s algorithm?
Allocate Need Available
P0 7 3 2
P1 2 2
P2 2 7
P3 3 2
Banker
Step i Work Finish
Init F,F,F,F
1 1 4 F,T,F,F
2 0 11 T,T,F,F
3 2 13 T,T,T,F
4 3 16 T,T,T,T
 SAFE
 At t , P has 7 tapes, P has 3 tapes, P each has 2 tapes, P has 3 tapes
2 0 1 2 3
 1 tapes available
 Is the system safe with Banker’s algorithm?
Allocate Need Available
P0 7 3 1
P1 3 1
P2 2 7
P3 3 2
Banker
Step i Work Finish
Init 1 F,F,F,F
1 1 4 F,T,F,F
2 0 11 T,T,F,F
3 2 13 T,T,T,F
4 3 16 T,T,T,T
 SAFE

 At t , P has 7 tapes, P has 3 tapes, P each has 2 tapes, P has 4 tapes


3 0 1 2 3
 0 tape available
 Is the system safe with Banker’s algorithm?
Available = 0 -> unsafe
Problem 2
 5 processes: P - P 3 resource types
0 4;
 A (10 instances), B (5 instances), and C (7 instances)
 At time T :
0
Allocation Max Available
ABC ABC ABC
P0 110 753 332

P1 100 322

P2 202 902

P3 211 222

P4 102 433
Is the system safe with banker’s algorithm?
Allocate Need Available
P0 110 613 332
P1 100 222
P2 202 700
P3 211 011
P4 102 331
Banker
Step i Work Finish
Init 332 F,F,F,F,F
1 1 432 F,T,F,F,F
2 3 643 F,T,F,T,F
3 0 753 T,T,F,T,F
4 2 955 T,T,T,T,F
5 4 10 5 7 T,T,T,T,T
PROBLEM 3
 5 processes: P - P 3 resource types
0 4;
 A (10 instances), B (5 instances), and C (7 instances)
Allocation Max Available
ABC ABC ABC
P0 012 753 332

P1 200 322

P2 301 902

P3 211 222

P4 001 433

Allocation Need Available


ABC ABC ABC
P0 012 641 332

P1 200 122

P2 301 601
P3 211 011

P4 001 432

 If P1 requests for (1,0,2) => can it be granted

Allocation Need Available


ABC ABC ABC
P0 012 641 230

P1 302 020

P2 301 601

P3 211 011

P4 001 432
Step i Work Finish
Init 230 FFFFF
1 1 532 FTFFF
2 3 743 FTFTF
3 0 755 TTFTF
4 2 10 5 6 TTTTF
5 4 10 5 7 TTTTT
 Granted

 If P4 requests for (1,0,0) => can it be granted?

Allocation Need Available


ABC ABC ABC
P0 012 641 232

P1 200 122

P2 301 601

P3 211 011

P4 101 332

Step i Work Finish


Init 232 FFFFF
1 1 432 FTFFF
2 3 643 FTFTF
3 0 655 TTFTF
4 2 956 TTTTF
5 4 10 5 7 TTTTT
 Granted
 If P0 requests for (0, 2, 0) => can it be granted?

Allocation Need Available


ABC ABC ABC
P0 032 621 312

P1 200 122

P2 301 601

P3 211 011

P4 001 432

Step i Work Finish


Init 312 FFFFF
1 1 512 FTFFF
2 3 723 FTFTF
3 0 755 TTFTF
4 2 10 5 6 TTTTF
5 4 10 5 7 TTTTT
 Granted

 If P1 requests for (1,0,2) => can it be granted


 If P1’s request is granted, can the next request for (1,0,0) by P be granted?
4

Allocation Need Available


ABC ABC ABC
P0 012 641 130

P1 302 020

P2 301 601

P3 211 011

P4 101 332

Step i Work Finish


Init 130 FFFFF
1 1 432 FTFFF
2 3 643 FTFTF
3 0 655 TTFTF
4 2 956 TTTTF
5 4 10 5 7 TTTTT
 Granted

 If P1 requests for (1,0,2) => can it be granted


 If P1’s request is granted, can the request for (0,2,0) by P0 be granted?

Allocation Need Available


ABC ABC ABC
P0 012 641 210

P1 302 020

P2 301 601

P3 211 011

P4 021 412

No i satisfies Need[i] < Available => unsafe


 Not granted
PROBLEM 4

 5 processes: P - P 3 resource types


0 4;
 A (10 instances), B (5 instances), and C (7 instances)
 At snapshot at time T0
Allocation Request Available
ABC ABC ABC
P0 010 100 431
P1 200 202
P2 203 000
P3 211 100
P4 002 002
 Is there a deadlock at T ?
0
Step i Work Finish
Init 431 FFFFF
1 0 441 TFFFF
2 1 641 TTFFF
3 2 844 TTTFF
4 3 10 5 5 TTTTF
5 4 10 5 7 TTTTT

 No Deadlock
 If P2 request (0, 0, 1), is there a deadlock?

Allocation Request Available


ABC ABC ABC
P0 010 100 431
P1 200 202
P2 203 001
P3 211 100
P4 002 002

Step i Work Finish


Init 431 FFFFF
1 0 441 TFFFF
2 1 641 TTFFF
3 2 844 TTTFF
4 3 10 5 5 TTTTF
5 4 10 5 7 TTTTT

You might also like