By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
428,742 Members | 1,570 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,742 IT Pros & Developers. It's quick & easy.

Djikstra counting semaphore in c# for your review

P: n/a
Here is the link. If you find an issue or think of a feature, please post a
reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP
Nov 16 '05 #1
Share this Question
Share on Google+
32 Replies


P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please post a reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP


I'm still checking further, but here a two instant remarks:

* The name is Dijkstra, not Djikstra (I'm dutch speaking, so I know why)
* I would make the class Semaphore sealed.

I'm going to check the rest later.

Cheers,
---
Tom Tempelaere
Nov 16 '05 #2

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please post a reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP


William,

About the Count property. I think this is a dangerous property to use. The
count is not guaranteed to be same when acquiring after checking the count.
It might be an optimization in some cases, but I don't see the use for it.

So perhaps then you shouldn't lock in the implementation of Count. What do
you think?

Cheers,
---
Tom Tempelaere
Nov 16 '05 #3

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please post a reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP


William,

Your AcquireAll method tries to acquire each slot seperately. Perhaps you
could optimize and acquire all slots available each iteration until you
acquired all slots.

Plus the millisecondsTimeout is deceiving, because the max time could be
( maxSlots * millisecondsTimeout )
to acquire all slots.

I noticed that there exists a
Release( int n )
method but not an
Acquire( int n )
method. Is this the intention?

If you would write the Acquire( int n ) method, you could implement
Acquire() as Acquire( 1 )
and
AcquireAll() as Acquire( maxCount )

Cheers,
---
Tom Tempelaere
Nov 16 '05 #4

P: n/a
"TT (Tom Tempelaere)" <_N_0SPA|/\|t*******@hotmail.com|/\|APS0_N_> wrote in
message news:v1**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please
post a
reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP

William,

About the Count property. I think this is a dangerous property to use. The
count is not guaranteed to be same when acquiring after checking the

count. It might be an optimization in some cases, but I don't see the use for it.

So perhaps then you shouldn't lock in the implementation of Count. What do
you think?


Perhaps it is necessary to introduce memory barriers so the count property
can't be optimized too heavily (ie inlining). Maybe making count volatile
would make the locking unnecessary...

---
Tom Tempelaere
Nov 16 '05 #5

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please post a reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP


William,

In the Acquire method there is a catch handler in which you Pulse. You don't
do that in the AcquireAll method. Is this the intention?

Cheers,
---
Tom Tempelaere
Nov 16 '05 #6

P: n/a
> Perhaps it is necessary to introduce memory barriers so the count property
can't be optimized too heavily (ie inlining). Maybe making count volatile
would make the locking unnecessary...


The lock and the Interlocked do introduce memory barriers. I don't see
current implementation as a performance issue. I still need the lock in the
other methods, so updating the count inside the lock seems like a good place
to leverage that lock. The Interlocked.CompareExchange only makes sure I
read the actual value atomically so it is like a mini-lock as it also has
mem barrier and deals with multi-processor cache issue. Volatile may also
work, not sure. I think I still want the increments and decrements to be
done inside the syncRoot lock, so also using volatile may just be overkill.
Other thoughts welcome.

--
William Stacey, MVP
Nov 16 '05 #7

P: n/a
> * The name is Dijkstra, not Djikstra (I'm dutch speaking, so I know
why)

Thanks Tom, you are correct. Thats for the update, I saw it both ways on
the INET. I will make the change. Cheers!

--
William Stacey, MVP
Nov 16 '05 #8

P: n/a
> About the Count property. I think this is a dangerous property to use. The
count is not guaranteed to be same when acquiring after checking the count. It might be an optimization in some cases, but I don't see the use for it.


Yes and no I think. I had thought the same thing while implementing.
However I look at like a hint, such as the count of a circular buffer. It
is only valid the instant you check it. Other threads could change this
directly after you "get" it. However the count is valid for that instant
and you never know how someone may want to use that. Maybe if only for perf
monitoring, or gui progress bar, etc.

--
William Stacey, MVP
Nov 16 '05 #9

P: n/a
> Your AcquireAll method tries to acquire each slot seperately. Perhaps you
could optimize and acquire all slots available each iteration until you
acquired all slots.
Probably. I just wanted to leverage existing method instead of writing more
duplicate logic.
Plus the millisecondsTimeout is deceiving, because the max time could be
( maxSlots * millisecondsTimeout )
to acquire all slots.
Yes, that is a side-effect. You could do some time calcs to get around the
right tot ms, but that starts to get messy - but is very doable.
I noticed that there exists a
Release( int n )
method but not an
Acquire( int n )
method. Is this the intention?


Yes. I looked at a lot of semaphore examples and none of them had
Acquire(int n). I guess the idea is one thread will only typically acquire
one slot. If you need more, you call twice, etc. The AcquireAll is just a
helper method if you need to acquireall for some reason to block others out
for awhile.

After looking at this again, however, I did discover an issue. The
AcquireAll locks the lock and loops inside. This would effectively block
other threads from doing a Release. I think removing the lock{} gives the
intended effect as the call to Acquire does its own locking (think this was
a carryover from another way I tried to implement that and did not remove
it.)

I will still think about the millisecond issue. This may be better handled
with documentation then updating the code? The intention is to provide some
safety valve instead of blocking forever.

--
William Stacey, MVP
Nov 16 '05 #10

P: n/a
"TT (Tom Tempelaere)" <_N_0SPA|/\|t*******@hotmail.com|/\|APS0_N_> wrote in
message news:4w**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please
post a
reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm
--
William Stacey, MVP

[...] Plus the millisecondsTimeout is deceiving, because the max time could be
( maxSlots * millisecondsTimeout )
to acquire all slots.

I noticed that there exists a
Release( int n )
method but not an
Acquire( int n )
method. Is this the intention?

If you would write the Acquire( int n ) method, you could implement
Acquire() as Acquire( 1 )
and
AcquireAll() as Acquire( maxCount )


Here's my try to implement Acquire( int nrSlots ). Warning: it doesn't look
very efficient though :D.

public sealed class Semaphore
{
private int currentCount;
private readonly int maxCount;
private readonly object acquireLock = new object();
private readonly object starvationLock = new object();

public Semaphore( int currentCount, int maxCount )
{
Debug.Assert (
maxCount >= 1 &&
currentCount >= 0 &&
currentCount <= maxCount
);
this.currentCount = currentCount;
this.maxCount = maxCount;
}

public Semaphore( int maxCount )
: this( maxCount, maxCount )
{}

public bool Acquire()
{
return _Acquire_N( 1, Timeout.Infinite );
}

public bool Acquire( int timeoutMs )
{
return _Acquire_N( 1, timeoutMs );
}

public bool AcquireAll()
{
return _Acquire_N( maxCount, Timeout.Infinite );
}

public bool AcquireAll( int overallTimeoutMs )
{
return _Acquire_N( maxCount, overallTimeoutMs );
}

public bool Acquire_N( int requestedCount )
{
return _Acquire_N( requestedCount, Timeout.Infinite );
}

public bool Acquire_N( int requestedCount, int overallTimeoutMs )
{
return _Acquire_N( requestedCount, overallTimeoutMs );
}

private bool _Acquire_N( int requestedCount, int overallTimeoutMs )
{
Debug.Assert (
( requestedCount > 0 ) &&
( overallTimeoutMs > 0 || ( overallTimeoutMs == Timeout.Infinite ) )
);

IAcquireTimeoutTracker acqTimeoutTracker = ( overallTimeoutMs > 0 ) ?
(IAcquireTimeoutTracker) new RegularTimeoutTracker( overallTimeoutMs ) :
new InfiniteTimeoutTracker();
int acquiredCount = 0;

lock( acquireLock )
{
while( acquiredCount != requestedCount )
{
while( currentCount == 0 )
try
{
if( acqTimeoutTracker.HasElapsed ||
!Monitor.Wait( acquireLock, acqTimeoutTracker.RemainingWaitTime ) )
{
if( acquiredCount > 0 )
Release( acquiredCount );
return false;
}
}
catch
{
if( acquiredCount > 0 )
Release( acquiredCount );
Monitor.Pulse( acquireLock );
throw;
}

int targetCount = Math.Min( (requestedCount - acquiredCount),
currentCount );
acquiredCount += targetCount;
currentCount -= targetCount;

if( currentCount == 0 )
lock( starvationLock )
Monitor.PulseAll( starvationLock );
}
return true;
}
}

internal interface IAcquireTimeoutTracker
{
bool HasElapsed {
get;
}
int RemainingWaitTime {
get;
}
}
internal class InfiniteTimeoutTracker : IAcquireTimeoutTracker
{
public bool HasElapsed {
get {
return false;
}
}
public int RemainingWaitTime {
get {
return Timeout.Infinite;
}
}
}
internal class RegularTimeoutTracker : IAcquireTimeoutTracker
{
DateTime deadline;
TimeSpan timeout;
public RegularTimeoutTracker( int timeoutMs )
{
deadline = DateTime.Now + TimeSpan.FromMilliseconds( timeoutMs );
}
public bool HasElapsed {
get {
return (timeout = deadline - DateTime.Now) <= TimeSpan.Zero;
}
}
public int RemainingWaitTime {
get {
return timeout.Milliseconds;
}
}
}

public bool Release( int count )
{
// release implementation
return true;
}

// ...
}

Cheers,
---
Tom Tempelaere
Nov 16 '05 #11

P: n/a
"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:R4**********************@phobos.telenet-ops.be...
[...]
public sealed class Semaphore
{ [...] private bool _Acquire_N( int requestedCount, int overallTimeoutMs )
{
Debug.Assert (
( requestedCount > 0 ) &&
( overallTimeoutMs > 0 || ( overallTimeoutMs == Timeout.Infinite ) )
);

IAcquireTimeoutTracker acqTimeoutTracker = ( overallTimeoutMs > 0 ) ?
(IAcquireTimeoutTracker) new RegularTimeoutTracker( overallTimeoutMs ) : new InfiniteTimeoutTracker();
int acquiredCount = 0;

lock( acquireLock )
{ while( acquiredCount != requestedCount )
This would better be a do-while loop instead of a while loop of course
(albeit it just a small optimization).
{
while( currentCount == 0 )
try
{
if( acqTimeoutTracker.HasElapsed ||
!Monitor.Wait( acquireLock, acqTimeoutTracker.RemainingWaitTime ) ) {
if( acquiredCount > 0 )
Release( acquiredCount );
return false;
}
}
catch
{
if( acquiredCount > 0 )
Release( acquiredCount );
Monitor.Pulse( acquireLock );
throw;
}

int targetCount = Math.Min( (requestedCount - acquiredCount),
currentCount );
acquiredCount += targetCount;
currentCount -= targetCount;

if( currentCount == 0 )
lock( starvationLock )
Monitor.PulseAll( starvationLock );
}
return true;
}
} [...] }


Cheers,
---
Tom Tempelaere
Nov 16 '05 #12

P: n/a
Very observant Tom. I can tell you are really studying the logic and
possible thread involved (as there are many in most locking primitives.)
However, this was another reason why I leveraged existing Acquire method.
If exception happens, the pulse is handled in Acquire and we just back-out
any slots we Acquired so far and throw the exception back to caller. The
release does not block so we should be able to release any slots we own
without an issue (except for slight lock issue below.)

However, you did remind me to bring up a point I wanted to make in the doco
and not sure if I did. It is possible to get an Interrupt or Abort
exception when *acquiring the monitor, even without a Wait(). A
Monitor.Enter() (which is what lock() starts with) could also throw
exception if the thread is Interrupted or Aborted directly before the
Enter(). I did not see any implementations that accounted for this slight
possibility either, and it would add more junk to the code, but I will have
to look over everything again with this specific issue in mind. Good
thoughts. Keep em coming. :-) Cheers.

