Здравствуйте, VladFein, Вы писали:

VF>Здравствуйте, antropolog, Вы писали:

A>>А надо было всего-лишь реализовать простой паттерн — привязку продюсера к конкретному потоку. В данном случае это делается отдельной очередью на каждый поток, и помещением таски в очередь с индексом = taskID % threadNum

VF>Такого требования нет в задании.
конечно нет, ведь я описываю имплементацию

VF>Таск от любого клиента может выполняться любым потоком, если только другой поток не выполняет в это время таск этого клиента.
вот именно, что "может", а не "должен", а вы все пытаетесь прочесть как "должен балансировать". Хотя единственное что "должен" поток, это не работать с таской, с которой работает в это же время другой поток.

VF>Мне видится простой алгоритм: все таски (с ID клиента) ставятся в одну очередь, в порядке поступления.
VF>CThreadPool имеет set "клиентов в процессе".
VF>Потокам при создании передаётся callback на:
VF>CTask* CThreadPool::NextTask(int& _clientId);
VF>Где [in, out] _clientId — при вызове равен ID предыдущего клиента (например, -1 для начала), а по возвращении — текущего.
VF>Потоки работают в бесконечном цикле NextTask() / Execute(). Ведь конечного условия не дано?

VF>CThreadPool::NextTask() удаляет ID предыдущего клиента из set'а, перебирает лист в поисках первого ID клиента, не найденного в том set'е, добавляет его в set, удаляет из очереди и возвращает потоку.
А если в очереди лежат только ID уже работающих клиентов, то нужно поток усыпить, а затем по прибытию нового таска, опять проверить список, так?

итого имеем:
set, queue, и один mutex, который защищает обе эти структуры и лочится на время работы:
NextTask,
AddTask
и всё это для того чтобы забалансить таски по тредам.

В то время как в моём случае:
отдельная lock-free очередь на каждый тред
NextTask/AddTask работает с конкретной очередью, мьютекс не нужен, поиск в очереди не нужен, добавление/удаление таски — одна CAS операция. Единственный недостаток — теоретическая разбалансировка, я повторюсь — теоретическая, например при малом количестве клиентов, и если у них внезапно совпал id % threadnum (ну или hash(id) % threadnum ). В реальном мире такая разбалансировка практически не встречается, а если встречается то на малом количестве "долгих клиентов" и при невезучем случае.

Иными словами — мой алгоритм оптимален для многоих клиентов с мелкими тасками ( т.к. минимальный shared state и отсутствие блокировок). Ваш алгоритм оптимален для "долгоиграющих" задач он небольшого количества клиентов (т.к. во-первых идеально балансирует, а во-вторых частота обращения к очереди задач относительно редка, что нивелирует влияние блокировок на перформанс ). Но повторюсь, об оптимальной балансировке в вакууме ( как и о трейде latency<->throughput ) можно написать диссертацию, а в тестовом задании ничего не сказано о балансировке, поэтому выбирается наиболее простой вариант ( и в то же время самый распространённый ), имплементация которого тривиальна.

Здравствуйте, antropolog, Вы писали:

A>В то время как в моём случае:
A>отдельная lock-free очередь на каждый тред
A>NextTask/AddTask работает с конкретной очередью, мьютекс не нужен, поиск в очереди не нужен, добавление/удаление таски — одна CAS операция. Единственный недостаток — теоретическая разбалансировка, я повторюсь — теоретическая, например при малом количестве клиентов, и если у них внезапно совпал id % threadnum (ну или hash(id) % threadnum ). В реальном мире такая разбалансировка практически не встречается, а если встречается то на малом количестве "долгих клиентов" и при невезучем случае.
A>Иными словами — мой алгоритм оптимален для многоих клиентов с мелкими тасками ( т.к. минимальный shared state и отсутствие блокировок).

Твой алгоритм не соответствует условию ТЗ:

S>Не должно быть "повисших" клиентов, даже если клиентов больше, чем потоков.
S>Т.е. поток должен обрабатывать разных клиентов по-очереди, а не одного до завершения всех его задач.

Возьми простой случай одного рабочего потока — никакого "разных клиентов по-очереди" у тебя нет.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Твой алгоритм не соответствует условию ТЗ:
EP>

S>>Не должно быть "повисших" клиентов, даже если клиентов больше, чем потоков.
S>>Т.е. поток должен обрабатывать разных клиентов по-очереди, а не одного до завершения всех его задач.

100% соответствие

EP>Возьми простой случай одного рабочего потока — никакого "разных клиентов по-очереди" у тебя нет.
возможно у нас разное понимание "по-очереди". В моём понимании по-очереди — значит в порядке очереди, т.е. в порядке добавления в очередь. А твоё какое?

