Capítulo 6: Sincronização de
Processos
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009
Background

Acesso concorrente a um dado compartilhado pode resultar em inconsistência

Para manter a consistência, é preciso garantir uma execução ordenada dos
processos cooperativos (que estão interagindo por meio de uma estrutura
compartilhada)

Estudo da concorrência entre processos através de modelos

Exemplo: Produtor-consumidor
Operating System Concepts – 8th Edition
6.2
Silberschatz, Galvin and Gagne ©2009
Problema do Produtor-Consumidor


Produtor e consumidor são dois processos distintos

O produtor produz e coloca o produto no buffer

O consumidor consome produtos que estão no buffer
Consequências


O buffer passa a ser uma estrutura compartilhada

O produtor não pode colocar um produto em um buffer cheio

O consumidor não pode consumir um produto se o buffer estiver vazio
A variável compartilhada count pode ser usada para saber o número de
elementos no momento dentro do buffer

Eventualmente, o count pode ser atualizado simultaneamente pelo produtor e
pelo consumidor
–
Atualização não é uma tarefa atômica (indivisível)
Operating System Concepts – 8th Edition
6.3
Silberschatz, Galvin and Gagne ©2009
Produtor
def produtor():
seed()
global count
i=0
while (True):
sleep(random())#Tempo para simular o processo produzindo a
informação
if count<BUFFER_SIZE:
buffer.append(str(i))
count = count +1
i=i+1
else:
while (count>=BUFFER_SIZE):
pass
Operating System Concepts – 8th Edition
6.4
Silberschatz, Galvin and Gagne ©2009
Consumidor
def consumidor():
seed()
global count
while (True):
if count>0:
buffer.pop(0)
count = count -1
sleep(random()) #Tempo para simular o processo
consumindo a informação
else:
while(count<=0):
pass
Operating System Concepts – 8th Edition
6.5
Silberschatz, Galvin and Gagne ©2009
Condição de disputa
 O incremento do contador pode ser implementado da seguinte forma:
register1 = counter
register1 = register1 + 1
counter = register1
 O decremento do contador, por sua vez, seria:
register2 = counter
register2 = register2 - 1
count = register2
 Suponha que, no momento, count=5 e que o produtor e o
consumidor estão sendo executados:
t0: produtor: register1 = counter {register1 = 5}
t1: produtor:
register1 = register1 + 1 {register1 = 6}
t2: consumidor: register2 = counter {register2 = 5}
t3: consumidor: register2 = register2 - 1 {register2 = 4}
t4: produtor:
counter = register1 {count = 6 }
t5: consumidor: counter = register2 {count = 4}
Operating System Concepts – 8th Edition
6.6
Silberschatz, Galvin and Gagne ©2009
Condição de disputa

Definição


Situação em que várias tarefas acessam dados concorrentemente e o resultado
da execução depende da ordem específica em que o acesso ocorre
Solução para a condição de disputa:

Sincronização de processos

Proteção das seções críticas

Uma seção crítica (ou região crítica) é um trecho de código no qual a tarefa
está alterando uma estrutura compartilhada (variáveis compartilhadas,
tabelas, arquivos, etc.)
–
Dessa forma, se um processo entra na sua seção crítica, nenhum outro
processo que compartilhe alguma estrutura pode ser autorizado a entrar
na sua seção crítica
Operating System Concepts – 8th Edition
6.7
Silberschatz, Galvin and Gagne ©2009
Problema da seção crítica

Problema de como controlar o acesso às seções críticas de processos que
compartilham dados

Ideia: Criar um protocolo de acesso

Processo pede autorização para entrar na seção crítica

Quando autorizado, processo executa seção crítica

Processo avisa que terminou sua seção crítica

Processo continua a sua execução
Operating System Concepts – 8th Edition
6.8
Silberschatz, Galvin and Gagne ©2009
Problema da seção crítica
A entra na região crítica
A deixa a região crítica
Processo A
B tenta entrar
na região crítica
Processo B
B entra na
região crítica
B deixa a
região crítica
B bloqueado
T1
Operating System Concepts – 8th Edition
T3
T2
6.9
T4
Silberschatz, Galvin and Gagne ©2009
Soluções para o problema da região
crítica
1. Exclusão mútua

Nunca dois processos podem estar simultaneamente em suas regiões
críticas
2. Progresso

