Site hosted by Angelfire.com: Build your free website today!

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

˛ See the rmi note on the newsgroup or the poker README

˛ Lab 3 is due in 2 weeks

˛ HW 4 is out

˛ Out of town April 7 - 13. Lectures will be handled by Vijay and Huan; my

email reading/answering will be sporadic.

CMPSCI 377: Operating Systems Lecture 14, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Today

˛ More on Resource Reservations

˛ Deadlock Avoidance: Banker's algorithm

CMPSCI 377: Operating Systems Lecture 14, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservations and Deadlock Prevention

recall...

˛ Threads provide advance information about the maximum resources they

may need during execution

˛ De¯ne a sequence of threads ft1; : : : ; tng as safe if for each ti, the

resources that ti can still request can be satis¯ed by the currently

available resources plus the resources held by all tj; j < i.

˛ A safe state is a state in which there is a safe sequence for the threads.

˛ An unsafe state is not equivalent to deadlock, it just may lead to

deadlock, since some threads might not actually use the maximum

resources they have declared.

CMPSCI 377: Operating Systems Lecture 14, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example

Consider the following reservation:

Disk Reservation

t1 6

t2 9

total available 11

Assume that t1 has been allocated 3 disks; t2 has been allocated 4 disks.

Is this a safe state?

CMPSCI 377: Operating Systems Lecture 14, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example

Consider the following reservation:

Disk Reservation

t1 6

t2 9

total available 11

Assume that t1 has been allocated 3 disks; t2 has been allocated 4 disks.

Is this a safe state? YES

Is it safe to allocate a disk to t1?

CMPSCI 377: Operating Systems Lecture 14, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example

Consider the following reservation:

Disk Reservation

t1 6

t2 9

total available 11

Assume that t1 has been allocated 3 disks; t2 has been allocated 4 disks.

Is this a safe state? YES

Is it safe to allocate a disk to t1? YES

Is it safe to allocate a disk to t2?

CMPSCI 377: Operating Systems Lecture 14, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example

Consider the following reservation:

Disk Reservation

t1 6

t2 9

total available 11

Assume that t1 has been allocated 3 disks; t2 has been allocated 4 disks.

Is this a safe state? YES

Is it safe to allocate a disk to t1? YES

Is it safe to allocate a disk to t2? YES

Is it safe to allocate two disks to t1?

CMPSCI 377: Operating Systems Lecture 14, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example

Consider the following reservation:

Disk Reservation

t1 6

t2 9

total available 11

Assume that t1 has been allocated 3 disks; t2 has been allocated 4 disks.

Is this a safe state? YES

Is it safe to allocate a disk to t1? YES

Is it safe to allocate a disk to t2? YES

Is it safe to allocate two disks to t1? YES

Is it safe to allocate two disks to t2?

CMPSCI 377: Operating Systems Lecture 14, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example

Consider the following reservation:

Disk Reservation

t1 6

t2 9

total available 11

Assume that t1 has been allocated 3 disks; t2 has been allocated 4 disks.

Is this a safe state? YES

Is it safe to allocate a disk to t1? YES

Is it safe to allocate a disk to t2? YES

Is it safe to allocate two disks to t1? YES

Is it safe to allocate two disks to t2? NO

CMPSCI 377: Operating Systems Lecture 14, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example II

Consider the following reservation:

Disk Reservation Printer Reservation

t1 6 10

t2 9 4

total available 10 12

Assume the following allocation:

Disk Alloc Printer Alloc

t1 2 8

t2 4 2

Is this a safe state?

CMPSCI 377: Operating Systems Lecture 14, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example II

Consider the following reservation:

Disk Reservation Printer Reservation

t1 6 10

t2 9 4

total available 10 12

Assume the following allocation:

Disk Alloc Printer Alloc

t1 2 8

t2 4 2

Is this a safe state? YES

Is it safe to allocate a disk to t1?

CMPSCI 377: Operating Systems Lecture 14, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example II

Consider the following reservation:

Disk Reservation Printer Reservation

t1 6 10

t2 9 4

total available 10 12

Assume the following allocation:

Disk Alloc Printer Alloc

t1 2 8

t2 4 2

Is this a safe state? YES

Is it safe to allocate a disk to t1? YES

Is it safe to allocate a printer to t2?

CMPSCI 377: Operating Systems Lecture 14, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example II

Consider the following reservation:

Disk Reservation Printer Reservation

t1 6 10

t2 9 4

total available 10 12

Assume the following allocation:

Disk Alloc Printer Alloc

t1 2 8

t2 4 2

Is it safe to allocate a disk to t1? YES

Is it safe to allocate a printer to t2? NO

If t1 deallocated 1 disk, is it safe to allocate a printer to t2?

CMPSCI 377: Operating Systems Lecture 14, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Resource Reservation Example II

If t1 deallocated 1 disk, is it safe to allocate a printer to t2?

Yes!

˛ Only some ordering must exist in order to be a safe state.

˛ Depending upon the reservations and the current allocation, we might

have to consider diŽerent orderings.

CMPSCI 377: Operating Systems Lecture 14, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Formalizing Deadlock Avoidance

r3 r4

t1 t2 t3 t4

r1 r2

