6

OpenStack を使用して学生が限られた数の仮想マシンにアクセスできるようにする Python アプリケーションを作成しています。

学生は、現在または将来の予約を行うことができます。

スロット/予約が利用可能な場合は学生が VM を予約できるようにしながら、いつでもスケジュールされる仮想マシンの数を X に制限する必要があります。

予約オブジェクトは次のようになります (sqlalchemy)。リクエストされた予約の開始時間と長さがわかり、その時点で既存の予約を調べて、リクエストされた期間に予約が多すぎるかどうかを確認する必要があります。*_job フィールドは、APScheduler ジョブの名前です。

class Reservation(Entity):
    student = ManyToOne('Student', required=True)
    class_id = ManyToOne('Class', required=True)
    image = ManyToOne('Image', required=True)
    # openstack image id filled in once the instance is started
    instance_id = Field(UnicodeText)

    # apscheduler jobs
    stop_instance_job = Field(UnicodeText)
    start_instance_job = Field(UnicodeText)
    warn_reservation_ending_job = Field(UnicodeText)
    check_instance_job = Field(UnicodeText)

スケジュール アルゴリズムなどの例をどこで探すべきかについての指針はありますか? 何を検索すればよいのかさえ明確ではありません...

ありがとう。

4

1 に答える 1

2

グリッド ベースのスケジューラを検索する必要があります。通常、スケジューラーは実際の実行時間 (またはリソース使用時間) を認識せず、複雑なヒューリスティックを使用して問題の所要時間を推測します (グリッド スケジューラーに関するヒューリスティックについては、PDF ダウンロード グリッド ベースでのスケジューリングの説明を参照してください)。時間の経過に伴うワークロードを表すための基本的なグリッドを使用した、より単純なアプローチが、ニーズを満たす可能性が最も高くなります。Python には、私が知っている素晴らしいグリッド オブジェクト ライブラリはありません (以前に C++ と Python でいくつか実装したことがありますが、それほど難しくはありません)。多次元オブジェクトをより簡単に解釈するには、numpy パッケージを参照する必要があります。これにより、グリッドを簡単にエミュレートまたは実装できます。

Msw は、ジョブ スケジューリングの一形態である Dijkstra の Banker's Algorithm について言及しましたが、問題は現在の状態よりも将来の状態に関心があり、タスク時間を正確に予測する (真の値を知る) ことができます。したがって、T(タイムステップ) × N (リソースの数 -- 1 の場合もある) × M (最大リソース予約) のグリッドで、ジョブの登録時に入力するグリッドで十分です。特定のタイムスロットで特定のジョブをスケジュールできるかどうかを判断するには、グリッドのサブセクション (start, stop)x(required_resources)x(1,M) で O(task_length * M) チェックを行い、空のスロットを探します。

特定のジョブの適切な場所を見つける (開始時刻を選択する) ことは、より困難なタスクであり、変更されたダイクストラのアルゴリズムによって、または標準のスケジューラから達成されます (msw のコメントは、タイムスロット機能チェックよりもこのタスクに役立ちます)。 . オンラインのスケジューラ コンテンツの多くは、操作の種類 (I/O かどうか) を重視する OS プロセス スケジューリングに固有のものであり、抽象的なリソースの使用よりも予想よりも時間がかかる場合のペナルティであることに注意してください。そのため、Google でスケジューラを検索すると、任意のデータに対する手法ではなく、Linux スケジューラの実装が得られることがよくあります。Shortest ジョブ スケジューラを調べてみてください。これは、多くの場合、よりシンプルで、OS タスクへの依存度が低いためです。

于 2012-08-01T18:05:28.757 に答える