Hello, I have the need for a locking object that can provide shared and exclusive locks in much the same manner as the POSIX flock() function. A thread that acquires an exclusive lock has a guarantee that no other thread holds any locks. A thread that acquires a shared lock has a guarantee that no other thread holds an exclusive lock, though any number of other threads hold shared locks. My intuition tells me that this could be implemented in terms of an MVar somehow. (At least, I've used MVars for simple locks for quite some time.) But I can't quite figure out how. Any ideas? Thanks, -- John
John Goerzen wrote:
Hello,
I have the need for a locking object that can provide shared and exclusive locks in much the same manner as the POSIX flock() function.
A thread that acquires an exclusive lock has a guarantee that no other thread holds any locks.
A thread that acquires a shared lock has a guarantee that no other thread holds an exclusive lock, though any number of other threads hold shared locks.
My intuition tells me that this could be implemented in terms of an MVar somehow. (At least, I've used MVars for simple locks for quite some time.) But I can't quite figure out how. Any ideas?
Thanks,
-- John
STM or IO ? You need a count of shared locks "S", *Var Word32. To increase the count "S", you need to hold a mutex "E", *Var (). So (take mutex "E" >> increment "S" >> release "E") is the the combined operation. To decrease the count "S", you do not need to hold a mutex. (decrement "S"). By grabbing the mutex "E" and waiting for "S" to go to zero, you have acquired exclusive control. When you are done just release "E". -- Chris
Hi, "The little book of semaphones" (287 pages) is available at http://greenteapress.com/semaphores/ It has a slightly better solution that uses two mutexes and a count, see the Readers-writers problem, section 4.2 page 67 (pdf page 79). It also goes on to discuss fairness and starvation and writer (i.e. exclusive) priority. -- Chris Chris Kuklewicz wrote:
John Goerzen wrote:
Hello,
I have the need for a locking object that can provide shared and exclusive locks in much the same manner as the POSIX flock() function.
A thread that acquires an exclusive lock has a guarantee that no other thread holds any locks.
A thread that acquires a shared lock has a guarantee that no other thread holds an exclusive lock, though any number of other threads hold shared locks.
My intuition tells me that this could be implemented in terms of an MVar somehow. (At least, I've used MVars for simple locks for quite some time.) But I can't quite figure out how. Any ideas?
Thanks,
-- John
STM or IO ?
You need a count of shared locks "S", *Var Word32.
To increase the count "S", you need to hold a mutex "E", *Var (). So (take mutex "E" >> increment "S" >> release "E") is the the combined operation.
To decrease the count "S", you do not need to hold a mutex. (decrement "S").
By grabbing the mutex "E" and waiting for "S" to go to zero, you have acquired exclusive control. When you are done just release "E".
On Dec 28, 2005, at 11:14 AM, Chris Kuklewicz wrote:
John Goerzen wrote:
Hello,
I have the need for a locking object that can provide shared and exclusive locks in much the same manner as the POSIX flock() function.
A thread that acquires an exclusive lock has a guarantee that no other thread holds any locks.
A thread that acquires a shared lock has a guarantee that no other thread holds an exclusive lock, though any number of other threads hold shared locks.
My intuition tells me that this could be implemented in terms of an MVar somehow. (At least, I've used MVars for simple locks for quite some time.) But I can't quite figure out how. Any ideas?
Thanks,
-- John
STM or IO ?
You need a count of shared locks "S", *Var Word32.
To increase the count "S", you need to hold a mutex "E", *Var (). So (take mutex "E" >> increment "S" >> release "E") is the the combined operation.
To decrease the count "S", you do not need to hold a mutex. (decrement "S").
By grabbing the mutex "E" and waiting for "S" to go to zero, you have acquired exclusive control. When you are done just release "E".
-- Chris
This seems fine for STM because you can just retry until count is 0, but I don't know of a good way to wait for an MVar to have a particular value (I assume busy-wait isn't what you have in mind). You'll probably need an additional MVar that exclusive lockers "take" to let them block. Then you need to be sure that this MVar is filled when count goes to 0 and empty when count goes above zero. Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
STM or IO ?
You need a count of shared locks "S", *Var Word32.
To increase the count "S", you need to hold a mutex "E", *Var (). So (take mutex "E" >> increment "S" >> release "E") is the the combined operation.
To decrease the count "S", you do not need to hold a mutex. (decrement "S").
By grabbing the mutex "E" and waiting for "S" to go to zero, you have acquired exclusive control. When you are done just release "E".
-- Chris
This seems fine for STM because you can just retry until count is 0, but I don't know of a good way to wait for an MVar to have a particular value (I assume busy-wait isn't what you have in mind). You'll probably need an additional MVar that exclusive lockers "take" to let them block. Then you need to be sure that this MVar is filled when count goes to 0 and empty when count goes above zero.
Rob Dockins
You are right. I spent too much time teaching myself STM, and I defaulted to those primatives. But STM, wrapped in small pieces, makes for interesting IO commands (untested): createLocks = do me <- newMVar () tv <- atomically $ newTVar (0::Word32) return (me,tv) waitForZero :: (Num a, Ord a) => (TVar a) -> IO () waitForZero tv = atomically $ do v <- readTVar tv when (v>0) retry takeExclusive :: MVar () -> TVar Word 32 -> IO () takeExclusive me tv = takeMVar me >> waitForZero tv releaseExclusive me = putMVar me () takeShared :: MVar () -> TVar Word32 -> IO () takeShared me tv = withMVar me $ atomically $ do v <- readTVar tv writeTVar tv (v+1) releaseShared tv = atomically $ do v <- readTVar tv writeTVar tv (v-1) So you don't need much STM to have the benefit of retry. Also: The ability to put (STM a) or (IO a) into a TVar or MVar makes for wonderful cross thread solutions to some of the standard synchronization problems. -- Chris Kuklewicz
On Wed, Dec 28, 2005 at 05:28:28PM +0000, Chris Kuklewicz wrote:
But STM, wrapped in small pieces, makes for interesting IO commands (untested):
waitForZero :: (Num a, Ord a) => (TVar a) -> IO () waitForZero tv = atomically $ do v <- readTVar tv when (v>0) retry
This function is rather useless in IO - you will get race conditions. That's what you get for leaving the STM wonderland ;-) Best regards Tomasz -- I am searching for a programmer who is good at least in some of [Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland
On Dec 28, 2005, at 1:38 PM, Tomasz Zielonka wrote:
On Wed, Dec 28, 2005 at 05:28:28PM +0000, Chris Kuklewicz wrote:
But STM, wrapped in small pieces, makes for interesting IO commands (untested):
waitForZero :: (Num a, Ord a) => (TVar a) -> IO () waitForZero tv = atomically $ do v <- readTVar tv when (v>0) retry
This function is rather useless in IO - you will get race conditions. That's what you get for leaving the STM wonderland ;-)
Actually, I think it works in the particular instance given of constructing read-write locks because the call to waitForZero is guarded by a mutex. But it would certainly be easy to introduce a race condition using constructs like this. Given the alternatives {use STM fully, use STM some, don't use STM}, I would have a hard time justifying the "use STM some" alternative (at least for new programs). If you are OK with introducing a dependency on STM, why not go whole hog? Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
participants (4)
-
Chris Kuklewicz -
John Goerzen -
Robert Dockins -
Tomasz Zielonka