˛ Claim edges: an edge from a thread to a resource that may be requested

in the future

˛ Satisfying a request results in converting a claim edge to an allocation

edge and changing its direction.

CMPSCI 377: Operating Systems Lecture 14, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Formalizing Deadlock Avoidance (cont)

˛ A cycle in this extended resource allocation graph indicates an unsafe

state.

˛ If the allocation would result in an unsafe state, the allocation is denied

even if the resource is available.

{ The claim edge is converted to a request edge and the thread waits.

˛ This solution does not work for multiple instances of the same resource.

CMPSCI 377: Operating Systems Lecture 14, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

An Implementation: the Banker's Algorithm

˛ This algorithm handles multiple instances of the same resource.

˛ Force threads to provide advance information about what resources they

may need for the duration of the execution.

˛ The resources requested may not exceed the total available in the system.

˛ The algorithm allocates resources to a requesting thread if the allocation

leaves the system in a safe state.

˛ Otherwise, the thread must wait.

CMPSCI 377: Operating Systems Lecture 14, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Preventing Deadlock with Banker's Algorithm

class ResourceManager {

int n; // # threads

int m; // # resources

int avail[m], // # of available resources of each type

max[n,m], // # of each resource that each thread may want

alloc[n,m], // # of each resource that each thread is using

need[n,m], // # of resources that each thread might still request

CMPSCI 377: Operating Systems Lecture 14, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Banker's Algorithm: Resource Allocation

public void synchronized allocate (int request[m], int i) {

// request contains the resources being requested

// i is the thread making the request

if (request > need[i]) //vector comparison

error(); // Can't request more than you declared

else while (request[i] > avail)

wait(); // Insufficient resources available

// enough resources exist to satisfy the requests

// See if the request would lead to an unsafe state

avail = avail - request; // vector additions

alloc[i] = alloc[i] + request;

need[i] = need[i] - request;

while ( !safeState () ) {

// if this is an unsafe state, undo the allocation and wait

<undo the changes to avail, alloc[i], and need[i]>

wait ();

<redo the changes to avail, alloc[i], and need[i]>

} }

CMPSCI 377: Operating Systems Lecture 14, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Banker's Algorithm: Safety Check

private boolean safeState () {

boolean work[m] = avail[m]; // accommodate all resources

boolean finish[n] = false; // none finished yet

// find a process that can complete its work now

while (find i such that finish[i] == false

and need[i] <= work) { // vector operations

work = work + alloc[i]

finish[i] = true;

}

if (finish[i] == true for all i)

return true;

else

return false;

}

Worst case: requires O(mn2) operations to determine if the system is safe.

CMPSCI 377: Operating Systems Lecture 14, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example using Banker's Algorithm

System snapshot:

Max Allocation Available

A B C A B C A B C

P0 0 0 1 0 0 1

P1 1 7 5 1 0 0

P2 2 3 5 1 3 5

P3 0 6 5 0 6 3

total 2 9 9 1 5 2

CMPSCI 377: Operating Systems Lecture 14, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example (cont)

˛ How many resources are there of type (A,B,C)?

˛ What are the contents of the Need matrix?

A B C

P0

P1

P2

P3

˛ Is the system in a safe state? Why?

CMPSCI 377: Operating Systems Lecture 14, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example (cont)

˛ How many resources are there of type (A,B,C)? 3, 14, 11

˛ What are the contents of the Need matrix?

A B C

P0 0 0 0

P1 0 7 5

P2 1 0 0

P3 0 0 2

˛ Is the system in a safe state? Yes!

P0 is at max (and so can only deallocate 0,0,1)

P2 does not compete with any other processes for the remaining resources

P3 can allocated the remaining 2 Cs (as long as P1 does not get them)

P1 can allocate its desired resources once the other processes are done

CMPSCI 377: Operating Systems Lecture 14, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example (cont)

˛ If a request from process P1 arrives for additional resources of (0,5,2), can

the Banker's algorithm grant the request immediately?

˛ What would be the new system state after the allocation?

Max Allocation Need Available

A B C A B C A B C A B C

P0 0 0 1

P1 1 7 5

P2 2 3 5

P3 0 6 5

total

˛ What is a sequence of process execution that satis¯es the safety

constraint?

CMPSCI 377: Operating Systems Lecture 14, Page 24

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example (cont)

˛ Can the Banker's algorithm grant the request immediately? YES

{ (0,5,2) ˇ (1,5,2), the Available resources, and

{ (0,5,2) + (1,0,0) = (1,5,2) ˇ (1,7,5), the maximum number P1 can

request.

Max Allocation Need Available

A B C A B C A B C A B C

P0 0 0 1 0 0 1 0 0 0

P1 1 7 5 1 5 2 0 2 3

P2 2 3 5 1 3 5 1 0 0

P3 0 6 5 0 6 3 0 0 2

total 1 0 0

˛ What is a sequence of process execution that satis¯es the safety

constraint? P0, P2, P1, P3

CMPSCI 377: Operating Systems Lecture 14, Page 25

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

˛ Wednesday: File Systems Interface (Chapter 11)

˛ Friday: more on the File Systems and the Bankers Algorithm

CMPSCI 377: Operating Systems Lecture 14, Page 26