Голодание. Приоритетные очереди
#опытным

Голодание бывает не только у потоков, но и у других сущностей с приоритетами.

Допустим у вас есть система задач с 3-мя приоритетами: High, Medium, Low. Продюсеры кладут каждую задачу в очередь, соответствующую ее приоритету. А консюмеры всегда должны потреблять задачи с самым высоким возможным приоритетом.

То есть, пока High очередь не опустеет, никто не будет брать Middle задачи. И никто не возьмет в обработку Low задачи, пока High и Middle очереди не пусты.

Может возникнуть такая ситуация, при которой задачи High будут постоянно приходить так, что обработчики редко будут брать задачи Middle и никогда не дойдут до Low очереди. Таким образом, эти очереди будут голодать от недостатка обработки.

class Scheduler {
private:
    std::vector<ThreadSafeQueue<std::string>> queues;
    std::vector<std::string> priority_names;

public:
    Scheduler() : queues(3), priority_names{"HIGH", "MEDIUM", "LOW"} {}

    std::string Get() {
        while(true) {
            for(int i = 0; i < queues.size(); ++i) {
                auto task = queues[i].take();
                if (!task)
                    continue;
                std::cout << "Get task " << priority_names[i] << ": " << task << std::endl;
                return task;
            }
            // some kind of waiting mechanism in case of every queue is full
            }
    }

    void AddTask(int priority, const std::string& task) {
        queues[priority].push(task);
        std::cout << "Add task " << priority_names[priority] << ": " << task << std::endl;
    }
};

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

Кстати сам алгоритм называется Fixed-priority pre-emptive scheduling. В каждый момент времени выполняется задача с самым высоким приоритетом.

Решение проблемы - сменить алгоритм взятия задач из очередей.

Например, можно установить правило, что вы обрабатываете не более f(priority) элементов в любой данной очереди, прежде чем рассматривать элементы из очереди с более низким приоритетом.

Функция f может быть:

👉🏿 Линейной: f(p) = p. Обрабатывается не более 4 элементов с приоритетом 4 (высший), затем не более 3 с приоритетом 3,..., 1 с приоритетом 1.

👉🏿 Экспоненциальной: f(p) = 2^(p-1). Обрабатывается не более 8 элементов с приоритетом 4 (высший), затем не более 4 с приоритетом 3, затем не более 2 с приоритетом 2,..., 1 с приоритетом 1.

Конкретная функция выбирается из ожидаемой частоты появления задач

Возьмем экспоненциальный случай и предположим, что в каждой очереди много ожидающих задач. Мы планируем: 8 высших, 4 высоких, 2 средних, 1 низкий, 8 высших и т.д... Каждый цикл содержит 8 + 4 + 2 + 1 = 15 задач, поэтому задачи высшего приоритета занимают 8/15 времени потребителя, следующие — 4/15, следующие — 2/15, следующие — 1/15.

Сравниваем эти частоты с ожидаемыми и корректируем коэффициенты или используем другую функцию.

You are the highest priority. Stay cool.

#concurrency