Shared/Exclusive Locks

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Shared/Exclusive Locks

John Goerzen-3
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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Shared/Exclusive Locks

haskell-2
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Shared/Exclusive Locks

haskell-2
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".
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Shared/Exclusive Locks

Bugzilla from robdockins@fastmail.fm
In reply to this post by haskell-2

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



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Shared/Exclusive Locks

haskell-2

>>
>> 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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Shared/Exclusive Locks

Tomasz Zielonka
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Shared/Exclusive Locks

Bugzilla from robdockins@fastmail.fm

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



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe