I'm trying to implement a low-overhead thread pool library that avoids busy
waiting, and the issue I keep running into is, if a thread is waiting on a job
in the pool queue, how to get the waiting thread to pause and then be resumed
by the worker thread when the job is finished, w/o creating any race hazards.
 Below is a simplified example:

class Task {
    bool isDone = false;
    Thread[] waitingThreads;  //Threads waiting for task to complete.

    //int delegate(), etc., etc.

    void wait() {
        if(isDone) return;
        Thread self = Thread.getThis;
        synchronized(this) {
            waitingThreads ~= self;
            self.pause;
        }
    }

    void resumeWaiting() {  //Called by worker function when done w/ task.
        isDone = true;
        foreach(waiting; waitingThreads) {
            waiting.resume;
        }
    }
}

This probably wouldn't work because, since resumeWaiting is not synchronized, it could theoretically be called while a thread is in the process of adding itself to waitingThreads.  In this case, resume would never get called for this thread.

If I synchronize resumeWaiting, then the thread that called wait() goes to pause inside a mutex, and nothing can get access to my instance of Task to resume it.

The third option would be to synchronize only the append to waitingThreads and
not the call to pause(), and to synchronize resumeWaiting().  However, then it
seems theoretically possible that the thread calling wait() would be suspended
by the scheduler before it called pause(), and if resumeWaiting() were then
called before the thread calling wait() got another timeslice, I'd have a
resume-before-pause.  I'm fairly (read:  very) new to concurrent programming.
 Is there a standard solution to problems like this?

NO NO NO NO NO NO NO.


I tried this once, and _believe me_, you do _not_ want to go down this route.

Use proper threading primitives. By which I mean, tools.threads and its POSIX/Win32 Semaphores and Mutexes.

It even already has a threadpool :)

 --downs

PS: The reason you don't want to go down this route is because you're interfering with the GC's own pause/resume schemes and inviting a world of race conditions and hard to find bugs.

Sorry, forgot to say.

without reading the whole post:

Is there a good reason to not just take the thread that is supposed to be waiting and add it to the thread pool until it should awake?

dsimcha wrote:
> I'm trying to implement a low-overhead thread pool library that avoids busy
> waiting, and the issue I keep running into is, if a thread is waiting on a job
> in the pool queue, how to get the waiting thread to pause and then be resumed
> by the worker thread when the job is finished, w/o creating any race hazards.

Assuming you're using Tango, you should use a Condition:

class Task
{
    alias void delegate() Dg;
    Mutex m;
    Condition c;
    Dg[] queue;

    this()
    {
        m = new Mutex;
        c = new Condition;
        auto t = new Thread( &run );
    }

    void assignTask( Dg dg )
    {
        synchronized( m )
        {
            queue ~= dg;
            c.notify();
        }
    }

private:
    void run()
    {
        Dg dg;

        while( true )
        {
            synchronized( m )
            {
                while( queue.length < 1 )
                    c.wait();
                dg = queue[$ - 1];
                queue = queue[0 .. $ - 1];
            }
            dg();
        }
    }
}

The pool above contains only one thread and is pretty basic, but you get the idea.  c.wait() above atomically unlocks the mutex and waits for c.notify() to be called, and then atomically re-locks the mutex before returning.  This is a classic producer-consumer algorithm.

> If I synchronize resumeWaiting, then the thread that called wait() goes to
> pause inside a mutex, and nothing can get access to my instance of Task to
> resume it.

See above.  Conditions are kind of a special case.  Don't use pause/resume in Thread--they're a deadlock waiting to happen.  They've been deprecated in Java for this reason, and I have no idea why they're exposed in Phobos.  It's a major mistake IMO.

>  Is there a standard solution to problems like this?

Condition variables.  See above :-)


Sean

Thanks.  Unfortunately, I'm using Phobos right now because Tango is not compatible with D2, except the experimental branches, which seem *very* experimental at this point in that I couldn't get them to compile cleanly on DMD 2.017.  I actually wrote the thing using "yield spinning," i.e. if(var != condition) self.yield.  It actually works reasonably well like that.  If/when Tango becomes 2.0 compatible or Phobos gets condition mutexes, I'll probably fix this.  However, I'm so impressed with the low latency of this thing that, for my purposes (futures and other similar ways of exploiting very fine-grained parallelism), it might be better this way.  I ran some microbenchmarks to find the break even job size for running jobs in serial w/o thread pool overhead vs. running them in parallel on the thread pool.  If the benchmarks are accurate, on my 2-core rig it's only about 3 microseconds/job.  This assumes you're queueing up a large number of jobs and then waiting for all of them to finish.

