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

Authors:
	Hiroaki Takada(1) and Ken Sakamura(2)

	(1) Department of Information Science,
	    School of Science, University of Tokyo

	(2) The University Museum, University of Tokyo

Abstract:
	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
	cost becomes 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 cost can be reduced to almost zero,
	while operations on complex data structures can be realized
	with reasonable efficiency.  This paper presents the two
	algorithms of the SPEPP synchronization and their extensions,
	and demonstrates its effectiveness through the performance
	measurements of real-time kernels implemented with the SPEPP
	synchronization algorithms.

Appeared in:
	Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS)