• Categories
• Proceso (Computación)
• Núcleo (Sistema operativo)
• Sistema operativo
• Unidad central de procesamiento
• Memoria de la computadora

Citation preview

Sistemas Operativos Centralizados y Distribuidos

Sistemas Operativos Centralizados y Distribuidos

M.C. Beatriz Beltrán Martínez M.C. Rafael de la Rosa Flores M.C. Hilda Castillo Zacatelco M.C. Leticia Mendoza Alonso Dra. Darnes Vilariño Ayala

Benemérita Universidad Autónoma de Puebla

Dirección General de Fomento Editorial

Benemérita Universidad Autónoma de Puebla

Enrique Agüera Ibáñez Rector José Ramón Eguíbar Cuenca Secretario General Lilia Cedillo Ramírez Vicerrector de Extensión y Difusión de la Cultura Carlos Contreras Cruz Director Editorial Mtro. José Jaime Vázquez López Vicerrector de Docencia Dr. Pedro Hugo Hernández Tejeda Vicerrector de Investigación y Estudios de posgrado Dr. Mario Rossainz López Director de la Facultad de Ciencias de la Computación

Primera edición, 2009 ISBN: ©Benemérita Universidad Autónoma de Puebla Dirección General de Fomento Editorial 2 Norte 1404 Teléfono y fax 2 46 85 59 Puebla, Puebla. Impreso y hecho en México Printed and made in Mexico

Prólogo

La misión del profesor en la actividad académica es mejorar el proceso de enseñanzaaprendizaje, contextualizar y vincular los contenidos teóricos de la materia con la realidad y permitirle al alumno usar correctamente las herramientas para su desarrollo profesional que le permitirán alcanzar satisfacción profesional, personal y social. Actualmente se cuenta con una gran información y material didáctico de todo tipo para las ciencias computacionales, sin embargo se observa que el alumno por lo mismo, no precisa elementos básicos y conceptos fundamentales en diferentes materias que conforman la currícula de la carrera de Ciencias de la Computación. Es por ello que se presenta en este texto, un material útil y práctico que se podrá consultar en cualquier momento y que no necesariamente será un auxiliar para la materia de Sistemas operativos, ya que su diseño, permite vincularlo con otras materias y usarlo como auxiliar en relación al tema propuesto. El libro contiene cinco capítulos que a su vez se dividen en subtemas que complementan de manera general el contenido. En los dos primeros capítulos se muestra al estudiante los conceptos fundamentales de un Sistema operativo, tanto centralizado, como distribuido; en el siguiente capítulo se aborda la gestión de procesos e hilos estudiando la teoría y los algoritmos utilizados en la comunicación y sincronización entre procesos en ambientes centralizados y distribuidos. El cuarto capítulo trata sobre la gestión entre memoria y el último el presenta una importante herramienta para la programación de lo estudiado en los cuatro capítulos anteriores: el uso de sockets en Java. A lo largo de los cinco capítulos encontrarán ejemplos, graficas y tablas que auxiliarán y fortalecerán la lectura del mismo, brindando de esta forma una fácil y motivante lectura para el entendimiento y aplicación del material proporcionado.



I Introducción a los Sistemas operativos centralizados y distribuidos

1.1. Componentes básicos de la arquitectura de Von Neuman La idea central del modelo de Von Neuman consiste en almacenar las instrucciones del programa de una computadora en su propia memoria, logrando así que la máquina siga los pasos definidos por su programa almacenado. Para llevar a cabo la función de procesamiento, una computadora con arquitectura von Neuman está compuesta por cuatro componentes básicos: 1. 2.

3.

• • • •

Memoria principal. Se construye con memoria ram y rom. En ella residen los datos a procesar, el programa máquina a ejecutar y los resultados. La unidad aritmética lógica. Permite realizar operaciones aritméticas y lógicas sobre operandos que residen en los registros o en memoria principal, y los resultados son almacenados en registros o en memoria principal. La unidad de control. La función principal de esta unidad es dirigir la secuencia de pasos de modo que la computadora lleve a cabo un ciclo completo de ejecución de una instrucción, y hacer esto con todas las instrucciones de que conste el programa. Los pasos para ejecutar una instrucción cualquiera son los siguientes: Leer de memoria las instrucciones de máquina que forman el programa. Interpretar cada instrucción leída Ejecutar cada instrucción. Prepararse para leer la siguiente casilla de memoria y regresarse al paso I.



4. La unidad de entrada/salida. Se encarga de hacer la transferencia de información entre la memoria principal o los registros y los periféricos. Se denomina unidad central de procesamiento (ucp, de aquí en adelante, aunque también es común referirse a ella como cpu, por sus siglas en inglés: Central Processing Unit) contiene a la unidad aritmético lógica y a la unidad de control. La función de la ucp es clara: ejecutar instrucciones. Pero para ello necesariamente deben cumplirse estas condiciones: • •

Que las instrucciones sean entendibles por la ucp Que estén almacenadas en la memoria

1.2 Registros básicos del procesador Un procesador incluye un conjunto de registros que proporcionan un nivel de memoria, que es más rápido y pequeño que la memoria principal. En los registros se almacenan temporalmente valores durante la ejecución de un programa. En la unidad de control se dispone generalmente de los registros visibles de usuario y registros de control y de estado. Registros visibles de usuario Estos registros permiten al programador de lenguaje de máquina o ensamblador minimizar las referencias a la memoria principal, optimizando el uso de estos registros. Con lenguajes de alto nivel, un compilador que optimice código intentará hacer una selección inteligente de qué variables asignar a registros y cuáles a ubicaciones de la memoria principal. Las clases de registro que normalmente están disponibles son: •

•

Registros de datos: pueden ser asignados por el programador a diversas funciones, en algunos casos son de propósito general y pueden ser empleados por cualquier instrucción de máquina que lleve a cabo operaciones sobre los datos. Registros de dirección: contienen direcciones de la memoria principal de datos e instrucciones o contener una parte de la dirección, que se utiliza en el cálculo de la dirección completa o efectiva, ejemplos de estos registros son:

- Registro de índice: El direccionamiento indexado es un modo común de direccionamiento, que implica sumar un índice a un valor base, para obtener la dirección efectiva. 

- Apuntador al segmento: en segmentación, la memoria se divide en segmentos, una referencia a la memoria consta de una referencia a un segmento particular y un desplazamiento dentro del segmento.

En algunas máquinas, una llamada a un procedimiento o subrutina provocará que los registros visibles de usuario se salven automáticamente, para luego restaurarlos al retornar, esto permite que cada procedimiento pueda usar los registros de forma independiente. En otras máquinas, es responsabilidad del programador salvar los contenidos de los registros del usuario visibles que sena relevantes antes de hacer la llamada a un procedimiento, incluyendo instrucciones en el programa con tal propósito. Registros de control y de estado: son utilizados por el procesador para el control de las operaciones y rutinas privilegiadas del sistema operativo para controlar la ejecución de los programas, algunos de estos registros se muestran a continuación: • • •

Contador de Programa (pc, Program Counter): Contiene la dirección de la instrucción a ser leída. Registro de Instrucción (ir, Instruction Register): Posee la última instrucción leída. Registro de Banderas: Indican el estado actual de la máquina y el resultado del procediendo.

1.3 Ejecución de instrucciones La unidad de control de la computadora es la que establece el funcionamiento del mismo. Este funcionamiento cuenta tres pasos:

1. Lectura de la instrucción apuntada por el contador de programa 2. Incremento del contador de programa 3. Ejecución de la instrucción

Esta secuencia tiene dos propiedades fundamentale: La de que es lineal y la otra que forma un bucle infinito (realiza esta secuencia ininterrumpidamente excepto computadoras con una instrucción halt. Existen mecanismos que permiten alterar esta ejecución lineal, los mecanismos básicos de ruptura de secuencia son los siguientes: • • •

Las instrucciones “máquina de salto o bifurcación” Las interrupciones internas o externas La instrucción de máquina trap 

1.4 Interrupciones Desde el punto de vista del programa de usuario, una interrupción es solamente eso, una interrupción de la secuencia normal de ejecución. Cuando el tratamiento de la interrupción se termina, la ejecución continúa, por lo que el programa de usuario no tiene que disponer de ningún código especial para dar cabida a las interrupciones; el procesador y el sistema operativo son los responsables de suspender el programa de usuario y reanudarlo después en el mismo punto. Para dar cabida a una interrupción, se añade un ciclo de interrupción al ciclo de instrucción. En el ciclo de interrupción, el procesador comprueba si ha ocurrido alguna interrupción, indicado por la presencia de una señal de interrupción. Si no hay interrupciones pendientes, el procesador continúa con el ciclo de lectura y trae la próxima instrucción del programa en curso. Si hay una interrupción pendiente, el procesador suspende la ejecución del programa en curso y ejecuta una rutina de tratamiento de la interrupción. Esta rutina de software de base es previamente escrita por un programador de sistemas, y reside en un área preespecificada de la memoria central, realizando cuantas acciones sean necesarias. 1.5 Taxonomia de Flynn La taxonomía de Flynn clasifica a las computadoras por su arquitectura y sus sistemas operativos; esto de acuerdo a la capacidad de un sistema para procesar uno o más flujos simultáneos de datos (data stream) e instrucciones (instruction stream). •

•

•

– Single Instruction, Single Data Stream: (Una instrucción, un dato) Computador secuencial que no explota el paralelismo en las instrucciones ni en flujos de datos. Ejemplos de arquitecturas sisd son las máquinas monoprocesador tradicionales como el pc o los antiguos mainframe. simd – Single Instruction, Multiple Data Stream: (Una instrucción, múltiples datos) - Un computador que explota varios flujos de datos dentro de un único flujo de instrucciones para realizar operaciones que pueden ser paralelizadas de manera natural. Por ejemplo, un procesador vectorial. mism – Multiple Instruction, Single Data Stream: (Múltiples instrucciones, un dato) - Poco común debido al hecho de que la efectividad de los múltiples flujos de instrucciones suele precisar de múltiples flujos de datos. Sin embargo, este tipo se usa en situaciones de paralelismo redundante, como por ejemplo en navegación aérea, donde se necesitan sisd

10

•

varios sistemas de respaldo en caso de que uno falle. También se han propuesto algunas arquitecturas teóricas que hacen uso de misd, pero ninguna llegó a producirse en masa. mimd – Multiple Instruction, Multiple Data Stream: (Múltiples instrucciones, múltiples datos)Varios procesadores autónomos que ejecutan simultáneamente instrucciones diferentes sobre datos diferentes. Los sistemas distribuidos suelen clasificarse como arquitecturas mimd; bien sea explotando un único espacio compartido de memoria, o uno distribuido.

1.6 Arquitectura de Multiprocesadores Este tipo de arquitecturas cuenta con dos o más microprocesadores (cpus), gracias a esto, el multiprocesador puede ejecutar simultáneamente varios hilos pertenecientes a un mismo proceso o bien a procesos diferentes. Las arquitecturas con multiprocesador presentan problemas de diseño que no se en-cuentran en arquitecturas monoprocesador. Estos problemas derivan del hecho de que dos programas pueden ejecutarse simultáneamente y, potencialmente, pueden interferirse entre sí. Concretamente, en lo que se refiere a las lecturas y escrituras en memoria. Existen dos arquitecturas que resuelven estos problemas: • •

La arquitectura numa (Non-Uniform Memory Acces), donde cada procesador tiene acceso y control exclusivo a una parte de la memoria. La arquitectura smp (Symmetric Multi Processing), donde todos los procesadores comparten toda la memoria.

Esta última debe lidiar con el problema de la coherencia de caché. Cada microprocesador cuenta con su propia memoria caché local. De manera que cuando un microprocesador escribe en una dirección de memoria, lo hace únicamente sobre su copia local en caché. Si otro microprocesador tiene almacenada la misma dirección de memoria en su caché, resultará que trabaja con una copia obsoleta del dato almacenado. Para que un multiprocesador opere correctamente necesita un sistema operativo especialmente diseñado para ello. La mayoría de los sistemas operativos actuales poseen esta capacidad. 1.7 Definición de Sistemas Operativos El sistema operativo es el programa fundamental de todos los programas del sistema, protege y libera a los programadores de la complejidad del hardware, colocándose un nivel de software por sobre el hardware para controlar todas las partes del sistema y presentar al usuario una interfaz o máquina virtual. Puede considerarse que un sistema operativo tiene tres objetivos: 11

• • •

Comodidad: un sistema operativo hace que un computador sea más cómodo de utilizar. Eficiencia: un sistema operativo permite que los recursos de un sistema informático se aprovechen de una manera más eficiente. Capacidad de evolución: un sistema operativo debe construirse de modo que permita el desarrollo efectivo, la verificación y la introducción de nuevas funciones en el sistema y, a la vez, no interferir en los servicios que brinda.

El Sistema Operativo desarrolla las siguientes tareas: • • • •

Administración de trabajos Administración de datos Administración de dispositivos (los controladores son proporcionados por los fabricantes) Seguridad (respaldo y recuperación)

Ejercicios 1. Para que una instrucción pueda ejecutarse debe: a) Estar almacenada en la memoria y los datos deben estar almacenados exclusivamente en los registros del cpu. b) Ser entendible para el procesador; los datos pueden estar tanto en memoria principal como en secundaria. c) Estar almacenada en la memoria; los datos deben estar almacenados en los registros del cpu y la memoria principal. d) Ser entendible para el procesador; los datos deben estar almacenados en memoria principal.

2. Son componentes del modelo Von Neuman: a) b) c) d)

Memoria, Dispositivos de e/s, cpu Memoria, Dispositivos de e/s, Unidad de Control Memoria, Unidad de Control, Unidad Aritmética Lógica Dispositivos de e/s, Unidad de Control, cpu

3. Suponga que tenemos un conjunto de instrucciones que realizan un ciclo (loop), el cual depende de un contador. En el ciclo se suman datos que se encuentran en cierta región de memoria, el resultado es almacenado en el registro especificado para esta acción. ¿Qué registros están involucrados en estas operaciones?

12

a) b) c) d)

Los registros de propósito general ax, cx, dx, ss. Los registros de propósito general ax, bx, cx, dx. Los registros segmentados ds y cs y los apuntadores si, di Los registros apuntadores si, bp y los registros de propósito general ds, ax, cx

4. Para que una instrucción se ejecute es necesario que el procesador obtenga los datos necesarios para esta instrucción. El medio que el procesador utiliza para obtener los datos es: a) El bus de datos

b) Un controlador

c) El segmento de datos

d) El stack

5. Las pc que tienen solamente procesador están clasificadas dentro de la taxonomía de Flynn como: a) sisd

b) simd

c) mimd

d) misd

6. Los sistemas distribuidos están clasificados dentro de la taxonomía de Flynn como: a) sisd

b) misd

c) simd

d) mimd

7. Cuando una rutina invoca a otra rutina la dirección de retorno es almacenada en: a. b. c. d.

El registro segmentado ss El registro apuntador ip El segmento ss El segmento cs

8. Los multiprocesadores coma tienen como característica principal: a) b) c) d)

Utilizar memoria local principalmente para la ejecución del programa Tener un solo espacio de direcciones lógico compuesto por las memorias caché Tener un solo espacio de direcciones lógico compuesto por las memorias locales Utilizar su memoria global principalmente

9. Son tres conceptos que definen básicamente a un sistema operativo: a) Señales, Procesos, Memoria b) Sistema operativo en Red, Administración de la memoria, Administrador de dispositivos c) Planificador de procesos, sistema de archivos, administración de la memoria d) Manejo de dispositivos de e/s, despachador de procesos

13

10. numa es un tipo de ____________ clasificado en la Taxonomía de Flynn como _____________ a) b) c) d)

Procesador, mimd Multiprocesador, simd Procesador, sisd Multiprocesador, mimd

Referencias Tanenbaum, Andrew S. Sistemas Operativos Modernos. Segunda Edición. Prentice Hall. Pearson Education. México, 2003. Carretero Pérez, Jesús; De Miguel Anasagasti, Pedro; García Carballeira, Féliz; Pérez Costoya, Fernando. Sistemas Operativos. Una visión Aplicada. Mc Graw Hill. España,2001. William Stallings . Sistemas Operativos, Prentice may, 4ta Edición. Prentice may. Flynn, Ida M.; McIver McHoes, Ann. Sistemas Operativos. Tercera Edición. Thomson Learning. México, 2001.

14

II Conceptos de Sistemas Operativos

2.1 Evolución de los Sistemas Operativos La evolución de los so se relaciona históricamente con la arquitectura de las computadoras. Primera computadora digital, inglés matemático Charles Babbage (1792-1871). Primera generación de computadoras (1945-1955): Bulbos y conexiones • • • • •

A mediados de los 40 Howard, Aiken, John Von Neumann, J. Presper, William Mauchley y Konrad Zuse lograron construir máquinas de cálculo mediante bulbos. Las computadoras eran enormes, lentas y contenían miles de bulbos. Un solo grupo de personas diseñaba, construía, programaba, operaba y daba mantenimiento. El lenguaje utilizado era el lenguaje de máquina (conexiones). A principios de los 50 se introdujeron las tarjetas perforadas (lector de tarjetas).

Segunda generación (1955-1965): Transistores y sistemas de procesamiento por lotes • • • • • • •

A mediados de los 50’s se introduce el transistor, esto dio origen a computadoras más confiables, además de que se podían fabricar varias y venderlas. Hay una clara separación entre los diseñadores, operadores, programadores, etc. Las computadoras estaban aisladas en cuartos de cómputo con aire acondicionado y un equipo de operadores profesionales a cargo para su ejecución. Utilizaban tarjetas perforadas. Los lenguajes utilizados era: fortran, ensamblador y jcl (Lenguaje de Control de Trabajo). Se desperdiciaba tiempo de cómputo. Eran muy caras, y sólo las podían adquirir grandes corporaciones y universidades. 15

• • • • •

Para agilizar el proceso se usa un sistema de procesamiento por lotes (varios trabajos .bat). Sólo se realizaban cálculos científicos y de ingeniería en ellos. Los so comunes eran: fms (Fortran Monitor System), ibsys que era el so de ibm para 7094. Se crean dos estados del so: superusuario y usuario. Aparecen las interrupciones y el gestor de interrupciones (int. de hw y de sw), la mmu, y más periféricos y más adelante los buffer (memorias intermedias) y con ello el buffering.

Cinta de salida

Cinta de entrada Unidad de cinta

Cinta de sistema

Sistema de procesamiento por lotes

Tercera generación (1965-1980): Circuitos integrados y multiprogramación • • • • • •

•

•

A principios de la década de los 60 las computadoras eran caras y había dos tipos de computadoras: científicas y comerciales, las cuales eran incompatibles entre sí. ibm introdujo el sistema/360 que fue la primera línea de computadoras que utilizó los circuitos integrados a pequeña escala, a partir de esta se fabrican computadoras compatibles. Cada tipo de computadora tenía su propio sistema operativo. Se intentó un so compatible que resultó enorme y complejo, el os/360 (Fred Brooks). Debido a la pérdida de tiempo en la e/s se particiona la memoria en varias partes, así cada parte puede realizar un trabajo distinto, multiprogramación. Cuando una partición quedaba vacían el so podía leer cargar un nuevo trabajo del disco en la partición desocupada y ejecutarla, a esta técnica se le llama spooling (Simultaneous Peripheral Operation On Line [operación simultánea y en línea de periféricos]). La diferencia entre el buffering y el spooling es que en el primero almacenamos la e/s de un trabajo con su proceso, mientras que en el segundo almacenamos (solapamos) la e/s de varios procesos con otro proceso distinto. En el procesamiento por lotes el programador perdía muchísimo tiempo en compilar y sobre todo cuando se equivocaba. 16

• • • • • • •

Aparece la escalabilidad (ampliar en un momento determinado las funciones del sistema). Cada usuario tenía una terminal en línea, nace el tiempo compartido (timesharing) Primer sistema de tiempo compartido: ctss (1962) Después: multics el cual no fue muy utilizado pero influyó en los sistemas subsecuentes Hay un crecimiento de las minicomputadoras, por ejemplo la dec pdp-1 en 1961 unix hace su aparición – Ken Thompson lo crea en una pdp-7 Aparecen los sistemas de tiempo real

Cuarta generación (1980-1990): Computadoras personales • • • • • •

• • •

(Large Scale Integration). Nacen los so de red y los so distribuidos. Aparecen los problemas de criptografía que intenta asegurar la privacidad, la integridad del mensaje y la autentificación del mismo. Nace msdos que utiliza un cpu 8088 de intel y sus sucesores 80286, 80386 ... unix utiliza un procesador risc. Se desarrolla el concepto de máquina virtual que simula otras máquinas en una plataforma concreta (emuladores). Esto alcanza su mayor desarrollo con la plataforma java que es un lenguaje y una máquina virtual. Uso de sistemas de gestión de bases de datos. so de red: En este tipo de sistema los usuarios están conscientes de la existencia de varias computadoras y pueden realizar operaciones con ellas. so distribuidos: Es aquel que aparece ante sus usuarios como un so tradicional de un solo procesador, aun cuando esté compuesto de varios procesadores. lsi

2.2. Funciones de los Sistemas Operativos Una de las principales funciones del sistema operativo es ocultar toda la complejidad y proporcionar al programador un conjunto de instrucciones más conveniente de instrucciones con el cual trabajar. El sistema operativo se ejecuta en: • •

Modo central o modo de supervición, el cual esta protegido, el usuario no puede escribir su propio controlador de interrupciones de disco por ejemplo (el hw no lo permite) Modo usuario, dentro de este modo se ejecutan los compiladores y los editores, si el usuario quiere escribir su propio editor lo puede hacer.

17

Las principales características de los s.o. son: • • • • • •

Definir la “Interfaz del Usuario” Compartir el hardware entre usuarios Permitir a los usuarios compartir los datos entre ellos Planificar recursos entre usuarios Facilitar la entrada/salida Recuperarse de los errores

Los principales recursos administrados por los s.o. son: • • • •

Procesadores Almacenamiento Dispositivos de e/s Datos

Los s.o. son una interfaz con: • • • • • •

Operadores Programadores de aplicaciones Programadores de sistemas (administradores del s.o.) Programas Hardware Usuarios

El Sistema Operativo debe presentar al usuario el equivalente de una máquina extendida o máquina virtual que sea mas fácil de programar que el hardware subyacente. • • • • • •

Definir la interfaz del usuario Compartir el hardware entre los usuarios Permitir a los usuarios compartir datos Planificar recursos entre usuarios Facilitar la entrada y salida de información Recuperación de errores

18

2.3 Llamadas al Sistema Los programas de usuario para solicitar servicios al Sistema Operativo utilizan las llamadas al sistema, las cuales son un conjunto de primitivas que brinda el Sistema Operativo y que sirven para comunicarse con el hw en forma entendible. A cada llamada le corresponde un procedimiento: • • •

•

Pone los parámetros de la llamada en un lugar específico para luego ejecutar una instrucción tipo “trap” de llamada a procedimiento protegido para iniciar el s.o. Luego de “trap” el s.o. recupera el control, examina los parámetros y si son válidos ejecuta el trabajo solicitado. Luego de terminar, el s.o. coloca un código de estado en un registro indicando si tuvo éxito o fracaso y ejecuta una instrucción del tipo “return from trap” para regresar el control al procedimiento. El procedimiento regresa al programa llamador con un código de estado como un valor de función; dentro de los parámetros pueden regresar valores adicionales.

2.4 Estructura de un Sistema Operativo 2.4.1 Micronúcleo Un micronúcleo (microkernel) es un pequeño núcleo del sistema operativo que proporciona las bases para ampliaciones modulares. El micronúcleo está rodeado por una serie de subsistemas compactos de forma que facilitan la tarea de implementar una gran variedad de plataformas. 2.4.2 Núcleo monolítico Los primeros sistemas operativos desarrollados a mediados de los cincuentas, fueron diseñados sin demasiada preocupación por la estructura. No había gran experiencia en sistemas de software realmente grandes, por lo que no se tomaron en cuenta los problemas provocados por la interacción y dependencia mutua. Esto fue insostenible cuando el Sistema Operativo alcanzó proporciones considerables (hablamos de alrededor de un millón de líneas de código), este tipo de Sistemas Operativos estaban constituidos por un núcleo monolítico. 19

Un núcleo monolítico es el núcleo o kernel de un Sistema Operativo que está programado en forma no modular y tiene un rendimiento mayor que un microkernel. Sin embargo cualquier cambio a realizar en cualquier servicio requiere la recopilación del núcleo y el reinicio del sistema para aplicar los nuevos cambios. Un Sistema Operativo con núcleo monolítico concentra todas las funcionalidades posibles dentro de un gran programa. Todos los componentes funcionales del núcleo tienen acceso a todas sus estructuras de datos interna y a sus rutinas. Estos Sistemas Operativos han surgido, normalmente, de Sistemas Operativos sencillos y pequeños a los que se les ha ido añadiendo un número mayor de funcionalidades. 2.4.3 Capas Virtuales El análisis de los Sistemas Operativos suelen dividirse en funciones jerárquicas, desde niveles muy cercanos a la máquina misma hasta niveles más virtuales, en el sentido de que ya no tratan a la computadora como una máquina (dotada de un procesador, memoria etc.), sino como un esquema diseñado para manejo de información, sin preocuparse demasiado por detalles como registros, direcciones, etcétera. El esquema que suele seguirse para el estudio de los Sistemas Operativos está formado por “capas”, el primer sistema por capas fue desarrollado por e.w. Dijkstra en 1968, el famoso the (Technische Hogeschool Eindhoven-Holanda) el cual constaba de 6 capas. 5

