TEMA 1. INTRODUCCIÓN. Requerimientos mínimos de un SO. • Capacidad de intercalar distintos procesos en ejecución para maximizar la utilización del procesador. (intentaremos meter el maximo numero de procesos en memoria) • Capacidad de asignar los recursos a los procesos siguiendo una politica para evitar la aparición del `Interbloqueo'. • Capacidad para comunicar procesos y para crear procesos por parte del usuario, esas capacidades ayudan a la estructuración de las aplicaciones. APÉNDICE A. Arquitectura del Sistema de Ficheros en UNIX System V. A.1 Caracteristicas del Sistema de Ficheros. − Posee una estructura jerarquica. • Realiza un tratamiento consistente de los datos de los ficheros. • Puede crear y Borrar ficheros • Permite un crecimiento dinamico de los ficheros • Protege los datos de los ficheros • Trata los dispositivos y periféricos como si fuesen ficheros. Los programas que se ejecutan en Unix no conocen el formato interno con el que el núcleo almacena los datos. Nuestro programa es el encargado de interpretar la secuencia de bytes y darle significado según sus necesidades. La sintaxis (forma) de acceso a los datos de un fichero viene impuesta por el sistema y es la misma para todos los programas, y la semántica (significado) de los datos es responsabilidad del programa que trabaja con el fichero. A.2. Estructura del Sistema de Ficheros. En esta se pueden distinguir 3 partes: • El Bloque de Arranque (boot y Superbloque) Ocupa la parte del principio del sistema de ficheros, tipicamente el primer sector, y puede contener el código de arranque, este es un pequeño programa que se encarga de buscar el SO y cargarlo en memoria para inicializarlo. En el Superbloque está la descripción del estado del sistema de ficheros. Contiene la siguiente información: • Tamaño del sistema de ficheros • Lista de bloques libres disponibles • Indice del siguiente bloque libre en la lista de bloques libres 1

• Tamaño de la lista de nodos−i • Total de nodos−i libres • Lista de nodos−i libres • Indice del siguiente nodo−i libre en la lista de nodos−i libres • Campos de bloqueo de elementos de las listas de bloques libres y de nodos−i libres • Indicador que informa si el Superbloque ha sido modificado o no. Cada vez que, desde un proceso se accede a un fichero, es necesario consultar el Superbloque y la lista de nodos−i. • Lista de nodos indice. i−Nodos. Se encuentra despues del Superbloque, esta lista contiene una entrada por cada fichero, donde se guarda una descripción del mismo. Esta información es necesaria para que un proceso pueda acceder al fichero. Esta información incluye: Propietario, derechos de acceso, tamaño, localización en el sistema de ficheros, etc Durante el proceso de arranque del sistema, el nucleo lee la lista de nodos−i del disco y carga una copia en memoria conocida como `Tabla de nodos−i'. Las manipulaciones que haga el subsistema de ficheros sobre los ficheros van a involucrar a la tabla de nodos−i, pero no a la lista de nodos−i. Los campos de que se compone un nodo−i son los siguientes: • Identificador del propietario del fichero. • Tipo de fichero. (ordinario, directorio, especial, tuberia) • Tipo de acceso al fichero. Acceso del propietario, grupo ó resto de usuarios. • Tiempos de acceso al fichero. Ultima modificación, fecha de creación • Número de enlaces del fichero. Representa el total de los nombres que el fichero tiene en la jerarquia de directorios. Un fichero puede tener asociado diferentes nombres que correspondan a diferentes rutas, pero através de las cuales accedemos a un mismo nodo−i y por consiguiente a los mismos bloques de datos. • Entradas para los bloques de dirección de los datos de un fichero. • Tamaño del fichero. Los bytes de un fichero se pueden direccionar indicando un desplazamiento a partir de la dirección de inicio del fichero. Hay que hacer notar que el nombre del fichero no queda reflejado en el nodo−i. • El estado del nodo−i: bloqueado, si hay algún proceso esperando que el nodo−i quede desbloqueado, si la copia del nodo−i que hay en memoria difiere de la que hay en el disco, si la copia de los datos del fichero que hay en memoria difiere de los que hay en el disco. • El número de dispositivo lógico del sistema de ficheros que contiene al fichero. • El número de nodo−i. • Punteros a otros nodos−i cargados en memoria. • Un contador que indica el número de copias del nodo−i que hay actualmente en memoria. • Los Bloques de Datos. Están situados a partir de la lista de nodos−i, cada nodo−i tiene unas entradas para localizar donde se encuentran los datos de un fichero en el disco. Como cada bloque del disco tiene asociada una dirección, las entradas de direcciones consisten en un conjunto de direcciones de bloques del disco. Si los datos de un fichero se almacenasen en bloques consecutivos, para poder acceder a ellos nos bastaría con conocer la dirección del bloque inicial y el tamaño del fichero. A.3. Tablas de Control de Acceso a los Ficheros. 2

• Tabla de Nodos−i Es un copia en memoria de la lista de Nodos−i que hay en el disco, a la que se le añade información adicional. Esta tabla se copia del disco para conseguir un acceso más rápido a sus componentes. • Tabla de Ficheros Es un estructura global del nucleo y en ella hay una entrada por cada fichero distinto que los procesos del nucleo o los procesos del usuario tienen abiertos. Cada vez que un proceso abre o crea un fichero nuevo, se reserva una nueva entrada en la tabla. Cada entrada de la tabla de ficheros tiene tambien un puntero a una estructura de datos que contiene información del estado actual del fichero, entre otros, debe contener los siguientes campos: • Nodo−i asociado a la entrada de la tabla • Desplazamiento de lectura y escritura • Permisos de acceso • Indicadores del modo de apertura el fichero • Un contador para indicar cuantas entradas e la tabla de descriptores tienen asociada esta entrada de la tabla de ficheros. • Tabla de Desciptores de Fichero Es una estructura local a cada proceso. Esta tabla identifica todos los ficheros abiertos por un proceso. Los procesos no van a manipular directamente ninguna de las tablas anteriores, de esto se encargará el nucleo, sino que van a acceder a los ficheros manipulando su descriptor asociado, que es un número. TEMA 2. DESCRIPCIÓN Y CONTROL DE PROCESOS. ESTADOS DE UN PROCESO. Un programa es un conjunto de instrucciones dispuestas en un orden determinado para conseguir un objetivo cuando estas se ejecuten (esto es un concepto estático). El concepto de proceso es dinámico, un proceso es una parte de un programa en ejecución, cuando comienza la ejecución de un programa surgen 1 ó N procesos, lo que se intenta es que surgan cuantos más procesos mejor para optimizar el uso del procesador y el programa termine de ejecutarse lo antes posible. El estado de un proceso es una información básica para que el SO gestione los mismos de forma óptima. Los procesos se encolan para poderse gestionar y uno de los encolamientos posibles que se pueden dar es atendiendo al estado del proceso. (Pág 101 Stallings) El mapa de estados más básico es el de dos estados: (Pág.101 Stallings) Un proceso que no se está ejecutando puede pasar a ejecutarse por elección de un programa del SO que es el encargado de seleccionar el siguiente proceso a ejecutar. En un momento dado, el proceso en ejecución puede dejar de ejecutarse por necesitar datos o por que se haya excedido en su tiempo de ejecución. Los sitemas multiusuario manejan algoritmos que permiten compartir el procesador entre mmuchos procesos, 3