--
William Stacey, MVP

"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:%1**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please
post a
reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP
William,

In the Acquire method there is a catch handler in which you Pulse. You

don't do that in the AcquireAll method. Is this the intention?

Cheers,
---
Tom Tempelaere


Nov 16 '05 #13

P: n/a
Instead of more classes for timeouts, here is what I came up with (still
need to test.) I still need to look at your other code. Cheers!

public bool AcquireAll(int millisecondsTimeout)
{
int slotsGot = 0;
int elapsedMS = 0;
DateTime start = DateTime.Now;
int timeout = millisecondsTimeout;
for (int i = 0; i < maxCount; i++)
{
try
{
if (! Acquire(timeout) )
{
// Could not acquire all slots, release any we may already have got.
if ( slotsGot > 0 )
Release(slotsGot);
return false;
}
else
{
elapsedMS = (int)((TimeSpan)(DateTime.Now - start)).TotalMilliseconds;
timeout = millisecondsTimeout - elapsedMS; // Next wait will be a
smaller timeout.
if ( timeout < 0 )
timeout = 0; // Next Acquire will return false if we have to wait;
slotsGot++; // If we get all remaining slots with no timeout, we just
keep going.
}
}
catch
{
// Catch any exception during Acquire wait.
if ( slotsGot > 0 )
Release(slotsGot);
throw;
}
} // end for.
// Count is not zero, so notify any/all starvation consumers.
lock(starvationLock) { Monitor.PulseAll(starvationLock); }
return true;
}

