Semáforos
Eduardo Nicola F. Zagari
Principles of Concurrent and
Distributed Programming - Ben-Ari
Tópicos
•
•
•
•
•
•
•
•
Introdução
Invariâncias
Exclusão Mútua
Definições de Semáforos
O Problema do Produtor Consumidor
Buffers Infinitos
Buffers Limitados
Produtor Consumidor com Semáforos Binários
Introdução
•
Soluções anteriores usam apenas
diretivas providas pela máquinas.
– Muito baixo nível para ser eficiente e
confiável
•
Semáforo é uma solução em nível mais
alto
– Implementados no sistema operacional
Introdução
• Semáforo é uma variável inteira não
negativa. São definidas apenas 2
operações num semáforo S:
– P(S) ou Down(S): Se S > 0 então S := S – 1,
senão suspende a execução deste processo.
– V(S) ou Up(S): Se existem processos
suspensos neste semáforo, acorda um deles,
senão S := S + 1.
Introdução
•
O semáforo tem as seguintes
propriedades:
1. P(S) e V(S) são atômicas
2. A todo semáforo deve ser atribuído um valor
inicial não negativo (semáforos gerais
versus semáforos binários)
3. A operação V(S) deve acordar um dos
processos suspensos (a definição não
especifica qual!)
Invariâncias
• Um semáforo satisfaz as seguintes
invariâncias:
S >= 0
S = S0 + #V(S) - #P(S)
Exclusão Mútua
S: Semaforo := 1;
task body P1 is
begin
loop
Regiao_Nao_Critica_1;
P(S);
Regiao_Critica_1;
V(S);
end loop;
end P1;
task body P2 is
begin
loop
Regiao_Nao_Critica_2;
P(S);
Regiao_Critica_2;
V(S);
end loop;
end P2;
Exclusão Mútua
• Note que:
– A propriedade de exclusão mútua é satisfeita;
– O programa não sofre deadlock;
– Não há starvation.
• Similar à segunda tentativa do capítulo anterior,
exceto pela atomicidade do pré e pósprotocolos.
• Difere da instrução Test-and-Set pelo fato de
que um processo suspenso num semáforo não
executa instruções checando valor de variáveis
provocando espera ocupada (busy-waiting).
Definições de Semáforos
• Semáforo Blocked-set: Um processo que faz a operação
“V” ( ou Up) acorda um dos processos suspensos.
– P(S): Se S > 0, então S := S - 1, senão suspende a execução
deste processo.
– V(S): Se há processos que estão suspensos neste semáforo,
acorde um deles, senão S := S + 1.
• Semáforo Blocked-queue: Os processos suspensos são
mantidos em uma fila FIFO e acordados na mesma
ordem em que foram suspensos.
– P(S): Se S > 0, então S := S - 1, senão suspende a execução
deste processo. Ele é adicionado no fim da fila FIFO.
– V(S): Se há processos que estão suspensos neste semáforo,
acorde o processo do início da fila, senão S := S + 1.
Definições de Semáforos
• Semáforo Busy-wait: o valor de S é testado em um laço
de espera ocupada. O comando if inteiro é executado
como uma operação atômica, mas pode haver
intercalamento entre ciclos do laço.
– P(S):
loop
if S > 0 then S := S - 1; exit; end if;
end loop;
– V(S):
S := S + 1;
Teoremas
• Teo 1: Para um semáforo busy-wait, é
possível starvation.
– Considere a seguinte seqüência de
execução:
• P1 executa P(S) e entra em sua seção crítica
• P2 encontra S = 0 e entra no laço
• P1 completa um ciclo inteiro consistindo do pósprotocolo, seção não crítica, pré-protocolo e entra
novamente em sua seção crítica
Teoremas
• Teo 2: Para um semáforo blocked-queue
não é possível a ocorrência de starvation.
• Teo 3: Para um semáforo blocked-set, é
possível a ocorrência de starvation para
N >= 3.
O Problema do ProdutorConsumidor
• Produtores: estes processos criam um
elemento de dados que deve ser enviado
para os consumidores.
• Consumidores: Ao receber um elemento
de dados, estes processos realizam algum
processamento
• Solução elementar: comunicação síncrona
• Solução mais flexível: introdução de buffer
Buffer Infinito
B: array(0..infinity) of Integer;
In_Ptr, Out_Ptr: Integer := 0;
task body Producer is
I: Integer;
begin
loop
Produce(I);
B(In_Ptr) := I;
In_Ptr := In_Ptr + 1;
end loop;
end Producer;
task body Consumer is
I: Integer;
begin
loop
Wait until In_Ptr > Out_Ptr;
I := B(Out_Ptr);
Out_Ptr := Out_Ptr + 1;
Consume(I);
end loop;
end Consumer;
...
Out_Ptr
In_Ptr
Buffer Infinito
B: array(0..infinity) of Integer;
In_Ptr, Out_Ptr: Integer := 0;
Elements: Semaphore := 0;
task body Producer is
I: Integer;
begin
loop
Produce(I);
B(In_Ptr) := I;
In_Ptr := In_Ptr + 1;
Up(Elements);
end loop;
end Producer;
task body Consumer is
I: Integer;
begin
loop
Down(Elements);
I := B(Out_Ptr);
Out_Ptr := Out_Ptr + 1;
Consume(I);
end loop;
end Consumer;
Buffer Finito
• Buffer circular:
...
Out_Ptr
In_Ptr
...
In_Ptr
Out_Ptr
• Pool de buffers:
In_Ptr
Pool
Out_Ptr
Consumer
Producer
Buffer Circular Finito
B: array(0..N-1) of Integer;
In_Ptr, Out_Ptr: Integer := 0;
Elements: Semaphore := 0;
Spaces: Semaphore := N;
task body Producer is
I: Integer;
begin
loop
Produce(I);
Down(Spaces);
B(In_Ptr) := I;
In_Ptr := (In_Ptr+1) mod N;
Up(Elements);
end loop;
end Producer;
task body Consumer is
I: Integer;
begin
loop
Down(Elements);
I := B(Out_Ptr);
Out_Ptr := (Out_Ptr+1) mod N;
Up(Spaces);
Consume(I);
end loop;
end Consumer;
Considerações
• O programa nunca remove um elemento
de um buffer vazio nem insere elementos
em um buffer cheio
• O programa nunca provoca deadlock
• Nunca há starvation em nenhum dos
processos
Produtor Consumidor com Semáforos Binários
B: array(0..N-1) of Integer;
In_Ptr, Out_Ptr, Count: Integer := 0;
S: Binary_Semaphore := 1;
Not_Empty, Not_Full: Binary_Semaphore := 0;
task body Producer is
I: Integer;
Local_Count: Integer := 0;
begin
loop
Produce(I);
if Local_Count = N then
Down(Not_Full); end if;
B(In_Ptr) := I;
Down(S);
Count := Count + 1;
Local_Count := Count;
Up(S);
if Local_Count = 1 then
Up(Not_Empty); end if;
In_Ptr := (In_Ptr+1) mod N;
end loop;
end Producer;
task body Consumer is
I: Integer;
Local_Count: Integer := 0;
begin
loop
if Local_Count = 0 then
Down(Not_Empty); end if;
I := B(Out_Ptr);
Down(S);
Count := Count - 1;
Local_Count := Count;
Up(S);
if Local_Count = N-1 then
Up(Not_Full); end if;
Out_Ptr := (Out_Ptr+1) mod N;
Consume(I);
end loop;
end Consumer;
Apêndice
• Tópico “avançado” em definição de
semáforo...
Definições de Semáforos
• Semáforo Strongly-fair: Se o semáforo faz a operação
“V” (ou Up) com freqüência infinita, todo processo
suspenso completará a instrução do semáforo.
• Semáforo Weakly-fair: Se o semáforo é mantido em um
valor maior que zero, todo processo suspenso
completará a instrução do semáforo.
Definições de Semáforos
• As definições dos tipos blocked-set,
blocked-queue e busy-wait dizem respeito
à forma como os semáforos são
implementados. Já os strong e weak são
definidos em termos de seu
comportamento abstrato.
– Um semáforo busy-wait é uma
implementação de um semáforo fraco
– Já o semáforo blocked-queue é um semáforo
forte