Implementação de Sincronização

Protocolos que usam busy waiting:
 Difíceis de projetar, compreender e provar
corretos
 Complexos
 Variáveis usadas para sincronizar são
idênticas às outras variáveis do programa
 ineficientes
Solução

usar ferramentas especiais para ajudar
a projetar protocolos de sincronização
corretos, e bloqueiam processos em
espera.
Semáforos





Foi uma das primeiras “ferramentas”
Uma das mais importantes
Torna fácil proteger regiões críticas
Pode ser usado de forma disciplinada para
implementar sincronização de condição
Podem ser implementados com busy-waiting
ou interagir com o escalonador de processos
para obter sincronização sem busy-waiting
Semáforo

Tipo abstrato de dados, com duas
operações:
 P(S)
Também chamada de wait
Atrasa um processo até que um evento ocorra.
 V(S)
Também chamado de signal
Sinaliza a ocorrencia de um evento
Invariante do Semáforo


Para um semáforo s, seja nP o número
de operações P completadas e nV o
número de operações V completadas.
Se init é o valor inicial de s, então, em
todos os estados visíveis, nP  nV + init
Execução de operações P esperam até
que um número adequado de
operações V tenha ocorrido
Representação de um Semáforo



Número não negativo
s = init + nV – nP
Invariante: s  0
Representação de um Semáforo
 P (s)
 <await (s > 0) -> s := s – 1>
 V (s)
 <s := s + 1>
Tipos de Semáforos

Semáforo genérico
 assume valores não negativos

Semáforo binário
 assume apenas valores 0 ou 1
Região Crítica

sem_t S = 1;
void Pi {
while (TRUE) {
Non_Cr_S_i;
P(S);
Critical_S_i;
V(S);
}
}
A propriedade de exclusão mútua
é satisfeita


#CS é o número de processos em sua
região crítica
provar que #CS + S = 1





#CS = nP(S) - nV(S)
S = 1 + nV(S) - nP(S)
S = 1 - #CS
#CS + S = 1
como S >= 0, então #CS <= 1
O programa não entra em
deadlock



os processos teriam que estar
suspensos em P(S)
teríamos S = 0 e #CS = 0
mas já mostramos que #CS + S = 1
contradição
não há starvation



Se P1 está suspenso, o semáforo deve
ter 0
Pelo invariante do semáforo, P2 está na
região crítica
Quando P2 sai da região crítica,
executa V(S), que acorda um processo
(P1)
Definições de semáforos

Blocked-set semaphore
 um sinal acorda um dos processos
suspensos

Blocked-queue semaphore
 os processos suspensos são mantidos em
uma fila FIFO e são acordados na mesma
ordem em que foram suspensos
Definições de semáforos

Busy-wait semaphore
 processos ficam testando o valor de S em
um loop de busy-wait. O teste é atômico.
Definições de semáforos

Strongly-fair semaphore
 se o semáforo é sinalizado infinatamente
frequente, em algum momento todos os
processos esperando serão acordados.

Weakly-fair semaphore
 se o semáforo é mantido com um valor
maior que zero, em algum momento todos
os processos esperando serão atendidos.
Provas

em um semáforo de busy-wait, pode
ocorrer starvation
 P1 executa P(S) e entra na região crítica
 P2 encontra S = 0 e fica no loop
 P1 executa todo um ciclo, e reentra na
região crítica
 P2 encontra S = 0 e fica no loop
Provas

em um semáforo blocked-queue, é
impossível ocorrer starvation
 suponha P1 bloqueado em S
 então existem no máximo N - 1 processos
na frente de P1 na fila para S
Provas

em um semáforo blocked-set, é
possível ocorrer starvation para N >= 3
 como não há garantia de qual processo
será acordado, se houverem pelo menos 2
processos bloqueados, um deles pode ser
sempre o escolhido.
Barreiras

sem_t barrier1 = 0;
sem_t barrier2 = 0;
void P2 {
void P1 {
while (TRUE) {
while (TRUE) {
...;
...;
V(barrier2);
V(barrier1);
P(barrier1);
P(barrier2);
}
}
}
}
Problema do ProdutorConsumidor


Problema de comunicação
Produtores
 geram dados com o procedimento
Produce, que devem ser enviados aos
consumidores

Consumidores
 ao receberem um dado fazem alguma
computação, com o procedimento
Consume
Buffer de tamanho 1

int B;
sem_t empty = 1;
sem_t full = 0;
void Producer {
int m;
while (TRUE) {
Produce(m);
P(empty);
B = m;
V(full);
}
}
void Consumer {
int m;
while (TRUE) {
P(full);
m = B;
V(empty);
Consume(m);
}
}
Buffer limitado (circular)

int B[n]; int front = 0; int rear = 0;
sem_t empty = n;
sem_t full = 0;
void Consumer {
void Producer {
int m;
int m;
while (TRUE) {
while (TRUE) {
P(full);
Produce(m);
m = B[front];
P(empty);
B[rear] = m;
front = (front + 1) % n
rear = (rear + 1) % n V(empty);
V(full);
Consume(m);
}
}
}
}
Buffer limitado – com vários
produtores e consumidores

int B[n]; int front = 0; int rear = 0;
sem_t empty = n; sem_t full = 0;
sem_t mutexD = 0; sem_t mutexF = 0;
void Consumer {
void Producer {
int m;
int m;
while (TRUE) {
while (TRUE) {
P(full); P(mutexF);
Produce(m);
m = B[front];
P(empty); P(mutexD); front = (front + 1) % n
B[rear] = m;
V(mutexF); V(empty);
rear = (rear + 1) % n Consume(m);
V(mutexD); V(full);
}
}
}
}
Exclusão mútua seletiva

Jantar dos filósofos
 Processos competem por acesso a
conjuntos sobrepostos de variáveis
compartilhadas

Leitores e Escritores
 Combinação de acesso concorrente e
exclusivo a variáveis compartilhadas
Jantar dos filósofos






Cinco filósofos ao redor de uma mesa redonda
Cada filósofo alterna entre comer e pensar
O spaghetti está no centro da mesa
Filósofos precisam de dois garfos para se
alimentar
Existem 5 garfos, um entre cada par de
filósofos
Evitar deadlock, e outras propriedades.
Jantar dos Filósofos
Fil. 1
Fil. 2
Fil. 0
Fil. 3
Fil. 4
Solução


sem_t fork[4] = 1;
void Philosopher[i] { /* filósofo 1 a 4 */
while (TRUE) {
Think;
P(fork[i]);
P(fork[(i+1) % 5]);
Eat;
V (fork[i]);
V (fork[(i+1) % 5]);
}
}
Solução 2


sem_t fork[4] = 1;
void Philosopher[i] { /* filósofo 0 a 3 */
while (TRUE) {
Think;
P(fork[i]);
P(fork[(i+1) % 5]);
Eat;
V (fork[i]);
V (fork[(i+1) % 5]);
}
}
Solução 2 (cont.)


sem_t fork[4] = 1;
void Philosopher[4] { /* filósofo 4 */
while (TRUE) {
Think;
P(fork[0]);
P(fork[4]);
Eat;
V (fork[4]);
V (fork[0]);
}
}
Leitores e Escritores





Dois tipos de processos: leitores e escritores,
compartilham o acesso a uma base de dados.
Leitores lêem valores da base de dados.
Escritores escrevem na base de dados.
A Base de dados está inicialmente em um
estado consistente.
Cada transação transforma a base de dados
de um estado consistente em outro.
Leitores e Escritores

Para evitar interferência o escritor deve
ter acesso exclusivo à base de dados
Se nenhum escritor estiver acessando a
base de dados, vários leitores podem ler
concorrentemente a base de dados

Exclusão mútua seletiva

Solução

Variáveis para controlar leitores e escritores
reading, writing[n]
Esboço da Solução

int reading = 0; int nr = 0; int writing[n] = 0;
void Reader[i] {
while (TRUE) {
<nr++; if (nr == 1) {reading++};>
read the database
<nr--; if (nr == 0) {reading--};>
}
}
void Writer[i] {
while (TRUE) {
<writing[i]++;>
write the database
<writing[i]--;>
}
}
Solução de grossa granularidade

int reading = 0; int nr = 0; int writing[n] = 0;
void Reader[i] {
while (TRUE) {
<nr++; if (nr == 1) {await (SUM0) -> reading++};>
read the database
<nr--; if (nr == 0) {reading--};>
}
}
void Writer[i] {
while (TRUE) {
<await (SUM 0) -> writing[i]++;>
write the database
<writing[i]--;>
}
}
Solução de grossa granularidade

int reading = 0; int nr = 0; int writing[n] = 0;
sem_t mutexR = 1;
void Reader[i] {
while (TRUE) {
P(mutexR);
nr++;
if (nr == 1) {<await (SUM0) -> reading++>};
V(mutexR);
read the database
P(mutexR);
nr--;
if (nr == 0) {< reading-- >};
V(mutexR);
}
}
Solução

int nr = 0;
sem_t mutexR = 1; sem_t rw = 1;
void Reader[i] {
while (TRUE) {
P(mutexR);
nr++; if (nr == 1) {P(rw)};
V(mutexR);
read the database
P(mutexR);
nr--; if (nr == 0) {V(rw)};
V(mutexR);
}
}
Solução

void Writer[i] {
while (TRUE) {
P(rw);
write the database
V(rw);
}
}
Solução

Prioridade para os escritores

Outra solução: controlar quais processos
estão em espera, e escolher outro tipo de
prioridade
 contar número de leitores e escritores na região
crítica (nr, nw), número de leitores e escritores
esperando (dr, dw).
Solução 2

int nr = 0; nw = 0;
sem_t e = 1; sem_t r = 0; sem_t w = 0;
int dr = 0; int dw = 0;
Solução 2

void Reader[i] {
while (TRUE) {
P(e);
if (nw > 0) {dr++; V(e); P(r)};
nr++;
if (dr > 0) {dr--; V(r)} else {V(e)};
read the database
P(e);
nr--; if (nr == 0 && dw > 0) {dw--;V(w)} else
{V(e)};
}
}
Solução 2

void Writer[i] {
while (TRUE) {
P(e);
if (nr > 0 || nw > 0) {dw++; V(e); P(w)};
nw++;
V(e);
read the database
P(e);
nw--;
if (dr > 0) {dr--;V(r)}
else {if (dw > 0) {dw--;V(w)}
else {V(e)}};
}
}