Reader Writer Lock поддерживает писателей с низким приоритетом

Я пытаюсь найти (или внедрить) блокировку чтения / записи, которая поддерживает устройства записи с низким приоритетом, но безуспешно при исследовании любых существующих решений.

Под автором с низким приоритетом я подразумеваю следующее: "уступит свое место в очереди" поступающим читателям или обычным писателям.

Конечно, это приведет к голоданию, если будет постоянный поток читателей, но это может быть решено либо с помощью варианта временной блокировки ("попробуйте синхронизировать блокировку с низким приоритетом при записи", а затем переключиться на обычную блокировку по таймауту), либо путем изменения способа чтения выдаются (возможно, периодически прекращается чтение короткого окна).

Если есть какая-либо литература, описывающая что-то подобное, я не нашел бы этого.

Если есть известное (правильное!) Решение, использующее обычные блокировки, я был бы признателен за описание.

Источник

3 ответа

Решение

Я не знаю ничего на 100% похожего на ваше предложение, но есть некоторые близкие интерфейсы:

Многие существующие API блокировки r / w имеют интерфейс "try lock", например pthread_rwlock_trywrlock() в системах UN*X Они без ожидания и получат блокировку, только если никто не владеет ею и не ждет ее уже.

Обычно вы используете это вращение для блокировки и / или искусственной задержки кода попытки (откат). Т.е. есть код вроде:

for (count = 0; count < MAX_SPINS && (locked = trywrlock(lock)); count++);
if (locked) {
    delay(some_backoff);
    wrlock(lock);         /* or try spinning loop above again ? */
}

К сожалению, это не совсем то, что вы просите; он получит блокировку поздно, но записывающее устройство с низким приоритетом будет загружать процессор и / или получать его с задержкой из-за (возможно, ненужного) отката.

Ядро Solaris имеет интерфейс rw_tryupgrade(9f)это можно использовать для проверки того, является ли текущий поток единственным читателем в блокировке без ожидающего записи, и если это так, обновите блокировку до эксклюзивной / записи, т.е. вы должны написать:

if (!rw_tryenter(lock, RW_WRITER)) {
    rw_enter(lock, RW_READER);    /* this might wait for a writer */
    if (!rw_tryupgrade(lock)) {   /* this fails if >1 reader / writer waiting */
        /* do what you must to if you couldn't get in immediately */
    }
}

Что немного ближе к тому, что вы просите, но все же не совсем то же самое - если это не удастся, вам придется сбросить блокировку чтения, возможно, отменить (подождать), повторно получить блокировку чтения, попытаться обновить. Этот процесс снова сводится к вращению.

Кроме того, многие системы UNIX, по крайней мере, фактически выполняют пробуждения официантов в порядке приоритета планирования; так что вам придется сделать ваш поток с самым низким приоритетом (если необходимо, искусственно), прежде чем пытаться обычного, ожидая wrlock() вызов; тот, кто еще захочет такую ​​же блокировку записи, пока ваш поток ожидает, получит ее до этого, благодаря тому, как работает планировщик. Хотя в многопроцессорных / основных системах это не обязательно гарантировано...

Наконец, SymbianOS (версия Symbian^3) имеет RRWlock класс, который может быть сделан для того, чтобы расставить приоритеты читателей над писателями, так что он намеренно будет голодать писателей, если есть читатели, ожидающие / входящие. Опять же, не совсем то поведение, которое вам нужно, так как оно влияет на всех писателей в данной блокировке, а не только на конкретный.

Боюсь, вам придется написать свою собственную приоритетную блокировку с двумя очередями активации писателя.

Источник

Здесь вы видите расстановку приоритетов между читателем и писателем, так что писатель с низким приоритетом всегда дает первый шанс читателю с высоким приоритетом. Это, очевидно, может привести к голоду для писателя с низким приоритетом из-за его щедрости.

Это может быть достигнуто на двух разных уровнях: 1. Со стороны приложения: это обычный подход, так как обычно мьютекс не смещен. Прежде чем потоки будут бороться за блокировку, логика приложения должна сама решить, какой поток имеет более высокий приоритет, и позволить этому потоку перейти на блокировку. Обычно это зависит от приложения:

-> Подход исполнителя задачи: поток исполнителя выполняет доступную задачу только на основе приоритета. Это решает приоритетное выполнение на уровне исполнителя, но та же проблема появляется выше этого уровня. Это работает как реализация длинного мьютекса в FIFO. Это также необходимо решить проблему с голодом.

  1. Напишите смещенный механизм блокировки, который понимает приоритет и позволяет блокировать поток с более высоким приоритетом. Это также необходимо для обеспечения "Нет голодания". Возможна импровизированная версия мьютекса.
Источник

Вне моей головы, вы бы хотели что-то вроде этого:

class PriorityRWLock
{ 
  int                rwcount;
  mutex              mtx;
  condition_variable cv;
  priority_queue<writer_info> writers;
};

... и PriorityRWLock::acquisition_write_lock() будет выглядеть примерно так:

lock_guard raii(mtx);

do {
if ( rwcount==0 ) // == no read or write locks
{
  if ( writers.top().thread == thread::self() )
  {  rwcount = -1; writers.pop_front(); break; } // == exclusive write access
  else 
  { 
     // wake up the waiting thread(s) and sleep
     writers.push( writer_info(thread::self(),priority) ); 
     cv.notify_all();
     cv.wait(mtx); 
  }
}
else
{ cv.wait(mtx); }  // sleep
} while ( true );

... или что-то похожее на это.

Это не будет слишком эффективным. Вы бы действительно предпочли хранить rwcount в atomic_int или подобном, но необходимость в condition_variable исключает это.

Блокировка по времени была бы сложной из-за возможной необходимости периодически ждать (). try_write_lock() должен быть выполнимым, хотя.

Источник
Другие вопросы по тегам