pthread_mutex дождаться освобождения без захвата мьютекса

> Подскажите, возможно ли заставить поток ожидать освобождения мьютекса без его захвата?

Невозможно.

В качестве выхода вижу вариант ожидания освобождения мьютекса без его захвата

Единственный выход - подумать и сделать нормально. Пока что ты хочешь, мягко говоря, странного.

Странность выходит из решаемой задачи: Есть список объектов. Каждый из объектов может быть обрабатываться только одним потоком в данный момент времени. После обработки объект может быть либо уничтожен либо оставлен в списке потоком обработчиком.

Если первый поток захватил объект, то второй уходит в ожидание. Если объект не будет уничтожен первым, то второй поток обязательно должен обработать этот объект после разблокирования мьютекса. Если объект будет уничтожен, то второй поток должен получить результат «объект не найден». Об уничтожении объекта можно узнать по его отсутствию в общем списке (фактически поиск может повторяться рекурсивно). Если использовать pthread_mutex_lock, то нельзя удалять мьютекс (потому как возникнет коллизия - удаление в потоке 1 захваченного потоком 2 мьютекса). В этом случае необходимо складывать мьютексы уничтоженных объектов и освобождать потом. Замечу, что в режиме ожидания могут находится несколько потоков, то есть удалить мьютекс в потоке 2 тоже нельзя (могут быть поток 3, 4 и т.п. с ожиданием этого мьютекса). Тогда необходимо организовывать хранение мьютексов, собирать мусор и в этом случае тоже возникают вопросы - как определить момент, когда мьютекс можно уничтожить.

Вариант с чем-то вроде pthread_mutex_wait_nolock был бы в моем случае идеальным: проснувшись поток 2 вызвал бы рекурсивно процедуру поиска и захвата объекта и получил бы требуемый результат (объект не найден или указатель эксклюзивно захваченного объекта если потоки 3,4 и тп не подсуетились раньше).

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

Добавить глобальный мютекс, защищающий номер последнего удаленного объекта?

> Если первый поток захватил объект, то второй уходит в ожидание. Если объект не будет уничтожен первым, то второй поток обязательно должен обработать этот объект после разблокирования мьютекса.

Ничего не понимаю. Расскажи подробнее, по какому алгоритму объект должен путешествовать между потоками-обработчиками?

> Странность выходит из решаемой задачи

Странность исходит из головы^Wрешения задачи.

Еще один вариант - создание пула мьютексов и распределение их между объектами,

Еще один вариант - хранить объекты в глобальном залоченном списке, и удалять их оттуда на время обработки. Да много чего можно придумать.

Зачем так много мутексов? не проще защитить список одним мутексом, уничтоженные объекты удалять из списка?

Честно говоря, внимательно прочитать условия вашей задачи и вникнуть сейчас нет времени, но можте быть поможет вот этот вариант:

Создать у объекта свойство: обрабатывается в данный момент. Это свойство захватывать потоком через мьютекс. Если объект уже обрабатывается - добавить коллбек, который будет вызван при завершении обработки. Коллбек принимает булев параметр: был ли уничтожен объект.

может быть pthread_wait_condition?

нет, не пройдет. Тогда второй поток не узнает, что объект существует и не обработает его.

> нет, не пройдет.

Не пройдет то, что выдумал ты.

Тогда второй поток не узнает, что объект существует и не обработает его.

Какой второй? Почему не узнает? Сказано же: «удаляет на время обработки». Это значит - после окончания обработки объект можно либо вернуть в глобальный список, либо удалить.

Есть некий сервер, принимающий в несколько потоков udp-пакеты. Дальше разбирается пакет, из него достается некий идентификатор и другая информация. Затем вызывается функция, которой я и занимаюсь.

Алгоритм таков:

1. По идентификатору ищется объект в пуле. Если он не найден, то объект создается.

2. Если объект уже обрабатывается в другом потоке, то ждем завершения обработки и возвращаемся к пункту 1.

3. Полученный объект обрабатывается в соответствии с информацией udp-пакете.

4. В зависимости от результатов обработки объект уничтожается.

Соответственно могут приходить одновременно пакеты с одинаковыми ID (это нештатная ситуация, но она возможна, а мне бы не хотелось, чтобы сервер повел себя «странно»). В этом случае, если найденный объект уже обрабатывается, то мы должны дождаться завершения его обработки после чего опять осуществить поиск. То есть, на момент начала обработки, состояние объекта должно быть таким, как если бы более ранняя обработка уже завершилась (пусть и уничтожением объекта - в этом случае будет создан новый)

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

Тогда возможна такая ситуация:

Первый поток просмотрел список, нашел объект, удалил его из списка и начал обрабатывать.

В это время второй поток просматривает глобальный список и не находит там объекта, после чего создает новый объект с таким ID обрабатывает и помещает в глобальный список.

