Algoritmos de sincronización de hardware: desbloquear y bloquear, probar y configurar, intercambiar

Los problemas de sincronización de procesos ocurren cuando dos procesos que se ejecutan simultáneamente comparten los mismos datos o la misma variable. Es posible que el valor de esa variable no se actualice correctamente antes de que lo utilice un segundo proceso. Tal condición se conoce como condición de carrera alrededor. Hay soluciones de software y hardware para este problema. En este artículo hablaremos sobre la solución de hardware más eficiente para los problemas de sincronización de procesos y su implementación. 

Hay tres algoritmos en el enfoque de hardware para resolver el problema de sincronización de procesos: 

1. Probar y configurar 
2. Intercambio 
3. Desbloquear y bloquear 

Las instrucciones de hardware en muchos sistemas operativos ayudan en la solución efectiva de problemas de secciones críticas. 

1. Probar y establecer: 
aquí, la variable compartida es lock, que se inicializa en falso. El algoritmo TestAndSet(lock) funciona de esta manera: siempre devuelve cualquier valor que se le envíe y establece el bloqueo en verdadero. El primer proceso ingresará a la sección crítica de inmediato, ya que TestAndSet(lock) devolverá false y saldrá del ciclo while. Los otros procesos no pueden entrar ahora ya que el bloqueo está establecido en verdadero y, por lo tanto, el ciclo while continúa siendo verdadero. La exclusión mutua está asegurada. Una vez que el primer proceso sale de la sección crítica, el bloqueo se cambia a falso. Entonces, ahora los demás procesos pueden entrar uno por uno. El progreso también está asegurado. Sin embargo, después del primer proceso, cualquier proceso puede ingresar. No se mantiene una cola, por lo que cualquier proceso nuevo que encuentre que el bloqueo es falso nuevamente, puede ingresar. Por lo tanto, la espera limitada no está garantizada. 

Probar y configurar el pseudocódigo – 

//Shared variable lock initialized to false
boolean lock;

boolean TestAndSet (boolean &target){
    boolean rv = target;
    target = true;
    return rv;
}

while(1){
    while (TestAndSet(lock));
    critical section
    lock = false;
    remainder section
}
 

2. Intercambio: 
el algoritmo de intercambio es muy parecido al algoritmo TestAndSet. En lugar de establecer directamente el bloqueo en verdadero en la función de intercambio, la clave se establece en verdadero y luego se intercambia con el bloqueo. Entonces, nuevamente, cuando un proceso está en la sección crítica, ningún otro proceso puede ingresar, ya que el valor de bloqueo es verdadero. La exclusión mutua está asegurada. Nuevamente, fuera de la sección crítica, el bloqueo se cambia a falso, por lo que cualquier proceso que lo encuentre no ingresará a la sección crítica. El progreso está asegurado. Sin embargo, nuevamente la espera limitada no está garantizada por la misma razón. 

Intercambiar pseudocódigo – 

// Shared variable lock initialized to false 
// and individual key initialized to false;

boolean lock;
Individual key;

void swap(boolean &a, boolean &b){
    boolean temp = a;
    a = b;
    b = temp;
}

while (1){
    key = true;
    while(key)
         swap(lock,key);
    critical section
    lock = false;
    remainder section
} 

3. Desbloquear y bloquear: 
El algoritmo de desbloqueo y bloqueo usa TestAndSet para regular el valor de bloqueo, pero agrega otro valor, esperando [i], para cada proceso que verifica si un proceso ha estado esperando o no. Se mantiene una cola de listos con respecto al proceso en la sección crítica. Todos los procesos que vienen a continuación se agregan a la cola de listos con respecto a su número de proceso, no necesariamente de forma secuencial. Una vez que el i-ésimo proceso sale de la sección crítica, no cambia el bloqueo a falso para que cualquier proceso pueda aprovechar la sección crítica ahora, que era el problema con los algoritmos anteriores. En su lugar, comprueba si hay algún proceso esperando en la cola. La cola se toma como una cola circular. Se considera que j es el siguiente proceso en línea y el ciclo while verifica desde el j-ésimo proceso hasta el último proceso y nuevamente desde 0 hasta (i-1)-ésimo proceso si hay algún proceso esperando para acceder a la sección crítica. Si no hay ningún proceso en espera, el valor de bloqueo se cambia a falso y cualquier proceso que venga a continuación puede ingresar a la sección crítica. Si lo hay, entonces el valor de espera de ese proceso se convierte en falso, de modo que el primer ciclo while se vuelve falso y puede ingresar a la sección crítica. Esto asegura una espera limitada. Entonces, el problema de la sincronización de procesos se puede resolver a través de este algoritmo. para que el primer bucle while se vuelva falso y pueda entrar en la sección crítica. Esto asegura una espera limitada. Entonces, el problema de la sincronización de procesos se puede resolver a través de este algoritmo. para que el primer bucle while se vuelva falso y pueda entrar en la sección crítica. Esto asegura una espera limitada. Entonces, el problema de la sincronización de procesos se puede resolver a través de este algoritmo. 

Desbloquear y bloquear pseudocódigo – 

// Shared variable lock initialized to false 
// and individual key initialized to false

boolean lock;
Individual key;
Individual waiting[i];

while(1){
    waiting[i] = true;
    key = true;
    while(waiting[i] && key)
        key = TestAndSet(lock);
    critical section
    j = (i+1) % n;
    while(j != i && !waiting[j])
         j = (j+1) % n;
    if(j == i)
         lock = false;
    else
         waiting[j] = false;
    remainder section
}