Módulo 5 - Problemas Clássicos de IPC e Deadlock

Relembrando

Processos podem se comunicar utilizando mecanismos de IPC (Inter-process Communication), como memória compartilhada ou comunicação por mensagens. A proteção que deve ser fornecida à essa comunicação pode gerar alguns problemas, como por exemplo deadlock, que ocorre quando dois ou mais processos aguardam mutuamente por um recurso utilizado por um deles, e starvation, que ocorre quando os mecanismos de sincronização não permitem que o programa avance. Para exemplificar o problema do deadlock a literatura fornece alguns problemas clássicos, como o do Jantar dos Filósofos.

Problema do Jantar dos Filósofos

Esse problema foi formulado e resolvido por Dijkstra em 1965 e consiste na seguinte situação:

Cinco filósofos estão sentados em torno de uma mesa circular, cada qual com um prato de espaguete escorregadio, que para ser consumido necessita de dois garfos, mas não há garfos suficientes para que todos os filósofos comam ao mesmo tempo, já que há um garfo entre cada par de pratos (Figura 1).

Figura 1. Ilustração do problema do jantar dos filósofos. (Fonte: [1]).

Portanto, cada filósofo compartilha seus garfos com os filósofos imediatamente à esquerda e à direita. A vida de um filósofo consiste em alternar períodos de pensar e se alimentar, sendo que depois de pensar durante muito tempo ele tentará se alimentar.

Para se alimentar, o filósofo tenta pegar um garfo à sua esquerda e à sua direita, em qualquer ordem. Quando conseguir pegar os dois garfos, ele se alimentará, e em seguida devolverá os garfos à mesa.

filosofos.c
#include <stdio.h>
#include <unistd.h>

int qtPhilosophers = 5; // Number of philosophers.

void think(int i)
{
    printf("Philosopher %d is THINKING...\n\n", i);
    sleep(1);
}

void take_fork(int i)
{
    printf("Attempting to get fork at position %d.\n\n", i);
}

void eat()
{
    printf("Eating...\n\n");
    sleep(1);
}

void put_fork(int i)
{
    printf("Returning fork at position %d.\n\n", i);
}

void philosopher(int i)
{
    while (1)
    {
        int left = i;
        int right = (i + 1) % qtPhilosophers;
        think(i);
        take_fork(left);
        take_fork(right);
        eat();
        put_fork(right); // Returning in inverse order of retrieval
        put_fork(left);  // increases parallelism.
    }
}

O problema acontece se todos os filósofos tentarem pegar o garfo ao mesmo tempo, a depender do escalonamento. Se o escalonamento fizer a troca de contexto após a obtenção do primeiro garfo, quando o N-ésimo filósofo tentar pegar o garfo direito, este já terá sido obtido pelo filósofo à sua direita.Então, todos os filósofos ficarão bloqueados tentando obter o outro garfo, e esse problema é conhecido como deadlock (ou impasse).

E se o filósofo devolver o garfo esquerdo se não conseguir obter o direito?

Essa solução pode minimizar o problema, mas ainda é possível obter um escalonamento problemático, como no caso em que a troca de contexto ocorre após um filósofo obter ou liberar um garfo, teríamos a situação:

F1 obtém o garfo, ..., F5 obtém o garfo.

<Troca de contexto>

F1 testa e libera o garfo, ..., F5 testa e libera o garfo. 

<Troca de contexto>

F1 obtém o garfo, ..., F5 obtém o garfo.

Essa situação gera outro problema, embora os filósofos estejam processando, não há nenhum tipo de progresso. Tal problema é chamado de starvation (inanição).

Uma terceira solução seria o filósofo esperar um tempo aleatório para tentar obter o garfo novamente, caso não consiga na primeira tentativa, que é uma solução muito boa do ponto de vista prático, inclusive utilizada no tráfego de pacotes em cabos de rede, mas não é uma solução completa do ponto de vista teórico, já que existe uma mínima probabilidade de que dois filósofos esperem a mesma quantidade de tempo, ficando bloqueados.

É possível resolver o problema utilizando semáforos binários, protegendo uma seção crítica com o uso de um mutex. Antes de começar a pegar os garfos, um filósofo realiza down em um mutex e após substituir os garfos ele realiza up nesse mutex. Essa solução, embora correta do ponto de vista teórico, apresenta um problema de desempenho, pois embora os filósofos possam pensar em paralelo, apenas um pode se alimentar por vez, embora seja possível que mais do que um se alimente em paralelo.

