PDF de programación - Sistemas Operativos Tema 3. Concurrencia - Conceptos generales - Sincronización con semáforos

Sistemas Operativos
Tema 3. Concurrencia
Conceptos generales

Sincronización con semáforos

© 1998-2015 José Miguel Santos – Alexis Quesada – Francisco Santana

1

Contenidos

n Sistemas concurrentes
n El problema de la sección crítica
n Semáforos

2

Referencias bibliográficas

n Fundamentos de Sistemas Operativos

q S. Candela, C.R. García, A. Quesada, F.J. Santana, J.M. Santos.

Thomson, 2007

q Capítulo 3

n Programación Concurrente

q J.T. Palma, M.C. Garrido, F. Sánchez, A. Quesada. Paraninfo, 2003
q Capítulos 1, 2, 3, 4, 5 y 6

n Principles of Concurrent and Distributed Programming

q M. Ben-Ari. Prentice Hall, 1990

n Concurrent Programming

q A. Burns, G. Davies. Addison-Wesley, 1993
q Capítulo 7

3

Modelo del sistema

n Conjunto de procesos cooperativos

q Red de cajeros automáticos
q Sistema de reserva de billetes
q Servidor de impresión
q Navegador web (pestañas, plugins…)
q ...

4

¿Qué es concurrencia?

n Definición de diccionario: coincidir en el espacio

o en el tiempo dos o más personas o cosas.

n En Informática, se habla de concurrencia

cuando hay una
existencia simultánea de varios procesos en
ejecución.

n Ojo, concurrencia existencia simultánea no

implica ejecución simultánea.

5

Paralelismo y concurrencia

n El paralelismo es un caso particular de la

concurrencia: cuando hay ejecución
simultánea de instrucciones en varios
procesadores.

n Computación distribuida: paralelismo en

sistemas distribuidos o en red.

6

Programación concurrente

n ¿Cómo expresamos la concurrencia al

programar?
q Una API (ej. pthreads)
q Objetos concurrentes (ej. Java)
q Sentencias concurrentes (ej. Ada, Go…)

7

Sentencia concurrente

n En estas diapos, expresaremos las

actividades concurrentes con una sentencia
concurrente:

void desayunar() {

preparar_ingredientes();
CONCURRENTE {

preparar_café();
calentar_tostadas();
calentar_leche();

}
comer();

}

8

Procesos cooperativos

n Necesidades de sincronización y

comunicación

n Los procesos concurrentes tendrán necesidad

de comunicarse información
q Si son hilos, pueden comunicarse mediante

variables compartidas.

n Además, será necesario en ocasiones detener

a un proceso hasta que se produzca un
determinado evento o se den ciertas
condiciones à sincronización

9

Ejemplo 1: operaciones bancarias
n Variable compartida por dos procesos

int saldo;

void ingreso(int N) {
saldo = saldo + N;

}

void reintegro(int N) {

if (saldo >= N)

saldo = saldo - N;

else

ERROR();

}

main() {

saldo = 0;
CONCURRENTE {

ingreso(100);
reintegro(50);

}

}

10

Ejemplo 2: sensor de paso de
vehículos

int contador = 0;

void cuenta_coches() {

while (true) {

main() {

CONCURRENTE {

cuenta_coches();
imprime_contador();

…espera que pase un coche…
contador++;

}

}

void imprime_contador() {

while (true) {

sleep(3600); // espera una hora
printf("coches que han pasado: %d\n",contador);
contador = 0;

}

}

}

}

11

Ejemplo 3: búfer limitado

const int N=...;
class Item {...};
Item buffer [N];
int entra=0, sale=0;
int pendientes=0;

Productor

Consumidor

while (true) {

while (true) {

Item* cosa = producir_algo();
while (pendientes==N) {}
buffer[entra] = cosa;
entra = (entra+1)%N;
pendientes++;

while (pendientes==0) {}
Item* cosa = buffer[sale];
sale = (sale+1)%N;
pendientes--;
consumir(cosa);

}

}

