Itineración de procesos

De Departamento de Informatica
Saltar a: navegación, buscar

La Itineración de Procesos, planificación de procesos o Process Scheduling es un concepto en sistemas operativos que se refiere a cómo los procesos son efectivamente ejecutados en el computador. Esta tarea es llevada a cabo por el itinerador de procesos (o process scheduler), quien toma un proceso disponible y lo pone en marcha. El estudio de éste concepto es sumamente importante pues la correcta implementación de cómo los procesos rotan su turno de ejecución permite lograr un rendimiento óptimo de la máquina, cumplir el objetivo de la multiprogramación (tener procesos corriendo para maximizar el uso de la CPU) y el del time sharing (crear la ilusión, conmutando rápidamente los procesos en la CPU, de que el usuario puede usar cualquier programa en curso).

Contenido

Colas de itineración

Procesos activos en linux.
Cola ready y distintas cola de dispositivos.

Al igual que en una cola de compras de supermercado, o la fila de clientes en un banco, los procesos se almacenan y manipulan en colas, las cuales son usualmente listas enlazadas. Existen tres colas en las cuales los procesos son almacenados según su estado:

  • La cola de jobs o job queue, reúne a todos los procesos del sistema.
  • La cola ready o ready queue, reúne a todos los procesos listos para ser ejecutados y en espera en memoria principal.
  • La cola de dispositivos o device queue, reúne a aquellos procesos que esperan por I/O (entrada/salida).

Un buen ejemplo de implementación de estas colas es Linux: su process control block (o PCB) se representa como una estructura en Lenguaje C llamada task_struct. Esta estructura contiene toda la información necesaria para representar un proceso, desde su estado hasta los punteros correspondientes a su proceso padre y los supuestos procesos hijos que pueda tener.

La cola de todos los procesos activos se mantiene usando una lista doblemente enlazada de PCBs y el kernel mantiene un puntero «actual» (o current) que apunta al proceso que se está ejecutando actualmente. De manera similar, la cola ready se organiza en una lista enlazada, donde su cabeza tiene dos punteros, uno apuntando al primer PCB y el otro apuntando al último. La cola de dispositivos, diseñada para aquellos procesos que requieren utilizar el mismo dispositivo, tiene la misma organización que la cola ready; además, cada dispositivo cuenta con su propia cola de espera.

La imagen a la derecha concretiza la idea de estas colas. La primera cola es la ready, donde se observan los punteros hacia el primer PCB y al último (head y tail respectivamente). Se observan además dos colas de dispositivos vacías pertenecientes a cintas magnéticas, una cola de disco duro con tres procesos encolados y una unidad de terminal con sólo un proceso en cola.


¿Qué sucede durante la planificación?

La itineración de procesos puede ser representada bajo un diagrama de encolamiento o diagrama de colas la cual muestra la interacción y planificación entre las distintas colas durante la vida de un proceso. En la imagen se aprecian las colas (rectángulos grises), los recursos que sirven a las colas (círculos celestes) y las flechas que indican el flujo de los procesos.

Diagrama de colas. Las colas (en gris) y los servicios usados por éstas (celestes).

Los procesos actúan de la siguiente manera según el diagrama:

  1. Todo nuevo proceso se coloca en la cola ready, esperando a ser seleccionado para la ejecución, vale decir, hasta ser «despachado». Cuando la CPU es asignada al proceso pueden suceder varias cosas dependiendo del mismo.
  2. Si el proceso ejecuta una solicitud de I/O, es colocado en la cola de dispositivo correspondiente.
  3. Si el tiempo asignado por la CPU para el proceso se termina, éste vuelve a la cola ready.
  4. Si el proceso crea un nuevo subproceso, tendrá que esperar hasta que este termine.
  5. Puede ser que el proceso sea removido de la CPU como resultado de una interrupción y puesto nuevamente en la cola ready.

En los casos 2 y 4 los procesos eventualmente cambian su estado de «espera» (wait) a «preparado» (ready) y son devueltos a la cola ready. Los procesos continúan su ciclo hasta que terminan su tarea, son removidos de todas las colas y la memoria asignada al PCB se libera.

Itineradores

Los itineradores, planificadores o schedulers son los encargados de seleccionar los procesos para asignación de recursos y posterior ejecución; el sistema operativo entonces debe manipular los procesos con distintos itineradores según corresponda la tarea a realizar (asignación o ejecución). Existen dos tipos principales de itineradores, que se diferencian principalmente por la frecuencia con los que se ejecutan:

  • Itinerador de largo plazo o Job scheduler: Encargado de enviar procesos hacia la cola ready [1] y de cargar procesos a memoria principal en caso de archivos por lotes, en donde se envían mas procesos de los que son posible ejecutar. Como su nombre indica, el orden de magnitud del tiempo entre llamadas para este itinerador es de segundos, llegando incluso a minutos entre la creación de un proceso y otro. Como éste itinerador es considerado parte del itinerador de largo plazo, se dice equivalentemente que ambos reducen el grado de multiprogramación. Respecto de este punto, si el grado de multiprogramación es estable, entonces la tasa media de creación de procesos debe ser igual a la tasa de salida media de procesos que sale del sistema, por lo que éste itinerador tendría que ser invocado sólo cuando un proceso sale del sistema. Por otro lado, debido al largo intervalo entre ejecuciones, el itinerador puede darse el lujo de tomar más tiempo para decidir que procesos deben ser seleccionados para su ejecución.
  • Itinerador de corto plazo o CPU scheduler: Encargado de seleccionar algún proceso residente en la cola ready y asignarle CPU, realizando esto de forma frecuente. Un proceso puede ejecutarse pocos milisegundos para luego esperar por entrada/salida. En una sesión normal, éste puede ejecutarse cada 100 milisegundos. La itineración puede ocurrir en cuatro ocasiones: cuando un proceso pasa de estado running al estado waiting, cuando pasa de running a ready, cuando pasa de waiting a ready y cuando finaliza su ejecución. Por ejemplo, si el itinerador tarda 10 milisegundos en decidir ejecutar un proceso entonces el 10 / (100 + 10) = 9 por ciento de la CPU está siendo utilizado exclusivamente para esta tarea, lo cual significa claramente un desperdicio.

Consideraciones sobre los itineradores

Swapping. Reduce el grado de multiprogramación. Ordena los jobs en la memoria principal

En algunos sistemas, el itinerador de largo plazo no existe o puede ser mínimo. Por ejemplo sistemas de tiempo compartido como UNIX y Microsoft Windows a menudo no tienen este itinerador, sino que simplemente encolan los procesos al itinerador de corto plazo. La estabilidad entonces para estos sistemas depende de las limitaciones tanto físicas (como el número de terminales disponibles) así como del ajuste natural de los usuarios humanos.

Algunos sistemas operativos, como los sistemas de tiempo compartido, pueden introducir un nivel adicional, el itinerador de mediano plazo. La idea principal de este itinerador es que a veces puede ser ventajoso para eliminar los procesos de la memoria (y así la CPU no es disputada por tantos procesos) y reducir así el grado de multiprogramación. Luego de un tiempo, estos procesos pueden volver a ser cargados en memoria y continuar en su ejecución. Este proceso se le llama swapping o intercambio. Este esquema es necesario si, por ejemplo, se requiere mejorar la mezcla de procesos o bien si la memoria disponible se ha acabado.

Tipos de Procesos

Cuando un proceso obtiene la CPU, sobre todo cuando todavía no ha tenido oportunidad de establecer un patrón de comportamiento, el planificador desconoce la cantidad de tiempo de CPU que necesitará el proceso. Los procesos limitados por I/O normalmente usan sólo un momento antes de generar una solicitud de I/O; los procesos limitados por la CPU pueden usar el procesador durante horas si está disponible en forma no apropiativa. Así, se pueden clasificar los procesos en estos dos tipos.

  • Tipos de procesos limitados por I/O o I/O-bound process: Procesos que pasan más tiempo haciendo I/O que cálculos (muchas ráfagas cortas de CPU).
  • Tipos de procesos limitados por CPU o CPU-bound: Procesos que pasan más tiempo haciendo cálculos, (pocas ráfagas largas de CPU).

Es vital que el itinerador de largo plazo haga una cuidadosa selección entre los procesos. Este debe buscar una combinación equilibrada de procesos, pues si se trabajan sólo procesos limitados por I/O, la cola ready estará casi siempre vacía y el itinerador de corto plazo estará ocioso; en el otro extremo, trabajar únicamente con procesos limitados por CPU hará que pocas veces se requieran operaciones de entrada/salida y esta vez los dispositivos serán los que estén en un estado ocioso.

Cambios de Contexto

Las interrupciones hacen que el Sistema Operativo Obligue a la CPU a abandonar su tarea actual para ejecutar una rutina Kernel. Cuando se produce una interrupción en el Sistema Operativo se tiene que guardar el contexto actual del proceso que se esta ejecutando en la CPU. Este contexto se almacena en el PCB del proceso.

El PCB incluye:
- El valor de los registros de la CPU.
- El estado del proceso.
- Información de gestión de memoria.

Qué se realiza en un Cambio de contexto:

  • Salvaguardia del estado, en modo kernel o en modo usuario.
  • Restauración del estado, para reanudar operaciones.

Cuando se produce una cambio de contexto, el kernel guarda el contexto del proceso antiguo en su PCB y carga el contexto almacenado del nuevo proceso que se ha decidido ejecutar.

El tiempo dedicado al cambio de contexto es tiempo desperdiciado, dado que el sistema no realiza ningún trabajo útil durante la conmutación. La velocidad del cambio de contexto varía de una maquina a otra, dependiendo de la velocidad de memoria, el número de registros que tengan que copiarse y de la existencia de instrucciones especiales ( como por ejemplo, una instrucción para cargar o almacenar todos los registros).

El tiempo empleado en los cambios de contexto depende fundamentalmente del soporte Hardware.

Tema de Investigación

Referencias

Enlaces externos

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas