Resumen de procesos

 Esta entrada comprende el resumen del documento "Fundamentos Sistemas Operativos".

Planificación de procesos

Tipos de planificación 

La planificación de procesos se refiere a cómo determina el sistema operativo al orden en que irá cediendo el uso del procesador a los procesos que lo vayan solicitando.

Hay tres tipos de planificación: 

A largo plazo: Las decisiones eran tomadas considerando los requisitos pre-declarados de los procesos y los que el sistema tenía libres al terminar algún otro proceso. La planificación a largo plazo puede llevarse a cabo con periodicidad de una vez cada varios segundos, minutos e inclusive horas.

A mediano plazo: Decide cuales procesos es conveniente bloquear en determinado momento, sea por escasez/saturación de un recurso.

A corto plazo: Decide cómo compartir momento a momento al equipo entre todos los procesos que requieren de sus recursos, especialmente el procesador.

El planificador a largo plazo se encarga de admitir un nuevo proceso: la transición de nuevo a listo.

El planificador a mediano plazo maneja la activación y bloqueo de un proceso relacionado con eventos, esto es, las transiciones entre en ejecución y bloqueado, y entre bloqueado y listo.

El planificador a corto plazo decide entre los procesos que están listos para ejecutarse y determina a cual de ellos activar, y detiene a aquellos que exceden su tiempo  de procesador - implementa las transiciones entre los estados listo y en ejecución. 

Tipos de procesos

Procesos largos: Aquellos que por mucho tiempo han estado en listos o en ejecución, esto es, procesos que estén en una larga ráfaga limitada por CPU.

Procesos cortos: Los que, ya sea en este momento estén en una ráfaga limitada por entrada-salida y requieran atención meramente ocasional del procesador, o tienden a estar bloqueados esperando a eventos.

Midiendo la respuesta

Para este tema, en vez de emplear unidades temporales formales, es común emplear ticks y quantums.

Tick: una fracción de tiempo durante el cual se puede realizar trabajo útil, esto es, usar el CPU sin interrupción. El tiempo correspondiente a un tick está determinado por una señal (interrupción) periódica, emitida por el temporizador.

Quantum: el tiempo mínimo que se permitirá a un proceso el uso del procesador. 

¿Qué mecanismos o métricas se emplean para medir el comportamiento del sistema bajo determinado planificador?

Tiempo de respuesta (T): cuanto tiempo total es necesario para completar el trabajo pendiente de un proceso P, incluyendo el tiempo que esta inactivo esperando ejecución.

Tiempo en espera (E=T-t): también referido como tiempo perdido. Del tiempo de respuesta total, cuanto tiempo p esta listo y esperando ejecutar.

Proporción de penalización (P=T/t) : proporción del tiempo de respuesta en relación al tiempo de uso del procesador (en qué proporción fue penalizado el proceso).

Proporción de respuesta (R=t/T): fracción del tiempo de respuesta durante la cual p pudo ejecutarse.

Tiempo nucleo o kernel: tiempo que pasa el sistema en espacio de núcleo, incluyendo entre otras funciones el empleado en decidir e implementar la política de planificación y los cambios de contexto.

Tiempo de sistema: tiempo que pasa un proceso en espacio núcleo atendiendo el pedido de un proceso.

Tiempo de usuario: tiempo que pasa un proceso en modo usuario, es decir, ejecutando las instrucciones que forman parte explicita y directamente del programa.

Tiempo de uso del procesador: tiempo durante el cual el procesador ejecutó instrucciones por cuenta de un proceso.

Tiempo desocupado: tiempo en que la cola de procesos listos esta vacía y no puede realizarse ningún trabajo.

Algoritmos de planificación

El planificador a corto plazo puede ser invocado cuando un proceso se encuentra en algunas de las cuatro siguientes circunstancias:

1. Pasa de estar ejecutando a estar en espera.

2. Pasa de estar ejecutando a estar listo.

3. Deja de estar en espera a estar listo.

4. Finaliza su ejecución, y pasa de ejecutando a terminado.

Objetivos de la planificación 

Los algoritmos que serán presentados a continuación son respuestas que intentan, de diferentes maneras y desde distintos supuestos base, darse a los siguientes objetivos principales:

Ser justo: debe tratarse de igual manera a todos los procesos que compartan las mismas características, y nunca postergar indefinidamente uno de ellos.

Maximizar el rendimiento: dar servicio a la mayor parte de procesos por unidad de tiempo.

Ser predecible: un mismo trabajo debe tomar aproximadamente la misma cantidad de tiempo en completarse independientemente de la carga del sistema.

Minimizar la sobrecarga: el tiempo que el algoritmo pierda en burocracia debe mantenerse al mínimo, dado que este es tiempo de procesamiento útil perdido.

Equilibrar el uso de recursos: favorecer a los procesos que empleen recursos subutilizados, penalizar a los que peleen por un recurso sobreutilizado causando contención en el sistema.

Evitar la postergación indefinida: aumentar la prioridad de los procesos mas viejos, para favorecer que alcancen a obtener algún recurso por el cual estén esperando.

Favorecer el uso esperado del sistema: en un sistema con usuarios interactivos, maximizar la prioridad de los procesos que sirvan a solicitudes iniciadas por este.

Dar preferencia a los procesos que podrían causar bloqueo: si un proceso de baja prioridad esta empleando un recurso del sistema por el cual mas proceso están esperando, favorecer que este termine de emplearlo mas rápido.

Favorecer los procesos con un comportamiento deseable: si un proceso  causa muchas demoras, se le puede penalizar porque degrada el rendimiento global del sistema.

Degradarse suavemente: si bien el nivel ideal de utilización del procesador es al 100%, es imposible mantenerse siempre a este nivel.

