Implementazione di MVar in C?

Question

Esiste un'implementazione nota di Haskell MVar in C? C'è un example su come implementarlo in C++. Ma, mi piacerebbe implementarlo in C - diciamo solo l'equivalente MVar CInt in C per ora. Scrivere primitive di sincronizzazione può essere complicato. Quindi, mi piacerebbe evitare la duplicazione degli sforzi se qualcuno l'ha già fatto. Non ho capito bene l'esempio C++ sopra abbastanza per tradurlo in modo sicuro in C - nasconde i dettagli algoritmici molto bene dal mio C++ - mente inesperta :)

Il motivo per cui sto pensando di scrivere MVar in C è perché rende davvero facile per me utilizzare l'associazione FFI a una libreria C esterna per ottenere il flusso di dati e utilizzare i thread Haskell per acquisire i dati (dai vettori memorizzabili per evitare il marshalling dei dati - MVar CInt qui memorizza la quantità di Storable i vettori sono stati riempiti). Devo assicurarmi che i thread in C che scrivono su posizioni Storable siano bloccati mentre un thread Haskell sta leggendo i dati. È qui che aiuta la sincronizzazione MVar sul lato C. È anche molto più veloce chiamare Haskell (circa 15ns per non sicuro, ~ 150ns per sicurezza nel mio test) non sicura o addirittura sicura C di callback in Haskell da C (~ 5us). Se i callback fossero veloci, avrei richiamato la funzione C in Haskell e bloccato su Haskell MVar.

Aggiornamento:

algoritmo in pseudo-codice farà pure. Dovrebbe essere abbastanza facile implementarlo in C, dato l'algoritmo per newEmptyMVar, takeMVar e putMVar.

Answer 1

MVAR può essere implementato in C utilizzando una struttura come di seguito:

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

put_cond è utilizzato da fili che mettono in valori MVAR per segnalare altri thread nell'attesa di prendere valore da MVAR. take_cond è la controparte analoga per Take. Per quanto riguarda la pianificazione, è la pianificazione predefinita.

value è un puntatore di vuoti - quindi, la struttura di cui sopra può essere utilizzata per proteggere qualsiasi tipo di valore in un MVar - ovviamente, C ti consente di scrivere quel puntatore all'esterno di MVar - quindi, è responsabilità del programma assicurare ciò non accade (evitando di allontanare il puntatore value all'esterno di MVar - accedere sempre tramite le funzioni MVar).

inizializzazione 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; 
} 

Empty MVar - utilizza sopra funzione:

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 
} 

Il codice completo è github, con example che mostra come utilizzare MVar.

MVar è piuttosto veloce se c'è un solo thread che lo accede (e contesa pesante). Ma, sotto pesante contesa, e più thread (anche due), si ridimensiona molto male.Questa non è una sorpresa a causa del modo in cui funzionano i pthread. Ho trovato MVar in Haskell per essere molto buono con più thread. Questa non è una sorpresa visto quanto bene i thread leggeri e le primitive di concorrenza sono implementati in GHC.

Answer 2

Il codice nell'esempio non è molto specifico per C++. I bit essenziali sono esattamente le frazioni pthread.