12

Problema al modificar datos
compartidos

n Ambas rutinas son correctas si se ejecutan por separado pero podrían

NO funcionar si se ejecutan de manera concurrente

n Supongamos que las instrucciones de incremento y decremento se

ejecutan al mismo tiempo. Veamos el código máquina que el
compilador ha generado para cada instrucción:

contador = contador + 1
(A) LW $3,contador
(B) ADD $3,$3,1
(C) SW $3,contador

contador=contador-1
(D) LW $4,contador
(E) ADD $4,$4,1
(F) SW $4,contador

Si el contador vale inicialmente 5 y se ejecutan las instrucciones en este orden:
(A) » (B) » (D) » (E) » (F) » (C),
el contador acaba valiendo 4.
Dependiendo del orden de ejecución de las instrucciones, el contador puede acabar
valiendo 4, 5 o 6 à esto no es un comportamiento deseable

13

EL PROBLEMA DE LA
SECCIÓN CRÍTICA

14

Sección crítica: modelo del
sistema
n N procesos intentan acceder a un recurso

compartido en un bucle infinito:

while (true) {

Sección_No_Crítica (SNC);
Pre_Protocolo();
Sección_Crítica (SC);
Post_Protocolo();

}

n Sección crítica: segmento de código donde se
accede a datos compartidos con otros procesos.
n Requisito: nunca debe haber más de un proceso

dentro de la sección crítica (exclusión mutua).

15

Requisitos de la solución

n Exclusión mutua
n Progreso: si ningún proceso está en sección
crítica y hay procesos que desean entrar en su
s.c., sólo estos últimos participarán en la
decisión y ésta se tomará en un tiempo finito.

n Espera limitada: hay un límite para el número

de veces que otros procesos pueden
adelantarse a un proceso que quiere entrar en
s.c.

16

Importante

n No podemos suponer nada sobre la

velocidad relativa de los procesos, ni el orden
de ejecución.

17

Solución primitiva:
inhibir las interrupciones
n Antes de que un proceso entre en su sección

crítica, se inhiben las interrupciones
n Así es imposible que el proceso sea
expulsado de la CPU mientras está
accediendo al dato compartido

n Al salir de la SC, se rehabilitan las

interrupciones

18

Inhibir las interrupciones:
inconvenientes
n Mientras un proceso está en SC, se

suspende toda la concurrencia en el sistema
à perjudica a los procesos que no están
intentando entrar en SC

n NO sirve en multiprocesadores (no se puede

enviar una señal simultánea a todos los
procesadores)

n NO garantiza espera limitada

19

Soluciones software con espera
activa (busywaiting)

n La sincronización se basa en que un proceso
espera mediante la comprobación continua de
una variable.

while (no_puedo_seguir) { }

n Ojo, la CPU se mantiene ocupada mientras el

proceso espera (ineficiente).

20

Intento ingenuo:
usar un indicador de disponibilidad

// variable global
// indica si la sección crítica está libre
bool ocupado = false;

// código que ejecuta cada proceso
while (true) {

… sección no crítica …
while (ocupado) {}
ocupado = true;
… sección crítica …
ocupado = false;

}

21

Primer intento serio:
variable turno
(solución para dos procesos)

int turno = 1;

while (true) {

SNC1;

while (true) {

SNC2;

while (turno!=1) {}

while (turno!=2) {}

SC1;
turno=2;

}

SC2;
turno=1;

}

proceso 1

proceso 2

22

Discusión del primer intento

n ¿Exclusión mutua?
n ¿Espera limitada?
n ¿Progreso?

23

Segundo intento: avisadores

bool quiere1=false, quiere2=false;

while (true) {

SNC1;
quiere1=true;
while (quiere2) {}
SC1;
quiere1=false;

}

