TEMA 1

INTRODUCCION.

•      Administración de procesos.

•      Concurrencia de procesos.

•      Protección y seguridad informática.

•      Sistemas distribuidos.

•      Sistemas operativos reales.

Proceso.- Es un programa en ejecución. Mientras que el programa es una entidad pasiva, el proceso es una entidad activa. Un proceso es la entidad que puede ser asignada al procesador y ejecutada pro este.

Se pueden conseguir mejoras en el rendimiento si en lugar de ejecutar un programa dentro de otro, introducimos diferentes procesos concurrentes en el procesador (Programación concurrente o multitarea).

La multiprogramación (además de lo anterior supone gestión de memoria y archivos). Fue diseñada para mantener ocupados a la vez al procesador como a los dispositivos de E/S incluidos los dispositivos de almacenamiento de modo que se alcance el máximo rendimiento.

La clave de este mecanismo es que, como respuesta a las señales que indiquen que ha terminado una operación de E/S el procesador cambie entre los diversos procesos en memoria.

El SO es el encargado de suministrar el software que ayude al hardware a la gestión de procesos :

•       Creación / Eliminación.

•       Control de avance y retroceso.

•       Interrupciones.

•       Gestión de errores.

•       Asignación de recursos hardware.

•       Proveer de método de comunicación entre diferentes procesos (mensajes u señales).

Un procesos, es un conjunto de ráfagas de CPU y E/S teniendo siempre en cuenta que la primera y la última ráfaga van a ser siempre de CPU.

•       Desde el punto de vista del usuario .- Un proceso es un conj. De operaciones e instrucciones especificas destinadas a obtener un resultado a partir de una entrada de datos.

•       Desde el punto de vista del operador del sistema.- Se trata de informar al SO del conj. De las actividades que deben ser planificadas para conseguir ejecución concurrente.

Residir en memoria.

Atributos à Recursos que necesita, Ficheros, Prioridades.

El que un mismo proceso pueda dividirse en tareas independientes requiere, código complejo, introducción de señales. El programador de sistema tendrá que tener todo esto en cuenta a la hora de diseño.

•       Desde el punto de vista del SO .- Es la entidad mínima individualmente planificable. Va a constar de código y datos y se caracteriza por sus atributos y su estado dinámico.

n     Un proceso puede a su vez estar formado por varias tareas o hilos que pueden ejecutarse en modo concurrente. La unidad mínima ejecutable es la tarea o hilo.

Diferencias entre proceso e Hilo :

•       Los procesos tienen asignados diferentes secciones de memoria mientras que os hilos no.

•       A los procesos se les asigna recursos mientras que los hilos disponen de los recursos asignados al proceso.

•       A la hora de planificar si se pueden planificar los hilos de un mismo proceso.

Un proceso a lo largo de su vida en el sistema va a pasar por varios estados :

n     Nuevo

n     Listo.- Estructuras de datos.

n     Ejecución.- CPU.

n     Bloqueo.- Espera de E/S o Evento.

n     Suspendido.- Suspender proceso por requerimientos del sistema.

•       La concurrencia supone , que a un proceso al se le asigna CPU sale de ejecución y se le asigna la CPU a otro proceso, este proceso en espera puede estar esperando evento o en cola de espera.

•       Esto supone que los procesos entren y salgan de la CPU sin finalizar su ejecución. Por tanto, debe de haber algo donde se guarda la información del proceso y que informe del estado del nuevo proceso.

•       Toda la información relativa a estos se guarda en el BCP. Que consiste en una serie de posiciones contiguas de memoria donde se guarda el identificador del proceso, puntero a la siguiente instrucción, ficheros abiertos, recursos asignados, lista de recursos solicitados, prioridades, etc.

•       En el momento de creación del proceso hay que crear un bloque de control de procesos y hay que ver cual es el sistema de gestión de memoria del sistema.

Si la memoria se gestiona estática se reserva un espacio para contener TBCP (numero de procesos limitados al numero de bloques de la tabla).

Gestión dimanica.- Donde no existe limitación de procesos.

Cuando un proceso comienza a ejecutarse vuelca el contenido del BCP en los registros de la CPU y cuando sale de CPU se realiza la operación contraria (Cambio de contexto) Para que el rendimiento de un sistema con multiproceso sea optimo el tiempo empleado en el Cambio de contexto tiene que ser despreciable frente al tiempo de CPU.

n     Los procesos van a provenir de 3 sistemas.-

•       Procesos por lotes.

•       Tiempo compartido.- Se asigna tiempo (cuanto) a cada proceso. Si todos los procesos tienen la misma prioridad el cuanto es el mismo, pero los procesos de mayor prioridad tiene un cuanto mayor. Procesos en Background .- Se ejecutan en tiempos de CPU libre, estos no entran en competición por cuantos de tiempo sino que van a la cola de Background.

•       Tiempo real.- Precisan tiempo de respuesta del orden de mili o microseg., que desalojan el proceso que esta en CPU.

n     En estos tipos de procesos hay que tener en cuenta 4 principales causas de error :

•       Sincronización incorrecta.- Mal diseño del mecanismo de señales. Puede dar lugar a perdida de señales o recuperación duplicada de estas

•       Fases de exclusión múltiple.- Un proceso puede dividirse en hilos, procesos de código independiente, esto es inviable, porque hay secciones de código criticas que hace volver al proceso a la ejecución secuencial, solo un proceso de los que esta operando puede seguir ejecutando y a los mecanismos empleados para que esa ejecución no sea concurrente se los llama mecanismos de exclusión mutua. Es habitual el caso en que dos usuarios o dos procesos intenten acceder a la vez a un recurso compartido. Si no se controlan estos casos puede producirse un error. Debe existir un mecanismo que permita que solo un proceso pueda realizar una transacción sobre una zona de datos.

•       Funcionamiento no determinista del programa.- Los resultados del programa debe depender solo de las entradas de ese programa y no de otros procesos en ejecución paralela, por ello no se deja acceder a memoria asignada a otro proceso y se da la canalización de datos de entrada.

•       Interbloqueo.- Es posible que dos o más procesos estén suspendidos uno a la espera del otro. Cada uno está deseando que el otro libere un recurso deseado. La única forma de resolver interbloqueo es suspender uno de los procesos para liberar los recursos y que el resto pueda finalizar y así el proceso suspendido pueda terminar también.

n    Protección y seguridad de la información. (Publicación de la oficina de Estandares).

El crecimiento de la utilización de sistemas en tiempo compartido y de redes de computadoras ha traído consigo un aumento por la preocupación por la protección de la inforamción

1)    Intentos organizados y deliberados de obtener información de las organizaciones del sector privado.

2)    Intentos organizados y deliberados de obtener información de las oficinas del gobierno.

3)    Adquisición inadvertida de información económica y mercantil.

4)    Adquisición inadvertida de información sobre personas.

5)    Intromisión del gobierno en los Derechos Individuales.

6)    Intrusión en Bases de Datos. (En la adquisición de datos financieros, económicos, y personales.)

7)    Atropello de derechos individuales por la comunidad de información.

•       Pueden construirse algunas herramientas de propósito general dentro de las computadoras y de los SO para dar soporte a varios mecanismos de protección y seguridad.

•       En general, interesan las problemas de control de acceso a las sistemas informaticos y a la información almacenada en ellos.

•       Se han definido cuatro clases de políticas generales de protección:

1)    No compartición.- Los procesos están completamente aislados unos de otros y cada proceso tiene control exclusivo sobre recursos que le fueron asignados. Los procesos suelen compartir programas o archivos de datos haciendo copias y pasandolas a su propia memoria virtual.

2)    Compartiendo originales de programas o archivos de datos.- Con el uso de una unica copia reentrante, una unica copia fisica de un programa puede aparecer en varios espacios de memoria virtual, como archivos de solo lectura. Se requieren mecanismos especiales de bloqueo para compartir archivos de datos en los que se puede escribir y evitar que usuarios simultaneos interfieran unos con otros.

3)    Subsistemas confinados o sin memoria.- En este caso los procesos se agrupan en subsistemas para cumplir una politica de protección en particular. Por ejemplo, un proceso ‘cliente' llama a un proceso ‘servidor' para llevar a cabo cierta tarea con datos. El servidor se protegerá de que el cliente no descubra el algoritmo con el cual realiza su trabajo y el cliente se protegerá de que el servidor no descubra que tipo de trabajo esta realizando.

4)    Diseminación controlada de información .- A los usuarios y a las aplicaciones se les de credenciales de seguridad en un cierto nivel, mientras que a los datos y recursos se les dota de clasificaciones de seguridad. La politica se seguridad hace cumplir las restricciones relativas a que usuarios tiene acceso a que clasificaciones.

•       Gran parte del trabajo realizado en cuanto a protección y seguridad se puede organizar en 3 categorías :

n     Control de acceso (En cuanto al acceso a la información).- Regulación de acceso al usuario al sistema completo, a los subsistemas y a los datos, así como regular el acceso a recursos del sistema.

n     Control del flujo de información, regulando flujo de información que se suministra al usuario.

n     Certificación.- Demostración de que los mecanismos de seguridad funcionan. Demostración de que el acceso y los mecanismos de control se llevan a cabo de acuerdo a las especificaciones y a que estas cumplen las políticas de protección y seguridad deseadas.

Capas del Sistema Operativo (Clasificación genérica págs 73-75). .-

Capa 13	SHELL
Capa 12	Procesos de usuarios.
Capa 11	Directorio
Capa 10	Dispositivos
Capa 9	Sistemas de archivos.
Capa 8	Comunicaciones
Capa 7	Memoria virtual.
Capa 6	Almacenamiento secundario.
Capa 5	Procesos primitivos
Capa 4	Interrupciones
Capa 3	Procedimientos
Capa 2	Conjunto de instrucciones
Capa 1	Circuitos electrónicos

•       Capa 1.- Circuitos electrónicos. Objetos tratados son registros, celdas de memoria, puertas lógicas.

•       Capa 2.- Conjunto de instrucciones del procesador. Las operaciones de este nivel son las permitidas por el conjunto de instrucciones del lenguaje máquina.

•       Capa 3.- Añade concepto de procedimiento o subrurina. Operaciones de llamada y retorno.

•       Capa 4.- Introduce interrupciones, las cuales hacen que procesador salve el contexto actual e invoque rutina de tratamiento de interrupción.

--- Las cuatros primeras capas anteriormente citadas no pertenecen al SO sino al hardware de la máquina. ---

•       Capa 5.- Se introduce noción de proceso como programa en ejecución. Entre requisitos fundamentales de un SO que ofrezca soporte para varios procesos incluye capacidad de suspender y reanudar un proceso (Exige guardar cambios de contexto à Capa 4). Si un proceso necesita cooperación será necesario un sistema de sincronización. (Técnica sencilla à Semáforo).

•       Capa 6.- Dispositivos de almacenamiento secundario del ordenador. Se incluyen procesos para la planificación de estos dispositivos.

•       Capa 7.- Crea un espacio de direcciones lógicas para procesos. Organiza el espacio de direcciones virtuales en bloques que se pueden mover entre memoria principal y secundaris.

3 esquemas.-

•       Paginación de longitud fija.

•       Segmentación de longitud variable.

•       Las dos anteriores.

•       Capa 8.- comunicación de información y mensajes entre procesos (Nivel 5 proporciona mecanismos de señalización). Una de las herramientas más potentes à Tubo à Canal lógico para flujo de datos entre procesos.

•       Capa 9.- Da soporte a almacenamiento a largo plazo de archivos con nombre. Los datos de almacenamiento secundario se contemplan en terminos de entidades abstractas de longitud variable en contraste con el enfoque a hardware del Nivel 6.

•       Capa 10.- Acceso a dispositivos externos.

•       Capa 11.- Mantienen asociación entre identificadores externos de recursos y objetos del sistema Estos se mantiene en un directorio. Las entradas no incluyen solo lo anterior sino también otras características.

•       Capa 12.- Servicio completo de soporte a proceso. Se da soporte para la gestión ordenada de toda la información asociada a la gestión de proceso. Esto incluye, espacio de direcciones virtuales, lista de objetos y procesos con los que puede interactuar y sus rectricciones, los parametros pasados al proceso.

•       Capa 13.- Interface de usuario con sistema operativo.

Sistemas Operativos Reales.-

•       WINDOWS NT à Sistema monousuario multitarea diseñado para trabajar con PC y Estaciones de trabajo. Incorpora los últimos adelantos.

•       UNIX à Sistema operativo multiusuario dirigido a todo tipo de computadoras. Siempre en grandes redes. Compatibilidad absoluta.

•       OS/2 à Sistemas de oficinas.

TEMA 2.

ADMINISTRACION DEL PROCESADOR. PLANIFICACION DE MULTIPROCESADORES.

Los requisitos principales que debe satisfacer un SO estan expresados haciendo referencia a los procesos :

•       Un SO debe intercalar la ejecución de un conjunto de procesos para maximizar la utilización del procesador ofreciendo a la vez un tiempo de respuesta razonable.

•       El SO debe asignar los recursos a los procesos en conformidad con una politica especifica, evitando al mismo tiempo el interbloqueo.

•       El SO podría tener que dar soporte a la comunicación entre procesos y la creación de procesos por parte del usuario, etc.

- Descripción y control de procesos.

Para poder diseñar el SO de una forma efectiva, se necesitra tener un modelo claro de comportamiento de un proceso.

El modelo más sencillo que puede construirse tiene en cuenta que un proceso puede estar ejecutandose en el procesador o no.

Un proceso puede estar en ejecución o en espera.

El proceso entra, y esta en un estado de no ejecución hasta que es seleccionado por administrador.

El administrador del sistema operativo, seleciona un proceso para que se ejecute. El proceso que estaba ejecutandose pasa del estado de ejecución al estado de Espera y uno de los demás procesos pasará al estado de Ejecución.

Del estado de EJECUCION puede pasar a PAUSA o TERMINAR.

Incluso en este modelo tan simple se aprecia la necesidad de utilizar una serie de estructuras de datos para almacenar el estado actual de cada proceso.

Aquellos procesos que no estan ejecutandose tiene que guardarse en algun tipo de cola, para que esperen su turno.

La cola consiste en una lista enlazada de bloques de datos en la que cada bloque representa un proceso.

El comportamiento del distribuidor se podrá describir como diagrama de colas.Cuando un proceso se crea hay que construir una estructuras de datos para administrar ese proceso y se le asigna unas posiciones de memoria.

Creación y Terminación de procesos.

Independientemente del modelo utilizado para su gestión los procesos tiene su vida limitada por el momento de creación y terminación.

•       Creación à Cuando se añade un proceso, hay que construir las estructuras de datos que se utilizan para administrar el procesoy asignar el espacio de direcciones que va a utilizar dicho proceso.

Hay diferentes razones por las que se puede crear un proceso.

•       Nueva tarea en proceso por lotes.- Un proceso se crea como respuesta a la emisión de un trabajo.

•       Nueva conexión iterativa.- Se crea un proceso cuando un nuevo usuario intenta conectarse.

•       Proceso del SO para dar un servicio. - El SO crea un proceso como parte de una aplicación ( Teras una solicitud de impresión el SO crea una proceso para gestiones solicitud).

•       Generado por otro proceso ya existente.- Tradicionalmente todos los procesos eran creados por el SO de una forma transparente para el usuario o para el programa de aplicación. Sin embargo, puede ser util permitir que un proceso pueda originar la creación de un proceso. El nuevo proceso se ejecutará de forma paralela con la aplicación .

Cuando un proceso es creado por el SO bajo la solicitud de otro proceso, este mecanismo se conoce como Generación de procesos. Donde el generador se conoce como proceso Padre y el proceso generado es el proceso Hijo.

•       Terminación à En cualquier sistema informatico, debe existir alguna forma de que un proceso pueda indicar que ha terminado.

En un proceso por lotes debe indicar al final la instrucción HALT (Terminación) y en un entorno iterativo debe ser el usuario quien de la orden de terminación, etc.

Razones para la terminación de un proceso :

•       Normal .- El proceso ejecuta llamada al servicio del SO que notifica su terminación normal.

•       Por tiempo excedido.- Una tarea tiene asignada la CPU ejecuta el tiempo máximo y le es requisada la CPU y pasa a la cola para competir por la nueva asignación.

•       Violación de limites.- Proceso trata de acceder a una posición de memoria que no le esta permitida acceder.

•       No memoria disponible.- El proceso necesita más memoria de la que el sistema puede proporcionar.

•       Error de protección.- El proceso intenta utilizar un recurso o archivo que no le esta permitido utilizar, o trat de utilizarlo de forma incorrecta.

 

•       Error aritmético.- Si el proceso intenta hacer un calculo prohibido, como la división por cero, o trata de acceder a un número mayor del que el hardware acepta.

•       Tiempo máximo de espera de recurso.- El proceso ha esperado más alla del tiempo máximo especificado para que se produzca cierto suceso.

•       Fallo de dispositivo de E/S.- Se produce un error en una operación de E/S

•       Instrucción no valida.- El proceso intenta ejecutar una instrucción inexistente ( a menudo como ressultado de un salto para ejecutar datos en la zona de datos)

•       Intento de acceso a una instrucción privilegiada.- El proceso intenta utilizar una instrucción reservada para el SO.

•       Finalización del padre.- Cuando un proceso padre finaliza, el SO puede diseñarse para teminar automaticamente con todos sus descendientes.

•       Mal uso de los datos .- Un elemento de dato, no esta inicializado o es de un tipo equivocado.

•       Intervención del operador o del SO.- Por alguna razon el operador o el SO termina con un proceso (ej : Interbloqueo).

•       Solicitud del padre.- Un proceso padre tiene normalmente autoridad para terminar con cualquiera de sus hijos.

Estados de un proceso.

Algunos procesos en el estado ejecución estan listos para ejecutar, mientras que otros están bloqueados, esperando a que termine una operación de E/S . (Por lo que el modelo de dos estados no sirve).

Asi pues utilizando una cola sencilla el distribuido busca el proceso más antiguo de la cola y que no este bloqueado

Una forma mñas natural de afrontar esta situación es dividir el estado de No ejecución en dos : Lista y Bloqueado. Pro tanto los 5 estados de este nuevo modelo son :

•       Ejecución à El que esta actualmente en ejecución.

•       Listo à Preparado para ejecutar en cuanto se le de la oportunidad.

•       Bloqueados à No puede ejecutar hasta que se produzca un cierto suceso. ( Terminación de una operación de E/S)

•       Nuevo à Proceso que se acaba de crear pero que todavia no ha sido admitido por el SO en el grupo de procesos ejecutables.

•       Terminado à Un proceso que ha sido excluido por el SO del grupo de procesos ejecutables.

Los estados Nuevo y Terminado son construcciones muy utiles para la gestión de procesos

•       El estado de Nuevo corresponde a los procesos que acaban de ser definidos.

El SO define un proceso nuevo en dos pasos :

¨     Primero, lleva a cabo tareas de gestión intera.

¨     Se le asocia un identificador al proceso y se construyen y asignan algunas tablas necesarias para gestionar el proceso. (En este punto el proceso llega al estado de nuevo. El SO operativo ha llevado a cabo las operaciones necesarias para crear proceso pero no se ha comprometido a su ejecución).

•       Un proceso sale del SO en dos pasos :

¨     El proceso llega al punto normal de terminación de un proceso, cuando se abandona debido a un error irrecuperable o cuando otro proceso hace que este abandone. La terminación pasa el proceso al estado de Terminado. (En este punto, el SO ya no eligira más este proceso para ejecutar aunque conserva las tablas asociadas al proceso durante un tiempo para la posible utilización de la información pro otros procesos)

¨     Finalmente el SO ya no necesita mantener los datos relativos al proceso y estos se borran del sistema.

¨     Estos cinco estados descritos anteriormente dan lugar a una serie de combinaciones :

•       Nulo à Nuevo : Se crea un nuevo proceso.

•       Nuevo à Listo se supone que el sistema esta preparado para aceptar un proceso más (Hay memoria disponible) Cambio de estado Admitir.

•       Listo à Ejecución (Ejecución). - Cuando es hora de seleccionar un nuevo proceso para ejecutar, el Sistema operativo elige uno de los procesos en estos de Listo.

•       Ejecución à Terminación ( Liberar). (Liberar CPU).El proceso que se esta ejecutando es finalizado por el SO si este indica que ha terminado o si se abandona el proceso.

•       Ejecución à Listo (Fin de plazo o Tiempo excedido). - El proceso que esta en ejecución ha alcanzado el tiempo maximo permitido de ejecución ininterrumpida. Existen otros dos casos :

•       Por establecimiento de prioridades .- Entra en el sistema un proceso con prioridad mayor que el que se está ejecutando. (Estado de Suspensión).

•       El proceso cede voluntariamente el control del procesador.

•       Ejecución à bloqueado (Bloqueo) à Espera de asignación de recurso y cuando evento se produce pasa a la cola de espera de Listos.

•       Bloqueado à Listo .- Un proceso en estado de bloqueado pasará al estado de Listo cuando se produzca el evento que estaba esperando.