uno de ellos es el Round Robin que dece un cuanto de tiempo a cada proceso, cuando este lo agota es expulsado del uso del procesador. Un programa antes de iniciar su ejecución debe estar al menos parcialmente en memoria interna y el SO debe saber que existe en memoria. El siguiente es el modelo de proceso con 5 estados: (Pág.104 Stallings) − Estado nuevo, el proceso se crea y el SO le dá una configuración. − Estado listo, el proceso tiene todo lo necesario para ejecutarse menos el procesador. − Estado ejecución, el proceso ya tiene tambien el procesador. − Estado terminado, se suspende la ejecución y el SO liberará recursos.Si la ejecución acaba por razón de tiempo y el proceso no ha acabado, pasará al estado listo, pero si acaba por que al proceso le falta algún recurso pasará al estado bloqueado, cuando tenga el recurso que le falta pasará de bloqueado a listo. El siguiente es el modelo de proceso con 6 estados: (Pág.110 Stallings) El estado suspendido surge para gestionar mejor el sistema, si estoy ejecutando un proceso y este para al necesitar un recurso, pasará a bloqueado y si se bloquean muchos procesos se convertiran en un lastre para el sistema, en este caso el SO selecciona 1 ó varios procesos y los hecha de la memoria interna, este es el estado suspendido, asi consigo meter en memoria interna otros procesos que sí se pueden ejecutar. El siguiente es el modelo de proceso con 7 estados: (Pág.110 Stallings) (............ significa Probabilidad de) Puede pasar de bloqueado suspendido a bloqueado cuando no entran muchos procesos a memoria interna, esto es un lujo. El proceso está en memoria esperando un suceso. • Nuevo • Listo • Ejecución • Bloqueado • Suspendido • Bloqueado/suspendido • Terminado El suiguiente modelo es el de 9 procesos que utiliza Unix System V. • Ejecución modo Usuario: Ejecutando en modo usuario. • Ejecución en modo Núcleo: Ejecutando en modo núcleo. • Listo para ejecutar y en memoria: Se ejecutará tan pronto como el núcleo lo planifique. • Dormido y en memoria: No dispuesto a ejecutar hasta que se produzca un suceso, está en memoria. • Listo para ejecutar y descargado: Está listo para ejecutar pero no se cargará en memoria hasta que el núcleo pueda planificar su ejecución. • Dormido y descargado: Está esperando un suceso y ha sido expulsado a memoria secundaria. • Expulsado: Retorna del modo núcleo al modo usuario, pero el núcleo lo expulsa y realiza un cambio de contexto paraplanificar otro proceso. • Creado: Está recien creado y no listo para ejecutar. • Zombie: Ya no existe, deja un registro para que lo recoga el proceso padre.

4

¿Cómo se crean los procesos? Los procesos se pueden crear por 4 razones: • Entrada de un nuevo trabajo en modo Batch. • Conexión interactiva, cuando se conecta un usuario el sistema le crea automaticamente un proceso. • Posibilitar que nazca un nuevo proceso a aprtir de uno ya existente. • Que el propio SO para dar un servicio necesite crear el proceso. En cualquier caso se necesita asignar a cada proceso las estructuras de datos necesarias para su gestión y asignarle las direcciones de memoria necesarias para que el proceso pueda ubicarse en memoria. Cuando un proceso crear otro proceso, al proceso que crea se le denomina proceso padre y al que es creado proceso hijo, estos procesos hijos pueden tener caracteristicas especiales, no son del todo independientes y dependiendo del SO pueden compartir recursos... en otro SO pueden tener vinculación pero más baja. Si un proceso crea a otro significa que cuando el proceso padre desaparece, la mayoria de los SO anulan los procesos hijos, en otros SO no pasa esto. RAZONES DE TERMINACIÓN DE UN PROCESO. • Terminación normal, el proceso llama al SO y le comunica que ha terminado, el SO a su vez le desasigna recursos y los libera. • Por que no hay memoria disponible. • Por violación de limites de memoria. • Errores aritmeticos como divisiones por cero. • Por rebasar el tiempo de espera máximo. • Consumir más CPU de lo autorizado inicialmente. • Instrucciones invalidas. • Fallos de Entrada/Salida. • Terminación por instrucción privilegiada. • Terminación del proceso hijo por haber terminado el proceso padre. • Intervención del usuario u operador. DESCRIPCIÓN DEL PROCESO. Existen 2 conceptos a diferenciar: • Imagen del proceso. • Bloque de control del proceso. Por un lado Imagen del proceso, es una información que agrupa los datos de usuario, el espacio en memoria para incorporar los datos de usuario y el programa de usuario (las instrucciones), tambien agrupa la pila del sistema que es un espacio asignado a cada proceso utilizado para almacenar parámetros y direcciones de retorno para la gestión de ese proceso, un proceso puede llegar a tener una ó varias pilas. Por último, la imagen del proceso tambien es la encargada de guardar el Bloque de control del proceso que tiene la información necesaria para que el SO controle el proceso. Por tanto, el concepto del Imagen del proceso es más global que el de Bloque de control del proceso. ESTRUCTURAS DE INFORMACIÓN DEL PROCESO. 5

Imagen del proceso: − Programa • Datos • Pila • BCP Para que un proceso se pueda ejecutar, la imagen del proceso debe estar en memoria interna. El BCP contiene un conjunto de informaciones que pueden estar divididas en tres grandes bloques de información: • Identificación del proceso: • Indica el nombre ó número asociado a dicho proceso • Información asociada al proceso padre que lo ha generado • Identificador del usuario que lo ha generado • Información del estado del procesador, permite guardar toda la información asociada a los registros del procesador para que cuando se interrumpa el proceso pueda seguir ejecutandose. Dentro de esta informacion están: 2.1− Registros de control y estado del procesador, basicos para controlar el procesador, estan el CP que guarda la direccion de la siguiente instrucción a ejecutar, otro registro es el codigo de condicion que guarda el codigo de condicion de la ultima instrucción ejecutada y luego información de estado que son los Flags. 2.2− Registros visibles para el usuario, son aquellos a los que el usuario puede invocar durante la ejecucion del proceso. • Información de control del proceso, se guarda informacion acerca de: 3.1− Planificación y estado del proceso 3.2− Referencias acerca de la planificacion referidas a la prioridad que le damos al proceso e información acerca de la ejecucion del proceso que le damos al SO 3.3− Informacion de comunicación entre procesos 3.4− Privilegios de los procesos 3.5− Gestion de memoria, en que direccion de memoria se encuentra el proceso 3.6− Indicacion de la propiedad y utilizacion de los recursos CONTROL DEL PROCESO. Hay que tener en cuenta la consecución de varios pasos: • Creación del oproceso, cuando se crea un proceso: • Peticion al SO para que lo cree, asigna un unico identificador al proceso • Asignación de espacio al proceso, se asignará un espacio estandar ó se puede solicitar un espacio concretos. • Rellenar la información base del BCP • Establecer los enlaces adecuados de este proceso con otros, se les colocará en un cola enlazando sus 6

BCP's correspondientes en funcion de sus prioridades • Crear estructuras de datos vinculadas al propio proceso • Cambio del proceso. No es un cambio de contexto, un cambio de proceso es que el procesador deja de ejecutar un proceso y empieza a ejecutar otro, esto implica que la información de los registros del procesador se tiene que cambiar, el proceso saliente guardará la información de los registros en el BCP y el entrante cargará los registros con su información. El cambio de proceso es una operación costosa en cuento a ciclos de reloj. Un cambio de contexto consiste en que el proceso que esta haciendo uso del procesador, en un momento dado no puede continuar su ejecucion, cuando esto ocurre el SO lo detecta por que se produce una interrupción, en ese momento el SO identifica que tipo de interrupcion es la que se a producido e invoca a una rutina de resolucion de la interrupcion para que inicie su ejecucion y resuelva la interrupcion. El SO rellena la información del procesador con los datos necesarios para que esa rutina de interrupcion pueda ejecutarse, cuando la rutina acaba de ejecutarse ha resuelto el problema de la interrupcion y apartir de aquí el proceso original puede continuar su ejecucion. Existe una informacion (Contexto de Programa) que se salva en un momento determinado cuando se produce una interrupcion: • Contexto del programa • Carga de la rutina de interrupcion • Restaurar contexto del programa De este modo, movemos menos informacion que si cambiaramos el proceso, ya que, el proceso en ejecución va a continuar ejecutandose. Un cambio de proceso sigue los siguientes pasos: • Salva el contexto del procesador (Registros) • Actualiza el BCP que estaba en estado de ejecucion • Mueve el BCP a la cola que le corresponda • Solicita otro proceso para ejecucion • Actualiza el BCP del proceso seleccionado • Actualiza las estructuras de datos para la gestion en memoria • Restaura el contexto del procesador con la informacion del nuevo proceso Una interrupcion puede suponer un cambio de proceso ó un cambio de contexto. Mecanismos por los cuales se produce una ` Interrupción en la Ejecución de un Proceso `. Podemos tener en cuenta tres mecanismos: • Interrupción, es algo externo a la ejecucion de la instrucción en curso. • Cepo, es una interrupcion provocada por la ejecucion de la instrucción en curso. • Llamada del supervisor, es una invocacion expresa para que el proceso se interrumpa y esto esta derivado de las posibilidades del SO. PROCESOS E HILOS. Proceso = Tarea. Hay dos ideas basicas en el concepto de proceso que es una unidad de propiedad de los 7

