Tema 1: Introducción a los sistemas operativos.

1.- ¿Qué es un S.O.?

Son un conjunto de programas que actúan como interface ó comunicación hombre - máquina (hardware), ofreciendo un entorno necesario para que el usuario pueda ejecutar sus programas, pero que a la vez limita la capacidad de la máquina, pues no podemos utilizar todos los recursos.

El S.O. tiene principalmente dos objetivos:

También podemos definir el S.O. como una parte importante de un sistema informático, pudiendo dividir el software de este en varias capas, de la siguiente forma:

Las utilidades y las herramientas sirven para dar soporte a otros programas y el software de aplicación es el que soluciona problemas concretos y que está orientado a usuarios.

CAPAS:

• S.O: Mantiene un entorno necesario para la ejecución de los programas de usuario.

• Herramientas: Son programas que nos ayudan. Proporcionan comodidad para el usuario en el uso de programas.

Ejemplos:

• Sistemas de gestión de bases de datos

• Intérpretes de ordenes (Shell): interface construido sobre el S.O., tiene ciertos interpretes sobre el S.O.

• Depuradores (Debugger): ayuda a corregir ó depurar programas.

• Programas de tratamiento de ficheros.

• Editores de texto (no procesadores): solo sirven para escribir.

• Comunicación: compiladores.

• Traductores: interpretes.

• Software de aplicación: Software construido para resolver problemas concretos (Ejemplo: Word Perfect).

• Software de sistema: Software construido para la ayuda de otros problemas, no para la ayuda del usuario.

Funciones del S.O.:

2.- Evolución histórica.

ETAPA 0:

Sólo existe hardware, no hay S.O. El programador escribía el programa y lo ejecutaba desde la consola del operador. El programa se cargaba manualmente en memoria, seguidamente se cargaba la dirección de inicio, en ese momento comenzaba la ejecución del programa, el programador seguía la misma mediante los pilotos de la consola. Podía corregir errores sobre la marcha, es decir, desde la misma consola. La salida se imprimía, se grababa en cinta ó se perforaba en una tarjeta.

Pero en esta etapa había un grave problema y era el método interactivo de reserva de tiempo de la C.P.U., ya que cada persona reservaba tiempo en una hoja de solicitud y este se calculaba a ojo. Si te faltaba tiempo, tenías que volver a continuar en otro momento, mientras que si te sobraba, la C.P.U. estaba inactiva. Por tanto el tiempo de preparación para la resolución de problemas era muy alto y como consecuencia, existía desperdicio de la C.P.U. No había S.O., sólo máquina trabajando * bajo uso de la C.P.U.

ETAPA 1:

Aparecen las cintas magnéticas. Tendremos 2 ordenadores, uno que saca cintas magnéticas (satélite) y otro (central). El central lee más rápido.

En esta etapa, lo que se intentó solucionar sobre todo era el desperdicio de tiempo de la C.P.U., ya que cada trabajo implicaba un tiempo de preparación considerable, por ejemplo, si queríamos ejecutar un programa en Fortram los pasos a seguir eran los siguientes:

• Cargar la cinta con el compilador de Fortram.

• Ejecutar el compilador de Fortram.

• Descargar la cinta del compilador.

• Cargar la cinta del ensamblador, ya que el compilador de Fortram generaba una salida en lenguaje ensamblador que tenía que ser ensamblada.

• Ejecución del ensamblador.

• Descarga de la cinta del ensamblador.

• Carga del programa objeto.

• Ejecución del programa objeto.

Y si tenías la desgracia de que se produjese un error en uno de los pasos, quizás tuvieras que empezar de nuevo.

Para solucionar el desperdicio de tiempo se encontraron 2 soluciones:

Una vez solucionado relativamente el desperdicio de tiempo, surgía un nuevo problema cuando un trabajo se detenía, ya que los operadores tenían que darse cuenta observando la consola, determinar porque se había detenido la ejecución del programa, realizar un volcado si era necesario, cargar la lectora de tarjetas ó cintas, etc., lo que hacía que la C.P.U. permaneciera inactiva. Para eliminar este tiempo de inactividad se introdujo el secuenciamiento automático de trabajos y con él se crearon los primeros y rudimentarios S.O..

Lo que se necesitaba era un procedimiento para la transferencia automática del control de un trabajo al siguiente. Así se creo un pequeño programa llamado Monitor Residente (ya que reside siempre en memoria). Al arrancar el ordenador el control estaba en el monitor residente, quien lo transfería al programa, hasta que se terminaba la ejecución del mismo, momento en el que se devolvía el control al monitor residente que continuaba con el programa siguiente. Era una forma de ejecutar secuencialmente todos los programas.

Para guiar al monitor residente de que programas debía ejecutar, se introdujeron las tarjetas de control. Un ejemplo de ello es :

Dándose cuenta que la C.P.U. quedaba inactiva el 93.7% del tiempo por culpa de los dispositivos de E/S (tarjetas perforadas), se medio solucionó el problema pasando primero la información de las tarjetas a cintas magnéticas: se pasaba la información de la tarjeta a la cinta, seguidamente se ejecutaba en el ordenador, la salida iba a otra cinta y por último si se creía conveniente se pasaba de nuevo a tarjeta. Por tanto las lectoras de tarjetas y las impresoras de línea eran operadas OFF - LINE, i.e., no por el ordenador principal. Para ello se necesitaba un pequeño ordenador que se dedicara a la tarea de copiar desde cinta ó en cinta. A éste se le llamaba Sistema Satélite y a la técnica de realizar la lectura desde tarjetas de manera adelantada se le llama Spooling.

ETAPA 2:

Aparece el concepto de interrupciones y controladores. Los controladores solapan las operaciones de E/S. Se trata de acelerar al máximo el tiempo de C.P.U..

Aparece el concepto de Multiprogramación que es un sistema para mantener ocupada el mayor tiempo posible la C.P.U., ya que existen varios procesos simultáneamente en trabajos de un grupo de ellos, si por algún motivo (especialmente operaciones E/S o término del tiempo asignado en los sistemas más modernos) hay que esperar, el S.O. cambiará a otro trabajo y lo ejecutará. Eso ocurrirá con todos los trabajos. Exige planificar los trabajos.

Multiproceso: son varios los procesos que pueden estar activos a la vez, pero solo los datos e instrucciones de uno de ellos está activo en Memoria principal (un ordenador que esté realizando varios trabajos a la vez).

Multiusuario: varios procesos pueden estar conectados a través de terminales a una computadora (como en la Escuela).

Sistemas de tiempo compartido: Lo primeros sistemas Batch eran una agrupación de trabajos similares, en los que había que esperar que acabase un trabajo para que empezase otro. Los sistemas basados en cintas o tarjetas solo permitían el acceso secuencial a los programas y datos y solo podía utilizarse una aplicación a la vez. Cuando se dispuso del almacenamiento en disco, i.e. acceso aleatorio, un S.O. Batch lee una serie de tareas diferentes, normalmente, cuando el trabajo se ha concluido imprime su salida. La característica definitiva de un sistema Batch es la falta de interacción entre el usuario y el trabajo, ya que este podía salir horas o incluso días más tarde. Por tanto estos sistemas tienen una serie de inconvenientes que son:

• El usuario no podía interaccionar en los procesos mientras se estaba ejecutando.

• La depuración de los programas se realizaba estáticamente, a partir de vocablos puntuales.

Un sistema informático interactivo o Hands - on, facilita la comunicación On - Line entre el usuario y el sistema. Los Sistemas de Tiempo Compartido son el resultado de la tentativa de obtener un funcionamiento interactivo de un sistema informático. Utiliza la planificación de la C.P.U. y la multiprogramación para dotar al usuario de una pequeña parte del ordenador compartido. Podemos trabajar con el ordenador aunque haya otros en la red. Este sistema permite que muchos usuarios compartan simultáneamente el ordenador, compartiendo el tiempo con todos los programas que se están ejecutando, siendo el tiempo de C.P.U. o de cambio de programas muy corto y el usuario no lo nota, cree que está sólo trabajando con el ordenador.

Estos sistemas necesitan introducir sistemas de seguridad, algún mecanismo de ejecución concurrente de procesos y mecanismo de protección de memoria

Sistemas en Tiempo Real: Este se utiliza frecuentemente como dispositivo de control en una aplicación especializada, con sensores que proporcionan datos al ordenador y a la vez éste se encarga de ajustarlos correctamente. Tienen que garantizar un tiempo mínimo de respuesta. Normalmente es Monousuario y se construye para entornos donde puede haber muchos sucesos. La mayoría de los sucesos son externos al S.O. y debería realizarse en un tiempo breve. Se construye porque existe un proceso que se va a encargar de cada suceso que tiene una cierta prioridad, depende de la importancia o de lo crítico que sea, se le da mayor prioridad. Capturar información, capturar recursos, necesita un soporte de memoria para que pueda comunicarse.

ETAPA 3:

Aparecen los Sistemas de Propósito General, en los cuales pueden ejecutarse cualquier tipo de aplicación. Tenemos ordenadores que no sólo hagan una cosa.

También aparecen los Sistemas Interactivos.

Los Sistemas Multimodo, que son sistemas que aportan tanto el modo interactivo como el Batch. Debido a la complejidad de estos, se hace una estructuración de los S.O..

Aparece el UNÍX.

ETAPA 4:

En esta etapa se desarrollan los microprocesadores y con ellos el ordenador personal (P.C.). Este ordenador personal monousuario necesitaba un S.O. y aparece el MS - DOS.

Aparecen los Sistemas Distribuidos (las redes comunes).

Importancia de los Sistemas de Gestión de Bases de Datos.

3.- Distintos aspectos de los S.O.

Se va a determinar que requerimiento funcional y estructural de seguridad se va a requerir respecto a los siguientes puntos:

Es un sistema de respuesta rápida, es decir, el usuario puede estar controlando el trabajo al mismo tiempo que se ejecuta. Pierde tiempo si el usuario está parado.

Mandas un proceso o trabajo. La C.P.U. no pierde tiempo si no le mandan un trabajo. Cuando no trabaja está parada. El usuario no puede seguir los pasos del programa o procesos, sólo cuado termina puede ver el resultado. Se ahorra tiempo de usuario. Tiende a aprovechar los recursos de la máquina.

Según el número de usuarios se dividen en dos tipos:

Existen 2 tipos:

OBJETIVOS PRINCIPALES: Son el tiempo de acceso y el tiempo de respuesta donde deben ser muy rápidos, para que todos los usuarios tengan las mismas oportunidades.

SISTEMAS CON MÁS DE UNA C.P.U.:

Según la arquitectura existen 2 tipos:

• Sistemas multiprocesadores o paralelos: Tienen la memoria y el reloj común. Se ejecuta sobre el S.O. multiprocesador. Tiene ventajas como mayor potencia de computación y fiabilidad. No se conoce un modelo general de S.O. multiprocesador. Un usuario nos es consciente de que hay más de un usuario trabajando con el ordenador. Utiliza memoria mínima. El objetivo de estos sistemas es aumentar la productividad del sistema y para ello hay que obtener paralelismo de tareas, es decir, más de una C.P.U. destinada a una misma aplicación. Y se ejecutan varias tareas que se reparten entre las distintas C.P.U..

• Sistemas distribuidos: La memoria es local, es decir, no compartida. Los usuarios son conscientes de que hay varias máquinas. Hay 2 tipos de S.O._

• Los de red: Los usuarios son conscientes de que hay varias máquinas. Cada nodo o cada máquina ejecuta su propio S.O. local. La comunicación es remota por medio de protocolos, pudiendo elegir el usuario la máquina donde realizar la aplicación, teniendo en cuenta que hay otros usuarios.

• Lo S.O. realmente o propiamente distribuidos: Aquí no son conscientes de que hay más de un usuario. Permite que el programa se ejecute en distintas C.P.U. (Ejemplo: el Linux de la Escuela).

4.- Soporte Hardware de los S.O.

Estos modos de funcionamiento del procesador se van a almacenar en 1 ó más bits del programa.

• Tiene acceso completo a todas las direcciones.

• Puede ejecutar cualquier instrucción máquina.

• Puede cambiar el valor de cualquier sentencia de la C.P.U.

• Modo Usuario (Bit de modo a 1):

• Sólo tiene acceso a un rango de dirección de memoria.

• No tiene acceso a las instrucciones privilegiadas.

• Activación o desactivación de las instrucciones.

• Sólo puede cambiar los valores de algunos registros del procedimiento.

• Software de diagnóstico.

• Programas que resuelven estadísticas: para comprobar el funcionamiento de la C.P.U. y hacer mejoras.

Nota: Sólo el S.O. puede usar la instrucción privilegiada de cambio de modo.

• INTERRUPCIONES Y EXCEPCIONES:

Hardware: Mecanismo por el cual cuando se ha producido un problema o algo raro en el sistema, provoca el paso del control de la C.P.U. a una interrupción que se almacena en una posición de memoria

Cuando se produce una interrupción de hardware, los pasos que sigue el ordenador son los siguientes:

• Deshabilitar las interrupciones para que sólo se produzca una cada vez (Opcional).

• Salvar el contador del programa y la palabra de estado (C.P. y P.S.W. respectivamente).

• Pasar a modo supervisor.

• Calcular el vector de interrupción.

• Pasar el control a la R.T.I. (Rutina de tratamiento de información; se carga la 1ª rutina en el vector de interrupción).

• Una vez ejecutada la R.T.I. restauramos el C.P. (contador de programa).

• Poner en modo usuario.

• Pasar el control al proceso que estaba en curso antes de que se produjera la interrupción.

Cuando se produce una interrupción hay que controlar que no se produzca otra ya que al provocarse 2 interrupciones a la vez se puede quedar colgado. Para evitar que se ejecuten 2 interrupciones a la vez y que se quede colgado, existen dos posibles soluciones:

• La más burda, que consiste en deshabilitar las interrupciones nada más producirse una para que no se produzcan más (es decir, el paso 1).

• Enmascaramiento de interrupciones: es un proceso más común y menos burdo que el anterior. Nos clasifica las interrupciones por tipos (privilegios). En el momento de producirse una interrupción, se deshabilitan las que sean de igual o menor privilegio.

Las interrupciones se utilizan también para controlar unidades que operan aparentemente y para responder a condiciones concretas del procesador.

Los tipos de interrupciones dependen de la arquitectura del procesador como por ejemplo:

• Ejecución de un programa (oveflow,...).

• Temporizador o reloj.

• Funciones de E/S.

• Fallo de hardware.

• Error en el direccionamiento.

• Violación de privilegios.