Primero llegado, primero servido

El esquema mas simple de planificación es el primero llegado, primero servido. Puede observarse que FCFS tiene características claramente inadecuadas para trabajo interactivo, sin embargo, al no requerir de hardware de apoyo (como un temporizador) sigue siendo ampliamente empleado.

Ronda (Round Robin)

El esquema Ronda busca dar una relacion de respuesta buena, tanto para procesos largos como para los cortos. La principal diferencia entre la ronda  y FCFS es que en este caso si emplea multitarea apropiativa: cada proceso que esté en la lista de procesos listos puede ejecutarse por un solo quantum.

La ronda puede ser ajustada modificando la duración de q.

El proceso mas corto a continuación (SPN)

Cuando no se tiene la posibilidad de implementar multitarea apropiativa, pero se requiere de un algoritmo mas justo, contando con información por anticipado acerca del tiempo que requieren los procesos que forman la lista, puede elegirse el mas corto de los presentes.

SPN apropiativo

Finkel apunta que a pesar de intuitivamente daría una mayor ganancia combinar las estrategias de SPN con un esquema de multitarea apropiativa, el comportamiento obtenido es muy similar para la amplia mayoría de los procesos.

Ronda egoísta (SRR)

Este método busca favorecer los procesos que ya han pasado tiempo ejecutando que a los recién llegados. De hecho, los nuevos procesos no son programados directamente para su ejecución, sino que se les forma en la cola de procesos nuevos, y se avanza únicamente con la cola de procesos aceptados.

Retroalimentación multinivel (FB)

Basa su operación en mas de una cola, pero en este caso, todas ellas tendrán el mismo tratamiento general, distinguiéndose solo por su nivel de prioridad.

Lotería 

Bajo este esquema, cada proceso tiene un numero determinado de boletos, y que cada boleto le representa una oportunidad de jugar la lotería. Cada vez que el planificador tiene que elegir el siguiente proceso a poner en ejecución, elige un numero al azar, y otorga el siguiente quantum al proceso que tenga el boleto ganador.

Esquemas híbridos:

Algoritmo por cola dentro de FB

Al introducir varias colas, se abre la posibilidad de que cada una de ellas siga un esquema diferente para elegir cual de sus procesos esta a la cabeza.

Planificación de hilos

Hay dos clases principales de hilo:

• Los hilos de usuario
• Hilos verdes

Hay tres modelos principales de mapeo:

Uno a uno: cada hilo es ejecutado como un proceso ligero; podría dar la impresión de que este esquema desperdicia la principal característica de los hilos, que es una mayor sencillez y rapidez de inicialización que los procesos

Muchos a uno: muchos hilos son agrupados en un solo proceso. Los hilos verdes entran en este supuesto.

Muchos a muchos: este mecanismo permite que hayan hilos de ambos modelos, permite hilos unidos y de hilos no unidos .

Los hilos POSIX

Hay dos enfoques respecto a la contención que deben tener los hilos, esto es en el momento en que un proceso separa su ejecución en dos hilos.

• Ámbito de contención de proceso: una respuesta es que todos los hilos deben ser atendidos sin exceder el tiempo que seria asignado a un solo proceso.
• Ámbito de contención de sistema: este ámbito es cuando, en contraposición, cada hilo es visto por el planificador como un proceso independiente.

Planificación de multiprocesadores

Para trabajar en multiprocesadores, puede mantenerse una sola lista de procesos e ir despachándolos a cada una de los procesadores como unidades de ejecución equivalentes e idénticas, o pueden mantenerse listas separadas de procesos.

Afinidad de procesador 

En un entorno multiprocesador, después de que un proceso se ejecutó por cierto tiempo, tendrá parte importante de sus datos copiados en el caché del procesador en el que fue ejecutado.

Balanceo de cargas

En un sistema multiprocesador, la situación ideal es que todos los procesadores estén despachando trabajos a 100% de su capacidad. Sin embargo, ante una definición tan rígida, la realidad es que siempre habrá uno o mas procesadores con menos del 100% de carga, o uno o mas procesadores con procesos encolados y a la espera. 

Hay dos estrategias primarias de balanceo: por un lado, la migración activa o migración por empuje, y la migración pasiva o migración por jalón.

Colas de procesos ¿Una o varias?

En los puntos relativos al multiprocesamiento hasta ahora abordados se parte del supuesto que hay una cola de procesos listos por cada procesador.

Procesadores con soporte a hilos hardware

El termino de hilos como abstracción general de algo que se ejecuta con mayor frecuencia y dentro de un mismo proceso puede llevar a una confusión, dado que en esta sección se tocan dos temas relacionados.

Tiempo real

Todos los esquemas de manejo de tiempo hasta este momento se han enfocado a repartir el tiempo disponible entre todos los procesos que requieren atención. Es necesario también abordar los procesos que requieren garantías de tiempo: procesos que para poder ejecutarse deben garantizar el haber tenido determinado tiempo de proceso antes de un tiempo limite.

Tiempo real, duro y suave

Los sistemas en que el tiempo máximo es garantizable son conocidos como tiempo real duro. Para solventar necesidades cómo las expresadas en sistemas de uso general, el tiempo real suave sigue requiriendo que los procesos críticos reciban un trato prioritario por encima de los procesos comunes. 

Un esquema de tiempo real suave puede implementarse mediante un esquema similar al de la retroalimentación multinivel, con las siguientes particularidades:

• La cola de tiempo real recibe prioridad sobre todas las demás colas.
• La prioridad de un proceso de tiempo real no se degrada conforme se ejecuta rápidamente.
• La prioridad de los demás procesos nunca llegan a subir al nivel de tiempo real por un proceso automático.
• La latencia de despacho debe de ser mínima.

Infografía