PLANIFICACIÓN DE PROCESOS

Cuando más de un proceso es ejecutable desde el punto de vista lógico, el Sistema Operativo debe decidir cuál de ellos debe ejecutarse en primer término.

El Planificador es la porción del Sistema Operativo que decide y el Algoritmo de Planificación es el utilizado.

Las decisiones de planificación de CPU se toman según  las cuatro situaciones siguientes:

1. Cuando un proceso pasa del estado en ejecución a en espera.

2. Cuando un proceso pasa del estado en ejecución a listo.

3. Cuando un proceso pasa del estado en espera al estado listo.

4. Cuando un proceso termina.

Los principales conceptos relacionados con Planificación del Procesador son los siguientes:

ñ Planificación apropiativa: es la estrategia de permitir que procesos ejecutables (desde el punto de vista lógico) sean suspendidos temporalmente.

ñ Planificación no apropiativa: es la estrategia de permitir la ejecución de un proceso hasta terminar. 

Principales algoritmos de planificación:

FIFO (First in, First ouput - primero en entrar, primero en salir): es un algoritmo no apropiativo ya que no libera el CPU hasta la ejecución del proceso.

Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que lleva más tiempo listo. Cuando el CPU está libre, éste es asignado al proceso que está en la cabeza de la cola. El proceso en ejecución se mantiene en la CPU hasta que espontáneamente lo suelta ya sea porque el proceso finalizó o por algún requerimiento de E/S.

Este algoritmo puede presentar un inconveniente ya que si el proceso que está adelante es demasiado largo, el resto sin importar su tiempo de duración, debe esperar hasta que termine completamente.

SJF (Short job first – Primero el trabajo más corto): puede ser apropiativo o no apropiativo.

Este tipo de algoritmo de planificación se usa para trabajos en batch o de procesamiento por lotes en los cuales se puede saber cual es el tiempo de duración de la ejecución de cada proceso y entonces se puede seleccionar primero el trabajo más corto. El problema que se presenta con éste algoritmo es que los grandes procesos podrían sufrir de inanición dado que cualquier proceso pequeño se "cuela" sobre uno de mayor tamaño y como resultado final se podría dar el caso que el proceso grande nunca obtenga procesamiento.

SRTF (Short Remaining time first – Tiempo restante de ejecución menor): es la parte apropiativa de SJF.

En este caso si un nuevo proceso pasa a listo y es más corto que lo que queda por ejecutar del proceso en ejecución, el proceso en ejecución pasa a listo y el nuevo a ejecución, es decir el proceso en CPU es desalojado si llega a la cola un proceso con duración más corta.

Round Robin: En este tipo de planificación cada proceso tiene asignado un quantum de tiempo para ejecutarse, en este caso al finalizar el quantum. El quantum de un proceso equivale a un número fijo de pulsos o ciclos de reloj. Si ese quantum no es suficiente para acabar, el reloj del sistema genera una interrupción y el proceso pasa de nuevo a la cola para ser atendido nuevamente cuando todos los demás procesos hayan recibido su quantum. 

La determinación del tamaño del cuanto es vital para la operación efectiva de un sistema de cómputo.


Si el cuanto de tiempo es muy grande, cada proceso tendrá el tiempo necesario para terminar, de manera que el esquema de planificación por turno rotatorio degenera en uno de primero-en-entrar-primero-en-salir. Si el cuanto es muy pequeño, el gasto extra por cambio de proceso se convierte en el factor dominante y el rendimiento del sistema se degradará.


Prioridad: A cada proceso se le asocia una prioridad y la CPU es asignada al proceso de mayor prioridad, el criterio principal es hacer que los procesos ‘en espera’ sean los primeros en ejecutarse es por esa que los procesos de prioridad más baja tienen riesgo de inanición, para evitar esto es recomendable ir aumentando de forma progresiva la prioridad de los procesos en espera.


Las prioridades pueden ser definidas externa o internamente. De forma interna, la define el SO. De forma externa, la definen los usuarios. El algoritmo SJF es un caso de planificación por prioridad.



 


Para conocer los tiempos de espera (tiempo que un proceso permanece en la cola de preparados) y de retorno (tiempo transcurrido entre la llegada de un proceso y su finalización), se utilizan las siguientes fórmulas:

Además se construye un diagrama de Gantt para colocar los procesos, todo esto se realiza según el criterio de cada algoritmo. Por ejemplo:


Se tiene una tabla con los siguientes valores y se desea aplicar el algoritmo FIFO:

TRANSICIÓN DE PROCESOS

n  De Nuevo a Listo: Este estado indica que ha un proceso recién creado se le permite competir por los recursos del CPU.

n  De Listo a en Ejecución: Es cuando a un proceso tiene la CPU a su disposición.

