473,320 Members | 1,902 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Monitor unblock priority

Suppose execution of a particular thread T1 hits

Monitor.Enter(obj);
//critical section

and blocks at the first line. (ie someone else is in the critical
section) Now suppose more threads T2, T3... try to enter the critical
section and are blocked.

What is the order that the threads get to enter the critical section?
I'm hoping its

T1, T2, T3...

If not, is there any (easy) way to guarantee the thread that blocked
first gets to enter the CS next?
--
Wal
http://www.vooose.com

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!
Nov 16 '05 #1
25 2658
Inline ***

Willy.

"vooose" <no****@microsoft.com> wrote in message
news:ut**************@TK2MSFTNGP14.phx.gbl...
Suppose execution of a particular thread T1 hits

Monitor.Enter(obj);
//critical section

and blocks at the first line. (ie someone else is in the critical
section) Now suppose more threads T2, T3... try to enter the critical
section and are blocked.

What is the order that the threads get to enter the critical section?
I'm hoping its

T1, T2, T3...
*** No, there is no way to hope for a FIFO fashion in thread scheduling in
..NET.
If not, is there any (easy) way to guarantee the thread that blocked
first gets to enter the CS next?
*** No, there is no way at all. What's more, thread "fairness" is not
guaranteed in .NET. That means that it's possible, when you have multiple
threads that are constantly trying to take ownership of an object, that some
thread(s) will never get serviced at all.

--
Wal
http://www.vooose.com

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!

Nov 16 '05 #2
Hi
I have been searching but couldn't find any article or document that says
it is implemented that way . but you can use semaphore objects or at worst
case build your own queue where blocked threads check in and out.
Mohamed Mahfouz
Developer Support Engineer
ITWorx on behalf of Microsoft EMEA GTSC

Nov 16 '05 #3
Willy, thanks for your replies.

I have thought of perhaps a way to guarantee the order of execution, not
using monitors. Instead of

Monitor.Enter(obj);

and block subsequent threads, you do (pseudo here)

myArrayList.Add(Thread.CurrentThread);
while(myArrayList[0] != Thread.CurrentThread)
Thread.Sleep(10);

//got past loop, do critucal stuff

myArrayList.Remove(Thread.CurrentThread);

Naturally the ArrayList would be made thread safe.

Any thoughts there?

Also I was wondering if you could answer one more question re: Monitors.
When we do

Monitor.Enter(obj);

What happens if the Thread calls sleep? Naturally I would expect the
other threads to be locked out until the thread wakes up and calls Exit(
) but I'm not sure if this is what is guaranteed to happen.
--
Wal
http://www.vooose.com

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!
Nov 16 '05 #4
vooose <no****@microsoft.com> wrote:
I have thought of perhaps a way to guarantee the order of execution, not
using monitors. Instead of

Monitor.Enter(obj);

and block subsequent threads, you do (pseudo here)

myArrayList.Add(Thread.CurrentThread);
while(myArrayList[0] != Thread.CurrentThread)
Thread.Sleep(10);

//got past loop, do critucal stuff

myArrayList.Remove(Thread.CurrentThread);

Naturally the ArrayList would be made thread safe.

