PLANIFICADOR PROCESOS

PLANIFICADOR PROCESOS

El planificador de procesos (process scheduler, en inglés) es la parte del sistema operativo que se encarga de seleccionar a qué proceso se asigna el recurso procesador y durante cuánto tiempo. 

El planificador de procesos tiene como funciones principales:

• Llevar el control del estado de cada proceso.
• Decidir qué proceso usará el procesador y durante cuanto tiempo, para ello empleará un cierto criterio en base al cual tomará las decisiones. Si implementa multiprogramación, deberá emplear un criterio que evite que un proceso monopolice el procesador.
• Asignar el procesador al proceso, restableciendo el contexto de la ejecución del proceso por donde fuere. El contexto de la ejecución se encuentra almacenado en el PCB del proceso asignado.
• Retirar el procesador al proceso, salvando el contexto de la ejecución del proceso, para poder restablecerlo posteriormente una vez que vuelva a ser asignado. El contexto de la ejecución se almacenará en el PCB del proceso retirado.

El planificador de procesos es software, por tanto, requiere emplear el recurso procesador para ejecutar su código.

Para la siguiente configuración de procesos:

• Proceso Pa: Llega en el instante de tiempo 0. Realiza una llamada al sistema bloqueante cada 1 unidad de tiempo, la operación bloqueante se resuelve tras 2 unidades de tiempo. Para finalizar su ejecución requiere 4 unidades de ejecución.
• Proceso Pb: Llega en el instante de tiempo 1. Para finalizar su ejecución requiere 4 unidades de ejecución.
• Suponga que el proceso Pa tiene mayor prioridad que el proceso Pb, por tanto, el planificador debe de dejar paso al proceso Pa siempre que éste esté en estado preparado.

La evolución de la asignación del procesador que realizaría el planificador es la siguiente:

 

Objetivos de la Planificación de procesos

La Planificación de procesos tiene como principales objetivos la equidad, la eficacia, el tiempo de respuesta, el tiempo de regreso y el rendimiento.

• Equidad: Todos los procesos deben ser atendidos.
• Eficacia: El procesador debe estar ocupado el 100% del tiempo.
• Tiempo de respuesta: El tiempo empleado en dar respuesta a las solicitudes del usuario debe ser el menor posible.
• Tiempo de regreso: Reducir al mínimo el tiempo de espera de los resultados esperados por los usuarios por lotes.
• Rendimiento: Maximizar el número de tareas que se procesan por cada hora. 

Algoritmos de Planificación

Primero en llegar primero en ser servido

Conocido como FCFS (First Come First Served). Este algoritmo emplea una cola de procesos, asignando un lugar a cada proceso por el orden de llegada. Cuando el proceso llega es puesto en su lugar en la cola después del que llegó antes que él y se pone en estado de listo. Cuando un proceso comienza a ejecutarse no se interrumpe su ejecución hasta que termina de hacerlo.

Prioridad al más corto

Su nombre es SJF (Shortest Job First). El proceso que se encuentra en ejecución cambiará de estado voluntariamente, o sea, no tendrá un tiempo de ejecución determinado para el proceso. A cada proceso se le asigna el tiempo que usará cuando vuelva a estar en ejecución, y se irá ejecutando el que tenga un menor tiempo asignado. Si se da el caso de que dos procesos tengan igual valor en ese aspecto emplea el algoritmo FCFS.

Round Robin

A cada proceso se le asigna un tiempo determinado para su ejecución, el mismo tiempo para todos. En caso de que un proceso no pueda ser ejecutado completamente en ese tiempo se continuará su ejecución después de que todos los procesos restantes sean ejecutados durante el tiempo establecido. Este es un algoritmo basado en FCFS que trata la cola de procesos que se encuentran en estado de listos como una cola circular.

Planificación por prioridad

En este tipo de planificación a cada proceso se le asigna una prioridad siguiendo un criterio determinado, y de acuerdo con esa prioridad será el orden en que se atienda cada proceso.

Planificación garantizada

