Unidade 6: Sincronização de Processos
•
•
•
•
•
•
•
•
•
Contexto
O problema da seção crítica
Hardware para sincronização
Semáforos
Problemas clássicos de sincronização
Regiões críticas
Monitores
Sincronização no Solaris 2
Transação atômica
Operating System Concepts
6.1
Silberschatz and Galvin1999
Contexto
•
•
•
Acesso concorrente a dados compartilhados pode levar a
inconsistências.
Para manter a consistência de dados necessitam-se de
mecanismos que garantem a execução de processos
cooperativos na ordem certa.
A solução do problema do buffer limitado (capítulo 4) permite que
tenha no máximo n – 1 itens no buffer no mesmo tempo. Uma
solução que usa todos os buffers não é simples.
– Suponhamos que modificamos o código de produtor e
consumidor colocando uma variável counter, inicializada em
0 e incrementada a cada vez que um item novo é colocado
no buffer
Operating System Concepts
6.2
Silberschatz and Galvin1999
Bounded-Buffer
•
•
Shared data
type item = … ;
var buffer array [0..n-1] of item;
in, out: 0..n-1;
counter: 0..n;
in, out, counter := 0;
Producer process
repeat
…
produce an item in nextp
…
while counter = n do no-op;
buffer [in] := nextp;
in := in + 1 mod n;
counter := counter +1;
until false;
Operating System Concepts
6.3
Silberschatz and Galvin1999
Bounded-Buffer (Cont.)
•
•
Consumer process
repeat
while counter = 0 do no-op;
nextc := buffer [out];
out := out + 1 mod n;
counter := counter – 1;
…
consume the item in nextc
…
until false;
As linhas de código:
– counter := counter + 1;
– counter := counter - 1;
devem ser executados atomicamente.
Operating System Concepts
6.4
Silberschatz and Galvin1999
O problema da seção crítica
•
•
•
•
n processos concorrem para usar algum dado compartilhado
Cada processo tem um trecho de código chamado seção crítica
no qual os dados compartilhados estão sendo acessados.
O problema: ter certeza que enquanto um processo está
executando dentro da sua seção crítica, nenhum outro processo
é permitido de executar na sua seção crítica.
Estrutura de processo Pi
repeat
seção de entrada
seção crítica
seção de saída
seção restante
until false;
Operating System Concepts
6.5
Silberschatz and Galvin1999
Solução do problema da seção crítica
1. Exclusão mútua. Se processo Pi está executando dentro da sua seção crítica,
nenhum outro processo pode executar na sua seção crítica.
2. Progresso.
Se nenhum processo está executando na sua seção crítica e existe
alguns processos que desejam entrar nas suas respetivas seções críticas, então
a seleção do processo que vai entrar na seção crítica não pode ser adiada por
causa de um processo que está na sua seção restante.
3. Espera limitada.
Deve existir um limite para o número de vezes que outros
processos são permitidos de entrar nas suas seções críticas depois que um
processo tenha feito uma solicitação para entrar a seção crítica dele e antes que
esta solicitação tenha sido atendida.