Затем первый, закончив обработку, возвращает объект в глобальный список. В результате мы получаем не только 2 объекта с одинаковым ID, но и неправильную логику работы 2 потока.

Если помещать выведеный из глобального списка объект в некий другой список, то получаем ту же самую ситуацию, что и в исходном посте

Второй поток ОБЯЗАН найти объект и дождаться окончания его обработки. Чтобы дождаться окончания его обработки я мог бы использовать мьютекс, но я не могу этот мьютекс блокировать, так как в результате работающей обработки этот мьютекс с объектом могут быть уничтожены.

Я представляю несколько способов решения, но они не отличаются простотой, что потенциально создает угрозы ошибок. На самом деле задача проста - дождаться освобождения мьютекса без его захвата и все. Просто с трудом верится, что такая очевидная возможность не реализуется.

ну ты зверь… а как ты вообще собираешься контролировать целостность списка, если у тебя один поток что-то там удаляет из него, а второй по нему шарицца в поисках истины? организуй для самого списка rwlock и не трави тюльку…

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

Целостность списка контроллируется одним глобальным rwlock. rwlock для всех объекто не годится - два ищущих потока найдут один объект и начнут одновременно обрабатывать его, что в моем случае - зло.

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

При таком подходе, второй поток, получив сигнал об освобождении мьютекса объекта, рекурсивно начинает поиск, и не найдя объект (пусть он еще и не уничтожен, но в списке его уже нет), создаст новый и PROFIT. НО! Получив сигнал об освобождении мьютекса объекта он захватвает мьютекс (FAIL)

Можно ждать освобождения объекта вручнуюю, то есть при неудачном trylock делать sleep и рекурсию на поиск. Но где гарантия, что при относительно маленьком sleep я не получу stack overlow, а при большом sleep существенный задержки?

Данные у тебя - список, а не объекты. Поскольку потоки могут его менять (удалять или добавлять объекты), то блокировать надо весь список.

Это то же самое, что классическая задача про счёт в банке.

Не парся над этим, подумай лучше как улучшить алгоритм.

обработка разных объектов не должна взаимно блокироваться

Это и есть проблема алгоритма. В начале работы потока у тебя может быть один список, а в конце другой (объект удалён). Это как в классической задаче про счёт в банке.

> В это время второй поток просматривает глобальный список и не находит там объекта, после чего создает новый объект с таким ID обрабатывает и помещает в глобальный список.

Сделать идентификатор, который не будет повторяться, тебе запрещает религия? А помечать объекты признаком «идет обработка»?

Да, пожалуй, лучше всего создавать/удалять мютексы. И, кстати, зачем их разблокировать? Удаляй так.

два ищущих потока найдут один объект и начнут одновременно обрабатывать его, что в моем случае - зло.

Ты не понял. Тебе надо глобальный мутек блокировать _перед_ тем, как искать. Нашел - обработал. Надо удалить - удалил. Не нашёл - создал. А вот тут можно и разблокировать.

> rwlock для всех объекто не годится - два ищущих потока найдут один объект и начнут одновременно обрабатывать его, что в моем случае - зло.

ты не понял. rwlock отвечает за целостность списка. за каждый объект отвечает свой мютекс/rwlock.

по остальным параграфам: ты явно всё не так организовал. во-первых, доступ к объекту должен быть по схеме «pthread_rwlock_rdlock(для очереди)»→«pthread_mutex_(try)lock(для элемента)»→«недеструктивные действия над элементом»→«pthread_mutex_unlock(для элемента)»→«pthread_rwlock_unlock(для очереди)». удаление элемента: «pthread_rwlock_wrlock(для очереди)»→«удаление элемента»→«pthread_rwlock_unlock(для очереди)».

лок для каждого объекта не нужен.

не факт.

да, не вчиталься в схему. если два глобальных использовать (rw) то да, ты прав.

А что за «классическая задача про счёт в банке»?

Данные у тебя - список, а не объекты. Поскольку потоки могут его менять (удалять или добавлять объекты), то блокировать надо весь список.

Не совсем так. Сам по себе список особой роли не играет, функциональную нагрузку несут именно объекты. Вместо линейного списка может быть что угодно, что позволит найти и получить объект по его ID.

Весь список я блокирую с помощью rwlock - объект не будет удален из списка, пока есть активные поиски объекта, и поиск объекта не начнется, пока не будет завершена вставка или удаление объекта из списка. Такой блокировкой я обеспечиваю то, что в списке будут только валидные объекты. Под поиском здесь понимается не только нахождение указателя на объект, но и обеспечение его «свободы». Замечу, что для недопущения deadlock-ов при неудачном захвате объекта блокировка чтения для всего списка освобождается, чтобы дать первому потоку при необходимости применить ко всему списку блокировку записи и удалить объект из списка; только после этого сам объект будет «освобожден» и уничтожен

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

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

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

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

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

