Exercises 1-6

Answers:

1.A deadlock is a problem occuring when the resources needed by some jobs to finish execution are held by other jobs, which, in turn, are waitingfor other resources to become available...Or a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.Also called deadly embrace. A Starvation is the result of conservative allocation of resources in which a single job is prevented from execution because it's kept waiting for resources that never become available. 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. While 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 succeeds
break; // leave the loop
else {
s.release(0,1); // release what is held
sleep( 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 occur when the bridge is destroyed.
b. When there are no traffic lights.
c. To prevent deadlock make all the road to be one-way direction.

6. Figure 5.17
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.