Search⌘ K
Home
Courses
Operating Systems: Virtualization, Concurrency & Persistence

Building Working Spin Locks with Test-And-Set

Explore how test-and-set atomic instructions enable the creation of spin locks to manage mutual exclusion in concurrent programming. Understand hardware support for locking, why simple methods fail on multiprocessor systems, and how spin locks operate to ensure only one thread accesses critical sections at a time. This lesson helps you grasp lock implementation nuances and concurrency challenges on modern hardware.

We'll cover the following...

Because disabling interrupts does not work on multiple processors, and because simple approaches using loads and stores (as you saw in the previous lesson) don’t work, system designers started to invent hardware support for locking. The earliest multiprocessor systems, such as the Burroughs B5000 in the early 1960s“The Architecture of the Burroughs B5000: 20 Years Later and Still Ahead of the Times?” by A. Mayer. 1982. Available: www.ajwm.net/amayer/papers/B5000.html. “It (RDLK) is an indivisible operation which reads from and writes into a memory location.” RDLK is thus test- and-set! Dave Dahm created spin locks (“Buzz Locks”) and a two-phase lock called “Dahm Locks.”, had such support; today all systems provide this type of support, even for single CPU systems.

Test and set

The simplest bit of hardware support to understand is known as a test-and-set (or atomic exchangeEach architecture that supports test-and-set calls it by a different name. On SPARC it is called the load/store unsigned byte instruction (ldstub); on x86 it is the locked version of the atomic exchange (xchg).) instruction. The function of test-and-set instruction can be defined via the following C code snippet:

C
int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; // fetch old value at old_ptr
    *old_ptr = new;     // store ’new’ into old_ptr
    return old;         // return the old value
}

ASIDE: DEKKER’S AND PETERSON’S ALGORITHMS

In the 1960s, Dijkstra posed the ...