Some thoughts about realtime buffers

One of the problems I have faced many times before is how can I avoid doing much locking in real time software. This is not an easy task, and failure to do it properly can cause obscure problems. While reading recent Dr. Dobb's Journal issue I though I could write something about on subject, when to use locking and when it can be avoided (or minimized). I will assume that reader has at least some idea why in multi threaded application there should be some locking :)

One of the principles of parallel programming is that if some resource is shared, its access should be synchronized or algorithm should be defined in a way that there are no sharing problems (like one writing to data that is being read elsewhere and incorrect result is being retrieved).

One of the problems with synchronizing access is that it usually needs some locking to be made like in following pseudo code:

read()
  lock resource X
  tmp = resource X
  unlock resource X
  return tmp

write(new value)
  lock resource X
  resource X = new value
  unlock resource X

Otherwise fine algorithm, safe to use but in some cases excessive locking can be a problem. If there are lots of read's and write's per second locking is starting to take lots of time and in some applications this is not favorable situation. Problem comes from fact that locking usually needs context switches which is usually quite expensive. One of the possible solutions for multicore (or multiple) processors is to use spinlocks - try to acquire lock multiple times before switching thread to sleep.

One approach is to use algorithms that require lesser amount of locking. Perhaps most classical algorithm is ring buffer. Caveat here is that system must support atomic reading & writing of needed data types used to store buffer status - or otherwise some locking must be implemented in here too. Though the access time can be smaller as lock is needed only for small period of time.

Algorithm proposed in Dr. Dobb's article was called Spin Buffers. Basically it has multiple buffers (minimum of 3) set up as a ring. One buffer can only be owned by one party. Algorithm works like following. When writing new data: put data to current buffer and then if next buffer is free, switch to it for future writes, mark old buffer as free. When reading data, read current read buffer until it is empty, if next buffer is free, switch to it and mark old buffer as free. Reason why this algorithm needs at least 3 buffers is that it tries to always allow reading of written data, and if reader is not fast enough, writer can always write new data to current buffer (until its full). If reading and writing is not balanced it is possible that writer does not have possibility to switch to another buffer until next write is issued. Eg. issue many writes to fill all buffers so it will have to queue items to last buffer (before read buffer), then writer decides to go to sleep for some time. During this time write buffer pointer can't be incremented as it is reserved for writer only. Now reader wakes up and reads all data until there are no free buffers to be consumed, only buffer having data is write buffer and it cannot be accessed as it is reserved for writer. This situation can be unlocked only by waking up writer to switch to next free buffer.