--
William Stacey, MVP

"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:R4**********************@phobos.telenet-ops.be...
"TT (Tom Tempelaere)" <_N_0SPA|/\|t*******@hotmail.com|/\|APS0_N_> wrote in message news:4w**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please
post
a
reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm
--
William Stacey, MVP


[...]
Plus the millisecondsTimeout is deceiving, because the max time could be
( maxSlots * millisecondsTimeout )
to acquire all slots.

I noticed that there exists a
Release( int n )
method but not an
Acquire( int n )
method. Is this the intention?

If you would write the Acquire( int n ) method, you could implement
Acquire() as Acquire( 1 )
and
AcquireAll() as Acquire( maxCount )


Here's my try to implement Acquire( int nrSlots ). Warning: it doesn't

look very efficient though :D.

public sealed class Semaphore
{
private int currentCount;
private readonly int maxCount;
private readonly object acquireLock = new object();
private readonly object starvationLock = new object();

public Semaphore( int currentCount, int maxCount )
{
Debug.Assert (
maxCount >= 1 &&
currentCount >= 0 &&
currentCount <= maxCount
);
this.currentCount = currentCount;
this.maxCount = maxCount;
}

public Semaphore( int maxCount )
: this( maxCount, maxCount )
{}

public bool Acquire()
{
return _Acquire_N( 1, Timeout.Infinite );
}

public bool Acquire( int timeoutMs )
{
return _Acquire_N( 1, timeoutMs );
}

public bool AcquireAll()
{
return _Acquire_N( maxCount, Timeout.Infinite );
}

public bool AcquireAll( int overallTimeoutMs )
{
return _Acquire_N( maxCount, overallTimeoutMs );
}

public bool Acquire_N( int requestedCount )
{
return _Acquire_N( requestedCount, Timeout.Infinite );
}

public bool Acquire_N( int requestedCount, int overallTimeoutMs )
{
return _Acquire_N( requestedCount, overallTimeoutMs );
}

private bool _Acquire_N( int requestedCount, int overallTimeoutMs )
{
Debug.Assert (
( requestedCount > 0 ) &&
( overallTimeoutMs > 0 || ( overallTimeoutMs == Timeout.Infinite ) )
);

IAcquireTimeoutTracker acqTimeoutTracker = ( overallTimeoutMs > 0 ) ?
(IAcquireTimeoutTracker) new RegularTimeoutTracker( overallTimeoutMs ) : new InfiniteTimeoutTracker();
int acquiredCount = 0;

lock( acquireLock )
{
while( acquiredCount != requestedCount )
{
while( currentCount == 0 )
try
{
if( acqTimeoutTracker.HasElapsed ||
!Monitor.Wait( acquireLock, acqTimeoutTracker.RemainingWaitTime ) ) {
if( acquiredCount > 0 )
Release( acquiredCount );
return false;
}
}
catch
{
if( acquiredCount > 0 )
Release( acquiredCount );
Monitor.Pulse( acquireLock );
throw;
}

int targetCount = Math.Min( (requestedCount - acquiredCount),
currentCount );
acquiredCount += targetCount;
currentCount -= targetCount;

if( currentCount == 0 )
lock( starvationLock )
Monitor.PulseAll( starvationLock );
}
return true;
}
}

internal interface IAcquireTimeoutTracker
{
bool HasElapsed {
get;
}
int RemainingWaitTime {
get;
}
}
internal class InfiniteTimeoutTracker : IAcquireTimeoutTracker
{
public bool HasElapsed {
get {
return false;
}
}
public int RemainingWaitTime {
get {
return Timeout.Infinite;
}
}
}
internal class RegularTimeoutTracker : IAcquireTimeoutTracker
{
DateTime deadline;
TimeSpan timeout;
public RegularTimeoutTracker( int timeoutMs )
{
deadline = DateTime.Now + TimeSpan.FromMilliseconds( timeoutMs );
}
public bool HasElapsed {
get {
return (timeout = deadline - DateTime.Now) <= TimeSpan.Zero;
}
}
public int RemainingWaitTime {
get {
return timeout.Milliseconds;
}
}
}

public bool Release( int count )
{
// release implementation
return true;
}

// ...
}

