Concorrência:
Sincronização de fina granularidade
André Santos
CIn-UFPE
©André Santos, 1998-2000
Busy Waiting



Tipo de sincronização em que um
processo continuamente verifica uma
condição até que ela se torne
verdadeira
Pode ser implementada com o conjunto
de instruções de qualquer processador
moderno
Ineficiente para multiprogramação
©André Santos,
1998-2000
Busy waiting


Utilizado em dispositivos de hardware
multiprocessados
Pode ser usado para implementar
await
©André Santos,
1998-2000
O Problema da Exclusão
Mútua (Região Crítica)

N processos executam um loop infinito:
 Seção crítica
 Seção não crítica

O programa deve satisfazer a
propriedade de exclusão mútua
 instruções das regiões críticas de dois ou
mais processos não podem ser
executadas ao mesmo tempo.
©André Santos,
1998-2000
Exclusão Mútua para N
processos

N processos executando loop infinito
 Seção crítica
 Seção não crítica

Programa deve satisfazer a propriedade
de exclusão mútua
 Em um dado instante no máximo um
processo está executando sua região
crítica.
©André Santos,
1998-2000
solução: instruções adicionais


protocolo de entrada e de saída
P[i: 1..n]:: while (TRUE) {
entry protocol
critical section
exit protocol
non-critical section
}
©André Santos,
1998-2000
outras condições


um processo pode parar ou terminar
fora da região crítica, sem interferir com
outros processos.
Ausência de deadlock (ou livelock)
 se dois ou mais processos tentam entrar
em sua região crítica, um deles deve
conseguir.
©André Santos,
1998-2000
Outras condições

Ausência de espera desnecessária
 Se um processo quer entrar em sua região
crítica e os outros processos estão fora da
sua região crítica ou terminaram, ele não
será impedido de entrar

Entrada eventual (ausência de
starvation)
 se um processo quer entrar na região
crítica, em algum momento ele entrará.
©André Santos,
1998-2000
Tentativa 1: variável Turn

int Turn = 1;
void P1() {
void P2() {
while (TRUE) {
while (TRUE) {
/* Non_Cr_S_1 */
/* Non_Cr_S_2 */
while (Turn != 1) {}; while (Turn != 2) {};
/* Crit_S_1 */
/* Crit_S_2 */
Turn = 2;
Turn = 1;
}
}
}
}
©André Santos,
1998-2000
Verificação da solução

A solução satisfaz o requisito de
exclusão mútua
 assuma que ela não satisfaz 
contradição

A solução não entra em deadlock
 assuma que o programa está em deadlock
 contradição
©André Santos,
1998-2000
Verificação da solução

Não há starvation
 ao sair da região crítica cada processo
passa a vez ao outro
©André Santos,
1998-2000
Verificação da solução

A solução pode falhar se um processo
parar fora da região crítica
 se um processo pára em sua região não
crítica, o outro não pode prosseguir.


Corrotinas
Execução “sincronizada”
©André Santos,
1998-2000
Tentativa 2: 2 variáveis

int In1, In2 = FALSE;
void P1 () {
void P2 () {
while (TRUE)
while (TRUE)
{ Non_Cr_S_1;
{ Non_Cr_S_2;
while (In2) {};
while (In1) {};
In1 = TRUE;
In2 = TRUE;
Crit_S_1;
Crit_S_2;
In1 = FALSE;
In2 = FALSE;
}
}
}
}
©André Santos,
1998-2000
Verificação da solução

P1 e P2 podem entrar na seção crítica
simultaneamente






P1 verifica In2 e encontra In2 = FALSE
P2 verifica In1 e encontra In1 = FALSE
P1 seta In1 para TRUE
P2 seta In2 para TRUE
P1 entra na seção crítica
P2 entra na seção crítica
©André Santos,
1998-2000
Tentativa 3:

Int In1, In2 = FALSE;
void P1 () {
void P2() {
while (TRUE)
while (TRUE)
{ Non_Cr_S_1;
{ Non_Cr_S_2;
In1 = TRUE;
In2 = TRUE;
while (In2) {};
while (In1) {};
Crit_S_1;
Crit_S_2;
In1 = FALSE;
In2 = FALSE;
}
}
}
}
©André Santos,
1998-2000
Verificação da solução

A solução satisfaz a propriedade de
exclusão mútua
©André Santos,
1998-2000
Verificação da solução

A solução pode entrar em deadlock




P1 atribui TRUE a In1
P2 atribui TRUE a In2
P1 testa In2 e fica no loop
P2 testa In1 e fica no loop
©André Santos,
1998-2000
Tentativa 4: passando a vez

Int In1, In2 = 1;
void P1 () {
while (TRUE)
{ Non_Cr_S_1;
In1 = TRUE;
while (In2)
{ In1 = FALSE;
In1 = TRUE;
};
Crit_S_1;
In1 = FALSE;
}
}
void P2 () {
while (TRUE)
{ Non_Cr_S_2;
In2 = TRUE;
while (In1)
{ In2 = FALSE;
In2 = TRUE;
};
Crit_S_2;
In2 = FALSE;
}
}
©André Santos,
1998-2000
Verificação da solução

Um processo pode ser starved




P1 seta In1 para TRUE
P2 seta In2 para TRUE
P2 verifica In1 e seta In2 para FALSE
P1 faz um ciclo completo: verifica In2,
entra na região crítica, seta In1 para
FALSE, executa região não-crítica, seta
In1 para TRUE
 P2 seta In2 para TRUE...
©André Santos,
1998-2000
Verificação da solução



A solução pode entrar em livelock
deadlock: nenhuma sequência resulta
em sucesso
livelock: existe uma ou mais sequências
que evita que os processos entrem na
região crítica
©André Santos,
1998-2000
Entretanto...


É possível inserir um delay entre as
mudanças nas variáveis, para aumentar
a possibilidade de context-switch
ocorrer com variável alterada.
Uso prático: algorítimo semelhante é
usado em redes Ethernet
©André Santos,
1998-2000
Solução Ideal 1

int In1, In2 = FALSE;
void P1 () {
void P2 () {
while (TRUE)
while (TRUE)
{ Non_Cr_S_1;
{ Non_Cr_S_2;
<await not In2 ->
<await not In1 ->
In1 = TRUE;>
In2 = TRUE;>
Crit_S_1;
Crit_S_2;
In1 = FALSE;
In2 = FALSE;
}
}
}
}
©André Santos,
1998-2000
Solução Ideal 2

int lock = FALSE;
void P1 () {
void P2 () {
while (TRUE)
while (TRUE)
{ Non_Cr_S_1;
{ Non_Cr_S_2;
<await not lock ->
<await not Iock ->
lock = TRUE;>
Iock = TRUE;>
Crit_S_1;
Crit_S_2;
lock = FALSE;
lock = FALSE;
}
}
}
}
©André Santos,
1998-2000
Exclusão mútua assistida por
hardware


load e store em uma única instrução
test e set:
 TS(lock, cc) = <cc := lock; lock := true>

Exchange(A,B)
 = <Temp := A; A := B; B := Temp;>
©André Santos,
1998-2000
Exclusão mútua com Test and Set

int lock = FALSE;
void P1 () {
int C1;
while (TRUE)
{ Non_Cr_S_1;
TS (lock,C1);
while (C1) {
TS (lock,C1);
};
Crit_S_1;
lock = FALSE;
}
}
void P2 () {
int C2;
while (TRUE)
{ Non_Cr_S_2;
TS (lock,C2);
while (C2) {
TS (lock,C2);
};
Crit_S_2;
lock = FALSE;
}
}
©André Santos,
1998-2000
Vantagens

Funciona facilmente para vários
processos.
©André Santos,
1998-2000
Desvantagens


Escrita frequente nas variáveis
Todos os processos acessam a mesma
variável lock.
©André Santos,
1998-2000
Exclusão mútua com Exchange

int InCS = FALSE;
void P1 () {
int L1 = TRUE;
while (TRUE)
{ Non_Cr_S_1;
Exchng (L1,InCS);
while (L1) {
Exchng (L1,InCS);
};
Crit_S_1;
Exchng (L1,InCS);
}
}
void P2 () {
int L2 = TRUE;
while (TRUE)
{ Non_Cr_S_2;
Exchng (L2,InCS);
while (L2) {
Exchng (L2,InCS);
};
Crit_S_2;
Exchng (L2,InCS);
}
}
©André Santos,
1998-2000