PDF de programación - Tema 3 - Sincronización entre Procesos - Sistemas operativos II

SISTEMAS OPERATIVOS II

TEMA 3. Sincronización entre Procesos

Área de Arquitectura y Tecnología de Computadores

Escuela Universitaria Politécnica de Teruel

http://????.????.es/SOII/

Sincronización entre procesos

Objetivos:

Entender el problema de la sección crítica

Entender los requisitos que debe cumplir la

solución al problema de la sección crítica

Conocer las soluciones hardware y software del

problema de la sección crítica

Conocer los tres problemas clásicos de

sincronización

Conocer algunos mecanismos de sincronización

de alto nivel

1

3

Sincronización entre procesos

Bibliografía:

Silberschatz & Galvin: Sistemas Operativos

Capítulo 6: Sincronización de procesos

Sincronización entre procesos

Introducción

El problema de la sección crítica

Sincronización hardware

Semáforos

Problemas clásicos de sincronización

Regiones críticas

Monitores

2

4

Introducción

“El modelo de procesos”

Sistema con un conjunto de procesos secuenciales

cooperantes que se ejecutan asíncronamente y pueden
compartir datos

Procesos independientes:

Son procesos que no afectan ni pueden ser afectados por otros

procesos en ejecución

Ejemplo: Procesos que se ejecutan en diferentes máquinas no

conectadas en red

5

Introducción

“El modelo de procesos”
Problema: “La concurrencia”

El acceso concurrente a datos compartidos puede llevar a la

inconsistencia de los mismos

Condición de carrera: situación en la que varios procesos

acceden a, y manipulan, los mismos datos de forma concurrente,
y el resultado de la ejecución depende del orden en el que se
produce el acceso

Solución: “Sincronización”

Para mantener la consistencia de los datos debemos asegurar la

ejecución ordenada de los procesos cooperantes

7

Introducción

“El modelo de procesos”

Procesos cooperantes:

Son procesos que pueden afectar o ser afectados por la

ejecución de otros procesos

Ejemplos:

Proceso que comparten código y datos: threads
Procesos que comparten datos a través del sistema de ficheros

Propiedades

Comportamiento no determinista

Puede no ser reproducible su ejecución

Introducción

Ejemplo: Problema de un productor consumidor con

buffer limitado

Proceso productor

repeat
. . .
produce item en var nextp
. . .
send(consumidor, nextp);

until false;

Proceso consumidor

repeat

receive(productor, nextc);
. . .
consume item en var nextc
. . .

until false;

6

8

Introducción

Introducción

Ejemplo: Problema de un productor consumidor con

buffer limitado

Primera solución: Memoria compartida

Datos compartidos

var n;
type item = … ;
var buffer : array[0 … n-1] of item;
in, out : 0 … n-1;

int := 0;
out := 0;

Ejemplo: Problema de un productor consumidor con

buffer limitado

Proceso productor

repeat

… … …
produce un item en var nextp
… … …
while in+1 mod n = out do no-op;
buffer[in] := nextp;
in := in+1 mod n;

until false;

9

10

Introducción

Introducción

Ejemplo: Problema de un productor consumidor con

buffer limitado

Proceso consumidor

repeat

while in = out do no-op;
nextc := buffer[out];
out := out+1 mod n;
… … …
consume un item en var nextc
… … …

until false;

Problema: sólo se utilizan n-1 posiciones
Problema: sólo se utilizan n-1 posiciones
del buffer
del buffer
11

Ejemplo: Problema de un productor consumidor con

buffer limitado

Segunda solución: Memoria compartida

Datos compartidos

var n;
type item = … ;
var buffer : array[0 … n-1] of item;
in, out : 0 … n-1;
counter : 0 … n;

int := 0;
out := 0;
counter := 0;

12

Introducción

Introducción

Ejemplo: Problema de un productor consumidor con

buffer limitado

Ejemplo: Problema de un productor consumidor con

buffer limitado

Proceso productor

repeat

… … …
produce un item en var nextp
… … …
while counter = n do no-op;
buffer[in] := nextp;
in := in+1 mod n;
counter := counter + 1;

until false;

Proceso consumidor

repeat

while counter = 0 do no-op;
nextc := buffer[out];
out := out+1 mod n;
counter := counter - 1;
… … …
consume un item en var nextc
… … …

until false;

13

14

Introducción

Si productor y consumidor se ejecutan

concurrentemente, ¿la solución es válida?

NO

counter := counter + 1;

counter := counter - 1;

reg1 := counter;
reg1 := reg1 + 1;
counter := reg1;

P(T1)
P(T2)
P(T3)

reg1 := counter;
reg1 := reg1 - 1;
counter := reg1;

C(T1)
C(T2)
C(T3)

Posible ejecución:

Posible ejecución:

Posible ejecución:

P(T1)
P(T2)
P(T3)
C(T1)
C(T2)
C(T3)

P(T1)
P(T2)
C(T1)
C(T2)
P(T3)
C(T3)

