This directory contains CSRI technical report #278:

	Optimal Strategies for Spinning and Blocking

	L. Boguslavsky, K. Harzallah, A. Kreinen, K. Sevcik, and A. Vainshtein

The file ``278.ps'' is a postscript version of this document. The
file ``278.ps.Z'' is a postscript compressed version of this document.
Remember to use binary mode for transferring the compressed version,
or ascii mode to transfer just the postscript version.

This report was made available for anonymous ftp by:
        karim@csri.toronto.edu
If you have any trouble printing it, please let me know.

			Abstract

  In  parallel and distributed computing environments, threads (or
processes) share access to variables and data structures. To assure
consistency 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 become free, and blocking, which means suspending its execution
and relinquishing its processor to some other thread. The choice
between spinning and blocking involves balancing the processor time
lost to spinning against the processor time required to save the
context of a process when it blocks (context switch overhead).

  In this paper, we investigate 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 estimating an optimal limit on spinning time
before blocking.  Results are obtained by a combination of analysis and
simulation.