Any thoughts there?
Yes - it's nastily inefficient, as you could have lots of threads which
end up taking most of the time calling Sleep. Instead, use a monitor
and Wait on it, then call NotifyAll on the monitor when you come out of
the appropriate block. (There's a bit more to it that that, of course,
but that's the relevant bit.)
Also I was wondering if you could answer one more question re: Monitors.
When we do

Monitor.Enter(obj);

What happens if the Thread calls sleep? Naturally I would expect the
other threads to be locked out until the thread wakes up and calls Exit(
) but I'm not sure if this is what is guaranteed to happen.


Yes. Calling Thread.Sleep doesn't release any monitors. Calling
Monitor.Wait releases the monitor you wait on.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 16 '05 #5

"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
vooose <no****@microsoft.com> wrote:
I have thought of perhaps a way to guarantee the order of execution, not
using monitors. Instead of

Monitor.Enter(obj);

and block subsequent threads, you do (pseudo here)

myArrayList.Add(Thread.CurrentThread);
while(myArrayList[0] != Thread.CurrentThread)
Thread.Sleep(10);

//got past loop, do critucal stuff

myArrayList.Remove(Thread.CurrentThread);

Naturally the ArrayList would be made thread safe.

Any thoughts there?


Yes - it's nastily inefficient, as you could have lots of threads which
end up taking most of the time calling Sleep. Instead, use a monitor
and Wait on it, then call NotifyAll on the monitor when you come out of
the appropriate block. (There's a bit more to it that that, of course,
but that's the relevant bit.)


Jon,

And what if the CurrentThread never equals the myArrayList[0] thread?
This what I meant in my previous reply, don't count on it, the CLR doesn't
guarantee "fairness", so it's possible the thread your waiting for never get
serviced.
AFAIK there is no solution to this in managed world.

Willy.
Nov 16 '05 #6
Eventually CurrentThread would have to equal myArrayList[0] (all other
things working correctly).

Eventually thread T2 that is waiting on T1 to remove itself from
myArrayList so T2 is now == myArrayList[0].

When T2 wakes up from Thread.Sleep(10); it entera the CS.
How could T2 not be guaranteed that execution sequence?

To me that is like saying any given thread may never execute one line of
code because the OS never schedules that thread to run!

--
Wal
http://www.vooose.com

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!
Nov 16 '05 #7

"vooose" <no****@microsoft.com> wrote in message
news:OR*************@TK2MSFTNGP11.phx.gbl...
Eventually CurrentThread would have to equal myArrayList[0] (all other
things working correctly).

Eventually thread T2 that is waiting on T1 to remove itself from
myArrayList so T2 is now == myArrayList[0].

When T2 wakes up from Thread.Sleep(10); it entera the CS.
How could T2 not be guaranteed that execution sequence?

To me that is like saying any given thread may never execute one line of
code because the OS never schedules that thread to run!


*** Wait a minute I didn' say that your threads don't get scheduled, I said
this isn't guaranteed under the CLR, and you should never expect they are
scheduled in a FIFO order (or LIFO or any order at all). That's why it's
called "unfair thread synchronization", and when your application absolutely
requires a fair thread synchronization (in a certain order) you shouldn't
use the .NET framework at all.

Why is that?
- When the CLR decides to kick a GC run, it determines which threads are
executing managed code and which are executing unmanaged code. When done the
CLR suspends the managed threads, unmanaged threads are treated specially
and can continue to run as long as they don't try to return to managed code.
Whenever the OS suspends a thread, it stops the thread waiting for a
synchronization object, later when the thread resumes, all suspended threads
start a race to obtain ownership of the synchronization object that it was
waiting on before the suspend. The result is that the threads (waiting for a
certain synchronization object) loose their order in the wait queue, and
loosing their order can possibly mean they don't get serviced for a long
period or worse they don't get scheduled at all.

- Other .NET API's that re-queue the wait order are WaitAll, WaitAny and
WaitOne.

Willly.
Nov 16 '05 #8
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
And what if the CurrentThread never equals the myArrayList[0] thread?
*One* of the ones which is unblocked by a call to PulseAll (sorry about
using the Java terminology before!) will be. Then everything moves down
the list (a queue would be better than an ArrayList here) and next time
the next thread gets a go.
This what I meant in my previous reply, don't count on it, the CLR doesn't
guarantee "fairness", so it's possible the thread your waiting for never get
serviced.
AFAIK there is no solution to this in managed world.


There is, and it can be encapsulated, I'm sure. It's probably not a bad
thing to write a utility class for - I'll give it a go when I get some
time.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 16 '05 #9
Jon, you said:

<quote>
Yes - it's nastily inefficient, as you could have lots of threads which
end up taking most of the time calling Sleep. Instead, use a monitor
and Wait on it, then call NotifyAll on the monitor when you come out of
the appropriate block.
</quote>

Regarding the use of

while(myArrayList[0] != Thread.CurrentThread)
Thread.Sleep(10);

Lets say the average thread has to wait 50ms, so makes the call 5 times.
I'm not sure of the overhead of that versus the overhead of something
like

Monitor.Enter( )

I could see three things going on.

a) the waiting thread goes to sleep and is somehow woken up by the
locking thread calling Monitor.Exit( )

b) the waiting thread constantly checks to see if it can Enter( ).

c) somewhere in between, where it sleeps for a short period then checks
- something like what I coded above.
Obviously the best way would be a) but I'm not even sure it works like
this in the first place.

If indeed it *does* work this way, then I suppose instead of doing

while(myArrayList[0] != Thread.CurrentThread)
Thread.Sleep(10);

you could add it to a FIFO and somehow get it to sleep indefinitly (how
so?). Then when the CS thread exits it wakes the thread at the front of
the queue

--
Wal
http://www.vooose.com

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!
Nov 16 '05 #10
vooose <no****@microsoft.com> wrote:
<quote>
Yes - it's nastily inefficient, as you could have lots of threads which
end up taking most of the time calling Sleep. Instead, use a monitor
and Wait on it, then call NotifyAll on the monitor when you come out of
the appropriate block.
</quote>

Regarding the use of

while(myArrayList[0] != Thread.CurrentThread)
Thread.Sleep(10);

Lets say the average thread has to wait 50ms, so makes the call 5 times.
I'm not sure of the overhead of that versus the overhead of something
like

Monitor.Enter( )

I could see three things going on.

a) the waiting thread goes to sleep and is somehow woken up by the
locking thread calling Monitor.Exit( )

b) the waiting thread constantly checks to see if it can Enter( ).

c) somewhere in between, where it sleeps for a short period then checks
- something like what I coded above.
The OS has ways of waking threads up efficiently - more efficiently
than your code. (This isn't hard, as it gets to schedule the threads in
the first place.)
Obviously the best way would be a) but I'm not even sure it works like
this in the first place.

If indeed it *does* work this way, then I suppose instead of doing

while(myArrayList[0] != Thread.CurrentThread)
Thread.Sleep(10);

you could add it to a FIFO and somehow get it to sleep indefinitly (how
so?). Then when the CS thread exits it wakes the thread at the front of
the queue


Waking just the thread at the front of the queue is hard, unless each
thread waits on a different monitor and you just notify the monitor at
the head of the list. That could potentially become problematic if you
have a long list - I *believe* the CLR is geared towards there not
being many locks "active" at a time, although I could be wrong.

Using NotifyAll on a single monitor would wake up more threads than you
really want, of course, but would be efficient in terms of monitors.

You could perhaps use a hybrid solution - have a limited number of
monitors (8, say) and use them in turn. That way you'd only end up
waking up n/8 threads at any one time (where n is the size of the
waiting list) but you wouldn't be using up too many monitors.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 16 '05 #11

"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
And what if the CurrentThread never equals the myArrayList[0] thread?


*One* of the ones which is unblocked by a call to PulseAll (sorry about
using the Java terminology before!) will be. Then everything moves down
the list (a queue would be better than an ArrayList here) and next time
the next thread gets a go.
This what I meant in my previous reply, don't count on it, the CLR
doesn't
guarantee "fairness", so it's possible the thread your waiting for never
get
serviced.
AFAIK there is no solution to this in managed world.


There is, and it can be encapsulated, I'm sure. It's probably not a bad
thing to write a utility class for - I'll give it a go when I get some
time.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

Jon, vooose,

You can't predict the unpredictable.
My point is that the CLR doesn't guarantee "fair thread" synchronization
when waiting for a common synchronization object (see my other postings).
Trying to synchronize threads in a fixed/predetermined order is highly
inefficient (or impossible).

To illustrate my point I made following code sample[1].
The main thread creates and starts x number of worker threads, and fills a
queue with work items. Each work item in this sample identifies the thread
that should handle the item.
The items are stored in ascending order starting with 0 up to noThreads.

Compile the code and run it, which the time it takes to handle the few items
and watch also the number of context switches!
To make it worse, just throw-in some IO calls (kernel transitions) or some
GC work (see code).
To look at the result when the work item is free to run on any thread,
un-comment the following block (and watch the thread sequence).
if (Convert.ToInt32(Thread.CurrentThread.Name) !=
(int)workToBeDone.Peek())
{
Monitor.Pulse(workToBeDone);
return null;
}

Willy.

[1]
// --- begin of code
using System;
using System.Text;
using System.Threading;
using System.Collections;

public class MyWorkQueue
{
// Work item queue
private Queue workToBeDone = new Queue();

public void AddWorkItem(object item)
{
// lock the worker queue
lock (workToBeDone)
{
workToBeDone.Enqueue(item);
// Notify a single worker (or all workers ).
Monitor.Pulse(workToBeDone);
// Monitor.PulseAll(workToBeDone);
}
}

public object GetWorkItemFromQueue()
{
lock (workToBeDone)
{
while (workToBeDone.Count == 0 )
{
// Block/Wait until pulsed
Monitor.Wait(workToBeDone);
// Handle possible race here.
// Another thread can have handled the item in between Pulse and Wait
returning.
if (workToBeDone.Count == 0)
Console.WriteLine("[{0}] other thread came in and did his job (woken
for nothing!)", Thread.CurrentThread.Name);
}
// OK, whe have an item, should we handle it?
if (Convert.ToInt32(Thread.CurrentThread.Name) !=
(int)workToBeDone.Peek())
{
// No, it's another thread's work, so pulse and return null, but keep the
item on the queue.
Monitor.Pulse(workToBeDone);
return null;
}
// it's ours, so remove item from the queue and return it.
return workToBeDone.Dequeue();
}
}
}

class Test
{
static MyWorkQueue q = new MyWorkQueue();
static int itemsToGo = 0;
static object locker = new object();
static StringBuilder sb = new StringBuilder();
static void Worker()
{
string n = Thread.CurrentThread.Name;
while (true)
{
object o;
if ((o = q.GetWorkItemFromQueue()) != null)
{
int i = (int) o;
lock (locker) { --itemsToGo; sb.Append(n);}
// Do your critical work here.
// Trow in some GC work in order to make it some more inefficient.
// GC.Collect(0);
}
}
}

static void Main()
{
// create workers
int noThreads = 4;
Thread[] ta = new Thread[noThreads];
for (int t = 0; t < noThreads ; t++)
{
ta[t] = new Thread (new ThreadStart(Worker));
ta[t].Name = t.ToString();
ta[t].IsBackground = true;
}
for (int t = 0; t < noThreads ; t++)
{
Console.WriteLine("Thread:{0} started", ta[t].Name);
ta[t].Start();
}

const int totalItems = 40;
while (true)
{
Thread.Sleep(500);
lock (locker)
{
// wait if still more than x work items to go
if (itemsToGo > 20) continue;
Console.WriteLine("{0}", itemsToGo);
itemsToGo += totalItems;
// dump thread sequence to console
Console.WriteLine(sb.ToString());
sb.Length = 0;
}
Console.WriteLine("Add more work");
int n = 0;
for (int i = 0; i < totalItems; ++i)
{
q.AddWorkItem(n++);
if (n == noThreads)
n = 0;
}
}
}
}// --- end of code
Nov 16 '05 #12
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
You can't predict the unpredictable.
No, but you can provide predictable services over unpredictable ones.
My point is that the CLR doesn't guarantee "fair thread" synchronization
when waiting for a common synchronization object (see my other postings).
Trying to synchronize threads in a fixed/predetermined order is highly
inefficient (or impossible).
I don't see why it has to be either of them.
To illustrate my point I made following code sample[1].


That only shows that the way you did it isn't a good way to do it. I
could show you a string being built up inefficiently, but that wouldn't
prove that StringBuilder doesn't exist :)

Note too that your example is trying to solve a slightly different
problem to the one originally posed, namely releasing threads in the
order they were suspended in.

While an ordered release mechanism will certainly be somewhat less
efficient than an unordered one, I don't think it needs to be *highly*
inefficient, and it's certainly not impossible.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 16 '05 #13
Jon,

See inline ***

Willy.

"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
You can't predict the unpredictable.
No, but you can provide predictable services over unpredictable ones.

*** Not if you have to rely on the unpredictable services.
My point is that the CLR doesn't guarantee "fair thread" synchronization
when waiting for a common synchronization object (see my other postings).
Trying to synchronize threads in a fixed/predetermined order is highly
inefficient (or impossible).


I don't see why it has to be either of them.

- Inefficient - because you don't control the thread that is awoken you are
forced to suspend it again incuring a context switch if it's not the 'right'
thread,
- impossible - when a certain thread never wakes up again (or doesn't switch
context) - due to dynamic priority changes (f.i after IO run down),
transitioning into unmanaged code etc....
To illustrate my point I made following code sample[1].


That only shows that the way you did it isn't a good way to do it. I
could show you a string being built up inefficiently, but that wouldn't
prove that StringBuilder doesn't exist :)


*** No, please don't, just show me what I did wrong :-).
Note too that your example is trying to solve a slightly different
problem to the one originally posed, namely releasing threads in the
order they were suspended in.
*** What I was showing is that it's highly inefficient to try to resume
threads in a predetermined (well defined) order.
IMO, what OP is trying to do is to resume the thread's procedures in the
order they where suspended. (ie. a well defined order), I don't thing it's
problem was to suspend in a specific order.
And that's exactly the problem, you don't know the order they are suspended,
only the CLR knows, and the CLR re-orders it's internal thread queue
- after a GC run (and this cannot be prevented),
- all managed wait methods suspend the calling threads (in an alertable
state), this will force the thread to stop waiting for a synchronization
object and to re-order its wait.

While an ordered release mechanism will certainly be somewhat less
efficient than an unordered one, I don't think it needs to be *highly*
inefficient, and it's certainly not impossible.


*** I'm sure it's possible, but not using the thread synchronization
primitives as present in .NET v1.x, they introduce to much context switching
and that's bad.
Sure implementing a "cooperative thread scheduler" using fibers in v2.x can
solve this issue, but that's yet another story.
Nov 16 '05 #14
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
You can't predict the unpredictable.
No, but you can provide predictable services over unpredictable ones.

*** Not if you have to rely on the unpredictable services.


So long as you don't rely on them being predictable when they're not,
it's fine - you allow for the unpredictability. That's how TCP/IP
works, for example - it builds a reliable service over an unreliable
one through retries etc.
My point is that the CLR doesn't guarantee "fair thread" synchronization
when waiting for a common synchronization object (see my other postings).
Trying to synchronize threads in a fixed/predetermined order is highly
inefficient (or impossible).


I don't see why it has to be either of them.


- Inefficient - because you don't control the thread that is awoken you are
forced to suspend it again incuring a context switch if it's not the 'right'
thread


Yes - but you can reduce that substantially so that although it's less
efficient, it doesn't become prohibitively inefficient.
- impossible - when a certain thread never wakes up again (or doesn't switch
context) - due to dynamic priority changes (f.i after IO run down),
transitioning into unmanaged code etc....
If a thread doesn't wake up when there's no reason why it shouldn't (if
it's waiting patiently to be woken up) then I think it's a failure of
the unpredictable threading. Just because it's unpredictable in some
ways doesn't mean it should be regarded as unreliable in others. (Or
rather, if it's unreliable then the unreliability is shown in normal
code which doesn't try to build a predictable service on top of it.)
To illustrate my point I made following code sample[1].


That only shows that the way you did it isn't a good way to do it. I
could show you a string being built up inefficiently, but that wouldn't
prove that StringBuilder doesn't exist :)


*** No, please don't, just show me what I did wrong :-).


For a start, you didn't use my suggestions from earlier on :)
Note too that your example is trying to solve a slightly different
problem to the one originally posed, namely releasing threads in the
order they were suspended in.


*** What I was showing is that it's highly inefficient to try to resume
threads in a predetermined (well defined) order.


Well, it's inefficient the way you did it, certainly. I can reasonably
make it significantly more efficient.

On thinking about it, the problem your code solved is indeed close to
the original question - it's just not how I'd have shown it. (I'd have
built an equivalent of Wait/Pulse, where the order of calling Wait is
the order in which the threads are resumed.)
IMO, what OP is trying to do is to resume the thread's procedures in the
order they where suspended. (ie. a well defined order), I don't thing it's
problem was to suspend in a specific order.
Not sure what you mean there.
And that's exactly the problem, you don't know the order they are suspended,
only the CLR knows, and the CLR re-orders it's internal thread queue
- after a GC run (and this cannot be prevented),
- all managed wait methods suspend the calling threads (in an alertable
state), this will force the thread to stop waiting for a synchronization
object and to re-order its wait.


You know the order in which they're suspended if you're the one
suspending them by calling Wait...
While an ordered release mechanism will certainly be somewhat less
efficient than an unordered one, I don't think it needs to be *highly*
inefficient, and it's certainly not impossible.


