1
$\begingroup$

I came across following problem:

Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P (wait) and V (signal) functions. Consider the following C implementation of a barrier with line numbers shown on left.

void barrier (void)  
{
    P(S);
    process_arrived++;
    V(S);
    while (process_arrived !=3);
    P(S);
    process_left++;
    if (process_left==3) 
    {
        process_arrived = 0;
        process_left = 0;
    }
    V(S);
}

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally. The above implementation of barrier is incorrect, because ... ?

I know that after execution of below steps, this may lead to halting of all processes:

| #process | process_arrived | process_left |
|----------|-----------------|--------------|
| 1        | 1 blocked       |              |
| 2        | 2 blocked       |              |
| 3        | 3 blocked       |              |
| 1        |                 | 1            |
| 2        |                 | 2            |
| 3        |                 | 3            |
| 1        | 4               |              | <-- (1)
| 3        | 0               | 0            |
| 2        | 1 blocked       |              |
| 3        | 2 blocked       |              |

Above each line shows which process executes and what changes it does to two variables.

After last step all processes have started their 2nd attempt to synchronize and all have incremented process_arrived twice. However, 2nd increment of process_arrived by p1 is done (<-- (1)) before process_arrived is reset to 0. Thus even after all processes incremented process_arrived twice, its value is 2 and all processes keep busy waiting for it to become 3.

My doubt is does this state certify to called as deadlock as I dont see necessary requirements of deadlock hold here, namely circular wait and hold and wait. I guess process_arrived is a single resource here. How can a circular wait, hold and wait and hence deadlock occur with single resource? Or is there some other, more generalized definition of deadlock which I am missing? Quick google defines deadlock as "a situation, typically one involving opposing parties, in which no progress can be made". Does that mean we can ignore necessary conditions of deadlock, in the context of computer science?

This is rather simple or subtle doubt, but I want precise understanding about whats called deadlock.

PS: I believe mutual exclusion requirement of deadlock is satisfied here as all updates to variables are protected by semaphore S

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.