Алгоритм планирования с ограничениями

Ответ 1

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

Этот код похож на Дефицит round robin, но с несколькими упрощениями. Во-первых, мы сами кормим очереди, добавляя к переменной data_to_process. Во-вторых, очереди просто перебирают список значений.

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

Грубый эскиз: не скомпилирован (С++ 11) unix на основе кода

#include <iostream>
#include <vector>
#include <numeric>
#include <unistd.h>
//#include <cmath> //for ceil

#define TIME_SCALE ((double)60.0) //1 for realtime speed

//Assuming you are not refreshing ints in the real case
template<typename T>
struct queue
{
    const std::vector<T> data; //this will be filled with numbers
    int position;

    double refresh_rate; //must be refreshed ever ~ hours
    double data_rate; //this many refreshes per hour
    double credit; //amount of refreshes owed

    queue(std::initializer_list<T> v, int r ) :
        data(v), position(0), refresh_rate(r), credit(0) {
        data_rate = data.size() / (double) refresh_rate;
    }

    int getNext() {
        return data[position++ % data.size()];
    }
};

double time_passed(){
static double total;
//if(total < 20){ //stop early
    usleep(60000000 / TIME_SCALE); //sleep for a minute
    total += 1.0 / 60.0; //add a minute
    std::cout << "Time: " << total << std::endl;
    return 1.0; //change to 1.0 / 60.0 for real time speed
//} else return 0;
}

int main()
{
    //keep a list of the queues
    std::vector<queue<int> > queues{
    {{1, 2, 3}, 2},
    {{1, 2, 3, 4}, 3}};

    double total_data_rate = 0;
    for(auto q : queues) total_data_rate += q.data_rate;

    double data_to_process = 0; //how many refreshes we have to do
    int queue_number = 0; //which queue we are processing

    auto current_queue = &queues[0];

    while(1) {
        data_to_process += time_passed() * total_data_rate;
        //data_to_process = ceil(data_to_process) //optional

        while(data_to_process >= 1){
            //data_to_process >= 0 will make the the scheduler more
            //eager in the first time period (ie. everything will updated correctly
            //in the first period and and following periods
            if(current_queue->credit >= 1){
            //don't change here though, since credit determines the weighting only,
            //not how many refreshes are made
                //refresh(current_queue.getNext();
                std::cout << "From queue " << queue_number << " refreshed " <<
                current_queue->getNext() << std::endl;
                current_queue->credit -= 1;
                data_to_process -= 1;
            } else {
                queue_number = (queue_number + 1) % queues.size();
                current_queue = &queues[queue_number];
                current_queue->credit += current_queue->data_rate;
            }
        }
    }
   return 0;
}

Теперь пример должен скомпилировать gcc с -std = С++ 11 и предоставить вам то, что вы хотите.

и вот результат тестового случая: (для несрочного масштабированного более раннего кода)

Time: 0
From queue 1 refreshed 1
From queue 0 refreshed 1
From queue 1 refreshed 2
Time: 1
From queue 0 refreshed 2
From queue 0 refreshed 3
From queue 1 refreshed 3
Time: 2
From queue 0 refreshed 1
From queue 1 refreshed 4
From queue 1 refreshed 1
Time: 3
From queue 0 refreshed 2
From queue 0 refreshed 3
From queue 1 refreshed 2
Time: 4
From queue 0 refreshed 1
From queue 1 refreshed 3
From queue 0 refreshed 2
Time: 5
From queue 0 refreshed 3
From queue 1 refreshed 4
From queue 1 refreshed 1

В качестве расширения, чтобы ответить на проблему с повторяющимся шаблоном, разрешив этому планировщику выполнить только первые шаги lcm (update_rate * lcm (... refresh...), ceil (update_rate)), а затем повторить шаблон.

ТАКЖЕ: это действительно будет неразрешимо иногда из-за требования на часовых границах. Когда я использую ваш неразрешимый пример и изменяю time_passed, чтобы вернуть 0.1, расписание разрешается с обновлениями каждые 1,1 часа (только не на границах часов!).

Ответ 2

Кажется, ваши ограничения повсюду. Чтобы быстро подытожить мой другой ответ:

• Он соответствует частотам обновления только в среднем
• Наименьшее количество загрузок с часовыми интервалами, необходимыми для выполнения вышеуказанных

Он основывался на этих (иногда невыполнимых) ограничениях

• Обновление с дискретными интервалами в 1 час.
• Обновлять наименьшее количество элементов каждый раз
• Обновление каждого элемента с фиксированными интервалами

и сломал 3.

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

#include <iostream>
#include <vector>
#include <numeric>
#include <unistd.h>

#define TIME_SCALE ((double)60.0)

//Assuming you are not refreshing ints in the real case
template<typename T>
struct queue
{
    const std::vector<T> data; //this is the data to refresh
    int position; //this is the data we are up to
    double refresh_rate; //must be refreshed every this many hours
    double data_rate; //this many refreshes per hour
    double credit; //is owed this many refreshes
    const char* name;//a name for each queue

    queue(std::initializer_list<T> v, int r, const char* n ) :
        data(v), position(0), refresh_rate(r), credit(0), name(n) {
        data_rate = data.size() / (double) refresh_rate;
    }

    void refresh() {
        std::cout << "From queue " << name << " refreshed " << data[position++ % data.size()] << "\n";
    }
};

double time_passed(){
static double total;
    usleep(60000000 / TIME_SCALE); //sleep for a minute
    total += 1.0; //add a minute
    std::cout << "Time: " << total << std::endl;
    return 1.0; //change to 1.0 / 60.0 for real time speed
}

int main()
{
    //keep a list of the queues
    std::vector<queue<int> > queues{
        {{1}, 1, "A"},
        {{1}, 2, "B"}};

    while(1) {
        auto t = time_passed();
        for(queue<int>& q : queues) {
            q.credit += q.data_rate * t;
            while(q.credit >= 1){
                q.refresh();
                q.credit -= 1.0;
            }
        }
    }
   return 0;
}

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

Я думаю, что это самый простой и требует минимального количества обновлений (например, предыдущего ответа), но не нарушает правило 3.