•       Bloqueado à Terminado .

¨     Debido a que un proceso puede ser suspendido (Debido a requerimientos del sistema O por prioridades ). (Ha sido expulsado de la memoria principal). Se generan nuevos estados :

•       Listo à Proceso esta en memoria principal preparado para ejecutar.

•       Bloqueado à Esta en meoria principal a la espera de un rpoceso.

•       Bloqueado y suspendido à Esta en memoria secundaria esperando un suceso.

•       Listo y Suspendido à El proceso esta en memoria secundaria pero esta disponible para ejecutar tan pronto como se cargue en memoria principal.

¨     Va a observarse ahora el modelo de estados desarollado :

•        Bloqueado à Bloqueado y Suspendido.- Si no hay procesos listos al menos un proceso bloqueado se suspende para dar cabida a otro que no este bloqueado.

•       Bloqueado y Suspendido à Listo y Suspendido.- Un proceso bloqueado y suspendido pasa al estado de Listo y suspendido cuando ocurre el suceso que estaba esperando.

•       Listo y Suspendido à Listo .- No hay procesos Listos en la memoria principal, el sistema Operativo tendrá que traer uno para continuar con la ejecución. (Puede darse el caso de que el proceso Listo y Suspendido tiene mayor prioridad que el proceso que esta en la cola de Listos ).

•       Listo à Listo y Suspendido .- el Sistema Operativo prefiere suspender un proceso bloqueado que uno Listo, ya que el proceso Listo podría ejecutarse de inmediato, mientras que el proceso bloqueado esta ocupando espacio en memoria principal. Puede ser necesario suspender un proceso Listo si esta es la única manera de liberar un bloque de memoria lo suficientemente grande.

¨     Otras transacciones :

•       Nuevo - Listo, Suspendido y Nuevo à Listo .- cuando se crea un nuevo proceso, se le puede añadir a la cola de Listos o a la cola de Listos y Suspendidos.

•       Bloqueado y Suspendido à Bloqueado .- Un proceso termina de ejecutar y deja un espacio en memoria principal. Hay un proceso Suspendido y Bloqueado que tiene una prioridad mayor que cualquiera de la cola de Listos y Suspendidos.

•       Ejecución à Listo y Suspendido .- Un proceso en ejecución pasa al estado de Listo cuando expira su cuanto de tiempo asignado. Sin embargo si se esta liberando un proceso de la cola de Bloqueados y suspendidos puede que el SO pase el proceso directamente a la cola de Listos Suspendidos liberando así una porción de memoria principal.

•       Varios à Terminado .- Terminación ( en algunos SO) por causas ajenas al proceso.

n     Otros usos de la suspensión.-

Se define proceso suspendido como aquel que tiene las características siguientes :

¨     No está disponible de inmediato para su ejecución.

¨     El proceso puede estar esperando o no un suceso. Si lo está, la condición de Bloqueado es independiente de la condición de Suspendido y el acontecimiento del suceso bloqueando no lo habilita para la ejecución.

¨     El proceso fue situado en el estado de suspendido por un agente con el fin de impedir su ejecución.

¨     El proceso no puede apartarse de este estado hasta que el agente loordene explicitamente.

•       Razones para la suspensión de un proceso :

•       Intercambio .- Liberar memoria principal para otro proceso que está listo para ejecutarse.

•       Suspensión por parte del sistema operativo por sospechar que el proceso es causante de problema

•       Solicitud del usuario.- Un usuario puede querer suspender la ejecución de un programa con fines de depuración o en conexión con el uso de un recurso.

•       Por tiempo (Procesos que se ejecutan a intervalos).- Puede ser suspendido mientras espera el siguiente intervalo de tiempo.

•       Solicitud del proceso padre (Puede solicitar suspensión del hijo).- Un proceso padre puede suspender la ejecución de un hijo para examinar o modificar el proceso suspendido o para coordinar la actividad de varios descendientes.

Estructuras de Control del Sistema Operativo.

El SO tiene que disponer de información sobre cada proceso o recurso.

Para ello construye unas tablas con información sobre cada entidad de las que administra. (Memoria, Dispositivos, ficheros, recursos y procesos).

Tablas de memoria.

De E/S

De archivos.

De Proceso.

¨     Las Tablas de memoria se encargan de la gestión de la memoria principal y virtual . Parte de la memoria principal esta reservada para el uso del SO y el resto esta disponible para el uso de los procesos. Los procesos se mantienen en memoria secundaria mediante alguna forma de memoria virtual o por un simple mecanismo de intercambio. Las tablas de memoria deben incluir la información siguiente :

•       La asignación de memoria principal a los procesos.

•       La asignación de memoria secundaria a los procesos.

•       Cualesquiera atributos de protección de segmentos de memoria principal o virtual, tales como que procesos pueden acceder a que zonas de memoria compartidas.

•       Cualquier información secundaria para la gestión de memoria virtual.

¨     Las Tablas de E/S son utilizadas por el sistema operativo para administrar los dispositivos y los canales de E/S del sistema informatico. En un momento dado, un dispositivo de E/S puede estar disponible o estar asignado a un proceso en particular. El SO necesita conocer el estado de la operación de E/S y la posición de memoria principal que se esta utilizando como origen o destino de la transferencia de E/S.

¨     Las Tablas de Archivos ofrecen información sobre la existencia de archivos, su posición en la memoria secundaria, su estado actual y otros atributos.

¨     Las Tablas de proceso que el SO debe mantener para administrarlos.

•       Datos de usuario.- Parte modificable del espacio de usuario. Puede guardar datos del programa, una zona para una pila de usuario y programas que pueden modificarse.

•       Programas de usuario.- El programa a ejecutar.

•       Pila del sistema.- Cada procesos tiene una o más pilas asociadas a él. Una pila se utiliza para almacenar los parametros y las direcciones de retorno.

•       BCP.- Información necesaria para que el SO controle el proceso.

Cambio de contexto

Para cambiar la CPU de un proceso a otro se reuiere guardar el estado anterior y cargar el estado nuevo para el proceso (Cambio de contexto).

El tiempo de cambio de contexto es un gasto más y depende de la máquina.

Los tiempos de cambio de contexto dependen en gran medida del apoyo del hardware.

•       En procesadores que ofrecen varios conjuntos de registros, un cambio de contexto implica cambiar el apuntador el conjunto actual de registros.

•       Si hay más procesos activos que registros, el cambio de contexto se realiza utilizando la memoria.

•       Cuanto más complejo es el SO, más trabajo se realiza en un cambio de contexto.

Bloque de control de Procesos (BCP) 

Bloque o registro de datos que contiene diversa información relacionada con un proceso concreto.

•       Estado del proceso .- En el estado en que se encuentra el proceso (Nuevo, Listo, Espera ...)

•       Contador de programa.- Contador indica la dirección de la siguiente instrucción a ejecutar.

•       Reg. De la CPU .- Varian en número y tipo según la arquitectura del computador. Información que debe guardarse junto con el contador de programa cuando ocurre una interrupción.

•       Información de planificación de la CPU .- Incluye una prioridad de proceso, apuntadores a colas de planificación y otros parametros de planificación.

•       Información de administración de memoria .- Incluye registros limites o tablas de paginas.

•       Información contable .- Cantidad de tiempo real y de la CPU utilizado, limites de tiempo, números de cuenta, nºde proceso...

•       Información del estado de E/S .- La información incluye solicitudes de E/S pendientes, dispositivos de E/S asignados, etc.

Hilo.

Un ‘Hilo' es una unidad básica de utilización de la CPU y tiene poco estado compartido. Un grupo de hilos semejantes comparten código, espacio de direcciones y recursos del SO.

El entorno el el cual se ejecuta un hilo se llama ‘Tarea' .

Un proceso tradicional equivale a una tarea con un solo hilo. Una tarea no hace nada si no tiene hilos.

Un hilo posee un registro de estados y generalmente su propia pila.

•       El coste de comunicación de la CPU entre hilos del mismo grupo y de la creación de hilos es el mismo que el de procesos pesados. De esta forma, una solución razonable para el problema de como un servidor puede manejar eficientemente solicitudes es bloquear un hilo y pasar a otro.

•       Existen varias alternativas a la implementación de hilos :

•       Los hilos pueden ser apoyados por el nucleo à Se proporcionan un conjunto de llamadas al sistema similares a las de los procesos.

•       Pueden apoyarse por encima del nucleo, a traves de bibliotecas de usuario.

Tipos de planificación.

La planificación del microprocesador consiste en asignar los procesos de forma que se cumplan determinados objetivos à El tiempo de respuesta sea mínimo, productividad máxima (Rendimiento optimo del sistema).

 En el transcurso de su vida, un proceso transita por las diferente colas del SO y es este quien debe seleccionar los procesos que entran en esas colas. (Tarea realizada por el planificador.)

¨     Planificador a Largo Plazo .- Selecciona procesos de un deposito y las carga en memoria para su ejecución. (Planificador de procesos.)

¨     Planificador a Corto Plazo .- selecciona uno de los procesos Listos para ejecución y le asigna la CPU.(Planificador de la Cola de Nuevos).

La principal diferencia entre los planificadores es su frecuencia de ejecución :

El planificador a corto plazo debe seleccionar con mucha frecuencia un nuevo proceso (Como minimo una vez cada 10 miliseg).

El planificador a largo plazo se ejecuta con una frecuencia menor (Pueden transcurrir minutos entre la creación de procesos).

•       Si el grado de multiprogramación es estable la tasa de creación debe ser igual a la tasa de salida de procesos del sistema.

•       En algunos sistemas es posible que no exista planificador a largo plazo o que su función sea minima.

Algunos sistemas como los de tiempo compartido deberian presentar un nivel intermedio de planificación o Planificador a Medio Plazo .- Puede ser a veces ventajoso eliminar un proceso de la memoria y de ese modo reducir el grado de multiprogramación. (Colas de suspensión)

A este esquema se le conoce como Swaping, y el planificador a medio plazo se encarga del intercambio de procesos, sacandolo de la memoria y volviendolo a introducir más tarde (Pueden ser necesarios para mejorar la mezcla de procesos o para liberar memoria

Existen tambien otros planificadores :

•       Planificador de E/S.- Gestiona las diferentes colas de bloqueo. (Colas de Dispositivo).

Planificación de la CPU.

¨     Ciclo de rafagas de CPU y E/S à  La ejecución de un proceso consiste en un ciclo de ejecución de CPU y espera de E/S. La ejecución de un procesos comienza con una rafaga de CPU, a esta el siguen rafagas de CPU y E/S. La última rafaga de CPU, terminará con solicitud al sistema de terminación ejecución.

•       Un programa limitado por E/S tendrá muchas rafagas de CPU breves.

•       Un programa limitado por la CPU tendra pocas rafagas de CPU muy largas.

¨     Planificador de CPU à El proceso de selección de procesos se realiza por el planificador a corto plazo. La cola de listos, tendra diferentes implementaciones, conceptualmente se encuentran en fila esperando una oportunidad para ejecutarse.

¨     Colas de planificación à Conforme los procesos entran en el sistema se colocan en la colas de procesos (Residen en almacenamiento secundario). Los procesos que residen en memoria proncipal se colocan en la cola de procesos listos. (Cada PCB tiene un apuntador que indica cul es el siguiente proceso en la cola de listos).

Existen otras colas en el sistema :

•       La lista de procesos que esperan a un dispositivo de E/S se colocan en la Cola de dispositivo :

•       Si se trata de un dispositivo dedicado nunca tendrá más de un procesos en la cola.

•       Si por el contrario es un dispositivo compartido, en la cola podrá haber varios procesos.

Diagrama de colas.- Un proceso nuevo se coloca inicialmente en un cola de procesos Listos y allí espera hasta que es entregada a la CPU, una vez asignado pueden ocurrir unos de estos sucesos :

•       Proceso puede emitir solicitud de E/S y colocarse en la cola de dispositivo.

•       Procesos puede crear nuevo procesos y esperar a que este termine.

•       Ser extraido de la CPU por la fuerza.

Algoritmos de Planificación

•       La planificación se hace teniendo en cuenta determinados criterios :

•       Tiempo de respuesta.- En un sistema interactivo puede que el mejor criterio no sea el tiempo de retorno , por eso se utiliza esta otra medida : Tiempo que transcurre desde que se emite solicitud hasta que se recibe la primera respuesta respuesta.

•       Tiempo de retorno.- Desde el punto de vista de un unico proceso el criterio más improtante es el tiempo que tarda en ejecutarse. El intervalo de tiempo entrada de un proceso en el sistema hasta su finalización.

•       Plazos.- Si se especifica un plazo de terminación de un proceso la planificación debe planificar otras metas a la maximización de plazos cumplidos.

•       Previsibilidad.- Una tarea que se ejecute reiteradamente se deberá ejecutar en el mismo tiempo y con el mismo coste.

•       Productividad.- Nº de procesos finalizados por unidad de tiempo.

•       Utilización de procesador.- Porcentaje de tiempo que procesador esta ocupado.

•       Equidad.- Todos los procesos deben ser tratados de igual forma impidiendo inanición de un proceso.

•       Prioridades.- Se debe favorecer a los procesos con mayor prioridad.

•       Recursos equilibrados.- Se deben mantener todos los recursos del sistema ocupados.

•       Tiempo de espera.- Total de tiempo que un proceso espera por su ejecución completa. Se obtiene sumando los tiempos de espera de todas las ráfagas con el tiempo de espera de la primera ráfaga.

Otras políticas de planificación.

Hay sistemas cuya política de planificación se basa en prioridades :

n     Estáticas.- Se mantiene en ejecución.

n     Dinámicas.- Varían en ejecución.

El resto de políticas apropiativas / No apropiativas.-

•       No apropiativasà Una vez que el proceso obtiene CPU no le puede ser requisada hasta que acaba la ráfaga.

•       Apropiativas à Permiten que un proceso con mayor prioridad requise de CPU al proceso que la tenis asignada sin finalizar la ejecución.

Diferentes algoritmos de planificación.

•       FCFS

•       RR

•       SJF / SPN

•       SJF apropiativo o SRT

•       Colas multinivel

•       Colas multinivel realimentadas.

•       HRRN

A)    FCFS .- El proceso que primero solicita la CPU es el primero al que se le asigna. Esta politica se implementa facilmente utilizando un cola FIFO.

Cuando un proceso entram el PCB apunta al último proceso en la cola FIFO. Cuando la CPU esta libre se asigna al proceso que esta situado el primero en la cola. En la politica FCFSm el tiempo promedio de espera es bastante largo.

•       El algoritmo FCFS es no apropiativo, una vez que se ha asignado la CPU a un proceso, este la conserva hasta que desee liberarla ya sea por terminación o por E/S

•       Especialmente problemática.

PROCESOS	I LLEGADA	T SERVICIO	I COMIENZO	FINAL	T RET	Tq/Ts
A	0	1	0	1	1	1
B	1	100	1	101	100	1
C	2	1	101	102	100	100
D	3	100	102	202	199	1.99

Tm = 201+199 /4 = 100

B)  SJF (Tiempo restante más corto) à Este algoritmo asocia a cada proceso la longitud de su siguiente rafaga de CPU. Cuando la CPU esta disponible es asignada al proceso que tiene la siguiente rafaga de CPU menor. Si dos procesos tiene la misma longitud para la siguiente rafaga de CPU se utiliza la planificación FCFS para romper el emparte.

Puede comprobarse que el algoritmo SJF es óptimo, ya que ofrece el menor tiempo promedio para un conjunto de procesos dados.

El problema principal del algoritmo es el conocimiento de la longitud de la siguiente rafaga de CPU por tanto no puede implantarse a nivel de la planificación de la CPU, aunque se utilizan aproximaciones.

Aunque no se conocen los valores de las siguientes rafagas de la CPU podemos predecir su valor esperando que sea más o menos del mismo tamaño que las anteriores ( Por ello se elige el proceso con rafaga previa de CPU más breve)

El algoritmo SJF puede ser apropiativo(SRT) o no aporpiativo. La alternativa se plantea cuando cuando un nuevo proceso llega a la cola de procesos listos mientras se esta ejecutando otro proceso. El nuevo proceso ùede tener una rafaga de CPU menor que lo que resta del proceso que se jecuta en ese momento.

Un algorotmo SJF apropiativo desplazará al proceso que se ejecuta.

La politica SJF apropiativa es más comunmente conocida como SRT.

PROCESOS	I LLEGADA	T SERVICIO	I COMIENZO	FINAL	T RET	Tq/Ts
A	0	1		1	1
B	1	100		102	101
C	2	1		3	1
D	3	100		202	199

Tm = 302 / 4 =75 aprox.

TAREAS	T ENTRADA	CPU	PRIORIDAD
P1	0	5	1
P2	0	2	0
P3	1	4	2
P4	2	3	1
P5	3	10	2
P6	20	4	1
P7	25	20	2
P8	30	2	0
P9	31	6	2
P10	60	1	0

SJF

SRT

Tr (SJF) = (2+14+8+3+31+8+23+20+25+1) / 10 = 12.5 ms.

Tr /SRT) = (2+14+8+3+21+8+31+2+7+1) / 10 = 9.7 ms.

ROUND ROBIN (Algoritmo de planificación circular) .- Diseñado especialmente para sistemas en tiempo compartido. Se define una pequeña cantidad de tiempo o cuanto de tiempo, que generalmente varía entre los 10 y 100 milisegundos. La cola de procesos Listos se trata como una cola circular, el planificador de CPU la recorre asignando a cada proceso un cuanto de tiempo.

Se mantiene la cola de Listos en una cola FIFO. Los nuevos procesos se agregan al final de la cola. El planificador toma el primer proceso de la cola de Listos y programa el cronometro para que provoque una interrupción y despacha el proceso.

Pueden suceder una de estas dos cosas :

•       El proceso tenga una rafaga de CPU menor que el cuanto , el proceso se libera voluntariamente.

•       Si la rafaga es más grande que el cuanto el cronometro se activará y provocará una interrupción para el sistema operativo. Se ejecuta cambio de contexto y el proceso se colocará al final de la cola de Listos.

El rendimiento del RR depende en gran medida del cuanto de tiempo. Si el cuanto es muy grande la politica es la misma que la del FCFS. Si es muy pequeño el enfoque se llama Compartir el procesador, y para los usuarios parece que cada proceso tiene su propio procesador.

RR (Cuanto = 4)

Rendimiento = 60% (Trabajos que acaban en su primera rafaga).

Rendimiento optimo 70% , se tiene que subir el Cuanto a 5

Rendimiento = 80 % . Calcular tiempo de ret medio.

Colas con prioridad

Se han creado otros algoritmos de planificación en aquellos sistemas donde los procesos pueden clasificarse facilmente en diferentes grupos.

Un algoritmo de Planificación de colas de multiples niveles divide la cola de Listos en varios niveles o colas. Los procesos se asignan de forma permanente a un cola, generalmente dependiendo de una prioridad. Cada cola tiene su propio algoritmo de planificación.

Debe existir además una planificación entre colas la cual es generalmente una planificación apropiativa de prioridad fija.

•       Se gestiona la cola de más prioridad hasta que esta vacía y se pasa a la siguiente.

Q=5

Q=10

Q=15

Tiempo de retorno medio.- Se calcula separadamente para cada cola y luego se hace la media aritmética.

Nivel 0 = 2+10+ /3 =4.3

Nivel 1 = 24+8+3+8 / 4 = 10.7

Nivel 2 = 19+31+15 /3 =21.6

Tiempo medio de ret = 12.2 ms.

Colas multinivel.

La planificación de colas multinivel (con realimentación ) permiten al proceso moverse de una cola a otra. La idea es separar a los procesos con diferentes caracteristicas en cuanto a rafagas de CPU. Si n procesos utiliza demasiado tiempo la CPU pasará a una cola de menor prioridad.

Este esquema deja a los procesos interactivos y a los limitados por E/S en las colas de mayor prioridad.

Por lo general un planificador de colas multinivel se define por los siguientes parametros :

•       Número de colas.

•       Algoritmo de planificación para cada cola.

•       El método utilizado para promover proceso a colas de mayor prioridad.

•       El método utilizado para degradar proceso a colas de menor prioridad.

•       Método utilizado para determinar a cual cola entrará un proceso cunado necesite un servicio.

Q=5

Q=10

Q=15

* Algoritmo entre colas SRT

Q=5

Q=10

Q=15

TAREAS	T ENTRADA	CPU
P1	0	5
P2	0	20
P3	1	4
P4	2	30
P5	3	10
P6	20	4
P7	25	20
P8	30	2
P9	31	6
P10	60	10

Tiempo Umbral .- Tiempo en que una tarea puede finalizar si con esto finaliza su ejecución completa mejorando así el rendimiento medio del sistema.

Tiempo de refresco.- Tiempo máximo que una tarea puede estar en una cola sin ser ejecutado. Transcurrido ese tiempo sube de nivel.

•       Si coinciden en el tiempo procesos :

n     Primero memoria.

