Семафорные очереди

Question

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

Я знаю, что семафор работает, блокируя потоки, которые ожидают его, когда они вызывают sem_wait (), и другой поток в настоящее время заблокировал его. Затем поток блокируется и помещается в список ожидания для этого семафора.

Мой вопрос касается того, что происходит с sem_post (). Будет ли следующий поток удален из списка ожидания, установлен как поток блокировки и разрешен ли его разблокировка? Или схема публикации совершенно другая?

Спасибо!

Answer 1

Следующим потоком, который будет разблокирован на его sem_wait(), будет любой поток, который, по мнению ОС, будет следующим, в который будет переключаться контекст. Никто не дает никаких гарантий заказа; это зависит от стратегии планирования вашей ОС. Это может быть поток, который долгое время находился вне ЦП, или тот, которому был присвоен самый высокий «приоритет», или тот, который исторически имел определенную статистику использования ресурсов, или любой другой.

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

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

Answer 2

Семафоры имеют две операции:

1. P() Чтобы получить семафор (кажется, вы называете это sem_wait)
2. V() Чтобы освободить семафор (вы, кажется, называете это sem_post)

Семафорам также присвоено целое число, которое является числом одновременных потоков, которым разрешено передавать P () без блокировки. Другие вызовы P () будут блокироваться до тех пор, пока не будет вызван V () для освобождения мест.

Это классическое определение семафора.

Редактировать: Семафоры не дают никаких гарантий заказа. Им не нужно фактически использовать очередь или другую структуру FIFO. Когда одновременно разрешен только один поток, когда он вызывает V (), другой (возможно, случайный) поток вернется из своего вызова P () и продолжит.