O que é um semáforo?

Um semáforo é um conceito de programação usado com freqüência para resolver problemas de multiencadeamento. Minha pergunta para a comunidade:

O que é um semáforo e como você o usa?

Pense nos semáforos como seguranças de uma boate. Há um número dedicado de pessoas que são permitidas no clube de uma só vez. Se o clube estiver cheio, ninguém poderá entrar, mas assim que uma pessoa sair, outra pessoa poderá entrar.

É simplesmente uma maneira de limitar o número de consumidores para um recurso específico. Por exemplo, para limitar o número de chamadas simultâneas para um banco de dados em um aplicativo.

Aqui está um exemplo muito pedagógico em C # :-)

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace TheNightclub
{
    public class Program
    {
        public static Semaphore Bouncer { get; set; }

        public static void Main(string[] args)
        {
            // Create the semaphore with 3 slots, where 3 are available.
            Bouncer = new Semaphore(3, 3);

            // Open the nightclub.
            OpenNightclub();
        }

        public static void OpenNightclub()
        {
            for (int i = 1; i <= 50; i++)
            {
                // Let each guest enter on an own thread.
                Thread thread = new Thread(new ParameterizedThreadStart(Guest));
                thread.Start(i);
            }
        }

        public static void Guest(object args)
        {
            // Wait to enter the nightclub (a semaphore to be released).
            Console.WriteLine("Guest {0} is waiting to entering nightclub.", args);
            Bouncer.WaitOne();          

            // Do some dancing.
            Console.WriteLine("Guest {0} is doing some dancing.", args);
            Thread.Sleep(500);

            // Let one guest out (release one semaphore).
            Console.WriteLine("Guest {0} is leaving the nightclub.", args);
            Bouncer.Release(1);
        }
    }
}

O artigo Mutexes e semáforos desmistificados por Michael Barr é uma excelente introdução ao que diferencia mutexes e semáforos, e quando eles devem e não devem ser usados. Trecho de vários parágrafos-chave aqui.

O ponto principal é que mutexes devem ser usados ​​para proteger recursos compartilhados, enquanto semáforos devem ser usados ​​para sinalização. Geralmente, você não deve usar semáforos para proteger recursos compartilhados, nem mutexes para sinalização. Há problemas, por exemplo, com a analogia do segurança em termos de uso de semáforos para proteger recursos compartilhados - você pode usá-los dessa maneira, mas pode dificultar o diagnóstico de bugs.

Embora os mutexes e semáforos tenham algumas semelhanças em sua implementação, eles sempre devem ser usados ​​de maneira diferente.

A resposta mais comum (mas mesmo assim incorreta) à pergunta colocada no topo é que os mutexes e semáforos são muito semelhantes, com a única diferença significativa: os semáforos podem contar mais que um. Quase todos os engenheiros parecem entender corretamente que um mutex é um sinalizador binário usado para proteger um recurso compartilhado, garantindo exclusão mútua em seções críticas do código. Mas, quando solicitados a expandir sobre como usar um "semáforo de contagem", a maioria dos engenheiros - variando apenas em seu grau de confiança - expressa algum sabor da opinião do livro didático de que estes são usados ​​para proteger vários recursos equivalentes.

...

Nesse ponto, uma analogia interessante é feita usando a idéia de chaves do banheiro como proteção de recursos compartilhados - o banheiro. Se uma loja tiver um único banheiro, uma única chave será suficiente para proteger esse recurso e impedir que várias pessoas o usem simultaneamente.

Se houver vários banheiros, pode-se ficar tentado a digitá-los da mesma maneira e criar várias chaves - isso é semelhante a um semáforo sendo mal utilizado. Quando você tem uma chave, na verdade não sabe qual banheiro está disponível, e se você seguir esse caminho, provavelmente acabará usando mutexes para fornecer essas informações e garantir que não toma um banheiro já ocupado .

