JP2020024636A - スケジューリング装置、スケジューリングシステム、スケジューリング方法及びプログラム - Google Patents

Abstract

【課題】中断等を行うジョブを選択する。【解決手段】スケジューリング装置は、記憶部と、処理回路と、を備える。記憶部は、実行中のジョブの情報を記憶する。処理回路は、ジョブを受け付け、前記受け付けたジョブの実行リソースを確保できない場合に、前記実行中のジョブの情報に基づいて、前記実行中のジョブのうち前記受け付けたジョブよりも優先度が低いジョブの少なくとも１つを停止候補として選択し、前記停止候補に対して停止命令を発行する。【選択図】図２

Description

本発明は、スケジューリング装置、スケジューリングシステム、スケジューリング方法及びプログラムに関する。

コンピュータにおいて複数のジョブを同時に実行することは広く行われている。クラスタとして実装されているコンピュータに対しても、クラスタ中の１又は複数のコンピュータを同じタイミングで複数のジョブが起動されるように実装されることが多い。クラスタは、複数のユーザがアクセス可能であり、これら複数のユーザの各々がジョブを実行することができるように実装されていることが多い。

このような場合、リソースが十分に確保できない状態において、あるユーザが優先度の高いジョブを実行しようとすると、他のジョブを中断又は停止させることとなる。この中断等を行うジョブは、各ジョブに割り振られた優先度等さまざまな指標に基づいて決定される。クラスタを用いて行う計算は膨大な計算量であるものが多く、これらの膨大な計算量を有するジョブの中からどのように中断等を行うジョブを抽出するのかは課題の１つとなっている。

特許第６１２１４３１号公報 特開２０１８−２６０５０号公報

そこで、一実施形態では、中断等を行うジョブを選択するスケジューリング装置を提供する。

一実施形態によれば、スケジューリング装置は、実行中のジョブの情報を記憶する記憶部と、ジョブを受け付け、前記受け付けたジョブの実行リソースを確保できない場合に、前記実行中のジョブの情報に基づいて、前記実行中のジョブのうち前記受け付けたジョブよりも優先度が低いジョブの少なくとも１つを停止候補として選択し、前記停止候補に対して停止命令を発行する、処理回路と、を備える。

一実施形態に係るスケジューリング装置が実装されたシステムの一例を示す図。 一実施形態に係るスケジューリング装置の一例を示すブロック図。 一実施形態に係るジョブ実行装置の一例を示すブロック図。 ジョブ実行中の一例を示す概念図。 複数ジョブ実行中の一例を示す概念図。 優先度の高いジョブがエンキューされた一例を示す概念図。 優先度の高いジョブがエンキューされた別例を示す概念図。 一実施形態に係るスケジューリング装置の処理の一例を示すフローチャート。 一実施形態に係る処理の別の例を示すフローチャート。 一実施形態に係る処理のさらに別の例を示すフローチャート。 一実施形態に係るジョブ実行装置の処理の一例を示すフローチャート。 装置実装のハードウェア構成例を示す図。

以下、図面を参照して本発明の実施形態について説明する。図面及び実施形態の説明は一例として示すものであり、本発明を限定するものではない。

図１は、一実施形態に係るスケジューリング装置を用いたシステムの一例を示す図である。ユーザがクライアントからジョブを管理サーバに登録、又は、送信等すると、管理サーバが、当該ジョブにおいて利用される計算資源を判断し、計算サーバにジョブ（より細かくは、タスク）を振り分ける。このように、ユーザからの命令に基づいて、管理サーバによりジョブがクラスタにおいて実行される。ユーザは１であるとは限られず、例えば、複数のユーザが複数のクライアントを介して管理サーバにジョブをデプロイすることも可能である。

なお、図１においては、クラスタを構成するのは計算サーバとしているが、これには限られない。例えば、アクセラレータ等に搭載されている演算コア等の粒度であってもよい。計算サーバは、クラウド上に形成されているクラスタであってもよいし、オンプレミスに形成されているクラスタであってもよい。また、クラスタとは、上述した演算コア等の集合であってもよく、すなわち、図１においては複数のサーバが存在しているが、１つのサーバ内における演算コア等へのジョブ（又はタスク）の割り当てにも以下の説明におけるスケジューリングは適用できるものとする。

また、クライアントから管理サーバへのジョブ等の送信、及び、管理サーバから計算サーバへのジョブ等の送信は、仮想マシン環境を介して行ってもよい。演算の計算サーバへのデプロイは、例えば、コンテナを用いて行ってもよい。これらの手法は、一般的なものでよく、特定の技術に限られるものではない。

一実施形態に係るスケジューリング装置は、例えば、管理サーバに実装される。管理サーバは、独立したものとして記載されているがこれには限られず、クラスタとして構成されている計算サーバのうち少なくとも１つが管理サーバの機能を備えていてもよい。

図２は、一実施形態に係るスケジューリング装置の機能を示すブロック図の一例である。スケジューリング装置１０は、例えば、ジョブスケジューラとして動作する装置であり、ジョブ受付部１００と、優先度取得部１０２と、コスト取得部１１０と、記憶部１０４と、ジョブキュー１０６と、停止命令発行部１１２と、ＳＳ時刻取得部１０８と、を備える。一例として、図２のクライアントは、図１のクライアントに対応する。同様に、図２スケジューリング装置１０、ジョブ実行装置２０は、図１の管理サーバ、計算サーバにそれぞれ実装されるが、これに限られる構成でなくともよい。

ジョブ受付部１００は、ユーザの指示によりジョブを受け付ける。この指示は、例えば、クライアントを介してスケジューリング装置１０のジョブ受付部１００へと送信される。このジョブ受付部１００は、さらに、ジョブキュー１０６にエンキューされているジョブ及び／又はジョブ実行装置２０において実行中であるジョブに使用されているリソースに基づいて、受け付けたジョブがそのタイミングにおいて実行可能であるか否かを判断する判断手段として機能してもよい。

