Complexidade de Algoritmos

CENTRO UNIVERSITÁRIO CATARINENSE
CIÊNCIA DA COMPUTAÇÃO
SISTEMAS OPERACIONAIS
PROFESSOR MÁRCIO JOSÉ SEMBAY

SEMÁFOROS
JANTAR DOS FILÓSOFOS
BUFFER

MARINA MOTTA DA COSTA SILVA
LAGES- SC, ABRIL 2013
Semáforos
Em 1965, E.W. Dijkstra sugeriu o uso de uma variável inteira para contar o número de sinais armazenados para o uso futuro. Foi criado então um novo tipo de variável, o semáforo. Essa variável pode possuir valor 0, indicando que não há nenhum sinal armazenado, ou pode ter um valor positivo, indicando o número de sinais armazenados. Dijkstra estruturou sua ferramenta com duas operações, DOWN e UP (generalizações de SLEEP e WAKEUP, respectivamente). A operação DOWN executada sobre um semáforo verifica se o valor do semáforo é maior do que 0. Se for, seu valor é decrementado e o processo simplesmente continua sua progressão. Se o valor do semáforo for 0, o processo que executou a operação DOWN é posto para dormir. A verificação do valor do semáforo, a modificação de seu valor, e eventualmente a colocação do processo para dormir, são ações únicas, indivisíveis, denominadas ações atômicas. A implementação da ferramenta deve garantir que, uma vez que um processo inicie uma operação sobre um semáforo, nenhum outro processo terá acesso ao semáforo até que a operação se conclua. A atomicidade é absolutamente essencial para resolver os problemas de sincronização entre processos, evitando as condições de corrida. A operação UP incrementa o valor do semáforo. Se um ou mais processos estiverem dormindo neste semáforo, impedidos de completar uma operação DOWN, um deles vai ser escolhido pelo sistema (randomicamente, por exemplo), sendo-lhe então permitido completar a operação DOWN. Então, após um UP sobre um semáforo (binário) com processos dormindo, o semáforo permanecerá em 0, porém haverá menos um processo dormindo ao associado ao tal semáforo. A operação de incrementar o semáforo e acordar um processo é também