Um semáforo é a ferramenta errada para proteger vários dos mesmos recursos, mas é quantas pessoas pensam e o usam. A analogia do segurança é distintamente diferente - não há vários do mesmo tipo de recurso; em vez disso, existe um recurso que pode aceitar vários usuários simultâneos. Suponho que um semáforo possa ser usado nessas situações, mas raramente existem situações do mundo real em que a analogia realmente se mantém - é mais frequente que existam vários do mesmo tipo, mas ainda recursos individuais, como os banheiros, que não podem ser usados por aqui.

...

O uso correto de um semáforo é para sinalizar de uma tarefa para outra. Um mutex deve ser obtido e liberado, sempre nessa ordem, por cada tarefa que usa o recurso compartilhado que protege. Por outro lado, as tarefas que usam semáforos sinalizam ou esperam - não as duas. Por exemplo, a Tarefa 1 pode conter código para postar (ou seja, sinal ou incremento) um semáforo específico quando o botão "power" é pressionado e a Tarefa 2, que ativa a tela, fica pendente no mesmo semáforo. Nesse cenário, uma tarefa é a produtora do sinal de evento; o outro o consumidor.

...

Aqui, é importante ressaltar que os mutexes interferem de maneira ruim nos sistemas operacionais em tempo real, causando inversão de prioridade, onde uma tarefa menos importante pode ser executada antes de uma tarefa mais importante por causa do compartilhamento de recursos. Em resumo, isso acontece quando uma tarefa de prioridade mais baixa usa um mutex para capturar um recurso, A, e tenta capturar B, mas é interrompida porque B não está disponível. Enquanto espera, uma tarefa de maior prioridade surge e precisa de A, mas já está vinculada e por um processo que nem está em execução porque está aguardando B. Há muitas maneiras de resolver isso, mas na maioria das vezes é corrigido alterando o mutex e o gerenciador de tarefas. O mutex é muito mais complexo nesses casos do que um semáforo binário,

...

A causa da confusão moderna e difundida entre mutexes e semáforos é histórica, pois remonta à invenção de 1974 do Semaphore (capital "S", neste artigo) de Djikstra. Antes dessa data, nenhum dos mecanismos de sincronização e sinalização de tarefas com segurança contra interrupções, conhecidos pelos cientistas da computação, era escalonável com eficiência para uso em mais de duas tarefas. O semáforo revolucionário, seguro e escalonável da Dijkstra foi aplicado tanto na proteção de seção crítica quanto na sinalização. E assim começou a confusão.

No entanto, mais tarde ficou óbvio para os desenvolvedores de sistemas operacionais, após o surgimento do RTOS preemptivo baseado em prioridades (por exemplo, VRTX, ca. 1980), publicação de trabalhos acadêmicos que estabelecem a RMA e os problemas causados ​​pela inversão de prioridades, e um artigo sobre prioridade protocolos de herança em 1990, 3 tornou-se aparente que os mutexes devem ser mais do que apenas semáforos com um contador binário.

Mutex: compartilhamento de recursos

Semáforo: sinalização

Não use um para o outro sem considerar cuidadosamente os efeitos colaterais.

Mutex: acesso de membro exclusivo a um recurso

Semáforo: acesso de n membros a um recurso

Ou seja, um mutex pode ser usado para sincronizar o acesso a um contador, arquivo, banco de dados, etc.

Um sempahore pode fazer a mesma coisa, mas suporta um número fixo de chamadas simultâneas. Por exemplo, posso agrupar minhas chamadas de banco de dados em um semáforo (3) para que meu aplicativo multithread chegue ao banco de dados com no máximo três conexões simultâneas. Todas as tentativas serão bloqueadas até que um dos três slots seja aberto. Eles fazem coisas como fazer uma otimização ingênua muito, muito fácil.

Considere um táxi que pode acomodar um total de 3 pessoas ( traseira ) +2 ( dianteira ), incluindo o motorista. Portanto, a semaphorepermite apenas 5 pessoas dentro de um carro por vez. E um mutexpermite apenas 1 pessoa em um único assento do carro.

Portanto, Mutexé permitir acesso exclusivo a um recurso ( como um encadeamento do SO ) enquanto a Semaphoreé permitir acesso a um número n de recursos por vez.

@Craig:

Um semáforo é uma maneira de bloquear um recurso para garantir que, enquanto um pedaço de código é executado, apenas esse pedaço de código tenha acesso a esse recurso. Isso evita que dois threads acessem simultaneamente um recurso, o que pode causar problemas.

Isso não está restrito a apenas um segmento. Um semáforo pode ser configurado para permitir que um número fixo de threads acesse um recurso.

O semáforo também pode ser usado como ... semáforo. Por exemplo, se você tiver vários dados de enfileiramento de processos em uma fila e apenas uma tarefa consumindo dados da fila. Se você não deseja que sua tarefa consumidora pesquise constantemente na fila os dados disponíveis, use o semáforo.

Aqui o semáforo não é usado como um mecanismo de exclusão, mas como um mecanismo de sinalização. A tarefa de consumo está aguardando no semáforo. A tarefa de produção está lançando no semáforo.

Dessa forma, a tarefa consumidora é executada quando e somente quando há dados a serem desenfileirados

Existem dois conceitos essenciais para a criação de programas concorrentes - sincronização e exclusão mútua. Veremos como esses dois tipos de bloqueios (semáforos são geralmente um tipo de mecanismo de bloqueio) nos ajudam a obter sincronização e exclusão mútua.

Um semáforo é uma construção de programação que nos ajuda a obter simultaneidade, implementando a sincronização e a exclusão mútua. Os semáforos são de dois tipos, Binário e Contagem.

Um semáforo tem duas partes: um contador e uma lista de tarefas aguardando para acessar um recurso específico. Um semáforo executa duas operações: aguarde (P) [é como adquirir um bloqueio] e libere (V) [semelhante à liberação de um bloqueio] - essas são as únicas duas operações que se pode executar em um semáforo. Em um semáforo binário, o contador logicamente varia entre 0 e 1. Você pode pensar nele como sendo semelhante a um bloqueio com dois valores: aberto / fechado. Um semáforo de contagem possui vários valores para contagem.

O que é importante entender é que o contador de semáforo controla o número de tarefas que não precisam ser bloqueadas, ou seja, elas podem progredir. As tarefas são bloqueadas e adicionadas à lista de semáforos somente quando o contador é zero. Portanto, uma tarefa é adicionada à lista na rotina P () se não puder progredir e "liberada" usando a rotina V ().

Agora, é bastante óbvio ver como os semáforos binários podem ser usados ​​para resolver a sincronização e exclusão mútua - eles são essencialmente bloqueios.

ex. Sincronização:

thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}

//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}

main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}

No exemplo acima, B2 só pode ser executado após a conclusão de B1. Digamos que o encadeamento A seja executado primeiro - chegue a sem.P () e aguarde, pois o contador é 0 (fechado). O segmento B aparece, termina B1 e libera o segmento A - que completa B2. Então, alcançamos a sincronização.

Agora, vamos examinar a exclusão mútua com um semáforo binário:

thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...

}

main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}

A exclusão mútua também é bastante simples - m1 e m2 não podem entrar na seção crítica ao mesmo tempo. Portanto, cada thread está usando o mesmo semáforo para fornecer exclusão mútua para suas duas seções críticas. Agora, é possível ter maior concorrência? Depende das seções críticas. (Pense em como mais alguém poderia usar semáforos para obter exclusão mútua. Dica dica: preciso necessariamente usar apenas um semáforo?)

Semáforo de contagem: um semáforo com mais de um valor. Vejamos o que isso implica - um bloqueio com mais de um valor? Tão aberto, fechado e ... hmm. De que uso um bloqueio de vários estágios na exclusão ou sincronização mútua?

