Sistemas operativos modernos

inactiva y necesita tener acceso a la lista compartida de procesos listos, para escoger el proce­ so a ejecutar. Si la lista está bloqueada, la CPU no podrá simplemente suspender lo que está haciendo y ejecutar otro proceso, porque para ello necesitaría obtener acceso a la lista de pro­ cesos listos. Tendrá que esperar hasta que pueda obtener la lista. Sin embargo, en otros casos sí hay opciones. Por ejemplo, si algún subproceso de una CPU necesita acceso al caché de búfer del sistema de archivos y éste está bloqueado, la CPU podría decidir cambiar a un subproceso distinto en vez de esperar. La cuestión de si es mejor ponerse a dar vueltas o cambiar de subproceso ha sido tema de muchos trabajos de investigación, algu­ nos de los cuales veremos a continuación. Cabe señalar que esta decisión no se presenta en un uniprocesador porque no tiene mucho sentido ponerse a dar vueltas cuando no hay otra CPU que libere el bloqueo. Si un subproceso trata de obtener un bloqueo y fracasa, siempre se bloqueará para que el dueño del bloqueo tenga oportunidad de ejecutarse y de liberar el bloqueo. Suponiendo que tanto dar vueltas como cambiar de subproceso sean opciones válidas, el resultado es como sigue. Dar vueltas desperdicia ciclos de CPU en forma directa. Probar un bloqueo una y otra vez no es trabajo productivo. Sin embargo, cambiar de subproceso también desperdicia ciclos de CPU porque debe guardarse el estado del subproceso actual, obtener el bloqueo de la lista de procesos listos, seleccionar un subproceso, cargar su estado y ponerlo en marcha. Además, el caché de la CPU contiene bloques que no le sirven al nuevo subproceso, así que habrá muchos fallos de caché costosos cuando el nuevo subproceso inicie su ejecución. También es probable que haya fallos de TLB. Tarde o temprano, tendrá que efectuarse el cam­ bio al subproceso original, lo cual causará más fallos de caché. Los ciclos que se ocupan en efectuar estos dos cambios de contexto, más todos los fallos de caché, se desperdician. Si se sabe que en general los mutexes se retienen durante, digamos, 50 |xs, y que se requie­ re 1 ms para cambiar a un nuevo subproceso y 1 ms para cambiar otra vez al subproceso ori­ ginal, será más eficiente a dar vueltas esperando el mutex. En cambio, si en promedio un mutex se retiene durante 10 ms, vale la pena hacer los dos cambios de contexto. El problema es que las regiones críticas pueden variar de duración de manera considerable. Entonces, ¿cuál enfo­ que es mejor? Un diseño sería dar vueltas siempre. Otro sería cambiar siempre. Pero un tercer diseño con­ siste en tomar una decisión individual cada vez que se encuentra un mutex bloqueado. En el momento en que se toma la decisión, no se sabe si es mejor dar vueltas o cambiar, pero para cualquier sistema dado es posible hacer un rastreo de todas las actividades y analizarlo más tar­ de fuera de línea. Entonces podrá determinarse en retrospectiva cuál decisión era la mejor y cuánto fiempo se desperdició en el mejor caso. Este algoritmo retrospectivo se usa entonces co­ mo base de comparación para medir los posibles algoritmos. Este problema ha sido estudiado por varios investigadores (Karlin et al., 1989; Karlin et al., 1991; Osterhout, 1982). Casi todos estos trabajos emplean un modelo en el que un sub­ proceso que no logra adquirir un mutex da vueltas durante cierto tiempo. Si se excede este um­ bral, se efectúa un cambio. En algunos casos, el umbral es fijo: por lo regular ei gasto adiciona! conocido de cambiar a otro subproceso y cambiar de vuelta al subproceso original. En otros casos el umbral es dinámico, dependiendo del historial observado del mutex que se espera. Los mejores resultados se obtienen cuando el sistema lleva un registro de los últimos tiem­ pos de giro observados y supone que el siguiente será similar a los anteriores. Por ejemplo, su