Sistemas operativos modernos

Otra forma de reducir el tráfico de bus es utifizar el algoritmo de retroceso exponencial bi­ nario de Ethernet (Anderson, 1990). En vez de hacer un sondeo en forma continua, como en la figura 2-22, puede insertarse un ciclo de retraso entre sondeos. En un principio, el retraso es de una instrucción. Si el bloqueo sigue ocupado, el retraso se aumentará a dos instrucciones, lue­ go a cuatro, y así hasta algún máximo. Si el máximo es bajo, la respuesta será rápida cuando el bloqueo se libere, pero se desperdiciarán más ciclos de bus por la hiperpaginación de caché {cache thrashing). Un máximo alto reduce la hiperpaginación de caché a expensas de tardar más en percatarse de que el bloqueo está libre. El retroceso exponencial binario puede utilizar­ se con o sin las lecturas puras previas a la instrucción TSL. Una idea mejor aún es dar a cada CPU que quiere adquirir el mutex su propia variable de blo­ queo privada para que la pruebe, como se ilustra en la figura 8-11 (Mellor-Crummey y Scott, 1991). La variable debe residir en un bloque de caché que no se use para ninguna otra cosa, a fin de evitar conflictos. El algoritmo opera exigiendo a una CPU que fracasó en el intento de obte­ ner un bloqueo que asigne una variable de bloqueo y se coloque al final de una lista de procesa­ dores que esperan el bloqueo. Cuando el poseedor de éste salga de la región critica, libera el bloqueo privado que la primera CPU de la lista está probando (en su propio caché). Esta CPU en­ tra entonces en la región crítica. Cuando termine, liberará el bloqueo que esté usando su suceso­ ra, y así en forma sucesiva. Aunque el protocolo es un tanto complicado (para evitar que dos CPUs se enganchen al final de la lista al mismo fiempo), es eficiente y no produce inanición. Si usted desea conocer los pormenores, puede consultar el artículo. CPU 3 La CPU 2 da vueltas esperando este bloqueo {privado) \ Memoria compartida La CPU 1 tiene el verdadero bloqueo La CPU 3 da vueltas esperando este bloqueo (privado) La CPU 4 da vueltas esperando este bloqueo (privado) Cuando la CPU 1 termina de usar el bloqueo real, lo libera y también libera el bloqueo privado por el que está dando vueltas la CPU 2 Figura 8 - n . Uso de múltiples bloqueos para evitar la hiperpaginación de caché. Dar vueltas en comparación con cambiar de proceso Hasta aquí hemos supuesto que una CPU que necesita un mutex ocupado simplemente espera hasta que esté disponible, ya sea haciendo un sondeo en forma continua o intermitente, o intro­ duciéndose al final de una lista de procesadores que esperan. En algunos casos, la CPU solici­ tante no tiene más alternativa que esperar. Por ejemplo, supongamos que alguna CPU está