OPTIMAL STRATEGIES FOR SPINNING AND BLOCKING

In parallel and distributed computing environments, threads (or proces ses) share access to variables and data structures. To assure consiste ncy during updates, locks are used. When a thread attempts to acquire a lock but finds it busy, it must choose between spinning, which means repeatedly attempting to acquire the lock in the hope that it will be come free, and blocking, which means suspending its execution and reli nquishing its processor to some other thread. The choice between spinn ing and blocking involves balancing the processor time lost to spinnin g against the processor time required to save the context of a process when it blocks (context switch overhead). In this paper, we investiga te a model that permits us to evaluate how long a process should spin before blocking. We determine conditions under which the extreme cases of immediate blocking (no spinning) and pure spinning (spin until the lock is acquired) are optimal. In other cases, we seek ways of estima ting an optimal limit on spinning time before blocking. Results are ob tained by a combination of analysis and simulation. (C) 1994 Academic Press, Inc.