n     Sale de ejecutar

n     Refresco.

Q=5

Q=10

Q=15

T Umbral = 2

T Refresco =20

Algoritmo RR Virtual .- Se aplica a sistemas con muchas operaciones de E/S y ráfagas de CPU cortas.

Cuando se va a seleccionar una tarea, se da prioridad a las que han finalizado su operación de E/S frente a las que vienen de la cola de listos. Con las tareas que vienen de E/S se crea una cola de prioridad, pero el cuanto asignado queda disminuido en el tiempo de CPU ejecutado.

•       Finalidad .- Ocupación de dispositivos de E/S

Proceso à 1,20,1,10,2,15

Ej.- En un ordenador se gestiona la CPU mediante una cola multinivel con 2 Niveles.

Primer nivel à SRT

Segundo nivel à FIFO

La CPU se asigna a cada nivel durante 100 ms. Siempre que un trabajo finalice en un nivel o realice una operación de E/S y no consuma los 100 ms. se cambia de nivel.

La cola E/S à FCFS

PROCESO	T ENTRADA	T CPU	NIVEL
P1	0	70,100,20	1
P2	0	150,100	2
P3	30	30,40,5	1
P4	170	60,30,20	2
05	170	30,4	1

SRT

FIFO

FCFS (E/S)

Tiempo de Ret medio = 239 ms.

Ej .- Se plantean dos soluciones para mejorar FCFS, cuando un proceso largo hace esperar.

A) Cuando un proceso largo produce un convoy de 3 unidades (3 procesos en espera más corta que el que se ejecuta), se detiene dicho proceso y se ejecuta el más corto y cuando termina se vuelve al más largo.

B) Plantea algoritmo multinivel con dos colas sin realimentar

Trabajos de menos de 7 ms a la Primera cola (FCFS).

Trabajos largos de más de 7 ms a la Segunda cola (SJF)

El sistema de adjudicación de tiempo a cola mediante RR Q=10

PROCESO	T LLEGADA	CPU
P1	0	50
P2	1	5
P3	3	6
P4	5	4
P5	9	1
P6	15	2
P7	25	10
P8	38	8
P9	50	10
10	57	20

A)

B)

Planificación de Multiprocesadores.

Existen 3 tipos de diseño diferentes dentro de los sistemas de Multiprocesador :

•       Débilmente acoplados.- Son prácticamente autónomos, cada procesador tiene su propia memoria y dispositivos de E/S.

•       Especializados.- Similares a los procesadores de E/S. Hay un procesador principal de proposito general ; los procesadores especializados están controlados por el micro principal y al que le ofrecen determinados servicios.

•       Fuertemente acoplados.- Conjunto de procesadores que comparten la memoria y dispositivos de E/S y se encuentran bajo el control integrado de un SO.

n     Dos objetivos.-

•       Rendimiento.- Un único procesador ejecutando en un sistema operativo multiprogramado ofrecerá mejor rendimiento que un sistema monoprocesador equivalente y puede ser más efectivo que varios sistemas monoprocesador.

•       Seguridad.- Con varios micros, y uno de ellos cae, la carga se reparte entre los demás, provocando unicamente una degeneración en el rendimiento en lugar de la perdida completa del servicio.

En un sistema con multiprocesador se pueden ejecutar a la vez los diferentes hilos en diferentes procesadores en lugar de asignar rebanadas de tiempo.

n     Granularidad de sincronización.- Mide el grado de dependencia de procesos. 5 Categorías de paralelismo.

•       Paralelismo independiente.- No existe sincronización explícita entre procesos.(Sistemas en tiempo compartido) En el caso de multiprocesador como se asigna a un proceso un micro, existe paralelismo independiente entre procesos. El multiprocesador ofrece el mismo servicio que el monoprocesador multiprogramado.

•       Grano grueso y muy grueso.- Existe algo de sincronización a nivel muy bajo. Esta situación se maneja muy bien con un conjunto de procesos concurrentes ejecutando en un monoproceasdor multiprogramado y puede verse respaldado por un multiprocesador con escasos cambios o incluso ninguno en el software de usuario.

•       Grano medio.- Planificación por hilos. Los hilos no son independientes, debe haber una sincronización de hilos, para cuando se produzca una zona critica en el proceso.

•       Grano fino.-  Significa un uso del paralelismo mucho más complejo que el que se consigue con los hilos. Bifurcación y sincronización de una misma sentencia.

Elementos de diseño.

1)   Como se asignan procesos a procesadores à Si la arquitectura es uniforme, la forma más sencilla es tratar a los procesadores como un recurso resvado y asignar los procesos a los procesadores por demanda.

Estática.- Durante ejecución de procesos va a estar asignado al mismo procesador. Debe mantenerse una cola dedicada a corto plazo para cada procesador. La función de planificación tiene un coste menor puesto que la asignación se realiza una sola vez. Permite estrategia de planificación por grupos.

Dinámica.- Cada vez que el proceso sale para bloqueo puede ser asignado a otro micro. Todos los procesos van a una cola comun y son ejecutados en cualquier procesador que este disponible. Durante la vida de un proceso este puede ejecutarse en diferentes procesadores en momentos diferentes.

•       La principal característica de la Estática es su menor coste de planificación y se podrá usar la planificación por grupos.

•       La principal desventaja es que algún procesador quede inactivo.

Forma de asignación.

•       Arquitectura Maestro / Esclavo.- Hay un procesador principal que ejecuta el sistema operativo y la rutina principal y los esclavos solo ejecutan programas de usuario. El maestro es responsable de la planificación de trabajos.

•       Dos inconvenientes.-

•       Si se cae el maestro.

•       Si el acceso al maestro es en modo exclusivo se podrá producir un cuello de botella.

•       Arquitectura Simétrica.- El SO se puede ejecutar entre varios procesadores, de modo que si uno se cae las rutinas del Kernel se reparten. Cuando un procesador queda ocioso solicita una rutina y se ejecuta en el mismo procesador.

2)   Multiprogramación y Multitarea.- Depende del nº de procesadores del sistema que estos además de realizar multiprogramación realicen multitarea. En los multiprocesadores tradicionales (Grano grueso) esta claro que cada procesador puede alternar entre varios procesos para conseguir una más alta utilización. Cuando se trabaja con aplicaciones de grano medio la situación es menos clara. Cuando hay varios procesadores, no resulta importante que cada procesador este ocupado al máximo.

3)   Expedición de un proceso.- Selección real de un proceso a ejecutar. Depende de la política de asignación.

•       Planificación de hilos.-

•       Comparición de carga.

•       Planificación por grupos.

•       Asignación dedicada.

•       Planificación dinámica.

•       Comparición de carga.- La carga se distribuye uniformemente entre micros.

No es necesario un planificador centralizado, la rutina de planificación del sistema operativo se ejecuta en cada procesador para seleccionar un nuevo hilo.

La cola global se gestiona con algoritmos de prioridad.

FCFS.

Menor nº de hilos.

Menor nº de hilos apropiativos.

Desventajas.-

•       La cola ocupa mucho espacio en memoria.

•       Acceso exclusivo a la cola.

•       Uso de cache de procesadores no será muy eficaz por la asignación dinámica de hilos.

•       Nº de intercambios que hay que realizar.

n     Planificación por grupos.- Los procesos próximos se ejecutan en paralelo y se reducen los bloqueos por sincronización e intercambio. La sobrecarga de planificación puede reducirse debido a que una decisión afectará a varios procesadores y procesos al mismo tiempo.

n     Asignación dedicada de procesadores.- Asignar un grupo de procesadores a una aplicación mientras dura aplicación. Se asigna cada uno de sus hilos a un procesador que permanece dedicado hasta que termina la aplicación. Se produce cuando se tiene un numero suficiente de microprocesadores.

•       Se pueden plantear varias observaciones :

•       En un procesador masivamente paralelo con cientos de procesadores, cada uno de los cuales representa una pequeña parte del coste del sistema, la utilización del procesador no es tan importante como medida de la efectividad o rendimiento.

•       La anulación total del intercambio de procesos durante el tiempo de vida de un proceso dará como resultado una aceleración sustancial del programa.

n     Planificación dinámica.- Se combina dinámicamente la carga del sistema. El SO es el encargado de repartir los procesadores entre los trabajos

El SO es el encargado de :

•       Un trabajo solicita uno o más procesadores. S hay procesadores libres se le asignan para satisfacer petición.

•       Si no hay libres se quitan procesadores a aquellos que tengan más de un procesador asignado.

•       Si no hay, se pasa a una cola de peticiones. Cuando se liberan proc. Se explora la cola y se asigna un procesador por proceso y si sobran se recorre otra vez la cola y se asignan (FCFS).

Ej.- Se quiere determinar entre los algoritmos SJF y RR cual es el más idóneo para la instalación. Se decide implementar el de menor tiempo de espera.

PROCESO	CPU Y E/S	T LLEGADA
P1	3/2/3/3/1	0
P2	2/3/7/5/3	0
P3	5/4/6	3
P4	6/4/5/2/4	4
P5	4/6/9	5

RR = 3 ms.

RR Q=3

E/S

TEMA 3

CONCURRENCIA DE PROCESOS : EXCLUSION MUTUA Y SINCRONIZACION

•       Principios de la concurrencia.

•       Exclusión mutua. Enfoques por software.

•       Exclusión mutua. Enfoques por hardware.

•       Semáforos.

•       Paso de mensajes.

•       Problema de los lectores / escritores.

•       3 principios generales de concurrencia.-

n     Para que exista exclusión mutua :

•       Debe existir exclusión mutua en el sentido de que solo un proceso ejecute a la vez esa sección de código.

•       Debe de asegurarse que los procesos no esperen indefinidamente por la obtención del recurso. Se debe garantizar que en un mínimo de tiempo los procesos acceden al recurso (Espera limitada).

•       Acceso progresivo, no puede depender el acceso del acceso previo de un proceso al recurso.

La Sección Critica viene precedida de una sección de entrada y seguida de una sección de salida.

While true do begin

Sección de entrada

Sección critica

Sección de salida (Salida incondicional si se quiere romper el bucle).

End

Dentro de un Sistema Operativo que elementos de gestión y diseño surgen por la concurrencia.-

•       El SO tiene que ser capaz de seguir la pista a los diferentes procesos activos. (Esto lo hace por medio de BCP).

•       Debe asignar y quitar recursos a procesos activos. Entre estos se incluyen :

•       Tiempo de CPU

•       E/S

•       Ficheros

•       Memoria

•       Debe proteger los datos y recursos físicos de otro proceso por cada inferencia de otros procesos.

•       Los resultados de un proceso deben ser independientes de la velocidad relativa de ejecución con respecto a otros procesos.

Interacción de procesos.

Se ha señalado que la concurrencia de los procesos puede ser resultado de multiprogramación de aplicaciones independientes, de aplicaciones con varios procesos y de uso de la estructura de procesos en el sistema operativo. Teniendo en cuenta esto es posible clasificar estas iteracciones en función del nivel de conocimiento que cada proceso tiene de la existencia de los demás.

Los procesos no tiene conocimiento de los demás.

Aunque los procesos sean independientes unos de otros el SO debe encargarse de distribuir recursos. Existe lo que se llama competencia por los recursos entre los procesos.

Aunque los resultados de los procesos son independientes, los tiempos de ejecución se verán afectados por los tiempos de espera de recursos.

Problemas de control

•       Exclusión mutua.

•       Interbloqueo.

•       Inanición.

Los procesos tiene conocimiento indirecto de otros.

Existe cooperación por compartición de algun objeto común . Los resultados de un proceso pueden depender de los datos obtenidos de otros procesos.

Problemas de control

•       Exclusión mutua.

•       Interbloqueo.

•       Inanición.

•       Coherencia de datos.

Los procesos tiene conocimiento directo de otros procesos.

Los procesos son capaces de comunicarse con los demás por su nombre y estan diseñados para trabajar conjuntamente en alguna actividad.

•       Primitivas de comunicación.

•       Resultados de procesos dependen de información recibida de otros.

Problemas de control

•       Interbloqueo.

•       Inanición.

Requisitos para la exclusión mutua.

n     El uso adecuado de concurrencia exige capacidad de definir secciones criticas.

n     Cualquier servicio y que soporte de exclusión mutua debe cumplir.-

•       Solo un proceso de todos los que poseen sección critica con mismo proceso deben tener permiso para acceder al recurso en un momento dado.

•       Un proceso que interrumpe su sección critica debe hacerlo sin molestar a otro proceso.

•       Un proceso que solicita su sección critica no debe ser demorado indefinidamente à Interbloqueo, Inanición.

•       Cuando ningun proceso esta en su sección critica cualquier proceso que solicita su sección critica debe poder hacerlo sin dilación.

•       No se puede hacer suposiciones sobre velocidad relativa.

•       Un proceso permanece en su sección critica un tiempo finito.

Soluciones Software para exclusión mutua.

Solución 1

Program Exclusión mutua ;

var

turno : 0.. 1 ;

procedure uno

begin

while true do

begin

while turno <> 0 do ;

seccion critica ;

turno := 1 ;

{Resto de codigo}

end ;

end ;

procedure dos ;

begin

while true do

begin

while turno <> 1 do ;

seccion critica ;

turno := 0 ;

{Resto de codigo}

end ;

end ;

begin

turno :=0 ;

parbegin

uno ;

dos ;

parend ;

end.

•       El algoritmo funciona si se produce acceso alternativo a la sección critica (Velocidad viene determinada por el más lento). Si se da el caso de que un proceso no quiere volver a entrar o termina su ejecución el otro no puede ejecutar.

•       Solo cumple la primera primitiva à Exclusión mutua.

Solución 2

Program exclusion mutua 2 ;

var

turno : ARRAY [0 ..1] of boolean ;

procedure uno ;

begin

while true do

begin

while turno[1] do ;

turno [0] := true ;

sección critica ;

turno[0] := false ;

{Resto de codigo}

end ;

end ;

procedure dos ;

begin

while true do

begin

while turno[0] do ;

turno [1] := true ;

sección critica ;

turno[1] := false ;

{Resto de codigo}

end ;

end ;

•       No se cumple la exclusión mutua, ya que los procesos puede entrar a la vez en sus secciones criticas.

•       Por tanto tampoco se cumplen el resto de primitivas.

Solución 3

Program exclusion mutua 3 ;

var

turno : ARRAY [0 ..1] of boolean ;

procedure uno ;

begin

while true do

begin

turno [0] := true ;

while turno[1] do ;

sección critica ;

turno[0] := false ;

{Resto de codigo}

end ;

end ;

procedure dos ;

begin

while true do

begin

turno [1] := true ;

while turno[0] do ;

sección critica ;

turno[1] := false ;

{Resto de codigo}

end ;

end ;

•       Se cumple la exclusión mutua, pero no el resto de primitivas à No entra ninguno en caso de acceso simultaneo. (En este caso se producirá interbloqueo).

Solución 4

Program exclusion mutua 4 ;

var

turno : ARRAY [0 ..1] of boolean ;

Procedure uno ;

begin

while true do

begin

turno [0] := true ;

while turno[1] do 

begin

turno[0] := false ;

delay (random) ;

turno [0] := false ;

end ;

sección critica ;

turno [0] := false ;

{Resto de codigo}

end ;

end ;

Procedure dos ;

begin

while true do

begin

turno [1] := true ;

while turno[0] do ;

turno[1] := false ;

delay(random) ;

turno[1] := false ;

end ;

sección critica ;

turno [1] := false ;

{Resto de codigo}

end ;

end ;

•       Podría darse el caso de que el random de ambos cogiese la misma semilla y no entrara ninguno de los dos .

•       Se produce exclusión mutua, pero no el resto de primitivas.(Podría darse el caso de interbloqueo , en el caso de que se produjeran semillas identicas).

Algoritmo de Dekker

var

señal : ARRAY [0..1] of boolean ;

turno : 0 ..1 ;

Procedure Uno ;

begin

while true do

begin

señal [0] := true ;

while señal [1] do

if turno = 1 then

begin

señal [0] := false ;

while señal[1] do ;

señal [0[ := true ;

end ;

sección critica ;

turno :=1 ;

  señal [0] := false ;

{Resto de sentencias} ;

end ;

end ;

Procedure Dos ;

begin

while true do

begin

señal [1] := true ;

while señal [0] do

if turno = 0 then

begin

señal [1] := false ;

while señal[0] do ;

señal [1] := true ;

end ;

sección critica ;

turno :=0 ;

  señal [1] := false ;

{Resto de sentencias} ;

end ;

end ;

{ Programa principal }

begin

turno := 0 ;

señal [0] := false ;

señal [1] := false ;

parbegin ;

uno ;

dos ;

parend ;

end.

Ej.- problema de los esquimales.

Program Esquimales ;

var

pescar : ARRAY [0..1] of boolean ;

turno : 0..1 ;

Procedure Come _esquimal1 ;

begin

while true do

begin

pescar [0] := true ;

while pescar [1] do

begin

if turno = 1 then

begin

pescar[0] := false ;

while pescar [1] do ;

pescar [0] := true ;

end ;

sección critica ;

pescar[0] := false ;

turno := 1 ;

{ Resto de codigo }

end ;

end ;

Procedure Come _esquimal2 ;

begin

while true do

begin

pescar [1] := true ;

while pescar [0] do

begin

if turno = 0 then

begin

pescar[1] := false ;

while pescar [1] do ;

pescar [1] := true ;

end ;

sección critica ;

pescar[1] := false ;

turno := 0 ;

{ Resto de codigo }

end ;

end ;

{ Programa Principal }

Begin

pescar [0] := false ;

pescar [1] := false ;

turno := 0 ;

parbegin ;

Come_esquimal1 ;

Come_esquimal2 ;

parend ;

End.

Fork / Join Parbegin / Parend.

Cuando un proceso se bifurca en otros dos procesos paralelos, se ejecuta un FORK y se convierten estos en procesos hijos y mediante u JOIN se juntan de nuevo en el proceso Padre.

Grafo de precedencia à Define que proceso se ejecuta antes que otro o cual se ejecuta en paralelo.

a := a+1 ;

b := a+2 ;

c : = 3*a ;

d : = b +2c ;

A ;

cont := 2 ;

Fork L 1 ;

B ;

GOTO L2 ; { Equivale a decrementar el contador }

L 1 : C

GOTO L2 ;

L2 : Join cont ;

D ;

A

PARBEGIN

B

C

PAREND

D

Ej.-

P1

CONT := 4 ;

FORK L1

FORK L2

FORK L3

P2

GOTO L4

L1 : P5

GOTO L4

L2 : P4

GOTO L4

L3 : P3

GOTO L4

L4 : JOIN CONT

P6

P1

PARBEGIN

P2

P3

P4

P5

PAREND

P6

Ej.-

PO

CONT1 := 3

FORK L1

FORK L2

P1

CONT2 := 2

FORK L3

P4

GOTO L4

L1 : P3

GOTO L4

L2 :P2

GOTO L4

L3 : P5

GOTO L4

L4 : JOIN CONT2

P6

GOTO L5

L5 : JOIN CONT1

P7

P0

PARBEGIN

P3

P2

BEGIN

P1

PARBEGIN

P4

P5

PAREND

P6

END

PAREND

P7

Ej.-

PO

CONT1 := 2

FORK L1

P1

CONT2 := 2

FORK L2

P3

GOTO L4

L2 : P4

GOTO L4

L4 : JOIN CONT2

P7

GOTO L6

L1 : P2

CONT3 := 2 ;

FORK L3

P5

GOTO L5

L3 : P6

GOTO L5

L5 : JOIN CONT3

P8

GOTO L6

L6 : JOIN CONT1

P9

 

P0

PARBEGIN

BEGIN

P1

PARBEGIN

P3

P4

PAREND

P7

END ;

BEGIN

P2

PARBEGIN

P5

P6

PAREND

END

P8

PAREND

P9

Soluciones hardware.

•       Pesimistas à Resuelven exclusión mutua pero con costes muy elevados para el sistema.

Inhabilitacion / Habilitacion de interrupciones .- Cuando un proceso pide entrar en su sección critica se inhabilitan interrupciones. Se asegura que el proceso no va ha ser interrumpido, se produce un retroceso en todos los procesos (Inactividad total). Cuando se ejecuta la sección critica se habilitan interrupciones.

Para evitar inanición se habilitan las interrupciones por niveles. ( Lo más utilizado antiguamente).

•       Optimistas à A nivel de hardware los accesos a posiciones de memoria excluyen cualquier otro acceso a esa misma posición. Con esa base, los diseñadores han propuesto varias instrucciones de máquina que realizan dos acciones atomicamente tales como leer y escribir o leer y examinar, sobre una posición de memoria en un unico ciclo (Pro tanto no estan sujetas a interrupciones por parte de otras instrucciones).

•       Instrucción TS

•       Instrucción CS

•       Instrucción de intercambio.

Instrucción TS (Comparar y fijar).- Se basan en que el acceso a posición de memoria excluye el acceso de otros procesos a esa posición de memoria. Creando instrucciones de máquina que realizan su código de forma atomica (indivisible). à Algun proceso puede interrumpir.

Function TS (var i:entero):boolean;

begin

if i =0 {libre} then

begin

i:= 1;

TS:= true;

end

else

TS:= false;

end;

La función examina el valor del argumento i. Si el valor es 0 lo cambia por 1 y devuelve cierto. En otro caso el valor lo no se modifica y devuelve falso.

Program Exclusion_mutua;

const N= ___

var

cerrojo: entero;

procedure P (i:entero);

begin

repeat

repeat until TS (cerrojo);

sección critica;

cerrojo:=0;

{Resto codigo}

Forever

end;

Begin

cerrojo := 0;

parbegin;

P(1);

.

.

.

P(N);

parend;

end;

Instrucción CS.- Propia de las máquinas de IBM, se utiliza para actualizar una variable.

Se realiza una copia del valor de la variable (señal) a registro viejo . Aquí se realizan operaciones necesarias y posteriormente se comprueba que señal, tiene el mismo valor, si lo tiene es que no ha entrado otro proceso a actualizar la variable. Si coincide, actualiza la variable directamente y si no coincide, se vuelve a copiar el valor de la clave al registro y se vuelven a realizar operaciones.

Instrucción de Intercambio.- Intercambia el contenido de un registro con una posición de memoria. Durante la ejecución se bloquea el acceso a esa posición de memoria. Se asigna el valor de la memoria a una variable temporal, se copia en memoria el valor del registro, se copia en el registro el valor de la variable auxiliar y todo ello sin interrupción de principio a fin.

Propiedades de las soluciones.

 

El uso de las soluciones de máquina tiene ventajas e inconvenientes.

Ventajas.-

•       Es aplicable a sistemas con cualquier número de procesos, en memoria compartida, monoprocesador o multiprocesador.

•       Simple o facil de verificar.

•       Pueden usarse para disponer de varias secciones criticas, cada sección critica puede definirse con su propia variable.

Inconvenientes.-

•       Se emplea espera activa. Mientras un proceso esta esperando para acceder a la sección critica continua consumiendo tiempo de procesador.

•       Inanición.- Cuando un proceso abandona la sección critica y hay más de un proceso esperando, la selección es arbitraria, asi pues, se podría denegar acceso a lagun proceso indefinidamente.

•       Puede producirse interbloqueo.

SEMAFOROS.

Principio fundamental.- dos o más procesos pueden cooperar con uso de simples señales, de forma que se pueda detener un proceso, en una posición determinada hasta que se recibe una señal especifica. Para transmitir señal se utiliza semaforo s, y los procesos ejecutan la primitiva SIGNAL y para recibir una señal del semaforo se utiliza la primitiva WAIT. (Si la señal correspondiente todavia no se ha transmitido el proceso queda suspendido hasta que reciba la señal.

Las primitivas wait y signal se suponen atomicas, no pueden ser interrumpidas y cada rutina puede considerarse como un paso indivisible.

La forma más primitiva es el Semaforo Binario à Solo puede tomar dos valores :

0 à No pasar.

1 à Pasar.

•       Son más sencillos de implementar y puede demostrarse que tienen la misma potencia que los semaforos generales.

Semaforo general à Puede contemplarse como una variable que tiene un valor entero sobre el que se definen las tres operaciones siguientes :

1)   Puede inicializarse no un valor no negativo (N).

2)   WAIT à Decrementa el valor del semaforo. Si el valor se hace negativo el proceso se bloquea.

3)   SIGNAL à Incrementa el valor del semaforo. Si el valor no es positivo, se desbloquea a un proceso bloqueado por la primitiva WAIT.

