Accession Number : ADA261663


Title :   Fast Mutual Exclusion for Uniprocessors


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE


Personal Author(s) : Bershad, Brian N ; Redell, David D ; Ellis, John R


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a261663.pdf


Report Date : Oct 1992


Pagination or Media Count : 15


Abstract : In this paper we describe restartable atomic sequences, an optimistic mechanism for implementing simple atomic operations (such as Test-and-Set) on a uniprocessor. A thread that is suspended within a restartable atomic sequence is resumed by the operating system at the beginning of the sequence, rather than at the point of suspension. This guarantees that the thread eventually executes the sequence atomically. A restartable atomic sequence has significantly less overhead than other software-based synchronization mechanisms, such as kernel emulation or software, reservation. Consequently, it is an attractive alternative for use on uniprocessors that do not support atomic operations. Even on processors that do support atomic operations in hardware, restartable atomic sequences can have lower overhead. We describe different implementations of restartable atomic sequences for the Mach 3.0 and Taos operating systems. These systems' thread management packages rely on atomic operations to implement higher-level mutual exclusion facilities. We show that improving the performance of low-level atomic operations, and therefore mutual exclusion mechanisms, improves application performance.


Descriptors :   *CONTROL SYSTEMS , *DATA PROCESSING EQUIPMENT , GUARANTEES , LOW LEVEL , MANAGEMENT , OPERATING SYSTEMS(COMPUTERS) , OPERATION , OPTIMIZATION , SYNCHRONIZATION(ELECTRONICS) , TEST AND EVALUATION


Subject Categories : Computer Hardware


Distribution Statement : APPROVED FOR PUBLIC RELEASE