сразу возникает вопрос, что на момент pthread_mutex_(try)lock(для элемента)»→«недеструктивные действия над элементом»→«pthread_mutex_unlock(для элемента) не известно, будут ли действи деструктивными или нет. Объект «сам решает», должен ли он быть уничтожен. Другими словами, не возможно определить необходимость уничтожения элемента, не проведя над ним обработку, а для обработки его надо блокировать.

Даже если я как-то смогу определить факт уничтожения потока, существует возможность что при каждом запросе объект будет уничтожаться, таким образом из N-потоков работать будет только 1, так как весь список заблокирован записью.

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

помечать объект флагом «обрабатывается», а потоки, которым нужен объект, который обрабатывается в данное время, блокировать на глобальном семафоре. После того, как обработка закончена, поток обрабатывавший объект будит все остальные потоки, блокированные на семафоре. Один из потоков начинает обрабатывать «свой» объект, остальные блокируются на том же семафоре.

Вообще, по моей оценке, на каждые 7-10 изменений состояния будет приходиться 1 удаление, но это соотношение может существенно изменяться для различных алгоритмов.

Сама задача - это реализация EAP-* протоколов в существующей системе. В объектах хранятся некоторые backend-специфичные данные (MD5, TLS, TTLS и т.п.). Под обработкой подразумевается вызов backend-ов (у каждого объекта он может быть свой). Фактически, объекты соответствуют EAP-сессиям, поэтому и накладываются такие ограничения на блокировку обработки каждой сессии.

По идее, EAP-протокол подразумевает, что не может придти новый запрос, пока не получен ответ на предыдущий, но, во первых, возможна повторная отправка EAP-сообщений (из-за таймаута), а во вторых, оборудование может дать сбой. Поэтому, такие ситуации я вынужден предусмотреть.

> сразу возникает вопрос, что на момент […] не известно, будут ли действи деструктивными или нет.

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

> Другими словами, не возможно определить необходимость уничтожения элемента, не проведя над ним обработку, а для обработки его надо блокировать.

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

последний абзац не распарсил…

Перечитай свой абзац, который про "...и рассматривать задачу с одиночным объектом.". Может лучше меня поймёшь. Повторюсь, вижу только одно решение: использовать один глобальный мутекс. блокировать его перед поиском, разблокировать после обработки/удаления/добавления объекта. Не хочешь тормозов - меняй алгоритм.

Тов. arsi придумал какую-то схему с тремя. Но я не уверен. Я до конца не понял, как она работает.

Интересное решение, чем-то напоминает логику waipid() (по сигналу просыпаются все ожидания, но для не совпадающим pid в sigcld и ожидаемого опять засыпает)

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

В таком подходе наверно как раз подойдет pthread_wait_cond, но я буду посмотреть, спасибо!

А если объёкт удалят во время обработки?

>А если объёкт удалят во время обработки?

Ну поток не нашедший объект с подходящим ID в очереди, завершается, например.

>очереди

в списке конечно же.

tailgunner тебе уже все решение написал. Что тебе еще надо не пойму?

Не получается, например возможна такая ситуация:

1. Поток 1: rdlock(список)

2. Поток 1: trylock(объект) // успешно

3. Поток 1: unlock(очередь) //пока объект обрабатывается, другие объекты могут создаваться/уничтожаться

4. Поток 2: rdlock(список)

5. Поток 2: trylock(объект) //не успешно

6. Поток 2: unlock(список) //другие потоки должны иметь возможность удалять создавать другие объекты пока мы ждем

7. Поток 2: lock(объект) //ждем освобождения объекта

8. Поток 1: объект необходимо уничтожить

9. Поток 1: wrlock(список)

10. Поток 1: удаляем объект из списка

11. Поток 1: unlock(объект)

12. Поток 2: просыпаемся, начинаем повторно искать объект, вдруг он удален?

13. Поток 2: unlock(объект) //FAIL //необходимо освободить захваченный мьютекс

14. Поток 1: уничтожаем объект и мьютекс //FAIL

В этом примере в шаге 13 возникает проблема - имеем заблокированный мьютекс, который надо освобождать (где-нибудб все-равно придется это делать)

Можно между шагами 12 и 13 сделать rdlock(список), тогда Поток 2 ждет, пока Поток 1 не сделает unlock(список), но опять получаем FAIL при освобождении захваченого мьютекса

Значит, либо ждать завершения обработки объекта не мьютексом (а чем?), либо не уничтожать мьютекс (пул, сборщик мусора - плохо и не красиво), либо искать способо не блокировать мьютекс после ожидания (что хочу сделать я)

Не вариант, по условию, поток обязан отработать, в этом случае создать объект, и применить действия к этому объекту

