Capítulo 6: Sincronização de Processos

Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Capítulo 6: Sincronização de Processos

6.2 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

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


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)


Produtor

def produtor():

seed()

global count, BUFFER_SIZE, buffer

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


Consumidor

def consumidor():

seed()

global count, BUFFER_SIZE, buffer

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


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}


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


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


Problema da seção crítica

Processo A

Processo B

T1 T2 T3 T4B bloqueado

A entra na região crítica A deixa a região crítica

B tenta entrar na região crítica

B entra na região crítica

B deixa a região crítica


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


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

– 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

Condição de disputa:Vários processos disputando ao

mesmo tempo o acesso às mesmas variáveis


Revisão

Qual é/são as seções críticas do código?

Uso da variável count

Uso da variável buffer

Consumidordef consumidor():

seed()global countwhile (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

Seção crítica


Revisão

Produtor

def produtor():seed()global counti=0while (True):

sleep(random())#Tempo para simular o processo produzindo a informação

if count<BUFFER_SIZE:buffer.append(str(i))count = count +1i=i+1

else:while (count>=BUFFER_SIZE):

pass

Seção crítica

Seção crítica


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 = 0prod=20 #Numero de produtorescons= 20 #Numero de consumidorest=[1]*(prod+cons) #Inicio o número de threadsfor 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)

sleep (0.1)if (len(buffer)>10):

print "ERRO!!!!, pois o buffer estourou!!!"

Seção crítica

Seção crítica


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


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


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

VARIÁVEL VEZ

P1 P2 Se P1 começa na frente:

2211

Se P2 começa na frente:P1 ganhou

a vez!!!

P2 ganhou a vez!!!

Solução de Peterson: É dando que se recebe!



Código para Processo 0

Enquanto(1){

eu_quero_entrar[0]=1

vez = 1

enquanto (eu_quero_entrar[1]==1 e vez==1){

Não faço nada

}

Executo seção crítica


}

Se quero entrar, sinalizo issoDou a vez para o outro para ver se eu ganho a vez...:)

Se eu quero entrar e a vez é minha, eu pulo o enquanto e vou para seção crítica

Quando terminar a seção crítica, aviso que não quero mais entrar

Quando eu não quiser mais entrar, eu paro o enquanto do outro processo e deixo ele entrar na seção crítica



Código para Processo 0

Enquanto(1){


vez = 1

enquanto (eu_quero_entrar[1]==1 e vez==1){

Não faço nada

}

Executo seção crítica


}

Se quero entrar, sinalizo issoDou a vez para o outro para ver se eu ganho a vez...:)

Se eu quero entrar e a vez não é minha, eu espero até a vez passar a ser minha

Quando o outro programa terminar a seção crítica, ele não vai mais querer entrar e eu saio do enquanto.

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


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

critical section

release lock

remainder section

} while (TRUE);

- Exemplo: ex_threadv2 e ex-thread-lock.py

Fácil de usar....

Mas como funciona???

test and set ou swap!!!

Instruções atômicas(vem daquela ideia antiga de que o átomo era indivisível)(do grego: a=não, tomo=divisão)



Sem me preocupar com a ordem dos processos, usando test and set lock (TSL)

do {

acquire lock

critical section

release lock

remainder section

} while (TRUE);

TSL(x):Se x==0, então x=1 e retorna 0Se x==1, então x=1 e retorna 1

while(TestAndSet(&lock)) ;

lock=0

Então, se lock =0, pode usar. Se lock =1, não pode usar, pois fica

preso no while

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.



Sem me preocupar com a ordem dos processos, usando swap

do {

acquire lock

critical section

release lock

remainder section

} while (TRUE);

swap(x,y):x recebe o valor de y e y recebe o valor de x. É literalmente uma troca.

key=true;while(key==true)

swap(lock,key);

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

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.



Me preocupando com a ordem dos processos, usando test and set

do {

acquire lock

critical section

release lock

remainder section

} while (TRUE);

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.




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.




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;

j = (i + 1) % n; while ((j != i) && !waiting[j])

j = (j + 1) % n; if (j == i)

lock = FALSE; else

waiting[j] = FALSE;

Escolhe o próximo processo que está esperando para entrar

Se ninguém está esperando, libera o lock para qualquer umDo contrário, o próximo processo esperando pode entrar na região crítica


Semáforos

Signal e wait

Operações atômicas na modificação do semáforo

Modificam o valor do sinal

signal (S) { S++; }

int sinal=1;

wait(sinal);

Região crítica;

signal (sinal);