*** I'm sure it's possible, but not using the thread synchronization
primitives as present in .NET v1.x, they introduce to much context switching
and that's bad.
Sure implementing a "cooperative thread scheduler" using fibers in v2.x can
solve this issue, but that's yet another story.


It sounds like I'm going to actually have to implement this in order to
persuade you, unless the following description works...

1) You keep a Queue, each element of which is a Thread
2) You keep an array of objects, the size of which is fixed at creation
of the encapsulating class. These act as the locks
3) When a thread calls the equivalent to Wait, it is added to the queue
and waits on the next object. A counter is kept for "the next object to
wait on" and "the next object to pulse". The counters wrap round, so
that the n+1st thread added waits on the same object as the 1st.
4) When a thread calls the equivalent of Pulse, Monitor.PulseAll is
called for the next object (using the counter). The calling thread then
waits for the woken thread to notice that it has been woken up. (This
part is inefficient, and can possibly be avoided. It's still easily
possible using just Monitor.Wait and Monitor.Pulse, with a separate
lock, however.)
5) Each of the threads associated with the object which has been
notified wakes up, checks whether or not it's time for it to run, and
waits again if not. If it is, it notifies the separate lock so that
everyone knows that that thread is effectively dequeued.

By judging the number of monitors to create appropriately, you can get
a balance between having too many monitors active at a time and having
too many context switches. For instance, with just 8 objects (i.e. not
taking up much of the CLR's estimate of how much the system will use)
you can divide the number of threads woken by the call to PulseAll by
8. That would significantly reduce the inefficiency seen in your
example.

Do you see what I mean? If I do end up writing this, it'll be a while
before it's ready - I've got various other threading emails to answer
which take priority, unfortunately :( (In my new job I can't do any of
this at work, hence the posting frequency reduction...)

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 16 '05 #15

"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...


Jon,

Waiting for you to persuade me :-)
Just some remarks though, you said:
Your argument about what's wrong in my code is weak at best.
At least I showed you some code, you where only suggesting to use separate
locks (which may lessen the inefficiency issue, but not solve it
completely - and to me, some useless context switches are a waste of CPU
resources) :-), while I always said that waiting on a common synchronization
object (a single SynchBlock) leads to inefficient code, and that's what I
showed OP and you.
You know the order in which they're suspended if you're the one
suspending them by calling Wait... That's the whole point (my point) by calling wait, you possibly induce a GC
run, and when that happens the GC suspends all threads in an order
determined by the GC.
If a thread doesn't wake up when there's no reason why it shouldn't (if
it's waiting patiently to be woken up) then I think it's a failure of
the unpredictable threading. Just because it's unpredictable in some
ways doesn't mean it should be regarded as unreliable in others. (Or
rather, if it's unreliable then the unreliability is shown in normal
code which doesn't try to build a predictable service on top of it.)


I didn't say it's unreliable, I said it wasn't "fair". Everyone knows by now
that, due to the presence of a GC, the CLR uses a "NON FAIR thread
synchronizing) mechanism through the Monitor class, and there's no way to
make it fair. If your application absolutely requires "fair thread
synchronization" you shouldn't use the CLR as platform. Normal code that
doesn't require fair thread synchronization will run just fine.

Willy.
Nov 16 '05 #16

"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
> Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
(In my new job I can't do any of this at work, hence the posting frequency reduction...)

Jon,

Great, congratulations and all the best with your new job.

Willy.


Nov 16 '05 #17
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
Waiting for you to persuade me :-)
Just some remarks though, you said:
Your argument about what's wrong in my code is weak at best.
I don't see why - you're making all your threads wait on a single
monitor when that's not necessary. Why is that a weak argument against
your code, when your code is trying to show inherent inefficiency?
At least I showed you some code, you where only suggesting to use separate
locks
Yes, I don't have the time to write a full example at the moment. I may
have by the end of the week - I've spent half of this evening clearing
out backlogs of news and mail (and haven't quite finished, but I'm
getting there). I think I gave enough suggestions to show that your
code wasn't the most efficient way to go.
(which may lessen the inefficiency issue, but not solve it
completely - and to me, some useless context switches are a waste of CPU
resources) :-)
They're a waste if you don't want the predictability. If you want the
predictability and are willing to pay a reasonably small price, it's
not a waste at all.
while I always said that waiting on a common synchronization
object (a single SynchBlock) leads to inefficient code, and that's what I
showed OP and you.


You said more than that though - you said that trying to synchronize
threads in a fixed/predetermined order was highly inefficient or
impossible. I reckon it's feasible to make it only minorly inefficient
- at least for reasonable scenarios (where you don't have thousands of
threads).
You know the order in which they're suspended if you're the one
suspending them by calling Wait...

That's the whole point (my point) by calling wait, you possibly induce a GC
run, and when that happens the GC suspends all threads in an order
determined by the GC.


I think we're talking at cross-purposes here. Calling Wait involves
entering a monitor first, and at that point there's a definite ordering
involved.
If a thread doesn't wake up when there's no reason why it shouldn't (if
it's waiting patiently to be woken up) then I think it's a failure of
the unpredictable threading. Just because it's unpredictable in some
ways doesn't mean it should be regarded as unreliable in others. (Or
rather, if it's unreliable then the unreliability is shown in normal
code which doesn't try to build a predictable service on top of it.)


