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

Imágen de pdf Sistemas Operativos Tema 3. Concurrencia - Conceptos generales - Sincronización con semáforos

Sistemas Operativos Tema 3. Concurrencia - Conceptos generales - Sincronización con semáforosgráfica de visualizaciones

Actualizado el 21 de Marzo del 2018 (Publicado el 23 de Febrero del 2018)
418 visualizaciones desde el 23 de Febrero del 2018
2,0 MB
59 paginas
Creado hace 5a (01/01/2015)
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
  • Links de descarga
http://lwp-l.com/pdf9006

Comentarios de: Sistemas Operativos Tema 3. Concurrencia - Conceptos generales - Sincronización con semáforos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad