{"id":10943,"date":"2011-04-13T07:00:00","date_gmt":"2011-04-13T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2011\/04\/13\/lock-free-algorithms-update-if-you-can-im-feeling-down\/"},"modified":"2011-04-13T07:00:00","modified_gmt":"2011-04-13T07:00:00","slug":"lock-free-algorithms-update-if-you-can-im-feeling-down","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20110413-00\/?p=10943","title":{"rendered":"Lock-free algorithms: Update if you can I'm feeling down"},"content":{"rendered":"

\nA customer was looking for advice on this synchronization problem:\n<\/p>\n

\n

\nWe have a small amount of data that we need to share among\nmultiple processes.\nOne way to protect the data is to use a spin lock.\nHowever, that has potential for deadlock if the process\nwhich holds the spinlock doesn’t get a chance to release it.\nFor example, it might be suspended in the debugger,\nor somebody might decide to use Terminate­Process<\/code>\nto nuke it.\n<\/p>\n

\nAny suggestions on how we can share this data without exposure to\nthese types of horrible failure modes?\nI’m thinking of something like a reader takes the lock,\nfetches the values, and then checks at status at the end of\ntell if the data is valid.\nMeanwhile, a writer tries to take the lock with a timeout,\nand if the timeout fires, then the writer just goes ahead\nanyway and updates the values, and somehow sets the status\non the reader so it knows that the value is no good and it\nshould try again.\nBasically, I don’t want either the reader or writer to get\nstuck indefinitely if a developer, say, just happens to break\ninto the debugger at the worst possible time.\n<\/p>\n<\/blockquote>\n

\nThis can be solved with a publishing pattern.\nWhen you want to update the values,\nyou indicate that new values are ready by publishing their new location.\n<\/p>\n

\nLet’s say that the data that needs to be shared is a collection\nof four integers.\n<\/p>\n

\nstruct SHAREDDATA {\n int a, b, c, d;\n};\n<\/pre>\n
\nAssume that there is\na practical limit on how often the value can change;\nthis is usually a safe assumption because you’ll have some\nsort of external rate limiter, like “This value changes\nin response to a user action.”\n(Even if there is no such limit, most solutions will simply\nposit one.\nFor example, the\n\nSLIST<\/code> functions<\/a>\nsimply assume that a processor won’t get locked out more\nthan 65535 times in a row.)\nIn our case, let’s say that the value will not change more than\n64 times in rapid succession.\n<\/p>\n
\n#define SHAREDDATA_MAXCONCURRENT 64\nSHAREDDATA g_rgsd[SHAREDDATA_MAXCONCURRENT];\nUINT g_isd; \/\/ current valid value\nvoid GetSharedData(__out SHAREDDATA *psd)\n{\n *psd = g_rgsd[g_isd];\n}\n<\/pre>\n
\nReading the data simply retrieves the most recently\npublished value.\nThe hard part is publishing the value.\n<\/p>\n
\nActually, it’s not hard at all.\n<\/p>\n
\nLONG g_isdNext = 1;\nvoid UpdateSharedData(__in const SHAREDDATA *psd)\n{\n UINT isd = (UINT)InterlockedIncrementAcquire(&g_isdNext);\n isd %= SHAREDDATA_MAXCONCURRENT;\n g_rgsd[isd] = *psd;\n InterlockedExchange(&g_isdNext, isd);\n}\n<\/pre>\n
\nPublishing the data is a simple matter of obtaining a slot\nfor the data, using Interlocked­Increment<\/code> to\nget a unique location to store the data,\nor at least least unique until\nSHAREDDATA_MAXCONCURRENT - 1<\/code> intervening\npublications have occurred.\nWe store our results into the memory we obtained\nand then publish the new index.\nThe publication needs to be done with release semantics,\nbut since there is no\nInterlocked­Exchange­Release<\/code>,\nwe just do a full barrier exchange.\n<\/p>\n
\nNote that the update is not atomic with the read.\nA processor can call Get­Shared­Data<\/code>,\nrevise the values, then publish them,\nonly to find that it overwrite a publication from\nanother processor.\nIf the new values are dependent on the old values\n(for example, if they are a running total),\nthen you just lost an update.\n<\/p>\n
\nNote also that if two threads try to update at the same\ntime, it’s pretty much random which set of values you get\nsince it’s last writer wins<\/i>.\n<\/p>\n
\nIt so happens that in this particular case,\nthe new values had nothing to do with the old values,\nso there was no problem with lost updates.\nAnd in practice, only one process updated the values at a time.\n(There is a master controller who updates the values, and everybody\nelse just reads them.)\nTherefore, this simple method meets the requirements.\n<\/p>\n
\nExercise<\/b>:\nHow would you adapt this solution if the new values depended on the\nold values?<\/p>\n","protected":false},"excerpt":{"rendered":"
A customer was looking for advice on this synchronization problem: We have a small amount of data that we need to share among multiple processes. One way to protect the data is to use a spin lock. However, that has potential for deadlock if the process which holds the spinlock doesn’t get a chance to […]<\/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-10943","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
A customer was looking for advice on this synchronization problem: We have a small amount of data that we need to share among multiple processes. One way to protect the data is to use a spin lock. However, that has potential for deadlock if the process which holds the spinlock doesn’t get a chance to […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/10943","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=10943"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/10943\/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=10943"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=10943"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=10943"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}