Nenhum processo fora da sua região crítica pode bloquear outros
processos
3. Espera limitada

Nenhum processo deve esperar eternamente para entrar em sua região
crítica
Nada pode ser afirmado sobre a velocidade de processamento ou sobre
o número de CPUs disponíveis
Operating System Concepts – 8th Edition
6.10
Silberschatz, Galvin and Gagne ©2009
Revisão

Problema do produtor-consumidor


Código em Python

Único buffer com 10 posições

P produtores

C consumidores
Problema?

A variável count é modificada por vários threads ao mesmo tempo
–

Condição de disputa:
Vários processos disputando ao
mesmo tempo o acesso às mesmas
variáveis
Inconsistência no valor
Alguma diferença entre o uso de processos ou threads?

Usando processos fica mais pesado

Usando processos tem que usar memória compartilhada
–
Python já tem certo controle sobre essas variáveis
Operating System Concepts – 8th Edition
6.11
Silberschatz, Galvin and Gagne ©2009
Revisão

Qual é/são as seções críticas do código?

Uso da variável count

Uso da variável buffer

Consumidor
def consumidor():
seed()
global count
while (True):
if count>0:
buffer.pop(0)
count = count -1
Seção crítica
sleep(random()) #Tempo
para simular o processo consumindo a
informação
else:
while(count<=0):
pass
Operating System Concepts – 8th Edition
6.12
Silberschatz, Galvin and Gagne ©2009
Revisão

Produtor
def produtor():
seed()
global count
i=0
while (True):
sleep(random())#Tempo para simular o
processo produzindo a informação
if count<BUFFER_SIZE:
Seção crítica
buffer.append(str(i))
count = count +1
i=i+1
else:
while (count>=BUFFER_SIZE):
Seção crítica
pass
Operating System Concepts – 8th Edition
6.13
Silberschatz, Galvin and Gagne ©2009
Revisão

Main:
if __name__ == '__main__': ###Programa principal
print "Esse programa simula o problema do produtor-consumidor, utilizando
uma lista compartilhada por n threads: os produtores e os consumidores"
print "Está se utilizando o método da espera ocupada."
count = 0
prod=20 #Numero de produtores
cons= 20 #Numero de consumidores
t=[1]*(prod+cons) #Inicio o número de threads
for i in range(prod):
t[i] = Thread(target=produtor, args=())
t[i].start()
for i in range(prod,prod+cons):
t[i] = Thread(target=consumidor, args=())
t[i].start()
while (True):
if (len(buffer) != count):
print "ERRO!!!!, pois tamanho do buffer = %d e count = %d"
% (len(buffer),count)
Seção
sleep (0.1)
crítica
if (len(buffer)>10):
print "ERRO!!!!, pois o buffer estourou!!!"
Operating System Concepts – 8th Edition
6.14
Seção
crítica
Silberschatz, Galvin and Gagne ©2009
Revisão

Como proteger a seção crítica?

Enquanto um produtor está na seção crítica, nenhum outro produtor ou
consumidor pode entrar na seção crítica


Seção crítica = seção aonde se atualiza ou se compara as variáveis
compartilhadas
Enquanto um consumidor está na seção crítica, nenhum outro consumidor ou
produtor pode entrar na seção crítica
Operating System Concepts – 8th Edition
6.15
Silberschatz, Galvin and Gagne ©2009
Soluções para o problema da seção crítica

Soluções

Solução de Peterson – Software

Test and set – Solução por hardware

Semáforos e mutexes – Auxílio de hardware
Operating System Concepts – 8th Edition
6.16
Silberschatz, Galvin and Gagne ©2009
Solução de Peterson

Solução por software para controle de 2 processos

Ideia

Se eu quero entrar na região crítica, devo dizer isso ao outro programa

Eu só posso entrar na seção crítica quando for a minha vez
–

Se o outro processo não quer entrar na seção crítica, então passa a ser a
minha vez automaticamente
Eu começo dando a vez para o outro programa, mesmo que eu queira usar
–
Se dois querem, quem der a vez primeiro para o outro vai passar na
frente
P2 ganhou
vez!!!
P1a ganhou
a vez!!!
Operating System Concepts – 8th Edition
P1
P2
Se P1 começa na frente:
Se P2 começa na frente:
VARIÁVEL VEZ
1
2
6.17
Silberschatz, Galvin and Gagne ©2009
Solução de Peterson

Código para Processo 0
Se quero entrar, sinalizo isso
Dou a vez para o outro para
ver se eu ganho a vez...:)
Enquanto(1){
eu_quero_entrar[0]=1
vez = 1
enquanto (eu_quero_entrar[1]==1 e vez==1){
Não faço nada
Quando terminar a seção
crítica, aviso que não quero
mais entrar
}
Executo seção crítica
eu_quero_entrar[0]=0
Quando eu não quiser mais
entrar, eu paro o enquanto
do outro processo e deixo
ele entrar na seção crítica
}
Operating System Concepts – 8th Edition
Se eu quero entrar e a vez é
minha, eu pulo o enquanto
e vou para seção crítica
6.18
Silberschatz, Galvin and Gagne ©2009
Solução de Peterson

Código para Processo 0
Se quero entrar, sinalizo isso
Dou a vez para o outro para
ver se eu ganho a vez...:)
Enquanto(1){
eu_quero_entrar[0]=1
vez = 1
enquanto (eu_quero_entrar[1]==1 e vez==1){
Não faço nada
Quando o outro programa
terminar a seção crítica, ele
não vai mais querer entrar e
eu saio do enquanto.
}
Executo seção crítica
eu_quero_entrar[0]=0
}
Se eu quero entrar e a vez
não é minha, eu espero até
a vez passar a ser minha
Depois que eu executar
minha seção crítica, eu digo
que não quero mais entrar.
A variável vez só serve para distinguir quem vai
entrar se tiver disputa, ou seja, mais de um
processo querendo entrar na seção crítica
Operating System Concepts – 8th Edition
6.19
Silberschatz, Galvin and Gagne ©2009
Solução de hardware

Como implementar o lock?

Como permitir que os programas entrem na sua seção crítica segundo uma fila?
do {
acquire lock
Fácil de usar....
critical section
Mas como funciona???
release lock
remainder section
test and set ou swap!!!
} while (TRUE);
- Exemplo: ex_threadv2 e ex-thread-lock.py
Operating System Concepts – 8th Edition
6.20
Instruções atômicas
(vem daquela ideia antiga de
que o átomo era indivisível)
(do grego: a=não,
tomo=divisão)
Silberschatz, Galvin and Gagne ©2009
Solução de hardware

Sem me preocupar com a ordem dos processos, usando test and set lock (TSL)
TSL(x):
Se x==0, então x=1 e retorna 0
Se x==1, então x=1 e retorna 1
do {
acquire lock
critical section
release lock
while(TestAndSet(&lock)) ;
remainder section
} while (TRUE);
lock=0
A TSL é uma instrução atômica.
Então, apenas 1 processo pode
executá-la, mesmo que existam
vários processadores. Assim,
apenas 1 processo pode aproveitar
o lock=0.
Então, se lock =0, pode usar. Se
lock =1, não pode usar, pois fica
preso no while
Operating System Concepts – 8th Edition
6.21
Silberschatz, Galvin and Gagne ©2009
Solução de hardware

Sem me preocupar com a ordem dos processos, usando swap
swap(x,y):
x recebe o valor de y e y recebe
o valor de x. É literalmente uma
troca.
do {
acquire lock
critical section
key=true;
while(key==true)
swap(lock,key);
release lock
remainder section
} while (TRUE);
lock=0
Então, se lock =0, key vira false,
lock vira 1 e o processo sai do while.
Se lock =1, não pode usar, pois
key=lock=1 e o processo fica preso
no while
Operating System Concepts – 8th Edition
6.22
A swap também é uma instrução
atômica. Então, apenas 1 processo
pode executá-la, mesmo que
existam vários processadores.
Assim, apenas 1 processo pode
aproveitar o lock=0.
Silberschatz, Galvin and Gagne ©2009
Solução de hardware

Me preocupando com a ordem dos processos, usando test and set
do {
acquire lock
critical section
release lock
Em todos os exemplos anteriores,
não é possível garantir que algum
processo não vai ficar esperando
eternamente. O mais rápido pega o
lock, e não o processo que está
esperando a mais tempo.
remainder section
} while (TRUE);
Operating System Concepts – 8th Edition
6.23
Silberschatz, Galvin and Gagne ©2009
Solução de hardware

