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) { main() {

saldo = saldo + N; saldo = 0;
} CONCURRENTE {
ingreso(100);
void reintegro(int N) { reintegro(50);
if (saldo >= N) }
saldo = saldo - N; }
else
ERROR();
}

10
Ejemplo 2: sensor de paso de
vehículos
int contador = 0; main() {
CONCURRENTE {
void cuenta_coches() { cuenta_coches();
while (true) { 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==0) {}
while (pendientes==N) {} Item* cosa = buffer[sale];
buffer[entra] = cosa; sale = (sale+1)%N;
entra = (entra+1)%N; pendientes--;
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 contador=contador-1

(A) LW $3,contador (D) LW $4,contador
(B) ADD $3,$3,1 (E) ADD $4,$4,1
(C) SW $3,contador (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 (busy waiting)

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) { while (true) {

SNC1; SNC2;

while (turno!=1) {} while (turno!=2) {}

SC1; SC2;
turno=2; 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) { while (true) {

SNC1; SNC2;
quiere1=true; quiere2=true;
while (quiere2) {} while (quiere1) {}
SC1; SC2;
quiere1=false; 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; SNC2;
quiere1 = true; quiere2 = true;
turno = 2; turno = 1;
while while
(quiere2 && turno==2) {} (quiere1 && turno==1) {}
SC1; SC2;
quiere1 = false; 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] ) {
j=(j+1)%N;
}
if (j==i)
cerradura = false;
else
esperando[j] = false;
}

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ón crítica resuelta
con semáforos
n Usamos un único semáforo inicializado a
uno.
begin
Sección no crítica
wait(s)
Sección crítica
signal(s)
end;

36
Semáforos: esperar por eventos
y condiciones
n Se asocia un semáforo, inicializado a cero, al evento
por el que queremos esperar. Cuando un proceso ha
hecho que se cumpla una determinada condición, lo
indica ejecutando un signal(c). Un proceso esperará
a que la condición sea cierta mediante un wait(c).

P1 P2
begin begin
S1; R1;
signal(c); wait(c);
S2; R2;
end; end;

37
Semáforos: ejercicios
n Ejercicios
q a.-) Resolver el problema de la sección crítica con n
procesos
q b.-) Resolver diversos problemas de sincronización
n b.1.-) Sean P1 y P2 dos procesos concurrentes. Modificar el
código de ambos procesos de forma que el conjunto de
sentencias R2 del proceso 2 se ejecute después de que se
haya ejecutado el conjunto de sentencias S1 del proceso 1.

P1 P2
begin begin
S1; R1;
S2; R2;
end; end;

38
Semáforos: ejercicios
q b.2.-) Realizar un pequeño programa que se
ajuste al siguiente diagrama (o grafo) de
precedencia (suponiendo que disponemos de las
herramientas siguientes: sentencia concurrente
cobegin/coend )

A C

B D

39
Semáforos: ejercicios

q b.3.-) Realizar un pequeño programa que se

ajuste al siguiente diagrama (o grafo) de
precedencia (suponiendo que disponemos de las
herramientas siguientes: sentencia concurrente
cobegin/coend y semáforos)

A C

B D

40
Semáforos:
implementación con espera activa
n También llamados spinlocks

wait(s):
while s<=0 do nada;
s:=s-1;

signal(s):
s:=s+1;

41
Semáforos:
implementación sin espera activa
n Suponemos que el SO proporciona unas operaciones
para bloquear y desbloquear procesos
type Semáforo is record
valor:integer;
L: Lista<Proceso>;
end record;

wait(s): signal(s):
s.valor := s.valor-1; s.valor := s.valor+1;
if s.valor<0 then if s.valor<=0 then
L.insertar(procesoActual); L.extraer(proceso);
bloquear(procesoActual); despertar(proceso);
end if; end if;

42
Semáforos: la implementación
debe garantizar atomicidad
n Es crítico que las operaciones se ejecuten
de forma atómica
n Entorno uniprocesador:
q Inhibir interrupciones
n Entorno multiprocesador:
q Instrucciones hardware especiales
q Aplicar un algoritmo de sección crítica con
espera activa

43
Semáforos binarios

n Los semáforos vistos reciben el nombre de

semáforo general o semáforo de conteo
n Un semáforo que sólo puede tomar los
valores 0 y 1 recibe el nombre de semáforo
binario

44
Ejercicio

n Implementación de un semáforo de conteo a

partir de semáforos binarios

45
PROBLEMAS CLÁSICOS DE
SINCRONIZACIÓN