recursos y una unidad de expedición. Como unidad de propiedad de los recursos se hace referencia a que cada proceso tiene su propio espacio de direcciones en el que se incorpora la imagen del proceso, ademas, al proceso se le asignan recursos que cuando los tiene asignados forman parte de esa `unidad de propiedad del proceso'. Como unidad de expedicion se dice que un proceso es un camino de ejecucion, este camino de ejecucion puede intercalarse con el camino de ejecucion de otro proceso distinto, asi la unidad de expedicion puede tener un estado distinto y una prioridad asignada por el sistema que forman una unidad de planificacion para el procesador. (Figura A). Con el objeto de optimizar los procesos, los SO posibilitan que dentro de un proceso existan una ó varias lineas de ejecucion a cada linea de ejecucion se la denomina Hilo, y la parte de recursos asignados al proceso es lo que se denomina Proceso. (Figura B). Figura A. Figura B. Al compartir recursos dentro de esa imagen del proceso, comparten posiciones de memoria comunes por lo que la comunicación entre los hilos se hace de manera inmediata siendo una ventaja para la ejecucion del proceso ya que no hay que pasar por el nucleo para comunicarse. Otra consecuencia importante es que un proceso puede generar N hilos y cada uno hace una parte diferente de la ejecución, en esta ejecución concurrente los hilos pelearán por el uso del procesador. Existen diferentes asociaciones Proceso−Hilo: Procesos Hilos 1 1 Unix System V 1 M MVS, NT, OS/2, Mach N 1 Ra N M Trix En el caso del Ra, un hilo puede emigrar a más de un proceso y podemos hacer pasar hilos de ejecucion de un sistema a otro. Con un sistema Multitarea ¿Para que sirven los hilos? Un sistema Multitarea permite que los hilos realicen trabajos interactivos y de fondo (imprimir), otra misión es que puedo definir la autoplanificación de un hilo de ejecucion por ejemplo de un buffer cada x segundos para salvar el contenido del buffer en un fichero y otro opcion de los hilos es la aceleración de la ejecucion. APÉNDICE A. Descripción y Control de Procesos en UNIX. Fork: Crea un solo proceso Parbegin: Permite lanzar N procesos simultaneos a ejecución 8

Descripción de Procesos: En UNIX los procesos hijos heredan parte (limitada) del proceso padre. La Imagen del Proceso en UNIX se divide en tres partes: • El contexto de usuario Contiene los elementos básicos de un programa de usuario y puede ser generado directamente a partir de un archivo de código compilado. • Texto del Proceso • Datos del Proceso • Pila de Usuario • Memoria compartida • El contexto de los registros, es parte del BCP (registros hardware) Almacena la información del estado del procesador cuando un proceso no está ejecutándose. • CP • Regs. De estado • SP • Regs. De propósito general • El contexto del sistema, guarda el estado del proceso. Contiene la información restante que el SO necesita para administrar el proceso. Aquí se encuentra la llamada área U. • Entrada de la tabla de procesos • Area U (usuario), información del control del proceso necesaria para el núcleo. • Tabla de regiones de preproceso. • Pila del núcleo. Control de Procesos: Hacen falta dos modos de ejecución. El Modo Usuario y el Modo Núcleo. La creación del proceso en Unix se hace por medio de la llamada `Fork' al núcleo del sistema. Cuando un proceso emite una petición `Fork', el núcleo de Unix realiza las siguientes acciones: • Asigna una entrada el la tabla de procesos al nuevo proceso. • Asigna un ID único al nuevo proceso. • Hace una copia de la imagen del proceso padre. • Incrementa los contadores de los archivos propiedad del padre. • Pone al proceso hijo en estado `Listo para Ejecutar'. • Devuelve al proceso padre el ID del hijo y devuelve 0 al proceso hijo. APÉNDICE B. Descripción y Control de Procesos en NT.

9

NT tiene los procesos orientados a satisfacer peticiones y dar soporte a servivios generados por varios ssoo. Los procesos en NT disponen de: • Lo que se conoce como `Acceso de llamada' o señal de acceso (Token Access) que controla si el proceso puede cambiar sus propios atributos. • Los Procesos de NT se implementan como Objetos. • La Estructura nativa de los procesos y servicios que brinda el núcleo de NT es muy simple y de propósito general. • El proceso dispone tambien de la posibilidad de aceder a la descripcion de señales virtuales. • Dispone de una tabla de descriptores donde se hace referencia a una serie de objetos que pertenecen al proceso. (Pág.147 Stallings) • Cada proceso en NT está representado por un objeto, la estructura del objeto biene representada por un conjunto de información: Información vinculada al proceso e información vinculada al hilo. • El objeto proceso contiene referencias y servicios, el hilo es tambien otro tipo de objeto y tiene unos atributos y una serie de funciones. • Un proceso ejecutable puede tener 1 ó N hilos. • Los objetos proceso y los objetos hilo tienen capacidades predefinidas de sincronización. • El núcleo de NT no conserva ninguna relación entre un proceso padre y otro hijo. • El proceso incorpora una tabla de objetos. • Existe un descriptor para cada hilo del proceso. • Un proceso es una entidad correspondiente a un trabajo de usuario ó aplicación que dispone de sus propios recursos. • Un hilo es una entidad de trabajo que es interrumpible de forma que el procesador pueda pasar de un hilo a otro. • Cada proceso queda definido por una serie de atributos y encapsula una serie de acciones ó servicios que puede desempeñar. • Cada vez que NT crea un proceso utiliza la clase de objeto que ya tiene prefijado y coge la mascara de hilo para cederla al nuevo hilo e inicializa sus datos fundamentales, el resto de datos se rellenaran a lo largo de la ejecución. • En NT debe existir al menos un hilo por cada proceso, el hilo original puede generar la aparición de nuevos hilos. • Si tenemos un entorno multiprocesador los distintos hilos del mismo proceso se pueden ejecutar en procesadores diferentes. El hilo servirá para facilitar la concurrencia en ejecuciones de un mismo proceso. • Los hilos de un mismo proceso pueden intercambiar información, este intercambio de información se efectua utilizando un espacio compartido de memoria que se ha asignado al objeto proceso y que los hilos del mismo proceso utilizan para el intercambio. • NT da soporte a la concurrencia entre procesos, varios hilos de un mismo proceso se pueden ejecutar en distintos procesadores. • Como NT da soporte a posibles subsistemas de otros ssoo, es posible que alguno de esos subsistemas no puedan utilizar más de un hilo, en ese caso el proceso solo generará ese hilo y a efectos del subsistema que lo ha invocado, el hilo será algo perteneciente al proceso en sí. APÉNDICE C. Descripción y Control de Procesos en MVS. Tareas de MVS. El SO MVS emplea un entorno de procesos muy estructurado. En MVS la memoria virtual se divide en grandes regiones llamadas `Espacios de Direcciones'. A cada aplicación le corresponde un solo Espacio de Direcciones. 10

