Sobre
Universidade Estadual de Ponta Grossa – Engenharia de Computação
Gustavo Marenda de Lima - RA: 19021026
Thiago Pankievicz – RA: 19011226
Professor: Dierone
Problema: Barbeiro Dorminhoco
Explicação do Problema
Este problema consiste em manter o barbeiro ocupado enquanto há clientes no estabelecimento , e fazê-lo descansar quando o estabelecimento se encontrar vazio. No estabelecimento há uma cadeira de barbeiro e n cadeiras de espera. Quando não tem clientes, o barbeiro irá sentar na cadeira de barbeiro e ir dormir. Quando um cliente chega, o mesmo deve acordar o babeiro. No caso da chegada de mais clientes, eles irão esperar caso haja cadeiras de espera vazias, caso contrário irão sair do estabelecimento.
No gif a seguir temos um exemplo de quando o cliente entra na barbearia vazia, e acorda o barbeiro, fazendo com que o mesmo corte o seu cabelo.
Já neste exemplo, o barbeiro está acordado e ja está ocupado, com apenas uma cadeira de espera vazia. Dessa forma o cliente que entra na barbearia deve sentar em uma das cadeiras disponíveis e esperar.
Neste último exemplo, a barbearia está cheia, e os novos clientes que chegam para cortar o cabelo, acabam indo embora.
Explicação do Código
O problema é programar o barbeiro e os clientes sem cair em condições de disputa (condições de corrida) (race conditions). Condições de disputa são situações em que duas ou mais threads (ou processos) estão trabalhando juntas e podem compartilhar algum armazenamento comum que cada uma pode ler e gravar. O resultado final depende de quem executa precisamente quando. Os resultados da maioria dos programas são bons, mas, de vez em quando, acontece algo estranho e inconsistente. Esse problema é semelhante a situações com várias filas, como uma mesa de atendimento de telemarketing com diversos atendentes e com um sistema computadorizado de chamadas em espera, atendendo a um número limitado de chamadas que chegam. Uma solução usa três semáforos: customers, que conta os clientes à espera de atendimento (exceto o cliente que está na cadeira de barbeiro, que não está esperando); barbers, o número de barbeiros (0 ou 1) que estão ociosos à espera de clientes, e mutex, que é usado para exclusão mútua. Precisamos ainda de uma variável, waiting, que também conta os clientes à espera de atendimento. É essencialmente uma cópia de customers. A razão de se ter waiting é que não há uma maneira de ler o valor atual do semáforo. Nessa solução, um cliente que entra na barbearia deve contar o número de clientes à espera de atendimento. Se este for menor que o número de cadeiras, ele ficará; do contrário, ele sairá. Nesta solução, quando chega de manhã para trabalhar, o barbeiro executa o método barber, que o leva a bloquear sobre o semáforo customers, que inicialmente está em 0. O barbeiro então vai dormir, e permanece dormindo até que o primeiro cliente apareça. Quando chega, o cliente executa customer e inicia obtendo mutex para entrar em uma região crítica. Se um outro cliente chega logo em seguida, o segundo nada pode fazer até que o primeiro libere o mutex. O cliente então verifica se o número de clientes à espera é menor que o número de cadeiras. Se não for, ele liberará o mutex e sairá sem cortar o cabelo. Se houver uma cadeira disponível, o cliente incrementará a variável inteira waiting. Ele faz então um up no semáforo customers, que acorda o barbeiro. Nesse ponto, o cliente e o barbeiro estão ambos acordados. Quando o cliente libera mutex, o barbeiro o pega, faz alguma limpeza e começa a cortar o cabelo. Quando termina o corte de cabelo, o cliente sai do procedimento e deixa a barbearia. Diferente de nossos exemplos anteriores, não há um laço para o cliente porque para cada um deles terá apenas um corte de cabelo. O barbeiro, contudo, contém um laço para tentar obter o próximo cliente. Se houver algum outro cliente, um novo corte de cabelo será iniciado. Do contrário, o barbeiro cairá no sono.
Código
Import threading
from time import sleep as sp
import random
#semáforos
customers = threading.semaphore(0) # mantém fila de clientes
barbers = threading.semaphore(0) # diz se o barbeiro está disponível ou não
mutex = threading.semaphore(1) # para exclusão mútua
#variáveis
sleep = 0 # diz se o barbeiro está dormindo ou não (1 - dormindo, 0 - acordado)
waiting = 0 #número de clientes esperando nos acentos
total = 0 # total de clientes presentes atualmente (incluindo quem está recebendo o corte)
waiting_list = [ ] # nome dos clientes esperando na fila
cust_getting_haircut = ‘ ’ # nome do cliente recebendo o corte
#funções
def barber ():
global total, waiting, sleep, waiting_list, cust_getting_haircut
while true:
print (“barbeiro esperando mais clientes, total de clientes
esperando:”, waiting, “\n”)
if (len(waiting_list) > 0): # se alguém estiver esperando
print (“clientes esperando são: ”, waiting_list)
if (waiting == 0 and total == 0): # se nenhum cliente estiver
presente, barbeiro dorme
print(“barbeiro dorme”)
sleep = 1
customers.acquire () # wait (customers)
mutex.acquire () # wait (mutex)
if (waiting > 0): # se o cliente estiver esperando
waiting -= 1 # decrementa número de clientes na fila
barbers.release () # signal (barber)
mutex.release() # signal (mutex)
sp (1) # espera por 1 segundo
cut_hair () # barbeiro vai cortar o cabelo
sp (4) # cortando por 4 segundos
print (f “barbeiro terminou o corte de {cust_getting_haircut}\n”)
if (len(wating_list) > 0 and cust_getting_haircut in waiting_list):
# remove o cliente
waiting_list.remove(cust_getting_haircut)
cust_getting_haircut = ‘ ’
total -= 1 # decrementa total
def customer(name):
global chairs, waiting, cust_getting_haircut, sleep, waiting_list, total
mutex.acquire() # wait (mutex)
if (waiting < chairs or total == 0):
if (total == 0):
total += 1 # incrementa total
print (f ‘cliente: {name} entrou na barbearia\n’)
else:
total += 1
waiting += 1 # incrementa número de clientes esperando
waiting_list.append(name) # adiciona nome do cliente na
lista de espera
print (f ‘cliente: {name} entrou na sala de espera, total
de clientes esperando :’, waiting, “\n”)
customers.release () # signal (customers)
mutex.release () # signal (mutex)
barbers.acquire () # wait (barber)
if (sleep == 1): # se o barbeiro estiver dormindo, ele acorda
print(f ‘cliente: {name} está acordando o barbeiro \n’)
sleep = 0 # barbeiro está acordado
cust_getting_haircut = name
get_hair_cut (name)
else: # se não houver mais acentos disponíveis
mutex.release () # signal (mutex)
balk (name) # deixar a loja
def get_hair_cut (name):
‘ ‘ ‘ Request for hair cut ’ ’ ’
print (f ‘Cliente: {name} chamou GET_HAIR_CUT\n’)
return
def cut_hair ():
‘ ‘ ‘ Cut the hair ’ ’ ’
print (f “Barbeiro cortando o cabelo de {cust_getting_haircut}\n”)
return
def balk (name):
‘ ‘ ‘ Leave the shop ’ ’ ’
print (f ‘Cliente: {name} está tentando entrar na sala de espera
\nloja cheia, chamada balk para {name} \n’)
#threads e outras variáveis
barber_thread = threading.Thread (name=“Barbeiro”, target=barber) # inicializa thread para o barbeiro
barber_thread.start() # começa a thread do barbeiro
custs = [ ‘Mr. a’, ‘Mr. b’, ‘Mr. c’, ‘Mr. d’, ‘Mr. e’, ‘Mr. f’, ‘Mr. g’, ‘Mr. h’ ]
cust_threads = [ ] # todas as threads de clientes
while true:
global chairs
if (len(cust_threads)): # se houverem threads em cust_threads
for t in cust_threads:
t.join () # executa os seguintes códigos somente quando
todas as threads de clientes terminam suas execuções
if (waiting == 0 and not (cust_getting_haircut)): # se nenhum cliente
estiver esperando ou recebendo corte
print (f ‘Cliente recebendo o corte: {cust_getting_haircut},
waiting_list: {waiting_list}’)
n_cust = int (input (“quantos clientes você quer?\n”)) # receber
entrada do número de clientes
chairs = int (input (“quantos acentos de espera você quer?\n”))
# receber entrada do número de clientes
if (n_cust > 11): # se o usuário quiser criar mais de 11 clientes
for i in range (12, n_cust +1): # cria mais exemplos de clientes
custs.append (f ‘Customer{i}’)
print (“gerando clientes...”)
for index, cust in enumerate (custs [:n_cust]):# para todos os
exemplos, inicializar e começar as threads
sp(1) # espera 1 segundo
customer_thread = threading.Thread (name = “Customer”,
target=customer, args=[f ‘ {cust} ({str(index +1)})’])
customer_thread.start()
cust_threads.append(customer_thread)
sp (random.randint (0,3)) # espera por um número aleatório
entre 0 e 3 segundos