La mise en œuvre de sémaphore par l'utilisation de mutex opérations primitives et

Il y a quelques temps, a eu une entrevue et a demandé de mettre en œuvre
Sémaphore par l'utilisation de mutex opérations primitives et seulement
(il permettait int pour être considérée comme atomique). Je suis venu avec la solution ci-dessous.
Il n'aimait pas occupé/wait - while (count >= size) {} -- et a demandé de mettre en œuvre le verrouillage de la place en utilisant plus primitive
les types et les mutex. Je n'ai pas réussi à venir avec une meilleure solution.
Des idées comment il pourrait être fait?

struct Semaphore {
int size;
atomic<int> count;
mutex updateMutex;

Semaphore(int n) : size(n) { count.store(0); }

void aquire() {
    while (1) {
        while (count >= size) {}
        updateMutex.lock();
        if (count >= size) {
            updateMutex.unlock();
            continue;
        }
        ++count;
        updateMutex.unlock();
        break;
    }
}

void release() {
    updateMutex.lock();
    if (count > 0) {
        --count;
    } //else log err
    updateMutex.unlock();
}
};
Utiliser une variable de condition de supprimer l'attente active. en.cppreference.com/w/cpp/thread/condition_variable Aussi, pourquoi n'utilisez-vous pas RAII à faire de verrouillage/déverrouillage.

OriginalL'auteur user2890398 | 2013-12-12

  1. 2

    EDIT - utiliser un deuxième mutex pour les les d'attente intstead de threads

    Depuis un mutex déjà bon thread de soutien, il peut être utilisé pour la file d'attente des threads (au lieu de le faire explicitement comme je l'avait tout d'abord essayé de faire). Sauf le mutex est limitée à seulement laisser le propriétaire de le déverrouiller (un de verrouillage?), ensuite, cette solution ne fonctionne pas.

    J'ai trouvé la solution dans Anthony Howe pdf que j'ai rencontré lors de la recherche. Il y a deux solutions. J'ai changé les noms pour faire plus de sens pour cet exemple.

    plus ou moins pseudo-code:

    Semaphore{
    int n;
    mutex* m_count;         //unlocked initially
    mutex* m_queue;         //locked initially
};

void wait(){
    m_count.lock();
    n = n-1;
    if(n < 0){
        m_count.unlock();
        m_queue.lock();     //wait
    }
    m_count.unlock();       //unlock signal's lock
}

void signal(){
    m_count.lock();
    n = n+1;

    if(n <= 0){
        m_queue.unlock();   //leave m_count locked
    }
    else{
        m_count.unlock();
    }
}
    Cela ne fonctionnera pas. Si vous avez une attente du thread(), puis les mettre en contexte commuté par l'OS après qu'il ait communiqué de m1, mais avant il bloque alors vous avez un autre thread signal d'appel(), voir le fil dans la file d'attente, le signal que ce thread de réveil (ce qui sera). Mais alors que le premier fil de la prochaine instruction à bloc, donc il va dormir immédiatement.
    édité ma réponse. Réalisé que c'est le même maintenant qu'une autre réponse ici.
    Je pense que c'est toujours en panne. Disons t1 commence par la signalisation. Ensuite, "m_count" devient verrouillé, et m_queue est déverrouillé. Maintenant, avez-t2 attendre. Il devient bloqué en attente pour entrer dans le "wait ()" fonction parce que "compter" est verrouillé. En outre, "les m_count" ne peut jamais devenir débloqué à moins que vous jamais signal avant de l'attente, qui n'est pas le comportement que vous êtes après.
    Désolé, j'ai fait une faute de frappe. m_count est débloqué au début de wait (modifier que maintenant). En outre, m_queue ne seront débloqués si n<=0, ce qui signifie un thread doit être en attente. m_count est débloqué dès le début donc wait peut être appelée avant le signal. Aussi, il ne fait aucun sens de commencer par la signalisation? Cela doit être évité et est généralement laissé à la coder de ce que j'ai vu.

    OriginalL'auteur dekuShrub

  2. 1

    J'avais miser ce n'est pas possible de mettre en œuvre sans une longue boucle utilisation de mutex seulement.

    Si pas occupé de boucle, tu dois bloquer quelque part. Le seul blocage primitive que vous avez est
    un mutex. Par conséquent, vous avez à bloquer sur certains mutex, lorsque le sémaphore compteur est à zéro. Vous peut être réveillé que par le seul propriétaire de ce mutex. Cependant, vous devrait réveillé à chaque fois qu'une arbitraire fil retourne contre le sémaphore.

    Maintenant, si vous êtes autorisé les variables de condition, c'est une histoire complètement différente.

    "Vous pouvez être réveillé que par le seul propriétaire de ce mutex." Pourquoi? N'est-ce pas le point de l'ensemble des mutex que vous laissez les non-possesseurs d'un fils de verrouillage et de déverrouillage?

    OriginalL'auteur chill

  3. 0

    @chill pointet, la solution que j'ai écrit ici-bas ne fonctionnera pas, que les serrures ont unique de la propriété. Je suppose qu'à la fin vous repasserez occupés à attendre (si vous n'êtes pas autorisé à utiliser les variables de condition). Je laisse ici si ppl. ont la même idée qu'ils voient que cela NE fonctionne PAS 😉

    struct Semaphore {
int size;
atomic<int> count;
mutex protection;
mutex wait;

Semaphore(int n) : size(n) { count.store(0); }

void aquire() {
    protection.lock();
    --count;
    if (count < -1) {
        protection.unlock();
        wait.lock();
    }
    protection.unlock();
}

void release() {
    protection.lock();
    ++count;
    if (count > 0) {
        wait.unlock();
    }
    protection.unlock();
}
};
    Il est intéressant de noter que cette solution n'a pas réellement besoin count atomique, puisque tous les requis de la synchronisation se fait avec le protection mutex.
    Non, cela ne fonctionne pas. Seul celui qui a exécuté d'attente.lock()' dans 'acquérir' peut appeler avec succès 'attendre.unlock()' dans la version, mais bon, il ne peut pas, parce qu'il est bloqué dans "acquérir" et n'importe quel autre thread obtiendrez une erreur de ne pas être le mutex propriétaire.
    pour moi, c'était la même chose que @Dolda2000 : je n'étais pas au courant que les mutex en C++11 ont cette propriété. Il est logique sind habituellement, vous devez utiliser une variable de condition.
    Cela fonctionne si vous avez un thread spécifique, qui prennent soin de tous le verrouillage et le déverrouillage de l'attendre et vous vous demandez simplement à ce fil de verrouillage et de déverrouillage (c'est à dire mettre en œuvre des mutex que n'importe qui peut acquiere ou release).
    C'est tout à fait une idée intéressante, bien que je ne peux pas vraiment imaginer comment faire pour que le travail actuellement. Je veux dire, ce que je pouvais imaginer serait que le sémaphore est son propre thread, Threads de Client appel d'acquérir et de toujours immédiatement aller dormir, si l'acquisition de l'op. des travaux, il est réveillé par le fil, sinon ils attendent. Cependant, comment je peux vous garantir que je ne rate pas qu'un réveil si la acquérir des œuvres? Ou je suis complètement sur une fausse piste maintenant?

    OriginalL'auteur Joerg Simon