Condition de course dans une file d'attente simultanée

Question

J'essaie actuellement d'écrire une file d'attente simultanée, mais j'ai des erreurs de segment que je ne peux pas m'expliquer. L'implémentation de ma file d'attente est essentiellement donnée par la première annonce sur ce site.

http://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html

Le site dit qu'il ya une condition de course si les objets sont retirés de la file d'attente en parallèle, mais je ne vois pas pourquoi il y en a un, quelqu'un pourrait-il me l'expliquer?

Edit: Voici le code:

template<typename Data> 
class concurrent_queue 
{ 
private: 
    std::queue<Data> the_queue; 
    mutable boost::mutex the_mutex; 
public: 
    void push(const Data& data) 
    { 
     boost::mutex::scoped_lock lock(the_mutex); 
     the_queue.push(data); 
    } 

    bool empty() const 
    { 
     boost::mutex::scoped_lock lock(the_mutex); 
     return the_queue.empty(); 
    } 

    Data& front() 
    { 
     boost::mutex::scoped_lock lock(the_mutex); 
     return the_queue.front(); 
    } 

    Data const& front() const 
    { 
     boost::mutex::scoped_lock lock(the_mutex); 
     return the_queue.front(); 
    } 

    void pop() 
    { 
     boost::mutex::scoped_lock lock(the_mutex); 
     the_queue.pop(); 
    } 
}; 

Answer 1

Si vous utilisez vide et de trouver la file d'attente n'est pas vide, un autre thread peut avoir sauté l'élément rendant vide avant d'utiliser le résultat.

De même pour l'avant, vous pouvez lire l'élément frontal, et il pourrait être déplacé par un autre fil au moment où vous utilisez l'élément. Que se passe-t-il si la file d'attente est vide au moment où vous tentez de lire un élément à partir de celle-ci?

Answer 2

Pensez ce code utilisateur:

while(!q.empty()) //here you check q is not empty 
{ 
     //since q is not empty, you enter inside the loop 
     //BUT before executing the next statement in this loop body, 
     //the OS transfers the control to the other thread 
     //which removes items from q, making it empty!! 
     //then this thread executes the following statement! 
     auto item = q.front(); //what would it do (given q is empty?) 
} 

Answer 3

Les réponses de @parkydr et @Nawaz sont corrects, mais voici une autre nourriture pour la pensée;

Qu'essayez-vous d'accomplir?

La raison d'avoir une file d'attente de thread-safe est parfois (je n'ose dire souvent) erronée. Dans la plupart des cas, vous voulez verrouiller "en dehors" de la file d'attente, dans le contexte où la file d'attente est juste un détail d'implémentation.

L'une des raisons cependant, pour les files d'attente thread-safe sont pour situations consommateurs producteurs, où 1-N noeuds poussent des données, et nœuds pop de 1-M ce, peu importe ce qu'ils obtiennent. Tous les éléments de la file d'attente sont traités de la même manière, et les consommateurs sautent sans savoir ce qu'ils obtiennent, et commencent à travailler sur les données. Dans de telles situations, votre interface ne doit pas exposer un T& front(). Eh bien, vous ne devriez jamais retourner une référence si vous n'êtes pas sûr qu'il y a un élément là-bas (et dans des situations parallèles, vous ne pouvez jamais être certain sans verrous externes).

Je recommande d'utiliser unique_ptr (ou shared_ptr bien sûr) et d'exposer uniquement les fonctions libres de la course (je laisse les fonctions const pour plus de brièveté). L'utilisation std::unique_ptr nécessitera C++ 11, mais vous pouvez utiliser boost::shared_ptr pour la même fonctionnalité si C++ 11 est impossible pour vous d'utiliser:

// Returns the first item, or an empty unique_ptr 
std::unique_ptr<T> pop(); 

// Returns the first item if it exists. Otherwise, waits at most <timeout> for 
// a value to be be pushed. Returns an empty unique_ptr if timeout was reached. 
std::unique_ptr<T> pop({implementation-specific-type} timeout); 

void push(std::unique_ptr<T>&& ptr); 

Des fonctionnalités telles que exist() et front() sont naturellement victimes de race conditions, car ils ne peuvent pas effectuer atomiquement la tâche que vous (pensez) voulez. exist() retournera parfois une valeur qui est incorrecte au moment où vous recevez le résultat, et front() devrait lancer si la file d'attente est vide.

Answer 4

Je pense que les réponses pour lesquelles la fonction empty() est inutile/dangereuse sont claires. Si vous voulez une file d'attente de blocage, supprimez-la.Au lieu de cela, ajoutez une variable de condition (boost :: condition, IIRC) à la place. Les fonctions de pousser/pop puis regarder comme ceci:

void push(T data) 
{ 
    scoped_lock lock(mutex); 
    queue.push(data); 
    condition_var.notify_one(); 
} 

data pop() 
{ 
    scoped_lock lock(mutex); 
    while(queue.empty()) 
     condition_var.wait(lock); 
    return queue.pop(); 
} 

Notez que ce code est pseudo-ish, mais je suis sûr que vous pouvez comprendre. Cela dit, la suggestion d'utiliser unique_ptr (ou auto_ptr pour C98) pour éviter de copier les données réelles est une bonne idée, mais c'est une question complètement distincte.