{"id":10963,"date":"2011-04-12T07:00:00","date_gmt":"2011-04-12T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2011\/04\/12\/lock-free-algorithms-the-trycommittry-again-pattern\/"},"modified":"2011-04-12T07:00:00","modified_gmt":"2011-04-12T07:00:00","slug":"lock-free-algorithms-the-trycommittry-again-pattern","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20110412-00\/?p=10963","title":{"rendered":"Lock-free algorithms: The try\/commit\/(try again) pattern"},"content":{"rendered":"

\nThe singleton constructor pattern and the\n\nInterlocked­Multiply<\/code><\/a> example we saw some time ago\nare really special cases of the more general pattern which I’ll call\ntry\/commit\/(try again).\nI don’t know if this pattern has a real name,\nbut that’s what I’m calling it for today.\n<\/p>\n

\nThe general form of this pattern goes like this:\n<\/p>\n

\nfor (;;) {\n \/\/ capture the initial value of a shared variable we want to update\n originalValue = sharedVariable;\n ... capture other values we need to perform the operation ...\n ... these values must be indepedent of sharedVariable ...\n newValue = ... calculate the desired new result\n                based on originalValue and other captured values ...\n \/\/ Xxx can be Acquire, Release, or null\n if (InterlockedCompareExchangeXxx(\n            &sharedVariable,\n            newValue, oldValue) == oldValue) {\n  break; \/\/ update was successful\n }\n ... clean up newValue ...\n} \/\/ loop back and try again\n<\/pre>\n
\nWe calculate the desired new value based on the initial value,\ncombining it with other values that vary depending on the operation\nyou want to perform,\nand then use an Interlocked­Compare­Exchange<\/code>\nto update the shared value,\nprovided the variable hasn’t changed from its initial value<\/i>.\nIf the value did change, then that means another thread raced against\nus and updated the value before we could;\nin that case, we go back and try it again.\nMaybe the next time through we won’t collide against somebody.\n<\/p>\n
\nNote that the try\/commit\/try again pattern is unfair.\nThere’s no assurance that the thread that has been trying to update\nthe value for the longest time will win the next race.\n(This is a property common to most lock-free algorithms.)\n<\/p>\n
\nThe Interlocked­Multiply<\/code> function\nfollows this pattern very closely:\nThe other value required to perform the operation is simply\nthe multiplier, which is a parameter to the function and therefore\nis independent of the shared variable.\nThe new value is simply the product,\nand if we are unable to update the shared value (because somebody\nelse modified it), we just start over.\n<\/p>\n
\nA variation of try\/commit\/try again is try\/commit\/abandon.\nIn this pattern, there is no loop.\nIf the exchange fails, you just give up and return a failure code.\nThe function Try­Enter­Critical­Section<\/code> uses the\ntry\/commit\/abandon pattern.\n(It also uses the Acquire version of\nInterlocked­Compare­Exchange<\/code>\nfor reasons which should be obvious.)\n<\/p>\n
\nOur singleton pattern is another special case of try\/commit\/try again\nwhere the “try again” is optimized out because we know what the result\nof “try again” is going to be, so we don’t actually have to do it.\nIn the singleton pattern case, the\nInterlocked­Compare­Exchange<\/code>\nis a Release because the new value depends on other memory locations.\n<\/p>\n
\nNormally, the shared variable is an integer rather than a pointer,\nbecause a pointer is subject to the ABA problem if you incorporate\nthe pointed-to data into your calculations.\nWe get away with it in the singleton pattern case because the value\nchange is unidirectional: It goes from NULL<\/code> to\nsomething<\/i>, and once it’s something<\/i> it never changes again.\nIf the value of the shared variable can change in more general ways,\nthen you have to be more careful if you use a pointer\nas the shared variable.\n(The most common solution is to make the shared variable not just\na pointer but a pointer plus a counter which increments at each operation.)\n<\/p>\n
\nHere’s another use of the try\/commit\/try again pattern, using\na change counter as the shared variable.\nFirst, two helper functions:\n<\/p>\n
\nLONG InterlockedReadAcquire(__in LONG *pl, __in LONG lUnlikely)\n{\n  return InterlockedCompareExchangeAcquire(pl, lUnlikely, lUnlikely);\n}\nLONG InterlockedReadRelease(__in LONG *pl, __in LONG lUnlikely)\n{\n  return InterlockedCompareExchangeRelease(pl, lUnlikely, lUnlikely);\n}\n<\/pre>\n
\nAlthough direct reads and writes of properly aligned LONG<\/code>s\nare atomic, the operations are not synchronized and impose no\nmemory ordering semantics.\nTo read a value with specific semantics,\nI pull a sneaky trick:\nI perform an\nInterlocked­Compare­Exchange<\/code> with the\ndesired memory ordering semantics, passing the same value as the\ncomparand and the exchange;\ntherefore, the operation, even if successful, has no computational effect.\n<\/p>\n
\nif (*pl == lUnlikely) *pl = lUnlikely;\n<\/pre>\n
\nTo avoid dirtying the cache line,\nI use an unlikely value as the comparand\/exchange,\nso most of the time, the comparison fails and no memory is written.\n(This trick doesn’t help on all architectures, but it doesn’t hurt.)\n<\/p>\n
\nOkay, back to the change counter example:\n<\/p>\n
\nLONG g_lColorChange;\n...\ncase WM_SYSCOLORCHANGE:\n InterlockedIncrement(&g_lColorChange);\n ...\nint CalculateSomethingAboutSystemColors()\n{\n LONG lColorChangeStart;\n do {\n  lColorChangeStart = InterlockedReadAcquire(&g_lColorChange, -1);\n  COLORREF clrWindow = GetSysColor(COLOR_WINDOW);\n  COLORREF clrHighlight = GetSysColor(COLOR_HIGHLIGHT);\n  ... other computations involving GetSysColor(...)\n } while (InterlockedReadRelease(\n                       &g_lColorChange, -1) != lColorChangeStart);\n return iResult;\n}\n<\/pre>\n
\nWe capture the color change counter and then begin doing our\ncalculations.\nWe capture the value with acquire semantics so that we get the value\nbefore we start reading the system colors.\nWhen we’re done,\nwe compare the value of the change counter against the value we\ncaptured.\nIf it’s different, then that means that the colors changed while\nwe were doing our calculations, so our calculations are all messed up.\nIn that case,\nwe go back and try it again.\n<\/p>\n
\nThis technique does assume that you won’t get into a situation where\none thread manages to increment the change counter 4 billion times\nbefore the other thread manages to run.\nThis is not a problem in practice.\nFor example, in this case, it’s reasonable to assume that\nnobody is going to change their system\ncolors 4 billion times within a single thread quantum.\n<\/p>\n
\nNext time,\nI’ll show a different variation on try\/commit\/abandon\nwhich might be suitable for simple caches.\n<\/p>\n
\nExercise<\/b>:\nCriticize the following:\n“I noticed that there is no interlocked read operation,\nbut there is Interlocked­Or<\/code>,\nso my plan is to perform an interlocked read by or’ing with zero.”<\/p>\n","protected":false},"excerpt":{"rendered":"
The singleton constructor pattern and the Interlocked­Multiply example we saw some time ago are really special cases of the more general pattern which I’ll call try\/commit\/(try again). I don’t know if this pattern has a real name, but that’s what I’m calling it for today. The general form of this pattern goes like this: for […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-10963","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
The singleton constructor pattern and the Interlocked­Multiply example we saw some time ago are really special cases of the more general pattern which I’ll call try\/commit\/(try again). I don’t know if this pattern has a real name, but that’s what I’m calling it for today. The general form of this pattern goes like this: for […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/10963","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=10963"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/10963\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=10963"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=10963"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=10963"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}