• Acceso a instrucciones ilegales o privilegiadas.

• Finalización de la tarea de un controlador.

• Chequeo de la propia máquina.

• PROTECCIÓN:

Este subapartado lo vamos a dividir en 3 partes claramente diferenciadas:

• Protección de E/S :

Una protección de E/S se asegura haciendo que las instrucciones de E/S sean instrucciones máquina, i.e. que sean instrucciones privilegiadas. El hardware cuida de que dichas instrucciones se ejecuten sólo en modos supervisor ya que si se hace tentativa de hacerlo en modo usuario, este no la ejecuta, la trata como ilegal. Siempre que se produce una interrupción, el hardware cambia de modo usuario a supervisor y antes de devolver el control al programa se vuelve a pasar a modo usuario.

• Protección de memoria:




En este caso debemos proteger a:

• La memoria que une el S.O. de los procesos de usuario. Con ello obtenemos la protección en la memoria

• Los procesos de usuarios entre ellos.

• Otro hardware subyacente, hardware que use memoria

• El vector de interrupciones de cualquier modificación por parte del usuario (muy importante proteger esto).

• Las rutinas de servicio de interrupciones del supervisor residente ante una posible modificación.

Tenemos que asegurarnos que un programa de usuario nunca toma el control del ordenador en modo supervisor

• Protección de la C.P.U.:

Se basa en garantizar que para cierto intervalo de tiempo se pasará el control al S.O., esto se realiza mediante un reloj que cada cierto intervalo de tiempo produce una interrupción. Con esto tratamos de contrarrestar los bucles infinitos y que un proceso no controle la C.P.U. todo el tiempo.

5.- Visión externa de los S.O.

• Servicios de los S.O.: este apartado lo vamos a dividir en dos subapartados claramente diferenciables:

• Ayuda al usuario:

• Aporta al usuario instrucciones para que este pueda ejecutar sus programas. Ejem.: ps Proceso que estaba activo en el sistema, el usuario sabe en que estado están sus procesos.

• Operaciones de E/S, que no pueden ser ejecutadas por el usuario sino que es el S.O. el que proporciona las instrucciones en orden

• Manipulación de archivos: abstracción de archivos. El S.O. nos da el concepto de archivo.

• Respecto a la comunicación entre procesos: cuando tenemos distintas máquinas. Tiene 2 implementaciones básicas:

• Memoria compartida. Puede usarse cuando 2 procesos están en la misma memoria, que trabajan sobre la misma variable.

• Paso de mensajes. Un proceso manda una señal a otro proceso (por ejemplo para sincronizarlos).

• Detección de errores: el S.O. debe ser capas de detectar y corregir cualquier tipo de error, tanto:

• Hardware: C.P.U., memoria, dispositivos, etc,

• Programas de usuario

• Gestión del sistema: no son generalmente servicios para usuarios normales sino que son servicios que están para los administradores.

• Correcto funcionamiento del S.O.:

• Realiza una asignación de recursos.

• Contabilidad: permite medir cuanto tiempo de C.P.U. ha consumido un determinado usuario (sobre todo se usa en redes). La contabilidad en este caso tiene 2 fines:

• Los contables propiamente dichos

• Los estadísticos.

• Relativos a protección: deben dar mecanismos para proteger a los usuarios entre ellos mismos.

• Usuario del lenguaje de órdenes (SHELL)

Son los que obtienen servicios del S.O., tecleando órdenes desde su terminal o a través de un trabajo por lotes.

El interprete (traductor) de órdenes captura dichas órdenes introducidas por el usuario, las traduce y ejecuta las llamadas al sistema necesarias para recibir el servicio requerido por el usuario.

Cuando el usuario está trabajando con el sistema, el intérprete de órdenes (SHELL) se desconecta mientras se ejecuta la orden.

Cuando se ejecuta una orden en background (segundo plano), antes de que termine la ejecución aparece el prompt del sistema en pantalla. Ejemplo: ls>fich &

• Background: Interactivamente, devuelve el prompt para seguir mientras hace algo.

• Foreground: El programa se espera hasta que finaliza una orden.

• Usuarios de las llamadas al S.O.:

Son los que realizan las llamadas al S.O. en tiempo de ejecución. Esta llamadas van a realizar una interface entre los programas de usuario en ejecución y el S.O.

Estas llamadas pueden ser mediante interrupciones o también mediante funciones que realizan los pasos necesarios para que hagan las llamadas al sistema.

El mecanismo para iniciar una llamada al S.O. transcurre por los siguientes pasos:

• Ejecución de una instrucción en Ensamblador. Ejemplo: int 12 (abrir un fichero).

• Llamada al sistema * Interrupción SINCRONÍA.

• Interrupción hardware * ASINCRONA. (se produce al hacer una llamada al sistema).

• Llamada a una función

Si mientras yo hago una llamada al S.O. con una de las formas anteriores, si se produce un error, ello provoca una interrupción.

La información que se debe transmitir al S.O. es:

• Registro de la C.P.U.

• Zona de memoria.

• Pila (esto no lo puede hacer el propio usuario).

A su vez el S.O. debe devolver el resultado y eso puede hacerse en alguno de los sitios anteriores. Para esto Unix tiene una instrucción que es trap.

6.- Estructura interna de un Sistema Operativo.

• Sistemas monolíticos.

Se caracterizan porque no tienen estructura o si la tienen está poco definida. Se trata de un conjunto de procedimientos, los cuales están visibles entre ellos. No hay modularidad ni abstracción de la información. Sólo hay un programa objeto. Podemos ver en una pequeña división que los sistemas monolíticos se dividen en tres partes:

Cualquier Procedimiento puede llamar a cualquier otro.

• Sistemas por capas o por niveles.

Se trata de una degeneración de los sistemas monolíticos. Se dividen por capas y cada una de ellas tiene una función bien definida. Cada capa a su vez se puede dividir en un conjunto de módulos.

Las ventajas del sistema por capas respecto del anterior son las siguientes:

• Modularidad.

• Fácil mantenimiento.

• Fácil modificación de alguna de las capas (los cambios no afectan a las otras capas).

• Fácil detección de errores.

Las desventajas de los sistemas por capas o la dificultad aparece a la hora de crear dichas capas, al igual que la jerarquía de dichas capas, i.e. saber cual es superior o prioritaria y cual es inferior.

La gestión de memoria no va con el hardware desnudo, sino que se has de planificar en procesos. Modificar cualquier procedimiento de una capa es muy fácil sin tener los interfaces de las capas anteriores.

Tienen 6 capas:

• Situada sobre el hardware: se asigna al procesador y gestores de multiprogramación

• Gestión y administración de memoria y disco: contiene las direcciones de los procesos en memoria y disco.

• Común: entre operador y procesos

• Manejadores o controladores de dispositivos E/S.

• Programas de usuario

• Proceso que se está ejecutando en ese momento.

Ejemplo: el sistema THE.

• Sistemas cliente - servidor.

Estos sistemas se basan en implementar partes del S.O. como procesos independientes y conservar un núcleo mínimo.

Ventaja: al ejecutarse los servidores en modo usuario, si algo falla no tiene porque pararse la máquina ya que se ejecuta en modo usuario.

Surge en este momento un problema que consiste en que si implemento el servidor de disco en modo usuario, no puede acceder a las operaciones de E/S y cosas parecidas. Este problema tiene 2 posibles soluciones:

