1

n個のタスクがあるタスクスケジューラを実装しようとしています。私のタスクスケジューラの背後にある考え方は、ベクトルのキューのループでは、タスクはキューのループの中で最も短いキューにエンキューされる必要があるということです。これは、次のコードによって実行されます。

#include <vector> 
#include <queue> 
std::vector<std::queue<int> > q
int min_index = 0;
task t // implemented in the other part of the program
std::size_t size = q.size();
for( i=0; i<size; i++){ //accessing loop of queues
    if(q[min_index].size() > q[i].size())
        min_index = i; // Now q[min_index] is the shortest queue
} 
q[min_index].push(Task);

次に、このパラダイムを拡張してスケジューラーのオーバーヘッド時間を削減しようとしています。毎回最短のキューを検索する代わりに、何らかの条件を検索します。5つのタスクが最短キューにエンキューされた後、最短キューを検索します。

私はこのようなことをする必要があります

#include <vector> 
#include <queue> 
std::vector<std::queue<int> > q
task t // implemented in the other part of the program
while(q[min_index].size()!=q[min_index].size()+5) // check whether current min_index  queue's size is increased 5 more times if not goto enqueue
        {
        goto enqueue;
        }

    int min_index = 0;

    std::size_t size = q.size();
    for( i=0; i<size; i++){ //accessing loop of queues
        if(q[min_index].size() > q[i].size())
            min_index = i; // Now q[min_index] is the shortest queue
    } 
    enqueue:  
    q[min_index].push(Task);

誰かがそれを正しく進める方法を教えてもらえますか？前もって感謝します

更新 5（乱数）の代わりに、信頼性が高く、毎回概算する数を使用することを考えました。そこで、キューのループのmin_valueサイズとmax_valueサイズの差を取得し、毎回カウンターと比較することを考えました。

// global variables 
std::vector<std::queue<int> > q;
int counter = INT_MAX; // 
int min_index = 0;
int max_size = -1;

void enqueue(scheduler::task new_task) { 
 if ( counter > diff_size ){
  // look for new min and maximum
  std::size_t size = q.size();
  for( i=0; i<size; i++){ 
    if(q[min_index].size() > q[i].size())
     min_index = i; 
       if(q[i].size() > max_size)
        max_size = q[i].size(); 
    diff_size=max_size - min_index;
  } 
  // counter reset
  counter = 0;
 }

 // enqueue in minimum queue
 q[min_index].push(new_task)

 // increase counter
 counter ++;
}
4

1 に答える 1

1

私はこれを試してみると思います（コードはコンパイルされ、動作します）：

#include <vector> 
#include <queue>
#include <cassert>
#include <iostream>
using namespace std;

class multi_queue{
  private:
    typedef std::vector<std::queue<int> > mq_type;
    mq_type q;
    int min_queue;
    int min_queue_inc;
    int max_inc;
    void find_min_queue(){
      max_inc=q[min_queue].size();
      min_queue_inc=0;
      min_queue=0;
      for(int i=1;i<q.size();++i)
        if(q[i].size()<q[min_queue].size())
          min_queue=i;
    }
  public:
    multi_queue(int n) {
      assert(n>0);
      min_queue=0;
      min_queue_inc=0;
      max_inc=5;
      increase_queues(n);
    }
    void increase_queues(int n){ 
      if(n<q.size()) return;
      q.resize(n);
    }
    void push(int item){
      if(min_queue_inc++==max_inc)
        find_min_queue();
      q[min_queue].push(item);
    }
    int queues() const {
      return q.size();
    }
    int pop_from(int qnum){
      assert(qnum>=0);
      assert(qnum<q.size());
      assert(can_pop_from(qnum));
      int temp=q[qnum].front();
      q[qnum].pop();
      return temp;
    }
    bool can_pop_from(int qnum) const {
      return q[qnum].size()>0;
    }
    int largest_queue() const {
      int largest=0;
      for(int i=1;i<q.size();++i)
        if(q[i].size()>q[largest].size())
          largest=i;
      return q[largest].size();
    }
};


int main(){
  multi_queue q(10);
  for(int i=0;i<100;++i){
    cout<<"Current largest queue: "<<q.largest_queue()<<endl;
    cout<<"Pushing: " <<i<<endl;
    q.push(i);
  }

  for(int i=0;i<10;++i)
  for(int j=0;j<100;++j)
    if(q.can_pop_from(i))
      cout<<q.pop_from(i)<<endl;
}

q.largest_queue()当然、ポイントが崩れるので毎回表示したくないのですが、ここで表示するのは、動作していることを確認できるようにするためです。

push()あなたの質問に答えるという観点からの重要な方法はとfind_min_queue()です。

私は2つの状態変数を使用min_queueしmin_queue_inc、何が起こっているかを追跡します。

min_queue常に最短のキューを指します。min_queue_incそのキューに追加されたアイテムの数を追跡します。

ここではpush()、現在の最小キューに5つのアイテムが追加されているかどうかを確認します。もしそうなら、私たちが使用すべき新しい最小キューがあるかどうかを確認する時が来たので、それを呼び出しますfind_min_queue()。

find_min_queue()をリセットmin_queue_incし、最短のキューを見つけて、そのキューをに記録しますmin_queue。

やりたいことに応じてmax_inc、ニーズに合わせて変数の動作を調整します。

于 2013-03-07T15:05:45.290 に答える