wait (S) { while S <= 0

; // no-op S--; }

Se S=1, decrementa S e pode entrar.Caso contrário, fica esperando em espera

ocupada

Espera ocupada = espera usando CPU


Semáforos

Signal e wait

Operações atômicas na modificação do semáforo

Modificam o valor do sinal

signal (S) { S++; }

int sinal=1;

wait(sinal);

Região crítica;

signal (sinal);

wait (S) { while S <= 0

; // no-op S--; }

S pode ser apenas 1 ou 0.S é um MUTEX, pois permite exclusão

mútua (apenas 1 pode executar).


Semáforos

Signal e wait + block e wakeup

wait(semaphore *S) { S->value--; if (S->value < 0) {

add this process to S->list; block();

} }

signal(semaphore *S) { S->value++; if (S->value <= 0) {

remove a process P from S->list; wakeup(P);

}}

int sinal=1;

wait(sinal);

Região crítica;

signal (sinal);

S pode variar entre –infinito e 1. Se S=1, o processo acessa a região crítica.

Permite fazer a fila de processos esperando.


Semáforos

Signal e wait + block e wakeup

wait(semaphore *S) { S->value--; if (S->value < 0) {

add this process to S->list; block();

} }

signal(semaphore *S) { S->value++; if (S->value <= 0) {

remove a process P from S->list; wakeup(P);

}}

int sinal=1;

wait(sinal);

Região crítica;

signal (sinal);

Não tem espera ocupada!


Exemplos

Semáforos em python

Thread-lock-semaphore.py


Exercícios Quando ocorre condição de disputa?

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.

Qual a relação entre seção crítica e condição de disputa?

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?

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?

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.


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);

signal (Q); signal (S);


Exercício

Crie um programa que crie 2 processos cuja a interação leve a um deadlock.


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


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



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

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



Estrutura do processo produtor

do {

// produce an item in nextp

wait (empty);

wait (mutex);

// add the item to the buffer

signal (mutex);

signal (full);

} while (TRUE);

Não pode trocar a ordem!

Espera ter um vazio para usar e usa

Pede acesso ao buffer

Libera o acesso ao buffer

Aumenta o número de espaços ocupados



Estrutura do processo consumidor

do {

wait (full);

wait (mutex);

// remove an item from buffer to nextc

signal (mutex);

signal (empty);

// consume the item in nextc

} while (TRUE);

Espera ter um cheio para usar e usa

Pede acesso ao buffer

Libera o acesso ao buffer

Aumenta o número de espaços vazios


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 Full Empty Buffer[0] Buffer[1] Buffer[2]


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.



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 •Solução proposta: nenhum leitor deve esperar que outros leitores terminem só porque existe um

escritor esperando prioridade para leitores



Dados compartilhados

Conjunto de dados

Semáforo mutex inicializado em 1

Semáforo wrt inicializado em 1

Inteiro readcount inicializado em 0

Trata do acesso ao readcount

Exclusão mútua para escritores

Número de leitores



Estrutura do processo escritor

do {

wait (wrt) ;

// writing is performed

signal (wrt) ;

} while (TRUE);

Estrutura do processo leitor

do {

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);

Seção críticaSeção crítica

Seção crítica




do {

wait (wrt) ;


signal (wrt) ;

} while (TRUE);


do {

wait (mutex) ;

readcount ++ ;

if (readcount == 1)

wait (wrt) ;

signal (mutex)


wait (mutex) ;

readcount - - ;

if (readcount == 0)

signal (wrt) ;

signal (mutex) ;

} while (TRUE);

Espera ter acesso ao buffer sozinho

Libera para leitores e escritores




do {

wait (wrt) ;


signal (wrt) ;

} while (TRUE);


do {

wait (mutex) ;

readcount ++ ;

if (readcount == 1)

wait (wrt) ;

signal (mutex)


wait (mutex) ;

readcount - - ;

if (readcount == 0)

signal (wrt) ;

signal (mutex) ;

} while (TRUE);

Acabei de ler. Se ninguém estiver usando, atualizo o readcount

Se ninguém está usando o readcount, posso usar

Começando pelo mutex readcount

Depois de atualizar, libero o readcount

Libero o readcount




do {

wait (wrt) ;


signal (wrt) ;

} while (TRUE);


do {

wait (mutex) ;

readcount ++ ;

if (readcount == 1)

wait (wrt) ;

signal (mutex)


wait (mutex) ;

readcount - - ;

if (readcount == 0)

signal (wrt) ;

signal (mutex) ;

} while (TRUE);

Se não tem mais leitores, então libera o acesso para escritores e leitores

Se já não tem alguém lendo, pode ter alguém escrevendo

Agora o mutex wrt


Variações do problema dos leitores-escritores

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 leitor-escritor.


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


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] );

// think

} while (TRUE);

Qual o problema com esse algoritmo?

Possibilidade de deadlock e de inanição


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


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 (…) { … }

}

}


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


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

Implementado no Python com a classe Condition


Solução para o jantar dos filósofos

monitor DiningPhilosophers

{

enum { THINKING; HUNGRY, EATING) state [5] ;

condition self [5];

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);

}

void test (int i) { if ( (state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING ;

self[i].signal () ; } }

initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING;}

}


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

Solução para o jantar dos filósofos

Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

End of Chapter 6

Documents

Capítulo 6: Sincronização de Processos