• El núcleo se encarga de realizar las acciones en modo supervisor. Los servidores se encargan de la gestión.

• Permitir que los servidores críticos se ejecuten en modo supervisor. Pero las comunicaciones con los clientes se realizan a través del núcleo. Así quedaría:

Cliente solicita un servicio * Núcleo * Servidor lo sirve

Existen sistemas distribuidos que utilizan una arquitectura de cliente - servidor, como por ejemplo AMOEBA, MACA, etc.

NFS: Network File System

Tema 2: Procesos

1.- Concepto de proceso

Definición: Es el programa en ejecución y más cosas, i.e. un proceso es una entidad activa, que está en ejecución mientras que un programa es una entidad pasiva que no está en ejecución.

El S.O. se encarga de realizar una planificación de la C.P.U. entre los distintos tipos de procesos de manera que parezca que cada proceso dispone de una C.P.U. virtual.

Por tanto un proceso:

• Es un programa en ejecución.

• Controla los datos y la pila.

• El contexto de un proceso incluye los valores activos del C.P., registros del procesador y variables del programa.

Un proceso puede encontrarse en los siguientes estados:

• Ejecutándose o activo: Cuando utiliza la C.P.U. en un instante dado (sólo puede ser un proceso a la vez).

• Ejecutable, preparado o listo: Se encuentra detenido a la espera de que acabe de ejecutarse otro proceso para usar la C.P.U.

• Bloqueado: No se puede ejecutar debido a que se ha producido algún evento extraño.

Los procesos son asíncronos e independientes unos de otros. En la C.P.U. sólo se ejecuta un proceso cada vez.

Diagrama de transposición de estados:

• El proceso se bloquea en espera de datos: Esto ocurre cuando el proceso descubre que no puede continuar. En algunos sistemas hay que hacer una llamada al ídem para pasar al estado de bloqueo.

• El planificador elige otro proceso: Esto se produce cuando el planificador decide que el proceso en ejecución ya ha sido ejecutado el tiempo suficiente y que es hora de que otro proceso tenga tiempo de C.P.U.

• El planificador elige este proceso: Ocurre cuando los demás procesos han tenido su parte y este proceso vuelve a ejecutarse.

• Los datos están disponibles: Se produce cuando ocurre el evento externo por el cual espera el proceso (ejemplo: entrada de datos nuevos). Si no existe otro proceso en ejecución en ese momento se produce la transición a ejecutándose de forma inmediata.

Cuando a uno de los procesos se le retira la C.P.U., cada vez que pasa de bloqueado a ejecutable o al revés, el S.O. debe guardar toda la información necesaria del proceso que luego vuelve al mismo lugar donde estaba.

Toda la información que debe guardar el S.O. lo hace en una tabla de procesos. En esta tabla hay una entrada por cada proceso que exista en el sistema y contiene la información relativa al estado del proceso. A cada una de estas entradas se le llama descriptor de proceso o P.C.B. En el se guarda la información necesaria para que cuando llamemos nuevamente a un proceso que previamente le hemos retirado la C.P.U. pueda continuar. A esto se le llama cambio de contexto.

Este P.C.B. (Bloque de Control de Procesos) guarda:

• P.I.D.: identificador de procesos que contiene

• Nombre del proceso.

• Nombre del usuario.

• U.I.D.(identidad del usuario).

• Estado actual del proceso: ejecutable, ejecutándose o bloqueado.

• Guarda la línea o el puntero al proceso padre o a los procesos hijos, lo que corresponda, en los sistemas con jerarquía de procesos.

• Los sistemas que asignen prioridad a los procesos guardarán dicha prioridad.

• Información relativa a la memoria propia del proceso, así como un puntero a dicha memoria.

• C.P., registros del proceso (valores).

• Procesador en el que se ejecuta (para sistema multiprocesadores).

• Información acerca de los recursos que usa el proceso:

• Ficheros que tiene abiertos.

• Peticiones de E/S pendientes o dispositivos de E/S que tiene asignados.

• Información estadística:

• Tiempo de C.P.U. consumido por el proceso.

• Volumen de E/S.

• Tiempo bloqueado.

Nota: una interrupción no provoca un cambio de contexto. Cuando acaba la interrupción se sigue con el proceso que estaba antes de dicha interrupción.

A cada clase de dispositivos de E/S se les asocia una localidad cercana a la parte inferior de la memoria, llamado vector de interrupciones que contiene la dirección del procedimiento de servicio a las interrupciones si se produce un cambio de contexto (ejemplo: interrupción de disco).

Este cambio de contexto es una operación que normalmente sufren los procesos y consiste en retirar la C.P.U. al proceso actual (guardando todos los registros en la tabla de procesos). Como variables globales se pasan el nº de proceso activo y el apuntador de datos. Seguidamente la información depositada por la interrupción se elimina de la pila y el apuntador de ésta apunta a una pila temporal que utiliza el control del proceso. Por último asignamos la C.P.U: a otro proceso (ejecutable)

Hay dos tipos de procesos:

• Limitados por E/S: son procesos que usan la C.P.U. en intervalos cortos y pocas veces y usan mucho E/S.

• Limitados por la C.P.U.: procesos que usan mucho la C.P.U. y poco E/S.

Para obtener el mayor rendimiento posible del sistema, debemos mantener un equilibrio entre ambos tipos de procesos.

2.- Planificador de procesos.

El planificador es el que se encarga de decidir por ejemplo que proceso se va a ejecutar con anterioridad si hay más de uno ejecutable, es decir, es la parte del S.O. que planifica el orden de ejecución de los programas y utiliza un algoritmo llamado algoritmo de planificación.

Dentro de este apartado vamos a ver varios subapartados:

• Tipos de planificadores.

La actividad básica del planificador consiste en controlar que trabajos entran en un sistema o que procesos interactivos se van a ejecutar en un momento dado. El objetivo principal es optimizar el rendimiento del sistema.

Existen 3 tipos de planificadores:

• Planificadores a largo plazo: son los que se encargan de trabajar con la cola de trabajos por lote (batch). Se encarga de admitir en el sistema los trabajo por lote. Se llama cuando un proceso finaliza o si no finaliza ninguno en un cierto tiempo.

• Planificadores a medio plazo: se encargan de procesar los trabajos que están bloqueados y lo que va a insertar y quitarlo de memoria para ponerlos en la cola de ejecutables.

• Planificadores a corto plazo: de los procesos que están en la cola de ejecutables, este planificador elige que proceso va a asignarlo a la cola de la C.P.U.

Diagrama:

El planificador a largo y medio plazo es el que se encarga de regular la carga del sistema mientras que el planificador a corto plazo es el que se encarga de planificar lo mismo.

En los sistemas operativos pequeños sólo existe el planificador a corto plazo.

• Dispatcher o despachadores.

Es el que se va a encargar realmente de mandar el control de la C.P.U. a un proceso de la cola de ejecutables. Se encarga del planificador a corto plazo y asigna procesos a la C.P.U.

El funcionamiento de esto tiene varios pasos:

• Decide si se debe cambiar el proceso que está activo.

• Si se debe cambiar * Paso b.

• Si no se debe cambiar * Devuelve el control al proceso activo

• Salva el entorno volátil del proceso actual.

• Toma el primer proceso de la cola de preparados o ejecutables.

• Carga el entorno volátil del proceso elegido (el contenido del P.C.B.).

• Cede el control al proceso y lo pone en modo usuario.