while (true) {

SNC2;
quiere2=true;
while (quiere1) {}
SC2;
quiere2=false;

}

proceso 1

proceso 2

24

Algoritmo de Peterson –
Funciona (para 2 procesos)

bool quiere1=false, quiere2=false;
int turno = 1;

while (true) {

while (true) {

SNC1;
quiere1 = true;
turno = 2;
while
(quiere2 && turno==2) {}
SC1;
quiere1 = false;

SNC2;
quiere2 = true;
turno = 1;
while
(quiere1 && turno==1) {}
SC2;
quiere2 = false;

}

}

25

Solución para N procesos:
Algoritmo de la panadería (Lamport)

bool cogiendonumero [N] = { [0..N-1] = false };
int num[N] = { [0..N-1] = 0 };

// código del proceso "i"
while (true) {

Sección no crítica (i);
// cojo número
cogiendonumero[i] = true;

num[i] = 1 + MAX(num(1) ... num(n));

cogiendonumero[i] = false;
// Comparo mi número con los de los demás procesos
for (int j=0;j<N;j++) {
if (i==j) continue; // no me comparo conmigo mismo
while (cogiendonumero[j]) {} // por si lo he pillado cogiendo número
if (num[j]==0) continue; // si no está interesando, sigo con otro
// me mantengo en espera si j ha cogido un número menor que el mío
// o tiene el mismo número que yo, pero j<i
while ( num[j]<num[i] || (num[j]==num[i] && j<i) ) {}

}
Sección crítica (i);
num[i] = 0;

}

26

Instrucciones hardware atómicas

n Inventadas en los años 60.
n Permiten evaluar y asignar un valor a una

variable de forma atómica.
q test-and-set(B): Pone B a true y devuelve el

antiguo valor de B.

q SWAP(A,B): Intercambia los valores de A y B.
n Si disponemos de estas instrucciones, se

simplifica muchísimo el problema de la
sección crítica.

27

Algoritmo básico con test-and-set

bool ocupado = false;

while (true) {

Sección no crítica;
while ( Test_and_Set(ocupado) ) {}
Sección crítica;
ocupado = false;

}

OJO: no garantiza espera indefinida

28

Algoritmo básico con SWAP

bool ocupado = false;

while (true) {

Sección no crítica;
bool aux=true; // variable local
while (aux) {

SWAP(ocupado,aux);

}
Sección crítica;
ocupado=false;

}

29

Solución completa (test-and-set)

bool esperando[N] = { [0 … N] = false };
bool cerradura = false;
while (true) {

SNCi;
esperando[i] = true;
bool llave = true;
while (esperando[i] && llave) {
llave = test_and_set(cerradura);
}

esperando[i] = false;
SCi;
int j=(i+1)%N;
while ( j!=i && !esperando[j] ) {
}
if (j==i)
else

cerradura = false;
esperando[j] = false;

j=(j+1)%N;

}

30

SEMÁFOROS

31

Herramientas de sincronización

n Basadas en memoria compartida

q Inhibición de Interrupciones
q Espera activa
q Semáforos
q Regiones críticas
q Monitores

n Basadas en el paso de mensajes

q Canales
q Buzones

32

Semáforos

n Edsger Dijkstra, 1965
n Objetivo: herramienta universal para
sincronizar procesos, que sirva como
componente básico para construir algoritmos
concurrentes

33

Concepto de semáforo

n Dijkstra lo definió como una variable entera

S con dos operaciones atómicas:

n P(S): esperar a que S>0;

S:=S-1;

n V(S): S:=S+1;

n NOTA: el semáforo no puede adquirir

valores negativos

34

Semáforos: otras notaciones

n P(s) = wait(s) = espera (s)
n V(s) = signal(s) = señal (s)

n (se utilizan varias notaciones para las

operaciones de los semáforos, pero todas
significan lo mismo)

35

Ejemplo: secci