La programación se divide básicamente en 2 categorías: la primera es la programación controlada por reloj y la otra es la programación controlada por eventos . Los algoritmos de programación controlados por reloj son aquellos algoritmos en los que las interrupciones que recibe un reloj ayudan a determinar el punto de programación y estos son FCFS , Round Robin , etc. En un algoritmo controlado por eventos, los eventos ayudan a determinar el punto de programación. El Event-Driven se divide a su vez en 3 tipos: el primero es el basado en prioridad simple , el segundo es el análisis monotónico de tasa (RMA) y el tercero es el primero en la fecha límite más temprana (EDF) .
La programación de primer plano y segundo plano se encuentra en el primer tipo de algoritmo impulsado por eventos, es decir, basado en prioridad simple. En este algoritmo se mantienen 2 listas de espera una en Primer Plano y otra en Segundo Plano. Al principio, cada proceso ingresa en la lista de primer plano para su ejecución y permanece allí durante un pequeño período de tiempo para su ejecución hasta que se alcanza el límite de tiempo límite, después de esto, si el proceso está incompleto, ese proceso ingresa en la lista de espera de fondo donde se ejecutará solo cuando la lista de primer plano esté vacía y en la lista de espera de fondo se utilice el algoritmo de programación Round Robin para ejecutar el proceso.
Entonces, de acuerdo con el procedimiento anterior, la prioridad de la lista de primer plano es más alta que la lista de fondo y el tiempo de umbral del primer plano es más corto que el de la lista de fondo. Por lo general, en el proceso de la lista de primer plano, se permite usar 2 cuantos, después de eso se enviará al fondo y, en segundo plano, el proceso obtendrá 4 cuantos para completar todo su trabajo y, si el proceso aún está incompleto, volverá al final. la lista de fondo y espera su turno para obtener 4 cuantos nuevamente y este proceso se repite hasta que el proceso completa su trabajo. Este algoritmo ayuda en aquellos casos en los que es necesario ejecutar el proceso justo después de su creación.
Funcionamiento del programador de primer plano y segundo plano:
el programador de primer plano y segundo plano sigue los siguientes pasos para programar tareas en tiempo real:
- Paso 1:
todas las tareas en tiempo real se clasifican como tareas en primer plano y en segundo plano. Las tareas en primer plano incluyen tareas periódicas y las tareas en segundo plano incluyen tareas esporádicas y aperiódicas. - Paso 2:
Las tareas en primer plano tienen la prioridad más alta y las tareas en segundo plano tienen la prioridad más baja. - Paso 3:
al programar tareas en primer plano, en todos los puntos de programación se considera la prioridad más alta. - Paso 4:
cuando las tareas en primer plano no están listas para la programación, se programan las tareas en segundo plano. - Paso 5:
entre las tareas en segundo plano, se siguen las mismas reglas de programación que en las tareas en primer plano.
Tiempo de finalización para tareas en primer plano:
como se mencionó anteriormente, las tareas en primer plano incluyen las tareas periódicas, por lo que su tiempo de finalización es el mismo que su fecha límite absoluta.
Hora de finalización de las tareas en segundo plano:
cuando todas las tareas en primer plano están programadas solo después de que se programen las tareas en segundo plano. Cuando se ejecuta cualquier tarea en primer plano, esperan tareas en segundo plano.
Sea Task T i la tarea de primer plano, y E i es la cantidad de tiempo de procesamiento requerido en cada período P i .
Por eso,
Avg. CPU utilization for Ti is Ei/Pi
Si hay n tareas periódicas (tareas en primer plano) i, e.
T1, T2, T3, ..., Tn
Luego Promedio total. Utilización de CPU para tareas en primer plano,
= (E1/P1) + (E2/P2) + ... + (En/Pn)
Por lo tanto, el promedio. el tiempo disponible para la ejecución de tareas en segundo plano en cada unidad de tiempo es,
1 - (E1/P1) + (E2/P2) + ... + (En/Pn)
Sea T b la tarea en segundo plano y E b el tiempo de procesamiento requerido, luego
el tiempo de finalización para la tarea en segundo plano (CT b ),
= Eb / ( 1 - (E1/P1) + (E2/P2) + ... + (En/Pn) )
Ejemplo:
en un sistema en tiempo real, las tareas se programan utilizando un algoritmo de programación de primer plano, T f es solo una tarea de primer plano con E f = 100 ms y P f = 200 ms, hay una tarea de fondo T b cuyo E b = 500 EM.
El tiempo de finalización de la tarea en segundo plano
CTb = Eb / (1 - Ef/Pf)
= 500 / (1 - 100/200)
= 1000 ms
Por lo tanto, la tarea en segundo plano tardará 1000 ms en completarse.
Ventajas de la programación de primer plano y segundo plano:
- Las tareas periódicas tienen la máxima prioridad.
- Se adelanta a la ejecución de tareas en curso para tareas entrantes de mayor prioridad.
Desventajas de la programación de primer plano y segundo plano:
- Las tareas de fondo pueden morir de hambre.
- A veces, la preferencia puede crear estragos.
Ejemplos:
1. Considere que tenemos 3 tareas T1, T2, T3 en primer plano y la tarea T4 en segundo plano.
| Número de tarea | ei (en ms) | pi (en ms) |
| t1 | 5 | 20 |
| t2 | 10 | 25 |
| t3 | 15 | 50 |
Calcule el tiempo de finalización para el T4 cuando su requisito de tiempo de procesamiento es de 200 ms para completarse.
Solución: La primera tarea es encontrar la suma de todas las tareas en la Frente. Entonces, obtenemos la utilización total de la CPU para tareas frontales
(e1/p1) + (e2/p2) + (e3/p3)
(5/20) + (10/25) +(15/50)
(25 + 40 + 30) / 100
95/100
La segunda tarea es restar 1 con la sumatoria. Entonces, podemos saber cuánto tiempo promedio está disponible para la tarea en segundo plano en cada unidad de tiempo
1 – (95/100)
5/100
Y por último, tenemos que dividir el eB por el valor anterior
200/(5/100)
200*100/5
20000/5
4000
Por lo tanto, el tiempo total de finalización de la tarea en segundo plano es de 4000 ms.
2. Considere 2 tareas, una está en primer plano T1 y otra está en segundo plano TB. El tiempo de finalización de la tarea en segundo plano TB es de 3000 ms y el tiempo de procesamiento requerido para TB es de 1500 ms. Calcule el tiempo de procesamiento requerido para T1 cuando p1 es 100 ms.
Solución: dado: ctB=3000 ms , eB=1500 ms , p1=100 ms
ctB = eB / ( 1 – e1 / p1 )
3000 = 1500 / ( 1 – x / 100 )
2 = 1 / ( (100 – x ) / 100 )
2 = 100 / (100 – x)
200 – 2x = 100
2x = 100
x = 50
El tiempo de proceso requerido para T1 es de 50 ms
Sobrecarga durante el cambio de contexto entre la lista de espera en primer plano y en segundo plano:
Fig: Overhead en primer plano Programación de fondo
Al principio, se ejecuta la tarea de primer plano, se produce una sobrecarga de 2 ms, como se ve claramente en la imagen. El tiempo de sobrecarga está representado por el área gris, la lista que se está ejecutando a la vez está representada por el color verde, y la lista que se adelanta y espera su turno o está inactiva está representada por el color blanco. De la figura anterior, está claro que de 2 a 52 la lista en primer plano se está ejecutando y la lista en segundo plano está esperando. Solo una lista puede ejecutar sus tareas a la vez, como en la primera ejecución de la tarea en primer plano, luego se reemplaza después de un período de tiempo particular para las tareas en segundo plano después de que se completa el período de tiempo en segundo plano, se reemplaza para el primer plano y así sucesivamente. En el estado inicial, hay una sobrecarga de 2 ms y después de eso, el primer plano comienza a funcionar (se muestra en la imagen), Está claro que el tiempo de ejecución de cada tarea en primer plano aumenta en dos tiempos de cambio de contexto (uno debido a sí mismo, es decir, de 0 a 2 ms, y el otro debido a que la tarea en segundo plano se ejecuta después de cada vez que se completa, es decir, de 52 a 54 ms). Por lo tanto, el tiempo de cambio de contexto aumenta en 4 ms porque en 1 cambio de contexto tarda 2 ms, por lo tanto, en 2 cambios de contexto tarda 4 ms. Por lo tanto, el tiempo de ejecución de la lista de primer plano aumenta y se convierte en 54 ms en lugar de 50 ms. Considere que el período (pi) para la tarea en primer plano es de 100 ms, lo que significa que después de cada 100 ms, las tareas en segundo plano se adelantan y las tareas en primer plano comienzan a ejecutarse. Tomemos un ejemplo: el tiempo de cambio de contexto aumenta en 4 ms porque en 1 cambio de contexto tarda 2 ms, por lo tanto, en 2 cambios de contexto tarda 4 ms. Por lo tanto, el tiempo de ejecución de la lista de primer plano aumenta y se convierte en 54 ms en lugar de 50 ms. Considere que el período (pi) para la tarea en primer plano es de 100 ms, lo que significa que después de cada 100 ms, las tareas en segundo plano se adelantan y las tareas en primer plano comienzan a ejecutarse. Tomemos un ejemplo: el tiempo de cambio de contexto aumenta en 4 ms porque en 1 cambio de contexto tarda 2 ms, por lo tanto, en 2 cambios de contexto tarda 4 ms. Por lo tanto, el tiempo de ejecución de la lista de primer plano aumenta y se convierte en 54 ms en lugar de 50 ms. Considere que el período (pi) para la tarea en primer plano es de 100 ms, lo que significa que después de cada 100 ms, las tareas en segundo plano se adelantan y las tareas en primer plano comienzan a ejecutarse. Tomemos un ejemplo:
Ejemplo. Considere una tarea T1 en primer plano y su e1 es 50 ms y p1 es 100 ms y una tarea T2 en segundo plano su e2 es 2000. Calcule el tiempo de finalización para tareas en segundo plano cuando la sobrecarga de cada cambio de contexto es 2 ms.
Solución: De la discusión anterior, se observa que e1 se convierte en 54 ms.
2000 / ( 1 – 54 / 100 )
2000 / ((100 – 54 ) / 100 )
200000 / 46
4347.82
Entonces, el tiempo de finalización de la tarea en segundo plano es 4347.82 ms