Cheers,
---
Tom Tempelaere


Nov 16 '05 #14

P: n/a
"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:R4**********************@phobos.telenet-ops.be...
[...]
Plus the millisecondsTimeout is deceiving, because the max time could be
( maxSlots * millisecondsTimeout )
to acquire all slots.
Here's my try to implement Acquire( int nrSlots ). Warning: it doesn't look very efficient though :D.


Another issue is that lock could take some time and that should counted too
to check for timeout. Modifications are inside the code for _Acquire_N &
RegularTimeoutTracker.
public sealed class Semaphore
{
private int currentCount;
private readonly int maxCount;
private readonly object acquireLock = new object();
private readonly object starvationLock = new object();

public Semaphore( int currentCount, int maxCount )
{
Debug.Assert (
maxCount >= 1 &&
currentCount >= 0 &&
currentCount <= maxCount
);
this.currentCount = currentCount;
this.maxCount = maxCount;
}

public Semaphore( int maxCount )
: this( maxCount, maxCount )
{}

public bool Acquire()
{
return _Acquire_N( 1, Timeout.Infinite );
}

public bool Acquire( int timeoutMs )
{
return _Acquire_N( 1, timeoutMs );
}

public bool AcquireAll()
{
return _Acquire_N( maxCount, Timeout.Infinite );
}

public bool AcquireAll( int overallTimeoutMs )
{
return _Acquire_N( maxCount, overallTimeoutMs );
}

public bool Acquire_N( int requestedCount )
{
return _Acquire_N( requestedCount, Timeout.Infinite );
}

public bool Acquire_N( int requestedCount, int overallTimeoutMs )
{
return _Acquire_N( requestedCount, overallTimeoutMs );
}

private bool _Acquire_N( int requestedCount, int overallTimeoutMs )
{
Debug.Assert (
( requestedCount > 0 ) &&
( overallTimeoutMs > 0 || ( overallTimeoutMs == Timeout.Infinite ) )
);

IAcquireTimeoutTracker acqTimeoutTracker = ( overallTimeoutMs > 0 ) ?
(IAcquireTimeoutTracker) new RegularTimeoutTracker( overallTimeoutMs ) :
new InfiniteTimeoutTracker();
int acquiredCount = 0;

if( Monitor.TryEnter( acquireLock, acqTimeoutTracker.RemainingWaitTime ) )
try
{
do
{
while( currentCount == 0 )
if( acqTimeoutTracker.HasElapsed ||
!Monitor.Wait( acquireLock, acqTimeoutTracker.RemainingWaitTime ) )
throw new TimeoutException();

int targetCount = Math.Min( (requestedCount - acquiredCount),
currentCount );
acquiredCount += targetCount;
currentCount -= targetCount;

if( currentCount == 0 )
lock( starvationLock )
Monitor.PulseAll( starvationLock );
}
while( acquiredCount != requestedCount );
return true;
}
catch( Exception e )
{
if( acquiredCount > 0 )
Release( acquiredCount );
Monitor.Pulse( acquireLock );
if( !(e is TimeoutException) )
throw;
}
finally
{
Monitor.Exit( acquireLock );
}

return false;
}

private class TimeoutException : Exception
{
public override string Message {
get {
return "Waiting timeout";
}
}
}

internal interface IAcquireTimeoutTracker
{
bool HasElapsed {
get;
}
int RemainingWaitTime {
get;
}
}
internal class InfiniteTimeoutTracker : IAcquireTimeoutTracker
{
public bool HasElapsed {
get {
return false;
}
}
public int RemainingWaitTime {
get {
return Timeout.Infinite;
}
}
}
internal class RegularTimeoutTracker : IAcquireTimeoutTracker
{
DateTime deadline;
TimeSpan timeout;
public RegularTimeoutTracker( int timeoutMs )
{
this.deadline = DateTime.Now + TimeSpan.FromMilliseconds( timeoutMs );
this.timeout = deadline - DateTime.Now;
}
public bool HasElapsed {
get {
return (timeout = deadline - DateTime.Now) <= TimeSpan.Zero;
}
}
public int RemainingWaitTime {
get {
Debug.Assert (
timeout.Milliseconds > 0
);
return timeout.Milliseconds;
}
}
}

public bool Release( int count )
{
return true;
}
}
Looks better. Only starvation isn't checked for timeout.