P.S. Очевидно же что это условие "по-очереди, а не одного до завершения всех его задач" добавлено чтобы оградиться от простого, очевидного, но кривого дизайна, когда заводят по одной очереди на клиента и пул выбирает из этой очереди таски пока она не пуста.

P.P.S.
всё обсуждение в этом треде похоже на заседание дагестанской академии наук, не хочу никого задеть, но реально, кто из отписывающихся в треде прочёл хоть одну книгу по многопоточному программированию? Вопрос риторический, можно не отвечать.

Здравствуйте, antropolog, Вы писали:

EP>>Твой алгоритм не соответствует условию ТЗ:
EP>>

S>>>Не должно быть "повисших" клиентов, даже если клиентов больше, чем потоков.
S>>>Т.е. поток должен обрабатывать разных клиентов по-очереди, а не одного до завершения всех его задач.

A>100% соответствие

Нет
Там ещё другое условие не выполняется — "Разные клиенты обслуживаются параллельно".
Рассмотрим ситуацию когда у нас есть два потока и два клиента — их задания должны обслуживаться параллельно. В твоём же варианте они оба могут попасть в один поток, а второй будет простаивать.

EP>>Возьми простой случай одного рабочего потока — никакого "разных клиентов по-очереди" у тебя нет.
A>возможно у нас разное понимание "по-очереди". В моём понимании по-очереди — значит в порядке очереди, т.е. в порядке добавления в очередь.

Даже если допустить что "в порядке добавления в очередь" — то о какой конкретно очереди идёт речь? Очевидно что речь не об очередях на поток как у тебя — так как это всего лишь деталь твоей реализации.
Значит речь об очереди по времени — сначала пришло задание от одного клиента, его и выполняем, потом от второго — если есть ресурсы выполняем его, потом пришло от третьего — оно должно начать выполнятся в последнюю очередь. У тебя же сначала могут начать выполнятся задания от первого (по времени) и третьего клиента, а только потом от второго, так как его задание попало в один поток с первым клиентом

A>А твоё какое?

"Разных клиентов по-очереди" — означает что для двух клиентов сначала выполняем задание первого клиента, потом второго, потом опять первого (если его задания не выполняются).

ГВ>

ГВ>void CWorkThread::RunTask(int clientID, CTask* task)
ГВ>{
    this->>task = task;
    this->>clientID = clientID;

ГВ>    cv.notify_one();
ГВ>}
ГВ>

Непривычно но тем не менее все правильно.

ГВ>Мне показалось, что если бы формальные параметры были оформлены иначе, чем имена членов класса, код был бы чуть проще.

Обычно оформляют члены а не наоборот.

Вы как-то немного аггресивно реагируете в ответ на критику (о которой вы вроде бы спрашивали). Это всего-лишь тестовое задание.. расслабтесь и просто сделайте выводы

Здравствуйте, MozgC, Вы писали:

MC>Вы как-то немного аггресивно реагируете в ответ на критику (о которой вы вроде бы спрашивали). Это всего-лишь тестовое задание.. расслабтесь и просто сделайте выводы

Вероятно Вы правы)
Просто хотелось услышать критику технической реализации многопоточного приложения, а всю дорогу слышал что то типа "ты изменил интерфейс, значит недостоин называться программистом".
И только 2 Евгения спасли ситуацию)

Впрочем, стоило бы формулировать четче что я хочу получить

Здравствуйте, Evgeny.Panasyuk, Вы писали:


EP>Значит речь об очереди по времени — сначала пришло задание от одного клиента, его и выполняем, потом от второго — если есть ресурсы выполняем его, потом пришло от третьего — оно должно начать выполнятся в последнюю очередь.

Вот это поворот.

представь что у тебя два потока, два клиента, и четыре таски ( в порядке добавления через AddTask ):
1111(1) 22222222222(2) 2222222222(3) 1111(4)
(здесь цифра — id клиента, количество цифр — время выполнения таски )

итого в начале имеем:
t1 1111(1)
t2 22222222222(2)

в первый тред попадает таска(1) от первого клиента, во второй — таска(2) от второго клиента, после того как отработала первая таска(1), по твоей логике должна выполняться обязательно таска(3) ? потому что её добавили третьей? Если да, то у тебя будет вынужден простаивать поток t1, т.к. мы не можем пускать таски одного клиента в параллель, а если нет — то таска(4) начнёт выполнятся раньше таски(3), и тогда о какой очерёдности ты говоришь? Как по-твоему здесь должен действовать шедулер?

Здравствуйте, DvaSL, Вы писали:

DSL>Просто хотелось услышать критику технической реализации многопоточного приложения, а всю дорогу слышал что то типа "ты изменил интерфейс, значит недостоин называться программистом".
DSL>[...]

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

DSL>И только 2 Евгения спасли ситуацию)

Этточно.

DSL>Впрочем, стоило бы формулировать четче что я хочу получить

Спросил бы сразу про реализацию, тебе и отвечали бы по-другому. Ну ничего, что ни делается — всё к лучшему.

Здравствуйте, antropolog, Вы писали:

EP>>Значит речь об очереди по времени — сначала пришло задание от одного клиента, его и выполняем, потом от второго — если есть ресурсы выполняем его, потом пришло от третьего — оно должно начать выполнятся в последнюю очередь.
A>Вот это поворот.
A>представь что у тебя два потока, два клиента, и четыре таски ( в порядке добавления через AddTask ):
A>...
A>в первый тред попадает таска(1) от первого клиента, во второй — таска(2) от второго клиента, после того как отработала первая таска(1), по твоей логике должна выполняться обязательно таска(3) ? потому что её добавили третьей?

Конечно же нет. Свою логику я вообще-то описал:

EP>"Разных клиентов по-очереди" — означает что для двух клиентов сначала выполняем задание первого клиента, потом второго, потом опять первого (если его задания не выполняются).

Видимо стоило добавить, что если задания первого выполняются — то переходим ко второму и так далее.

A>Если да, то у тебя будет вынужден простаивать поток t1, т.к. мы не можем пускать таски одного клиента в параллель, а если нет — то таска(4) начнёт выполнятся раньше таски(3), и тогда о какой очерёдности ты говоришь? Как по-твоему здесь должен действовать шедулер?

Ты потерял контекст. Восстанавливаем:
Сначала ты сказал что ты понял что имеется в виду "в порядке добавления в очередь".

A>>возможно у нас разное понимание "по-очереди". В моём понимании по-очереди — значит в порядке очереди, т.е. в порядке добавления в очередь.

Естественно возникает вопрос — о какой конкретно очереди идёт речь:

EP>Даже если допустить что "в порядке добавления в очередь" — то о какой конкретно очереди идёт речь? Очевидно что речь не об очередях на поток как у тебя — так как это всего лишь деталь твоей реализации.

Вот выяснили — что это точно не очереди на поток, о них вообще ничего не было сказано в ТЗ.
Тогда о каком порядке "порядке добавления в очередь" ты говоришь? Видимо про общую временную очередь:

EP>Значит речь об очереди по времени — сначала пришло задание от одного клиента, его и выполняем, потом от второго — если есть ресурсы выполняем его, потом пришло от третьего — оно должно начать выполнятся в последнюю очередь. У тебя же сначала могут начать выполнятся задания от первого (по времени) и третьего клиента, а только потом от второго, так как его задание попало в один поток с первым клиентом

Но даже это не выполняется в твоей схеме.
Далее, ты пытаешься показать что жёсткая очерёдность по времени добавления ведёт к простаиванию потоков:

A>Если да, то у тебя будет вынужден простаивать поток t1

Правильно, но тогда возвращаемся в начало:

A>>возможно у нас разное понимание "по-очереди". В моём понимании по-очереди — значит в порядке очереди, т.е. в порядке добавления в очередь.

О какой очереди ты тогда говорил, если не об очереди по времени?

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, antropolog, Вы писали:


EP>О какой очереди ты тогда говорил, если не об очереди по времени?
Да, я тут очевидно зафейлил. Осталось тебе тоже признать, что об "очередности" здесь речи идти не может, только о балансировке, и тогда можешь сразу перечитать мой ответ для VladFein

Здравствуйте, antropolog, Вы писали:

A>Осталось тебе тоже признать, что об "очередности" здесь речи идти не может, только о балансировке, и тогда можешь сразу перечитать мой ответ для VladFein

Может. Как раз об очерёдности, но только не об строгой очерёдности по времени прибытия, а той которая "разных клиентов по-очереди" — ключевое слово выделено.
Это реализуется очередью клиентов (именно клиентов, а не заданий) — каждый рабочий поток забирает (pop) одного клиента из общей очереди клиентов, и обрабатывает одно его задание, после чего ставит (push) этого клиента в конец очереди клиентов.
За счёт того что каждый клиент, для которого выполнили одно задание, ставится в конец очереди — мы и получаем необходимое "разных клиентов по-очереди".

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, antropolog, Вы писали:

A>>Осталось тебе тоже признать, что об "очередности" здесь речи идти не может, только о балансировке, и тогда можешь сразу перечитать мой ответ для VladFein

EP>Может. Как раз об очерёдности, но только не об строгой очерёдности по времени прибытия, а той которая "разных клиентов по-очереди" — ключевое слово выделено.
EP>Это реализуется очередью клиентов (именно клиентов, а не заданий) — каждый рабочий поток забирает (pop) одного клиента из общей очереди клиентов, и обрабатывает одно его задание, после чего ставит (push) этого клиента в конец очереди клиентов.
EP>За счёт того что каждый клиент, для которого выполнили одно задание, ставится в конец очереди — мы и получаем необходимое "разных клиентов по-очереди".

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