Алгоритмы без использования блокировок: singleton-конструктор

  • Article

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

Весьма практичным шаблоном для Interlocked-* функций является ленивая инициализация без блокировок, которая использует InterlockedCompareExchangePointerRelease. Да, наименование у этой функции очень длинное, но, в действительности, каждая часть этого наименования важна.

Widget *g_pwidCached; Widget *GetSingletonWidget() {   Widget *pwid = g_pwidCached;   if (!pwid) {     pwid = new(nothrow) Widget();     if (pwid) {       Widget *pwidOld = reinterpret_cast<Widget*>             (InterlockedCompareExchangePointerRelease(                 &reinterpret_cast<PVOID&>(g_pwidCached),                 pwid, NULL));       if (pwidOld) {         delete pwid; // проиграл в гонке — теперь уничтожь ненужную копию         pwid = pwidOld; // используй старый экземпляр       }     }   }   return pwid; }

Здесь реализована двойная проверка, но блокировка при этом не используется. Вместо нее во время первого создания объекта мы просто-напросто разрешаем создавать этот объект всем потокам, дошедшим до выполнения этой операции. Если все пять потоков дойдут до этой точки одновременно, то пусть создают пять объектов, мы не будем им мешать. После того, как все они создадут по одному объекту, который, как они считают, единственный, они должны вызвать InterlockedCompareExchangePointerRelease для попытки обновления глобального указателя.

Части наименования функции InterlockedCompareExchangePointerRelease означают примерно следующее:

  • Interlocked (блокирующий): операция выполняется атомарно. Это важно для того, чтобы избежать ситуации, когда два потока одновременно обновляют значение g_pwidCached.
  • Compare (сравнение): значение g_pwidCached будет сравниваться со значением NULL.
  • Exchange (обмен): если значения равны, то значение g_pwidCached будет установлено равным значению pwid. Эта операция, вкупе со сравнением, гарантирует, что значение g_pwidCached будет установлено только одним потоком.
  • Pointer (указатель): операции работают с указателями.
  • Release (освобождение): операция выполняется с использованием семантики освобождения (release semantics). Это очень важно, поскольку объект pwid, создаваемый нами, должен быть проинициализирован полностью, прежде чем ссылка на него станет доступной другим процессам.

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

Дополнительная информация для ознакомления:

  • Вспомогательные функции для создания объектов с однократной инициализацией избавляют от написания всего этого вспомогательного кода. Они работают со всеми видами синхронизаций и барьерами памяти (memory barrier) и поддерживают как алгоритмы, в которых создание экземпляра допускается только один раз, так и алгоритмы, в которых создание экземпляров допускается несколько раз в разных потоках (как в рассмотренном выше примере).
  • В статье «Примеры использования ленивой инициализации в .NET» описано то же самое, но с использованием языка C#.

Отлично, а теперь — обещанное интересное упражнение. Здесь описана реально существовавшая проблема, которую я помогал решить, но некоторые ее детали были изменены для того, чтобы пример был более понятным.

У нас есть структура данных, которая управляет группой singleton-объектов. Предположим, что все они являются экземплярами структуры ITEMCONTROLLER и имеют 32-битный ключ-идентификатор. Требуется найти способы модификации этого кода, чтобы сделать его потокобезопасным. Существующий код выглядит примерно так (он представлен в виде псевдокода):

struct ITEMCONTROLLER; struct SINGLETONINFO {   DWORD dwId;   ITEMCONTROLLER *(*pfnCreateController)(); }; class SingletonManager { public:   // rgsi — массив, описывающий, как следует создавать объекты, он является статическим   // csi принимает значения в интервале от 20 до 50.   SingletonManager(const SINGLETONINFO *rgsi, UINT csi)                 : m_rgsi(rgsi), m_csi(csi),                   m_rgcs(NULL), m_ccs(0), m_ccsAlloc(0) { }   ~SingletonManager() { ... }   ITEMCONTROLLER *Lookup(DWORD dwId); private:   struct CREATEDSINGLETON {     DWORD dwId;     ITEMCONTROLLER *pic;   }; private:   const SINGLETONINFO *m_rgsi;   int m_csi;   // Массив, описывающий созданные объекты   CREATEDSINGLETON *m_rgcs;   int m_ccs; }; ITEMCONTROLLER *SingletonManager::Lookup(DWORD dwId) {   int i;   // Проверяем, создан ли уже объект   for (i = 0; i < m_ccs; i++) {     if (m_rgcs[i].dwId == dwId)       return m_rgcs[i].pic;   }   // Объект еще не создан — самое время создать его   ITEMCONTROLLER *pic;   for (i = 0; i < m_rgsi; i++) {     if (m_rgsi[i].dwId == dwId) {       pic = m_rgsi[i].pfnCreateController();       break;     }   }   if (pic == NULL) return;   ... если m_rgcs == NULL, тогда нужно выделить под него память и обновить значение m_ccsAlloc   ... иначе увеличить его размер, выделив под него дополнительную память, и обновить значение m_ccsAlloc   // добавим созданный объект в наш массив, чтобы в следующий раз мы смогли его найти   m_rgcs[m_ccs].dwId = dwId;   m_rgcs[m_ccs].pic = pic;   m_ccs++;   return pic; }

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

Нашим изначальным намерением было создание критической секции вокруг всей функции Lookup, но, возможно, есть какой-то более умный способ? Может, использовать тонкую блокировку чтения/записи (slim reader-writer lock)?

В продолжение темы: несмотря на то, что на платформе Windows обычные версии interlocked-функций предполагают и семантику захвата (acquire semantics), и семантику освобождения (release semantics), в других платформах все может быть иначе. В частности, на платформе XBOX360 обычные версии interlocked-функций не предполагают ни семантику захвата, ни семантику освобождения. Какое поведение реализовано на платформе Windows CE, мне неизвестно.

Дополнения к статье: раньше я знал, но потом забыл о том, что вариант шаблона «Одиночка» (singleton), описанный в этой статье (с использованием InterlockedCompareExchangePointer), не является потокобезопасным на некоторых архитектурах процессоров. Для того чтобы гарантировать, что при использовании косвенного доступа в операции извлечения указателя будет получено новое значение, а не одна из его закэшированных копий, после операции извлечения следует добавить вызов MemoryBarrier().

Widget *GetSingletonWidget() {   Widget *pwid = g_pwidCached;   if (!pwid) {     ...   } else {<br> // Нужно убедиться, что разыменование pwid будет возвращать новые,<br> // а не старые, закэшированные значения.<br> MemoryBarrier();   }   return pwid; }

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