LINUX.ORG.RU

Как правильно сделать синхронизацию массива между pthread'ами?


0

1

Задача из области gamedev.

Есть сервер, который шлет через Message Queues обновления карты процессам-клиентам
(на каждый процесс - отдельная очередь с идентификатором через ftok()).
Среди обновлений карты рассматривается событие лишь одного типа -
с карты исчез объект. При этом, клиентам приходит соответствующее
сообщение с кодом REMOVE_OBJECT. После этого клиентам следует сменить
один байт карты (так как каждый объект занимает один байт).

Обработка (прием) этих сообщений выполянется в каждом клиенте - одной нитью (pthread),
и используется двумя другими нитями (обработка действий игрока и отображение карты).
Как сделать, чтобы вторая и третья нити (которые используют измененную карту),
всегда использовали актуальные значения карты?
Карта типа unsigned char[] изменяется за один раз (одно сообщение) - на один байт (x,y).

P.S. Когда-то при программировании (в 90-е) годы, помню, использовали
префикс volatile. Можно ли его применить в данном случае к массиву map[], и - нужно ли?

Блокировки через mutex, я там понимаю, тоже здесь - бессмысленны?

★★★★★

правильный ответ - Erlang

капча: function axcha

anonymous
()

> Карта типа unsigned char[] изменяется за один раз (одно сообщение) - на один байт (x,y).


Если у тебя гаранитрованно маленькое количество изменений за один игровой тик - тебе вообще не нужны три карты тебе нужна одна, а изменения надо вносить на обработке тика.

LamerOk ★★★★★
()

гугли про readers/writers problem

yoghurt ★★★★★
()

Хм. Следует на каждой итерации в каждом треде делать pthread_rwlock_ (она есть не всегда, но ее можно либо самому реализовать либо откуда-то вытащить, вообще просто реализуется через pthread_mutex и pthread_cond)

Главное чтобы потоки не спали удерживая блокировку.

Тогда получается расшаренная карта которая будет довольно быстро реагировать на события.

OxiD ★★★★
()
Ответ на: комментарий от LamerOk

> тебе вообще не нужны три карты тебе нужна одна, а изменения надо вносить на обработке тика.

Про тик - не понял. А карта - одна, на все три нити.
И так - у каждого процесса-клиента.

Сервер -> Клиент, Клиент, ... Клиент

pacify ★★★★★
() автор топика
Ответ на: комментарий от pacify

Почти ;) Суть в том что если блокировать через мьютекс то все нити будут ждать его независимо от того - читают они карту или меняют.

Надо использовать блокировку чтения-записи, она может быть реализована через мьютексы и условные переменные.

Работает так - много потоков могут иметь одновременно доступ на чтение, при этом никто не может писать. Либо кто-то один пишет, но никто не может читать.

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

OxiD ★★★★
()
Ответ на: комментарий от OxiD

> Если обновления приходят очень часто,

А если - не очень часто? Блокировку можно не делать?
То есть - результат записи в массив (не объявленный volatile) из одной нити -
сразу будет виден в других нитях, не кэшируясь процессором?
У меня обновления на карте происходят (посылаются через MQ) с частотой от 2 до 10 Герц.

pacify ★★★★★
() автор топика
Ответ на: комментарий от LamerOk

> Плохо. У тебя же игра, нет?

Да, игра.

Погугли геймтик


Ну, интуитивно - понятно.
Я пока не задал частоты обработчикам. Только проектирую их.

Собираюсь делать частоту проверок на «коллизии» примерно в 2-3 раза
большей, чем частота «шагов» объектов игры. На один шаг каждого
персонажа-объекта может убираться один объект с карты (write) (он его
«съедает»). Поэтому такой частоты проверки карты (read) будет достаточно.

pacify ★★★★★
() автор топика
Ответ на: комментарий от pacify

> Собираюсь делать частоту проверок на «коллизии» примерно в 2-3 раза
большей, чем частота «шагов» объектов игры.

Это же бессмысленно.

LamerOk ★★★★★
()
Ответ на: комментарий от LamerOk

> Это же бессмысленно.

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

pacify ★★★★★
() автор топика
Ответ на: комментарий от pacify

> - поэтому «совокупная» их частота движения будет - в два раза большей частоты шагов одного игрока.

Это ошибка в реализации игровой логики. Частота движения игроков должна быть равна игровому тику.

LamerOk ★★★★★
()
Ответ на: комментарий от pacify

нет, блокировку надо всегда делать, про часто/нечасто - этоя про оптимизацию.

