Os 5722k

ÍNDICE. 2.1 Concepto de Proceso. ..................................................................................................................... 3 2.2 Estados y Transiciones de los Procesos. .......................................................................................... 6 2.3 Procesos Ligeros (Hilos o Hebras). ................................................................................................... 9 2.4 Concurrencia y Secuenciabilidad. .................................................................................................... 12 2.4.1 Exclusión Mutua de Secciones Críticas. ............................................................................... 15 2.4.2 Sincronización de Procesos en S.C. ...................................................................................... 19 2.4.2.1 Mecanismo de Semáforos. ...................................................................................... 23 2.4.2.2 Mecanismo de Monitores. ...................................................................................... 25 2.4.3 Interbloqueo (DeadLock). .................................................................................................... 30 2.4.3.1 Prevención. .............................................................................................................. 32 2.4.3.2 Detección. ................................................................................................................ 33 2.4.3.3 Recuperación. .......................................................................................................... 34 2.5 Niveles, Objetivos y Criterios de Planificación................................................................................. 35 2.6 Técnicas de istración del Planificador. .................................................................................. 40 2.6.1 FIFO. ..................................................................................................................................... 41 2.6.2 SJF. ....................................................................................................................................... 43 2.6.3 RR. ........................................................................................................................................ 45 2.6.4 Queves Multi-level. .............................................................................................................. 46 2.6.5 Multi-level Queves. ............................................................................................. 48

Introducción. Los sistemas operativos manejan muchísimos procesos, todos estos procesos se llevan a cabo con ayuda del procesador, En este trabajo se encuentra una información muy completa de la forma en que se realizan los procesos en el procesador, entre ellos se encuentra la forma de planificación de los procesos, los tipos de interbloqueo y las técnicas de istración de procesos. En el desarrollo del trabajo presentamos las definiciones que cada tipo de planificación utiliza, los objetivos que utilizan para ser la base de cada estructura de los procesos, presentamos algunas técnicas de istración en las que indicamos cual es la forma en que se deben de implementar para realizar operaciones con el procesador o para hacer funcionar mejor el procesador.

[2]

2.1 Concepto de Proceso. Un proceso no es más que un programa en ejecución e incluye los valores actuales del contador de programa, los registros y las variables. Conceptualmente, cada uno de estos procesos tiene su propia “U” virtual. Desdé luego en la realidad la verdadera U conmuta de un proceso a otro pero para entender el sistema es mucho más fácil de seguir la pista a la forma en la que la U conmuta de un programa a otro. Esta rápida conmutación se denomina multiprogramación. Con la U conmutado entre los procesos, la rapidez con que un proceso realiza sus cálculos no es uniforme y probablemente ni siquiera reproducible si los mismos procesos se ejecutan otra vez. por tanto, los procesos no deben programarse basándose en supuestos acerca de los tiempos. Considere, por ejemplo, un proceso de e/s que inicia una cinta continua para restaurar archivos respaldados, ejecuta un ciclo vacío 10000 veces para permitir que la cinta alcance la velocidad de trabajo y luego emite un comando para leer el primer registro. Si la U decide conmutar a otro proceso durante el ciclo vacío, es posible que los procesos de cinta no se ejecuten otra vez sino hasta después de que el primer registro haya pasado por la cabeza de lectura. Cuando un proceso tiene requisitos de tiempo real críticos como este, es decir, cuando ciertos eventos deben ocurrir en cierto número de milisegundos, se deben tomar medidas especiales para asegurar que así ocurran. Normalmente, empero, los procesos no resultan afectados por la multiprogramación subyacente de la U ni las velocidades relativas de los diferentes procesos. La diferencia entre un programa y un proceso es sutil, pero crucial. Tal vez una analogía ayude a aclarar este punto. Consideremos un computologo con inclinaciones gastronómicas que está preparando un pastel de cumpleaños para su hija. Él cuenta con una receta para pastel de cumpleaños y una cocina bien abastecida de las entradas necesarias: harina, huevos, azúcar, extracto de vainilla, etc. en esta analogía, la receta es el programa (es decir un algoritmo expresado en alguna flotación apropiada), el computologo es el procesador (U) y los ingredientes del pastel son los datos de entrada. el proceso es la actividad de nuestro pastelero consistente en leer la receta, obtener los ingredientes y hornear el pastel.

[3]

Imaginemos ahora que el hijo del computologo llega corriendo y llorando, diciendo que le pico una abeja. El computologo registra el punto en que estaba en la receta (guarda el estado del proceso actual), saca un libro de primeros auxilios, y comienza a seguir las instrucciones que contiene. Aquí vemos como el procesador se conmuta de un proceso (hornear) a un proceso de más alta prioridad (istrar cuidados médicos), cada uno con un programa diferente (receta vs primeros auxilios). Una vez que se ha atendido la picadura de abeja, el computologo regresa a su pastel, continuando en el punto donde había interrumpido. la idea clave aquí es que un proceso es una actividad de algún tipo: tiene programa, entrada, salida y un estado. Se puede compartir un procesador entre varios procesos, usando algún algoritmo de planificación para determinar cuándo debe de trabajar en un proceso para atender a uno distinto. Informalmente, un proceso es un programa en ejecución. La ejecución de un proceso debe proceder de manera secuencial. Es decir, en cualquier instante, cuando más una instrucción se estará ejecutando nombre del proceso. un proceso es más que el código del programa (también conocido como sección de texto); tambien incluye la actividad actual, representada por el valor del contador de programa y el contenido de los registros del procesador. Generalmente, un proceso también incluye la pila (stack) del proceso, que contiene datos temporales (como los parámetros de subrutinas, direcciones de retorno y variables temporales), y una sección de datos que contiene variables globales. Hacemos hincapié en que un programa por sí solo no es un proceso; un programa es una entidad pasiva, como el contenido de un archivo guardado en disco, mientras que un proceso es una entidad activa, con el contador de programa especificando la siguiente instrucción que se ejecutara, y un conjunto de recursos asociados. Aunque podría haber dos procesos asociados al mismo programa, de todas maneras se consideran como dos secuencias de ejecución distintas. Por ejemplo, varios s podrían estar ejecutando copias del programa editor. Cada una de estas es un proceso aparte, y aunque las secciones de texto sean equivalentes, las secciones de datos variaran. También es común tener un proceso que engendra muchos procesos durante su ejecución. [4]

Jerarquía de procesos. Los sistemas operativos que manejan el concepto de proceso deben contar con algún mecanismo para crear todos los procesos necesarios. En los sistemas muy sencillos, o en los diseñados para ejecutar solo una aplicación (por ejemplo, controlar un dispositivo en tiempo real), es posible que, cuando el sistema de inicia, todos los procesos que puedan necesitarse estén presentes. Sin embargo, en la mayor parte de los sistemas se necesita algún mecanismo para crear y destruir procesos según sea necesario durante la operación. En minix, los procesos se crean con la llamada del sistema fork (bifurcar), que crea una copia idéntica del proceso invocador. El proceso hijo también puede ejecutar fork, así que es posible tener un árbol de procesos. En otros sistemas operativos existen llamadas al sistema para crear un proceso, cargar su memoria y ponerlo a ejecutar. Sea cual sea la naturaleza exacta de la llamada al sistema, los procesos necesitan poder crear otros procesos. Obsérvese que cada proceso tiene un padre, pero cero, uno, dos, o más hijos. Como ejemplo sencillo del uso de los árboles de procesos, veamos la forma en que minix se inicializa a si mismo cuando se pone en marcha. Un proceso especial, llamado mit, está presente en la imagen de arranque. Cuando este proceso comienza a ejecutarse, lee un archivo que le indica cuantas terminales hay, y luego bifurca un proceso nuevo por terminal. Estos procesos esperan a que alguien inicie sesión. Si un inicio de sesión ( ) tiene éxito, el proceso de inicio de sesión ejecuta un shell para aceptar comandos . Estos comandos pueden iniciar más procesos, y así sucesivamente. Por tanto, todos los procesos del sistema pertenecen a un mismo árbol, que tiene a mit en si raíz. (El código de mit no se alista en este libro, y tampoco el del shell. Había que poner un límite en algún lado).

[5]

2.2 Estados y Transiciones de los Procesos. A medida que un proceso se ejecuta, cambia de estado. El estado de un proceso está definido en parte por la actividad actual de ese proceso. Cada proceso puede estar en uno de los siguientes estados: PROCESO - NUEVO (NEW). - EN EJECUCION (RUNNING). - EN ESPERA (WAITING).

-

LISTO (READY).

-

TERMINADO (TERMINATED).

