Embedded Files
O problema dos fumantes de cigarro foi originalmente presentado por Suhas Patil, o qual alegou que não pode ser resolvido com semáforos. Essa alegação vem com algumas qualificações, mas em todo caso, o problema é interessante e desafiador.
Suhas Patil
Suhas Patil
Suhas S. Patil (nascido em 1944) é um empresário indiano-americano, acadêmico e capitalista de risco. Ele fundou a Cirrus Logic, uma empresa de semicondutores sem fábrica. O trabalho de Patil cobriu arquitetura de computador, computadores de processamento paralelo, dispositivos de integração de grande escala e software de automação de projeto de circuito integrado.
O problema clássico
O problema clássico
Neste problema, quatro threads são usadas: um fornecedor e três fumantes, Os fumantes ficam em um loop infinito, primeiro eles esperam pelos ingredientes, depois fazem o cigarro e por ultimo eles fumam o cigarro. os ingredientes são: tabaco, papel e fósforos.
Assumindo que o fornecedor tem um suprimento infinito dos 3 ingredientes e que cada um dos fumantes tem um suprimento infinito de um dos ingredientes. Sendo assim, um fumante tem o tabaco, o outro tem o papel e o ultimo tem o fosforo.
O fornecedor fica repetidamente escolhendo entre 2 ingredientes aleatórios e os torna disponíveis aos fumantes. Dependendo de quais ingredientes foram escolhidos, o fumante que tem o ingrediente que falta pega ambos os recursos e monta seu cigarro e o fuma. O fornecedor só poderá fornecer mais ingredientes quando fumante tiver terminado seu cigarro..
Por exemplo, se o agente colocar papel e fosforo, o fumante com o tabaco deve pegar ambos os recursos, fazer um cigarro e então sinalizar ao fornecedor.
para explicar a premissa, o fornecedor representa um sistema operacional que aloca recursos e os fumantes representam os aplicativos que precisam de recursos. O problema é ter certeza de que, se houver recursos disponíveis que permitam que mais um aplicativo prossiga, esse aplicativo deve ser ativado. Por outro lado, é desejado que um aplicativo não seja ativado caso ele não possa continuar.
Deadlock
Deadlock
Imagine que o fornecedor disponibilize o tabaco e o papel. Já que o fumante com os fósforos espera o tabaco, ele pode ser ativo. Mas o fumante que tem o tabaco espera o papel, então é possível (bem provável) que também seja ativo. Então a primeira thread bloqueará no papel e a segunda bloqueará no fósforo.
Uma solução simples para esse problema, seria implementar uma restrição. Para que somente o fumante com o ingrediente complementar possa pegar os outros dois ingredientes disponíveis.
Vídeo sobre o assunto
Implementação em Golang
package main
import (
"fmt"
"math/rand"
"sync"
"time"
)
//criação das constantes e variáveis
const (
paper = iota
grass
match
)
var smokeMap = map[int]string{
paper: "paper",
grass: "grass",
match: "match",
}
var names = map[int]string{
paper: "Sandy",
grass: "Apple",
match: "Daisy",
}
type Table struct {
paper chan int
grass chan int
match chan int
}
//função que descreve o fornecedor
func arbitrate(t *Table, smokers [3]chan int) {
for {
time.Sleep(time.Millisecond * 500)
next := rand.Intn(3)
fmt.Printf("Table chooses %s: %s\n", smokeMap[next], names[next])
switch next {
case paper:
t.grass <- 1
t.match <- 1
case grass:
t.paper <- 1
t.match <- 1
case match:
t.grass <- 1
t.paper <- 1
}
for _, smoker := range smokers {
smoker <- next
}
wg.Add(1)
wg.Wait()
}
}
//função que descreve os fumantes
func smoker(t *Table, name string, smokes int, signal chan int) {
var chosen = -1
for {
chosen = <-signal // blocks
if smokes != chosen {
continue
}
fmt.Printf("Table: %d grass: %d match: %d\n", len(t.paper), len(t.grass), len(t.match))
select {
case <-t.paper:
case <-t.grass:
case <-t.match:
}
fmt.Printf("Table: %d grass: %d match: %d\n", len(t.paper), len(t.grass), len(t.match))
time.Sleep(10 * time.Millisecond)
select {
case <-t.paper:
case <-t.grass:
case <-t.match:
}
fmt.Printf("Table: %d grass: %d match: %d\n", len(t.paper), len(t.grass), len(t.match))
fmt.Printf("%s smokes a cigarette\n", name)
time.Sleep(time.Millisecond * 500)
wg.Done()
time.Sleep(time.Millisecond * 100)
}
}
const LIMIT = 1
var wg *sync.WaitGroup
func main() {
wg = new(sync.WaitGroup)
table := new(Table)
table.match = make(chan int, LIMIT)
table.paper = make(chan int, LIMIT)
table.grass = make(chan int, LIMIT)
var signals [3]chan int
// three smokers
for i := 0; i < 3; i++ {
signal := make(chan int, 1)
signals[i] = signal
go smoker(table, names[i], i, signal)
}
fmt.Printf("%s, %s, %s, sit with \n%s, %s, %s\n\n", names[0], names[1], names[2], smokeMap[0], smokeMap[1], smokeMap[2])
arbitrate(table, signals)
}
Saida
Sandy, Apple, Daisy, sit with
paper, grass, match
Table chooses match: Daisy
Table: 1 grass: 1 match: 0
Table: 1 grass: 0 match: 0
Table: 0 grass: 0 match: 0
Daisy smokes a cigarette
Table chooses paper: Sandy
Table: 0 grass: 1 match: 1
Table: 0 grass: 1 match: 0
Table: 0 grass: 0 match: 0
Sandy smokes a cigarette
Table chooses match: Daisy
Table: 1 grass: 1 match: 0
Table: 1 grass: 0 match: 0
Table: 0 grass: 0 match: 0
Daisy smokes a cigarette
Page updated
Report abuse