N threads synchronization - contrived example

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]

<em************ **@fastmail.fmw rote in message
news:11******** **************@ h48g2000cwc.goo glegroups.com.. .
| 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] wrote:

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.

em************* *@fastmail.fm wrote:

William Stacey [C# MVP] wrote:

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!

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.ReadLin e();

if (int.TryParse(i nput, out threadCount) && threadCount

0)

{
break;
}

Console.WriteLi ne("Enter a positive integer.");
}

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

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

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

events[0].Set();

Console.ReadLin e();
}
}

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

public ThreadConsole(s tring name, AutoResetEvent canStart,
AutoResetEvent nextcanStart)
{
thread = new Thread(ThreadPr oc);
this.name = name;
this.canStart = canStart;
this.nextCanSta rt = nextcanStart;
}

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

void ThreadProc()
{
for (int i = 0; i < 100; i++)
{
canStart.WaitOn e();
Console.WriteLi ne(name + ": " + i.ToString());
nextCanStart.Se t();
}
}
}
Cheers,

Emma.

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
understandabili ty, using the logN solution would not be the "better way".

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
understandabili ty, 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.

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

--
William Stacey [C# MVP]

<em************ **@fastmail.fmw rote in message
news:11******** **************@ f16g2000cwb.goo glegroups.com.. .
|
| 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
| understandabili ty, 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] 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 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
understandabili ty, 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.

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 eventwaithandle s, 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.

<em************ **@fastmail.fmw rote in message
news:11******** **************@ m7g2000cwm.goog legroups.com...

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
synchronizatio n objects needed, the minimal number of synchronization
objects needed to serialize N jobs is log2 N, but in terms of
understandabil ity, 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.