ACTIVIDAD EL PROCESO SE ESTA CREANDO. SE ESTAN EJECUTANDO. El PROCESO ESTA ESPERANDO QUE OCURRA ALGUN SUCESO (COMO LA TERMINACION DE UNA OPERACIÓN DE E/S O LA RECEPCION DE UNA SEÑAL). EL PROCESO ESTA ESPERANDO QUE SE LE ASIGNE A UN PROCESADOR. EL PROCESO TERMINO SU EJECUCION.

Estos nombres son arbitrarios, y varían de un sistema operativo a otro; sin embargo, los estados que representan se encuentran en todos los sistemas. Ciertos sistemas operativos hacen distinciones todavía más sutiles entre estados de los procesos. Es importante tener presente que solo un proceso puede estar ejecutándose en cualquier procesador en un instante dado, pero muchos procesos pueden estar listos y esperando. Un proceso sale de un sistema en dos pasos. Primero, el proceso termina cuando liega al punto normal de terminación, cuando se abandona debido a un error irrecuperable o cuando otro proceso con la debida autoridad hace que el proceso abandone, la terminación pasa el proceso al estado terminado. En este punto, el proceso ya no se elige más para la ejecución. Sin embargo, las tablas y otra información asociada con el trabajo son conservadas temporalmente por el sistema operativo. Esto le da tiempo a otros programas auxiliares o de soporte para extraer la información necesaria. Por ejemplo, puede ser que un programa de contabilidad necesite registrar el tiempo de procesador y otros recursos usados por el proceso con fines de facturación. Un programa de utilidades puede tener [6]

que extraer información sobre la historia del proceso con fines relativos a un análisis de uso o de rendimiento. Una vez que estos programas han extraído la información necesaria, el sistema operativo ya no necesita mantener más datos relativos al proceso y estos se borran del sistema.  Nulo  nuevo: se crea un nuevo proceso para ejecutar un programa.

 Nuevo  listo: el sistema operativo pasara a un proceso del estado nuevo al estado listo cuando esté preparado para aceptar un proceso más. La mayoría de los sistemas ponen un límite en función del número de procesos existentes o en la cantidad de memoria virtual dedicada a los procesos existentes. El motivo de este límite es asegurar que no haya tantos procesos activos como para degradar el rendimiento.

 Listo  ejecución: cuando es hora de seleccionar un nuevo proceso para ejecutar, el sistema operativo elige a uno de los procesos del estado listo.  Ejecución  terminada: el proceso que se está ejecutando es finalizado por el sistema operativo si indica que termino 0 si se abandona.  Ejecución  listo: la razón más común de esta transición es que el proceso que está en ejecución ha alcanzado el tiempo máximo permitido de ejecución interrumpida; casi todos los sistemas operativos con multiprogramación imponen este tipo de norma de tiempo. Hay otras causas alternativas para esta transición que no están implementadas en todos los sistemas operativos. Por ejemplo, si el sistema operativo asigna diferentes niveles de prioridad a los diferentes procesos. Supóngase que un proceso “a” esta ejecutándose con un cierto nivel de prioridad y que el proceso “b”, con un nivel de prioridad mayor, está bloqueado. Si el sistema operativo se entera de que el suceso que “b” estaba esperando se ha producido, pasando así “b” ha estado listo, entonces puede interrumpir al proceso “a” y expandir a “b”. Por último, otro caso es que un proceso ceda voluntariamente el control del procesador.  Ejecución  bloqueada: un proceso se pone en el estado bloqueado sus e solicita algo por lo que debe esperar. Las solicitudes al sistema operativo suelen ser en forma de llamadas a [7]

servicios del sistema, es decir , llamadas desde el programa que esta ejecutándose a un procedimiento que forma parte del código del sistema operativo.  Bloqueado  listo: un proceso que está en el estado bloqueado pasara al estado listo cuando se produzca el suceso que estaba esperando.  Listo  terminado: en algunos sistemas, un padre puede terminar con un proceso hijo en cualquier momento. Además, si el padre termina, todos los hijos asociados con él pueden ser finalizados.  Bloqueado  terminado: se aplica el mismo comentario que en el caso anterior.

[8]

2.3 Procesos Ligeros (Hilos o Hebras). Es un proceso tradicional hay un solo hilo de control y un solo contador de programa en cada proceso. Sin embargo. Algunos sistemas operativos modernos manejan múltiples hilos de control dentro de un proceso. Estos hilos de control se llaman solo hilos, ocasionalmente, procesos ligeros. Recordemos que un proceso se define por los recursos que usa y por el lugar donde se ejecuta. Sin embargo, hay muchos casos en los que sería útil compartir los recursos y acceder a ellos de forma concurrente. Esta situación es similar al caso en que se hace una llamada al sistema bifurcar (folk) con un nuevo contador de programa, o hilo de control ejecutándose dentro del mismo espacio de direcciones. Este concepto es tan útil que varios sistemas operativos nuevos incluyen un mecanismo para apoyarlo mediante hilos. Un hilo, también llamado proceso ligero (lwp,lightweight procesos), es una unidad básica de utilización de la U, y consiste en un contador de un programa, un juego de registros y un espacio de pila. El hilo comparte con sus hilos pares la sección de código, sección de datos y recursos del sistema operativo como archivos abiertos y señales, lo que se denomina colectivamente una tarea. Un proceso tradicional o pesado es igual a una tarea con un solo hilo. Una tarea no hace nada si no hay hilos en ella, y un hilo debe estar en una y solo una tarea. El extenso compartir hace que la conmutación de la U entre hilos pares, y la creación de hilos, sea económica en comparación con las conmutaciones de contexto entre procesos pesados. Aunque una conmutación de contexto de hilos también requiere un cambio de conjunto de registros, no hay que realizar operaciones relacionadas con la gestión de memoria. Al igual que en cualquier entorno de procesamiento paralelo, el multicitado de un proceso puede introducir problemas de control de concurrencia que requieren el uso de secciones críticas o cerraduras. Además, en algunos sistemas implementan hilos en el nivel de en bibliotecas en el nivel de , no por medio de llamadas al sistema, así que la conmutación de hilos no necesita invocar el sistema operativo ni causar una interrupción para pasar al núcleo. La conmutación entre hilos en el nivel de puede hacerse con independencia del sistema operativo y, por tanto muy rápidamente. Así, bloquear un hilo conmutar a otro es una solución razonable al problema de cómo un [9]

Servidor puede manejar muchas solicitudes de forma eficiente. Los hilos en el nivel de que ejecute una llamada al sistema harán que toda la tarea espere hasta que la llamada regrese.

Los hilos operan en muchos sentidos, de la misma forma que los procesos. Los hilos pueden estar en uno de varios estados: listo, bloquead, en ejecución o terminado. Al igual que los procesos, los hilos comparten la U, y solo hay un hilo activo (en ejecución) en un instante dado. Un hilo dentro de un proceso se ejecuta secuencialmente, y cada hilo tiene su propia pila y contador de programa. los hilos pueden crear hilos hijos, y se pueden bloquear en espera a que termine la ejecución de llamadas al sistema; si un hilo se bloquea, otro puede ejecutarse. Por otro lado, a diferencia de los procesos, los hilos no son independientes entre sí. Dado que todos los hilos pueden acceder a todas las direcciones de la tarea, un hilo puede leer la pila de cualquier otro hilo o escribir sobre ella. Esta estructura no ofrece protección entre hilos. Los hilos ofrecen un mecanismo que permite a procesos secuenciales hacer llamadas al sistema bloqueadoras y al mismo tiempo lograr paralelismo. La popularidad de los hilos está creciendo por que tienen algunas de las características de los procesos pesados pero se pueden ejecutar con mayor eficiencia. Hay muchas aplicaciones en las que esta combinación es útil. Por ejemplo, algunas implementaciones del núcleo de Unix son mono tareas: solo una tarea puede estar ejecutando código del núcleo en un momento dado con esto se evitan muchos problemas, como la sincronización del a datos (poniendo cerraduras a las estructuras de datos mientras se están modificando), porque solo permite a un proceso efectuar la modificación. Mach, en cambio, es multicitado y permite al núcleo atender muchas solicitudes simultáneamente.

[10]

En algunos sistemas del sistema operativo no está consciente de la existencia de los hilos. En otras palabras, los hilos se manejan totalmente en el espacio de . Por ejemplo, cuando un hilo está a punto de bloquearse, escoge e inicia a su sucesor antes de detenerse. Hay varios paquetes de hilos a nivel de , incluidos los paquetes de hilos p de posix e hilos c de mach. En otros sistemas, el sistema operativo esta consiente de la existencia de múltiples hilos por proceso, así que, cuando un hilo se bloquea, el sistema operativo escoge el que se ejecutara a continuación, ya sea del mismo proceso o de uno distinto. Para realizar la planificación, el kernel debe tener una tabla de hilos que liste todos los hilos del sistema análoga a la tabla de procesos. Aunque estas dos alternativas pueden parecer equivalentes, su rendimiento es muy distinto. La conmutación de hilos es mucho más rápida cuando la istración de hilos se efectúa en el espacio de que cuando necesita una llamada al kernel. Este hecho es un argumento convincente para realizar la istración en el espacio de y uno se bloquea.

[11]

2.4 Concurrencia Y Secuensiabilidad. La concurrencia es el punto clave y fundamental para el diseño de sistemas operativos. La concurrencia comprende un gran número de cuestiones de diseño, incluyendo la comunicación entre procesos, compartición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos. Se verá que estas cuestiones no solo surgen en entornos de multiprocesadores y proceso distribuido, sino incluso en sistemas multiprogramados con un solo procesador. Es también un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo para dar la apariencia simultánea. Aunque no se consigue un proceso paralelo real y aunque se produce una cierta sobrecarga en los intercambios de procesos de un sitio a otro, la ejecución intercalada produce beneficios importantes en la eficiencia del procesamiento y en la estructuración de los programas. La concurrencia comprende un gran número de cuestiones de diseño incluyendo la comunicación entre procesos, compartición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación de tiempo del procesador a los procesos. La concurrencia puede presentarse en tres contextos diferentes:  Varias aplicaciones: la multiprogramación se creó para permitir que el tiempo de procesador de la maquina fuese compartido dinámicamente entre varios trabajos o aplicaciones activas.

 Aplicaciones estructuradas: como aplicación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.  Estructura del sistema operativo: las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos.

[12]

Cuando dos o más procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos. Es importante mencionar que para que dos o más procesos sean concurrentes, es necesario que tengan alguna relación entre ellos como puede la cooperación para un determinado trabajo o el uso de información o recursos compartidos, por ejemplo: en un sistema de un procesador , la multiprogramación es una condición necesaria pero no suficiente para que exista concurrencia ya que los procesos pueden ejecutarse de forma totalmente independiente. Por otro lado en un sistema de varios procesos se puede presentar la concurrencia siempre y cuando las actividades necesiten actuar entre si ya sea para utilizar información en común o para cualquier otra cosa.

 BENEFICIOS DE LA CONCURRENCIA : 

Trata de evitar los tiempos muertos de la U.



Comparte y optimiza el uso de recursos.



Permite la modularidad en las diferentes etapas del proceso.



Acelera los cálculos.



Da mayor comodidad.

 DESVENTAJAS DE LA CONCURRENCIA: 

Inanición e interrupción de procesos



Ocurrencia de bloqueos



Que dos o más procesos requieran el mismo recurso (no apropiativo).

Tipos de computadora en los que puede haber concurrencia:  multiprogramación con un U: el sistema operativo se encarga de repartir el U entre los procesos, intercalando su ejecución para dar una apariencia de ejecución simultánea.  Multiprocesador: maquina formada por más de un U que comparten memoria principal. Los procesos no solo intercalan su ejecución sino también la superponer. [13]

 Multicomputadora: es una máquina de memoria distribuida formada por una serie de computadoras, es posible la ejecución simultanea de los proceso en los diferentes cups. La concurrencia será aparente siempre que el número de procesos sea mayor que el de procesadores disponibles y será real cuando haya un proceso por procesador (paralelismo).

[14]

2.4.1 Exclusión Mutua Secciones Criticas. El método más sencillo de comunicación entre los procesos de un programa concurrente es el uso común de unas variables de datos. El problema de este sistema es que la acción de un proceso interfiere en las acciones de otro de una forma no adecuada. Para evitar este tipo de errores se pueden identificar aquellas regiones de los procesos que acceden a variables compartidas y dotarlas de la posibilidad de ejecución como si fueran una única instrucción. Se denomina sección crítica a aquellas partes de los procesos concurrentes que no pueden ejecutarse de forma concurrente o, que desde otro proceso se ven como si fueran una única instrucción. Esto quiere decir que si un proceso entra a ejecutar una sección crítica en la que accede a unas variables compartidas, entonces otro proceso no puede entrar a ejecutar una región crítica en la que se modifique las variables compartidas con el anterior. Las secciones críticas se pueden agrupar en clases, siendo mutuamente exclusivas las secciones críticas de cada una. Para conseguir dicha exclusión se deben implementar protocolos software que impidan o bloqueen el a una sección crítica mientras está siendo utilizada por un proceso. Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusión) se usan en programación concurrente para evitar que fragmentos de código conocidos como secciones críticas accedan al mismo tiempo a recursos que no deben ser compartidos. La mayor parte de estos recursos son las señales, contadores, colas y otros datos que se emplean en la comunicación entre el código que se ejecuta cuando se da servicio a una interrupción y el código que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupción puede ocurrir entre dos instrucciones cualesquiera del código normal y esto puede provocar graves fallos. La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.

[15]

En un sistema multiprocesador de memoria compartida, se usa la operación indivisible test-and-set sobre una bandera, para esperar hasta que el otro procesador la despeje. La operación test-and-set realiza ambas operaciones sin liberar el bus de memoria a otro procesador. Así, cuando el código deja la sección crítica, se despeja la bandera. Esto se conoce como espera activa. Algunos sistemas tienen instrucciones multi-operación indivisibles similares a las anteriormente descritas para manipular las listas enlazadas que se utilizan para las colas de eventos y otras estructuras de datos que los sistemas operativos usan comúnmente. La mayoría de los métodos de exclusión mutua clásicos intentan reducir la latencia y espera activa mediante las colas y cambios de contexto. Algunos investigadores afirman que las pruebas indican que estos algoritmos especiales pierden más tiempo del que ahorran. A pesar de todo lo dicho, muchas técnicas de exclusión mutua tienen efectos colaterales. Por ejemplo, los semáforos permiten interbloqueos (deadlocks) en los que un proceso obtiene un semáforo, otro proceso obtiene el semáforo y ambos se quedan a la espera de que el otro proceso libere el semáforo. Otros efectos comunes incluyen la inanición, en el cual un proceso esencial no se ejecuta durante el tiempo deseado, y la inversión de prioridades, en el que una tarea de prioridad elevada espera por otra tarea de menor prioridad, así como la latencia alta en la que la respuesta a las interrupciones no es inmediata. La mayor parte de la investigación actual en este campo, pretende eliminar los efectos anteriormente descritos. Si bien no hay un esquema perfecto conocido, hay un interesante esquema no clásico de envío de mensajes entre fragmentos de código que, aunque permite inversiones de prioridad y produce una mayor latencia, impide los interbloqueos. Algunos ejemplos de algoritmos clásicos de exclusión mutua son:  El algoritmo de Dekker.

 El algoritmo de Peterson.

[16]

Los puntos de entrada de un recurso indican la cantidad de procesos que pueden utilizar simultáneamente al mismo. Si un recurso tiene sólo un punto de entrada, se lo denomina recurso crítico o recurso no compartible. Región crítica de un proceso es la fase o etapa en la vida de ese proceso concurrente en la cual accede a un recurso crítico para modificarlo o alterarlo. El uso adecuado de la concurrencia entre procesos exige la capacidad de definir secciones críticas y hacer cumplir la exclusión mutua. Cualquier servicio o capacidad que dé soporte para la exclusión mutua debe cumplir con un protocolo de sincronización, que tiene los requisitos siguientes:  Debe cumplirse la exclusión mutua: sólo un proceso de entre todos los que poseen secciones críticas por el mismo recurso u objeto compartido, debe tener permiso para entrar en ella en un instante dado.

 Un proceso que se interrumpe en una sección no crítica debe hacerlo sin estorbar a los otros. Es decir que si se cuelga un proceso que está usando un recurso, los demás procesos que esperan deben poder acceder al recurso de todas formas (el S.O. mata al proceso que se colgó y así libera al recurso).

 No se puede demorar indefinidamente la entrada de un proceso a un cierto recurso; no debe permitirse el interbloqueo y la inanición. Todos los procesos deben poder acceder al recurso que solicitan, sino se van a morir sin usarlo y no es justo.

 Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin dilatación. Es decir, si nadie está usando un cierto recurso, entonces se le otorga al primer proceso que lo solicite.

 No se pueden hacer suposiciones sobre la velocidad relativa de los procesos o su número (cantidad de procesadores). Nunca se puede saber a priori si a un proceso le falta mucho o poco para terminar.

[17]

 Un proceso permanece en su sección crítica sólo por un tiempo finito. Esto sirve para evitar que un proceso se quede con un recurso por mucho tiempo y para que un recurso no se quede trabado sin sentido.

[18]

