N threads synchronization - contrived example

[emma_middlebrook]

Hi

Say you had N threads doing some jobs (not from a shared queue or
anything like that, they each know how to do their own set of jobs in a
self-contained way). How can you coordinate them so that they all wait
until they've all done one job before starting off on each of their
next jobs.

I have been thinking about this for a day and can't seem to find a
solution.

Emma

 

[William Stacey [C# MVP]]

You could wait on an autoreset event that gets set after last job finished
or use Thread.Join to wait on N threads to finish job 1 and exit, then start
more threads for job 2, etc.

--
William Stacey [C# MVP]

| Hi
|
| Say you had N threads doing some jobs (not from a shared queue or
| anything like that, they each know how to do their own set of jobs in a
| self-contained way). How can you coordinate them so that they all wait
| until they've all done one job before starting off on each of their
| next jobs.
|
| I have been thinking about this for a day and can't seem to find a
| solution.
|
| Emma
|

 

[emma_middlebrook]

You could wait on an autoreset event that gets set after last job finished
or use Thread.Join to wait on N threads to finish job 1 and exit, then start
more threads for job 2, etc

That's given me some good ideas! I was thinking that the threads
shouldn't know about each other directly, and also my abstract problem
includes that there is nothing as such that is coordinating them. In
order to coordinate themselves, the AutoResetEvent idea is what I tried
initially but couldn't get it to work. Do you think a Semaphore is what
I should use? I'm finding it a bit hard to get it working though!

Emma.

 

[emma_middlebrook]

That's given me some good ideas! I was thinking that the threads
shouldn't know about each other directly, and also my abstract problem
includes that there is nothing as such that is coordinating them. In
order to coordinate themselves, the AutoResetEvent idea is what I tried
initially but couldn't get it to work. Do you think a Semaphore is what
I should use? I'm finding it a bit hard to get it working though!

Hi

So, I got a quick moment to knock up something that works ...

It uses N AutoResetEvents and each thread waits on its own event, then
signals the next one when finished, in circular fashion.

Is this the best I can do (i.e. I must use N synchronization objects)?
Can someone confirm that, if I want the threads to process jobs in this
particular order and one at a time, there is no better way?

Here's a related question: if I just want threads to all complete one
job before any other thread can go on to the next one (i.e. dump out
the next int!) but it doesn't have to be in any particular thread
order, can I use just 1 synchronization object? I'm trying to get the
Semaphore to work in this situation because it seems exactly what's
required!

If anyone is interested, fancies adapting and improving, I've enclosed
below a working program just in case:

static void Main()
{
int threadCount;

while (true)
{
Console.Write("Enter number of threads: ");
string input = Console.ReadLine();

if (int.TryParse(input, out threadCount) && threadCount

0)

{
break;
}

Console.WriteLine("Enter a positive integer.");
}

AutoResetEvent[] events = new AutoResetEvent[threadCount];
ThreadConsole[] threads = new ThreadConsole[threadCount];

for (int i = 0; i < threadCount; i++)
{
events = new AutoResetEvent(false);
}

for (int i = 0; i < threadCount; i++)
{
threads = new ThreadConsole("Thread " +
i.ToString(), events, events[i + 1 == threadCount ? 0 : i + 1]);
threads.Start();
}

events[0].Set();

Console.ReadLine();
}
}

class ThreadConsole
{
Thread thread;
string name;
AutoResetEvent canStart;
AutoResetEvent nextCanStart;

public ThreadConsole(string name, AutoResetEvent canStart,
AutoResetEvent nextcanStart)
{
thread = new Thread(ThreadProc);
this.name = name;
this.canStart = canStart;
this.nextCanStart = nextcanStart;
}

public void Start()
{
thread.Start();
}

void ThreadProc()
{
for (int i = 0; i < 100; i++)
{
canStart.WaitOne();
Console.WriteLine(name + ": " + i.ToString());
nextCanStart.Set();
}
}
}


Cheers,

Emma.

 

[Lebesgue]

Is this the best I can do (i.e. I must use N synchronization objects)?

Can someone confirm that, if I want the threads to process jobs in this
particular order and one at a time, there is no better way?

You don't state what you mean by "better way". In terms of number of
synchronization objects needed, the minimal number of synchronization
objects needed to serialize N jobs is log2 N, but in terms of
understandability, using the logN solution would not be the "better way".

 

[emma_middlebrook]

You don't state what you mean by "better way". In terms of number of
synchronization objects needed, the minimal number of synchronization
objects needed to serialize N jobs is log2 N, but in terms of
understandability, using the logN solution would not be the "better way".

Yes, in terms of the number of synchronization objects.

What I suppose I'm asking is what is the standard way to do what I'm
trying to do? By standard, I mean common/well-known/popular (and so
that might imply most readable as well). I have a feeling in the back
of my mind that there must be something more elegant, but maybe not.

For instance, it really feels as if the problem can be solved with one
synchronization object, if we relax the constraint that the threads
must do one job at at time and in order i.e. if they just have to do
one job at a time and in any thread order. I keep on looking at
semaphores but they don't 'enforce thread identity' as the help puts
it! I'll keep on thinking about this until someone tells me it can't be
done (which would be helpful so I can move on!).

Finally, I presume logN solution is using the synchronization objects
as binary digits and operating on them like that - e.g. thread 6
carries on when event 0, 2 are signalled and 1 is not! Yes, I agree
that it would certainly be a little more fiddly to read, nice idea
though.

Thanks very much,

Emma.

 

[William Stacey [C# MVP]]

Please provide a senerio using a description of tasks. That would help I
think.

--
William Stacey [C# MVP]

|
| Lebesgue wrote:
| > > Is this the best I can do (i.e. I must use N synchronization objects)?
| > > Can someone confirm that, if I want the threads to process jobs in
this
| > > particular order and one at a time, there is no better way?
| > >
| >
| > You don't state what you mean by "better way". In terms of number of
| > synchronization objects needed, the minimal number of synchronization
| > objects needed to serialize N jobs is log2 N, but in terms of
| > understandability, using the logN solution would not be the "better
way".
|
| Yes, in terms of the number of synchronization objects.
|
| What I suppose I'm asking is what is the standard way to do what I'm
| trying to do? By standard, I mean common/well-known/popular (and so
| that might imply most readable as well). I have a feeling in the back
| of my mind that there must be something more elegant, but maybe not.
|
| For instance, it really feels as if the problem can be solved with one
| synchronization object, if we relax the constraint that the threads
| must do one job at at time and in order i.e. if they just have to do
| one job at a time and in any thread order. I keep on looking at
| semaphores but they don't 'enforce thread identity' as the help puts
| it! I'll keep on thinking about this until someone tells me it can't be
| done (which would be helpful so I can move on!).
|
| Finally, I presume logN solution is using the synchronization objects
| as binary digits and operating on them like that - e.g. thread 6
| carries on when event 0, 2 are signalled and 1 is not! Yes, I agree
| that it would certainly be a little more fiddly to read, nice idea
| though.
|
| Thanks very much,
|
| Emma.
|

 

[emma_middlebrook]

Please provide a senerio using a description of tasks. That would help I
think.

Hi

The solution I posted works for the case where there are N threads and
the threads have to be scheduled in order - it follows your AutoReset
idea - or at least your suggestion gave me the idea for that
implementation - is that what you had in mind by the way? The point of
the iteration and the output is to simulate an arbitrary task so we
have as much information as we're going to get! I admit that this could
be seen as a relatively stupid question because there are N threads
effectively being serialized despite the fact that they're working on
separate data ...

Anyway, I'm now just thinking whether or not I can achieve similar with
less than N synch objects, in particular when the order of the threads
processing jobs doesn't matter but they all have to process one job
before any thread can process another job.

There's a post above that says it can be done with log N but, although
I thought I could see how, I can't any more. Not, in the sense of e.g.
an Event in the Win32 sense because you can't block on a non-signalled
event!

So, I've now got three questions! How to get the log N version to work?
Is there any difference between the number of synchronization objects
in the case I've already posted code for, and the case where the order
of threads doesn't matter, as outlined above. And finally, what other
ways are there and can Semaphores help?

Cheers.

Emma.

 

[emma_middlebrook]

You don't state what you mean by "better way". In terms of number of
synchronization objects needed, the minimal number of synchronization
objects needed to serialize N jobs is log2 N, but in terms of
understandability, using the logN solution would not be the "better way".

Hi

As I said in a previous post, I thought I understood the way to do the
logN synch objects but now I'm not so sure. I can't even think how to
achieve what my posted code does but with only 2 threads and 1 synch
object i.e. the simplest case!

Would you be able to outline?

Thanks!

Emma.

 

[Lebesgue]

As you have correctly stated in your previous post, the magic is in encoding
the order of the threads in binary.

Let's assume you have threads T0 T1 T2 T3 you want to serialize in such a
way that T1 starts after T0 has completed its job and so on.

Then we encode the order as shown in this table:

T0 T1 T2 T3
S1 0 0 1 1
S2 0 1 0 1

Each thread has unique combination of binary semaphores to wait for (1 means
to wait for the particular semaphore) and the previous thread ensures to
configure the semaphores to be in required combination.
When there are more threads in order to wait for the same semaphore (T2 and
T3 both wait for S1), the event needs to be signalled twice (as many times
as the number of threads to wait for the same object in a row).

In terms of implementation, I have implemented and tested this using binary
semaphores. I believe it could be implemented using eventwaithandles, but
have not tried so far - if there is an abvious reason it could not be
implemented using waithandles, I don't see it now, since it's midnight.

I just found out there is a solution with (constant) 3 semaphores, which is
the optimal solution in terms of number of synchronization objects needed,
but if logN solution makes it less readable, const3 solution would make it
unreadable.

Hope this helps.

 

[emma_middlebrook]

As you have correctly stated in your previous post, the magic is in encoding
the order of the threads in binary.

Let's assume you have threads T0 T1 T2 T3 you want to serialize in such a
way that T1 starts after T0 has completed its job and so on.

Then we encode the order as shown in this table:

T0 T1 T2 T3
S1 0 0 1 1
S2 0 1 0 1

Each thread has unique combination of binary semaphores to wait for (1 means
to wait for the particular semaphore) and the previous thread ensures to
configure the semaphores to be in required combination.
When there are more threads in order to wait for the same semaphore (T2 and
T3 both wait for S1), the event needs to be signalled twice (as many times
as the number of threads to wait for the same object in a row).

In terms of implementation, I have implemented and tested this using binary
semaphores. I believe it could be implemented using eventwaithandles, but
have not tried so far - if there is an abvious reason it could not be
implemented using waithandles, I don't see it now, since it's midnight.

Hi, it's just about midnight here too now and with a name like Lebesgue
I'll guess you're just on the other side of La Manche

Anyway, this is what I don't understand about the encoding. If T0 waits
on neither S1 nor S2 it will not block at all and spin around
processing whenever it gets a time slice! I can see that the rest
works. This is me thinking about it in terms of either type of Event in
Win32/.NET.

Unless I'm being incredibly stupid, I can't find a particular
synchronization object where one thread can wait on it being true, and
the other can wait on it being false. All I can see is blocking until
true (i.e. signalled)! It seems as if you need a pair of Events to
simulate blocking on true/false.

As you say, it's late but I'd really like to understand all this
tomorrow!

Cheers,

Emma.

 

[William Stacey [C# MVP]]

Sorry Emma, I am having trouble understanding your real need here in order
to suggest a solution. Is this just a homework problem or do you have some
real world need here? If the latter, could you explain the real problem
space using a real example. Also, why can't you use a blocking queue again
that multiple threads could pop jobs out of?

--
William Stacey [C# MVP]

| William Stacey [C# MVP] wrote:
| > Please provide a senerio using a description of tasks. That would help
I
| > think.
|
| Hi
|
| The solution I posted works for the case where there are N threads and
| the threads have to be scheduled in order - it follows your AutoReset
| idea - or at least your suggestion gave me the idea for that
| implementation - is that what you had in mind by the way? The point of
| the iteration and the output is to simulate an arbitrary task so we
| have as much information as we're going to get! I admit that this could
| be seen as a relatively stupid question because there are N threads
| effectively being serialized despite the fact that they're working on
| separate data ...
|
| Anyway, I'm now just thinking whether or not I can achieve similar with
| less than N synch objects, in particular when the order of the threads
| processing jobs doesn't matter but they all have to process one job
| before any thread can process another job.
|
| There's a post above that says it can be done with log N but, although
| I thought I could see how, I can't any more. Not, in the sense of e.g.
| an Event in the Win32 sense because you can't block on a non-signalled
| event!
|
| So, I've now got three questions! How to get the log N version to work?
| Is there any difference between the number of synchronization objects
| in the case I've already posted code for, and the case where the order
| of threads doesn't matter, as outlined above. And finally, what other
| ways are there and can Semaphores help?
|
| Cheers.
|
| Emma.
|

 

[Lebesgue]

Hi, it's just about midnight here too now and with a name like Lebesgue
I'll guess you're just on the other side of La Manche

Anyway, this is what I don't understand about the encoding. If T0 waits
on neither S1 nor S2 it will not block at all and spin around
processing whenever it gets a time slice!

Yes, it will. And it is not a problem, since as soon as it is done with its
job, it signals S2, finishes its work, and T1 can start working - this was
the desired behavior. At the time, there is probably T2 already waiting for
S1 (before it does its job) and T1 signals on S1 (twice) as soon as it has
its work done. T2 and T3 will both pass their first wait on S1 and T3 stops
on S2.Wait(). T2 doesn't wait on anything else than S1, so it gets its work
done, and finally signals on S2 and lets T3 to start its work.
Hope this makes things clear.

Unless I'm being incredibly stupid, I can't find a particular
synchronization object where one thread can wait on it being true, and
the other can wait on it being false. All I can see is blocking until
true (i.e. signalled)! It seems as if you need a pair of Events to
simulate blocking on true/false.

I don't fully understand what you mean by this, but this solution uses one
of the simplest synchronization mechanisms - semaphore. Threads can pass a
wait on semaphore onlyt if "it has any place left" (given a binary
semaphore, it can "have only one free place" at a time - so one thread can
pass a wait at a given time before any thread calls signal. (or V/P
respectively when using the traditional naming))

http://en.wikipedia.org/wiki/Semaphore_(programming)