OxiD ★★★★
()
Ответ на: комментарий от pacify

При чем тут вообще кеш процессора? нити могут на разных процессорах/ядрах работать, и одновременно одна будет читать то чтот ы наполовину переписал.

OxiD ★★★★
()
Ответ на: комментарий от LamerOk

> Частота движения игроков должна быть равна игровому тику.

В моей системе понятие «игровой тик» отсутствует, так как события
от игроков приходят асинхронно, но - с равной частотой. Эти события
могут быть «сдвинуты» друг относительно друга на небольшую дельту.
Поэтому «тики» от игроков могут приходить с любым интервалом,
«плавать» друг относительно друга, теоретически.

pacify ★★★★★
() автор топика
Ответ на: комментарий от OxiD

> и одновременно одна будет читать то чтот ы наполовину переписал.

Там всего один байт записывается.

Байт наполовину прочитать нельзя.

pacify ★★★★★
() автор топика
Ответ на: комментарий от pacify

Заметь, что ты читаешь всю карту за раз. Тебе говорят о том, что блокировку надо ставить не на один байт, а на весь массив. А так как у тебя (сказано тобой выше) асинхронно всё происходит, то тебе надо блокировать на время изменения ВЕСЬ массив (в конце концов, ты же не знаешь кому какой кусок карты нужен будет в тот или иной момент времни (если уж оптимизировать по области «видимости» карты игроком), а кто будет какой кусок карты изменять). Не зацикливайся на «почти одновременно», «с равной частотой» Это сферические треды в вакуумной операционке будут работать с равной частотой (пусть гуру поправят, если я что путаю). Volatile тебе тоже не поможет, как выше сказали уже, процессор тут ни при чем. Один из хороших вариантов подсказал г-н OxiD про блокировку на запись одним, блокируя чтение всем, и разрешать читать всем

BrotherWarrior
()
Ответ на: комментарий от pacify

> асинхронно, но - с равной частотой.

Это - оксюморон. Погугли, что такое (а-)синхронно.

события от игроков приходят асинхронно, но - с равной частотой. Эти события могут быть «сдвинуты» друг относительно друга на небольшую дельту. Поэтому «тики» от игроков могут приходить с любым интервалом, «плавать» друг относительно друга



При синхронной обработке это не имеет значения.

LamerOk ★★★★★
()
Ответ на: комментарий от LamerOk

LamerOk:

асинхронно, но - с равной частотой.

Это - оксюморон. Погугли, что такое (а-)синхронно.


а - частица отрицания
синхронно - одновременно

Я под этим понимаю неодновременность «ожидания» пакета (сообщения),
и - его фактического прихода [адресату].

У простите бывшего математика за такую вольность в терминологии.

BrotherWarrior:

Заметь, что ты читаешь всю карту за раз.


«Читающие» нити к ней обращаются постоянно.

Тебе говорят о том, что блокировку надо ставить не на один байт, а на весь массив.


А зачем вообще тут нужна блокировка?
Ведь запись/чтение байта - атомарно.
Я, конечно, могу «тормозить» mutex'ами нити на время записи/чтения (этот принцип еще помещается в мою голову).
Но зачем это делать - мне непонятно.
Разве изменение в одном байте одной нитью не будет доступно другим нитям (thread'ам) на чтение, сразу же?

в конце концов, ты же не знаешь кому какой кусок карты нужен будет

в тот или иной момент времни



В один промежуток времени (раз в пол-секунды - 1/4 секунды) - обнуляется одна клеточка карты.

Зачем вешать блокировку на чтение карты (часть карты)? Не могу понять.

pacify ★★★★★
() автор топика

Вообщем, уже нашел место, в котором блокировка на чтение нужна:
когда один поток меняет сразу две глобальные переменные: dx,dy для игрока (его направление движения).
Поток «рисования» не должен прочитать новые значения «наполовину».
Для этого и буду использовать рекомендации, высказанные ONIX'ом.

pacify ★★★★★
() автор топика
Ответ на: комментарий от pacify

если это всего 2 переменные, то лучше использовать что-то основанное на spinlock ах мне кажется, все таки мьютексы это переход в ядро, будет довольно медленно.

OxiD ★★★★
()
Ответ на: комментарий от OxiD

> если это всего 2 переменные, то лучше использовать что-то основанное на spinlock ах мне кажется,

Там будет немножко больше двух переменных. Пока сложно сказать - сколько, так как проект клепается на коленке без ТЗ (и - в сжатые сроки).

Всем спасибо, буду копать дальше.

pacify ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.