Перестановка буферов в потоках с одним писателем и несколькими считывателями

Какой API вы используете для блокировки чтения-записи? У вас есть временная блокировка, например pthread_rwlock_timedwrlock? Если да, я думаю, что это решение вашей проблемы, как в следующем коде:

void *buf[2];

void
writer ()
{
  int lock = 0, next = 1;

  write_lock (lock);
  while (1)
    {
      abs_time tm = now() + period;

      fill (buf [lock]);
      if (timed_write_lock (next, tm))
        {
          unlock (lock);
          lock = next;
          next = (next + 1) & 1;
        }
      wait_period (tm);
    }
}


void
reader ()
{
  int lock = 0;
  while (1)
    {
      reade_lock (lock);
      process (buf [lock]);
      unlock (lock);
      lock = (lock + 1) & 1;
    }
}

Что здесь происходит, так это то, что для записывающего устройства на самом деле не имеет значения, ждет ли он блокировки или следующего периода, если он обязательно проснется до того, как наступит следующий период. Абсолютный тайм-аут обеспечивает это.

Разве это не именно та проблема, которую должна решить тройная буферизация. Итак, у вас есть 3 буфера, назовем их write1, write2 и read. Поток записи чередуется между записью в записи 1 и запись 2, гарантируя, что они никогда не блокируются и что последний полный кадр всегда доступен. Затем в потоках чтения в какой-то подходящий момент (скажем, непосредственно перед или после чтения кадра) буфер чтения меняется местами с доступным буфером записи.

Хотя это гарантировало бы, что писатели никогда не блокируются (переключение буфера может быть выполнено очень быстро, просто перевернув два указателя, возможно, даже с помощью CAS atomic вместо блокировки), все еще остается проблема, связанная с тем, что читатели должны ждать, пока другие читатели закончат с буфером чтения перед переворачиванием. Я полагаю, что это можно было бы решить немного в стиле RCU с помощью пула буферов чтения, где можно перевернуть доступный.

• Использовать очередь (связанный список FIFO)
• Модуль записи в реальном времени всегда будет добавлять (ставить в очередь) в конец очереди
• Читатели всегда будут удалять (извлекать из очереди) из начала очереди
• Читатели будут блокироваться, если очередь пуста

изменить, чтобы избежать динамического размещения

Я бы, вероятно, использовал циклическую очередь... Я бы использовал встроенные атомарные операции __sync. http://gcc.gnu.org/onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins.html#Atomic-Builtins

• Круговая очередь (массив FIFO 2d)
• • ex: byte[][] Array = new byte[MAX_SIZE][BUFFER_SIZE];
• • Start and End index pointers
• Writer перезаписывает буфер в массиве[End][]
• • Writer can increment Start if it ends up looping all the way around
• Читатель получает буфер из Array[Start][]
• • Reader blocks if Start == End

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

Я бы посмотрел, нет ли вокруг какого-либо другого примитива синхронизации, который лучше подходит, но если дело дойдет до драки, я бы заблокировал и разблокировал блокировку записи, которую никто другой никогда не использует.

Затем читатели должны быть готовы время от времени пропускать что-то и должны уметь определять, когда они что-то пропустили. Я бы связал флаг достоверности и счетчик длинной последовательности с каждым буфером, а писатель сделал бы что-то вроде «очистить флаг достоверности, увеличить счетчик последовательности, синхронизировать, записать в буфер, увеличить счетчик последовательности, установить флаг достоверности, синхронизировать». Если читатель считывает количество последовательностей, синхронизируется, видит, что флаг достоверности верен, считывает данные, синхронизируется и повторно считывает тот же самый счетчик последовательностей, то, возможно, есть некоторая надежда, что он не получил искаженных данных.

Если вы собираетесь это сделать, я бы проверил это исчерпывающе. Мне это кажется правдоподобным, но может не работать с вашей конкретной реализацией всего, от компилятора до модели памяти.

Еще одна идея или способ проверить это — добавить контрольную сумму в свой буфер и записать ее в последнюю очередь.

См. также поиск по алгоритмам без блокировки, таким как http://www.rossbencina.com/code/lockfree

Чтобы пойти с этим, вы, вероятно, хотите, чтобы писатель подавал сигнал спящим читателям. Для этого вы можете использовать семафоры Posix - например. пусть читатель попросит писателя вызвать sem_post() для определенного семафора, когда он достигнет заданного порядкового номера или когда буфер станет действительным.

Другой вариант — придерживаться блокировки, но следить за тем, чтобы считыватели никогда не зависали слишком долго, удерживая блокировку. Читатели могут сократить время, затрачиваемое на удержание блокировки, и сделать его предсказуемым, ничего не делая, пока они удерживают эту блокировку, а копируя данные из буфера записи. Единственная проблема заключается в том, что чтение с низким приоритетом может быть прервано задачей с более высоким приоритетом на полпути записи, и лекарством от этого является http://en.wikipedia.org/wiki/Priority_ceiling_protocol.

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

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