Para realizar esta planificación el sistema tiene en cuenta el número de usuarios que deben ser atendidos. Para un número "n" de usuarios se asignará a cada uno un tiempo de ejecución igual a 1/n.

Planificación de Colas Múltiples

El nombre se deriva de MQS (Multilevel Queue Schedulling). En este algoritmo la cola de procesos que se encuentran en estado de listos es dividida en un número determinado de colas más pequeñas. Los procesos son clasificados mediante un criterio para determinar en qué cola será colocado cada uno cuando quede en estado de listo. Cada cola puede manejar un algoritmo de planificación diferente a las demás.

Tiempos

En la Planificación de procesos se tiene en cuenta diferentes tiempos que pueden ser calculados, como son el "Tiempo de espera medio", el "Tiempo de retorno del proceso" y el "Tiempo de retorno medio".

Tiempo de espera medio

Es el promedio de tiempos en que los procesos están en estado de listos. En algoritmos FCFS este tiempo suele ser bastante largo. En algoritmos SJF para los procesos largos este tiempo suele ser muy grande, pues se estarán ejecutando constantemente los procesos más cortos y los más largos se encontrarán constantemente en espera, por lo que pueden entrar en inanición. En Planificación por prioridad los procesos de prioridad baja podrían no ejecutarse nunca. Para dar solución a este problema el envejecimiento de un programa eleva su prioridad.

Tiempo de retorno del proceso

Es el tiempo que transcurre desde la creación de un proceso hasta que termina la ejecución del programa que le dio lugar.

Tiempo de retorno medio

Es la suma de los tiempos de retorno de cada uno de los procesos dividida entre la cantidad de procesos.

 

PROCESOS

 PROCESOS

Dentro de las operaciones más básicas y la vez más complejas de nuestra PC encontramos los procesos. Estos nos permitirán entrar al mundo que se "DESPERTARA" en nuestra computadora, o por lo menos seria nuestra manera de decirlo. Siempre que le pidamos a nuestra computadora que haga algo, los procesos asumirán el trabajo y de esta manera el microprocesador dará ejecución al plan que realice el sistema operativo a través de los procesos.

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.

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 son independientes y no comparten memoria (es decir, información) con el proceso que los ha creado.

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.

Estados de un proceso

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.

Modelo de dos 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 dos 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 bloqueados esperando hasta que puedan proseguir. Se divide entonces al estado No ejecución en dos estados: Listo y Bloqueado. Se agregan además un estado Nuevo y otro Terminado.

Los cinco estados de este diagrama son los siguientes:

• Ejecución: el proceso está actualmente en ejecución.
• Listo: el proceso está listo para ser ejecutado, sólo está esperando que el planificador así lo disponga.
• Bloqueado: el proceso no puede ejecutar hasta que no se produzca cierto suceso, como una operación de Entrada/Salida.
• 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 Bloqueado y Listo tienen ambos una cola 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. Los procesos suspendidos son mantenidos en una cola de bloqueados. Cuando se da un suceso se pasan a la cola de listos los procesos que esperaban por ese suceso.

Si existe un esquema con diferentes niveles de prioridad de procesos es conveniente mantener varias colas de procesos listos, una para cada nivel de prioridad, lo que ayuda a determinar cuál es el proceso que más conviene ejecutar a continuación.

Procesos suspendidos

Una de las razones para implementar el estado Bloqueado 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 en nuestro modelo de cinco estados todos los procesos en memoria estén esperando en el estado Bloqueado 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 bloqueado. Sólo convendría traerlo cuando ya está listo para ejecutar, esto implica que ya aconteció el suceso que estaba esperando cuando se bloqueó. Para tener esta diferenciación entre procesos suspendidos, ya sean listos como bloqueados, se utilizan cuatro estados: Listo, Bloqueado, Bloqueado y suspendido y Listo y suspendido.

Procesos en espera

Dos o más procesos pueden cooperar mediante señales de forma que uno obliga a detenerse a los otros hasta que reciban una señal para continuar.

