Testing a javascript mutex implementation

Question

I have written a mutex implementation for javascript / typescript, but I'm struggling with the question of how to test it. Here's the implementation:

class Mutex {

    private current = Promise.resolve();

    async acquire() {
        let release: () => void;
        const next = new Promise<void>(resolve => {
            release = () => { resolve(); };
        });
        const waiter = this.current.then(() => release);
        this.current = next;
        return await waiter;
    }

}

Usage:

const mut = new Mutex();

async function usesMutex() {
  const unlock = await mut.acquire();
  try {
    await doSomeStuff();
    await doOtherStuff();
  } finally {
    unlock();
  }
}

I'm not sure if there's any easy way to create the sort of timing issues that would lead to a test failure if the mutex doesn't work as expected. Any advice would be very much appreciated.

Answer 1

You need a test that is deterministic, and the behavior of which will change if the mutex breaks.

The example below is an atomic counter problem. Two workers are spawned that each do three things in a loop:

1. Fetch a value from a global counter and store it in a local variable
2. Increment the value in the local variable
3. Write the local variable back to the global counter

Crucially, I'm using await and setTimeout here to create breaks in the execution. An async function without any awaits will be completely atomic, so we need to create some breaks to allow the scheduler to switch between tasks. If the mutex is broken, these awaits will allow the scheduler to run code from the other worker, since each await is a chance for the Javascript scheduler to change jobs.

If the mutex is working, you should see the following. Between each step, the worker goes to sleep and wakes back up, but the mutex doesn't allow the other worker to do anything:

1. Worker 1 acquires the lock
2. Worker 1 reads the value 0 from the global counter
3. Worker 1 increments the value from 0 to 1
4. Worker 1 writes the value 1 back to the global counter
5. Worker 1 releases the lock
6. Worker 2 acquires the lock
7. Worker 2 reads the value 1 from the global counter
8. Worker 2 increments the value from 1 to 2
9. Worker 2 writes the value 2 back to the global counter
10. Worker 2 releases the lock

Result: 2, Expected: 2

If the mutex doesn't work (or isn't used), the two workers will trip over each other, and the end result will be incorrect. As before, the workers go to sleep each time they perform an action:

1. Worker 1 reads the value 0 from the global counter
2. Worker 2 reads the value 0 from the global counter
3. Worker 1 increments the value from 0 to 1
4. Worker 2 increments the value from 0 to 1
5. Worker 1 writes the value 1 back to the global counter
6. Worker 2 writes the value 1 back to the global counter

Result: 1, Expected: 2

In both cases the two workers are performing the same actions, but if the order is not enforced then the result is incorrect.

This example is contrived, but reproducible and mostly deterministic. When the mutex is working, you will always get the same end result. When it's not, you will always get a wrong result.

Working demo:

var state = {
  isMutexBroken: false,
  counter: 0,
  worker1LastAction: '',
  worker2LastAction: '',
  worker1IsActive: false,
  worker2IsActive: false,
}

class Mutex {
  constructor() {
    this.current = Promise.resolve();
  }

  async acquire() {
    if (state.isMutexBroken) {
      return () => {};
    }

    let release;
    const next = new Promise(resolve => {
      release = () => {
        resolve();
      };
    });
    const waiter = this.current.then(() => release);
    this.current = next;
    return await waiter;
  }
}

var mutex = new Mutex();

const renderState = () => {
  document.getElementById('mutex-status').textContent = state.isMutexBroken ? 'Mutex is *not* working correctly. Press "fix mutex" to fix it.' : 'Mutex is working correctly. Press "break mutex" to break it.';
  document.getElementById('counter').textContent = `Counter value: ${state.counter}`;
  document.getElementById('worker1').textContent = `Worker 1 - last action: ${state.worker1LastAction}`;
  document.getElementById('worker2').textContent = `Worker 2 - last action: ${state.worker2LastAction}`;

  document.getElementById('start-test').disabled = state.worker1IsActive || state.worker2IsActive;
  document.getElementById('break-mutex').disabled = state.worker1IsActive || state.worker2IsActive;
  document.getElementById('fix-mutex').disabled = state.worker1IsActive || state.worker2IsActive;
}

