From mboxrd@z Thu Jan 1 00:00:00 1970 To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> In-reply-to: Your message of "Fri, 25 Feb 2011 09:37:39 +0100." <9e5ef05b5cfedd0faa831cc7c0d57f74@plan9.cs.bell-labs.com> References: <11da45046fa8267e7445128ed00724cd@ladd.quanstro.net> <24bb48f61c5eab87a133b82a9ef32474@coraid.com> <2808a9fa079bea86380a8d52be67b980@coraid.com> <40925e8f64489665bd5bd6ca743400ea@coraid.com> <9e5ef05b5cfedd0faa831cc7c0d57f74@plan9.cs.bell-labs.com> From: Bakul Shah Date: Fri, 25 Feb 2011 01:18:14 -0800 Message-Id: <20110225091814.3387EB832@mail.bitblocks.com> Subject: Re: [9fans] sleep/wakeup bug? Topicbox-Message-UUID: b49993f8-ead6-11e9-9d60-3106f5b1d025 On Fri, 25 Feb 2011 09:37:39 +0100 Sape Mullender wrote: > I suppose the use of counting semaphores in sleep/wakeup could > help in cases like this (but I'm sure there are still plenty of > other scenarios where they might not help). The value of the > semaphore would represent something like "number of things to > do", so acquire(sema) would (atomically) wait until the value > of sema is greater than zero, then (using compare&swap, or > doing the whole thing inside an ilock) decrement the semaphore > and continue. > Release(sema) will (atomically) increment the semaphore and, if the > old value was zero, wake up any waiters. > > Now, at first glance that looks like a vast improvement over sleep/ > wakeup, but *inside* acquire and release, you'd still have sleep/wakeup > and you'd still run the risk of waking up just when something else > managed to grab the semaphore, or waking up something that hasn't > actually gone to sleep yet. > > So, I think you can think of semaphores as a wrapper for sleep/wakeup > that can be used in some case to make sure that you can indeed safely > do a free() of some memory (this was, I think what started the whole > discussion). wait(sema) & signal(sema) in either order would do proper synchronization. Not the case with sleep/wakeup -- they are cheaper though. > It's taken a long time to get sleep/wakeup bugfree in Plan 9 and > some of the greatest minds in code verification (formerly at Bell Labs) > have been called upon to help get it right. > > Russ is perfectly correct in the explanations below and it's a good > exercise to read through it. This stuff is really tricky. Many > optimization, all of them seemingly correct, failed because of subtle > race conditions, some of them involving three or more processes. Is it inherently tricky? Aren't semaphores easier to reason about and get right?