Semáforo (computação)

Origem: Wikipédia, a enciclopédia livre.

Em ciência da computação, semáforo é uma variável especial protegida (ou tipo abstrato de dados) que tem como função o controle de acesso a recursos compartilhados (por exemplo, um espaço de armazenamento) num ambiente multitarefa. A invenção desse tipo de variável é atribuída a Edsger Dijkstra, em 1965 e foi utilizado inicialmente no sistema operacional THEOS.

[editar] Operações sobre semáforo

O valor de um semáforo indica quantos processos (ou threads) podem ter acesso a um recurso compartilhado. As principais operações sobre semáforos são:

Inicialização: Recebe um valor inteiro indicando a quantidade de processos que podem acessar um determinado recurso.
Operação wait ou P: Decrementa o valor do semáforo. Se o semáforo está com valor zerado, o processo é posto para dormir.
Operação signal ou V: Se o semáforo estiver com zerado e existir algum processo adormecido, um processo será acordado. Caso contrário, o valor do semáforo é incrementado.

As operações de incrementar e decrementar devem ser operações atômicas, ou indivisíveis, ou seja, enquanto um processo estiver executando uma dessas duas operações, nenhum outro processo pode executar outra operação sob o mesmo semáforo, devendo esperar que o primeiro processo encerre sua operação sob o semáforo. Essa obrigação evita condições de disputa entre vários processos

No trabalho original, Dijkstra utilizou as letras P e V para denominar as operações, advindas dos verbos holandeses proberen (testar), e verhoegen (incrementar). Em textos sobre computação, essas operações são denominadas por down e up, respectivamente. Em engenharia de Software, as denominações mais comuns são wait e signal, mas existe também as denominações take e release, ou pend e post.

Para evitar espera ocupada, que desperdiça processamento da máquina, a operação P utiliza uma estrutura de dados (geralmente uma FIFO). Quando um processo executa essa operação e o semáforo tem o seu valor zerado, este é posto na estrutura. Quando um outro processo executar a operação V e há processos na estrutura, uma delas é retirada (em uma FIFO, é a primeira que entrou).

[editar] Algoritmos

Algoritmo de inicialização:

Inicialização(Semáforo S, Inteiro N){
   S = N;
 }

Algoritmo de Incremento:

 V(Semáforo S){
   Se(S == 0 && existe_processo_bloqueado())
      desbloqueia_processo();
   Então
      S++;
 }

Algoritmo de decremento:

 P(Semáforo S){
   Se(S == 0)
     bloqueia_processo();
   Então
     S--;
 }

[editar] Utilização

A utilização mais simples do semáforo é em situações na qual necessita-se que haja exclusão mútua, isto é, que só um processo execute por vez. Para isso utiliza-se um semáforo binário, com inicialização em 1. Esse semáforo binário atua como um mutex.