Semáforo (computação)
 |
Você está visualizando uma edição arquivada desta página, feita por Luís Felipe Braga (discussão | contribs) em 22h50min de 10 de julho de 2007. Esta edição pode ser muito diferente da versão atual da página. O endereço URL mostrado no navegador é uma ligação permanente para esta edição. Para mais informações, consulte a página de ajuda sobre histórico de edições. |
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.
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).
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--;
}
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.