Tom T.
Nov 16 '05 #15

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please post a reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP


I think you should forbid infinite timeouts, because in some patterns there
may be deadlocks. For instance if 2 clients (read: threads) of the semaphore
execute AcquireAll, and another (third) client already has one or a few
slots acquired. Thread 1 gets half the remainig slots and Thread2 gets the
other half. Then the third client releases but it wont have any effect.
Thread 1 & Thread 2 will never release their half so there is a deadlock.

I don't know if you should take that into account but it is possible.

---
Tom Tempelaere
Nov 16 '05 #16

P: n/a
What you say is true. However this patten is used by other lock primitives
like Monitor, where it is also possible to dead-lock yourself on infinite
timeout. As this is meant to be general and flexible (like Monitor), this
is an issue for the user to decide and program around - hence the timeout
overloads. If you have one producer and one consumer (binary sem for
example), this may be the exact behavior you want. You may want to block
forever until something is in a queue for example. Pooling on a timeout
really just brings you back to the same issue - what do you do if you
timeout? In most cases, you just wait again as you never know when you will
get signaled. If you truly want to wait only N ms, then you have that
option. This is always one of the challenges with threading, deciding how
long is long enouph for timeouts and then what to do when you do timeout? I
see your point, however there is not really a good solution to this imo -
just something each program will need to decide for itself. Naturally, the
control program can also Interrupt the threads, which is handled here
correctly I think. Cheers!

--
William Stacey, MVP

"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:fR**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please
post a
reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP
I think you should forbid infinite timeouts, because in some patterns

there may be deadlocks. For instance if 2 clients (read: threads) of the semaphore execute AcquireAll, and another (third) client already has one or a few
slots acquired. Thread 1 gets half the remainig slots and Thread2 gets the
other half. Then the third client releases but it wont have any effect.
Thread 1 & Thread 2 will never release their half so there is a deadlock.

I don't know if you should take that into account but it is possible.

---
Tom Tempelaere


Nov 16 '05 #17

P: n/a
I suppose one way to head off this specific issue is with another lock (i.e.
acquireAllLock) in the AcquireAll method. Allow only one thread at a time
to enter passed the acquireAllLock exclusive lock. This gets you a little
further, but is not a complete solution as the first AcquireAll() could
still block forever waiting on a Release() that never comes as the owner is
blocked for some reason. At some point, there is only so much you can do.
You can provide a tool, but you can't prevent the user from hitting
themselfs in the head with it when your not looking. Cheers.

--
William Stacey, MVP

"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:Oj**************@tk2msftngp13.phx.gbl...
What you say is true. However this patten is used by other lock primitives like Monitor, where it is also possible to dead-lock yourself on infinite
timeout. As this is meant to be general and flexible (like Monitor), this
is an issue for the user to decide and program around - hence the timeout
overloads. If you have one producer and one consumer (binary sem for
example), this may be the exact behavior you want. You may want to block
forever until something is in a queue for example. Pooling on a timeout
really just brings you back to the same issue - what do you do if you
timeout? In most cases, you just wait again as you never know when you will get signaled. If you truly want to wait only N ms, then you have that
option. This is always one of the challenges with threading, deciding how
long is long enouph for timeouts and then what to do when you do timeout? I see your point, however there is not really a good solution to this imo -
just something each program will need to decide for itself. Naturally, the control program can also Interrupt the threads, which is handled here
correctly I think. Cheers!

--
William Stacey, MVP

"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:fR**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please post
a
reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP


I think you should forbid infinite timeouts, because in some patterns

there
may be deadlocks. For instance if 2 clients (read: threads) of the

semaphore
execute AcquireAll, and another (third) client already has one or a few
slots acquired. Thread 1 gets half the remainig slots and Thread2 gets

the other half. Then the third client releases but it wont have any effect.
Thread 1 & Thread 2 will never release their half so there is a deadlock.
I don't know if you should take that into account but it is possible.

---
Tom Tempelaere


Nov 16 '05 #18

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:eK**************@TK2MSFTNGP11.phx.gbl...
I suppose one way to head off this specific issue is with another lock (i.e. acquireAllLock) in the AcquireAll method. Allow only one thread at a time
to enter passed the acquireAllLock exclusive lock. This gets you a little
further, but is not a complete solution as the first AcquireAll() could
still block forever waiting on a Release() that never comes as the owner is blocked for some reason. At some point, there is only so much you can do.
You can provide a tool, but you can't prevent the user from hitting
themselfs in the head with it when your not looking. Cheers.

