Tech Insider					     Technology and Trends

			      USENET Archives

Path: utzoo!attcan!utgpu!!mailrus!!bionet!ames!sgi!
From: (Jim Barton)
Newsgroups: comp.sys.sgi
Subject: Overview of Parallel Synchronization
Keywords: multiprocessor parallel programming
Message-ID: <>
Date: 7 Sep 89 16:17:00 GMT
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 996

Here is a formatted version of a section of the original IRIX software
specification, written by yours truly.  I can supply the raw MM source to
anyone who wants it.

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

--------------- cut here --------------------

       Section 2					      -	1 -

	      ($Revision: 1.12 $ $Date:	86/09/23 17:27:33 $)

       1.  UNIX_On_Multiprocessors

       Much of the discussion in this section follows that in [1].
       This section assumes that the Clover 2 multiprocessor
       structure will consist of two or	more CPU's that	share
       common memory and peripherals.  Such a structure	can
       potentially provide much	greater	throughput since processes
       can run concurrently on different processors.  Each CPU
       executes	independently, but all of them execute a single
       copy of the kernel.  In general,	processes are unaware that
       they are	running	on a multiprocessor, and can migrate
       between processors transparently.  Unfortunately, a process
       does not	consume	less CPU time.

       Allowing	several	processors to execute simultaneously in	the
       kernel causes integrity problems	unless protection
       mechanisms are used.  The original design of UNIX assumed
       that only a single processor would ever execute the kernel.
       Thus, kernel data structures could be protected by not
       preempting a process in the kernel.  A kernel process gives
       up control of the processor voluntarily,	through	the normal
       UNIX sleep/wakeup mechanism.

       There are three ways in which corruption	of kernel data
       structures can be prevented on a	multiprocessor:

	 1.  Execute the kernel	on one processor only, which
	     protects all kernel data structures but serializes	all
	     system functions.

	 2.  Serialize small sections of code (critical	regions)
	     with locking primitives.  This approach adds locking
	     overhead, and may increase	context	switching.

	 3.  Redesign algorithms to avoid contention for data
	     structures.  In many cases, this may be impossible	to
	     do	and still maintain reasonable performance.

       AT&T currently sells a multiprocessor version of	UNIX for
       the 3B20A attached processor system.  In	this UNIX kernel,
       locking primitives are used to create short critical
       sections	where contention for kernel data structures may
       occur.  This approach was chosen	because, if properly
       designed	and implemented, the problems of such locking can
       be managed easily without sacrificing system throughput or
       causing major redesigns of kernel algorithms.  By partially
       porting and otherwise using this	code as	an example, it will

       September 7, 1989		       Company Confidential

       Section 2					      -	2 -

       be possible to implement	a multiprocessor kernel	in a short
       period of time that meets the response and throughput
       requirements of Clover 2.

       The remainder of	this section is	devoted	to describing the
       locking primitives, how they are	used in	general	and how
       they will be used in the	Clover 2 kernel.

       2.  Semaphores

       2.1  Spinlocks

       2.1.1  General_Description  The class of	locking	primitives
       used in the UNIX	kernel goes under the general name of
       semaphores.  The	simplest semaphore is a	spinlock.  To
       access some critical resource, a	processor attempts to
       acquire the lock	using the simple algorithm:

		    if lock is set goto	loop;
		    set	lock;

       The lock	is obviously released simply by	clearing it, which
       will allow at most one other processor to obtain	it.

       If the testing and setting of the lock are not atomic, then
       it is possible that two processors may believe they have
       obtained	the lock at the	same time, or that neither has
       obtained	the lock.  The first case can result in	corrupted
       data structures,	while the second results in deadlock.

       Spinlocks can be	implemented atomically in software (see
       [1]), however this solution is slow and may potentially
       waste a substantial number of cycles.  Instead, most modern
       computers provide atomic	test-and-set instructions, which
       allow a processor to obtain the lock in a single	operation.

       2.1.2  Spinlock_Usage  Spinlocks	are used whenever the time
       in which	the lock is actually held by any one processor is
       very short.  In these cases it is more efficient	simply to
       wait for	the lock rather	than attempting	to find	some other
       useful work to do; the time spent searching for other work
       may exceed the time spent waiting for the lock.

       In a multiprocessor system, it is difficult to know when	a
       spinlock	may be more efficient than a mutual exclusion
       semaphore.  The use of spinlocks	must be	empirically
       determined during system	tuning,	when the effects can be
       measured.  Any very short operation is a	candidate for spin

       September 7, 1989		       Company Confidential

       Section 2					      -	3 -

       Example uses of sinplocks are for controlling free list
       access or performing linear scans of system tables.

       2.1.3  Spinlocks_and_Interrupts	One important aspect of
       locking that becomes apparent in	any interrupt-driven system
       is the possibility that an asynchronous routine started by
       the hardware may	take control of	the CPU	while it is
       attempting to obtain the	lock.  If the interrupt	occurs
       after the lock has been obtained, then the time for which
       the lock	is held	can increase dramatically, seriously
       impacting system	performance.

       If a spinlock is	used to	protect	a resource to which an
       interrupt routine needs access, then similar problems arise.
       The interrupt routine remains active while spinning,
       blocking	other important	interrupt processing and degrading
       system performance.

       Finally,	the consequence	if an interrupt	routine	attempts to
       obtain the same lock that normal	processing has just
       obtained	is guaranteed deadlock of the system.

       To avoid	all these problems, interrupts are disabled while
       attempting to obtain and	while holding a	spinlock.  This
       re-enforces the necessity for spinlocks to be held as short
       a time as possible.

       2.1.4  Hardware_Support	The Clover 2 hardware will supply a
       large set of "virtual" locks, which will	provide	atomic
       test-and-set capabilities between the processors	in the
       system.	This provides a	powerful mechanism for implementing
       spinlocks, since	traffic	on the multiprocessor bus can be
       avoided.	 The importance	of having a very large set of these
       locks will become apparent in the following sections.

       2.2  Mutual_Exclusion_Semaphores

       Once spinlocks are available, it	becomes	possible to
       implement more sophisticated types of semaphores.  Once of
       these is	the mutual exclusion semaphore,	which is used to
       protect critical	sections of code in a more intelligent
       manner than a spinlock.	Such a semaphore is a data
       structure which consists	of a counter and a queue of
       processes.  The counter is initialized to the value one.

       There are two operations	possible on such a semaphore,
       allocation, often called	the acquire operation, and de-
       allocation and wakeup, often called the release operation.
       A process attempting to acquire the semaphore does so using
       the following (abbreviated) algorithm:

       September 7, 1989		       Company Confidential

       Section 2					      -	4 -

	    if (counter	<= 0) then
		    add	this process to	end of queue of	processes;
		    block this process (allow another to run);
		    on return, decrement the counter;
		    continue with critical section;
		    decrement counter;
		    continue with critical section;

       The release operation is	performed in the following manner:

	    increment counter;
	    if (a process is waiting on	the queue) {
		    decrement counter;
		    unblock the	first process on the queue;

       Obviously the above operations must be atomic in	nature;	a
       spinlock	is used	to protect the semaphore, and is locked
       before and unlocked after each of the above operations.

       2.2.1  Usage  Mutual exclusion semaphores are used where	the
       length of the critical section to be protected is long or
       variable	in length.  This allows	other processes	to run and
       do useful work even though certain work must wait.

       Examples	of such	usage are when holding region entries for
       managing	segments of virtual memory, or when using an inode
       to access disk files or devices.

       2.2.2  Counting_Semaphores  The mutual exclusion	semaphore
       is a special case of a general counting semaphore.  A
       counting	semaphore is initialized to a value greater than
       one, allowing more than one process to acquire the semaphore
       at once.	 Counting semaphores are often used in resource
       allocation, where there is a fixed number of resources
       available.  Another use is to provide atomic counters; the
       semaphore is released each time the counter should be
       incremented, but	never acquired.

       The AT&T	multiprocessor code uses many atomic counters but
       no counting semaphores; the Clover 2 product may	include	the
       use of counting semaphores for controlling certain

       September 7, 1989		       Company Confidential

       Section 2					      -	5 -

       2.3  Synchronization_Semaphores

       This third type of semaphore is used to synchronize
       different processes (possibly on	different processors).	A
       synchronization semaphore is actually a mutual exclusion
       semaphore, however the acquire and release operations are
       performed by different processes, affecting a rendezvous

       Example usage is	in awakening the paging	daemon from the
       clock handler when memory is in short supply and	a
       sufficient time interval	has elapsed.

       3.  Multiprocessor_Semaphore_Primitives

       The AT&T	3B20A kernel introduced	several	new primitives to
       the kernel to provide semaphore facilities.  One	of the
       stated goals of the implementation was to provide a kernel
       that could run on either	uniprocessors or multiprocessors
       with no modification to the kernel code,	and to achieve this
       goal with only a	minor decrease in uniprocessor performance.
       This goal was met.

       Each set	of semaphore primitives	is described below.

       Spinlock	Primitives

	       lock_t  lock;

	       spsema(&lock);  - acquire the lock, spin	until acquired
	       svsema(&lock);  - release the lock

       On a uniprocessor the spinlock primitives are commented out
       using the C preprocessor	(since spinlocks are meaningless on
       a uniprocessor):

	    # define spsema
	    # define svsema

       The actual implementation of the	spinlock is done using a
       3B20 microcoded instruction for speed.  On the MIPS
       processor, there	is no test-and-set instruction.	 Thus,
       hardware	support	must be	provided to insure that	a high-
       performance path	exists for performing this operation.  The
       Clover 2	system will provide a separate,	high-speed bus for
       synchronization among the processors in the complex.  This
       bus will	provide	similar	functionality to the SLIC VLSI chip
       done for	the Sequent Balance multi-processor [2]	The Sequent
       implementation provides 64 test-and-set variables which are
       global to all processors.  In addition, a number	of 32-bit

       September 7, 1989		       Company Confidential

       Section 2					      -	6 -

       registers were available	that could be transferred between
       processors in an	atomic fashion,	provided a general message
       facility.  This facility	was used for distributing
       interrupts from I/O devices and communication between the

       The Clover 2 implementation will	be based on cheaper gate-
       array technology, and will be called the	SYNC bus for
       brevity.	 Access	to the SYNC bus	will be	through	normal load
       and store operations in the physical address space of each
       processor.  The SYNC bus	will provide 4096 test-and-set
       locks.  Each lock will be atomic	in nature, thus	a processor
       can use these locks for access control, busy waiting, or
       other uses.  The	locks will be grouped into 128 pages, each
       having 32 locks.	 This allows a group of	locks to be mapped
       into the	virtual	address	space of the processor,	allowing
       user access to certain locks if so desired.  Other
       facilities will be provided by the SYNC bus; they are not of
       interest	here 1.

       Unlike the Sequent system, such a large number of locks
       allows each semaphore in	the kernel to have a private lock,
       improving the overall performance of the	system.	 Since no
       memory cycles are used once the busy-wait instruction has
       been loaded from	memory,	all memory traffic is eliminated.

       With high-speed spinlocks available, the	semaphore
       operations can be defined.

       Synchronization Primitives

	       sema_t  sema;

	       psema(&sema, PRI);      - acquire the semaphore
	       vsema(&sema);	       - release the semaphore
	       cpsema(&sema, PRI);     - conditionally acquire the semaphore

       Algorithmically,	psema()	is implemented as:


	1. The SYNC bus	will provide 4 8-bit registers that can	be
	   incremented,	decremented or set in an atomic	fashion.
	   This	allows certain algorithms to be	speeded	up.  In
	   addition, the SYNC bus will be used for messaging
	   interrupts both from	the I/O	system and between
	   processors, eliminating this	load on	the system memory

       September 7, 1989		       Company Confidential

       Section 2					      -	7 -

	       acquire semaphore lock;
	       if (count <= 0) {
		  decrement count;
		  acquire semaphore queue lock;
		  release semaphore lock;
		  add process to semaphore queue;
		  release semaphore queue lock;
		  switch to another process;
		  on return, return to caller;
		  decrement count;
	       release semaphore lock;
	       return to caller;

       The routine vsema() is implemented as:

	       acquire semaphore lock;
	       increment count;
	       if (count > 0) {
		  acquire semaphore queue lock;
		  if (a	process	is queued) {
		     remove process from queue;
		     unblock process;
		     decrement count;
		  release semaphore lock;
		  release semaphore queue lock;
	       release semaphore lock;

       The routine cpsema() is used by a process which does not
       wish to block if	the semaphore cannot be	acquired.  This	is
       used in two instances.  First, if the caller is an interrupt
       routine wishing access to a data	structure, than	it may not
       block.  Thus, it	uses cpsema() to acquire the semaphore,	and
       takes some other	action if the critical section is in use.
       Second, some algorithms require that multiple semaphores	be
       used when updating related data structures.  In this case,
       it is necessary to avoid	blocking so that the system does
       not deadlock.  This type	of algorithm usually appears as:

       September 7, 1989		       Company Confidential

       Section 2					      -	8 -

		    if (cpsema(&sem2)) {
			    goto loop;

       Cpsema()	is also	used in	cases where semaphores must be
       acquired	in a different order than they will be released.
       This is also a case where only a	conditional operation will
       avoid deadlock.	Cpsema() is implemented	as:

	       acquire semaphore lock;
	       if (count <= 0) {
		  release semaphore lock;
		  return failure;
		  decrement count;
	       release semaphore lock;

       Mutual Exclusion	Primitives

	       sema_t  sema;

	       appsema(&sema, PRI);    - acquire the semaphore
	       apvsema(&sema, PRI);    - release the semaphore
	       apcpsema(&sema);	       - conditionally acquire semaphore

       These primitives	are implemented	differently depending on
       whether the target system is a uniprocessor or a
       multiprocessor.	The following C	preprocessor definitions
       control this:

       September 7, 1989		       Company Confidential

       Section 2					      -	9 -

	    # ifdef multiprocessor
	    #	    define appsema  psema
	    #	    define apvsema  vsema
	    #	    define apcpsema cpsema
	    # else
	    #	    define appsema
	    #	    define apvsema
	    #	    define apcpsema
	    # endif

       Thus, on	a uniprocessor,	these operations are not performed,
       since they would	only add overhead and perform no useful
       purpose.	 On a multiprocessor, these operations are
       equivalent to the previously defined psema() and	vsema()

       Miscellaneous Primitives

	       sema_t  sema;

	       initsema(&sema, value); - initialize the	given semaphore
	       valusema(&sema)	       - return	the value of the semaphore

       4.  Uniprocessor_UNIX_Semaphore_Usage

       Although	not explicitly shown in	the code, normal UNIX uses
       several implicit	semaphores to manage kernel data space in a
       crude manner.

       First, a	single semaphore is used to protect all	data
       structures from access by other processes: the mode, e.g.,
       kernel or user.	When in	kernel mode, the current process
       may not be preempted, protecting	kernel data structures.
       This is obviously a crude method	of protection, but has the
       advantage of elegance and simplicity.  This semaphore is	a
       mutual exclusion	semaphore.

       Second, the interrupt level of the processor is used to
       protect from access by interrupt	routines.  There are as
       many of these semaphores	as there are interrupt levels in
       the processor.  The kernel routines used	to acquire and
       release these semaphores	are the	spl routines.  These
       semaphores are spinlocks, since the interrupt is	blocked	by
       the processor only for short periods of time, and other
       processing (except higher priority interrupts) cannot
       continue	while the lock is held.

       Third, process synchronization is performed using the sleep
       and wakeup primitives, which provide an inefficient yet
       elegant method for synchronization.  The	usual sequence for

       September 7, 1989		       Company Confidential

       Section 2					     - 10 -

       acquiring the semaphore is:

	    while (flag	& BUSY)	{
		    flag |= WANT;
	    flag |= BUSY;

       The sequence for	releasing the semaphore	is:

	    flag &= ~BUSY;
	    if (flag & WANT) {
		    flag &= ~WANT;

       Thus, if	more than one process is waiting on the	semaphore,
       they will all awake at once, and	must contend for the
       semaphore once again.

       5.  Multiprocessor_UNIX_Semaphore_Usage

       A multiprocessor	UNIX kernel must abandon the mode
       semaphore, since	multiple processors may	be executing in	the
       kernel at once.	The sleep and wakeup primitives	are
       replaced	with synchronization semaphores.  This provides	a
       more efficient implementation, since only the first process
       waiting on the semaphore	will awake, and	that process will
       hold the	semaphore once it does.

       Even through the	multiprocessor UNIX kernel abandons the
       mode semaphore, it still	disallows preemption of	kernel
       processes on the	same processor.	 This is for performance
       reasons.	 For example, consider the case	where a	kernel
       process is preempted, but the next process chosen to run
       needs access to the same	resource.  Eventually control will
       pass back to the	preempted process, but only after a
       substantial amount of time and several unnecessary context

       At points where the uniprocessor	kernel used interrupt
       blocking	to protect from	interrupt routines, the
       multiprocessor kernel must also provide spinlocks to protect
       from other processors.  Thus, a common sequence in the
       multiprocessor kernel is:

       September 7, 1989		       Company Confidential

       Section 2					     - 11 -

	    x =	spl6();
	    spsema(&lock);  /* spsema()	is discussed below */
	    svsema(&lock);  /* svsema is discussed below */

       The most	difficult change is the	use of mutual exclusion
       semaphores to protect kernel data structures that previously
       were protected by the mode semaphore.  Thus, areas such as
       the buffer cache, process management and	virtual	memory
       management must be modified to use semaphores to	insure
       exclusive access	to structures.

       5.1  Semaphores_and_Signals

       One aspect of the normal	sleep/wakeup mechanism is that
       signal handling may be performed	within these primitives	if
       desired by the caller.  This allows long	waits to be
       interrupted by the user or application and proper cleanup to
       be performed.

       Thus, both mutual exclusion and synchronization semaphores
       provide the means by which a signal can be ignored or
       handled,	in the same manner as that used	by sleep/wakeup.
       An example call to a mutual exclusion semaphore is:

	    psema(&sema, PPRI);

	    psema(&sema, PPRI |	PCATCH);

       In the first case, if the priority PPRI is greater than
       PZERO, than a signal which is sent to the process will cause
       the process to wake up, cleanup it's entry on the semaphore
       queue, and use longjmp()	to return to the system	call
       handler for return to the user.	If the priority	is less
       than PZERO, than	such signals will always be ignored, and
       the process can only be woken by:


       In the second case, the PCATCH flag causes control to be
       returned	to the caller when a signal occurs (if the priority
       is greater than PZERO, as before).  Thus, the caller can
       take any	necessary cleanup actions before returning to the

       September 7, 1989		       Company Confidential

       Section 2					     - 12 -

       6.  Semaphore_Performance

       In a semaphored system, there are a number of different
       factors that effect the performance of the system.
       Obviously, the more semaphore operations	performed, the
       fewer cycles that will be devoted to real work.	The speed
       with which a semaphore can be accessed and updated is also
       critical.  AT&T dealt with this problem by micro-coding
       special instructions to handle the most common semaphore

       There is	one factor, however, that has an overriding effect
       on performance.	This is	the hit	ratio on a semaphore.  This
       is defined as the ratio of the number of	times a	semaphore
       could be	acquired immediately to	the number of attempts to
       acquire the semaphore.  By examining the	above algorithms,
       the reader can see that the optimal path	is to immediately
       acquire the semaphore - blocking	a process is an	expensive
       and time-consuming operation.

       During construction of the multiprocessor kernel, AT&T
       discovered that a hit ratio of at least 95% on all
       semaphores was necessary	to achieve adequate performance	of
       the system.  To achieve this goal, it is	often necessary	to
       break up	data structure accesses	into smaller chunks, and to
       isolate accesses	as much	as possible.  For instance, the
       buffer cache is broken up into a	large set of hash buckets
       that can	be searched individually, reducing the contention
       on any one semaphore.

       Fortunately, AT&T has already done most of this work,
       providing the Clover 2 effort with high performance debugged
       algorithms for handling most of these cases.

       7.  Driver_Semaphore_Use

       Clover 2	will obtain most of it's UNIX drivers from the
       Clover I	system.	 Converting drivers to semaphore use would
       be a long, costly and painful process, perhaps not worth	the
       effort.	To avoid the same situation for	the 3B20A port,
       AT&T added the concept of driver	semaphores to the kernel.
       Since a driver can only be entered in certain well-defined
       ways, it	was possible to	place a	semaphore sequence around
       each entry to the driver.  In general, these entry points
       are the open, close, read, write	and ioctl entries.  This is
       much like the mode semaphore in normal UNIX, in that it
       prevents	any other process from entering	the driver
       simultaneously.	Three separate types of	protection are

       September 7, 1989		       Company Confidential

       Section 2					     - 13 -

       First, the entire driver	can be semaphored on it's major
       device number.  Before the kernel invokes the driver, it
       calls psema() to	lock the driver	semaphores, and	after
       return from the driver it calls vsema() to unlock the

       Second, each minor device number	access to the driver can be
       semaphored.  Instead of locking a single	semaphore, each
       possible	minor device number has	a semaphore associated with
       it.  The	kernel locks the semaphore associated with the
       minor device before entering the	driver and unlocks it after
       return.	For example, this used in protecting the tty
       driver, which maintains independent structures for each
       minor device supported.

       Third, a	driver can be given no protection, in which case it
       is responsible for protecting it's own data structures.
       This means that structures within the driver that are shared
       between processes or with interrupt routines must be
       protected with semaphores.

       To protect from interrupt access	while a	driver semaphore is
       locked, the kernel checks the driver semaphore before
       launching the interrupt routine.	 If the	semaphore is
       locked, the kernel queues the interrupt and returns.  The
       code which unlocks the driver semaphore checks for the
       queued interrupt, and if	one exists it launches the
       interrupt routine at that time.	Note that this behavior	is
       only possible with major	device locking.	 A driver that uses
       minor device locking must be modified to	block the interrupt
       routine explicitly (if it does not already do so).

       If a driver choses to access kernel data	structures, it will
       not be possible to port it directly to the multiprocessor
       environment.  This is because it	will not follow	the
       kernel's	locking	strategy for the structures accessed.  Such
       drivers must be modified	to use the proper locking strategy
       before they can be used in the multiprocessor kernel.

       The Clover 2 kernel will	implement the 3B20A driver concept,
       maximizing the use of currently existing	drivers.  In most
       cases, it should	be possible to directly	use drivers written
       for Clover I.  It is expected that some drivers will require
       a porting effort.

       September 7, 1989		       Company Confidential

       Section 2					     - 14 -

       8.  Further_Reading

       Much of this discussion is based	on the actual code for the
       AT&T 3B20A implementation, as well as [3] and [1].

       September 7, 1989		       Company Confidential

       Section 2					     - 15 -


	1. Bach, Maurice J., The Design	of the UNIX Operating
	   System, Prentice-Hall, Englewood Cliffs, N. J., 1986.

	2. Beck, B., and Kasten, B., VLSI Assist in Building a
	   Multiprocessor UNIX System, Sequent Computer	Systems,
	   Portland Oregon, not	dated.

	3. Bach, M. J.,	and Buroff, S. J., Multiprocessor UNIX
	   Operating Systems, AT&T Bell	Laboratories Technical
	   Journal, Vol. 63, No. 8, October 1984.

       September 7, 1989		       Company Confidential

			        About USENET

USENET (Users’ Network) was a bulletin board shared among many computer
systems around the world. USENET was a logical network, sitting on top
of several physical networks, among them UUCP, BLICN, BERKNET, X.25, and
the ARPANET. Sites on USENET included many universities, private companies
and research organizations. See USENET Archives.

		       SCO Files Lawsuit Against IBM

March 7, 2003 - The SCO Group filed legal action against IBM in the State 
Court of Utah for trade secrets misappropriation, tortious interference, 
unfair competition and breach of contract. The complaint alleges that IBM 
made concentrated efforts to improperly destroy the economic value of 
UNIX, particularly UNIX on Intel, to benefit IBM's Linux services 
business. See SCO v IBM.

The materials and information included in this website may only be used
for purposes such as criticism, review, private study, scholarship, or

Electronic mail:			       WorldWideWeb: