PDF de programación - Sistemas multiprogramados

ditdit

UPM

Sistemas 

multiprogramados

Juan Antonio de la Puente

DIT/UPM

Objetivos

u Veremos cómo realizar sistemas de tiempo real con 

arquitectura asíncrona

– tareas como hebras de sistema operativo
– no todas las realizaciones son adecuadas
– los mecanismos de comunicación y sincronización están limitados

20/03/07

Sistemas multiprogramados

2

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Arquitectura síncrona y asíncrona

u La arquitectura síncrona (ejecutivo cíclico) tiene 

limitaciones
– muy rígida, bajo nivel
– mal encaje de tareas esporádicas
– limitaciones en los períodos

» mejor armónicos
» mejor si no son muy diferentes

u La alternativa es usar una arquitectura asíncrona

– las tareas se realizan como procesos ligeros (hebras)
– las tareas se reparten el procesador de forma dinámica

(invisible para el diseñador)

– un núcleo de tiempo real gestiona el reparto del tiempo del 

procesador

20/03/07

Sistemas multiprogramados

3

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Arquitectura síncrona

tarea 1

tarea 2

tarea 3

núcleo de tiempo real

20/03/07

Sistemas multiprogramados

4

t

 

5
0
0
2
e
n
e
u
P
a

 

l
 

i

t

 

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Procesos ligeros (hebras)

u Las hebras o threads son procesos concurrentes ligeros

– se ejecutan en el mismo espacio de memoria
– se pueden realizar de forma eficiente (contexto ligero)

u El núcleo de tiempo real proporciona la funcionalidad 

necesaria
– creación y terminación de hebras
– planificación del procesador
– sincronización (exclusión mutua y condiciones)
– gestión básica de interrupciones

20/03/07

Sistemas multiprogramados

5

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Estados de un proceso

Fin de E/S o 

suceso

Listo

Suspendido

I
n
t
e

rr

u

p

ció

n

E sp era p or E/S 
o suceso

P

la
nific

a

d

o
r

Nuevo

Ejecutándose

Terminado

20/03/07

Sistemas multiprogramados

6

t

 

5
0
0
2
e
n
e
u
P
a

 

l
 

i

t

 

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Núcleo de tiempo real

u El núcleo (kernel) de tiempo real se encarga de la 

creación, terminación y el multiplexado de los procesos 

u Puede tomar varias formas:

– Núcleo desarrollado como parte de la aplicación
– Núcleo incluido en el entorno de ejecución del lenguaje
– Núcleo de un sistema operativo de tiempo real
– Núcleo microprogramado

u El método de planificación que se usa afecta al 

comportamiento temporal del sistema

20/03/07

Sistemas multiprogramados

7

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Jerarquía de procesos

u Un proceso (padre) puede crear otros (hijos)

– el padre debe esperar la iniciación de los hijos antes de seguir
– el general, también debe esperar que terminen los hijos antes de 

terminar

u En sistemas de tiempo real a menudo se usa una 

estructura de procesos estática
– sólo se crean procesos al comenzar la ejecución del sistema
– sólo se crean procesos desde el proceso inicial
– los procesos  no terminan nunca

20/03/07

Sistemas multiprogramados

8

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Comunicación y sincronización

u Los procesos de un sistema de tiempo real pueden ser 

independientes unos de otros
– no se comunican entre sí
– no se sincronizan de ninguna manera
…pero es más frecuente que haya interacciones
– cooperar para un fin común 
– competir por la utilización de recursos.

u En este caso es necesario realizar operaciones de 

comunicación y sincronización entre procesos
– dos procesos se comunican cuando hay una transferencia de 

información de uno a otro

– dos procesos están sincronizados cuando hay restricciones en el 

orden en que ejecutan algunas de sus acciones

Los dos conceptos están relacionados

20/03/07

Sistemas multiprogramados

9

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Comunicación con datos comunes

u En un sistema monoprocesador, la forma más directa de 

comunicación entre dos o más procesos consiste en 
compartir datos
– un proceso escribe una variable compartida, el otro la lee

u Sin embargo, el acceso incontrolado a variables comunes 

puede producir resultados anómalos
– se dice que hay una condición de carrera cuando el resultado de la 
ejecución depende del orden en que se intercalan las instrucciones 
de dos o más procesos

– se trata de una situación anómala que hay que evitar

20/03/07

Sistemas multiprogramados

10

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

t

 

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Secciones críticas

u Un segmento de código en el que un proceso accede a 

una variable compartida se llama sección crítica
– las secciones críticas se deben ejecutar de forma atómica
– para ello se usa sincronización por exclusión mutua

» si un proceso está en una sección crítica, ningún otro proceso puede 

entrar en otra sección crítica que acceda a la misma variable

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

u La exclusión mutua debe cumplir algunas condiciones 

adicionales
– progreso: la selección del proceso que entra en la sección crítica 

no se puede aplazar indefinidamente.

– espera acotada: cuando un proceso espera para entra en su 

