Следующая информация взята непосредственно из Искусство многопроцессорного программирования , которая является хорошей книгой для изучения этого материала. На самом деле представлено 2 реализации: простая версия и верная версия. Я пойду дальше и воспроизведу честную версию.
Одним из требований для этой реализации является наличие примитива переменной условия. Я попытаюсь найти способ удалить его, но это может занять некоторое время. До тех пор это все равно должно быть лучше, чем ничего. Обратите внимание, что также возможно реализовать этот примитив, используя только блокировки.
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();
}
}
Во-первых, я немного упростил код, но алгоритм остался прежним. Также случается, что в книге есть ошибка для этого алгоритма, которая исправлена с ошибками. Если вы планируете читать книгу, держите ошибки рядом, иначе вы очень запутаетесь (как я несколько минут назад, когда я пытался заново понять алгоритм). Обратите внимание, что, с другой стороны, это хорошо, так как держит вас в тонусе, и это требование, когда вы имеете дело с параллелизмом.
Далее, хотя это может быть реализация Java, используйте ее только в качестве псевдокода. При реальной реализации вы должны быть осторожны с моделью памяти языка, иначе у вас наверняка возникнет головная боль. В качестве примера, я думаю, что переменные readAcquires и readReleases и writer должны быть объявлены как volatile в Java, или компилятор может оптимизировать их из циклов. Это связано с тем, что в строго последовательных программах нет никакого смысла в непрерывном цикле для переменной, которая никогда не изменяется внутри цикла. Обратите внимание, что моя Java немного ржавая, поэтому я могу ошибаться. Есть также другая проблема с целочисленным переполнением переменных readReleases и readAcquires, которая игнорируется в алгоритме.
Последнее замечание, прежде чем я объясню алгоритм. Условная переменная инициализируется с помощью блокировки. Это означает, что когда поток вызывает condition.await(), он отказывается от владения блокировкой. Как только он проснется вызовом condition.signalAll(), поток возобновит работу после того, как снова получит блокировку.
Наконец, вот как и почему это работает. Переменные readReleases и readAcquires отслеживают количество потоков, которые получили и сняли блокировку чтения. Когда они равны, ни один поток не имеет блокировки чтения. Переменная writer указывает, что поток пытается получить блокировку записи или он уже установлен.
Часть алгоритма блокировки чтения довольно проста. При попытке блокировки он сначала проверяет, удерживает ли писатель блокировку или пытается ее получить. Если это так, он ждет, пока не завершится запись, и затем запрашивает блокировку для читателей, увеличивая переменную readAcquires. При разблокировке поток увеличивает переменную readReleases и, если читателей больше нет, он уведомляет всех авторов, которые могут ожидать.
Часть алгоритма блокировки записи не намного сложнее. Чтобы заблокировать, поток должен сначала проверить, активен ли другой писатель. Если они есть, он должен ждать, пока другой писатель не закончит. Затем он указывает, что хочет заблокировать, установив для writer значение true (обратите внимание, что он еще не удерживает его). Затем он ждет, пока не останется больше читателей, прежде чем продолжить. Чтобы разблокировать, он просто устанавливает переменную writer в false и уведомляет любые другие потоки, которые могут ожидать.
Этот алгоритм справедлив, потому что читатели не могут блокировать писателя на неопределенный срок. Как только автор указывает, что хочет получить блокировку, больше читатели не смогут получить блокировку. После этого писатель просто ждет, пока последние оставшиеся читатели закончат, прежде чем продолжить. Обратите внимание, что по-прежнему существует вероятность того, что писатель на неопределенный срок заблокирует другого писателя. Это довольно редкий случай, но алгоритм может быть улучшен, чтобы учесть это.
Поэтому я перечитал ваш вопрос и понял, что частично (плохо) ответил на него по алгоритму, представленному ниже. Итак, вот моя вторая попытка.
Алгоритм, который вы описали, довольно похож на простой вариант, представленный в упомянутой мной книге.Единственная проблема в том, что А) это нечестно и Б) Я не уверен, как бы вы реализовали wait until recursive mutex has lock count zero.Для A), см. Выше и для B), книга использует единственное int для отслеживания читателей и переменную условия для выполнения сигнализации.