On another note, anyone have any idea when/if Tango for D2, and Tangobos for Tango for D2, will be available?  There are things I like and dislike about both Tango and Phobos, and I really wish I could mix and match modules from them without giving up my D2 features.  For example, I like Phobos's much simpler IO API, less "OO everywhere" look and feel and "simple operations should be simple" mentality, but I like Tango's extra math and threading stuff and richer feature set in general.  Also, I've written a decent amount of Phobos code that I don't feel like porting.

"dsimcha" <dsimcha@yahoo.com> wrote in message news:g5o4g7$2f5i$1@digitalmars.com...

> On another note, anyone have any idea when/if Tango for D2, and Tangobos
> for Tango
> for D2, will be available?  There are things I like and dislike about both
> Tango
> and Phobos, and I really wish I could mix and match modules from them
> without
> giving up my D2 features.  For example, I like Phobos's much simpler IO
> API, less
> "OO everywhere" look and feel and "simple operations should be simple"
> mentality,

Why does everyone say that Tango is "OO everywhere"?  There are free functions (or static functions) that correspond to most free functions in Phobos.  Please, please give me some examples of what you believe to be "OO everywhere."

Reading in a file.  Yes, Phobos has streams for when you actually need serious features, but it has the dead simple read() function that doesn't require instantiating a class or anything like that just to read a file into an array of bytes.  To be perfectly honest, the only parts of Tango I've really looked at hard are the threading and math stuff, since Tango is still basically for D1 only and otherwise I haven't had a problem with Phobos, but AFAIK Tango is much more OO and verbose than Phobos.  This isn't really a knock against it, it's really just personal preference, not that one is "better" than the other.  On the other hand, Phobos just doesn't have a lot of the features I'd like.

What I personally would like to see in the ideal world is for Phobos to become analogous to the C++ standard lib, i.e. simple in both features and API, very highly tested and optimized, "official", etc. and for Tango to become analogous to Boost, i.e. more complex, feature-rich, etc. and more of a "standard add-on lib" than a second "*the*" standard lib.  However, IDK how much they've diverged and whether using them together will grow more or less feasible with time.

Jarrett Billingsley wrote:
> "dsimcha" <dsimcha@yahoo.com> wrote in message news:g5o4g7$2f5i$1@digitalmars.com...
> 
>> On another note, anyone have any idea when/if Tango for D2, and Tangobos for Tango
>> for D2, will be available?  There are things I like and dislike about both Tango
>> and Phobos, and I really wish I could mix and match modules from them without
>> giving up my D2 features.  For example, I like Phobos's much simpler IO API, less
>> "OO everywhere" look and feel and "simple operations should be simple" mentality,
> 
> Why does everyone say that Tango is "OO everywhere"?  There are free functions (or static functions) that correspond to most free functions in Phobos.  Please, please give me some examples of what you believe to be "OO everywhere." 


One example: there are no stand-alone writefln/writef or readfln/readf functions in Tango.

--bb

"Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:g5ocsa$2v3b$2@digitalmars.com...
> Jarrett Billingsley wrote:
>> "dsimcha" <dsimcha@yahoo.com> wrote in message news:g5o4g7$2f5i$1@digitalmars.com...
>>
>>> On another note, anyone have any idea when/if Tango for D2, and Tangobos
>>> for Tango
>>> for D2, will be available?  There are things I like and dislike about
>>> both Tango
>>> and Phobos, and I really wish I could mix and match modules from them
>>> without
>>> giving up my D2 features.  For example, I like Phobos's much simpler IO
>>> API, less
>>> "OO everywhere" look and feel and "simple operations should be simple"
>>> mentality,
>>
>> Why does everyone say that Tango is "OO everywhere"?  There are free functions (or static functions) that correspond to most free functions in Phobos.  Please, please give me some examples of what you believe to be "OO everywhere."
>
>
> One example: there are no stand-alone writefln/writef or readfln/readf functions in Tango.

--! I mean ------ come on.  You call a method of a statically allocated object.  As if that's really different?