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. Some research told me Java and C# can wait() on any object, while "the other 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.

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. Some research told me Java and C# can wait() on any object, while "the other 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.

Yeah, I think we will need them to be able to lure Java and C# people to D. (However, the syntax in C# wasn't very attractive, so I wonder if anyone uses 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.

Yeah, I think we will need them to be able to lure Java and C# people to D. (However, the syntax in C# wasn't very attractive, so I wonder if anyone uses 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: http://groups.google.com/group/comp.programming.threads/browse_frm/thread/6191877e72ccb3fe/846010a82d6c51b0#846010a82d6c51b0 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