2.4.2 Sincronización de Procesos en S.C. (Según Deitel, 1993) Uno de los objetivos del sistema operativo es la representación de los procesos y el soporte de los cambios de contexto entre procesos, que posibilitan la compartición del recurso U. El a otros recursos compartidos y comunicación entre procesos relacionados (por ejemplo, de una misma aplicación) hacen necesaria la utilización de mecanismos de sincronización dentro del sistema operativo. Típicamente, un proceso requiere la U durante un periodo de tiempo, realiza alguna operación de E/S, y vuelve a requerir la U, repitiéndose este ciclo hasta la finalización del programa. El proceso pasa por diversos estados entre los que se definen transiciones, como representa, en su forma más sencilla, el grafo de la Figura siguiente. (Según Deitel, 1993) Cada vez que un proceso pasa al estado preparado, está compitiendo por el recurso U. Un segundo objetivo del sistema operativo multiprogramado es la planificación del uso del (de los) recurso(s) de proceso. Los criterios que se siguen para la planificación y las políticas que se usan se estudiarán más adelante en el desarrollo de la presente investigación. Para representar los procesos, un sistema operativo multiprogramado debe almacenar información en base a la cual:  Identificar cada proceso. Se utiliza un identificador del proceso, que suele ser un entero.

 Representar el estado de cada proceso para mantener el grafo de transición de estados.  Normalmente los estados se representan mediante colas de procesos.  Planificar el siguiente proceso que entre en la U (scheduling). Se requiere información que permita aplicar los criterios de planificación (prioridad, quantum, etc).  Contabilizar el uso de recursos por el proceso (tiempo consumido de U, tiempo de ejecución del proceso, tiempos máximos asignados, identificador de ). Parte de esta información puede ser útil para la planificación.

[19]

 Gestionar el contexto de los procesos. Por cada proceso hay que almacenar el estado del procesador, de la pila y de los otros recursos (memoria y entrada/salida). En un cambio de contexto hay que guardar el contexto del proceso que abandona la ejecución y restaurar el contexto del proceso planificado.  Gestionar la memoria. Punteros a tablas de páginas y otra información de la que hablaremos en su momento.  Soportar la entrada/salida. Peticiones pendientes, dispositivos asignados, tabla de canales, etc.

Esta información no tiene por qué estar concentrada en una estructura de datos única para cada proceso. Cómo se almacene dependerá de la estructura del sistema operativo. Por ejemplo, en los sistemas por capas, la información de un proceso estará segmentada a través de las capas. Sin embargo, conceptualmente podemos suponer una estructura, que denominaremos Bloque de Control del Proceso o PCB (Process Control Block), que almacena la información del proceso. Los PCBs se enlazan para formar listas encadenadas (Figura B), por lo que el PCB incluye uno o más apuntadores. La disciplina de a los PCBs puede ser diversa (FCFS, en base a la prioridad, etc.). Así, la gestión de procesos en el sistema operativo se puede representar mediante un conjunto de colas de PCBs. Habrá una cola para los procesos que estén en estado preparado para ejecución, una cola para cada condición de bloqueo, e incluso, para generalizar, se puede considerar una cola de procesos en ejecución (por cada U).

[20]

De esta forma, podemos definir el sistema operativo como un modelo de procesos que se representa mediante un sistema de colas, según se muestra a continuación.

En programación concurrente, se define como a la porción de código de un programa de computador el cual accede a un recurso compartido (estructura de datos ó dispositivo) que no debe de ser accedido por más de un hilo en ejecución (thread). La sección crítica por lo general termina en un tiempo determinado y el hilo, proceso ó tarea solo tendrá que esperar un período determinado de tiempo para entrar. Se necesita de un mecanismo de sincronización en la entrada y salida de la sección crítica para asegurar la utilización exclusiva del recurso, por ejemplo un semáforo. El concurrente se controla teniendo cuidado de las variables que se modifican dentro y fuera de la sección crítica. La sección crítica se utiliza por lo general cuando un programa multihilo actualiza múltiples variables sin un hilo de ejecución separado que lleve los cambios conflictivos a esos datos. Una situación similar, la sección crítica puede ser utilizada para asegurarse de que un recurso compartido, por ejemplo, una impresora, puede ser accedida por un solo proceso a la vez. La manera en cómo se implementan las secciones puede variar dependiendo de los diversos sistemas operativos. Sólo un proceso puede estar en una sección crítica a la vez. Propiedades del exclusivo a secciones críticas: Como criterios de validez de un mecanismo de sincronización nos referiremos al cumplimiento de las siguientes condiciones enunciadas por Dijkstra para el exclusivo a una sección crítica.  Exclusión mutua. No puede haber más de un proceso simultáneamente en la SC.

 No interbloqueo. Ningún proceso fuera de la SC puede impedir que otro entre a la SC. [21]

 No inanición. Un proceso no puede esperar por tiempo indefinido para entrar a la SC.  Independencia del hardware. No se pueden hacer suposiciones acerca del número de procesadores o de la velocidad relativa de los procesos.

[22]

2.4.2.1 Mecanismo de Semáforos. (Según William Stallings, 2002) Los semáforos son mecanismos que permiten sincronizar procesos para prevenir colisiones cuando uno o más procesos solicitan simultáneamente un recurso. Un mecanismo semáforo consta básicamente de dos operaciones primitivas señal (Signal) y espera (Wait) (Originalmente definidas como P y V por Disjkstra), que operan sobre un tipo especial de variable semáforo, “s”. La variable semáforo puede tomar valores enteros y, excepto posiblemente en su inicialización, solo puede ser accedida y manipulada por medio de las operaciones SIGNAL y WAIT. Ambas primitivas llevan un argumento cada una, la variable semáforo, y pueden definirse del modo siguiente:  SIGNAL (S): Incrementa el valor de su argumento semáforo, s, en una operación indivisible.  WAIT (S): Decrementa el valor de su argumento semáforo, s , en tanto el resultado no sea negativo. La conclusión de la operación WAIT, una vez tomada la decisión de decrementar su argumento semáforo, debe ser individual.

Propiedades. (Según William Stallings, 2002) Los semáforos son un mecanismo relativamente sencillo pero poderoso de asegurar la exclusión mutua entre procesos concurrentes para acceder a un recurso compartido. En vez de que lo s inventen sus propios protocolos de sincronización (tarea difícil y traicionera) los semáforos son una herramienta proporcionada por el diseñador de sistemas. Los s solo necesitan contribuir a controlar el a los recursos compartidos obedeciendo un protocolo estándar y sencillo. Disciplina de Servicio de los Semáforos. (Segun William Stallings, 2002) La definición de semáforo con espera activa no impone la aplicación de ninguna ordenación a los procesos que esperan, existe, por tanto, una posibilidad de que un proceso [23]

pueda quedar bloqueado debido a la competencia con otros. Esta situación, en la cual algunos procesos progresan hacia su terminación pero uno o más procesos permanecen bloqueados fuera del recurso, se denomina Aplazamiento Indefinido. Este fenómeno también es conocido como Bloqueo Activo, y los procesos afectados se dicen que son Postergados. Para evitar bloqueos activos algunas implementaciones de semáforos obligan a aplicar una disciplina de servicio entre los procesos en espera. La elección de una disciplina de servicio es muy importante ya que una disciplina sesgada puede posibilitar que un grupo de procesos conspire contra otros y usurpe permanentemente el recurso. La postergación de procesos puede evitarse añadiendo el siguiente requisito a la implementación de semáforo ..: “Una petición para entrar a la sección critica debe ser concedida en tiempo finito”. Dada la suposición de que cada proceso tarda un tiempo finito en ejecutar la sección critica, este requisito puede sastifacerse utilizando la disciplina FIFO (First Input First Output - “Primero en entrar... Primero en Salir”) para elegir entre los procesos en espera. Este método garantiza la entrada a la sección crítica en tiempo finito, como también es conocido como Implementación Estricta de Semáforos. Implementación de Semáforos con Colas. (Segun William Stallings, 2002) La implementación de los semáforos con espera activa tienen dos importantes desventajas .: el potencial aplazamiento indefinido y la baja eficiencia debido al consumo de ciclos de procesador por parte de procesos bloqueados. Aunque un proceso bloqueado no experimenta ningún proceso real, no obstante continua consumiendo recursos del sistema a causa de la espera activa. Tanto el bloqueo activo como la ineficaz espera activa pueden verse aliviados por la implementación de semáforos con cola. Un proceso suspendido no consume ciclos de procesador, de modo que este método es potencialmente más eficiente que el de la espera activa.

[24]

2.4.2.2 Mecanismos de Monitores. (Como comenta F. Vallejo, 2001) Los monitores son estructuras de datos utilizadas en lenguajes de programación para sincronizar dos o más procesos o hilos de ejecución que usan recursos compartidos. En el estudio y uso de los semáforos se puede ver que las llamadas a las funciones necesarias para utilizarlos quedan repartidas en el código del programa, haciendo difícil corregir errores y asegurar el buen funcionamiento de los algoritmos. Para evitar estos inconvenientes se desarrollaron los monitores. El concepto de monitor fue definido por primera vez por Charles Antony Richard en un artículo del año 1974. La estructura de los monitores se ha implementado en varios lenguajes de programación, incluido Pascal concurrente, Modula-2, Modula-3 y Java, y como biblioteca de programas.  Componentes : Un monitor tiene cuatro componentes: inicialización, datos privados, procedimientos del monitor y cola de entrada. 

Inicialización: contiene el código a ser ejecutado cuando el monitor es creado



Datos privados: contiene los procedimientos privados, que sólo pueden ser usados desde dentro del monitor y no son visibles desde fuera



Procedimientos del monitor: son los procedimientos que pueden ser llamados desde fuera del monitor.



Cola de entrada: contiene a los threads que han llamado a algún procedimiento del monitor pero no han podido adquirir permiso para ejecutarlos aún.

 Exclusión mutua en un monitor. (Como comenta F. Vallejo, 2001) Los monitores están pensados para ser usados en entornos multiproceso o multihilo, y por lo tanto muchos procesos o threads pueden llamar a la vez a un [25]

procedimiento del monitor. Los monitores garantizan que en cualquier momento, a lo sumo un thread puede estar ejecutando dentro de un monitor. Ejecutar dentro de un monitor significa que sólo un thread estará en estado de ejecución mientras dura la llamada a un procedimiento del monitor. El problema de que dos threads ejecuten un mismo procedimiento dentro del monitor es que se pueden dar condiciones de carrera, perjudicando el resultado de los cálculos. Para evitar esto y garantizar la integridad de los datos privados, el monitor hace cumplir la exclusión mutua implícitamente, de modo que sólo un procedimiento esté siendo ejecutado a la vez. De esta forma, si un thread llama a un procedimiento mientras otro thread está dentro del monitor, se bloqueará y esperará en la cola de entrada hasta que el monitor quede nuevamente libre. Aunque se la llama cola de entrada, no debería suponerse ninguna política de encolado.  Tipos de monitores. Antes se dijo que una llamada a la función cond_signal con una variable de condición hacía que un proceso que estaba esperando por esa condición reanudara su ejecución. Nótese que el thread que reanuda su ejecución necesitará obtener nuevamente el lock del monitor. Cualquier solución debe garantizar la exclusión mutua. Según quién continúa con la ejecución, se diferencian dos tipos de monitores: 

Hoare y Mesa.



Tipo Hoare.

En la definición original de Hoare, el thread que ejecuta cond_signal le cede el monitor al thread que esperaba. El monitor toma entonces el lock y se lo entrega al thread durmiente, que reanuda la ejecución. Más tarde cuando el monitor quede libre nuevamente el thread que cedió el lock volverá a ejecutar.

[26]

Aquí tenemos ventajas y desventajas del hoare. VENTAJAS

DESVENTAJAS

El thread que reanuda la ejecución puede Si el proceso que ejecuta cond_signal no hacerlo inmediatamente sin fijarse si la terminó con su ejecución se necesitarán dos condición se cumple, porque desde que se cambios de contexto para que vuelva a tomar ejecutó cond_signal hasta que llegó su turno el lock del monitor. Al despertar a un thread de ejecutar ningún proceso puede cambiarla. que espera en una variable de condición, se El thread despertado ya estaba esperando debe asegurar que reanude su ejecución desde antes, por lo que podría suponerse que inmediatamente. De otra forma, algún otro es más urgente ejecutarlo a seguir con el thread podría cambiar la condición. Esto proceso despertante.

implica que la planificación debe ser muy fiable, y dificulta la implementación.

Tipo mesa: Butler W. Lampson y David D. Redell en 1980 desarrollaron una definición diferente de monitores para el lenguaje Mesa que lidia con las desventajas de los monitores de tipo Hoare y añade algunas características. En los monitores de Lampson y Redell el thread que ejecuta cond_signal sobre una variable de condición continúa con su ejecución dentro del monitor. Si hay otro thread esperando en esa variable de condición, se lo despierta y deja como listo. Podrá intentar entrar el monitor cuando éste quede libre, aunque puede suceder que otro thread logre entrar antes. Este nuevo thread puede cambiar la condición por la cual el primer thread estaba durmiendo. Cuando reanude la ejecución el durmiente, [27]

debería verificar que la condición efectivamente es la que necesita para seguir ejecutando. En el proceso que durmió, por lo tanto, es necesario cambiar la instrucción if por while, para que al despertar compruebe nuevamente la condición, y de no ser cierta vuelva a llamar a cond_wait. Además de las dos primitivas cond_wait(c) y cond_signal(c), los monitores de Lampson y Redell poseen la función cond_broadcast(c), que notifica a los threads que están esperando en la variable de condición c y los pone en estado listo. Al entrar al monitor, cada thread verificará la condición por la que estaban detenidos, al igual que antes. Los monitores del tipo Mesa son menos propensos a errores, ya que un thread podría hacer una llamada incorrecta a cond_signal o a cond_broadcast sin afectar al thread en espera, que verificará la condición y seguirá durmiendo si no fuera la esperada. Tipos De Monitores. Monitor tipo monitor. Este

monitor

fue

implementado

en

Pascal

Concurrente, lenguaje desarrollado por Per Brinch Hansen. Es el monitor más simple de todos pues solo tiene tres estados y las funciones internas son muy sencillas. Una característica distintiva de este monitor es que el proceso que reinicia a otros debe salir del monitor, es decir abandona el estado activo. Monitor tipo manager. Este monitor es muy similar al monitor tipo monitor, la diferencia esencial es que un proceso que es reiniciado debe abandonar el monitor, es decir no se le permite que entre al estado activo.

[28]

Monitor tipo mediador Este monitor fue propuesto por C.A.R. Hoare, tiene la característica de compensar las desventajas de los monitores tipo monitor y tipo managEer. Un proceso que reinicia a otros puede permanecer dentro del monitor y un proceso reiniciado también puede permanecer dentro del monitor.

Monitor tipo gladiador. Este monitor propuesto por Cavers y Brown tiene la característica fundamental de solo tener un punto de consistencia interno (un punto de consistencia interno ocurre cuando el proceso que está activo abandona este estado y sigue dentro del monitor).

[29]

2.4.3 Interbloqueo DeadLock. El interbloqueo puede definirse formalmente como sigue: Un conjunto de procesos está en interbloqueo si cada proceso del conjunto está esperando un evento que sólo otro proceso del conjunto puede causar. Puesto que todos los procesos están esperando, ninguno de ellos puede causar ninguno de los eventos que podrían despertar a cualquiera de los demás del conjunto, y todos los procesos continúan esperando indefinidamente. Tipos de recursos Reutilizables: Un recurso reutilizable es aquél que puede ser usado con seguridad por un proceso y no se agota con el uso. Los procesos obtienen unidades de recursos que liberan posteriormente para que otros procesos las reutilicen. Como ejemplos de recursos reutilizables se tienen los procesadores, canales de E/S, memoria principal y secundaria, dispositivos y estructuras de datos tales como archivos, bases de datos y semáforos. Consumibles: Un recurso consumible es aquél que puede ser creado (producido) y destruido (consumido).

Coffman (1971) demostró que deben cumplirse cuatro condiciones para que haya un bloqueo mutuo:  Condición de exclusión mutua. Cada recurso está asignado únicamente a un solo proceso o está disponible.

 Condición de retener y esperar. Los procesos que actualmente tienen recursos que les fueron otorgados previamente pueden solicitar nuevos recursos.  Condición de no expropiación. No es posible quitarle por la fuerza a un proceso los recursos que le fueron otorgados previamente. El proceso que los tiene debe liberarlos explícitamente.  Condición de espera circular. Debe haber una cadena circular de dos o más procesos, cada uno de los cuales está esperando un recurso retenido por el siguiente miembro de la cadena.

[30]

Deben estar presentes estas cuatro condiciones para que ocurra un bloqueo mutuo. Si una o más de estas condiciones están ausentes, no puede haber bloqueo mutuo. Prevención La estrategia de prevención del interbloqueo consiste, a grandes rasgos, en diseñar un sistema de manera que esté excluida, a priori, la posibilidad de interbloqueo. Los métodos para prevenir el interbloqueo son de dos tipos. Los métodos indirectos consisten en impedir la aparición de alguna de las tres condiciones necesarias, antes mencionadas (condiciones 1 a 3). Los métodos directos consisten en evitar la aparición del círculo vicioso de espera (condición 4). Retención y Espera. La condición de retención y espera puede prevenirse exigiendo que todos los procesos soliciten todos los recursos que necesiten a un mismo tiempo y bloqueando el proceso hasta que todos los recursos puedan concederse simultáneamente. Esta solución resulta ineficiente por dos factores. En primer lugar, un proceso puede estar suspendido durante mucho tiempo, esperando que se concedan todas sus solicitudes de recursos, cuando de hecho podría haber avanzado con sólo algunos de los recursos.