A melhor solução, do ponto de vista teórico, é proteger as funções de pegar e liberar os garfos com um semáforo binário e um array de semáforos (s), no qual cada filósofo i incrementa s[i] caso obtenha os dois garfos, ou bloqueia nele esperando o vizinho liberar o garfo.

jantar_dos_filosofos.c
#include <semaphore.h>
#include <pthread.h>
#include <unistd.h>
#include <stdio.h>

#define N 5

#define LEFT (i + N - 1) % N
#define RIGHT (i + 1) % N

#define THINKING 0
#define HUNGRY 1
#define EATING 2

// Semáforo binário para proteger as funções de pegar e guardar os garfos.
sem_t mutex;

// Estados dos filósofos, entre {HUNGRY, EATING, THINKING}.
int state[N];

// Array de semáforos para os N filósofos.
sem_t s[N];

// Número dos filósofos definido globalmente para ser
// acessado pelos processos filhos.
int phil[N] = {0, 1, 2, 3, 4};

// Testa se os garfos estão livres para o filósofo i,
// o que ocorre se os seus vizinhos não estiverem comendo.
void test(int i)
{
    if (
        state[i] == HUNGRY 
        && state[LEFT] != EATING 
        && state[RIGHT] != EATING)
    {
        state[i] = EATING;
        printf("Philosopher %d takes forks %d and %d. \n", 
        i, LEFT, RIGHT);
        printf("Philosopher %d is EATING.\n", i);

        sem_post(&s[i]);
    }
}

// Função "atômica" para pegar ambos garfos, protegida pelo mutex.
void take_forks(int i)
{
    sem_wait(&mutex);
    state[i] = HUNGRY;

    printf("Philosopher %d is HUNGRY.\n", i);

    test(i);
    sem_post(&mutex);

    sem_wait(&s[i]);
    sleep(1);
}

// Função "atômica" para devolver os garfos e 
// sinalizar os vizinhos.
void put_forks(int i)
{
    sem_wait(&mutex);
    state[i] = THINKING;

    printf("Philosopher %d is putting down forks %d and %d.\n", 
                i, LEFT, RIGHT);
    printf("Philosopher %d is THINKING.\n", i);
    test(LEFT);
    test(RIGHT);

    sem_post(&mutex);
}

void think(int i)
{
    printf("Philosopher %d is THINKING...\n", i);
    sleep(1);
}

void *philosopher_semaphores(void *num)
{
    while (1)
    {
        int *i = num;
        think(*i);

        take_forks(*i);
        sleep(1);
        put_forks(*i);
    }
}



// Aplicação utilizando pthreads.
void main()
{
    int i;
    pthread_t thread_id[N];

    sem_init(&mutex, 0, 1);

    for (i = 0; i < N; i++)
        sem_init(&s[i], 0, 0);

    for (i = 0; i < N; i++)
        pthread_create(&thread_id[i], 
          NULL, philosopher_semaphores, &phil[i]);

    for (i = 0; i < N; i++)
        pthread_join(thread_id[i], NULL);
}

Outras soluções completas para o jantar dos filósofos são:

Permitir que apenas quatro filósofos sentem-se à mesa;
Permitir que o filósofo pegue o garfo da esquerda apenas se o da direita estiver livre (uma operação atômica para pegar e verificar);
Permitir que um filósofo ímpar pegue primeiro o seu garfo da esquerda e depois o da direita, enquanto um par pega o da direita e depois o da esquerda.

Recursos

Recursos são objetos que um processo pode adquirir de maneira exclusiva, quando apenas um processo pode utilizar por vez (exclusão mútua), ou não. Um recurso é qualquer coisa que pode ser adquirida, usada e liberada, e pode ser classificado em preemptível ou não preemptível.

Recursos preemptíveis: podem ser retirados do proprietário por uma entidade externa sem causar-lhe prejuízo, como por exemplo memória não utilizada.

Recursos não preemptíveis: não podem ser tomados à força, o processo que está utilizando deve liberá-lo espontaneamente, como por exemplo uma impressora.

Em geral, deadlocks ocorrem em recursos não preemptíveis, já que nos preemptíveis uma simples transferência de recursos resolveria o problema.

Para utilizar um recurso, um processo deve solicitá-lo, usá-lo e liberá-lo. Se o recurso não estiver disponível quando for solicitado, o processo é forçado a esperar.

Deadlock

O deadlock é definido, formalmente, da seguinte maneira:

“Um conjunto de processos estará em situação de deadlock se cada processo no conjunto estiver esperando por um evento que apenas outro processo no conjunto pode causar.”

Modelagem de Deadlock

Referências

[1] TANENBAUM, A. S. Sistemas. Operacionais Modernos. 4ª ed. Prentice Hall, 2016.