Me preocupando com a ordem dos processos, usando test and set
TSL(x):
Se x==0, então x=1 e retorna 0
Se x==1, então x=1 e retorna 1
do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);
waiting[i]=true;
key=true;
while(waiting[i]==true)&(key==true)
key = TestAndSet(&lock)
Waiting[i]=false;
Se lock=0, então lock=1 e key=0. Isso
faz o processo sair do while. Uma vez
que o processo ganhou o acesso, ele não
espera mais para entrar na seção crítica.
Se lock=1, então lock=key=1. O
programa fica preso no while.
Operating System Concepts – 8th Edition
6.24
Silberschatz, Galvin and Gagne ©2009
Solução de hardware

Me preocupando com a ordem dos processos, usando test and set
TSL(x):
Se x==0, então x=1 e retorna 0
Se x==1, então x=1 e retorna 1
do {
acquire lock
critical section
release lock
remainder section
waiting[i]=true;
key=true;
while(waiting[i]==true)&(key==true)
key = TestAndSet(&lock)
Waiting[i]=false;
} while (TRUE);
j = (i + 1) % n;
Escolhe o próximo processo que está
while ((j != i) && !waiting[j])
esperando para entrar
j = (j + 1) % n;
if (j == i)
Se ninguém está esperando, libera o lock
lock = FALSE;
para qualquer um
else
Do contrário, o próximo processo esperando
waiting[j] = FALSE;
pode entrar na região crítica Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
6.25
Semáforos

Signal e wait

Operações atômicas na modificação do semáforo

Modificam o valor do sinal
int sinal=1;
wait(sinal);
Região crítica;
wait (S) {
while S <= 0
; // no-op
S--;
}
Se S=1, decrementa S e pode entrar.
Caso contrário, fica esperando em espera
ocupada
signal (sinal);
Espera ocupada = espera usando CPU
signal (S) {
S++;
}
Operating System Concepts – 8th Edition
6.26
Silberschatz, Galvin and Gagne ©2009
Semáforos

Signal e wait

Operações atômicas na modificação do semáforo

Modificam o valor do sinal
int sinal=1;
wait (S) {
while S <= 0
; // no-op
S--;
}
wait(sinal);
Região crítica;
signal (sinal);
S pode ser apenas 1 ou 0.
S é um MUTEX, pois permite exclusão
mútua (apenas 1 pode executar).
signal (S) {
S++;
}
Operating System Concepts – 8th Edition
6.27
Silberschatz, Galvin and Gagne ©2009
Semáforos

Signal e wait + block e wakeup
int sinal=1;
wait(sinal);
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}
Região crítica;
S pode variar entre –infinito e 1. Se S=1, o
processo acessa a região crítica.
signal (sinal);
Permite fazer a fila de processos esperando.
Operating System Concepts – 8th Edition
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
6.28
Silberschatz, Galvin and Gagne ©2009
Semáforos

Signal e wait + block e wakeup
int sinal=1;
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}
wait(sinal);
Não tem espera ocupada!
Região crítica;
signal (sinal);
Operating System Concepts – 8th Edition
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
6.29
Silberschatz, Galvin and Gagne ©2009
Exemplos
 Semáforos em python

Thread-lock-semaphore.py
Operating System Concepts – 8th Edition
6.30
Silberschatz, Galvin and Gagne ©2009
Exercícios

Quando ocorre condição de disputa?


Qual a relação entre seção crítica e condição de disputa?


Uma solução para o problema da seção crítica feita por software para quando
existem no máximo 2 processos disputando o acesso a seção crítica.
Como funcionam as soluções de sincronismo baseadas em hardware?


A seção crítica é a parte do código na qual ocorrem os acessos às variáveis
compartilhadas, onde, eventualmente, podem ocorrer condições de disputa.
O que é a solução de Peterson?


Quando dois ou mais processos tentam utilizar a mesma variável compartilhada
ao mesmo tempo, de tal forma que o valor final da variável dependa da ordem
específica com a qual os acessos ocorrem.
Através do uso de instruções atômicas que auxiliam a exclusão mútua, tais como
a test & set e a swap.
Qual a principal diferença funcional entre locks e semáforos?

Os locks permitem criar apenas a exclusão mútua, enquanto que os semáforos
podem ser usados para fazer a exclusão mútua ou para selecionar um número
de eventos que podem ocorrer em paralelo.
Operating System Concepts – 8th Edition
6.31
Silberschatz, Galvin and Gagne ©2009
Deadlock e Inanição
Deadlock – Acontece quando dois ou mais processos estão esperando por
um evento que só poderia ser executado por um dos processos em espera
 Exemplo


Imagine que S e Q são dois semáforos inicializados em 1
P0
P1
wait (S);
wait (Q);
wait (Q);
wait (S);
.
.
.
.
.
.
signal (S);
signal (Q);
Operating System Concepts – 8th Edition
signal (Q);
signal (S);
6.32
Silberschatz, Galvin and Gagne ©2009
Exercício

Crie um programa que crie 2 processos cuja a interação leve a um deadlock.
Operating System Concepts – 8th Edition
6.33
Silberschatz, Galvin and Gagne ©2009
Deadlock e Inanição

Inanição – Bloqueio indefinido
 Um processo nunca é retirado da fila de espera por um semáforo
 Exemplo: Política de escolha de quem recebe o semáforo do tipo LIFO
(Last In, First Out)

Inversão de prioridades – Problema de escalonamento que ocorre quando
um processo de baixa prioridade tem posse de um semáforo compartilhado
com processos de alta prioridade

Solução: Protocolo de herança de prioridade
 Todos os processos que compartilham dados com um processo de
alta prioridade recebem a mesma prioridade que esse processo
Operating System Concepts – 8th Edition
6.34
Silberschatz, Galvin and Gagne ©2009
Problemas clássicos de sincronização

Problemas clássicos usados para testar novos esquemas de sincronização propostos

Problema do buffer limitado

Problema dos leitores-escritores

Problema do jantar dos filósofos
Operating System Concepts – 8th Edition
6.35
Silberschatz, Galvin and Gagne ©2009
Problema do buffer limitado


N buffers, cada um podendo armazenar um item
Semáforo mutex inicializado no valor 1

Semáforo full inicializado no valor 0

Semáforo empty inicializado no valor N
Operating System Concepts – 8th Edition
6.36
Controla o acesso ao
buffer
Controla o número de
espaços ocupados no buffer
Controla o número de
espaços vazios no buffer
Silberschatz, Galvin and Gagne ©2009
Problema do buffer limitado

Estrutura do processo produtor
do {
// produce an item in nextp
Espera ter um vazio
para usar e usa
Pede acesso ao buffer
wait (empty);
wait (mutex);
// add the item to the buffer
Libera o acesso ao buffer
signal (mutex);
Aumenta o número de
espaços ocupados
signal (full);
} while (TRUE);
Operating System Concepts – 8th Edition
Não pode trocar
a ordem!
6.37
Silberschatz, Galvin and Gagne ©2009
Problema do buffer limitado

Espera ter um cheio
para usar e usa
Estrutura do processo consumidor
Pede acesso ao buffer
do {
wait (full);
wait (mutex);
// remove an item from buffer to nextc
Libera o acesso ao buffer
signal (mutex);
Aumenta o número de
espaços vazios
signal (empty);
// consume the item in nextc
} while (TRUE);
Operating System Concepts – 8th Edition
6.38
Silberschatz, Galvin and Gagne ©2009
Exercícios

Com base nos códigos do produtor e do consumidor,qual o estado das variáveis
compartilhadas ao longo do tempo, se cada processo executa uma linha de código e
perde a vez? Dê sua resposta no formato da tabela abaixo. Preencha pelo menos 16
linhas e assuma que o processo produtor foi iniciado antes do processo consumidor.
Além disso, suponha que o buffer possui apenas 3 posições.
Linha de
código
Mutex
Operating System Concepts – 8th Edition
Full
Empty
6.39
Buffer[0]
Buffer[1]
Buffer[2]
Silberschatz, Galvin and Gagne ©2009
Exercício

Repita o exercício anterior, supondo que o consumidor foi o primeiro processo a ser
executado.

Repita o exercício anterior, supondo que a operação de produção de item seja 16x
mais rápida que a operação de consumo de item. Suponha que o buffer comece com
2 elementos e execute até que o produtor seja bloqueado pela primeira vez.

Suponha que as linhas 2 e 3 (wait empty e wait mutex) do código do produtor fossem
trocadas e que o buffer seja iniciado cheio. Isso causará algum problema?

Suponha que o buffer está cheio.
Operating System Concepts – 8th Edition
6.40
Silberschatz, Galvin and Gagne ©2009
Problema dos leitores-escritores



Um conjunto de dados é compartilhado entre um número de processos
concorrentes

Leitores – apenas leem o conjunto de dados; não realizam atualizações

Escritores – podem ler e escrever
Problema

Permitir que múltiplos leitores leiam ao mesmo tempo

Apenas um escritor pode acessar os dados compartilhados ao mesmo
tempo
Existem diversas variações sobre como tratar os leitores e os escritores

Todas envolvem prioridades
Operating System Concepts – 8th Edition
•Solução proposta: nenhum leitor
deve esperar que outros leitores
terminem só porque existe um
escritor esperando  prioridade
para leitores
6.41
Silberschatz, Galvin and Gagne ©2009
Problema dos leitores-escritores

Dados compartilhados
Trata do acesso ao readcount

Conjunto de dados

Semáforo mutex inicializado em 1

Semáforo wrt inicializado em 1

Inteiro readcount inicializado em 0
Exclusão mútua para escritores
Número de leitores
Operating System Concepts – 8th Edition
6.42
Silberschatz, Galvin and Gagne ©2009
Problema dos leitores-escritores


Estrutura do processo escritor
Estrutura do processo leitor
do {
do {
wait (wrt) ;
//
Seção crítica
Seção crítica
writing is performed
wait (mutex) ;
readcount ++ ;
if (readcount == 1)
wait (wrt) ;
signal (mutex)
signal (wrt) ;
// reading is performed
} while (TRUE);
Seção crítica
Operating System Concepts – 8th Edition
6.43
wait (mutex) ;
readcount - - ;
if (readcount == 0)
signal (wrt) ;
signal (mutex) ;
} while (TRUE);
Silberschatz, Galvin and Gagne ©2009
Problema dos leitores-escritores


Estrutura do processo escritor
Estrutura do processo leitor
do {
do {
wait (wrt) ;
//
Espera ter acesso ao
buffer sozinho
writing is performed
signal (wrt) ;
} while (TRUE);
Libera para leitores e
escritores
wait (mutex) ;
readcount ++ ;
if (readcount == 1)
wait (wrt) ;
signal (mutex)
// reading is performed
wait (mutex) ;
readcount - - ;
if (readcount == 0)
signal (wrt) ;
signal (mutex) ;
} while (TRUE);
Operating System Concepts – 8th Edition
6.44
Silberschatz, Galvin and Gagne ©2009
Problema dos leitores-escritores


Estrutura do processo escritor
Estrutura do processo leitor
do {
do {
wait (wrt) ;
Se ninguém está
usando o readcount,
posso usar
//
writing is performed
Depois de atualizar,
libero o readcount
signal (wrt) ;
// reading is performed
} while (TRUE);
Começando pelo
mutex readcount
Operating System Concepts – 8th Edition
wait (mutex) ;
readcount ++ ;
if (readcount == 1)
wait (wrt) ;
signal (mutex)
Acabei de ler. Se
ninguém estiver
usando, atualizo o
readcount
wait (mutex) ;
readcount - - ;
if (readcount == 0)
signal (wrt) ;
Libero o readcount
signal (mutex) ;
} while (TRUE);
6.45
Silberschatz, Galvin and Gagne ©2009
Problema dos leitores-escritores


Estrutura do processo escritor
Estrutura do processo leitor
do {
do {
Se já não tem alguém
wait (wrt) ;
lendo, pode ter alguém
escrevendo
// writing is performed
wait (mutex) ;
readcount ++ ;
if (readcount == 1)
wait (wrt) ;
signal (mutex)
signal (wrt) ;
// reading is performed
} while (TRUE);
Agora o mutex wrt
Operating System Concepts – 8th Edition
wait (mutex) ;
readcount - - ;
Se não tem mais
if (readcount == 0)
leitores, então libera o
signal (wrt) ;
acesso para escritores
signal (mutex) ;
e leitores
} while (TRUE);
6.46
Silberschatz, Galvin and Gagne ©2009
Variações do problema dos leitoresescritores

Primeira variação – nenhum leitor é deixado esperando a menos que o escritor tenha
permissão para usar o objeto compartilhado.

Segunda variação – uma vez que o escritor está pronto, ele escreve o mais rápido
possível

Ambos podem levar à inanição, criando ainda mais variações

Problema é solucionado em alguns sistemas pelo Kernel, que provê locks para leitorescritor.
Operating System Concepts – 8th Edition
6.47
Silberschatz, Galvin and Gagne ©2009
Problema do jantar dos filósofos

Filósofos passam suas vidas pensando e comendo

Eles não interagem com seus vizinhos

Ocasionalmente, eles tentam pegar dois palitos, um de cada vez, para
comer da vasilha central.


Eles precisam dos dois palitos para comer, mas liberam os dois
quando terminam
No caso de 5 filósofos

Dados compartilhados

Vasilha de arroz (conjunto de dados)

Semáforos chopstick [5] inicializado em 1
Operating System Concepts – 8th Edition
6.48
Silberschatz, Galvin and Gagne ©2009
Algoritmo do problema do jantar dos
filósofos

Estrutura do i-ésimo filósofo:
do {
wait ( chopstick[i] );
wait ( chopStick[ (i + 1) % 5] );
// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
Possibilidade de deadlock
e de inanição
// think
} while (TRUE);

Qual o problema com esse algoritmo?
Operating System Concepts – 8th Edition
6.49
Silberschatz, Galvin and Gagne ©2009
Problemas com semáforos


Uso incorreto de operações de semáforos:

signal (mutex) …. wait (mutex)

wait (mutex) … wait (mutex)

Omissão do wait (mutex) ou do signal (mutex) (ou de ambos)
Deadlock e inanição
Operating System Concepts – 8th Edition
6.50
Silberschatz, Galvin and Gagne ©2009
Monitores

Uma abstração de alto nível que provê um mecanismo conveniente e eficiente
para sincronizar processos
 Apenas 1 processo pode estar ativo no monitor por vez
 Contudo, não é poderoso o suficiente para modelar alguns esquemas de
sincronização
monitor monitor-name
{
// shared variable declarations
procedure P1 (…) { …. }
procedure Pn (…) {……}
Initialization code (…) { … }
}
}
Operating System Concepts – 8th Edition
6.51
Silberschatz, Galvin and Gagne ©2009
Variáveis condicionais

condição x, y;

Duas operações em uma variável condicional:

x.wait () – o processo que invoca a operação é suspenso até que x.signal
() seja chamado

x.signal () – resume um dos processos, se houver algum, que invocou o
x.wait ()

Se não existe nenhum x.wait () na variável, então isso não tem nenhum
efeito na variável
Operating System Concepts – 8th Edition
6.52
Silberschatz, Galvin and Gagne ©2009
Escolha de variáveis condicionais

Se o processo P chama x.signal (), com o processo Q no estado x.wait (), o
que deve acontecer em seguida?


Se Q é resumido, então P deve esperar
Opções incluem:

Signal and wait – P espera até que Q deixe o monitor ou espere por
alguma outra condição

Signal and continue – Q espera até que P deixe o monitor ou espera por
alguma outra condição

Ambos tem prós e contras – Escolha depende da implementação

Monitores implementados em Pascal concorrente


P executando o signal deixa o monitor imediatamente e Q é resumido
Implementado em outras linguagens, incluindo Mesa, C#, Java
Operating System Concepts –
Implementado no Python com a classe Condition
8th
Edition
6.53
Silberschatz, Galvin and Gagne ©2009
Solução para o jantar dos filósofos
monitor DiningPhilosophers
{
enum { THINKING; HUNGRY, EATING)
state [5] ;
condition self [5];
void test (int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING ;
self[i].signal () ;
}
}
void pickup (int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING) self [i].wait;
}
void putdown (int i) {
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
}
Operating System Concepts – 8th Edition
6.54
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
Silberschatz, Galvin and Gagne ©2009
Solução para o jantar dos filósofos

Cada filósofo I chama as operações pickup() e putdown() na seguinte sequência:
DiningPhilosophers.pickup (i);
EAT
DiningPhilosophers.putdown (i);

Não tem deadlock, mas a inanição é possível
Operating System Concepts – 8th Edition
6.55
Silberschatz, Galvin and Gagne ©2009
End of Chapter 6
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009