La Tarea en MVS constituye la unidad de expedición, MVS puede manejar miles de tareas concurrentemente. Explícitamente, el MVS hace uso de solo 3 estados para un tarea: Listo, Activo (en ejecución) y Esperando. Sin embargo, se puede descargar a memoria secundaria un espacio de direcciones entero. Por tanto, todas las tareas de dicho espacio de direcciones van a quedar suspendidas. Cada tarea está representada por un bloque de control de tarea, existe otro tipo de entidad que se puede expedir, `La petición de servicio'. La Petición de Servicio es una tarea del sistema de la que existen dos clases. Algunas tareas del sistema ofrecen servicios a una aplicación específica y se ejecutan en el espacio de direcciones de dicha aplicación; otras están involucradas en las operaciones realizadas entre espacios de direcciones y no ejecutan en ningun espacio de direcciones de usuario, sino en el espacio de direcciones reservado para el sistema. Estas tareas pueden considerarse en conjunto como el núcleo del MVS. TEMA 3. CONCURRENCIA DE PROCESOS. El objetivo de la concurrencia de los procesos es garantizar que la ejecución de los distintos procesos se llava a cabo de forma sincronizada para que el resultado final sea correcto y el procesador esté el maximo tiempo ocupado. La concurrencia requiere mecanismos que ante determinadas sisuaciones `no se aplique la concurrencia' solo se podrá dar concurrencia si los procesos no comparten recursos. Aquí aparece la sección critica que es la parte del codigo de un proceso que no puede ser ejecutada concurrentemente con otro proceso por que el resultado seria impredecible. En un proceso se distinguen distintas partes ó secciones: • La sección de entrada que consiste en establecer un control para que un proceso entre o no en su sección critica. • La sección critica que será la parte de codigo que no pueda ejecutarse en concurrencia. • La sección de salida es la parte de codigo que posibilita que otros procesos distintos que quieren entrar en su sección critica lo puedan hacer. • La sección residual es la parte de codigo que se ejecuta despues de la sección de salida y no produce efectos en la concurrencia. El problema de la concurrencia es identificar mecanismos que solucionen el problema de la sección critica y cualquier mecanismo debe cumplir tres condiciones: • Exclusion Mutua, que solo un proceso pueda estar en un momento dado en la sección critica. • Progresión, que se avance de manera que un proceso que quiera entrar en la sección critica tenga la certeza de que podrá hacerlo y no se va a parar en un punto. • Espera Limitada, un proceso se puede encontrar con muchos que quieran entrar en su sección critica y habrá que garantizarles que entraran en algun momento. Los mecanismos tienen que derivarse a algoritmos que den soluciones a los tres puntos anteriores, en esto trabajaron Dijstra, Dekker y Peterson. Algoritmo 1 de Dekker. (Posibilita la exclusión mutua pero no la progresión) Var Turno: 0,1 11

P0 While Turno<>0 do {nada} Turno=1 P1 While Turno<>1 do {nada} Turno=0 Algoritmo 2 de Dekker. (No posibilita la exclusión mutua, si la progresión pero si los procesos vienen a la vez el algoritmo no funciona) Var Señal: Array [0..1] of boolean P0 While Señal[1] do {nada} Señal[0]=cierto Señal[0]=falso P1 While Señal[0] do {nada} Señal[1]=cierto Señal[1]=falso Algoritmo 3 de Dekker. (Presenta un problema si entran los dos procesos a la vez, se produce no progresión) Var Señal: Array [0..1] of boolean P0 Señal[0]=cierto While Señal[1] do {nada} 12

Señal[0]=falso P1 Señal[1]=cierto While Señal[0] do {nada} Señal[1]=falso Algoritmo 4 de Dekker. Var Señal: Array [0..1] of boolean P0 Señal[0]=cierto While Señal[1] do begin Señal[0]=falso Señal[0]=cierto End Señal[0]=falso P1 Señal[1]=cierto While Señal[0] do begin Señal[1]=falso Señal[1]=cierto End Señal[1]=falso

13

En este existe un problema, si entran los dos a la vez puede haber bloqueo en ocasiones o podriamos generar una espera ilimitada en uno de los procesos por que el otro cuando sale de la seccion critica, quiere volver a entrar y el otro esta en el tiempo de espera. La solución será establecer la cesion a otro proceso dentro de un turno y no dentro de un tiempo. Algoritmo de Peterson. (Resuelve la axclusión mutua, progresión y espera limitada) Var Flag: Array [0..1] of Boolean Turno: 0..1 Repeat Flag(i):= True Turno:= j While (Flag(j)=true And Turno=j) do Skip Flag(i):= False Until False Algoritmo de Dekker. (Tambien resuelve los tres problemas de la sección critica). Var Vez: Who UsandoP1, UsandoP2: Boolean Process P1 Begin While True do begin UsandoP1:= True While UsandoP2= True do begin If Vez=Proc2 then begin UsandoP1:= False While Vez=Proc2 do {Mantener la prueba} UsandoP1:=True End {if} 14

Vez:= Proc2 UsandoP1:= False End End End Algoritmo de Lamport. (Extiende el de Peterson a N procesos) Var Eligiendo: Array [1..N] of integer Numero: Array [1..N] of integer Process i Var j: integer Begin Eligiendo[i]:= 1 Numero[i]:= 1 + max(Numero[i]..Numero[n]) Eligiendo:=0 For j=1 to N do begin While Eligiendo[j] <> 0 do {Mantener prueba} While (Eligiendo[j] <> 0) And (Numero[j],j < Numero[i],i) do {Mantener prueba} End {for} Numero[i]:= 0 End Los procesos cuando quieran entrar en la sección critica cogen un número y antes de entrar preguntarán si alguien tiene un turno menor al suyo. Eligiendo es si alguien está eligiendo el turno correspondiente y Numero es el numero de turno que nos ha correspondido. Conclusión: Habrá que pensar en mecanismos que hagan esto, pero de manera más sencilla, hay dos tipos: • Mecanismos Hardware. Instrucciones DI y EI

15

