пятница, 28 марта 2008 г.

Многопоточность и свойства. Часть 1

В однопоточном мире есть очень многие вещи, о которых мы даже не задумываемся. Например, в онлайн-игре вполне приемлемо такое описание здоровья «живого объекта» (NPC или игрока) на C#:


public int Health
{
get { return m_health; }
set { m_health = value; }
}

Когда наносится повреждение, следующий код вполне логичен:

int damage = 100;
target.Health -= damage;

if (target.Health <= 0)
{
target.Die();
}

Т.е. мы вычитаем значение здоровья, затем сверяем, жива ли цель. Время идет, онлайн растет, процессоры дешевеют. Теперь у нас уже несколько многоядерных процессоров, тысячные онлайны, большая нагрузка. В этом свете один поток обработки выглядит архаичным и будет рано или поздно превращен в несколько конкурирующих потоков.
Если оставить указанный код без изменений в многопоточной модели, мы рано или поздно получим неприятные неожиданности. Чтобы было удобнее воспринимать, я преобразую работу со свойствами так, как делает это компилятор, но оставлю эту часть в формате C#:

int damage = 100;
int tmpHealth = target.get_Health();
target.set_Health(tmpHealth - damage);
if (target.get_Health() <= 0)
{
target.Die();
}


Расписывать, почему Health -= превратилось в такого монстрика, тут я не буду – читайте Рихтера, MSDN. Гораздо важнее то, что в этих нескольких строках кода у нас несколько проблем синхронизации. Распишу в виде таблицы несколько вариантов развития событий с двумя потоками, которые одновременно пытаются сделать такую операцию. Для удобства скажем, что значение m_health изначально было равно 150, а damage для наших потоков 100 и 200 соответственно.

Вариант 1

Поток 1Поток 2
int tmpHealth = target.get_Health();
значение tmpHealth = 150
int tmpHealth =target.get_Health();
значение tmpHealth = 150
target.set_Health(tmpHealth - damage);
значение m_health = 50
target.set_Health(tmpHealth - damage);
значение m_health = -50
if (target.get_Health() <= 0)
{
    target.Die();
}
условие истинно, т.к. m_health уже -50,
вызывается target.Die()
if (target.get_Health() <= 0)
{
    target.Die();
}
условие истинно, вызывается target.Die()


Вариант 2


Поток 1Поток 2
int tmpHealth = target.get_Health();
значение tmpHealth = 150
target.set_Health(tmpHealth - damage);
значение m_health = 50
int tmpHealth = target.get_Health();
значение tmpHealth = 50
target.set_Health(tmpHealth - damage);
значение m_health = -150
if (target.get_Health() <= 0)
{
    target.Die();
}
условие истинно, вызывается target.Die()
if (target.get_Health() <= 0)
{
    target.Die();
}
условие истинно, т.к. m_health = -150,
вызывается target.Die()


Вариант 3

Поток 1Поток 2
int tmpHealth = target.get_Health();
значение tmpHealth = 150
int tmpHealth = target.get_Health();
значение tmpHealth = 150
target.set_Health(tmpHealth - damage);
значение m_health = -50
target.set_Health(tmpHealth - damage);
значение m_health = 50
if (target.get_Health() <= 0)
{
    target.Die();
}
условие ложно, т.к. m_health = 50
if (target.get_Health() <= 0)
{
    target.Die();
}
условие ложно


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

public int Health
{
get
{
lock (m_healthLock)
return m_health;
}
set
{
lock (m_healthLock)
m_health = value;
}
}

Но подобная блокировка не даст ничего, кроме строго указанного порядка записей/чтений, что в нашей задаче ничего не изменит. Правильным будет окружить сам метод блокировкой и двойной проверкой:

if (target.Health > 0)
lock (taget.HealthLock)
if (target.Health > 0)
{
int damage = 100;
target.Health -= damage;

if (target.Health <= 0)
{
target.Die();
}
}

Такой подход дает оптимальный результат, но влечет значительные изменения кода, а также работу с CriticalSection (вместе с ThinLock в .Net 2.0 и выше) при каждом обращении.
Конечно, было бы легче, если бы мы пользовались С++, а метод для получения здоровья возвращал ссылку или указатель, но подобных стандартных механизмов в C# нет (unsafe и указатели мы пока опустим). Также было бы проще, если бы Health было не свойством (property), а полем (field). В таком случае, мы бы поступили так:

