O jantar dos filósofos é um problema sobre a sincronização na comunicação entre processos e threads em sistemas operacionais. O problema foi proposto por Edsger W. Dijkstra em 1965 e é considerado um dos problemas clássicos sobre sistemas operacionais.
O problema consiste em cinco filósofos sentados ao redor de uma mesa circular para o jantar, onde cada filósofo possui um prato para comer macarrão. Os filósofos possuem hashis e cada um precisa de 2 hashis para comer, porém para cada par de pratos existe apenas um hashi. Um filósofo possui duas ações: pensar ou comer. Quando um filósofo ficar com fome ele irá tentar pegar o hashi à sua direita e à sua esquerda, um de cada vez. Se ele conseguir pegar os dois hashis, ele irá comer a comida em um tempo determinado e irá colocar os hashis sobre a mesa novamente, voltando a pensar.
O objetivo é a criação de um algoritmo que seja implementado de modo que cada filósofo execute suas ações sem ficar travado. Caso todos os filósofos peguem um hashi ao mesmo tempo, todos irão ficar parados para sempre aguardando o segundo hashi ficar disponível, gerando um Deadlock.
Deadlock, que pode ser traduzido como "impasse", é uma situação onde dois ou mais processos ficam impedidos de continuar suas execuções. Essa situação ocorre quando um processo necessita de um recurso do sistema para continuar sua execução e este está sendo usado por outro processo, que por sua vez também espera pela liberação de algum recurso utilizado por outro processo. Assim, todos estes processos ficam bloqueados, esperando uns pelos outros.
Fonte: Medium
Se um filósofo conseguir pegar apenas o primeiro hashi e por isso devolvê-lo a mesa, esperando um tempo fixo para tentar pegar os dois hashis novamente, teremos um caso de starvation (inanição), onde o filósofo poderá morrer de fome. Ele poderá tentar fazer a mesma ação de pegar e depois devolver o hashi pra sempre, nunca conseguindo comer. A solução do problema é feita para não ocorrer casos de deadlock ou starvation. Para tal são utilizados os conceitos de semáforo e exclusão mútua (mutex)
Mutex, acrônimo para mutual exclusion (exclusão mútua) é uma técnica utilizada em programação concorrente para evitar que dois processos tenham acesso a algum recurso compartilhado ao mesmo tempo, sendo esse acesso denominado por região crítica. A forma mais simples de mutex é a utilização de um semáforo binário, bloqueando o acesso ao recurso enquanto uma tarefa estiver utilizando-o e liberando em seguida. Neste caso, os mutexes serão utilizados para controlar o acesso dos filósofos aos hashis.
No código é criada a classe Filosofo, que irá representá-los, com suas ações e características. Ela herda a classe Thread, uma classe da biblioteca Threading que representa uma atividade realizada por uma thread utilizando paralelismo. Uma classe construtora __init__ é definida para preencher os atributos dos filósofos: seu nome, a identificação do hashi a sua esquerda e o da sua direita. Também chama o construtor de sua superclasse: Thread.__init__(self). A identificação dos hashis é feita utilizando uma lista de mutexes, com índices de 0 a 4. Por exemplo: quando o mutex de índice 0 estiver desbloqueado, significa que o hashi 0 está livre para uso.
A função run definida na biblioteca Threading é sobreposta, possuindo um laço onde, enquanto o Filósofo estiver sendo executado, deixa o filósofo pensando por um intervalo de tempo e após isso ele tenta comer. A função comer (se o Filosofo estiver em execução) tenta pegar o hashi a esquerda (bloquear o mutex relacionado ao hashi) e após tenta pegar o hashi a direita. Se o segundo hashi ja está bloqueado, o primeiro hashi é liberado e o filósofo volta a pensar. Se os dois hashis estiverem disponíveis, o filósofo os bloqueia e começa a comer. Após um intervalo de tempo, o filósofo para de comer, libera os hashis e o contador de vezes que o filósofo comeu é incrementado.
É iniciada uma lista com 5 nomes de filósofos, a lista de hashis já falada anteriormente e uma lista mesa, que instancia os 5 filósofos com os hashis correspondentes. Então, dentro de um laço é iniciada a execução e também cada thread de filósofo. Assim, o programa é executado.
O código abaixo implementa a solução para o problema do jantar dos filósofos utilizando os conceitos elencados anteriormente.
from random import uniform
from time import sleep
from threading import Thread, Lock
pratos = [0, 0, 0, 0, 0] # 0 = Não comeu, 1 = Já comeu
class Filosofo(Thread):
execute = True # variável para realizar a execução
def __init__(self, nome, hashi_esquerda, hashi_direita): # Construtor da classe Filosofo
Thread.__init__(self)
self.nome = nome
self.hashi_esquerda = hashi_esquerda
self.hashi_direita = hashi_direita
def run(self):
""" Sobrescrita de Thread, a função run definirá o que irá acontecer após chamar o método start() na
instância criada. """
while self.execute:
print(f"\n {self.nome} está pensando")
sleep(uniform(5, 15))
self.comer()
def comer(self):
"""
Pega o hashi 1 e tenta pegar o hashi 2. Se o hashi 2 estiver livre,
o ele janta e solta os dois hashis em seguida,senão ele desiste de
comer e continua pensando.
"""
hashi1, hashi2 = self.hashi_esquerda, self.hashi_direita
while self.execute: # enquanto tiver executando
hashi1.acquire(True) # tenta pegar o primeiro hashi
locked = hashi2.acquire(False) # verifica se o segundo hashi está livre
if locked:
break
hashi1.release() # libera o hashi1
else:
return # volta a pensar
print(f"\n {self.nome} começou a comer")
sleep(uniform(5, 10))
print(f"\n {self.nome} parou de comer")
pratos[nomes.index(self.nome)] += 1 # contabiliza o número de vezes que cada filosofo comeu
print(pratos)
hashi1.release() # libera o hashi1
hashi2.release() # libera o hashi2
nomes = ['Aristóteles', 'Platão', 'Sócrates', 'Pitágoras', 'Demócrito'] # Nomes dos filósofos
hashis = [Lock() for _ in range(5)]
mesa = [Filosofo(nomes[i], hashis[i % 5], hashis[(i + 1) % 5]) for i in range(5)]
for _ in range(50):
Filosofo.execute = True # Inicia a execução
for filosofo in mesa:
try:
filosofo.start() # inicia o objeto de thread criado.
sleep(2)
except RuntimeError: # Se a thread já tiver sido iniciada
pass
sleep(uniform(5, 15))
Filosofo.execute = False # Para a execução