Instrucciones TS y SWAP • Mecanismos Software Semaforos Monitores Paso de mensaje Otros MECANISMOS HARDWARE. Sincronizan los procesos y posibilitan la concurrencia, usan las instrucciones DI (disable interrupts) y EI (enable interrupts) del procesador. En el momento en el que entre en la sección critica se hará un DI y cuando termine se ejecutará un EI, esto se denomina `Solución Pesimista' por que restringe la posibilidad de una mayor concurrencia en el sistema. Una solución más optimista es la aparición de unas instrucciones máquina que lo resuelven de forma más eficiente, si no puedo entrar en la sección critica no lo hago pero lo seguiré intentando hasta que el que está acabe y en ese mismo momento yo entraré. Son las instrucciones TS (testear y fijar) y SWAP (intercambiar). TS (es una instucción que no se puede interrumpir) Program TS; Const N = {numero de procesos} Var Cerrojo: Entero Procedure P (i: Entero) Begin Repeat Repeat {nada} Until TS(Cerrojo) Cerrojo:= 0 Forever End; Begin {Programa Principal}

16

Cerrojo:= 0 ParBegin P(1) P(2) ...... P(n) ParEnd End. Program SWAP; Const N = {numero de procesos} Var Cerrojo: Entero Procedure P (i: Entero) Var Clavei: Entero Begin Repeat Clavei:= 1 Repeat Intercambiar (Clavei, Cerrojo) Until Clavei=0 Intercambiar (Clavei, Cerrojo) Forever End; Procedure Intercambiar (r, m) Var Temp: Entero Begin Temp:= m

17

m:= r r:= Temp End; Function TS(i: Entero): Boolean Begin If i=0 then begin i:= 1 TS:= Cierto Else TS:= Falso End {if} End; MECANISMOS SOFTWARE. Antes de entrar en profundidad en ellos vamos a ver una serie de reseñas sobre la Concurrencia de procesos. Existen los denominados Grafos de precedencia, estos son grafos aciclicos (no vuelven para atrás) cuyos nodos corresponden a sentencias individuales. La S1 se debe ejecutar antes que la S2 y S3, estas se pueden ejecutar concurrentemente y la S4 se ejecutará cuando se haya ejecutado S2. Tambien la S4 se podria ejecutar concurrentemente con S3. En estos casos se aplicarán las condiciones de Berstein estas nos dicen si se pueden ejecutar dos sentencias concurrentemente. Toda sentencia tendrá dos conjuntos, R(s) ó conjunto de lectura de la sentencia S y W(s) ó conjunto de escritura de la sentencia S. Dos sentencias se pueden ejecutar concurrentemente si: • El R(Si) ð W(Sj) = {} Conjunto vacio • El R(Sj) ð W(Si) = {} • El W(Si) ð W(Sj) = {} Ejemplo: S1: a = x + y S2: b = z + 1 S3: c = a − b S4: w = c + 1 18

Aplicando las condiciones anteriores nos dará que S1 y S2 se pueden ejecutar concurrentemente, luego se ejecutará S3 y por ultimo S4. • Semaforos Los implemento por primera vez Disktra y sustituyen a todos los anteriores, para su implementación se necesita: • Que la variable tipo semaforo pueda ser accedida por cualquier proceso. • Garantizar que cuando se opere con la variable semaforo no se van a producir interrupciones, habrá que identificar a la variable semaforo como un tipo especial. • Solo se podrá jugar con esa variable con una serie de operaciones especiales. Las operaciones especiales que aceptará el tipo de variable semaforo son: • Inicialización. Init(S) • Wait(S) = P(S) = Down(S) Esta operación genera una resta al valor de S en una unidad y si S<0 el proceso quedará bloqueado. • Signal(S) = V(S) = Up(S) Esta operación incrementa la variable S en una unidad si S<=0 lanzará el proceso a ejecución. Para saber si el mecanismo del semaforo funciona se darán casos generalizables como: Productor − Consumidor, Lectores − Escritores, Cena de los filosofos y Problema de la barberia. • Monitores Permiten exclusión mutua y sincronización de procesos, surgen ante una deficiencia de los semaforos, dejamos en mano del programador la exclusión mutua y la sincronización. Hoave trabajo en los monitores. El monitor es una estructura de datos abstracta, entre su fase de inicialización de variables y la definición de estas tenemos definidos los procedimientos, esto garantiza que solo se va ha permitir a un proceso entrar en el procedimiento que utilize el monitor, lo que nos garantiza la exclusión mutua. Hay una cuestión que NO garantiza la sincronización de procesos y la tendremos que controlar. El monitor facilita una operativa determinada, lo puedo usar a base de definir variables de condición ó `Condition' que quedan definidas dentro del monitor y hacen referencia a un punto de una cola donde puedo encolar y bloquear procesos. Existen dos operaciones usadas con las variables Condition para permitir la sincronización: • CWAIT. Actua sobre una variable condicion previamente definida por nosotros. El proceso que efectue un CWAIT sobre la variable, se bloquea y se encola sobre la variable condicion, dentro del encolamiento los procesos se ordenan (por llegada, por prioridad...). • CSIGNAL. Sobre una variable condición, activa un proceso de los situados en la cola de la variable condicion, el primero de ellos, puede ser que no haya procesos encolados, en este caso CSIGNAL(x) no hará nada. Se producen varias caracteristicas: • Las variables del monitor son exclusivas del monitor y se usan por los procedimientos del monitor. • Un proceso entra en el monitor al invocar uno de sus procedimientos. • No se permite a más de un proceso estar dentro de un monitor en un momento dado, es decir, 19

ejecutando el monitor solo puede haber un proceso. En los monitores tambien existen algoritmos estandar cómo Procuctor−Consumidor. Soluciones propuestas al problema que se dá si CSIGNAL esta en medio de un procedimiento provocando que dos procesos puedan usar el procedimiento. 1ª Solución: El CSIGNAL deberia darse como ultima instrucción del procedimiento del monitor, asi no se da la concurrencia de que haya dos procesos ejecutandose en el monitor. Si no es CSIGNAL la ultima instrucción, hay estudios que bloquean uno de los procesos, Hoave bloqueará al proceso que llama ya que es el proceso que provoca el error y lo mete en una cola de procesos urgentes o prioritarios que tendrá prioridad sobre los procesos que quieran entrar. Cuando un proceso sale del monitor, mira en la cola de priorodad y luego en la cola general. Por esto tendremos tres colas: • Cola de prioridad • Cola de entrada general • Cola por variable condition definida, cada variable condition es un punto donde encolo procesos. 2ª Solución: Lampson y Redell proponen sustituir el CSIGNAL por CNOTIFY que llama al primer proceso encolado en la variable condition y le notifica que va ha ser el proximo proceso que se ejecute en el monitor una vez que haya salido el proceso que efectua el CNOTIFY. Por tanto, genera un despertar de un proceso para que este en espera activa preguntando en todo momento si ha salido el proceso que está en el monitor para entrar él. 3ª Solución: Aparece CBROADCAST(x), que una mejora del anterior, un proceso despertado por CNOTIFY si no se puede ejecutar, con CBROADCAST avisamos a todos los encolados y todos estarán atentos a ver si pueden entrar en el lugar de los advertidos. • Paso de Mensajes Técnica que permite la sincronización de procesos y además nos facilita la comunicación entre allos. La sincronización nos identifica la necesidad de que esté cubierta la exclusión mutua. El paso de mensajes es la única forma de sincronizar procesos en entornos distribuidos, dado que no es posible el intercambio de valores atraves de una variable compartida. Una de las caracteristicas mas significativas del paso de mensaje son las distintas posibilidades que tenemos para llevarlo a cabo. Existen dos operaciones básicas para el paso de mensajes: • SEND (destino, mensaje) • RECEIVE (origen, mensaje) Se pueden dar distintas formas de sincronización: • Envio Bloqueante, significa que el proceso que hace un SEND queda detenido hasta que se cerciora de que el mensaje ha llegado al destino. (acuse de recibo) • Recepción Bloqueante, Se corresponde con los procesos que esperan recibir un mensaje, si el mensaje no le llega, el proceso se bloquea y no continua hasta que no lo reciba. 20

