Sistemas operativos modernos

guen nos ocuparemos de los sistemas interactivos y en tiempo real. Vale la pena señalar que al­ gunos algoritmos se usan en sistemas tanto por lotes como interactivos; los estudiaremos más adelante. Aquí nos concentraremos en algoritmos que sólo son apropiados para sistemas por lotes. Primero en llegar, primero en ser atendido Tal vez el algoritmo de calendarización más sencillo sea el de primero en llegar, primero en ser atendido, que es no expropiativo. Aquí, la CPU se asigna a los procesos en el orden en que la solicitan. De manera básica, hay una sola cola de procesos listos. Cuando el primer tra­ bajo entra en el sistema en la mañana, se le inicia de inmediato y se le permite ejecutar todo el tiempo que desee. A medida que llegan otros trabajos, se les coloca al final de la cola. Cuan­ do se bloquea el proceso en ejecución, se ejecuta el primer proceso de la cola. Si un proceso bloqueado vuelve a estar listo, se le coloca al final de la cola como si fuera un trabajo recién llegado. La gran ventaja de este algoritmo es que es fácil de entender y de programar. También es equitativo en el mismo sentido en que es equitativo entregar el reducido número de entradas para un concierto o evento deportivo a las personas que estén dispuestas a hacer fila desde las 2 A.M. Con este algoritmo, una sola lista enlazada lleva el control de todos los procesos listos. Escoger el proceso a ejecutar sólo requiere sacar un elemento del inicio de la cola. La adición de un nuevo trabajo o de un proceso desbloqueado sólo requiere anexarlo al final de la cola. Nada más sencillo. Lamentablemente, esta política también tiene una grave desventaja. Supongamos que hay un proceso dedicado al cómputo que se ejecuta durante un segundo a la vez y muchos proce­ sos dedicados a la E/S que casi no consumen tiempo de CPU pero que deben realizar 1000 lec­ turas de disco para terminar. El proceso dedicado al cómputo se ejecuta durante 1 s, y luego lee un bloque de disco. Ahora se ejecutan todos los procesos dedicados a la E/S e inician una lec­ tura de disco. Cuando el proceso dedicado al cómputo recibe su bloque de disco, se ejecuta du­ rante otro segundo, seguido de lodos los procesos dedicados a la E/S en rápida sucesión. El resultado neto es que cada proceso dedicado a la E/S leerá un bloque cada segundo y tardará 1000 s en terminar. Con un algoritmo de calendarización que expropiara el proceso dedicado a la CPU cada 10 ms, los procesos dedicados a la E/S terminarían en 10 s en lugar de 1000 s, sin hacer muy lenta la ejecución del proceso dedicado al cómputo. Trabajo más corto primero Ahora examinemos otro algoritmo no expropiativo para lotes que supone un conocimiento anticipado de los tiempos de ejecución. Por ejemplo, en una compañía de seguros es posible predecir con gran exactitud cuánto tardará el procesamiento de un lote de 1000 reclamaciones, pues se realizan trabajos similares todos los días. Si hay varios trabajos de la misma importan­ cia en la cola de entfada, el calendarizador escoge el trabajo más corto primero (vea la figura 2-39). Ahí tenemos cuatro trabajos, A , B , C y D, con tiempos de ejecución de 8 , 4, 4 y 4 minutos, respectivamente. Si los ejecutamos en ese orden, el tiempo de retomo de A será 8