PDF de programación - Tema 2. Semáforos

Contenidos
(cid:132) El problema de la sección crítica
(cid:132) Semáforos
(cid:132) Regiones críticas
(cid:132) Monitores

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

1

Bibliografía
(cid:132) Programación Concurrente

(cid:132) J. Palma, C. Garrido, F. Sánchez, A. Quesada, 2003
(cid:132) Capítulo 4

(cid:132) Principles of Concurrent and Distributed Programming

(cid:132) M. Ben-Ari. Prentice Hall, 1990
(cid:132) Capítulo 4

(cid:132) Sistemas Operativos

(cid:132) A. Silberschatz, P. Galvin. Addison-Wesley, 1999
(cid:132) Capítulo 6

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

2

Concepto de semáforo
(cid:132) Una variable entera con dos

operaciones atómicas:

(cid:132) Wait(s). si s>0 (cid:198) s:=s-1; si no,

suspende al proceso. (P(s))
(cid:132) Signal(s). si hay procesos

suspendidos, despierta uno; si no,
s:=s+1. (V(s))

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

3

Propiedades de los semáforos
(cid:132) wait(s) y signal(s) son instrucciones

atómicas

(cid:132) El semáforo debe tomar un valor inicial

positivo

(cid:132) La operación signal(s) despierta uno de
los procesos bloqueados. La definición
de la operación no especifica qué
proceso es despertado

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

4

Semáforos binarios
(cid:132) Un semáforo que pueda tomar cualquier valor

no negativo recibe el nombre de semáforo
general

(cid:132) Un semáforo que sólo puede tomar los

valores 0 y 1 recibe el nombre de semáforo
binario

(cid:132) La definición de las operaciones queda igual

salvo signa(s)
(cid:132) Si hay procesos suspendidos, despierta uno, si no,

s:=1

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

5

Invariantes del semáforo
(cid:132) Todo semáforo, al margen de su

implementación, debe cumplir los invariantes:

(cid:132) S >= 0
(cid:132) S = Sinicial + #signals - #waits

(cid:132) #signals es la cantidad de signal ejecutados en S
(cid:132) #waits es la cantidad de waits completados en S

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

6

Ejercicios

(cid:132) a.-) Resolver el problema de la sección

crítica para n procesos con semáforos

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

7

Ejercicios
(cid:132) b.-) Resolver diversos problemas de sincronización

(cid:132) b.1.-) Empleando la sentencia concurrente (cobegin, coend)

y semáforos, construir un programa concurrente que se
corresponda con el siguiente grafo de precedencia

A

B

C

D

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

8

Ejercicios

(cid:132) b.2.-) Supongamos tres procesos concurrentes P1, P2 y P3 con

el código que se muestra en las figuras. Se pide:
(cid:132) 1.- Introducir las modificaciones necesarias para que d se ejecute

(cid:132) 2.- Introducir las modificaciones necesarias para que d se ejecute

solo si e o a se han ejecutado

solo si e y a se han ejecutado

Process P1;
begin

repeat

Process P2;
begin

repeat

Process P3;
begin

repeat

a;
b;

c;
d;

e;
f;

forever;

end;

forever;

end;

forever;

end;

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

9

Implementación

(cid:132) Espera activa

wait(s):

loop

exit when s>0;

end loop;
s:=s-1;

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

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

10

Implementación

(cid:132) Sin espera activa (1)

type semaforo is

record

valor:integer;

L: ListaProceso;

end;

wait(s):

signal(s):

s.valor:=s.valor-1;
if s.valor<0 then

L.agregar(proceso);
bloquear;

end if;

s.valor:=s.valor+1;
if s.valor<=0 then

L.sacar(proceso);
despertar(proceso);

end if;

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

11

Implementación

(cid:132) Sin espera activa (2)

type semaforo is

record

valor:integer;

L: ListaProceso;

end;

wait(s):

signal(s):

