Programación de listas en el sistema operativo

Requisito previo: programación de CPU

La programación de listas, también conocida como programación basada en listas de prioridades, es una técnica de programación en la que se crea una lista ordenada de procesos asignándoles algunas prioridades.

Entonces, básicamente lo que sucede es que se hace una lista de procesos que están listos para ser ejecutados en un punto dado. Y luego, dependiendo de la disponibilidad de los procesadores, es decir, si están libres u ocupados, si los procesadores están libres, seleccionan los procesos y los ejecutan.

Ahora entendamos la programación de lista usando un ejemplo.

Ejemplo:
Supongamos que tenemos 7 procesos P1, P2, P3, P4, P5, P6, P7 tales que –

1. P3 depende de P1 y P2 (P3 puede comenzar su ejecución solo cuando P1 y P2 completan su ejecución).
2. P4 depende de P3 y P6 (P4 puede comenzar su ejecución solo cuando tanto P3 como P6 completan su ejecución).
3. P6 depende de P5.

Las dependencias se muestran a continuación en la figura.

Supongamos que tenemos una restricción de dos procesadores y tenemos ambos procesadores libres.
Dado que P1, P2, P5, P7 son independientes, supongamos que inicialmente están esperando en la lista lista y listos para la ejecución.

Ejecución paso a paso de los procesos:

1. Solo tenemos dos procesadores libres, así que vamos a ejecutar primero P1 y P2.
2. P1 y P2 salen de la lista de preparados y P3 entra en la lista de preparados. Entonces P3, P5, P7 están en la lista lista ahora
3. Supongamos que de los 3 procesos presentes en la cola de procesos listos, P3 y P5 se ejecutan a continuación, por lo que P3 y P5 salen de la lista de procesos listos y P6 entra en la lista de procesos listos. P4 no aparecerá en la lista de listos porque también depende de P6, que aún no se ha ejecutado.
4. P6 y P7 están en lista lista ahora. Entonces P6 y P7 se ejecutan a continuación.
5. P6 y P7 salen de la lista lista y P4 entra en la lista lista y finalmente P4 se ejecuta y todos los procesos terminan.

La lista lista se muestra a continuación en cada paso que se muestra en la figura:

Entonces puede ver que después de 4 unidades de tiempo, se ejecutan todos los procesos. Pero este tiempo puede variar según el mecanismo de programación que utilice el sistema operativo.

La explicación que muestra el tiempo de ejecución depende de los algoritmos de programación utilizados.

1. Considere el caso cuando el mismo proceso comienza con la ejecución de P5 y P7 primero esta vez en lugar de P1 y P2.
2. Después de eso, P5 y P7 salen de la lista lista y P6 entra en la lista lista.
3. P1, P2, P6 están en lista lista ahora. Deje que P2 y P6 se ​​ejecuten.
4. P2 y P6 salen de la lista de listos. P1 se ejecuta entonces.
5. P1 sale de la lista de listos y P3 viene de la lista de listos y luego se ejecuta P3.
6. Finalmente se ejecuta P4 y se ejecutan todos los procesos.

La lista lista para este proceso se muestra a continuación:

Así que puedes ver esta vez que se toman 5 unidades de tiempo si cambiamos el orden de los procesos en los que se ejecutan.

Las prioridades se determinan estáticamente antes de que comience el proceso de programación. El primer paso elige el proceso con la prioridad más alta, el segundo paso selecciona el mejor recurso posible. Algunas de las estrategias de programación que se pueden utilizar son:

• Algoritmo de ruta más larga
• Tiempo de procesamiento más largo
• Método del camino crítico

El objetivo del algoritmo es maximizar la utilización de la CPU y minimizar el retraso. Entonces, cualquier algoritmo de programación que ayude a lograr esto se puede usar según los procesos.