2.1 Concepto de Proceso

(Menciona Deitel, 1993) No hay un acuerdo universal sobre una definición de proceso, pero sí algunas definiciones aceptadas:

Un proceso es una instancia de ejecución de un programa, caracterizado por su contador de programa, su palabra de estado(Palabra que recoge en binario el estado del entorno de programa, después de la ejecución de cada instrucción.), sus registros ( pequeña memoria interna del microprocesador, formada generalmente por biestables) del procesador, su segmento de texto, pila (zona reservada de la memoria o registros hardware donde se almacena temporalmente el estado o información de un programa, rutina, etc..) y datos, etc.

Un proceso es un concepto manejado por el sistema operativo que consiste en el conjunto formado por:

*Las instrucciones de un programa destinadas a ser ejecutadas por el microprocesador.
*Su estado de ejecución en un momento dado, esto es, los valores de los registros de la CPU para dicho programa.

*Su memoria de trabajo, es decir, la memoria que ha reservado y sus contenidos.
*Otra información que permite al sistema operativo su planificación.

Esta definición varía ligeramente en el caso de sistemas operativos multihilo, donde un proceso consta de uno o más hilos, la memoria de trabajo (compartida por todos los hilos) y la información de planificación. Cada hilo consta de instrucciones y estado de ejecución.

(Menciona Deitel, 1993) Los procesos son creados y destruidos por el sistema operativo, así como también este se debe hacer cargo de la comunicación entre procesos, pero lo hace a petición de otros procesos. El mecanismo por el cual un proceso crea otro proceso se denomina bifurcación (fork). Los nuevos procesos pueden ser independientes y no compartir el espacio de memoria con el proceso que los ha creado o ser creados en el mismo espacio de memoria.

En los sistemas operativos multihilo es posible crear tanto hilos como procesos. La diferencia estriba en que un proceso solamente puede crear hilos para sí mismo y en que dichos hilos comparten toda la memoria reservada para el proceso.

2.2 Estados y Transiciones de los Procesos

ESTADOS.
(Segun Andrew S. Tanenbaum, 2003) El principal trabajo del procesador es ejecutar las instrucciones de máquina que se encuentran en memoria principal. Estas instrucciones se encuentran en forma de programas. Para que un programa pueda ser ejecutado, el sistema operativo crea un nuevo proceso, y el procesador ejecuta una tras otra las instrucciones del mismo. En un entorno de multiprogramación, el procesador intercalará la ejecución de instrucciones de varios programas que se encuentran en memoria. El sistema operativo es el responsable de determinar las pautas de intercalado y asignación de recursos a cada proceso.

Existen varios modelos que representan los estados que puede tener un proceso; esto es el Modelo de dos estados y el Modelo de los cinco estados.

Modelo de 2 estados:
El modelo de estados más simple es el de dos estados. En este modelo, un proceso puede estar ejecutándose o no. Cuando se crea un nuevo proceso, se pone en estado de No ejecución. En algún momento el proceso que se está ejecutando pasará al estado No ejecución y otro proceso se elegirá de la lista de procesos listos para ejecutar para ponerlo en estado Ejecución. De esta explicación se desprende que es necesario que el sistema operativo pueda seguirle la pista a los procesos, conociendo su estado y el lugar que ocupa en memoria. Además los procesos que no se están ejecutando deben guardarse en algún tipo de cola mientras esperan su turno para ejecutar.

Modelo de Cinco estados:
El modelo anterior de 2 estados funcionaría bien con una cola FIFO y planificación por turno rotatorio para los procesos que no están en ejecución, si los procesos estuvieran siempre listos para ejecutar. En la realidad, los procesos utilizan datos para operar con ellos, y puede suceder que no se encuentren listos, o que se deba esperar algún suceso antes de continuar, como una operación de Entrada/Salida. Es por esto que se necesita un estado donde los procesos permanezcan esperando la realización de la operación de Entrada Salida por parte del Sistema Operativo hasta que puedan proseguir. Se divide entonces al estado No ejecución en dos estados: Listo y Espera. Se agregan además un estado Nuevo y otro Terminado.

Los cinco estados de este diagrama son los siguientes según Osëliyo:

*Ejecución: el proceso está actualmente en ejecución.
*Listo: el proceso está listo para ser ejecutado, sólo está esperando que el planificador de corto plazo así lo disponga.
*Espera: el proceso no puede ejecutar hasta que no se produzca cierto suceso, como la finalización de una operación de Entrada/Salida solicitada por una llamada al sistema operativo.
*Nuevo: El proceso recién fue creado y todavía no fue admitido por el sistema operativo. En general los procesos que se encuentran en este estado todavía no fueron cargados en la memoria principal.
*Terminado: El proceso fue expulsado del grupo de procesos ejecutables, ya sea porque terminó o por algún fallo, como un error de protección, aritmético, etc.

Los nuevos estados Nuevo y Terminado son útiles para la gestión de procesos. En este modelo los estados Espera y Listo tienen ambos colas de espera. Cuando un nuevo proceso es admitido por el sistema operativo, se sitúa en la cola de listos. A falta de un esquema de prioridades ésta puede ser una cola FIFO. Cuando se da un suceso se pasan a la cola de listos los procesos que esperaban por ese suceso.

Una de las razones para implementar el estado Espera era poder hacer que los procesos se puedan mantener esperando algún suceso, por ejemplo una Entrada/Salida. Sin embargo, al ser mucho más lentas estas operaciones, puede suceder que en nuestro modelo de cinco estados todos los procesos en memoria estén esperando en el estado Espera y que no haya más memoria disponible para nuevos procesos. Podría conseguirse más memoria, aunque es probable que esto sólo permita procesos más grandes y no necesariamente nuevos procesos. Además hay un costo asociado a la memoria y de cualquier forma es probable que se llegaría al mismo estado con el tiempo. Otra solución es el intercambio. El intercambio se lleva a cabo moviendo una parte de un proceso o un proceso completo desde la memoria principal al disco, quedando en el estado Suspendido. Después del intercambio, se puede aceptar un nuevo proceso o traer a memoria un proceso suspendido anteriormente. El problema que se presenta ahora es que puede ser que si se decide traer a memoria un proceso que está en el estado Suspendido, el mismo todavía se encuentre en espera. Sólo convendría traerlo cuando ya está listo para ejecutar, esto implica que ya aconteció el suceso que estaba esperando. Para tener esta diferenciación entre procesos suspendidos, ya sean listos como en espera, se utilizan cuatro estados: Listo, Espera, Espera y suspendido y Listo y suspendido.

TRANSICIONES

(Segun Andrew S. Tanenbaum, 2003)

*De ejecución á Bloqueado: al iniciar una operación de E/S, al realizar una operación WAIT sobre un semáforo a cero (en el tema de procesos concurrentes se estudiarán los semáforos).
*De ejecución á Listo: por ejemplo, en un sistema de tiempo compartido, cuando el proceso que ocupa la CPU lleva demasiado tiempo ejecutándose continuamente (agota su cuanto) el sistema operativo decide que otro proceso ocupe la CPU, pasando el proceso que ocupaba la CPU a estado listo.
*De Listo á en ejecución: cuando lo requiere el planificador de la CPU (veremos el planificador de la CPU en el tema de planificación de procesos).
*De Bloqueado á Listo: se dispone del recurso por el que se había bloqueado el proceso. Por ejemplo, termina la operación de E/S, o se produce una operación SIGNAL sobre el semáforo en que se bloqueó el proceso, no habiendo otros procesos bloqueados en el semáforo.

Obsérvese que de las cuatro transiciones de estado posibles, la única iniciada por el proceso de usuario es el bloqueo, las otras tres son iniciadas por entidades externas al proceso.

Interpretación de la figura: Como podemos observar en esta figura tenemos una serie de transiciones posibles entre estados de proceso, representados a partir mediante una gama de colores. Estos colores hay que interpretarlos de forma que, el color del borde de los estados representa a dichos estados, los colores dentro de los circulos nos dicen las posibles alternativas de acceso hacia otro estado, y los colores de las flechas nos representan hacia que estado nos dirigimos si seguimos la misma.

2.3 Procesos Ligeros

(Como menciona Albert S. Woodhull, 1999) Un hilo de ejecución, en sistemas operativos, es una característica que permite a una aplicación realizar varias tareas concurrentemente. Los distintos hilos de ejecución comparten una serie de recursos tales como el espacio de memoria, los archivos abiertos, situación de autenticación, etc. Esta técnica permite simplificar el diseño de una aplicación que debe llevar a cabo distintas funciones simultáneamente.

Los hilos de ejecución que comparten los mismos recursos, sumados a estos recursos, son en conjunto conocidos como un proceso. El hecho de que los hilos de ejecución de un mismo proceso compartan los recursos hace que cualquiera de estos hilos pueda modificar éstos. Cuando un hilo modifica un dato en la memoria, los otros hilos acceden e ese dato modificado inmediatamente.

Lo que es propio de cada hilo es el contador de programa, la pila de ejecución y el estado de la CPU (incluyendo el valor de los registros).

El proceso sigue en ejecución mientras al menos uno de sus hilos de ejecución siga activo. Cuando el proceso finaliza, todos sus hilos de ejecución también han terminado. Asimismo en el momento en el que todos los hilos de ejecución finalizan, el proceso no existe más y todos sus recursos son liberados.

(Como menciona Albert S. Woodhull, 1999) Algunos lenguajes de programación tienen características de diseño expresamente creadas para permitir a los programadores lidiar con hilos de ejecución (como Java o Delphi). Otros (la mayoría) desconocen la existencia de hilos de ejecución y éstos deben ser creados mediante llamadas de biblioteca especiales que dependen del sistema operativo en el que estos lenguajes están siendo utilizados (como es el caso del C y del C++).

Un ejemplo de la utilización de hilos es tener un hilo atento a la interfaz gráfica (iconos, botones, ventanas), mientras otro hilo hace una larga operación internamente. De esta manera el programa responde de manera más ágil a la interacción con el usuario. También pueden ser utilizados por una aplicación servidora para dar servicio a múltiples clientes.

Diferencias entre Hilos y Procesos

(Como menciona Albert S. Woodhull, 1999) Los hilos se distinguen de los tradicionales procesos en que los procesos son –generalmente– independientes, llevan bastante información de estados, e interactúan sólo a través de mecanismos de comunicación dados por el sistema. Por otra parte, muchos hilos generalmente comparten otros recursos de forma directa. En muchos de los sistemas operativos que dan facilidades a los hilos, es más rápido cambiar de un hilo a otro dentro del mismo proceso, que cambiar de un proceso a otro. Este fenómeno se debe a que los hilos comparten datos y espacios de direcciones, mientras que los procesos, al ser independientes, no lo hacen. Al cambiar de un proceso a otro el sistema operativo (mediante el dispatcher) genera lo que se conoce como overhead, que es tiempo desperdiciado por el procesador para realizar un cambio de modo (mode switch), en este caso pasar del estado de ejecución (running) al estado de espera (waiting) y colocar el nuevo proceso en ejecución. En los hilos, como pertenecen a un mismo proceso, al realizar un cambio de hilo el tiempo perdido es casi despreciable.

