Semáforos

Variáveis compartilhadas são globais Acesso a variáveis ocorre em procedimentos,

mas podem estar espalhados pelo programa Exige consulta a todo o programa para

entender como as variáveis compartilhadas são usadas

A cada novo processo, é preciso verificar se ele usa as variáveis corretamente

Mesma estrutura é usada para exclusão mútua e sincronização de condição

Modularização ADT – Abstract Data type

Abstração de dados: esconde a representação de dados

Dados são manipulados apenas pelas operações disponibilizadas pelo tipo de dados

Concentra dados e operações em um único lugar

Permite que a implementação seja modificada, desde que a interface e funcionamento continuem os mesmos.

Monitores

Utilizam o coceito de ADT Processos interagem apenas através de

chamadas aos procedimentos do monitor Modularização abstrai os processos da

implementação do procedimento Permite ignorar como e onde os

procedimentos do monitor são usados: o monitor estará correto independentemente do número de processos que o utilizam.

Monitores Podem ser implementados eficientemente Exclusão mútua implícita entre

procedimentos do monitor Variáveis de condição são usadas para

sincronização de condição Permite o desenvolvimento por equipes

independentes dos processos e monitores Facilita o desenvolvimento e entendimento

dos programas concorrentes

Produtor-Consumidor monitor Producer_Consumer_Monitor {

int B [0..N-1];int In_Ptr = 0; int Out_Ptr = 0;int Count = 0;Condition Not_Full, Not_Empty;void Append(int I) { while (Count == N) {wait(Not_Full)}; B [In_Ptr] = I; Count = Count + 1; In_Ptr = (In_Ptr + 1) % N; signal(Not_Empty);}

Produtor-Consumidor

void Take(int I) { while (Count == 0) {wait(Not_Empty)}; I = B[Out_Ptr]; Count = Count - 1; Out_Ptr = (Out_Ptr + 1) % N; signal(Not_Full);}}

Produtor-Consumidor

Producer () { int I; while (TRUE) { Produce(I); Append(I); }}

Consumer { int I; while (TRUE) { Take(I); Consume(I); } }

Diferenças

3 Semáforos Um para exclusão mútua, e dois

(Not_empty e Not_Full) para sincronização Monitores:

exclusão mútua: implícita entre os procedimentos do monitor

sincronização: através de variáveis de condição

Operações sobre Variáveis de Condição wait(C)

suspende processo em uma fila FIFO associada a C, e libera a exclusão mútua.

signal(C) se a fila de C não está vazia, acorda o

processo no início da fila, caso contrário não faz nada.

empty(C) true se a fila de C está vazia

Operações sobre Variáveis de Condição wait(C,rank)

Semelhante ao wait, mas processos são acordados em ordem crescente de rank

minrank(C) Retorna o rank do primeiro processo da

fila Signal_all(C)

Acorda todos os processos suspensos em C

Shortest-job-next monitor ShortestJobNext {

BOOL free = TRUE;Condition turn;void request (int time) { if (free) {free = FALSE} else {wait(turn, time)};}void release () { if (empty(turn)) {free = TRUE;} else {signal(turn);};}

Revendo o problema dos Leitores e Escritores Leitores não precisam se excluir

mutuamente Escritores precisam excluir todos os

outros processos

Leitores e Escritores

Reader () { while (TRUE) { Start_Read; Read_the_Data; End_Read; }}

Writer () { while (TRUE) { Start_Write; Write_the_Data; End_Write; }}

Monitor

Variáveis de status Readers

# de leitores lendo

Writing true quando o processo está escrevendo

Variáveis de condição OK_to_Read OK_to_Write

Monitor Monitor Reader_Writer_Monitor {

int Readers = 0;BOOL Writing = False;Condition OK_to_Read, OK_to_Write;

void Start_Read { while (Writing) {wait(OK_to_Read);}; Readers = Readers + 1;}

void End_Read { Readers = Readers - 1; if (Readers==0) {signal(OK_to_Write);};}

Monitor void Start_Write {

if (Readers > 0 || Writing) {wait(OK_to_Write);}; Writing = True;}

void End_Write { Writing := False; signal(OK_to_Write); signal_all(OK_to_Read);}}

Emulação de semáforos por monitores monitor Semaphore_Emulation {

int S = 0;Condition Not_Zero;procedure P { while (S==0) {wait(Not_Zero);}; S = S - 1;}procedure V { S = S + 1; signal(Not_Zero);}}

Emulação de semáforos por monitores (2) monitor Semaphore_Emulation {

int S = 0;Condition Not_Zero;procedure P { if (S > 0) {S = S – 1;} else {wait(Not_Zero);};}procedure V { if (empty(Not_Zero) {S = S + 1} else {signal(Not_Zero)};}}

O Problema do barbeiro que dorme Semelhante a problemas de

escalonamento de disco Relacionamento cliente-servidor rendezvous

O Problema do barbeiro que dorme Barbearia com duas portas (entrada e

saída) e algumas cadeiras (espera) Barbeiro atende um cliente de cada vez Se faltam clientes, o barbeiro dorme Se um cliente chega, ele acorda o

barbeiro para que corte seu cabelo Cliente dorme nas cadeiras de espera

se o barbeiro está ocupado

O Problema do barbeiro que dorme Clientes e barbeiros são processos Barbearia é o monitor Relação cliente/servidor(barbeiro)

Procedimentos do monitor

get_haircut get_next_custumer finished_cut

Leitores e Escritores

Reader () { while (TRUE) { Start_Read; Read_the_Data; End_Read; }}

Writer () { while (TRUE) { Start_Write; Write_the_Data; End_Write; }}