Xen creditスケジューラのアルゴリズム概要

Xen3.0がリリースされた時は、sedfスケジューラ（Simple Early Deadline First Scheduler）が、Xenの標準ドメインスケジューラとして採用されていました。Xen 3.0.3ではそれに代わり creditスケジューラが標準となっています。この creditスケジューラは、どのような特徴をもったスケジューラでしょうか？
creditスケジューラは、SMP環境を効率よく利用することを目的に導入されました。
物理CPU間の負荷バランスが崩れた時、ドメイン（仮想CPU）が動作する物理CPUを変更することにより、物理CPU間の負荷バランスを取ります。また、より運用者が期待するCPU時間割り当てに近づけることも目指したアルゴリズムを採用しています。

creditスケジューラ上で動作するドメインには重み（weight）付けを行なうことができ、一定時間毎にその重みに応じたCPU持ち時間を各ドメインに与えます。
この時、現在あまり活発に動作していないと判断されたドメインには、新たにCPU持ち時間を与えないようにするという点は、工夫されている点のひとつです。新たに与えられるCPU持ち時間は、活発に動作している（ACTIVEな）ドメイン間のみで分け合います。
割り当てられたCPU持ち時間を使い切ったドメイン（図中ではOVERという状態にあるドメイン）も、スケジューリング対象にはなりますが、CPU持ち時間が残っているドメインが動作していない時に限り動作可能です。CPU持ち時間を使い切ったドメインが動作する時も、利用した時間は計測され、CPU時間を前借りして動作しているものとして扱われます。このドメインが新たにCPU待ち時間が与えられた時には、この借りている時間を返却しなければなりません（脚注：借りた時間を返し切れなくならないように、ある一定量以上の時間は返却しなくてよい実装になっている）。
また、あるドメインが与えられたCPU持ち時間を使い切れず、その量が一定量を超えると、そのドメインは活発に動作していないものと判断され、そのCPU持ち時間がすべて没収されます。この時、新たなCPU持ち時間割り当ての対象ドメインからも外されます。とはいえ、このドメインもスケジューリング対象であることに変わりはなく、動作することができます。またこのドメインが活発に動作し始めると、また新たなCPU持ち時間割り当て対象ドメインに組み込みます。

物理CPUが空いている場合でも、あるドメインが一定量以上のCPUを使わないように制御する機能（CAPと呼ばれている）もあります。
このCAP指定をされたドメインは、割り当てられたCPU持ち時間を使い切ると（OVER状態）、スケジューリング対象から完全に外されます。ただし、新たなCPU持ち時間割り当て対象ドメインのひとつであり、再度CPU持ち時間を与えられ、スケジューリング対象に組み込まれます。

• 物理CPU間の負荷バランス機能があります。
• 各ドメイン（仮想CPU）は、原則ラウンドロビンで実行権が与えられます。
  ただし、休止状態から起床したばかりにドメインには高い優先度を与え、優先的に実行できるようにしています。

SMP環境での実行効率は、まだまだ改善の余地があります。
物理CPU間の負荷に偏りが出た場合、負荷バランスを取るように、ドメイン（仮想CPU）をスケジューリングする物理CPUを変更しますが、その決定アルゴリズムにはまだまだ改良の余地があります。キャッシュの利用効率、物理CPUに残っているTLBの再利用などを考慮した場合、ドメイン（仮想CPU）を別の物理CPUに移動させるべきと判断する閾値を上げた方が良さそうにも感じます。
またこのスケジューラは、まだNUMA環境を考慮していません。Linuxカーネルのように、同じドメインの仮想CPUは同じノードに割り付ける、また負荷バランスをとる場合もノードを跨いでドメイン（仮想CPU）を移動させないようなアルゴリズムを取り入れる必要があるでしょう。