www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - On condvars, synchronization and the specs

reply Tommie Gannert <Tommie_member pathlink.com> writes:
Hi All,

I began to follow D a year ago, but never felt I had the time to build all the
fundamental libraries I need to start working. That has changed, and as I was
looking for a new language to use, I thought I should give it a go...

I'll start with "the specs". I was making a syntax pattern for NEdit when I
found this in the Lexical specs. Admittedly, I haven't read all specs, so it
might just be me... But, IMHO, the Binary, Octal and Hexadecimal rules (Integer)
can contain underscores too, right?

That's all for the specs. But I have to point out that D is the first language
I've read the specs on and for each statement got a warm fuzzy feeling (no it's
not just because I'm feverish... ;) It's here to stay, and I'll do everything I
can to make that come true.

Next, the (from what I've seen) eternal question of having condvars. I'm not
entirely up to date, but I have not seen any solution to this yet. What's the
status?

You can program with merely monitors and condvars, but not with just monitors...
To interface it with the monitors, we would need a compiler modification. Is
this a bad thing? I wouldn't want to destroy the DMD/GDC sisterhood just because
of this...

/Tommie
Dec 02 2005
parent reply Sean Kelly <sean f4.ca> writes:
Tommie Gannert wrote:

 
 Next, the (from what I've seen) eternal question of having condvars. I'm not
 entirely up to date, but I have not seen any solution to this yet. What's the
 status?
 
 You can program with merely monitors and condvars, but not with just
monitors...
 To interface it with the monitors, we would need a compiler modification. Is
 this a bad thing? I wouldn't want to destroy the DMD/GDC sisterhood just
because
 of this...


Personally, I'd love to have condvars in D, but implementing them 
correctly on Win32 is problematic.  And language support aside, you need 
platform support  as well.  That said, Ben Hinkle did port Doug Lea's 
Locks library to D and it appears to have condvars in it.  I haven't 
given them a very thorough look yet, but here's the link:

http://home.comcast.net/%7Ebenhinkle/locks/locks.html


Sean
Dec 02 2005
parent reply Sean Kelly <sean f4.ca> writes:
Sean Kelly wrote:

 
 Personally, I'd love to have condvars in D, but implementing them 
 correctly on Win32 is problematic.  And language support aside, you need 
 platform support  as well.


Oops.  By platform support, I meant that it's difficult to implement 
condvars without platform support, as the transition from the locked to 
unlocked wait state needs to be atomic.  And the rules for wakeups are 
pretty strict.  Windows events are completely broken, for example, 
though they work okay for single-consumer models.


Sean
Dec 02 2005
parent reply Tommie Gannert <Tommie_member pathlink.com> writes:
In article <dmq0e9$2chv$1 digitaldaemon.com>, Sean Kelly says...

Sean Kelly wrote:

 
 Personally, I'd love to have condvars in D, but implementing them 
 correctly on Win32 is problematic.  And language support aside, you need 
 platform support  as well.


Oops.  By platform support, I meant that it's difficult to implement 
condvars without platform support, as the transition from the locked to 
unlocked wait state needs to be atomic.  And the rules for wakeups are 
pretty strict.  Windows events are completely broken, for example, 
though they work okay for single-consumer models.


Yeah, Events are pretty useless... However there are workarounds. Since Windows
is probably the only platform that does not (and never will have native) support
for condvars, I would be willing to go for a complex solution. Though creating
some overhead, I think it's worth getting a platform independent condvar-style
primitive. For Windows programmers (I mostly sit on Linux) there still is an
option to use the Win32 API functions, and I would rather see one official
implementation of condvars with a hundred users than a hundred implementations
each with one user... I'm thinking about the ability to bugfix. ;)

So, how would this be implemented?

It seems logical to start at the Win32 pthreads implementation.

http://sourceware.org/pthreads-win32/

They have a long paper (README.CV) which describes the evolution from

Strategies for Implementing POSIX Condition Variables on Win32
http://www.cs.wustl.edu/~schmidt/win32-cv-1.html

The biggest drawback of this is that it uses a WinNT feature, so we would need
another solution if we care about Win9x. pthreads-win32 is licensed under LGPL.
I don't know how this fits with DMD.
Dec 02 2005
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Tommie Gannert wrote:

 
 So, how would this be implemented?
 
 It seems logical to start at the Win32 pthreads implementation.
 
 http://sourceware.org/pthreads-win32/
 
 They have a long paper (README.CV) which describes the evolution from
 
 Strategies for Implementing POSIX Condition Variables on Win32
 http://www.cs.wustl.edu/~schmidt/win32-cv-1.html
 
 The biggest drawback of this is that it uses a WinNT feature, so we would need
 another solution if we care about Win9x. pthreads-win32 is licensed under LGPL.
 I don't know how this fits with DMD.


Good place to start, I suppose.  The "where can I get a condvar 
implementation for Win32" topic is practically a FAQ item in 
comp.programming.threads as well, so some googling there should turn up 
a few good references.


Sean
Dec 02 2005
parent reply Tommie Gannert <Tommie_member pathlink.com> writes:
In article <dmqbnc$4s5$1 digitaldaemon.com>, Sean Kelly says...

Good place to start, I suppose.  The "where can I get a condvar 
implementation for Win32" topic is practically a FAQ item in 
comp.programming.threads as well, so some googling there should turn up 
a few good references.


"Google is your friend"

And MS now has pthreads support in their Unix Services. If they can get it right
the second time, it can't be that hard. ;)

Seriously, if no one else has a comment on this I will do some thinking, code
reading and implementing in GDC.
Dec 02 2005
parent Sean Kelly <sean f4.ca> writes:
Tommie Gannert wrote:

 In article <dmqbnc$4s5$1 digitaldaemon.com>, Sean Kelly says...

 Good place to start, I suppose.  The "where can I get a condvar 
 implementation for Win32" topic is practically a FAQ item in 
 comp.programming.threads as well, so some googling there should turn up 
 a few good references.


 
 "Google is your friend"
 
 And MS now has pthreads support in their Unix Services. If they can get it
right
 the second time, it can't be that hard. ;)


That's why I mentioned Interix (or as it's more commonly known, 
"Microsoft Windows Services for Unix")--Microsoft recently deprecated it 
and will drop support of it at some point.  But supposedly they're going 
to replace it with something a bit more reliable.


 Seriously, if no one else has a comment on this I will do some thinking, code
 reading and implementing in GDC.


Go for it.  Concurrency is a topic of interest for me, but I have enough 
other things going on at the moment that I won't be looking at 
primitives for a while yet.  That said, you might be interested in the 
Ares atomic library:

http://svn.dsource.org/projects/ares/trunk/src/ares/std/atomic.d

It's based on work by Alexander Terekhov, and I believe serves as a 
useful building-block for lock-free programming in D.  I suggest using 
msync.acq and msync.rel for now, as the finer-grained methods are 
subject to review and may change at some point.


Sean
Dec 02 2005
prev sibling parent reply Bruno Medeiros <daiphoenixNO SPAMlycos.com> writes:
Tommie Gannert wrote:

 The biggest drawback of this is that it uses a WinNT feature, so we would need
 another solution if we care about Win9x. pthreads-win32 is licensed under LGPL.
 I don't know how this fits with DMD.
 


I say we shouldn't care. Win9x was never very good and is fast becoming 
obsolete.


-- 
Bruno Medeiros - CS/E student
"Certain aspects of D are a pathway to many abilities some consider to 
be... unnatural."
Dec 03 2005
parent reply Tommie Gannert <Tommie_member pathlink.com> writes:
In article <dmsb4v$6fm$1 digitaldaemon.com>, Bruno Medeiros says...

Tommie Gannert wrote:

 The biggest drawback of this is that it uses a WinNT feature, so we would need
 another solution if we care about Win9x. pthreads-win32 is licensed under LGPL.
 I don't know how this fits with DMD.
 


I say we shouldn't care. Win9x was never very good and is fast becoming 
obsolete.


That's good news. It seems the pthreads-win32 implementation doesn't use
SignalAndWait() (the function in question), which means we could probably get
away with a much simpler implementation.

Anyway. I have a working Linux implementation, and as it happens it only needed
one modification to Phobos.


languages" uses external constructs. In Python they are called Condition, and I
used that name. Condition is

class Condition
{
this(Object monitor);

void broadcast();
Object monitor();
void signal();
bit wait(int timeout = -1, TimeUnit unit = TimeUnit.SECOND);
//true if signaled, false on error or timeout
}

The only external contract is that the current thread must own the monitor
before entering wait(). broadcast/signal can be called at any time. Two notes:

1) I didn't want to put this in every object since (mesh.h)Object is pretty
clean right now, just having a vtable and a monitor (which, btw, should be a
pointer type [not uint], to cope with X86_64).

