EXERCISE (1-2)

1.
Deadlock a problem occuring when the resources needed by some jobs to finish execution are held by other jobs , which, in turn, are waiting for other resources to become available. Also called deadly embrace. Starvation 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. Race a synchronization problem between two processes vying for the same resource.

2.
*Deadlock example - a traffic cituation of vehicles in a highway.

*Starvation example - a cituation in a dining table with one food served to 5 people using 5 utensils only but 2 utensils each. This results to the starvation of some people.

*Race example - a cituation that has a competition between 2 persons for only one source of food.

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.