ЧП: пользователи

тэкс.. и до сюда добрался

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

по этой теме я придумал вот что:
в памяти завести отдельный список. при "получении" от юзера пинга добавлять в хвост этого списка запись - мол такой-то юзер "отметился", и заодно хранить время..
если при добавлении в этот список выясняется, что пользователь в нём уже есть, то запись о нём удалить из списка и прицепить её в хвост.
таким образом получится список пользователей, отсортированных по "активности".
и для проверки на таймауты нужно пробежаться от головы списка до первого "активного" юзера..

имхо звучит вполне резонно..
хотелось бы услышать ваши предложения

зы. не знал, куда конкретно впихнуть эту тему, так что прошу сильно не пинать

мдя... Но тебе-то всё равно нужно будет проходить список... чтобы узнать, есть ли там уже твой пользователь...
А вот как проще...
................(театральная пауза)..............  ;D ;D ;D
Пользователь добавляется в список при коннекте и удаляется при таймауте или при дисконнекте, поэтому просто-напросто - не ищи в списке этого пользователя при добавлении - его там быть не должно... ну разве что список пользователей и этот твой этот самый список (IMHO: типичная реализация таймеров) - суть одно и тоже

Одним словом: правильной дорогой идёте товарищи! Copyright - В.И. Ленин.
;D ;D ;D

хм..
дык ведь всё-равно придётся просматривать этот список при получении пинга от юзера!
блин.. хз.. приоритетные очереди маст дай ;D ;D ;D

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

посмотри в инете про структуру данных под названием "куча", она же "пирамида", она же "heap". Позволяет эффективно организовывать приоритетную очередь. Может подойти...

хм.. куча врядли подойдёт.. да и биномиальное дерево, имхо тоже..

2Meg -> дык! именно об этом и говорю - если пользователь уже в списке, то нужно перенести его "узел" в хвост..

тэкс.. судя по всему ещё больше оптимизировать сиё счастье уже никак.. это хорошо :-)

Ещё можешь проюзать хэш-таблицы...

Задача - по имени пользователя, или другой инфы, приходящей от пользователя (по дискриптору пользователя), найти енту структуру.

Проюзаем идею хэш таблиц. Дискриптор будем выдумывать и присваивать пользователю как того пожелаем сами! Если создать вот такой дискриптор:
<A1 = 1 byte>.<A2 = 1 byte>.<A3 = 1 byte>.<A4 = 1 byte> == unsigned int
то появляется возможность создать вот что:

<br>typedef struct UserInfo{<br>UserInfo* next;<br>UserInfo* prev;<br>...<br>} UserInfo;<br><br>UserInfo* g_Head;<br>UserInfo* g_Tail;<br><br>typedef UserInfo*    HashLevel1;<br>typedef HashLevel1*    HashLevel2;<br>typedef HashLevel2*    HashLevel3;<br>typedef HashLevel3*    HashLevel4;<br>typedef Hash*    HashLevel4;<br><br>...<br>Hash _hash = new HashLevel4[256];<br>...<br><br>if(!_hash[A1])<br>_hash[A1] = new HashLevel3[256];<br><br>...<br><br>и доступ к юзер инфе:<br><br>_hash[A1][A2][A3][A4]; //вот только проверки делать ещё надо!<br><br>

Вот такая вот параноя  ;D ;D ;D !!!

А теперь самое главное:
а) написать правильный алгоритм распределения дискрипторов для пользователей, что бы память экономнее юзалась...
б) написать сборку мусора. Когда пользователь отваливается, следует проверить как там себя чувствует подмассивчик в котором он сидел, если пользователей там нет - удаляем и сам подмассив (HashLevel1), далее смотрим на HashLevel2, и тд, и тп, и др...

И теперь по поводу пингования.
1) Не следует делать проверку каждую секунду! Ты всегда знаешь, какой пользователь пинговался раньше всех (g_Head) и какой позже (g_Tail). Если нужно выбрасывать юзера по таймауту - установи запуск таймера на время, когда прийдёт таймаут для пользователя, который пинговался раньше всех (g_Head)!
2) Когда юзер пингуется, ты МОМЕНТАЛЬНО находишь его по дискриптору в нужной таблице, прописываешь в его структуру время пинга, удаляешь из связного списка (next, prev поля) и кидаешь его в самый зад (g_Tail). И самое главное!!! - если до этого пользователь был впереди (g_Head) - переустанавливаешь таймер (см 1)
3) В ф-ции таймера проходишь связный список начиная от g_Head, делаешь что надо и переустанавливаешь таймер
4) ещё следует установить ограничение на частоту таймера - например - не меньше секунды. Если таймаут для g_Head пользователя должен наступить через 10 милисеков, то всё-равно устанавливаешь - одну секунду!

ЗЫ: и, сорри, в таком состоянии, как сейчас, мне проще на С++, чем на русском... (да простят меня модераторы!!!) ;D ;D ;D

