Алгоритмы без использования блокировок: выбор уникального значения (решения)

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

dwUniqueId = InterlockedCompareExchange(&g_dwUniqueId,                                         g_dwUniqueId+1,                                         g_dwUniqueId);

Скорее всего, проще будет перечислить то, что в этой функции корректно, нежели перечислять то, что она делает неправильно.

Эм... все слова написаны без ошибок.

Это все.

Дэмиен (Damien) был первым, кто отметил, что автор просто-напросто реализовал еще один вариант функции InterlockedIncrement. Неудовлетворительно.

Как мы видели ранее, алгоритм для выполнения сложных вычислений с использованием interlocked-функций содержит следующие стадии: захват (capture), вычисление (compute), сравнение-обмен (compare-exchange), повтор попытки (retry). Но вышеприведенный код ничего такого не делает.

Без захвата этих значений вышеприведенный код подвержен проблемам, когда два потока в одно и то же время изменяют значение g_dwUniqueId. Это означает, что шаг вычисления может потерпеть неудачу из-за несвоевременного считывания значения g_dwUniqueId, что приведет к тому, что значение, передаваемое в функцию InterlockedCompareExchange, станет неопределенным.

Итак, они правильно написали наименование функции InterlockedCompareExchange.
Но потом они забыли реализовать шаг повторения операции, в том случае, когда шаг сравнения-обмена завершился неудачей, что означает, что они просто-напросто продолжают использовать то значение g_dwUniqueId, которое находилось в этой переменной в момент вызова InterlockedCompareExchange и может быть как корректным, так и некорректным. Если это значение было увеличено на единицу другим потоком, то оба этих потока будут использовать одно и то же «уникальное» значение.

Джошуа (Joshua) отмечает, что настройки оптимизации компилятора могут не позволить операции захвата выполнить действительный захват. Однако я бы предпочел поставить ключевое слово «volatile» перед переменной g_dwUniqueId, нежели перед переменной scv, поскольку объект, помеченный ключевым словом volatile, является глобальной переменной, а не локальной. Пометка локальной переменной ключевым словом volatile заставляет выполнять все запросы к локальной переменной так, как указано в коде, но компилятор по-прежнему может оптимизировать операции доступа к переменной g_dwUniqueId. (К примеру, он может использовать значение переменной, полученное во время ее предыдущего считывания в функции).

И примите во внимание предупреждение Лео Дэвидсона (Leo Davidson): эта серия статей предназначена для того, чтобы заглянуть за кулисы и узнать, как там все устроено, а не для того, чтобы дать готовые инструкции и примеры для использования в реальных проектах. Нам придется разобрать несколько тостеров, чтобы узнать, как они работают. Но в реальных проектах, когда это возможно, лучше используйте код, написанный людьми, которые умнее вас.