Алгоритмы без использования блокировок: обнови, если сможешь, а я выключаюсь

  • Article

Клиент попросил помощи в решении проблемы синхронизации процессов:

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

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

Эта задача может быть разрешена при помощи шаблона «Издатель – подписчик». Когда издателю нужно обновить значения, он уведомляет подписчиков об этом, просто сообщая им местоположение обновленных данных.

Давайте предположим, что разделяемые данные являются коллекцией четырех целых чисел типа int.

struct SHAREDDATA {   int a, b, c, d; };

Также предположим, что существует некоторый лимит на частоту изменения этих данных. Это предположение, обычно, является допустимым, потому что в подобных ситуациях присутствует какое-либо внешнее ограничение, вроде: «Это значение изменяется в результате некоторого действия пользователя». (Даже если такой лимит отсутствует, большинство реализаций просто устанавливают какое-либо собственное значение в качестве лимита. К примеру, функции SLIST предполагают, что процессор не будет заблокирован более чем 65535 раз подряд). Давайте предположим, что в нашем случае значение не будет изменяться более чем 64 раза в расчете на одну операцию чтения.

#define SHAREDDATA_MAXCONCURRENT 64 SHAREDDATA g_rgsd[SHAREDDATA_MAXCONCURRENT]; UINT g_isd; // текущее местоположение корректного значения void GetSharedData(__out SHAREDDATA *psd) {   *psd = g_rgsd[g_isd]; }

Считывателю данных нужно просто получить последнее опубликованное значение. Самой сложной частью является публикация значения.

Хотя, на самом деле, не так уж это и сложно.

LONG g_isdNext = 1; void UpdateSharedData(__in const SHAREDDATA *psd) {   UINT isd = (UINT)InterlockedIncrementAcquire(&g_isdNext);   isd %= SHAREDDATA_MAXCONCURRENT;   g_rgsd[isd] = *psd;   InterlockedExchange(&g_isd, isd); }

Публикация данных заключается в простом получении слота для данных при помощи функции InterlockedIncrement, которая вернет нам уникальное местоположение для сохраняемых данных, или, по крайней мере, уникальное в течение SHAREDDATA_MAXCONCURRENT – 1 промежуточных публикаций. Мы сохраняем наши результаты в полученный нами слот памяти, а затем публикуем новый индекс. Публикация должна быть осуществлена с применением семантики освобождения (Release semantics), но поскольку другие вызовы функции InterlockedExchangeRelease отсутствуют, то мы просто выполним обновление значения с использованием полного барьера памяти.

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

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

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

Упражнение: как бы вы изменили это решение, если бы новые значения зависели от старых?