A Novel Approach to Multiprogrammed Multiprocessor Synchronization for Real-Time Kernels

In order to solve the problem of inopportune preemption in multiprogrammed multiprocessor synchronization, two strategies which are applicable to real-time systems have been investigated: preemption-safe locking and wait-free synchronization. Either of them, however, has a problem for use in the implementation of a real-time kernel. Preemption-safe locking has the drawback that the preemption overhead becomes quite large; while wait-free operations on complex data structures are generally very inefficient and are not practical. In this paper, we propose a novel approach to multiprogrammed multiprocessor synchronization, called the SPEPP (Spinning Processor Executes for Preempted Processors) synchronization, with which the preemption overhead can be reduced to zero, while operations on complex data structures can be realized with reasonable overhead. This paper presents the two algorithms of the SPEPP synchronization, and demonstrates its effectiveness through the performance measuremen..