--
William Stacey, MVP


I think that it should indeed be the responsability of the user of the
semaphore object to avoid such situations.

Tom T.


Nov 16 '05 #19

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:eK**************@TK2MSFTNGP11.phx.gbl...
I suppose one way to head off this specific issue is with another lock (i.e. acquireAllLock) in the AcquireAll method. Allow only one thread at a time
to enter passed the acquireAllLock exclusive lock. This gets you a little
further, but is not a complete solution as the first AcquireAll() could
still block forever waiting on a Release() that never comes as the owner is blocked for some reason. At some point, there is only so much you can do.
You can provide a tool, but you can't prevent the user from hitting
themselfs in the head with it when your not looking. Cheers.

--
William Stacey, MVP


I think that it should indeed be the responsability of the user of the
semaphore object to avoid such situations.

Tom T.


Nov 16 '05 #20

P: n/a
Hello!

Could you give me an example (or two) of a scenario, where this kind of
class would be usefull?

This is probably the most interesting thread for days! :-)

--
venlig hilsen / with regards
anders borum
--
Nov 16 '05 #21

P: n/a
1) Blocking Circular queue. Create two semaphores, one for free elements
and one for used elements. The Enqueue method grabs one slot from the free
Sem or blocks until a slot is available. The Dequeue method grabs one slot
from the used sem or blocks until a slot is available. This can make the
implementation kinda clean, but I have come to the conclusion that this is
probably not the best way to implement a blocking CQ. To do it right
requires another syncLock to protect the buffer in the middle and any other
counters. So you can end up with 5 locks being taken. One for sem enter.
One to pulse the other sem. One for syncLock in the middle, One for other
sem release and one to pulse the other sem. A two lock monitor
implementation is probably better. Actually, at the end of the day, a one
lock queue is very clean and probably better for most needs.

2) Network resource counting is a good example. Novell used a Semaphore for
years (and may still) to restrict/count the number of logins to the server.
You could use the same method for any shared service you can think of.

3) Any access to some shared data structure that you want to limit to some
count. Say you only want 5 threads to access something or only want 3
instances of your program. The Semaphore does not provide mutual exclusion
(except a binary semaphore does) so others lock(s) need to taken in right
places.

4) Limit number of email messages in an inbox on a server or local client or
limit number of SMTP server or Web clients that can "hit" the service at the
same time - others will block.

I will try to think of some more, but you could probably come up with at
least 10 new ones after thinking about 1-4 above.

--
William Stacey, MVP

"Anders Borum" <a@b.dk> wrote in message
news:Om**************@tk2msftngp13.phx.gbl...
Hello!

Could you give me an example (or two) of a scenario, where this kind of
class would be usefull?

This is probably the most interesting thread for days! :-)

--
venlig hilsen / with regards
anders borum
--


Nov 16 '05 #22

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please post a reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP

Any updates yet?
---
Tom Tempelaere
Nov 16 '05 #23

P: n/a
Update to the code? I did post a few changes after the first post. Let me
know what updates you would like to see.

--
William Stacey, MVP

"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:JD**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:OD**************@TK2MSFTNGP09.phx.gbl...
Here is the link. If you find an issue or think of a feature, please
post a
reply or send an email. Cheers!
http://www.mvptools.com/doco/csharp/...redjikstra.htm

--
William Stacey, MVP

Any updates yet?
---
Tom Tempelaere


Nov 16 '05 #24

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:eI**************@TK2MSFTNGP12.phx.gbl...
Update to the code? I did post a few changes after the first post. Let me know what updates you would like to see.
--
William Stacey, MVP


I forgot to check the link before posting, I see that you already made some
changes. Woops.

Have you already done some tests under stress? A working project that uses
the semaphore to demonstrate that it works ...

The code-documentation in AcquireAll, just before the lock on starvationLock
is a typo: it sais "... is not zero ..." but I think it should read "... is
now zero ...".

I think you should introduce Debug.Assert's at specific places for several
reasons, which is my opinion and perhaps a question of style (or QOI).
* clients of your library made a mistake in using your class/lib
* you made a mistake (aka bug) when making your class/lib
* when you refactor these can prove invaluable (I say this from experience)
* to highlight some pre-conditions or post-conditions. It looks like proof
then, and they will probably never even trigger. It helps the reviewer of
the library and yourself when you return back to the project after a long
time.
* in some libraries (eg in-house) you would not throw exceptions when
receiving bad parameters (or a bad combination), just assert. When debugging
the developer can use the code as a tool to know what he did wrong in using
the library. He should correct things if the asserts trigger and afterwards
the assert will no longer trigger. In that case the checking + throwing code
is no longer necessary and becomes code bloat. On the other hand in some
circumstances you would prefer to throw (for stability reasons), it all
depends on the type of library and who you are writing it for. MFC library
is a good example, it has a lot of asserts. A quick count of "ASSERT" (match
case, match whole word) in code of vc6 mfc library gave 5618 occurences.
Just to mention.
* Asserts could reveal nasty sneaky threading issues (because code execution
isn't linear anymore). Throwing pulls you out of the context in which the
state-error occured.

I'm not saying that this is all applicable to your class of course, but it
is something that I think is very valuable and it is something that I like
to see in library-like classes.

Another thing is that maxCount should probably be strictly greater than one.
A Mutex (or just lock) is a .Net primitive which is probably somewhat more
efficient and closer to the OS. On the other hand, you would not have the
starvation trigger though. Maybe a small docu-entry to the class ;-)?
Because reverse-sensing semaphore with maxSlots=1 will probably have its
use.

