|
The mutual exclusion algorithms for shared-memory
multiprocessors are mainly categorized into two classes:
spinning and blocking. The spinning constructs are good for
speeding up the concurrent program in which processes
repeatedly test shared variable to determine when they may
proceed. Blocking constructs are good for system throughput:
waiting process blocks itself and leaves an idle processing
element for other processes. In this thesis, we propose a
spinning-cum-blocking algorithm which yields drastic
improvement in system throughput, sacrificing only a small
amount of speed up for time critical application. We compare
the speed up of our algorithm with Anderson's queueing lock,
which works best in a coherent-cache multiprocessor, on a
Sequent Symmetry. We also build a mathematical model to show
the speed up and throughput gain in an ideal system.
|