Sistemas operativos como Windows NT, OS/2 y Linux (2.5 o superiores) dicen tener hilos "baratos", y procesos "costosos" mientras que en otros sistemas no hay una gran diferencia.

Si bien los hilos son generados a partir de la creación de un proceso, podemos decir que un proceso es un hilo de ejecución, conocido como Monohilo. Pero las ventajas de los hilos se dan cuando hablamos de Multihilos, que es cuando un proceso tiene múltiples hilos de ejecución los cuales realizan actividades distintas, que pueden o no ser cooperativas entre sí. Los beneficios de los hilos se derivan de las implicaciones de rendimiento.

1.Se tarda mucho menos tiempo en crear un hilo nuevo en un proceso existente que en crear un proceso. Algunas investigaciones llevan al resultado que esto es así en un factor de 10.
2.Se tarda mucho menos en terminar un hilo que un proceso, ya que cuando se elimina un proceso se debe eliminar el BCP del mismo, mientras que un hilo se elimina su contexto y pila.
3.Se tarda mucho menos tiempo en cambiar entre dos hilos de un mismo proceso
4.Los hilos aumentan la eficiencia de la comunicación entre programas en ejecución. En la mayoría de los sistemas en la comunicación entre procesos debe intervenir el núcleo para ofrecer protección de los recursos y realizar la comunicación misma. En cambio, entre hilos pueden comunicarse entre sí sin la invocación al núcleo. Por lo tanto, si hay una aplicación que debe implementarse como un conjunto de unidades de ejecución relacionadas, es más eficiente hacerlo con una colección de hilos que con una colección de procesos separados.

2.4 Concurrencia y Secuenciabilidad

(Como comenta Deitel, 1987) La concurrencia comprende un gran número de cuestiones de diseño, incluyendo la comunicación entre procesos, comparició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 y es fundamental para que existan diseños como Multiprogramación, Multiproceso y Proceso distribuido

(Como comenta Deitel, 1987) Los procesos son concurrentes si existen simultáneamente. 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 La concurrencia puede presentarse en tres contextos diferentes:

*Varias aplicaciones: La multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varios trabajos o aplicaciones activas.
*Aplicaciones estructuradas: Como ampliació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.

Existen tres modelos de computadora en los que se pueden ejecutar procesos concurrentes:

*Multiprogramación con un único procesador. El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecución de los mismos para dar así una apariencia de ejecución simultánea.

*Multiprocesador. Es una maquina formada por un conjunto de procesadores que comparten memoria principal. En este tipo de arquitecturas, los procesos concurrentes no sólo pueden intercalar su ejecución sino también superponerla.

*Multicomputadora. Es una maquina de memoria distribuida, que está formada por una serie de computadoras. En este tipo de arquitecturas también es posible la ejecución simultánea de los procesos sobre los diferentes procesadores.

En general, la concurrencia será aparente siempre que el número de procesos sea mayor que el de procesadores disponibles, es decir, cuando haya más de un proceso por procesador. La concurrencia será real cuando haya un proceso por procesador. Aunque puede parecer que la intercalación y la superposición de la ejecución de procesos presentan formas de ejecución distintas, se verá que ambas pueden contemplase como ejemplos de procesos concurrentes Existen diversas razones que motivan la ejecución de procesos concurrentes en un sistema:

*Facilita la programación de aplicaciones al permitir que éstas se estructuren como un conjunto de procesos que cooperan entre sí para alcanzar un objetivo común.
*Acelera los cálculos. Si se quiere que una tarea se ejecute con mayor rapidez, lo que se puede hacer es dividirla en procesos, cada uno de los cuales se ejecuta en paralelo con los demás.
*Posibilita el uso interactivo a múltiples usuarios que trabajan de forma simultánea.
*Permite un mejor aprovechamiento de los recursos, en especial de la CPU, ya que pueden aprovechar las fases de entrada-salida de unos procesos para realizar las fases de procesamiento de otros.

Así como existen las razones que motivan la ejecución de procesos concurrentes, también existen sus contras:

*Inanición e interrupción de procesos
*Ocurrencia de bloqueos
*Que dos o mas procesos requieran el mismo recurso (No apropiativo)

Tipos de procesos concurrentes.

Los procesos que ejecutan de forma concurrente en un sistema se pueden clasificar como:

Proceso independiente: Es aquel que ejecuta sin requerir la ayuda o cooperación de otros procesos. Un claro ejemplo de procesos independientes son los diferentes shells que se ejecutan de forma simultánea en un sistema.

Procesos son cooperantes: Son aquellos que están diseñados para trabajar conjuntamente en alguna actividad, para lo que deben ser capaces de comunicarse e interactuar entre ellos. En ambos tipos de procesos (independientes y cooperantes), puede producirse una serie de interacciones entre ellos y pueden ser de dos tipos:

*Interacciones motivadas porque los procesos comparten o compiten por el acceso a recursos físicos o lógicos. Por ejemplo, dos procesos independientes compiten por el acceso a disco o para modificar una base de datos.

*Interacción motivada porque los procesos se comunican y sincronizan entre sí para alcanzar un objetivo común, Por ejemplo, un compilador que tiene varios procesos que trabajan conjuntamente para obtener un solo archivo de salida.

Elementos a gestionar y diseñar a causa de la concurrencia.

Se pueden enumerar los siguientes:

1.El sistema operativo debe ser capaz de seguir la pista de los distintos procesos activos. Esto lo hace por medio de PBC’s (Bloque de Control de Procesos)

2.El sistema operativo debe asignar y quitar los distintos recursos a cada proceso activo. Entre estos recursos se incluyen:

*Tiempo de procesador: Es función de la planificación.
*Memoria: La mayoría de los sistemas operativos emplean esquemas de memoria virtual.
*Archivos:
*Dispositivos de E/S:

3.El sistema operativo debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos.

4.Los resultados de un proceso deben ser independientes de la velocidad relativa a la que se realiza la ejecución con respecto a otros procesos concurrentes.

Cuando dos o mas 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 mas procesos sean concurrentes, es necesario que tengan alguna relaciones entre ellos como puede ser la cooperacion para un determinado trabajo o el uso de informacion y recursos compartidos, por ejemplo: en un sistema de un procesador, la multiprogramacion 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 ellos sea para utilizar informacion como para cualquier otra cosa.

2.4.1 Exclusion Mutua en Secciones Criticas

(Segun Linus Torvals,2000) La exlcusión mutua la podríamos definir como una operación de control que permite la coordinación de procesos concurrentes, y que tiene la capacidad de prohibir a los demás procesos realizar una acción cuando un proceso haya obtenido el permiso.

El control de la competencia involucra al sistema operativo inevitablemente, porque es el sistema operativo el que asigna los recursos. Además, los procesos deben ser capaces por sí mismos de expresar de algún modo los requisitos de exclusión mutua, como puede ser bloqueando los recursos antes de usarlos.

(Segun Linus Torvals,2000) Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusion) 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.

(Segun Linus Torvals,2000) 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 spin lock o espera activa.

Algunos sistemas tienen instrucciones multioperació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.

2.4.2 Sincronizacion de Procesos en S.C

(Segun 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 CPU. El acceso 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 CPU durante un periodo de tiempo, realiza alguna operación de E/S, y vuelve a requerir la CPU, 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.

(Segun Deitel, 1993) Cada vez que un proceso pasa al estado preparado, está compitiendo por el recurso CPU. 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 mas 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 CPU (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 CPU, tiempo de ejecución del proceso, tiempos máximos asignados, identificador de usuario). Parte de esta información puede ser útil para la planificación.
*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 acceso 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 CPU).

Una lista de PCBs de encadenado simple
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 mas 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 acceso 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 acceso 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 acceso exclusivo a una sección crítica.

a. Exclusión mutua. No puede haber más de un proceso simultáneamente en la SC.
b. No interbloqueo. Ningún proceso fuera de la SC puede impedir que otro entre a la SC.
c. No inanición. Un proceso no puede esperar por tiempo indefinido para entrar a la SC.
d. Independencia del hardware. No se pueden hacer suposiciones acerca del número de procesadores o de la velocidad relativa de los procesos.

Suposición inicial adicional: las instrucciones del Lenguaje Máquina son atómicas y se ejecutan secuencialmente. Además, existen otros criterios que determinan la calidad del mecanismo y que fundamentalmente se refieren a su rendimiento, como son la productividad(número de operaciones de sincronización por unidad de tiempo que el mecanismo es capaz de soportar) y el tratamiento equitativo entre los procesos (por ejemplo, siguiendo una política FIFO para entrar a la sección crítica).

2.4.2.1 Mecanismos de Semaforos

