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

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

4 голосов
/ 22 февраля 2011

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

Что я подразумеваю под писателем с низким приоритетом: «уступит свое место в очереди» для входящих читателей или обычных писателей.

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

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

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

Ответы [ 3 ]

3 голосов
/ 22 февраля 2011

Я не знаю ничего на 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 голос
/ 08 июля 2018

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

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

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

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

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

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

... и PriorityRWLock :: acqu_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 () должен быть выполнимым, хотя.

...