n  De Ejecución a Bloqueado: Esta transición sucede cuando un proceso realiza una operación de Entrada/Salida antes de que termine su tiempo de ejecución. El proceso abandona la CPU y se bloquea así mismo.

n  De Ejecución a Listo: Cuando el proceso que ocupa la CPU lleva demasiado tiempo ejecutándose, el sistema operativo decide que otro proceso ocupe la CPU, pasando el proceso que ocupaba la CPU a estado listo.

n  De Bloqueado a Listo: Se dispone del recurso por el que se había bloqueado el proceso.

n  De Bloqueado a Terminado: Ocurre cuándo el proceso supere el tiempo máximo de espera de un recurso y el SO decida terminarlo.

n  De Ejecución a Terminado: Esta transición ocurre cuando el proceso se ha terminado de ejecutarse, y pasa a un estado de terminado.

Cambio de Procesos: En cierto momento, un proceso que se está ejecutando se interrumpe, el sistema operativo pone a otro proceso en el estado de ejecución y pasa el control a dicho proceso. Un cambio de proceso puede suceder en cualquier instante en el que el sistema operativo gana el control de la CPU. Uno de los eventos que provocan un cambio de estado en el proceso son las interrupciones como las interrupciones de Entrada/salida, las interrupciones de reloj o falta de memoria.

Cambio de Contexto: el contexto son las principales características que proporcionan información sobre el entorno de un proceso como el contador de Programa, registros del procesador, información de la pila y sus principales atributos. Un cambio de contexto implica salvar toda la información referente al proceso que se está ejecutando para reanudarlo posteriormente; puede ocurrir un cambio de contexto sin cambiar el estado del proceso que está actualmente en estado de ejecución, sin embargo, un cambio de proceso si implica un cambio de contexto.

ESTADOS DE PROCESOS

Durante su existencia un proceso pasa por una serie de estados discretos, siendo varias las circunstancias que pueden hacer que el mismo cambie de estado.

Según el sistema operativo, los modelos de estado pueden variar, sin embargo este es el más utilizado:

• 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.
• Listo: el proceso está listo para ser asignado a un procesador y ser ejecutado, sólo está esperando que el despachador así lo disponga.

Para aclarar el término, el despachador o dispatcher es una entidad del sistema operativo cuya función es la de asignar un proceso al CPU.

• Ejecución: el proceso está actualmente en ejecución.
• Bloqueado: el proceso no puede ejecutar hasta que no se produzca cierto suceso, como una operación de Entrada/Salida.
• 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éticos, etc.

Bloqueo de procesos: cuando un proceso está pendiente de un evento externo que le ha hecho bloquear, tales como una operación de lectura/escritura, la espera de finalización de un proceso hijo, una señal o una operación sobre un semáforo. El dispositivo o hecho externo "avisa" al S.O. cuando ha terminado la acción que realizaba mediante una INTERRUPCIÓN, puede ocurrir que el S.O. deje lo que está haciendo para atender a esta última. Tras esto, el S.O. comprueba cuales son los procesos que fueron bloqueados por ese evento externo, cambiándolos al estado de preparado.

Un semáforo es una estructura diseñada para sincronizar dos o más hilos o procesos, de modo que su ejecución se realice de forma ordenada y sin conflictos entre ellos. Sin embargo, cuando un proceso requiere los recursos que otro tiene y viceversa, se produce lo que se conoce como interbloqueo.

Interbloqueo: El interbloqueo se puede definir como el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros.

Un proceso requiere recursos y si los recursos no están disponibles, el proceso entra en estado de espera. Puede suceder que el proceso que espera nunca cambie su estado debido a que los recursos que requiere, están asignados a otros procesos, que a su vez están en estado de espera. Ejemplo: 

• Dos procesos desean imprimir grandes archivos en cinta.
• El proceso “a” solicita la impresora, que se le concede.
• El proceso “b” solicita la unidad de cinta, que se le concede.
• El proceso “a” solicita la unidad de cinta, pero se deniega la solicitud hasta que “b” la libera.
• El proceso “b” solicita la impresora y se produce el bloqueo.

Adicional a estos estados, existen 2 que valen la pena mencionar por su importancia o particularidad: 

Proceso Suspendido: El estado suspendido permite tener en espera un proceso hasta que se realice el proceso para continuar. El procesador es más rápido que la Entrada/Salida y dado que para que un proceso se ejecute debe ser cargado en memoria completamente todos los procesos tendrían que esperar haciendo más lentas las operaciones. Para conseguir más memoria una 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 evitando que el proceso entre al reparto de CPU y manteniéndolo en una cola de bloqueados.

Zombie: Todo proceso al finalizar avisa a su proceso padre, para que éste elimine su entrada de la tabla de procesos. En el caso de que el padre, por algún motivo, no reciba esta comunicación no lo elimina de la tabla de procesos. En este caso, el proceso hijo queda en estado zombie, no está consumiendo CPU, pero sí continua consumiendo recursos del sistema.

Para entender más sobre los procesos padre e hijo, es necesario hablar un poco de hilos.

Un hilo es básicamente una tarea que puede ser ejecutada en paralelo con otra tarea. Permiten dividir un programa en dos o más tareas que corren simultáneamente. 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, entre otros

Los beneficios clave de los hilos se derivan de las implicaciones del rendimiento: se tarda menos tiempo en crear un nuevo hilo de un proceso que ya existe, en terminarlo, y en hacer un cambio de contexto entre hilos de un mismo proceso. Al someter a un mismo proceso a varios flujos de ejecución se mantiene una única copia en memoria del código, y no varias.

CREACIÓN Y TERMINACIÓN DE PROCESOS

Creación de procesos: los procesos se crean mediante una llamada al sistema de “crear proceso”, durante el curso de su ejecución se construye las estructuras de datos que son usadas para administrar los procesos y le asigna espacio de direcciones.

Los procesos pueden ser creados por:

• El sistema operativo.
• Por otro proceso (en este caso el proceso creador se denomina padre mientras que al proceso creado se le llama hijo).
• Por las aplicaciones de usuario.
• Por la entrada de un nuevo usuario al sistema.

Cada vez que el SO crea un proceso se procede de la siguiente manera:

• Asignar un único identificador del proceso.
• Asignar espacio para el proceso. Elementos de la imagen del proceso. Espacio de direcciones privado, de la pila.
• Inicializar el Bloque de Control de Procesos.
• Establecer los enlaces apropiados. Colocarlo en la lista de procesos listos o suspendidos.
• Crear otras estructuras de control.

Bloque de Control de Procesos: Cada proceso se representa en el Sistema Operativo con un bloque de control de proceso (también llamado bloque de control de tarea).

Estado: actual del proceso. Contador de programa: indica la dirección de la siguiente instrucción que se ejecutará de ese proceso. Registros de CPU: acumuladores, registros, índice, punteros de pila y registros generales. Información de planificación de CPU: prioridad del proceso, punteros a colas de planificación, etc. Información de gestión de memoria: valor de los registros de base y límite, tabla de páginas o tabla de segmentos. Información de contabilidad: tiempo de CPU, tiempo consumido, números de procesos, etc. Información de estado de E/S: dispositivos de E/S asignados a este proceso, lista de archivos abiertos, etc.

Terminación de un proceso: Un proceso termina cuando ejecuta su última instrucción y pide al sistema operativo que lo elimine. En este momento, el proceso puede devolver un valor de estado a su proceso padre.

El sistema operativo libera la asignación de todos los recursos del proceso, incluyendo las memorias física y virtual, los archivos abiertos y los búferes de E\S.

Razones para la terminación de un proceso:

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

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

Violación de límites: Proceso trata de acceder a una posición de memoria que no le está permitida acceder.

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

Error de protección: El proceso intenta utilizar un recurso o archivo que no le está permitido utilizar, o trata de utilizarlo de forma incorrecta.

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

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

Fallo de dispositivo de E/S: Se produce un error en una operación de E/S

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

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

Finalización del padre: Cuando un proceso padre finaliza, el SO puede diseñarse para terminar automáticamente con todos sus descendientes.

Mal uso de los datos: Un elemento de dato, no está inicializado o es de un tipo equivocado.

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

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

PROCESOS

Un proceso es una instancia de ejecución de un programa, caracterizado por su contador de programa, su palabra de estado, sus registros del procesador, su segmento de texto, pila y datos.

Los procesos pueden ser:

Independientes: no puede afectar, ni ser afectado por los demás procesos que se ejecutan en el sistema, compiten por el uso de recursos escasos.

Cooperativos: en este caso se entiende que los procesos interactúan entre sí y pertenecen a una misma aplicación.

Modos de Ejecución:

Modo Usuario: son procesos ejecutados por las distintas aplicaciones, dichos procesos tienen privilegios limitados para proteger al sistema operativo de las inferencias de los programas de usuario.

Modo núcleo o kernel: bajo este modo, el sistema operativo tiene control completo del procesador y de todas las instrucciones, registros y memoria. Son procesos críticos que requieren de todos los privilegios para optimizar el uso de los recursos del sistema y proveer tiempos de respuesta aceptables (las interrupciones se incluyen en el núcleo para actuar rápido).

El “núcleo” del Sistema Operativo controla todas las operaciones que implican procesos y representa solo una pequeña porción del código de todo el Sistema Operativo pero es de amplio uso.


Generalmente permanece en el almacenamiento primario.

Cuando ocurre una interrupción el núcleo inhabilita las demás mientras responde una de ellas. Las interrupciones son habilitadas de nuevo después de completar el proceso.