Almost done with our miniseries on lock-free many-producer\/single-consumer patterns. Today, we’ll look at the case of multiple producers generating distinct work items which cannot be coalesced, but for which the order of processing is not important. <\/p>\n
As I noted last time, you can view this as a scenario built on top of the previous one. In the previous scenario, there was a counter of the number of work items to be done, but the work itself was fixed. You can pair this with another data structure that contains a collection of things to do. In that case, the We’re going to go one step further: We’re going to let the work item be its own counter. <\/p>\n We use the lock-free linked list data structure On the consumer side, we atomically pop work off the list and process them, and we stop when there is no more work. Since the order in which work items are processed is presumed to be unimportant, we can process them LIFO. <\/p>\n Remember, there is only one consumer, so if Next time, we’ll wrap up by looking at the case where work items must be processed FIFO. <\/p>\n","protected":false},"excerpt":{"rendered":" Each one is different in its own special way, but we don’t care what order they are processed.<\/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-94775","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":" Each one is different in its own special way, but we don’t care what order they are processed.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/94775","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=94775"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/94775\/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=94775"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=94775"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=94775"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}DoSomeWork()<\/code> function pulls a work item out of the collection. <\/p>\n\nSLIST_HEADER WorkQueue;\n\nstruct alignas(MEMORY_ALLOCATION_ALIGNMENT)\nWorkItem : SLIST_ENTRY\n{\n ... other stuff ...\n};\n\nvoid Initialize()\n{\n InitializeSListHeader(&WorkQueue);\n}\n\nvoid RequestWork(WorkItem* work)\n{\n if (InterlockedPushEntrySList(&WorkQueue, work)\n == nullptr) {\n \/\/ You provide the WakeConsumer() function.\n WakeConsumer();\n }\n}\n\n\/\/ You call this function when the consumer receives the\n\/\/ signal raised by WakeConsumer().\nvoid ConsumeWork()\n{\n PSLIST_ENTRY entry;\n while ((entry = InterlockedPopEntrySList(&WorkQueue))\n != nullptr) {\n ProcessWorkItem(static_cast<WorkItem*>(entry));\n delete entry;\n }\n}\n<\/pre>\nLIST_HEADER<\/code> to manage our work queue. To request some work, we push an item onto the front of the list. The InterlockedPushEntrySList<\/code> function returns the previous list head. If that returns nullptr<\/code>, then it means that the list was empty, so we wake up the consumer. If the list was not empty, then it means that somebody else woke the consumer, so we won’t do it (to avoid a spurious wake). <\/p>\nWakeConsumer<\/code> is called while ConsumeWork<\/code> is still running, the wake will not start a new consumer immediately. It will wait for the existing ConsumeWork<\/code> to complete before starting a new ConsumeWork<\/code>. <\/p>\n