I don't understand the use for TryRelease. The implementation of Release is
almost the same, the difference is that you throw in Release and return true
or false in TryRelease. Why would someone try to release and not just
release? The way I see it, if releaseCount<=0 or if (count + releaseCount) >
maxCount then that's an error of the user of semaphore. I think you don't
need two methods that do the same thing but indicate errors in a different
way.

I think I'd prefer a TryAcquire (which is nothing more then "return
Acquire(0);") or TryAcquireAll (which is not the same as AcquireAll(0) since
all slots are acquired individually). They acquire if a slot is free (or all
slots are free) and return true if they did, otherwise they don't acquire
anything and return false.

ReleaseAll is a dangerous function now. I don't know if I would allow it to
be called if count isn't zero. That is something to think about.

In your implementation of Acquire there is a (very) small chance of
inconsistency in the face of a Thread.Interrupt call and the exception that
is a result of this. I've added some code to counter this (check below). The
same issue is present in AcquireAll.

Explanation. The exception could occur when you lock (Mutex under the hood).
If the exception occurs, the caller will think that the slot was not
acquired since the exception percolated through, but you already decremented
count when it happens.

public bool Acquire( int millisecondsTimeout )
{
lock( syncLock )
{
while( count == 0 )
try
{
if( !Monitor.Wait( syncLock, millisecondsTimeout ) )
return false;
}
catch
{
Monitor.Pulse(syncLock);
throw;
}

if( --count == 0 )
try
{
lock( starvationLock )
Monitor.PulseAll( starvationLock );
}
catch // guard against ThreadInterruptedException
{
++count;
throw;
}
return true;
}
}

I am very cautious with this because I tend to use Thread.Interrupt to wake
threads. Thread.Abort throws too but there is no good way to protect against
that of course. Anyway, ...

Cheers,
---
Tom Tempelaere
Nov 16 '05 #25

P: n/a
Hello William

Thanks for the explanation. Sound really interesting!

--
venlig hilsen / with regards
anders borum
--
Nov 16 '05 #26

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:eI**************@TK2MSFTNGP12.phx.gbl...
Update to the code? I did post a few changes after the first post. Let me know what updates you would like to see.

--
William Stacey, MVP


Make maxCount readonly since you cannot change it.

Cheers,
---
Tom Tempelaere
Nov 16 '05 #27

P: n/a
Sounds good.

--
William Stacey, MVP

"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:sL**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:eI**************@TK2MSFTNGP12.phx.gbl...
Update to the code? I did post a few changes after the first post. Let

me
know what updates you would like to see.

--
William Stacey, MVP


Make maxCount readonly since you cannot change it.

Cheers,
---
Tom Tempelaere


Nov 16 '05 #28

P: n/a
Thanks for the info. I will look at all of these closer.

--
William Stacey, MVP

"TT (Tom Tempelaere)" <_|\|_0P@|/\|titi____AThotmail.com|/\|@P0_|\|_>
wrote in message news:qz**********************@phobos.telenet-ops.be...
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:eI**************@TK2MSFTNGP12.phx.gbl...
Update to the code? I did post a few changes after the first post. Let me
know what updates you would like to see.
--
William Stacey, MVP


I forgot to check the link before posting, I see that you already made

some changes. Woops.

Have you already done some tests under stress? A working project that uses
the semaphore to demonstrate that it works ...

The code-documentation in AcquireAll, just before the lock on starvationLock is a typo: it sais "... is not zero ..." but I think it should read "... is now zero ...".

I think you should introduce Debug.Assert's at specific places for several
reasons, which is my opinion and perhaps a question of style (or QOI).
* clients of your library made a mistake in using your class/lib
* you made a mistake (aka bug) when making your class/lib
* when you refactor these can prove invaluable (I say this from experience) * to highlight some pre-conditions or post-conditions. It looks like proof
then, and they will probably never even trigger. It helps the reviewer of
the library and yourself when you return back to the project after a long
time.
* in some libraries (eg in-house) you would not throw exceptions when
receiving bad parameters (or a bad combination), just assert. When debugging the developer can use the code as a tool to know what he did wrong in using the library. He should correct things if the asserts trigger and afterwards the assert will no longer trigger. In that case the checking + throwing code is no longer necessary and becomes code bloat. On the other hand in some
circumstances you would prefer to throw (for stability reasons), it all
depends on the type of library and who you are writing it for. MFC library
is a good example, it has a lot of asserts. A quick count of "ASSERT" (match case, match whole word) in code of vc6 mfc library gave 5618 occurences.
Just to mention.
* Asserts could reveal nasty sneaky threading issues (because code execution isn't linear anymore). Throwing pulls you out of the context in which the
state-error occured.

I'm not saying that this is all applicable to your class of course, but it
is something that I think is very valuable and it is something that I like
to see in library-like classes.

Another thing is that maxCount should probably be strictly greater than one. A Mutex (or just lock) is a .Net primitive which is probably somewhat more
efficient and closer to the OS. On the other hand, you would not have the
starvation trigger though. Maybe a small docu-entry to the class ;-)?
Because reverse-sensing semaphore with maxSlots=1 will probably have its
use.

