Previous | Next --- Slide 21 of 35
Back to Lecture Thumbnails

bounded queue is lock free because producer and consumers can work simultaneously without imposing any locks (since producer only modifies tail, consumer only modifies head)


More specifically, we know that no number of push/pop operations would change the condition in the if statement of the other function. Cases like that are where it is easy to get into trouble with race conditions; you check a condition and it changes before you act upon it.


I'm really interested in what would happen here (or in the next several examples) under a relaxed sequential model.

We've seen examples where code behaves differently under different memory consistency model, but it's good to see it in a practical data structure.


If the producer and consumer work simultaneously, then couldn't it be possible that pushes and pops fail? For example, the queue is full as an element is pushed on, but has elements popped off and has free space at the same time, falsely reporting that it is still full.

Why is it ok to ignore this case (as we did in lecture)?


@maxdecmeridius, if we're thinking about parallel code, it's often useful to relax our concept of "time". In the example you've given the queue was full, then a pop instruction ran, then a push instruction spuriously failed - clearly a bug in the data structure! However, we can look at this a different way: both of these took place at essentially the same point in time (otherwise we would've seen the queue as no longer full). As such, we can slightly rearrange the ordering that we consider the requests arrived in: the queue was full, a push instruction ran and failed, and a pop instruction ran successfully.


I think the tail can be seen as a implicit lock in this data structure.

The tail is updated only when the the data is pushed into queue. Before then no one can access the region between tail to new_tail.


In the push function, q->tail is added after[q->tail] is written. If we reverse the order, and let them be "int prev_index = q->tail; q->tail = MOD_N(q->tail + 1);[prev_index] = value;", then there will be a problem: the pop function may read the from the address where new data hasn't been written (this instruction hasn't been executed: "[prev_index] = value;").


One small detail about the queue is that the capacity is only N-1 though the array size is N.