• Se usa una variable llamada semáforo para intercambiar señales.
• Si un proceso esta esperando una señal, se suspende (WAIT) hasta que la señal se envíe (SIGNAL).
• Se mantiene una cola de procesos en ESPERA en el semáforo.
• La forma de elegir los procesos de la cola en ESPERA es mediante una política FIFO.

La sincronización explícita entre procesos es un caso particular del estado "bloqueado". En este caso, el suceso que permite desbloquear un proceso no es una operación de entrada/salida, sino una señal generada a propósito por el programador desde otro proceso.

 

PAGINACION Y SEGMENTACION

PAGINACION

La paginación es un esquema de gestión de memoria muy utilizado actualmente, que consiste en dividir la memoria principal, en bloques iguales de tamaño fijo y relativamente pequeños, que se denominan marcos de pagina. De igual modo, los procesos se dividen también en bloques de tamaño fijo y de igual tamaño que los de la memoria principal, que se denominan páginas. De esta manera, las paginas en que se ha dividido un proceso, pueden asignarse a los marcos libres de la memoria principal.

           

La utilización de este esquema de gestión de memoria permite asegurar, que no se va a producir fragmentación externa, ya que cualquier marco libre, se puede asignar al proceso que lo necesite y que solo se producirá una pequeña fragmentación interna, en la última pagina del proceso, ya que los marcos se asignan como unidades, por lo tanto, si los requisitos de memoria de un proceso, no coinciden con los limites de las paginas, el último marco asignado puede estar parcialmente vacío.

 

Cada sistema operativo tiene sus propios métodos para almacenar las tablas de páginas y la mayoría asigna una tabla de páginas para cada proceso. En el bloque de control de proceso se almacena un apuntador a la tabla de páginas y cuando al despachador se le indica que inicie un proceso debe volver a cargar la tabla de páginas correspondiente

SEGMENTACION

La generalización del concepto de dividir la memoria en varias partes, definido anteriormente, introduce un aspecto importante en la administración de la memoria, que consiste en la separación de la perspectiva que el usuario tiene de la memoria lógica o virtual y la memoria física o real.

 

La perspectiva que el usuario tiene de la memoria, se fundamenta en la organización lógica de un programa en la actualidad, que no se corresponde con el concepto de la memoria física real, pero si existe, una correspondencia entre la perspectiva del usuario y la estructura de la memoria física, que permite establecer la diferencia entre la memoria lógica y la memoria física.

La memoria física está formada por un vector lineal de palabras, algunas con instrucciones y otras con datos, sin embargo, el usuario no considera la memoria como un vector lineal de palabras, si no más bien, como un conjunto de partes claramente definidas por la función que cumplen en el desarrollo del programa.

Cada una de esas partes esta agrupada de tal forma, que puedan ocupar posiciones contiguas de la memoria, pero las partes entre sí, pueden estar separadas y en cualquier orden. Al espacio que ocupan cada una de esas partes es a lo que se denomina segmento.

Un programa desde el punto de vista del usuario, está formado por un módulo principal y varios secundarios, los cuales utilizan unos módulos de código y unas estructuras de datos determinadas. Cada uno de los módulos o partes del programa tiene un nombre, que define el usuario sin preocuparse por las direcciones que estas partes van a ocupar en la memoria.

Cada una de esas partes ocupa un segmento, que tiene una longitud variable y que está definida intrínsecamente por el propósito de ese segmento en el programa. Los elementos de información que contiene un segmento, se identifican por su desplazamiento, a partir del inicio del segmento correspondiente.

COMO  ACTÚA  LA  SEGMENTACIÓN.

Aunque el usuario se puede referir a los objetos de un programa utilizando direcciones lógicas bidimensionales, la memoria física real sigue siendo una secuencia unidimensional de bytes o palabras.

Por todo ello, debemos definir una forma de implantar la correspondencia entre direcciones lógicas bidimensionales, definidas por el usuario y direcciones físicas unidimensionales. Esta correspondencia se logra por una estructura de datos que se denomina tabla segmentos.