2) The reason I did not do it the pthread way;

bit wait(Object monitor, int timeout = -1, TimeUnit unit = TimeUnit.SECOND);

is that this would make it easier for the user to accidentaly use the wrong
monitor and introduce unneccessary bugs. A condvar should be associated with
exactly one monitor anyway. This also has the sideeffect of keeping any GC from
destroying the monitor while there still are condvars left.

Comments on this?

/Tommie
Dec 03 2005
parent reply Sean Kelly <sean f4.ca> writes:
Tommie Gannert wrote:

 In article <dmsb4v$6fm$1 digitaldaemon.com>, Bruno Medeiros says...

 Tommie Gannert wrote:

 The biggest drawback of this is that it uses a WinNT feature, so we would need
 another solution if we care about Win9x. pthreads-win32 is licensed under LGPL.
 I don't know how this fits with DMD.


 I say we shouldn't care. Win9x was never very good and is fast becoming 
 obsolete.


 
 That's good news. It seems the pthreads-win32 implementation doesn't use
 SignalAndWait() (the function in question), which means we could probably get
 away with a much simpler implementation.
 
 Anyway. I have a working Linux implementation, and as it happens it only needed
 one modification to Phobos.
 

 languages" uses external constructs. In Python they are called Condition, and I
 used that name. Condition is
 
 class Condition
 {
 this(Object monitor);
 
 void broadcast();
 Object monitor();
 void signal();
 bit wait(int timeout = -1, TimeUnit unit = TimeUnit.SECOND);
 //true if signaled, false on error or timeout
 }
 
 The only external contract is that the current thread must own the monitor
 before entering wait(). broadcast/signal can be called at any time. Two notes:
 
 1) I didn't want to put this in every object since (mesh.h)Object is pretty
 clean right now, just having a vtable and a monitor (which, btw, should be a
 pointer type [not uint], to cope with X86_64).
 
 2) The reason I did not do it the pthread way;
 
 bit wait(Object monitor, int timeout = -1, TimeUnit unit = TimeUnit.SECOND);
 
 is that this would make it easier for the user to accidentaly use the wrong
 monitor and introduce unneccessary bugs. A condvar should be associated with
 exactly one monitor anyway. This also has the sideeffect of keeping any GC from
 destroying the monitor while there still are condvars left.
 
 Comments on this?