El operador

4

Programas del usuario

3

Control de Entrada/Salida

2

Comunicación operador-proceso

1

Administración de la memoria y el disco

0

Asignación del procesador y multiprogramación

multics fue otro sistema que utilizó una generalización de capas más avanzado. En lugar de capas multics estaba organizado como una serie de anillos concéntricos, siendo los anillos interiores los privilegiados.

Máquinas virtuales: •

Este concepto fue introducido por Seawright y MacKinnon en 1979 en un sistema originalmente llamado cp/cms y que ahora se llama vm/370. 20

•

•

El monitor de la máquina virtual es el corazón del sistema, se ejecuta en el hw simple y realiza la multiprogramación, proporcionando no una , sino varias máquinas virtuales a la siguiente capa superior, estas máquinas virtuales no son máquinas extendidas, con archivos u otras características adecuadas, son copias exactas del hw simple, con su modo núcleo/ usuario, E/S, interrupciones y todo lo demás que posee la máquina real. Por lo tanto cada máquina virtual pueden ejecutar diferentes so. Las llamadas al sistema son atrapadas por su propio sistema operativo en su máquina virtual.

En la actualidad las capas que forman al Sistema Operativo son “capas” concéntricas alrededor del núcleo. La parte interna del conjunto jerárquico de programas que forman un Sistema Operativo recibe precisamente el nombre de núcleo (kernel, en inglés). Las otras capas o subsistemas se encargan del manejo de la memoria, el procesador, los dispositivos de entrada/salida, los archivos, etcétera. Manejo de información Manejo de I/O Manejo de procesador Manejo de memoria Kernel

Capas virtuales de un Sistema Operativo Actual

2.4.4

Otras estructuras virtuales

Modelo cliente-servidor • • •

La tendencia de los so modernos es tratar de mantener un núcleo mínimo implantando la mayoría de las funciones del so en los procesos del usuario. Para solicitar un servicio de proceso del usuario (proceso cliente) envía un mensaje a un proceso servidor para que se realice el trabajo y regrese con la respuesta. El servidor se ejecuta como proceso en modo usuario y no sabe de dónde viene el mensaje, si este es local o remoto. 21

Solicitud de servicio Servidor

Cliente Respuesta

2.5 Tipos de Sistemas Operativos 2.5.1 Sistemas Operativos Centralizados Un sistema operativo centralizado es un sistema que utiliza el hardware de una sola pc. El procesamiento se hace en un solo equipo utilizando uno o más procesadores. 2.5.2 Sistemas Operativos de Red Son aquellos que mantienen a dos o más computadoras unidas a través de algún medio de comunicación, con el objetivo de poder compartir los diferentes recursos y la información del sistema. Los Sistemas Operativos de red también se definen como aquellos que tienen la capacidad de interactuar con Sistemas Operativos en otras computadoras por medio de un medio de transmisión con el objeto de intercambiar información, transferir archivos, ejecutar comandos remotos y un sin fin de otras actividades. El punto crucial de estos sistemas es que el usuario debe saber la sintaxis de un conjunto de comandos o llamadas al sistema para ejecutar estas operaciones, además de la ubicación de los recursos que desee accesar. 2.5.3 Sistemas Operativos Distribuidos 2.5.3.1 Definición En un Sistema Operativo distribuido los usuarios pueden acceder a recursos remotos de la misma manera en que lo hacen para los recursos locales. Permiten distribuir trabajos, tareas o procesos, entre un conjunto de procesadores. Puede ser que este conjunto de procesadores esté en un equipo o en diferente lo cual es transparente para el usuario. 22

Los Sistemas Distribuidos deben ser muy confiables y estables ya que si un componente del sistema se descompone otro componente debe ser capaz de reemplazo inmediatamente y no afectar los procesos del sistema. Entre los diferentes Sistemas Operativos distribuidos que existen tenemos los siguientes: Sprite, Solaris-mc, CHorus, Amoeba, Taos, etc. 2.5.3.2 Aspectos de Diseño de un Sistema Distribuido •

Transparencia. El Sistema distribuido debe dar la impresión de un sistema de un solo cpu, ocultando la distribución a los usuarios.

Clases de transparencia en los Sistemas Distribuidos: • Acceso. Los usuarios pueden acceder a recursos locales y remotos empleando operaciones idénticas • Localización. Los usuarios no tienen que especificar dónde se encuentran los recursos • Migración. Los recursos se pueden mover sin cambiar su nombre • Réplica. Los usuarios no tienen que indicar cuántas copias existen • •

Concurrencia. Varios usuarios pueden compartir recursos automáticamente Paralelismo. Diferentes actividades ocurren en paralelo sin el conocimiento de los usuarios

•

Flexible (Heterogéneo) Un sistema distribuido debe construirse desde una variedad de diferentes redes, Sistemas Operativos, hardware de computadoras y lenguajes de programación. Los protocolos de comunicación especiales enmascaran las diferencias entre redes y middleware puede tratar con las diferencias restantes.

•

Confiable (Seguridad) Se puede emplear encriptación para proporcionar una protección adecuada a los recursos compartidos y mantener secreta la información sensible cuando se transmite un mensaje a través de la red, además algunos recursos deben ser protegidos de accesos no autorizados. Tolerante a fallas Los sistemas distribuidos se deben diseñar para ocultar lo más posible las fallas a los usuarios. Concurrencia La presencia de múltiples usuarios en un sistema distribuido es una fuente de peticiones concurrentes a sus recursos. Cada recurso debe estar diseñado para ser confiable en un entorno concurrente. 23

•

Escalable Un sistema es escalable si el costo de añadir un usuario es una cantidad constante en términos de recursos que se deberán añadir.

2.5.3.3 Ventajas y desventajas de un Sistema Distribuido Ventajas sobre sistemas centralizados: • • • • • •

Económicas: Ofrecen una razón precio/funcionamiento mejor. Velocidad: Tienen una potencia computacional total mayor. Inherentes: Algunas aplicaciones son inherentemente distribuidas. Confiable: Si una máquina falla, el sistema como un todo funciona. Incremental: Se puede sumar mayor potencia computacional. Flexibilidad: Distribuye la carga de trabajo sobre las máquinas disponibles de la mejor forma posible.

Desventajas • • •

Software: Existe poco software disponible para sistemas distribuidos. Interconexión: Las redes se pueden saturar u ocasionar otros problemas. Seguridad: El fácil acceso también se aplica a la información secreta.

Ejercicios 1. Suponga que usted está a punto de almacenar un archivo en disco duro, y para ello tiene que saber la ubicación del mismo. El Sistema Operativo que utiliza le permite aprovechar los recursos de todo un conjunto de computadoras. En este caso ¿qué tipo de Sistema Operativo estará utilizando? a) Centralizado b) Distribuido c) De red d) De tiempo compartido 2. Suponga que usted inicia una tarea en su máquina y está trabajando en un sod, esta tarea está compuesta de varios procesos, el sistema operativo coloca los procesos en donde más convenga sin su conocimiento. ¿Qué tipo de transparencia está manejando? a) De migración b) De réplica c) De acceso d) De localización 3. La redundancia en hardware permite que un Sistema Operativo sea tolerante a fallas. A esta característica se le llama: a) Transparencia b) Desempeño c) Escalabilidad d) Confiabilidad 24

4. Suponga que usted ejecuta una tarea que exhibe un paralelismo de grano fino en un sod, que consiste de un conjunto de computadoras personales con un solo procesador. La característica que de sod que se vería afectada con este tipo de trabajos es: a) Desempeño b) Flexibilidad c) Escalabilidad d) Confiabilidad 5. La estructura de un sistema operativo en donde el núcleo contiene funciones básicas y otras funciones no tan básicas para mejorar el desempeño se llama: a) Monolítico b) Micronúcleo c) Exokernel d) Híbrido 6. La diferencia principal entre un Sistema Operativo de red y un Sistema Operativo distribuido es (Seleccione todas las que apliquen): a) El so de red aprovecha recursos como disco duro y memoria de otras computadoras y el so distribuido el procesador. b) El so distribuido aprovecha recursos de otras computadoras de manera que el usuario no se de cuenta, y el so de red no. c) El so de red permite al usuario conectarse a la máquina que quiera, y el so distribuido no lo permite. d) El so distribuido aparece ante el usuario como la imagen de un único sistema y el so de red no. 7. Los Sistemas Distribuidos son: a) sistemas fuertemente acoplados en software y fuertemente acoplados en hardware b) sistemas fuertemente acoplados en software y débilmente acoplados en hardware c) sistemas débilmente acoplados en software y fuertemente acoplados en hardware d) sistemas débilmente acoplados en software y débilmente acoplados en hardware 8. Suponga que estamos trabajando en un sod y al listar el contenido del directorio x en la máquina 1 su contenido es el siguiente: hola.txt juegos programa.c Al listar el contenido de la carpeta x en la máquina 2 vemos el mismo contenido y así para cada una de las máquinas conectadas al sistema. Decimos entonces que el sod cuenta con la característica de: a) Transparencia b) Flexibilidad c) Sistema de archivos global d) Reconfiguración 25

9. Mencione la principal desventaja de un sod ____________________ 10. Los sistemas distribuidos son e) Sistemas fuertemente acoplados en software y fuertemente acoplados en hardware f) Sistemas fuertemente acoplados en software y débilmente acoplados en hardware g) Sistemas débilmente acoplados en software y fuertemente acoplados en hardware h) Sistemas débilmente acoplados en software y débilmente acoplados en hardware

Referencias

Tanenbaum, Andrew S. Sistemas Operativos Modernos. Segunda Edición. Prentice Hall. Pearson Education. México, 2003. Carretero Pérez, Jesús; De Miguel Anasagasti, Pedro; García Carballeira, Féliz; Pérez Costoya, Fernando. Sistemas Operativos. Una visión Aplicada. Mc Graw Hill. España, 2001. William Stallings. Sistemas Operativos, Prentice may, 4ta Edición. Prentice may. Haviland, Keith; Salama, Ben. Unix System Programming. Addison-Wesley Publishing Company. Flynn, Ida M.; McIver McHoes, Ann. Sistemas Operativos. Tercera Edición. Thomson Learning. México, 2001. Chow, Jhonson. Distributed Operating Systems & Algorithms, Addison Wesley.

26

III Gestión de procesos e hilos en ambientes centralizados y distribuidos

3.1 Conceptos básicos de procesos e hilos Proceso. Es un programa en ejecución, consta del programa ejecutable, datos y pila, contador, registros e información adicional necesaria para ejecutar el programa. El código se compone de instrucciones de máquina y llamados a servicios del sistema. Toda la información asociada a un proceso se almacena en una tabla del so conocida como tabla de procesos. El intérprete de comandos o shell es un proceso que lee los comandos a partir de una terminal, y crea un proceso que se encarga de la ejecución del comando. Los procesos creados por otro proceso se llaman procesos hijo. •

• • • • •

A veces es importante que los procesos se comuniquen entre sí, la comunicación entre procesos puede darse en una sola máquina o entre máquinas distintas (a través de la red) mediante paso de mensajes o señales (análoga a una interrupción de hw pero en sw). Es importante saber a qué usuario pertenece cada proceso. Cada usuario tiene asociado un id (entero de 16 ó 32 bits). Varios procesos pueden correr el mismo programa, pero cada uno de ellos es un proceso distinto con su propio estado. Un proceso consiste de código, datos y demás atributos. El código se compone de instrucciones de máquina y llamados a servicios del sistema.

El estado de un proceso consiste de al menos: •

El código para el programa ejecutándose 27

• • • • • • •

Los datos estáticos para el programa ejecutándose Espacio para datos dinámicos El contador del programa, indicando la próxima instrucción Un stack de ejecución con el stack pointer Valores de registros de cpu Un conjunto de recursos en uso del so (archivos abiertos, conexiones a otros programas, etc.) El estado del proceso

Entorno del proceso. Es un conjunto de variables que se le pasan al proceso en el momento de su creación, el cual está formado por una tabla nombre-valor que se incluye en la pila del proceso. el nombre especifica el nombre de la variable y el valor su valor. Ejemplo de entorno en unix: path=/usr/bin:/home/pepe/bin term=vt100 home=/home/pepe pwd=/home/pepe/libros/primero

Grupo de procesos. Los procesos forman grupos que tienen diversas propiedades, se pueden realizar diversas operaciones sobre todos los procesos de un determinado grupo, por ejemplo matar a todos los procesos pertenecientes a un mismo grupo.

Interrumpido a Termin

Ejecutándose

Dormido

Espera

por un

Despachado

Creado

Listo

Esperando

o l event

e Ocurre

Diagrama de Transición de Estados 28

evento

Estados de un proceso • • •

•

Dormido. Proceso inexistente. Sólo se indica para uso de una tabla de procesos Listo. Cuando un proceso es creado se pasa a una cola de procesos listos para ejecutarse los procesos listos no tiene recursos asignados. Ejecutándose. El proceso tiene todos los recursos necesarios para su ejecución. Si se dispone de un solo procesador, solamente un proceso puede estar ejecutándose. Este puede ser interrumpido y pasar a la cola de listos. Esperando. Espera a que ocurra un evento externo, no tiene recursos asignados. Cuando el evento ocurre el proceso suspendido normalmente pasa a la cola de listos a esperar que se le otorgue nuevamente un turno para el uso del procesador.

El núcleo del Sistema Operativo se encarga de hacer las transiciones de los diferentes procesos a fin de que ellos puedan ser creados, ejecutados y terminados. Implantación de los procesos (Tabla de procesos) El Sistema Operativo agrupa toda la información que necesita conocer acerca de un proceso en particular en una estructura de datos denominada bloque de control de proceso o descriptor de proceso (pcb). El bloque de control de procesos contiene muchas piezas de información asociadas con un proceso específico, incluyendo: • • •

• • • •

Estado del proceso. Contador de programa. Indica la dirección de la siguiente instrucción que va a ejecutar el proceso. Registros de cpu. Varían en número y tipo dependiendo de la arquitectura de la computadora. Incluyen: acumuladores, registros índice, registros de propósito general y cualquier información de la condición del código. Información del manejo de memoria. Incluye todo tipo de información acerca de la memoria que está siendo utilizada por el proceso. Información de contabilidad. Incluye: tiempo de cpu usado, tiempo límite, número de cuenta, número de proceso, etc. Información del estado de e/s. Incluye el estado de las solicitudes de entrada y salida enviadas por el proceso, los dispositivos asignados a él, la lista de archivos abiertos, etc Información para el despacho del proceso. Incluye la prioridad del proceso, apuntadores a las colas de despacho y cualquier otro parámetro necesario para el despacho del proceso. 29

Lista de procesos esperando

Lista de procesos dormidos

Lista de procesos listos

Tabla de control de procesos Toda la información de los pcb´s reside generalmente en una tabla de bloques de control de procesos. En la cual se organizan listas de procesos listos, listas de procesos suspendidos y lista de procesos dormidos. Cambio de contexto Cuando ocurre una transición de un proceso que se está ejecutando a otro estado, el núcleo selecciona otro proceso de la cola de listos para ejecutarse. Entonces se debe restablecer 30

el ambiente adecuado para la ejecución del proceso seleccionado, este ambiente incluye la definición de los registros de cpu, su contador de programa, etc. A esta actividad se le denomina cambio de contexto. Servicios del Sistema Operativo para el manejo de procesos Entre los llamados al sistema operativo debe existir un conjunto específico para el manejo de procesos entre los cuales se deben encontrar los siguientes: • • • • •

Crear proceso (fork) Borrar proceso Cambiar la prioridad al proceso Interrumpir proceso Obtener los atributos de un proceso

Procesos ligeros (subprocesos o threads, hilos) Un proceso ligero es un programa en ejecución que comparte la imagen de memoria y otras informaciones con otros procesos ligeros. Cada proceso ligero tiene información propia y no la comparte con otros procesos ligeros, tal como: • • • •

Contador de programa Pila Registros Estado del proceso ligero (ejecutando, listo o bloqueado)

Todos los procesos ligeros de un mismo proceso comparten la información del mismo. Como: • • • • • • •

Espacio de memoria Variables globales Archivos abiertos Procesos hijos Temporizadores Señales y semáforos Contabilidad 31

El estado del proceso será la combinación de los estados de sus procesos ligeros. Una ventaja de los procesos ligeros es que permiten paralelizar una aplicación. Comparando el uso de los procesos ligeros con otras soluciones se puede decir que los procesos ligeros permiten paralelismo y variables compartidas así como que utilizan llamadas al sistema bloqueantes por proceso ligero. En un proceso convencional con un solo proceso ligero no hay paralelismo y utiliza llamadas al sistema bloqueantes. Varios procesos convencionales cooperando permite paralelismo y no comparte variables, por lo que la comunicación puede consumir mucho tiempo.

El paralelismo que permiten los procesos ligeros, unido a que comparten memoria (utilizan variables globales que ven todos ellos), permite la programación concurrente. En este tipo de programación hay que garantizar que el acceso a los datos compartidos se haga de forma correcta. Planificación en posix Posix especifica una serie de políticas de planificación, aplicables a procesos y procesos ligeros. Cada unidad ejecutable lleva asociada una política de planificación y una prioridad. Cada política de planificación lleva asociada un rango de prioridades. posix especifica que cada implementación debería ofrecer un rango, de al menos, 32 niveles de prioridad. El planificador elegirá siempre para ejecutar el proceso o proceso ligero con la prioridad más alta. Las políticas de planificación disponibles en posix son las siguientes: fifo:

Los procesos que se planifica según esta política se introducen al final de la cola de su prioridad asociada. Un proceso con esta política de planificación será expulsado de la cpu únicamente cuando ejecute una llamada bloqueante al sistema o cuando aparezca en el sistema un proceso con más alta prioridad. El comportamiento para este tipo de despachador es el siguiente:

•

• • •

Si un proceso es expulsado de la cpu por otro de mayor prioridad, el proceso expulsado para a ser el primero de la cola asociada a su prioridad. Cuando un proceso bloqueado pasa a listo para ejecutar, el proceso se introduce al final de la cola asociada a su prioridad. Cuando un proceso cambia su prioridad o su política de planificación, utilizando los servicios adecuados, se realiza una replanificación. Si como resultado de ésta el proceso resulta expulsado, éste se introduce al final de la cola de procesos de su prioridad. 32

Cíclica: Los procesos de cada nivel de prioridad se planifican según una política de planificación cíclica con una determinada rodaja de tiempo. El comportamiento del despachador es el siguiente:

•

• •

Cuando un proceso acaba su rodaja de tiempo, se introduce al final de la cola de procesos de su prioridad. Cuando un proceso es expulsado por otro de mayor prioridad, se introduce al principio de su cola sin restaurar su rodaja de tiempo. De esta forma, cuando el proceso continúe su ejecución, lo hará hasta que consuma el resto de su rodaja de tiempo.

Otra: Esta depende de cada implementación. De acuerdo al estándar posix, todo sistema operativo que siga el estándar posix debe ofrecer la políticas al menos las dos políticas anteriores, pudiendo además ofrecer cualquier otra.

•

Planificación en Windows nt/2000 En Windows nt la unidad básica de ejecución es el proceso ligero y, por tanto, la planificación se realiza sobre este tipo de procesos. Los estados de un proceso ligero que maneja este sistema operativo son: • • •

• •

•

Listo. Proceso listo para ejecutarse. Reserva. Proceso ligero que será el siguiente proceso ligero a ejecutar en un procesador determinado. Sólo puede haber un proceso ligero en este estado por procesador. Ejecución. El proceso ligero permanece ejecutándose hasta que se cumpla una de las siguientes condiciones: el sistema operativo lo expulsa para ejecutar un proceso ligero de mayor prioridad, la rodaja de tiempo del proceso termina o bien el proceso ligero finaliza su ejecución. Bloqueado. Cuando el proceso ligero deja de estar bloqueado puede, dependiendo de su prioridad, comenzar su ejecución inmediatamente o pasar al estado de listo para ejecutar. Transición. Un proceso ligero entra en este estado cuando esta listo para ejecutar, pero la pila que utiliza el sistema operativo para este proceso no reside en la memoria principal. Cuando la página vuelva a memoria, el proceso ligero pasará al estado de listo para ejecutar. Finalizado. Cuando un proceso ligero finaliza su ejecución pasa a este estado. Una vez terminado, el proceso puede o no ser eliminado del sistema. En caso de no ser eliminado, podría ser reutilizado.

33

Windows nt implementa una planificación cíclica con prioridades y con expulsión. En Windows nt existen 32 niveles de prioridad, de 0 a 31, siendo el 31 el nivel de prioridad máximo. Estos niveles se dividen en tres categorías: • • •

Dieciséis niveles con prioridades de tiempo real (niveles 16 al 31). Quince niveles con prioridades variables (niveles 1 al 15). Un nivel de sistema (0).

Todos los procesos ligeros en el mismo nivel se ejecutan según una política de planificación cíclica con una determinada rebanada de tiempo. En la primera categoría, todos los procesos tienen una prioridad fija. En la segunda, los procesos comienzan su ejecución con una determinada prioridad y ésta va cambiando durante la vida del proceso, pero sin llegar al nivel 16. Esta prioridad se modifica según el comportamiento que tiene el proceso durante su ejecución. Así, un proceso ve decrementada su prioridad si acaba la rebanada de tiempo. En cambio, si el proceso se bloquea, su prioridad aumentará. Con esto se persigue mejorar el tiempo de respuesta de lo procesos interactivos que realizan e/s. 3.2 Despacho en Sistemas Centralizados Despacho. Conjunto de políticas y mecanismos construidos en el sistema operativo que gobiernan el orden en el cual se realiza la carga de trabajo del sistema. Despachador. Módulo del sistema operativo que selecciona el siguiente trabajo a ser admitido en el sistema y el siguiente proceso a ejecutarse. El objetivo principal del despachador es optimizar la eficiencia del sistema de acuerdo con criterios considerados importantes para el ambiente del sistema operativo. 3.2.1 Criterios de despacho Porcentaje de utilización del cpu. Es la fracción de tiempo durante la cual el cpu está ocupado. Throughput. La cantidad de trabajo terminado por unidad de tiempo. Tiempo de terminación. Tiempo que transcurre desde el momento en que un programa o un trabajo es sometido hasta que es terminado por el sistema. Tiempo de espera. Tiempo que un trabajo espera por el asignamiento de un recurso debido al uso compartido de recursos en ambientes multiprogramación. Tiempo de espera = tiempo de terminación – tiempo de ejecución 34

Tiempo de respuesta. En sistemas de tiempo compartido es el tiempo que transcurre desde que se presiona el último caracter de un comando hasta que se imprime el primer caracter de la respuesta. En sistemas de tiempo real es el tiempo que transcurre desde que ocurre un evento hasta que se ejecuta la primera instrucción de su rutina de servicio. • • • •

Algoritmos de despacho. Existen dos tipos de disciplinas de despacho: -Non pre-emtive. Las que permiten que el proceso en ejecución retenga la propiedad -Pre-emptive.

3.2.2 Tipos de despachadores •

•

•

• • • • •

De largo plazo. El despachador de largo plazo, cuando existe, trabaja con la cola de los trabajos en lotes y selecciona el siguiente trabajo de lotes a ejecutarse. Su objetivo principal es proporcionar una mezcla balanceada de trabajos al despachador de corto plazo. Este tipo de despachador es invocado cada vez que un proceso termina y abandona el sistema. Su utilización es relativamente poco frecuente. En términos del diagrama de transición de estados de un proceso, el despachador de largo plazo se encarga de la transición de un proceso del estado de dormido al estado de listo. De mediano plazo. Cuando existen procesos que necesitan un uso intensivo de las facilidades de entrada y salida, y que por ello permanezcan suspendidos, puede ser que éstos procesos se quiten temporalmente de memoria principal y se guarden en memoria secundaria, hasta que su condición de espera haya concluido (a esta actividad se le conoce como ]“swapping”), para darle oportunidad a otros procesos que quieran ser admitidos. El despachador de mediano plazo se encarga del manejo de procesos que temporalmente se han enviado a memoria secuandaria. En términos del diagrama de transición de estados, el despachador de mediano plazo se encarga de la transición suspendido a listo. De corto plazo. El despachador de corto plazo asigna el cpu entre los procesos listos en memoria principal. Su objetivo principal es maximizar la eficiencia del sistema de acuerdo con ciertos criterios. Ya que se encarga de las transiciones de listo a ejecutándose. En la práctica, el despachador de corto plazo se invoca cada vez que ocurre un evento que modifique el estado global del sistema. Algunos eventos que provocan tales cambios son: Pulsos de reloj (interrupciones de tiempo) Interrupciones y terminaciones de e/s La mayoría de los llamados operacionales al Sistema Operativo Envío y recepción de señales Activación de programas interactivos 35

3.2.3 Algoritmos de despacho Estos algoritmos se pueden agrupar en: • • •

Calendarización en sistemas por lotes Calendarización en sistemas interactivos Calendarización en sistemas de tiempo real

a) Calendarización en sistemas por lotes: • • • • 1. 2. 3.

