Primer plano-fondo generalizado en Scheduling

Requisito previo: programación de primer plano y segundo plano La política de programación de
primer plano y segundo plano generalizada en la programación, también conocida como servicios mínimos alcanzados (LAS) , se utiliza principalmente en sistemas donde las estimaciones de tamaño no están disponibles. Calcula el tiempo de servicio restante del trabajo en función del servicio recibido hasta el momento. Si hay n tales trabajos, entonces se sirven simultáneamente, es decir, cada uno de ellos se sirve a razón de 1/n.

El primer plano generalizado da servicio al trabajo en el sistema que ha recibido la menor cantidad de servicio. En caso de empate, los trabajos que hayan recibido el menor servicio comparten procesador en el modo de uso compartido de procesador. Un trabajo recién llegado siempre reemplaza el trabajo actualmente en servicio y retiene el procesador hasta que se va, o hasta que ocurre la próxima llegada, o hasta que obtiene una cantidad de servicio igual a la recibida por el trabajo reemplazado a la llegada, lo que ocurra primero.

Trabajo de primer plano-fondo:
un trabajo ingresa al primer estado (o de mayor prioridad) al llegar a la cola. La prioridad de los trabajos depende de su hora de llegada a ese estado en particular en forma de First Come First Serve. Los trabajos se sirven uno a la vez sin interrupción durante un período de tiempo q. Después de que el servidor haya completado la solicitud de servicio del trabajo en cierto estado, se selecciona el trabajo del estado de prioridad más alto (no vacío) para el servicio. Si el trabajo no sale de la cola durante su tiempo en el k- _ésimo estado, se mueve al estado k + 1, que tiene menor prioridad, y espera hasta que se sirve en ese estado. En el estado n- _ésimo y final, los trabajos se cumplen solo si no hay trabajos en otros estados. En ese estado final, se sirven hasta que salen del sistema.

Teoremas en primer plano-fondo generalizado (FB):

Notaciones:

• p : se refiere a la política
• X : Requerimiento de servicio con media E[X] y varianza var(X)
• SRPT : Tiempo de procesamiento restante más corto
• LAS : Otra representación para FB
• E[Tl] : E[T _LAS ]
• E[Ts] : E[T _SPRT ]

Teorema-1:

Esta distribución determinista constituye el peor de los casos donde se alcanza el límite superior del tiempo medio de respuesta de FB, mientras que el número de distribuciones conduce al límite inferior. Cuando la carga llega a 1, el tiempo medio de respuesta crece hasta el infinito.

Teorema-2:
Cuando p > 1, todos los trabajos de tamaño x < x _p , tal que p _Xp = 1 tienen respuesta finita bajo FB.

Este teorema establece un parámetro para garantizar la equidad en la programación. La métrica utilizada para evaluar la equidad es la desaceleración condicional media E[S(x)]. Se dice que una política es justa si su ralentización condicional media para todos los tamaños de trabajo es menor que la métrica correspondiente en PS (Procesador – Compartir). Sin embargo, cuando la distribución del tamaño del flujo tiene un segundo momento finito, algunos trabajos grandes (aunque no el trabajo más grande) siempre experimentan una mayor desaceleración en FB.

Teorema-3:
Para todos los tamaños de trabajo x y con carga p<1

This theorem depicts relation between mean condition response time of SRPT and FB.

Características del primer plano generalizado – fondo:

1. LAS otorga prioridad de espacio de búfer a los primeros paquetes TCP de cada flujo, lo que significa que estos paquetes no deberían experimentar ninguna pérdida.
2. Un nuevo flujo TCP comienza en lo que se conoce como «inicio lento», donde su ventana de congestión se inicializa a un valor muy pequeño y luego se duplica después de cada ronda de transmisión. Dado que, en FB, los primeros paquetes de flujo experimentarán un retraso en la cola nulo o insignificante, la duración de la ronda será más corta en FB y la ventana de congestión aumentará más rápido.
3. El comportamiento del enrutador FB es similar al de la cola FB, siempre que el paquete a ser atendido llegue al enrutador antes del instante de tiempo, donde es seleccionado por el programador.
4. FB se puede modificar para obtener un valor de umbral para los paquetes TCP, donde la prioridad de servicio asignada a cualquier paquete no puede tener un valor mayor que el umbral.
5. FB minimiza/maximiza la distribución de longitud de cola bajo distribuciones DFR/IFR y, por lo tanto, también EQ de longitud de cola media y EV de tiempo de respuesta medio.
6. Para las distribuciones de servicios deterministas, FB tiene tiempos de respuesta medios que son tan grandes como sea posible bajo cualquier política de conservación de trabajo
7. Para las distribuciones de servicio de cola ligera, FB tiene un comportamiento de cola que coincide con la cola más pesada posible según las políticas de conservación del trabajo.