[31]

2.4.3.1 Prevención Interbloqueo DeadLock. Los bloqueos mutuos pueden ser evitados si se sabe cierta información sobre los procesos antes de la asignación de recursos. Para cada petición de recursos, el sistema controla si satisfaciendo el pedido entra en un estado inseguro, donde puede producirse un bloqueo mutuo. Existen varios algoritmos para evitar bloqueos mutuos: Algoritmo del banquero, introducido por Dijkstra. Algoritmo de grafo de asignación de recursos Algoritmo de Seguridad. Algoritmo de solicitud de recursos. Prevención Los bloqueos mutuos pueden prevenirse asegurando que no suceda alguna de las condiciones necesarias vistas anteriormente. Eliminando la exclusión mutua: ningún proceso puede tener exclusivo a un recurso. Esto es imposible para procesos que no pueden ser encolados (puestos en un spool), e incluso con colas también pueden ocurrir interbloqueos. La condición de retención y espera puede ser eliminada haciendo que los procesos pidan todos los recursos que van a necesitar antes de empezar. Este conocimiento por adelantado muchas veces es imposible nuevamente. Otra forma es requerir a los procesos liberar todos sus recursos antes de pedir todos los recursos que necesitan.

[32]

2.4.3.2 Detección Interbloqueo DeadLock. Las estrategias de prevención del interbloqueo son muy conservadoras; solucionan el problema del interbloqueo limitando el a los recursos e imponiendo restricciones a los procesos. En el lado opuesto, las estrategias de detección del interbloqueo no limitan el a los recursos ni restringen las acciones de los procesos. Una vez detectado el interbloqueo, hace falta alguna estrategia de recuperación. Las técnicas siguientes son posibles enfoques, enumeradas en orden creciente de sofisticación:  Abandonar todos los procesos bloqueados. Esta es, se crea o no, una de las soluciones más comunes, si no la más común, de las adoptadas en un sistema operativo.

 Retroceder cada proceso interbloqueado hasta algún punto de control definido previamente y volver a ejecutar todos los procesos. Es necesario que haya disponibles unos mecanismos de retroceso y reinicio en el sistema. El riesgo de esta solución radica en que puede repetirse el interbloqueo original.  Abandonar sucesivamente los procesos bloqueados hasta que deje de haber interbloqueo. El orden en el que se seleccionan los procesos a abandonar seguirá un criterio de mínimo costo.  Apropiarse de recursos sucesivamente hasta que deje de haber interbloqueo. Para los puntos 3 y 4, el criterio de selección podría ser uno de los siguientes, consistentes en escoger el proceso con: Algunas de estas cantidades son más fáciles de medir que otras. El tiempo restante estimado deja lugar a dudas, especialmente. Además, aparte de las medidas de prioridad, no existe otra indicación del “coste” para el frente al coste para el sistema en conjunto.

[33]

2.4.3.3 Recuperación Interbloqueo DeadLock. Una vez que se ha detectado el interbloqueo se debe romper para que los recursos puedan finalizar su ejecución y liberar así los recursos. Para ruptura de la espera se pueden realizar varias opciones. Las idónea sería suspendiendo algunos de los procesos bloqueados para tomar sus recursos y reanudar sus ejecución una vez que se hubiera deshecho el interbloqueo. Esta solución solo puede resultar factible en casos muy particulares; no se podría suspender a un proceso de escribir de escribir en una impresora para pasarla a otro proceso y reanudar después la impresión, como tampoco se podría suspender indefinidamente un proceso de tiempo real. Para aplicar la primera de las opciones se deben tener en cuenta una serie de factores con el fin de elegir aquellos procesos cuya reiniciación resulte menos traumática. Entre los factores a tener en cuenta en cada proceso se tienen:  La prioridad del proceso.

 El tiempo de procesamiento utilizado y el que le resta.  El tipoy número de recursos que posee.  El número de recursos que necesita para finalizar. El procedimiento de la segunda opción consiste en ir expropiando recursos de algunos procesos de forma sucesiva hasta que se consiga salir del interbloqueo. La elección de los recursos que se expropian se basa en criterios similares a los expuestos en la reiniciación de los procesos.

[34]

2.5 Niveles, Objetivos y Criterios de Planificación. En épocas pasadas de los sistemas de procesamiento por lotes, con una entrada en forma de imágenes de tarjetas en una cinta magnética, el algoritmo de planificación era sencillo: solo había que ejecutar el siguiente trabajo en la cinta. En los sistemas de multi de tiempo compartido, que se combinaban con un fondo de trabajos procesados en lote, el algoritmo era más complejo. En forma invariable, existían varios s en espera de servicio y podían existir también otros trabajos para ser procesados en lote. Incluso en los sistemas puros de tiempo compartido existen con frecuencia los trabajos colaterales, como el sistema de correo electrónico, que a

menudo

se

ejecuta

todo

el

tiempo

para

enviar

o

recibir

correo

o

noticias.

Cuando más de un proceso es ejecutable, el Sistema Operativo debe decidir cuál de ellos deberá ejecutarse primero. Hay que tener una planificación de los procesos que quieren ejecutarse en el sistema. La planificación es una función primordial del Sistema Operativo. La mayoría de los recursos, si no es que todos, se planifican antes de que se utilicen. La asignación de procesadores físicos a los procesos hace posible que estos realicen su trabajo, y tal asignación es un problema complejo manejado por el Sistema Operativo.

Concepto de Planificación. La planificación hace referencia a un conjunto de políticas y mecanismos incorporados al sistema operativo que gobiernan el orden en que se ejecutan los trabajos que deben ser cumplimentados por el sistema informático.

[35]

Objetivo de la Planificación. El objetivo principal de la planificación es optimizar el rendimiento del sistema y proporcionar un buen servicio a todos los procesos que se encuentren en él. En general, la planificación trata de cubrir los siguientes objetivos: Justicia. La planificación debe ser lo más justa posible con todos los procesos, sin favorecer a unos y perjudicar a otros. Máxima capacidad de ejecución. Debe dar un servicio eficiente para que todos los trabajos se realicen lo más rápidamente posible. Esto se puede lograr disminuyendo el número de cambios de proceso. Máximo número de s interactivos. En los sistemas de tiempo compartido se tratara de que puedan estar trabajando el mayor número de s al mismo tiempo. Predecibilidad. La planificación debe realizarse de tal forma que en todo momento pueda saberse como será su ejecución. Minimización de la sobrecarga. La computadora debe tener poca sobrecarga ya que esta afecta directamente al rendimiento final del sistema: a menor sobrecarga mayor velocidad de proceso. Equilibrio en el uso de recursos. Para obtener un mayor rendimiento en el uso de los recursos y que estos estén ocupados equitativamente el mayor tiempo posible. Seguridad de las prioridades. Si un proceso tiene mayor prioridad que otro, este debe ejecutarse más rápidamente. Evitar la postergación indefinida. Esto se logra aumentando la prioridad de un proceso mientras espere por un recurso. La prioridad llegara a ser tan alta que al proceso le será asignado el recurso que pidió. [36]

Criterios de planificación. Para realizar los objetivos de la planificación, un mecanismo de planificación debe considerar lo siguiente:

La limitación de un proceso a las operaciones de Entrada / Salida: Cuando un proceso consigue la U, ?la utiliza solo brevemente antes de generar una petición de Entrada / Salida? La limitación de un proceso a la U: Cuando un proceso obtiene la U, ?tiende a usarla hasta que expira su tiempo? Si un proceso es por lote (batch) o interactivo: los s interactivos deben recibir inmediato servicio para garantizar buenos tiempos de respuesta. ¿Qué urgencia tiene una respuesta rápida?: Por ejemplo, un proceso de tiempo real de un sistema de control que supervise una refinería de combustible requiere una respuesta rápida, más rápida que la respuesta requerida por un proceso en lotes (batch) que deberá entregarse al dia siguiente. La prioridad de un proceso: A mayor prioridad mejor tratamiento. Frecuentemente un proceso genera fallos (carencias) de página: Probablemente los procesos que generan pocos fallos de página hayan acumulado sus “conjuntos de trabajo” en el almacenamiento principal. Los procesos que experimentan gran cantidad de fallos de página aún no han establecido sus conjuntos de trabajo.

