Operating Systems: Virtualization, Concurrency & Persistence/

...

/

Building Working Spin Locks with Test-And-Set

Building Working Spin Locks with Test-And-Set

In this lesson, you will learn the correct implementation of a lock, the test-and-set method.

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:

Press + to interact
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 ...