(Segun 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.
(Segun 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 usuarios 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 usuarios solo necesitan contribuir a controlar el acceso 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 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 critica 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.

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 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. Surge la siguiente pregunta: ¿qué sucede con el thread que hizo el cond_signal? ¿pierde el lock para dárselo al thread que esperaba? ¿qué thread continúa con su ejecución? 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.

• Ventajas:

El thread que reanuda la ejecución puede hacerlo inmediatamente sin fijarse si la condición se cumple, porque desde que se ejecutó cond_signal hasta que llegó su turno de ejecutar ningún proceso puede cambiarla. El thread despertado ya estaba esperando desde antes, por lo que podría suponerse que es más urgente ejecutarlo a seguir con el proceso despertante.

• Desventajas:

Si el proceso que ejecuta cond_signal no terminó con su ejecución se necesitarán dos cambios de contexto para que vuelva a tomar el lock del monitor. Al despertar a un thread que espera en una variable de condición, se debe asegurar que reanude su ejecución inmediatamente. De otra forma, algún otro thread podría cambiar la condición. Esto 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, 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.

2.4.3 Interbloqueo DeadLock

(Como menciona Albert S. Woodhull, 1999) El bloqueo mutuo (también conocido como interbloqueo, traba mortal, deadlock, abrazo mortal) es el bloqueo permanente de un conjunto de procesos o hilos de ejecución en un sistema concurrente que compiten por recursos del sistema o bien se comunican entre ellos. A diferencia de otros problemas de concurrencia de procesos, no existe una solución general para los interbloqueos.

Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de cuatro vehículos que se encuentran en una intersección en el mismo momento. Cada uno necesita que otro se mueva para poder continuar su camino, y ninguno puede continuar.

(Como menciona Albert S. Woodhull, 1999) Los recursos compartidos en este caso son los cuatro cuadrantes. El vehículo que se dirige de oeste a este, por ejemplo, necesita de los cuadrantes suroeste y sureste.En el siguiente ejemplo, dos procesos compiten por dos recursos que necesitan para funcionar, que sólo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos (adquiere el lock sobre ese recurso).

El segundo proceso toma el lock del otro recurso, y luego intenta utilizar el recurso ya utilizado por el primer proceso, por lo tanto queda en espera. Cuando el primer proceso a su vez intenta utilizar el otro recurso, se produce un interbloqueo, donde los dos procesos esperan la liberación del recurso que utiliza el otro proceso.

Condiciones necesarias.
También conocidas como condiciones de Coffman por su primera descripción en 1971 en un artículo escrito por E.G.Coffman. Estas condiciones deben cumplirse simultáneamente y no son totalmente independientes una de otra.Sean los procesos Po, P1,.. Pn y los recursos Ro, R1,..., Rm:

*Condición de exclusión mutua: Existencia al menos de un recurso compartido por los procesos, al cual sólo puede acceder uno simultáneamente.

*Condición de Posesión y espera: Al menos un proceso Pi ha adquirido un recurso Ri, y lo mantiene mientras espera al menos un recurso Rj que ya ha sido asignado a otro proceso.
Condición de no expropiación: Los recursos no pueden ser apropiados por los procesos, es decir, los recursos sólo podrán ser liberados voluntariamente por sus propietarios.

*Condición de espera circular: Dado el conjunto de procesos P0...Pn, P0 está esperando un recurso adquirido por P1, que está esperando un recurso adquirido por P2, que...,que está esperando un recurso adquirido por Pn, que está esperando un recurso adquirido por P0. Esta condición implica la condición de retención y espera.

Evitando bloqueos mutuos.
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. De esta forma, el sistema satisface los pedidos de recursos solamente si se asegura que quedará en un estado seguro. Para que el sistema sea capaz de decidir si el siguiente estado será seguro o inseguro, debe saber por adelantado y en cualquier momento el número y tipo de todos los recursos en existencia, disponibles y requeridos.

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.

2.4.3.1 Prevencion Interbloqueo DeadLock

(Segun Andrew S. Tanenbaum, 2003) 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 acceso 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. Esto también es poco práctico en general.

*La condición de no expropiación puede ser también imposible de eliminar dado que un proceso debe poder tener un recurso por un cierto tiempo o el procesamiento puede quedar inconsistente.

*La condición de espera circular es la más fácil de atacar. Se le permite a un proceso poseer sólo un recurso en un determinado momento, o una jerarquía puede ser impuesta de modo tal que los ciclos de espera no sean posibles.

2.4.3.2 Deteccion Interbloqueo DeadLock

(Segun Andrew S. Tanenbaum, 2003) Las estrategias de prevención de interbloqueo son muy conservadoras; resuelven el problema limitando el acceso a recursos e imponiendo restricciones sobre los procesos. En cambio, las estrategias de detección de interbloqueo, no limitan el acceso a recursos ni restringen las acciones del proceso. Con la detección del interbloqueo, se concederán los recursos que los procesos necesiten siempre que sea posible. Periódicamente, el S. O. ejecuta un algoritmo que permite detectar la condición de circulo vicioso de espera. La detección del interbloqueo es el proceso de determinar si realmente existe un interbloqueo e identificar los procesos y recursos implicados en él. Una posibilidad detectar un interbloqueo es monitorear cada cierto tiempo el estado de los recursos. Cada vez que se solicita o se devuelve un recurso, se actualiza el estado de los recursos y se hace una verificación para observar si existe algún ciclo. Este método está basado en suponer que un interbloqueo no se presente y que los recursos del sistema que han sido asignados, se liberarán en el momento que otro proceso lo requiera.

(Segun Andrew S. Tanenbaum, 2003) Algoritmo de detección del interbloqueo .-Una comprobación para interbloqueo puede hacerse con igual o menor frecuencia que cada solicitud de recursos, dependiendo de que tan probable es que ocurra un interbloqueo. Comprobar cada solicitud de recursos tiene dos ventajas: Conduce a la detección temprana y el algoritmo es simple, de manera relativa porque se basa en cambios crecientes al estado del sistema. Además, las comprobaciones frecuentes consumen un tiempo considerable de procesador.

Los algoritmos de detección de bloqueos implican cierta sobrecarga en tiempo de ejecución, entonces surge el siguiente interrogante: ¿compensa la sobrecarga implicita en los algoritmos de detección de bloqueos, el ahorro potencial de localizarlos y romperlos?

El empleo de algoritmos de detección de interbloqueo implica cierto gasto extra durante la ejecución. Así pues, se presenta de nuevo la cuestión de costeabilidad, tan habitual en los sistemas operativos. Los algoritmos de detección de interbloqueo determinan por lo general si existe una espera circular.

2.4.3.3 Recuperacion Interbloqueo DeadLock

(Segun Andrew S. Tanenbaum, 2003) Cuando se ha detectado que existe un interbloqueo, podemos actuar de varias formas. Una posibilidad es informar al operador que ha ocurrido un interbloqueo y dejar que el operador se ocupe de él manualmente. La otra posibilidad es dejar que el sistema se recupere automáticamente del interbloqueo. Dentro de esta recuperación automática tenemos dos opciones para romper el interbloqueo: Una consiste en abortar uno o más procesos hasta romper la espera circular, y la segunda es apropiar algunos recursos de uno o más de los procesos bloqueados.

La recuperación después de un interbloqueo se complica porque puede no estar claro que el sistema se haya bloqueado. Las mayorías de los Sistemas Operativos no tienen los medios suficientes para suspender un proceso, eliminarlo del sistema y reanudarlo más tarde.

Actualmente, la recuperación se suele realizar eliminando un proceso y quitándole sus recursos. El proceso eliminado se pierde, pero gracias a esto ahora es posible terminar. Algunas veces es necesario, eliminar varios procesos hasta que se hayan liberado los recursos necesarios para que terminen los procesos restantes.

(Segun Andrew S. Tanenbaum, 2003) Los procesos pueden eliminarse de acuerdo con algún orden de prioridad, aunque es posible que no existan prioridades entre los procesos bloqueados, de modo que el operador necesita tomar una decisión arbitraria para decidir que procesos se eliminarán.

Recuperación Manual Está forma de recuperación consiste en avisarle al administrador o al operador del sistema que se ha presentado un interbloqueo, y será el administrador el que solucione dicho problema de la manera más conveniente posible, de modo que su decisión no afecte demasiado a al usuario del proceso en conflicto, y sobre todo que no afecte a los demás usuarios del sistema.

Abortar los Procesos Para eliminar interbloqueos abortando un proceso, tenemos dos métodos; en ambos, el sistema recupera todos los recursos asignados a los procesos terminados.

1 ) Abortar todos los procesos interbloqueados. Esta es una de las soluciones más comunes, adoptada por Sistemas Operativos. Este método romperá definitivamente el ciclo de interbloqueo pero con un costo muy elevado, ya que estos procesos efectuaron cálculos durante mucho tiempo y habrá que descartar los resultados de estos cálculos parciales, para quizá tener que volver a calcularlos más tarde.

2 ) Abortar un proceso en cada ocasión hasta eliminar el ciclo de interbloqueo. El orden en que se seleccionan los procesos para abortarlos debe basarse en algún criterio de costo mínimo. Después de cada aborto, debe solicitarse de nuevo el algoritmo de detección, para ver si todavía existe el interbloqueo. Este método cae enmucho tiempo de procesamiento adicional.

Quizá no sea fácil abortar un proceso. Si éste se encuentra actualizando un archivo, cortarlo a la mitad de la operación puede ocasionar que el archivo quede en un mal estado. Si se utiliza el método de terminación parcial, entonces, dado un conjunto de procesos bloqueados, debemos determinar cuál proceso o procesos debe terminarse para intentar romper el interbloqueo. Se trata sobre todo de una cuestión económica, debemos abortar los procesos que nos representen el menor costo posible.

Existen muchos factores que determinan el proceso que se seleccionará, siendo los principales los siguientes:

1. La prioridad del proceso. Se elimina el proceso de menor prioridad.
2. Tiempo de procesador usado. Se abortará aquel proceso que haya utilizado menos tiempo el procesador, ya que se pierde menos trabajo y será más fácil recuperarlo más tarde.
3. Tipos de recursos utilizados. Si los recursos son muy necesarios y escasos será preferible liberarlos cuanto antes.
4. Cuántos recursos más necesita el proceso. Es conveniente eliminar a aquellos procesos que necesitan un gran número de recursos.
5. Facilidad de suspensión / reanudación. Se eliminarán aquellos procesos cuyo trabajo perdido sea más fácil de recuperar.

Apropiación de Recursos Para eliminar interbloqueos utilizando la apropiación de recursos, vamos quitando sucesivamente recursos de los procesos y los asignamos a otros hasta romper el ciclo de interbloqueo. Si se utiliza la apropiación de recursos para tratar los interbloqueos, hay que considerar tres aspectos:

*Selección de la víctima
*Retroceso
*Bloqueo indefinido

La detección y recuperación es la estrategia que a menudo se utiliza en grandes computadoras, especialmente sistemas por lote en los que la eliminación de un proceso y después su reiniciación suele aceptarse.

2.5 Niveles, Objetivos y Criterios de Planificacion

(Segun Deitel, 1987) Se consideran tres niveles importantes de planificación, los que se detallan a continuación:

*Planificación de alto nivel: Se encarga de llevar procesos de disco a memoria y viceversa. Seleccionando los trabajos que deben admitirse en el sistema.

*También se denomina Planificación de trabajos. oDetermina a qué trabajos se les va a permitir competir activamente por los recursos del sistema, lo cual se denomina Planificación de admisión. Administrar todos los recursos del sistema excepto el CPU. Mantiene las colas de procesos bloqueados y suspendidos. Controla la creación de procesos. Maneja el nivel de multiprogramación.

*Planificación de nivel intermedio: En algunos casos, en especial cuando el sistema está sobrecargado, el planificador de nivel medio encuentra ventajoso retirar trabajos activos de la memoria para reducir el grado de multiprogramación, y por lo tanto, permitir que los trabajos se completen mas aprisa. Este subadministrador controla los trabajos que se intercambian hacia fuera y de regreso.

*Determina a qué procesos se les puede permitir competir por la cpu. Efectúa “suspensiones” y “activaciones” (“reanudaciones”) de procesos. Debe ayudar a alcanzar ciertas metas en el rendimiento total del sistema. Equilibrar la administración de trabajos en el sistema con la asignación del CPU a dichos procesos. Nivelar la carga del sistema (procesos activos y pasivos).

*Planificación de bajo nivel: Se encarga de pasar de un proceso a otro en memoria principal. Determinando a cuál proceso listo se le asignará el CPU cuando éste se encuentra disponible. Determina a qué proceso listo se le asigna la cpu cuando esta queda disponible y asigna la cpu al mismo, es decir que “despacha” la cpu al proceso.

