Algoritmos de Planificación: FCFS, SJF, Round Robin y Multicola en Informática

Algoritmos de Planificación: FCFS

DIA 4 ALGORITMOS DE PLANIFICACIÓN: PLANIFICACION FCFS Se asigna primero la CPU al proceso que primero la solicite, según la orden de llegada. Se gestiona fácilmente con una cola FIFO, cuando un proceso entra en la cola de "listos", su PCB se coloca al final de la cola. Cuando la CPU queda libre, se asigna al proceso que esté al principio de la cola.

Tiempo de Retorno: representa el tiempo total que el proceso pasa en el sistema, desde que llega hasta que termina. Es no apropiativo, una vez que la CPU ha sido asignada a un proceso, no puede ser desalojado por otro proceso, debe esperar a que se libere (incluso si otro de mayor prioridad llega al sistema). Esto es problemático ya que cuando un proceso requiere mucho tiempo de CPU, va a generar un mal uso y tiempos de espera largos, mientras otros procesos más rápidos permanecen en la cola. Este algoritmo no es cooperativo en el sentido estricto de la planificación. En la planificación cooperativa, un proceso cede voluntariamente la CPU.

Algoritmos de Planificación: SJF

ALGORITMOS DE PLANIFICACIÓN: PLANIFICACION SJF Este asocia a cada proceso con la próxima ráfaga de CPU más corta para ser ejecutado. Si las ráfagas de dos procesos son iguales, se usa la FCFS para romper el empate. Aunque es óptimo por minimizar el tiempo de espera, no se puede implementar en la planificación de la CPU a corto plazo ya que no hay forma de conocer la duración de la siguiente ráfaga de CPU. Podemos predecir el valor de la siguiente ráfaga de CPU basada en las ráfagas anteriores utilizando un promedio exponencial.

La siguiente ráfaga de CPU del proceso que acaba de llegar puede ser más corta que lo que quede del proceso que está en ejecución. Un SJF Apropiativo detendrá el proceso actualmente en ejecución y le otorga la CPU al nuevo (mejora los tiempos de respuesta), mientras que un SJF No Apropiativo permitirá que dicho proceso termine su ráfaga de CPU.

Algoritmos de Planificación: Planificación por Prioridades

ALGORITMOS DE PLANIFICACIÓN: PLANIFICACIÓN X PRIORIDADES Cada proceso tiene asociada una prioridad y la CPU se asigna al proceso con prioridad más alta. Los procesos con la misma prioridad se planifican en orden FCFS. Las prioridades se indican mediante un rango de números fijos.

Cuando un proceso llega a la cola de procesos preparados, su prioridad se compara con la prioridad del proceso actualmente en ejecución. Uno por prioridades apropiativo desaloja de la CPU al proceso actual si la prioridad del proceso que acaba de llegar es mayor. Uno por prioridades no apropiativo simplemente pondrá el nuevo proceso en el lugar correspondiente según su prioridad en la cola de "listos".

Un problema de estos algoritmos es la muerte por inanición, ocurre cuando deja a procesos de baja prioridad esperando indefinidamente porque llegan procesos con mayor prioridad. Una solución es aplicar mecanismos de envejecimiento, que consiste en aumentar gradualmente la prioridad de los procesos que estén esperando en el sistema durante mucho tiempo.

Algoritmos de Planificación: Round Robin

ALGORITMOS DE PLANIFICACIÓN: ROUND ROBIN Es apropiativo, ya que los procesos pueden ser desalojados de la CPU Este algoritmo está diseñado para sistemas de tiempo compartido, donde se define una pequeña unidad de tiempo a cada proceso, denominada quantum de tiempo.

Se genera un quantum de tiempo y se le da a cada proceso un máximo de tiempo en el cual puede utilizar la CPU, al finalizar ese quantum es desalojado y se coloca al final de la cola (del tipo FCFS) y también lo hace cuando un proceso abandona por su propia voluntad (por terminar antes de agotar el quantum). Si un proceso recibe una interrupción externa, al terminar vuelve a ejecutarse ese proceso si su quantum de tiempo no ha terminado, no vuelve al final de la cola.

El problema es que es "injusto", porque los procesos de E/S pueden usar menos tiempo de CPU que otro tipo de procesos y estos se ven en desventaja. Para esto surgió una variación llamado Round Robin con doble cola, en el cual tenemos dos colas, una llamada activa y otra pasiva, cuando arrancamos le damos el mismo quantum de tiempo a los procesos, pero se le otorga un quantum largo. Por ejemplo, suponemos que entran 3 procesos A, B Y C a la cola de activos, con 40 ms de quantum c/u, el proceso A utiliza 5 ms y sale, vuelve al final de la cola de activos y se ejecuta el proceso B que es el que sigue, este usa los 40 ms y pasa a la cola de pasivos, entonces ahora en la cola de activos solamente quedan A y C, hasta que agoten sus quantums. Cuando todos están en la cola de pasivos, se invierten las colas, la cola activa que ahora está vacía pasa a ser la pasiva, y la cola pasiva que está llena pasa a ser la activa. Esto nos garantiza que todos los distintos tipos procesos tienen el mismo tiempo de uso de CPU.

Round Robin con Retroalimentación

ROUND ROBIN CON RETROALIMENTACION: un esquema de colas multilevel feedback, utiliza múltiples colas con diferentes quantums para manejar los procesos en función de su comportamiento: los que devuelven la CPU y aquellos que consumen más tiempo (dar mayor prioridad a los procesos interactivos que necesitan menos tiempo)

Algoritmos de Planificación: Planificación Multicola

ALGORITMOS DE PLANIFICACIÓN: PLANIFICACION MULTICOLA Los procesos se dividen en diferentes colas según criterios predefinidos y estan asignados permanentemente a una cola y cada una tiene su propio algoritmo de planificación (planificación intracola).

Además, debe definirse una planificación entre las colas (intercola), la cual suele implementarse como una planificación apropiativa y prioridad fija.

Por ejemplo, un algoritmo de planificación mediante colas multinivel con 3 colas, según su prioridad:

1. Procesos del sistema
2. Procesos interactivos
3. Procesos de edición interactivos

Cada cola tiene prioridad absoluta sobre las colas de prioridad más baja. Entonces, ningún proceso de una prioridad más baja puede ejecutarse hasta que se vacíe la cola de los procesos con mayor prioridad. Si un proceso de menor prioridad se está ejecutando y llega un proceso a la cola de mayor prioridad, el proceso en ejecución es desalojado. Otra posibilidad consiste en repartir el tiempo entre las colas. Por ejemplo, que los procesos de primer plano (interactivos) dispongan del 80 por ciento del tiempo de CPU y los de segundo plano (por lotes) el resto.

Para que no haya muerte por inanición se suele utilizar el algoritmo multicola realimentadas que permite mover un proceso de una cola a otra. Así, si un proceso está en espera en una cola de baja prioridad mucho tiempo, puede subir a una cola de mayor prioridad para poder ser ejecutado en algún momento (envejecimiento).

Planificación MultiCPU

PLANIFICACION MULTICPU Si hay disponible múltiples CPU, se puede compartir la cargade trabajo; sin embargo, el problema de la planificación se hace más complejos. Dos tipos de enfoques:

Planificación MultiCPU Asimétrico (AMP)

Asimétrico (AMP): consiste en que todas las decisiones sobre la planificación, el procesamiento de E/S y otras actividades del sistema sean gestionadas por un mismo procesador y los demás procesadores solo ejecutan código de. Se lo conoce como procesador maestro y procesadores esclavos.

Ciclo de vida de un proceso en AMP: Cuando un proceso nace, se debe definir si va a ser ejecutado en la CPU o en la GPU (se dividen). Luego va a estar la cola de listos asociada a cada una de ellas.

Planificación MultiCPU Simétrico (SMP)

Simétrico (SMP): cada uno de los procesadores se autoplanifica. Todos los procesos pueden estar en una cola común de procesos preparados, o cada procesador puede tener su propia cola privada de procesos preparados. Independientemente de esto, el planificador de cada proceso examina la cola de procesos preparados y selecciona un proceso para ejecutarlo.

Ciclo de vida de un proceso en SMP: Nace el proceso, va a la cola de listo, y por cada procesador podemos tener más de un proceso en ejecución. Tiene una enorme ventaja porque todas las PCB son iguales, por lo que un proceso puede ser asignado a cualquier CPU y puede moverse entre ellos.

Gestión de Procesos: Sincronización de Procesos

Condición de Carrera

GESTION DE PROCESOS: SINCRONIZACION DE PROCESOS CONDICION DE CARRERA En un sistema con multiprocesamiento, los procesos cooperativos comparten recursos y puede generar conflictos si varios intentan acceder al mismo tiempo. Una condición de carrera ocurre cuando dos o más procesos acceden y manipulan los mismos datos de manera concurrente, y el resultado de la ejecución depende del orden en el que se produzcan los accesos. Para evitar las condiciones de carrera, es necesario garantizar que solo un proceso pueda acceder a un recurso compartido en un momento dado y para eso debemos sincronizar los procesos.

Sección Crítica

SECCION CRITICA Cada proceso tiene un segmento de código, llamado SECCION CRITICA, en el que el proceso puede acceder y modificar recursos compartidos (como variables comunes). La característica importante es que solo un proceso a la vez puede ejecutar su sección critica. Cada proceso debe solicitar permiso para entrar en su sección crítica y quien implementa esta solicitud es la SECCION DE ENTRADA, donde el proceso intenta adquirir los permisos necesarios. La sección critica es seguida por la SECCION DE SALIDA, donde el proceso debe liberar el control del recurso compartido. El resto del código está en la SECCION RESTANTE (código que no está relacionado con la sección critica).

Cualquier solución a este problema debe satisfacer estos requisitos:

• Exclusión mutua: Si un proceso está ejecutando su sección critica, los demás procesos no pueden estar ejecutando sus secciones críticas.
• Progreso: Si ningún proceso está en su SC pero hay procesos que quieren acceder a ella, solo aquellos procesos que no estén ejecutando sus secciones restantes pueden participar, es decir procesos "libres".
• Espera limitada: Al ser un algoritmo de prioridad, puede ser que un proceso quede siempre en wait. La espera limitada evita esto.

Soluciones al Problema de la Sección Crítica

Soluciones por Software

SOLUCIONES LA PROBLEMA DE LA SECCION CRITICA SOLUCIONES POR SOFTWARE:

• Algoritmo de Peterson: La solución de Peterson se funciona con dos procesos que van alternando la ejecución de la sección crítica y la sección restante y requiere que los procesos compartan dos variables, una indica si el proceso esta listo y otra le cede el turno al otro proceso. No funciona en sistemas multihilo ya que no tiene en cuenta ejecuciones simultaneas.
• Barreras de Memoria: Herramienta para poder utilizar el algoritmo de Peterson en sistemas multihilo. Fue reemplazado por una solución por hardware.

Soluciones por Hardware

SOLUCIONES POR HARDWARE:

• Cerrojo: herramienta que protege las regiones críticas. Un proceso debe adquirir un cerrojo antes de entrar en la sección crítica y liberarlo cuando salga.
• A nivel del procesador se implementaron instrucciones, TestAndSet -para leer y modificar una variable y swap -para intercambiar el valor de dos variables que permiten que se ejecute un conjunto de operaciones en un solo ciclo.