Previous | Next --- Slide 24 of 30
Back to Lecture Thumbnails
marjorie

I spent some time this weekend trying to implement a thread pool, before I realized that the helper code provides much of what's needed. :) In the process I learned a bit about pthread condition variables, which seem so handy I was surprised they weren't taught in 213. The pthread_cond functions allow you to have a thread (or threads) block until a specific condition is met. Here is a very brief overview:

http://www.cs.nmsu.edu/~jcook/Tools/pthreads/pthread_cond.html

kayvonf

But certainly it was an excellent exercise nonetheless.

Kapteyn

I think it might be more efficient if we had:

void Barrier(Barrier_t* b, int p) {  
  lock(b->lock);  
  if (b->arrive_counter == 0) {  
     if (b->leave_counter == P) {  
        b->flag = 0;  
     } else {  
        while (b->flag != 0); // instead of while (b->leave_counter != P)  
     }  
   }  

... // rest is same

}

So that we spin on the flag instead of the leave_counter. This is better because the leave_counter gets updated by each thread as they leave the barrier and you don't want to be spinning on something that gets updated frequently because you incur a cache miss every time another thread leaves the barrier, causing a lot of interconnect traffic. Spinning on the flag is better because you'll only incur a cache miss once right before you exit the spin loop.

MediumPepsi

@Kapteyn I think the reason to spin on the leave_counter is to make sure that all threads leave the first barrier before the fastest thread clears the flag in the second barrier. I don't think your version guarantees this.

Kapteyn

@MediumPepsi I believe it does, each thread will first check if leave_counter == P before setting flag to 0. So if leave_counter != P, then it will spin on flag, waiting for some other thread to set the flag to 0, which will only happen when leave_counter == P.

MediumPepsi

@Kapteyn You are right, all other threads will be blocked until one thread is aware that b->leave_counter==P and set flag = zero.

apoms

Instead of having two separate counters for both arriving and leaving, we can combine them into a single counter:

struct Barrier_t {
  LOCK lock;
  int counter;
  int flag;
};

void Barrier(Barrier_t* b, int p) {
  while (b->counter > 0 && flag == 1);
  lock(b->lock);
  if (b->counter == 0) {
    b->flag = 0;
  }
  int num_arrived = ++(b->counter);
  unlock(b->lock);

  if (num_arrived == p) {
    b->flag = 1;
  } else {
    while (b->flag == 0);
  }
  --(b->counter);
}

Please go over it yourself to verify that it works as I am not 100% sure.