title: Single producer, single consumer data structure with double buffer in C++
body: <p>I have an application at $work where I have to move between two real-time threads that are scheduled at different frequencies. (The actual scheduling is beyond my control.) The application is hard real-time-ish (one of the threads has to drive a hardware interface), so the data transfer between the threads should be lock-free and wait-free to the extent possible.</p>
  
  <p>It is important to note that only one block of data needs to be transferred: because the two threads run at different rates, there will be times when two iterations of the faster thread are completed between two wakeups of the slower thread; in this case it is OK to overwrite the data in the write buffer so that the slower thread gets only the latest data.</p>
  
  <p>In other words, instead of a queue a double buffered solution suffices. The two buffers are allocated during initialization, and the reader and write threads can call methods of the class to get pointers to one of these buffers.</p>
  
  <p>C++ code:</p>
  
  <pre><code>#include &lt;mutex&gt;
  
  template &lt;typename T&gt;
  class ProducerConsumerDoubleBuffer {
  public:
      ProducerConsumerDoubleBuffer() {
          m_write_busy = false;
          m_read_idx = m_write_idx = 0;
      }
  
      ~ProducerConsumerDoubleBuffer() { }
  
      // The writer thread using this class must call
      // start_writing() at the start of its iteration
      // before doing anything else to get the pointer
      // to the current write buffer.
      T * start_writing(void) {
          std::lock_guard&lt;std::mutex&gt; lock(m_mutex);
  
          m_write_busy = true;
          m_write_idx = 1 - m_read_idx;
  
          return &amp;m_buf[m_write_idx];
      }
      // The writer thread must call end_writing()
      // as the last thing it does
      // to release the write busy flag.
      void end_writing(void) {
          std::lock_guard&lt;std::mutex&gt; lock(m_mutex);
  
          m_write_busy = false;
      }
  
      // The reader thread must call start_reading()
      // at the start of its iteration to get the pointer
      // to the current read buffer.
      // If the write thread is not active at this time,
      // the read buffer pointer will be set to the 
      // (previous) write buffer - so the reader gets the latest data.
      // If the write buffer is busy, the read pointer is not changed.
      // In this case the read buffer may contain stale data,
      // it is up to the user to deal with this case.
      T * start_reading(void) {
          std::lock_guard&lt;std::mutex&gt; lock(m_mutex);
  
          if (!m_write_busy) {
              m_read_idx = m_write_idx;
          }
  
          return &amp;m_buf[m_read_idx];
      }
      // The reader thread must call end_reading()
      // at the end of its iteration.
      void end_reading(void) {
          std::lock_guard&lt;std::mutex&gt; lock(m_mutex);
  
          m_read_idx = m_write_idx;
      }
  
  private:
      T m_buf[2];
      bool m_write_busy;
      unsigned int m_read_idx, m_write_idx;
      std::mutex m_mutex;
  };
  </code></pre>
  
  <p>To avoid stale data in the reader thread the payload structure is versioned.
  To facilitate bidirectional data transfer between the threads, two instances of the above monstrosity are used, in opposite directions.</p>
  
  <p>Questions:</p>
  
  <ul>
  <li>Is this scheme threadsafe? If it's broken, where?</li>
  <li>Can it be done without the mutex? Perhaps with just memory barriers or CAS instructions?</li>
  <li>Can it be made better?</li>
  </ul>