StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You problem is a typical scheduling problem. These kinds of problems are well studied in computer science so there is a huge array of literature to consult.</p> <p>The code is kind of like <a href="http://en.wikipedia.org/wiki/Deficit_round_robin" rel="nofollow">Deficit round robin</a>, but with a few simplifications. First, we feed the queues ourself by adding to the <code>data_to_process</code> variable. Secondly, the queues just iterate through a list of values.</p> <p>One difference is that this solution will get the optimal value you want, barring mathematical error.</p> <p><strike>Rough sketch: have not compiled (c++11)</strike> unix based, to spec code</p> <pre><code>#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; } </code></pre> <p>The example should now compile on gcc with --std=c++11 and give you what you want.</p> <p>and here is test case output: (for non-time scaled earlier code)</p> <pre><code>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 </code></pre> <p>As an extension, to answer the repeating pattern problem by allowing this scheduler to complete only the first lcm(update_rate * lcm(...refresh rates...), ceil(update_rate)) steps, and then repeating the pattern.</p> <p>ALSO: this will, indeed, be unsolvable sometimes because of the requirement on hour boundaries. When I use your unsolvable example, and modify time_passed to return 0.1, the schedule is solved with updates every 1.1 hours (just not at the hour boundaries!).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload