Comment fonctionne un mutex / verrou en lecture / écriture?

Les éléments suivants sont pris directement à partir de L'Art de la Programmation Multiprocesseur qui est un bon livre pour apprendre ce genre de choses. Il y a en fait 2 implémentations présenté: une version simple et une juste version. Je vais aller de l'avant et de le reproduire à la juste version.

L'une des exigences de cette application est que vous avez une variable de condition primitive. Je vais essayer de trouver un moyen de le supprimer mais qui pourrait me prendre un peu de temps. Jusqu'alors, ce doit être encore mieux que rien. Notez qu'il est également possible de mettre en œuvre cette primitive à l'aide de cadenas.

public class FifoReadWriteLock {
    int readAcquires = 0, readReleases = 0;
    boolean writer = false;
    ReentrantLock lock;
    Condition condition = lock.newCondition(); //This is the condition variable.

    void readLock () {
        lock.lock();
        try {
            while(writer)
                condition.await();
            readAcquires++;
        }
        finally {
            lock.unlock();
        }
    }

    void readUnlock () {
        lock.lock();
        try {
            readReleases++;
            if (readAcquires == readReleases)
                condition.signalAll();
        }
        finally {
            lock.unlock();
        }
    }

    void writeLock () {
        lock.lock();
        try {
            while (writer)
                condition.await();

            writer = true;

            while (readAcquires != readReleases)
                condition.await();
        }
        finally {
            lock.unlock();
        }
    }

    void writeUnlock() {
        writer = false;
        condition.signalAll();
    }
}

Tout d'abord, j'ai simplifié un peu le code, mais l'algorithme reste le même. Il y a aussi une erreur dans le livre de cet algorithme qui est corrigé dans l'errata. Si vous avez l'intention de lire le livre, garder les errata à proximité, ou vous allez finir par être très confus (comme moi il y a quelques minutes quand j'ai essayé de re-comprendre l'algorithme). Notez que sur le côté positif, c'est une bonne chose, car il vous permet de rester sur vos orteils et c'est une exigence lorsque vous faites affaire avec la concurrence.

Prochaine, alors que cela peut être une implémentation de Java, seule l'utilisation du pseudo-code. Lors de la mise en œuvre effective, vous devrez être prudent au sujet de la modèle de mémoire de la langue ou vous allez certainement retrouver avec un mal de tête. Comme exemple, je pense que le readAcquires et readReleases et writer toutes les variables doivent être déclarées comme volatile en Java ou le compilateur est libre de les optimiser hors de la boucle. C'est parce que d'un strict point de programmes séquentiels il n'y a aucun point en continu en boucle sur une variable qui n'est jamais modifiée à l'intérieur de la boucle. Notez que mon Java est un peu rouillé donc j'ai peut-être tort. Il y a aussi un autre problème de dépassement d'entier, de la readReleases et readAcquires variables qui est ignoré dans l'algorithme.

Une dernière remarque avant d'expliquer l'algorithme. La variable d'état est initialisé à l'aide de la serrure. Cela signifie que lorsqu'un thread appelle condition.await()il renonce à son droit de propriété de la serrure. Une fois qu'il est réveillé par un appel à condition.signalAll() le thread va reprendre une fois qu'il a acquis de nouveau la serrure.

Enfin, voici comment et pourquoi il fonctionne. Le readReleases et readAcquires variables de garder une trace du nombre de threads qui ont acquis et publié le verrou en lecture. Lorsque ceux-ci sont égaux, pas de fil a le verrou en lecture. Le writer variable indique qu'un thread est d'essayer d'acquérir le verrou d'écriture ou elle a déjà.

Le verrou en lecture de la partie de l'algorithme est assez simple. Lors de la tentative de verrouillage, il vérifie d'abord si un écrivain est maintenant le verrou ou est en train d'essayer de l'acquérir. Si oui, il attend jusqu'à ce que l'écrivain est fait et puis les revendications de la serrure pour les lecteurs en incrémentant le readAcquires variable. Lors du déverrouillage, un fil augmente la readReleases variable et si il n'y a pas plus de lecteurs, il le notifie à tous les écrivains qui l'attend peut-être.

Le verrou d'écriture de la partie de l'algorithme n'est pas beaucoup plus compliqué. Pour verrouiller, un thread doit d'abord vérifier si aucun autre écrivain est active. Si elles le sont, il doit attendre jusqu'à ce que l'écrivain est fait. Il indique ensuite qu'il veut la serrure par la mise en writer de vrai (à noter que elle ne possède pas encore). Puis, il attend jusqu'à ce qu'il n'y a pas plus de lecteurs avant de continuer. Pour le déverrouiller, il suffit simplement de définir la variable writer à faux et en informe les autres threads qui peuvent être en attente.

Cet algorithme est juste parce que les lecteurs ne peuvent pas bloquer un écrivain indéfiniment. Une fois qu'un écrivain indique qu'il veut acquérir le verrou, pas plus les lecteurs peuvent acquérir le verrou. Après que l'auteur attend simplement les derniers lecteurs pour finir avant de continuer. Noter qu'il y a toujours la possibilité d'un écrivain indéfiniment blocage d'un autre écrivain. C'est assez rare, mais l'algorithme peut être amélioré afin de prendre en compte.

---

Donc j'ai re-lu votre question et se rendit compte que j'ai un peu (mal) répondu il avec l'algorithme présenté ci-dessous. Voici donc ma deuxième tentative.

L'algorithme, vous avez décrit est assez similaire à la version simple présenté dans le livre que j'ai mentionné. Le seul problème est que ce n'est pas juste et B) je ne suis pas sûr de savoir comment vous mettre en œuvre wait until recursive mutex has lock count zero. Pour A), voir ci-dessus et pour B), le livre utilise un seul int pour garder la trace des lecteurs et une variable de condition de faire de la signalisation.