Nodejs 经典互斥算法解析： Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包店算法

Nodejs 经典互斥算法解析： Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包店算法

原文：http://levi.cg.am/?p=2171 本文用较为轻松的方式介绍了几个经典的互斥算法： Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包店算法，并简单地给出了每一个算法的正确性证明和相关的讨论。本文探寻分布式计算历史上的几个非常有名非常经典的互斥算法,尽管这些算法几乎是所有操作系统、分布式系统或多线程编程课本中必介绍的算 法,可是由于这些算法由于性能问题已经被现代的算法或机制替代了,实际中不会有人使用这些算法。尽管如此,了解这些算法可以帮助我们理解同步领域的基本原理。此外,了解这些算法的正确性证明可还可以训练并发算法正确性推导的思维。 enter image description here

文档下载：

enter image description here 乱炖 http://levi.cg.am php、js、html5、css3


2 回复

Nodejs 经典互斥算法解析： Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包店算法

在本篇文章中，我们将探讨几种经典的互斥算法，包括 Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包店算法。虽然这些算法已经不常用于现代系统中，但它们仍然是理解和学习并发编程的基础。

Dekker 算法

Dekker 算法是第一个解决临界区问题的确定性算法。它通过两个变量 flag 和 turn 来确保两个进程不会同时进入临界区。

let flag = [false, false];
let turn;

function enterCriticalSection(pid) {
    let otherPid = 1 - pid;
    flag[pid] = true;
    turn = otherPid;
    while (flag[otherPid] && turn === otherPid) {}
}

function leaveCriticalSection(pid) {
    flag[pid] = false;
}

Dijkstra 提出的算法

Dijkstra 提出的算法利用了信号量来实现进程间的互斥。

let semaphores = [new Semaphore(1), new Semaphore(1)];

function enterCriticalSection(pid) {
    semaphores[pid].wait();
    if (semaphores[1-pid].value === 1) {
        semaphores[pid].signal();
        semaphores[pid].wait();
    }
}

function leaveCriticalSection(pid) {
    semaphores[pid].signal();
}

Peterson 算法

Peterson 算法是 Dekker 算法的一个改进版本，它通过更简单的逻辑实现了相同的功能。

let flag = [false, false];
let turn;

function enterCriticalSection(pid) {
    let otherPid = 1 - pid;
    flag[pid] = true;
    turn = otherPid;
    while (flag[otherPid] && turn === otherPid) {}
}

function leaveCriticalSection(pid) {
    flag[pid] = false;
}

面包店算法

面包店算法是一种更复杂的算法，它模拟了面包店中的排队机制，确保每个进程都能公平地访问资源。

let number = [0, 0];
let choosing = [false, false];

function enterCriticalSection(pid) {
    choosing[pid] = true;
    number[pid] = Math.max(number[0], number[1]) + 1;
    choosing[pid] = false;
    for (let otherPid = 0; otherPid < 2; otherPid++) {
        while (choosing[otherPid]) {}
        while (number[otherPid] !== 0 && (number[otherPid] < number[pid] || (number[otherPid] === number[pid] && otherPid < pid))) {}
    }
}

function leaveCriticalSection(pid) {
    number[pid] = 0;
}

以上代码示例展示了每种算法的基本逻辑。尽管这些算法在现代系统中很少使用，但它们提供了理解和实现并发编程的重要基础。


Node.js 并不直接支持多进程间的锁机制，因为 Node.js 是单线程的，主要运行在事件循环中。但我们可以用 Node.js 来模拟或实现一些简单的互斥算法逻辑。下面简要介绍一下 Dekker 算法、Peterson 算法以及如何使用信号量（Semaphore）来模拟锁的行为。

Dekker 算法

Dekker 算法是第一个公平的二进程互斥算法。它通过两个进程之间的显式协议来确保互斥。

示例代码：

const DEKKER_LOCK = {
  want: [false, false],
  turn: 0,
};

function dekkerLock(processId) {
  DEKKER_LOCK.want[processId] = true;
  DEKKER_LOCK.turn = processId;
  while (DEKKER_LOCK.want[1 - processId] && DEKKER_LOCK.turn === processId);
}

function dekkerUnlock(processId) {
  DEKKER_LOCK.want[processId] = false;
}

Peterson 算法

Peterson 算法是另一种简单的二进程互斥算法，它比 Dekker 算法更直观。

示例代码：

const PETERSON_LOCK = {
  flag: [false, false],
  victim: 0,
};

function petersonLock(processId) {
  const other = 1 - processId;
  PETERSON_LOCK.flag[processId] = true;
  PETERSON_LOCK.victim = processId;
  while (PETERSON_LOCK.flag[other] && PETERSON_LOCK.victim === processId);
}

function petersonUnlock(processId) {
  PETERSON_LOCK.flag[processId] = false;
}

使用信号量模拟锁

在 Node.js 中，可以使用 async 和 await 结合 Semaphore 模拟锁。

示例代码：

const Semaphore = require('semaphore');

const sem = new Semaphore(1); // 初始化一个信号量，最多允许一个进程进入

async function criticalSection() {
  await sem.take(); // 请求锁
  try {
    // 进入临界区
    console.log("Process entered critical section");
  } finally {
    sem.leave(); // 释放锁
  }
}

以上代码展示了如何在 Node.js 中模拟一些经典的互斥算法。这些算法虽然在现代系统中可能不常用，但对于理解并发控制的基本原理仍然很有帮助。

回到顶部