============================================
Идея: порционное чтение приоритетной очереди
============================================

:Author: Евгений Охотников
:Contact: eao197 at intervale dot ru; eao197 at yahoo dot com
:Version: 0.1
:Date: 2008.12.27

.. _SObjectizer: http://sobjectizer.sourceforge.net

.. contents:: **Оглавление**

Мотивация
=========

В 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`` будет
происходить крайне редко. Для некоторых рабочих нитей это значение вообще не
будет никогда изменяться, т.к. работающие на этих нитях агентов не будут
использовать приоритетов событий, отличных от нуля. *Возможно, это уже наметки
для какой-то следующей идеи...*

.. vim:ts=2:sw=2:sts=2:expandtab:tw=78:ft=rst: