彼得森算法 [英] Peterson's Algorithm

问题描述

在经典的 Peterson 算法中，您在进入临界区之前检查 2 个标志 flag1 和 flag2 以及 turn 变量.如果我先检查 turn 然后检查标志，这会起作用吗?

In the classic Peterson's algorithm, you check for 2 flags flag1 and flag2 and the turn variable before entering a critical section.Will this work if I check for turn first and then check for the flags ?

推荐答案

是的，如果你先检查 turn 然后检查 flag[0] 或flag[1] 在 while() 中的条件内.

Yes, it will work, if you first check turn and then check flag[0] or flag[1] inside the condition in while().

原因是只有当两个条件都为真时才会执行忙等待.

The reason is that busy waiting is performed only when both conditions are true.

作为一个证明，我编写了一个小型 C 程序来模拟两个进程，并在它们之间进行随机切换.

As a proof I've written a small C program simulating two processes with random switches between them.

对于关键部分，我在进程 0 中使用了这段代码:

For the critical section I use this piece of code in process 0:

global ^= 0x5555;
global ^= 0x5555;
global++;

这在过程 1 中:

global ^= 0xAAAA;
global ^= 0xAAAA;
global++;

两个进程各执行此部分 1000 次.如果两者的关键部分之间存在竞争条件，则 global 可能与模拟结束时的 2000 不同.

Both processes execute this section 1000 times each. If there's a race condition between the critical sections of the two, global will likely be different from 2000 at the end of the simulation.

代码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef enum
{
  InstrNop,
  InstrHalt,
  InstrSetVarNum,
  InstrJumpVarZero,
  InstrJumpVarNonzero,
  InstrJump,
  InstrIncVar,
  InstrDecVar,
  InstrXorVarNum,
} tInstr;

int ExecuteInstruction(unsigned* Vars, const unsigned* Program, unsigned* Position)
{
  switch (Program[*Position])
  {
  default:
  case InstrHalt:
    return 0;

  case InstrNop:
    (*Position)++;
    break;

  case InstrSetVarNum:
    Vars[Program[*Position + 1]] = Program[*Position + 2];
    (*Position) += 3;
    break;

  case InstrXorVarNum:
    Vars[Program[*Position + 1]] ^= Program[*Position + 2];
    (*Position) += 3;
    break;

  case InstrJumpVarZero:
    if (Vars[Program[*Position + 1]] == 0)
      (*Position) = Program[*Position + 2];
    else
      (*Position) += 3;
    break;

  case InstrJumpVarNonzero:
    if (Vars[Program[*Position + 1]] != 0)
      (*Position) = Program[*Position + 2];
    else
      (*Position) += 3;
    break;

  case InstrJump:
    (*Position) = Program[*Position + 1];
    break;

  case InstrIncVar:
    Vars[Program[*Position + 1]]++;
    (*Position) += 2;
    break;

  case InstrDecVar:
    Vars[Program[*Position + 1]]--;
    (*Position) += 2;
    break;
  }

  return 1;
}

typedef enum
{
  VarGlobal,

  VarCnt0,
  VarCnt1,

  VarFlag0,
  VarFlag1,
  VarTurn,

  VarIdxMax
} tVarIdx;

unsigned Vars[VarIdxMax];

#define USE_PETERSON 01
#define SWAP_CHECKS 01

const unsigned Program0[] =
{
  // cnt0 = 1000;
  InstrSetVarNum, VarCnt0, 1000,

// 3:
#if USE_PETERSON
  // flag[0] = 1;
  InstrSetVarNum, VarFlag0, 1,
  // turn = 1;
  InstrSetVarNum, VarTurn, 1,
// 9:
  // while (flag[1] == 1 && turn == 1) {}
#if SWAP_CHECKS
  InstrJumpVarZero, VarTurn, 17,
  InstrJumpVarZero, VarFlag1, 17,
#else
  InstrJumpVarZero, VarFlag1, 17,
  InstrJumpVarZero, VarTurn, 17,
#endif
  InstrJump, 9,
// 17:
#endif

// Critical section starts
  // global ^= 0x5555;
  // global ^= 0x5555;
  // global++;
  InstrXorVarNum, VarGlobal, 0x5555,
  InstrXorVarNum, VarGlobal, 0x5555,
  InstrIncVar, VarGlobal,
// Critical section ends

#if USE_PETERSON
  // flag[0] = 0;
  InstrSetVarNum, VarFlag0, 0,
#endif

  // cnt0--;
  InstrDecVar, VarCnt0,
  // if (cnt0 != 0) goto 3;
  InstrJumpVarNonzero, VarCnt0, 3,

  // end
  InstrHalt
};

const unsigned Program1[] =
{
  // cnt1 = 1000;
  InstrSetVarNum, VarCnt1, 1000,

// 3:
#if USE_PETERSON
  // flag[1] = 1;
  InstrSetVarNum, VarFlag1, 1,
  // turn = 0;
  InstrSetVarNum, VarTurn, 0,
// 9:
  // while (flag[0] == 1 && turn == 0) {}
#if SWAP_CHECKS
  InstrJumpVarNonzero, VarTurn, 17,
  InstrJumpVarZero, VarFlag0, 17,
#else
  InstrJumpVarZero, VarFlag0, 17,
  InstrJumpVarNonzero, VarTurn, 17,
#endif
  InstrJump, 9,
// 17:
#endif

// Critical section starts
  // global ^= 0xAAAA;
  // global ^= 0xAAAA;
  // global++;
  InstrXorVarNum, VarGlobal, 0xAAAA,
  InstrXorVarNum, VarGlobal, 0xAAAA,
  InstrIncVar, VarGlobal,
// Critical section ends

#if USE_PETERSON
  // flag[1] = 0;
  InstrSetVarNum, VarFlag1, 0,
#endif

  // cnt1--;
  InstrDecVar, VarCnt1,
  // if (cnt1 != 0) goto 3;
  InstrJumpVarNonzero, VarCnt1, 3,

  // end
  InstrHalt
};

void Simulate(void)
{
  unsigned pos0 = 0, pos1 = 0;

  while (Program0[pos0] != InstrHalt ||
         Program1[pos1] != InstrHalt)
  {
    int cnt;

    cnt = rand() % 50;
    while (cnt--)
      if (!ExecuteInstruction(Vars, Program0, &pos0))
        break;

    cnt = rand() % 50;
    while (cnt--)
      if (!ExecuteInstruction(Vars, Program1, &pos1))
        break;
  }
}

int main(void)
{
  srand(time(NULL));
  Simulate();
  printf("VarGlobal = %u
", Vars[VarGlobal]);
  return 0;
}

输出(ideone):

VarGlobal = 2000

现在，检查顺序与 Wikipedia 中相同的程序，用于我将 SWAP_CHECKS 定义为 0:输出(ideone):

Now, the same program with the order of the checks as in Wikipedia, for which I define SWAP_CHECKSas 0: output (ideone):

VarGlobal = 2000

最后，为了表明当 Peterson 算法被禁用时存在竞争条件，我将 USE_PETERSON 定义为 0: output (ideone):

Finally, to show that there's a race condition when Peterson's algorithm is disabled, I define USE_PETERSON as 0: output (ideone):

VarGlobal = 1610

这篇关于彼得森算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！