{"id":37863,"date":"2004-09-15T07:00:00","date_gmt":"2004-09-15T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2004\/09\/15\/interlocked-operations-dont-solve-everything\/"},"modified":"2004-09-15T07:00:00","modified_gmt":"2004-09-15T07:00:00","slug":"interlocked-operations-dont-solve-everything","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20040915-00\/?p=37863","title":{"rendered":"Interlocked operations don’t solve everything"},"content":{"rendered":"

\n\nInterlocked operations<\/A>\nare a high-performance way of updating DWORD-sized\nor pointer-sized values in an atomic manner.\nNote, however, that this doesn’t mean that you can avoid\nthe critical section.\n<\/P>\n

\nFor example, suppose you have a critical section that protects\na variable, and in some other part of the code, you want to\nupdate the variable atomically. “Well,” you say,\n“this is a simple imcrement, so I can skip the critical section\nand just do a direct InterlockedIncrement. Woo-hoo, I avoided\nthe critical section bottleneck.”\n<\/P>\n

\nWell, except that the purpose of that critical section was to\nensure that nobody changed the value of the variable while the\nprotected section of code was running. You just ran in and\nchanged the value behind that code’s back.\n<\/P>\n

\nConversely, some people suggested emulating complex interlocked operations\nby having a critical section whose job it was to protect the variable.\nFor example, you might have an InterlockedMultiply that goes like this:\n<\/P>\n

\n\/\/ Wrong!\nLONG InterlockedMultiply(volatile LONG *plMultiplicand, LONG lMultiplier)\n{\n  EnterCriticalSection(&SomeCriticalSection);\n  LONG lResult = *plMultiplicand *= lMultiplier;\n  LeaveCriticalSection(&SomeCriticalSection);\n  return lResult;\n}<\/I>\n<\/PRE>\n
\nWhile this code does protect against two threads performing an\nInterlockedMultiply against the same variable simultaneously,\nit fails to protect against other code performing a simple\natomic write to the variable.  Consider the following:\n<\/P>\n
\nint x = 2;\nThread1()\n{\n  InterlockedIncrement(&x);\n}<\/p>\n
Thread2()\n{\n  InterlockedMultiply(&x, 5);\n}\n<\/PRE>\n
\nIf the InterlockedMultiply were truly interlocked,\nthe only valid results would be x=15 (if the interlocked\nincrement beat the interlocked multiply)\nor x=11 (if the interlocked multiply beat the interlocked\nincrement).\nBut since it isn’t truly interlocked, you can get other\nweird values:\n<\/P>\n\n
Thread 1<\/TH>Thread 2<\/TH><\/TR>\n
x = 2 at start<\/TD><\/TR>\n
<\/TD>InterlockedMultiply(&x, 5)<\/TD><\/TR>\n
<\/TD>EnterCriticalSection<\/TD><\/TR>\n
<\/TD>load x (loads 2)<\/TD><\/TR>\n
InterlockedIncrement(&x);
\n        x is now 3<\/TD>		<\/TD><\/TR>\n
<\/TD>multiply by 5 (result: 10)<\/TD><\/TR>\n
<\/TD>store x (stores 10)<\/TD><\/TR>\n
<\/TD>LeaveCriticalSection<\/TD><\/TR>\n
x = 10 at end<\/TD><\/TR>\n<\/TABLE>\n
\nOh no, our interlocked multiply isn’t very interlocked after all!\nHow can we fix it?\n<\/P>\n
\nIf the operation you want to perform is a function solely of the\nstarting numerical value and the other function parameters\n(with no dependencies on any other memory locations), you can\nwrite your own interlocked-style operation with the help of\n\nInterlockedCompareExchange<\/A>.\n<\/P>\n
\nLONG InterlockedMultiply(volatile LONG *plMultiplicand, LONG lMultiplier)\n{\n  LONG lOriginal, lResult;\n  do {\n    lOriginal = *plMultiplicand;\n    lResult = lOriginal * lMultiplier;\n  } while (InterlockedCompareExchange(plMultiplicand,\n                                      lResult, lOriginal) != lOriginal);\n  return lResult;\n}\n<\/PRE>\n
\n[Typo in algorithm fixed 9:00am.]\n<\/P>\n
\nTo perform a complicated function on the multiplicand, we perform\nthree steps.\n<\/P>\n
\nFirst, capture the value from memory:\n    lOriginal = *plMultiplicand;<\/CODE>\n<\/P>\n
\nSecond, compute the desired result from the captured value:\n    lResult = lOriginal * lMultiplier;<\/CODE>\n<\/P>\n
\nThird, store the result provided the value in memory has not changed:\nInterlockedCompareExchange(plMultiplicand, lResult, lOriginal)<\/CODE>\n<\/P>\n
\nIf the value did change, then this means that the interlocked operation\nwas unsucessful because somebody else changed the value while we were\nbusy doing our computation.  In that case, loop back and try again.\n<\/P>\n
\nIf you walk through the scenario above with this new InterlockedMultiply\nfunction, you will see that after the interloping InterlockedIncrement,\nthe loop will detect that the value of “x” has changed and restart.\nSince the final update of “x” is performed by an InterlockedCompareExchange\noperation, the result of the computation is trusted\nonly if “x” did not change value.\n<\/P>\n
\nNote<\/STRONG> that this technique works only if the\noperation being performed is a pure function of the memory value\nand the function parameters.  If you have to access other memory\nas part of the computation, then this technique will not work!\nThat’s because those other memory locations might have changed\nduring the computation and you would have no way of knowing, since\nInterlockedCompareExchange checks only the memory value being\nupdated.\n<\/P>\n
\nFailure to heed the above note results in problems such as the\nso-called “ABA Problem”.\nI’ll leave you to google on that term and read about it.\nFortunately, everybody who talks about it also talks about how\nto solve<\/STRONG> the ABA Problem, so I’ll leave you to\nread that, too.\n<\/P>\n
\nOnce you’ve read about the ABA Problem and its solution,\nyou should be aware that the solution has already been\nimplemented for you, via the\n\nInterlocked SList functions<\/A>.\n<\/P><\/p>\n","protected":false},"excerpt":{"rendered":"
Interlocked operations are a high-performance way of updating DWORD-sized or pointer-sized values in an atomic manner. Note, however, that this doesn’t mean that you can avoid the critical section. For example, suppose you have a critical section that protects a variable, and in some other part of the code, you want to update the variable […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-37863","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Interlocked operations are a high-performance way of updating DWORD-sized or pointer-sized values in an atomic manner. Note, however, that this doesn’t mean that you can avoid the critical section. For example, suppose you have a critical section that protects a variable, and in some other part of the code, you want to update the variable […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/37863","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=37863"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/37863\/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=37863"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=37863"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=37863"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}