I didn't say it's unreliable, I said it wasn't "fair". Everyone knows by now
that, due to the presence of a GC, the CLR uses a "NON FAIR thread
synchronizing) mechanism through the Monitor class, and there's no way to
make it fair. If your application absolutely requires "fair thread
synchronization" you shouldn't use the CLR as platform. Normal code that
doesn't require fair thread synchronization will run just fine.


Well, you talked about a thread never waking up again - that was one of
the reasons you gave for it being impossible to write a mechanism for
releasing threads in the same order as they're suspended. If a thread
never wakes up when it should do (i.e. when it's runnable) that
suggests it's unreliable for general use - at least under the
conditions that prevent the thread from ever running

I'm not talking about making threading in general fair - just about
introducing a reasonably efficient way of making threads suspend and
then resuming them in the order in which they suspended. I believe
that's what the OP was after. Monitor.Wait/Pulse/PulseAll doesn't
provide it out of the box, but it can be built on top of them.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 16 '05 #18

"Willy Denoyette [MVP]" <wi*************@pandora.be> wrote in message
news:uo**************@TK2MSFTNGP11.phx.gbl...

I didn't say it's unreliable, I said it wasn't "fair". Everyone knows by now
that, due to the presence of a GC, the CLR uses a "NON FAIR thread
synchronizing) mechanism through the Monitor class, and there's no way to
make it fair. If your application absolutely requires "fair thread
synchronization" you shouldn't use the CLR as platform. Normal code that
doesn't require fair thread synchronization will run just fine.


Getting in late on this conversation but I would like to believe (like Jon) that
there is a way to layer one's own mechanism on top of the CLR in order
to achieve fairness. It's not fair ;-) to tell someone that they can't use the
CLR (or Win32) just because the platform does not natively provide a fair
mechanism. If fairness is required by an application, then build a mechanism
that provides it (and don't fret about the extra context switches).

(If I'm way out of line here, I apologize in advance; just started reading this
newsgroup after a hiatus of a year or two and I missed the early part of this
discussion.)

-- jeff
Nov 16 '05 #19

"jeff" <ms**********@xoxy.net> wrote in message
news:Oh**************@TK2MSFTNGP10.phx.gbl...

"Willy Denoyette [MVP]" <wi*************@pandora.be> wrote in message
news:uo**************@TK2MSFTNGP11.phx.gbl...
to tell someone that they can't use the CLR (or Win32) just because the platform does not natively provide a fair
mechanism. If fairness is required by an application, then build a
mechanism
that provides it (and don't fret about the extra context switches).

Looks like I'm not alone to believe it:

http://www.codeguru.com/Csharp/.NET/...icle.php/c4647

Willy.
Nov 16 '05 #20
Jon,

Inline ***

Willy.

"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
Waiting for you to persuade me :-)
Just some remarks though, you said:
Your argument about what's wrong in my code is weak at best.
I don't see why - you're making all your threads wait on a single
monitor when that's not necessary. Why is that a weak argument against
your code, when your code is trying to show inherent inefficiency?


*** No, I didn't want to show inefficiency, I only wanted to illustrate the
"un-fairness" of the CLR when using Monitor classes as synchronization
mechanism, and I only wanted to warn OP and others about this behavior. And
note that you changed your mind only recently when you proposed the hybrid
solution (which is still somewhat inefficient be it less, unless you are
using a single lock per thread).
At least I showed you some code, you where only suggesting to use
separate
locks


Yes, I don't have the time to write a full example at the moment. I may
have by the end of the week - I've spent half of this evening clearing
out backlogs of news and mail (and haven't quite finished, but I'm
getting there). I think I gave enough suggestions to show that your
code wasn't the most efficient way to go.

*** No, you didn't, you only gave suggestions to OP before I posted the
code, and after I illustrated the "un-fairness" when waiting on a common
SynchBloc (resulting in inefficiency when trying to make it behave like it
was "fair"), you said it was inefficient and you gave anough suggestions to
make it more efficient.

(which may lessen the inefficiency issue, but not solve it
completely - and to me, some useless context switches are a waste of CPU
resources) :-)


They're a waste if you don't want the predictability. If you want the
predictability and are willing to pay a reasonably small price, it's
not a waste at all.


*** And what do you call a reasonable price?
while I always said that waiting on a common synchronization
object (a single SynchBlock) leads to inefficient code, and that's what I
showed OP and you.
You said more than that though - you said that trying to synchronize
threads in a fixed/predetermined order was highly inefficient or
impossible. I reckon it's feasible to make it only minorly inefficient
- at least for reasonable scenarios (where you don't have thousands of
threads).


*** I have a something similar using a single lock per thread, it works fine
on a single CPU box, but fails some time on a 4 way SMP box unless I pin
each thread to a specific CPU (using CPU mask).
> You know the order in which they're suspended if you're the one
> suspending them by calling Wait... That's the whole point (my point) by calling wait, you possibly induce a
GC
run, and when that happens the GC suspends all threads in an order
determined by the GC.


I think we're talking at cross-purposes here. Calling Wait involves
entering a monitor first, and at that point there's a definite ordering
involved.