I think it would be quite useful so long as it's implemented correctly. 
  And the design seems pretty clean and straightforward.  I'll certainly 
want condvars once I start doing application coding in D.


Sean
Dec 03 2005
parent reply Tommie Gannert <Tommie_member pathlink.com> writes:
I think it would be quite useful so long as it's implemented correctly. 


Reminds me of the time where this guy wanted to start a development project and
stated the goals to us, including such oddities as "bug free software" and "fast
code"... ;)

Well, the Posix implementation shouldn't be a problem, really. The Windows stuff
is - not intuitive. The worst about the SignalAndWait() function in Windows is
that I can't use a CriticalSection there. Now is the time to ask if it's worth
replacing CriticalSection for Mutex in the synchronized() blocks... Either way
the implementation on Windows will be less elegant.


  And the design seems pretty clean and straightforward.  I'll certainly 
want condvars once I start doing application coding in D.




it.)
Dec 03 2005
parent reply Sean Kelly <sean f4.ca> writes:
Tommie Gannert wrote:

 I think it would be quite useful so long as it's implemented correctly. 


 
 Reminds me of the time where this guy wanted to start a development project and
 stated the goals to us, including such oddities as "bug free software" and
"fast
 code"... ;)
 
 Well, the Posix implementation shouldn't be a problem, really. The Windows
stuff
 is - not intuitive. The worst about the SignalAndWait() function in Windows is
 that I can't use a CriticalSection there. Now is the time to ask if it's worth
 replacing CriticalSection for Mutex in the synchronized() blocks... Either way
 the implementation on Windows will be less elegant.


hehe, I said that only because getting it right on Windows is so 
difficult :)  The Boost implementation uses something like three 
semaphores and I've heard comments that it still has issues (though this 
was a while ago).


  And the design seems pretty clean and straightforward.  I'll certainly 
 want condvars once I start doing application coding in D.


 


 it.)


Windows people tend not to be particularly familiar with condvars, but 
they're about the only way I know of to do multiple producer/consumer 
correctly.  All the standard Windows methods I know of tend to have 
subtle races and spurious wakeup problems.  This is one area that Java 
has become quite nice, thanks, I suppose, to Doug Lea.


Sean
Dec 03 2005
parent Sean Kelly <sean f4.ca> writes:
Sean Kelly wrote:

 Tommie Gannert wrote:

 I think it would be quite useful so long as it's implemented correctly. 


 Reminds me of the time where this guy wanted to start a development 
 project and
 stated the goals to us, including such oddities as "bug free software" 
 and "fast
 code"... ;)

 Well, the Posix implementation shouldn't be a problem, really. The 
 Windows stuff
 is - not intuitive. The worst about the SignalAndWait() function in 
 Windows is
 that I can't use a CriticalSection there. Now is the time to ask if 
 it's worth
 replacing CriticalSection for Mutex in the synchronized() blocks... 
 Either way
 the implementation on Windows will be less elegant.


 
 hehe, I said that only because getting it right on Windows is so 
 difficult :)  The Boost implementation uses something like three 
 semaphores and I've heard comments that it still has issues (though this 
 was a while ago).


This topic resurfaced again recently on c.p.t so I did a bit of looking. 
  There are three pseudocode implementations for condvars in this 
(somewhat old) thread:



Also, this project likely has a correct pthread implementation for 
Win32, though it uses the LGPL license:

http://sourceware.org/pthreads-win32/

It's worth noting that this project uses an algorithm described in the 
aforementioned usenet thread (Algorithm 8a).  If I suddenly find some 
time to play with this I'll translate one of the algothms (8a or 8c) to 
D code--it would be great to have cross-platform condvar support in D.


Sean
Jan 13 2006