algorithm - secciones - Algoritmo de Peterson

quien creo el algoritmo de dekker

Question

En el algoritmo clásico de Peterson, comprueba 2 indicadores flag1 y flag2 y la variable de giro antes de ingresar a una sección crítica. ¿Funcionará si primero verifico si doy la vuelta y luego busco las banderas?

Answer 1

Sí, funcionará, si primero verifica turn y luego marca flag[0] o flag[1] dentro de la condición en while() .

La razón es que la espera ocupada se realiza solo cuando ambas condiciones son verdaderas.

Como prueba, he escrito un pequeño programa en C que simula dos procesos con interruptores aleatorios entre ellos.

Para la sección crítica, uso este fragmento de código en el proceso 0:

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

y esto en el proceso 1:

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

Ambos procesos ejecutan esta sección 1000 veces cada uno. Si hay una condición de carrera entre las secciones críticas de los dos, global probablemente sea diferente de 2000 al final de la simulación.

Código:

#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/n", Vars[VarGlobal]);
  return 0;
}

Salida ( ideone ):

VarGlobal = 2000

Ahora, el mismo programa con el orden de los controles como en Wikipedia , para el cual defino SWAP_CHECKS como 0: output ( ideone ):

VarGlobal = 2000

Finalmente, para mostrar que hay una condición de carrera cuando el algoritmo de Peterson está desactivado, defino USE_PETERSON como 0: output ( ideone ):

VarGlobal = 1610