Programación de CPU de trabajo más corto primero con tiempo de ráfaga previsto – Part 1

Requisito previo: programación de CPU , SJF: conjunto 1 (no preventivo) , conjunto 2 (principal)

El trabajo más corto primero (SJF) es un algoritmo de programación óptimo, ya que brinda un rendimiento máximo y un tiempo de espera promedio mínimo (WT) y un tiempo de respuesta (TAT), pero no es prácticamente implementable porque el tiempo de ráfaga de un proceso no se puede predecir en ventaja.

Es posible que no sepamos la duración de la próxima ráfaga de CPU, pero podemos predecir su valor. Esperamos que la próxima ráfaga de CPU sea similar en longitud a las anteriores. Al calcular una aproximación de la duración de la siguiente ráfaga de CPU, podemos elegir el proceso con la ráfaga de CPU prevista más corta.

Hay dos métodos por los cuales podemos predecir el tiempo de ráfaga del proceso:

1. Método estático: podemos predecir el tiempo de ráfaga por dos factores:

• Tamaño del proceso:
  digamos que tenemos un proceso P _antiguo con un tamaño de 200 KB que ya se ejecutó y su tiempo de ráfaga es de 20 unidades de tiempo, ahora digamos que tenemos un nuevo proceso P _nuevo con un tamaño de 201 KB que aún no se ha ejecutado.
  Tomamos el tiempo de ráfaga del proceso P _antiguo ya ejecutado, que es casi del mismo tamaño que el del proceso nuevo, como el tiempo de ráfaga del proceso nuevo P _nuevo .
• Tipo de proceso:
  podemos predecir el tiempo de ráfaga según el tipo de proceso. El proceso del sistema operativo (como programador, despachador, segmentación, fragmentación) es más rápido que el proceso del usuario (juegos, software de aplicación). El tiempo de ráfaga para cualquier proceso de sistema operativo nuevo se puede predecir a partir de cualquier proceso de sistema operativo antiguo de tipo similar y lo mismo para el proceso de usuario.

Nota: el método estático para la predicción del tiempo de ráfaga no es fiable, ya que no siempre se predice correctamente.

2. Método dinámico: sea ti el tiempo de ráfaga real del i _– ^ésimo proceso y Τ _n+1 el tiempo de ráfaga predicho para el n+1 ^-ésimo proceso.

• Promedio simple – Dados n procesos ( P ₁ , P ₂ … P _n )

  Τn+1 = 1/n(Σi=1 to n ti)

• Promedio exponencial (Envejecimiento) –

  Τn+1 = αtn + (1 - α)Τn

  donde α = es el factor de suavizado y 0 <= α <= 1 ,

  t _n = tiempo de ráfaga real del n ^ésimo proceso,
  Τ _n = tiempo de ráfaga previsto del n ^ésimo proceso.

  Termino general,

  αtn + (1 - α)αtn-1 + (1 - α)2αtn-2...+ (1 - α)jαtn-j...+ (1 - α)n+1Τ0 

  Τ ₀ es un promedio constante o general del sistema.

Factor de suavizado (α) – Controla el peso relativo de la historia reciente y pasada en nuestra predicción.

• Si α = 0, Τ ⁿ⁺¹ = Τ ⁿ , es decir, no hay cambio en el valor del tiempo de ráfaga inicial previsto.
• Si α = 1, Τ ⁿ⁺¹ = t ⁿ , es decir, el tiempo de ráfaga previsto del nuevo proceso siempre cambiará de acuerdo con el tiempo de ráfaga real del proceso n ^-ésimo .
• Si α = 1/2, la historia reciente y pasada tienen el mismo peso.

Ejemplo:
calcule el promedio exponencial con T1 = 10, α = 0,5 y el algoritmo es SJF con ejecuciones anteriores como 8, 7, 4, 16.
(a) 9
(b) 8
(c) 7,5
(d) Ninguno

Explicación:
Inicialmente T1 = 10 y α = 0.5 y los tiempos de ejecución dados son 8, 7, 4, 16 ya que es el trabajo más corto primero,
por lo que el orden posible en el que estos procesos servirían sería 4, 7, 8, 16 ya que SJF es una técnica no preventiva.
Entonces, usando la fórmula: T2 = α*t1 + (1-α)T1
tenemos,
T2 = 0.5*4 + 0.5*10 = 7, aquí t1 = 4 y T1 = 10
T3 = 0.5*7 + 0.5*7 = 7, aquí t2 = 7 y T2 = 7
T4 = 0,5*8 + 0,5*7 = 7,5, aquí t3 = 8 y T3 = 7
Entonces, la predicción futura para el cuarto proceso será T4 = 7,5, que es la opción (c) .

Este artículo es una contribución de Yash Singla . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.