Primero en llegar, primero en salir Trabajo más corto primero Tiempo restante más corto a continuación Calendarización de tres niveles Calendarizador de admisión Calendarizador de memoria Calendarizador de cpu

CPU

Memoria principal Trabajo que llega

Calendarizador de admisión

Calendarizador de CPU

Disco

Calendarizador de memoria

b) Calendarización en sistemas interactivos • •

Calendarización por turno circular (Round-Robin). Un cuanto de 20-50ms es razonable. Calendarización por prioridades. Para que ningún proceso de baja prioridad espere infinitamente en ser atendido, cada vez que un proceso de alta prioridad es despachado se le baja su prioridad, o se utiliza un umbral, donde cada vez que un proceso de baja prioridad 36

•

es discriminado se incrementa un contador. Cuando el contador llegue a ser igual al umbral, entonces el despachador ya no podrá discriminarlo. Las asignación de prioridades a los procesos puede ser dinámica o estática. Múltiples colas

Prioridad 4

Más alta prioridad

Prioridad 3 Prioridad 2 Prioridad 1

Más baja prioridad

En cada turno se baja la prioridad al proceso que se acaba de ejecutar • • •

•

Proceso más corto a continuación. Calendarización garantizada. Darle a cada proceso la rebanada de tiempo que sea más adecuada para él. Calendarización por lotería. Se reparten boletos a los procesos y el despachador elige uno; el proceso ganador es el que es ejecutado. Si un proceso es más importante o más interesante que los demás, se le dan más boletos, así su probabilidad de ganar el procesador es más alta. Los procesos que cooperan entre sí pueden intercambiar boletos para tener más probabilidades de ganar el cpu. Calendarización por porción equitativa. Se utiliza turnos circulares o prioridades uniformes.

c) Calendarización en sistemas en tiempo real Se pueden clasificar a estos sistemas en: • •

Tiempo real estricto. Aquel que no da plazos, sus plazos son absolutos. Tiempo real no estricto. Permite incumplimientos ocasionales.

Los sucesos en un Sistema en Tiempo Real se pueden clasificar en: • •

Periódicos. Se presentan en intervalos regulares Aperiódicos. Cuya ocurrencia en impredecible

Los algoritmos de calendarización para sistemas en tiempo real pueden ser estáticos o dinámicos. 37

Los primeros toman sus decisiones de calendarización antes de que el sistema comience a ejecutarse. Los segundos toman las decisiones en tiempo de ejecución. 3.3 Despacho en sistemas operativos distribuidos Los procesos no comparten el mismo espacio de direcciones y no tienen nada que ver uno con otro. Para comunicarse utilizan primitivas de comunicación como memoria compartida, tuberías y paso de mensajes. 3.3.1 Modelos de Sistemas El modelo de estación de trabajo Este modelo consiste de estaciones de trabajo (ws) dispersas en un edificio o campus y conectadas entre sí por medio de una lan. Las ws de trabajo pueden tener discos locales o no. Estaciones de trabajo sin disco Si las ws carecen de disco, el sistema de archivos debe ser implantado en uno o varios servidores de archivos de red. Ventajas • • • •

Precio más bajo. Fácil mantenimiento y respaldo. Al cambiar de versión de software o instalar uno nuevo, sólo se tiene que instalar en pocos servidores. Son silenciosas (no tienen ventiladores). Proporcionan simetría y flexibilidad. Un usuario puede entrar a cualquier estación de trabajo y entrar al sistema.

Desventajas • •

Se debe contar con uno o más servidores de archivos equipados con discos enormes y rápidos a los cuales se tiene acceso mediante una lan. Gran uso de la red que puede llevar a cuellos de botella.

38

Estaciones de trabajo con disco Formas en las que se puede utilizar el disco: 1.

2.

3.

4.

Para paginación y archivos temporales, los cuales se eliminan al finalizar la sesión. Su ventaja es reducir la carga de la red comparado con el caso sin disco, y su desventaja es el alto costo debido al gran número de discos duros. Para paginación, archivos temporales y binarios del sistema, tales como compiladores, editores de texto, controladores de correo electrónico, etc. Este esquema reduce aún más la carga sobre la red. Su desventaja es el alto costo y la complejidad adicional para actualizar los binarios. Para paginación, archivos temporales, binarios del sistema y sistema de ocultamiento de archivos. Los usuarios pueden cargar archivos desde los servidores de archivos hasta sus propios discos, leerlos y escribir en ellos en forma local, y después regresar los archivos modificados al final de la sesión. El objetivo es mantener centralizado el almacenamiento a largo plazo, pero reducir la carga en la red. Su principal desventaja es que puede tener problemas de consistencia del caché. Un sistema local de archivos completo. Su ventaja es la escasa carga en la red y que elimina la necesidad de los servidores de archivos. Pero hay pérdida de transparencia y es más parecido a un sistema operativo de red.

Otros problemas relacionados con este modelo son los siguientes: Si los circuitos siguen abaratándose pronto será posible proporcionar a cada usuario varios cpu, pero serían demasiados en un solo lugar; además surgiría otro problema, la asignación de recursos sería ineficiente ya que algunos usuarios recibirían recursos que no necesitan mientras que otros usuarios si los necesitan. Uso de estaciones de trabajo inactivas El problema en el modelo de estaciones de trabajo (ws) es que existen ws inactivas o subutilizadas. La primera solución a este problema fue proporcionar el comando rsh (unix Berkeley), con este comando se puede ejecutar en una máquina remota un comando. Para llevar a cabo la ejecución remota de un comando en una máquina inactiva mediante rsh se debe tener un registro acerca de cuál ws esta inactiva. Además el proceso

39

que se ejecuta en una máquina remota seguirá ejecutándose aunque llegue un usuario, quien debe aceptar el desempeño menor de su sistema o buscar otra máquina. Problemas clave a solucionar con respecto al tema de las estaciones de trabajo inactivas: 1. 2. 3.

¿Cómo encontrar una estación de trabajo inactiva? ¿Cómo lograr que un proceso remoto se ejecute en forma transparente? ¿Qué ocurre si regresa el poseedor de la máquina?

1. La estación de trabajo está inactiva cuando nadie toca el ratón o el teclado durante varios minutos y no se ejecuta algún proceso iniciado por el usuario. Los algoritmos para localizar una ws inactiva se pueden dividir en dos categorías: • •

Controlados por el servidor Controlador por el cliente

En el primer caso cuando una ws está inactiva anuncia su disponibilidad registrándose en un archivo o base de datos, da su nombre, dirección de red y propiedades. Cuando el usuario desea ejecutar un comando en una ws inactiva, mediante un comando busca en el registro la ws adecuada (el registro de ws inactivas esta centralizado con algunas copias). Otra alternativa es que la ws inactiva envíe un mensaje en toda la red. Las demás ws registran el mensaje en su propio registro. Así la búsqueda tiene menor costo y mayor redundancia. La desventaja es pedir a todas las máquinas que se encarguen de mantener el registro. Puede haber condiciones de competencia si dos usuarios descubren una misma máquina como inactiva. Para solucionar este problema, se envía un mensaje a la máquina inactiva para detectar su estado, si aún está libre, la máquina inactiva se elimina del registro. Entonces quien hizo la llamada puede enviar su ambiente e iniciar el proceso remoto. En el segundo método, controlado por el cliente, la máquina que busca una ws(ws) inactiva transmite una solicitud donde indica el programa que desea ejecutar, y los requerimientos de memoria, procesador, etc. Al regresar la respuesta se elige a una ws inactiva. Las ws inactivas retrasan sus respuestas, con un retraso proporcional a la carga actual. Así, la respuesta de la máquina con la menor carga llega primero y se selecciona. 2. Ahora hay que ejecutar el programa. El desplazamiento de código es fácil. Se debe configurar el proceso remoto de modo que vea el mismo ambiente que tendría en el caso local y llevar a cabo el cómputo de la misma forma que en el caso local. 40

Necesita la misma visión del sistema de archivos, el mismo directorio de trabajo, mismas variables de ambiente. Problemas al ejecutar un proceso en otra máquina. •

• • •

Las llamadas al sistema ¿dónde dirigirlas? ¿a la máquina origen o a la máquina remota? Por ejemplo, la lectura de teclado y escritura a pantalla son funciones que deben dirigir la solicitud a la máquina origen; pero las llamadas que tienen que ver con prioridades o tamaño de memoria deben dirigir su solicitud a la máquina remota. Llamadas al sistema relacionadas con el tiempo Seguimiento del ratón Escritura en dispositivos de hardware

3. Es fácil que el poseedor de la máquina regrese a no hacer nada, pero destruye la idea de ws personales. Otra posibilidad es eliminar el proceso intruso, advirtiéndole primero para que tenga tiempo de cerrar archivos, escribir los búferes editados en un disco, etc. Sino sale después de unos segundos el proceso es terminado. Otro método es hacer que el proceso emigre a otra máquina, ya sea a la máquina origen o a alguna otra estación de trabajo inactiva. Esto es un proceso complejo. El proceso debe dejar la máquina en el mismo estado exactamente como la encontró. El modelo de pila de procesadores Se construye una pila de procesadores, repleta de cpu, en un cuarto de máquinas, los cuales se pueden ejecutar de forma dinámica a los usuarios según la demanda. A cada usuario se le da una terminal gráfica de alta rendimiento, como las terminales x, incluso se pueden utilizar terminales ascii. Ventajas • • •

Precio Elimina la asociación entre el número de usuarios y el de ws Facilita el crecimiento por incrementos

De hecho se convierte el poder de cómputo en ws inactivas, a las que se puede tener acceso de manera dinámica. Aquí no existe el concepto de propiedad. 41

El principal argumento para la centralización del poder de cómputo como pila de procesadores proviene de la teoría de colas. Los sistemas de colas son útiles, puesto que es posible modelarlos de forma analítica. Sea λ la tasa de entradas totales de solicitudes por segundo de todos los usuarios combinados. Sea μ la tasa de procesamiento de solicitudes por parte del servidor. Para una operación estable debemos tener μ > λ. Si el servidor procesa menos solicitudes que las que los usuarios generan, la cola crecerá sin límite. El promedio de tiempo entre la emisión de una solicitud y la obtención de una respuesta completa está relacionado con λ y μ mediante la fórmula: T=1/(μ - λ)

1)

Si tenemos n computadoras, T estará dado en cada computadora como en 1). Ahora si reemplazamos estos n pequeños recursos por uno grande que sea n veces más poderoso, entonces tenemos: T=1/(nμ - nλ) = T/n Se reduce el tiempo promedio de respuesta n veces. Por esto una pila de procesadores tiene un mejor desempeño, aunque esté en contra de los propios sistemas distribuidos. Sin embargo el tiempo promedio de respuesta no lo es todo. También está el costo, la confiabilidad y la tolerancia a fallas. Una variación en el tiempo de respuesta también puede influir. Además en muchos trabajos la pila no es n veces mejor, pues no todos los trabajos se pueden ejecutar en paralelo. Aún así, el modelo de pila de procesadores es una forma más limpia de obtener poder de cómputo adicional que la búsqueda de estaciones inactivas. Ningún procesador pertenece a alguien, no hay máquina origen, no hay peligro de que el poseedor regrese. Seleccionar pila de procesadores o estaciones de trabajo inactivas va a depender del trabajo que se desarrolle. Modelo híbrido Se puede establecer una mediación al proporcionar a cada usuario una ws personal y además tener una pila de procesadores. Esto es más caro. Para procesos interactivos sería mejor utilizar ws. Para procesos que requieren un gran poder de procesamiento y no son interactivos es más adecuado una pila de procesadores. 42

3.3.2 Planificación en sistemas distribuidos Se pueden utilizar los algoritmos de prioridad, roun robin, lotería, etc. A menudo los paquetes de hilos proporcionan ciertas llamadas para que el usuario pueda especificar el algoritmo de despacho y establecer las prioridades (si es el caso). Implantación de un paquete de hilos Existen dos métodos, en el espacio de usuario y en el espacio de núcleo. Implantación de los hilos en el espacio de usuario El núcleo no sabe de la existencia de los hilos. Ventajas • • • •

El sistema operativo no debe soportar hilos. Por ejemplo unix. La planificación y cambio de estado la realiza un Sistema de Tiempo de Ejecución a nivel de usuario. Se permite que cada proceso tenga su algoritmo de planificación adaptado. Los hilos en este espacio tienen mejor escalabilidad, puesto que los hilos del núcleo requieren algún espacio para sus tablas y su pila en el núcleo, lo cual puede ser un problema si existe un número muy grande de hilos.

Desventajas •

•

La implantación de las llamadas al sistema con bloqueo. Por ejemplo, la lectura a un pipe vacío. Se puede permitir el bloqueo a un hilo pero que no afecte a los demás. Con las llamadas al sistema con bloqueo esto no se puede lograr. Una posible solución sería modificar tales llamadas al sistema, pero cambiar el sistema operativo no es atractivo. Además uno de los objetivos de tener un paquete de hilos a nivel de usuario es poder ejecutar los Sistemas Operativos existentes. Un cambio de una llamada al sistema requeriría muchos cambios a muchos programas de usuario. Otra alternativa es revisar primero si una llamada al sistema se bloqueará utilizando la llamada select. Entonces la llamada al sistema bloqueante es reemplazada por select y luego la llamada al sistema. select verifica si la llamada es segura (no se va a bloquear), si es así se lleva a cabo, si no no se ejecuta. El código que se coloca junto a la llamada al sistema para hacer la verificación recibe el nombre de jacket. Este método requiere escribir parte de la biblioteca de llamadas. Bloqueo de las llamadas al sistema en el fallo de páginas. Si un hilo causa un fallo de páginas, el núcleo que desconoce la existencia de los hilos, bloqueará todo el proceso hasta que la página necesaria sea incluida aunque se puedan correr otros hilos. 43

•

•

•

Si un hilo comienza su ejecución, ningún otro hilo de ese proceso puede ejecutarse, a menos que el primer hilo entregue en forma voluntaria el cpu. Dentro de un proceso, no existen interrupciones de reloj, lo que imposibilita la planificación round robin. Sincronización. Cuando un hilo realiza espera ocupada esperando la respuesta de un hilo, necesita interrupciones de reloj. La espera ocupada es atractiva cuando se espera una respuesta rápida y el costo del semáforo es alto, pero se pueden dar bloqueos. Los programadores desean los hilos en aplicaciones donde esto se bloqueen a menudo, por ejemplo en un servidor de archivos.

Implantación de hilos en el núcleo El núcleo sabe de los hilos y cómo manejarlos. Éste contiene una tabla con una entrada por cada hilo, con los registros, estado, prioridades y demás información relativa al hilo. Las llamadas que pueden bloquear un hilo se implantan como llamadas al sistema, con un costo considerable. Cuando un hilo se bloquea el núcleo ejecuta otro hilo del mismo proceso o de otro proceso. Pero el programador esperaría que se ejecutara un hilo del mismo proceso. Algunos sistemas reciclan sus hilos; cuando un hilo termina y se destruye, se marca como no ejecutable pero sus estructuras de datos en el núcleo no se afectan sino que se ocupan cuando se crea otro hilo. Esto implica un ahorro. Los hilos del núcleo no requieren nuevas llamadas al sistema sin bloqueo, no conducen a bloqueos cuando se utiliza la espera ocupada. Si un hilo de un proceso provoca un fallo de página, el núcleo puede ejecutar otro hilo mientras que espera que la página requerida sea traída del disco. Los hilos en el espacio del usuario o del núcleo tienen asociados otros problemas. Muchos procedimientos no son reentrantes, por ejemplo cuando ambos hilos utilizan la variable errno o algún búfer estático. Esto sucede porque estos procedimientos no fueron escritos para hilos sino para un solo proceso. Una solución sería escribir toda la biblioteca. Otra solución consiste en proporcionar a cada quien su jacket que cierre un semáforo mutex global al iniciar el procedimiento. De hecho la biblioteca se convierte en un enorme monitor. Las señales también presentan dificultades. Asignación de procesadores Las estrategias de asignación de procesadores se pueden dividir en dos categorías amplias: • •

No migratorios. Cuando un proceso es creado se decide dónde colocarlo. Una vez colocado en una máquina el proceso permanecerá ahí hasta que termine su ejecución. Migratorios. Un proceso se puede trasladar aunque haya iniciado su ejecución. Este tipo de categorías permiten un mejor balance de carga. 44

Un algoritmo que asigne procesos a procesadores tiene como meta optimizar algún aspecto, por ejemplo los siguientes: • •

Maximizar el uso de cpu Minimizar el tiempo de respuesta

Aspectos del diseño de algoritmos de asignación de procesadores Las decisiones que deben tomar los diseñadores se pueden resumir en cinco aspectos: 1. 2. 3. 4. 5.

Algoritmos deterministas vs. heurísticos Algoritmos centralizados vs. distribuidos Algoritmos óptimos vs. subóptimos Algoritmos locales vs. globales Algoritmos iniciados por el emisor vs. iniciados por el receptor

Los algoritmos deterministas son adecuados cuando se sabe de antemano todo acerca del comportamiento de los procesos o por lo menos una aproximación razonable. Cuando la carga del sistema es completamente impredecible se utilizan técnicas heurísticas. Tener toda la información en un solo lugar permite tomar una mejor decisión, pero es menos robusta y coloca una carga pesada en la máquina central. Son preferibles los descentralizados, pero carecen de alternáticas adecuadas. Encontrar la mejor asignación, la más óptima, es más caro, pues hay que recolectar más información y procesarla más. En la práctica se buscan soluciones subóptimas, heuríticas y distribuidas. Otro aspecto llamado política de transferencia también es importante, tiene que ver con ejecutar un proceso en la máquina local o transferirlo; esta decisión depende de la carga de la máquina. Una escuela dice que la decisión se debe tomar con respecto a la información de la máquina local, si está sobrecargada (está por sobre una marca) entonces hay que migrar el proceso, si no el proceso se debe ejecutar en la máquina local. Otra escuela dice que es mejor recolectar toda la información del sistema para decidir dónde ejecutar el proceso. El último aspecto tiene que ver con lo que se llama política de localización, decidir dónde enviarlo una vez que se ha decidido migrar el proceso. En el caso de los algoritmos iniciados por el emisor, es el emisor (la máquina local que necesita colocar su proceso en otra máquina) quien envía solicitudes a las demás máquinas en busca de ayuda y de un lugar apropiado para su proceso. En el caso de los algoritmos iniciados por el receptor, 45

es el receptor quien decide que está subcargada y que necesita trabajo, así que enviar mensajes a las demás máquinas a ver quién necesita ayuda. Aspectos de la implantación de algoritmos de asignación de procesadores •

Medición de la carga • • • •

•

Los algoritmos suponen que cada máquina conoce su carga. Algunos algoritmos cuentan el número de procesos para determinar su carga. Una mejora al criterio anterior es contar sólo los procesos en ejecución o listos. Otra forma de medir la carga es determinar la fracción de tiempo que el cpu está ocupado.

Costo excesivo •

Muchos algoritmos teóricos ignoran el costo de recolectar medidas y desplazar los procesos de aquí para allá. Al desplazar un proceso se debe verificar si hay ganancia en hacerlo. Para esto hay que tomar en cuenta el uso de memoria, tiempo de cpu y ancho de banda de la red.

•

•

Complejidad • •

1.

2.

3.

Existen algoritmos que tienen un desempeño un poco mejor que otros, pero son más complejos. Eager realizó un estudio a este respecto, y para ello trabajó con tres algoritmos. Se supone que al crear un nuevo proceso en una máquina ésta se sobrecargará, por lo tanto hay que desplazar el proceso a otro lugar. Se elige una máquina al azar y se envía el proceso, si la máquina está subcargada entonces aceptará el proceso, en caso contrario se repite la operación hasta que alguien acepte el proceso o se exceda un contador de tiempo. Se elige una máquina al azar y se le pregunta si está subcargada, si su respuesta es afirmativa entonces la máquina origen le envía el proceso, si no se repite la operación con otra máquina elegida al azar y así hasta encontrar una máquina adecuada o se exceda el número de pruebas, en cuyo caso permanecerá en el sitio de su creación. Se analizan k máquinas para determinar sus cargas exactas. El proceso se envía a la máquina con la carga más pequeña. El mejor algoritmos es el 3, sin embargo el algoritmo 2 tiene un desempeño casi igual al 3, pero es más sencillo. La conclusión a la que llegó Eager fue: “Si el uso de un algoritmo sencillo proporciona casi la misma ganancia que uno más caro y más complejo, es mejor utilizar el más sencillo”.

46

•

Estabilidad •

El sistema nunca está en equilibrio por la actualización constante de las tablas de las máquinas, así una máquina podría pensar que otra está actualizada sin que sea así.

Ejemplo de algoritmos de asignación de procesadores, un algoritmo determinista según la teoría de gráficas Para sistemas que constan de procesos con requerimientos conocidos de cpu y memoria, además de una matriz conocida con el tráfico promedio entre cada pareja de procesos. Si el número de cpu es menor que el número de procesos, habrá que asignar varios procesos al mismo cpu. La idea es llevar a cabo esta asignación de forma que se minimice el tráfico en la red. Sea la siguiente gráfica de procesos, los arcos indican el nivel de comunicación entre los procesos. Una posible asignación es la siguiente:

cpu1

cpu2

3

B

cpu3

2

C

3

D

A 1 F

2

2 E

8 5

4

6 3

1

30 unidades

5

4 G 4

2

H

cpu1 3

B

cpu2 2 C

I

cpu3 3

D

A 1 F

2

2 E

8 5

4

6 3

1

28 unidades

5

4 G 4

H

2

I

Podemos observar que la segunda asignación es la mejor. 47

Un algoritmo centralizado Arriba-abajo (Mutka y Livny, 1987) es centralizado. Usa una tabla de uso, con una entrada por cada estación de trabajo personal. Si un proceso se ejecuta en otra máquina, la máquina origen acumula puntos de penalización cada segundo. Si tiene solicitudes pendientes no satisfechas, los puntos de penalización se restan de su entrada en la tabla de usos. Si no existen solicitudes pendientes y ningún procesador esta en uso, la entrada de la tabla de usos se desplaza un cierto número de puntos hacia el cero. Si la puntuación asociada a una estación de trabajo en la tabla de usos es positiva, indica que la estación de trabajo es un usuario de los recursos del sistema. Si tiene una puntuación negativa indica que necesita recursos, si es cero es neutra. El objetivo de este algoritmo es asignar la capacidad de manera justa. Su desventaja es que en sistemas grandes con muchos nodos crea cuellos de botella. Un algoritmo jeráquico Para este tipo de algoritmo es necesaria una gran cantidad de procesadores, los cuales se agrupan por jerarquías, en un primer nivel (el nivel más alto) un grupo de procesadores forman el comité de coordinadores, en el siguiente nivel están los jefes de departamento. Los niveles pueden ser n, todo dependerá del número de procesadores. En el último nivel están los trabajadores. Este algoritmo es utilizado en el sistema micros. Cuando una tarea requiere de varios procesadores, entonces la solicitud se hace a los jefes de departamento (o el nivel anterior al de los trabajadores), si éstos no la pueden resolver la envían a su jefe inmediato, hasta alcanzar un nivel en donde se pueda resolver el problema. El administrador divide la solicitud en partes y los esparce entre los administradores por debajo de él, quienes repiten la operación hasta llegar a los trabajadores. Se señalan a los procesadores elegidos para realizar la tarea como ocupados y se informa de regreso en el árbol. Comité de Coordinadores

coordinadores

Jefes de departamento

Trabajadores

48

Un algoritmo heurístico distribuido iniciado por el emisor Este es el segundo algoritmo de Eager mencionado en páginas anteriores. La desventaja de éste es que si casi todas las ws están sobrecargadas entonces se enviarán pruebas de forma constante en vano. La red se sobrecargará cuando más trabajo existe. Un algoritmo heurístico distribuido iniciado por el receptor Este algoritmo es complementario al anterior. Cuando un proceso termina, el sistema verifica si la ws donde terminó el proceso tiene suficiente trabajo. En caso contrario, elige alguna máquina al azar y le solicita trabajo. Si no encuentra trabajo en n pruebas, el receptor deja de preguntar por cierto tiempo, e intenta de nuevo. Este algoritmo crea tráfico en la red cuando las ws están subcargadas (desempleadas), pero es mejor en este momento y crea tráfico cuando el sistema está sobrecargado. Una posible modificación a este algoritmo es combinar el algoritmo anterior y éste. Si una ws está sobrecargada deberá intentar deshacerse de trabajo, y cuando esté subcargada debe tratar de conseguir trabajo. Se puede manejar un historial de máquinas que estén crónicamente subcargadas o sobrecargadas. Un algoritmo de remates Este algoritmo fue creado por Ferguson. En este caso se crea una comunidad económica en donde los procesos compran tiempo de cpu para terminar su trabajo. Los procesadores venden sus ciclos al mejor postor. El precio de un procesador va de acuerdo a su velocidad, tamaño de memoria, hardware y a lo que pagó el último cliente, incluso el tiempo de respuesta. Cuando se desea iniciar un proceso hijo, verifica si alguien ofrece el servicio que necesita y elije el mejor. Genera una oferta. Los procesadores reúnen todas las ofertas y eligen una. Se informa a los ganadores y perdedores. 3.4 Comunicación entre procesos en ambientes distribuidos La diferencia más importante entre un sistema distribuido y un sistema con un procesador es la comunicación entre procesos. En un sistema con un procesador se supone la existencia de una memoria compartida, lo cual no existe en un sistema distribuido. La comunicación entre procesos debe respetar reglas llamadas protocolos. 49

