Алгоритм Петерсона

Question

В классическом алгоритме Петерсона вы проверяете наличие 2 флагов flag1 и flag2 и переменную поворота перед вступлением в критический раздел. Будет ли это работать, если я сначала проверю очередь и затем проверит флаги?

Answer 1

Да, это будет работать, если вы сначала проверите turn, а затем отметьте flag[0] или flag[1] внутри этого условия в while().

Причина в том, что ожидание выполняется только при условии, что оба условия являются истинными.

В качестве доказательства я написал небольшую программу на C, имитирующую два процесса со случайными переключателями между ними.

Для критической секции я использую этот кусок кода в процессе 0:

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

и это в процессе 1:

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

Оба процесса выполняют этот раздел 1000 раз каждый. Если между критическими разделами есть условие гонки, global, вероятно, будет отличаться от 2000 в конце моделирования.

Код:

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

Выход (ideone):

VarGlobal = 2000 

Теперь та же программа с порядком проверок, как в Wikipedia, для которых я определяю SWAP_CHECKS, как 0: выход (ideone):

VarGlobal = 2000 

И, наконец, s как это состояние гонки, когда алгоритм Петерсона отключен, я определяю USE_PETERSON как 0: выход (ideone):