• Envio no Bloqueante, el proceso envia un mensaje y continua, no se preocupa de si llega ó no. • Recepción no Bloqueante, un proceso espera recibir algo, efectua un RECEIVE y si no le llega nada continua su ejecución. El envio bloqueante y la recepción bloqueante, producen un efecto conocido como `Rendezvous' que garantiza una mayor sincronización. El envio no bloqueante y recepción bloqueante, en el destino está obligado a recibir el mensaje para poder continuar, es la más util, envio el mensaje y continuo, el destino esperará el mensaje. El envio no bloqueante y recepcion no bloqueante, significa que nadie debe esperar, por tanto envio y sigo, en el destino se espera recibir algo, si no lo recibe continua. El envio bloqueante y recepción no bloqueante, es absurdo, se quedará casi siempre bloqueado. En la programación concurrente el SEND no bloquea, es lo que normalmente se usa junto con el RECEIVE bloqueado, tiene el fallo de que los procesos se quedan bloqueados antes de llegar al destino, ya que, el que recive puede que no pueda seguir. Existen dos tipos de direccionamiento de mensajes: • Direccionamiento Directo El emisor conoce al receptor, sabe a que proceso va a mandar el mensaje, normalmente se conocerán tanto el emisor cómo el receptor, será más complejo para el SO. • Direccionamiento indirecto Los mensajes no se envian a un proceso determinado, ni los recibirá un proceso determinado, sino que se remitirán a una estructura de datos llamada buzón, que es compartida con el emisor y el receptor, y donde los mensajes se depositaran temporalmente. Creación de Buzones: • Que los buzones los facilite el SO, se pide al SO que cree el buzón • Que el buzón lo cree uno de los procesos La asociación de los Buzones a los Procesos puede ser: • Estática. Un proceso se asocia a un buzón, se establece un buzón privado para compartir entre el emisor y el receptor. • Dinámica, los buzones dinamicos se usan cuando existen multiples emisores que actuan sobre un mismo buzon de manera que los emisores pueden enviar mensajes a distintos buzones según las caracteristicas del proceso en cuestión. En este tipo de procesos actuan las operaciones Conectar/Desconectar Buzón. Formato de los Mensajes: Los mensajes tienen dos grandes bloques de información: • Cabecera del mensaje, guarda información de control e identificación, se guarda el origen y el destino del mensaje, longitud del mensaje, tipologia ... 21

• Cuerpo del mensaje, donde va la información del mensaje. Otra caracteristica en relación con el formato de los mensajes es si tienen Formato Fijo (tamaño de mensaje estándar) ó Formato Variable (el tamaño varia). Los mensajes se almacenan y pueden gestionarse de distintas maneras, esto se cocoze como `Disciplina de Colas', la disciplina normal es aplicar FIFO aunque los mensajes se pudieran ordenar por criterios de prioridad, otra disciplina de cola es la posible investigación que los procesos de recepción hagan de la cola de mensajes, en esta última existen dos variantes: Rigida ó por investigación de los procesos receptores. • Otros (Región Critica) Es un mecanismo introducido por Hansen y Hoave, es una construcción que permite sustituir al semáforo para asegurar que el programador no se equivoca en el planteamiento de los controles de una seccion critica al utilizar semáforos. Var {variables compartidas que solo pueden ser utilizadas dentro de una region critica} V: Shared T Region V do Sentencias {solo un procedimiento puede estar dentro de esta region} ........ Region Z do Sentencias Ej: Region V When C do S, quiere decir que cuando se define a nivel de region, si cumple la condición C pasa a ejecutar S y si no la cumple no lo hará. Esto genera que el proceso se encola asociado a la variable compartida manejada en esa región. El siguiente codigo hará lo mismo pero con la condición C dentro de la región: Region V do begin .......... .......... Await ( ) .......... End; EJERCICIOS FOTOCOPIAS. • Exclusión mutua con Paso de Mensajes. Initiate, se lanzan a ejecutar todos los procesos de usuario que haya. While True, ejecuta el procedimiento permanentemente.

22

Sincronizamos los N procesos para que no entren en la sección critica con un RECEIVE que va al buzón a recibir un mensaje y quien de el primer RECEIVE puede entrar en la sección critica, si quiere entrar otro proceso efectuará un RECEIVE y cómo ya no existe el mensaje, no puede entrar en la seccion critica. Cuando salgo de la sección critica efectuo un SEND al buzón y le mando un mensaje para que otro proceso lo reciba y pueda entrar en la seccion critica. • Productor / Consumidor con Paso de Mensajes. Mando al buzón `Puede Producir' N mensajes, tantos como la capacidad del buzón. El proceso productor no puede producir mas que el limite de mensajes preestablecidos y sabrá que puede producir cuando efectue un RECEIVE y reciba algún mensaje. • Nota: Problemas Clasicos de Sincronización: Productores / Consumidores (no se puede consumir algo que no se haya producido) Lectores / Escritores (Si un proceso escribe, modifica el contenido, por tanto, el que lea debe leer despues de que se haya escrito para leer los datos actualizados. Otro caso será leer antes de escribir, la prioridad la tendrán los lectores. • Lectores / Escritores por medio de Semáforos con prioridad para los Lectores. El contador de lectores lo ponemos a 0 y con PARBEGIN mandamos a ejecución concurrente los lectores y los escritores. Contador de lectores es la misma para lectores y escritores. En el procedimiento Lectores, protegemos con el semáforo X el uso de la variable contador de lectores porque puede haber N procesos, mientras haya un lector se hará un WAIT a los escritores. Si por ejemplo tengo un proceso Escritor que está escribiendo, tres procesos Escritores que esperan escribir y me viene un proceso Lector, será cuestión de azar el que me entre un Lector ó un Escritor, por tanto este caso habrá que perfeccionarlo. • Lectores / Escritores por medio de Semáforos con prioridad para los Escritores. Lanzare la ejecución igual que el anterior, el contador de lectores y contador de escritores estarán a 0, para controlar el acceso al contador de lectores se hace un acceso a la variables semaforo Z, garantizamos que un solo lector estará entre el WAIT(z) y el SIGNAL(z). El leer no esta protegido con ningun semaforo, ya que se puede hacer concurrentemente con otro proceso, cuando deje de leer haremos una protección sobre el contador de lectores. En el procedimiento de Escritores, si el contador de escritores es igual a 1, efectuo un WAIT(lsem) parando a todos los lectores, ahora vamos a escribir y habrá que efectuar un WAIT(s) para saber si lo puedo hacer, esto me lo condiciona el WAIT(esem) del proceso Lector, esto pretende que todos los lectores que hay lean todo lo que tengan que leer y salgan antes de que aparezca un escritor, por tanto, esto hace que todos los lectores se vayan antes de actualizar los datos, cuando ya no haya lectores, activamos la posibilidad de escribir con SIGNAL(esem) y cuando se ha escrito, el proceso escritor sale de la seccion critica diciendo que si no vienen más escritores, sigan los lectores y si viene algún escritor, que este escriba. • Algoritmo del Barbero. Existen dos modalidades, el Barbero Equitativo (barberia2) y el No Equitativo (barberia1). 23

El Barbero No Equitativo (barberia1), en el procedimiento Barbero, `Cortar Pelo' es una sección critica que cuando acaba efectua un SIGNAL(terminado) que repercute sobre el proceso Cliente que ya puede levantarse de la silla. El WAIT(dejarsilla) significa que cuando el cliente se levante efectuara un SIGNAL para que alguien ocupe su lugar. Clientes habrá un maximo de 20, barberos son 3 y cajeros 1 que deberá ser uno de los barberos, el cajero actua cuando el cliente deja la silla y va ha pagar. Cada proceso debe realizar unas iniciativas reflejadas en sus procedimientos y existen semáforos particulares en cada procedimiento para proteger su sección critica. El Barbero Equitativo (barberia2). La diferencia es la personalización, aquí lo que se pretende es controlar que alguien se sienta y se levanta cuando ha terminado, la duración del tratamiento de un cliente puede ser mayor ó menor. Tenemos la misma capacidad 20, un sofá de 4 plazas y 3 barberos, se incorpora un `extmut1' que es un semáforo para una sección critica y luego un contador que llevará la cuenta de los clientes que entran y las proporciona un número, asi los podemos personalizar. El `terminado' será un Array de los 50 clientes que puede haber. La operativa es muy semejante, el cliente antes de entrar tiene un semáforo que mira la capacidad, al entrar está `Contador' que es compartida y hay que protegerla, la incrementamos y le asignamos el número al cliente que ha entrado, luego se quiere sentar en el sofá y efectuará un WAIT(sofa) para haber si puede (no se le podrá atender sin antes haberse sentado en el sofá), ahora mira haber si hay alguna silla de barbero libre, cuando haya alguna libre, se levantará del sofá con SIGNAL(sofa) y se sienta en la silla del barbero. Poner_Cola_1(numcliente) y SIGNAL(cliente_listo), quiere decir que ya se ha sentado y está listo, a continuación el barbero hace su trabajo en una seccion critica y cuando ha terminado efectua un WAIT(terminado_cliente), el cliente se levanta y va a pagar haciendo un SIGNAL(pago) y espera el recibo, cuando se lo dan sale de la tienda. • Problema de los Filosofos Comensales. En el procedimiento Filosofos la pauta de acción es: − Pensar − Coger los palillos − Comer − Dejar los palillos Todo esto anidado en un While(true). Test(i), está dentro de una sección critica, es decir, solo lo puede hacer un filosofo a la vez. Down(mutex), es que se queda hay el proceso si no puede coger los palillos, además no puede haber concurrencia entre coger y dejar. • Productor / Consumidor con buffer acotado por medio de Monitores. Primero existe un programa Productor / Consumidor `Monitor_Buffer_Acotado' donde aparece la definición del monitor. Lo que mandamos a ejecutar concurrentemente son los procesos Productor y Consumidor, pudiendo haber N productores y N consumidores. El productor produce y una vez producido algo va a Añadir (es un proceso del monitor). Para invocar a un 24

