semaphores vs locks?

[Jim Barton]

In article <1989Sep5.185510.7836 at jarvis.csri.toronto.edu>, moraes at csri.toronto.edu (Mark Moraes) writes:
> On an Iris4d multiprocessor, what is the difference between a semaphore
> and a lock? I couldn't find any specific mention of the difference in
> the documentation.  As far as I can tell, semaphores have queues in
> which threads wait till the semaphore is freed, whereas locks are
> continuously retried (assuming ussetlock) with some delay.
> 

Semaphores and spinlocks are standard OS primitives which have existed for
25 years or more.  There are many professors and others who have made their
living writing textbooks about how to use these in operating systems.  For
a description in a UNIX context, Maurice Bach's book, "The Design of the UNIX
Operating System" has a chapter dedicated to multiprocessing, where he
describes how these primitives work (be careful though - there is a bug
in the algorithm for psema() he gives).

Fundamentally, a spinlock is a loop in software that does the following:

	while (!(location changes)) ;

Thus, the spinlock reacts very quickly when the location changes, but some
time may be wasted waiting for it.

A semaphore is a queue with a counter, using a spinlock to protect the queue
and the counter.  Semaphores were originally designed by Edgar Dijkstra, as
documented in the seminal paper "Cooperating Sequential Processes" which
has been reprinted in hundreds of places.

I'm posting a section of the original kernel design document that goes
into some detail on this stuff.

> For a system with hardware locks, which is faster/cheaper - a
> semaphore or a lock? Does a lock consume much cpu time while spinning?
> Is the cost of going to sleep and awakening on a semaphore high? Does
> anyone have any numbers on these?

Cost of a lock < cost of a semaphore.  A semaphore implies that a context
switch may happen, while none happens with a spinlock.  The generic rule
is that if the time spent spinning on the average is greater than the
time to block a process and switch to another one, use a semaphore, else use
a spinlock.

> 
> Is there a section of the manual summarizing the parallel facilities
> available? (Suggestion: Perhaps a future release of the documentation
> could group manual pages by subsection and alphabetically - i.e. all
> manual pages for 3P together, rather than alphabetically across all
> subsections) The following is a list I've created, with some attempt
> to order them in 'recommended reading order'. Have I missed anything?
> 

The list given is complete.  The parallel programmers guide is in final
edit now, and should be available from SGI Real Soon Now.

> Thanks.

-- Jim Barton
Silicon Graphics Computer Systems    "UNIX: Live Free Or Die!"
jmb at sgi.sgi.com, sgi!jmb at decwrl.dec.com, ...{decwrl,sun}!sgi!jmb