/down-with-locks

Viva la revolucion! Down with locks!

Primary LanguageCBSD 2-Clause "Simplified" LicenseBSD-2-Clause

Down with locks!

Viva la revolucion! Down with locks!

Let us band together, and cask off our tyrranical lock-based bonds (shown here) of mutually exclusive oppression!

Ne'er shall we be forced to serialize in a critical section again!

We need doors without locks; we need windows without locks; band together with me revolutionaries, we need stacks without locks! Let us not be afraid of the race conditions, and instead embrace the race conditions! Open access for all; let the cleansing light of complete transparency and arbitrary interleavings wash over your data-structures!

The call to action

Inspired by the lockless luminary, Robert Frost, and our shadowy leader, the Loch-less Monster, we will draw all our attention to data-structures with no lock to lock.

It went many years,

But at last came a knock,

And I thought of the door

With no lock to lock.

...

-The Lockless Door, Robert Frost

Find our lock-free stack comrade, main.c. They exist as the founders imagined it, blissfully existing in freedom with unregulated access to all!

  • First, let us understand the power that comes with freedom. Execute bin and taste the freedom. By default our revolution is focused on BURN_IT_DOWN! (See the #defines at the top of main.c.) What is the problem with this phase of the revolution? Necessary radical reforms always face head-winds! But we have to identify where the problem is so that we can come up with a plan.
  • Second, lets add some order to the chaos. Now, WE_HAVE_A_PLAN. But our plan is not, well, good. Why is it not good?
  • As it turns out, organizing bytes is hard. Lets let the PROFESSIONALS_TAKE_OVER. What is this code doing? What is the principle that it is imposing? Why does it add more order to the system?

PSSSSSST!

Come check out the counter revolution in ticket.c. We're formenting distrust in the anarchy of arbitrary interleaving by using the power of counting to maintain orderly mutual exclusion with bounded wait. However, even the counter-revolution cannot be perfect, and after the drastic fall of the lock-free revolution due to the ABA uprising, we must be more self-critical.

  • How does this lock guarantee bounded wait?
  • What are the downsides of ticket locks over a lock (using cas or t&s which we saw in lecture) that don't provide bounded wait?