Lecture 5: Deadlock Banker’s Algorithm
[Pages:62]Lecture 5: Deadlock ? Banker's Algorithm Memory management
Contents
Deadlock - Banker's Algorithm Memory management - history Segmentation Paging and implementation Page table Segmentation with paging Virtual memory concept Paging on demand Page replacement Algorithm LRU and it's approximation Process memory allocation, problem of thrashing
AE3B33OSS
Lecture 5 / Page 2
2012
Banker's Algorithm
Banker's behavior (example of one resource type with many instances):
Clients are asking for loans up-to an agreed limit The banker knows that not all clients need their limit simultaneously All clients must achieve their limits at some point of time but not
necessarily simultaneously After fulfilling their needs, the clients will pay-back their loans
Example:
The banker knows that all 4 clients need 22 units together, but he has only total 10 units
Client Used Max.
Adam
0 6
Eve
0 5
Joe
0 4
Mary
0 7
Available: 10
State (a)
Client Used Max.
Adam
1 6
Eve
1 5
Joe
2 4
Mary
4 7
Available: 2
State (b)
Client Used Max.
Adam
1 6
Eve
2 5
Joe
2 4
Mary
4 7
Available: 1
State (c)
AE3B33OSS
Lecture 5 / Page 3
2012
Banker's Algorithm (cont.)
Always keep so many resources that satisfy the needs of at least one client
Multiple instances.
Each process must a priori claim maximum use.
When a process requests a resource it may have to wait.
When a process gets all its resources it must return them in a finite amount of time.
AE3B33OSS
Lecture 5 / Page 4
2012
Data Structures for the Banker's Algorithm
Let n = number of processes, and m = number of resources types.
Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available.
Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj.
Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj.
Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task.
Need [i,j] = Max[i,j] ? Allocation [i,j].
AE3B33OSS
Lecture 5 / Page 5
2012
Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available Finish [i] = false for i = 1,2, ..., n.
2. Find and i such that both:
(a) Finish [i] = false (b) Needi Work If no such i exists, go to step 4.
3. Work = Work + Allocationi
Finish[i] = true go to step 2.
4. If Finish [i] == true for all i, then the system is in a safe state.
AE3B33OSS
Lecture 5 / Page 6
2012
Resource-Request Algorithm for Process Pi
Requesti = request vector for process Pi. Requesti [ j ] == k means that process Pi wants k instances of resource type Rj.
1. If Requesti Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim
2. If Requesti Available, go to step 3. Otherwise Pi must wait, since resources are not available.
3. Test to allocate requested resources to Pi by modifying the state as follows:
Available = Available - Requesti; Allocationi = Allocationi + Requesti; Needi = Needi ? Requesti; If safe the resources are allocated to Pi. If unsafe Pi must wait, and the old resource-allocation state is restored
AE3B33OSS
Lecture 5 / Page 7
2012
Example of Banker's Algorithm
5 processes P0 through P4; 3 resource types A (10 instances), B (5instances, and C (7 instances).
Snapshot at time T0:
Allocation Max
ABC ABC
P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2
7 5 3 3 2 2 9 0 2 2 2 2 4 3 3
Need A B C 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1
Total A B C 10 5 7 Allocated 7 2 5 Available 3 3 2
The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria
AE3B33OSS
Lecture 5 / Page 8
2012
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- the risks of easy money
- fema booklet english
- the banking regulation act 1949
- how daily simple interest works onemain financial
- simple steps to choosing the right financing
- funding organizations for emerging farmers
- lecture 5 deadlock banker s algorithm
- on the move
- smart credit strategies for small business owners web
Related searches
- 5 c s of customer service
- 5 p s of marketing definition
- 5 types of author s purpose
- weber s 5 characteristics of bureaucracy
- questions a banker should ask
- the 5 p s of marketing
- 5 p s marketing
- cramer s top 5 stock picks
- 5 p s marketing strategy
- s p 5 star stock list
- s p 5 star stocks
- personal banker value statement