Previous | Next --- Slide 37 of 43
Back to Lecture Thumbnails

It may incur deadlock. For example, if there are two threads T0, T1. T0 reaches

while (b->flag == 0);

and begins busy waiting. At this time t1 reaches

b->flag = 1; // at last

Before t0 checks b->flag again, t1 immediately goes to

b->flag = 0; // at beginning

In t0's eye, t1 hasn't arrived, so it keeps waiting. In t1's eye, it's entered next barrier, and begins to wait for t0, who will never be able to come. Deadlock so happens.


If we don't reuse the same barrier struct b for the second barrier, is there still a deadlock issue?


@trappedin418 Yeah, that's correct. This was the first solution suggested in class, which is perfectly reasonable. One way to fix the problem without having a different barrier struct, as shown on the next slide, we can implement a mechanism that waits until everyone reaches the first barrier, and if you're the first thread to reach the second barrier, you have to wait until everyone has left the first barrier before you can change any variables.


We use flag rather than checking num_arrived here because using two different variables can make better use of cache. Some threads is working on num_arrived while the finished ones polling the value of flag.

Reference: link


In short, the problem is that when the last guy executes "b->flag = 1", while other guys are waiting for "flag", the last guy might go to the second BARRIER and set "flag" to 0 again.


Second Barrier may start before all threads exit the first Barrier due to the fact that they use the same b.