Стандарты POSIX и семантика семафоров

«... засыпает на секунду, чтобы быть (почти) уверенным, что помощник запустился» — Вы уверены, что помощник действительно запускается в течение этой секунды? Вы могли бы, например. добавьте оператор printf() в функцию helper перед sem_wait и проверьте, действительно ли его сообщение печатается в вашем сценарии.

Ре. "when a thread sem_posts and there is another thread waiting on that semaphore, one of the waiters shall be woken up and allowed to return from sem_wait": где ты это прочитал? Я не вижу этого нигде в предоставленной ссылке POSIX.

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

@Г.М. Если значение семафора, полученное в результате этой операции, равно нулю, то одному из потоков, заблокированных в ожидании семафора, будет разрешено успешно вернуться из вызова sem_wait().

По ссылке: «Если поддерживается опция планирования процессов, разблокируемый поток должен выбираться способом, соответствующим политикам планирования и параметрам, действующим для заблокированных потоков. В случае планировщиков SCHED_FIFO и SCHED_RR самый высокий поток ожидания с наивысшим приоритетом должен быть разблокирован, и если существует более одного потока с самым высоким приоритетом, заблокированного в ожидании семафора, то поток с самым высоким приоритетом, который ожидал дольше всего, должен быть разблокирован. Если опция планирования процессов не определена, выбор поток для разблокировки не указан.».

@wohlstad Но семафора не ожидает несколько процессов.

@Barmar в тексте ссылки упоминаются в основном потоки, а не процессы.

@wohlstad Такая же разница. В то время sem_post() называется, там только один официант.

@Barmar Хорошо, меня смутило использование ОП термина «другой» - я, очевидно, слишком много читал о том, чего там не было :-)

@Бармар, я согласен. Я просто привел цитату из ссылки для дополнительной информации. Но как вы объясните поведение, наблюдаемое ОП?

@Oka: Добавление return NULL; ничего не меняет в моих тестах. Я добавил его в код в вопросе. Надеюсь, это облегчит вам рассуждения :-)

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

@Barmar В то время sem_post() называется, есть только один официант Но теперь вам нужно точно определить «в то время».

@AndrewHenle Прочтите мой ответ и обратите особое внимание на последний абзац о правиле «как если бы», которое допускает подобную оптимизацию.

@Barmar Правило «как если бы» здесь совершенно не нужно - дочерний поток запускается, переходит в sem_wait() и засыпает, ожидая семафора. Родительский поток делает это в течение 1 секунды sleep(), просыпается, а затем БАМ-БАМ вызывает sem_post() и sem_wait() в быстрой последовательности, в то время как дочерний поток все еще находится в глубоком сне, заблокированный на семафоре. К тому моменту, когда ядро ​​сможет проверить состояние семафора, в нем уже заблокированы два потока. Дочерний поток находится в глубоком сне, родительский поток активен и работает. Угадайте, кому достается семафор? Ожидание здесь просто ошибочно.

@AndrewHenle Все понимают, что спецификация описывает что-то синхронное: внутри sem_post() она проверяет, есть ли заблокированные потоки sem_wait(), немедленно разблокирует их и не возвращается, пока не сделает это. Так что никакого БАМ-БАМа быть не должно. Я хочу сказать, что вы не можете различить эти два случая, потому что невозможно узнать, заблокирован ли первый поток.

@Barmar (продолжение) Похоже, это ожидание основано на убеждении, что существует такая вещь, как «X в потоке A происходит раньше Y в потоке B» при отсутствии каких-либо явных вызовов объектов синхронизации потоков. Таких отношений просто не существует.

@ЭндрюХенле; Проблема, которую меня вызывает эта теория, заключается в том, что спецификация, похоже, подразумевает, что проверка состояния семафора и разблокировка заблокированного процесса, если таковой имеется, выполняются до возврата sem_post.

@NateEldredge «Разрешено вернуться» не означает «немедленно возвращается».