// https://stackoverflow.com/a/39914235/8166701
function sleep(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

const worker = async(delay, count, id) => {
  state[`${id}IsActive`] = true;

  let workerCopyOfCounter;

  for (let i = 0; i < count; i++) {
    const unlock = await mutex.acquire();

    state[`${id}LastAction`] = `Aquired lock.`;
    renderState();

    await sleep(delay);

    workerCopyOfCounter = state.counter;
    state[`${id}LastAction`] = `Acquired global counter: ${workerCopyOfCounter}`;
    renderState();

    await sleep(delay);

    workerCopyOfCounter++;
    state[`${id}LastAction`] = `Incremented counter: ${workerCopyOfCounter}`;
    renderState();

    await sleep(delay);

    state.counter = workerCopyOfCounter;
    state[`${id}LastAction`] = `Wrote ${workerCopyOfCounter} back to global counter.`;
    renderState();

    await sleep(delay);

    unlock();

    state[`${id}LastAction`] = `Released lock.`;
    renderState();

    await sleep(delay);
  }

  state[`${id}LastAction`] = `Finished.`;
  state[`${id}IsActive`] = false;
  renderState();
}

document.getElementById('break-mutex').onclick = () => {
  state.isMutexBroken = true;
  renderState();
}
document.getElementById('fix-mutex').onclick = () => {
  state.isMutexBroken = false;
  renderState();
}
document.getElementById('start-test').onclick = () => {
  document.getElementById('test-result').textContent = '';
  document.getElementById('start-test').textContent = 'Reset and start test';

  state.counter = 0;
  state.worker1LastAction = '';
  state.worker2LastAction = '';

  renderState();
  
  const slow = document.getElementById('slow').checked;
  const multiplier = slow ? 10 : 1;

  Promise.all([
    worker(20 * multiplier, 10, 'worker1'),
    worker(55 * multiplier, 5, 'worker2')
  ]).then(() => {
    const elem = document.getElementById('test-result');
    elem.classList.remove('pass');
    elem.classList.remove('fail');
    elem.classList.add(state.counter === 15 ? 'pass' : 'fail');
    elem.textContent = state.counter === 15 ? 'Test passed' : 'Test failed';
  });
}

renderState();

.flex-column {
  display: flex;
  flex-direction: column;
}

.flex-row {
  display: flex;
}

.top-padding {
  padding-top: 8px;
}

.worker-state-container {
  background-color: #0001;
  margin-top: 8px;
  padding: 5px;
}

.pass {
  background-color: limegreen;
  color: white;
}

.fail {
  background-color: red;
  color: white;
}

<div class="flex-column">
  <div className="flex-row">
    <button id="break-mutex">Break mutex</button>
    <button id="fix-mutex">Fix mutex</button>
    <div id="mutex-status"></div>
  </div>
  <div className="flex-row">
    <input type="checkbox" id="slow" name="slow"><label for="slow">slow</label>
  </div>
  <div class="flex-row top-padding">
    <button id="start-test">Start test</button>
  </div>

  <div id="counter"></div>
  <div>Expected end value: 15</div>
  <div id="test-result"></div>

  <div class="top-padding">
    <div id="worker1" class="worker-state-container">

    </div>
    <div id="worker2" class="worker-state-container">

    </div>
  </div>
</div>

Minimal version:

var state = { counter: 0 }

// https://stackoverflow.com/a/39914235/8166701
function sleep(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

const worker = async (delay, count) => {
  let workerCopyOfCounter;

  for (let i = 0; i < count; i++) {
    // Lock the mutex
    const unlock = await mutex.acquire();

    // Acquire the counter
    workerCopyOfCounter = state.counter;
    await sleep(delay);

    // Increment the local copy
    workerCopyOfCounter++;
    await sleep(delay);

    // Write the local copy back to the global counter
    state.counter = workerCopyOfCounter;
    await sleep(delay);

    // Unlock the mutex
    unlock();
    await sleep(delay);
  }
}

// Create two workers with different delays. If the code is working,
// state.counter will equal 15 when both workers are finished.
Promise.all([
  worker(20, 10),
  worker(55, 5),
]).then(() => {
  console.log('Expected: 15');
  console.log('Actual:', state.counter);
});