OBJETIVOS DE PLANIFICACIÓN.
(Segun Deitel, 1987) Los objetivos de la planificación del procesador son los siguientes e involucran a los conceptos detallados seguidamente:
•Ser justa: Todos los procesos son tratados de igual manera. Ningún proceso es postergado indefinidamente.
•Maximizar la capacidad de ejecución: Maximizar el número de procesos servidos por unidad de tiempo.
•Maximizar el número de usuarios interactivos que reciban unos tiempos de respuesta aceptables: En un máximo de unos segundos.
•Ser predecible: Un trabajo dado debe ejecutarse aproximadamente en la misma cantidad de tiempo independientemente de la carga del sistema.
•Minimizar la sobrecarga: No suele considerarse un objetivo muy importante.
•Equilibrar el uso de recursos: Favorecer a los procesos que utilizarán recursos infrautilizados
•Equilibrar respuesta y utilización: La mejor manera de garantizar buenos tiempos de respuesta es disponer de los recursos suficientes cuando se necesitan, pero la utilización total de recursos podrá ser pobre.
•Evitar la postergación indefinida: Se utiliza la estrategia del “envejecimiento” . Mientras un proceso espera por un recurso su prioridad debe aumentar, así la prioridad llegará a ser tan alta que el proceso recibirá el recurso esperado.
•Asegurar la prioridad: Los mecanismos de planificación deben favorecer a los procesos con prioridades más altas.
•Dar preferencia a los procesos que mantienen recursos claves: Un proceso de baja prioridad podría mantener un recurso clave, que puede ser requerido por un proceso de más alta prioridad. Si el recurso es no apropiativo, el mecanismo de planificación debe otorgar al proceso un tratamiento mejor del que le correspondería normalmente, puesto que es necesario liberar rápidamente el recurso clave.
•Dar mejor tratamiento a los procesos que muestren un “comportamiento deseable”: Un ejemplo de comportamiento deseable es una tasa baja de paginación.
•Degradarse suavemente con cargas pesadas: Un mecanismo de planificación no debe colapsar con el peso de una exigente carga del sistema. Se debe evitar una carga excesiva mediante las siguientes acciones: No permitiendo que se creen nuevos procesos cuando la carga ya es pesada. Dando servicio a la carga más pesada al proporcionar un nivel moderadamente reducido de servicio a todos los procesos.

CRITERIOS DE PLANIFICACIÓN.
-Equidad Garantizar que cada proceso obtiene su proporción justa de la cpu.
-Eficacia Mantener ocupada la cpu el ciento por ciento del tiempo.
-Tiempo de respuesta Minimizar el tiempo de respuesta para los usuarios interactivos.
-Tiempo de regreso Minimizar el tiempo que deben esperar los usuarios por lotes(batch) para obtener sus resultados.
-Rendimiento Maximizar el número de tareas procesadas por hora.

2.6 Tecnicas de Administracion Del Planificador

(Segun Deitel, 1987) Las disciplinas de planificación pueden ser:

• Expropiativas
• No expropiativas

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á.

(Segun Deitel, 1987) Los algoritmos (técnicas) tienen distintas propiedades según los criterios en los que se basen para su construcción, lo cual se refleja en qué tipo de procesos se puede ver favorecido frente a otro en la disputa del procesador. Antes de realizar la elección de un algoritmo se debe considerar las propiedades de estos frente al criterio de diseño elegido. Algunos de estos son:

a) Eficacia: Se expresa como un porcentaje del tiempo medio de utilización. Aunque puede parecer lógico intentar mantener este parámetro próximo al 100%, con un valor tan elevado otros aspectos importante de medida del comportamiento del sistema pueden verse deteriorados, como por ejemplo el tiempo medio de espera.

b) Rendimiento: Es una medida del numero de procesos completados por unidad de tiempo. Por ejemplo 10 procesos por segundo.

c) Tiempo de retorno o regreso: Es el intervalo de tiempo que transcurre desde que un proceso se crea o presenta hasta que completa por el sistema.

d) Tiempo de espera: Es el tiempo que el proceso espera hasta que se le concede el procesador. Puede resultar una medida mas adecuada de la eficiencia del sistema, ya que se elimina de la media el tiempo que tarda en ejecutarse el mismo.

e) Tiempo de respuesta a un evento: Se denomina así el intervalo de tiempo que transcurre desde que se señala un evento hasta que se ejecuta la primera instrucción de la rutina de servicio de dicho evento.

2.6.1 FIFO (First In First Out )

(Segun J. Boria, 2002 ) 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 CPU se escoge al que llevara más tiempo listo. El proceso se mantiene en la CPU 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.

(Segun J. Boria, 2002 ) FIFO es el acrónimo inglés de First In, First Out (primero en entrar, primero en salir). Un sinónimo de FIFO es FCFS, acrónimo inglés de First Come First Served ( primero en llegar, primero en ser servido). Es un método utilizado en estructuras de datos, contabilidad de costes y teoría de colas. Guarda analogía con las personas que esperan en una cola y van siendo atendidas en el orden en que llegaron, es decir, que la primera persona que entra es la primera persona que sale.

Los FIFOs se usan comúnmente en circuitos de electrónica para almacenaje y hacer control de flujo. Hablando de hardware form un FIFO consiste básicamente en una conjunto de punteros de lectura/escritura, almacenamiento y lógica de control. El almacenamiento puede ser SRAM, flip-flops, latches o cualquier otra forma adecuada de almacenamiento. Para FIFOs de un tamaño importante se usa usualmente una SRAM de doble puerto, donde uno de los puertos se usa para la escritura y el otro par a la lectura.

Un FIFO sincrónico maneja el mismo reloj (clock) tanto para las lecturas como para las escrituras. Una asicrónico es aquel que utiliza diferentes relojes (clocks) una para lectura y otro para la escritura. Cuando se habla de FIFOs asincrónicos se introduce el tema de la meta-estabilidad. Una implementación común de un FIFO asincrónico usa un Gray code ( o cualquier código de unidad de distancia) para los punteros de lectura y escritura de modo de asegurarse una generación de banderas (flags) segura/estable. Otra nota adicional respecto de la generación de banderas es que uno debe necesariamente usar punteros aritméticos para generar banderas para implementaciones asincrónicas de FIFO. Por otro lado, uno puede usar tanto un acercamiento “leaky bucket” o punteros aritméticos para generar banderas en una implementación FIFO sincrónica.

El hardware FIFO se utiliza para propositos de sincronizacion como:

1. Puntero de Lectura/Registro de Dirección de Lectura.
2. Puntero de Escritura/Registro de Dirección de Escritura.

2.6.2 SJF

(Segun Silberschatz, 2001) SJF al igual que en el algoritmo FIFO las ráfagas se ejecutan sin interrupción, por tanto, sólo es útil para entornos batch. Su característica es que cuando se activa el planificador, éste elige la ráfaga de menor duración. Es decir, introduce una noción de prioridad entre ráfagas.

Hay que recordar que en los entornos batch se pueden hacer estimaciones del tiempo de ejecución de los procesos. La ventaja que presenta este algoritmo sobre el algoritmo FIFO es que minimiza el tiempo de finalización promedio, como puede verse en el siguiente ejemplo:

Supongamos que en un momento dado existen tres ráfagas listos R1, R2 y R3, sus tiempos de ejecución respectivos son 24, 3 y 3 ms. El proceso al que pertenece la ráfaga R1 es la que lleva más tiempo ejecutable, seguido del proceso al que pertenece R2 y del de R3.

FIFO F = (24 + 27 + 30) / 3 = 27 ms.
SJF F = (3 + 6 + 30) / 3 = 13 ms.

2.6.3 RR (Round Robin)

(Segun Bic, L, 1995) 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 CPU. Si el proceso se bloquea o termina antes de agotar su cuantum también se alterna el uso de la CPU.El round robin es muy fácil de implementar.

(Segun Bic, L, 1995) Todo lo que necesita el planificador es mantener una lista de los procesos listos.Round robin es un método para seleccionar todos los elementos en un grupo de manera equitativa y en un orden racional, normalmente comenzando por el primer elemento de la lista hasta llegar al último y empezando de nuevo desde el primer elemento. El planeamiento Round Robin es tan simple como fácil de implementar, y está libre de inanición.El nombre del algoritmo viene del principio de Round-Roubin conocido de otros campos, donde cada persona toma una parte de un algo compartido en cantidades parejas.

Una forma sencilla de entender el round robin es imaginar una secuencia para "tomar turnos". En operaciones computacionales, un método para ejecutar diferentes procesos de manera concurrente, para la utilización equitativa de los recursos del equipo, es limitando cada proceso a un pequeño periodo de tiempo (quantum), y luego suspendiendo éste proceso para dar oportunidad a otro proceso y así sucesivamente.

A esto se le denomina comúnmente como Planificación Round-Robin.

Aplicación en Sistemas Operativos:

Round Robin es uno de los algoritmos de planificación de procesos más simples dentro de un sistema operativo que asigna a cada proceso una porción de tiempo equitativa y ordenada, tratando a todos los procesos con la misma prioridad. En Sistemas operativos, la planificación Round Robin da un tiempo máximo de uso de CPU a cada proceso, pasado el cual es desalojado y retornado al estado de listo, la lista de procesos se planifica por FCFS, primero llegado, primero atendido.

Pasos de ciclos:

Para averiguar los pasos de ciclos de procesos totales se toman todos los números de procesos y se calculan con los procesos necesarios para la realización de estos...Suponga que hay tres procesos y se desea averiguar cuanto tarda.proceso

A: 3 vecesproceso B: 4 vecesproceso C: 5 veces

Aplicación en redes:

La planificación Round Robin puede ser aplicada también a otros problemas de planificación, como la planificación de redes. En las redes inalámbricas, donde varios servidores comparten un mismo canal, este algoritmo provee a cada servidor un intervalo regular de tiempo para transmitir o recibir información mediante el canal compartido. Esto hace parecer a Round Robin como un algoritmo justo, pero, de todos modos, por ser mucho menos eficiente que el "algoritmo de proporcionalidad justa", es muy difícil proveer un buen servicio a los suscriptores. El operador de la red también sufrirá capacidad reducida en la red.

La causa principal es que este algortimo no tiene en cuenta el cambio de condiciones de recepción en los diferentes receptores, por lo que planeará transmisiones desde/hacia los suscriptores de la mitad de tiempo cuando sus condiciones de recepción sean peores que las habituales. En contraste, el planeamiento de proporcionalidad justa tendrá en cuenta el cambio de condiciones de recepción en los diferentes receptores y agendará las transmisiones desde/hacia los suscriptores cada vez que las condiciones de recepción estén peores que lo normal.

2.6.4 Queves Multilevel

(Segun Deitel, 1987) Un algoritmo de planificación multinivel particiona la cola de listos en colas separadas. Se asignan en forma permanente los trabajos a una cola, generalmente, basándose en alguna propiedad del mismo (requerimientos de memoria, tipo de trabajo), teniendo cada cola su propio algoritmo.

Por ejemplo, la cola interactiva podría planificarse usando RR y la batch FIFO. Ningún trabajo en una cola de baja prioridad puede ejecutarse si las colas con mayor prioridad no están vacías. Si algún trabajo entra en una cola de mayor prioridad, el trabajo de otras colas es interrumpido.

2.6.5 Multi Level Feedback Queves

(Segun Deitel, 1987) En colas multinivel realimentadas los trabajos pueden moverse dentro de distintas colas. La idea es separar procesos con distintos tipos de interrupciones de la CPU.
Si un trabajo consume mucho tiempo de CPU, será movido a una cola con menor prioridad.En forma similar, si un proceso espera demasiado tiempo en una cola de baja prioridad, lo moveremos a una cola de mayor prioridad.En general un planificador de este tipo esta definido por los siguientes parámetros:

*El número de colas.
*El tipo de algoritmo de planificación de cada cola.
*Un método de determinación de cuando mover un trabajo a una cola de mayor prioridad.
*Un método de determinación de cuando mover un trabajo a una cola de menor prioridad.
*Un método de determinación de a qué cola se enviará un trabajo cuando necesita servicio.