ノンプリエンプティブな優先度

問題

優先度に基づいて次に処理するワークアイテムを選択する。

コンテキスト

インテル® スレッディング・ビルディング・ブロック (インテル® TBB) のスケジューラーは、スケーラビリティーに基づく規則を使用してタスクを選択します。この規則は、タスクがスポーンまたはキューに入れられた順序に基づいており、タスクの内容は考慮しません。場合によっては、優先度の関係に基づいてワークを選択するほうが良いこともあります。

影響

ソリューション

ワークを共有ワークパイルに入れます。タスク実行がパイルから実際のワークを選択できるように、特定のワークからタスクを分離します。

サンプル

次のサンプルは、3 つの優先度を実装します。ユーザー・インターフェイスとトップレベルの実装が続きます。

enum Priority {
   P_High,
   P_Medium,
   P_Low
};
 
template<typename Func>
void EnqueueWork( Priority p, Func f ) {
   WorkItem* item = new ConcreteWorkItem<Func>( p, f );
   ReadyPile.add(item);
}

呼び出し元はルーチン EnqueueWork に優先度 p とファンクター f を提供します。ファンクターはラムダ式によるものかもしれません。EnqueueWork は f を WorkItem としてパッケージし、グローバル・オブジェクト ReadyPile に追加します。

WorkItem クラスは、不明な型のファンクターを実行するための統一されたインターフェイスを提供します。

// 優先度を付けるワークの抽象基本クラス
class WorkItem {
public:
   WorkItem( Priority p ) : priority(p) {}
   // 派生クラスは実際のワークを定義
   virtual void run() = 0;
   const Priority priority;
};
 
template<typename Func>
class ConcreteWorkItem: public WorkItem {
   Func f;
   /* オーバーライド */ void run() {
       f();
       delete this;
   }
public:
   ConcreteWorkItem( Priority p, const Func& f_ ) :
       WorkItem(p), f(f_)
   {}
};

ReadyPile クラスはコアパターンを含みます。ワークのコレクションを保持して、コレクションからワークを選択するタスクを送ります。

class ReadyPileType {
   // 各優先度レベルごとに 1 つのキュー
   tbb::concurrent_queue<WorkItem*> level[P_Low+1];
public:
   void add( WorkItem* item ) {
       level[item->priority].push(item);
       tbb::task::enqueue(*new(tbb::task::allocate_root()) RunWorkItem);
   }
   void runNextWorkItem() {
       // アイテムの優先度順にキューをスキャン
       WorkItem* item=NULL;
       for( int i=P_High; i<=P_Low; ++i )
           if( level[i].try_pop(item) )
               break;
       assert(item);
       item->run();
   }
};
 
ReadyPileType ReadyPile;

add(item) によってキューに入れられたタスクは、必ずしもそのアイテムを実行するわけではありません。タスクは runNextWorkItem() を実行し、より優先度の高いアイテムが見つかることがあります。各アイテムにつき 1 つのタスクがありますが、マッピングにより、タスクがいつ作成されるかではなく、タスクがいつ実際に実行されるかを指定できます。

RunWorkItem クラスの詳細は次のとおりです。

class RunWorkItem: public tbb::task {
   /* オーバーライド */tbb::task* execute(); // 仮想メソッドのプライベート・オーバーライド
};
...
tbb::task* RunWorkItem::execute() { 
   ReadyPile.runNextWorkItem();
   return NULL;
};

RunWorkItem オブジェクトは代替可能です。インテル® TBB のスケジューラーは、これらのオブジェクトを使用して、どのワークアイテムを行うかではなく、いつワークアイテムを行うかを決定します。呼び出しはすべて task 基本クラス経由でディスパッチされるため、task::execute 仮想メソッドのオーバーライドはプライベートです。

ほかの優先度手法は ReadyPileType の内部を変更することで実装できます。非常に細粒度の優先度を実装するには、優先度キューを使用することができます。

パターンのスケーラビリティーは ReadyPileType のスケーラビリティーによって制限されるため、この部分には理想的にスケーラブルなコンカレント・コンテナーを使用するべきです。

親トピック: デザインパターン