Sincronización de sistemas distribuidos (página 2)

2. Algoritmo con Promedio

Este algoritmo no dispone de un servidor que controle, centralice y mantenga la sincronización del tiempo en el sistema. A diferencia de ello, cada máquina del sistema informa su hora local con cada mensaje que requiera enviar a otra máquina o máquinas del sistema. A partir de ese momento, cada máquina inicializa localmente un cronómetro, cuya duración es de intervalo y longitud fija. A partir de ese momento, cada máquina promedia su hora local con el uso de las horas que le informan el resto de las máquinas que interactúan con ella.

1. Algoritmos para la Exclusión Mutua

Estos algoritmos están definidos para asegurar el cumplimiento de exclusión mutua entre procesos que requieren acceder a una región crítica del sistema.

1. Este algoritmo simula la filosofía de operación de exclusión mutua utilizada en sistemas monoprocesadores. Para ello, existe una máquina en el sistema distribuido que se encarga de controlar el acceso a las diferentes secciones críticas, la cual es denominada coordinador. Cada proceso del sistema que requiera acceso a una sección crítica, debe solicitar acceso al coordinador, el cual lo otorgará en caso que la sección crítica esté disponible; caso contrario, colocará en una cola de espera al proceso solicitante. Cuando un proceso que recibió acceso a la sección crítica culmina su tarea, informa por igual al coordinador a fin de que éste pueda otorgar acceso a un próximo proceso solicitante o que se encuentre en cola de espera.

   Este algoritmo presenta una gran limitante, consistente en que el coordinador representa un único punto de control para el acceso a las diferentes secciones críticas del sistema distribuido, lo cual se convierte en un cuello de botella que puede afectar la eficiencia de los procesos que se ejecutan en el sistema. Igualmente, cualquier falla que presente el coordinador ocasionará la paralización de los procesos.

2. Centralizado
3. Distribuido

Este algoritmo fue desarrollado a fin de eliminar el problema latente en el algoritmo centralizado. Por lo tanto, su enfoque está basado en no disponer de un único coordinador para el control de acceso a las secciones críticas del sistema distribuido.

En este sentido, cada proceso que requiere acceso a una sección crítica, envía su solicitud a todos los procesos existentes en el sistema, identificándose así mismo y a la sección crítica que desea acceder. Cada proceso receptor envía su respuesta al proceso solicitante, indicando una de las siguientes posibles respuestas:

• Sección crítica no en uso por el proceso receptor. Mensaje de respuesta: OK.
• Sección crítica en uso por el proceso receptor. Mensaje de respuesta: no aplica, coloca al proceso emisor en cola de espera.
• Sección crítica no en uso pero solicitada por el proceso receptor.

• Mensaje de respuesta: OK, si la solicitud es anterior a la del receptor.
• Mensaje de respuesta: No aplica, si la solicitud es posterior a la del receptor, coloca al proceso de emisor en cola de espera.

Sin embargo, este algoritmo también contiene un problema, consistente en que si un proceso presenta una falla no podrá enviar su respuesta ante la solicitud de un proceso emisor, por lo cual esto será interpretado como una negación de acceso, bloqueando a todos los procesos que soliciten acceso a cualquier sección crítica.

1. Este algoritmo establece un anillo lógico de procesos, controlado por software, a través del cual se hace circular una ficha o testigo (token) entre cada proceso. Cuando un proceso recibe la ficha, puede entrar a una sección crítica si lo requiere, procesar todas sus tareas, abandonar la sección crítica y entregar la ficha al próximo proceso del anillo. Este proceso se repite continuamente en el anillo de procesos. Cuando un proceso recibe la ficha y no requiere entrar a una sección crítica, pasa la ficha inmediatamente al siguiente proceso.

   Este algoritmo contiene una debilidad, asociada a la posible pérdida de la ficha de control para el acceso a las secciones críticas. Si esto ocurre, los procesos del sistema asumirán que la ficha está en uso por algún proceso que se encuentra en la sección crítica.

2. De Anillo de Fichas (Token Ring)

   Estos algoritmos están diseñados para elegir un proceso coordinador. En los mismos, se garantiza que una vez realizada la elección del proceso coordinador, la misma concluya con el acuerdo de todos los procesos el sistema en la elección de un nuevo coordinador.

3. De Elección
4. Del Grandulón (García Molina)

Este algoritmo se inicia cuando un proceso cualquiera determina que no hay respuesta a las solicitudes hechas al proceso coordinador. En este momento, este proceso envía a todos los procesos mayores que él un mensaje de elección del nuevo coordinador, lo cual puede conllevar a los siguientes escenarios:

• Un proceso, con un número mayor que el proceso emisor del mensaje, responda OK, con lo cual queda elegido como coordinador del sistema.
• Ningún proceso responde el mensaje de elección, con lo cual el proceso emisor queda electo como proceso coordinador.

1. De Anillo

Este algoritmo opera de manera similar al algoritmo del Grandulón, con la diferencia que en este método se presenta las siguientes variantes:

El mensaje de elección se hace circular a todos los procesos del sistema, y no solo a los procesos mayores que el emisor.

Cada proceso inscribe en el mensaje su identificación.

Una vez que el mensaje completa el anillo y regresa a proceso emisor, quien establece como nuevo coordinador al proceso con el número mayor.

Se hace circular a través del anillo un nuevo mensaje indicando quién es el coordinador del sistema.

1. Transacciones Atómicas

Es un método de sincronización a alto nivel, que a diferencia de los métodos revisados hasta el momento, no ocupa al programador en los aspectos de exclusión mutua, prevención de bloqueos y recuperación ante fallos. Por el contrario, este método orienta el esfuerzo del programador a los verdaderos problemas y esencia de la sincronización de sistemas distribuidos.

El concepto de transacciones atómicas consiste en garantizar que todos los procesos que conforman una transacción deben ejecutarse en forma completa y satisfactoria. De producirse falla en alguno de los procesos, toda la transacción falla, revirtiéndose la misma y procediéndose a su reinicio.

1. PROCESOS Y PROCESADORES

1. Hilos de Procesos (Threads)

Hoy en día los sistemas operativos pueden soportar múltiples hilos de control dentro de un proceso. Dos características notorias en los hilos de procesos es que comparten un único espacio de direcciones, y a su vez, simulan un ejecútese de múltiples procesos independientes como si fuera en paralelo.

Solo en una maquina que tenga multiprocesador se pueden ejecutar realmente procesos en paralelo. Los hilos se pueden colocar en cuatro estados:

• En ejecución, cuando el proceso se esta ejecutando.
• Bloqueado, cuando un proceso depende de un recurso critico.
• Listo, cuando puede utilizarse nuevamente.
• Terminado, cuando culmina su tarea.

1. Implantación de un Paquete de Hilos

Existen dos formas de implantar los hilos:

1. En el usuario

Cuando se realiza la instalación de los paquetes a nivel de usuario, el núcleo no debe saber de su existencia, por lo cual el núcleo solo va a manejar un único hilo. Los hilos se ejecutan en el sistema por tiempo de ejecución en grupos de procedimientos. En el caso que el sistema o procedimiento requiera suspender un hilo dentro de su manejo, almacena los registros del hilo en una tabla, busca los no bloqueados y vuelve a cargar los registros de la máquina con los valores iniciales.

Sus principales ventajas son:

• Cada proceso o hilo puede tener su propio algoritmo o planificación de proceso.
• El intercambio es más rápido, ya que se utilizan los identificadores en el núcleo.
• Tiene una mayor escalabilidad en el incremento de procesos.

1. En el Núcleo

A diferencia de la implementación en el cliente, la implementación en el núcleo no necesita el manejo de tiempo de ejecución; cada proceso dentro del mismo maneja su tabla de procesos, aunque esto signifique un costo mayor en recursos de máquina y tiempo de procesamiento.

Una de las ventajas más relevantes es que no se requiere de llamadas de bloqueo al sistema.

1. GESTIÓN DE ARCHIVOS DISTRIBUIDOS

1. Estructura del Sistema de Archivos Distribuidos

Básicamente, un sistema de archivos distribuidos está conformado por dos componentes principales, sobre las cuales reposa todo el funcionamiento efectivo que permite a un sistema distribuido almacenar programas y datos, así como mantenerlos disponibles a dicho sistema cuando este lo necesite, en las tareas relevantes al acceso de lectura y escritura.

Estos componentes son denominados servicio de archivos y servicio de directorios, los cuales se pasan a explicar de inmediato.