P(T1)
P(T2)
C(T1)
C(T2)
C(T3)
P(T3)

15

El problema de la sección crítica

Considerar un sistema formado por n procesos:
{P0, P1, … …, Pn-1} que usan una serie de datos
compartidos

Def.- Se denomina sección crítica al trozo de código

de cada proceso en el que se accede a los datos
compartidos

Característica del sistema:

Cuando un proceso está ejecutando el código de su sección

crítica, ningún otro proceso puede ejecutar el código de su
sección crítica

16

El problema de la sección crítica

El problema de la sección crítica

Hipótesis generales:

Cada proceso se ejecuta a velocidad no nula

No se hace ninguna hipótesis sobre la velocidad relativa de

los n procesos

Las instrucciones de lenguaje máquina se ejecutan

atómicamente, cada una de forma indivisible

Solución:

Diseñar un “protocolo”, que los procesos puedan

usar, para permitir la cooperación entre ellos

El “protocolo” debe asegurar que cuando un

proceso esté ejecutando su sección crítica, ningún
otro proceso tenga permiso para ejecutar su
sección crítica

Problema de la sección crítica
Problema de la sección crítica

≅
≅

Garantizar la exclusión mutua entre los n procesos
Garantizar la exclusión mutua entre los n procesos

durante la ejecución de su sección crítica
durante la ejecución de su sección crítica

El problema de la sección crítica

Estructura del proceso Pi

repeat

entrada a la sección crítica

Sección crítica

salida de la sección crítica

Trabajo propio

until false;

17

19

El problema de la sección crítica

Condiciones que debe satisfacer una solución al

problema de la sección crítica:

Exclusión mutua

Progreso

Espera limitada

18

20

El problema de la sección crítica

El problema de la sección crítica

Exclusión mutua

Si Pi está ejecutando su sección crítica, ningún otro proceso

puede estar ejecutando su sección crítica

Progreso

Si ningún proceso está ejecutando su sección crítica y hay

procesos que desean entrar en su sección crítica, la selección
del proceso que podrá entrar en ella NO será pospuesta
indefinidamente

Espera limitada

Cuando un proceso realiza una solicitud para entrar en su

sección crítica, el número de veces que otros procesos
pueden entrar en sus secciones críticas antes de que sea
atendida la solicitud del primer proceso está acotado

21

Algoritmo 1 (Dijkstra 1965)

Solución para dos procesos

Sean los procesos P0 y P1 .
Notación: Pi, Pj son procesos tal que j = i - 1

Datos compartidos

var turno: (0, 1);

turno = 0;

/* Inicialmente turno = 0 */
/* turno = i ⇒ Pi puede entrar en su sección crítica */

22

El problema de la sección crítica

El problema de la sección crítica

Proceso Pi

repeat

while turno ≠ i do no-op;

Sección crítica

turno := j;

Trabajo propio

until false;

Análisis de propiedades:

Exclusión mutua: SI (Por reducción al absurdo)

Supongamos que los dos procesos se encuentran ejecutando sus

secciones críticas

Esto significa que la variable turno al ejecutar la sección de

entrada, en el proceso Pi tiene el valor i = 0 ∧ 1

Esto no es posible ya que turno sólo puede tener un valor y su

valor sólo se cambia cuando un proceso sale de su sección crítica

23

24

El problema de la sección crítica

El problema de la sección crítica

Análisis de propiedades:

Progreso y espera limitada: NO (Contra-ejemplo)

Supongamos que el proceso P0 entra en su sección crítica
Al salir turno = 1, permitiendo que P1 pueda entrar en su sección

crítica

Supongamos que el proceso P1 no desea entrar nunca en su

sección crítica

Si P0 desea volver a entrar en su sección crítica, nunca lo

conseguirá y no podrá acabar su trabajo

El problema de la sección crítica

Proceso Pi

repeat

flag[i] := true;
while flag[j] do no-op;
Sección crítica

flag[i] := false;

Trabajo propio

until false;

25

27

Algoritmo 2 (Dijkstra 1965)

Solución para dos procesos

Sean los procesos P0 y P1
Notación: Pi, Pj son procesos tal que j = i - 1

Datos compartidos

var flag: array[0, 1] of boolean;

flag[0] := false;
flag[1] := false;

/* Inicialmente flag[0] = flag[1] = false;
/* flag[i] := true ⇒ Pi puede entrar en su sección crítica */

*/

26

El problema de la sección crítica

Análisis de propiedades:

Exclusión mutua: SI (Por reducción al absurdo)

Supongamos que los dos procesos se encuentran ejecutando sus

secciones críticas

Esto significa que flag[0] = false, flag[1] = false

Esto no es posible ya que si flag[i] = false para que el proceso Pj

se encuentre en su sección crítica, el proceso Pi no ha podido pasar por
su sección de entrada y por lo tanto no se encuentra en su sección
crítica

28

El problema de la sección crítica

El problema de la sección crítica

Análisis de propiedades:

Progreso y espera limitada: NO (Contra-ejemplo)

Supongamos que el proceso P0