Modeling spin locks with queuing networks

Abstract

Modern multiprogramming, multiprocessing operating systems encounter a common problem: multiple parallel processes (perhaps being executed on multiple processors) share common data and control blocks, and must use some form of process synchronization to ensure data integrity. This problem has been addressed in many places in the literature (for instance, in Dijkstra (1965) and Dijkstra (1968)) and a clear distinction has been drawn between synchronization primitives which employ busy versus non-busy waiting (Dijkstra (1971)). Though the non-busy wait method (used by Dijkstra's semaphores, operated upon by P and V) has received wide acclaim, there is a place for the busy wait. King, et al (1974) analyze the effects of busy and noa-busy wait strategies for the idealized case where there is no overhead for the process switch associated with the nonbusy wait, and find that the idealized non-busy wait strategy should be preferred. Fuller, et al (1976) compare the performance of processes using busy versus non-busy waiting running on an actual multiprocessing system (C.mmp). There are criteria, however, for legitimately using the busy wait. When the projected wait time is less than the time to perform a process switch, or when the processor cannot run any other work due to the critical nature of the current work, (dispatching, virtual storage management, etc.) then a busy wait can be used. In the MVS operating system, described in Arnold, et al (1974), both types of process synchronization primitives are used:---~isabled spin locks" (busy wait) and "enabled suspend locks" (non-busy wait). Analysis of MVS disabled spin locks is the subject of this paper. System performance is greatly affected by spin locks, since in a multiprocessing (MP) environment some time is wasted