Trabalho apresentado no Curso de Engenharia de Computação da Universidade Estadual de Ponta
Grossa,tendo como tema o problema
"O Barbeiro dorminhoco",
que se consiste em um problema de fila e como o barbeiro pode atender os seus clientes
Tendo como objetivo entender sobre o que se trata o problema e,
principalmente como seria a sua implementação na linguagem Java.
Professor: Dierone César Foltran Júnior
Alunos: Danilo Carneiro Christensen e Pedro Henrique Cebuliski
Na barbearia há um barbeiro, uma cadeira de barbeiro e n cadeiras para eventuais clientes esperarem a vez. Quando não há clientes, o barbeiro senta-se na cadeira de barbeiro e cai no sono. Quando chega um cliente, ele precisa acordar o barbeiro. Se outros clientes chegarem enquanto o barbeiro estiver cortando o cabelo de um cliente, eles se sentarão (se houver cadeiras vazias) ou sairão da barbearia (se todas as cadeiras estiverem ocupadas). 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.
//Nós vamos ter a classe Customer e Barber separadas, onde respectivamente, uma é responsável por fazer o serviço, e outra por esperar o serviço. public class Barber { // Procedimento para cortar o cabelo do cliente. public void cutHair() { System.out.println("Barber: Cutting Hair --- " + Thread.currentThread().getName()); } } public class Customer { // Procedimento para o cliente entrar no barbershop public void enter() { System.out.println("Customer: Enters the shop --- " + Thread.currentThread().getName()); } //Procedimento get que retorna o nome da thread que está sendo utilizada. public void getHairCut() { System.out.println("Customer: Getting Haircut --- " + Thread.currentThread().getName()); } // Procedimento que informa que o cliente saiu da barbershop, é mostrado a thread que foi utilizada. public void leave() { System.out.println("Customer: Leaves the shop --- " + Thread.currentThread().getName()); } }
// Essa classe é responsável pela coordenação e sincronismo entre o barbeiro e os clientes.
//Classe da barbearia
public class Barbershop {
private final int limit; // número de cadeiras de espera
public int customers; // Variavel armazena cliente
private final Barber barber; // variavel barber do tipo Barber
private final Semaphore customerReady; // Semáforo se o cliente está disponível
private final Semaphore barberReady; // Semáforo para saber se o barbeiro está disponível
private final Semaphore customerDone; //semáforo para informar que o cliente já teve cabelo cortado
private final Semaphore barberDone; // semáforo para informar que o barbeiro terminou
private final ReentrantLock mutex; // variável para exclusão mútua
public Barbershop(int limit) {
this.limit = limit; // define a quantidade de cadeiras de espera
customers = 0; // inicializa sem clientes
customerReady = new Semaphore(0); // Instancia um semáforo com o número de permissões
barberReady = new Semaphore(0);
customerDone = new Semaphore(0);
barberDone = new Semaphore(0);
mutex = new ReentrantLock();
barber = new Barber();
}
public Void startService() {
// começa o serviço
//espera um cliente chegar
try {
customerReady.acquire(); //semáforo customerReady recebe uma permissão e começa ser utilizado
} catch (InterruptedException e) {
System.out.println("Barber wait task is interrupted: " + e.getMessage());
}
// Informa q o barbeiro está pronto
barberReady.release(); // semáforo barberReady foi solto, barbeiro disponível
barber.cutHair(); // corta o cabelo do cliente
//espera até o terminar o corte de cabelo do cliente
try {
customerDone.acquire();
} catch (InterruptedException e) {
System.out.println("Barber wait task is interrupted: " + e.getMessage());
}
// Informa que o barbeiro já cortou o cabelo
barberDone.release();
System.out.println("Haircut is done");
return null;
}
// receber um novo cliente
public Void receiveNewCustomer() {
Customer customer = new Customer(); // instancia um cliente Customer
customer.enter(); //entra na fila
mutex.lock(); // utiliza o mutex
if (customers == limit) {// se a qtde de clientes == numero de cadeiras de espera
mutex.unlock(); // mutex é desbloqueado
customer.leave(); // o cliente vai embora
return null;
}
customers += 1; // nr de cliente é incrementado
mutex.unlock(); // mutex utilizado foi desbloqueado
customerReady.release(); // semáforo disponível
// espera o barbeiro ficar disponível
try {
barberReady.acquire();
} catch (InterruptedException e) {
System.out.println("Customer wait task is interrupted: " + e.getMessage());
}
// corta o cabelo do cliente
customer.getHairCut();
// terminou de cortar o cabelo do cliente
customerDone.release();
// espera o barbeiro terminar o corte
try {
barberDone.acquire();
} catch (InterruptedException e) {
System.out.println("Customer wait task is interrupted: " + e.getMessage());
}
mutex.lock(); //trava o mutex
customers -= 1; // cliente já cortou o cabelo e foi embora
mutex.unlock(); // desbloquea o mutex
return null;
}
}
//Na class Simulator que será realizado as operações com as threads.
public class Simulator {
private static final int NUM_ITERATION = 8; // numero de interações
public static void main(String[] args) {
ExecutorService executor = Executors.newWorkStealingPool(); //automaticamente configura as threads para executar as tarefas, de modo assincrono
Barbershop barbershop = new Barbershop(4); // instancia uma barbearia
Callable barbershopTask = barbershop::startService;
Callable receiveCustomerTask = barbershop::receiveNewCustomer;
List > barberFutures = new ArrayList<>(); // lista de tarefas do barbeiro
List > customerFutures = new ArrayList<>(); // lista de tarefas cliente
//Preenche as listas de tarefas do barbeiro e cliente.
for (int i=0; i barberFuture = executor.submit(barbershopTask);
barberFutures.add(barberFuture);
Future customerFuture = executor.submit(receiveCustomerTask);
customerFutures.add(customerFuture);
}
// Imprime as tarefas, uma por uma.
barberFutures.forEach(future -> {
try {
future.get(); //
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
});
customerFutures.forEach(future -> {
try {
future.get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
});
}
}
Customer: Enters the shop --- ForkJoinPool-1-worker-9 Customer: Enters the shop --- ForkJoinPool-1-worker-5 Customer: Enters the shop --- ForkJoinPool-1-worker-13 Customer: Enters the shop --- ForkJoinPool-1-worker-17 Barber: Cutting Hair --- ForkJoinPool-1-worker-27 Customer: Getting Haircut --- ForkJoinPool-1-worker-13 Barber: Cutting Hair --- ForkJoinPool-1-worker-3 Barber: Cutting Hair --- ForkJoinPool-1-worker-23 Customer: Getting Haircut --- ForkJoinPool-1-worker-17 Customer: Getting Haircut --- ForkJoinPool-1-worker-9 Barber: Cutting Hair --- ForkJoinPool-1-worker-19 Haircut is done Haircut is done Customer: Enters the shop --- ForkJoinPool-1-worker-25 Customer: Enters the shop --- ForkJoinPool-1-worker-21 Customer: Getting Haircut --- ForkJoinPool-1-worker-25 Customer: Getting Haircut --- ForkJoinPool-1-worker-21 Haircut is done Customer: Getting Haircut --- ForkJoinPool-1-worker-5 Haircut is done Barber: Cutting Hair --- ForkJoinPool-1-worker-7 Barber: Cutting Hair --- ForkJoinPool-1-worker-31 Customer: Enters the shop --- ForkJoinPool-1-worker-23 Customer: Enters the shop --- ForkJoinPool-1-worker-17 Customer: Getting Haircut --- ForkJoinPool-1-worker-23 Customer: Getting Haircut --- ForkJoinPool-1-worker-17 Barber: Cutting Hair --- ForkJoinPool-1-worker-13 Haircut is done Haircut is done Haircut is done Barber: Cutting Hair --- ForkJoinPool-1-worker-9 Haircut is done