¨    Tanto los semaforos binarios como los generales emplean una cola para mantener a los procesos esperando. En el semaforo.

Wait (s)

while s<> 1 do;

s:= s - 1 (0); (n-1);

seccion critica;

signal (s) : s:= s+1;

•       No hay una planificación fija aunque se considera una politica fija .- Cada proceso ejecuta un Wait antes de entrar y cuando sale libera ejecutando un signal.

•       Cuando un proceso intenta entrar se coloca en la cola y decrementa el semaforo. Cuando un proceso se elimina de la cola ejecuta un signal e incrementa el valor del semaforo.

Exclusión Mutua .- En cada proceso se ejecuta un wait antes de entrar en su sección critica. Si el valor es 1 el semaforo se decrementa a 0 y el proceso entra inmediatamente en su sección critica. Puesto que el valor de s ya no es positivo no se permitirá la entrada de ningun proceso a la sección critica.

El semaforo se inicializa a 1. De este modo el primer proceso que ejecute el wait podrá entrar en la sección critica poniendo el valor de s a 0. Cualquier proceso que entre posteriormente podra el semaforo a valor negativo y se bloqueará entrando en la cola de espera.

Cuando el proceso que ejecuta su sección critica salga de esta se incrementará s se desbloqueará un proceso de la cola de espera.

Implementación de un Semáforo Binario.

Type

semaforobinario = RECORD

valor : (0,1)

cola: lista de procesos;

end;

var

s: semaforo;

wait (s):

if s.valor := 1 then

s.valor := 0

else

begin

Poner este proceso en la cola.

Bloquear este proceso.

End;

signal (s):

if s.cola esta vacia then

s.valor := 1;

else

begin

Quitar proceso P de la s.cola

Poner proceso P en la cola de listos;

end;

•       Si contador > 0 es el numero de procesos que pueden ejecutar el wait sin bloquearse.

•       Si contador < 0 Contador es el nº de procesos que estan bloqueados en la s.cola.

•       Si contador = 0 no hay nadie en la cola de espera.

Implementación de un Semáforo General.

Type semaforo = RECORD

contador : entero;

cola: list of procesos;

end;

var

s:semaforo;

wait (S):

s.contador := s.contador -1;

if s.contador < 0 then

begin

Poner proceso en cola;

Bloquear proceso;

end;

signal (s):

s.contador := s.contador +1;

if s.contador <= 0 then

begin

quitar proceso de la s.cola;

poner proceso en la cola de listos;

end;

Program exclusion_mutua;

const

N = ...;

var

s: semaforo;

Procedure P (i:entero);

begin

repeat

wait (s);

seccion critica;

signal (s);

{ Resto Codigo }

Forever;

end;

Begin

s:= 1;

parbegin

p(1);

p(2);

p(n);

parend;

end;

Ej 1.- En un cuartel hay un comedor para 500 soldados. El soldado cuando quiere comer entra en el recinto y coge una bandeja con comida. (5 mostradores);la bandeja tiene agua o botellin , si escoge esto ultimo tiene 50 abridores.

Despues de la comida puede comer un postre (3 mostradores);

Cuando finaliza sale del recinto.

Program comida cuartel;

var

recinto, b_comida, abridor, b_postre : semaforo;

procedure soldado (i:integer);

var

abrir , postre : boolean;

begin

while true do

begin

wait (recinto);

{entrar}

wait (b-comida);

{Bandeja}

signal (b_comida);

readln (abrir);

if abrir then

wait (abridor);

{abre}

signal (abridor);

readln (postre);

if postre then

wait (b_postre);

{come postre}

signal (b_postre);

{comer}

signal (recinto);

end;

end;

begin

recinto := 500;

b_comida:= 5;

abridor:= 50;

b_postre := 3;

parbegin

soldado(1);

soldado (n);

parend;

end;

Ej 2.- En una clinica de traumatologia hay diferentes secciones Medico, escayola, y Rayos-x.

Los enfermos acceden a la clinica y la enfermera les indica la sala a la que deben acceder.

Medico .- tiene una sala de espera para 20 enfermos.

Escoyola .- Sala de espera para 6 enfermos.

Rayos-x .- No espera.

Program clinica;

var

enfermera, s_medico, medico, s_esca, escayola, rayos :semaforo;

procedure enfermo (i:integer);

begin

while destino <> casa do

begin

wait (enfermera);

readln (destino);

if destino = medico then

begin

wait (s-medico);

wait (medico);

signal (s_medico);

readln (destino);

signal (medico);

end;

if destino = esca then

begin

wait (s_esca);

wait (esca);

readln (destino );

signal (s_esca);

signal (esca);

end;

if destino = rayos then

begin

wait (rayos);

readln (destino );

signal (rayos);

end;

end;

end;

begin

enfermera := 1;

s_medico .= 20;

s_esca := 6;

rayos := 1;

medico = 1;

parbegin

enfermo (1);

enfermo (n);

parend

end;

Problema de la Barbería.

Como otro ejemplo del uso de semaforos en la concurrencia se considera el problema de una barberia.

La barbería tiene tre sillas, tres barberos, una zano de espera en la que se pueden acomodar 4 clientes en un sofá y una sala de espera de pie para el resto de los clientes. Las medidas contra incendios limitan el número total de clientes en la tienda a 20.

•       Un cliente no entrará en la tienda si su capacidad esta al completo.

•       Una vez dentro, el cliente toma asiento en el sofá o permanece de pie se el sofá esta completamente ocupado.

•       Cuando un barbero esta libre, se atiende al cliente que ha estado más tiempo en el sofá y si hay clientes de pie, el que ha entrado en la tienda hace más tiempo ocupa el lugar libre en el sofá.

•       Cuando finaliza el corte de pelo, cualquier barbero puede aceptar el pago, pero debido a que solo hay una caja registradora solo se acepta el pago de un cliente por vez. Los barberos dividen su tiempo entre cortar el pelo, aceptar pagos y dormir en su silla esperando clientes.

¨    El cuerpo principal del programa activa 50 clientes tres barberos y el proceso del cajero. Considerese el proposito y la posición de los siguientes operadores de sincronización :

•       Capacidad de la tienda o del sofa à Esta gobernadas por los semaforos max_capacidad y sofá .

•       Capacidad de las sillas del barbero à Hay tres sillas de barbero . El semaforo silla_barbero se asegura de que no más de tres clientes intentan ser atendidos a la vez.

•       Asegurarse de que los clientes están en la silla del barbero à el semaforo cliente_listo indica a un barbero que estuviera durmiendo que un cliente acaba de sentarse en una silla. (Si este semaforo el barbero nunca dormiría o incluso podría cortar el pelo incluso sin cliente).

•       Mantener los clientes en la silla del barbero à El cliente permanece en la silla hasta que el barbero le indica que el corte esta completo mediante el semaforo terminado.

•        Limitarse a un cliente por silla à El semaforo silla _barbero no lo conseguiria por si solo y por ello se añade un semaforo silla_barbero_b (Evita que el barbero invite a otro cliente hasta que este a aabndonado su silla)

•       Pagar y tomar el recibo àCada cliente al levantarse de la sillade barbero, paga y despues informa al cajero que quiere un recibo (signal (pago) y wait (recibo)).

•       Coordinación de las labores de cajero y barbero à Mediante el semaforo coord se consigue que un barbero no efectue dos acciones al tiempo.

 

Program Barbería ;

var

sofa, silla_barbero, max_capacidad, coord : semaforo ;

dejar_silla _b, cliente listo, terminado ,pago, recibo : semaforo binario ;

Procedure Cliente ;

begin

wait (max_capacidad) ;

entrar tienda ;

wait (sofá) ;

sentarse en el sofa ;

wait (silla_barber) ;

Levantarse del sofa ;

signal(sofá) ;

sentarse en la silla del barbero ;

signal (cliente_listo) ;

wait (terminado) ;

levantarse de la silla del barbero ;

signal (dejar_silla_b) ;

pagar ;

signal (pago) ;

wait (recibo) ;

salir tienda ;

signal (max_capacidad) ;

end ;

Procedure barbero

begin

repeat

wait (cliente_listo) ;

wait(coord) ;

cortar pelo ;

siagnal (terminado) ;

wait (dejar_silla_b) ;

signal (silla_barbero) ;

forever ;

end ;

Procedure cajero ;

begin

repeat

wait (pago) ;

wait (coord) ;

aceptar pago ;

signal (coord) ;

signal (recibo) ;

forever ;

end ;

{ PROGRAMA PRINCIPAL}

begin

max_capacidad := 20 ;

sofa := 4 ;

silla_barbero := 3 ;

coord := 3 ;

cliente_listo := 0 ;

terminado := 0 ;

pago := 0 ;

recibo := 0 ;

dejar_silla_b := 0 ;

END.

Lectores / Escritores (Problema Tipo).

Trata el acceso a un fichero por parte de lectores y escritores. Los lectores accedena el para lectura. Los escritores acceden a el para modificar, con lo que acceden de uno en uno.

Se da prioridad a los lectores frente a los escritores y cuendo ya no halla lectores, se deja entrar a modificar. Este no permite la entrada de lectores y tampoco permite el paso o otro escritor.

Program Lectores_Escritores ;

var

contlect :entero ;

contalect, fichero : semaforo ;

Procedure lector (i :entero) ;

begin

while true do

begin

wait (contalect) ;

contlect := contlect +1 ;

if contlect = 1 then

wait (fichero) ;

signal (contalect) ;

{lee}

wait (contalect) ;

contlect := contlect -1 ;

if contlect = 0 then signal (fichero) ;

signal (contalect) ;

{Resto de codigo}

end ;

end ;

Procedure Escritor (I :entero) ;

begin

while true do

begin

wait (fichero) ;

{Escribe}

signal (fichero) ;

{Resto de codigo}

end ;

end ;

{PROGRAMA PRINCIPAL }

Begin

contlect := 0 ;

contalect := 1 ;

fichero := 1 ;

parbegin

lector (1 ) ;

lector (N) ;

escritor (1) ;

escritor(N) ;

end ;

END.

Ej .- Conocido el problema tipo del lectores escritores, crear una variable turno que de prioridad a lectores deje leer a 10 y cambie el turno a escritores.

Si hay escritores, deja escribir a 3 y cambia el turno a los lectores.

Un lector lee si hay menos de 10 lectores leyendo o no hay escrotores y un escritor escribe se es su turno, si hay menos de 3 escritores y si no hay lectores

Program Lectores_Escritores (Modificado) ;

var

contlec, contesc :entero ;

lectoresdentro, escritoresdentro : entero ;

fichero, contalect, contaesc : lectdentro, escdentro : semaforo ;

turno : (Lectores, escritores) ;

Procedure lector (i :entero) ;

begin

while true do 

begin

wait (contalect) ;

contlect := contlect +1 ;

while (contlect > 10) OR (turno = escritores) do ;

signal (contalect) ;

wait (lectdentro) ;

lectoresdentro := lectoresdentro +1 ;

if lectoresdentro =1 then wait (fichero9 ;

signal (lectdentro) ;

{Leer}

wait (contalect) ;

contlect := contlect -1 ;

wait (lectdentro) ;

if lectoresdentro =10 OR contlect=0 then

begin

signal (fichero) ;

turno := escritores ;

lectresdentro := 0 ;

end ;

signal (lectdentro) ;

signal (contalect) ;

end ;

end ;

Procedure escritor (i :entero) ;

begin

while true do

begin

wait (contaesc) ;

contesc := contesc +1 ;

while (contesc > 3) OR (turno = lectores ) do ;

signal (contaesc) ;

wait (escdentro) ;

escritoresdentro := escritoresdentro +1 ;

signal (escdentro) ;

{Escribe}

wait (contaesc) ;

contesc := contesc -1 ;

wait (escdentro) ;

if (escdentro =3) OR (conesc=0) then

begin

signal (fichero) ;

turno := lectores ;

escritoresdentro := 0 ;

end ;

signal (escdentro) ;

signal (contaesc) ;

end ;

end ;

{PROGRAMA PRINCIPAL }

Begin

Contlect := 0 ;

contesc := 0 ;

turno := lectores ;

fichero := 1 ;

contalect := 1 ;

contaesc := 1 ;

lectdentro := 1 ;

escdentro :=1 ;

lectoresdentro :=0 ;

escritoresdentro .= 0 ;

parbegin

lector (1)

lector(N) ;

escritor(1) ;

escritor (N) ;

parend ;

end.

MONITORES

Un monitor es un modulo de software que consta de uno o más procedimientos, una secuencia de inicialización y unos datos locales. Tiene las siguientes caracteristicas :

•       Las variables de datos locales están solo accesibles para los procedimientos del monitor y no para procedimientos expternos.

•       Un proceso entra en el monitor invocando a uno de sus procedimientos.

•       Sólo un proceso puede estar ejecutando en el monitor en un instante determinado.

Una estructura de datos compartida puede protegerse situandola dentro de un monitor. Si los datos del monitor representan algún recurso. El monitor ofrecerá un servicio en exclusión mutua a este recurso.

Para que resulten utiles en el proceso concurrente, los monitores deben incluir herramientas de sincronización. Supongase que un proceso llama a un monitor, y mientras esta en el monitor debe suspenderse hasta que se cumpla una condición. Hace falta un servicio no solo para que está suspendido sino tambien para que libere el monitor y otro proceso pueda entrar

Un monitor proporciona sincronización pro medio de las variables de condición que se incluyen en el monitor y son accesibles solo desde este. Hay dos funciones para operar con estas variables variables :

•       CWAIT (C) à suspende la ejecución del proceso llamado bajo la condición C. El monitor esta ahora disponible para ser usado por otro proceso.

•       CSIGNAL (C) à Reanuda la ejecución de algun proceso despues de CWAIT bajo la misma condición. Si hay varios procesos elige el primero.

Problema del Productor_Consumidor. (MILENKOVIC pág. 153)

module M_productores_consumidores ;

...

b_1 : monitor ;

begin

buffer : array [1 ..capacidad] of dato ;

ent, sal : (1.. capacidad) ;

cuenta (0..capacidad) ;

producir, consumir : condition ;

procedure mdepositar (pdato : dato) ; { publico}

begin

if cuenta = capacidad then cwait (produce) ;

buffer [ent] := pdato ;

ent := (ent mod capacidad) +1 ;

csignal (consumir) ;

end {depositar}

procedure mtomar (var cdato : dato) ; {publico}

begin

if cuenta = 0 then cwait (consumir) ;

cdato := buffer [ sal] ;

sal := (sal mod capacidad ) +1 ;

cuenta := cuenta -1 ;

end ;

end {m_productores_consumidores}

module productores_cosumidores ;

procedure productor (i :entero) ;

var pdato :dato ;

begin

while true do

begin

pdato := producir ;

b_1. Mdepositar (pdato) ;

{resto codigo ;

end {while}

end

Productor consumidor (i :entero) ;

var

cdato :dato ;

begin

while true do

begin

b_1.mtomar (cdato) ;

consumir(cdato) ;

resto codigo ;

end {while}

end ;

{Proceso padre}

begin

initiate productores, consumidores ;

end

end {productores_consumidores}

La definición que hace HOARE de los monitores exige que si hay al menos un proceso en la cola de condición, un proceso de dicha cola deberá ejecutar en cuanto otro proceso ejecute un csignal para la condición. El proceso que ejecuta el csignal debe salir del monitor.

La primitiva csignal se reemplaza por la promitiva cmotify con la siguiente interpretación :

•       Cuando un proceso que esta en un monitor ejecuta cmotify (x) origina una notificación hacia la cola de condición x pero el proceso que da la señal puede continuar ejecutando.

La sentencia IF se sustituye por un WHILE . Así pues, se genera con la notificación una evaluación extra de la condición.

Con la norma de notificar los procesos en lugar de reactivarlos a la fuerza es posible añadir una primitiva de difusión cbroadcast . La difusión provoca que todos los procesos que estan esperando la condición se situen en estado de listo.

PASO DE MENSAJES.

Cuando los procesos interactuan unos con otros, se deben satisfecer dos requisitos basicos : sincronización y comunicación. Los procesos deben sincronizarse para cumplir la exclusión mutua ; los procesos pueden necesitar intercambiar información. Un metodo que ofrece ambas funciones es el paso de mensajes. Tiene la ventaja adicional de que puede ser implementado en sistemas distribuidos, así como en sistemas multiprocesador y monoprocesador con memoria compartida.

La funcionalidad real del paso de mensajes se ofrece por medio de un par de primitivas :

send (destino, mensaje) ;

recive (origen , mensaje) ;

Un proceso envia información en forma de mensaje o tro proceso (send) designado como destino. Un proceso recibe un mensaje de un proceso designado como origen mediante la primitiva recive.

Mensaje à Estructura de datos. (Normalmente implementado con un RECORD)

•       Permite controlar el contenido.

•       Control de sección critica.

•       Intercambio de información.

Sincronización.

La comunicación de un mensaje entre dos procesos implica cierto nivel de sincronización entre ambos.

Asi pues, tanto el emisor como el receptor pueden ser bloqueantes o no bloqueantes. Son abituales estas tres combinaciones :

•       Envio bloqueante, recepción bloqueante à Tanto el emisor como el receptor se bloquean hasta que se entrega el mensaje ; (rendezvous)

•       Envío no bloqueante, recepción bloqueante à Aunque el emisor puede continuar, el receptor se bloquea hasta que llega el mensaje solicitado. Paermite que un proceso envíe uno o más mensajes a varios destinos tan repido como sea posible.

•       Envío no bloqueante, recepción no bloqueante à Nadie debe esperar.

Exclusión mutua.

Un conjunto de procesos concurrentes comparten un buzón (exmut). El buzon contiene inicialmente un buzón tiene un unico mensaje de contenido nulo. Un proceso que desea entrar en su sección critica intenta primero recibir un mensaje. Si el proceso esta vacio se bloquea. Un vez que el proceso ha conseguido su mensaje ejecuta su sección critica y despues devuelve el mensaje al buzón. En mensaje actua como testigo o token. Esta tecnica supone que si hay más de un proceso ejecutando la orden recive concurrentemente ocurre :

•       Si hay un mensaje se entrega a uno de los procesos y los demás se bloquean.

•       Si el buzon esta vacio todos los procesos se bloquean.

Al igual que los semaforos existen dos tipos de buzones :

•       Buzon binario à Buzon con un unico mensaje. (Semaforo binario).

•       Buzon general à Buzon con varios mensajes. Los procesos piden mensajes hasta que estos se acaban, y cuando han ejecutado su sección critica los devuelven al buzón y se desbloquean otros procesos.

Program Exclusión Mutua ;

Const= .... (* Numero de procesos*) ;

Procedure P (I :entero)

begin

repeat

recive (exmut, msj) ;

Sección critica ;

send (exmut, msj) ;

{Resto de codigo}

Forever ;

end ;

{ PROGRAMA PRINCIPAL }

Begin

Crear buzon (exmut) ;

Send (exmul, null) ;

parbegin

p(1) ;

p(N) ;

parend ;

END .

Direccionamiento.

Dos categorias :

Directo à La primitiva send incluye una identificación especifica del proceso destino. La primitiva recive se puede gestionar de dos formas. Un posibilidad requiere que el proceso designe explicitamente un proceso emisor. Así pues, el proceso debe conocer de antemano de qu´ñe proceso espera un mensaje. En otros casos es imposible conocer al emisor de antemano y se utiliza el direccionamiento implicito.

Indirecto à Los mensajes no se envían directamente del eisor al receptor, sino a una estrucutra de datos compartida formada por colas que pueden guardar los mensajes. Estas colas se denominan buzones. Para que dos buzones se comuniquen se realiza a traves de una buzon.

Formato de mensajes.

El mensaje se divide en dos partes.

•       Una cabecera que alberga información sobre el mensaje.

•       Identificación del origen.

•       Longitud.

•       Campo de tipo de mensaje.

•       Un campo apuntador para crear una lista enlazada de mensajes

•       Un número de secuencia

•       Campo de prioridad.

•       Un cuerpo que alberga el contenido real.

Ej .- Con objeto de medir el rendimiento de un coche se instalan los siguientes sensores :

•       Tacometro que envia un señal por cada kilometro recorrido.

•       Cronometro que devuelve tiempo transcurrido en nim y permite programar su puesta a 0 cuando devuelve un valor.

•       Medidor de combustible que permite obtener en cualquier momento los litros de combustible consumidos.

•       Ordenador en el coche à Cada 10 Km indica la velocidad media y el consumo en litros por cada 100 Km.

Program coche ;

const N= 50 ;

type mensaje = RECORD

id :string ;

espacio, tiempo, combustible : entero ;

end ;

buzon = array [1.. N] of mensaje ;

var

b_ordenador, b_cronometro, b_medidor : mensaje ;

Procedure tacometro ;

var

m : mensaje ;

begin

while true do

begin

{ Mide 1 Km}

m.espacio := 1 ;

m.id := tacometro ;

send (b_odenador, m) ;

end ;

end ;

Procedure cronometro ;

begin

while true do

begin

recive (b_cronometro, m) ;

m.tiempo := gettime ;

m.id := cronometro ;

send ( b_ordenador, m) ;

m.tiempo := 0 ;

end

end ;

procedure medidor ;

var

m :mensaje ;

begin

while true do

begin

recive (b_medidor,m) ;

m.combustible = obtener consumo ;

m.id := medidor ;

send (b_ordenador,m ) ;

end ;

end ;

Procedure ordenador ;

var

m.mensaje ;

c :entero ;

begin

repeat

recive (b_ordenador,m)

if m.id = tacometro then

begin

c := c +1 ; 

if c= 10 then

begin

m = null ;

send (b_medidor, m) ;

send (b_cronometro, m) ;

end ;

end 

else

if m.id = cronometro then

imprime 10 / (m.tiempo / 60)

else

imprime ( combustible * 10)

until false ;

end ;

{Programa principal}

Crear (b_ordenador) ;

crear (b_cronometro) ;

crear (b_medidor) ;

crear (b_tacometro) ;

c : = 0 ;

parbegin ;

tacometro ;

cronometro ;

medidor ;

ordenador ;

parend ;

END.

Ej .- Hay 4 niños y su madre. Inicialmente los niños se encuentran jugando, cuando tene hambre recurren a un plato y cogen una porción de queso, duermen 30 unidades de tiempo y vuelven a sus juegos.

Si un niño encuentra el plato vacio recurre a la madre.

La función de la madre es despertar a los niños de su sueño y reponer el plato con 4 porciones de queso cuando sea necesario.

Program queso ;

const N = 10 

type mensaje = RECORD

id :integer ;

comer, dormir :boolean ;

end ;

buzon = buffer [1 .. n] of mensaje ;

var

b_madre : buzon

b_niño : array [1..4] of buzon ;

b_despierta array [1..4] of buzon ;

plato : semaforo ;

q : 0..4 ;

a :integer ;

Procedure niño (i :integer) ;

var

m,n : mensaje ;

begin

while true do

begin

{ Juega}

wait (plato) ;

if q= 0 then

begin

m.id := i ;

m. comer := true ;

send (b_madre, m)

recive (b_niño[i], n) ;

end ;

q = q-1 ;

m.comer := false ;

signal (palto) ;

{ Comer}

m.id := i ;

m.dormir := true ;

send (b_madre, m) ;

recive b_niño [i] , n) ;

m.dormir := false ;

end ;

end ;

Procedure madre ;

var

i : entero ;

m,n,d : mensaje ;

begin

while true do

begin

recive (b_madre, m) ;

i := m.id ;

if m.comer := true  then

begin

wait (plato) ;

q := 4 ;

signal (plato) ;

n.id := i ;

send (b_niño[i],n ) ;

end ;

if m. dormir := true then

begin

d.id := i ;

send (b_despierta[i], d) ;

end ;

end ;

end ;

Procedure despertar (i :integer) ;

var

n.m : mensaje ;

t, tiempo : integer ;

begin

while true do

begin

recive (b_despierta [i], d) ;

t := 0 ;

tiempo := gettime ;

repeat

t := t+1 ;

until t = tiempo + 30 ;

n.id := i ;

send (b_niño[i], n) ;

end ;

end ;

{Programa Principal}

Begin

for a := 1 to 4

begin

crear (b_despierta[a]) :

crear (b_niño [a]) ;

end ;

crear (b_madre) ;

q= 0 ;

signal (palto) ;

parbegin

niño (1..N) ;

despierta (1.. N) ;

madre ;

parend ;

END.

Ej .- En una estación de autobuses Una persona se dirige a la ventanilla para conseguir un billete. Se dirige a un autobus y se sube a el . En el caso de que dicha persona complete las 45 plaza envia un mensaje a controlador que da salida al autobus y envia a otro vacio.

Ej .- Se desean hacer las siguientes transformaciones en un fichero de texto.

Procedimiento lee y convierte ninusculas a mayusculas.

Procedimiento y sustituyento blancos por *

Procedimiento que escribe fichero en lineas de 13 columnas.

Ej .- Un establecimiento tiene 20 sillas. Cuando llega un cliente observa si hay una silla libre. Si la hay indica el nº de silla y se siente.

Cliente llama a Romualda para que el sirva la comida. Si no espera en la salida.

Cliente come sin parar y deja la silla libre ;

Llama a Romualdo para que le cobre la comida.

Si no hay clientes Romualdo y Romualda duermen.

Program comidas ;

type

silla = 1..20 ;

mensaje = RECORD

comer, cobrar : boolean ;

end ;

b_silla : array [1 .. 20] of silla ;

b_mensaje = array [1.. N] of mensaje ;

var

silas : b :silla ;

b_R, b_H , B_cliemte : b_,mensaje ;

Procedure R

var

m :mensaje ;

begin

while true do

begin

recive (b_cliente, m) ;

if (m.cobrar) then

{ Cobrar}

send (b_cliente, m) ;

end ;

end ;

Procedure H ;

var

m :mensaje :

begin

while true do

begin

recive (b_cliente, m ) ;

if (m.comer) then

{Servir comida}

send (b_cliente,m) ;

end ;

end ;

Procedure cliente ;

var

m:mnesaje ;

n : sillas ;

begin

recive (b_silla, n) ;

m.comer := true ;

send (b_H, m) ;

recive (b_h, m) ;

{Comer}

m.comer := false ;

send (b_silla, n) ;

m.cobrar := true ;

send (b_R, m) ;

recive (b_R,m) ;

end ;

begin

{Inicializar buzones}

{Mirar buzones}

TEMA 5.

SEGURIDAD Y PROTECCION

El campo de la seguridad abarca controles fisicos , administrativos y automatizados, y tenemos que distinguir entre protección y seguridad.

•       La protección va más orientada a objetos informaticos ( Hardware y Software) y datos :

El concepto de seguridad es mas amplio , abarca :

•       Instalaciones (incendios, terremotos, catastrofes ...)

•       Robo.

•       Averias..

Tambien existen otros 2 conceptos que son :

•       Mecanismos.- Implementación de las politicas.

•       Politicas .- Diseño y directrices de seguridad.

De hecho, no tiene que ser el mismo sujeto el que diseña la politica y el que implementa el mecanismo de esa misma politica.

Amenazas a la seguridad.

Para comprender los diversos tipos de amenazas a la seguridadm hace falta disponer de una definición de los requisitos para la seguridad :

•       Confidencialidad .- Exige que la información de un sistema de computadoras sea accesible para un sistema de lectura, solo para los grupos autorizados.

•       Integridad.- exige que los elementos de un sistema e computadoras puedan ser modificados solo por los grupos autorizados.

•       Disponibilidad.- exige que los elementos de un sistema de computadoras esten disponibles solo para los grupos autorizados.

Tipos de amenazas à Estas se pueden dividir en cuatro categorias :

•       Interrupción .- Supone la destrucción de un elemento del sistema o bien se hace inasequible o inutil.

•       Interceptación .- Una parte no autorizada, consigue acceder a un elemento del sistema. La parte no autorizada puede ser un programa o una persona (capturar información de un red a traves de interceptación de linea telefonica, copia ilicita de archivos o programas.

•       Modificación .- Una parte no autorizada no solo consigue acceder, sino que además modifica una parte del sistema.

•       Invención.- Supone además de un acceso no autorizado, insercción de elementos falsos en el sistema.

Elementos de un sistema de computadoras.

  Los elementos de un sistema de computadores pueden clasificarse en hardwarem software, datos, lineas de comunicación Y las amenazas a las que pueden ser sometidos cada uno de ellos son :

•       Hardware .- Las amenazas son siempre de disponibilidad. Pueden ser robos, inutilización de equipos, o dejar equipos fuera de servicio.

•       Software .-

•       Disponibilidad.- Eliminación de programas o denegación de acceso a los usuarios.

•       Confidencialidad.- Realización de copias no autorizadas del software.

•       Integridad .- alteración de un programa en su funcionamiento haciendolo fallar o provocando resultados erroneos.

•       Datos .-

•       Disponibilidad .- Eliminación de archivos o denegación de acceso a usuarios.

•       Confidencialidad.- Lecturas de datos no autorizadas. Una analisis de datos estadistico que revele datos ocultos.

•       Integridad .- Modificación de archivos existentes o invención de nuevos archivos.

•       Lineas de comunicación .-

•       Disponibilidad .- destrucción o eliminación de mensajes, dejando no disponibles lineas de comunicación y redes.

•       Confidencialidad.- Lectura de mensajes. Observación de la muestra de trafico de mensajes.

•       Integridad.- Mensajes modificados retardados, reordenados, o duplicados. Invencion de mensajes falsos.

Protección.

Principios de diseño .- Se identifican una serie de principio de diseño de medidas de seguridad para las diversas amenazas a los sistemas informáticos. Entre estos principios se incluyen los siguientes :

¨    Minimo privilegio .- Todos los programas de usuario del sistema deben operar utilizando el menor número de privileos necesarios para completar la labor. Los derechos de acceso deben adquirirse solo por permiso explicito ; por omisión deberia ser ‘Sin permiso'.

¨    Ahorro de mecanismos .- Los mecanismos de seguridad deben ser tan pequeños y simples como sea posible, , ayudando en su verificación. Esta exigencia suele suponer que deben ser una parte integral del diseño, más que mecanismos añadidos a diseños existentes.

¨    Aceptación .- Los mecanismos de seguridad no deben interferir excesivamente en el trabajo de los usuarios, mientras cumplen al mismo tiempo las necesidades de aquellos que autoricen el acceso. Si los necanismos son dificiles de usar o no se usaran o se hará de forma incorrecta.

¨    Mediación total .- Cada acceso debe ser cotejado con la información de control de acceso, haciendo muchos mas incapie en accesos que se salen de la operación normal.

¨    Disño abierto.- La seguridad del sistema no debe depender de guardar en secreto el diseño de sus mecanismos. De esta forma, los mecanismos podrám ser revisados por muchos expertos y los usuarios podrán depositar una alta confianza.

Protección de memoria.

 

  Es fundamental en un entorno de multiprogramación no solo en cuanto a seguridad sino tambien en cuanto a funcionamiento correcto de los procesos.

Un proceso no puede escribir en la zona de memoria de otro proceso, pues este segundo proceso no funcionaría bien.

Es separación de procesos es facil de hacer con un sistema de memoria virtual.

La segmentación, paginación o la combinación de ambas son un metodo eficaz para la protección de memoria principal.

Ofrecen sistema de seguridad ya que el SO debe asegurar que cada registro o pagina sea accesible unicamente por el proceso que la tiene asignada. No puede haber entradas duplicadas en las tablas de paginas o segmentos.

Protección orientada al usuario.

El control de acceso al usuario se leconoce con Autentificación, la tecnica más usada consiste en adjudicar al usuario un nombre de lógica o identificador y un pasword o contraseña asociada a ese nombre

Los primero que se comprueba es que ese usuario pertenece a la lista de usuarios que tienen acceso al sistema. (Hay una tabla en todo SO con los usuarios )

El pasword asegura que ningun otro usuario entre en el sistema con el nombre de otro usuario.

Solo el propio usuario conoce su contraseña y la combinación de ambos (Nombre y pasword) permiten la entrada. Nadie debe saber la contraseña de un usuario. Estas se encuentran en un fichero cifrado.

Si se borra algunos de estos dos ficheros , ningun usuario podrá entrar al sistema. Y la unica forma es reinstalar el sistema.

Si un usuario pierde su clave se le asigna una nueva, no se puede obtener un antiguo pasword de ningun modo.

El problema del control de acceso a usuarios se complica en una red de comunicaciones. El dialogo de conexión debe realizarse a traves del medio de comunicación y las escuchas se convierten en una amenaza potencial.

El control de acceso al usuario en entornos distribuidos puede tener un enfoque centralizado o no centralizado.

Enfoque centralizado.

La propia red proporciona un servicio de conexión para determinar a quien se le permite usar la red y a quien se le permite conectarse.

•       Servicio de identificación.

•       Servicio de autentificación

•       Define para que se puede acceder a un conjunto de elementos ( Dominio).

Enfoque no centralizado.

La red es considerada como un enlace transparente de comunicaciones. Es el servidor el que lleva a cabo la identificación de usuarios y la identificación de permisos.

Hay otros sistemas que establecen otros sistemas de protección.

•       A nivel de Red.

•       A nivel de Servidor.

El SO controla el acceso a los recursos a traves de la matriz de acceso. Esta matriz define para los diferentes objetos diferentes dominios y para cada objeto en cada dominio definimos una serie de atributos.

Los elementos basicos del modelo son :

•       Sujeto .- Una entidad capaz de acceder a los objetos. En general, el concepto de sujeto es equiparable con el de proceso. Cualquier usuario a aplicación consigue acceder en realidad a un objeto por medio de un proceso que representa a un sujeto o aplicación.

•       Objeto .- Cualquier cosa cuyo acceso debe controlarse.

•       Derechos de acceso .- La manera en que un sujeto accede a un objeto.

Una dimensión de la matriz consta de los sujetos identificados que pueden acceder a los datos. Normalmente esta lista consta de usuarios individuales o grupos de usuarios aunque tambien se puede controlar el acceso a instalaciones en su conjunto.

La otra dimensión enumera los objetos a los que se puede acceder.

Cada entrada de la matriz indica los derechos de acceso de un sujeto a un objeto.

En la practica las matrices de acceso suelen estar dispersas y se implementan por descomposiciones en una o más dimensiones. La matriz se puede descomponer en columnas, obtenendose Listas de control de acceso. Asi pues para cada objeto una lsita de control de acceso (ACL) indica los usuarios y sus derechos de acceso.

Por la descomposición por filas se obtiene Etiquetas de Capacidades, que especifica los objetos y las operaciones autorizadas para un usuario.

No es el propio proceso el que consulta la tabla sino que lo hace el SO. Pudiendo ser este el unico que accede a los datos protegidos.

Mecanismo Llave - Cerradura.

La cerradura son una lista de bits que se asignan a los Dominios.

El proceso posee ciertas llaves y podrá acceder a los dominios para los que tenga llave. El dominio es el que pone los derechos de acceso al objeto.

INTRUSOS .

Es una de las dos amenazas más conocidas a la seguridad es el intruso ( la otra son los virus), conocido en general como pirata (Hacker o Cracker).

Existen dos tipos de ataques de intrusos :

•       Benignos à Siemplemente desea curiosear las interredes y curiosear lo que hay ahí fuera.

•       Malignos à Individuos que intentan leer datos privilegiados, realizar modificaciones no autorizadas a los datos o trastornar el sistema. ( Reciben dinero por conseguir datos cara al espionaje industrial o para destruir datos de empresas).

En gran parte se han facilitado estos accesos no autorizados por la arquitectura de las redes Cliente - Servidor , la tendencia hacia la globalización y la curva tan inclinada de aprendizaje de los piratas.

Caracteristicas del pirata.

•       Consume el número necesario de horas que hagan falta para abrir una puerta.

•       Afan de notoriedad. Difunden todo lo que consigen.

Las diferentes empresas se unieron en una cooperativa llamada Equipo de Respuesta ante Emergencias en Computadoras. (CERT). Reunian información sobre los puntos debiles de los sistemas para informar a los administradores de sistemas y ayudar a establecer nuevas medidas de seguridad.

Si esta información se distribuye por la red, los piratas tenían acceso a los informes del CERT antes que los propios administradores de los sistemas de las empresas.

Técnicas de intrusión.

Las principales tecnicas utilizadas para conectarse son :

•       Probar las contraseñas por omisión que se emplean en cuentas standard que se suministran con el sistema. El administrador debe cambiar estas contraseñas no pudiendo dejarlas abiertas.

•       Probar exaustivamente contraseñas cortas.

•       Probar las palabras del diccionario y todas las matriculas de coche. (Programa comercial que las quequea en tres minutos).

•       Investigar todos los datos personales del administrador e introducirlos.

•       Introducir un Caballo de Troya que capture contraseñas.

•       Intervenir la linea.

Estrategias a seguir para evitar el pirateo.

•       Cifrado de claves.

•       Utilizar contraseñas sin referencia al usuario.

•       Proteger el fichero de claves.

Los Caballos de Troya se pueden introducir de diferentes formas (La mas significativa à Juegos publicos en Internet, que cambian los permisos y desprotegen)

La protección más utilizada es la Protección por contraseña y esta debe estar cifrada.

•       Ejemplo de cifrado de claves en UNIX.

Cada usuario elige una contraseña de hasta 8 caracteres de longitud. Esta es convertida a un valor de 56 bits empleando el ASCII de 7 bits. Que sirve como clave de rutina de cifrado. La rutina de cifrado esta basada en el algoritmo Estandar de Cifrado de Datos.

El DES se modifica mediante un valor base de 12 bits, este valor esta relacionado con el momento en que se asigna la contraseña al usuario. El algoritmo DES modificado ejecuta con una entrada de datos consistente en un bloque de ceros de 64 bits sobre el que actuan la base y la clave de cifrado . La salida del algoritmo sirve como entrada para un segundo cifrado. Este proceso se repite un total de 25 veces. La salida de 64 bits resultante se traduce entonces a una secuencia de 11 caracteres . El archivo de contraseñas guarda la contraseña cifrada junto a una copia en claro de la base para el ID de usuario correspondiente.

 (Se considera un sistema poco seguro).

El averiguador de contraseñas más rapido fue encontrado en Internet. Y sometido a diversas pruebas dio como resultado 800.000 cifrados por segundo en una maquina de de 128 nodos y 14,4 millones de cifrados en una máquina de 1024 nodos.

 

Los claves que más frecuentemente se averiguan son las que corresponden :

•       Nombres de usuarios.

•       Nombres de mujeres.

•       Arte y Leyenda.

•       Nombres de asteroides.

•       Terminos del diccionario

•       Nombres de dibujos animados.

•       Nombres de famosos.

Es decir, contraseñas que NUNCA deberían ser utilizadas.

Se recomiendan las siguientes estrategias para la elección de contraseñas.

•       Introducir al usuario a contraseñas legibles encriptadas.

•       Contraseñas generadas por el computador. Poco efectivo. Usuario no lo coge nunca y olvida las claves.

•       Inspección reactiva y proactiva :

•       Reactiva .- Incorparan en el sistema un propio averiguador de claves que chequea periodicamente para encontrar contraseñas facilmente adivinables. El sistema cancela todas las contraseñas adivinables y se lo notifica al usuario.

•       Proactiva .- Al usuario se le permite elegir su propia contraseña, sin embargo, en el momento de la elección el sistema conmprueba si la contraseña es permisible, y si no lo es, la rechaza.

¨    Una herramienta fundamental en en la detección de intrusos en el sistema es el Registro de auditoría.

•       Nativos (Generales) à Son como las cajas negras de los aviones. Almacenan todas las operaciones que se realizan en el sistema. De aquí se sacan datos cuando se produce una avería, intentos de penetración , etc.

Que absolutamente todo en los Registros Historicos.

•       Especificos à Un formato de este tipo sería una serie de campos que incluyan sujeto, acción, Objeto, Condición de excepción, utilización de recursos y marca de tiempo.

VIRUS Y AMENAZAS AFINES .

Los tipos de ataque más sofisticados de ataque a los sistemas informaticos son los presentados por programas que se aprovechan de los puntos vulnerables de los mismos.

Entre los que necesitan un programa anfitrón estan las tranpillas, las bombas logicas, los caballos de troya y los virus.

Entre los independientes estan las bacterias y los gusanos.

De estos , los que no se reproducen son las trampillas, bombas lógicas, y los caballos de troya. Y los que se reproducen son los virus, las bacterias y los gusanos.

•       Bacterias .- Son programas que consumen recursos del sistema reproduciendose a si mismo y agotando así los recursos disponibles. (Capacidad de procesador, memoria, disco ... ) privando al usuario de recursos.

•       Bomba lógica .- estan incrustados en un programa y saltan cuando se cumple una condición, ejecutando acciones no autorizadas. Siempre esta preparado para destruir información.

•       Trampillas .- Son puntos de entrada que deja el programador del sistema para acceder fuera de los metodos usuarios de autentificación.

•       Camballos de Traoya .- Spn programs ingeniosamente colocados para que si el usuario los ejecutam poder acceder a los privilegios de dicho usuario. Su intención es capturar información, pero tambien pueden ocasionalmente destruirla.

•       Virus .- Codigo incrustado en un programa, que hace que se ejecute una copia de si mismo en uno o más programas. Además de propagarse puede realizar alguna función no deseada.

•       Gusanos .- Programas carcteristicos de redes. Infectan un nodo a traves de una conexión (Normalmente por E-Mail) y realiza acciones no deseadas . Son dificiles de detectar. Se pueden ejecutar remotamente. Existe la posibilidad de conectarse remotamente y propagarse remotamente.

Método de programación de virus.

Un virus normalmente se programa en lenguaje ensamblador.

•       Encontrar la primera instrucción del programa.

•       Sustituirla por un salto a la posición de memoria siguiente a la última del programa.

•       Insertar una copia del código del virus en dicha posición

•       Hacer que el virus simule la instruccón sustituida por el salto.

•       Saltar a la siguiente instrucción del programa anfitrión

•       Terminación del programa anfitrión.

¨    Los viruss pasan pro una fase latente, una fase de propagación, una fase de activación y una fase de ejecución.

Algunos Virus.

 

n     Cerebro Pakistaní .- De origen Pakistaní. Infecta sector de arranque del HD y se reproduce infectando el BOOT de los Floppy introducidos. Modifica la FAT diciendo que dichos sectores estan defectuosos.

n     Jerusalen .- Infecta programas ejecutables. Reside en memoria. Destruye FATS.

n     LEHIGH .- Infecta SO introduciendose en el procesador de ordenes. Accede al procesador de comandos de las distintas instrucciones. Lleva un contador , cuando esta infectado incrementa el contador . Cuando el contador llega a 10 destruye todos los datos del disco duro.

n     Alameda .- Infecta el sector de arranque del sistema. Depues infecta cualquier disco flexible insertado dureante el nuevo arranque y destruye la ultima pista del disco.

n     Virus de cuenta .- Diseñado para reproducirse un número determinado de días. Seguido por varios días de latencia. Tras ello, cuando el usuario intente guardar información en un archivo el virus se lo impedirá y hundirá el sistema.

n     NVIR .- Se presenta en varias formas. Se han detectado por lo menos una docena. Invade el archivo de sistema, y todas las aplicaciones lanzadas a continuación son infectadas.

Tipos de virus :

•       Parasitos.

•       Residentes en memoria.

•       Del sector de arranque.

¨    Virus clandestino à Virus que utilizan compresión para que el programa infectado tenga exactamente la misma longitud que una versión no infectada.

¨    Virus polimorfo à La ‘Firma ‘ del virus varia con cada copia. Para lograr esta variación el virus puede insertar eleatoriamente instrucciones superfluas o intercambiar el orden de las instrucciones independientes. Una parte del virus, generalmente llamada motor de mutación , crea una clave de cifrado aleatoria para cifrar el resto del virus.

Métodos AntiVirus.

Incluyen 3 tipos o funciones de combatir los tipos :

•       Detección.

•       Identificación.

•       Eliminación.

¨    1ª Generación .- Rastreadores simples. (Requiere una firma del virus para identificarlo. Limitados a la detección de virus conocidos.)

¨    2º Generación .- Rastreadores heuristicos. ( Rastreador emplea reglas euristicas para buscar infecciones posibles de virus. Un tipo de tales rastreadores buscan trozos de código que suelen estar asociados con código.)

¨    3ª Generación .- Trampas de actividad ( Son programas residentes en memoria que identifican un virus por sus acciones más que por la estructura de un programa infectado.

¨    4ª Generación .- Protección completa ( Son paquetes que constan de una gran variedad tecnicas de antivirus.

TEMA 6

SISTEMAS DISTRIBUIDOS.

Introducción.

La tendencia reciente de todo sistema informatico es distribuir la computación entre varios microprocesadores fisicos.

Existen dos esquemas :

Fuertemente acoplados à Los micros comparten memoria y reloj. La comunicación tiene lugar por medio de memoria compartida.

Debilmente acoplados à Los micros no comparten ni memoria ni reloj, los procesos se comunican por medio de mensajes a traves de lineas de comunicación. (buses, lineas telefonicas, etc). Estos sistemas se conocen habitualmente como sistemas distribuidos.

Hay cuatro motivos importantes para la implantación de estos sistemas :

1)   Compartición de recursos à Diferentes procesadores comparten recursos asociados a otros micros.

2)   Aceleración de la computación à Si un proceso se divide en hilos y cada hilo se ejecuta en un microprocesador diferente, se acelera el calculo.

3)   Fiabilidad à Si un de los puestos falla, los restantes absorven la carga que este tinía asociada, y siguie el funcionamiento del sistema. Solamente produce una ralentización ya que la carga es soportada en un microprocesador menos. Cuando se recupera la anomalía, el sistema vuelve a distribuir la carga entre todos los micros.

4)   Comunicación à Los usuarios tiene la posibilidad de intercambiar información mediante correo electronico. Cada usuario tiene su propio buzón y puede actuar sobre su correo.