La actuación del despachador se invoca por alguna de las siguientes razones:

• Un proceso finaliza.

• El S.O. decide que el proceso activo no debe seguir ejecutándose. Ejemplo: E/S o espera a la finalización de los procesos hijos.

• El proceso agota su quantum de tiempo.

• Un proceso cambia de estado de bloqueado a ejecutable.

• Políticas de planificación de la C.P.U.

Se implementa con vistas a conseguir el mayor rendimiento de la C.P.U. Consiste en un algoritmo para planificar o controlar la asignación de la C.P.U., ya que puede haber varios usuarios peleándose por la C.P.U. y el planificador debe decidir que proceso es más importante de los varios que están en la cola de ejecutables. Los objetivos son dos:

• Obtener un buen rendimiento, i.e. que se haga el mejor trabajo útil posible en el sistema.

• Obtener un buen servicio.

Con objeto de establecer si estamos obteniendo o no un buen servicio de manera objetiva establecemos unas medidas. Partamos de un proceso P1 que necesita un tiempo de servicio t.

• T (tiempo de respuesta): tiempo transcurrido desde que se remite una solicitud hasta que se produce la primera respuesta.

• M (tiempo de espera): tiempo que un proceso ha estado esperando en la cola de preparados (T-t).

• P (penalización): tiempo que ha desperdiciado el proceso en cada ráfaga (T/t). Si P es bajo mejor porque el proceso se va a ejecutar en menos t de C.P.U.

• R (índice de respuesta): es la fracción de tiempo que el proceso P1 está recibiendo servicio (t/T). Si R se aproxima a 1 será bueno mientras que si se aproxima a 0 será malo.

• Tiempo de núcleo: tiempo perdido por el núcleo del S.O. tomando decisiones de planificación y cambio de contexto. Típicamente tiene un valor de entre el 10% y el 30% del tiempo consumido.

• Tiempo de inactividad: es el tiempo en que la cola de procesos ejecutables está vacía y no se realiza ningún trabajo productivo.

Podemos clasificar los procesos en 2 tipos diferenciados:

• Procesos cortos: aquellos procesos con fuerte demanda de E/S y baja demanda de C.P.U.

• Procesos largos: aquellos procesos con fuerte demanda de C.P.U. y baja demanda de E/S.

No existe ninguna política de planificación que favorezca a todos los procesos en general.

Igualmente podemos clasificar los algoritmos de planificación en 2 categorías:

• No apropiativos o sin desplazamiento sin derecho preferente: son aquellos que mantienen el proceso al cual se le ha asignado la C.P.U. en ésta hasta que se bloquee o finalice.

• Apropiativos o con desplazamiento o con derecho preferente: son aquellos que pueden retirarle la C.P.U. a un proceso aunque éste no se haya bloqueado o finalizado.

A priori no podemos conocer cuanto va a durar la ejecución de un proceso por lo que únicamente podemos realizar una estimación. Se podría seguir una fórmula de promedio exponencial que se va a basar en las longitudes ya medidas de las ráfagas de C.P.U. anteriores:

• TN: duración real de la n - ésima ráfaga.

• *n: valor estimado de la n - exima ráfaga.

• *: valor de ponderación. 0 ***1

Así pues nos quedaría:

Normalmente, *= 0.5. En el caso de que *=0 obtendríamos que la historia reciente no influye y en el caso de que *=1 veríamos que solo cuenta la ráfaga actual.

Otra forma de planificar los procesos en espera es mediante un algoritmos de prioridades, el cual le asigna un número entero que indica la prioridad del proceso. Hay dos formas de asignar las prioridades:

• Internamente * S.O. * * Estática

• Externamente * Usuario * * Dinámica.

Los algoritmos se pueden implementar de dos formas.

• Apropiativa: Permite que los procesos ejecutables (desde el punto de vista lógico) sean suspendidos de forma temporal.

• No apropiativa: Se ejecuta el proceso seleccionado hasta que termine. Estos sistemas son fáciles de implementar aunque no son adecuados para los sistemas de propósito general con varios usuarios.

Problema: Puede pasar que con un algoritmo apropiativo, un proceso se bloquee indefinidamente.

Solución: El envejecimiento de los procesos. Se basa en aumentar la prioridad de un proceso ha medida que transcurra el tiempo para que de esta forma no se bloquee indefinidamente y no nos de problemas de inanición.

3.- Operaciones sobre procesos.

• Creación: consiste en coger memoria principal y definir la estructura de datos del proceso así como asignar el espacio de direcciones propio.

• Primero se le asigna un nombra al proceso. Puede ser simplemente con un identificador de procesos (P.I.D.).

• Creación del P.C.B. o desencriptación de procesos. Inserta el proceso en la tabla de procesos.

• Asigna alguno de los valores a los contenidos del P.C.B.:

• Establece la prioridad inicial.

• Establece el estado inicial.

• Asigna recursos iniciales como memoria, archivos abierto, etc.

El S.O. crea un proceso debido a 4 situaciones posibles:

• Recepción y admisión de un nuevo trabajo (sistemas batch).

• La conexión del usuario provoca la creación de un proceso que ejecute el SHELL (sistema interactivos).

• El S.O. crea un proceso en respuesta a una petición del usuario.

• Un proceso puede solicitar la creación de otro proceso.

Existen S.O. que permiten jerarquías de procesos, i.e. se permite que un proceso genere otro proceso, creando una estructura en árbol de tal forma que el proceso que genera en él procesos se llama padre y los generados hijos.

Cuando se produce una jerarquía de procesos, caben dos posibilidades:

• Los hijos obtienen recursos directamente del S.O.

• Los hijos comparten los recursos del padre.

Una vez que el proceso padre ha creado a los hijos y este comienza a ejecutarse, esta forma de ejecución puede ser:

• El proceso padre se bloquee hasta que finalicen sus hijos (foreground).

• Tanto el proceso padre como el hijo se ejecutan concurrentemente (UNIX). (background).

ESPACIO DE DIRECCIONES:

• Alternativa 1: Cuando se crea un proceso, existen sistemas donde el hijo es una copia exacta de la imagen del padre (UNIX: va ha hacer una llamada al sistema (fork), por tanto todos los recursos del padre van a pasar al hijo).

• Alternativa 2: Se crea el hijo con un programa que carga el propio fichero hijo (VMS, que es un S.O.).

• Destrucción: un proceso puede terminar por:

• Ha finalizado. Es algo que el propio proceso se encarga de notificar al S.O.

• El proceso provoca la finalización de otro proceso. Esto es privilegio de los procesos padres sobre sus hijos.

Eliminarlos del S.O. significa:

• Borrarlos de cualquier lista o tabla del S.O.

• Borrar el P.C.B. de la tabla de procesos.

• Desasignar los recursos que estaban activos.

En un sistema de jerarquías de procesos como el anterior puede ocurrir:

• Llamada al sistema (exit) para eliminar los recursos del sistema.

• Dos casos posibles:

• Si el proceso padre finaliza, tanto el proceso padre como el proceso hijo concluyen. La terminación del padre * terminación del hijo.

• Si el padre termina, los hijos continúan ejecutándose de forma implícita. El hijo hereda los recursos del padre caso de estar compartiéndolos.

Otra forma de terminación del sistema es con abort. Un proceso puede finalizar por concluir una ejecución o porque un proceso de jerarquía mayor realiza una llamada al sistema, pero acaba con él.

