测试 javascript 互斥实现

Question

我已经为 javascript / typescript 编写了一个互斥实现，但我正在为如何测试它而苦苦挣扎。这是实现：

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;
    }

}

用法：

const mut = new Mutex();

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

我不确定是否有任何简单的方法可以创建那种在互斥量未按预期工作时会导致测试失败的计时问题。任何建议将不胜感激。

Answer 1

我会创建一个可能将对象按顺序放在共享数组上的实现。您可以使用互斥锁模拟按顺序访问数组。您的测试将简单地声明正确的插入顺序。我会利用 setTimeout 来安排尝试锁定互斥锁，并在成功获取后，将一个元素添加到共享数组。

Answer 2

您需要一个确定性的测试，如果互斥体中断，其行为将会改变。

下面的例子是一个原子计数器问题。产生两个工人，每个工人循环做三件事：

从全局计数器中获取一个值并将其存储在局部变量中
增加局部变量中的值
将局部变量写回全局计数器

重要的是，我在这里使用 await 和 setTimeout 来在执行中创建中断。没有任何 await 的 async 函数将是完全原子的，因此我们需要创建一些中断以允许调度程序在任务之间切换。如果互斥量被破坏，这些 awaits 将允许调度程序从其他工作人员运行代码，因为每个 await 都是 Javascript 调度程序更改作业的机会.

如果互斥体正常工作，您应该会看到以下内容。在每一步之间，worker 进入睡眠状态并再次醒来，但互斥体不允许其他 worker 做任何事情：

Worker 1 acquires the lock

Worker 1 reads the value 0 from the global counter

Worker 1 increments the value from 0 to 1

Worker 1 writes the value 1 back to the global counter

Worker 1 releases the lock

Worker 2 acquires the lock

Worker 2 reads the value 1 from the global counter

Worker 2 increments the value from 1 to 2

Worker 2 writes the value 2 back to the global counter

Worker 2 releases the lock

结果：2，预期：2

如果互斥量不起作用（或未被使用），两个工人将互相绊倒，最终结果将是不正确的。和以前一样，工人每次执行一个动作都会进入睡眠状态：

Worker 1 reads the value 0 from the global counter

Worker 2 reads the value 0 from the global counter

Worker 1 increments the value from 0 to 1

Worker 2 increments the value from 0 to 1

Worker 1 writes the value 1 back to the global counter

Worker 2 writes the value 1 back to the global counter

结果：1，预期：2

在这两种情况下，两名工人都在执行相同的操作，但如果不执行命令，则结果不正确。

此示例是人为设计的，但可重现并且大部分是确定性的。当互斥量起作用时，您将始终获得相同的最终结果。如果不是，你总是会得到错误的结果。

工作演示：

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;
}

// 
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>

最小版本：

var state = { counter: 0 }

// 
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);
});

测试 javascript 互斥实现

Testing a javascript mutex implementation

javascript

testing

mutex

typescript