Concorrência
Concorrência e Sincronização
André Santos
CIn-UFPE
©André Santos, 2000
Notação: Declarações




type days = (SUN,MON,...,SAT)
var i : int := 0, x : real,
s : string(10)
var forks[1:5]:bool := ([5] false)
type student =
rec (name:string(30)
age : int
classes[1:5] : string(15))
©André Santos, 2000
Notação: Statements





skip
vector[1] := n + 2
v1 :=: v2
x := x+1; y := y-1
if B1 -> S1
[] ...
[] Bn -> Sn
fi
©André Santos, 2000
Notação: Statements


do B1 -> S1
[] ...
[] Bn -> Sn
od
MDC:
x := X; y := Y
do x > y -> x := x – y
[] y > x -> y := y – x
od
©André Santos, 2000
Notação: Statements


fa i:=1 to n -> vector[i]:=0
af
procedure inc (var x:int)
x := x + 1
end
©André Santos, 2000
Notação: Concorrência



co S1 // ...
x := 0; y :=
co x:= x + 1
z := x + y
co i := 1 to
// Sn oc
0
// y:= y + 1 oc
n -> a[i]:=0 oc
©André Santos, 2000
Notação: Concorrência

var a[1:n], b[1:n] : int
Largest::
var max:int
max:=a[1]
fa j:=2 to n st max < a[j]
-> max := a[j]
af
©André Santos, 2000
Notação: Concorrência

Sum[i:1..n]::
b[i] := a[1]
fa j:=2 to i
-> b[i] := b[i] + a[j]
af
©André Santos, 2000
Políticas de Escalonamento e
Fairness


Várias das propriedades de liveness
dependem de fairness.
O escalonamento se preocupa em como
garantir que processos tenham chance de
prosseguir, independentemente das ações
dos demais processos.
 A existência de várias ações elegíveis fazem com
que uma política de escalonamento seja usada
para definir qual será executada.
©André Santos, 2000
Atomicidade de fina
granularidade



Ação atômica faz uma transformação
indivisível no estado.
Qualquer estado intermediário na
implementação da ação deve ser invisível
para os outros processos.
Ação atômica de fina granularidade é
implementada diretamente pelo hardware em
que o programa concorrente executa.
©André Santos, 2000
Exemplo: atribuição


y:=0; z:=0
co x := y+z // y :=1; z:=2 oc
x = 0,1,2 ou 3?
©André Santos, 2000
Assumir nos exemplos




Valores de tipos básicos são lidos e escritos
como uma ação atômica
Valores são manipulados carregando-os em
registros, executando operações e depois
guardando os resultados na memória.
Cada processo tem seu conjunto de registros
(chaveamento de contexto)
Resultados intermediários são guardados em
registros ou em memória.
©André Santos, 2000
Especificando sincronização





Objetivo: possibilitar criação de ações
atômicas de maior granularidade.
Exemplo: modificação simultânea em
um banco de dados
<expressão>
<await B -> S>
<await (s>0) -> s := s-1>
©André Santos, 2000
Especificando sincronização





Exclusão mútua
<x := x+1; y := y+1>
Sincronização de condição
<await count > 0>
Ação atômica incondicional x
condicional
©André Santos, 2000
Políticas de Escalonamento e
Fairness

Exemplo:
var continue := true
Loop:: do continue -> skip od
Stop:: continue := False

O que acontece se o escalonador faz o
chaveamento de contexto (context
switch) apenas quando um processo
termina ou fica em espera?
©André Santos, 2000
Unconditional Fairness


Uma política de escalonamento é
incondicionalmente justa se toda ação
atômica incondicional que é elegível é
executada em algum momento.
Para o exemplo anterior, round-robin ou
execução paralela em
multiprocessadores seria
incondicionalmente justa.
©André Santos, 2000
Weak Fairness


Na presença de ações atômicas
condicionais, é necessário hipóteses mais
fortes para garantir que os processos vão
progredir.
Uma política de escalonamento é fracamente
justa se ela é incondicionalmente justa e toda
ação atômica condicional elegível é
executada em algum momento, assumindo
que sua guarda se torne verdadeira e não
seja subsequentemente mudada para falso
por outro processo.
©André Santos, 2000
Weak Fairness


Round-robin e timeslicing são
fracamente justas.
O processo em algum momento verá
que sua condição de espera se tornou
verdadeira.
©André Santos, 2000
Strong Fairness


Se a guarda pode mudar - de falsa para
verdadeira e novamente para falsa –
enquanto um processo espera.
Uma política de escalonamento é fortemente
justa se ela é incondicionalmente justa e toda
ação atômica condicional elegível é
executada em algum momento, assumindo
que a guarda é infinitamente frequentemente
verdadeira.
©André Santos, 2000
Strong Fairness

Exemplo:
var continue := true,
try := false;
Loop::
do continue -> try := true;
try := false od
Stop:: <await try ->
continue := false>
©André Santos, 2000
Strong Fairness

De forma geral não é viável na prática:
 Alternar a cada instrução
 Escalonador de um multiprocessador

Não é fortemente justo:
 Round-robin e timeslicing
©André Santos, 2000
Strong Fairness

Instâncias específicas:
<await (s > 0) -> s := s - 1>

2 processos de espera, demais
incrementam s
Escalonador FCFS (First Come First
Served)

©André Santos, 2000