if s.valor>0 then

s.valor:=s.valor-1;

else

L.agregar(proceso);
bloquear;

end if;

if not vacia(L) then
L.sacar(proceso);
despertar(proceso);

else

s.valor:=s.valor+1;

end if;

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

12

Implementación (Nachos)

Semaphore::Semaphore(char* debugName,
int initialValue)
{

name = debugName;
value = initialValue;
queue = new List;

}

Semaphore::~Semaphore()
{

delete queue;

}

void
Semaphore::P()
{

void
Semaphore::V()
{

IntStatus oldLevel = interrupt->SetLevel(IntOff);
while (value == 0) {

queue->Append((void *)currentThread);
currentThread->Sleep();

}
value--;
(void) interrupt->SetLevel(oldLevel);

Thread *thread;
IntStatus oldLevel = interrupt->SetLevel(IntOff);
thread = (Thread *)queue->Remove();
if (thread != NULL)

scheduler->ReadyToRun(thread);

value++;
(void) interrupt->SetLevel(oldLevel);

}

}

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

13

Implementación
(cid:132) Aspecto crítico de los semáforos:

(cid:132) Operaciones se ejecuten de forma atómica

(cid:132) Entorno uniprocesador:

(cid:132) interrupciones

(cid:132) Entorno multiprocesador

(cid:132) Instrucciones hardware especiales
(cid:132) Solución software (espera activa)

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

14

Problemas
(cid:132) Mecanismo de bajo nivel: no estructurado

(cid:132) Aunque entienda perfectamente su uso, un programador
puede olvidar accidentalmente alguna de las operaciones
(signal o wait) o realizarlas sobre semáforos distintos

(cid:132) Uso desordenado de las primitivas podría provocar que no

se consiga la exclusión mutua (signal, wait)

(cid:132) Bloqueos mutuos

(cid:132) El compilador no reconoce qué variables protege un

semáforo, con lo cual no nos ayudaría si estamos
utilizando una variable compartida fuera de su SC

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

15

Problemas
(cid:132) Tanto la exclusión mutua como la condición
de sincronización se implementan usando el
mismo par de primitivas
(cid:132) Difícil identificar el propósito de waity signalen

un código sin mirar el contexto global

(cid:132) Código difícil de mantener

(cid:132) Código de sincronización repartido entre los

diferentes procesos

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

16

Ejercicios

(cid:132) Tenemos un sistema con un conjunto de N tareas (procesos):

tarea1, tarea2, ...,tareaN. Cada tarea debe ejecutarse
periódicamente cada cierto intervalo de tiempo. Por ejemplo: la
tarea1 debe ejecutarse cada segundo, la tarea2 cada 10
segundos, etc... Los intervalos de tiempo para cada tarea están
predefinidos y se almacenan como datos del programa (por
ejemplo en un array). Durantes estos intervalos las tareas están
dormidas. Se pide programar un planificador que arranque las
tareas cuando les corresponda.
(cid:132) NOTA: Las tareas ejecutarán un proceso trivial. Tenemos la

sentencia cobegin, coend. El temporizador se puede resolver con
un reloj software (un contador que se va decrementando).

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

17

Ejercicios

(cid:132) En un sistema concurrente existen dos tipos de procesos, A y B,

que compiten por utilizar cierto recurso. Al recurso se accede
mediante la rutina de solicitarlo, esperar hasta que se pueda
usar, usarlo y luego liberarlo. En cualquier momento puede
haber un máximo de N procesos de cualquier tipo usando el
recurso (N es constante). Por otro lado, para que un proceso de
tipo A pueda entrar a emplear el recurso, debe haber al menos
el doble de procesos de tipo B que procesos de tipo A dentro del
recurso. Diseñe un algoritmo que cumpla con estas reglas de
funcionamiento empleando semáforos.

© Alexis Quesada Arencibia – José Miguel Santos Espino

ProgramaciónConcurrente

18