Assignment: Exercises

1.A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.

A Starvation is similar in effect to deadlock. Two or more programs become deadlocked together, when each of them wait for a resource occupied by another program in the same set. On the other hand, one or more programs are in starvation, when each of them is waiting for resources that are occupied by programs, that may or may not be in the same set that are starving. Moreover, in a deadlock, no program in the set changes its state.

A race is a synchronozation problem between two processes vying for the same resources.

2. Real-life example of deadlock is the traffic.Real-life example of starvation is in the staircase, when two people meet at the opposing side. The staircase can be accomodated by one person.Real-life example of Race is when two people arrived at the same time on the same door.

3. Four Necessary Conditions for Deadlock:The presence of deadlock in a systems is characterized by these four necessary conditions. The term necessary means that if there is deadlock then all four must be present.

a. Mutual exclusive resource access - A resource acquired is held exclusively, i.e., it is not shared by other processes.

b. No preemption - A process' resources cannot be taken away from it. Only the process can give up its resources.

c. Hold and Wait - A process has some resources and is blocked requesting more.

d. Circularity - This means that there is a circular chain of two or more processes in which the resources needed by one process are held by the next process.

4. Algorithm for prevention of deadlock and starvation:public boolean tryAcquire( int n0, int n1, ... ) { if ( for all i: ni ≤ availi ) { // successful acquisition availi -= ni for all i; return true; // indicate success } else return false; // indicate failure}init) Semaphore s = new Semaphore(1,1);Thread A Thread B-------- --------s.acquire(1,0); s.acquire(0,1);s.acquire(0,1); s.acquire(1,0);Thread B--------while(true) {s.acquire(0,1);if ( s.tryAcquire(1,0) ) // if second acquisition succeedsbreak; // leave the loopelse {s.release(0,1); // release what is heldsleep( SOME_AMOUNT); // pause a bit before trying again}}run action s.value--- ------ -------(1,1)A s.acquire(1,0) (0,1)B s.acquire(0,1) (0,0)A s.acquire(0,1) A blocks on secondB s.tryAcquire(1,0) => falseB s.release(0,1) (0,1)A s.acquire(0,1) (0,0) A succeeds on second

5.a. Deadlock can be occurred. When the bridge is destroyed.
b. When there are no traffic lights.
c. To prevent deadlock make all the road to be one-way.

6.a. This is not a deadlocked.
b. There is no blocked processes.
c. P2 can freely request on R1 and R2.
d. P1 can freely request on R1 and R2.
e. Both P1 and P2 have requested R2.1. P1 will wait after the request of P2.2. P2 will wait after the request of P1.