4.- Threads (hebras o hilos).

Sería bueno tener unos flujos de control de procesos. Supongamos que el S.O. con servidor de ficheros sería un proceso que cuando recibe la solicitud de otro proceso, el servidor de ficheros debe darle paso mientras los otros procesos deben esperar (bloqueado).

Esto se mejoraría con varios flujos de control que comparten el mismo espacio de direccionamiento de forma que si se ejecuta un proceso y se bloquea uno, los demás pueden seguir ejecutándose por otro lado.

Hebras o procesos ligeros: una hebra es un proceso que tiene sus propios

• Contador de programa.

• Pila.

• Conjunto de registros.

Una hebra se puede ver como un proceso de forma que el planificador trabajaría con hebras. Esto mejora el cambio de contexto que sería cambio entre hebras, con lo que se mejoraría el coste.

Todas la hebras van a tener acceso a las divisiones del espacio de direcciones, no hay protección de memoria. Cada hebra comparte con una hebra par:

• La sección de código.

• La sección de datos.

• Recursos del S.O.

Esto puede dar lugar a conflictos a la hora de ejecutarse procesos concurrentes.

Tarea: Entorno clave donde se ejecutan varias hebras que comparten el espacio de direcciones.

El proceso pesado o tradicional es un espacio de direcciones virtual con una única hebra. Las hebras van a poder estar en los mismos estados que le preceden:

• Ejecutándose.

• Ejecutable.

• Bloqueado.

Esto es así porque en un sistema de hebras, se tratan las hebras como unidad básica. Si cambiamos las tareas, empleamos el mismo coste que los procesos paralelos.

Utilizar el mecanismo de hebras aporta ventajas como:

• Mayor rendimiento.

• Aumento de concurrencia (permite varios procesos paralelos concurrentemente).

• Mejor servicio (para el usuario).

Los sistemas de hebras son muy utilizados en sistemas distribuidos multiprocesador, ya que podemos ejecutar una hebra en cada procesador.

Podemos observar varios niveles de hebras:

• Hebras implementadas en el Kernel: el kernel tiene implementadas las rutinas necesarias para el tratamiento de las hebras. Entra en la C.P.U. una hebra u otra.

• Hebras a nivel de usuario: las rutinas para trabajar con las hebras están implementadas en librerías, no en el kernel. La C.P.U. se reparte entre las diferentes hebras.

Tema 3: Comunicación y sincronización

1.- Concurrencias.

Procesos concurrentes: son aquellos procesos cuya ejecución se solapa en el tiempo.

Los procesos mantienen 2 tipos de relaciones:

• Relación de cooperación: los procesos concurrentes forman parte de la misma aplicación.

• Relación de competición: cuando los distintos procesos compiten por un recurso.

El software que se ocupa de los procesos concurrentes es la programación concurrente, que va a abarcar al conjunto de técnicas y rotaciones necesarias para expresar el paralelismo potencial de un sistema concurrente y resolver los problemas de sincronización y comunicación.

Existe paralelismo cuando hay más de una C.P.U. y seudo - paralelismo cuando solamente existe una C.P.U.

Razones por las que se necesita concurrencia en un sistema:

• Compartir recursos físicos: pues estos son limitados en un sistema. Para dar servicio a varios usuarios los procesos han de compartir recursos si dichos procesos se ejecutan de forma simultanea.

• Compartir recursos lógicos: nos puede interesar que dos procesos compartan un fichero; para ello hay que utilizar los mecanismos necesarios que nos eviten problemas.

• Mayor velocidad de ejecución: si tenemos un proceso que realiza una adecuación de una lista de números, se podría conseguir una ejecución más rápida si se divide el problema en 2 partes. En el caso de existir paralelismo real la ejecución del proceso mediante la realización de divisiones de este será más rápida que de la otra forma.

• Por razones de modularidad: vamos a tener diversos procesos independientes que realizan sus propias tareas.

• Comodidad: desde el punto de vista del usuario, por poder realizar varias tareas simultaneas.

Programas concurrentes: Existen varias secuencias que se ejecutan en paralelo, por tanto existen varios flujos de control. Existen lenguajes de programación concurrente que permiten dicha programación.

Dentro de un sistema operativo se distinguen los siguientes procesos:

• Procesos independientes: procesos que se ejecutan independientemente y no necesitan información compartida, esto es un proceso que no va a depender de otro

• Procesos cooperativos: procesos que comparten información con otros. Su estado puede ser afectado por la ejecución de otro. Ejemplo: proceso productor / consumidor.

Ejemplo de procesos cooperativos: productor - consumidor

Se dispone de un buffer en el cual introduce datos un proceso productor y un proceso consumidor retira los datos del mismo. Estos procesos son cooperativos porque se ejecutan de forma concurrente. Por ejemplo, si el proceso productor ha llenado el buffer, este proceso ha de esperar hasta que el proceso consumidor retire datos de este. El consumidor no puede retirar datos del buffer si previamente el productor no ha introducido nada. Es necesaria la introducción de mecanismos de concurrencia y sincronización para controlar la ejecución concurrente.

Otra característica de los procesos concurrentes será por tanto la sincronización entre procesos que se ejecutan de dicha forma.

Al modo en el que se ejecutan los procesos, esto es, la secuencia de instrucciones que se realizan durante la ejecución de un proceso se denomina interfoliación. Esta será una característica de los sistemas concurrentes.

Ejemplo: supongamos que se ejecutan concurrentemente dos procesos P1 y P2, compartiendo ambos una variable común x.

X está inicialmente a uno. ¿Qué valor tendrá la variable x después de que se hayan ejecutado ambos procesos? ¿0,1 ó 2?. La clave está en que las instrucciones x := x + 1 y x := x - 1 no son indivisibles. Cada una se implementa en lenguaje máquina como:






Registro 1 y registro 2 son registros del procesador (incluso pueden ser el mismo físicamente: un acumulador).

Veamos distintas secuencias de ejecución:

• a1 b1 a2 b2 a3 b3 Resultado: x=0.

• a1 a2 a3 b1 b2 b3 Resultado: x=1.

• a1 b1 b2 b3 a2 a3 Resultado: x=2.

Conclusiones:

• Debemos asegurarnos que la ejecución de procesos concurrentes sea correcta independientemente del orden en que se ejecuten sus instrucciones (interfoliación).

• No podemos hacer suposiciones de la velocidad a la que evoluciona cada proceso. Si no se utiliza un mecanismo especial no se pueden realizar suposiciones de ningún tipo.

• Necesitamos asegurar que sólo un proceso en cada ocasión manipule la variable compartida. Para ello necesitamos algún tipo de sincronización de procesos, establecer un orden relativo dentro de la interfoliación

2.- Sincronización.




La sincronización es la paralización de una actividad mientras no se cumpla una determinada condición.

Ejemplo: supongamos que queremos calcular la siguiente expresión

y tras ello, escribir el valor de A. Podríamos construir dos procesos concurrentes que realizaran lo siguiente:

Se observa que B y C se pueden ejecutar concurrentemente pero D se ha de ejecutar después. Hay que sincronizar P1 y P2, de tal forma que P2 ha de esperar hasta que P1 haya finalizado su ejecución.

Para la secuenciación de las operaciones a realizar se utilizan grafos de precedencia, que son grafos dirigidos acíclicos, en los cuales, los nodos representan las instrucciones.