3.4.1 Modelos por capas Para que dos procesos logren la comunicación se deben poner de acuerdo en varios aspectos como, cuántos voltios hay que utilizar para señalar un bit 0 y un bit 1; cómo detectar el fin de un mensaje, etc. Para facilitar este trabajo la organización internacional de estándares (internacional standards organization- iso) ha desarrollado un modelo de referencia llamado el modelo de referencia para interconexión de sistemas abiertos, lo cual se abrevia como iso, osi o el modelo osi. El modelo osi está diseñado para permitir la comunicación de los sistemas abiertos. Un sistema abierto es aquel preparado para comunicarse con cualquier otro sistema abierto mediante estándares que gobiernan el formato, contenido y significado de los mensaje enviados y recibidos. Un protocolo es un acuerdo entre las partes acerca de cómo debe desarrollarse la comunicación. El modelo osi maneja dos tipos generales de protocolos (conexiones). • •

Protocolos orientados a la conexión. Antes de intercambiar datos, el emisor y el receptor deben establecer en forma explícita una conexión y tal vez el protocolo. Protocolos sin conexión. No es necesaria una negociación previa. En el modelo osi la comunicación se divide en siete niveles o capas. Cada capa se maneja de forma independiente y se encarga de un aspecto específico. Cada capa proporciona una interfaz con la capa por encima de ella. La interfaz es un conjunto de operaciones que juntas definen el servicio que la capa está preparada para ofrecer a sus usuarios.

La ventaja de un protocolo por capas es su independencia, ya que una capa puede modificarse o mejorarse sin afectar a las demás. En el modelo osi cuando se va a enviar un mensaje éste pasa por todas las capas comenzando en la de Aplicación. Cada capa le coloca un encabezado al frente o al final, al llegar el mensaje al otro lado, cada capa lo va desmenuzando, quitándole el encabezado que le corresponde; la capa que recibe el mensaje es la capa física. Capas Física, Enlace de Datos, Red, Transporte, Sesión, Presentación, Aplicación La colección de protocolos utilizados en un sistema particular se llama una serie de protocolos o pila de protocolos. 50

Capa física Su propósito es transportar el flujo de bits de una máquina a otra. El protocolo de la capa física se encarga de la estandarización de las interfaces eléctricas, mecánicas y de señalización. Maneja elementos como la intensidad de la señal de red, cables, enchufes, voltajes, distancias entre cables. Capa de enlace de datos La tarea principal de esta capa es agrupar a los bits en unidades llamadas marcos o tramas, y detectar y corregir errores. Uno de los mecanismos en la detección de errores es asignar números secuenciales a las tramas y a cada trama colocarle una suma de verificación, si no está correcta la suma de verificación a la hora de recibir el marco, entonces el receptor le pide al transmisor que vuelva a transmitir el marco x. Capa de red La tarea principal de la capa de red es elegir la mejor ruta (a esta actividad se le llama ruteo), la ruta más corta no siempre es la mejor, lo importante es la cantidad de retraso, y esto complica los algoritmos de ruteo. La capa de red maneja dos protocolos: x.25 (orientado a la conexión) y el ip (sin conexión). Capa de transporte La tarea de la capa de transporte es proporcionar conexiones confiables y económicas. Las conexiones confiables (orientadas a la conexión) se pueden construir por arriba de x.25 o ip. En x.25 los paquetes llegan en orden, en ip no, entonces la capa de transporte es la encargada de ponerlos en orden. El protocolo de transporte oficial iso tiene cinco variantes, tp0, tp1,… tp4. Los protocolos más utilizados en esta capa son: tcp (Transmisión Control ProtocolProtocolo para el Control de Transmisiones), orientado a la conexión y udp (Universal Datagrama Protocol- protocolo Datagrama Universal) que es un protocolo sin conexión. Capa de sesión Esta es en esencia una versión mejorada de la capa de transporte. Proporciona el control del diálogo facilidades en la sincronización, la posibilidad de establecer conexiones llamadas sesiones y la posibilidad de transferir datos sobre las sesiones en forma ordenada. En la práctica rara vez las aplicaciones soportan esta capa.

51

Capa de presentación Esta capa trata los problemas relacionados con la representación y el significado de los datos. Capa de aplicación Es una colección de varios protocolos para actividades comunes como el correo electrónico, la transferencia de archivos y la conexión entre terminales remotas a las computadoras en una red. Esta capa contiene los programas de usuario. Protocolos utilizados: x.400 para correo electrónico, x.500 para el servidor de directorios. 3.4.2 Modelo cliente servidor El modelo cliente-servidor es un modelo de computación en el que el procesamiento requerido para ejecutar una aplicación o conjunto de aplicaciones relacionadas se divide entre dos o más procesos que cooperan entre sí. Usualmente la mayoría del trabajo pesado se hace en el proceso llamado servidor y el proceso cliente sólo se ocupa de la interacción con el usuario. Los principales componentes del esquema cliente-servidor son entonces los Clientes, los Servidores y la infraestructura de comunicaciones. Los Clientes interactúan con el usuario, usualmente en forma gráfica. Frecuentemente se comunican con procesos auxiliares que se encargan de establecer conexión con el servidor, enviar el pedido, recibir la respuesta, manejar las fallas y realizar actividades de sincronización y de seguridad. Los Servidores proporcionan un servicio al cliente y devuelven los resultados. En algunos casos existen procesos auxiliares que se encargan de recibir las solicitudes del cliente, verificar la protección, activar un proceso servidor para satisfacer el pedido, recibir su respuesta y enviarla al cliente. Además deben manejar los interbloqueos, la recuperación ante fallas, y otros aspectos afines. Por las razones anteriores la plataforma computacional asociada con los servidores es más poderosa que la de los clientes. Por esta razón se utilizan pcs poderosos, estaciones de trabajo, minicomputadores o sistemas grandes. Además deben manejar servicios como administración de la red, mensajes, control y administración de la entrada al sistema (“login”), auditoría y recuperación y contabilidad. Usualmente en los servidores existe algún tipo de servicio de bases de datos. Para que los clientes y los servidores puedan comunicarse se requiere una infraestructura de comunicaciones la cual proporciona los mecanismos básicos de direccionamiento y transporte. La mayoría de los sistemas Cliente/Servidor actuales se basan en redes 52

locales y por lo tanto utilizan protocolos no orientados a conexión, lo cual implica que las aplicaciones deben hacer las verificaciones. La red debe tener características adecuadas de desempeño, confiabilidad, transparencia y administración. Como ejemplos de clientes pueden citarse interfaces de usuario para enviar comandos a un servidor, apis para el desarrollo de aplicaciones distribuidas, herramientas en el cliente para hacer acceso a servidores remotos (por ejemplos servidores de sql) o aplicaciones que solicitan acceso a servidores para algunos servicios. Como ejemplos de servidores pueden citarse servidores de ventanas como x-windows, servidores de archivos como nfs, servidores para el manejo de bases de datos, como los servidores de sql, servidores de diseño y manufactura asistidos por computador, etc 3.4.3 Llamada a un procedimiento remoto (rpc) Birrel y Nelson abordaron este tema en 1984. En este esquema el programador no se preocupa por la transferencia de mensajes. Mediante rpc se puede invocar la ejecución de un procedimiento en la máquina a que no está en a, sino en b. Operación básica de rpc. De manera convencional, cuando un procedimiento es invocado, la dirección que tiene el registro apuntador a la próxima instrucción (ip) es almacenada en la pila, y el registro apuntador será cargado con la dirección del procedimiento invocado, cuando el procedimiento invocado termina, entonces el registro ip es cargado con la dirección que esta en el tope de la pila y sigue la ejecución del programa. En la mayoría de los casos es necesario enviar parámetros de entrada y obtener parámetro de salida. Los lenguajes de programación como c, utilizan dos tipos de paso de parámetros: por valor o por referencia. En un paso de parámetros por valor se pasa el valor de la variable y no hay problema, puesto que no se modifica la variable. En el caso del paso de parámetro por referencia, lo que se pasa es la dirección, y es posible realizar modificaciones sobre esta variable. Existe otra forma de pasar parámetros que no maneja el lenguaje c, este mecanismo se llama copia/restauración. Quien recibe la llamada copia la variable en la pila, como en la llamada por valor, y entonces copia de regreso la variable después de la llamada, escribiendo sobre el valor original. El objetivo de un rpc es que se parezca lo más posible a una llamada local (transparencia). Cuando un servidor se ejecuta por primera vez, lo primero que hace es exportar su interfaz, esto es, el nombre de los servicios y sus parámetros, especificando si son parámetros de 53

entrada o de salida, su versión, su identificador único y su asa. Un proceso llamado conector es quien recibe la interfaz y realiza el registro. El conector además de realizar el registro de un servidor puede darlo de baja y buscar algún servidor. La versión de un servicio es importante pues indica si un servidor ha sido actualizado o no. Así el conector contendrá las últimas versiones de los servidores. Este método de exportación e importación es altamente flexible. Por ejemplo, puede manejar varios servidores que manejen la misma interfaz. Pero tiene sus desventajas. El conector se puede convertir en un cuello de botella, además un proceso puede tener un tiempo de vida corto y el tiempo entre importar y exportar interfaces puede ser significativo. Semántica de rpc en presencia de fallas El objetivo es ocultar la comunicación, al hacer que las llamadas a los procedimientos remotos se parezcan a los locales. Sin embargo, esto no es tan sencillo. Existen cinco clases distintas de fallas que pueden ocurrir en los rpc’s. • • • • •

El cliente no puede localizar al servidor Se pierde el mensaje de solicitud del cliente al servidor Se pierde el mensaje de respuesta del servidor al cliente El servidor falla antes de recibir una solicitud El cliente falla después de enviar la solicitud

El cliente no puede localizar al servidor Debido a que el servidor cambió de dirección y el cliente no se actualizó (tal vez preguntó antes de que se actualizara). En unix se retorna -1 y una variable global errno, pero si -1 es un valor válido, habrá confusión acerca de si fue error o el resultado de alguna operación. Otro mecanismo que no tiene la desventaja anterior es que el error provoque una excepción. Por ejemplo se podrían utilizar señales. Pero no todos los lenguajes tienen excepciones y/o señales. Además el uso de estos mecanismos, destruyen la transparencia. Pérdida de mensajes de respuesta Se puede utilizar un cronómetro, si no llega respuesta en un periodo razonable, se envía la solicitud nuevamente. ¿Pero qué se perdió, la solicitud, la respuesta o el servidor es lento? Si es la respuesta la que se perdió, entonces esto es más difícil de enfrentar. Algunas 54

operaciones se pueden repetir muchas veces sin efectos colaterales y sin causar daños. A esta propiedad se le llama idempotencia. Pero existen operaciones que no son independientes, por ejemplo retirar dinero de un cajero automático. Una posible solución es asociar un número secuencial a cada solicitud. Entonces el núcleo del servidor debe mantener un registro del número secuencial más reciente, así podrá notar la diferencia entre una solicitud original y las retransmisiones. Como protección adicional se podría colocar un bit en el encabezado del mensaje para distinguir las solicitudes originales de las retransmisiones. Fallas del servidor Puede suceder que el servidor falle después de responder o que el servidor falle antes de responder. Existen tres escuelas en torno a lo que se debe hacer en este caso: 1.

2. 3.

Semántica al menos una vez. Seguir intentando hasta conseguir una respuesta (el servidor puede volver a arrancar o se reconecta un nuevo servidor). Garantiza que la rpc se realiza al menos una vez o más veces. Semántica a lo más una vez. Se da por vencido inmediatamente e informa de la falla. La rpc se realiza a lo más una vez o ni una sola vez. No garantiza nada.

Fallas del cliente Cuando un cliente falla después de enviar una solicitud sin que haya recibido respuesta, existirá una labor de cómputo de la cual nadie espera respuesta. A esta labor de cómputo no deseada se le llama huérfano. Problemas que puede provocar un huérfano. • • •

Desperdiciar ciclos de cpu Bloquear archivos o capturar recursos valiosos Crear confusión (si el cliente vuelve a arrancar y realiza de nuevo la rpc, la respuesta puede ser inmediata y entonces no sabrá lo que pasó)

¿Qué hacer con los huérfanos? Nelson (1981) hizo un estudio acerca de este problema y propuso lo siguiente: •

Exterminación. Antes de enviar la solicitud, el resguardo del cliente crea un registro de lo que se va a hacer y lo almacena en dusci. Al volver a arrancar (el cliente) se verifica el contenido del registro y se elimina al huérfano. 55

• • • •

•

•

Desventaja. Gasto en la escritura y disco. Si hay más huérfanos es muy probable que no se puedan localizar No es un buen método. Reencarnación. Se divide el tiempo en épocas. Cuando el cliente arranca de nuevo envía un mensaje a todas las máquinas que declaran el inicio de una época. Se eliminan los cómputos remotos que estén fuera de época. Reencarnación sutil. Utiliza también épocas, pero el que está ejecutando el rpc verifica si existe el dueño de la rpc cuando le llega un mensaje de cierta época, si no existe elimina la operación. Expiración. Se asigna a cada rpc una cantidad de tiempo, si no puede terminar en ese tiempo pide otro quantum, sino entonces se elimina el proceso.

En la práctica ninguno es recomendable. La eliminación de un huérfano puede traer consecuencias. Protocolos rpc Orientado a la conexión • Ventaja. Comunicación fácil • Desventaja: Pérdida de desempeño Sin conexión • En este caso se debe adaptar el protocolo para garantizar seguridad. • Algunos sistemas utilizan udp o udp integrado a ip. • Ventajas • El protocolo ya ha sido diseñado • Estos protocolos son utilizados en casi todos los sistemas unix. • udp e ip son soportados por muchas redes existentes. • Desventajas • Cada protocolo forma un paquete con varios campos y además ambos realizan una suma de verificación. • Lo anterior hace que se pierda el desempeño. • Alternativa • Utilizar un protocolo especializado para rpc, que debe ser diseñado e implantado por el programador.

Con respecto a la longitud del paquete y el mensaje, sale más caro hacer 64 rpc de 1k que 1 rpc de 64k. Por lo tanto el protocolo debe permitir las transmisiones largas (Sun Microsystems 8k, el límite de Ethernet es de 1536 bytes). 56

Reconocimientos 1. 2.

Protocolo detenerse y esperar. Envía un paquete y espera reconocimiento. Los paquetes son enviados uno a uno. Protocolo de chorro. El cliente envía todos los paquetes tan pronto como pueda. Así el servidor reconoce todo el mensaje al recibir todo el paquete, y no uno por uno.

Propiedades del protocolo detenerse y esperar Si se daña o pierde un paquete, el cliente no puede recibir a tiempo un reconocimiento, por lo que vuelve a transmitir el paquete defectuoso. En el protocolo de chorro sí se pierde el paquete 1 pero le llega de manera correcta; puede abandonar todo y esperar a que el cliente vuelva a transmitir todo el mensaje o esperar con la esperanza de que 3 llegue bien y luego pedirle al cliente que envíe el paquete 1. A esto se le llama repetición selectiva. 3.4.4 Comunicación en grupo Para rpc la comunicación sólo es entre dos partes: el cliente y el servidor. A veces existen casos donde es necesario que varios procesos se comuniquen (por ejemplo, enviar un mensaje a todos los usuarios avisando que el sistema será dado de baja temporalmente para darle mantenimiento). Un grupo es una colección de procesos que actúan juntos en cierto sistema o alguna forma determinada por el usuario. La propiedad fundamental de un grupo es que cuando se envía un mensaje al propio grupo, todos los miembros de éste lo reciben. A este tipo de comunicación se le llama unomuchos (la de cliente-servidor es una comunicación puntual). Los grupos son dinámicos, se pueden crear nuevos y destruir anteriores. Un proceso puede unirse a un grupo o dejarlo. Un proceso puede ser miembro de varios grupos a la vez. La implantación de comunicación en grupo depende del hardware en gran medida. •

•

Multitransmisión. Cuando se envía un mensaje a un grupo éste se recibe automáticamente en todas las máquinas que escuchan esa dirección. Cada grupo escucha una dirección de multitransmisión. Transmisión simple. Los procesos deben ser concientes acerca de a cuál grupo pertenecen porque el mensaje lo verifican todos y sólo los miembros del grupo al cual va dirigido el mensaje lo toman. La desventaja es que si un proceso no pertenece al grupo entonces descarta el mensaje, pero esto implica desperdicio de tiempo. 57

•

Unitransmisión. El mensaje es enviado a cada proceso uno a uno, es decir, si el grupo tiene n miembros, se envían n paquetes.

Grupos cerrados vs. Grupos abiertos Los procesos pueden clasificarse en grupos cerrados y grupos abiertos. En un grupo cerrado sólo los miembros del grupo pueden enviar mensajes al grupo. En un grupo abierto cualquiera puede enviar mensajes al grupo. Grupos de compañeros vs. grupos jerárquicos Otra forma de clasificar a los grupos es en grupos de compañeros y grupos jerárquicos. En un grupo de compañeros todos los procesos son iguales, la ventaja es que si uno falla los demás pueden seguir trabajando. La desventaja es que al tomar una decisión se debe votar, esto implica mayor retraso y costo. En el caso de un grupo jerárquico existe un jefe o coordinador, la ventaja es que hay menos retraso y costo, la desventaja es que si falla el jefe, el grupo hace un alto. Membresía del grupo Para manejar la creación y eliminación de grupos, así como permitir a los procesos que se unan o dejen grupos se puede utilizar un servidor de grupos. Este servidor debe mantener una base de datos acerca de qué grupos existen y quiénes lo forman. La desventaja es que si el servidor falla, se pierde información acerca de grupos y tal vez deban ser reconstruidos los grupos totalmente. Otro método es manejar la membresía de grupo en forma distribuida. En un grupo abierto un extraño puede enviar un mensaje a todos los miembros del grupo para anunciar su presencia. En un grupo cerrado es necesario algo similar. Para salir del grupo se debe enviar mensaje de despedida a todos. Si un miembro falla, al no haber mensaje de despedida, los otros miembros se darán cuenta al tratar de comunicarse con él, entonces sino responde, lo eliminan de su grupo.

58

3.5 Sincronización en sistemas distribuidos 3.5.1. Sincronización de relojes En general los algoritmos distribuidos tienen las siguientes propiedades: 1. 2. 3. 4.

La información relevante se distribuye entre varias máquinas Los procesos toman las decisiones sólo con base en la información Debe evitarse un punto de fallo en el sistema No existe un reloj común o alguna otra fuente precisa del tiempo global

Algoritmo de Lamport Lamport señaló que la sincronización de relojes no tiene que ser absoluta. Si dos procesos no interactúan no es necesario que sus relojes estén sincronizados. Además lo que importa no es que los procesos concuerden de manera exacta en la hora, sino que coincidan en el orden en el cual ocurren los eventos. Así para cierta clase de algoritmos lo que importa es la consistencia interna de los relojes, no su particular cercanía al tiempo. Para estos algoritmos los relojes se denominan relojes lógicos. Lamport definió una relación llamada “a ocurre antes de b“ (a→b). Esta relación se puede observar de manera directa en dos situaciones: 1. 2.

Si a y b son eventos en el mismo proceso y a ocurre antes de b, entonces a→b es verdadero. Si a es el evento de envío de un mensaje por un proceso y b es el evento de la recepción del mensaje por otro proceso, entonces a→b también es verdadero.

El algoritmo de Lamport consiste en lo siguiente, cuando un proceso a envía un mensaje el mensaje lleva consigo su marca de tiempo C(a), si el proceso receptor b tiene un tiempo C(b) mayor que el del proceso a, entonces el mensaje es aceptado y no pasa nada. Pero si la marca de tiempo de a, es decir C(a) es mayor que C(b), entonces el proceso b ajusta su reloj, toma la marca de tiempo C(a) y le suma uno (Ver siguiente figura). Lamport plantea que dos eventos no ocurren exactamente al mismo tiempo. Con este algoritmo se puede obtener un orden total para todos los eventos del sistema.

59

0

1

2

3

0

0

0

0

2

3

1

4

4

6

2

8

6

9

7

12

8

12

8

16

10

15

9

20

18

10

24

21

25

28

24

26

32

27

28

40

12 14 16 18 20

30

27

36

Algoritmo de Cristian Cuando un sistema hace uso de un servidor de tiempo (quizá porque tiene instalado un receptor wwv para obtener un tiempo real), se puede usar el algoritmo de Cristian. Este algoritmo consiste en que todos los clientes se sincronicen con el servidor de tiempo en forma periódica. Según el algoritmo de Cristian el tiempo no debe correr hacia, por lo tanto el cambio debe realizarse de forma gradual, esto se consigue haciendo lo siguiente, si se generan 100 interrupciones por segundo, lo normal es que se tengan que añadir 10 milisegundos en cada interrupción. Entonces si se quiere atrasar un reloj, se podrían añadir 9 o menos milisegundos en cada interrupción hasta que el reloj esté sincronizado. Si lo que se quiere es adelantar el reloj entonces en cada interrupción hay que añadir 11 milisegundos hasta lograrlo. Otro problema en este algoritmo es que el tiempo que tarda el servidor en responder al emisor es distinto de cero. Pero este retraso depende de factores como, por ejemplo la carga de ese momento en el sistema. Una forma de medirlo es tomando el tiempo inicial TI y el tiempo final TF obtener la diferencia y dividirlo entre 2, (tf –ti)/2. Algoritmo de Berkeley En el algoritmo de Cristian el servidor de tiempo es pasivo. En el caso del algoritmo de Berkeley está activo y realiza un muestreo de forma periódica a todas las máquinas para 60

preguntarles su tiempo. En base al tiempo de todas las máquinas incluyéndose él mismo, obtiene el promedio y les indica a cada máquina cuánto tiempo deben adelantarse o retrasarse para lograr la sincronización. Al igual que en Cristian, para adelantar o retrasar el reloj hay que hacerlo paulatinamente de acuerdo a las interrupciones que genera el cronómetro. Procedimiento 1. 2.

3. 4.

5.

El servidor de tiempo le envía a cada máquina su tiempo Las máquinas cliente le indican el número de segundos que están adelantadas o retrasadas con respecto al tiempo del servidor, si es un número positivo entonces están adelantadas y si es negativo están atrasadas. El servidor suma todos estos datos y los divide entre el número de máquinas incluyéndose él mismo. El resultado lo suma a su propio tiempo obteniendo t, y calcula el número de segundos que le falta o le sobra a una máquina para llegar a ese tiempo t, y se lo envía a la máquina. Lo mismo hace para cada máquina. Las máquinas reciben el resultado y sincronizan su tiempo.

Una modificación es considerar el tiempo que tardan los mensajes y sumarlo a la respuesta del servidor. Ejemplo: Supongamos que tenemos cuatro máquinas y una de ellas es el servidor de tiempo. Las máquinas tienen los siguientes tiempos (en este caso manejaremos el tiempo en minutos): T=(-62+48+24)/4=+2 Le suma 2 al servidor.

15:12

15:14

+24 -62

-22 +64

+48

14:10 16:00

14:10

15:36

-46 16:00

15:36

Una mejora es eliminar los tiempos que estén muy alejados del tiempo del servidor.

61

3.5.2 Exclusión mutua Un algoritmo distribuido (El algoritmo de Ricart y Agrawala ) Este algoritmo requiere de un orden total de todos los eventos en el sistema. Para cualquier pareja de mensajes debe quedar claro quién ocurrió primero. Cuando un proceso desea entrar a la región crítica, construye un mensaje con el nombre de ésta, su número de proceso y la hora actual, y la envía a todos los demás procesos y de forma conceptual a él mismo. Se puede utilizar comunicación en grupo confiable. Cuando un proceso recibe un mensaje de solicitud de otro proceso para entrar a una región crítica, debe distinguir tres casos: 1. 2. 3.

Si el receptor no está en la región crítica y no desea entrar a ella, envía de regreso un mensaje ok al emisor. Si el receptor desea entrar a la región crítica, no responde, sino que forma la solicitud en una fila. Si el receptor desea entrar a la región crítica, pero no lo ha logrado todavía, compara la marca de tiempo en el mensaje recibido con la marca contenida en el mensaje que envió a cada uno. La menor de las marcas gana. Si el mensaje recibido es menor, el receptor envía un mensaje ok. Si su propio mensaje tiene una marca menor, el receptor forma la solicitud en una fila y no envía nada.

Un proceso puede entrar a la región crítica si obtiene permiso de todos. Si es así, entra y cuando sale envía mensajes ok a todos los procesos de su fila y elimina los elementos de la fila. Con este método la exclusión mutua queda garantizada sin bloqueo ni inanición. El número de mensajes necesarios por entrada es de 2(n-1), donde n es el número total de procesos en el sistema. Ejemplo: Supongamos que tenemos cuatro procesos numerados del 0 al 3, los procesos 1 y 3 desean entrar a la región crítica, 0 no desea entrar a la región crítica y 2 está dentro de la región crítica. Los procesos 1 y 3 envían mensaje casi al mismo tiempo, pero la marca de 3 es menor a la de 1 (1 tiene marca de tiempo igual a 3 y 3 tiene marca de tiempo igual a 2). Cuando 0 recibe el mensaje de 3 le otorga el permiso, como la marca de tiempo de 3 es menor que la de 1 entonces 1 debe enviar un mensaje de ok a 3, 2 está dentro de la región crítica por lo que forma el mensaje de 3 en una fila. 62