優先度取得部１０２は、ジョブ受付部１００が受け付けたジョブの優先度を取得する。取得した優先度は、ジョブと紐付けて記憶部１０４に記憶しておいてもよい。優先度とは、一般的にジョブに付与される優先度であり、例えば、優先度高、優先度中、優先度低、等のランク付けがされる。これには限られず、数値でさらに複数の優先度を表してもよいし、２段階の優先度（例えば、高、低）としてもよい。優先度は、クライアントにより設定されるものであってもよいし、ユーザが設定できるものであってもよい。

記憶部１０４は、スケジューリング装置１０の動作に必要な情報を記憶する。例えば、ジョブ受付部１００が受け付けたジョブに関する情報、既に動作しているジョブに関する情報、動作しているジョブのコスト計算に必要となる情報、各ジョブから送信されてきたスナップショットを取得した時間に関する情報等が記憶される。この他、スケジューリング装置１０がソフトウェアにより動作している場合には、当該ソフトウェアを動作するために必要なプログラム、又は、バイナリファイル等を記憶していてもよい。

ジョブキュー１０６は、ジョブ受付部１００が受け付けたジョブをエンキューしておくキューである。このジョブキュー１０６は、通常のキューで構成されていてもよいし、優先度付キューで構成されていてもよい。優先度付キューで無い場合には、優先度の高いジョブが受け付けられた場合に、ジョブキュー１０６を介さずに優先して命令を、ジョブを実行するジョブ実行装置２０に送信してもよい。優先度付キューである場合には、例えば、優先度の高いジョブをキューの待ち行列の先頭付近に移動させてもよい。優先度付キューは、例えば、ヒープで実装されてもよいし、これ以外の実装であってもよい。デキューについては、ジョブ実行装置２０の空きリソースが十分に確保できるタイミングにおいて、キューの先頭にあるジョブをスケジューリング装置１０がジョブ実行装置２０へと送信してもよいし、ジョブ実行装置２０がキューの先頭にあるジョブを取得してもよい。

ＳＳ時刻取得部１０８は、ジョブ実行装置２０がスナップショット（ＳＳ：Snap Shot）を取得した時間をジョブ実行装置２０から取得する。例えば、ジョブ実行装置２０は、スナップショットを取得しはじめたタイミングにおいて、その時刻を記憶しておき、スナップショットが取得し終えた後に、ＳＳ時刻取得部１０８へと記憶した当該時刻を送信する。ＳＳ時刻取得部１０８は、この時刻を受信して取得する。取得した時刻は、ジョブと紐付けて記憶部１０４に記憶してもよいし、ＳＳ時刻取得部１０８が記憶しておいてもよい。１つのジョブにおいて適切なタイミングにおいてスナップショット（あるいは、状態をダンプした情報）を取得しておくことにより、中断したジョブがスナップショットを参照することにより再開することが可能となる。各ジョブが取得したスナップショットは、共有ストレージ等に記憶する。

すなわち、スナップショットは、各ジョブが当該スナップショットを取得した状態に復帰可能な情報である復帰情報として取得され、記憶される。そして、スナップショットの取得を開始した時刻は、各ジョブが復帰情報を取得した時刻である。このように、ＳＳ時刻取得部１０８は、動作中の各ジョブが復帰情報を取得した時刻を取得して記憶部１０４に記憶する。以下においては、スナップショットを用いて説明するが、他の復帰情報としては、例えば、適切なタイミングでダンプされた復帰に必要となるデータ集合等で代替することも可能である。

コスト取得部１１０は、ジョブキュー１０６にジョブがエンキューされている状態において、優先度の高いジョブがジョブ受付部１００により受付された場合に、そのタイミングにおいて動作している各ジョブのコストを取得する。このコスト取得部１１０は、さらに、取得したコストに基づいて、停止するジョブ（以下、単に停止候補とも記載する。）を選択する選択手段として機能してもよい。コストの取得は、記憶部１０４に記憶されている、各ジョブのスナップショットを取得した時刻に基づいて決定される。また、各ジョブのコスト計算に利用する情報にも依存していてもよい。

コスト計算に利用する情報とは、例えば、ジョブが使用する演算コアの個数、メモリ使用量、ハードディスク使用量、通信帯域、演算を行う際に発生する熱量、消費電力、又は、これらの情報を一元的に理解できるように金額若しくは所定の基準値に対する比率等により示される情報であり、単位時間あたりの指標となる情報である。コスト取得部１１０は、例えば、スナップショットを取得した時刻から現在時刻までの経過時間をコストとしてもよいし、この経過時間と、上記の単位時間あたりの指標とを乗算した値をコストとしてもよいし、さらには、優先度等の他のパラメータを用いてコストを計算するような関数に基づいてコストを求めてもよい。

停止命令発行部１１２は、コスト取得部１１０が取得した各ジョブのコストについて、コストの低いジョブの動作を停止する命令を発行し、ジョブ実行装置２０へと送信する。ジョブ実行装置２０は、停止命令に基づいて、コストの低いジョブの動作を停止する。ジョブ実行装置２０は、停止した後、当該ジョブに利用されていたリソースが利用可能なリソースとなったことをスケジューリング装置１０へと送信してもよい。

なお、図２においては、ジョブキュー１０６は、スケジューリング装置１０に備えられているものであるが、これには限られない。例えば、スケジューリング装置１０とは別に備えられ、スケジューリング装置１０は、受け付けたジョブ、停止したジョブ（リソースが確保したタイミングで再開するジョブ）を、ジョブキュー１０６へとエンキューするような構成であってもよい。

図３は、一実施形態に係るジョブ実行装置２０の機能を示すブロック図の一例である。ジョブ実行装置２０は、演算実行部２００と、ＳＳ取得部２０２と、時間通知部２０４と、を備える。このジョブ実行装置２０は、処理回路上に仮想的に実装されているものであってもよく、具体的なハードウェア構成を有しない（より詳しくは、具体的に構成を考慮しなくてもよい）コンテナのようなものであってもよい。