Topología.

1)   Conexión total à Cada instalación está conectada directamente con todas las instalaciones del sistema. En este sistema los mensajes se envian con rapidez ya que solo tienen que viajar por un unico enlace.

2)   Conexión parcial à Existe enlace directo entre algunos pero no todos.Un mensaje es posible que tenga que pasar por varias instalaciones intermedias.

3)   Jerarquía à Instalaciones se organizan como un arbol. Cada instalación tiene solo un padre (excepto el raiz) y varios hijos.

4)   Red en estrella à Una de las instalaciones del sistema esta conectada con todas las demás y ninguna otra instalación esta conectada con las otras.

5)   Red en anillo à Cada instalación esta conectada fisicamente a otras dos. El anillo puede ser unidireccional o bidireccional(Doble anillo). En una red bidireccional deben fallar los dos enlaces para que se particione la red, sin embargo, en una red unidireccional si falla una instalación se particiona la red

6)   Canal multiacceso (Conecxión en BUS)à Existe solo un enlace compartido. Todas las instalaciones del sistema se conectan directamente a ese enlace. Si falla una instalación esta no afect a al comunicación con las demás sin embargo si falla el enlace la red que completamente particionada.

SISTEMAS DISTRIBUIDOS DE ENFOQUE CENTRALIZADO.

Cada puesto mantiene su propio sistema de ficheros locales, y hay un puesto centralizado para los ficheros compartidos o en un sistema totalmente distribuido cada puesto mantiene su sistema de ficheros local pero puede ser accedido por otros puestos (comparten recusrsos y datos).

Migración de procesos.

La migración de una parte suficiente del estado de un proceso desde una máquina a otra para que el proceso pueda ejecutarse en la máquina destino. Incluye la capacidad de expulsar un proceso de una máquina y reactivarlo más tarde en otra máquina.

La migración de procesos es deseable en los sistemas distribuidos por una serie de razones :

•       Compartición de carga à Traslado de procesos desde sistemas muy sobrecargados a otros sistemas menos sobrecargados. Los datos empiricos sugieren una mejora del redimiento del sistema.

•       Rendimiento en las comunicaciones à Los procesos que interactuan con mucha frecuencia pueden moverse a un mismo nodo para reducir el coste de las comunicaciones durante su interacción

•       Disponibilidad à Los procesos que duran mucho tiempo deben poder sobrevivir a los fallos del sistema. Para ello debe obtener un aviso previo de estos fallos, que debe ser proporcionado por el SO.

•       Utilización de capacidades especiales à Un proceso puede moverse para sacar maximo partido a las capacidades que solo posee un determinado nodo ejecutar parte del proceso en este nod y posteriormente migrar al nodo anterior para continuar ejecutandose.

Mecanismos de migración.

Quien inicia la migración de un procesos depende del objetivo del servicio de migración. Si el objetivo es equilibrar la carga algún modulo supervisor de la carga del sistema operativo es normalmente el responasable de decidor cuando tendra lugar la migración.

Si el objetivo es llegar hasta unos recursos determinados, el procesos puede emigrar por si mismo cuando surja la necesidad.

¿Que es lo que migra ?.

Cuando un proceso migra hace falta destruirlo del sistema origen y crearlo en el destino. Debe moverse la imagen del proceso, que por la menos consta del PCB y debe actualizarse cualquier enlace entre este y otros procesos.

El movimiento del PCB es sencillo, la dificultad se encuentra en el espacio de direccionamiento del proceso y los archivos abiertos que tenga asignados.

Considerese primero el espacio de direcciones del proceso y supongase que esta utilizando un esquema de memoria virtual. Poeden surguir dos estrategias :

•       Traferir todo el espacio de direcciones en el momento de la migración.

•       Transferir solo aquella parte del espacio de direcciones que reside en memoria principal. Cualquiere bloque del espacio de direcciones adicional sera transferido unicamente bajo demanda. Necesita que la máquina de origen siga involucrada en la vida del proceso

Si los procesos se estructuran el hilos y la unidad elemental de migración es el hilo y no el proceso la segunda estrategia parece ser la mejor.

Los archivos solo se transfieren en caso de que el proceso emigrado realice una solicitud de acceso.

Si se permite la utilización de cache se presentra una complicacion más, ya que un archivo abierto se encuentra en dos lugares a la vez ( mem principal y cache) y al producirse la emigración de un proceso podría provocar que un fichero se encontrara disponible en dos máquinas a la vez.. Por ello en la migración de procesos nunca se utiliza cache y siempre se acceden los datos desde disco.

Mensajes y señales.

Los mensajes pendientes hay que redirigirlos al nuevo destino. Durante un tiempo hay que guardar información de la nueva dirección en el emplazamiento original.

Automigración à Proceso que requiere recursos de otro sistema y gestiona su propia migración.

•       selecciona una máquina destino y envia un mensaje de tarea remota. El mensaje lleva una parte de la imagen del proceso e información de los archivos abiertos.

•       En el receptor, un proceso servior del núcleo crea un hijo y le cede esta información.

•       El nuevo proceso extrae los datos, los argumentos, la información del entorno y de la pila que necesita para completar su ejecución. El código del programa se copia si se ha alterado y si no se pagina por demanda en el sistema de archivos global.

•       Se indica con una señal al proceso originario que la migración ha terminado. El proceso original de la máquina origen se destruye.

Si la migración la inicia otro proceso el enfoque consiste en copiar la imagen del proceso y todo su espacio de direccionesa un archivo. Una vez creado este archivo el proceso original se destruye y se copia el archivo original a la máquina destino, y a partir de aquí se vuelve a crear el proceso en la máquina destino a partir de la información del proceso.

Negociación de la migración.

La decisión de migrar en algunos casos la toma una unica entidad. Si esa decisión es distribución de carga es el SO el que toma la decisión y si no es el propio proceso.

En algunos sistemas se permite que el destino designado participe en la decisión de si acepta o no la migración, entre otras cosas para conservar el tiempo de respuesta a los usuarios. Un usuario de un puesto de trabajo puede sufrir una degradación notable del tiempo de respuesta si hay procesos que emigran a ese puesto de ususario incluso si esto produce un mejor equilibrio global en el sistema.

Un mecanismo existente en el proceso de migración es el de la existencia de una utilidad iniciadora que coordina todas estas posibilidades . Esa utilidad es la responsable de la planificación a largo plazo y de la asignación de la memoria, con lo cual posee muchos datos que sirven para determinar si la migración es oportuna o no.

Este proceso iniciador recibe de cada nodo una estadistica de carga que le permite establecer si un proceso puede migrar o no.

Para ello suceden las siguientes etapas :

•       El iniciador que controla el sistema de origran (S) decide que un proceso (P) debe migrar a un sistema destino (D). Entonces envia un mensaje al iniciador de D solicitando la transferencia.

•       Si el iniciador de D esta preparado para recibir al proceso, devuelve un mensaje afirmativo.

•       El iniciador de S comunica su decisión el nucleo de S mediante una llamada a un servicio o un mensaje al nucleo de la máquina S.

•       El nucleo de S se ofrece entonces para enviar el proceso a D, ademá incluye estadisticas sobre P.

•       Si D anda escaso de recursos puede rechazar la oferta. En otro caso el nucleo de D propone la oferta a su iniciador. (Se incluye la misma información recibida de S).

•       La decisión del iniciador es comuniicada a D mediante una llamada.

•       D reserva los recursos necesarios para evitar probleas de interbloqueo y control de flujo y envia una señal aformativa a S.

•       En caso de que P tuviera enlaces con otros procesos estos enlaces son actualizados, en la máquina destino.

Desalojo.

Comprede 2 funciones :

¨    Rechazar una migración.

¨    Fallo del nodo donde se encuentra.

Elmentos del mecanismo son los siguientes :

•       Un proceso supervisor en cada nodo que lleve la cuenta de la carga actual para determinar cuando se pueden aceptar nuevos procesos extranjeros. Si el supervisor detecta actividad en la consola del puesto de trabajo ejecuta un procesos de desalojo para el proceso extranjero.

Cuando se deloja un proceso este puede volver al nodo origen o bien puede migrar a otro nodo que etuviese disponible.

•       Aunque la operación puede durar un tiempo el proceso es suspendido en ejecución para no reducir la capacidad de calculo del host-

•       Si el proceso es desalojado todo su espacio de direcciones de memoria es desalojado con el y transferido al nodo de origen

Tranferencias apropiativas y no apropiativas.

No apropiativa à Involucra solo al proceso que no ha comenzado su ejecución y por tanto no se necesita transferir el estado del proceso.

Apropiativa à Consiste en la tranferencia de un proceso parcialmente ejecutado o al menos cuya creación se haya completado.

Estados Globales Distribuidos.

Canal .- Existe un canal entre dos procesos siempre que intercambian mensajes. Se va a consisderar un canal como de un unico sentido, de este modo si dos procesos intercambian mensajes se necesitaran dos canales, uno para cada dirección de la transferencia.

Estado .- De un proceso es la secuencia de mensajes enviados y recibidos por los canales de un proceso.

Instantanea .- Registro el estado de un proceso. Cada instantanea incluye un registroincluye un regoistro de todos los mensajes enviados y recibidos por todos los canales desde la instantanea anterior.

Estado global .- El estado combinado de todos los procesos.

Instantanea distribuida .- Un conjunto de instantaneas, una para cada proceso.

ALGORITMOS DE EXCLUSION MUTUA

Enfoque centralizado.

Se elige un proceso como proceso coordinador, cuando un proceso quiere entrar en su sección critica, manda un mesaje al proceso coordinador. El proceso coordinador mira una cola y si no hay peticiones en la cola, le envia un mensaje de acceptación y entonces el proceso entra en su sección critica..

Cuando finaliza la ejecución de la sección critica, envia al proceso coordinador un mensaje de Liberación.

Si cuando el coordinador exaamina la cola, hay peticiones pendientes :

n     Coloca la petición en la cola.

n     Sirve las peticiones en orden.

Este proceso cumple la exclusión mutua, y asegura que no se pueden producir interbloqueos e inanición.

Tiene 2 inconvenientes :

¨    Si el proceso coordinador se cae, es necesario lanzar un proceso de elleción de un nuevo coordinador. Se copia la cola de petieciones al nuevo ccordinador y se continua con la ejecución.

¨    Como todos los mensajes de solicitud van a parar al coordinador, se produce un acceso de trafico de mensajes en torno al coordinador, lo que puede producir un cuello de botella, ralentizando el funcionamiento del sistema.

Enfoque totalmente distribuido.

Todos los nodos disponen de una cantidad igual de información. Cada nodo tiene una definición parcial del sistema. Todos influyen igualmente en la decisión final de entrada a al sección critica. La falla de un nodo, no provoca en ningun caso el fallo del sistema.

La dificultad principal es que no existe un reloj de tiempos, porque no sabemos como ordenar los sucesos para saber cual de ellos va a entrar primero.

Lamport elavoró un metodo de ordenación de sucesos en un sistema distribuido sin necesidad de utilizar relojes fisicos, conocido como Registros de tiempo o Marcas de tiempo.

•       Se establecen una serie de controladores locales. De forma que el nodo i mantendra un controlador Ci que hara las veces de reloj.

•       Cada vez que un nodo transmita un mensaje se incrementará su controlador en 1.

•       El mensaje envia los siguientes para metros (m, Ti,i ) :

•       m à contenido del mensaje.

•       Ti à Marca de tiempo del mensaje (Ci).

•       i à Identificador del nodo.

•       Cuando se recibe el mensaje el sistema receptor j pone su reloj a uno más que el maximo de su valor actual y la marca de tiempo entrante.

Cj = 1 + MAX [Ci, Cj]

•       En cada nodo la ordenación de sucesos queda determinada según las normas siguientes :

•       Para los mensajes x del nodo i y los y del nodo j se dice que x precede a y si se cumple una de las suientes condiciones :

•       Si Ti < Tj

•       Si Ti = Tj e i< j

La primera solución se debe a Lamport utilizan el esquema de Registros de tiempo.

Cuando un proceso quiere entrar en su sección critica envia n-1 mensajes a todos los procesos. Estos le envian n-1 mensajes de respuesta bien de aceptación o bien de solicitud. Despues de recibir los n-1 mensajes examina una cola, si hay peticiones las ordena con la suya propia . Si es la primera en la cola entra en la sección critica, y si hay una petieción de prioridad superior no puede entrar.

Cuando el proceso entra en la sección critica envia n - 1mensajes a los demas procesos. Los demás proceos le envian n-1 respuestas indicando aceptación o bien solicitud.

Cuando ha recibido los mensajes observa la cola y si hay peticiones las ordena con la suya propia, si la suya es la primera entra en la sección critica en cuyo caso al terminar envia un mensaje de liberación. (Quitar la petieción del buzón).

•       Este algotirmo requiere 3* (n-1) mensajes para una solicitud de entrada.

Algoritmo de Ricart.

Reduce el número de mensajes a 2 * (n-1)

•       Cuando un proceso quiere entrar en su sección critica, envia un mensaje de solicitud, a todos los demás procesos. (n-1)

•       El proceso que recibe el mensaje se encuentra en 1 de estos 3 estados :

•       No quiere entrar en su seccion critica. Envia mensaje de aceptación.

•       esta en ese momento en su sección critica. Demora un mesaje de aceptación hasta que salga de su sección critica.

