PDF de programación - Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Administración de procesos: Ejercicios de

sincronización

Gunnar Wolf

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Índice

1

Introducción

2 De gatos y ratones

3

Intersección de caminos

4 El elevador

5 Los alumnos y el asesor

6 El servidor Web

7 El cruce del río

8 Santa Claus

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Introducción

En estas láminas presento varios ejercicios de sincronización
Sin un órden claro

Simplemente son ejercicios que, comprendiendo los
fundamentos de concurrencia y sincronización, deben poder
realizar.

Sugiero su implementación empleando semáforos

Pero pueden emplear cualquier otro mecanismo de
sincronización.

Uso probable de estas láminas

Tarea
Ejercicios en clase

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Índice

1

Introducción

2 De gatos y ratones

3

Intersección de caminos

4 El elevador

5 Los alumnos y el asesor

6 El servidor Web

7 El cruce del río

8 Santa Claus

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Planteamiento

Fuente: Matt Welsh, 2007 (problema 1)

Tengo k gatos (y desafortunadamente, l ratones) en su casa.

Le sirvo la comida a mis gatos en m platos.

Gatos y ratones han llegado a un acuerdo para repartirse el tiempo
y comida — Pero tienen que convencerme de que están haciendo

su trabajo.

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Reglas

Los gatos pueden comer de sus m platos de comida.
Los ratones pueden comer de esos mismos platos siempre y
cuando no sean vistos.
Si un gato ve a un ratón comiendo, se lo debe comer (para
mantener su reputación)

Los platos están puestos uno junto al otro

Sólo un animal puede comer de cada plato a la vez
Si un gato está comiendo y un ratón comienza a comer de otro
plato, el gato lo ve (y se lo come).
Por acuerdo de caballeros, los gatos no se van a acercar a los
platos mientras hay ratones comiendo.
Importante: ¡Hay que evitar la inanición!

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Índice

1

Introducción

2 De gatos y ratones

3

Intersección de caminos

4 El elevador

5 Los alumnos y el asesor

6 El servidor Web

7 El cruce del río

8 Santa Claus

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Planteamiento

Fuente: Matt Welsh, 2007 (problema 2)

Hay un cruce de caminos sin señalamiento vial:

El tránsito puede llegar desde cualquier lugar y en cualquier

momento. ¿Cómo aseguramos que no haya choques?

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Reglas

No puede haber dos autos en la misma sección de la
intersección a la vez (llamemos a esa situación accidente o
choque)
No existe el rebase, los autos no invaden el carril izquierdo.
No debes permitir que se lleve a la inanición: Aunque haya
tráfico constante en un sentido, un auto que llegue desde otro
debe poder cruzar.

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Refinamiento 1

Tal vez elegiste bloquear la intersección completa cuando un auto

llega.

¿Por qué es ineficiente?
¿Cómo podrías mejorar el rendimiento (reducir la inanición) y
mantener la garantía de no-choques?

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Refinamiento 2

¿Cómo ajustarías el código para modelar también los giros?

Un auto podría girar a la derecha (y emplear sólo un
cuadrante)
Podría seguir de frente (y emplear dos cuadrantes)
Podría girar a la izquierda (y emplear tres cuadrantes).
Ojo: ¿Puedes evitar los bloqueos mutuos?

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Índice

1

Introducción

2 De gatos y ratones

3

Intersección de caminos

4 El elevador

5 Los alumnos y el asesor

6 El servidor Web

7 El cruce del río

8 Santa Claus

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Planteamiento

Fuente: Zoran Dimitrijevic (ejercicio 4)

El elevador de la Facultad se descompone demasiado, porque
sus usuarios no respetan los límites.

Te toca evitar este desgaste (y el peligro que conlleva).

Implementa el elevador como un hilo, y a cada persona que
quiere usarlo como otro hilo.
El elevador de la Facultad de Ingeniería da servicio a cinco
pisos.

Un usuario puede llamarlo en cualquiera de ellos
Puede querer ir a cualquiera otro de ellos.

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Reglas

El elevador tiene capacidad para cinco pasajeros

Recuerden que el peso canónico de todo ingeniero (estudiante
o docente) es constante.

Para ir del piso x a y, el elevador tiene que cruzar todos los
pisos intermedios
Los usuarios prefieren esperar dentro del elevador que fuera de
él

Si el elevador va subiendo y pasa por el piso x, donde está A
esperando para bajar, A aborda al elevador (no espera a que
vaya en la dirección correcta).

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Refinamiento

Evita la inanición.

¿Cómo puedes asegurarte de que una serie de alumnos que van
entre dos pisos no van a monopolizar al elevador ante otro
usuario que va para otro piso?

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Índice

1

Introducción

2 De gatos y ratones

3

Intersección de caminos

4 El elevador

5 Los alumnos y el asesor

6 El servidor Web

7 El cruce del río

8 Santa Claus

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Planteamiento

Fuente: Zoran Dimitrijevic (ejercicio 5)

Un profesor de la facultad asesora a varios estudiantes, y estamos
en su horario de atención.

Modelar la interacción durante este horario de modo que la espera
(para todos) sea tan corta como sea posible.

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Reglas

Un profesor tiene x sillas en su cubículo

Cuando no hay alumnos que atender, las sillas sirven como
sofá, y el profesor se acuesta a dormir la siesta.

Los alumnos pueden tocar a su puerta en cualquier momento,
pero no pueden entrar más de x alumnos
Para evitar confundir al profesor, sólo un alumno puede
presentar su duda (y esperar a su respuesta) al mismo tiempo.
Los demás alumnos sentados deben esperar pacientemente su
turno.
Cada alumno puede preguntar desde 1 y hasta y preguntas
(permitiendo que los demás alumnos pregunten entre una y
otra)

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Índice

1

Introducción

2 De gatos y ratones

3

Intersección de caminos

4 El elevador

5 Los alumnos y el asesor

6 El servidor Web

7 El cruce del río

8 Santa Claus

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Planteamiento

Al presentar los modelos de programación con hilos presentamos al

Jefe-trabajador:

Dijimos que así operan muchos servidores de red, como el servidor

Apache.

¿Cómo modelarías la interacción entre jefe y trabajadores,

empleando mecanismos de sincronización?

Gunnar Wolf

Administración de procesos: Ejercicios de sincronización

Introducción
De gatos y ratones
Intersección de caminos
El elevador
Los alumnos y el asesor
El servidor Web
El cruce del río
Santa Claus

Reglas

Al inicializar, el proceso jefe lanza k hilos trabajadores

Los t