演算実行部２００は、ジョブにおいて実行されるべき演算を実行する。演算の実行は、例えば、アクセラレータ上に実装されている演算コアのような処理回路を用いてもよい。この演算実行部２００は、ジョブキュー１０６からジョブ実行装置２０へとジョブが送信又はジョブ実行装置２０が生成されると、ストレージ３０に当該ジョブについての復帰情報、すなわち、スナップショットが記録されているか否かを確認する。

当該ジョブについてスナップショットが無い場合、初期化を行った後にジョブを実行する。当該ジョブについてスナップショットがある場合、当該スナップショットを用いて、停止、又は、中断されているジョブを再開する。

ＳＳ取得部２０２は、ジョブにおいて演算処理を行っている間に、所定のタイミングで復帰情報としてスナップショットを取得し、ストレージ３０に記憶する。スナップショットは、例えば、演算に必要となるパラメータ、それまでの演算により最適化されているパラメータ、乱数のシード及びスナップショット取得時における乱数表における位置等、並びに、その他の演算に必要となるパラメータ又は演算の途中経過として取得されうるパラメータを記録することにより取得される。このように、スナップショットは、処理中のジョブ全体のスナップショットであってもよいし、状態を復帰させるために必要なデータを、データごとにダンプした情報の集合をも含む概念であってもよい。

上述したように、演算実行部２００によりジョブが実行されると、当該ジョブが新たな演算を行うのか、停止、中断された状態から再開するのかを判断する必要がある。このため、ＳＳ取得部２０２は、スナップショットにジョブの識別子等、いずれのジョブのスナップショットであるかの情報を付与してストレージ３０に記憶させてもよい。あるいは、ストレージ３０内にテーブル等を備えておき、当該テーブル等にスナップショットを記憶したジョブに関する情報を記憶してもよい。ジョブに関する情報は、例えば、ジョブに固有に割り振られたＩＤを用いてもよいし、ハッシュ値等ジョブから得られる情報を用いてもよい。

ＳＳ取得部２０２は、さらに、スナップショットの取得を開始した時刻を取得する。スナップショットを取得し終えた後、時間通知部２０４は、ＳＳ取得部２０２が取得した開始時刻をスケジューリング装置１０へと送信する。

ジョブを複数のノードで並列演算している場合には、各ノードにおいてスナップショットを取得してもよい。これには限られず、各ノードの情報をマスターノードへと集約し、スナップショットを取得してもよい。各ノードにおいてスナップショットを取得する場合には、例えば、最後に取得したスナップショットに基づいて時刻を記憶するが、これには限られない。

ストレージ３０に既に同じジョブのスナップショットがある場合には、ＳＳ取得部２０２は、スナップショットを取得したタイミングにおいて、当該過去のスナップショットを消去（削除）してもよい。あるいは、所定の個数のスナップショットを残し、当該タイミングにおいて、所定の個数以上のスナップショットがある場合には、一番古いスナップショットを消去してもよい。この所定の個数は、ジョブごとに設定されてもよい。

ストレージ３０は、上記のスナップショットを記憶するための記憶領域である。このストレージ３０は、ジョブ実行装置２０の外部に備えられ、複数のジョブ実行装置２０からアクセス可能な共有のストレージであってもよい。また、ストレージ３０は、ファイルストレージであってもよいし、オブジェクトストレージであってもよい。

複数のジョブ実行装置２０からアクセス可能とすることにより、停止、中断されたジョブについて、新しいジョブ実行装置２０が仮想的に生成された場合においても、スナップショットが取得されているか否かを確認することが可能である。さらに、スナップショットが取得されている場合には、当該新しいジョブ実行装置２０において実行するジョブが過去に停止、中断されたタイミングにおいて取得されている最新のスナップショットを参照することが可能となる。

以下、概念図を用いて、上述したスケジューリング装置１０のスケジュールの様子を説明する。図４は、ジョブを実行中の様子を示す概念図である。

まず、スケジューリング装置１０がジョブの実行を指示する。この指示は、上述したように、ジョブキューへのエンキュー及びジョブキューからのデキューにより行われる。

ジョブ実行装置２０においてジョブが開始されると、所定のタイミングにおいて当該ジョブはスナップショットを取得する。図中の破線矢印で示すように、取得されたスナップショットはストレージ３０に記憶される。一方、スナップショットがジョブ実行装置２０において取得されたタイミング、又は、スナップショットがストレージ３０に記憶されたタイミングにおいて、スナップショットの取得を開始した時刻がスケジューリング装置１０へと送信される。

このように、演算リソースが足りない状況における優先度の高いジョブの割り込みが無い場合、所定のタイミングでスナップショットが取得され、ストレージ３０へと記憶され、ジョブが終了するまで演算が繰り返される。なお、所定のタイミングとは、スナップショットを取る間隔が等しいというわけではなく、例えば、最適化計算における所定のイテレーションごと、ビッグデータ処理における所定のデータ数ごと、評価関数の減少度合い、又は、機械学習における１エポックごと、等、ジョブに応じて変更することが可能である。もちろん、所定の時間ごとにスナップショットを取得してもよいが、この場合においても、厳密に同間隔である必要は無い。

図５は、複数のジョブが存在する場合のジョブの様子の一例を示す図である。この図において、開始、終了は、ジョブの開始、終了のタイミングをそれぞれ表し、破線で示したＳＳと記載されている箇所は、スナップショットを取得するタイミングを表す。

ジョブＡは、開始した後、所定の周期でスナップショットを取得し、ジョブを終了する。ジョブＢは、開始した後、所定の周期ではあるが、時間的にはジョブＡよりも短い周期でスナップショットを取得し、ジョブを終了する。ジョブの終了時間は、ジョブＡよりも前である。ジョブＣは、開始した後、スナップショットを取得することなく、終了する。

