0
$\begingroup$

I'm reading Arpaci's Operating Systems: Three Easy Pieces, the chapter on Locks.

At the end of the chapter, they present Two-phase locks (section 28.16). They say

A two-phase lock realizes that spinning can be useful, particularly if the lock is about to be released. So in the first phase, the lock spins for a while, hoping that it can acquire the lock.

I understand this may only be useful in a multiprocessor environment, is that right?

Also, it seems a little arbitrary to me to wait the first time and then go to sleep. I mean, I don't see why this would be such a great improvement over going directly to sleep in the case the lock is being held.

Is there anything I'm missing?

Thanks in advance!


Below is the whole paragraph on Two-phase locks:

One final note: the Linux approach has the flavor of an old approach that has been used on and off for years, going at least as far back to Dahm Locks in the early 1960’s [M82], and is now referred to as a two-phase lock. A two-phase lock realizes that spinning can be useful, particularly if the lock is about to be released. So in the first phase, the lock spins for a while, hoping that it can acquire the lock.

However, if the lock is not acquired during the first spin phase, a sec- ond phase is entered, where the caller is put to sleep, and only woken up when the lock becomes free later. The Linux lock above is a form of such a lock, but it only spins once; a generalization of this could spin in a loop for a fixed amount of time before using futex support to sleep.

Two-phase locks are yet another instance of a hybrid approach, where combining two good ideas may indeed yield a better one. Of course, whether it does depends strongly on many things, including the hard- ware environment, number of threads, and other workload details. As always, making a single general-purpose lock, good for all possible use cases, is quite a challenge.

$\endgroup$
2
  • 2
    $\begingroup$ It's about trade-offs: suppose that spinning to check a lock is released takes 1 unit of time, the critical section takes 5 units of time while the lock is held, and going to sleep and waking back up will take upwards of 100 units of time, due to the overheads of context switching and running the OS scheduler in between. Then it seems that spinning perhaps 10-20 times before sleeping could result in much higher throughput. In reality, you would measure all these things and try to optimise (either theoretically or empirically) for the metric you want: throughput, power consumption, etc. $\endgroup$
    – Joppy
    Sep 29 '20 at 23:55
  • $\begingroup$ Thanks for your comment! Wish you posted it as an answer so I could upvote it ;) $\endgroup$
    – 89f3a1c
    Sep 30 '20 at 2:57
1
$\begingroup$

To answer your first question: Spinlocks are only useful in a multiprocessing environment.

Spinning is waiting. If you're waiting for a lock to be released, and it must occur on the current CPU because there are no other CPUs, then a context switch must occur for the lock to be released. It follows that the current thread should just sleep, because it will need to anyway.

Of course, in a single-CPU environment, you can still spin-wait for other types of resource, such as a hardware device.

As Joppy indicated in the comment, putting a thread to sleep is a much heavier-weight operation than sitting in a loop. Whether or not it's worth spinning depends on a bunch of things, such as how expensive it is to sleep and context switch, and how long the lock is likely to be held.

There is a huge design space here. The default behaviour of Solaris kernel locks, for example, is to spin if the owner is running on another CPU, and sleep otherwise, the theory being that if the owner is making progress, it's more likely that the lock may be released soon. As a nice bonus, this automatically does the "right" thing on a single CPU.

$\endgroup$
1
  • $\begingroup$ Thanks! It really helped me get the point! $\endgroup$
    – 89f3a1c
    Sep 30 '20 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.