*** Calling Wait requires you to own the SynchBlok, but calling Wait can
induce a GC run (the CLR is prepared for this), suspending all managed
threads and doing some funny stuff with threads that are trying to return
from unmanaged land, and a GC run will re-order the Monitor wait queue in
the CLR (unles ther's only a single lock :-)).
> If a thread doesn't wake up when there's no reason why it shouldn't (if
> it's waiting patiently to be woken up) then I think it's a failure of
> the unpredictable threading. Just because it's unpredictable in some
> ways doesn't mean it should be regarded as unreliable in others. (Or
> rather, if it's unreliable then the unreliability is shown in normal
> code which doesn't try to build a predictable service on top of it.)
I didn't say it's unreliable, I said it wasn't "fair". Everyone knows by
now
that, due to the presence of a GC, the CLR uses a "NON FAIR thread
synchronizing) mechanism through the Monitor class, and there's no way to
make it fair. If your application absolutely requires "fair thread
synchronization" you shouldn't use the CLR as platform. Normal code that
doesn't require fair thread synchronization will run just fine.


Well, you talked about a thread never waking up again - that was one of
the reasons you gave for it being impossible to write a mechanism for
releasing threads in the same order as they're suspended. If a thread
never wakes up when it should do (i.e. when it's runnable) that
suggests it's unreliable for general use - at least under the
conditions that prevent the thread from ever running

*** I have testcases running on large SMP boxes and I can simulate thread
starvation when not taking care when using Monitor methods to make threads
cooperate this way.

Monitor.Wait/Pulse/PulseAll doesn't provide it out of the box, but it can be built on top of them.


*** Agreed, but before I can make it reasonable fail-safe, I stick with
unmanaged code for this.
Willy.
Nov 16 '05 #21
"Willy Denoyette [MVP]" <wi*************@pandora.be> wrote in message
news:ec**************@TK2MSFTNGP12.phx.gbl...


Looks like I'm not alone to believe it:

http://www.codeguru.com/Csharp/.NET/...icle.php/c4647


As far as I can tell, Richter is saying that you can't do fair scheduling by using only
the .NET synchronization primitives. He doesn't talk at all about the possibility
of using your own queue for ensuring fairness.

-- jeff
Nov 16 '05 #22

"Willy Denoyette [MVP]" <wi*************@pandora.be> wrote in message
news:u1**************@tk2msftngp13.phx.gbl...

*** Agreed, but before I can make it reasonable fail-safe, I stick with
unmanaged code for this.


Weren't there some problems with fairness in the Win32 primitives as well?

-- jeff
Nov 16 '05 #23

"jeff" <ms**********@xoxy.net> wrote in message
news:uI**************@TK2MSFTNGP11.phx.gbl...

"Willy Denoyette [MVP]" <wi*************@pandora.be> wrote in message
news:u1**************@tk2msftngp13.phx.gbl...

*** Agreed, but before I can make it reasonable fail-safe, I stick with
unmanaged code for this.


Weren't there some problems with fairness in the Win32 primitives as well?

-- jeff

Jeff,

The Win32 thread scheduler uses a round-robin scheme build around a number
priority based queues. The scheduler has mechanism in place to provide
reasonable fair thread scheduling, but as you know nothing is perfect in
this business so it's possible there are/were some glitches.
Also you shouldn't compare the OS scheduler with the light weight CLR
"scheduler", they server some different purposes, the first has to manage
all threads in all processes (so it has to be reasonable fair) , the CLR has
only to manage it's process wide threads and is far less sophisticated (he
can't/shouldn't be) than the former. Another point is that the CLR "unfair
thread synchronization" is not necessarily a bad thing, it's generally more
perform than fair thread scheduling.
I remember having used some "fair thread scheduler" for Java a couple of
years ago, but this was on U**x using POSIX threads (Pthreads), don't know
if we can expect something on the CLR though.

Willy.
Nov 16 '05 #24

"jeff" <ms**********@xoxy.net> wrote in message
news:OV**************@tk2msftngp13.phx.gbl...
"Willy Denoyette [MVP]" <wi*************@pandora.be> wrote in message
news:ec**************@TK2MSFTNGP12.phx.gbl...


Looks like I'm not alone to believe it:

http://www.codeguru.com/Csharp/.NET/...icle.php/c4647


As far as I can tell, Richter is saying that you can't do fair scheduling
by using only
the .NET synchronization primitives. He doesn't talk at all about the
possibility
of using your own queue for ensuring fairness.

-- jeff


Jeff,

Not exactly, he says you can't make it "fair" using the Monitor class and
it's primitives (CLR Wait/Pulse/PulseAll), the problem is not the queue.
Note that the term "fair" is somewhat overloaded when talking about thread
synchronization, strictly speaking it means that all threads in a system
get's the same chance(1) to be on a CPU for the same amount of time(2). The
latter cannot/shouldn't be guaranteed when running a pre-empting scheduler
using different priority chains, but IMO the latest Windows OS'ses do a fair
job to achieve the first.

Willy.


Nov 16 '05 #25
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om...
Willy Denoyette [MVP] <wi*************@pandora.be> wrote:
Waiting for you to persuade me :-)
Just some remarks though, you said:
Your argument about what's wrong in my code is weak at best.
I don't see why - you're making all your threads wait on a single
monitor when that's not necessary. Why is that a weak argument against
your code, when your code is trying to show inherent inefficiency?


*** No, I didn't want to show inefficiency