Vamos pegar o mais fácil dos dois:

Sincronização usando um semáforo de contagem: Digamos que você tenha 3 tarefas - nº 1 e 2 que deseja executar após 3. Como você projetaria sua sincronização?

thread t1{
...
s.P();
//block of code B1

thread t2{
...
s.P();
//block of code B2

thread t3{
...
//block of code B3
s.V();
s.V();
}

Portanto, se o seu semáforo começar fechado, você garante que o bloco t1 e t2 seja adicionado à lista do semáforo. Então, vem toda a T3 importante, encerra seus negócios e libera T1 e T2. Em que ordem eles são libertados? Depende da implementação da lista do semáforo. Pode ser FIFO, pode ser baseada em alguma prioridade particular, etc. (Nota: pense em como você organizaria seus P e V; s se você desejasse que t1 e t2 fossem executados em alguma ordem específica e se não estivesse ciente da implementação do semáforo)

(Descubra: O que acontece se o número de V's for maior que o número de P's?)

Exclusão mútua Usando semáforos de contagem: eu gostaria que você construísse seu próprio pseudocódigo para isso (faz você entender melhor as coisas!) - mas o conceito fundamental é este: um semáforo de contagem de counter = N permite que N tarefas entrem livremente na seção crítica . O que isso significa é que você tem N tarefas (ou threads, se quiser) entram na seção crítica, mas a N + 1ª tarefa é bloqueada (entra na nossa lista de tarefas bloqueadas favoritas) e só é liberada quando alguém V é o semáforo pelo menos uma vez. Assim, o contador de semáforo, em vez de balançar entre 0 e 1, agora passa entre 0 e N, permitindo que N tarefas entrem e saiam livremente, bloqueando ninguém!

Agora, caramba, por que você precisaria de uma coisa tão estúpida? Não é o ponto de exclusão mútua não permitir que mais de um indivíduo acesse um recurso? (Dica Dica ... Você nem sempre tem apenas uma unidade no seu computador, tem ...?)

Pensar : a exclusão mútua é alcançada por ter um semáforo de contagem sozinho? E se você tiver 10 instâncias de um recurso e 10 threads (através do semáforo de contagem) e tentar usar a primeira instância?

Um semáforo é um objeto que contém um número natural (ou seja, um número inteiro maior ou igual a zero) no qual duas operações de modificação são definidas. Uma operação, Vadiciona 1 ao natural. A outra operação, Pdiminui o número natural em 1. Ambas as atividades são atômicas (ou seja, nenhuma outra operação pode ser executada ao mesmo tempo que uma Vou outra).P ).

Como o número natural 0 não pode ser diminuído, a chamada Pde um semáforo contendo um 0 bloqueará a execução do processo de chamada (/ thread) até algum momento em que o número não seja mais 0 eP possa ser executado com êxito (e atomicamente).

Conforme mencionado em outras respostas, os semáforos podem ser usados ​​para restringir o acesso a um determinado recurso a um número máximo (mas variável) de processos.

Eu criei a visualização que deve ajudar a entender a ideia. O semáforo controla o acesso a um recurso comum em um ambiente multithreading.

ExecutorService executor = Executors.newFixedThreadPool(7);

Semaphore semaphore = new Semaphore(4);

Runnable longRunningTask = () -> {
    boolean permit = false;
    try {
        permit = semaphore.tryAcquire(1, TimeUnit.SECONDS);
        if (permit) {
            System.out.println("Semaphore acquired");
            Thread.sleep(5);
        } else {
            System.out.println("Could not acquire semaphore");
        }
    } catch (InterruptedException e) {
        throw new IllegalStateException(e);
    } finally {
        if (permit) {
            semaphore.release();
        }
    }
};

// execute tasks
for (int j = 0; j < 10; j++) {
    executor.submit(longRunningTask);
}
executor.shutdown();

Resultado

Semaphore acquired
Semaphore acquired
Semaphore acquired
Semaphore acquired
Could not acquire semaphore
Could not acquire semaphore
Could not acquire semaphore

Código de exemplo do artigo

Um sinalizador de hardware ou software. Em sistemas multitarefa, um semáforo é uma variável com um valor que indica o status de um recurso comum. Um processo que precisa do recurso verifica o semáforo para determinar o status dos recursos e decide como proceder.

Os semáforos agem como limitadores de rosca.

Exemplo: se você possui um pool de 100 threads e deseja executar alguma operação de banco de dados. Se 100 threads acessarem o banco de dados em um determinado momento, pode haver um problema de bloqueio no banco de dados, para que possamos usar o semáforo que permite apenas threads limitados por vez. O exemplo abaixo permite apenas um thread por vez. Quando um thread chama o acquire()método, ele obtém o acesso e, após chamar o release()método, libera o acesso para que o próximo thread obtenha o acesso.

    package practice;
    import java.util.concurrent.Semaphore;

    public class SemaphoreExample {
        public static void main(String[] args) {
            Semaphore s = new Semaphore(1);
            semaphoreTask s1 = new semaphoreTask(s);
            semaphoreTask s2 = new semaphoreTask(s);
            semaphoreTask s3 = new semaphoreTask(s);
            semaphoreTask s4 = new semaphoreTask(s);
            semaphoreTask s5 = new semaphoreTask(s);
            s1.start();
            s2.start();
            s3.start();
            s4.start();
            s5.start();
        }
    }

    class semaphoreTask extends Thread {
        Semaphore s;
        public semaphoreTask(Semaphore s) {
            this.s = s;
        }
        @Override
        public void run() {
            try {
                s.acquire();
                Thread.sleep(1000);
                System.out.println(Thread.currentThread().getName()+" Going to perform some operation");
                s.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        } 
    }

Imagine que todo mundo está tentando ir ao banheiro e há apenas um certo número de chaves no banheiro. Agora, se não houver chaves suficientes, essa pessoa precisa esperar. Então, pense no semáforo como representando o conjunto de chaves disponíveis para banheiros (os recursos do sistema) aos quais diferentes processos (frequentadores de banheiros) podem solicitar acesso.

Agora imagine dois processos tentando ir ao banheiro ao mesmo tempo. Essa não é uma boa situação e semáforos são usados ​​para evitar isso. Infelizmente, o semáforo é um mecanismo voluntário e os processos (nossos frequentadores do banheiro) podem ignorá-lo (ou seja, mesmo que haja chaves, alguém ainda pode simplesmente abrir a porta).

Também existem diferenças entre os semáforos binários / mutex e de contagem.

Confira as notas da aula em http://www.cs.columbia.edu/~jae/4118/lect/L05-ipc.html .

Esta é uma pergunta antiga, mas um dos usos mais interessantes do semáforo é um bloqueio de leitura / gravação e não foi mencionado explicitamente.

Os bloqueios r / w funcionam de maneira simples: consuma uma permissão para um leitor e todas as permissões para escritores. De fato, uma implementação trivial de ar / w lock, mas requer modificação de metadados na leitura (na verdade duas vezes) que pode se tornar um gargalo, ainda significativamente melhor do que um mutex ou bloqueio.

Outra desvantagem é que os escritores também podem ser iniciados com bastante facilidade, a menos que o semáforo seja justo ou que as gravações obtenham permissões em várias solicitações; nesse caso, eles precisam de um mutex explícito entre si.

Leia mais :

Um semáforo é uma maneira de bloquear um recurso para garantir que, enquanto um pedaço de código é executado, apenas esse pedaço de código tenha acesso a esse recurso. Isso evita que dois threads acessem simultaneamente um recurso, o que pode causar problemas.