Cuando 0 recibe el mensaje de 1 le responde con un ok, 3 al recibir el mensaje de 1 checa su propia marca de tiempo, como su marca de tiempo es menor que la de 1 entonces forma la solicitud de 1 es una fila y no responde nada. El proceso 2 al recibir mensaje de 1, forma el mensaje en una fila ya que 2 está en la r.c.

3 0

1

2

3 2

2

2

Los procesos 1 y 3 envían mensajes con su marca de tiempo

3

3

Esta dentro de la región crítica

ok 0

ok

1

Respuesta de los procesos al mensaje de 1 y3

ok

3 1 fila

2

2

1

3

fila

El proceso 3 tiene el permiso de 0 y 1 para entrar a la región crítica, y el proceso 1 tiene el permiso de 0. Cuando 2 sale de la región crítica envía mensajes de ok a los procesos de su fila, en este caso, a los procesos 3 y 1.

63

0

1

2 sale de la región crítica

ok ok

3 1 fila

3

2

1

El proceso 3 ya tiene el permiso de todos por lo tanto puede entrar a la r.c., mientras que el proceso 1 debe esperar a que 3 salga de la región crítica. Cuando 3 salga de la región crítica debe enviar un mensaje de ok al proceso 1. Ahora existen n puntos de falla. Sino hay respuesta, se interpretará como una negación de permiso, aún cuando el proceso haya muerto, podría haber bloqueos. Una posible modificación es la siguiente, cada vez que se haga una solicitud debe haber una respuesta negativa o positiva. Funciona bien con comunicación en grupo, donde se tenga un registro de los integrantes del grupo, quiénes entran y quiénes han salido o han fallado. Funciona bien con grupos pequeños. El algoritmo es más lento, más complejo y más caro y menos robusto que el centralizado. Pero sirve para estimular a investigadores a producir algoritmos útiles.

64

Algoritmo de anillo de fichas Se necesita construir un anillo lógico, donde a cada proceso se le asigna una posición en el anillo. Se da una ficha al primer proceso, la cual circula en todo el anillo. Si necesita entrar a la región crítica y tiene la ficha, entonces entra, cuando sale de ella entrega la ficha al siguiente proceso. No se permite entrar a una segunda región crítica con la misma ficha. Si un proceso no está interesado en entrar a la región crítica sólo pasa la ficha. Problemas. La ficha se puede perder, hay que regenerarla ¿Cuánto tiempo un proceso debe esperar para considerar que la ficha se ha perdido? Tal vez alguien la esté ocupando. Si un proceso falla, se puede solucionar solicitando un reconocimiento al vecino al recibir la ficha. Si no hay reconocimiento se da por muerto y se entrega la siguiente ficha al siguiente proceso. Se debe actualizar el grupo de procesos. 3.5.3 Algoritmos de elección En muchos algoritmos distribuidos es necesario que un proceso actúe como coordinador ¿cómo elegirlo? Supondremos que cada proceso tiene asociado un número único. En general, los algoritmos de elección intentan localizar el proceso con el máximo número de proceso y designarlo como coordinador. Además supondremos que cada proceso conoce el número de proceso de todos los demás. El objetivo de un algoritmo de elección es garantizar que al inicio de una elección, ésta concluya con el acuerdo de todos los procesos con respecto a la identidad del nuevo coordinador. El algoritmo del grandulón (García-Molina 1982) Un proceso p realiza una elección cuando se da cuenta que el coordinador no responde, de la siguiente forma: 1. 2. 3.

envía un mensaje elección a los demás procesos con un número mayor. Si nadie responde, p gana la elección y se convierte en el coordinador. Si uno de los procesos con un número mayor responde, toma el control. El trabajo de termina. p

p

Cuando un proceso toma el papel del coordinador debe enviar un mensaje coordinador a los demás procesos par que éstos se den por enterados. Si un proceso ináctico se activa, realiza una elección. Si tiene el número mayor, ganará la elección. De ahí el nombre de “algoritmo del grandulón”. 65

falla elección 5 0

ok

4

3 1 2

falla

falla

5

5

0

4

0

4

3

3

1

1 2

2 falla

5 0

4 coordinador 3

1 2

66

Un algoritmo de anillo Este algoritmo no utiliza una ficha. Suponemos que los procesos tienen un orden y que conocen a su sucesor. Cuando algún proceso observa que el coordinador no funciona, construye un mensaje elección con su propio número de proceso y envía el mensaje a su sucesor. Si éste está inactivo, el emisor pasa sobre el sucesor y va hacia el siguiente número del anillo. El emisor añade su propio número de proceso a la lista en el mensaje. Cuando el mensaje da toda la vuelta (el proceso recibe un mensaje con su propio número). Entonces circula de nuevo el mensaje anunciando quien es el nuevo coordinador (el del número más grande) y además se anuncia quiénes son miembros del anillo. Ejemplo: Supongamos que tenemos 6 procesos numerados del 0 al 5, el proceso 5 es el coordinador pero ha fallado, el primero en darse cuenta en el proceso 2, así que envía mensajes de elección, cuando recibe un ok, sabe que su trabaja ha terminado. 3 envía mensajes de elección lo mismo que 4, 4 no recibe ningún ok, por lo que asume que él es el nuevo coordinador. 3.5.4. Transacciones atómicas Son una abstracción de mayor nivel, que oculta aspectos técnicos y permite a los programadores concentrarse en los algoritmos y la forma en que los procesos trabajan juntos en paralelo. Cuando un proceso desea llevar a cabo una transacción les pregunta a los procesos que llevarán a cabo las operaciones si se comprometen, en caso de que se comprometan todos, entonces los resultados se vuelven permanentes, si uno de ellos o más no se comprometen entonces la transacción se aborta. Y todo debe regresar al estado hasta antes de empezar la transacción, sin que existan efectos colaterales. Un ejemplo de transacción es cuando se lleva a cabo una operación bancaria. El modelo de transacción Se supone que el hardware subyacente maneja de manera transparente los errores de comunicación (retransmisiones, almacenamiento de información en búferes, etc.)

67

Almacenamiento estable El almacenamiento estable tiene tres categorías: 1. 2. 3.

ram

Disco duro, que puede dañarse debido a problemas con la cabeza lectora del disco. Almacenamiento estable. Se puede implantar con dos disco ordinarios.

Cada bloque en la unidad 2 es una copia exacta del bloque correspondiente en la unidad. Se supone que la unidad 1 es correcta. Primitivas de transacción Los sistemas que manejan transacciones deben tener al menos las siguientes primitivas. 1. begin_transaction 2. end_transaction 3. abort_transaction 4. read 5. write Lo que está dentro de begin_transaction y end_transaction se debe llevar a cabo todo o nada. Propiedades de las transacciones (acid) Las transacciones tienen cuatro propiedades fundamentales. Las transacciones son: 1. 2. 3.

4.

Atómicas. Para el mundo exterior, la transacción ocurre de manera indivisible. Consistentes. La transacción no viola los invariantes del sistema. Aisladas. Las transacciones concurrentes no interfieren entre sí. Si dos o más transacciones se ejecutan al mismo tiempo, para cada una de ellas y para los demás procesos, el resultado final aparece como si todas las transacciones se ejecutasen de manera secuencial en cierto orden (el resultado no debe verse afectado en caso de intercalar los procesos). Durables. Una vez comprometida una transacción, los cambios son permanentes.

Transacciones anidadas Las transacciones pueden contener subtransacciones, a menudo llamadas transacciones. La transacción de nivel superior puede producir hijos que se ejecuten en paralelo entre sí, en procesadores distintos, para mejorar el desempeño. Cada hijo puede a su vez tener más hijos. 68

Si una subtransacción falla, entonces la transacción de orden superior (de la cual derivan todas) debe abortar, así los compromisos hechos por las demás subtransacciones deben deshacerse. Por lo tanto la durabilidad sólo se aplica a las transacciones del nivel más alto. Implantación Espacio de trabajo privado Cuando un proceso inicia una transacción se le otorga un espacio de trabajo privado, si la transacción se compromete, se copia el estado del espacio de trabajo privado al real; pero si aborta, no pasa nada y el espacio de trabajo real no se modifica. Una mejora es crear en el espacio de trabajo privado, apuntadores a los bloques con los cuales la transacción va a trabajar; si la operación es una escritura, se copia el bloque al espacio privado y se modifica. Cuando la transacción se compromete, los apuntadores se desplazan hacia el espacio de trabajo real de forma atómica, y los que estaban en el espacio de trabajo real se marcan como bloques libres. Si la operación es una lectura no hay necesidad de copiar los bloques. Si la transacción aborta, los bloques en el espacio de trabajo privado (las copias) se marcan como bloques libres y los apuntadores se eliminan. Bitácora de escritura anticipada En este caso antes de cambiar cualquier bloque, primero se escribe un registro de la bitácora de escritura anticipada la transacción que realiza el cambio, el archivo y bloques modificados y los valores anterior y nuevo. Después de esto se realiza el cambio en el archivo. Si la transacción se compromete se escribe un registro en la bitácora acerca de esta acción, las estructuras de datos ya no tienen que modificarse puesto que ya están modificadas. En caso de que la transacción aborte, sólo hay que realizar las operaciones de la bitácora de la última ala primera para deshacer cada cambio realizado. A esta acción se le llama retroalimentación. Protocolo de compromiso de dos fases En un sistema distribuido el llevar a cabo una transacción requiere, muchas de las veces, de la cooperación de varios procesos en diferentes máquinas. La idea del protocolo de dos fases es la siguiente: Uno de los procesos funge como coordinador y es quien realmente 69

ejecuta la transacción. El protocolo de compromiso comienza cuando el coordinador escribe una entrada en la bitácora indicando el inicio del protocolo, después envía un mensaje a cada uno de los procesos implicados para que estén listos para el compromiso. Cuando uno de los procesos implicados recibe el mensaje, verifica si está listo para comprometerse, escribe una entrada en la bitácora y envía de regreso su decisión. Cuando el coordinador recibe todas las respuestas, sabe si establece el compromiso o aborta. Si uno o más procesos no se comprometen (o no responden), la transacción aborta. De cualquier modo, el coordinador escribe una entrada en la bitácora y envía entonces un mensaje a cada subordinado para informarle de la decisión. El uso de la bitácora permite que si el coordinador falla pueda recuperarse puesto que todo lo ha escrito en la bitácora. Control de concurrencia Cerradura Cuando un proceso necesita leer o escribir en un archivo como parte de una transacción, primero cierra el archivo. El control de cerraduras puede implantarse a través de un controlador centralizado o uno local en cada máquina, éste controlador mantendrá una lista de los archivos cerrados y rechazará los intentos de otros procesos por cerrar un archivo ya cerrado. Para mejorar este esquema se podrían distinguir las cerraduras de lectura de las de escritura. Se puede compartir una cerradura para lectura (varios procesos pueden leer del mismo archivo pero se excluyen los escritores para que no puedan modificar el archivo), pero la cerradura de escritura debe ser exclusiva de un solo proceso. Cerradura de dos fases La adquisición y liberación de las cerraduras en el preciso momento en que se necesiten o se dejen de necesitar puede conducir a cierta inconsistencia y a bloqueos. En vez de esto, si el proceso durante su ejecución necesita de varias cerraduras, primero las adquiere en la fase de crecimiento y las libera en la fase de contracción. Así si un proceso no puede adquirir todas las cerraduras que necesita, entonces libera las que llevaba hasta el momento, espera y vuelve a comenzar.

70

Cerradura estricta de dos fases En este caso el proceso adquiere primero todas las cerraduras y las libera sólo hasta que la transacción haya terminado o aborte. Control optimista de la concurrencia El control optimista de la concurrencia mantiene un registro de los archivos leídos o en los que se ha escrito algo. En el momento del compromiso se verifican todas las demás transacciones para ver si alguno de los archivos ha sido modificado desde el inicio de la transacción. Si esto ocurre, la transacción aborta, si no se realiza el compromiso. Esto se trabaja mejor si se utiliza espacio de trabajo particular. 3.5.5 Bloqueos en sistemas distribuidos Prevención distribuida de bloqueos La prevención de bloqueos consiste en el diseño cuidadoso del sistema, que cada proceso ocupe sólo un recurso a la vez, exigir que los procesos soliciten los recursos desde un principio y hacer que liberen todo cuando soliciten uno nuevo. Llevar esto a la práctica puede ser un poco difícil. Existen dos algoritmos básicos siguiendo esta idea. 1. Espera-muerte En este se clasifican los procesos en dos: antiguos y viejos.(Ver fig. 3.25). Con esto tenemos dos casos: •

•

El proceso nuevo está ocupando un recurso, debido a que el antiguo ya lleva mucho tiempo en ejecución y ha consumido recursos con anterioridad, se opta por dejar que el proceso espere hasta que el joven termine para que pueda continuar su ejecución. Un proceso joven requiere un recurso que está siendo ocupado por uno viejo. Aquí se opta por matar al proceso joven para que el viejo continúe su ejecución, teniendo en cuenta que el proceso al ser joven volverá ha ser invocado un poco después, por lo que en algún momento al ejecutar este proceso encontrará el recurso libre.

71

2. Herida-espera En este se retoma la idea anterior de proceso joven y viejo por lo que volvemos a tener los mismos casos. (Ver fig. 3.26) • •

Un proceso viejo requiere recursos ocupados por uno joven. Aquí se elimina la transacción del proceso joven y el proceso viejo toma su lugar. Un proceso joven requiere recursos que tiene un proceso viejo. Aquí el proceso joven espera hasta que el viejo termine, de este modo se evita el estar matando a un proceso continuamente.

72

3.6 Tolerancia de fallas Fallas de componentes Una falla es un desperfecto causado por un error de diseño, de fabricación, de programación, físico, tiempo, condiciones ambientales, etc. Las fallas se clasifican en: • • •

Transitorias. Ocurren una vez y después desaparecen. Intermitentes. Desaparecen y reaparecen. Permanentes. Continuan existiendo hasta reparar el componente con el desperfecto.

El objetivo del diseño y construcción de sistemas tolerantes a fallas consisten en garantizar que el sistema continúe funcionando de manera correcta como un todo, incluso en la presencia de fallas. Fallas del sistema Se pueden distinguir dos tipos de fallas del procesador: • •

Fallas silentes. Un procesador que fallas sólo se detiene y no responde a las entradas subsecuentes ni produce más entradas (también se llaman fallas de detención). Fallas bizantinas. Un procesador que falla continúa su ejecución, proporcionando respuestas incorrectas a las preguntas, y posiblemente trabajando de manera maliciosa junto con otros procesadores que han fallado, para dar la impresión de que todos funcionan de manera correcta aunque no sea así.

Sistemas síncronos vs. asíncronos En el contexto de la investigación relativa a la tolerancia a fallas, un sistema que tiene la propiedad de responder siempre a un mensaje dentro de un límite finito conocido, es síncrono. Un sistema que no tiene esta propiedad es asíncrono. Uso de redundancia El método general para la tolerancia de fallas consiste en el uso de redundancia. Existen tres tipos posibles: 73

• • •

Redundancia de la información. Se agregan bits para poder recuperar los bits revueltos. Redundancia del tiempo. Se realiza una acción y en caso necesario se vuelve a realizar. Este tipo de redundancia es de utilidad cuando las fallas son transitorias o intermitentes. Redundancia física. Se trata de agregar equipo adicional.

Formas de organizar procesadores • •

Réplica activa Respaldo primario

Tolerancia de fallas mediante réplica activa (método de la máquina de estados) Las solicitudes deben ser recibidas y procesados en el mismo orden. Un sistema es tolerante de ka fallas si puede sobrevivir a fallas de k componentes, entonces son necesarios k+1 componentes. Tolerancia de fallas mediante respaldo primario 2.Realiza el trabajo 1.Solicitud Cliente

3.Actualiza Primario

Respaldo

6.Respuesta

5.Reconocimiento

Acuerdos en sistemas defectuosos • •

El problema de los dos ejércitos El problema de los generales bizantinos

74

4.Realiza el trabajo

Ejercicios

1. Suponga que usted ejecuta un proceso en Linux, en la carpeta donde está almacenado el ejecutable de tal proceso se almacenan tres ejecutables más. Usted esta leyendo su correo electrónico y en otra consola está escribiendo un programa en c llamado procesos. c. ¿Cuántos procesos en este contexto (sólo en este contexto sin tomar en cuenta bash) existen? a) 3 b) 6 c) 7 d) no se sabe 2. Suponga que un proceso realiza una operación down sobre un semáforo cuyo valor es cero, ¿a qué estado pasara éste proceso? a) Dormido b) Listo c) Bloqueado d) En ejecución 3. Suponga que la tabla de pcb’s consta de 100 entradas, de las cuales 50 de ellas están vacías, 20 son procesos listos, 29 son procesos bloqueados ¿cuántos procesos están en estado de dormido? 4. El despachador de ________ maneja las operaciones que tiene que ver con el cambio de estado de los procesos de bloqueados a listos. a) De largo plazo b) De mediano plazo c) De corto plazo d) De dos niveles 5. Suponga que tenemos 4 procesos en el sistema en el siguiente orden. El proceso 1 tiene un tiempo de ejecución de 100 ms, el segundo de 120 ms, el tercero de 20 ms, y el cuarto de 75 ms. Suponga también que se está utilizando el algoritmo de round robin (rebanadas de tiempo) y que el quantum (rebanada de tiempo) es de 30 ms y el cambio de contexto es de 1ms. ¿Cuál será el tiempo de terminación del proceso 3 tomando en cuenta que el proceso 2 se bloqueará en su tiempo 10ms?, el proceso 1 es el que está a punto de ejecutarse? 6. La tabla de pcb’s contiene información referente a los procesos del sistema, tales como identificador de proceso, valores de registro, etc. excepto: a) Apuntador a su tabla de descriptores b) Código del proceso c) Dirección de la siguiente instrucción en ejecutarse d) Estado del proceso 75

7. Cuando un proceso es interrumpido por el despachador para permitir la ejecución de otro proceso, se debe restablecer el ambiente del proceso a ejecutarse, y almacenar el del proceso interrumpido. A esta actividad se le llama ____________ a) spooling b) Cambio de contexto c) Intercambio d) Fallo de página 8. Suponga que la tabla de pcb’s consta de 100 entradas, de las cuales 50 de ellas están vacías, 20 son procesos listos, 29 son procesos bloqueados ¿cuántos procesos están en estado de dormido? 9. Suponga estamos utilizando un despachador ____________, este tipo de despachador lleva a los proceso del estado dormido al listo a) De largo plazo b) De mediano plazo c) De corto plazo d) De dos niveles 10. Suponga que tenemos 4 procesos en el sistema en el siguiente orden. El proceso 1 tiene un tiempo de ejecución de 100 ms, el segundo de 120 ms, el tercero de 20 ms, y el cuarto de 75 ms. Suponga también que se está utilizando el algoritmo de round robin (rebanadas de tiempo) y que el quantum (rebanada de tiempo) es de 30 ms y el cambio de contexto es de 1ms. ¿Cuál será el tiempo de espera del proceso 2, tomando en cuenta que el proceso 1 es el que está a punto de ejecutarse? 11. Suponga que tenemos 10 procesos, cada uno tiene una duración de 300ms. 3 procesos son de prioridad 3, 3 de prioridad 2 y 4 de prioridad 1. El algoritmo de despacho que estamos utilizando es el de colas múltiples, la cual maneja sólo 3 prioridades donde 1 es la máxima prioridad. El quantum para la primera prioridad es de 50ms, el de la segunda 60ms y el de la tercera 100ms. ¿En cuánto tiempo serán despachados todos los procesos? 12. Suponga que tenemos 10 procesos de los cuales 5 son procesos del sistema, 4 procesos de usuario (es este el orden de la lista de procesos). Los procesos del sistema tienen una duración de 200 ms cada uno, y hacen una llamada al sistema cada 90ms. Los procesos 76

de usuario son interactivos y hacen una operación de E/S cada 80ms, y su duración es de 300ms. ¿Qué proceso es el primero en terminar?¿Qué proceso es el último en terminar? 13. Suponga que tenemos un sistema en donde no se sabe mucho acerca del comportamiento de los procesos, pero es necesario agilizar su despacho, sin ocasionar cuellos de botella. ¿Qué clase de asignación de procesos a procesadores utilizaríamos? a) Global, óptimo, heurístico b) Iniciado por el emisor, heurístico, centralizado c) Iniciado por el receptor, subóptimo, global d) Local, heurístico, distribuido 14. Suponga que usted está utilizando un sistema operativo distribuido, y tiene que salir un momento de la oficina, cuando regresa los procesos intrusos son migrados a otras máquinas. ¿Qué modelo de sistema está utilizando? a) Estaciones de trabajo b) Pila de procesadores 15. Cuando un proceso es migrado a otra máquina existen ciertas operaciones que deben ser realizadas en la máquina origen y otras en la máquina destino. Mencione dos de cada una. Origen: ______________________________________ Destino: _______________________________________________ 16. La capa del modelo osi que tiene que ver con el enrutamiento de los paquetes es a) Enlace de datos b) Red c) Transporte d) Presentación 17. Mencione una desventaja que tienen los modelos por capas para ser utilizados en sistemas distribuidos. _________________________________________ 18. atm es una red de alta velocidad que fue creada con un fin diferente al de los modelos osi y tcp/ip. ¿Cuál fue ese fin? _______________________________________

77

19. Un ejemplo de algoritmo de asignación de procesos a procesadores centralizado es a) Determinístico según la teoría de grafos b) Arriba – abajo c) Jerárquico d) Remates 20. En ambientes distribuidos, cuando dos procesos que se comunican se están ejecutando en nodos diferentes, sería importante para mejorar su desempeño, que ambos en sus respectivos nodos se despachen exactamente en el mismo instante de tiempo. A esta técnica se le llama: a) Planificación distribuida b) Scheduler c) Retroalimentación d) Coplanificación 21. Suponga que usted es el diseñador de un sistema operativo distribuido y es necesario que diseñe primitivas de comunicación cliente–servidor. Necesita garantizar que cuando un emisor ejecute un send y el receptor no esté listo el mensaje no se pierda. Además debe garantizar que el mensaje realmente llegue a su destino. ¿Qué tipo de primitivas debe diseñar? (Selecciona todas las que correspondan) a) Primitivas síncronas b) Primitivas asíncronas c) Primitivas almacenadas en buffer d) Primitivas no almacenadas en buffer e) Primitivas confiables f) Primitivas no confiables 22. Uno de los mayores problemas de la comunicación en grupo utilizando unitransmisión es: a) El ordenamiento de paquetes b) El hardware a) Los protocolos utilizados b) Los reconocimientos

78

23. El tipo de paso de parámetros utilizado por rpc para cubrir la dolencia que tiene rpc con el paso de parámetros por referencia se llama: a) Copiado b) Valor/copiado c) Copia/Nombre d) Copia/restauración 24. rpc tiene una ventaja frente al modelo cliente – servidor. ¿Cuál es? a) Transparencia b) Desempeño c) Confiabilidad d) Escalabilidad 25. Cuando un proceso que no pertenece a un grupo de procesos puede enviar un mensaje a todo ese grupo de procesos, decimos que ese grupo de procesos es: a) Jerárquico b) De amigos c) Abierto d) Cerrado 26. La ventaja de los semáforos frente a la técnica de dormir y despertar para la sincronización de procesos es (seleccione todas las que apliquen) a) Que las operaciones de los semáforos no son bloqueantes b) Que los semáforos guardan despertares c) Que las operaciones de los semáforos son atómicas d) Que los semáforos pueden ser manipulados a través de arreglos 27. Cuando los procesos están en máquinas diferentes, qué debemos utilizar para sincronizar procesos? a) Monitores b) Paso de mensajes c) Señales 28. Suponga que tenemos 5 procesos instalados en diferentes computadoras, y cada una de ellas maneja un tiempo que difiere por 10 minutos entre cada una de ellas, es decir, la máquina A tiene el tiempo 3:25, la B tiene el tiempo 3:35, la C 3:45, la D 3:55, y la E 4:05. Aplique Lamport para sincronizar las máquinas, de tal manera que se utilice el mínimo número de mensajes. 79

29. Suponga que tenemos el escenario anterior, pero ahora tenemos un servidor de tiempo el cual tiene el tiempo 3:40. Aplique el algoritmo de Cristian para sincronizar el tiempo de cada una de las máquinas. 30. Suponga que vamos a utilizar el algoritmo de Berkeley para sincronizar relojes lógicos. El servidor de tiempo tiene 4:34, el cliente1 10:02, el cliente2 4:45, el cliente3 4:20 y el cliente4 4:35. Si se toma en cuenta la hora del cliente1 obtendríamos un tiempo demasiado despegado de los demás clientes. Entonces ¿qué debe hacer el algoritmo de Berkeley para sincronizar los relojes de todas las máquinas incluyendo el cliente1 sin que la marca de tiempo sea tan distante de la hora del servidor de tiempo y de las demás máquinas? Después de realizar operaciones de acuerdo al algoritmo de Berkeley indique cuanto se tiene que adelantar o retrasar cada máquina. 31. Suponga que tenemos 4 procesos. Dos de ellos están compitiendo por entrar a la misma región crítica, los procesos 2 y 3; el proceso 1 no desea entrar a la región crítica; y el proceso 4 está dentro de la región crítica. La marca de tiempo del mensaje del proceso 3 es 45 y la marca de tiempo del mensaje del proceso 2 es 48. ¿Cuál es la operación y el estado de cada uno de los procesos después de recibir el mensaje del proceso 3? 32. Cuando una operación se puede repetir las veces que sean sin efectos colaterales y sin ningún daño, se dice que es una operación __________ 33. Mencione al menos dos técnicas de implantación de transacciones atómicas _________________________________________________________________ 34. La transacción A es iniciada en el tiempo x, y una transacción B en el tiempo x+10. Suponga que la transacción A necesita un recurso que esta utilizando la transacción B, si se está utilizando la técnica de espera-muerte para prevenir bloqueos entonces la transacción A a) muere b) espera c) ejerce su derecho de prioridad