[37]

Un criterio indica favorecer a los procesos que han establecido sus conjuntos de trabajo. Otro criterio indica favorecer a los procesos con una tasa alta de fallos de página ya que rápidamente generaran una petición de Entrada / Salida. Frecuentemente un proceso ha sido apropiado por otro de más alta prioridad, lo cual significa lo siguiente: A

menudo

los

procesos

apropiados

deben

recibir

un

tratamiento

menos

favorable.

Cada vez que el Sistema Operativo asume la sobrecarga para hacer ejecutar este proceso, el corto tiempo de ejecución antes de la apropiación no justifica la sobrecarga de hacer ejecutar al proceso en primer lugar. ¿Cuanto tiempo de ejecución real ha recibido el proceso?: Un criterio considera que debe ser favorecido un proceso que ha recibido muy poco tiempo de U. ¿Cuánto tiempo adicional va a necesitar el proceso para terminar?: Los tiempos promedio de espera pueden reducirse priorizando los procesos que requieren de un tiempo de ejecución mínimo para su terminación, pero pocas veces es posible conocer la cantidad de tiempo adicional que cada proceso necesita para terminar. En épocas pasadas de los sistemas de procesamiento por lotes, con una entrada planificación era sencillo: solo había que ejecutar el siguiente trabajo en la cinta. En los sistemas de multi de tiempo compartido, que se combinaban con un fondo de trabajos procesados en lote, el algoritmo era más complejo. En forma invariable, existían varios s en espera de servicio y podían existir también otros trabajos para ser procesados en lote. Incluso en los sistemas puros de tiempo compartido existen con frecuencia los trabajos colaterales, como el sistema de correo electrónico, que a menudo se ejecuta todo el tiempo para enviar o recibir correo o noticias. Cuando más de un proceso es ejecutable, el Sistema Operativo debe decidir cuál de ellos deberá ejecutarse primero. Hay que tener una planificación de los procesos que quieren ejecutarse en el sistema. La planificación es una función primordial del Sistema Operativo. La mayoría de los recursos, si [38]

no es que todos, se planifican antes de que se utilicen. La asignación de procesadores físicos a los procesos hace posible que estos realicen su trabajo, y tal asignación es un problema complejo manejado por el Sistema Operativo. En forma de imágenes de tarjetas en una cinta magnética.

[39]

2.6 Técnicas de istración del Planificador. Se denomina planificador al software del sistema operativo encargado de asignar los recursos de un sistema entre los procesos que los solicitan. Siempre que haya tomar una decisión, el planificador debe decidir cuál de los procesos que compiten por la posesión de un determinado recursos lo recibirá. El planificador es un componente funcional muy importante de los sistemas operativos multitarea y multiproceso y es esencial en los sistemas operativos de tiempo real. Su función consiste en repartir el tiempo disponible de un microprocesador entre todos los procesos para su ejecución. Todo sistema operativo gestiona los programas mediante el concepto de proceso. En un instante dado, en el ordenador pueden existir diversos procesos listos para ser ejecutados. Sin embargo, solamente uno de ellos puede ser ejecutado (en cada microprocesador). De ahí la necesidad de que una parte del sistema operativo gestione, de una manera equitativa, qué proceso debe ejecutarse en cada momento. La planificación (scheduling) es la base para lograrla multiprogramación. Un sistema multiprogramado tendrá varios procesos que requerirán el recurso procesador a la vez. Esto sucede cuando los procesos están en estado ready (pronto). Si existe un procesador disponible y existen procesos en estado ready, se debe elegir el que será asignado al recurso para ejecutar. El componente del sistema operativo que realiza la elección del proceso es llamada planificador (scheduler).

[40]

2.6.1 FIFO. FIFO: First In First Out Mecanismo de scheduling en el cual los procesos se ordenan en una fila, en la cual se ejecutan cada uno de los procesos hasta su finalizacion secuencialmente. Es tremendamente ineficiente. Cuando se tiene que elegir a qué proceso asignar la U se escoge al que llevara más tiempo listo. El proceso se mantiene en la U hasta que se bloquea voluntariamente. Para implementar el algoritmo sólo se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada. Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola. Algoritmo de planificación de FIFO. Tal vez la disciplina más simple de planificación sea la de primeras entradas, primeras salidas (PEPS). Los procesos se despachan de acuerdo con su tiempo de llegada a la cola de procesos listos. Cuando un proceso tiene la U, se ejecuta hasta terminar. Es junto en el sentido formal, pero algo injusta en cuanto a que los trabajos largos hacen esperar a los cortos y los trabajos sin importancia hacen esperar a los importantes. FIFO ofrece variaciones relativamente pequeñas en los tiempos de respuesta y por lo tanto es más predecible que los otros esquemas. No es útil en la planificación para los s interactivos porque no puede garantizar buenos tiempos de respuesta. El esquema FIFO rara vez se usa como esquema principal en los sistemas actuales, pero a menudo está incorporado en otros sistemas. Por ejemplo, muchos esquemas de planificación despachan los procesos de acuerdo con la prioridad, pero los procesos con la misma prioridad se despachan de acuerdo con el esquema FIFO. Este es un algoritmo que no usa apropiación, y que consiste en atender a los procesos por estricto orden de llegada a la lista de procesos listos. Cada proceso se ejecuta hasta que termina, o hasta que hace una llamada bloqueante (de E/S). Se trata de una política muy simple y sencilla de llevar a la práctica, pero muy pobre en cuanto a su comportamiento. Las características principales de este algoritmo son las siguientes:  No es apropiativa. [41]

 Es justa, aunque los procesos largos hacen esperar mucho a los cortos.  Es una política predecible.  El tiempo promedio de servicio es muy variable ya que está en función del número de procesos y la duración promedio que tenga.

[42]

2.6.2 Planificación SJF. Shortest-job-First (Trabajo más corto Primero), este algoritmo asocia con cada proceso la duración de la siguiente ráfaga de U del proceso. Cuando el U está disponible, se asigna al proceso que tiene la siguiente ráfaga de U más corta. Cuando las siguientes ráfagas de U de dos procesos son iguales, se usa la planificación FCFS para romper el empate. Un término más apropiado sería el de “algoritmo de la siguiente ráfaga de U más corta”, ya que la planificación depende de la duración de la siguiente ráfaga de U, en lugar de depender de la duración total. Como ejemplo de planificación SFJ, tenemos el siguiente conjunto de procesos, estando especificada la duración de la ráfaga de U en milisegundos:

Usando la planificación SJF, planificaríamos estos procesos de acuerdo al siguiente diagrama de Gantt:

El tiempo de espera es de 3 milisegundos para el proceso P1, de 16 milisegundos para el proceso P2, de 9 milisegundos para el proceso P3 y de 0 milisegundos para el proceso P4. Por tanto, el tiempo medio de espera es de (3+16+9+0)/4 = 7 milisegundos. Por comparación, si estuviéramos usando el esquema de planificación FCFS, el tiempo de espera seria de 10.25 milisegundos El algoritmo de planificación SJF es probablemente óptimo, ya que proporciona el tiempo medio de espera mínimo para un conjunto de procesos. Al anteponer un proceso corto a uno largo disminuye el tiempo de espera del proceso corto en mayor medida de lo que incrementa el tiempo de espera del proceso largo. Por esto, el tiempo medio de espera disminuye. La dificultad del algoritmo SJF es conocer la duración de la siguiente solicitud de U. En una planificación a largo plazo en un sistema de procesamiento por lotes, podemos usar una duración el

[43]

límite del tiempo del proceso que el especifique en el momento de enviar el trabajo. La planificación SJF se usa frecuentemente como mecanismo de planificación a largo plazo. Aunque el algoritmo SJF es optimo, no se puede implementar en el nivel de planificación del U a corto plazo, ya que no hay forma de conocer la duración de la siguiente ráfaga de U. Un método consiste en intentar aproximar la planificación SJF: podemos no conocer la duración de la siguiente ráfaga de U, pero podemos predecir su valor, por el procedimiento de confiar en que la siguiente ráfaga de U sea similar en duración a las anteriores. De esta manera, calculando una aproximación de la duración de la siguiente ráfaga de U, podemos tomar el proceso que tenga la ráfaga de U predicha más corta. La siguiente ráfaga de U se predice como una media exponencial de las duraciones medias anteriores. Sea tn la duración de la n-ésima ráfaga de U y sea τn+1 el valor predicho rapa la siguiente ráfaga de U. Entonces, para α, 0≤α≤1, se define: τn+1 = αtn + (1 - α)tn Esta fórmula define un promedio exponencial. El valor de tn contiene la información más reciente; τn almacena el historial pasado. El parámetro α controla el peso relativo del historial reciente y pasado de nuestra predicción. Si α=0, entonces τn+1 = τn, y el historial reciente no tiene ningún efecto; si α=1, entonces τn+1 = τn y solo la ráfaga de U mas reciente importa. Frecuentemente, α=1/2, el historial reciente y pasado tienen el mismo peso. El valor inicial τ0 puede definirse como una constante o como un promedio global para todo el sistema. La siguiente figura muestra el promedio exponencial como α=1/2 y τ0 = 10.