•       Tiene una petición pediente de entrada en su sección critica. Copara la marca de la petición con la suya propia. Si su marca de petición es superior a la que ha recibido en el mensaje de petición no atiende la petición hasta que no ah salido de su sección critica, pero si es inferior, envia un mensaje de aceptación y espera su turno.

•       Un proceso para entrar en su sección critica necesita n-1 mensajes de aceptación., si los recibe, es que todos estan de acuerdo.

•       Cuando sale de su seción critica libera el recurso enviando mensajes a cada petición pendiente.

El algoritmo cumple la exclusión mutua asegurando que no se producen interbloqueos ni tampoco inanición.

Inconveniente à

Hay que tener informados a todos los procesos que existen en el sistema, ya que si uno de los proceos cae, un proceso podría esperar indefinidamente por un mensaje que no va a producirse. Y si entra un nuevo proceso en el sistema, hay que notificarlo inmediatamente.

Paso de Testigo.

Hay que tener encuenta dos situaciones :

¨    Que los procesos formen algun tipo de anillo lógico o fisico.

¨    Que los procesos no formen algún tipo de anillo lógico o fisico.

Si forman anillo de alguna manera :

•       Simplemente se hace circular el testigo de unos a otros.

•       Si un proceos quiere entrar en su sección critica espera a que le llegue el testigo.

•       El proceso que tenga en su poder el testigo entrará en su sección critica.

Tiene el inconveniete del numero de mensajes.

No forman anillo fisico no logico :

•       Hay una serie de procesos cada uno con su correspondiente buzón.

•       Existe un testigo, que es un vector con tantos posiciones como procesos haya.

•       El vector contiene una serie de posiciones que se cooresponden con cada proceso, conteniendo el número de veces que un proceso ha entrado en su sección critica

•       El vector esta asociado al ultimo proceso que ha entrado en su sección critica.

•       El proceso examina la cola de petieciones y envia el vector a la primera que no este servida, previa actualización del testigo, las peticiones servidas son sacadas del buzón.

•       Proceso que recibe el testigo realiza el mismo proceso.

•       Los mensajes se ordenan en los buzones en el orden en que son recibidos.

GESTION DE ABRAZOS MORTALES.

En un sistema distribuido se utilizan los mismos mecanismos de detección, evitación y prevención de interbloqueo que en los sistemas centralizados.

Hay que hacer que al menos una de las condiciones no se cumpla y se elige la de la Espera circular.

Vamos a utilizar unas marcas o referencias de tiempo asociadas a cada proceso. Cada vez que se crea una marca se le asigna una marca o referencia de tiempo.

Hay 2 esquemas :

WAIT- DIE à Se basa en una tecnica no apropiativa. Si un proceso Pi solicita un recurso actualmente poseido por Pj , a Pi se le permite esperar solo si Pi tiene una marca de tiempo menor que la de Pj, ( Pi es más viejo que Pj) en caso contrario Pi muere. Y se reinicia con su misma marca de tiempo anterior.

P1, P2, P3

5, 10 , 15

P1 solicita un recurso de P2, P1 esperará

P3 solicita recurso que tiene P2 . P3 muere y se reinicia con su marca de tiempo anterior. (Libera todos sus recusrsos).

WOUND - WAIT à Se basa en un esquema apropiativo. P1 solicita recurso de P2, solo podrá esperar , en caso de que su registro de tiempo sea mayor que el de P2. En cualquier otro caso a P2 se le requisa el recurso y debe volver a solicitarlo.

PROBLEMA à Se pueden producir retrocesos innecesarios. Requisa recurso sin saber si va a existir abrazo mortal. Para evitarlo primero vamos a detectar el interbloqueo. Grafos de recursos.

Sistema distribuido :

•       Primero realiza llamadas locales a cada nodo.

•       Con los grafos locales ya se pueden detectar abrazos mortales en cada nodo.

•       Aunque no existan abrazos mortales en cada nodo puede que existan abrazos mortales entre varios nodos.

•       Hay que realizar un grafo global de espera.

Se peuden utilizar varios procedimientos :

Enfoque centralizado.

Hay un proceso coordinador que tiene el grafo global de recusrsos. El Grafo Global me va a decir si existen o no abrazos mortales.

Hay que decidir cuando se va a construir un grafo global :

1)   Siempre que un arco se invierte o elimina, en uno de los grafos locales.

2)   Periodicamente, cada vez que ocurra un determinado numero de cambios en los grafos locales.

3)   Siempre que el coordinador detecte anomalias en el sistema y precise invocar un algorotmo de detección de ciclos.

El grafo se construye de la siguiente forma :

•       El coordinador envia un mensaje a cada puesto del sistema.

•       Al recibir el mensaje, el puesto construye un grafo de espera local que refleja la instantanea de ese puesto.

•       A continuación se envia ese grafo al coordinador.

•       El coordinador construye entonces en grafo general y detecta si hay un ciclo en dicho grafo en cuyo caso procede a la suspensión de uno de los procesos implicados.

Enfoque jerarquico.

Los nodos estan organizados según una jerarquñia.

Cada nodo construye por tanto el grafo del subarbol que se encuentra debajo de él.

El nodo que se encuentra en la cabeza de la jerarquía pide el grafo local a los nodos que cuelgan de el y estos a su vez se lo piden a sus respectivos hijos.

Con la información que recibe se construye el grafo local al raiz, que es a su vez el que construye el grafo global definitivo.

Enfoque Totalmente Distribuido.

Cada nodo debería construir el grafo global. S existe abrazo mortal aparecerá un ciclo en por lo menos uno de los grafos parciles.

Robustez

Tiene que ver con los fallos hardware del sistema. Puede haber fallos en el enlace (Rotura fisica). Falos en microprocesadores y perdida de mensajes.

Para robustecer el sistema hay que detectar esos fallos, reconfigurar el sistema sacando fuera del servicio a los nodos implicados, recuperar todos los nodos y cada micro y volver a reconfigurar.

Para que un sistema sea fiable, además de poveer mecanismos de robustez, necesita mecanismo que permita al conjunto de procesos ponerse de acuerdo en un valor comun. Existen dos razones por las cuales no puede producirse ese acuerdo :

¨    Medio de comunicación defectuoso. Perdida o alteración de mensajes.

¨    Propios procesos podrían estar corrompidos. SU comportamiento podría ser impredecible.

•       Problema expresado como el Problema de los generales bizantinos. (pag 490)

ALGORITMOS DE ELECCION.

Cuando un coordinador de un sistema muere, es necesario la elección de un nuevo coordinador. Existen varios algoritmos :

BULLY (Sistemos no organizados en anillo).

Cuando un proceso envia un mensaje de entrada en la sección critica tiene garantizado que va a recibir respuesta an forma de mensaje de respuesta.

Un proceso, transcurrido tiempo de respuesta, en la entrada de su sección critica, no ha recibido el mensaje se supone que el proceso coordinador ha muerto.

El proceso pasa a ser coordinador si el resto de los procesos lo aprueban en un sistema. El proceso coordinador es el de mayor prioridad.

El proceso que detecta que no existe coordinador, envia un mensaje al resto de procesos enviando un nº de prioridad, pero solo envia mensajes a quellos procesos en la lista que figuran como de mayor prioridad que el. Si ninguno de los procesos responde tras un periodo de tiempo el proceso de proclama coordinadory envia mensajes al resto de los procesos indicando que es el coordinadory copia la cola de mensajes en su cola. Si no la puede recuperar los procesos repiten solicitudes al nuevo coordinador..

Si recibe respuesta, el proceso de mayor prioridad inicia un nuevo BULLY. En un sistema se inician tantos BULLYS como procesos de mayor prioridad detecte este proceso .

Este proceso se repite hasta que el proceso de mayor prioridad completa el algoritmo y se elige como coordinador.

Si el antiguo coordinador se recupera, vuelve a ser el coordinador e informa de ello a los demás procesos.

Mientra se producen los tiempos de BULLY, no hay entrada en la sección critica.

Algoritmo de Le Lana (Sistema estructura en anillo)

Hace que el proceso que detecta que se ha muerto el coordinador, inicia una lista enviando un mensaje a traves del anillo, a cada proceso cuando le llega la lista le añade su número de proceso y prioridad. Así recupera el anillo logico y asi se sabe que proceso esta activo en el anillo. El mensaje viaja por el anillo hasta que encuentra al proceso que inicio el mensaje el cual es el que determina cual es el proceso de mayor prioridad y encia mensajes al resto de procesos para informar de cual es el nuevo coordinador.

TEMA 7.

ESTUDIO COMPARATIVO DE SISTEMAS OPERATIVOS REALES.

Sistemas Abiertos (UNIX), Sistemas de Propietario (WINDOWS NT) , Grandes Sistemas (MVS)

INTRODUCCION.

•      WINDOWS NT à  Después de la tentativa de Microsoft con IBM (OS/2). Microsoft sigue la investigación de sistemas que aprovechen la potencia de los microprocesadores actuales y la facilidad de WINDOWS. Aparece WINDOWS NT como un entorno Multiterea monousuario.

Filosofía Cliente-Servidor .- Hace que una computadora personal con estaciones de trabajo (HOST) se unan para llevar a cabo una aplicaicón en particular.

A cada una se le asigna una parte del trabajo acorde con su capacidad.

Existen aplicaciones clientes standard que recogen las peticiones de cualquier servidor, las envian a ser ejecutadas en el servidor con capacidad para ello y las devuelve al servidor que emitió la petición.

El servidor puede ser local o remoto.

Todo esto se ejecuta a través de un sistema de mensajería.

NT ofrece la misma interface grafica de usuario que los anteriores WINDOWS. Su estructura interna se basa en el sistema MATCH (Donde se baso tambien UNIX en un principio). NT tiene todo lo bueno de UNIX y además pretende mejorar a este en cuestiones de seguridad implementadas desde el diseño. Acopla subsistemas con sus API´S que le permiten ejecutar aplicaciones de otros sistemas operativos.

Puede ejecutarse sobre varias plataformas hardware. Debido a una abstracción del hardware llamada HAL que se encarga de compatibilizar del Hardware, estableciendo correspondencia entre las ordenes del Kernel y las propias de una plataforma determinada.

Diseño de NT

•       Dentro del Modo Usuario à Diferentes clientes con sus diferentes API´S

Gran parte de la potencia de NT, proviene de la capacidad de ejecutaraplicaciones de otros sistemas operativos.

El sistema protegido presenta una interface gráfica similar al sistema operativo original y una interface o API de este sistema en particular.

En muchos casos estas aplicaciones unicamente necesitan ser recompiladas en NT.

La filosofía Cliente-Servidor, simplifica el SO base, mejora la fiablilidad y proporciona una base natural para el proceso distribuido.

En el proceso distribuido se puede definir el Hilo o proceso (Colección de uno o más hilos). El tipo de multiproceso es simetrico. Las rutinas del SO se pueden ejecutar en cualquier procesador libre. Permite el uso de varios hios de un mismo proceso que se pueden ejecutar en varios procesadores. Los servidores pueden utilizar varios hilos para peticiones simultaneas. Mecanismos de compartición y sistemas de comunicación fiables.

NT incorpora concepto de diseño orientado a objetos, sobre todo orientado a la compartición y a los sistemas de seguridad. No es un lenguaje totalmente orientado a objetos porque no soporta herencia o polimorfismo, pero si :

•       Encapsulamiento .- Datos o atributos precisos de servicios para acceder a ellos.

•       Clase o instancia .- Plantillas que enumenra atributos del objeto, los servicios que puede invocar sobre el objeto y caracteristicas. El sistema operativo puede generar instancias de un objeto.

Los objetos de NT à Archivos, Procesos, Semaforos, Temporizadores, Ventanas.

Para gestionarlos se utiliza el administrador de objetos. Un objeto puede hacer referencia a otro abriendo un descriptor o puntero al objeto.

Existen objetos con nombre (Seguridad) à Solo procesos que conozcan su nombre pueden acceder a este ; y objetos sin nombre.

•       UNIX à Fue desarrollado en un principio en los laboratorios de BELL , fue operativo a finales de los 70 y tuvo su maxima expansión en los 80.

Incorpora idea de MATCH y de MULTICS. Sistema operativo diseñado en lenguaje de lato nivel (C) , por tanto un sistema muy abierto.

SO multiusuario y multitarea que utiliza tiempo compartido.

Tuvo una gran difusión porque durante los primeros años se distribuyo gratuitamente. Surgieron debido a esto muchas versiones, sobre todo a nivel de universidades, que se apartaron de la idea original.

Posteriormente se unifican todas estas versiones en el UNIX SYSTEM V v.4 que soporta cualquier plataforma.

Se tiene en hardware rodeado por el Kernel y una serie de SHELL´s

CSH (Leng. C)

KSH ( Más utilizado)

Bourne Shell (Más antiguo)

JSH (Hot Shell à gestión de trabajos)

Cualquier usuario puede modificar los shell añadiendo ordenes o modificando las existentes.

El SO tiene rutinas primitivas que interactuan directamente con el hardware.

•       Subsistema de control de procesos , responsable de la gestión de memoria, planificación , sincronización y comunicación entre procesos.

•       Sistema de archivos, intercambio de datos, con la caracteristica de que puede usar dos sistemas de archivos.

•       Con Buffer à Transferencia se realiza por bloques.

•       Sin buffer à Tranferencia se realiza carácter a carácter.

En UNIX se trata todos los dispositivos en forma de ficheros.

 

•       Se distinguen tres tipos de ficheros :

•       Ordinarios.

•       Directorios.

•       Dispositivos.

En el arbol de directorios apareceran como ficheros.

•       MVS à Nace en el año 64 en el que IBM anuncia sus nuevos sistemas 360 incompatibles con los sistemas anteriores, lo cual supone una revolución en el mundo de las computadoras, ya que se desechan los sistemas antiguos y se entra en esta filosofía para grandes computadoras de IBM.

El éxito fue enorme e IBM se hace con una cuota de mercado del 70%.

El sistema original es un sistema por lotes con multiprogramación. La siguiente versión, derivada de la MTV, es la SVS, que establece un espacio de direcciones de 16 Mb compartido entre los procesos activos y el SO, esto supone un gran paso frente a los sistemas antiguos.

Derivado del SVS surge el MVS donde cada trabajo tiene su propia memoria virtual. Maneja direcciones de 24 bits y espacio de memoria de 16Mb para cada trabajo.

Con las direcciones de 32 bits se genera el MVS /XA que utiliza direcciones de 31 bits que compatibiliza con las versiones anteriores de 24 bits (mediante el bit 32). Utiliza un espacio de direcciones de 2 Gb.

Aparece por último, el MVS /ESA que aporta 15 espacios de direccionamiento adicionales de 2 Gb. Con lo que se llega a un espacio de direccionamiento de 32 Gb.

Es el sistema operativo más complejo.

Da soporte a tareas por lotes e interactivas. Permite multiprogramación fuertemente acoplada.

Tiene un sistema de asignación de recursos de sistema (SRM). El concepto de recurso incluye procesador, memoria y canales de E/S.

Ej à Para manejar paginación bajo demanda la memoria se divide en marcos o encuadres a los que le corresponde una página.

Cada 20 seg. Se realiza un control y aquella pagina no referenciada aumenta su contador de pagina. A la hora de hacer intercambio elige la que tenga contador más alto.

Dispone de un shell externo y una serie de programas para generar y compilar programas y los JES (Sistemas de gestión de trabajos) à Interpretan ordenes de operador, leen datos de entrada y escriben los datos de salida, asignan dispositivos de E/S y convierten cada trabajo en tareas.

En nucleo consta de una serie de modulos o subsistemas :

•       Distribuidor à Administrador de procesadores. Su misión es la de recorrer la cola de tareas listas y planificarla.

•       Tratamiento de interrupciones.

•       JES

•       Gestión de programas.

•       Admon. De almacenamiento (Control de memoria virtual o real).

•       Métodos de acceso à Para llevar a cabo operaciones de E/S

•       Supervisor de E/S à Para inicilizar y terminar tareas E/S a nivel hardware.

•       Gestor de recursos (SRM)

EJEMPLOS DE DESCRIPCION DE PROCESOS.

UNIX SYSTEM V x.4 à Utiliza un servio de procesos simple, potente y visibles para el usuario. Donde todos los procesos son creados por ordenes del sistema menos el proceso de SWAPPING, INIT.

Procesos à 9 estados :

•       2son de ejecución .- Identifican si esta en modo usuario o en modo Kernel.

•       Listo para ejecutar y en memoria.

•       Dormido y en memoriaà Suspendido en memoria principal.

•       Listo para ejecutar y descargado.

•       Explusado à El proceso retorna del modo nucleo al modo usuario mediante expulsión (Cambio de contexto).

•       Creado .- No ha entrado en estado de Listo.

•       Zombie .- Proceso ha perdido su entronque con su proceso padre. El proceso no puede ser referenciado por su Path- Name. La orden de muerte para un proceso zombie lo deja en estado de Funck. Para solucionar esto, el proceso INIT chequea el sistema , apadrina estos procesos huerfanos y luego los mata (UNIX SYSTEN V x.4)

Un proceso en UNIX es un conjunto de estructuras de datos para dar información al sistema para administrarlo y expedirlo . La imagen esta dividida en 3 partes :

•       Contexto de usuario .- Elementos tipicos de programas de usuario

•       Contexto de registros .- Cuando un proceso no esta en ejecución guarda información en este contexto (Contador de programa, registro de estado del proceso, puntero de pila y registro de proposito general )

•       Contexto del sistema .-

•       Entrad del proceso en la tabla de usuario.

•       Area de usuario.

•       Tabla que define la traducción de direcciones de memoria.

•       Permisos de procesos y pila del nucleo.

Por entradas a la tabla de procesos en UNIX entendemos una serie de información sobre el proceso :

•       Estado del proceso.

•       Punteros de contexto de usuario, texto , ...

•       Taqmaño del proceso.

•       Id´s de usuario à Id real (Nombre del propietario del proceso) Id efectivo ( Usuario que temporalmente dispone de privilegios pertenecientes al propietario).

•       Id de proceso .- Todos los procesos tiene un identificador unico en el sistema y referncias al id del proceso padre.

•       Señales

•       Temporizadores

•       Enlaces

•       Estados de memoria.

Area de usuario à Incluye :

Un puntero a la tabla de procesos.

Información de la tabla de procesos o identificación de usuarios (reales y efectivos) Registros de tiempo de un proceso y sus descendientes tanto en modo usuario como en modo nucleo.

Vector de tratamiento de señales. Errores producidos durante las llamadas al sistemas. Valores devueltos por las llamadas al sistema.

Parametros de E/S

Parametros de archivo.

Tablas de descriptores à Ficheros abiertos por ese proceso.

Campos de limites à Restringe tamaño del proceso o fichero.

Campos de protección à Mascaras de protección (16 bits) que se corresponden con lectura, escritura, ejecución por usuario, grupo u otros.

rwx à 9 bits (atributo à Presencia de la letra, presencia de atributo).

(Presencia de ‘-‘ denegado atributo)

El bit 10 y 11 de la mascara son atributos especiales à Bloqueo de archivo en memoria (cuando fichero esta accedido para modificación por varios usuarios)

Atributo que se corresponde con el usuario efectivo à bit de enmascaramiento, que si esta activo convierte en efectivo a efectos de ejecución.

El resto hasta los 16 se refieren a tipos de archivos, en función de estos actuan los otros atributos.

Creación de procesos.

Mediante una operación FROK el SO crea una entrada en la tabla de procesos, le asigna un identificador unico en el sistema (suelen ser consecutivos)

0 à SWAPPING

1 à INIT

......

Rango de los numeros enteros à Cuando se agota este se utilizan identificadores de los procesos que van desapareciendo.

Se realiza una copia de la imagen del padre excepto las direcciones de memoria.

El proceso Hijo va a poder acceder a ficheros abiertos por el padre, y lo que reflejarán los contadores del padre es que va a haber más procesos que puedan acceder a los ficheros.

El proceso se pone a listo para ejecutar.

Esto va a permitir ejecución en paralelo o el hijo puede intercalar su propio código (EXEC).

Hay un código de retorno, para el padre es el identificador del hijo y para este es el el 0 (Dependiendo de este se sabe si se esta en el padre o en el hijo o si se ha producido un error)

WINDOWS NT à Diseño de procesos es muy simple, ya que cada subsistema añade lo propio. Se distinguen objeto proceso y objeto hilo. Ya que debido a la existencia de procesos e hilos se generan diferentes objetos con diferentes asignaciones.

El objeto proceso tiene asignada una tabla de objetos con descriptores de hilos o archivos, tiene además asignadas una especie de direcciones virtuales y el resto de los recursos que compartiran los objetos hilos.

El valor del atributo hilo se obtiene a partir del atributo del objeto. Pro tanto los campos de un objeto proceso varian de los campos de objeto hilo.

 

Para el objeto proceso :

•       Indentificador del proceso.

•       Señal de accso .- Contiene informe sobre seguridad.

•       Prioridad de base que heredaran del hilos.