región crítica, el número de veces que entran otros procesos en 
sus respectivas secciones críticas está acotado

20/03/07

Sistemas multiprogramados

11

Sincronización condicional

u Cuando una acción de un proceso solo se puede ejecutar 

si otro proceso está en determinado estado o ha 
ejecutado ciertas acciones, hace falta un tipo de 
sincronización denominada sincronización condicional

Ejemplo: Productor y consumidor con tampón limitado

A

:productor

:Buffer

A

:consumidor

Put
Get

» no se debe hacer Put cuando el tampón está lleno.
» no se debe hacer Get cuando el tampón está vacío
» además, hay exclusión mutua en el acceso al tampón

20/03/07

Sistemas multiprogramados

12

t

 

5
0
0
2
e
n
e
u
P
a

 

l
 

i

t

 

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Mecanismos de sincronización

u El núcleo de tiempo real debe proporcionar mecanismos 

de sincronización adecuados
– para exclusión mutua y sincronización condicional

Ejemplos
– semáforos
– monitores
– objetos protegidos

u Todos están basados en la suspensión de un proceso 

mientras no se cumplen las condiciones para que se siga 
ejecutando

20/03/07

Sistemas multiprogramados

13

t

 

5
0
0
2
e
n
e
u
P
a

 

l
 

i

t

 

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Semáforos

u Un semáforo es una variable que toma valores enteros no 

negativos

u Además de asignarle un valor inicial, sólo se pueden hacer 

dos operaciones con un semáforo S
– Down (o wait):  Si S > 0, decrementa S en 1 

– Up (o signal): 

Si S £  0, el proceso se suspende hasta que S > 0
Incrementa S en 1

t

 

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

u Down y Up son indivisibles

– de eso se ocupa el núcleo

20/03/07

Sistemas multiprogramados

14

Sincronización condicional con semáforos

S : Semaphore; -- iniciado a 0

-- proceso 1
...
Down(S) -- espera condición
...

-- proceso 2
...
Up(S) -- avisa de condición
...

20/03/07

Sistemas multiprogramados

15

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

t

 

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Exclusión mutua con semáforos

M : Semaphore := 1; -- iniciado a 1

-- proceso 1
...
Down(S) -- entra en SC
-- sección crítica
Up(S) -- sale de SC
...

-- proceso 2
...
Down(S) -- entra en SC
-- sección crítica
Up(S) -- sale de SC
...

M sólo toma los valores 1 y 0 (semáforo binario)

20/03/07

Sistemas multiprogramados

16

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

t

 

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Ejemplo: productor y consumidor (1)

package Buffers is

type Buffer is tagged limited private;
procedure Put(B: in out Buffer; X: in Item);
procedure Get(B: in out Buffer; X: out Item);

private
...

type Buffer is
record
...
Mutex : Semaphore := 1; -- exclusión mutua
Full : Semaphore := 0; -- elementos ocupados
Empty : Semaphore := Size; -- elementos libres
end record;

end Buffers;

20/03/07

Sistemas multiprogramados

17

t

 

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Ejemplo: productor y consumidor (2)

procedure Put (B: in out Buffer; X: in Item) is
begin
Down(B.Empty);
Down(B.Mutex);
...
Up(B.Mutex);
Up(B.Full);
end Put;

procedure Get (B: in out Buffer; X: out Item) is
begin
Down(B.Full);
Down(B.Mutex);
...
Up(B.Mutex);
Up(B.Empty);
end Get;

end Buffers;

20/03/07

Sistemas multiprogramados

18

t

 

5
0
0
2
e
n
e
u
P
a

 

l
 

i

 

t

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Problemas de los semáforos

u Es fácil cometer errores

– Un solo Down o Up mal colocado puede hacer que el programa 

funcione incorrectamente

u Problemas de vivacidad y equidad

– Interbloqueo (deadlock): cada proceso espera una condición o un 

recurso que depende de otro, en una cadena circular

– bloqueo vivo:  (livelock): los procesos se ejecutan, pero ninguno 

consigue los recursos que necesita

– inanición (starvation): los procesos se ejecutan, pero algunos no 

consiguen los recursos nunca

u Es mejor usar mecanismos más abstractos y fiables

– monitores
– objetos protegidos

20/03/07

Sistemas multiprogramados

19

 

t

5
0
0
2
e
n
e
u
P
a

 

l
 

i

t

 

e
d
o
n
o
n
A
n
a
u
J
 
©

 

Monitores

u Un monitor es un módulo cuyas operaciones se ejecutan 

en exclusión mutua
– el compilador produce el código de bajo nivel necesario

u La sincronización condicional se obtiene con

variables de condición
– dos operaciones primitivas: signal y wait

» wait suspende el proceso de forma incondicional y lo pone en una 

cola asociada a la condición que espera

» signal reanuda el primer proceso que espera en la señal
» no hay memoria: si no espera nadie, la señal se pierde
– un proceso que espera una condición libera el monitor

20/03/07

Sistemas multip