proceso del monitor hay que llamarlo con `Monitor.Nombre_del_Procedimiento'. En Añadir se invoca al monitor, la primera parte del monitor hace referencia a la edfinición de variables internas al monitor, existen la variables Condition (no_lleno, no_vacio) establecidas con el proposito de parar los procesos y encolarlos, luego viene el cuerpo del monitor que recoge sus procedimientos y por último la inicialización de las variables. Cuando se invoca a Añadir miramos si el número de elementos que existen ya producidos es igual a N, si esto es cierto, no podré producir más, por tanto, el proceso Productor tiene que detenerse con CWAIT(no_lleno), si por el contrario se puede producir, lo que se va a añadir se guarda en el buffer en la posición siguiente a la última que se a ocupado y dejamos dispuesto el índice de ese buffer en el siguiente elemento. (Mod N) es para hacer que el buffer sea circular y luego libero el proceso que esta esperando por una unidad nueva producida. Cuando efectuo un CSIGNAL a un encolamiento, si no hay nada en la cola, no hace nada. El proceso Consumidor, toma del buffer y lo consume, para tomar invoca al monitor, si el monitor no tiene ningún proceso dentro admite la petición y accede a `Tomar' este mira si Contador=0 (no hay nada producido) y si esto es asi se para, si hay algo que consumir cogo lo que me corresponde según el indice `Sigsalida' y lo incremento para el próximo elemento, resto 1 a Contador y efectuo un CSIGNAL(no_lleno) para que se pueda producir una unidad más. Los CSIGNAL se deben poner como última instrucción para evitar que haya más de un proceso dentro del monitor, si no lo hacemos asi, puede entrar más de un proceso en el monitor y habria que encolar los procesos como `urgentes'. TEMA 4. CONCURRENCIA DE PROCESOS, INTERBLOQUEO E INANICIÓN. (ABRAZOS MORTALES). La concurrencia significa un solo procesador y multiples procesos a ejecutarse, la sincronización permite que los procesos se ordenen para que puedan ejecutarse adecuadamente y bien. Interbloqueo significa que los procesos que están compitiendo por el uso del procesador no se bloqeen entre ellos por que si lo hacen ninguno va ha poder continuar su ejecución y por tanto, no terminarán. Uno de los objetivos del SO en cuanto a la concurrencia es fomentarla para que la CPU esté el mayor tiempo ocupada pero esto no tiene sentido si los procesos se bloquean. Existen 3 motivos necesarios pero no estrictamente suficientes para que se produzca interbloqueo: • Exclusión mutua Que el recurso que se va a utilizar, se utilizará exclusivamente y no se podrá compartir. • No apropiatividad. La no pisibilidad de hacerse con el recurso apropiandose del mismo. • Situación de retener y no liberar. Retener el recurso que tengo y no liberarlo para otros procesos que lo necesiten. Existe otra 4ª condición, dandose esta última simultaneamente con las otras tre anteriores ya será condición 25

necesaria y suficiente para que exista interbloqueo. • Circulo vicioso de espera. El resultado de esto es el interbloqueo que se entiende como la competencia de dos ó más procesos para hacerse con el uso de uno ó más recursos, un solo proceso no crea interbloqueo. Ejemplo: Para determinar si existe interbloqueo y quien lo produce podemos recurrir a un `Grafo de Asignación de Recursos'. P ={P1, P2, P3} R ={r1, r2, r3, r4} E ={(P1,r1), (P2,r3), (P2,r1), (P2,r2), (P1,r2), (P3,r3)} r1= 1, r2=2, r3=1, r4=4 : Estas son el número ed instancias de cada recurso. No están en interbloqueo por que no existe ningún circulo en el grafo, no hay ningún bucle. ¿Y si el P3 solicita r2? Entonces se crean dos bucles: P1 − r1 − P2 − r3 − P3 − r2 − P1 P2 − r3 − P3 − r2 − P2 Existen algoritmos que examinan constantemente esta situación:

P1 P2 P3

r1 X @

r2 @ @ X

r3

r4

X @

Donde: @ = Tiene asignado X = Solicita Ninguno puede continuar y cualquier proceso que entre y pida el r1, r2 ó r3 se bloqueará. MECANISMOS PARA EVITAR EL INTERBLOQUEO. Existen tres métodos distintos: • Método de la Prevención: Prevenir alguna de las cusas que generan la aparición del interbloqueo, si se dan las tres primeras condiciones puedo salir del interbloqueo pero como se de tambien la 4ª es imposible. • Con la exclusión mutua significa que haga que un recurso pueda compartirse, pero hay determinados recursos que no se pueden compartir. El luchar contra la exclusión mutua dependerá del tipo de recurso, no existe ninguna alternativa. 26

• Con la no apropiatividad hay una alternativa, antes de comenzar el proceso declaramos los recursos que este necesita y esperamos a que estén todos disponibles para entrar en ejecución, el problema de esto es que se utilizarán muy poco los recursos además, podemos entrar en inhanición, ya que los procesos pueden estar pendientes de los recursos y no se les atiende. • Con retener y no liberar, ante esta situación se puede avtuar de dos formas: 1º cuando pide algo y no se lo conceden, lo que tiene el proceso lo libera para los demás ó 2º que actue el SO y le quite los recursos que tenga automaticamente. Aquí surgen dos problemas: 1º El hecho de retirar recursos a los procesos significa que debo hacer que el proceso se reanude desde algún punto sin que empieze de Zero, estos son los CheckPoint que son imágenes del proceso en un punto, estos puntos no se pueden colocar arbitrariamente en cualquier sitio. 2º El otro problema es la inhanición ya que yo he cedido todo y me tienen que devolver todo en ese punto. • Con el circulo vicioso de espera es un tema que se puede resolver de forma sencilla. ¿Por qué tengo procesos que se bloquean? Es problema de sincronizar los avances de los procesos en el mismo sentido. Se trata de que a los recursos se les asigne un número en orden descendente de manera que estén en el sentido de avance de ejecución de los procesos, el proceso hará las peticiones en orden creciente y así los recursos del primer proceso serán mayores que los del segundo y evito las vueltas atrás que son generalmente las que producen el interbloqueo. Los recursos pueden ser de dos tipos: • Reutilizables: Los necesitan distintos procesos pero no se ceden definitivamente. • Consumibles: Los acaba un proceso, son solo para este. • Método de la Detección. Es mucho más liberal que el anterior, no establecemos medidas de prevención, solo tomamos medidas si detectamos la aparición del interbloqueo. Periodicamente lanzo a ejecutar un proceso que contiene un algoritmo para ver si me encuentro en interbloqueo. El primer problema es que el simple hecho de lanzar otro proceso detector ya es una carga añadida, el segundo problema es que si detectamos que hay interbloqueo ¿Qué hacemos? Las medidas que se toma pueden ser drásticas como eliminar los procesos bloqueados ó medidas más pensadas como coger todos los procesos en interbloqueo y situarlos en su último Checkpoint volviendolos a lanzar a ejecución. Otra via es ir eliminando procesos y volver a comprovar por fases si hay interbloqueo, siguiendo eliminando hasta que este desaparezca. Otro supuesto en el cual el intento es apropiarse de los recursos para ir cediendolos de un proceso a otro. En los casos en los que se apliquen los dos últimos supuestos (eliminar y apropiar) ¿Qué proceso debo seleccionar para eliminar ó apropiar? Aquí aplicaremos distintos criterios: • El proceso que tiene menor tiempo de CPU concedido. • Eliminar los procesos que más tiempo les quede por ejecutar • Aplicar la prioridad. • El número de recursos asignado, a mayor número de recursos asignados, le facilitaremos la labor para que acabe. • Método de Evitación ó Predicción. Se considera el más edecuado, consiste en hacer comprobaciones a los procesos antes de que entren a ejecutarse ó cuando soliciten otro recurso para verificar en que situación ó estado quedaria el sistema. El sistema puede quedar en dos posibles estados: • Estado Seguro: Es que hay al menos una combinación que permite que ese proceso se pueda ejecutar 27

