Планирование процессов, ожидающих семафор

Question

Всегда говорится, что когда счетчик семафора равен 0, процесс, запрашивающий семафор, блокируется и добавляется в очередь ожидания.
Когда какой-то процесс освобождает семафор, и число увеличивается с 0-> 1, активируется процесс блокировки. Это может быть любой процесс, случайно выбранный из заблокированных процессов.

Теперь мой вопрос:
Если они добавляются в очередь, почему активация блокирующих процессов НЕ выполняется в порядке FIFO? Я думаю, что было бы легко выбрать следующий процесс из очереди, а не выбрать случайный процесс и предоставить ему семафор. Если за этой случайной логикой стоит какая-то идея, пожалуйста, объясните. Кроме того, как ядро ​​случайным образом выбирает процесс из очереди? получение случайного процесса, который тоже из очереди, является чем-то сложным с точки зрения структуры данных очереди .
теги: различные ОС , каждая из которых имеет ядро ​​, обычно написанное на C ++ и mutex , имеет сходную концепцию

Answer 1

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

Answer 2

Все остальные ответы здесь являются отличным описанием основной проблемы - особенно в отношении приоритетов потоков и готовых очередей. Однако следует учитывать и IO. Я говорю здесь только о Windows, так как это единственная платформа, которую я знаю с какими-либо полномочиями, но другие ядра, вероятно, будут иметь аналогичные проблемы.

В Windows, когда IO завершается, то, что называется APC в режиме ядра (асинхронный вызов процедуры), ставится в очередь против потока, который инициировал IO, чтобы завершить его. Если поток находится в ожидании объекта планировщика (например, семафора в вашем примере), то поток удаляется из очереди ожидания для этого объекта, что приводит к тому, что ожидание (внутренний режим ядра) завершается (что-то вроде) STATUS_ALERTED. Теперь, поскольку эти APC в режиме ядра являются подробностями реализации, и вы не можете видеть их в пользовательском режиме, реализация ядра WaitForMultipleObjects перезапускает ожидание в этой точке, что приводит к выталкиванию потока в конец очереди. С точки зрения режима ядра очередь по-прежнему находится в порядке FIFO, поскольку первый вызывающий API-интерфейс ожидания по-прежнему находится во главе очереди, однако, с вашей точки зрения, в пользовательском режиме вас просто подталкивают к задняя часть очереди из-за чего-то, что вы не видели и, возможно, не имели никакого контроля. Это заставляет порядок очереди казаться случайным из пользовательского режима. Реализация по-прежнему является простым FIFO, но из-за ввода-вывода она не похожа на более высокую степень абстракции.

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

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

Answer 3

Когда процесс запланирован «наугад», дело не в том, что процесс выбран случайным образом; дело в том, что процесс выбора непредсказуем.

Алгоритм, используемый ядрами Windows, заключается в том, что существует очередь потоков (Windows планирует «потоки», а не «процессы»), ожидающих семафор. Когда семафор освобождается, ядро ​​планирует следующий поток, ожидающий в очереди. Однако планирование потока не сразу заставляет этот поток начать выполнение; это просто делает поток способным к выполнению, помещая его в очередь потоков, ожидающих запуска. На самом деле поток не будет работать до тех пор, пока у ЦП не будет потоков с более высоким приоритетом для выполнения.

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

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

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

Answer 4

Это не значит, что это не может быть FIFO;на самом деле, я бы поспорил, что многие реализации являются АРЕ, только по причинам, которые вы заявляете.Спецификация не в том, что процесс выбран случайным образом;это то, что она не указана, поэтому ваша программа не должна полагаться на то, что она выбрана каким-либо особым образом.(Это МОЖЕТ быть выбрано случайным образом; просто потому, что это не самый быстрый подход, не означает, что это невозможно сделать.)

Answer 5

Эта статья охватывает вашу тему: http://www.codeguru.com/cpp/w-d/dislog/win32/article.php/c9823

Answer 6

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

Что касается случайного выбора, мотивация может быть по разным причинам.Одна из них - попытка получить хорошую пропускную способность и т. Д., Как указано выше.Однако это было бы недетерминировано (гипотетически) и невозможно доказать.Это свойство может быть использование вероятности (случайные выборки и т. Д.), Но, опять же, доказательства могут быть основаны только на эмпирических данных о том, будет ли это действительно работать.