#php #mysql #math #task
#php #mysql #математика #задача
Вопрос:
В нашем сервисе пользователи могут добавлять различные задачи, которые выполняются, как только слот становится доступным.
Все задачи хранятся в таблице mysql. Таблица выглядит следующим образом
user_id | task | status | created_at | started_at
int | string | pending,active | datetime | datetime
В настоящее время мы используем стратегию fifo, но поскольку количество задач увеличивается, и мы не хотим добавлять ограничение на количество задач, которые может добавить пользователь, мы хотим добавить к ней справедливую политику слотов. Обычно задача выполняется за 30-75 минут до ее завершения. Это также может быть меньше или больше.
Я создал набор образцов данных:
Пример данных:
158 total tasks
144 pending tasks
14 running tasks
15 tasks can run at the same time
# of pending tasks for each user
user 1 => 28 tasks
user 2 => 76 tasks
user 3 => 5 tasks
user 4 => 22 tasks
user 5 => 3 tasks
# of active tasks for each user
user 1 => 5 tasks
user 2 => 0 tasks
user 3 => 2 tasks
user 4 => 4 tasks
user 5 => 3 tasks
Мой подход заключается в
следующем: сначала разделите количество ожидающих выполнения задач для каждого пользователя на общее количество ожидающих выполнения задач (pending_tasks_of_user_x / pending_tasks).
-второй: затем разделите активные задачи на количество задач, которые могут выполняться одновременно (active_tasks_of_user_x / concurrent_tasks).
Но теперь я не знаю, как поступить. Если мой подход совершенно неверен, я открыт для этого.
Для доступа к базе данных я использую php.
Редактировать:
Как справедливо я определяю, что пользователю не нужно ждать, пока все остальные задачи других пользователей не будут завершены. Например, у пользователя 2 76 задач, а у пользователя 1 28 задач. Теперь пользователь 5 добавляет 3 задачи. Я не хочу, чтобы пользователь 5 должен был ждать, пока все задачи пользователя 1 и 2 должны быть выполнены первыми, прежде чем будут выполнены задачи пользователя 5. Больше похоже на то, что пользователь 2 может запускать 8 задач одновременно, пользователь 1 4 и пользователь 5 могут запускать 2 или что-то подобное. Если доступно больше пользователей, чем одновременных задач, оно должно соответственно уменьшиться, а некоторым придется подождать.
Комментарии:
1. Вы не сказали, что считаете «справедливым». Это: чем больше задач вы отправляете, тем больше слотов вы получаете? Или наоборот? Есть что сказать обоим.
2. Есть нечто, называемое справедливым распределением . Это то, что вы хотите сделать?
3. @KIKOSoftware совершенно забыл об этом. Извините за это. Отредактировал сообщение
4. Я думаю, я ищу что-то похожее на планирование справедливой доли
Ответ №1:
Я думаю, что планирование справедливой доли является хорошим подходом в этом случае.
Разделите общее количество доступных слотов задач на общее количество пользователей, у которых есть незавершенные задачи.
15 / 5 = 3
Таким образом, каждый пользователь теперь может запускать 3 задачи одновременно.
Это означает, что пользователи с небольшим количеством задач будут выполнены быстро, а пользователям с большим количеством задач придется ждать дольше.
Если появится другой пользователь, доступные задачи будут
15 / 6 = 2.5
Конечно, вы не можете выполнить половину задачи, но это можно решить в реальном алгоритме очередей.
Я думаю, вы могли бы реализовать это в PHP. Я не думаю, что это мое дело кодировать это для вас.
Алгоритм должен быть примерно таким:
- Слот задачи освобождается и ищет новую задачу для выполнения.
- Найдите пользователя с наименьшим количеством запущенных задач.
- Найдите самую старую ожидающую задачу этого пользователя.
- Если у пользователя нет ожидающих выполнения задач, удалите пользователя из рассмотрения и начните снова с пункта 2.
- Запустите ожидающую задачу.
Это все, что вам нужно сделать, чтобы реализовать это.