howie@voodoo.voodoo.uucp (howie) (12/19/90)
Can someone tell me, or point me to some document, that details the differences between semaphores and locks? Thanks in advance. -- howie uunet!bcstec!voodoo!howie
howie@voodoo.voodoo.uucp (howie) (12/19/90)
Can someone tell me, or point me in the direction of some document that details the differences between locks and semaphores? Thanks in advance. -- howie uunet!bcstec!voodoo!howie
jmb@patton.wpd.sgi.com (Jim Barton) (01/02/91)
In article <651@voodoo.UUCP>, howie@voodoo.voodoo.uucp (howie) writes: > Can someone tell me, or point me in the direction of some document that > details the differences between locks and semaphores? > > Thanks in advance. > -- > howie > > uunet!bcstec!voodoo!howie There are lots of references (these days) to this basic area of processor synchronization. The following chapter is straight out of the original IRIX design specification, and it shows how the kernel, at least, uses these beasts. -- Jim Barton Silicon Graphics Computer Systems jmb@sgi.com (Format with the MM macros) ---------- cut here ----------- .\" .\" .\" Copyright (C) 1989, Silicon Graphics, Inc. .\" .\" These coded instructions, statements, and computer programs contain .\" unpublished proprietary information of Silicon Graphics, Inc., and .\" are protected by Federal copyright law. They may not be disclosed .\" to third parties or copied or duplicated in any form, in whole or .\" in part, without the prior written consent of Silicon Graphics, Inc. .\" .\" .PH "'Section 2''- \\\\nP -'" .SK .PF "'\\\\*(DT''Silicon Graphics Inc.'" .DS 2 James M. Barton Copyright (c) 1986 Silicon Graphics Computer Systems \s-2This document is part of the original software specification for the IRIX\(tm operating system. Although the technology and techniques described here are valid, there is no gaurantee that any particular feature or capability of either the hardware or software environment actually exist as part of a POWERSeries\(tm system.\s0 .I ($Revision: 1.12 $ $Date: 86/09/23 17:27:33 $) .R .DE .nr Ds 1 .nr H1 0 .nr Hs 2 .H 1 "UNIX On Multiprocessors" Much of the discussion in this section follows that in \*(Rf. .RS Ba Bach, Maurice J., .B The Design of the UNIX Operating System, .R Prentice-Hall, Englewood Cliffs, N. J., 1986. .RF 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. .P 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. .P There are three ways in which corruption of kernel data structures can be prevented on a multiprocessor: .AL .LI Execute the kernel on one processor only, which protects all kernel data structures but serializes all system functions. .LI Serialize small sections of code (critical regions) with locking primitives. This approach adds locking overhead, and may increase context switching. .LI Redesign algorithms to avoid contention for data structures. In many cases, this may be impossible to do and still maintain reasonable performance. .LE .SP 1 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 be possible to implement a multiprocessor kernel in a short period of time that meets the response and throughput requirements of Clover 2. .P 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. .H 1 "Semaphores" .H 2 "Spinlocks" .H 3 "General Description" The class of locking primitives used in the UNIX kernel goes under the general name of .IR semaphores . The simplest semaphore is a .IR spinlock . To access some critical resource, a processor attempts to acquire the lock using the simple algorithm: .DS 1 loop: if lock is set goto loop; set lock; .DE The lock is obviously released simply by clearing it, which will allow at most one other processor to obtain it. .P 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. .P Spinlocks can be implemented atomically in software (see \*(Ba), however this solution is slow and may potentially waste a substantial number of cycles. Instead, most modern computers provide atomic .I test-and-set instructions, which allow a processor to obtain the lock in a single operation. .H 3 "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. .P 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 locking. .P Example uses of sinplocks are for controlling free list access or performing linear scans of system tables. .H 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. .P 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. .P 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. .P 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. .H 3 "Hardware Support" The Clover 2 hardware will supply a large set of "virtual" locks, which will provide atomic .I 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. .H 2 "Mutual Exclusion Semaphores" Once spinlocks are available, it becomes possible to implement more sophisticated types of semaphores. Once of these is the .I mutual exclusion .R 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. .P There are two operations possible on such a semaphore, allocation, often called the .I acquire operation, and de-allocation and wakeup, often called the .I release operation. A process attempting to acquire the semaphore does so using the following (abbreviated) algorithm: .DS 1 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; else decrement counter; continue with critical section; fi .DE The release operation is performed in the following manner: .DS 1 increment counter; if (a process is waiting on the queue) { decrement counter; unblock the first process on the queue; } .DE 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. .H 3 "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. .P 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. .H 3 "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. .P 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 resources. .H 2 "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 .I rendezvous operation. .P 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. .H 1 "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. .P Each set of semaphore primitives is described below. .DS 0 .B Spinlock Primitives .R lock_t lock; spsema(&lock); - acquire the lock, spin until acquired svsema(&lock); - release the lock .DE On a uniprocessor the spinlock primitives are commented out using the C preprocessor (since spinlocks are meaningless on a uniprocessor): .DS 1 # define spsema # define svsema .DE The actual implementation of the spinlock is done using a 3B20 microcoded instruction for speed. On the MIPS processor, there is no .I 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 \*(Rf .RS Beck, B., and Kasten, B., .I VLSI Assist in Building a Multiprocessor UNIX System, .R Sequent Computer Systems, Portland Oregon, not dated. .RF The Sequent implementation provides 64 test-and-set variables which are global to all processors. In addition, a number of 32-bit 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 processors. .P 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 \*F. .FS 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 bus. .FE .P 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. .P With high-speed spinlocks available, the semaphore operations can be defined. .DS 0 .B Synchronization Primitives .R sema_t sema; psema(&sema, PRI); - acquire the semaphore vsema(&sema); - release the semaphore cpsema(&sema, PRI); - conditionally acquire the semaphore .DE Algorithmically, psema() is implemented as: .DS 1 BEGIN 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; } else decrement count; release semaphore lock; return to caller; END .DE The routine vsema() is implemented as: .DS 1 BEGIN 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; return; } release semaphore lock; END .DE The routine .I 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: .DS 1 loop: psema(&sem1); . . . if (cpsema(&sem2)) { vsema(&sem1); goto loop; } . . . vsema(&sem2); vsema(&sem1); .DE 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: .DS 1 BEGIN acquire semaphore lock; if (count <= 0) { release semaphore lock; return failure; } else decrement count; release semaphore lock; .DE .DS 0 .B Mutual Exclusion Primitives .R sema_t sema; appsema(&sema, PRI); - acquire the semaphore apvsema(&sema, PRI); - release the semaphore apcpsema(&sema); - conditionally acquire semaphore .DE These primitives are implemented differently depending on whether the target system is a uniprocessor or a multiprocessor. The following C preprocessor definitions control this: .DS 1 # ifdef multiprocessor # define appsema psema # define apvsema vsema # define apcpsema cpsema # else # define appsema # define apvsema # define apcpsema # endif .DE 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() operations. .DS 0 .B Miscellaneous Primitives .R sema_t sema; initsema(&sema, value); - initialize the given semaphore valusema(&sema) - return the value of the semaphore .DE .H 1 "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. .P 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. .P 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 .I 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. .P Third, process synchronization is performed using the .I sleep and .I wakeup primitives, which provide an inefficient yet elegant method for synchronization. The usual sequence for acquiring the semaphore is: .DS 1 while (flag & BUSY) { flag |= WANT; sleep(&flag); } flag |= BUSY; .DE The sequence for releasing the semaphore is: .DS 1 flag &= ~BUSY; if (flag & WANT) { flag &= ~WANT; wakeup(&flag); } .DE 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. .H 1 "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 .I sleep and .I 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. .P 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 switches. .P 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: .DS 1 x = spl6(); spsema(&lock); /* spsema() is discussed below */ . . . svsema(&lock); /* svsema is discussed below */ splx(x); .DE .P 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. .H 2 "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. .P 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: .DS 1 psema(&sema, PPRI); .DE .DS 1 psema(&sema, PPRI | PCATCH); .DE 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 .I 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: .DS 1 vsema(&sema); .DE 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 application. .H 1 "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 operations. .P There is one factor, however, that has an overriding effect on performance. This is the .B 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. .P 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. .P 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. .H 1 "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 .IR open , .IR close , .IR read , .I write and .I 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 provided. .P First, the entire driver can be semaphored on it's major device number. Before the kernel invokes the driver, it calls .I psema() to lock the driver semaphores, and after return from the driver it calls .I vsema() to unlock the semaphore. .P 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. .P 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. .P 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). .P 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. .P 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. .H 1 "Further Reading" Much of this discussion is based on the actual code for the AT&T 3B20A implementation, as well as \*(Rf .RS Bach, M. J., and Buroff, S. J., .I Multiprocessor UNIX Operating Systems, .R AT&T Bell Laboratories Technical Journal, Vol. 63, No. 8, October 1984. .RF and \*(Ba.