Sistemas operativos modernos

uno tiene derecho, que sería el tiempo desde la creación dividido entre n. Puesto que también se conoce el tiempo de CPU que ha tenido cada proceso, se puede calcular el cociente del tiem­ po de CPU consumido realmente entre el tiempo al que el proceso tiene derecho. Un cociente de 0.5 implica que el proceso sólo ha recibido la mitad de lo que debería haber recibido, y un cociente de 2.0 implica que el proceso ha recibido el doble de lo que le corresponde. El algo­ ritmo consiste entonces en ejecutar el proceso cuyo cociente es más bajo, hasta que el cocien­ te rebase al de su competidor más cercano. Calendarización por lotería Aunque hacer promesas a los usuarios y luego cumplirlas es una idea excelente, no es fácil de implementar. Sin embargo, es posible utilizar otro algoritmo para obtener resultados igual de pre­ decibles con una implementación mucho más sencilla: el de calendarización por lotería (Walds- purger y Weihl, 1994). La idea fundamental consiste en entregar a los procesos “billetes de lotería” para los dis­ tintos recursos del sistema, como el tiempo de CPU. Cada vez que se deba tomar una decisión de calendarización, se escoge un billete de lotería al azar, y el proceso que lo tiene obtiene el recurso. Si este sistema se aplica a la calendarización de CPU, el sistema podría celebrar un “sorteo” 50 veces por segundo, y el premio sería 20 milisegundos de tiempo de CPU. Parafraseando a George Orwell: “Todos los procesos son iguales, pero algunos son más iguales que otros”. Podríamos dar más billetes a los procesos más importantes para aumentar sus posibilidades de ganar. Si se emiten 100 billetes y un proceso tiene 20 de ellos, tendrá una probabilidad del 20% de ganar cada sorteo. A la larga, ese proceso recibirá aproximadamente el 20% del tiempo de CPU. En contraste con los calendarizadores por prioridad, donde es muy difícil decir qué significa en realidad tener una prioridad de 40; aquí la regla es muy clara: un proceso que fiene una fracción / d e los billetes recibirá aproximadamente una fracción/ del re­ curso en cuestión. La calendarización por lotería fiene varias propiedades interesantes. Por ejemplo, si llega un proceso nuevo y recibe cierto número de billetes, en el siguiente sorteo tendrá una probabi­ lidad de ganar proporcional al número de billetes que tenga. Dicho de otro modo, la calenda­ rización por lotería es muy sensible. Los procesos que cooperan pueden intercambiar billetes si lo desean. Por ejemplo, si un proceso cliente envía un mensaje a un proceso servidor y luego se bloquea, podría entregar to­ dos sus billetes al servidor para mejorar la probabilidad de que sea el servidor quien se ejecu­ te a confinuación. Cuando el servidor termine, devolverá los billetes al cliente para que pueda ejecutarse otra vez. De hecho, si no hay clientes, los servidores no necesitan billetes. La calendarización por lotería puede resolver problemas difíciles de manejar con otros mé­ todos. Un ejemplo es un servidor de vídeo en el que varios procesos alimentan flujos de vídeo a sus clientes, pero con tasas de cuadros disfintas. Supongamos que los procesos necesitan ví­ deo a razón de 10, 20 y 25 cuadros por segundo. Si se asignan a tales procesos 10, 20 y 25 bi­ lletes, respecfivamente, se repartirán en forma automática la CPU en la proporción correcta, es decir, 10 : 20 : 25.