•       Lista de procesadores en los cuales se pueden ejecutar hilos.

•       Cantidad maxima de memoria paginadad y no paginada.

•       Tiempo total de ejecución de todos los hilos.

•       Contadores de E/S y memoria virtual.

•       Canales de comunicación entre procesos.

•       Razoón de terminación

Para objeto hilo :

•       Identificador del hilo.

•       Contexto del hilo.

•       Prioridad dinamica.

•       Prioridad base (Heredada del proceso)

•       Conjunto de procesadores donde se puede ejecutar.

•       Tiempo de ejecución.

•       canal(es) de comunicación por las que puede enviar mensajes.

•       Estado de terminación.

Cuando se crea un proceso nuevo en un subsistema hereda atributos propios de ese subsistema. Si corresponde a un subsistema de seguridad o POSIX hereda recursos del sistema NT.

MVS à Su unidad de expedición es la tarea. Dentro del espacio de direcciones de cada aplicación se pueden generar tareas. Debido a gran tamaño MVS puede gestionar miles de procesos concurrentes.

Tareas tiene 3 estados :

•       Listo.

•       Activo

•       Esperando

Aunque permite descargar en memoria secundaria (suspender)

Cada proceso tiene un bloque de control de tareas (TCB). Cada tarea tiene su propio bloque de petición de servicios. (SRB)

Cuando llega el momento de expedir una terea el distribuidor escoge entre los SRB y los TRB disponibles.

Estructura de control de procesos.

Cada tarea tiene asignado su SRB.

También existe el bloque de control de espacio de direcciones (ASCB)

Bloque ampliado de espacio de direcciones (ASXB)

Bloque local de direcciones y Bloque de control de tareas (TCB)

Los primeros contiene información sobre espacio de direcciones, el último representa a un proceso en ejecución y contiene información sobre el estado del proceso y punteros a los programas que forman parte de la tarea.

Una vez que se elige un espacio de direcciones . Se trabaja con una estructura o zona local de colas del sistema, formadas por las diferentes tareas ubicadas en los espacios de direcciones. Para servir esas tareas expide el SRB de mayor prioridad, si no hay ninguno se elige el TCB de mayor prioridad dentro del sistema.

La gestión de procesos más completa la realiza UNIX ( Caracteristica principal à Entroncamiento de procesos) y NT tiene a su favor la utilización de objetos y la posibilidad de ejecutarlos en diferentes subsistemas.

MVS à Sistema muy orientado al trabajo por lotes.

PLANIFICACION.

UNIX à El planificador de UNIX emplea realimentación multinivel con RR en cada una de las colas de prioridad. Existen varios niveles de prioridad, y los procesos pueden pasar de un nivel de prioridad a otro. El cuanto debe ser pequeño pues el sistema debe dar soporte a un entorno multiusuario.

El sistema lleva a cabo una apropiación cada segundo, es decir, si un proceso en ejecución no se bloquea o termina en 1 seg. Será expulsado. La prioridad esta basada en :

•       Prioridad base.

•       Tiempo de CPU consumido.

•       Parametro externo (usuario) à Mediante la orden NICE.

Pj = Basej + CPU (i-1) /2 + nicej ;

Realiza una media ponderada.

El proceso se colocará en una banda de prioridad en función de su prioridad base.

La prioridad de cada proceso se recalcula cada segundo instante en el que se toma una decisión de planificación.

Hay tareas que tiene una mayor prioridad que otras :

•       Intercambio con disco.

•       Control de dispositivos de E/S por bloques.

•       Gestión de archivos.

•       Control de dispositivos de E/S por carácter.

•       Procesos de usuario :

•       Carga E/S à Mayor prioridad por su nivel de interacción alto.

•       Carga de CPU à Procesos en Background.

¨    Esta jerarquía proporciona un aprovechamiento más eficiente de los dispositivos de E/S. En la banda de procesos de usuario, el empleo del historial de ejecución tiende a penalizar los procesos con carga de CPU frente a los procesos con carga de E/S . Conjuntamente con el esquema apropiativo por turno rotatorio, la estrategia de planificación esta bien preparada para cumplir los requisitos de tiempo compartido de propósito general.

WINDOWS NT à Fue diseñado para ser sensible a las necesidades de un unico usuario en un entorno muy interactivo o en el papel de un servidor.

En caso de WINDOWS NT es implementa un sistema de prioridades que incluye planificación por RR dentro de cada nivel, y para algunos niveles variación dinámica de la prioridad en función de la actividad de sus hilos.

Las prioridades se organizan en dos bandas o clases : tiempo real y variable. Cada una de estas bandas consta de 16 niveles de prioridad.

Los hilos que requieren atención inmediata estan en la banda real.

Las prioridades se gestionan de forma diferente en las dos bandas :

•       En la banda de tiempo real los hilos tienen una prioridad fija que no cambia nunca.

•       En la banda de prioridad variable, la prioridad de un hilo parte de un valor inicial pudiendo cambiar durante la vida de dicho hilo. (Hay una cola FIFO en cada nivel de prioridad pero un proceso puede emigrar de una de estas colas a otra dentro de la clase de prioridad variable no pudiendo nunca superar el nivel 15.

La prioridad de un hilo en la clase de prioridad variable viene determinada por dos valores :

•       La prioridad base del proceso.

•       Prioridad base del hilo.

Una de las propiedades del objeto proceso es la prioridad base del proceso, que puede tomar valores entre 0 y 15. Cada objeto hilo asociado a un proceso tiene su atributo prioridad base del hilo, que indica la prioridad base del hilo relativa al proceso.

La prioridad base del hilo puede ser igual a la del proceso o dos niveles por encima o por debajo.

Ej à Si la prioridad base de un proceso es 4 y la de uno de sus hilos es -1 la prioridad inicial del hilo sera 3.

Si la prioridad base de un proceso es 6 y la prioridad base de un hilo es +1, la prioridad inicial del hilo será 7.

•       Si un hilo se interrumpe por una operación de E/S la prioridad del hilo aumenta, sin embargo si el proceso se bloquea por exceder el cuanto de tiempo disminuye su prioridad

Cuando NT se ejecuta en una máquina monoprocesador se ejecutará siempre el hilo de mayor prioridad a no ser que se encuentre esperando un suceso. Si hay más de un hilo con máxima prioridad, el procesador esta compartido con un turno rotatorio entre todos los hilos de este nivel de prioridad.

Cuando se ejcuta en un sistema multiprocesador, con N procesadores, siempre estaran activos los N-1 procesos de maxima prioridad en N-1 procesadores, el resto de los hilos de menor prioridad se ejcutan en el procesador que queda libre compartido por turno rotatorio.

•       La disciplina anterior se ve afectada por una propiedad del hilo à afinidad de procesador.. Si un hilo esta listo para ejecutar pero en el conjunto de procesadores no se encuentra el procesador afín a ese hilo este es obligado a esperar, planificándose otro hilo de menor prioridad.

MVS à Se debe recordar que el entorno de procesos de MVS esta formado por las siguientes entidades :

•       Bloque de petición de servicio global (SRB global) .- Tarea del sistema que no se ejecuta en el espacio de direcciones de usuario.

•       Bloque de control del espacio de direcciones (ASBC) y bloque de extensión del espacio de direcciones (ASXB) .- Para gestionar el espacio de direcciones correspondiente a una unica aplicación o trabajo.

•       Bloque de petición de servicio local (SBR local) .- Tarea del sistema que se ejecuta dentro del espacio de direcciones de usuario.

•       Bloque de control de tarea (TCB) .- Tareas de un espacio de direcciones.

Las tares de los SRB no son apropiativas, por el contrario una tarea controlada por un TCB es apropiativa.

Los SBR globales se mantiene en una cola de prioridad descendente en el area de colas del sistema. Cuando hay un procesador disponible se busca primero un SRB listo en esta cola. Si no encuentra ninguno busca en un espacio de direcciones que tenga al menos un TCB o un SRB local listo

La cola ASBC se mantiene con el fin de asignar un nivel de prioridad completo a cada espacio de direcciones, de ese modo una vez seleccionado un espacio de direcciones, MVS puede trabajar con las estructuras de ese espacio de direcciones, o area local de colas del sistema.

Las prioridades de expedición tienen 256 niveles de MVS y los SRB globales se expiden por encima del nivel más alto definido.

Las prioridades de expedición se organizan en bandas de 16 niveles. Normalmente un espacio de direcciones es asignado a esa banda y normalmente permanece en ella.

En cada banda los 6 primeros niveles son niveles de prioridad fija, mientras que los 10 niveles inferiores son de prioridad variable.

Cuando se crea un espacio de direcciones, es asignado un grupo de rendimiento de determinada prioridad, o conjunto de niveles de prioridad donde se va a ejecutar dicho espacio de direcciones. Un espacio de direcciones en un grupo de rendimiento se considera que pasa por una serie de periodos de rendimiento, que permiten gestionar una tarea en función de la edad de la misma.

SEGURIDAD .

WINDOWS NT à Ofrece un servicio de control de acceso que se aplica a los procesos, hilo, archivos, semáforos, ventanas y otros procesos. El control de acceso está gobernado por dos entidades : Una señal de acceso asociada a cada proceso y un descriptor de seguridad asociado con cada objeto para el que es posible el acceso entre procesos.

Cuando un sistema se conecta al sistema NT, este utiliza un sistema de nombre/contraseña para autentificar el usuario. Si se acepta la conexión, se crea un proceso para el usuario y se le asocia una señal de acceso al objeto que representa a dicho proceso. La señal de seguridad incluye un SID (Security ID) que es el identificador por medio del cual el usuario es conocido en el sistema con fines de seguridad. Cuando un proceso de usurio crea más procesos estos heredan su SID. Las señales de acceso sirven para dos fines :

•       Reúnen la información necesaria para acelerar la validación de los accesos.

•       Permite a los procesos modificar su característica de seguridad de forma limitada.

Hay un descriptor de seguridad asociado a cada objeto para el que es posible el acceso entre procesos. El componente principal del descriptor de seguridad es una lista de control de accesos que especifica los derechos de accesos a varios usuarios o grupos de usuario para el objeto. Cuando un proceso intenta tener acceso se compara el SID con la lista para ver si se le permite el acceso.

Un aspecto importante de la seguridad de NT es el concepto de imitación, que simplifica la seguridad en un entorno cliente/servidor. El servidor asume temporalmente la identidad del cliente, de forma que pueda evaluar una solicitud de acceso relativa a los derechos de dicho cliente. Tras l acceso, el servidor vuelve a tomar su propia identidad.

Señales de acceso 

•       ID de seguridad .- Identifica unívocamente a cada usuario de todas las máquinas de la red.

•       SID de grupo.- Una lista de grupos a los que pertenece el usuario. El acceso al objeto puede definirse en función del SID de grupo o SID individual.

•       Privilegios .- Una lista de servicios del sistema sensibles a la seguridad que el usuario puede pedir

•       Propietario por omisión .- Si un proceso crea objetos, este campo especifica el propietario del nuevo objeto.

•       ACL por omisión .- Es una lista inicial de protectores que se aplica a los objetos que crea el usuario.

Descriptores de seguridad.

•       Indicadores .- Definen el tipo y el contenido del descriptor de seguridad.

•       Propietario .- El propietario del objeto puede realizar en general cualquier acción sobre el objeto. El propietario puede ser un SID individual o de grupo.

•       Lista de control de acceso al sistema (SACL) .- Especifica los tipos de operación sobre el objeto que debe generar mensajes de auditoría.

•       Lista de control de acceso direccional (DACL) .- Determina que usuarios o grupos pueden acceder al objeto y para que operaciones.

Cuando se crea un proceso el creador puede asignarle una señal de acceso con su propio SID o el de un grupo. El proceso creador no puede asignarle un SID que no este en la acceso de acceso actual.

Listas de control de acceso.

Cada lista consta de una cabecera global y de un número variable de ACE. Cada entrada especifica un SID individual o de grupo y una mascara de acceso que define el tipo de derechos otorgados al SID.

Cuando un proceso intenta acceder a un objeto se lee el SID de la señal de acceso y recorre el DACL del objeto. Si encuentra un ACE con un SID de la señal el proceso tendrá sobre el objeto los derechos especificados sobre la mascara.

Mascara.

Los 16 bits más significativos de la mascara se aplican a todos los objetos .

Tipo de acceso standard :

•       Sincronizar à Concede permiso para sincronizar la ejecución con algún proceso asociado al objeto.

•       Escribir_propietario à Permite modificar el propietario del objeto.

•       Escribir_DAC à Permite al proceso modificar el DACL.

•       Leer_control à Permite consultar los campos de propietario y DACL.

•       Eliminar à Permite eleminar el objeto.

De acceso generico :

•       Todo_generico à Permitir todos los accesos.

•       Ejecución_generica à Permitir ejecución si es ejecutable.

•       Escritura_generica à Permitir acceso a escritura.

•       Lectura_generica à Permitir acceso a elctura.

Los dos bits restantes del ACE tiene significado especial :

•       Seguridad del sistema de acceso à Permite modificar el control de alarma o auditoria del objeto.

•       Máximo permitido à Máximo numero de búsquedas permitidas de un SID.

EL PROBLEMA DE LOS FILOSOFOS.

Los preparativos de la comida son simple, una mesa redonda con 5 platos y 5 tenedores. Un filosofo que quisiera comer se dirigiría a la mesa y usando los tenedores de cada lado del plato comerá. El problema es hallar el algoritmo que permita comer a los filósofos, el algoritmo debe satisfacer la exclusión mutua, además de evitar el interbloqueo y la inanición.

El problema propuesto por Dijkstra puede no parecer importante en si mismo, sin embargo, sirve para ilustrar los problemas que surgen a la hora de la programación concurrente (inanición e interbloqueo).

Se sugiere una solución con semáforos, cada filosofo toma primero su tenedor de la izquierda y luego el de la derecha y entonces come. Esta solución, produce interbloqueo, . Si todos los filósofos se sientan a comer al mismo tiempo, todos intentan coger el tenedor de la izquerda y luego el de la derecha que no estará.

Para superar el riesgo de interbloqueo se podría utilizar otra herramienta de concurrencia à Región Critica.

Es una variable à shared [tipo] , definida para proteger una sección critica de código.

Region var do

Begin

await (tenedor(i) & tenedor ((i+1) mod 5)

end ;

La región critica condicional incluye parametros que permiten evaluar una condición.

•       Si la condición no se cumple el proceso se introduce en un cola de suspendidos liberando el recurso.

•       Cuando un proceso sale se mira antes la cola de suspendidos y si un proceso cumple la condición pasa por delante de la cola de espera.

HERRAMIENTAS DE CONCURRENCIA.

UNIX à Ofrece diversos mecanismos para la comunicación entre procesos y la sincronización :

•       Tubos.

•       Mensajes.

•       Memoria compartida.

•       Semáforos.

•       Señales.

Los tubos, mensajes y memoria compartida proporcionan un medio de comunicación entre procesos, mientras que los semaforos, señales sirven para provocar acciones en otros procesos.

Tubos .- Una de las contribuciones más significativas de UNIX al diseño de sistemas operativos. Un tubo es un buffer circular según el modelo de productor/consumidor. Así pues, consiste en una cola del que primero lega primero sale en la que un proceso escribe y otro lee.

Cuando un proceso intenta escribir en el tubo, la solicitud de escritura se ejecuta inmediatamente si hay suficiente espacio, de otro modo el proceso se bloquea. Del mismo modo el lector se bloquea si intenta leer más bytes de los que tiene el tubo en ese momento. El sistema operativo se encarga de la exclusión mutua.

Existen dos tipos de tubos à Con nombre y sin nombre :

Solo procesos afines pueden compartir tubos sin nombre, y los procesos no afines no pueden compartir tubos con nombre.

Mensajes .- Es un bloque de texto con un tipo asociado. UNIX tiene asociadas unas llamadas al sistema para la gestión de estos. Cada proceso tiene asociado una cola de mensajes. Que funciona como un buzón de correos.

El emisor del mensaje especifica el tipo de mensaje en cada envio y el receptor puede usarlo como criterio de selección. El receptor puede recuperar los mensajes tanto en orden FIFO con por el tipo. Un proceso se suspenderá cuando intente leer de una cola vacia Si un proceso intenta leer un proceso de cierto tiempo y falla no se suspenderá.

Memoria compartida .- La forma más rápida de comunicación entre procesos que proporciona UNIX, se trat de un bloque comun de memoria virtual compartida por varios procesos. Los procesos leen y escriben en la memoria virtual usando las mismas intrucciones que emplea para leer o escribir en zonas de memoria normales.

 Semáforos .- Las llamadas al sistema para los semáforos en UNIX son una generalización de el wait y el signal, en las que se pueden realizar simultáneamente muchas tareas, y los incrementos y decrementos pueden ser de valores mayores que 1.

Un semáforo consta de los siguientes elementos :

•       Valor actual del semáforo.

•       ID del último proceso que opero con el semaforo.

•       Número de procesos esperando a que el valor del semáforo sea mayor que su valor actual.

•       Número de procesos esperando a que el valor del semáforo sea cero.

Asociadas a cada semaforo existe una cola de procesos suspendidos.

Los semaforos se pueden crear por conjuntos. Hay una llamada al sistema que permite dar valores a los semaforos de un conjunto todos a la vez. Existen una serie de operaciones definidas sobre semáforos :

•       Incrementa el valor del semáforo y despierta a todos los procesos que esperan a que el valor del semáforo se incremente.

•       Comprueba el valor del semáforo . Si es cero, incrementa el numero de procesos esperando a que el semaforo sea 0 y suspende el proceso.

•       Si el resultado es 0 el nucleo despierta a todos los procesos que esperan que el valor del semaforo sea igual a 0.

•       Si si valor abs es mayor que el valor del semaforo el nucleo suspende el proceso.

¨    Los semaforos ofrecen una gran flexibilidad.

Señales .- Mecanismo de software que funciona igual que las interrupciones hardware. Informan a un proceso del acintecimiento de un rpoceso asincrono.

Un proceso puede responder a una señal ejecutando alguna acción por omisión, ejecutando una función del manejo de señal o ignoran la señal.

Son 19 y pueden ser tratadas por ordenes de usuario à $TRAP fich1 ,,fichn ...señal1,señal n &

01 SIGNUP Colgar

02 SIGINT Interrumpir.

03 SIGQUIT Salir

04 SIGILL Instrucción ilegal.

05 SIGTRAP Ejecución de un código de seguimiento de un proceso

09 SIGKILL Matar

15 SIGTERM Terminación de un proceso

18 SIGCLD Muerte de un hijo

19 SIGPWR Corte de energía.

WINDOWS NT à Ofrece sincronización entre los hilos como parte de la arquitectura de los objetos. El mecanismo usado por el ejecutor de NT para inplementar los ervicios de sincronización es la familia de objetos de sincronizacion :

Proceso

Hilo

Archivo

Suceso

Pareja de sucesos

Semáforo

Temporizador

Metante

Los tre primeros tipos de objetos de la lista anterior tiene otros usos, pero tambien se pueden emplear para sincronización.

Cada caso de objeto se sincronización puede estar en estado de señalizado o de no señalizado. Un hilo puede estar suspendido por un objeto en estado no señalizado, el hilo es liberado cuando el proceso es señalizado.

Cuando un objeto pasa al estado de señalizado, el ejecutor de NT libera todos los objetos hilos, que estaban esperando por dicho objeto de sincronización.

El objeto mutante se utiliza para hacer cumplir la exclusión mutua en el acceso a un recurso, permitiendo que un solo objeto hilo obtenga el acceso en cada instante. Funciona como un semáforo binario, Cuando el objeto mutante pasa al estado de señalizado, solo se libera uno de los hilos que esperan.

MVS à Proporciona dos servio para hacer cumplir la exclusión mutua en el uso de recursos :

Colas .- Regulan el acceso a recursos de datos compartidos. Un proceso solicita control compartido si el recurso es de solo lectura y control exclusivo si los datos pueden modificarse. Para determinar la acción a seguir cuando se produce una solicitud, el esquema se basa en los lectores/escritores con prioridad para los lectores.

El usuario puede pedir que se compruebe la disponibilidad del recurso pero sin solicitar el control o bien puede pedir que se asigne el control del recurso al solicitante solo si el recurso esta libre en ese momento. Pueden emplearse para prevenir interbloqueo.

Cierres .- Sirven para hacer valer la exclusión mutua en el acceso a los recursos del sistema. Los cierres se clasifican en dos clases y dos tipos :

•       Globales .- Todo el espacio de direcciones.

•       Locales .- En todas las tareas de un solo espacio de direcciones.

¨    Cierre de giro .- Procesador ejecutar algún tipo de operación "test and set" sobre el cierre con espera activa.

¨    Cierres de suspensión .- La tarea en espera queda suspendida.

Para prevenir interbloqueos los cierres se disponen en una jerarquía ; esta es la estrategia discutida para prevenir el ciclo de espera circular. Un procesador puede solicitar solamente los cierres superiores a los que posee según la jerarquía.