Then why did you talk about inefficiency with respect to it? "Compile
the code and run it, which the time it takes to handle the few items
and watch also the number of context switches!" That sounds like an
emphasis on inefficiency to me.
I only wanted to illustrate the
"un-fairness" of the CLR when using Monitor classes as synchronization
mechanism, and I only wanted to warn OP and others about this behavior. And
note that you changed your mind only recently when you proposed the hybrid
solution (which is still somewhat inefficient be it less, unless you are
using a single lock per thread).
Well, I proposed the hybrid solution before you presented your code, so
I don't think it was *that* recently. Even the non-hybrid solution
would be more efficient than the code originally presented by vooose.
At least I showed you some code, you where only suggesting to use
separate
locks


Yes, I don't have the time to write a full example at the moment. I may
have by the end of the week - I've spent half of this evening clearing
out backlogs of news and mail (and haven't quite finished, but I'm
getting there). I think I gave enough suggestions to show that your
code wasn't the most efficient way to go.

*** No, you didn't, you only gave suggestions to OP before I posted the
code, and after I illustrated the "un-fairness" when waiting on a common
SynchBloc (resulting in inefficiency when trying to make it behave like it
was "fair"), you said it was inefficient and you gave anough suggestions to
make it more efficient.


I suggest you have another look at the timestamps on posts. You posted
your code at 13:58 yesterday. I posted my hybrid suggestion at 06:57
yesterday. (Both times GMT.)
(which may lessen the inefficiency issue, but not solve it
completely - and to me, some useless context switches are a waste of CPU
resources) :-)


They're a waste if you don't want the predictability. If you want the
predictability and are willing to pay a reasonably small price, it's
not a waste at all.


*** And what do you call a reasonable price?


That depends on the application, of course. The hybrid solution can be
tuned, of course - and if you end up only using one thread per lock
(which I think would be the most common case for most applications) you
don't get much inefficiency at all. Bear in mind that your code did no
actual *work* there - in a real app where work items could take
significant amounts of time, the inefficiency of a few context switches
whenever another thread was released could easily be lost in the noise.
while I always said that waiting on a common synchronization
object (a single SynchBlock) leads to inefficient code, and that's what I
showed OP and you.


You said more than that though - you said that trying to synchronize
threads in a fixed/predetermined order was highly inefficient or
impossible. I reckon it's feasible to make it only minorly inefficient
- at least for reasonable scenarios (where you don't have thousands of
threads).


*** I have a something similar using a single lock per thread, it works fine
on a single CPU box, but fails some time on a 4 way SMP box unless I pin
each thread to a specific CPU (using CPU mask).


That sounds like either a bug in the code or a bug in .NET threading -
without seeing the code it would be impossible to say for sure. Can you
see any theoretical reason why it *should* fail?
I think we're talking at cross-purposes here. Calling Wait involves
entering a monitor first, and at that point there's a definite ordering
involved. *** Calling Wait requires you to own the SynchBlok, but calling Wait can
induce a GC run (the CLR is prepared for this), suspending all managed
threads and doing some funny stuff with threads that are trying to return
from unmanaged land, and a GC run will re-order the Monitor wait queue in
the CLR (unles ther's only a single lock :-)).
But the whole point is that we're not *relying* on the monitor wait
queue, because we've got our own queue. That's how we achieve the (very
limited) fairness.
Well, you talked about a thread never waking up again - that was one of
the reasons you gave for it being impossible to write a mechanism for
releasing threads in the same order as they're suspended. If a thread
never wakes up when it should do (i.e. when it's runnable) that
suggests it's unreliable for general use - at least under the
conditions that prevent the thread from ever running


*** I have testcases running on large SMP boxes and I can simulate thread
starvation when not taking care when using Monitor methods to make threads
cooperate this way.


That sounds interesting. Just so I can check that we're not talking at
cross-purposes, are you getting to a situation where the CPU is idle
and there are threads which *should* be runnable, but aren't getting
anywhere?

I'm not suggesting that my solution makes threads get their fair
timeslice in a basically overloaded system - that kind of fairness is
out of the remit of the OP's request, IMO.
Monitor.Wait/Pulse/PulseAll doesn't
provide it out of the box, but it can be built on top of them.


*** Agreed, but before I can make it reasonable fail-safe, I stick with
unmanaged code for this.


So you agree it's not impossible? Sounds like I'm getting somewhere :)

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 16 '05 #26

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: bughunter | last post by:
Hi, Consider this code: ---- Monitor.Pulse(oLock); Monitor.Exit(oLock); ---- If a thread was waiting on oLock then will the current thread
2
by: Jack David | last post by:
Using the code below I am able to monitor a single directory for a new file and then kick-off a process to deal with the file. The question is??? How would I modify this code to be able to monitor...
4
by: Vittorio Pavesi | last post by:
Hello, I'm using CDO in my VB Application. Does anybody know how to set the Mail priority (Urgent, Medium, Low) ?? Thanks Vittorio...
1
by: Kevin | last post by:
In a newsgroup thread from Jan 8, 2003 between Barry Holsinger and the VBDotNet Team, please review this excerpt: "You understood my problem completely. Your sample code provides a really...
1
by: Mis Dep. | last post by:
Dear all how can i monitor web service and check user connect from web service to sql server Brg , TingN@ng
1
by: DR | last post by:
What ports do i need to unblock on client and server (running msvsmon.exe) to debug remotely from my client box with visual studio 2005 pro? When I attach to remote process a connection shows up...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.