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
[editar | editar código-fonte]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
[editar | editar código-fonte]- 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
[editar | editar código-fonte]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
[editar | editar código-fonte]- ↑ http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html E. W. Dijkstra, Cooperating sequential processes. Technological University, Eindhoven, The Netherlands, September 1965.