Мотивация

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

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

Идея

Идея базируется на том, что в подавляющем большинстве случаев в SObjectizer используются равноприоритетные заявки, a отличные от нуля приоритеты в моей работе встречаются крайне редко. Поэтому рабочая нить может перемещать заявки из основной очереди в свою локальную очередь, а затем выбирать их из своей локальной очереди уже без захвата мутекса. Но при этом проверять, не появилась ли в основной очереди заявка с более высоким приоритетом.

Для этого заводится специальная volatile переменная highest_demand_priority. В нее помещается наивысший приоритет заявок, которые сейчас находятся в рабочей очереди. Рабочая нить перед извлечением очередной заявки из своей локальной очереди читает содержимое highest_demand_priority и:

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

Т.е. работа с очередями заявок выглядит следующим образом.

При постановке заявки в основную очередь:

захватывается мутекс основной очереди;
заявка помещается в основную очередь;
если заявка помещена в голову очереди:
  # Т.е. заявка имеет приоритет выше, чем
  # предыдущий максимальный приоритет заявок в очереди.
  атомарное присваивание highest_demand_priority максимума из основной очереди;
мутекс основной очереди освобождается.

При извлечении следующей заявки рабочей нитью:

если локальная очередь заявок не пуста:
  если highest_demand_priority выше, чем минимум в локальной очереди:
    захватывается мутекс основной очереди;
    заявки из основной очереди переносятся в локальную очередь;
    атомарное присваивание highest_demand_priority минимума из локальной очереди;
    мутекс основной очереди освобождается;
иначе
  # Локальная очередь заявок пуста и нужно обращение
  # к основной очереди.
  захватывается мутекс основной очереди;
  если основная очередь пуста:
    рабочая нить засыпает на событии добавления заявки в очередь;
    # После срабатывания этого события мутекс основной
    # очереди вновь окажется захваченным рабочей нитью.
  заявки из основной очереди переносятся в локальную очередь;
  атомарное присваивание highest_demand_priority минимума из локальной очереди;
  мутекс основной очереди освобождается;
# К этому моменту локальная очередь не может быть пустой.
из локальной очереди заявок извлекается первая заявка;

Соображения

Привлекательность идеи состоит в том, что при извлечении очередной заявки из локальной очереди заявок будет производится одно атомарное чтение highest_demand_priority. Что не должно быть дорого на современных процессорах семейства x86. А обновление highest_demand_priority будет происходить крайне редко. Для некоторых рабочих нитей это значение вообще не будет никогда изменяться, т.к. работающие на этих нитях агентов не будут использовать приоритетов событий, отличных от нуля. Возможно, это уже наметки для какой-то следующей идеи...