y terminar, y el resto de procesos tambien. Si se encuentra en estado Seguro se le concederan las peticiones al proceso. • Estado No Seguro: Es lo contrario de lo anterior, si estamos en este estado, las peticiones no se concederán al proceso y este solicitara los recursos en otro momento. Para implementar estos estados se necesita: • Una aceptación ó negativa al inicio del proceso. • Una negativa ante una nueva asignación de recursos. El SO debe saber cuales son las necesidades máximas del proceso desde el principio, para esto se guarda una estructura de datos que representa al número de recursos de cada tipo R, otra estructura con el número de unidades disponibles de cada recurso D, tambien habrá una `Matriz Demanda' en la que se definirán las necesidades máximas que cada proceso requiere. R = (r1, r2, r3, ...,r n) Recursos D = (rd1, rd2, rd3, ...,rd n) Disponible Demanda = r1p1 r2p1 r3p1 .......... r np1 r1p2 r2p2 r3p2 .......... r np2 r1p3 r2p3 r3p3 .......... r np3 ........ .......... ........ .......... ........ r np1 r np2 r np3 .......... r npn Tambien está la `Matriz Asignación' en la que se lleva referencia de todos los recursos asignados al proceso. Asignación = Ar1p1 Ar2p1 Ar3p1 .......... Ar np1 Ar1p2 Ar2p2 Ar3p2 .......... Ar np2 Ar1p3 Ar2p3 Ar3p3 .......... Ar np3 ........ .......... ........ .......... ........ Ar np1 Ar np2 Ar np3 .......... Ar npn De todo esto se puede deducir la `Matriz Necesidad', que nos informa de cuantas instancias de cada recurso necesita cada proceso para completar su ejecución. Necesidad = (r1p1−Ar1p1) (r2p1−Ar2p1) (r3p1−Ar3p1) .......... (r np1−Ar np1) (r1p2−Ar1p2) (r2p2−Ar2p2) (r3p2−Ar3p2) .......... (r np2−Ar np2) (r1p3−Ar1p3) (r2p3−Ar2p3) (r3p3−Ar3p3) .......... (r np3−Ar np3) .................... .................... .................... .......... .......................

28

(r1pn−Ar1pn) (r2pn−Ar2pn) (r3pn−Ar3pn) .......... (r npn−Ar npn) La comprobación para verificar que todo es correcto será: • El sumatorio por columnas de la matriz asignación seria los recursos de tipo X asignados a todos. La suma de estos recursos mas el vector disponible tiene que coincidir con los recursos totales. Recursos que he declarado − Recursos que tengo asignados = Recursos libres • Toda petición de demanda que haga un recurso, como máximo debe ser menor ó igual <= a lo declarado, es decir: r1p1 <= r1 r2p1 <= r2 La comprobación para el inicio del proceso dice: Los recursos totales deben ser >= que las asignaciones máximas del conjunto de todos los procesos + la asignación máxima del nuevo proceso, si esto se cumple, el nuevo proceso podrá entrar a ejecutarse. El problema de la negativa a la asignación de nuevos recursos (cuando se solicitan), los controles serán los siguientes: • Vector Solicitud, controla que la solicitud i <= Necesidad i, para que no pida nadie algo que supere sus necesidades, si se pasa eliminaremos el proceso. • Comprobar si la Solicitud i <= Diponible, si es asi, se atenderá. • La solicitud se añade provisionalmente al vector asignación de ese proceso, entonces la solicitud aumenta la asignación y disminuyen las necesidades, por tanto actualizare las estructuras de datos: Asignación i = Asignación i + Solicitud i Necesidad i = Necesidad i − Solicitud i Disponible = Disponible − Solicitud i Todo esto es provisional hasta que pueda garantizar que el sistema se encuentra en estado Seguro, para saberlo tengo que aplicar el `Algoritmo del Banquero' y luego el `Algoritmo de Seguridad'. Se llama algoritmo del banquero por que se está relacionando esta operación con un banco, de manera que, el banquero va cediendo recursos a los procesos, pero siempre que los procesos tengan recursos (el banco no te dá más de lo que tú tienes). Algoritmo del Banquero. • Solicitud i <= Necesidad • Solicitud i <= Disponible • Asignación i = Asignación i + Solicitud i Necesidad i = Necesidad i − Solicitud i Disponible = Disponible − Solicitud i Van juntos:

29

1º se ejecuta el Banquero 2º se ejecuta el de Seguridad Algoritmo de Seguridad. • Trabajo = Disponible (para no machacar disponible) Para todo i Acabar[i] = Falso • Hallar un i tal que Acabar[i] = Falso y además Necesidad i <= Trabajo Si no existe tal i ir al paso 4 • Trabajo = Trabajo + Asignación[i] Acabar[i] = Cierto Ir al paso 2 • Si Acabar[i] = Cierto, para todo i entonces el estado es Seguro Si no, el estado es No Seguro Si despues de aplicar el algoritmo de Seguridad me dá seguro, la asignación del Banquero la dejo como definitiva, si no, debo deshacer la asignación hecha por el Banquero. El estado seguro identifica una combinación para que todos los procesos acaben, pero no se garantiza, ya que, la probabilidad de una situación contraria es muy baja. Algoritmo de Detección. • Trabajo = Disponible Acabar[i] = Falso, si Asignación i <> 0 Acabar[i] = Cierto, si Asignación i = 0 • Encontrar un i tal que Acabar[i] = Falso y Solicitud i <= Trabajo Si no existe ir al paso 4 Si existe ir al paso 3

30

• Trabajo = Trabajo + Asignación i Acabar[i] = Cierto Ir al paso 2 4− Si Acabar[i] = Falso para algún 1<=i<=n, entonces hay InterBloqueo. El algoritmo de Detección, se aplica con el método de detección del interbloqueo, este se puede detectar de varias formas: • Viendo haber si existen ciclos en el grafo de asignación de recursos. • Aplicando un algoritmo que se basa en manejar las mismas estructuras de datos que el algoritmo de predicción. Este método se aplica cada vez que se realiza una nueva solicitud. Ejercicio. InterBloqueo. Tenemos un sistema con 3 recursos A, B, y C. Del recurso A se dispone de 10 unidades, del B 5 unidades y del C de 7 unidades. Existen 5 procesos en el sistema P0...P4, estos procesos han declarado unos maximos de recursos y yan han sido asignados a esos procesos los recursos de la matriz Asignado. El P1 hace una nueva solicitud y solicita 1 unidad de A y 2 unidades de C. ¿Podemos conceder esa petición? Asignado A B

C

Maximo A B

C

Disponible A B

31