Suponha que todo processo executa na seção crítica em velocidade não-zero.
Não faça nenhuma suposição sobre a velocidade relativa dos n processos.
Operating System Concepts
6.6
Silberschatz and Galvin1999
Initial Attempts to Solve Problem
•
•
Somente dois processos, P0 e P1
Estrutura geral do processo Pi (outro processo é Pj)
repeat
seção de entrada
seção crítica
seção de saída
seção restante
until false;
•
Processos são permitidos de compartilhar alguns variáveis para
poder sincronizar suas ações.
Operating System Concepts
6.7
Silberschatz and Galvin1999
Algoritmo 1
•
•
Variáveis compartilhadas:
– var turn: (0..1);
inicialmente turn = 0
– turn - i  Pi pode entrar dentro da sua seção crítica
Processo Pi
repeat
while turn  i do no-op;
seção crítica
turn := j;
seção restante
until false;
•
Satisfaz exclusão mútua, mas não o progresso:
Processo Pi não pode executar duas vezes em seguida a seção
critica sem que Pj tenha executado uma vez a seção crítica dele
Operating System Concepts
6.8
Silberschatz and Galvin1999
Algoritmo 2
•
•
Variáveis compartilhadas
– var flag: array [0..1] of boolean;
inicialmente flag [0] = flag [1] = false.
– flag [i] = true  Pi pode entrar dentro da sua seção crítica
Process Pi
repeat
flag[i] := true;
while flag[j] do no-op;
seção crítica
flag [i] := false;
seção restante
until false;
•
Satisfaz exclusão mutua, mas não a condição de progresso.
Operating System Concepts
6.9
Silberschatz and Galvin1999
Algoritmo 3
•
•
Combinação das variáveis compartilhadas de algoritmo 1 e 2.
Processo Pi
repeat
flag [i] := true;
turn := j;
while (flag [j] and turn = j) do no-op;
seção crítica
flag [i] := false;
seção restante
until false;
•
preenche todas as condições e resolve o problema da seção
crítica para dois processos.
Operating System Concepts
6.10
Silberschatz and Galvin1999
Algoritmo do Banco
Seção crítica para n processos
•
•
•
Antes de entrara na sua seção crítica o processos recebe um
número (ficha). Quem está com número menor entra na seção
crítica.
Se procesos Pi e Pj recebem o mesmo número, se i < j, então Pi
é servido primeiro; senão Pj é servido primeiro.
O esquema de enumeração sempre gera números em ordem
crescente, ou seja, 1,2,3,3,3,3,4,5...
Operating System Concepts
6.11
Silberschatz and Galvin1999
Algoritmo do Banco (Cont.)
•
•
Notação < significa ordem numérica da seqüência (ficha #,
processo #)
– (a,b) < (c,d) if a < c or if a = c and b < d
– max (a0,…, an-1) é um elemento k, tal que k  ai for i = 0,
…, n – 1
Dados compartilhados
var choosing: array [0..n – 1] of boolean;
number: array [0..n – 1] of integer,
inicializados para false e 0 respectivamente
Operating System Concepts
6.12
Silberschatz and Galvin1999
Algoritmo de Banco(Cont.)
repeat
choosing[i] := true;
number[i] := max(number[0], number[1], …, number [n – 1])+1;
choosing[i] := false;
for j := 0 to n – 1
do begin
while choosing[j] do no-op;
while number[j]  0
and (number[j],j) < (number[i], i) do no-op;
end;
seção crítica
number[i] := 0;
seção restante
until false;
Operating System Concepts
6.13
Silberschatz and Galvin1999
Hardware de Sincronização
•
Testa e modifica o conteúdo de uma palavra atomicamente
function Test-and-Set (var target: boolean): boolean;
begin
Test-and-Set := target;
target := true;
end;
Operating System Concepts
6.14
Silberschatz and Galvin1999
Exclusão mútua com Test-and-Set
•
•
Dado compartilhado: var lock: boolean (initially false)
Processo Pi
repeat
while Test-and-Set (lock) do no-op;
seção crítica
lock := false;
seção restante
until false;
Operating System Concepts
6.15
Silberschatz and Galvin1999
Semáforo
•
•
•
Um mecanismo de sincronização que nao implica em espera
ocupada (busy waiting).
Semáforo S – variável inteira
pode ser acessado somente através de duas operações
indivisíveis (atômicas)
wait (S): while S 0 do no-op;
S := S – 1;
signal (S): S := S + 1;
Operating System Concepts
6.16
Silberschatz and Galvin1999
Exemplo: Seção crítica de n processos
•
•
Variáveis compartilhadas
– var mutex : semaphore
– inicialmente mutex = 1
Processo Pi
repeat
wait(mutex);
seção crítica
signal(mutex);
seção restante
until false;
Operating System Concepts
6.17
Silberschatz and Galvin1999
Implementação de semáforo
•
Define um semáforo como estrutura (record)
type semaphore = record
value: integer
L: list of process;
end;
•
Suponha duas operações simples:
– block suspende o processo que a executa
– wakeup(P) recomeça a execução do processo P.
Operating System Concepts
6.18
Silberschatz and Galvin1999
Implementação de semáforos (Cont.)
•
Operações em cima de semáforos agora são definidas assim:
wait(S):
S.value := S.value – 1;
if S.value < 0
then begin
add this process to S.L;
block;
end;
signal(S): S.value := S.value + 1;
if S.value  0
then begin
remove a process P from S.L;
wakeup(P);
end;
Operating System Concepts
6.19
Silberschatz and Galvin1999
O semáforo como mecanismo geral de sincronização
•
•
•
Execute B in Pj only after A executed in Pi
Use semaphore flag initialized to 0
Code:
Operating System Concepts
Pi
Pj


A
wait(flag)
signal(flag)
B
6.20
Silberschatz and Galvin1999
Deadlock and Starvation
•
•
•
Deadlock – dois ou mais processos esperam indefinitamente por
um evento que pode ser causado somente por um dos
processos em espera.
S e Q sejam dois semáforos inicializados em 1
P0
P1
wait(S);
wait(Q);
wait(Q);
wait(S);


signal(S);
signal(Q);
signal(Q)
signal(S);
Starvation – bloqueio sem fim. Um processo nunca é removido
da fila de semáforo na qual ele fica bloqueado.
Operating System Concepts
6.21
Silberschatz and Galvin1999
Dois Tipos de Semáforos
•
Semáforo contábil – valor inteiro que se pode estender até o
infinito.
•
Semáforo binário – valor pode ser somente 0 ou 1; mais facil
de implementar.
•
É possível implementar semáforo contábil a partir de
semáforos binários.
Operating System Concepts
6.22
Silberschatz and Galvin1999
Implementando S com semáforos binários
•
•
Estruturas de dados:
var S1: binary-semaphore;
S2: binary-semaphore;
S3: binary-semaphore;
C: integer;
Initialização:
S1 = S3 = 1
S2 = 0
C = valor inicial do semáforo S
Operating System Concepts
6.23
Silberschatz and Galvin1999
Implementando S (Cont.)
•
•
wait operation
wait(S3);
wait(S1);
C := C – 1;
if C < 0
then begin
signal(S1);
wait(S2);
end
else signal(S1);
signal(S3);
signal operation
wait(S1);
C := C + 1;
if C  0 then signal(S2);
signal(S1);
Operating System Concepts
6.24
Silberschatz and Galvin1999
Problemas clássicos de Sincronização
•
•
•
Problema do buffer limitado
Problema de Escritores e Leitores
Problema dos filósofos jantando
Operating System Concepts
6.25
Silberschatz and Galvin1999
Problema do Buffer limitado
•
Dados compartilhados
type item = …
var buffer = …
full, empty, mutex: semaphore;
nextp, nextc: item;
full :=0; empty := n; mutex :=1;
Operating System Concepts
6.26
Silberschatz and Galvin1999
Bounded-Buffer Problem (Cont.)
•
Processo produtor
repeat
…
produza um item em nextp
…
wait(empty);
wait(mutex);
…
coloque o item em nextp no buffer
…
signal(mutex);
signal(full);
until false;
Operating System Concepts
6.27
Silberschatz and Galvin1999
Bounded-Buffer Problem (Cont.)
•
Processo consumidor
repeat
wait(full)
wait(mutex);
…
remove um item do buffer para nextc
…
signal(mutex);
signal(empty);
…
consume o item em nextc
…
until false;
Operating System Concepts
6.28
Silberschatz and Galvin1999
Readers-Writers Problem
•
•
Dados compartilhados
var mutex, wrt: semaphore (=1);
readcount : integer (=0);
processo escritor
wait(wrt);
…
escrevendo
…
signal(wrt);
Operating System Concepts
6.29
Silberschatz and Galvin1999
Readers-Writers Problem (Cont.)
•
Process leitor
wait(mutex);
readcount := readcount +1;
if readcount = 1 then wait(wrt);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount := readcount – 1;
if readcount = 0 then signal(wrt);
signal(mutex):
Operating System Concepts
6.30
Silberschatz and Galvin1999
Problema dos filósofos jantando
•
Dados compartilhados
var chopstick: array [0..4] of semaphore;
(=1 initially)
Operating System Concepts
6.31
Silberschatz and Galvin1999
Dining-Philosophers Problem (Cont.)
•
Filósofo i:
repeat
wait(chopstick[i])
wait(chopstick[i+1 mod 5])
…
come
…
signal(chopstick[i]);
signal(chopstick[i+1 mod 5]);
…
pensa
…
until false;
Operating System Concepts
6.32
Silberschatz and Galvin1999
Regiões críticas
•
•
Uma construção de alto nível
Uma variável v do tipo T é declarada assim:
var v: shared T
•
a variável v é acessado somente dentro de uma construção do
tipo
region v when B do S
na qual B é uma expressão booleana.
Enquanto a instrução (o bloco de instruções) S é executado,
nenhum outro processo pode acessar a variável v.
Operating System Concepts
6.33
Silberschatz and Galvin1999
Regiões críticas (Cont.)
•
•
Regiões que se referem aos mesmos variáveis excluem uma à
outra no tempo.
Quando um processo executa uma construção region, a
expressão booleana B é avaliada. Se B é verdade, a instrução S
é executada. Se é falso, o processo fica bloqueado até que B
passa a ser verdade e nenhum outro processo está na região
associada com v.
Operating System Concepts
6.34
Silberschatz and Galvin1999
Exemplo – Buffer limitado
•
Variáveis compartilhadas:
var buffer: shared record
pool: array [0..n–1] of item;
count,in,out: integer
end;
•
Processo produtor
region buffer when count < n
do begin
pool[in] := nextp;
in:= in+1 mod n;
count := count + 1;
end;
Operating System Concepts
6.35
Silberschatz and Galvin1999
Exemplo – Buffer limitado (Cont.)
•
Processo consumidor
region buffer when count > 0
do begin
nextc := pool[out];
out := out+1 mod n;
count := count – 1;
end;
Operating System Concepts
6.36
Silberschatz and Galvin1999
Implementação: region x when B do S
•
Associate with the shared variable x, the following variables:
var mutex, first-delay, second-delay: semaphore;
first-count, second-count: integer,
•
•
Mutually exclusive access to the critical section is provided by
mutex.
If a process cannot enter the critical section because the Boolean
expression B is false, it initially waits on the first-delay
semaphore; moved to the second-delay semaphore before it is
allowed to reevaluate B.
Operating System Concepts
6.37
Silberschatz and Galvin1999
Implementation (Cont.)
•
•
•
Keep track of the number of processes waiting on first-delay and
second-delay, with first-count and second-count respectively.
The algorithm assumes a FIFO ordering in the queuing of
processes for a semaphore.
For an arbitrary queuing discipline, a more complicated
implementation is required.
Operating System Concepts
6.38
Silberschatz and Galvin1999
wait(mutex);
while not B
do begin first-count := first-count + 1;
if second-count > 0
then signal(second-delay)
else signal(mutex);
wait(first-delay):
first-count := first-count – 1;
if first-count > 0 then signal(first-delay)
else signal(second-delay);
wait(second-delay);
second-count := second-count – 1;
end;
S;
if first-count >0
then signal(first-delay);
else if second-count >0
then signal(second-delay);
else signal(mutex);
Operating System Concepts
6.39
Silberschatz and Galvin1999
Monitors
•
High-level synchronization construct that allows the safe sharing
of an abstract data type among concurrent processes.
type monitor-name = monitor
variable declarations
procedure entry P1 :(…);
begin … end;
procedure entry P2(…);
begin … end;

procedure entry Pn (…);
begin…end;
begin
initialization code
end
Operating System Concepts
6.40
Silberschatz and Galvin1999
Monitors (Cont.)
•
To allow a process to wait within the monitor, a condition
variable must be declared, as
var x, y: condition
•
Condition variable can only be used with the operations wait
and signal.
– The operation
x.wait;
means that the process invoking this opeation is
suspended until another process invokes
x.signal;
– The x.signal operation resumes exactly one suspended
process. If no process is suspended, then the signal
operation has no effect.
Operating System Concepts
6.41
Silberschatz and Galvin1999
Schematic view of a monitor
Operating System Concepts
6.42
Silberschatz and Galvin1999
Monitor with condition variables
Operating System Concepts
6.43
Silberschatz and Galvin1999
Dining Philosophers Example
type dining-philosophers = monitor
var state : array [0..4] of :(thinking, hungry, eating);
var self : array [0..4] of condition;
procedure entry pickup (i: 0..4);
begin
state[i] := hungry,
test (i);
if state[i]  eating then self[i], wait,
end;
procedure entry putdown (i: 0..4);
begin
state[i] := thinking;
test (i+4 mod 5);
test (i+1 mod 5);
end;
Operating System Concepts
6.44
Silberschatz and Galvin1999
Dining Philosophers (Cont.)
procedure test(k: 0..4);
begin
if state[k+4 mod 5]  eating
and state[k] = hungry
and state[k+1 mod 5] ]  eating
then begin
state[k] := eating;
self[k].signal;
end;
end;
begin
for i := 0 to 4
do state[i] := thinking;
end.
Operating System Concepts
6.45
Silberschatz and Galvin1999
Monitor Implementation Using Semaphores
•
Variables
var mutex: semaphore (init = 1)
next: semaphore (init = 0)
next-count: integer (init = 0)
•
•
Each external procedure F will be replaced by
wait(mutex);
…
body of F;
…
if next-count > 0
then signal(next)
else signal(mutex);
Mutual exclusion within a monitor is ensured.
Operating System Concepts
6.46
Silberschatz and Galvin1999
Monitor Implementation (Cont.)
•
•
For each condition variable x, we have:
var x-sem: semaphore (init = 0)
x-count: integer (init = 0)
The operation x.wait can be implemented as:
x-count := x-count + 1;
if next-count >0
then signal(next)
else signal(mutex);
wait(x-sem);
x-count := x-count – 1;
Operating System Concepts
6.47
Silberschatz and Galvin1999
Monitor Implementation (Cont.)
•
The operation x.signal can be implemented as:
if x-count > 0
then begin
next-count := next-count + 1;
signal(x-sem);
wait(next);
next-count := next-count – 1;
end;
Operating System Concepts
6.48
Silberschatz and Galvin1999
Monitor Implementation (Cont.)
•
•
Conditional-wait construct: x.wait(c);
– c – integer expression evaluated when the wait opertion is
executed.
– value of c (priority number) stored with the name of the
process that is suspended.
– when x.signal is executed, process with smallest associated
priority number is resumed next.
Check tow conditions to establish correctness of system:
– User processes must always make their calls on the monitor
in a correct sequence.
– Must ensure that an uncooperative process does not ignore
the mutual-exclusion gateway provided by the monitor, and
try to access the shared resource directly, without using the
access protocols.
Operating System Concepts
6.49
Silberschatz and Galvin1999
Solaris 2 Operating System
•
•
•
Implements a variety of locks to support multitasking,
multithreading (including real-time threads), and multiprocessing.
Uses adaptive mutexes for efficiency when protecting data from
short code segments.
Uses condition variables and readers-writers locks when longer
sections of code need access to data.
Operating System Concepts
6.50
Silberschatz and Galvin1999