46
Problemas clásicos de
sincronización
n Problema del búfer limitado
n Problema de los lectores y escritores
q 1er problema: prioridad para los lectores
q 2º problema: prioridad para los escritores
n Problema de los filósofos comensales

47
 Búfer limitado
N: constant integer:=...;
type elemento is ...;
buffer: array(0..N-1) of elemento;
entra,sale: mod N:=0;
hayElementos: Semaphore :=0;
hayHuecos: Semaphore :=N;
Productor cerradura: Semaphore :=1;
Consumidor
loop loop
... wait(hayElementos);
producir un elemento elem wait(cerradura);
... elem:=buffer(sale);
wait(hayHuecos); sale:=sale+1;
wait(cerradura); signal(cerradura);
buffer(entra):=elem; signal(hayHuecos);
entra:=entra+1; ...
signal(cerradura); consumir elemento elem
signal(hayElementos); ...
end loop; end loop;

48
Lectores y escritores

n Esquema útil para gestionar el acceso a una

base de datos:
q Puede haber varios lectores accediendo a la BD
de forma concurrente
q Sólo puede haber un escritor trabajando
q No puede haber lectores y escritores al mismo
tiempo
q … y si se puede, que no haya inanición

49
Lectores y escritores:
dos variantes
n Primera variante: prioridad para los lectores
q Si un escritor está esperando, se le pueden
adelantar otros lectores
q Ojo, riesgo de inanición para los escritores
n Segunda variante: prioridad para los
escritores
q Si hay escritores esperando por la BD, los
lectores que van llegando nuevos se deben
esperar hasta que todos los escritores finalicen
q Ahora hay riesgo de inanición para los lectores

50
 Lectores y escritores: 1ª variante
cerradura: Semaphore :=1;
escritura: Semaphore :=1;
nlectores: natural :=0;
Lector Escritor
loop loop
wait(cerradura); wait(escritura);
nlectores:=nlectores+1; ESCRIBIR EN LA BD;
if nlectores=1 then signal(escritura);
wait(escritura); end loop;
signal(cerradura);
LEER DE LA BD;
wait(cerradura);
nlectores:=nlectores-1;
if nlectores=0 then
signal(escritura);
signal(cerradura);
end loop;

51
Lectores y escritores: 2ª variante
cerrojo : Semaphore := 1;
escribiendo : boolean := false;
nlec,nesc : natural := 0;
Escritor
Lector wait(cerrojo);
wait(cerrojo); nesc := nesc + 1;
while escribiendo or while escribiendo or
nesc>0 loop nlec>0 loop
signal(cerrojo); signal(cerrojo);
wait(cerrojo); wait(cerrojo);
end loop; end loop;
nlec := nlec + 1; nesc := nesc - 1;
signal(cerrojo); escribiendo := true;
… leer de la BD … signal(cerrojo);
wait(cerrojo); … escribir en la BD …
nlec := nlec – 1; wait(cerrojo);
signal(cerrojo); escribiendo := false;
signal(cerrojo);

52
Los filósofos (the dining philosophers)

53
Los filósofos: modelo simple

palillo: array(0..4) of Semaphore := (others=>1);

loop
wait(palillo(i));
wait(palillo(i+1 mod 5));
...
COMER;
...
signal(palillo(i));
signal(palillo(i+1 mod 5);
...
PENSAR;
...
end loop;

54
Filósofos: ojo al interbloqueo

n La solución anterior puede entrar en un

estado de bloqueo mutuo entre todos los
filósofos à interbloqueo
n Posibles soluciones:
q Algoritmo asimétrico filósofos pares/impares
q Impedir a más de cuatro filósofos entrar a pedir
los palillos
q Coger los dos palillos de forma atómica (o coges
los dos, o no coges ninguno)

55
Los semáforos ayudan, pero
tienen limitaciones…
n Los semáforos son una herramienta de
bajo nivel, que requiere un uso
disciplinado y cuidadoso.
n Es muy fácil cometer errores de uso con
semáforos.
n Veamos algunos ejemplos…

56
¿dónde está el fallo?

Sem = 0

P (sem)
… sección crítica …
V (sem)

57
¿dónde está el fallo?

Sem = 1

void rutina_en_exclusion_mutua () {
P (Sem)
… código de sección crítica
if ( error ) return;
… más código de sección crítica
V (sem)
}

58
Más problemas…

Dos procesos que acceden a recursos compartidos:

¿qué ocurre al ejecutarlos al mismo tiempo?

Proceso 1 Proceso 2
P (impresora) P (disco)
P ( disco ) P ( impresora )
… usar disco e impresora … usar disco e impresora
V (disco) V (impresora)
V (impresora) V (disco)

59