Идентификатор присылает мне оборудование, я его не определяю (например, это идентификатор сессии подключения, вполне вероятно, что оборудование решить продублировать пакет), поэтому я вынужден работать с тем, что у меня есть.

В качестве признака я использую мьютекс. Вариант с переменной-признаком подразумевает цикл до выполнения условия «свобода», критическую секцию на изменение признака, и sleep, что мне категорически не нравится (именно sleep, особенно в плане выбора правильного значения времени ожидания)

> 1. Поток 1: rdlock(список)
> 2. Поток 1: trylock(объект) // успешно
> 3. Поток 1: unlock(очередь)

ты явно не читал, что я раньше тебе написал… с какого перепугу ты освобождаешь очередь, не освободив объект после успешной блокировки? остальные пункты уже не читал, естественно.

Очень просто, обработка может быть длительной, в это время другие объекты могут быть созданы/уничтожены (то есть требуется wrlock), пожтому на время обработки объект необходимо освободить список. Простой пример - сессия в backend обрабатывается 10 сек, в это время пришли 100 запросов, для которых надо создать новый объект со средним временем обработки 0.001 сек. Все это 100 запросов будут ждать, пока я не обработаю самый первый объект и не освобожу очередь (10 сек).

Если освободить список после захвата объекта, то такой задержки не возникает. Замечу, что объекты создаются/уничтожаются постоянно

> Идентификатор присылает мне оборудование, я его не определяю

Я понял. Значит, менять идентификатор запрещено, и у тебя остается только вариант с дополнительным признаком.

Вариант с переменной-признаком подразумевает цикл до выполнения условия «свобода», критическую секцию на изменение признака, и sleep, что мне категорически не нравится (именно sleep, особенно в плане выбора правильного значения времени ожидания)

Весь доступ к этому признаку производится в критической секции (залоченный список).

> в это время другие объекты могут быть созданы/уничтожены (то есть требуется wrlock)

для добавления объекта в конец связного списка wrlock не требуется;

(немедленное) уничтожение объекта не обязательно: 1) его можно повторно использовать; 2) его можно удалить позже.

Да, доступ к этому признаку естественно в критической секции, в этом варианте мне не нравится sleep, потому что можно спать либо слишком долго (падает отзывчивость) либо слишком медленно (увеличивается загрузка цп). И тот и другой вариант одинаково плохи. Предпочтительней наверно второй, но тут я еще буду оценивать, насколько такой подход влияет на функционирование в целом (кроме этих действий система еще общается с базой, пишет логи, обрабатывает не EAP-запросы и т.п.)

> Да, доступ к этому признаку естественно в критической секции, в этом варианте мне не нравится sleep

Я вообще не говорил о sleep. Если тебе нужно оповещение о событиях, используй condvar или несколько.

я еще буду оценивать, насколько такой подход влияет на функционирование в целом

Даже не знаю, смеяться или плакать.

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

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

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

По поводу добавления в конец согласен, вполне достаточно rdlock, надо запомнить. Но если объекты все-таки удалять из списка (даже без их уничтожения), то соответствующие потоки будут ждать, в то время как они могли бы быть заняты чем-нибудь полезным

condvar на каждый объект опять таки требует мьютекс. Создавая мьютекс на каждый объект (а иначе я получаю блокировки, там, где они не нужны), я упираюсь в его уничтожение. Может быть я смотрю не тот man по condvar...

Даже не знаю, смеяться или плакать

пока я не доделал программу, я не могу сказать, насколько тот или иной подход будет влиять на отзывчивость в целом. Программа уже используется, и у каждого клиента разные инстансы могут работать в совсем разных конфигурациях. В случае если 1% будет EAP (что я сейчас пилю), то получится один оверхед, а если 50% то совсем другой. Может быть, я конечно не так понимаю

> condvar на каждый объект опять таки требует мьютекс.

Тебя переклинило на «каждый объект». Не нужно ничего делать «на каждый объект», так делают только идиоты, и даже они быстро упираются в пределы ОС.

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

способ решения задачи тем проще, чем полнее на неё ТЗ. а в данном случае баз гадания на кофейной гуще не обойтись…

> Но если объекты все-таки удалять из списка (даже без их уничтожения), то соответствующие потоки будут ждать, в то время как они могли бы быть заняты чем-нибудь полезным

я уже говорил — нет смысла ждать (можно установить флаг доступности объекта под его же мютексом, например). используй trylock для удалятора; используй отдельный мютекс для удаляторо-алокатора; способов решения — масса, всё зависит от задачи.

До меня начинает потихоньку доходить, что ты хотел до меня донести, буду завтра пробовать. Спасибо за наводку

Спасибо за подсказки, завтра перечитаю все на свежую голову и буду пробовать.