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 signalSinaliza 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 P1 {while (TRUE) { ...; V(barrier1); P(barrier2); }}

void P2 {while (TRUE) { ...; V(barrier2); P(barrier1); }}

Problema do Produtor-Consumidor 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 Producer { int m; while (TRUE) { Produce(m); P(empty); B[rear] = m; rear = (rear + 1) % n V(full); }}

void Consumer {int m; while (TRUE) { P(full); m = B[front];

front = (front + 1) % n V(empty); 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 Producer { int m; while (TRUE) { Produce(m); P(empty); P(mutexD); B[rear] = m; rear = (rear + 1) % n V(mutexD); V(full); }}

void Consumer {int m; while (TRUE) { P(full); P(mutexF); m = B[front];

front = (front + 1) % n V(mutexF); V(empty); Consume(m);}

}

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. 2

Fil. 3

Fil. 4

Fil. 0

Fil. 1

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 (SUM0) -> 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 (SUM0) -> 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)}}; }}