int damage = 100;
if (Interlocked.Add(ref target.Health, -damage) > 0)
{
target.Die();
}

Атомарная операция Interlocked.Add обеспечит нам выполнение вычитания без вмешательства других потоков, а также вернет старое новое значение переменной. Таким образом, мы без проблем сможем узнать, было ли именно это повреждение смертельным.
Мы отошли от принципов «красивого программирования» ради дополнительной производительности. В большей части случаев такой вариант приемлем, но у свойств есть еще одно полезное свойство – они могут быть виртуальными.
Например, в базовой реализации «живого объекта» мы имеем всю ту же работу с переменной:

public virtual int Health
{
get { return m_health; }
set { m_health = value; }
}

А в наследнике, реализующем игрока, запись уже идет в объект БД:

public override int Health
{
get { return m_dbCharacter.Health; }
set { m_dbCharacter.Health = value; }
}

Перейти к Interlocked методам в этом случае будет проблематично, потому самым разумным вариантом будет в таком случае перестать пользоваться свойством set напрямую (например, объявить его как protected в .Net 3.5) и сделать отдельный метод для изменения здоровья объекта:

void ModifyHealth(int value)
{
if (Health > 0)
lock (m_healthLock)
if (Health > 0)
{
Health += value;

if (Health <= 0)
{
Die();
}
}
}

Хотелось бы использовать атомарные методы и в этой ситуации, но это уже проблематично, т.к. m_dbCharacter.Health в свою очередь вполне может быть свойством.
Наиболее производительным решением будет отказаться от виртуальности в таких свойствах, а объект БД обновлять в ключевых точках (при выходе из игры, при смерти и т.п.). Наиболее правильным решением будет отказ от использования публичных сеттеров для свойств, которые могут быть использованы в разных потоках. Разумным людям я советую остановиться на одном из этих вариантов. Остальным же (любителям нестандартных решений и «крестовых походов») я предложу несколько своих вариантов решения в следующих статьях на эту тему.


Update 03.04.08: Interlocked.Increment/Interlocked.Decrement не имеют второго параметра. Правильно пользоваться Interlocked.Add. Если кого сбил с толку - извиняюсь, самого бес попутал

Update 04.04.08: В ходе испытаний оказалось, что Interlocked.Add возвращает не старое, а новое значение. Это я проворонил, каюсь.

4 коммент.:

iLych комментирует...

"Конечно, было бы легче, если бы мы пользовались С++, а метод для получения здоровья возвращал ссылку или указатель, но подобных стандартных механизмов в C# нет (unsafe и указатели мы пока опустим)."
Если так хочется ссылку - что мешает завернуть переменную в класс?

Nomad комментирует...

Этот вопрос я думаю обсуждать в следующей статье. Навскидку, если у нас около 20 свойств (на самом деле больше 300 бывает) у каждого плеера и всего 2000 плееров в онлайне, это означает 40000 вспомогательных классов. А если учитывать еще 100000 NPC c 10ю подобными свойствами у каждого, выйдет еще миллион классов на ровном месте. А т.к. они живут столько же, сколько и сами NPC, это подопечные 2й генерации.

iLych комментирует...

Я имел ввиду просто вместо int ( или что-именно там требуется ) Сделать

CInt - с нужным набором операций ( например просто продублировать int'овые )

CInt a;
...
CInt b = a;

b - будет ссылкой на объект a, то есть можно будет воплотить "метод для получения здоровья возвращал ссылку или указатель"

Я не имел ввиду классы типа

CHealth, CMana, COneHandedSwordSkill... :)

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

Я так понимаю в следующей статье будет что-то по этому поводу - буду ждать. Может и в моем варианте подвохи есть, а может их и больше чем тут.

Nomad комментирует...

Я и говорю об экземплярах. В памяти это будут полноценные объекты, с виртуальной таблицей, наследованием от System.Object, отдельной записью в GC, счетчиком ссылок. Оптимизатор в лучшем случае сами операции добавления/вычитания заинлайнит, а тысячи экземпляров будут висеть в памяти, обрабатываться по общим правилам, дефрагментироваться и попадать в Gen 2 сборку мусора, т.к. их родители живут от нескольких минут до часов.
Но есть еще несколько вариантов, которые надо будет проверить. Распишу, когда проведу необходимые тесты.