do semáforos satisface la espera limitada

Question

¿El semáforo satisface la espera acotada o son solo para proporcionar exclusión mutua?

Answer 1

respuesta

se puede romper delimitada condición de espera teóricamente como se verá a continuación. Prácticamente, depende en gran medida de qué algoritmo de programación se utiliza.

La aplicación clásica de wait()signal() y primitiva es como:

//primitive 
wait(semaphore* S) 
{ 
    S->value--; 
    if (S->value < 0) 
    { 
     add this process to S->list; 
     block(); 
    } 
} 

//primitive 
signal(semaphore* S) 
{ 
    S->value++; 
    if (S->value <= 0) 
    { 
     remove a process P from S->list; 
     wakeup(P); 
    } 
} 

Cuando un proceso llama a la wait() y falla el "si" de prueba, aparecerá carente en una lista de espera. Si se bloquean más de un proceso en el mismo semáforo, todos se ponen en esta lista (o de alguna manera se vinculan entre sí como se puede imaginar). Cuando otro proceso abandona la sección crítica y se llama a la señal(), se seleccionará un proceso en la lista de espera para que se active, listo para competir nuevamente por la CPU. Sin embargo, es el planificador quien decide qué proceso elegir de la lista de espera. Si la programación se implementa de una manera LIFO (último en entrar, primero en salir), por ejemplo, es posible que algunos procesos estén privados de comida.

Ejemplo

T1: thread 1 calls wait(), enters critical section 
T2: thread 2 calls wait(), blocked in waiting list 
T3: thread 3 calls wait(), blocked in waiting list 
T4: thread 1 leaves critical section, calls signal() 
T5: scheduler wakes up thread 3 
T6: thread 3 enters critical section 
T7: thread 4 calls wait(), blocked in waiting list 
T8: thread 3 leaves critical section, calls signal() 
T9: scheduler wakes up thread 4 
.. 

Como se puede ver, aunque se implementa/utiliza el semáforo correctamente, el hilo 2 tiene un tiempo de espera sin límites, incluso, posiblemente, el hambre, provocada mediante la introducción continua de nuevos procesos.