@AndrewHenle: sem_post определяется как операция синхронизации, см. pubs.opengroup.org/onlinepubs/9699919799/basedefs/….

@NateEldredge Он синхронизирует память: «Следующие функции синхронизируют память относительно других потоков». Требований к порядку выполнения нет, только «одному из потоков, заблокированных в ожидании семафора, должно быть разрешено успешно вернуться из своего вызова в sem_wait(). ...выбор потока для разблокировки не указан».

@AndrewHenle: Но во время выполнения sem_post основной поток определенно не блокируется в sem_wait, поэтому его нет среди потоков, которые можно выбрать. Таким образом, чтобы объяснить поведение в соответствии со стандартом, либо мы должны допустить, чтобы операции, описанные для sem_post, происходили не синхронно с его выполнением (что неявно имеет место для всех других системных вызовов), а асинхронно в более позднее время; или, как предполагает Бармар, во время выполнения sem_post нет заблокированных потоков, ожидающих семафора.

@AndrewHenle: Я имею в виду, что когда вы читаете описание, скажем, mkdir(2), вы понимаете, что описываемые им операции выполняются синхронно с вызовом и видны по всей системе до того, как вызов вернется. Каталог создается сейчас, а не где-нибудь на следующей неделе. Кажется, вы предполагаете, что sem_post каким-то образом не подчиняется тому же принципу.

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

@NateEldredge Определите «синхронно» между потоками, когда сигналу, что поток A вызвал sem_post(), не хватает времени даже на скорости, близкой к скорости света, чтобы добраться до потока B до того, как поток A будет заблокирован в sem_wait().

@JoshLevi Вы пытаетесь навязать свое представление о времени в макромире системам, измеряемым в нанометрах и рассчитанным на наносекунды, где термин «одно и то же время» имеет абсолютно нулевое значение.

@NateEldredge Основной поток, работающий в режиме ядра, просто должен будет уменьшить семафор и пометить вспомогательный поток как работоспособный... Вы полностью не учитываете, что к тому времени, когда ядро ​​увидит, какой поток следует активировать, основной поток уже заблокирован в sem_wait() и все еще «горячий» и вполне работоспособен. Таким образом, выбор между «горячим» недавно запущенным потоком, готовым к работе, и «холодным» потоком (или потоками), находящимся в глубоком сне, даже если они помечены как работоспособные, сделать несложно. «Выбор потока для разблокировки не указан».

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

Что касается предполагаемого «требования» разбудить ожидающий поток до возвращения sem_post()? Как?!? Пометьте каждую ожидающую цепочку надписью «Вы можете меня разбудить!» пометить тег, чтобы темы, которые вызывают sem_wait() «после» вызова sem_post() «произошло», не просыпались? Итак, как же это сделать, если два потока вызывают sem_post() «одновременно»? Опять же — «одновременно» не имеет никакого значения — потоки выполняются быстрее, чем могут распространяться состояния.

Linux не совместим с POSIX, поэтому семантика семафоров POSIX может быть реализована не в соответствии с нормой.

Это действительно возможное объяснение. +1. Хотя я должен признать, что в этом сценарии [по крайней мере, по умолчанию] я ожидал, что помощник будет разбужен (и семафор будет более «справедливым»). Однако поведение, о котором сообщает ОП, воспроизводимо, по крайней мере, в Godbolt — насколько это актуально. Я даже добавил printf, чтобы убедиться, что помощник запустился и вернулся из вспомогательной функции (чтобы избежать UB).

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

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

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

Правило «как если бы» позволяет ему действовать так, как будто первый поток еще не вызвал «sem_wait()». В этом случае он просто увеличивает семафор и немедленно возвращает результат.

@NateEldredge, но если это так (эффекты должны быть видны), почему помощником не является пробудившийся поток? В моем тесте он наверняка запускался и вызывал sem_wait, и поэтому, когда sem_post выполняется, он должен быть единственным, кто ждет и, следовательно, пробуждается. Не так ли?