1. Este servicio, propio del sistema operativo, es el encargado de controlar y poner a disposición todas las operaciones, definiciones y características propias de los archivos del sistema. Este servicio no está relacionado en lo absoluto con el manejo de la lógica o significado interno de la data contenida en los archivos, ni mucho menos en la relación o jerarquización que esta data mantienen entre sí, puesto que todo ello es materia de interés y trabajo para los aplicativos que se ejecutan en el sistema y que acceden a estos datos contenidos en el archivo.

   Realmente el servicio de archivos del sistema operativo se encarga de establecer el método de acceso que dispondrán los archivos, así como la organización que tendrán físicamente los datos dentro de ellos. Dependiendo del tipo de distribución y sistema operativo, se podrá establecer la conformación de los archivos como cadenas secuenciales de bytes, o bien como agrupación lógica secuencial de registros identificables o no. De aquí parte obviamente el método de acceso que aceptarán estos archivos para su lectura y escritura. Por ello nos encontramos en cada sistema operativo, distribuido o no, definiciones propias del sistema de archivos; tal es el caso de los archivos VSAM o QSAM en la plataforma centralizada mainframe, o sistemas de archivos FAT32 o NTFS en el sistema distribuido Windows, así como Ext2/Ext3 en Linux, entre otros.

   Adicionalmente, el servicio de archivos tiene un papel primordial en cuanto al establecimiento de atributos o características de los archivos, con lo cual el sistema operativo establece políticas de acceso sobre los mismos. Aunque estos atributos no son parte de la data contenida en los archivos, permiten establecer parámetros de propiedad o autoría, permisología en el acceso bajo niveles de lectura, escritura, modificación y/o eliminación, así como atributos para bitácora de modificaciones.

2. Servicio de Archivos
3. Servicio de Directorios

Básicamente brinda las capacidades para la creación y eliminación de directorios en el sistema, los cuales contendrán internamente al conjunto de archivos. Así mismo, el servicio de directorios establece la estructura y nomenclatura que se aplicará a los nombres de archivos, así como a los nombres de los propios directorios. De esta manera, todas las piezas de software que requieran acceder datos contenidos en los archivos deberán hacerlo bajo esta nomenclatura.

1. Niveles de Jerarquía en un Sistema de Archivos Distribuidos

El servicio de directorios del sistema operativo, permite que se establezca una relación de tipo jerárquica entre los archivos. Esta relación, al igual que se mencionó en la descripción del servicio de archivos, no está asociada a la data interna de los archivos. En este caso, se trata de mantener una relación jerárquica de arriba hacia abajo en cuanto a la definición de directorios dentro de directorios. Cuando entra en escena el concepto de subdirectorios, se permite entonces la agrupación lógica de archivos que guardan alguna relación entre sí.

El hecho de que los directorios puedan contener internamente subdirectorios, con una dimensionalidad máxima establecida por el propio sistema operativo, da origen a niveles de jerarquía en el sistema de archivos distribuidos, jerarquías que serán conocidas por todas las máquinas y procesos que conformen el sistema.

1. GESTIÓN DE MEMORIA

1. Administración de Memoria Distribuida

A fin de manejar la memoria en un sistema distribuido, es establecen dos métodos aceptados:

• Proveer un espacio de direccionamiento virtual que sea compartido entre todas las computadoras que conforman el sistema distribuido. La mayor complejidad de implementar un espacio de memoria compartida distribuida, es el mantener la consistencia de los datos que son actualizados en dicha área, así como reducir los retardos en el acceso de los mismos. Es decir, el control y bloqueo de los equipos que escriben en esta área debe ser eficiente.
• Análogo al esquema monoprocesador, manejando páginas o bloques de memoria (virtualización) de aquellos datos del sistema menos accedidos. Estos bloques o páginas son enviados por el administrador de memoria a petición de cada máquina del sistema. Aunque la duplicidad de los bloques de memoria compartidos aumenta el rendimiento y evita los problemas de acceder una única área de memoria, se origina un problema de consistencia entre las diferentes copias de la página que se reparten en el sistema. Adicionalmente, con cada escritura es necesario actualizar todas las copias del bloque de memoria, con lo cual el envío de la página por la red provocaría un tiempo de espera inaceptable.

Para solucionar estos problemas, se han propuesto diferentes modelos que aseguren la consistencia y que establezcan un nivel aceptable de rendimiento.

