Как использовать V, чтобы разбудить обозначенный P?

Question

Предположим, у нас есть семафор s, и есть несколько потоков, ожидающих его, вызывая P (s). Тогда V (s) разбудит ровно одну нить среди них. Есть ли способ разбудить назначенный поток вместо того, чтобы система принимала решение? Например, в проблеме парикмахерской после каждой стрижки парикмахер хочет обслужить самого долгого клиента, а не случайного.

Answer 1

Зависит от реализации семафора. Вы должны будете использовать умный семафор, который создает очередь ожидающих потоков и сигнализирует их в правильном порядке. Я думаю, что обычная реализация семафора в Windows не работает таким образом. Он просто отправляет сигнал ОС, которая, в свою очередь, отправляет сигнал любому из ожидающих потоков. Было бы даже целесообразно использовать стек Lifo, потому что он реализован проще. Но это не составит труда создать самостоятельно, создав очередь, которая может быть связанным списком или циклическим массивом.

Answer 2

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

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

Answer 3

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

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