1. Deadlock
-> deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does. “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.”
*Starvation - describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress. This happens when shared resources are made unavailable for long periods by "greedy" threads.
*Race is a synchronozation problem between two processes vying for the same resources.
2. *Deadlock example : Alphonse and Gaston are friends, and great believers in courtesy. A strict rule of courtesy is that when you bow to a friend, you must remain bowed until your friend has a chance to return the bow. Unfortunately, this rule does not account for the possibility that two friends might bow to each other at the same time.
*Example of starvation suppose an object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.
3. Necessary Conditions for a Deadlock:
1.) Mutual exclusion - Each resource is either currently allocated to exactly one process or it is available. (Two processes cannot simultaneously control the same resource or be in their critical section).
2.) Hold and Wait - processes currently holding resources can request new resources
3.) No preemption - Once a process holds a resource, it cannot be taken away by another process or the kernel.
4.) Circular wait - Each process is waiting to obtain a resource which is held by another 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.
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.
