Алгоритмы без использования блокировок: обнови, если сможешь, а я выключаюсь
Клиент попросил помощи в решении проблемы синхронизации процессов:
У нас есть небольшой объем данных, который разделяется между несколькими процессами. Одним из способов защиты данных является использование примитива взаимоисключающей блокировки 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, обработать полученные значения, а затем опубликовать их, перезаписывая тем самым публикацию, производимую в это время другим процессором. Если новые значения зависят от старых (например, если они являются нарастающим итогом), то в таком случае вы только что потеряли одно обновление данных.
Также обратите внимание, что если два потока попытаются обновить данные одновременно, то нельзя сказать с полной уверенностью, какой набор данных будет прочитан, потому что здесь действует правило «выигрывает последний издатель».
Так получилось, что в данном случае новые значения абсолютно не зависят от старых, следовательно, проблема с потерянными обновлениями попросту отсутствует. Кроме того, в системе клиента обновлением данных в каждый момент времени занимается только один процесс. (В системе присутствует главный контроллер, который обновляет эти значения, а все остальные процессы лишь считывают их). Таким образом, этот простой механизм удовлетворяет заданным требованиям.
Упражнение: как бы вы изменили это решение, если бы новые значения зависели от старых?