Xref: utzoo comp.sys.next:5539 comp.os.mach:336
Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!pt.cs.cmu.edu!spice.cs.cmu.edu!mbj
From: mbj@spice.cs.cmu.edu (Michael Jones)
Newsgroups: comp.sys.next,comp.os.mach
Subject: Re: technique used to implement mutex_lock()
Summary: On spinning
Message-ID: <8554@pt.cs.cmu.edu>
Date: 22 Mar 90 19:31:33 GMT
References: <8460@pt.cs.cmu.edu> <429@kgw2.bwi.WEC.COM> <5612@odin.corp.sgi.com>
Distribution: na
Organization: Carnegie-Mellon University, CS/RI
Lines: 41

In article <5612@odin.corp.sgi.com>, jwag@moose.sgi.com (Chris Wagner) writes:
> In article <8460@pt.cs.cmu.edu>, mbj@spice.cs.cmu.edu (Michael Jones) writes:
> > Now to answer your real question.  No, it's not a waste of cpu to spin on a
> > mutex in a correctly written threads application.   A mutex provides mutual
> > exclusion between two threads.  It's intended to be called only when the
> > mutual exclusion is of a short or bounded duration.  It's not the right
> > primitive for unbounded waiting.  Any potentially unbounded waiting should
> > be done using condition_wait and condition_{signal,broadcast} (which
> > don't spin).
> 
> Although in many cases, spinning is a good idea - what happens when a
> thread holds a lock for what it thnks is a short time - however during the
> few instructions it has the lock it gets context switched, other threads
> trying to get the lcok will spin a while then yield. Thats ok as long the
> the number of threads is not too much greater than the number of processors
> - but what happens when you have 100 or more threads going after a single
> lock often, the time till the thread that owns the lock gets to run could
> be fairly long.

The case you describe can certainly happen although it should be quite rare.
A timeslice should be substantially larger than the window during which you
hold a mutex, so this should happen only with probability
(mutex_time)/(slice_time).  (And in actuality, it probably happens far less
than that for the following reason -- mutexes will often be acquired following
a condition_wait; if the condition_wait blocked, the mutex will be acquired at
the beginning of a timeslice.)  Even if it does happen, the cthread_yield() in
the spin loop of mutex_lock() will yield the processor to another thread
within a few dozen (application) instructions, allowing other threads to have
their turn.

That having been said, if you do have a parallel program with 100 threads
contending frequently for a single resource you'll probably incur
synchronization delays no matter what algorithm you use.  Restructuring your
algorithm to avoid this bottleneck might be appropriate.  Profiling your
should help determine if you have a contention bottleneck.  If you have a
potential bottleneck you can at least reduce wasted cycles by protecting this
resource with a condition variable rather than a mutex if contention is
statisticly probably, rather than statisticly unlikely (the case for which
mutexes are appropriate).

				-- Mike