Реализация приоритетной очереди с условной переменной в C

Question

Мое нынешнее понимание переменных условий заключается в том, что все заблокированные (ожидающие) потоки вставляются в базовую очередь FIFO, первый элемент которой пробуждается при вызове signal().

Есть ли способ изменить эту очередь (или создать новую структуру), чтобы она работала в качестве приоритетной очереди?Я думал об этом некоторое время, но большинству решений, которые я нашел, в конечном итоге мешала существующая структура очередей, присущая C.V. и мьютексам.

Спасибо!

Answer 1

Я думаю, тебе следует переосмыслить то, что ты пытаешься сделать.Если вы пытаетесь оптимизировать свою производительность, вы, вероятно, лаете не по тому дереву.

pthread_cond_signal() даже не гарантированно разблокирует ровно один поток — он гарантированно разблокирует по меньшей мере один поток, чтобы ваш код лучше справлялся с ситуацией, когда несколько потоков разблокируются одновременно.Типичный способ сделать это — каждый поток повторно проверяет условие после разблокировки и, если оно ложно, снова возвращается к ожиданию.

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

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

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

Answer 2

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

С помощью комбинации атомов, дополнительных переменных условий и предварительного знания задействованных потоков/приоритетов вы можете создать решение, в котором сигнальный поток будет повторно сигнализировать главное CV, а затем повторно блокировать приоритетное CV, но это, конечно, не будет. Это общее решение.Это тоже не пришло мне в голову, так что может быть еще какой-то недостаток.

Answer 3

Планировщик определяет, какой поток будет запущен.Вы можете посмотреть pthread_setschedparam и pthread_getschedparam и возиться с политикой(SCHED_OTHER, SCHED_FIFO, или SCHED_RR) и приоритеты.Но это, вероятно, не приведет вас туда, куда, как я подозреваю, вы хотите попасть.

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