Peterson’s Algorithm: Uma Solução Elegante para Exclusão Mútua

Peterson’s Algorithm é um algoritmo clássico usado em sistemas concorrentes para garantir exclusão mútua entre dois processos. Ele se destaca por sua simplicidade, eficiência e por não depender de instruções atômicas específicas do hardware, como o uso de spinlocks baseados em instruções test-and-set.

Neste artigo, vamos explorar os seguintes pontos:

1. O problema da exclusão mútua.
2. Como o algoritmo de Peterson resolve este problema.
3. A relação entre Peterson’s Algorithm e spinlocks.
4. Comparação com outras soluções de exclusão mútua.
5. Exemplos práticos em código.

1. O Problema da Exclusão Mútua

Em sistemas com threads ou processos que compartilham recursos (como variáveis ou arquivos), pode ocorrer o problema de condições de corrida. Isso ocorre quando dois ou mais processos tentam acessar e modificar o mesmo recurso ao mesmo tempo, causando resultados imprevisíveis.

A exclusão mútua garante que apenas um processo possa acessar o recurso crítico por vez.

2. O Algoritmo de Peterson

O algoritmo de Peterson é uma solução de exclusão mútua projetada para dois processos. Ele usa duas variáveis:

• flag[i]: indica que o processo i quer entrar na seção crítica.
• turn: determina de quem é a vez de entrar na seção crítica.

O algoritmo funciona da seguinte forma para dois processos (P0 e P1):

Implementação do Algoritmo

#include <stdio.h>
#include <pthread.h>
#include <stdbool.h>
#include <unistd.h>

#define NUM_ITERATIONS 5

bool flag[2] = {false, false};
int turn = 0;

void *process_0(void *arg) {
    for (int i = 0; i < NUM_ITERATIONS; i++) {
        // Indica interesse em entrar na seção crítica
        flag[0] = true;
        turn = 1;

        // Aguarda até que o outro processo não esteja interessado ou seja sua vez
        while (flag[1] && turn == 1);

        // Seção crítica
        printf("Processo 0 na seção crítica.\n");
        sleep(1);

        // Sai da seção crítica
        flag[0] = false;
    }
    return NULL;
}

void *process_1(void *arg) {
    for (int i = 0; i < NUM_ITERATIONS; i++) {
        // Indica interesse em entrar na seção crítica
        flag[1] = true;
        turn = 0;

        // Aguarda até que o outro processo não esteja interessado ou seja sua vez
        while (flag[0] && turn == 0);

        // Seção crítica
        printf("Processo 1 na seção crítica.\n");
        sleep(1);

        // Sai da seção crítica
        flag[1] = false;
    }
    return NULL;
}

int main() {
    pthread_t t0, t1;

    pthread_create(&t0, NULL, process_0, NULL);
    pthread_create(&t1, NULL, process_1, NULL);

    pthread_join(t0, NULL);
    pthread_join(t1, NULL);

    return 0;
}

3. Relação com Spinlocks

Peterson’s Algorithm pode ser visto como uma forma rudimentar de spinlock, uma técnica onde um processo “gira” em um loop verificando continuamente se pode acessar um recurso.

Vantagens e Desvantagens

• Vantagens:
  • Simples e eficiente para dois processos.
  • Não requer instruções atômicas específicas do hardware.
• Desvantagens:
  • Não é escalável para mais de dois processos.
  • É menos eficiente que soluções modernas que usam instruções como compare-and-swap.

Spinlock Clássico em C

#include <stdatomic.h>
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

atomic_flag lock = ATOMIC_FLAG_INIT;

void lock_spin() {
    while (atomic_flag_test_and_set(&lock)); // Gira até obter o lock
}

void unlock_spin() {
    atomic_flag_clear(&lock); // Libera o lock
}

void *critical_section(void *arg) {
    lock_spin();
    printf("Thread %ld na seção crítica.\n", (long)arg);
    sleep(1);
    unlock_spin();
    return NULL;
}

int main() {
    pthread_t threads[2];

    for (long i = 0; i < 2; i++) {
        pthread_create(&threads[i], NULL, critical_section, (void *)i);
    }

    for (int i = 0; i < 2; i++) {
        pthread_join(threads[i], NULL);
    }

    return 0;
}

4. Comparação com Outras Soluções

5. Exemplos de Uso no Mundo Real

Embora Peterson’s Algorithm seja de interesse mais acadêmico, a ideia de exclusão mútua se aplica amplamente:

• Mutexes e Semáforos em sistemas operacionais.
• Controle de acesso em bases de dados.
• Exclusão mútua em drivers de hardware.

Conclusão

Peterson’s Algorithm é uma solução elegante para exclusão mútua, especialmente em cenários simples. Apesar de suas limitações, sua compreensão é essencial para qualquer profissional interessado em sistemas concorrentes.