[boost] Re: boost::shared_ptr and atomic_count_linux.hpp

From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2002-06-03 13:03:09

Peter Dimov wrote:
> 
> From: "Alexander Terekhov" <terekhov_at_[hidden]>
> > Darin Adler wrote:
> > [...]
> > > Once we found this out, Peter Dimov and others changed smart_ptr
> > > so that it doesn't use this header any more. They also made other
> > > improvements to the thread safety code to make it simpler and faster.
> > > The current version of Boost, 1.28.0, has this fixed.
> >
> > Memory visibility (acquire-on-lock/release-on-unlock semantics) aside,
> > the 'lwm' stuff in CVS (the one full of sched_yield()/winapi::Sleep(0))
> > is BROKEN... unless, of course, ALL boost MT client applications are
> > meant for deployment on scheduling allocation domains of size ONE
> > (uniprocessors) ONLY... WITH FIFO/RR priority scheduling {POSIX realtime
> > option} among *ALL-EQUAL-PRTY* threads.
> >
> > regards,
> > alexander.
> >
> > P.S. "....Similarly, sched_yield() can be used to resolve some problems
> >       on a uniprocessor, though such problems can usually be solved more
> >       cleanly in other ways. Using sched_yield() will never solve a
> > problem
> >       (unless the problem statement is "the performance is too good") on
> > a
> >       multiprocessor, and you should never use it there."
> > --Butenhof_at_c.p.t
> 
> Butenhof is right; 

;-)

> sched_yield does not affect the correctness of the code, only its performance.
> 
> In this particular case, the yield is necessary. On a single processor, the
> spinlock will never acquire if it fails the first time, and will spin madly
> until the time slice elapses. On multiple CPUs, there is a chance that a
> subsequent iteration will acquire, but my timing tests showed that, contrary
> to my intuitive understanding, an immediate yield offers the best
> performance.
> 
> sched_yield aside, lwm_* is most certainly "broken" as a general
> synchronization primitive; it's only useful in lock-do something quickly,
> like increment a count-unlock scenarios.

Well, again, MP w.r.t. NO-scheduling-rules-defined-whatsoever [in POSIX] 
*and* PROPER memory sync./visibility/coherency protocol aside, consider: 

< from my e-mail archive, censored >

-----

Well, it seems that you are right with the Sleep() call and Windows
priorities.
This beats everything that i ever thought about Windows. If a higher prior
thread can block all lower ones from running, than i know why Windows runs
that bad (or is it the best real time OS and no one knows it).

-----

> Every thread will run sometimes even low priority ones.

Not true. Windows implements priority scheduling (RR).
Some versions do randomly boost priority (to solve the
priority inversion problem) but only when the system
knows that a higher priority thread(s) is/are blocked 
on the synchronization object(s) (critical sections
internaly use event kernel object to handle contention,
AFAIK). see:

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/prothred_75ir.asp
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/prothred_8gq6.asp

Another Windows feature is "dynamic priorities":

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/prothred_3gj7.asp

but since it is *event driven* (could be disabled and does 
not work for all base priorites) that is irrelevant wrt the 
problem of livelocking/busy-waiting.

So, I believe that you are wrong.

If you disagree than I would appreciate if in your 
subsequent response(s) (if any) you would provide 
some technical info backing your opinion.

regards,
alexander.

On Fri, <censored>, Alexander Terekhov wrote:

>
>
> > Instead of a critical section a simple loop with a counter could be
> > generated:
> >
> > while( InterlockedIncrement( &Counter ) != 0 )
> > {
> >    InterlockedDecrement( &Counter );
> >    Sleep(0);
> > }
>
> T<censored>, Sleep(0) (or yield) is a rather useless SCHEDULING
> operation. Unless you are absolutely sure (know and control
> thread priorities, know which thread will be given the
> processing time when you yield your time slice, etc...),
> you should NEVER misuse scheduler in place of having PROPER
> SYNCRONIZATION/BLOCKING. The price of that error is a
> "livelock":

IT IS NOT IF YOU KNOW WHAT YOU ARE DOING AND IN THIS CASE I DO KNOW IT !!!

1. Windows is not a real time system. Every thread will run sometimes,
even low priority ones.
2. The guarded code is small enough and predictable. The only system call
in it is ReleaseSemaphore.
3. The possibilty that the lock is ever needed is nearly zero.
4. Since there is an assembly version of InterlockedCompareExchange i will
not need it.
5. Please do not feed me with msdn documentation.
6. I do not like kernel objects when they are not needed. Windows will
make context switches far to often with them and they will slow down your
program execution.

greetings
<censored>

-----

> Instead of a critical section a simple loop with a counter could be
> generated:
> 
> while( InterlockedIncrement( &Counter ) != 0 )
> {
> 	InterlockedDecrement( &Counter );
> 	Sleep(0);
> }

T<censored>, Sleep(0) (or yield) is a rather useless SCHEDULING 
operation. Unless you are absolutely sure (know and control 
thread priorities, know which thread will be given the 
processing time when you yield your time slice, etc...), 
you should NEVER misuse scheduler in place of having PROPER 
SYNCRONIZATION/BLOCKING. The price of that error is a 
"livelock":

"If a high priority thread executes a busy wait loop,
 it may prevent a lower priority thread from being scheduled.  
 If that lower priority thread is the one which must unblock 
 the busy waiting thread, a situation known as a "livelock" 
 results."

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/prothred_75ir.asp

"However, if you have a thread waiting for another thread 
 with a lower priority to complete some task, be sure to 
 block the execution of the waiting high-priority thread. 
 To do this, use a wait function, critical section, or the 
 Sleep function, SleepEx, or SwitchToThread function. This 
 is preferable to having the thread execute a loop. 

 Otherwise, the process may become deadlocked, because the 
 thread with lower priority is never scheduled."

The bottom lime is that sleep(0)/yield, in general, does NOT 
guarantee that processing time on some processor will be given 
to the thread you are waiting for!! That is the same as pure
busy-waiting which is a "bug" (unless you are running in a
rather special environment with far more control/knowledge
than "normal" application). 

BTW, note that POSIX spinlocks, while being portable themself, 
are NOT meant to be used in "general" portable appls for the 
same reasons/problems -- busy-waiting/livelocking/priority
inversion.

regards,
alexander.

-----

regards,
alexander.