Tuesday, January 15, 2008

Assingment 4

1. The major difference between deadlock, starvation and race is that in deadlock, the problem occurs when the jobs are processed.

Race conditions
: Threads can try to update the same data structure at the same time.
The result can be partly what one thread wrote and partly what the other thread wrote.

: To avoid updating the same data structure at the same time, threads lock a
data structure until they have finished making their modifications to it.

: In its effects, starvation is similar to deadlock in that some threads do not
make progress. But the causes of starvation are different from those of deadlock: The
threads could, in theory, execute, but they just don’t get time on a processor, perhaps
because they don’t have a high enough priority.

2. Example of Deadlock:
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.
Example of Starvation:
When one person borrowed a pen from his classmate and hisclassmate get his pen back.
Example of Race:
When two guys have the same girlfriend.
3. Four necessary condition needed for the deadlock from exercise #2:
if the product is only one.if the two person needed that one product urgently.if there's other alternative products available.if the two person are brand concious and the product happen to be what they like.
4. Design an algorithm for using it so that both deadlock and starvation are not possible.
public boolean tryAcquire( int n0, int n1, ... )
if ( for all i: ni ≤ availi )
{ // successful acquisition availi -= ni for all i; returntrue; // 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. Deadlock will not happen because there are two traffic lights that control the traffic.
a.But when some motorist don't follow the traffic lights, deadlock can occur because there's only one bridge to drive through.
b. Deadlock can be detected when there will be a huge bumper to bumper to the traffic and there will be accident that will happen.
c. The solution to prevent deadlock is that, the traffic lights should be accurate and motorist should follow it. In order to have a nice driving through the bridge.
6. Based on figure 5.17 answer the following question.
a. is this system deadlock?-this is an deadlock because P2 still requesting or waitng for R1 that has already been allocated.