@wohlstad: Да, именно поэтому я тоже подумал, что наблюдаемое поведение незаконно. Но Бармар считает, что мы не можем доказать, что вспомогательный поток действительно блокируется sem_wait при вызове sem_post; все, что мы наблюдаем, также согласуется с возможностью того, что помощник застопорился непосредственно перед вызовом sem_wait. (С другой стороны, strace показывает, что помощник фактически заблокирован sem_wait — но я думаю, что это не совсем «наблюдаемое поведение».)

@NateEldredge Я вижу, может быть.

Это оптимизация, которая уменьшает накладные расходы на планирование. Многие оптимизации основаны на правиле «как если бы».

Даже добавление printf() в функцию helper() не предотвращает этого. Цепочка может остановиться между printf() и sem_wait().

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

@JoshLevi Потому что правило «как если бы» означает, что это не имеет значения, если вы не сможете это доказать.

@barmar Что именно вы подразумеваете под «когда планировщик принимает решение, какой поток разблокировать?» В большинстве случаев этот код производит ровно нулевое количество непроизвольных переключений контекста, поэтому планировщик вообще не участвует. Семафоры могут использовать системные вызовы для блокировки потоков, но они реализованы в пользовательском пространстве.

@JoshLevi Я предполагал, что семпаоры реализованы в ядре.

@Бармар, ну ты ошибаешься и не вник в суть моего вопроса

Я подумал: «В какой ситуации несправедливый семафор будет предпочтительнее?» была суть вопроса. Ситуация заключается в минимизации переключений контекста.

Можете ли вы предоставить источник, подтверждающий, что это действительно было причиной?

соответствует ли такое поведение спецификации POSIX?

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

Кажется, я уже несколько раз отвечал на вопрос «разрешено ли это».

ок, я понимаю суть. но не могли бы вы прочитать, заблокировано ли состояние потока из чего-то вроде /proc/? или это не считается «наблюдаемым поведением»?

@JoshLevi Я не думаю, что просмотр /proc или использование strace считается. Спецификации написаны с точки зрения абстрактного поведения, они рассматривают детали реализации низкого уровня.

@JoshLevi Ваше ожидание того, что вы сможете зависеть от того, в какой нити sem_post() просыпается от sem_wait(), нереально. В отсутствие явной синхронизации в вашем коде просто не существует связи «X происходит в потоке A раньше, чем Y происходит в потоке B». Период. И в этом конкретном случае у вашего дочернего потока нет возможности синхронизировать тот факт, что он заблокирован в семафоре, с другими потоками - потому что он заблокирован в семафоре. Вызов синхронизации любого типа, который говорит: «Меня скоро заблокируют в семафоре!» не работает.

Что касается чтения /proc, это ошибка TOCTOU, ожидающая своего часа - это говорит о том, что поток был заблокирован в семафоре.

@AndrewHenle TOCTOU обычно относится к чему-то, что вызывает неожиданное изменение состояния между T и T. Но если вы ожидаете изменения состояния, а этого не происходит, это не ошибка TOCTOU.

хм. Итак, означает ли все это, что «набор потоков, ожидающих семафора», не является наблюдаемой/четко определенной концепцией? в таком случае, что вообще будет означать, что семафор будет «справедливым», если мы можем предположить, что все потоки находятся в точке «непосредственно перед» sem_wait?

Гарантируется ли где-нибудь справедливость? С чего вы взяли, что это должно быть справедливо?

Согласитесь, нигде это не гарантировано. Но, например, в документе по семафорам Java говорится, что семафоры могут быть либо «справедливыми», либо нет. Однако, согласно семантике «как если бы», существует ли заметная разница между ними?

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

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

так типа, если бы они были честными, мы бы чаще видели «помощник проснулся»? в любом случае я думаю, что вы помогли мне лучше понять ситуацию. Спасибо!

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