¿Cómo hacer la sincronización del hilo sin usar mutex, semorphore, spinLock y futex?

Question

Esta es una pregunta de la entrevista, la entrevista se ha realizado.

Cómo hacer la sincronización del hilo sin usar mutex, semorphore, spinLock y futex?

Dados 5 hilos, ¿cómo hacer que 4 de ellos esperen una señal del hilo izquierdo en el mismo punto? significa que cuando todos los hilos (1,2,3,4) se ejecutan en un punto de su función de hilo, se detienen y esperan a que la señal del hilo 5 envíe una señal; de lo contrario, no continuarán.

Mi idea:

Uso variable global bool como una bandera, si el hilo 5 no establece cierto, todos los otros subprocesos esperan en un punto y también establecer su variable de indicador cierto. Después de que el hilo 5 encuentre que todas las variables de indicador de los hilos son verdaderas, lo configurará como indicador var verdadero.

Es una espera ocupada.

¿Alguna idea mejor?

Gracias

the pseudo code: 
bool globalflag = false; 
bool a[10] = {false} ; 
int main() 
{ 
    for (int i = 0 ; i < 10; i++) 
    pthread_create(threadfunc, i) ; 

     while(1) 
     { 
     bool b = true; 
     for (int i = 0 ; i < 10 ; i++) 
     { 
       b = a[i] & b ; 
     } 
     if (b) break; 
    } 
    } 
    void threadfunc(i) 
    { 
    a[i] = true; 
    while(!globalflag); 
    } 

Answer 1

empezar con una lista enlazada vacío de subprocesos en espera. El cabezal debe establecerse en 0.

Use CAS, compare y cambie, para insertar un hilo al principio de la lista de camareros. Si el encabezado = -1, no inserte ni espere. Puede usar CAS de manera segura para insertar elementos al principio de una lista vinculada si lo hace bien.

Después de insertarse, el hilo de espera debe esperar en SIGUSR1. Use sigwait() para hacer esto.

Cuando esté listo, el hilo de señalización usa CAS para establecer el jefe de la lista de espera en -1. Esto evita que se agreguen más subprocesos a la lista de espera. Luego, el hilo de señalización itera los hilos en la lista de espera y llama a pthread_kill (& hilo, SIGUSR1) para activar cada hilo en espera.

Si se envía SIGUSR1 antes de una llamada a sigwait, sigwait regresará inmediatamente. Por lo tanto, no habrá una carrera entre agregar un hilo a la lista de espera y llamar a sigwait.

EDIT:

CAS ¿Por qué es más rápido que un mutex? La respuesta de Laymen (soy un hombre común). Es más rápido para algunas cosas en algunas situaciones, ya que tiene una sobrecarga menor cuando NO hay raza. Entonces, si puede reducir su problema concurrente a la necesidad de cambiar 8-16-32-64-128 bits de memoria contigua, y una carrera no va a suceder muy a menudo, CAS gana. CAS es básicamente una instrucción mov un poco más sofisticada/costosa, donde ibas a hacer un "mov" regular de todos modos. Es una "exclusión de bloqueo" o algo así.

Un mutex por otro lado es un montón de cosas extra, que ensucia otras líneas de caché y usa más barreras de memoria, etc. Aunque CAS actúa como una barrera de memoria en el x86, x64, etc. Entonces, por supuesto tienes que desbloquear el mutex, que es probablemente la misma cantidad de material extra.

Aquí es cómo agregar un elemento a una lista enlazada usando CAS:

while (1) 
{ 
    pOldHead = pHead; <-- snapshot of the world. Start of the race. 
    pItem->pNext = pHead; 
    if (CAS(&pHead, pOldHead, pItem)) <-- end of the race if phead still is pOldHead 
    break; // success 
} 

Entonces, ¿Con qué frecuencia piensa su código va a tener múltiples hilos en esa línea CAS exactamente al mismo tiempo? En realidad ... no muy a menudo. Hicimos pruebas que acababan de realizar bucles para agregar millones de elementos con múltiples hilos al mismo tiempo, y eso ocurre mucho menos del 1% del tiempo. En un programa real, puede que nunca suceda.

Obviamente si hay una carrera, tienes que volver atrás y hacer ese ciclo otra vez, pero en el caso de una lista vinculada, ¿qué te cuesta eso?

La desventaja es que no puede hacer cosas muy complejas en esa lista vinculada si va a utilizar ese método para agregar elementos al encabezado. Intente implementar una lista de doble enlace. Que dolor.

EDIT:

En el código anterior utilizo una macro CAS. Si está usando linux, CAS = macro usando __sync_bool_compare_and_swap. Ver gcc atomic builtins. Si está usando Windows, CAS = macro usando algo como InterlockedCompareExchange. Esto es lo que una función en línea en las ventanas podría ser:

inline bool CAS(volatile WORD* p, const WORD nOld, const WORD nNew) { 
    return InterlockedCompareExchange16((short*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(volatile DWORD* p, const DWORD nOld, const DWORD nNew) { 
    return InterlockedCompareExchange((long*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(volatile QWORD* p, const QWORD nOld, const QWORD nNew) { 
    return InterlockedCompareExchange64((LONGLONG*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(void*volatile* p, const void* pOld, const void* pNew) { 
    return InterlockedCompareExchangePointer(p, (PVOID)pNew, (PVOID)pOld) == pOld; 
} 

Answer 2

1. Elija una señal de usar, dicen SIGUSR1.
2. Utilice pthread_sigmask para bloquear SIGUSR1.
3. Crear los hilos (heredan la máscara de señal, por lo tanto, 1 debe hacerse primero!)
4. Los hilos 1-4 llaman a sigwait, bloqueando hasta que se recibe SIGUSR1.
5. El hilo 5 llama a kill() o pthread_kill 4 veces con SIGUSR1. Como POSIX especifica que las señales se entregarán a un hilo que no está bloqueando la señal, se enviará a uno de los hilos esperando en sigwait(). Por lo tanto, no es necesario realizar un seguimiento de qué subprocesos ya han recibido la señal y cuáles no, con la sincronización asociada.

Answer 3

Usted puede hacer esto utilizando MONITOR y MWAIT instrucciones SSE3, disponibles a través de los _mm_mwait_mm_monitor y los intrínsecos, Intel tiene un artículo sobre ella here. (también hay una patente para usar memory-monitor-wait para contención de bloqueo here que puede ser de interés).

Answer 4

creo que busca la Peterson's algorithm o Dekker's algorithm

Se sincronizan procesos únicamente en base a la memoria compartida