リソースが足りない状態において、優先度の高いジョブＸがジョブキュー１０６にエンキューされた場合にどのような動作をするかを説明する。ただし、ジョブＸは、ジョブＡ、Ｂ、Ｃのいずれかを停止させることにより使用するリソースが確保できるジョブであるとする。以下、ジョブキュー１０６は、優先度付キューであるとして説明する。優先度付キューではない場合には、一時的にキューからのデキューを停止させておき、ジョブＸをジョブキュー１０６にはエンキューをせずに直接演算装置へと送信して実行させることにより以下の説明と同様の効果を得ることができる。

ジョブＸをジョブキュー１０６にエンキューするタイミングにおいて、リソースが足りないと判断した場合、優先度取得部１０２は、ジョブＸの優先度を取得する。ジョブＸの優先度がジョブＡ、Ｂ、Ｃのいずれの優先度よりも高く無い場合には、ジョブキュー１０６にエンキューする。

一方、ジョブＸの優先度がジョブＡ、Ｂ、Ｃのいずれかよりも高い場合には、ジョブＸをジョブキュー１０６へとエンキューした上で、ジョブＡ、Ｂ、Ｃのいずれかを停止させる。ジョブＡ、Ｂ、Ｃにおいて、優先度がより低いジョブがある場合には、当該ジョブを停止させ、ジョブＸを実行させる。例えば、ジョブＡがジョブＢ、Ｃよりも優先度が低い場合には、ジョブＡを停止させることにより、ジョブキュー１０６にエンキューされているジョブＸが実行される。

ジョブＡ、Ｂ、Ｃの優先度に優劣が無い場合、ジョブＡ、Ｂ、Ｃのコストを取得して、コストの低いジョブを停止させる。

図６は、各ジョブにおいて直近でスナップショットを取得した時刻からの経過時間をコストとして取得する場合についての概念図を示す。コスト取得部１１０は、ＳＳ時刻取得部１０８により記憶部１０４に記憶されている各ジョブについてのスナップショットを取得した時刻から、ジョブＸがジョブ受付部１００により受け付けられたタイミング、又は、ジョブＸがジョブキュー１０６にエンキューされたタイミングまでの時間を経過時間として算出し、算出した経過時間をコストとして取得する。

例えば、ジョブＸが、図示したタイミングにおいて受付、又は、エンキューされた場合、各コストは、実線の矢印で示したようになり、この場合、コストの大きさとして矢印の長さで比較をして、コストＡ＜コストＢ＜コストＣとなる。スナップショットが取得されていない場合、例えば、ジョブＣのような場合には、ジョブの開始時刻からの時間を取得する。

図に示すようにコストＡが最小となる場合、ジョブＡを停止させ、ジョブＸを実行させる。ジョブの停止は、コスト取得部１１０が取得したコストに基づいて停止命令発行部１１２がジョブＡに対してジョブを停止する命令を発行することにより実行される。ジョブＡが停止されると、優先度付キューにエンキューされているジョブＸの実行が開始される。

停止したジョブＡは、例えば、ジョブキュー１０６の先頭になるようにエンキューしてもよい。このようにしておくことにより、図６に示すように、ジョブＸの実行が終了した後、ジョブキュー１０６からジョブＡがデキューされ、ジョブＡの実行が開始される。実行を開始したジョブＡは、ストレージ３０に記憶されているスナップショットを参照し、停止位置からジョブを再開する。なお、ジョブＡの再エンキューは、必ずしもジョブキュー１０６の先頭にする必要は無く、ジョブＡよりも優先度の高い、あるいは、等しいジョブがジョブキュー内に存在する場合は、そのジョブの後に実行されるようにエンキューされてもよい。別の実装としては、単純に、ジョブキューの最後にエンキューしてもよい。

ジョブＸよりも先にジョブＣが終了した場合、ジョブＡが使用するリソースが足りるのであれば、ジョブＣに利用されていたリソースを用いてジョブＡがジョブの再開をしてもよい。このように、必ずしも停止以前に用いていたものと同じリソースを用いてジョブを再開する必要は無い。ストレージ３０を各リソースからアクセスできる共有ストレージとしておくことにより、スムーズなジョブの再開を行うことが可能となる。

図７は、コスト取得の別の例の場合のジョブ実行の様子を示す概略図である。図６と同じようなタイミングでジョブＸがエンキューされた場合であっても、コスト取得の方法によっては、必ずしもジョブＡが停止されるわけではない。

例えば、図７において、コストは、単位時間あたりのリソースの使用率（単位時間あたりのコスト）×直近のスナップショット取得からの時間、として計算されるものであるとする。ジョブＡの単位時間あたりのコストと時間を乗算したものが、ジョブＢの単位時間あたりのコストと時間を乗算したものよりも大きく、ジョブＡよりもジョブＣのコストが大きくなる場合、コストＢ＜コストＡ＜コストＣとなる。

この場合、ジョブＢを停止させ、ジョブＸの実行を開始する。そして、ジョブＢをジョブキュー１０６の先頭へエンキューする。このようにすることにより、ジョブＸを優先して実行し、かつ、停止したジョブＢをリソースが空き次第再開することが可能となる。

単位時間あたりのコストは、例えば、ＧＰＵ（Graphical Processing Unit）、ＣＰＵ（Central Processing Unit）、メモリ、ＨＤＤ（Hard Disc Drive）、ＦＰＧＡ（Field Programmable Gate Array）等の処理回路又は記憶領域の使用に関するコスト、あるいは、通信バス、インフィニバンド（Infini Band）等の通信コストを含むコストから計算されてもよい。もちろん、前述したように、発生する熱、消費電力等をコストとしてもよいし、これらの例を複合したものを時間あたりのコストとして計算してもよい。このように単位時間あたりのコストを一元的に数値にすることにより、コストの取得を簡易に行うことが可能となる。

図６及び図７の例においては、ジョブＸは、ジョブＡ、Ｂ、Ｃのいずれかを停止することでリソースが足りるものであるとしたが、これには限られない。例えば、１つのジョブだけを停止してもリソースが足りない場合には、複数のジョブを停止してもよい。停止候補の選択は、コストの低いジョブから順に選択し、優先度の高いジョブを実行するためのリソースが確保できるところまでのジョブを停止してもよい。別の手法としては、コストを取得するタイミングで使用しているリソースを考慮してもよい。

また、優先度は、高い、低い、であるものとしたが、３以上の優先度を有していてもよい。この場合、コストに拘わらず、優先度の低いジョブを停止候補として選択し、同じ優先度内では、上記のようにコストを計算することにより停止候補を選択してもよい。

図８は、上述したスケジューリングについての処理を示すフローチャートである。このフローチャートを用いて、上述のスケジューリングについて処理の流れを説明する。

まず、スケジューリング装置１０のジョブ受付部１００は、ジョブを受け付ける（Ｓ１００）。

次に、ジョブ受付部１００が受け付けたジョブをジョブキュー１０６にエンキューする（Ｓ１０２）。ジョブキュー１０６が優先度付キューである場合、受け付けたジョブの優先度にしたがいエンキューする。エンキューするタイミングで優先度を確認する場合、後述のＳ１０６を省略してもよい。

次に、受け付けたジョブを実行するためのリソースが十分にあるか否かを判定する（Ｓ１０４）。リソースが十分であるか否かは、リソースモニタ等によりモニタリングして判断してもよい。また、ジョブキュー１０６にジョブが既に存在している場合には、リソースが足りていないと判断してもよい。

リソースが足りている場合（Ｓ１０４：ＹＥＳ）、スケジューリング装置１０は、ジョブキュー１０６にエンキューされているジョブを順番に実行させるとともに、ジョブを受け付ける状態へと遷移する。リソースが足りていない場合（Ｓ１０４：ＮＯ）、優先度取得部１０２は、受け付けたジョブの優先度を取得する（Ｓ１０６）。

次に、実行されているジョブの優先度と、受け付けたジョブの優先度を比較する（Ｓ１０８）。受け付けたジョブの優先度が実行されているジョブの優先度よりも低いか、又は、優先度が同じである場合（Ｓ１０８：ＮＯ）、スケジューリング装置１０は、ジョブキュー１０６にエンキューされているジョブを順番に実行させるとともに、ジョブを受け付ける状態へと遷移する。

受け付けたジョブの優先度が、実行されているジョブの優先度よりも高い場合（Ｓ１０８：ＹＥＳ）、コスト取得部１１０は、動作中のジョブのコストを取得する（Ｓ１１０）。なお、優先度の低いジョブが１つだけ実行されている場合には、以下の選択処理を行わずに、Ｓ１１４の処理を行ってもよい。

次に、コスト取得部１１０が取得したコストに基づいて、停止するジョブ（停止候補）を選択する（Ｓ１１２）。停止候補は、エンキューされ、実行しようとしている優先度の高いジョブのリソースが確保できるまで、１又は複数のジョブについて、コストの小さい順に選択する。

次に、停止命令発行部１１２は、停止候補に対して、ジョブの停止命令を送信する（Ｓ１１４）。停止命令が発行されたジョブについて、ＳＳ取得部２０２は、復帰情報としてスナップショットを取得し、適切なストレージ３０へと格納する。そして、上述したように、スナップショットが取得された場合には、スナップショットを取得しはじめた時刻の情報をＳＳ時刻取得部１０８へと送信する。ＳＳ時刻取得部１０８は、取得した時刻を記憶部１０４へと格納するが、Ｓ１１４以降の適切なタイミング、例えば、ＳＳ時刻を取得したタイミング又は停止したジョブを再エンキューするタイミング等でこの時刻をする。

そして、停止候補をジョブキュー１０６へとエンキューする（Ｓ１１６）。停止されたことを確認した後にエンキューしてもよいし、停止命令を発行のタイミングで優先度の高いジョブよりも遅く実行されるようにエンキューしてもよい。

なお、図８には示されていないが、ジョブ実行装置２０からスナップショット（復帰情報）の取得時刻が送信された場合には、当該取得時刻を受信したタイミングにおいて、ＳＳ時刻取得部１０８は、記憶部１０４へ取得時刻を記憶させる。この場合、さらに、取得時刻が未来の時刻であった場合には、時刻の更新を拒否してもよい。

図９は、本実施形態の変形例に係る処理を示すフローチャートである。図８は、新たなジョブを受け付けた場合の処理であったが、図９においては、既に動作しているジョブの停止又は中断が発生した場合の処理を示すものである。

まず、何らかの原因により、ジョブの停止又は中断がされる（Ｓ１１８）。ジョブの停止又は中断は、ユーザが任意のタイミングで指示して行ってもよいし、計算サーバ又は管理サーバにおいて、実行不能になる状況が起こった場合にエラー処理として中止又は中断をしてもよい。

このような場合、ジョブキュー１０６にエンキューされているジョブの先頭、又は、ジョブキュー１０６に存在している最も優先度の高いジョブのうちエンキューされたタイミングが早いものを実行するリソースが足りているか否かを判定する（Ｓ１２０）。この後の処理は、図８に示す処理と同様である。このように、ジョブを受け付けた場合だけではなく、ジョブの停止／中断をフラグとしてスケジューリング装置１０が動作してもよい。

図１０は、本実施形態の別の変形例に係る処理を示すフローチャートである。優先度の判定（Ｓ１０８）までの処理は、図８に示した処理と同様である。優先度を判定した後、受け付けたジョブが必要とするリソースに対して、優先度が低いジョブがそのタイミングにおいて使用しているリソースの合計が少ない場合、優先度が低いジョブを中断させても解放されるリソースが少なく、受け付けたジョブを動作させることができない。

そこで、空き予定、すなわち、受け付けたジョブよりも優先度の低いジョブが使用しているリソースの合計が、受け付けたジョブのリソースよりも大きいか否か（以上であるか否か）を判断する（Ｓ１２２）。受け付けたジョブを実行するリソース（実行リソース）が確保できる場合（Ｓ１２２：ＹＥＳ）、Ｓ１１０からの処理を実行する。

一方で、受け付けたジョブを実行リソースの確保が困難である場合（Ｓ１２２：ＮＯ）、待機処理に移行する（Ｓ１２４）。この待機処理は、例えば、リソースが確保できるまで待機する処理である。リソースを確保することができたタイミングで実行させてもよい。別の例として、受け付けたジョブと同じ優先度のジョブが新たに受け付けられ、さらに、新たに受け付けたジョブの方が利用するリソースが少ない場合には、新たに受け付けられたジョブを実行させてもよい。

解放されるリソースが実行に必要なリソースよりも小さい場合には、優先度の低いジョブを停止させても受け付けたジョブを実行することができないので、優先度の低いジョブの実行を継続させる。このように、リソースに空きが出ないようにして、システム全体としてのリソースの使用率を向上させることも可能である。なお、図９のＳ１２２、Ｓ１２４は、図８の場合についても適用することが可能である。

図１１は、ジョブ実行装置２０の処理の流れを示すフローチャートである。以下の説明では、ジョブ実行装置２０としてマスターの装置が存在し、当該マスターの装置において各リソースを用いたジョブを実行しているものとする。これには限られず、ジョブキュー１０６にエンキューされているジョブが、リソースが十分に使用できる状態となったタイミングにおいて、コンテナとして新しいジョブ実行装置２０として生成される場合にも、以下の説明を適用することが可能である。コンテナは、例えば、ジョブ実行装置２０が実装されるクラスタ内のマスターの計算機で生成されてもよいし、スケジューリング装置１０が実装される、管理サーバ等のサーバで生成されてもよい。

まず、ジョブ実行装置２０は、ジョブキュー１０６にエンキューされている先頭のジョブを実行するために必要なリソースが存在するか否かを判断する（Ｓ２００）。リソースが十分にあいていない場合（Ｓ２００：ＮＯ）、待機状態へと戻る。この場合、リソースの空きができたことを検知して待機してもよいし、所定時間ごとにリソースの状態を確認して待機してもよい。

ジョブを実行するのに十分なリソースの空きがある場合（Ｓ２００：ＹＥＳ）、ジョブをデキューする（Ｓ２０２）。コンテナである場合、デキューすることにより、デキューしたジョブの実行を行うジョブ実行装置２０が生成されてもよい。

次に、ジョブ実行装置２０は、ストレージ３０を参照し、当該ジョブに対応するスナップショット（復帰情報）が存在するか否かを確認する（Ｓ２０４）。ジョブに対応するスナップショットが存在する場合（Ｓ２０４：ＹＥＳ）、演算実行部２００は、ストレージ３０に記憶されているスナップショットを参照、又は、スナップショットをダウンロード等することにより、スナップショットの状態からジョブを再開する（Ｓ２０６）。

スナップショットが存在しない場合（Ｓ２０４：ＮＯ）、演算実行部２００は、デキューしたジョブを新規のジョブとして初期状態から実行する。再開したジョブ、又は、新規のジョブを実行するとともに、所定のタイミングにおいて、ＳＳ取得部２０２は、スナップショットを取得し、ストレージ３０へと記憶させる（Ｓ２０８）。上述したように、スナップショットの取得を開始した時刻を記憶する。時間通知部２０４は、取得が終了したタイミングで取得を開始した時刻をスケジューリング装置１０へと送信する。

特に優先度の高いジョブが受け付けられず、停止命令を受信していない場合（Ｓ２１０：ＮＯ）、演算実行部２００は、演算の実行を続行する。そして、ジョブが終了するか否かを判断し（Ｓ２１４）、ジョブが終了していない場合（Ｓ２１４：ＮＯ）には、停止命令の受信の待機状態へと遷移する。フローチャートにおいて、Ｓ２１０とＳ２１４はシリアルに記載されているがこれには限られず、ジョブ実行状態においては、これらの２つの判断を並行して監視してもよい。

停止命令を受信した場合（Ｓ２１０：ＹＥＳ）、ジョブ実行装置２０は、ジョブの実行を停止し（Ｓ２１２）、待ち状態へと移行する。コンテナで実行している場合には、適切にコンテナを消去させてもよい。停止命令を受信せず（Ｓ２１０：ＮＯ）に、ジョブが終了した場合（Ｓ２１４：ＹＥＳ）も同様に、ジョブの待機状態、又は、コンテナの消去を行う。

ジョブ実行装置２０は、上記のように、マスターとして存在している装置があり、当該マスターの装置からジョブを実行してもよいし、各ジョブ実行装置２０が、コンテナとして生成されるものであってもよい。この実装は、コンピュータ、又は、クラスタ等の管理状態に応じて適切に変更できるものであり、本実施形態に記載の方法は、これらの管理方法に依存せずに実行できるものである。

以上のように、本実施形態によれば、スナップショットを利用し、優先度に応じたジョブのスケジューリングをすることが可能となる。スナップショットを取得した状態からのコストを計算することにより、優先度はもとより、クラスタ内のリソースの無駄を抑制するスケジューリングを行うことが可能となる。また、上述のスケジューリング装置１０、ジョブ実行装置２０、ストレージ３０を併せてスケジューリングシステムとして構成してもよい。また、ストレージ３０として不揮発性のメモリを用いた場合には通電状態に無い状態でもスナップショットが記憶され、クラスタを構成しているサーバのメンテナンス性を高めるとともに、既に計算されているデータに適用されるはずであったリソースの無駄を省くことも可能である。

スナップショット取得の時刻を利用してコストを計算することにより、例えば、機械学習、ビッグデータ利用等、一般的に計算時間又はリソースを含めた計算コストが大きい処理についても、優先度に基づいたスケジューリングを行うことが可能となる。これらの処理は、計算コストが大きくなるが、所定のタイミングごと（例えば、１エポックごと）にスナップショットを有効に取得することが可能である。

なお、動作中のプロセスのダンプを取得して中断したジョブの再開を行うライブマイグレーションを用いる場合においても、本実施形態を適用することは可能である。ライブマイグレーションを実行する場合、マイグレーションが実行される所定時間前に、仮想マシン上のゲストＯＳに対して開始が事前通知される。すなわち、ライブマイグレーションを行うためには、ある程度の時間が必要となる。そこで、この事前通知のタイミングにおいて、本実施形態に係るスケジューリング装置１０における停止ジョブの選定手法を用いることが可能である。

さらに、ライブマイグレーションを行う場合、ＩＰアドレス等のホストに関する情報や時刻に依存する動作がプログラムに含まれるとダンプを同じタイミングで取得する保証は無く、かつ、処理が複雑となり、実行するのが困難な場合がある。一方で、本実施形態によれば、このような場合においても、ソフトウェアレベルのスナップショットを利用することによりハードウェア等、実行環境が変化する場合にも対応することが可能である。

前述した実施形態におけるスケジューリング装置１０及びジョブ実行装置２０において、各機能は、アナログ回路、デジタル回路又はアナログ・デジタル混合回路で構成された回路であってもよい。また、各機能の制御を行う制御回路を備えていてもよい。各回路の実装は、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）等によるものであってもよい。

上記の全ての記載において、スケジューリング装置１０及びジョブ実行装置２０の少なくとも一部はハードウェアで構成されていてもよいし、ソフトウェアで構成され、ソフトウェアの情報処理によりＣＰＵ等が実施をしてもよい。ソフトウェアで構成される場合には、スケジューリング装置１０、ジョブ実行装置２０及びその少なくとも一部の機能を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記憶媒体に収納し、コンピュータに読み込ませて実行させるものであってもよい。記憶媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記憶媒体であってもよい。すなわち、ソフトウェアによる情報処理がハードウェア資源を用いて具体的に実装されるものであってもよい。さらに、ソフトウェアによる処理は、ＦＰＧＡ等の回路に実装され、ハードウェアが実行するものであってもよい。ジョブの実行は、例えば、ＧＰＵ等のアクセラレータを使用して行ってもよい。

例えば、コンピュータが読み取り可能な記憶媒体に記憶された専用のソフトウェアをコンピュータが読み出すことにより、コンピュータを上記の実施形態の装置とすることができる。記憶媒体の種類は特に限定されるものではない。また、通信ネットワークを介してダウンロードされた専用のソフトウェアをコンピュータがインストールすることにより、コンピュータを上記の実施形態の装置とすることができる。こうして、ソフトウェアによる情報処理が、ハードウェア資源を用いて、具体的に実装される。

例えば、スケジューリング装置１０及びジョブがプログラムとして記載され、ソフトウェアの処理によりハードウェア上で具体的に実行される場合、スケジューリング装置１０へのジョブのデプロイは、プラグイン、アドイン、アドオン等の簡易な設計とすることができる。この場合、事前に準備されているＡＰＩを読み出したり、必要なファイルとリンクをしたりすることにより、簡単に実装することが可能である。これらのプラグイン等により、スナップショットを取得する動作が実装されていてもよい。

図１２は、本発明の一実施形態におけるハードウェア構成の一例を示すブロック図である。スケジューリング装置１０及びジョブ実行装置２０は、プロセッサ７１と、主記憶装置７２と、補助記憶装置７３と、ネットワークインタフェース７４と、デバイスインタフェース７５と、を備え、これらがバス７６を介して接続されたコンピュータ装置７として実現できる。

なお、図１２のコンピュータ装置７は、各構成要素を一つ備えているが、同じ構成要素を複数備えていてもよい。また、図１２では、１台のコンピュータ装置７が示されているが、ソフトウェアが複数のコンピュータ装置にインストールされて、当該複数のコンピュータ装置それぞれがソフトウェアの異なる一部の処理を実行してもよい。

プロセッサ７１は、コンピュータの制御装置および演算装置を含む電子回路（処理回路、Processing circuit、Processing circuitry）である。プロセッサ７１は、コンピュータ装置７の内部構成の各装置などから入力されたデータやプログラムに基づいて演算処理を行い、演算結果や制御信号を各装置などに出力する。具体的には、プロセッサ７１は、コンピュータ装置７のＯＳ（オペレーティングシステム）や、アプリケーションなどを実行することにより、コンピュータ装置７を構成する各構成要素を制御する。プロセッサ７１は、上記の処理を行うことができれば特に限られるものではない。スケジューリング装置１０、ジョブ実行装置２０及びそれらの各構成要素は、プロセッサ７１により実現される。ここで、処理回路とは、１チップ上に配置された１又は複数の電気回路を指してもよいし、２つ以上のチップあるいはデバイス上に配置された１又は複数の電気回路を指してもよい。

主記憶装置７２は、プロセッサ７１が実行する命令および各種データなどを記憶する記憶装置であり、主記憶装置７２に記憶された情報がプロセッサ７１により直接読み出される。補助記憶装置７３は、主記憶装置７２以外の記憶装置である。なお、これらの記憶装置は、電子情報を格納可能な任意の電子部品を意味するものとし、メモリでもストレージでもよい。また、メモリには、揮発性メモリと、不揮発性メモリがあるが、いずれでもよい。スケジューリング装置１０及びジョブ実行装置２０内において各種データを保存するためのメモリは、主記憶装置７２または補助記憶装置７３により実現されてもよい。例えば、記憶部１０４は、この主記憶装置７２又は補助記憶装置７３に実装されていてもよい。別の例として、アクセラレータが備えられている場合には、記憶部１０４は、当該アクセラレータに備えられているメモリ内に実装されていてもよい。

ネットワークインタフェース７４は、無線または有線により、通信ネットワーク８に接続するためのインタフェースである。ネットワークインタフェース７４は、既存の通信規格に適合したものを用いればよい。ネットワークインタフェース７４により、通信ネットワーク８を介して通信接続された外部装置９Ａと情報のやり取りが行われてもよい。

外部装置９Ａは、例えば、カメラ、モーションキャプチャ、出力先デバイス、外部のセンサ、入力元デバイスなどが含まれる。また、外部装置９Ａは、スケジューリング装置１０及びジョブ実行装置２０の構成要素の一部の機能を有する装置でもよい。そして、コンピュータ装置７は、スケジューリング装置１０及びジョブ実行装置２０の処理結果の一部を、クラウドサービスのように通信ネットワーク８を介して受け取ってもよい。

デバイスインタフェース７５は、外部装置９Ｂと直接接続するＵＳＢ（Universal Serial Bus）などのインタフェースである。外部装置９Ｂは、外部記憶媒体でもよいし、ストレージ装置でもよい。記憶部１０４は、外部装置９Ｂにより実現されてもよい。

外部装置９Ｂは出力装置でもよい。出力装置は、例えば、画像を表示するための表示装置でもよいし、音声などを出力する装置などでもよい。例えば、ＬＣＤ（Liquid Crystal Display）、ＣＲＴ（Cathode Ray Tube）、ＰＤＰ（Plasma Display Panel）、スピーカなどがあるが、これらに限られるものではない。

なお、外部装置９Ｂは入力装置でもよい。入力装置は、キーボード、マウス、タッチパネルなどのデバイスを備え、これらのデバイスにより入力された情報をコンピュータ装置７に与える。入力装置からの信号はプロセッサ７１に出力される。

上記の全ての記載に基づいて、本発明の追加、効果又は種々の変形を当業者であれば想到できるかもしれないが、本発明の態様は、上記した個々の実施形態に限定されるものではない。特許請求の範囲に規定された内容及びその均等物から導き出される本発明の概念的な思想と趣旨を逸脱しない範囲において種々の追加、変更及び部分的削除が可能である。例えば、前述した全ての実施形態において、説明に用いた数値は、一例として示したものであり、これらに限られるものではない。

１０：スケジューリング装置、１００：ジョブ受付部、１０２：優先度取得部、１０４：記憶部、１０６：ジョブキュー、１０８：ＳＳ時刻取得部、１１０：コスト取得部、１１２：停止命令発行部、２０：ジョブ実行装置、２００：演算実行部、２０２：ＳＳ取得部、２０４：時間通知部、３０：ストレージ

Claims (9)

1. 実行中のジョブの情報を記憶する、記憶部と、
   ジョブを受け付け、前記受け付けたジョブの実行リソースを確保できない場合に、前記実行中のジョブの情報に基づいて、前記実行中のジョブのうち前記受け付けたジョブよりも優先度が低いジョブの少なくとも１つを停止候補として選択し、前記停止候補に対して停止命令を発行する、処理回路と、
   を備えるスケジューリング装置。
2. 前記記憶部に記憶されている前記実行中のジョブの情報は、前記実行中のジョブの復帰情報を取得した時刻に関する情報を備え、
   前記処理回路は、前記時刻からの経過時間に基づいて、前記停止候補を選択する、
   請求項１に記載のスケジューリング装置。
3. 前記記憶部に記憶されている前記実行中のジョブの情報は、前記実行中のジョブの単位時間あたりのコストに関する情報を備え、
   前記処理回路は、前記時刻からの経過時間と前記単位時間あたりのコストとの乗算値に基づいて、前記停止候補を選択する、
   請求項２に記載のスケジューリング装置。
4. 前記復帰情報は、前記実行中のジョブのスナップショットである、請求項２又は請求項３に記載のスケジューリング装置。
5. 前記処理回路は、前記停止候補が停止した後、又は、前記停止命令を発行した後に、停止した前記停止候補を実行待ち状態にする、請求項１乃至請求項４のいずれかに記載のスケジューリング装置。
6. ジョブを受け付ける、クライアントと、
   請求項１乃至請求項５のいずれかに記載のスケジューリング装置と、
   前記スケジューリング装置が前記ジョブをエンキューする、ジョブキューと、
   前記ジョブキューにエンキューされている順序にしたがい、前記ジョブを実行する、ジョブ実行装置と、
   を備えるスケジューリングシステム。
7. 前記ジョブ実行装置は、コンテナにより実装される、請求項６に記載のスケジューリングシステム。
8. 実行中のジョブの情報を記憶するステップと、
   ジョブを受け付けるステップと、
   前記受け付けたジョブを実行するリソースが確保できるか否かを判断するステップと、
   前記受け付けたジョブを実行するリソースを確保できない場合に、前記実行中のジョブの情報に基づいて、前記実行中のジョブのうち前記受け付けたジョブよりも優先度が低いジョブの少なくとも１つを停止候補として選択するステップと、
   前記停止候補に対して停止命令を発行するステップと、
   を備えるスケジューリング方法。
9. コンピュータを、
   実行中のジョブの情報を記憶する、記憶手段、
   ジョブを受け付ける、受付手段、
   前記受け付けたジョブを実行するリソースが確保できるか否かを判断する、判断手段、
   前記受け付けたジョブを実行するリソースを確保できない場合に、前記実行中のジョブの情報に基づいて、前記実行中のジョブのうち前記受け付けたジョブよりも優先度が低いジョブの少なくとも１つを停止候補として選択し、前記停止候補に対して停止命令を発行する、停止命令発行手段、
   として機能させるプログラム。

Images