Dependiendo del problema al que nos enfrentemos tendremos una solución u otra. Así pues podemos distinguir 2 casos:

• Memoria común: usamos espera ocupada. Consiste en utilizar una variable booleana para que un proceso espere hasta que el otro acabe. Así mismo podemos utilizar semáforos cuyo procedimiento es el mismo pero están predefinidos por el sistema.

• Mensajes: cuando no se pueden compartir memoria.

Problema de la exclusión mutua.

Un problema particular de la sincronización se plantea cuando en un momento dado, dos o más procesos intentan acceder a un recurso común (datos compartidos). La solución consiste en asegurarse que la secuencia de sentencias que acceden a datos compartidos se traten como una operación indivisible.

Sección crítica: Secuencia de sentencias de un proceso que accede a datos compartidos.

REQUERIMIENTOS QUE SE HAN DE SATISFACER DURANTE LA EJECUCIÓN DE LA SECCIÓN CRÍTICA:

• Dos procesos no deben encontrarse al mismo tiempo dentro de sus secciones críticas * se debe respetar la exclusión mutua. Las secciones críticas deben ejecutarse como procesos individuales.

• No se deben hacer hipótesis sobre la velocidad de los procesos o el número de C.P.U.'s.

• Ningún proceso que esté fuera de su sección crítica puede bloquear a otros procesos.

• Propiedad de vivacidad: debe haber una ausencia de inacción, ningún proceso debe de quedarse retrasado indefinidamente.

• Ningún proceso debe esperar eternamente para entrar en su sección crítica.

• Propiedad de equidad: todos los procesos deben avanzar con iguales condiciones.

• Ausencia de interbloqueo: un interbloqueo es un estado en el cual todos los procesos se esperan unos a otros y el sistema se detiene. Ejemplo: el problema de los 5 filósofos.

Soluciones para implementar la exclusión mutua:

• Soluciones software:

Protocolo de entrada: antes de ejecutar las instrucciones de la sección crítica se comprueba si se puede entrar a dicha sección, atendiendo al problema de la exclusión mutua.

Protocolo de salida: deja al proceso en un estado de tal forma que cualquier otro proceso puede acceder a su sección crítica, esto es, a la sección crítica del proceso que quedó en este estado.

Entre procesos que comparten datos o acceden a datos compartidos, existen condiciones de competencia. El resultado final de la ejecución dependerá de que proceso se ejecute y de cómo realice su ejecución.

La solución al problema de exclusión mutua es hacer que las operaciones se realicen de un solo paso, de forma indivisible.

Al conjunto de instrucciones que se ejecutan de forma independiente se denomina sección crítica. Sólo un proceso puede entrar en un instante determinado en la sección crítica.

ALGORITMO 1: Alternancia estricta de una variable compartida.

Desventajas:

• Espera ocupada (tiempo de C.P.U. desperdiciado).

• No cumple la condición 3ª, pues procesos que se encuentran fuera de sus secciones críticas bloquean a otros.

• Alternancia estricta.

ALGORITMO 2: Variables puerta de paso o de cerradura.

Si de entrada hago c1 = c2 = 1 consigo equidad.

c1 = 0 *P1 está dentro de su sección crítica.

c2 = 0 *P2 está dentro de su sección crítica.

c1 y c2 a la vez a cero * No entran en su sección crítica.

No resuelve el problema de la exclusión mutua.

MODIFICACIÓN DEL ALGORITMO 2:

Inicialmente c1 = c2 = 1.

Ningún proceso entra en la sección crítica, paro si soluciona el problema de la exclusión mutua.

Pueden bloquearse ambos procesos * INTERBLOQUEO.

ALGORITMO 3: Modificación de los dos anteriores.

Cambia las estrategias anteriores, utiliza una variable turno, que controla cuando 2 procesos intentan acceder a la vez a la sección crítica.

c1 y c2 indican que la sección crítica está libre para P1 ó P2, esto es, si P1 está en la sección crítica c1 está a cero y en caso contrario sale de la sección crítica.

Se cumple la condición de la exclusión mutua.

Se cumple la condición 3ª, esto es, ningún proceso puede bloquear a otro si no se encuentra en la sección crítica.

Cumple todas las condiciones.

• Soluciones hardware:

• Activación - desactivación de interrupciones

Si se desactivan las interrupciones no se presenta el problema de la exclusión mutua porque al hacerlo impedimos que ningún otro proceso pueda parar al que ya está.

Desventajas:

• No se debe permitir a los procesos de usuario utilizar este mecanismo de exclusión mutua, que será utilizado únicamente por procesos del S.O.

• Excluye a todos los procesos del sistema, no sólo a los procesos que poseen las condiciones de competencia.

• Si existe un bloqueo en la sección crítica se para el sistema debido a que se han desactivado las interrupciones.

• Los mecanismos para implementar sincronización y comunicación son de bajo nivel.

• Si tenemos más de un C.P.U. no nos sirve la activación - desactivación de interrupciones porque sólo se realiza esto para un procesador y los demás no se ven afectados. Por tanto falla en sistemas multiprocesadores.

• Instrucción test & set

Cerradura inicialmente tiene asignado el valor falso.

En este caso se dispone de una interrupción llamada TEST & SET que se ejecuta de forma indivisible, realizando la devolución de un valor booleano. Dado un parámetro, se actualiza devolviendo la variable objetivo y asignándole a ésta el valor verdadero.

Mientras TEST & SET sea `1' no se entra en las sección crítica.

Ventajas: soluciona el problema de la exclusión mutua en sistemas multiprocesadores.

Inconvenientes:

• si se bloquea en la sección crítica, se bloquean todos los procesos: interbloqueo.

• Utiliza la espera ocupada * perdemos eficiencia.

Existe otra instrucción llamada TEST & SET BLOCK que a diferencia de la anterior realiza intercambio de variables.

3.- Semáforos.

Un semáforo es un tipo de datos que sólo puede tomar valores enteros positivos, incluido el cero.

Sobre un semáforo sólo se pueden realizar 3 operaciones, las cuales se realizan de forma indivisible y por tanto no existen problemas de interfoliación. Estas operaciones son:

• Inicialización: asignarle un valor entero positivo a un semáforo. Sólo se puede realizar una asignación, lo que se hace al principio de la implementación.

• Señalización: comprueba si hay procesos bloqueados. Si los hubiera, desbloquea uno y en caso contrario incrementa el valor del semáforo.

• Wait: si el valor del semáforo es cero, el proceso se bloquea. En caso contrario se decrementa en 1 el valor del semáforo.

Los semáforos se utilizan para sincronizar y resolver el problema de la exclusión mutua.

Propiedades:

• Los semáforos implementan correctamente el problema de la exclusión mutua para cualquier número de procesos y para cualquier número de procesadores.

• Puede ocurrir inanición a menos que se siga un orden FIFO en la cola de procesos bloqueados.

• Un semáforo que se utiliza para resolver exclusión mutua está sujeto a interbloqueos.

• La comunicación de procesos queda bajo responsabilidad de los programas. Los semáforos sólo hacen su función.

Ejemplo:

Si S = 0 se bloquea el proceso.

Signal (s) * Indica que se ha ejecutado la instrucción anterior.

Tipo de semáforos:

• Generales o contadores: son los vistos hasta el momento. Nos sirven como contadores. (Asignándole a S un valor de 10 tendremos un bucle que se repite 10 veces).

• Binarios: toman valores booleanos, 0 ó 1.

Implementación de semáforos:

Necesitamos de una estructura de datos enteros donde se almacene el número del semáforo y los punteros a los procesos en cada momento.

Para almacenar los procesos bloqueados necesitamos un puntero a la cola de bloqueados y cada semáforo poseerá una cola de bloqueados.

Una vez ejecutado Wait (s) se incorporaría el proceso actual en la cola de bloqueados. Para gestionar dicha cola se utilizará una rutina de tratamiento, con un puntero a la rutina.

Las rutinas de tratamiento pueden ser la siguientes:

• FIFO: facilidad de implementación y manejo de la cola.

• PRIORIDADES: en caso de existir varios procesos con distinta prioridad que compartan información.

• LIFO: no se suele utilizar.

Otra implementación de semáforos trata de conseguir que las operaciones Wait y Signal sean atómicas, esto es, las operaciones sobre semáforos sean indivisibles. Esta atomicidad se puede conseguir de dos maneras:

• Sistemas monoprocesadores: se consigue activando y desactivando las interrupciones.

• Sistemas multiprocesadores: mediante las instrucciones Test & set ó Test & set block si el sistema las permite. En caso contrario utilizaremos algoritmos software con espera ocupada. También se puede conseguir ésta mediante la centralización en un procesador de un planificador que gestiones sus semáforos.

Problemas:

• Productor / consumidor con buffer ilimitado.

Se explicará este problema utilizando un ejemplo que cuenta con dos procesos, uno productor y otro consumidor que cumplen:

• Un proceso, Productor, que continuamente introduce elementos en un buffer BUFF.

• Un procesos, Consumidor, que continuamente saca elementos de un buffer BUFF.

Inicialmente:

• BUFF está vacío.

• i,j := 1

• mutex := 1 (controla el problema del acceso mutuo a BUFF).

• vacío := 0 (controla que el proceso consumidor no intente leer de BUFF cuando está vacío).

Se ha de cumplir las siguientes condiciones para los dos procesos anteriores:

• El proceso consumidor no puede coger datos de BUFF (buffer) si este está vacío. Esto se controla con la variable vacío.

• Ambos procesos comparten datos comunes, presentando el problema de exclusión mutua, esto es, ambos no pueden acceder a la vez a datos compartidos (se soluciona con mutex).

El proceso productor indicará que el buffer se está llenando mediante signal.

El interbloqueo (deadlock) ocurre cuando se ejecutan procesos concurrentes. Es una situación en la cual un conjunto de procesos se quedan bloqueados esperando que ocurra algún suceso que solamente un proceso de dicho conjunto puede provocar. Este interbloqueo se produce por el intento de acceder a datos compartidos.

• Productor / consumidor con buffer limitado.

Suponemos que BUFF es un buffer con capacidad limitada a N elementos (implementado como una lista circular).

Inicialmente:

• BUFF está vacío

• i,j := 1

• mutex := 1

• vacío := 0

• espacio := N (controla que el proceso PRODUCTOR no introduzca más elementos en BUFF si éste no está vacío).

El PRODUCTOR no debe introducir más datos en el buffer si este está lleno, pues se machacarían datos al ser el espacio limitado.

Cuando se produce un elemento hay que comprobar si existe o no espacio para ello.

Hay que tomar precauciones con las operaciones Wait dentro de la sección crítica, pues puede producir un problema de interbloqueo.

Limitaciones de los semáforos:

• Este tipo de semáforos presupone la existencia de una memoria común. No es una solución viable la utilización de semáforos para los sistemas distribuidos (tiempo de comunicación elevados). Por esto se utilizan en sistemas centralizados.

• La comunicación entre procesos concurrentes queda bajo la responsabilidad del programa de aplicación. Esto es, de ello no se encargan los semáforos.

• No asegura la buena utilización de Wait y Signal por lo que se dice que los semáforos son un mecanismo no estructurado.

• La implementación de semáforos produce código difícil de verificar.

4.- Mensajes.

Definición:

Son un mecanismo sencillo en su implementación que resuelve algunas limitaciones de los semáforos. Se utilizan por ello tanto en sistemas centralizados como en sistemas distribuidos.

Se utilizan para resolver problemas como sincronización, comunicación y exclusión mutua.

Otra definición de mensajes: una colección de información intercambiada entre un proceso emisor y un proceso receptor.

Formato:

Cabecera: formato fijo.

Cuerpo: opcional y de longitud variable.

Operaciones:

• Enviar o SEND.

• Recibir o RECEIVE.

Implementación de mensajes:

• Designación del emisor / receptor:

• Directa: cada emisor designa al receptor específico y viceversa. El receptor debe conocer el nombre del que envía el mensaje.

Ventajas: no existen fallos de identificador, de receptor o de emisor.

Desventajas: ha de conocer en todo momento todos sus posibles clientes.

• Indirecta: Los mensajes son enviados y recibidos a través de depósitos especiales llamados buzones. El emisor manda los mensajes a un buzón, que es un lugar que ha sido creado con anterioridad, tomando el receptor los mensajes de dicho buzón.

El propio sistema ha de gestionar a los buzones, proporcionando instrucciones para mejorar estos.

Es necesario disponer de servicios adicionales para el mantenimiento de los buzones:

• Crear_buzón.

• Borrar_buzón.

Con este tipo de mensajes de designación indirecta, la comunicación podrá ser:

• 1 a 1.

• 1 a muchos.

• Muchos a 1.

• Muchos a muchos.

Un buzón es una cola donde se almacenan los mensajes.

• Intercambio síncrono y asíncrono de mensajes

• Síncrono:

La comunicación se realiza sólo cuando ambos procesos, emisor y receptor, están separados.

Sólo puede existir un mensaje pendiente como máximo en cada momento por cada par emisor - receptor.

La operaciones Set y Receive van a ser bloqueantes. Si un proceso realiza una operación enviar y otro proceso una operación recibir sobre el mismo buzón, el primer proceso va a estar esperando hasta que el segundo reciba y viceversa.

Ventajas:

• Fácil implementación.

• Seguridad en la recepción del mensaje.

Inconvenientes: sincronización forzosa.

• Asíncrono:

El proceso emisor no se bloquea, aunque el proceso receptor no esté preparado (no haya ejecutado una operación recibir).

El sistema operativo acepta y almacena temporalmente los mensajes pendientes hasta que se reciban (recargo adicional para el sistema).

Aumenta la concurrencia.

Por un mal uso, un proceso puede agotar la capacidad de almacenamiento intermedio (temporal) del sistema. Como el S.O. no posee espacio de almacenamiento, los procesos quedarían bloqueados.

Problema común: aplazamiento indefinido. Se produce por las siguientes causas:

• Se envía un mensaje y nadie lo recibe. Se bloquea en síncrono.

• Un mensaje nunca se envía. Se bloquea en síncrono y en asíncrono.

Esto se soluciona implementando la operación recibir con otro parámetro, siguiendo la sintaxis:

Recibir (buzón, mensaje, límite de tiempo).

El límite de tiempo es el tiempo que va a esperar el proceso como máximo para recibir un mensaje (proceso receptor). Si el proceso receptor sobrepasa ese límite de tiempo esperando un mensaje que no llega, dicho proceso se desbloquea y manda a su vez un mensaje informando que se ha sobrepasado el límite de tiempo.

PRODUCTOR CONSUMIDOR CON BUFFER LIMITADO: MENSAJES