[44]

2.6.3 RR. Cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado cuantum o cuanto. Si el proceso agota su cuantum de tiempo, se elige a otro proceso para ocupar la U. Si el proceso se bloquea o termina antes de agotar su cuantum también se alterna el uso de la U. El round robin es muy fácil de implementar. Todo lo que necesita el planificador es mantener una lista de los procesos listos.

[45]

2.6.4 Queves Multi-level. Otra clase de algoritmos de planificación es la que se ha desarrollado para aquellas situaciones en las que los procesos pueden clasificarse fácilmente en grupos diferentes. Por ejemplo, una clasificación habitual consiste en diferenciar entre procesos de primer plano (interactivos) y procesos de segundo plano (por lotes). Estos dos tipos de procesos tienen requisitos diferentes de tiempo de respuesta y, por tanto, pueden tener distintas necesidades de planificación. Además, los procesos de primer plano pueden tener prioridad (definida externamente) sobre los procesos de segundo plano. Un algoritmo de planificación mediante colas multinivel divide la cola de procesos preparados en varias colas distintas. Los procesos se asignan permanentemente a una cola, generalmente en función de alguna propiedad del proceso, como por ejemplo el tamaño memoria, la prioridad del proceso o el tipo de proceso. Cada cola tiene su propio algoritmo de planificación. Por ejemplo, pueden emplearse colas distintas para los procesos de primer plano y de segundo plano. La cola de primer plano puede planificarse mediante un algoritmo por turnos, mientras que para la cola de segundo plano puede emplearse un algoritmo FCFS. Además, debe definirse una planificación entre las colas, la cual suele implementarse como una planificación apropiada y prioridad fija. Por ejemplo, la cola de procesos de primer plano puede tener velocidad absoluta sobre la cola de procesos de segundo plano. Veamos un ejemplo de algoritmo de planificación mediante colas multinivel con las cinco colas que se enumeran a continuación, según su orden de prioridad:  Procesos del sistema.  Procesos interactivos.  Procesos de edición interactivos.  Procesos por lotes.  Procesos de estudiantes. Cada cola tiene prioridad absoluta sobre las colas de prioridad más baja. Por ejemplo, ningún proceso de la cola por lotes podrá ejecutarse hasta que se hayan vaciado completamente las colas de los procesos del sistema, los procesos interactivos y los procesos de edición interactivos. Si un proceso de [46]

edición interactivo llega a la cola de procesos preparados mientras se está ejecutando un proceso por lotes, el proceso por lotes será desalojado. Otra posibilidad consiste en repartir el tiempo entre las colas. En este caso, cada cola obtiene una cierta porción del tiempo de U, con la que puede entonces planificar sus distintos procesos Por ejemplo, en el caso de la colas de procesos de primer plano y segundo plano, la cola de primer plano puede disponer del 80 por ciento del tiempo de U para planificar por turnos sus procesos, mientras que la cola de procesos de segundo plano recibe el 20 por ciento del tiempo de U para gestionar sus procesos mediante el método FCFS.

[47]

2.6.5 Multi-level Queves. Normalmente, cuando se usa el algoritmo de planificación mediante colas multinivel, los procesos se asignan de forma permanente a una cola cuando entran en el sistema. Por ejemplo, si hay colas diferentes para los procesos de primer y segundo plano, los procesos no se mueven de una cola a otra, dado que no pueden cambiar su naturaleza de proceso de primer o segundo plano. Esta configuración presenta la ventaja de una baja carga de trabajo de planificación, pero resulta poco flexible. Por el contrario, el algoritmo de planificación mediante colas multinivel realimentadas permite mover un proceso de una cola a otra. La idea es separar los procesos en función de las características de sus ráfagas de U. Si un proceso utiliza demasiado tiempo de U, se pasa a una a dé prioridad más baja. Este esquema deja los procesos limitados por E/S y los procesos interactivos en las colas de prioridad más alta. Además, un proceso que esté esperando demasiado tiempo en una cola de baja prioridad puede pasarse a una cola de prioridad más alta. Este mecanismo de envejecimiento evita el bloqueo indefinido. Por ejemplo, considere un planificador de colas multinivel realimentadas con tres colas, numeradas de 0 a 2 (Figura 5.7). En primer lugar, el planificador ejecuta todos los procesos de la cola 0. Solo cuando la cola 0 este vacía ejecutara procesos de la cola 1. De forma similar, los procesos de la cola 2 solo se ejecutaran si las colas 0 y 1 están vacías. Un proceso que llegue a la cola 1 desalojara a un proceso de la cola 2 y ese proceso de la cola 1 será, a su vez, desalojado por un proceso que llegue a la cola 0. Un proceso que entre en la cola de procesos preparados se coloca en la cola 0 y a cada uno de los procesos de esa cola se le proporciona un cuanto de tiempo de 8 milisegundos. Si el proceso no termina en ese tiempo, se pasa al final de la cola 1. Si la cola 0 esta vacía, al proceso que se encuentra al principio de la cola 1 se le asigna un cuanto de 16 milisegundos. Si no se completa en ese tiempo, se lo desaloja y se lo incluye en la cola 2. Los procesos de la cola 2 se ejecutan basándose en una planificación FCFS, pero solo cuando las colas 0 y 1 están vacías. Este algoritmo de planificación proporciona la prioridad más alta a todo proceso que tenga una ráfaga de U de 8 milisegundos o menos. Tales procesos acceden rápidamente a la U, concluyen su ráfaga de U y pasan a su siguiente ráfaga de E/S. Los procesos que necesitan más de 8 milisegundos y menos de 24 milisegundos también son servidor rápidamente, aunque con una prioridad más baja que [48]

los procesos más cortos. Los procesos largos terminan yendo automáticamente a la cola 2 y se sirven, siguiendo el orden FCFS, con los ciclos de U no utilizados por las colas 0 y 1. En general, un planificador mediante colas multinivel realimentadas se define mediante los parámetros siguientes:  El número de colas.  El algoritmo de planificación de cada cola.  El método usado para determinar cuándo pasar un proceso a una cola de prioridad más alta.  El método usado para determinar cuándo pasar un proceso a una cola de prioridad más baja.  El método usado para determinar en qué cola se introducirá un proceso cuando haya que darle servicio. La definición del planificador mediante colas multinivel realimentadas le convierte en el algoritmo de planificación de la U más general. Puede configurarse este algoritmo para adaptarlo a cualquier sistema específico que se quiera diseñar. Lamentablemente, también es el algoritmo más complejo, puesto que definir el mejor planificador requiere disponer de algún mecanismo para seleccionar los valores de todos los parámetros.

[49]

Conclusión. Con esto llegamos al final del desarrollo de investigación de esta unidad, los conocimientos obtenidos nos están ayudando a comprender más a fondo la funcionabilidad del sistema operativo. Estamos comprendiendo también algunas funciones específicas de los procesos y la forma en que estas se presentan, en cada uno de los diferentes comportamientos de la máquina. Al igual hemos aprendido que gran parte de las funciones del sistema operativo se llevan a cabo a través de las comunicaciones y estas comunicaciones a través de procesos. La importancia jerarquía que los procesos le otorgan a las diferentes actividades y la forma en que esta las istra para que se lleven a cabo las tareas. Y con esto llegamos al final de la investigación de esta unidad esperamos ampliar más nuestro conocimientos en el transcurso de las siguientes unidades.

[50]

Bibliografía.

http://istraciondeprocesos-naranjo.blogspot.mx/2008/10/241-exclusin-mutua-de-seccionescrticas.html sistemasoperativos.angelfire.com/html/2.4.3.html sistemasoperativos.angelfire.com/html/2.4.3.html http://istraciondeprocesos-barrueta.blogspot.mx/2008/10/2432-deteccin-deinterbloqueos.html http://istraciondeprocesos-barrueta.blogspot.mx/2008/10/2433-recuperacin-deinterbloqueo.html Sistemas Operativo, 2 Ed, Prentice Hall, Madrid, 1997. Sistemas operativos, diseño e implementación 2da edición - Andrew S. Tanenbaum & Albert S. Wood Hull. Sistemas operativos - 5ta edición - Abraham Silbers chatz & Peter Baer Galvin.

[51]