Puis-je utiliser une partie de mes données comme verrou?

J'ai un grand tableau (3e9 éléments) de données, et je mets à jour sa valeur dans plusieurs threads. Je viens de découvrir qu'il y a des conditions de course.Puis-je utiliser une partie de mes données comme verrou?

Je pense qu'il est inutile de verrouiller toute la fonction, comme les éléments sont indépendants les uns des autres, la mise à jour sur et data[234] peut être effectuée en toute sécurité en même temps.

J'ai également trouvé le bit le plus significatif de chaque élément dans data[] ne sera jamais utilisé. Est-il sûr d'implémenter un verrou intégré atomique GCC sur ce bit?

Mon code est le suivant, mais il semble qu'il se bloque.

const unsigned short LOCK_MASK = 1<<15; 
unsigned short * lock = &(data[position]); 
unsigned short oldLock, newLock; 

//lock 
do { 
    oldLock = *lock; 
    newLock = oldLock^LOCK_MASK; 
} while ((oldLock & LOCK_MASK) || !__sync_bool_compare_and_swap(lock, oldLock, newLock)); 

//update data[position] here 
... 
... 
... 

//unlock 
*lock ^= LOCK_MASK;

J'ai aussi lu ce post (Lightweight spinlocks built from GCC atomic operations?) et a ajouté volatile sur mon data

EDIT Dans ma conception, 0 signifie déverrouillé et 1 signifie verrouillé

Source

2017-02-20 bbvan

Toutes vos lectures avant l'acquisition de la serrure doivent être synchronisées. En particulier, 'oldLock = * lock;' est faux, cela doit être atomique. En l'état, l'optimiseur peut supposer que '* lock' ne change jamais si' (oldLock & LOCK_MASK) 'était vrai une fois. –

Une approche plus prudente pourrait consister à allouer un nombre approprié de mutex réels (ou spinlocks ou tout mécanisme que vous souhaitez utiliser) et à les utiliser pour synchroniser l'accès à vos données. par exemple. si vous avez un tableau de M mutex, alors chaque thread verrouille mutex # (i% M) avant de lire ou d'écrire la valeur #i dans le tableau de données. Réglez la valeur de M jusqu'à ce que vous trouviez la plus petite valeur pour laquelle la contention pour les mutex est encore assez rare. –

Votre code contient un certain nombre de courses de données, y compris oldLock = *lock et le déverrouillage du bit *lock ^= LOCK_MASK, qui ne parvient pas à synchroniser vos mises à jour à d'autres cœurs par l'absence d'une barrière de libération. Sachez qu'en plus de verrouiller un segment de tableau pour un accès en écriture, vous devez également verrouiller ce segment pour un accès en lecture car les lectures et les écritures doivent être synchronisées.

Est-il sûr d'implémenter un verrou intégré atomique GCC sur ce bit?

Plusieurs bits sont nécessaires si vous voulez exprimer des états séparés pour l'accès en écriture et en lecture (déverrouillé, x verrouillé en lecture N, écriture verrouillée). A limites à un seul bit de verrouillage à 2 états, verrouillés et déverrouillé, qui, en fonction de votre code, peut être mis en œuvre avec:

const unsigned short LOCK_MASK = 1<<15; 

void lock_array_segment(int position) 
{ 
    unsigned short *lock = &data[position]; // global array 
    unsigned short oldLock, newLock; 

    do { 
     oldLock = __atomic_load_n (lock, __ATOMIC_RELAXED); 
     newLock = oldLock | LOCK_MASK; // set bit 

    } while ((oldLock & LOCK_MASK) || !__sync_bool_compare_and_swap(lock, oldLock, newLock)); 
} 


void unlock_array_segment(int position) 
{ 
    unsigned short *lock = &data[position]; // global array 
    unsigned short oldLock, newLock; 

    oldLock = __atomic_load_n (lock, __ATOMIC_RELAXED); 
    newLock = oldLock & ~LOCK_MASK; // clear bit 

    __atomic_store_n (lock, newLock, __ATOMIC_RELEASE); 
}

La documentation __sync_bool_compare_and_swap dit Dans la plupart des cas, ces builtins sont considéré comme une barrière complète. Vous avez besoin d'une barrière d'acquisition ici, donc cela devrait être couvert.

Étant donné que votre approche est basée sur le spinlocking, cela ne fonctionne pas bien si vous souhaitez conserver un verrouillage de lecture plus longtemps. Dans ce cas, envisagez une approche plus simple avec un mutex distinct pour chaque segment de votre tableau de données qui doit être verrouillé. Si vous souhaitez autoriser l'accès à plusieurs lecteurs, vous pouvez utiliser std::shared_mutex (C++ 17) ou boost::shared_mutex.

Source

2017-02-20 10:23:21 LWimsey

ne connaissait pas les instructions __atomic_ * avant! Merci – bbvan

Vous devriez envisager d'autres moyens de verrouillage standard (au C++11 ou mieux).

Peut-être commencer par lire quelques Pthread tutorial (au moins pour les concepts expliqués ici).

Lire à propos de atomic operations et thread support en C++.

Vous pourriez envisager d'avoir un mutex de manière heuristique pour chaque segment d'éléments consécutifs de 1024 (ou d'une autre puissance de deux).

Vous pouvez envisager une approche producer-consumer.

Source

2017-02-20 11:27:32

Puis-je utiliser une partie de mes données comme verrou?

Répondre

Questions connexes