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

↑ 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

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

[1]