I don't understand the use for TryRelease. The implementation of Release is almost the same, the difference is that you throw in Release and return true or false in TryRelease. Why would someone try to release and not just
release? The way I see it, if releaseCount<=0 or if (count + releaseCount)

maxCount then that's an error of the user of semaphore. I think you don't
need two methods that do the same thing but indicate errors in a different
way.

I think I'd prefer a TryAcquire (which is nothing more then "return
Acquire(0);") or TryAcquireAll (which is not the same as AcquireAll(0) since all slots are acquired individually). They acquire if a slot is free (or all slots are free) and return true if they did, otherwise they don't acquire
anything and return false.

ReleaseAll is a dangerous function now. I don't know if I would allow it to be called if count isn't zero. That is something to think about.

In your implementation of Acquire there is a (very) small chance of
inconsistency in the face of a Thread.Interrupt call and the exception that is a result of this. I've added some code to counter this (check below). The same issue is present in AcquireAll.

Explanation. The exception could occur when you lock (Mutex under the hood). If the exception occurs, the caller will think that the slot was not
acquired since the exception percolated through, but you already decremented count when it happens.

public bool Acquire( int millisecondsTimeout )
{
lock( syncLock )
{
while( count == 0 )
try
{
if( !Monitor.Wait( syncLock, millisecondsTimeout ) )
return false;
}
catch
{
Monitor.Pulse(syncLock);
throw;
}

if( --count == 0 )
try
{
lock( starvationLock )
Monitor.PulseAll( starvationLock );
}
catch // guard against ThreadInterruptedException
{
++count;
throw;
}
return true;
}
}

I am very cautious with this because I tend to use Thread.Interrupt to wake threads. Thread.Abort throws too but there is no good way to protect against that of course. Anyway, ...

Cheers,
---
Tom Tempelaere


Nov 16 '05 #29

P: n/a
> A TryRelease method just doesn't seem useful.

It is mainly some sugar. The normal Release throws exception if count is 0.
TryRelease returns false. Some times a user may just want to TryRelease
until value is false instead of catching exception and incure the exception
slowness. Or they may not know how many are available and just want to
release one or more, but not all, if they are available. It is not required
so you can remove.
BTW: I've heard rumours that .NET v2 will supply a semaphore class but I

haven't seen anything about it on the net.

I hope they do. It was a curious omission for v1. Until then, someone out
there may find this usefull, even just for learning.

--
William Stacey, MVP
Nov 16 '05 #30

P: n/a
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:Od**************@tk2msftngp13.phx.gbl...
A TryRelease method just doesn't seem useful.
It is mainly some sugar. The normal Release throws exception if count is

0.

0? Don't you mean maxCount?
TryRelease returns false. Some times a user may just want to TryRelease
until value is false instead of catching exception and incure the exception slowness. Or they may not know how many are available and just want to
Exceptions aren't slow because they're exceptional! I don't see _any_
overhead in throwing an exception in an exceptional case. I can't think of
anyone that is going to 'try' to release for serious in production code. He
releases the slots he acquired, and shouldn't release any other. What is the
point in 'trying' if you know how many slots you acquired (of course users
of semaphore should keep track)? Releasing too many or too few is just
writing bugs IMO. If acquiring N slots was succesfull, then releasing N
slots should succeed by design. If it doesn't then there is a bug somewhere,
either in the client's code or in the library code. In that case, release
either throws an exception or you assert but I don't see the point of a
TryRelease here.
release one or more, but not all, if they are available. It is not required so you can remove.
BTW: I've heard rumours that .NET v2 will supply a semaphore class but I haven't seen anything about it on the net.

I hope they do. It was a curious omission for v1. Until then, someone

out there may find this usefull, even just for learning.
It is an interesting excercise of course.
--
William Stacey, MVP


Cheers,
---
Tom Tempelaere
Nov 16 '05 #31

P: n/a
William Stacey [MVP] <st***********@mvps.org> wrote:
BTW: I've heard rumours that .NET v2 will supply a semaphore class but I

haven't seen anything about it on the net.

I hope they do. It was a curious omission for v1. Until then, someone out
there may find this usefull, even just for learning.


The bizarre thing is that Java hasn't had it until 1.5, either. (1.5
has a whole load of threading classes, courtesy of Doug Lea.)

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 16 '05 #32

P: n/a
> Exceptions aren't slow because they're exceptional! I don't see _any_
overhead in throwing an exception in an exceptional case. I can't think of


It may not be exceptional behavior is my point. It may be just the thing
you want in the fast path. You may get passed a Sem representing some
random amount of StarShips. Your code then just wants to release them out
at some interval until false (you don't know or care how many.) Or allow
button click until false. It is impossible to predict how someone may want
to use this.

--
William Stacey, MVP
Nov 16 '05 #33

This discussion thread is closed

Replies have been disabled for this discussion.