Path: utzoo!censor!geac!torsqnt!hybrid!scifi!bywater!uunet!xavax!jat
From: jat@xavax.com (John Tamplin)
Newsgroups: comp.realtime
Subject: Re: Spin locks
Message-ID: <1991Feb3.034819.17011@xavax.com>
Date: 3 Feb 91 03:48:19 GMT
Organization: Xavax
Lines: 38

Spin locks are quite useful in multiprocessor systems, at least in terms
of synchronization between OS's on different processors accessing common
data structures.

However, it is still not perfect.  If n processors are accessing some
shared data structure simultaneously, 1 will get it.  The others will
spin on local copies in their respective caches.  When the lock is released,
the lock gets ping-ponged between the caches with one getting it again.  This
costs n-1 bus cycles moving ownership of the cache line between the processors.
You do it again next time, and so on, until the last processor wins the lock.
Granted, this is worst case, but you can still have O(n^2) bus cycles to get
the lock to all processors.  Additionally, there is only a probabilistic
guarantee of fairness.

If the resources are available, I think hardware semaphores are a much
neater solution.  With the gap between processor and memory speeds increasing,
it is reasonable to assume that large-scale multiprocessors will use some
sort of "request packet" structure (ie, the processor sends a message "read
location 20 and send me the result" and blocks until it gets a response).
With this structure, it would be easy to implement hardware semaphores
that queue requests and send a response to a processor when it owns the
semaphore.  With the depths available in FIFOs, you won't have to worry about
a limited queue, and the interface could be as simple as:

	dummy=[sem0]	/* block until lock granted */
	... critical section ...
	[sem0]=dummy	/* release lock */

This solution guarantees O(n) bus cycles (cycle in this case being a request
packet and a response packet) to solve the same problem as before, which is
optimal.  Also, you can enforce whatever kind of fairness you desire, even
giving certain processors higher priority and ordering the queue by that
priority.  None of this requires any changes to the processor itself, although
the bus interface would have to already support a disconnect-style bus.
-- 
John Tamplin						Xavax
jat@xavax.COM						2104 West Ferry Way
...!uunet!xavax!jat					Huntsville, AL 35801