80

35. La técnica de control de concurrencia en donde las cerraduras son liberadas solo cuando la transacción se compromete se llama a) Control optimista de la concurrencia b) Cerradura de dos fases c) Cerradura estricta de dos fases d) Marcas de tiempo

Referencias Randy Chow, Theodore Jhonson, Distributed Operating Systems & Algorithms, Addison-Wesley Silberschatz Galvin, Sistemas Operativos, Pearson, 5ta Edición. Addison-Wesley Longman. William Stallings. Sistemas Operativos, Prentice may, 4ta Edición. Prentice may. Coulouris George, Dollimore Jean, Kindberg Tim. Sistemas Distribuidos, Conceptos y Diseño, 3ª. Edición, Addison Wesley.

81

IV Gestión de memoria en ambientes centralizados y distribuidos

Sistemas Centralizados La parte del sistema operativo que administra la memoria se llama administrador de memoria. Sus tareas son: 1.

2. 3.

Llevar un registro de las partes de memoria que se estén utilizando y aquellas que no, para poder asignar espacio en memoria a los procesos que la necesiten y liberarla cuando terminen. Administrar el intercambio entre memoria principal y disco (cuando la memoria principal no pueda albergar a todos los procesos). Administración de la memoria sin intercambio o paginación.

Los sistemas de administración de memoria se pueden clasificar en dos tipos: 1. 2.

Los que desplazan los procesos de la memoria principal al disco y viceversa, durante la ejecución (intercambio y paginación). Los que no lo hacen, que son los más sencillos.

Monoprogramación sin intercambio o paginación •

Primer esquema: Solo existe un programa en memoria en cada instante.Problema:el programa debía contener todos los controladores para los dispositivos de e/s que ocupara. 83

•

Segundo esquema: Cada vez que el sistema operativo carga un nuevo proceso, lo escribe encima del anterior. Además reserva cierta parte de la memoria ram para tener ahí al sistema operativo. Figura a)

Después este esquema evoluciona y se tiene al programa de usuario en memoria y en rom al sistema operativo, aún así los controladores de e/s que utilizara el programa debían colocarse dentro de éste. Figura b). Así que el esquema cambia hasta obtener el que fue utilizado por las pc’s de ibm, el cual colocaba a los controladores de dispositivos en rom (lo que conocemos como bios), el programa de usuario se colocaba en ram y se reservaba parte de la memoria ram para el sistema operativo. Figura c).

Programa de usuario

SO en ROM Programa de usuario

SO en RAM Figura a)

Controlado res de dispositivo s en ROM Programa de usuario SO en RAM

Figura b)

Figura c)

Multiprogramación y uso de memoria La multiprogramación: • • •

Facilita la programación de una aplicación al dividirla en dos o más procesos. Hace eficiente el servicio interactivo que se les da a varias personas al mismo tiempo (en un sistema multiusuario) Hace eficiente la e/s al disco; mientras existen procesos ejecutándose, no hay que esperar hasta que la e/s concluya.

84

Modelos de multiprogramación ¿Qué tan ventajosa es la multiprogramación? ¿Qué ventajas tiene ponerle más memoria a la máquina? 4.1 Manejo de memoria con particiones fijas Dividir la memoria en n partes de tamaños distintos. Primer esquema: Particiones fijas de memoria con colas de entrada independientes para cada partición, donde las particiones tienen diferentes tamaños. En este caso cada proceso se formará en la partición que más le convenga dependiendo de su tamaño. El problema en este caso es que si llegan varias tareas pequeñas se formarán en la cola de la partición pequeña y ésta se saturará, además de que las particiones grandes se desperdiciarán. (Figura a).

Partición 1 Partición 2

1m

800K

Partición 3 Partición 4 290K SO

Figura a)

85

Segundo esquema: Particiones fijas en la memoria con una única cola de entrada. Así cada vez que llegue un proceso éste se formará en la única cola; si una partición llegara a desocuparse y fuera demasiado grande para el siguiente proceso, aún así se asignaría esa partición a ese proceso si no hubiera una partición más pequeña desocupada. Figura b). Con este esquema se desperdicia memoria puesto que habrá procesos pequeños en particiones grandes, además si empleamos un algoritmo de despacho tipo fifo podría suceder que un proceso grande impida la ejecución de los siguientes procesos porque sólo se están liberando particiones pequeñas, y ese proceso no será despachado hasta que una partición grande sea liberada, mientras los demás tienen que esperar; por lo tanto se pueden realizar las siguientes modificaciones a este esquema: Cada vez que se libere una partición se podría cargar y ejecutar en ella la tarea más cercana al frente de la cola que se ajuste a dicha partición, el problema en este caso es que podría estar al frente un proceso muy pequeño y detrás de éste procesos un poco más grandes que se ajustan mejor a las particiones recién liberadas; por lo tanto este proceso se estaría discriminando continuamente. Además que se gastaría mucho tiempo en verificar cuál es el proceso que mejor se ajuste a la partición recién liberada. Una solución a este problema es tener una partición pequeña que permita la ejecución de tareas pequeñas. Otra alternativa es no excluir a un proceso más de k veces, entonces cada vez que un proceso sea excluido obtiene un punto, cuando adquiera k puntos, ya no podrá ser excluido nuevamente. Reasignación y protección Los dos problemas esenciales de la multiprogramación son: la reasignación y la protección. Cuando un programa se liga (el programa principal, los procedimientos escritos por el usuario y los procedimientos de la biblioteca se conjuntan en un espacio con una sola dirección), el ligador debe conocer la dirección donde comienza el programa en la memoria. Si utiliza dirección absoluta puede ser que un llamado o un salto no se encuentre dentro de su espacio de direcciones, entonces debe tomar la dirección inicial de su espacio de direcciones y sumarle la dirección del salto. A este problema se le conoce como el problema de la reasignación. Una solución es modificar las instrucciones cuando el programa sea cargado en memoria, es decir, añadir a todas las direcciones la dirección inicial de su partición.

86

Pero esto no resuelve el problema de la protección; pues un programa podría saltar a una partición que no es de él. En los sistemas multiusuario no es deseable que los procesos lean o escriban en la memoria perteneciente a otros usuarios. Entonces para evitar el problema cada bloque debía tener una contraseña, así cada vez que se accese a una dirección de la memoria, primero se debía comprobar la contraseña, si ésta era válida entonces el programa seguía con su ejecución. La otra solución es equipar a la computadora con hardware especial que garantice protección a los procesos. Intercambio En un sistema multiusuario existen generalmente muchos procesos, los cuales tienen que estar en memoria, pero es imposible albergarlos a todos, por lo que es necesario mantener el exceso de los procesos en disco. El traslado de los procesos a la memoria principal al disco y viceversa se llama intercambio. 4.2 Manejo de memoria con particiones variables Debido al desperdicio de memoria que existe con las particiones fijas, ahora se utilizarán particiones variables. Las particiones cambian en número, en tamaño y de posición de acuerdo al tamaño y número de procesos en memoria. Debido a lo anterior la asignación y la protección de la memoria es más difícil. Con este tipo de algoritmo existe el intercambio. Compactación de la memoria: Combinar todos los huecos en uno grande y colocarlos en la parte inferior mientras sea posible (por lo general no se lleva a cabo porque consume mucho tiempo). ¿Qué cantidad de memoria se debe asignar a un proceso? • •

Si los procesos se crean con tamaño fijo, entonces la asignación de memoria se realizará de manera justa y sencilla. Los segmentos de datos pueden crecer (por ejemplo cuando utilizamos asignación dinámica). En este caso si hay un hueco adyacente, el proceso puede crecer hacia el hueco. De lo contrario el proceso debe ser asignado a un hueco lo suficientemente grande, o habrá que intercambiar uno o más procesos para crear un hueco grande.

Si el proceso no puede crecer en memoria y el área de intercambio del disco está lleno, el proceso deberá esperar a ser aniquilado. 87

Una posible solución a este problema es la siguiente: si los procesos van a crecer durante su ejecución entonces se debe asignar un poco de memoria adicional para reducir el gasto excesivo asociado con el traslado o intercambio de procesos. Al intercambiar, sólo bajar a disco la porción de memoria que realmente se está utilizando y no la memoria adicional. Registro del uso de memoria En general existen tres formas utilizadas por los sistemas operativos para llevar un registro del uso de la memoria: • •

Mapas de bits Listas (ligadas)

Administración de la memoria con mapas de bits Se crea un mapa de bits que representa a todas las direcciones de memoria existentes (o bloques de memoria), si el bits es 1, la dirección asociada a éste está ocupada, si es 0, entonces está desocupada. Administración de la memoria con listas ligadas Lista ligada

1 ProcA 2

ProcA 1 4

3 4

Hueco 5 3

5

ProcB

6

ProcB 8 3 ProcC

7 8

Hueco 16 2

9 ProcD 10

ProcD 181

Memoria

88

Algoritmos de asignación de memoria 1. 2. 3. 4. 5.

El primero en ajustarse El siguiente en ajustarse El mejor en ajustarse El peor en ajustarse Ajuste rápido

4.3 Memoria Virtual en sistemas operativos centralizados Para que un proceso demasiado grande puede ejecutarse se debe dividir en bloques o capas, así algunos bloques se almacenarán en memoria secundaria (disco duro) y otros, además del bloque que se está ejecutando realmente, se carga en memoria física. A esta técnica en donde se combina el uso de memoria física y memoria secundaria se le llama Memoria Virtual. En un principio se le dejaba al programador la responsabilidad de separar el programa en capas, después se dejó esa responsabilidad al Sistema Operativo. Existen dos técnicas importantes para el manejo de memoria virtual: Paginación y Segmentación. El espacio de direcciones generadas por los programas forman el espacio de direcciones virtuales. Cuando un proceso genera una dirección, esta dirección es una dirección virtual y debe ser reemplazada por la dirección física correspondiente. Existe un módulo que se encarga de ello, la mmu, Unidad de Administración de Memoria. La memoria virtual se divide en páginas y la memoria física en marcos para páginas. El tamaño de una página debe ser igual al tamaño de un marco para página. Si la dirección a la cual hace referencia el proceso que se está ejecutando está en una página que no se encuentra en memoria física, entonces el administrador de memoria debe buscar la página en memoria secundaria y cargarla en memoria física, a esta operación se le llama Fallo de página. Cuando todos los marcos para página en la memoria física ya estan ocupados, el sistema debe desalojar (expulsar) una página y colocarla en la memoria secundaria para liberar un espacio, el problema ahora se centra en decidir qué página deberá ser desalojada. Para esto existen una serie de algoritmos llamados Algoritmos de Reemplazo de páginas que permiten decidir, con base en diferentes criterios, qué página debe ser expulsada.

89

4.3.1 Paginación El número de página virtual sirve como índice para consultar la tabla de páginas y encontrar la entrada correspondiente a esa página virtual. En esa entrada se encuentra el número de marco de página, si lo hay, y ese número se anexa al extremo de orden alto de la distancia, sustituyendo al número de página virtual y formando una dirección física que se puede enviar a la memoria. El propósito de la tabla de páginas es transformar páginas virtuales en marcos de página. Existen dos problemas a resolver: la tabla de páginas puede ser extremadamente grande y la transformación debe ser rápida. Con 32 bits, donde cada página es de 4K, tenemos un millón de páginas. Cada proceso necesita su propia tabla de páginas. El segundo problema es que la transformación de memoria de virtual a física se debe realizar en cada referencia de memoria. A veces por cada instrucción hay que hacer referencia una, dos o más veces a la tabla de páginas. El diseño más sencillo es tener una sola tabla de páginas, que consiste en un arreglo de registros rápidos en hardware, con una entrada para página virtual indizado por número de página virtual. Cuando se inicia un proceso, el Sistema Operativo carga los registros con la tabla de páginas del proceso. El método es sencillo, pero el costo es muy alto, pues hay que cargar la tabla de páginas en cada conmutación. Otro método consiste en tener toda la tabla de páginas en la memoria principal. Este enfoque casi nunca se usa. Tablas de páginas multinivel

Número de marco de página

Número de marco de página

Caché inhabilitado

Referida

Protección Presente/ausente Modificada

90

Entrada de tabla de páginas representativa Los bits de protección indican el tipo de acceso. En su forma más sencilla sólo es un bit y es 0 para lectura/escritura y 1 sólo lectura. El bit modificado se enciende cuando se escribe a una página. El bit referido se enciende cuando se hace referencia a una página para lectura o escritura. El bit caché inhabilitado permite inhabilitar la colocación en caché de la página. tlb-

Buffers de consulta para traducción

Las referencias a la tabla de páginas por cada instrucción hacen que el rendimiento del sistema se reduzca a una tercera parte. Su solución se basa en la observación de que muchos programas tienden a efectuar un gran número de referencias a un número pequeño de páginas, y no al revés. La solución a este problema consiste en equipar a las computadoras con un pequeño dispositivo de hardware para transformar las direcciones virtuales en físicas sin pasar por la tabla de páginas. El dispositivo llamado tlb (buffer de consulta para traducción –Traslation Lookaside Buffer) o también memoria asociativa, generalmente se encuentra en la mmu y consiste de un pequeño número de entradas (pocas veces mas de 64). Cada entrada contiene: número de página virtual, bit modificado, código de protección y marco de página físico. Funcionamiento: cuando se presenta una dirección virtual a la mmu para ser traducida, lo primero que hace el hw es verificar si su número de página virtual está presente en el tlb, comparándolo con todas las entradas simultáneamente. Si se encuentra se toma del tlb sin acudir a la tabla de páginas. Si la dirección virtual no se encuentra en el tlb, entonces la mmu realiza una búsqueda ordinaria en la tabla de páginas, y desaloja una de las entradas del tlb y la sustituye por la entrada de tabla de páginas que encontró. Administración de tlb por software Algunas máquinas modernas risc (mips, Alpha, hp pa) realizan casi toda la administración de páginas en software. Cuando una dirección virtual no se encuentra en el tlb, la mmu efectúa un fallo de tlb y deja todo al sistema operativo (encontrar la página, eliminar una entrada del tlb y colocar la entrada nueva en el tlb, y reiniciar la instrucción que falló. Algunas mejoras se han hecho, tales como que el Sistema Operativo averigue cuáles van a ser las páginas a utilizarse y precargarlas en el tlb. 91

Tablas de páginas invertidas En este diseño hay una entrada por marco de página de la memoria real, no por cada página del espacio de direcciones virtual. La entrada indica cuál (proceso, página virtual) está en ese marco de página. La desventaja es que la traducción de virtual a física se vuelve más difícil. Cuando el proceso n hace referencia a la página virtual p, el hw ya no puede encontrar la página física usando como índice de tabla de páginas a p, ahora debe buscar en toda la tabla de páginas una entrada (n,p). Y si esto es en cada referencia a la memoria, la administración se vuelve muy lenta. Una solución es usar tlb, aunque en cada fallo de tlb hay que buscar en toda la tabla de páginas. Si se usa una tabla de dispersión como índice de la tabla de páginas invertida, la búsqueda se llevaría a cabo más rápidamente. Algoritmos de reemplazo de páginas El algoritmo de reemplazo óptimo Fácil de describir pero imposible de implantar. Rotular cada página con el número de instrucciones que se llevarán a cabo antes de que se haga la primera referencia a esa página, así la página que se debe desalojar es la que tiene el número más grande. Este algoritmo no se puede poner en práctica puesto que no sabe cuántas instrucciones se ejecutarán antes de llamar a determinada página, a menos que sean programas que ya se hayan ejecutado al menos una vez con los mismos datos. Entonces se debe llevar un registro acerca del historial de los procesos para poner en práctica este algoritmo, aún así no es un algoritmo muy útil. El algoritmo de reemplazo de páginas no usadas recientemente Para este algoritmo a cada página se le asocian dos bits r que se enciende cada vez que se hace referencia a la página para leer o escribir y m que se enciende cada vez que se escribe a la página, es decir, se modifica. Al inicio ambos bits estarán en cero, si hay un fallo de página para leer se pone el bit R a 1 y si es para escribir se pone el bit r a 1 y m también a 1, estos bits se estarán inicializando cada interrupción de reloj. Así cada vez que haya un fallo de página el so examinará y las clasificará en 4 categorías:

92

• • • •

Clase 0: No solicitada, no modificada Clase 1: No solicitada, modificada Clase 2: Solicitada, no modificada Clase 3: Solicitada, modificada

El algoritmo no usado recientemente (nru: not recently used) desaloja al azar una página de la clase de número más bajo que no esté vacía. Este algoritmo se basa en la suposición de que es preferible desalojar una página modificada a la que no se ha hecho referencia en por lo menos un tic de reloj, en vez de una página limpia que se está usando mucho. Ventajas: fácil de entender, implementación moderadamente eficiente, desempeño aceptable. El algoritmo de reemplazo de páginas de primero en entrar, primero en salir (fifo: first-in, firstout). El algoritmo de sustitución de páginas se segunda oportunidad Este algoritmo consisten en inspeccionar la página más vieja, si su bit r es 0, entonces esta página es desalojada y si ha sido modificada se escribe a disco, si su bit r es 1 entonces es colocada al final de la lista, su bit r es puesto en 0 y se actualiza su tiempo de carga como si acabara de ser traída a la memoria. Lo que hace este algoritmo de segunda oportunidad es buscar una página vieja a la que no se haya hecho referencia en el intervalo de reloj anterior. El algoritmo de sustitución de páginas por reloj Consiste en mantener todas las páginas en una lista circular. Funciona igual que el algoritmo de segunda oportunidad. El algoritmo de sustitución de páginas menos recientemente usadas (lru). Se desaloja la página que haya estado más tiempo sin usarse. Se ejecutaría en hardware y se necesitaría de una matriz de nxn bits, donde n es el número de marcos. Cada vez que se haga referencia a la página k, se encienden todos los bits del renglón k y se apagan todos los bits de la columna k, el renglón con el menor valor es la página menos recientemente usada.

93

Por ejemplo para 3 marcos. Orden de referencia: 2 0 1 0 1

0 1 2

0 1 2

0 1 2

0 1 2

0 1 2

0 0 1 1

0 0 0 1

0 0 1 1

0 0 0 1

0 0 0 0

1 0 0 0

1 1 0 1

1 0 0 1

1 1 0 1

1 0 0 0

2 0 1 0

2 0 0 0

2 0 0 0

2 0 0 0

2 1 1 0

Simulación de lru con software se puede simular con el algoritmo de No usada frecuentemente (nfu; not frequently used). En el caso puro de nfu, cada página tiene un contador. En cada interrupción de reloj el Sistema Operativo explora todas las páginas que están en memoria y suma el bit r a su contador (el contador es para saber qué tanto se hace referencia a esa página). Cuando se presenta un fallo de página se selecciona a la página con el contador más bajo. El problema con este algoritmo es que nfu nunca olvida (si hay dos contadores iguales no sabemos cuál es la página más vieja). La solución a este problema es modificar nfu para simular lru, al algoritmo que se emplea para tal simulación se denomina envejecimiento. Sigue los siguientes pasos: lru

1. 2.

Todos los contadores se desplazan un bit a la derecha antes de sumar el bit r. El bit r se suma al bit de la extrema izquierda.

Por ejemplo: Bits r para las páginas 0-3 1010

0010

0111

94

1001

Tic de reloj Página 0 1 2 3



0 10000000 00000000 10000000 00000000

1 01000000 00000000 11000000 00000000

2 00100000 10000000 11100000 10000000

3 10010000 10000000 01110000 11000000

Buffering de páginas Consiste en mantener un conjunto de marcos para página libres. Cuando se produce un fallo de página se usa un marco de página libre (sin liberar otro) pero sin aplicar el algoritmo de reemplazo. Cuando el Sistema Operativo detecta que el número de marcos de página disminuye por debajo de un umbral, aplica repetidamente el algoritmo de reemplazo de páginas hasta que el número de marcos libres sea suficiente. Las páginas liberadas que no están modificadas pasan a la lista de marcos libres. Las que han sido modificadas pasan a la lista de modificadas. Las páginas que están en cualquiera de las dos listas pueden recuperarse si vuelven a referenciarse. Este fallo no implicaría operaciones de entrada y salida. Las páginas en la lista de modificadas se pueden escribir en tandas al dispositivo para obtener un mejor rendimiento. Cuando la página modificada se ha escrito al dispositivo, se la incluye en la lista de marcos libres. Retención de páginas en memoria No todas las páginas residentes en memoria son candidatas al reemplazo. Por ejemplo las páginas del Sistema Operativo. La mayoría de los sistemas operativos tienen su mapa de memoria fijo en memoria principal. Las páginas que están llevando a cabo operaciones de entrada y salida, donde la dma (Acceso Directo a Memoria) realiza una transferencia directa a la memoria de un proceso. Éstas no pueden ser reemplazables hasta que termine la operación. Algunos Sistemas Operativos ofrecen el servicio a las aplicaciones de retener en memoria una o más páginas de su mapa. Este servicio puede ser útil para procesos de tiempo real, pero si se usa indiscriminadamente puede afectar gravemente el rendimiento del sistema. 95

Aspectos de diseño de los sistemas con paginación Paginación por demanda La paginación por demanda se da cuando se hacen transferencias desde la memoria secundaria hacia la principal sólo cuando un proceso necesita acceder a una página que no está en memoria principal, es decir, sólo se cargan páginas cuando se necesitan. Si al intentar traer la página desde memoria secundaria se detecta que no hay espacio en la memoria principal (no hay marcos libres), será necesario expulsar una página de la memoria principal hacia la secundaria. Prepaginación. En un fallo de página no sólo se trae la página en cuestión, sino también las páginas adyacentes, ya que es posible que el proceso las necesite en un corto plazo de tiempo. La efectividad de esta técnica va a depender de si hay acierto en esta predicción. Políticas de administración de la memoria virtual • •

Política de reemplazo. Determina qué página debe ser reemplazada de la memoria principal para dejar sitio a la página entrante (algoritmos de reemplazo de páginas). Política de asignación de espacio a los procesos. Decide cómo se reparte la memoria física entre los procesos existentes en un determinado instante.

Política de asignación de marcos de página Asignación fija. Se asigna a cada proceso un número fijo de marcos para página. Normalmente este tipo de asignación lleva asociada una estrategia de reemplazo local. Asignación dinámica. El número de marcos asignados a un proceso varía según las necesidades que tenga el proceso en diferentes instantes de tiempo. Con este tipo de asignación se pueden usar tanto estrategias de reemplazo locales como globales. Hiperpaginación (thrashing) Es la situación en la cual se producen un número elevado de fallos de página debido a que el número de marcos de página asignados a un proceso no es suficiente para almacenar las páginas referenciadas activamente por el mismo. Con una asignación fija sólo el proceso que hiperpágina se ve afectado, el resto no. 96

En una asignación dinámica se ven afectados todos los procesos. Cuando es el sistema hiperpágina se deben suspender uno o dos procesos. Políticas de asignación local y global ¿Los algoritmos de reemplazo de página deben desalojar una página del proceso que provocó el fallo de página o una página cualquiera de la memoria? Si es el primer caso, entonces el reemplazo de páginas es local y si se realiza lo segundo el reemplazo de páginas es global. Para acelerar el proceso de fallo de página y evitar la hiperpaginación, se podría asignar un conjunto de marcos de página por proceso de acuerdo a la frecuencia de fallos de página (pff; page fault frequency). Existen algoritmos que pueden operar local o globalmente, como lo son fifo y lru y sus similares; sin embargo existen algoritmos que sólo tienen sentido en una estrategia local como los de conjunto de trabajo y wsclock. Control de carga Si la memoria está llena es obvio que haya fallos de página y por ende hiperpaginación. Para resolver el problema es necesario bajar a disco algunos procesos y liberar todos sus marcos de página y asignarlos a los procesos que están hiperpaginados. Ahora el problema es ¿qué proceso debemos intercambiar?, pues deben considerarse sus características (algoritmos de despacho). Estrategia del conjunto de trabajo. El conjunto de trabajo de un proceso es el conjunto de páginas accedidas por un proceso en las últimas n referencias. El número n se denomina la ventana del conjunto de trabajo. 4.4 Memoria Compartida Distribuida (dsm) 4.4.1 Manejo de memoria compartida en multiprocesadores Los multiprocesadores son difíciles de construir y fáciles de programar. Las multicomputadoras son difíciles de programar y fáciles de construir. El objetivo de la memoria compartida distribuida es que el hardware en el que se base sea fácil de construir y fácil de programar. En 1986 Li y más tarde Hudak, propusieron un mecanismo para el manejo de memoria en sistemas distribuidos llamado memoria compartida distribuida (dsm). Su propuesta fue 97

tener una colección de estaciones de trabajo conectadas por una lan compartiendo un solo espacio de direcciones virtuales con páginas. La desventaja de este esquema es que exhibe un desempeño pobre, ya que las páginas andan de un lado para otro de la red. La ventaja es que es un modelo fácil de programar y de construir. Otro método consiste en no compartir todo el espacio de direcciones, sino sólo una porción seleccionada, de hecho, sólo aquellas variables o estructuras de datos que se necesitan utilizar en más de un proceso, lo cual produce un alto nivel de abstracción, pues ya no se piensa en una porción de memoria, sino en una colección de variables. Una posible optimización consiste en repetir las variables compartidas en varias máquinas, el problema en este caso es mantener consistentes las copias. Las lecturas se pueden hacer de manera local, sin ningún tráfico y las escrituras mediante un protocolo de actualización con varias copias. Otra posible optimización es compartir objetos. 4.4.1.1 Multiprocesadores basados en un bus.

CPU

CPU

CPU

Memoria bus

Para evitar que dos o más cpu’s intenten el acceso a la memoria al mismo tiempo, se necesita algún tipo de arbitraje del bus. El cpu debe pedir permiso para conseguir el bus. La concesión puede hacerse de forma centralizada, utilizando un dispositivo de arbitraje de bus, o de forma descentralizada, donde el primer cpu que realice una solicitud en el bus ganará cualquier conflicto. La desventaja es la sobrecarga del bus. Una solución sería equipar a cada cpu con un caché husmeador.

CPU Cache

CPU Cache

CPU Cache

Memoria bus

98

Un protocolo en particular común es el de escritura a través del caché. Cuando un cpu lee por primera vez una palabra de memoria, esa palabra es llevada por el bus y guardada en el caché del cpu solicitante. Puede suceder que una palabra en particular se oculte en dos o más cpu al mismo tiempo. Operación de lectura • •

Si la palabra no está en el caché, entonces buscarla en la memoria y copiarla a su caché. Si la palabra está en el caché, tomar el dato de ahí.

Operación de escritura • • •

Si ningún cpu tiene la palabra en su caché, entonces la palabra es actualizada en memoria, como si el ocultamiento no hubiera sido utilizado. Si el cpu (que realiza la escritura) tiene la única copia de la palabra, se actualiza su caché y también la memoria mediante el bus. Si dos o más cpu tienen la palabra, entonces se actualiza la palabra en el caché y en la memoria, y se invalidan las entradas de esa palabra en los cahés de los otros cpu. Así la palabra sólo la tendrá la memoria y un sólo caché.

Una alternativa a invalidar otras entradas de caché es actualizarlas todas, pero esto puede resultar más lento.Una ventaja de este protocolo es que es fácil de entender e implantar, la desventaja es que todas las escrituras utilizan el bus. Existe otro tipo de protocolos como el protocolo de membresía. Una versión de este protocolo plantea lo siguiente: Se manejan bloques de caché, cada uno de los cuales puede estar en uno de los siguientes estados: 1. 2. 3.

INVÁLIDO: Este bloque de caché no contiene datos válidos. LIMPIO: La memoria está actualizada, el bloque puede estar en otros cachés. SUCIO: La memoria es incorrecta; ningún otro caché puede contener al bloque.

A

B

C

W1

La memoria es correcta

W1 limpio

bus

99

Estado inicial. La palabra W que contiene el valor w1 esta en la memoria y también está en el caché de B

A

B

W1

W1 limpio

A

B

W2

W1 sucio

C

limpio

B

W3

W1 sucio

C

W1

C

W1

invalido

La memoria ya no es correcta

bus

B

C

W3

W1

W3 invalido

La memoria ya no es correcta

bus

A

invalido

A lee la palabra W y obtiene W1. B no responde a la lectura, pero la memoria si.

bus

invalido

A

La memoria es correcta

W1

W1

sucio

La memoria ya no es correcta

bus

100

A escribe un valor W2. B husmea en el bus, ve la escritura e invalida su entrada. La copia de A se marca como sucio.

A escribe W de nuevo. Esta y las escrituras posteriores por A se realizan de manera local, sin tráfico en el bus.

C lee o escribe W. A ve la solicitud al husmear en el bus, proporciona el valor e invalida su propia entrada. C tiene ahora la única copia válida.

La palabra permanece en estado sucio hasta que se elimine del caché donde se encuentra en la actualidad por razones de espacio. En este momento desaparece de todos los cachés y se escribe en la memoria. Este protocolo tiene tres propiedades importantes: 1. 2. 3.

La consistencia se logra haciendo que todos los cachés husmeen el bus. El protocolo se integra dentro de la unidad de administración de memoria. Todo el algoritmo se realiza en un ciclo de memoria.

La desventaja es que no funciona para multiprocesadores de mayor tamaño y nada es válido para la memoria compartida distribuida. 4.4.1.2 Multiprocesadores basados en un anillo Un ejemplo de multiprocesadores basados en anillo es Memnet. En Memnet, un espacio de direcciones se divide en una parte privada y una compartida. La parte compartida se divide en bloques de 32 bytes, unidad mediante la cual se realizan las transferencias entre las máquinas. Las máquinas Memnet están conectadas mediante un anillo de fichas modificado. El anillo consta de 20 cables paralelos, que juntos permiten enviar 16 bits de datos y 4 bits de control cada 100 nanosegundos, para una velocidad de datos de 160 Mb/seg.

MMU

Cache

Dispositivo Interrupción Memnet Exclusivo

Mem. de origen

CPU Memoria Privada

Valido

101

Origen

Posición

Un bloque exclusivo de lectura puede estar presente en varias máquinas, uno de lecturaescritura debe estar presente en una sola máquina. Los bits en el dispositivo Memnet indican uno o más de los siguientes estados: • • • • •

VÁLIDO: El bloque está presente en el caché y está actualizado. EXCLUSIVO: La copia local es la única. ORIGEN: Se activa si ésta es la máquina origen del bloque. INTERRUPCIÓN: Se utiliza para forzar interrupciones. POSICIÓN: Indica la localización del bloque en el caché si está presente y es válido.

Protocolo Memnet Lectura Cuando un cpu desea leer una palabra de la memoria compartida, la dirección de memoria por leer se transfiere al dispositivo Memnet, el cual verifica la tabla del bloque para ver si está presente. Si es así, la solicitud es satisfecha de inmediato. En caso contrario, el dispositivo Memnet espera hasta capturar la ficha que circula; después, coloca un paquete de solicitud en el anillo y suspende el cpu. El paquete de solicitud contiene la dirección deseada y un campo vacío de 32 bytes. Cada dispositivo Memnet en el anillo verifica si tiene el bloque. De ser así, coloca el bloque en el campo vacío y modifica el encabezado del paquete para inhibir la acción de las máquinas posteriores. Si el bit exclusivo del bloque está activo, se limpia. Cuando el paquete regresa al emisor, se garantiza que contiene al bloque solicitado. El cpu que envía la solicitud guarda el bloque, satisface la solicitud y libera al cpu. Si la máquina solicitante no tiene espacio libre en su caché para contener el bloque recibido, entonces toma al azar un bloque oculto y lo envía a su origen, con lo que libera un espacio de caché. Los bloques cuyo bit origen están activados nunca se eligen, pues se encuentran en su origen. Escritura Tenemos tres casos: • •

Si el bloque contiene la palabra por escribir está presente y es la única copia en el sistema, (el bit exclusivo esta activado) la palabra sólo se escribe de manera local. Si está presente el bloque pero no es la única copia, se envía primero un paquete de invalidación por el anillo para que las otras máquinas desechen sus copias del bloque por 102

•

escribir. Cuando el paquete de invalidación regresa al solicitante, el bit exclusivo se activa para ese bloque y se procede a la escritura local. Si el bloque no está presente, se envía un paquete que combina una solicitud de lectura y una de invalidación. La primera máquina que tenga el bloque lo copia en el paquete y desecha su copia. Todas las máquinas posteriores sólo desechan el bloque de sus cachés. Cuando el paquete regresa al emisor, éste lo guarda y escribe en él.

La ventaja de este protocolo es que se puede aplicar a multicomputadoras. 4.4.2 Principales aproximaciones a dsm Existen tres aproximaciones a la implementación de memoria compartida distribuida, las cuales involucran el uso de hardware, memoria virtual o bibliotecas de soporte. Estos no son mutuamente exclusivas necesariamente. Basada en hardware. Por ejemplo Dash y plus. El conjunto de procesadores y los módulos de memoria están conectados vía una red de alta velocidad. El problema es la escalabilidad. Basado en páginas. Por ejemplo Ivy, Munin, Mirage, Clouds, Choices, COOL y Mether, todas implantan dsm como una región de memoria virtual que ocupa el mismo rango de dirección en el espacio de direcciones de cada proceso participante. En cada caso el kernel mantiene la consistencia de datos dentro de las regiones dsm como parte del manejo de fallo de página. Basado en bibliotecas. Algunos lenguajes o extensiones de lenguaje tales como Linda soportan formas de dsm.

103

orca

y

Ejercicios

1. Las direcciones virtuales son direcciones generadas por: a) Los programas b) Por la paginación

