Operating Systems

 

Homework #5

Due: 2004/5/26

 

1.      Is it possible to have a deadlock involving only one process? Explain your answer.

 

2.      Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock-free.

 

3.      Consider the following snapshot of a system:

 

 

 

Allocation

 

Max

 

Available

 

 

A

B

C

D

 

A

B

C

D

 

A

B

C

D

P0

 

0

0

1

2

 

0

0

1

2

 

1

5

2

0

P1

 

1

0

0

0

 

1

7

5

0

 

 

 

 

 

P2

 

1

3

5

4

 

2

3

5

6

 

 

 

 

 

P3

 

0

6

3

2

 

0

6

5

2

 

 

 

 

 

P4

 

0

0

1

4

 

0

6

5

6

 

 

 

 

 

 

Answer the following questions using the bankerfs algorithm:

 

a.       What is the content of the matrix Need?

b.      Is the system in a safe state?

c.       If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately?

 

 

4.      Consider the following resource-allocation policy. Requests and releases for resources are allowed at any time. If a request for resources cannot be satisfied because the resources are not available, then we check any processes that are blocked, waiting for resources. If they have the desired resources, then these resources are taken away from them and are given to the requesting process. The vector of resources for which the waiting process is waiting is increased to include the resources that were taken away.

 

For example, consider a system with three resource types and the vector Available initialized to (4,2,2). If process P0 asks for (2,2,1), it gets them. If P1 asks for (1,0,1), it gets them. Then, if process P0 asks for (0,0,1), it is blocked (resource not available). If P2 now asks for (2,0,0), it gets the available one (1,0,0) and one that was allocated to P0 (since P0 is blocked). P0fs Allocation vector goes down to (1,2,1), and its Need vector goes up to (1,0,1).

 

a.       Can deadlock occur? If so, give an example. If not, which necessary condition cannot occur?

b.      Can indefinite blocking occur?