В поисках безблокировочной RT-безопасной структуры с одним считывателем и одним устройством записи - PullRequest
6 голосов
/ 25 февраля 2010

Я ищу конструкцию без блокировки , соответствующую следующим требованиям:

  • a один писатель пишет в структуру, а один читатель читает из этой структуры (эта структура уже существует и безопасна для одновременного чтения / записи)
  • но в какой-то момент структура должна быть изменена автором , который затем инициализирует, переключает и записывает в новую структуру (того же типа, но с новым содержимым)
  • и в следующий раз, когда читатель читает, он переключает на эту новую структуру (если автор многократно переключается на новую структуру без блокировки, читатель отбрасывает эти структуры, игнорируя их данные).
  • Структуры должны использоваться повторно, т. Е. Во время операции записи / чтения / переключения не допускается выделение / освобождение памяти в куче для целей RT .

В настоящее время я реализовал кольцевой буфер, содержащий несколько экземпляров этих структур; но эта реализация страдает от того факта, что когда писатель использовал все структуры, присутствующие в кольцевом буфере, больше нет места для изменения структуры ... Но остальная часть кольцевого буфера содержит некоторые данные, которые не нужно читать читателем, но не может быть повторно использован писателем. Как следствие, кольцевой буфер не подходит для этой цели.

Любая идея (имя или псевдо-реализация) дизайна без блокировки? Спасибо, что рассмотрели эту проблему.

Ответы [ 2 ]

0 голосов
/ 25 февраля 2010

Вот один. Ключи состоят в том, что есть три буфера, и читатель резервирует буфер, из которого это читает. Автор пишет в один из двух других буферов. Риск столкновения минимален. Плюс это расширяется. Просто сделайте ваш массив массивов на один элемент длиннее, чем количество читателей плюс количество писателей.

class RingBuffer
{
  RingBuffer():lastFullWrite(0)
  { 
    //Initialize the elements of dataBeingRead to false
    for(unsigned int i=0; i<DATA_COUNT; i++)
    {
      dataBeingRead[i] = false;
    } 
  }

  Data read()
  {
    // You may want to check to make sure write has been called once here
    // to prevent read from grabbing junk data. Else, initialize the elements
    // of dataArray to something valid.
    unsigned int indexToRead = lastFullWriteIndex;
    Data dataCopy;
    dataBeingRead[indexToRead] = true;
    dataCopy = dataArray[indexToRead];
    dataBeingRead[indexToRead] = false;
    return dataCopy;
  }

  void write( const Data& dataArg )
  {
    unsigned int writeIndex(0);

    //Search for an unused piece of data.
    // It's O(n), but plenty fast enough for small arrays.
    while( true == dataBeingRead[writeIndex] && writeIndex < DATA_COUNT )
    {
      writeIndex++;
    }  

    dataArray[writeIndex] = dataArg;

    lastFullWrite = &dataArray[writeIndex];
  }

private:
  static const unsigned int DATA_COUNT;
  unsigned int lastFullWrite;
  Data dataArray[DATA_COUNT];
  bool dataBeingRead[DATA_COUNT];
};

Примечание. Как написано здесь, есть две копии для чтения ваших данных. Если вы передадите свои данные из функции чтения через ссылочный аргумент, вы можете сократить их до одной копии.

0 голосов
/ 25 февраля 2010

Вы на правильном пути.

Блокировка свободного обмена фиксированными сообщениями между потоками / процессами / процессорами alt text

фиксированный размер кольцевые буферы могут использоваться для беспрепятственной связи между потоками, процессами или процессорами, если есть один производитель и один потребитель.Некоторые проверки для выполнения:

переменная head записывается только производителем (как атомарное действие после записи)

tail переменная записывается толькопотребитель (как элементарное действие после чтения)

Подводный камень: введение переменной размера или флага заполнения / пустого буфера;они, как правило, пишутся как производителем, так и потребителем, и, следовательно, могут вызвать проблемы.

Я обычно использую кольцевые буферы для этой цели.Самый важный урок, который я усвоил, состоит в том, что кольцевой буфер не может содержать больше элементов.Таким образом, переменные head и tail записываются производителем и потребителем.

Расширение для блоков большого / переменного размера Чтобы использовать буферы в среде реального времени, вы можете использовать пулы памяти (часто доступные в оптимизированном виде в операционных системах реального времени) или отделить выделение отиспользование.Последнее, как мне кажется, подходит к этому вопросу.

extended queue

Если вам нужно обмениваться большими блоками, я предлагаю использовать пул с буферными блоками и общатьсяуказатели на буферы, использующие очередь.Так что используйте третью очередь с указателями буфера.Таким образом, распределение может быть выполнено в приложении (в фоновом режиме), и ваша часть в реальном времени имеет доступ к переменному объему памяти.

Приложение

while (blockQueue.full != true)
{
    buf = allocate block of memory from heap or buffer pool
    msg = { .... , buf };
    blockQueue.Put(msg)
}

Producer:
   pBuf = blockQueue.Get()
   pQueue.Put()

Consumer
   if (pQueue.Empty == false)
   {
      msg=pQueue.Get()
      // use info in msg, with buf pointer
      // optionally indicate that buf is no longer used
   }
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...