1. Modelos de Consistencia

1. Cualquier lectura a una localidad de memoria, regresa el valor guardado por la operación de escritura mas reciente en dicha localidad.

2. Estricta

   El resultado de cualquier ejecución es el mismo que si las operaciones de todos los procesos fueran ejecutadas en algún orden secuencial, y las operaciones de cada proceso individual aparecen en esta secuencia en el orden especificado por su programa.

3. Secuencial

   Las escrituras potencialmente relacionadas de forma causal son vistas por todos los procesos en el mismo orden. Las escrituras concurrentes pueden ser vistas en un orden diferente en maquinas diferentes.

4. Causal

   Las escrituras realizadas por un proceso son recibidas por los otros procesos en el orden en que son realizadas, pero las escrituras de procesos diferentes pueden verse en un orden diferente por procesos diferentes.

5. PRAM

   Para cada posición de memoria existe un acuerdo local acerca del orden de las escrituras en ella. Las escrituras en diferentes posiciones no tienen que ser vistas en el mismo orden por los diferentes procesos.

6. Del Procesador

   Los accesos a las variables de sincronización son secuencialmente consistentes.

   No se permite realizar un acceso a una variable de sincronización hasta que las escrituras anteriores hayan terminado en todas partes.

   No se permite realizar un acceso a los datos (L/E) hasta realizar todos los accesos anteriores a las variables de sincronización

7. Débil

   Antes de realizar un acceso ordinario a una variable compartida, deben terminar con éxito todas las adquisiciones anteriores del proceso en cuestión.

   Antes de permitir la realización de una liberación, deben terminar las (L/E) anteriores del proceso.

   Los accesos de adquisición y liberación deben ser consistentes con el procesador (no se pide la consistencia secuencial).

8. De Liberación
9. De Entrada

No se permite realizar un acceso de adquisición a una variable de sincronización con respecto de un proceso hasta que se realicen todas las actualizaciones de los datos compartidos protegidos con respecto de ese proceso.

Antes de permitir la realización de un acceso en modo exclusivo a una variable de sincronización por un proceso, ningún otro proceso debe poseer la variable de sincronización, ni siquiera en modo exclusivo.

Después de realizar un acceso en modo exclusivo a una variable de sincronización, no se puede realizar el siguiente acceso en modo no exclusivo de otro proceso a esa variable de sincronización hasta haber sido realizado con respecto del propietario de esa variable.

1. SISTEMAS OPERATIVOS MÁS CONOCIDOS

1. Cuadro Comparativo

1. Una vez realizada la investigación y analizado los documentos los cuales hacen referencias a los algoritmos en sistemas distribuidos, podemos decir que cada algoritmo de sincronización tiene sus fortalezas y debilidades, los cuales funcionan de acuerdo a su definición según su creador, aunque consideramos que el algoritmo de Cristian se adapta mas a las necesidades actuales y su fácil manejo permite la sincronización de procesos de una forma mas optima.

   En referencia a los sistemas operativos, podemos concluir que cada sistema operativo tiene un fin individual. Windows XP y Mac OS están diseñados para usuario final por su manejo. Debian Linux y Solaris, poseen complejidades, aunque no se descarta que pueda ser usado por usuario final. Sin embargo, debido a su complejidad de manejo requiere de especialistas en el manejo de estos sistemas.

   Otro punto decisivo antes de seleccionar un sistema operativo para una empresa, es cuánto se requiere invertir en su implementación, ya que dependiendo del sistema operativo que se escoja los costes de instalación pueden ser mayores.

2. CONCLUSIONES

3. BIBLIOGRAFÍA

TANENBAUM, Andrew. "Sistemas Operativos Modernos". Prentice Hall, México, 1992. pp. 825.

William Stallings, Sistemas Operativos. Disponible en línea.

Miltos D. Grammatikakis, D. Frank Hsu & Miro Kraetzl, Parallel System Interconnections and Communications. Disponible en línea.

Peterson Silberschatz, Sistemas operativos. Disponible en línea.

Jean-Marie Rifflet, Comunicaciones en UNIX. Disponible en línea.

AUTOR

Leonardo Muro García

Universidad Nueva Esparta

Facultad de Ciencias

Caracas, Venezuela

21 de Noviembre de 2007