c) La tabla de páginas

2. Suponga que el número de bits utilizados en una dirección virtual es de 20, se ocupan 8 bits para el número de página y 12 para el desplazamiento ¿Cuántas páginas se pueden manejar en memoria virtual? __________ 3. De acuerdo a la pregunta anterior, ¿qué cantidad de memoria virtual se está manejando? _________________________ 4. El objetivo de un tlb es: a) El manejo de tablas de página muy grandes c) El tlb es la tabla de páginas

b)

Acelerar la paginación

5. La diferencia entre estos dos algoritmos difiere únicamente en la estructura de datos a utilizar, pero su política de reemplazo es la misma a) nru y lru b) De segunda oportunidad y el de tipo reloj c) fifo y Conjunto de trabajo 6. Suponga que tenemos cinco páginas (0 a 4) y que los contadores iniciales de cada página son: para 0 es 01101100, para 1 es 00000111, para 2 es 10000101, para 3 es 10000000, para 4 es 11011110. En los siguientes tics de reloj son referenciadas las siguientes páginas: tic0 1,3; tic1 0,2,4 , tic2 1,4. Suponga que en este último tic hay un fallo de página. ¿Qué página deberá ser desalojada? Utilice el algoritmo de envejecimiento y describa el comportamiento de contadores en cada tic de reloj. 7. Suponga que se está utilizando el algoritmo fifo para el reemplazo de páginas. Si tenemos las páginas b5, d1, c2, d6, a3, d3, a5, d1, b1, a1, d7, en este orden (B5 es la más antigua y D7 la más reciente); y D3 produce un fallo un página (invoca a D9), ¿Qué página debemos desalojar si se está utilizando una política de asignación local? ____

104

8. Suponga que se está utilizando el protocolo de membresía y se tienen 6 cpu, el cpu 1, el 4 y 5 tienen la palabra ‘w’ en su caché y su estado es limpio. De pronto el cpu 3 necesita escribir la palabra ‘w’. ¿Qué operaciones se realizarán y cuál será el estado de los cachés y de la memoria? 9. ¿Por qué se genera un número elevado de fallos de página en la hiperpaginación (thrashing)? _________________________________________________________ 10. ¿Los algoritmos de reemplazo de página deben desalojar una página del proceso que provocó el fallo de página o una página cualquiera de la memoria? __________________________________________________________________

Referencias

1. Andrew Tanembaum. Computer Network. Uppers Saddle River, NJ:Prentice Hall, 2. Haviland, Keith; Salama, Ben. Unix System Programming. Addison-Wesley Publishing Company. 3. Coulouris George, Dollimore Jean, Kindberg Tim. Sistemas Distribuidos, Conceptos y Diseño, 3ª. Edición, Addison Wesley. 4. Randy Chow, Theodore Jhonson, Distributed Operating Systems & Algorithms, Addison-Wesley.

105

V Sockets en Java

Existen dos protocolos de transporte en la familia tcp/ip que son tcp y udp; los cuales asumen la tarea de transmitir datos de un puerto a otro para llevar a cabo la comunicación entre aplicaciones. tcp es un servicio de transporte orientado a conexión y quiere decir: Transmission Control Protocol (Protocolo de Control de la Transmisión). Cuando existe una comunicación tcp también existe un enlace entre el emisor y el receptor, el cual permite que se intercambie la información de manera bidireccional. Este protocolo introduce algoritmos de detección y corrección de errores en la transmisión de datos; y garantiza que la entrega de los paquetes de datos tcp (datagramas tcp), sean al receptor, en el orden en que los envió el emisor. Este protocolo sacrifica rapidez pero aumenta la seguridad. Mientras que un emisor envía un datagrama tcp, se comienza una cuenta atrás de cierto tiempo. Cuando el tiempo acaba y el emisor no ha recibido ningún mensaje de confirmación de la aplicación tcp del receptor, entonces el datagrama se envía de nuevo. El protocolo tcp proporciona confiabilidad a ip. Con el protocolo tcp, las comunicaciones se realizan mediante flujos de bytes. Realmente, la comunicación física se basa en paquetes llamados (datagramas); pero tcp simula un flujo lógico continuo de bytes. En una capa de nivel más bajo, el protocolo tcp acepta un flujo de datos de una aplicación, fragmenta los datos en datagramas que no exceden de 65535 bytes y envía cada datagrama a la capa de red, donde será transformado en un paquete ip. Al llegar los datagramas ip al nodo de destino, éste los pasa a la aplicación tcp correspondiente, que reconstruye el flujo continuo de bytes. A causa del enlace que existe entre el emisor y el receptor durante una comunicación tcp, el protocolo se compara con el servicio telefónico: se establece la conexión, se transfieren los datos y, por último, se cierra la conexión. 107

Figura 1. Esquema de un datagrama tcp. El campo inferior alberga los datos. En el proceso de envío de la información entre ordenadores, los datagramas tcp se encapsulan en datagramas ip.

Figura 2. Esquema del funcionamiento del protocolo tcp.

108

El protocolo de datagramas de usuario (udp, User Datagram Protocol), es un servicio de transporte sin conexión: el mensaje del emisor se descompone en paquetes udp (datagramas udp); y cada datagrama se envía al receptor por el camino que se envíe oportuno, de forma independiente de los otros. Los datagramas pueden llegar en cualquier orden al receptor (incluso pueden no llegar), y el emisor ignora si han llegado correctamente o no. Por este motivo, udp suele compararse con el servicio postal: se envían los datos sin que medie conexión (una carta puede enviarse sin que se sepa si existe la dirección de destino o si alguien vive allí).

Figura 3. Esquema de un datagrama udp. El campo inferior alberga los datos.

El envío de información entre ordenadores se lleva a cabo mediante el encapsulamiento de los datagramas udp en datagramas ip. Los protocolos tcp y udp usan sockets (literalmente, “conectores” o “enchufes”; el término procede de los paneles de conexiones que usaban antes las centralitas telefónicas, paneles donde la conmutación de las líneas telefónicas se hacía a mano) para comunicar programas entre sí en una arquitectura cliente-servidor. Un socket es un punto terminal o extremo en el enlace de comunicación entre dos aplicaciones (que, por lo general, se ejecutan en ordenadores distintos). Las aplicaciones se comunican mediante el envío y recepción de mensajes mediante sockets. Un socket tcp viene a ser un teléfono; un socket udp, un buzón de correos. Los sockets pueden encuadrar dentro de uno de estos grupos: • •

Sockets activos: pueden enviar y recibir datos a través de una conexión abierta. Sockets pasivos: esperan intentos de conexión. Cuando llega una conexión entrante, le asignan un socket activo. No sirven para enviar o recibir datos. 109

El socket es la abstracción de software usada para representar los terminales de una conexión entre dos máquinas. Para una conexión dada, hay un socket en cada máquina, y puedes imaginar un cable hipotético corriendo entre las dos máquinas con cada extremo del cable enchufado a un socket. Desde luego, el hardware físico y el cableado entre máquinas, es completamente desconocido. El punto fundamental de la abstracción es que no necesitamos conocer más de lo necesario. La abstracción del socket

Figura 4. La abstracción del socket.

Figura 5. Ubicación conceptual de los sockets. 110

Figura 6. Comunicación mediante sockets.

Figura 7. Comunicación mediante sockets incluyendo puertos. 111

Según Bruce Eckel, los sockets son creados por el Sistema Operativo y ofrecen una interfaz de programación de aplicaciones (api) mediante la cual pueden las aplicaciones enviar mensajes a otras aplicaciones, ya sean locales o remotas. Las operaciones de los sockets (enviar, recibir, etc.) se implementan como llamadas al Sistema Operativo en todos los modernos so; dicho de otra manera: los sockets forman parte del núcleo del so. En lenguajes orientados a objetos como Java o C++, las clases de sockets se implementan sobre las funciones ofrecidas por el so para sockets. Consideremos un servidor Web (es decir, http) que atiende simultáneamente a varios clientes por el puerto estándar (80). Los clientes usan el protocolo tcp (http usa este protocolo por defecto). ¿Cómo puede el servidor saber a qué cliente corresponde cada petición? La respuesta se representa en la figura 8.

Figura 8. Estructura interna de una comunicación con sockets tcp. Por ejemplo, para el protocolo http:

Figura 9. Una comunicación http desde el punto de vista de los sockets.

112

Las diferencias entre las comunicaciones con sockets tcp y con sockets udp resultan similares a las que existen entre llamar por teléfono y enviar una carta. Por ejemplo, cuando se llama por teléfono a alguien, el estado de la comunicación se conoce en todo momento: quien llama sabe si el teléfono está ocupado o no (en algunos casos, el destinatario de la llamada también sabe si tiene alguna llamada entrante); percibe cuándo puede comenzar la comunicación (cuando acaban los pitidos largos y suena una voz); sabe si se está dirigiendo a la persona deseada (salvo que lo engañen) y distingue cuándo la comunicación ha concluido o se ha interrumpido (cuando cesa la voz del interlocutor y se oyen unos pitidos breves). Por otro lado, cuando se envía una carta el remitente la introduce en un buzón y se olvida de ella durante un tiempo: ignora si llegará a su destino o si recibirá respuesta (la dirección puede no existir; el destinatario puede no vivir ya allí; la carta puede perderse en alguna oficina de correos con exceso de trabajo). No puede haber, un seguimiento continuo del estado de la comunicación Si no recibe respuesta, no estará seguro de si la carta llegó a su destino; lo mismo ocurre en el protocolo udp: un emisor de datagramas udp desconoce si llegan o no a su destino. Por esto, para que se pueda llevar a cabo la comunicación cliente-servidor, el cliente debe establecer sockets y conectarlos a sockets del servidor. Los pasos que se siguen en una comunicación típica con sockets tcp son éstos: • Se crean los sockets en el cliente y el servidor. • El servidor establece el puerto por el que proporcionará el servicio. • El servidor permanece a la escucha de peticiones de los clientes por el puerto definido en el paso anterior. • Un cliente conecta con el servidor. • El servidor acepta la conexión. • Se realiza el intercambio de datos. • El cliente o el servidor, o ambos, cierran la conexión. Para comenzar, el servidor debe estar en ejecución antes de que los clientes intenten conectarse a él y debe mantener activo un socket pasivo que permanezca a la espera de peticiones entrantes. Después, el cliente debe crear un socket activo en el cual se especifiquen la dirección ip y el número de puerto de la aplicación que proporciona el servicio deseado. Mediante este socket, el cliente comienza una conexión tcp con el servidor. En tercer

113

lugar, el intento de conexión tcp desencadena que el servidor cree un socket activo para el cliente (durante su tiempo de vida, no podrá ser asignado a otros clientes). Finalmente, se establece la conexión tcp entre el socket del cliente y el socket activo del servidor. A partir de entonces, uno y otro pueden enviar datos o recibirlos a través de la conexión. Un socket es la representación de una conexión para la transmisión de información entre dos aplicaciones para el programador de Java, ya se ejecuten en un mismo ordenador o en varios. Esta abstracción de alto nivel permite despreocuparse de los detalles que yacen bajo ella (correspondientes a los protocolos subyacentes). Para implementar los sockets tcp, el paquete java.net de Java proporciona dos clases: ServerSocket y Socket. La primera representa un socket pasivo que espera conexiones de los clientes y que se ubica en el lado del servidor. La segunda representa un socket activo que puede enviar y recibir datos (puede ubicarse en el servidor y en el cliente). Podemos resumir que un socket permite conectarse a un equipo a través de un puerto, enviar o recibir datos y cerrar la conexión establecida. Todos los detalles de los protocolos de red, de la naturaleza física de las redes de telecomunicaciones y de los sistemas operativos involucrados se ocultan a los programadores. Si no fuera así, no habría muchos más programadores de aplicaciones para redes que estudiosos de la literatura en sánscrito. El Paquete Java.Net De Java Java proporciona una interfaz de sockets orientada a objetos que simplifica muchísimo el trabajo en red. Comunicarse con otras aplicaciones a través de Internet es muy similar a obtener la entrada del usuario a través de la consola o a leer archivos con este lenguaje, en contraste con lo que sucede en lenguajes como C. Java fue el primer lenguaje de programación donde la manipulación de la entrada y salida de datos a través de la red se realizaba como la E/S con archivos. java.net proporciona una interfaz orientada a objetos para crear y manejar sockets, conexiones http, localizadores url, etc., comprende clases que se pueden dividir en dos grupos: a) Clases que corresponden a las api (Interfaces de Programación de Aplicaciones) de los sockets: Socket, ServerSocket, DatagramSocket, etc. b) Clases correspondientes a herramientas para trabajar con url: url, urlConnection, HttpurlConnection, urlEncoder, etc.

114

El contenido completo de java.net en la J2SE 1.2 es el siguiente: Clases: Authenticator ContentHandler DatagramPacket DatagramSocket DatagramSocketImpl HttpurlConnection InetAddress JarurlConnection MulticastSocket NetPermission PasswordAuthentication ServerSocket Socket SocketImpl SocketPermission url urlClassLoader urlConnection urlDecoder urlEncoder urlStreamHandler

Excepciones: BindException ConnectException MalformedURLException NoRouteToHostException ProtocolException SocketException UnknownHostException UnknownServiceException

115

Interfaces: ContentHandlerFactory FileNameMap SocketImplFactory SocketOptions URLStreamHandlerFactory El paquete java.net permite trabajar con los protocolos tcp y udp. La clase java.net. Socket permite crear socket tcp para el cliente; la clase java.net.ServerSocket hace lo mismo para el servidor. Para las comunicaciones udp, java ofrece la clase java.net.DatagramSocket para los dos lados de una comunicación udp, y la clase java.net.DatagramPacket para crear datagramas udp.

Clases MulticastSocket Basadas DatagramPacket

DatagramSocket

en UDP

Conexión mediante datagramas sin conexión Clases Socket

ServerSocket

Basadas en TCP

Comunicación sin conexión

URL

URLEncoder

InetAdress

Manipulación de direcciones de internen

Figura 10. Esquema de las clases basadas en tcp y udp

116

La clase java.net.ServerSocket Esta clase la utiliza el servidor mediante el protocolo tcp para recibir conexiones de los clientes. Toda aplicación que actué como servidor deberá crear una instancia de la clase ServerSocket y así podrá llamar a su método accept(); esto hará que la aplicación que actúa como servidor sea bloqueada (o sea, permanecerá esperando) sólo hasta que algún cliente solicite conexión. Cuando un cliente haya solicitado conectarse al servidor, el método accept() creará una instancia de la clase java.net.Socket la cual será usada para conectarse con el cliente. Es posible que un servidor tenga un único objeto ServerSocket y muchos objetos Socket asociados. ServerSocket será siempre un objeto pasivo. Se ha considerado en la documentación de Sun y en algunos otros libros que SeverSocket son “sockets de servidor”, esta identificación resulta ambigua, un servidor de socket siempre será aquel que reside en un servidor, ya sea pasivo (ServerSocket) o activo (Socket). Conexión entrante Aplicación de cliente

ServerSocket

Socket

Aplicación cliente Sock et

Sock et

Socket

Sock et

Aplicación de Servidora

Figura 11. Las clases socket y serversocket en funcionamiento. 117

Los constructores más utilizados por la ServerSocket son los siguientes: • • •

public ServerSocket(int puerto) throws IOException public ServerSocket(int puerto, int longitudCola) throws IOException public ServerSocket(int puerto, int longitudCola, InetAddress dirinternet) throws IOException

Los tres métodos cuentan con el argumento “puerto” en el cual se especifica el número de puerto que utiliza el socket del servidor para escuchar las peticiones de tcp de todos los clientes, otro argumento es “longitudCola” que indica la longitud máxima de la cola de conexiones entrantes y por último el argumento dirInternet es un objeto InetAddress. Cabe mencionar que la cola de conexiones entrantes es del tipo fifo (First In First Out: primero en entrar, primero en salir) y la longitud máxima de esta cola está determinada por el Sistema Operativo sin avisar al usuario al programador, si a caso se llegara a llenar la cola, el objeto ServerSocket rechazará nuevas conexiones hasta que se desocupe algún lugar en la cola. Las instancias de la clase java.net.InetAdress representan direcciones ip. Esta clase no contiene constructores públicos. Para poder obtener un objeto InetAddress tenemos que llamar al método estático byName() con un argumento de tipo String que representa el nombre de la computadora la cual está estableciendo la conexión con el servidor, InetAddress proporciona un método getHostName() que permite conocer el nombre del ordenador local. A continuación se mostrarán algunos ejemplos los cuales manifiestan el uso de la clase java.inet.Address (el primer ejemplo requerirá una conexión a internet):

