Sistemas operativos modernos

A4 ‘ B3 A4 ::(C3 A4 tC3 Tiempo (ms) Figura 7-12. Ejemplo de calendarización en tiempo real RMS y EDF. SOS tardan 30 ms en ejecutarse, así que cuando C termina es hora de que A se ejecute otra vez. Esta rotación continúa hasta que el sistema se queda sin trabajo en t = 70. En í = 80 fi está listo y se ejecuta. Sin embargo, en í = 90 está listo un proceso de más al­ ta prioridad, A, así que expropia a 5 y se ejecuta hasta terminar. En ese punto el sistema pue­ de escoger entre terminar B e iniciar C, así que escoge el proceso de más alta prioridad, B. 7.4.4 Calendarización de plazo más cercano primero Otro algoritmo de calendarización de tiempo real muy utilizado es el de plazo más cercano pri­ mero (EDF; Earliest Deadline First). EDF es un algoritmo dinámico que no requiere que los procesos sean periódicos, como el algoritmo de tasa monotónica. Tampoco es necesario que sea uniforme el tiempo de ejecución por ráfaga de CPU, como en RMS. Cada vez que un proceso necesita tiempo de CPU, anuncia su presencia y su plazo. El calendarizador mantiene una lista de procesos ejecutables en orden por plazo. El algoritmo ejecuta el primer proceso de la lista, el que tiene el plazo más cercano. Cada vez que un nuevos proceso está listo, el sistema verifica si su plazo se va a cumplir antes que se cumpla el del proceso que se está ejecutando. En tal caso, el nuevo proceso expropiará al actual. En la figura 7-12 se presenta un ejemplo de EDF. En un principio los tres procesos están fistos, y se ejecutan en orden según sus plazos. A debe terminar antes de t = 30, B debe termi­ nar antes de r = 40, y C debe terminar antes de t = 50, así que A tiene el plazo más cercano y por tanto se ejecuta primero. Hasta f = 90 se toman las mismas decisiones que con RMS. En í = 90, A vuelve a estar listo, y su plazo es r = 120, el mismo que tiene B. El calendarizador po­ dría escoger cualquiera de los dos, pero como en la práctica la expropiación de B implica al­ gún costo disfinto de cero, es mejor dejar que se siga ejecutando B. Para que el lector no piense que RMS y EDF siempre dan los mismos resultados, examinemos otro ejemplo que se muestra en la figura 7-13. En este ejemplo los periodos de A, fi y C son los mismos de antes, pero ahora A necesita 15 ms de tiempo de CPU en cada ráfaga, no 10 ms. La prueba de calendarizabifidad calcula una utilización de CPU de 0.5(X) + 0.375 + 0.100 = 0.975.