Semáforo (computação)

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[1], em 1965 e foi utilizado inicialmente no sistema operacional THEOS.

Operações

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 zero, o processo é posto para dormir.
• Operação signal ou V: Se o semáforo estiver com o valor zero 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 a 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 verhogen (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).

Algoritmos

• Algoritmo de inicialização:

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

• Algoritmo de Incremento:

 V(Semáforo S){   //semáforo Signal
   Se(S != 0)
      S++;
   Senão
      desbloqueia_processo();
 }

• Algoritmo de decremento:

 P(Semáforo S){    //semáforo Wait
   Se(S == 0)
     bloqueia_processo();
   S--;
 }

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.

Referências

1. http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html E. W. Dijkstra, Cooperating sequential processes. Technological University, Eindhoven, The Netherlands, September 1965.

Ligações externas

• Artigo original de Dijkstra, em holandês
• (em inglês) The Little Book of Semaphores, de Allen B. Downey
• (em inglês) Biblioteca semaphore.h