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

Question

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

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

Спасибо!

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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