Download Enunciado de la primera práctica

AMPLIACIÓN DE SISTEMAS
OPERATIVOS.
ALGORITMO “BULLY” DE ELECCIÓN
(ver. 0.1)
Guillermo González Talaván
24 de febrero de 2010
1.
Objetivo de la práctica
Programar mediante JAVA-RMI un conjunto de procesos distribuidos
que, de un modo tolerante a fallos, elijan a un coordinador.
2.
Descripción de la práctica
El algoritmo que se usará será el del abusón o bully, el cual se explica
con más en detalle en la sección siguiente. Este algoritmo es usado para
permitir que un grupo de procesos acuerden la elección de un coordinador
único de entre todos ellos, a pesar de que los procesos pueden en cualquier
momento fallar y recuperarse. El funcionamiento del algoritmo es tal que
siempre se llegue al resultado de que el coordinador es aquel proceso activo
que tiene el identificador más alto. Se asume que la comunicación es fiable,
aunque los procesos pueden fallar en cualquier momento (incluido durante el
procedimiento de elección que el algoritmo desencadena).
1
2.1.
Entorno y herramientas
El programa se hará en JAVA-RMI, pudiendo elegir para su desarrollo,
pruebas y defensa tanto las versiones de Windows como de Linux instaladas
en el Laboratorio.
2.2.
Modo de operación
La práctica en funcionamiento debe consistir en arrancar de forma automática seis procesos java en tres nodos distintos (dos procesos en cada
máquina).
Los procesos implicados interrogarán continuamente al coordinador cada
0.5-1.0 segundos (se elegirá como intervalo entre dos peticiones consecutivas un número aleatorio uniformemente distribuido en dicho intervalo). Esta
interrogación simula la petición de cualquier resultado al coordinador. El
coordinador tarda 0.2 segundos en atenderla.
Los procesos estarán preparados para que cuando se invoque un determinado método via RMI desde otro proceso programado al efecto, impriman
todos ellos por la pantalla el identificador del coordinador.
Durante la ejecución de la práctica, los procesos deberán poder ser arrancados y cancelados manualmente varias veces para ver si el algoritmo está realizado correctamente.
Se deberán programar scripts de modo que permitan arrancar automáticamente los procesos en todas las máquinas, sin tener que hacerlo manualmente.
2.3.
Forma de entrega y defensa
Las prácticas se realizarán en parejas, salvo causa justificada para realizarlas individualmente (consultad primero).
Se abrirá un plazo en DIAWEB para formar grupos de prácticas, depositar
el código fuente y entregar la copia impresa. Permaneced atentos a la página
web de la parte práctica de la asignatura:
http://avellano.fis.usal.es/~gyermo/assoo/
2
Una vez superado el plazo de entrega, la práctica no será modificada ni
se admitirá enmienda alguna.
La práctica estará formada por tres ficheros fuente con extensión “.java”:
Bully.java, Interfaz.java y Gestor.java. El primero se encargará de los
procesos que gestionan el algoritmo. El segundo, se podrá usar para especificar la interfaz remota. Finalmente, la clase Gestor servirá para realizar
peticiones a los procesos, como por ejemplo que se les pida que impriman
cuál de ellos es el coordinador.
Se entregará un listado del código fuente de la práctica, en letra de espaciado fijo, impreso por las dos caras del folio y al que se adjuntará una
portada que se obtendrá de la dirección:
http://majuelo.fis.usal.es/Latex/PortadaASSOO.html
2.4.
Evaluación
En la defensa se evaluará tanto las prácticas como la actuación de cada
miembro de la pareja. La nota individual de defensa servirá para modular la
nota obtenida en la práctica.
La defensa se realizará en el mismo acto por los dos miembros del grupo
de prácticas en el Laboratorio de Informática.
Para obtener una nota de 5 en la práctica, basta con que funcione correctamente en el Windows o en el Linux de clase. Esta condición es inexcusable,
incluso para aquellas personas que por razones de trabajo o de otra ı́ndole
no pueden asistir a clase. A partir de ahı́, y dependiendo de la calidad del
trabajo realizado, la nota que se puede obtener es superior.
Se entenderá que la ejecución de la práctica es correcta si realiza bien el
algoritmo bully, sin provocar interbloqueo ni inanición. Caso de que no ocurra
ası́, o no se haga con las especificaciones expresadas en este documento, la
práctica no se considerará aprobada.
3.
El algoritmo del abusón
Se trata de un algoritmo que pretende garantizar la existencia de un
coordinador único de entre un conjunto de procesos aunque algunos de ellos
3
puedan fallar.
3.1.
Premisas
1. Cada proceso participante tiene un número identificador único
2. Los procesos guardan en una variable el identificador del proceso coordinador actual
3. En cada momento, la aplicación del algoritmo debe garantizar que todos
los procesos ven al mismo coordinador, que será además aquel proceso
vivo cuyo identificador es el mayor
3.2.
3.2.1.
Funcionamiento del algoritmo
Tipos de mensajes que se envı́an los procesos
1. ELECCIÓN: el proceso se postula como coordinador
2. OK: un proceso de identificador mayor le dice que no
3. COORDINADOR: un proceso informa a los demás de que es el nuevo
coordinador
3.2.2.
Protocolo de actuación
1. Partimos de un estado en que todos los procesos coinciden en la identidad del coordinador. Cada cierto tiempo, sondean al proceso para ver
si sigue vivo.
2. Si cualquier proceso no obtiene respuesta del coordinador a uno de sus
sondeos, supone que ha muerto. Toma entonces la iniciativa e inicia
un proceso de elecciones enviando un mensaje ELECCIÓN a todos los
procesos de identificador mayor que el suyo
3. Si nadie responde a ese mensaje, se erige coordinador e informa de ello
mediante un mensaje COORDINADOR
4. Si alguno responde con un mensaje de OK diciéndole que no, la iniciativa la tienen procesos mayores que él. Se esperará a ver si llega un
4
mensaje con el nuevo coordinador y lo escribe en su variable. Si pasara
el tiempo y este mensaje no llegara, inicia un nuevo procedimiento de
elección.
3.2.3.
Importancia del tiempo
El tiempo es un factor muy importante en este algoritmo. La falta de respuesta del coordinador durante un intervalo prefijado inicia el procedimiento
de elección. La ausencia de respuestas a mensajes de ELECCIÓN, permite
erigirse a un proceso como nuevo coordinador. Si se recibe un mensaje desalentador de OK y transcurre cierto intervalo sin que llegue el mensaje de
nuevo coordinador, el proceso inicia un proceso de elecciones otra vez.
4.
Consideraciones adicionales
Permaneced atentos a las versiones que pueden aparecer de este enunciado, para corregir posibles errores, por ejemplo.
5