Implementación de MVar en C?

Question

¿Hay alguna implementación conocida de Haskell MVar en C? Hay un example sobre cómo implementarlo en C++. Pero me gustaría implementarlo en C, digamos solo MVar CInt equivalente en C por ahora. Escribir primitivas de sincronización puede ser complicado. Por lo tanto, me gustaría evitar la duplicación de esfuerzos si alguien ya lo ha hecho. No entendí el ejemplo de C++ más arriba lo suficiente como para traducirlo con confianza en C - esconde muy bien los detalles algorítmicos de mi C++ - mente inexperta :)

La razón por la que estoy pensando en escribir MVar en C es porque hace que sea muy fácil para mí usar el enlace FFI a una biblioteca C externa para obtener la secuencia de datos, y usar hilos Haskell para tomar los datos (de vectores almacenables para evitar ordenar los datos - MVar CInt aquí almacena cuánto de los Almacenables vectores se han llenado). Necesito asegurarme de que los hilos C que escriben en ubicaciones Almacenables estén bloqueados mientras un hilo Haskell está leyendo los datos. Ahí es donde la sincronización de MVar en el lado C ayuda. También es mucho más rápido llamar a la función C insegura o incluso segura de Haskell (~ 15ns por inseguro, ~ 150ns por seguro en mi prueba), que volver a llamar a Haskell desde C (~ 5us). Si las devoluciones de llamada fueran rápidas, habría hecho que la función C llamara de nuevo a Haskell y bloqueara Haskell MVar.

Actualización:

algoritmo en pseudocódigo hará también. Debería ser bastante fácil implementarlo en C, dado el algoritmo para newEmptyMVar, takeMVar y putMVar.

Answer 1

MVar puede ser implementado en C usando un struct, como a continuación:

typedef struct{ 
    pthread_cond_t put_cond; 
    pthread_cond_t take_cond; 
    pthread_mutex_t lock; 
    void* value; 
} mvar; 

put_cond es utilizado por hilos que ponen a valores en MVar para señalar otros hilos que están esperando para tomar valor de MVar. take_cond es la contraparte análoga para tomar. En cuanto a la programación, es la programación predeterminada.

value es un puntero de vacío, por lo tanto, la estructura anterior puede usarse para proteger cualquier tipo de valor en un MVar; por supuesto, C le permitirá escribir ese puntero fuera de MVar, por lo tanto, es responsabilidad del programa esto no ocurre (al evitar sacar el puntero value fuera de MVar, acceda siempre a través de las funciones de MVar).

Inicialización MVar:

mvar* newMVar(void* arg){ 
//create new mvar struct 
mvar* var=(mvar*) malloc(sizeof(mvar)); 
pthread_mutex_init(&var->lock,NULL); 
pthread_cond_init(&var->take_cond,NULL); 
pthread_cond_init(&var->put_cond,NULL); 
var->value = arg; 
return (mvar*) var; 
} 

vacío MVar - usos anteriores función:

mvar* newEmptyMVar(){ 
return newMVar(NULL); 
} 

putMVar:

void putMVar(mvar* var,void* value){ 
    pthread_mutex_lock(&var->lock); 
    while(var->value != NULL) 
    pthread_cond_wait(&var->put_cond,&var->lock);//if MVar is full, wait until another thread takes the value - release the mutex, and wait on put_cond to become true 
    var->value = value;//if here, we got the signal from another thread that took MVar - MVar is empty now. OK to fill 
    pthread_cond_signal(&var->take_cond);//signal other threads that value is available for taking now 
    pthread_mutex_unlock(&var->lock); 
} 

takeMVar:

void* takeMVar(mvar* var){ 
    void* value; 
    pthread_mutex_lock(&var->lock); 
    while(var->value == NULL) 
    pthread_cond_wait(&var->take_cond,&var->lock);//if MVar is empty, wait until another thread fills it - release the mutex, and wait on take_cond to become true 
    //take the value 
    value = var->value; 
    var->value = NULL; //push NULL value to indicate MVar is empty now 
    pthread_cond_signal(&var->put_cond);//signal other threads that value is available for filling now 
    pthread_mutex_unlock(&var->lock); 
    return value; //return the value that was taken from MVar 
} 

El código completo está en github, con example que muestra cómo usar MVar.

MVar es bastante rápido si solo hay un subproceso accediendo a él (y gran controversia). Pero, bajo fuerte contención, y múltiples hilos (incluso dos), escalan muy mal.Esto no es una sorpresa debido a la forma en que pthreads funcionan. He encontrado que MVar en Haskell es muy bueno con múltiples hilos. Esto no es una sorpresa, dado lo bien que se implementan los subprocesos livianos y las primitivas de concurrencia en GHC.

Answer 2

El código en el ejemplo no es muy específico de C++. Los bits esenciales son exactamente los pthread -fragmentos.