\nThe first half may be familiar to many (most?) readers,\nbut there’s an interesting exercise at the bottom.\n<\/p>\n
\nA very useful pattern for the Interlocked* functions is\nlock-free lazy initialization via\n \nThis is a double-check lock, but without the locking.\nInstead of taking lock when doing the initial construction,\nwe just let it be a free-for-all over who gets to create the\nobject.\nIf five threads all reach this code at the same time,\nsure, let’s create five objects.\nAfter everybody creates what they think is the winning object,\nthey called\n \nThe parts of the name of the\n \nThis technique is suitable when it’s okay to let multiple threads\ntry to create the singleton (and have all the losers destroy\ntheir copy).\nIf creating the singleton is expensive or has unwanted\nside-effects, then you don’t want to use the free-for-all algorithm.\n<\/p>\n \nBonus reading:\n<\/p>\n \nOkay, now here’s the interesting exercise.\nThis is an actual problem I helped out with,\nalthough details have been changed for expository purposes.\n<\/p>\n \nWe have a data structure which manages a bunch of singleton objects,\nlet’s say that they are instances of a structure\ncalled \nIn words, the \nOur initial inclination is to put a critical section around\nthe entire \nBonus chatter<\/b>:\nAlthough it’s the case on Windows that\n\nthe plain versions of the interlocked functions impose both acquire\nand release semantics<\/a>,\nother platforms may not follow Windows’ lead.\nIn particular,\non the XBOX360 platform, the plain versions of the interlocked\nfunctions impose neither<\/u> acquire nor release semantics.\nI don’t know what the rules are for Windows CE.\n<\/p>\nInterlockedCompareExchangePointerRelease<\/code>.\nYes, that’s a really long function name, but it turns out\nevery part of it important.\n<\/p>\n\nWidget *g_pwidCached;\nWidget *GetSingletonWidget()\n{\n Widget *pwid = g_pwidCached;\n if (!pwid) {\n pwid = new(nothrow) Widget();\n if (pwid) {\n Widget *pwidOld = reinterpret_cast<Widget*>\n (InterlockedCompareExchangePointerRelease(\n &reinterpret_cast<PVOID&>(g_pwidCached),\n pwid, NULL));\n if (pwidOld) {\n delete pwid; \/\/ lost the race - destroy the redundant copy\n pwid = pwidOld; \/\/ use the old one\n }\n }\n }\n return pwid;\n}\n<\/pre>\nInterlockedCompareExchangePointerRelease<\/code>\nto attempt to update the global pointer.\n<\/p>\nInterlockedCompareExchangePointerRelease<\/code>\nfunction\nwork like this:\n<\/p>\n\n
Interlocked<\/code>: The operation is atomic.\n This is important to avoid two threads successfully updating\n the value of g_pwidCached<\/code>.\n<\/li>\nCompare<\/code>: The value in g_pwidCached<\/code>\n is compared against NULL<\/code>.\n<\/li>\nExchange<\/code>:\n If the values are equal, then\n g_pwidCached<\/code> is set to pwid<\/code>.\n This, combined with the comparison, ensures that only one\n thread gets to set the value of g_pwidCached<\/code>.\n<\/li>\nPointer<\/code>:\n The operations are on pointer-sized data.\n<\/li>\nRelease<\/code>:\n The operation takes place with\n \n release semantics<\/a>.\n This is important to ensure that the pwid<\/code> we created\n is fully-constructed before we publish its pointer to other\n processors.\n<\/li>\n<\/ul>\n\n
\n
ITEMCONTROLLER<\/code> and they are keyed by a 32-bit ID.\nWe’re looking for design suggestions on making it thread-safe.\nThe existing code goes like this (pseudocode):\n<\/p>\n\nstruct ITEMCONTROLLER;\nstruct SINGLETONINFO {\n DWORD dwId;\n ITEMCONTROLLER *(*pfnCreateController)();\n};\nclass SingletonManager {\npublic:\n \/\/ rgsi is an array that describes how to create the objects.\n \/\/ It's a static array, with csi in the range 20 to 50.\n SingletonManager(const SINGLETONINFO *rgsi, UINT csi)\n : m_rgsi(rgsi), m_csi(csi),\n m_rgcs(NULL), m_ccs(0), m_ccsAlloc(0) { }\n ~SingletonManager() { ... }\n ITEMCONTROLLER *Lookup(DWORD dwId);\nprivate:\n struct CREATEDSINGLETON {\n DWORD dwId;\n ITEMCONTROLLER *pic;\n };\nprivate:\n const SINGLETONINFO *m_rgsi;\n int m_csi;\n \/\/ Array that describes objects we've created\n CREATEDSINGLETON *m_rgcs;\n int m_ccs;\n};\nITEMCONTROLLER *SingletonManager::Lookup(DWORD dwId)\n{\n int i;\n \/\/ See if we already created one\n for (i = 0; i < m_ccs; i++) {\n if (m_rgcs[i].dwId == dwId)\n return m_rgcs[i].pic;\n }\n \/\/ Not yet created - time to create one\n ITEMCONTROLLER *pic;\n for (i = 0; i < m_rgsi; i++) {\n if (m_rgsi[i].dwId == dwId) {\n pic = m_rgsi[i].pfnCreateController();\n break;\n }\n }\n if (pic == NULL) return;\n ... if m_rgcs == NULL then allocate it and update m_ccsAlloc\n ... else realloc it bigger and update m_ccsAlloc\n \/\/ append to our array so we can find it next time\n m_rgcs[m_ccs].dwId = dwId;\n m_rgcs[m_ccs].pic = pic;\n m_ccs++;\n return pic;\n}\n<\/pre>\nSingletonManager<\/code> takes an array\nof SINGLETONINFO<\/code> structures, each of which\ncontains an ID and a function to call to create the object\nwith that ID.\nTo look up an entry, we first check if we already created one;\nif so, then we just return the existing one.\nOtherwise, we create the object (using pfnCreateController<\/code>)\nand add it to our array of created objects.\n<\/p>\nLookup<\/code> function, but maybe there’s\nsomething more clever we can do here.\nMaybe a\n\nslim reader-writer lock<\/a>?\n<\/p>\n<\/blockquote>\n