SpinLock/Mutex : Difference ?
in [Win32 Kernel]
|
From: Hugo gleaves on 21 Dec 2009 07:09 Well I am aware of what is on the net, I did research this a few years ago and spent ages looking at code in many places. The problem definition is this: 1. Must be a spinlock, using Interlock operations only, for concurrency handling. 2. Must not use Mutex, Critical Sections, Semaphores etc. 3. Must supported nested lock acquisition. 4. Must support Read/Write modes. 5. Must work in multi-process settings , not just multithreaded settings in a singe process. I found nothing at all on this subject, I have seen zero published on the subject of read/write spin locks. I have created an API that does this on Windows, the API also has a vicious test harness. Interestingly an early version appeared to work fine but when I tested it on a true dual processor box it failed, I debugged and fixed the failure and now it seems to be stable (assuming my test harness is truly rigorous). I also once asked id anyone could dream up a good test harness to prove the code, but nobody seemed interested, I'd still like to see anyone's suggestions for a test shell because I may have missed something. Either way, the subject of read/write spinlocks is genuinely interesting and it seems neglected by current movers & shakers. Hugh "m" wrote: > FYI reference implementations of shared reader, single writer locks are > widely available on usernet - the archives of this NG have at least two > threads on the topic and I am sure there is more out there. > > IMHO, a minimal implementation can be created with three volatile long > variable in less than 50 lines of code so the APIs provided by MS > (AcquireSRWLockExclusive and friends) are almost redundant > > http://msdn.microsoft.com/en-us/library/aa904937(VS.85).aspx > > > > "Hugogleaves(a)hotmail.com>" <hugh<underbar> wrote in message > news:574400EE-AFAF-4620-BDDD-7E49608392E0(a)microsoft.com... > > The idea of a spinlock is to ensure secure access/updates to some datum, > > usually for operations that are very very brief. So although some other > > thread/process may have to "spin" for a time, the time is deemed to brief > > as > > to be not a serious performance issue. > > > > The kind of operations that might be suited to a spinlock protection are: > > > > 1) Updating several fields atomically in some shared structure. > > 2) Adding/removing an entry from a shared list. > > > > As Don says a Mutex is much more sophisticated and expensive and although > > very uself in Win32 programming is no match for a spinlock when it comes > > to > > raw speed (this is why device drivers use them). > > > > The real question here is why has MS not provided developers with a > > spinlock > > API for user mode code? > > > > I had to hand craft such a beast in C, it has to support: > > > > 1) Nested locking (a spinlock can be acquired 'n' times and must then be > > released 'n' times). > > 2) Read/Write locking modes. > > 3) Not end up dragging its heels because of these needs. > > > > If you do a lot of work with shared/mapped memory as we do, then such an > > API > > is very important, if you rely on Mutexes it will cost dearly, also the > > interlock functions alone wont let you easily do the above (but they do > > provide the foundation). > > > > I've been interested for some time in seeing open source or public domain > > implementations of a user-mode spinlock API (one that is truly tested on > > multicore H/W) but there seems to be absolutely nothing, what we have > > seems > > to be pretty good but it is pretty complex and I worry sometimes... > > > > ;) > > > > > > "o0Zz" wrote: > > > >> Thank you very much ! > >> > >> "Daniel Terhell" <daniel(a)resplendence.com> a écrit dans le message de > >> groupe > >> de discussion : emRp7$LdKHA.2188(a)TK2MSFTNGP04.phx.gbl... > >> > "m" <m(a)b.c> wrote in message > >> > news:eP9kilIdKHA.6096(a)TK2MSFTNGP02.phx.gbl... > >> >> The loop will consume all 100% of a single CPU until the lock is > >> >> acquired, the thread is interrupted by a higher priority thread or the > >> >> thread quantum ends (and the OS schedules another thread). > >> >> > >> > > >> > That information is incorrect, on Windows a spinlock raises to > >> > DISPATCH_LEVEL (or higher) so it is not possible to get interrupted by > >> > any > >> > thread. It's not even possible for the thread to finish its quantum > >> > while > >> > it spins or for the dispatcher to schedule another thread on the same > >> > CPU. > >> > It can get interrupted by an ISR but it will return (to the spinning > >> > state) as soon as the ISR has executed and returns control. > >> > > >> > //Daniel > >> > > >> > > >> . > >> > . >
From: Chris M. Thomasson on 21 Dec 2009 08:30 "Hugo gleaves(a)hotmail.com>" <hugh<underbar> wrote in message news:575741A2-0093-4630-A652-248B0B35C9C1(a)microsoft.com... > Well I am aware of what is on the net, I did research this a few years ago > and spent ages looking at code in many places. > > The problem definition is this: > > 1. Must be a spinlock, using Interlock operations only, for concurrency > handling. > 2. Must not use Mutex, Critical Sections, Semaphores etc. > 3. Must supported nested lock acquisition. > 4. Must support Read/Write modes. > 5. Must work in multi-process settings , not just multithreaded settings > in > a singe process. For number 5, how are you handling the case when a thread dies while it has acquired either read or write access? > I found nothing at all on this subject, I have seen zero published on the > subject of read/write spin locks. I have created an API that does this on > Windows, the API also has a vicious test harness. Interestingly an early > version appeared to work fine but when I tested it on a true dual > processor > box it failed, I debugged and fixed the failure and now it seems to be > stable > (assuming my test harness is truly rigorous). You should probably model the algorithm in Relacy Race Detector: http://groups.google.com/group/relacy/web It will quickly find all types of bugs. It can even simulate every possible thread interleaving, which will find all errors. Can you post the algorithm? > I also once asked id anyone could dream up a good test harness to prove > the > code, but nobody seemed interested, I'd still like to see anyone's > suggestions for a test shell because I may have missed something. > > Either way, the subject of read/write spinlocks is genuinely interesting > and > it seems neglected by current movers & shakers. FWIW, have you seen what is probably the most clever rw-spinlock out there? Well, IMHO that is: http://groups.google.com/group/comp.programming.threads/browse_frm/thread/be3871ad661efa73 I applied eventcount's to Joe's bakery algorithm in order to allow waiters to block on a kernel waitset, but you can easily strip all of that out and add simple backoff scheme in the wait loop. It's 100% fair, starvation-free, and has wait-free fast-paths. It was invented by Joe Seigh and presented on `comp.programming.threads' some years ago, IIRC. However, I don't think it supports read or write recursion. I need to revisit the algorithm. You can always add read/write recursion using thread local data-structures.
From: Hugo gleaves on 21 Dec 2009 09:41 The current code does not cater for that scenario. I have designed a way to do it, on paper and I have a very solid "IsProcessRunning" function (that wasn't as trivial to write as it may first seem). The idea is that after a number of failed tries (e.g. 100 spins) call IsProcessRunning (the lock struct currently records the PID and DateTimeStarted of the locker, these two items uniquely identify a process) and if it has died, execute an "unlock on behalf of" type operation. Then (in effect) retry the lock operation. If it was read locked by many readers in that process, then eventually this approach will release each read lock and resolve the problem. However, I have not inserted this code or worked it out at the code level of detail yet, the reason is that I am undecided as to how to handle the dead locker anyway. If a locker died with a spin lock held then we may have a corrupt system. These locks are held purely within a larger API, the locking is never exposed to consumers of the main API, any API function that gets a lock will release it before it exits, so locks are never held unless executing inside one of the main APIs. I'm not at liberty unfortunately to reveal the algorithm or source code. Let me look at this relay race thing.... Thx Hugh "Chris M. Thomasson" wrote: > "Hugo gleaves(a)hotmail.com>" <hugh<underbar> wrote in message > news:575741A2-0093-4630-A652-248B0B35C9C1(a)microsoft.com... > > Well I am aware of what is on the net, I did research this a few years ago > > and spent ages looking at code in many places. > > > > The problem definition is this: > > > > 1. Must be a spinlock, using Interlock operations only, for concurrency > > handling. > > 2. Must not use Mutex, Critical Sections, Semaphores etc. > > 3. Must supported nested lock acquisition. > > 4. Must support Read/Write modes. > > 5. Must work in multi-process settings , not just multithreaded settings > > in > > a singe process. > > For number 5, how are you handling the case when a thread dies while it has > acquired either read or write access? > > > > > > I found nothing at all on this subject, I have seen zero published on the > > subject of read/write spin locks. I have created an API that does this on > > Windows, the API also has a vicious test harness. Interestingly an early > > version appeared to work fine but when I tested it on a true dual > > processor > > box it failed, I debugged and fixed the failure and now it seems to be > > stable > > (assuming my test harness is truly rigorous). > > You should probably model the algorithm in Relacy Race Detector: > > > http://groups.google.com/group/relacy/web > > > It will quickly find all types of bugs. It can even simulate every possible > thread interleaving, which will find all errors. Can you post the algorithm? > > > > > > I also once asked id anyone could dream up a good test harness to prove > > the > > code, but nobody seemed interested, I'd still like to see anyone's > > suggestions for a test shell because I may have missed something. > > > > Either way, the subject of read/write spinlocks is genuinely interesting > > and > > it seems neglected by current movers & shakers. > > FWIW, have you seen what is probably the most clever rw-spinlock out there? > Well, > IMHO that is: > > > http://groups.google.com/group/comp.programming.threads/browse_frm/thread/be3871ad661efa73 > > > I applied eventcount's to Joe's bakery algorithm in order to allow waiters > to block on a kernel waitset, but you can easily strip all of that out and > add simple backoff scheme in the wait loop. It's 100% fair, > starvation-free, and has wait-free fast-paths. It was invented by Joe Seigh > and presented on `comp.programming.threads' some years ago, IIRC. However, I > don't think it supports read or write recursion. I need to revisit the > algorithm. You can always add read/write recursion using thread local > data-structures. > > . >
From: Hugo gleaves on 21 Dec 2009 10:39 Although I said I can't post the core locking code, I can post the test shell src. I'd be delighted if anyone had suggestions about how to modify the test code so as to push the locking code to its limits. Curently the test code creates four writer threads and ten reader threads, the writer threads run a writer-test function and the reader threads run a reader-test function. These are similar, the tests execute a loop, getting the lock then repeatedly checking some shared vars. The vars should never take on unexpected values whilst a lock is held. The reader threads also briefly lock in write lock mode to further stress the code. The core testing consists of each thread ensuring that while it has a lock, the shared variables never take on any unexpected or inavlid value as would be the case if some thread "thought" it had the lock when technically it did not. In addition the threads all sleep for a short but random time, whilst the havey the lock and whilst the dont, further ensuring that no cyclic patters emerge that could mask problems. Ive run this test many times, soemtimes for hours and never seen any issue, after a number of iterations each thread ends and the test shell thread does a WaitForMultipleObjects on them. So at the end of the test shell main function, I can examine the state of the lock struct to see if it too looks OK. The overall design of the lock algorithms began life as a FSM and was defined in a spreadsheet as a state table with transitions etc, I pored over this for weeks before writing any code. Should I post the test code here as a straightforward message? Thx Hugh "Chris M. Thomasson" wrote: > "Hugo gleaves(a)hotmail.com>" <hugh<underbar> wrote in message > news:575741A2-0093-4630-A652-248B0B35C9C1(a)microsoft.com... > > Well I am aware of what is on the net, I did research this a few years ago > > and spent ages looking at code in many places. > > > > The problem definition is this: > > > > 1. Must be a spinlock, using Interlock operations only, for concurrency > > handling. > > 2. Must not use Mutex, Critical Sections, Semaphores etc. > > 3. Must supported nested lock acquisition. > > 4. Must support Read/Write modes. > > 5. Must work in multi-process settings , not just multithreaded settings > > in > > a singe process. > > For number 5, how are you handling the case when a thread dies while it has > acquired either read or write access? > > > > > > I found nothing at all on this subject, I have seen zero published on the > > subject of read/write spin locks. I have created an API that does this on > > Windows, the API also has a vicious test harness. Interestingly an early > > version appeared to work fine but when I tested it on a true dual > > processor > > box it failed, I debugged and fixed the failure and now it seems to be > > stable > > (assuming my test harness is truly rigorous). > > You should probably model the algorithm in Relacy Race Detector: > > > http://groups.google.com/group/relacy/web > > > It will quickly find all types of bugs. It can even simulate every possible > thread interleaving, which will find all errors. Can you post the algorithm? > > > > > > I also once asked id anyone could dream up a good test harness to prove > > the > > code, but nobody seemed interested, I'd still like to see anyone's > > suggestions for a test shell because I may have missed something. > > > > Either way, the subject of read/write spinlocks is genuinely interesting > > and > > it seems neglected by current movers & shakers. > > FWIW, have you seen what is probably the most clever rw-spinlock out there? > Well, > IMHO that is: > > > http://groups.google.com/group/comp.programming.threads/browse_frm/thread/be3871ad661efa73 > > > I applied eventcount's to Joe's bakery algorithm in order to allow waiters > to block on a kernel waitset, but you can easily strip all of that out and > add simple backoff scheme in the wait loop. It's 100% fair, > starvation-free, and has wait-free fast-paths. It was invented by Joe Seigh > and presented on `comp.programming.threads' some years ago, IIRC. However, I > don't think it supports read or write recursion. I need to revisit the > algorithm. You can always add read/write recursion using thread local > data-structures. > > . >
From: Chris M. Thomasson on 21 Dec 2009 12:01
"Hugo gleaves(a)hotmail.com>" <hugh<underbar> wrote in message news:697530AB-81F0-4B1B-9B4D-8E39B29236B9(a)microsoft.com... >A critical section is useless if the data to be locked is in shared memory, > shared by multiple processes. [...] FWIW, here is a very simple mutex implementation that only relies on atomic swap and can be used in shared memory: <pseudo-code typed in news reader> _________________________________________________________ struct mutex { LONG m_state; // = 0 HANDLE m_waitset; // auto-reset event void lock() { if (InterlockedExchange(&m_state, 1)) { while (InterlockedExchange(&m_state, 2)) { WaitForSingleObject(m_waitset, INFINITE); } } } void unlock() { if (InterlockedExchange(&m_state, 0) == 2) { SetEvent(m_waitset); } } }; _________________________________________________________ However, it's not robust... |