Сообщение отредактировано: Shaman - 07.07.03, 08:10

в этом что-то есть.. надо будет поразмыслить на досуге..
сейчас распечатаю это счастье и по дороге на английский буду обдумывать... ;D

<offtopic>
зы. сборка мухора - вообще задница.. у меня при отлогировании юзера кол-во используемой памяти сервером, по показаниям таск манагера, не уменьшается!
хотя везде всё удаляю.. бяка..
</offtopic>

;D на самом деле происходит вот что:
1. Если ты используешь С++ и оператор new, то будь уверен, что он создаёт пулы памяти - блоки, на много большие тех, которые ты запрашиваешь, твоя память распределяется в них. При распределении, код, отвечающий за аллокацию, проверяет, есть ли память в пулах - если нет - создает новый, если есть - отдаёт тебе указатель на свободную память в пуле. Пул уничтожается только тогда, когда он не имеет распределённых блоков памяти - тобиш, когда деаллокируется последний блок.
2. Если ты пишешь на С - malloc&free могут использовать ту же схему. Всё зависит от версии и производителя стандартной библиотеки (или производителя системы - для *никсов)

Так что - сборка мусора - рулес!!!  ;D ;D ;D

malloc&free :-)
кстати.. именно это я и заметил - сложилось ощущение, что память выделяется бОльшими кусками и сначала расходуются они, а потом уже выделяются новые.. но вот ни разу не заметил, чтоб эти пулы особождались :-))

Ну вот сам-то подумай.
В каждом пуле сидит >100 мелких блоков.
Какова вероятность того, в пуле освободятся ВСЕ блоки?
Если есть утечка памяти (memory leak) ходя бы в 4 байта, то это будет означать, что по крайней мере один пул будет прибиваться только при завершении программы.
То же может происходить, если в твоей программе есть механизмы кэширования данных. Например ты преднамеренно не удаляешь какие-то данные после логаута пользователя, в надежде, что он опять залогинится (это чисто теоретическое предположение ).

Если память для твоей программы - критический вопрос, можно написать свой механизм аллокации. К сожалению я не помню (и нет сейчас возможности подсмотреть), что для этого нужно сделать на *никсах. Нужно смотреть исходники аллокации. Но, на сколько я помню, должен быть механизм подмены внутренностей, ипользующихся в malloc/free... Более того, ты можешь глобально перегрузить макросами malloc&free

<br>/*file GlobalHeader.h, MUST be included to each file in your program*/<br>#define malloc(X) my_malloc(X)<br>#define free(X) my_free(X)<br>------<br><br>/*file MyMalloc.h, do not include GlobalHeader.h!!!*/<br>void* my_malloc(int inSize);<br>void my_free(void inPtr);<br>------<br><br>/*file MyMalloc.c, do not include GlobalHeader.h!!!*/<br>#include "MyMalloc.c"<br>void* my_malloc(int inSize)<br>{<br>/*пишешь свою аллокацию, используя Ф-ЦИИ РАСПРЕДЕЛЕНИЯ ПАМЯТИ НИЗКОГО УРОВНЯ*/<br>}<br><br>void my_free(void inPtr)<br>{<br>/*пишешь свой разрушатор, используя Ф-ЦИИ РАСПРЕДЕЛЕНИЯ ПАМЯТИ НИЗКОГО УРОВНЯ*/<br>}<br>

Это прокатит только в том случае, если ты заведомо НЕ ИСПОЛЬЗУЕШЬ И НЕ СОБИРАЕШЬСЯ ИСПОЛЬЗОВАТЬ готовые библиотеки, которые могут распределять память, которую ты должен сам удалить с помощью free. Хотя и єтот вопрос можно решить, с помощью ф-циq StdMalloc/StdFree - ты их должен будешь реализовать в MyMalloc.c, они должны вызывать напрямую стандартные методы malloc&free. В любом случае, перед началом таких эксперементов, лучше подсмотреть, что делают стандартные ф-ции.

И ещё... Именно для ЧП!!!
Только представь, что оно станет популярно и будет 0xFFFFFFFF пользователей....  ;D ;D ;D
Не лучше ли обойтись без распределения памяти??
Когда нужна структура, описывающая пользователя, который находится онлайн? Только тогда, когда он проявляет активность.... Не лучше ли после логина создавать файл для этого пользователя:
/tmp/chepe/online-users/K/L/M/N.usr
где K, L, M, N - те самые индексы массива, о котором говорилось в моих предидущих постах? Вот только нужно решить проблему с указателями, хранящимися в этой структуре, я думаю, что это проще пареной репы... если это указатель на структуру другого пользователя - ты можешь хранить его дескриптор, по которому ТУТ ЖЕ сможешь найти, где находится его запись...

Что-то в этом духе  ;D ;D ;D