Эффективность использования pthread_rwlock при большом количестве читателей

Question

Пока я просматривал справочную страницу функции pthread_rwlock_unlock, я заметил, что функция возвратит EPERM, если вызывающий поток не владеет rwlock.

Поскольку блокировка rdlock позволяет нескольким потокам получить блокировку, должна существовать структура данных, такая как ссылка или массив, для хранения идентификатора владельца одного конкретного rwlock.

Здесь возникает вопрос:

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

Большое спасибо, ребята:)

Answer 1

нм дало хороший ответ.Ваше предположение о структурах для хранения владения блокировкой неверно в реализации Linux, которую вы пометили, и похоже на метод подсчета, к которому обращается nm.

Вот отредактированная версия типа pthread_rwlock_t из / usr / include / bits/pthreadtypes.h

  struct
  {
    int __lock;
    unsigned int __nr_readers;
    unsigned int __readers_wakeup;
    unsigned int __writer_wakeup;
    unsigned int __nr_readers_queued;
    unsigned int __nr_writers_queued;
    int __writer;
    int __shared;
    unsigned int __flags;
  } __data;

Вы можете увидеть поля количества.Также pthread_rwlock_unlock.c не возвращает EPERM, и большая часть работы вращается вокруг проверки владения писателем в pthread_rwlock_wrlock.c и pthread_rwlock_rdlock.c .

Вы можете проверить это с помощью небольшой программы, чтобы объявить и инициализировать блокировку, а затем просто разблокировать ее.

Таким образом, сложность времени в этой реализации кажется достаточно близкой к постоянной, но она достигается за счет использования некоторых функций, которые вы, возможно, думалиили хотел быть там.

Answer 2

Обратите внимание, что реализация не обязана возвращать EPERM.Результат разблокирования чужой блокировки не определен, как указано в стандарте.

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