InformarConexionUV.java import java.io.*; import java.net.*; // Proporciona información sobre la conexión a la página web de la // Universidad de Valencia. public class InformarConexionUV { public static void main(String[] args) {

118

Socket socket = null; try { InetAddress direccion = InetAddress.getByName(“www.uv.es”); System.out.println(direccion); socket = new Socket(direccion, 80); System.out.println(“Conectado a “ + socket.getInetAddress()); System.out.println(“por el puerto “ + socket.getPort()); System.out .println(“desde el puerto local “ + socket. getLocalPort()); System.out.println(“y desde la dirección local “ + socket.getLocalAddress()); } catch (UnknownHostException e1) { System.out .println(“No se pudo encontrar una máquina con ese nombre.”); } catch (SocketException e2) { System.out .println(“No se pudo conectar con la máquina por el puerto establecido.”); } catch (IOException e3) { System.out.println(e3); } finally { try { socket.close(); } catch (IOException e4) { // No se hace nada: no se pudo cerrar el socket. } } } }

119

La salida del programa anterior es:

Figura 12. Ejemplo

DireccionLocal.java import java.net.*; public class DireccionLocal { public static void main(String args[]) { try { InetAddress direccion = InetAddress.getLocalHost(); System.out.println(direccion); } catch (UnknownHostException e) { System.out .println(“Error al intentar obtener el nombre de la máquina local.”); } } } 120

La salida del programa anterior es:

Figura 13. Ejemplo de uso de la clase InetAddress.

La siguiente dirección ip 127.0.0.1 es una dirección especial la cual representa el nombre del ordenador local ya sea que estén o no conectados a Internet. Para que esta dirección pueda ser válida, el ordenador deberá tener instalada y además configurada una implementación de la pila de protocolos tcp/ip (actualmente no hay que preocuparse por eso porque los sistemas operativos se encargan de esto; pongamos como ejemplo Windows 3.1, se tenía que instalar por separado el software de tcp/ip). A continuación mencionaremos los métodos mas usados en la clase ServerSocket:

Método Descripción accept() Escucha conexiones a este socket de servidor y las acepta getInetAdress() Devuelve la dirección IP local del socket de servidor getLocalPort() Devuelve el puerto con el que escucha el socket de servidor close() Cierra el socket del servidor

121

•

public Socket accept() throws IOException: Este método espera conexiones. Una vez que sea detectada una conexión entrante, el objeto ServerSocket admitirá la conexión entrante y creará un objeto Socket. En caso de que falten conexiones el ServerSocket permanecerá en estado bloqueado. Ocurrirán casos en los que al intentar crear el objeto Socket se producirán excepciones debidas a la configuración de seguridad del ordenador donde reside el ServerSocket.

•

public InetAddress getInetAddress(): Este método devolverá un objeto InetAddress el cual contiene la dirección ip del ordenador al cual está conectado el socket. En caso de que el servidor ya no se encuentre conectado se devolverá un null.

•

public int getLocalPort(): Este método devolverá el puerto por el cual el Socket Servidor está escuchando las conexiones entrantes de los sockets clientes.

•

public void close() throws IOException: Este método tiene la capacidad de cerrar el Socket Servidor y liberará los recursos asociados. Si esta operación no fuera posible (por ejemplo, por que ya ha sido cerrado), en este caso será lanzada una excepción del tipo IOException.

En esta clase no existen métodos para poder extraer los flujos de datos de entrada y salida: es necesario usar el método accept(); y aplicar los métodos getInputStream() y getOutputStream() de la clase Socket que se vera a continuación sobre el socket devuelto. Ejemplo: // Se ha seleccionado el puerto 9000 para escuchar las // peticiones de los clientes ServerSocket socketservidor = new ServerSocket(9000); // Se creará un socket cuando un cliente haga una petición Socket socketcliente = socketservidor.accept(); Si intentamos que un ServerSocket quiera escuchar puertos por un puerto que ya está ocupado por otro ServerSocket entonces se presentará una excepción del tipo java.net. BindException.

122

Conexión entrante Aplicación de cliente

ServerSocket

Socket Puerto accept

Aplicación cliente Socket

Socket

Socket

Aplicación de Servidora

Figura 13. El método accept() en marcha.

La clase java.net.Socket Esta clase implementa sockets tcp activos (capaces de recibir y transmitir datos). Sus constructores son: protected Socket () throws SocketException protected Socket (SocketImpl impl) throws SocketException public Socket (String host, int puerto) throws UnknownHostException, IOException public Socket (InetAddress direccion, int puerto) throws IOException public Socket(String host, int puerto, InetAddress dirLocal, int puertoLocal) throws IOException public Socket (InetAddress direccion, int puerto, InetAddress dirLocal, int puertoLocal) throws 123

IOException public Socket (String host, int puerto, boolean flujo) throws IOException public Socket (InetAddress host, int puerto, boolean flujo) throws IOException protected Socket () throws SocketException protected Socket (SocketImpl impl) throws SocketException public Socket (String host, int puerto) throws UnknownHostException, IOException public Socket (InetAddress direccion, int puerto) throws IOException public Socket(String host, int puerto, InetAddress dirLocal, int puertoLocal) throws IOException public Socket (InetAddress direccion, int puerto, InetAddress dirLocal, int puertoLocal) throws IOException public Socket (String host, int puerto, boolean flujo) throws IOException public Socket (InetAddress host, int puerto, boolean flujo) throws IOException El constructor public Socket(String host, int puerto) throws UnknownHostException, IOException es posiblemente el más usado. El cual crea un objeto de tipo Socket conectado a un puerto con numero puerto de la maquina de nombre host. Si no se puede localizar la maquina con nombre host se produce una excepción del tipo java.net. UnknownHostException. El parámetro puerto corresponde al número de puerto de la maquina destino. Si no se especifica el número de local vinculado al socket, éste es asignado por la máquina virtual Java. Independientemente existe dos constructores que permiten especificar el puerto local. Método getInetAddress() getPort() getLocalAddress() getLocalPort() getInputStream() getOutputStream() close()

Descripción Devuelve la dirección InetAddress a la cual está conectado el socket Devuelve el número de puerto al que está conectado el socket Devuelve la dirección local a la cual está conectado el socket Devuelve el número de puerto local al cual está conectado el socket Devuelve un flujo de entrada para el socket Devuelve un flujo de salida para el socket Cierra el socket

124

• • • • •

•

•

public InetAddress getInetAddress(): Este método devuelve la dirección IP remota (en forma de un objeto de tipo InetAddress) de la máquina a la que está conectado el socket. public int getPort(): Este método devuelve el puerto remoto al cual está conectado el socket. public InetAddress getLocalAddress(): Este método devuelve la dirección ip local (en forma de un objeto de tipo InetAddress) a la que está conectado el socket. public int getLocalPort(): Este método devuelve el puerto local al cual está conectado el socket. public void close() throws IOException: Este método cierra el socket y libera los recursos asociados. Si la operación no es posible (por ejemplo, porque ya ha sido cerrado), se lanza una excepción IOException. Al cerrar un socket, también se cierran los flujos de entrada y de salida asociados. public InputStream getInputStream() throws IOException: Este método devuelve un flujo de entrada para el socket. Con él, una aplicación puede recibir información procedente de la máquina de destino (es decir, del otro lado de la conexión). public OutputStream getOutputStream() throws IOException: Este método devuelve un flujo de salida para el socket, que puede usarse para enviar información a la máquina de destino (es decir, al otro lado de la conexión).

Cuando se trata de sockets activos hay dos métodos que son indispensables: esto debido a que el socket necesita una manera de enviar y recibir información. Para lo que el paquete java.net ocupa al paquete java.io, en particular a las clases java.io.InputStream y java. io.OutputStream. Estas dos clases proporcionan métodos muy sencillos para la lectura y escritura de bytes y arrays de bytes, éstas a su vez extienden su funcionalidad a clase como java.io.Reader y java.io.Writer, que transmiten datos en forma de caracteres Unicode, ya no como simples bytes. Cuando trabajamos con el api java.net, tenemos a nuestra disposición tres clases del api java.io que podemos ocupar para extender la funcionalidad de los objetos devueltos por getOutputStream() y getOutputStream(): •

•

•

BufferedReader. Tiene dos métodos que nos pueden ser muy útiles read() y readLine(). El primero de éstos devuelve el valor entero correspondiente al carácter leído (devuelve -1 cuando hemos alcanzado el final del flujo), el segundo devuelve un String correspondiente a una línea de texto. Ambos provocan bloqueo: no terminan de ejecutarse hasta que haya datos disponibles o hasta que se lance una excepción. PrintStream. Incluye los métodos print() y println(), que permiten enviar datos primitivos y objetos String. El método write() permite enviar bytes arrays de bytes. Los tres métodos bloquean la E/S. PrintWriter. Es una clase similar a la anterior e incluye también los métodos print() y println(). La principal diferencia es que permite enviar caracteres codificados mediante distintas codificaciones (ISO Latin, UTF-8...). Ambos métodos bloquean la E/S. 125

Ejemplos: // 1 creamos un socket con el un nombre de host y numero de puerto dado Socket socketCliente = new Socket(“latigo.cs.buap.mx”, 25); // 2 Se crea un socket con la dirección IP dada y el puerto 25. Socket socketCliente = new Socket(“26.56.78.140”, 25); // 3 Se crea un socket con la dirección IP dada y el puerto 1025. Socket socketCliente = new Socket(“26.56.78.140”, 1025); // Se obtiene el nombre del ordenador al que pertenece el socket. System.out.println(socketCliente.getInetAddress()); // Se obtiene el número de puerto asociado al socket. System.out.println(socketCliente.getPort()); // 4 Se crea un socket con la dirección IP dada y el puerto 25. Socket socketCliente = new Socket(“26.56.78.140”, 25); // Una vez establecida la conexión, se extraen los flujos de E/S asociados al socket. InputStream entrada = socketCliente.getInputStream(); OutputStream salida = socketCliente.getOutputStream(); // Se lee del servidor un byte mediante el método read(). entrada.read(); // Se envía al servidor un byte mediante el método write(). salida.write(64); // Se usa la clase PrintWriter como envoltorio de OutputStream para enviar una cadena de // caracteres al flujo de salida. Luego, se cierra el socket. PrintWriter pw = new PrintWriter(salida, true); pw.println(“Escribiendo en la salida”); socketCliente.close(); 126

// 5 Se crea un socket con la dirección IP dada y el puerto 25. Socket socketCliente = new Socket(“26.56.78.140”, 25); // Una vez establecida la conexión, se extraen los flujos de E/S asociados al socket. InputStream entrada = socketCliente.getInputStream(); OutputStream salida = socketCliente.getOutputStream(); // Se usa la clase BufferedReader como envoltorio de InputStream para leer líneas // completas del flujo de entrada. BufferedReader br = new BufferedReader(new InputStreamReader(socketCliente.getInputStream())); // Se lee una línea completa y se cierra el socket. br.readLine(); socketCliente.close(); La implementación de cualquier programa servidor en Java sigue esta secuencia de pasos: 1. Se crea un objeto ServerSocket para escuchar a las peticiones que llegan al puerto asociado al servicio. 2. Cuando se llama al método accept(), el socket de servidor permanece a la espera de peticiones de clientes por el puerto. 3. Al llegar una solicitud se siguen tres pasos: 3.1. Se acepta la conexión, lo cual genera un objeto Socket asociado al cliente. 3.2. Se asocian objetos de las clases contenidas en el paquete java.io a los flujos (streams) de entrada y salida del socket. 3.3. Se lee de los flujos y se escribe en ellos; es decir, se leen y procesan los mensajes entrantes y se envían las respuestas a los clientes. 4. Se cierran los flujos. 5. Se cierra el socket vinculado al cliente. 6. El socket de servidor continúa a la espera de nuevas peticiones. Igualmente, los programas cliente se implementan así: 1. Se crea un objeto Socket, que tiene asociado un nodo de destino y un puerto donde se ejecuta el servicio de interés. 2. Se asocian objetos de las clases contenidas en el paquete java.io a los flujos (streams) de entrada y salida del socket. 3. Se lee de los flujos o se escribe en ellos. 127

4. Se cierran los flujos. 5. Se cierra el socket.

El cierre de los sockets no debe pasarse por alto: por su naturaleza bidireccional consumen bastantes recursos, tanto de la máquina virtual Java como del sistema operativo. Un socket se cierra cuando • • • •

finaliza el programa que lo creó; se llama a su método close(); se cierra uno de los flujos de E/S asociados; es eliminado por el recolector de basura.

Confiar en el recolector de basura para cerrar los sockets o los flujos de E/S es práctica poco recomendable. Consideremos, por ejemplo, este método: public void escribirArchivo() { try { File fichero = new File(“C:\temporal.txt”); BufferedOutputStream salida = new BufferedOutputStream(new FileOutputStream(f ichero)); salida.write( (int) ‘A’); // Escribe el byte correspondiente al carácter ‘A’ salida.flush(); } catch (IOException e) { e.printStackTrace(); } } Como el objeto salida no se cierra explícitamente, quedará marcado como posible “presa” del recolector de basura cuando termine el método. Cuando el recolector de basura lo “cace”, lo cerrará y liberará su memoria. Al cerrarse el objeto salida, también se cerrará el FileOutputStream. Perfecto. Es lo que se quiere, ¿verdad? ¿Para qué hay que preocuparse de cerrar los flujos? Hay varios motivos para rechazar el código anterior y mandarlo a un infierno mucho peor que el que sufren los objetos eliminados por el recolector de basura: 128

1.

2.

Hasta que el recolector de basura actúe, el archivo permanecerá abierto. Si se intentara borrarlo o volverlo a abrir, se arrojaría una excepción que indicaría que el archivo está abierto y en uso. La tarea del recolector de basura consiste en liberar memoria de los objetos Java que no se usan, no liberar recursos del sistema operativo (estructuras de datos, etc.). La única manera “limpia” de liberar recursos del so usados por los objetos Java es usar métodos –close(), dispose()– que se encarguen de llamar al código de limpieza escrito específicamente para cada plataforma (suele estar escrito en C o C++).

Algunos programadores se olvidan de cerrar los sockets y los flujos cuando terminan de usarlos y colocan el código de limpieza dentro del método finalize() (este método es llamado por el recolector de basura cuando se dispone a borrar algún objeto para el cual no existen referencias). Así, los recursos del so se liberarán cuando el objeto sea eliminado por el recolector de basura. En general, esta práctica resulta nefasta. Supongamos, por ejemplo, un programa que abre muchos archivos y no los cierra. Puede suceder que el límite de ficheros abiertos admitido por el so se alcance sin que el recolector de basura haya actuado –y, por ende, sin que se haya llamado a finalize(), donde reside el código de limpieza–; pues el recolector sólo empieza a ponerse nervioso y a afilarse las uñas cuando queda poca memoria en la pila, no cuando quedan pocos recursos libres para el Sistema Operativo. En este caso, el programa se colgaría o sería incapaz de abrir más archivos. Aparte, si se confía en el recolector de basura y en la limpieza de recursos dentro de finalize(), el comportamiento del programa será diferente en cada implementación de la mvj, pues cada una tiene sus técnicas para el recolector de basura: en las que el recolector fuera muy activo, funcionaría bien; en las que no, podría provocar fallos inexplicables a simple vista. La peor situación se daría en las implementaciones sin recolector de basura (la especificación de la mvj establece claramente que el recolector de basura es potestativo), típicas de los dispositivos pequeños. Los problemas derivados de no cerrar los sockets empeoran los correspondientes a mantener abiertos los flujos de E/S asociados a archivos: los sockets mantienen una conexión bidireccional que atraviesa las redes que median entre las máquinas donde están. Para mantenerla, se usan muchos recursos del sistema operativo y se produce un constante envío de datagramas ip entre las máquinas. No cerrar los sockets cuando se ha terminado de usarlos constituye un claro desperdicio de recursos. Cuando un socket no se cierra correctamente porque la aplicación ha fallado, el sistema operativo puede tardar minutos en conseguir cerrarlo. Dependiendo de la mvj y del so, la 129

“desaparición” de un socket sin hacer antes un close() puede ser interpretada por el socket del otro extremo como una falta de envío de datos, y este último socket puede colgarse hasta que se cierre el programa. Un ejemplo de aplicación cliente-servidor con java.net Para mostrar la implementación en Java de los pasos para escribir aplicaciones clienteservidor, incluyo este ejemplo:

RegistroConexiones.java import java.net.*; import java.io.*; /** * Esta clase envía un breve mensaje a los clientes que se conectan y cierra la * conexión. No puede atender a la vez a más de un cliente. Si hay algún error * al intentar enviar el mensaje al cliente (por ejemplo, porque se ha cerrado * tras conectarse), la aplicación se cierra. */ public class RegistroConexiones { public static void main(String args[]) { ServerSocket socketServidor = null; Socket socketCliente = null; PrintWriter salida = null; // Se crea el socket de servidor en el puerto 4000 try { socketServidor = new ServerSocket(4000); } catch (IOException e1) { System.out.println(“No se ha podido arrancar el servidor.”); // Se intenta cerrar el socket de servidor. if (socketServidor != null) try { socketServidor.close(); 130

} catch (IOException e2) { // No se hace nada } System.exit(-1); } while (true) { // bucle infinito try { // Se aceptan peticiones de los clientes. socketCliente = socketServidor.accept(); // Se abre un flujo de salida. salida = new PrintWriter(socketCliente. getOutputStream()); // Se muestra información sobre la conexión entrante y se envía // un mensaje al // cliente. System.out.println(“Conexión del cliente con dirección “ + socketCliente.getInetAddress(). getHostAddress() + “ por el puerto “ + socketCliente. getPort()); salida.println(“Hola y adiós”); salida.close(); // Se cierra el socket. socketCliente.close(); } catch (IOException e3) { if (salida != null) { salida.close(); } if (socketCliente != null) { try { socketCliente.close(); } catch (IOException e4) {

131

} // No se hace nada } if (socketServidor != null) { try { socketServidor.close(); } catch (IOException e5) { } // No se hace nada } e3.printStackTrace(); System.exit(-1); // Se sale del programa. } } } } El programa cliente no se necesita escribirlo: hacer un telnet (Siguiente figura).

Otro cliente del servicio de registro de conexiones 132

Salida del cliente del servicio de registro de conexiones.

El ejemplo de la clase RegistroConexiones no es aceptable en ninguna aplicación profesional: sólo es capaz de atender simultáneamente a un cliente. Mientras no acabe con uno, no podrá comenzar con el siguiente. La solución más sencilla al problema es utilizar hilos (threads). Un hilo no es más que un flujo de control dentro de una aplicación. En el programa anterior, si se asigna un hilo a cada cliente que se conecte, el programa principal podrá seguir aceptando conexiones.

133

Veámoslo con código:

RegistroConexionesHilos.java import java.net.*; import java.io.*; /** * Versión con hilos de RegistroConexiones. Esta clase envía un breve mensaje a * los clientes que se conectan y cierra la conexión. Puede atender * simultáneamente a varios clientes. Si hay algún error al intentar enviar el * mensaje al cliente (por ejemplo, porque se ha cerrado tras conectarse), se * cierra el hilo correspondiente a ese cliente, pero no la aplicación. */ public class RegistroConexionesHilos { public static void main(String args[]) { ServerSocket socketServidor = null; Socket socketCliente = null; PrintWriter salida = null; // Se crea el socket de servidor en el puerto 4000 try { socketServidor = new ServerSocket(4000); } catch (IOException e1) { System.out.println(“No se ha podido arrancar el servidor.”); // Se intenta cerrar el socket de servidor. if (socketServidor != null) try { socketServidor.close(); } catch (IOException e2) { // No se hace nada } System.exit(-1); } while (true) { // bucle infinito try { 134

// Se aceptan peticiones de los clientes. socketCliente = socketServidor.accept(); new ThreadCliente(socketCliente); } catch (IOException e3) { if (socketCliente != null) { try { socketCliente.close(); } catch (IOException e4) { } // No se hace nada } } } // fin while } } class ThreadCliente extends Thread { private Socket socketCliente; public ThreadCliente(Socket socket) { socketCliente = socket; start(); // Se arranca el hilo. } public void run() { PrintWriter salida = null; try { // Se abre un flujo de salida. salida = new PrintWriter(socketCliente.getOutputStream()); // Se muestra información sobre la conexión entrante y se envía un // mensaje al cliente. System.out.println(“Conexión del cliente con dirección “ + socketCliente.getInetAddress(). getHostAddress() + “ por el puerto “ + socketCliente.getPort());

135

salida.println(“Hola y adiós”); salida.close(); // Se cierra el socket. socketCliente.close(); } catch (IOException e1) { if (salida != null) { salida.close(); } if (socketCliente != null) { try { socketCliente.close(); } catch (IOException e2) { } // No se hace nada } e1.printStackTrace(); } } }

Referencias 1. Haviland, Keith; Salama, Ben. Unix System Programming. Addison-Wesley Publishing Company. 2. Flynn, Ida M.; McIver McHoes, Ann. Sistemas Operativos. Tercera Edición. Thomson Learning. México, 2001. 3. Chow, Jhonson . Distributed Operating Systems & Algorithms ,Addison Wesley 4. M.L.Liu, Computación Distribuida, Fundamentos y Aplicaciones. 5. Especificación del API de la Plataforma Java 1.5, http://java.sun.com/j2se/1.5/dos/api/index. html 6. Java socket API, http://java.sun.com/producsts/jdk/1.2/docs/api/index.html

136

Contenido

Prólogo 5 Capítulo 1: Introducción a los Sistemas Operativos Centralizados y Distribuidos 1.1 Componentes básicos de la Arquitectura de Von Neuman 7 1.2 Registros básicos del procesador 8 1.3 Ejecución de instrucciones 9 1.4 Interrupciones 10 1.5 Taxonomía de Flynn 10 1.6 Arquitectura de multiprocesadores 11 1.7 Definición de Sistemas operativos 11 Ejercicios 12 Referencias 14 Capítulo 2: Conceptos de Sistemas Operativos 2.1 Evolución de los Sistemas operativos 2.2 Funciones de los Sistemas operativos 2.3 Llamadas al Sistema 2.4 Estructura de un Sistema operativo 2.4.1 Micronúcleo 2.4.2 Núcleo monolítico 2.4.3 Capas virtuales 2.4.4 Otras estructuras virtuales 2.5 Tipos de Sistemas operativos 2.5.1 Sistemas operativos centralizados 2.5.2 Sistemas operativos de red 2.5.3 Sistemas operativos distribuidos 2.5.3.1 Definición 2.5.3.2 Aspectos de diseño de un sistema distribuido 2.5.3.3 Ventajas y desventajas de un sistema distribuido Ejercicios Referencias 137

15 17 19 19 19 19 20 21 22 22 22 22 22 23 24 24 26

Capítulo 3: Gestión de procesos e hilos en ambientes centralizados y distribuidos 3.1 Conceptos básicos de procesos e hilos 27 3.2 Despacho en sistemas centralizados 34 3.2.1 Criterios de despacho 34 3.2.2 Tipos de despachadores 35 3.2.3 Algoritmos de despacho 36 3.3 Despacho en sistemas operativos distribuidos 38 3.3.1 Modelos de sistemas 38 3.3.2 Planificación en sistemas distribuidos 43 3.4 Comunicación entre procesos en ambientes distribuidos 49 3.4.1 Modelos por capas 50 3.4.2 Modelo Cliente-Servidor 52 3.4.3 Llamados a procedimientos remotos (rpc) e Invocación a métodos remotos (rmi) 53 3.4.4 Comunicación en grupo 57 3.5 Sincronización en ambientes distribuidos 59 3.5.1 Sincronización de relojes 59 3.5.2 Exclusión mutua 62 3.5.3 Algoritmos de elección 65 3.5.4 Transacciones atómicas 67 3.5.5 Bloqueos 71 3.6 Tolerancia a fallas 73 Ejercicios 75 Referencias 81 Capítulo 4: Gestión de memoria en ambientes centralizados y distribuidos 4.1 Manejo de memoria con particiones fijas 85 4.2 Manejo de memoria con particiones variables 87 4.3 Memoria virtual en sistemas operativos centralizados 89 4.3.1 Paginación 90 4.4 Memoria compartida distribuida (dsm) 97 4.4.1 Manejo de memoria compartida en multiprocesadores 97 4.4.1.1 Multiprocesadores basados en un bus 98 4.4.1.2 Multiprocesadores basados en un anillo 101 4.4.2 Principales aproximaciones a dsm 103 Ejercicios 104 Referencias 105 Capítulo 5: Uso de sockets en Java 107 Referencias 136 138

Sistemas Operativos Centralizados y Distribuidos se terminó de imprimir en agosto de 2009 en la imprenta Papelería “la UNI” ubicad en Río Pánuco 6137 Col. San Manuel, Puebla, Pue. Teléfonos: 01-222 345 73 32, la coordinación estuvo a cargo de José Luis Olazo García la edición y composición tipográfica son de Ervey Castillo Tiraje 400 ejemplares.



139