Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, kotalex, Вы писали:

K>> В основе futex идёт (первым аргументом) адрес некоторой переменной (назовём её 'A' в некотором "подопытном" процессе). Далее внутри реализации происходит преобразование адреса переменной из "пользовательского пространства" в физический адрес (это нужно для shared операций между процессами). Далее, от полученного адреса вычисляется 32 битный хэш (так называемый jhash2). Затем вычисляется индекс: от полученного значения берётся маска, что-то типа ( hash & ((1<<20) — 1 ) ). Значение этой маски сильно зависит от системы (настроек, количества процессоров), но обычно она не превышает 1 МБ. Полученный индекс используется для индексации в глобальной таблице, описывающей все futex-объекты.

W>Вот до этого места правильно описывается одна из возможных реализаций, но дальше идёт просто фееричная чушь:

K>>В итоге, если есть в системе какой-либо другой процесс, у которого есть своя переменная 'B' и индекс, подсчитанный от этой переменной совпадёт с индексом переменной 'A' и "выставится событие" по переменой 'B' — то выставится это-же событие и для переменной 'A', т.е. для неё ('A') произойдёт "ложное пробуждение". Вероятность данного явления небольшая, но всё-же есть.

W>То что несколько фьютексов могут отображаться в один бакет таблицы никак не делает их зависимыми. Они (как и в любой нормальной хеш-таблице без открытой адресации) просто будут оба лежать в одном бакете. Это хеширование с цепочками называется.
W>Вот в ядре linux есть функция match_futex, которая используется во всех операциях обхода бакета как раз для того, чтобы отфильтровать фьютексы попавшие в него из-за коллизий.

W>То есть тут даже не важно что используется: хеш-таблица, какое-нибудь дерево поиска, или вообще единственная глобальная очередь на всё ядро. Различия будут в производительности (очевидно, глобальная очередь будет медленновато работать из-за параллельных локов), но не в семантике операций.

W>---

W>Да и вообще, даже если допустить, что ядро не имеет возможностей отличить где чей фьютекс находится, а сравнивает их только по хешу, то тогда невозможно было бы реализовать функции вроде pthread_cond_signal, которые будят ровно один тред, а не все. Ведь вызов pthread_cond_signal мог бы разбудить своего доппельгангера (для которого бы это пробуждение выглядело как spurious wakeup), и, соответственно, не разбудить поток ожидающий на целевом фьютексе. А это, внезапно, куда большая проблема: в системе образовался поток, которому не дошел сигнал пробуждения и который завис навечно (если конечно, ещё раз не произойдёт чудо и не придёт сигнал на пробуждение от какого-то третьего неудачника с совпавшим хешом ). Вы регулярно наблюдаете такие зависшие потоки? А знаете почему нет?

W>Призываю не верить объяснению kotalex — оно прикольное, но совершенно неверное.

Вот в ядре linux есть функция match_futex, которая используется во всех операциях обхода бакета как раз для того, чтобы отфильтровать фьютексы попавшие в него из-за коллизий

Да, есть такая функция, которая используется во всех операциях обхода бакета. Можно ссылку на код, который используется именно для отфильтровывания "коллизийных" фьютексов ?

Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, kotalex, Вы писали:

K>> В основе futex идёт (первым аргументом) адрес некоторой переменной (назовём её 'A' в некотором "подопытном" процессе). Далее внутри реализации происходит преобразование адреса переменной из "пользовательского пространства" в физический адрес (это нужно для shared операций между процессами). Далее, от полученного адреса вычисляется 32 битный хэш (так называемый jhash2). Затем вычисляется индекс: от полученного значения берётся маска, что-то типа ( hash & ((1<<20) — 1 ) ). Значение этой маски сильно зависит от системы (настроек, количества процессоров), но обычно она не превышает 1 МБ. Полученный индекс используется для индексации в глобальной таблице, описывающей все futex-объекты.

W>Вот до этого места правильно описывается одна из возможных реализаций, но дальше идёт просто фееричная чушь:

K>>В итоге, если есть в системе какой-либо другой процесс, у которого есть своя переменная 'B' и индекс, подсчитанный от этой переменной совпадёт с индексом переменной 'A' и "выставится событие" по переменой 'B' — то выставится это-же событие и для переменной 'A', т.е. для неё ('A') произойдёт "ложное пробуждение". Вероятность данного явления небольшая, но всё-же есть.

W>То что несколько фьютексов могут отображаться в один бакет таблицы никак не делает их зависимыми. Они (как и в любой нормальной хеш-таблице без открытой адресации) просто будут оба лежать в одном бакете. Это хеширование с цепочками называется.
W>Вот в ядре linux есть функция match_futex, которая используется во всех операциях обхода бакета как раз для того, чтобы отфильтровать фьютексы попавшие в него из-за коллизий.

W>То есть тут даже не важно что используется: хеш-таблица, какое-нибудь дерево поиска, или вообще единственная глобальная очередь на всё ядро. Различия будут в производительности (очевидно, глобальная очередь будет медленновато работать из-за параллельных локов), но не в семантике операций.

W>---

W>Да и вообще, даже если допустить, что ядро не имеет возможностей отличить где чей фьютекс находится, а сравнивает их только по хешу, то тогда невозможно было бы реализовать функции вроде pthread_cond_signal, которые будят ровно один тред, а не все. Ведь вызов pthread_cond_signal мог бы разбудить своего доппельгангера (для которого бы это пробуждение выглядело как spurious wakeup), и, соответственно, не разбудить поток ожидающий на целевом фьютексе. А это, внезапно, куда большая проблема: в системе образовался поток, которому не дошел сигнал пробуждения и который завис навечно (если конечно, ещё раз не произойдёт чудо и не придёт сигнал на пробуждение от какого-то третьего неудачника с совпавшим хешом ). Вы регулярно наблюдаете такие зависшие потоки? А знаете почему нет?

W>Призываю не верить объяснению kotalex — оно прикольное, но совершенно неверное.

Вот в ядре linux есть функция match_futex, которая используется во всех операциях обхода бакета как раз для того, чтобы отфильтровать фьютексы попавшие в него из-за коллизий

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