\nThe last lock-free pattern for this week isn’t actually lock-free,\nbut it does run without blocking.\n<\/p>\n
\nThe pattern for what I’ll call try\/commit\/(hand off) is more complicated\nthan the other patterns, so I’ll start off by\ndescribing it in words rather than in code,\nbecause the code tends to make things more complicated.\n<\/p>\n
\nFirst, you take the state variable and chop it up into pieces.\nYou need some bits\nto be used as a lock and as a work has been handed off<\/i> flag.\nAnd if the work that has been handed off is complicated,\nyou may need some more bits to remember the details of the handoff.\nA common way of doing this is to use a pointer-sized state variable,\nrequire that the objects being pointed to are suitably aligned,\nand reusing the bottom bits as flags.\nFor example, if you require that the objects be \nTo perform an operation, you first try to lock the state variable.\nIf you can’t because the state variable is already locked,\nthen you record the details of the operation in the state variable\nand update it atomically.\n<\/p>\n \nIf you succeed in locking the state variable, then you perform\nthe desired operation, but before you unlock the state variable,\nyou look to see if any work has been handed off.\n(This hand-off work is the result of attempts to perform the operation\nwhile you held the lock.)\nIf there is hand-off work, then you perform that work as well.\nOf course, while you’re doing that, more\nhand-off work may arrive.\nYou can’t unlock the state variable until you’ve\ndrained off all the pent-up hand-off work.\n<\/p>\n \nThe code for this pattern tends to be a tangle of loops since there\nis a lot off backing off and retrying.\nEvery atomic operation is its own loop, draining the hand-off work\nis another loop,\nand\nany time an \nI trust only about five people in the world to write code\nthat is this advanced, and I’m not one of them.\nBut just to illustrate the principle (although I will certainly\nget the details wrong), here’s an implementation of a synchronization-like\nobject which I will call a \nThe group wait object is just a linked list of\n \nActually, this type of object doesn’t need to use the try\/commit\/hand off\nmodel.\nIt can be implemented in a much more straightforward manner by\nhaving \nSince the bottom two bits of the pointer must be zero due to alignment,\nwe repurpose them as a lock bit and a signal bit.\nThe lock bit is set when the list is locked,\nand the signal bit is set when a signal was requested but had to be\nhanded off because the list was locked.\n<\/p>\n \nSince I will be viewing the \nFor notational purposes, a \nrepresents a group wait with three registered event handles.\nThe DWORD<\/code>-aligned,\nthen the two bottom bits will always be zero\nand you can reuse them as flags.\n<\/p>\nInterlockedCompareExchange<\/code> fails,\nyou have to undo the work you did and retry—another loop.\n<\/p>\nGroupWait<\/code> for lack of any other\nname.\nIt has the following operations:\n<\/p>\n\n
AddWait<\/code>:\n Register an event handle with the group wait.\n<\/li>\nSignalAll<\/code>:\n Signals all events that are registered with the group wait.\n Once an event is signalled, it is automatically unregistered\n from the group wait.\n If you want the event to be signalled at the next call to\n SignalAll<\/code> you have to re-add it.\n<\/li>\n<\/ul>\nNODE<\/code>s containing the handles being waited on.\n<\/p>\nAddWait<\/code> atomically prepend the node to a list\nand having SignalAll<\/code> atomically steal the list.\nThere are even\n\nprewritten functions to perform these atomic\nlinked list operations for you<\/a>.\nBut I’m going to implemented it the complicated way\nfor demonstration purposes.\nIn real life, the code would be much simpler.\n<\/p>\n\n\/\/ WARNING! IF YOU USE THIS CODE YOU ARE AN IDIOT - READ THE TEXT ABOVE\nstruct NODE;\nNODE *Node(LONG_PTR key) { return reinterpret_cast<NODE*>(key); }\nenum {\n Locked = 1,\n Signalled = 2,\n};\nstruct NODE {\n NODE *pnNext;\n HANDLE hEvent;\n LONG_PTR Key() { return reinterpret_cast<LONG_PTR>(this); }\n NODE *Ptr() { return Node(Key() & ~(Locked | Signalled)); }\n};\n#define NODE_INVALID Node(-1)\nclass GroupWait {\npublic:\n GroupWait() : m_pnRoot(NULL) { }\n ~GroupWait();\n BOOL AddWait(HANDLE hEvent);\n void SignalAll();\nprivate:\n NODE *m_pnRoot;\n};\n<\/pre>\nNODE*<\/code> as both a pointer\nand as a bunch of bits (which I call a key<\/i>),\nI created some helper methods to save typing.\nNode<\/code> and Key<\/code> convert back and forth\nbetween node pointers and keys,\nand Ptr<\/code> strips off the tag bits and returns a usable\npointer.\n<\/p>\nNODE*<\/code> will be written as\nthe combination p|S|L<\/code> where p<\/code> is a\npointer to the next node, S<\/code> is the signalled bit,\nand L<\/code> is the lock bit.\nThe signalled bit is set to indicate that\nwe need to signal all the nodes in the list\nstarting with the next<\/i> node.\n(Think of the S<\/code> bit\nas being attached to the outgoing arrow.)\nFor example, this linked list:\n<\/p>\n\n m_pnRoot\n +--------+-+-+\n | * |0|1|\n +---|----+-+-+\n |\n v\n +--------+-+-+---------+\nA | * |1|?| hEvent1 |\n +---|----+-+-+---------+\n |\n v\n +--------+-+-+---------+\nB | * |?|?| hEvent2 |\n +---|----+-+-+---------+\n |\n v\n +--------+-+-+---------+\nC | NULL |?|?| hEvent3 |\n +--------+-+-+---------+\n<\/pre>\n
S<\/code> bit is clear on the root pointer,\nwhich means that\nnobody has yet requested that hEvent1<\/code> be signalled.\nOn the other hand,\nthe S<\/code> bit is set on node A, which means that\nall the events after node A need to be signaled,\nspecifically,\nhEvent2<\/code> and hEvent3<\/code>.\nNote that this means that it doesn’t matter whether the S<\/code>\nbit is set on nodes B or C; those events are\ngetting set regardless because the S<\/code> bit on node A\nalready requested it.\n(In particular, the S<\/code> bit on the last node is meaningless\nsince there are no nodes which come after it.)\n<\/p>\n