Pythonで予約を予約する（レストランではない）

Question

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

生徒は現在または将来のいずれかで予約を行うことができます。

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

予約オブジェクトは以下のようになります（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) 

スケジュールアルゴリズムの例などを探すためのポインタはありますか？私は何を探すべきか明確ではない...

ありがとう。

Answer 1

グリッドベースのスケジューラを検索する必要があります。通常、スケジューラは実際の実行時間（またはリソース使用時間）を知らず、複雑なヒューリスティックを使用して問題の発生時間を推測します（グリッドスケジューラのヒューリスティックはPDF download Describing Scheduling on Grid basisを参照してください）。時間の経過とともにワークロードを表現するための基本的なグリッドを使用した簡単なアプローチは、ニーズを満たす可能性が非常に高いでしょう。 Pythonには私が知っているすばらしいグリッドオブジェクトライブラリはありません（私はC++とPythonでいくつか実装していますが、あまり難しくありません）。グリッドを簡単にエミュレートまたは実装できる多次元オブジェクトの解釈を容易にするために、numpyパッケージを参照する必要があります。

Mswはジョブスケジューリングの一種であるDijkstraのBanker's Algorithmについて言及していますが、あなたの問題は現在の状態よりも未来の状態を気にしていますが、タスク時間の正確な値を知ることができます。したがって、ジョブが登録されたときに記入するM（最大リソース予約）グリッドによるN（リソースの数はわずか1かもしれません）によるT（タイムステップ）は十分です。特定のジョブが特定のタイムスロットでスケジューリングできるかどうかを判断するには、空スロットのグリッドのサブセクション（開始、停止）x（required_resources）x（1、M）のOチェックをtask_length *

特定のジョブの適切な場所を見つけること（開始時刻を選ぶこと）は、より困難な作業であり、変更されたDijkstraのアルゴリズム、または任意の標準スケジューラによって達成されるでしょう（mswのコメントは、タイムスロット能力チェック）。スケジューラのオンラインコンテンツの多くは、操作の種類（I/Oの有無）と、抽象リソースの使用よりも予想以上の時間がかかり過ぎることに対するペナルティを気にするOSのプロセススケジューリングに固有のものです。だから、スケジューラのためのGoogle検索は、任意のデータのテクニックではなく、Linuxスケジューラの実装を提供することがよくあります。最短のジョブスケジューラを探してみてください。ほとんどの場合、説明されているときにOSタスクに依存することはほとんどありません。