1. Tasa de Respuesta mas Alta HRN, highest-response-ratio-next
1.1. Corrige algunas deficiencias de SJF, particularmente el retraso excesivo de trabajos largos y el favoritismo excesivo para los trabajos cortos.
1.2. HRN es un disciplina de planificación no apropiativa en la cual la prioridad de cada proceso no sólo se calcula en función del tiempo de servicio, sino también del tiempo que ha esperado para ser atendido.
1.3. Cuando un trabajo obtiene el procesador, se ejecuta hasta terminar. Las prioridades dinámicas en HRN se calculan de acuerdo con la siguiente expresión:
1.3.1. prioridad = (tiempo de espera + tiempo de servicio) / tiempo de servicio
1.3.1.1. Como el tiempo de servicio aparece en el denominador, los procesos cortos tendrán preferencia. Pero como el tiempo de espera aparece en el numerador, los procesos largos que han esperado también tendrán un trato favorable.
2. Tiempo restante más corto primero (SRT).
2.1. Es apropiativa, en ella el proceso con el tiempo estimado de ejecución menor para llegar a su terminación es el siguiente en ser ejecutado, incluyendo las nuevas llegadas.
2.2. En SRT, un proceso en ejecución puede ser apropiado por un nuevo proceso con n tiempo estimado de ejecución menor.
2.3. La SRT tiene una sobrecarga mayor que la SJF. Debe mantener un registro del tiempo de servicio transcurrido del trabajo en ejecución y debe controlar las apropiaciones ocasionales.
3. Siguiente con Relación de Respuesta Máxima (HRN)
3.1. Corrige algunas de las debilidades del SJF, tales como el exceso de perjuicio hacia los procesos (trabajos) largos y el exceso de favoritismo hacia los nuevos trabajos cortos. Es una disciplina no apropiativa.
3.2. La prioridad de cada proceso está en función no sólo del tiempo de servicio del trabajo, sino que también influye la cantidad de tiempo que el trabajo ha estado esperando ser servido.
3.3. Cuando un proceso ha obtenido la cpu, corre hasta terminar.
3.4. Las prioridades, que son dinámicas, se calculan según la siguiente fórmula, donde:
3.4.1. pr es la “prioridad”, te es el “tiempo de espera” y ts es el “tiempo de servicio”:
4. Prioridad al Tiempo Restante más Corto (SRTF, Short Remaining Time First).
4.1. Se penalizan las ráfagas largas (como en SJF). Un punto débil de este algoritmo se evidencia cuando una ráfaga muy corta suspende a otra un poco más larga, siendo más largo la ejecución en este orden al ser preciso un cambio adicional de proceso y la ejecución del código del planificador.
4.1.1. Es la contraparte apropiativa del SJF.
4.1.2. Es útil en sistemas de tiempo compartido.
4.1.3. El proceso con el tiempo estimado de ejecución menor para …nalizar es el siguiente en ser ejecutado.
4.2. Un proceso en ejecución puede ser apropiado por un nuevo proceso con un tiempo estimado de ejecución menor. Tiene mayor sobrecarga que la planificación SJF. Debe mantener un registro del tiempo de servicio transcurrido del proceso en ejecución, lo que aumenta la sobrecarga.
4.2.1. Los trabajos largos tienen un promedio y una varianza de los tiempos de espera aún mayor que en SJF.
4.2.2. La apropiación de un proceso a punto de terminar por otro de menor duración recién llegado podría significar un mayor tiempo de cambio de contexto (administración del procesador) que el tiempo de finalización del primero.
4.3. Al diseñarse los Sistemas Operativos se debe considerar cuidadosamente la sobrecarga de los mecanismos de administración de recursos comparándola con los beneficios esperados.
5. Prioridad al más corto (SJF, Short Job First).
5.1. es NO apropiativa y en ella el trabajo o proceso con tiempo estimado de ejecución hasta terminación más corto, es el siguiente en ser ejecutado.
5.2. El SJF reduce el tiempo de espera de los procesos, sin embargo, tiene una varianza mayor (es decir, es menos predecible) que en FIFO, sobre todo para los trabajos largos.
5.3. SJF favorece a los procesos cortos a costa de los procesos largos. Además, selecciona los trabajos que serán atendidos y que dejarán el sistema lo antes posible
5.3.1. Es una disciplina no apropiativa y por lo tanto no recomendable en ambientes de tiempo compartido.
5.3.2. El proceso en espera con el menor tiempo estimado de ejecución hasta su terminación es el siguiente en ejecutarse.
5.3.3. Los tiempos promedio de espera son menores que con “FIFO”.
5.3.4. Los tiempos de espera son menos predecibles que en “FIFO”.
5.3.5. Favorece a los procesos cortos en detrimento de los largos.
5.3.6. Tiende a reducir el número de procesos en espera y el número de procesos que esperan detrás de procesos largos.
5.3.7. Requiere un conocimiento preciso del tiempo de ejecución de un proceso, lo que generalmente se desconoce.
5.3.8. Se pueden estimar los tiempos en base a series de valores anteriores.
6. Primero en llegar - Primero en Salir (FIFO).
6.1. Los procedimientos son despachados de acuerdo al orden de llegada a la cola de listos. Una vez que un proceso tiene el CPU, se ejecuta hasta su terminación.
6.2. Esta planificación es No apropiativa; es justa en el sentido formal, pero algo injusta porque los grandes procesos hacen esperar a trabajos pequeños y, los trabajos sin importancia hacen esperar a los trabajos importantes.
6.3. La Planificación FIFO ofrece una varianza en tiempo de respuesta relativamente pequeña y es, por tanto, más predecible que otros esquemas; no es un esquema útil en la planificación de procesos interactivos porque no garantiza buenos tiempos de respuesta
6.3.1. Se reemplazan las páginas de la cabeza y se agregan al final.
6.4. Una vez que el proceso obtiene la cpu, se ejecuta hasta terminar, ya que es una disciplina “no apropiativa”. Puede ocasionar que procesos largos hagan esperar a procesos cortos y que procesos no importantes hagan esperar a procesos importantes.
6.4.1. Suele utilizarse integrado a otros esquemas, por ejemplo, de la siguiente manera:
6.4.1.1. Los procesos se despachan con algún esquema de prioridad.
6.4.1.2. Los procesos con igual prioridad se despachan “FIFO”.
7. Comportamiento
7.1. Se pretende garantizar al usuario cierta prestación del sistema y tratar de cumplirla.
7.2. Si en un sistema tenemos 'n' usuarios lo normal será garantizar a cada uno de ellos al menos 1/n de la potencia del procesador. Para ello necesitamos del tiempo consumido por el procesador y el tiempo que lleva el proceso en el sistema.
7.3. La cantidad de procesador que tiene derecho a consumir el proceso será el cociente entre el tiempo que lleva en el sistema entre el número de procesos que hay en el sistema.
7.4. A esa cantidad se le puede asociar una prioridad que vendrá dada como el cociente entre tiempo de procesador que ha consumido y el tiempo que se le prometió (el tiempo que tiene derecho a consumir).
7.4.1. De tal modo que si esa proporción es de 0'5 significa que tan sólo ha consumido la mitad del tiempo prometido pero si es de 2 quiere decir que ha consumido más de lo debido, justamente el doble
8. Selfish round robin (SRR)
8.1. Es variante del Round Robin (RR)
8.2. En este esquema los procesos que entran al sistema se colocan primero en una lista de espera hasta que su prioridad alcanza el nivel de proceso para la lista de activos.
8.3. Mientras un proceso está en la lista de espera, su prioridad aumenta en una relación a; cuando un proceso entra a la lista de activos su prioridad se incrementa en una relación
8.3.1. b. Tamaño del cuanto.
9. Round Robin (RR)
9.1. Es efectivo en un ambiente de tiempo compartido en el cual el sistema necesita garantizar un tiempo de respuesta razonable para los usuarios interactivos.
9.2. La sobre carga de la apropiación se mantiene baja mediante eficientes mecanismos de cambio de contexto y proporcionado suficiente memoria para que los procesos residan en ella al mismo tiempo.
10. Siguiente con relación de respuesta máxima (HRT).
10.1. Corrige algunas de las debilidades de SJF, en especial el favoritismo por los tamaños pequeños.
10.2. La HRT es una disciplina de planificación NO apropiativa en la cual la prioridad de cada trabajo está en función, no sólo del tiempo de servicio del trabajo, sino del tiempo que un proceso ha estado esperando a ser servido, Una vez que un trabajo obtiene el CPU, se ejecuta hasta su terminación.
11. Plazo Fijo.
11.1. Ciertos trabajos se planifican para ser terminados en un periodo específico
11.1.1. Estos trabajos tienen un alto valor si se entregan a tiempo y pueden carecer de valor si se entregan después del límite.
11.1.2. La planificación a plazo fijo es compleja por muchas razones:
11.1.2.1. Los usuarios deben proporcionar por adelantado y en forma precisa las necesidades de recursos de su trabajo. Tal información rara vez está disponible.
11.1.2.2. El sistema debe ejecutar el programa de plazo fijo sin una severa degradación de servicio para los otros usuarios.
11.1.2.3. El sistema debe planificar cuidadosamente las necesidades de recursos permitiendo un libre tránsito del plazo fijo. Esto puede ser difícil debido a la llegada de programas nuevos con demandas impredecibles.
11.1.2.4. Si se activan muchos trabajos de plazo fijo, la planificación puede llegar a ser tan compleja que necesite métodos de optimización sofisticados para asegurar que el plazo fijo se cumpla.
11.1.2.5. El manejo intenso de recursos requeridos por la planificación de plazo fijo puede generar una sobrecarga sustancial.
12. Medidas para evaluarlas.
12.1. Porcentaje de utilización de la CPU por procesos de usuario
12.1.1. La CPU es un recurso caro que necesita ser explotado, los valores reales suelen estar entre un 40% y un 90%.
12.2. Rendimiento (throughput)
12.2.1. nº de ráfagas por unidad de tiempo. (Se define una ráfaga como el período de tiempo en que un proceso necesita la CPU)
12.2.1.1. Un proceso, durante su vida, alterna ráfagas con bloqueos. Por extensión, también se define como el nº de trabajos por unidad de tiempo.
12.3. Tiempo de espera (E)
12.3.1. Tiempo que una ráfaga ha permanecido en estado listo.
12.4. Tiempo de finalización (F)
12.4.1. Tiempo transcurrido desde que una ráfaga comienza a existir hasta que finaliza.
12.4.1.1. F = E + t (t = tiempo de CPU de la ráfaga).
12.5. Penalización (P)
12.5.1. Es una medida adimensional que se puede aplicar homogéneamente a las ráfagas independientemente de su longitud.
12.5.1.1. P = E + t / t = F / t
13. En general, hay que maximizar los dos primeros parámetros y minimizar los tres últimos.
13.1. El dedicar más tiempo de CPU a los usuarios se hace a costa de llamar menos al algoritmo de planificación (menos cambios de proceso), y de simplificarlo. Esto provoca que la CPU se reparta menos equitativamente entre los procesos, en detrimento de los últimos tres parámetros.
13.1.1. En los sistemas por lotes suele primar el rendimiento del sistema, mientras que en los sistemas interactivos es preferible minimizar, por ejemplo, el tiempo de espera.