JPH06202884A - マルチプログラム実行管理方法 - Google Patents

Abstract

(57)【要約】 【目的】 実行されるプログラムにその性質や数に特定
の制限が設けられていない汎用の計算機システムで時分
割方式でＣＰＵの占有権を各プログラムに与え、各プロ
グラムの実行の実時間を短縮する。 【構成】 複数のプログラムを同時実行する際、現在走
行している各プログラムが現在までにＣＰＵを占有した
時間であるＣＰＵ消費量と、実行に要するＣＰＵ占有時
間に相当する要求ＣＰＵ時間と、一定時間内にＣＰＵを
占有して走行したプログラムの平均走行数と、ユーザが
設定した負荷要因値とによりスケジューリング優先度を
計算する。該スケジューリング優先度に従って、各走行
プログラム記憶し、実行する。また、各プログラム毎に
実行に要したＣＰＵ占有時間の最大値と平均値を実行デ
ータとして保持し、プログラムを新たに実行する際、前
記実行データを要求ＣＰＵ時間としてスケジューリング
プログラム２に転送する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、計算機における複数
のプログラムの実行管理に関し、特に時分割方式でＣＰ
Ｕの占有権を各プログラムに与え、複数のプログラムの
同時実行を可能とするマルチプログラム実行管理方法の
改良に関する。

【０００２】

【従来の技術】 従来のプログラム・スケジューリング方法は、優先
権があるプログラムと無いプログラムが事前に判明して
いる場合、実行するプログラムに与えるＣＰＵの占有時
間を変化させていた。すなわち、優先権のあるプログラ
ムは、処理目標時間内に処理が完了するようにＣＰＵの
占有権を与える。一方優先権の無いプログラムは、処理
許容時間内に処理が完了するようにＣＰＵの占有権を調
整していた。これにより、複数のプログラムを同時に実
行しながら、且つ、実行プログラムに優先順位を与えて
いた（特開平３ １２５２２８）。

【０００３】また、別のプログラム・スケジューリン
グ方法として、実行中のプログラムの処理において、該
プログラムがＣＰＵを占有したＣＰＵ消費量とユーザが
設定した負荷要因値をパラメータとしてスケジューリン
グ優先度を計算する。このスケジューリング優先度によ
り各実行中のプログラムに順序をつける。この順序に従
って、各プログラムを実行していた。

【０００４】

【発明が解決しようとする課題】しかしながら、従来の
のプログラム・スケジューリング方法においては、実
行されるプログラムの優先権の有無が予め判明している
必要がある。このため、実行されるプログラムにその性
質や数に特定の制限を設けない汎用の計算機システムに
適用できない欠点があった。

【０００５】また一方、のプログラム・スケジューリ
ング方法では、そのプログラムが過去において、ＣＰＵ
を占有した時間がパラメータとなって該プログラムの優
先度を決定する。このため、より最近により多くの時間
ＣＰＵを占有したプログラムの優先度は、低くなる。よ
って、処理の終了が近づいたプログラムであっても過去
のＣＰＵの占有時間の影響が残っている間、実行されな
い場合がある。このため、各プログラムの実行の実時間
（処理の開始から終了までの時間）が長くなる欠点があ
った。

【０００６】この発明の目的は、実行されるプログラム
にその性質や数に特定の制限が設けられていない汎用の
計算機システムで時分割方式でＣＰＵの占有権を各プロ
グラムに与え、各プログラムの実行の実時間を短縮する
プログラム・スケジューリング方法を提供することにあ
る。

【０００７】

【課題を解決するための手段】この発明のマルチプログ
ラム実行管理方法は、複数のプログラムを同時実行する
際に、現在走行している各プログラムの実行の開始から
現在までにＣＰＵを占有した時間であるＣＰＵ消費量
と、各プログラムの実行に要するＣＰＵ占有時間に相当
する要求ＣＰＵ時間と、一定時間内にＣＰＵを占有して
走行したプログラムの平均走行数と、ユーザが設定した
負荷要因値とにより各走行プログラムのスケジューリン
グ優先度を計算し、該スケジューリング優先度に従って
各走行プログラムに順序をつけ、各プログラムをこの順
序に従って記憶し、この記憶された順序に従って各走行
プログラムの実行を行うことを特徴とする。

【０００８】また、各走行プログラム毎に実行に要した
ＣＰＵ占有時間の最大値と平均値を実行データとして保
持し、プログラムを新たに実行する際、該プログラムの
前記実行データを前記要求ＣＰＵ時間としてスケジュー
リングすることを特徴とする。

【０００９】

【作用】この発明のプログラム・スケジューリング方法
においては、現在走行している各プログラムの実行の開
始から現在までにＣＰＵを占有した時間であるＣＰＵ消
費量と、各プログラムの実行に要するＣＰＵ占有時間に
相当する要求ＣＰＵ時間と、一定時間内にＣＰＵを占有
して走行したプログラムの平均走行数と、ユーザが設定
した負荷要因値とにより各走行プログラムのスケジュー
リング優先度を計算する。そして、このスケジューリン
グ優先度に従って各走行中プログラムに順序を付ける。
この順序で記憶し、この記憶された順序に従って各走行
中プログラムにＣＰＵを占有させて処理を行う。

【００１０】さらに、各走行プログラム毎に実行に要し
たＣＰＵ占有時間の最大値と平均値を実行データとして
保持する。プログラムを新たに実行する際、該プログラ
ムの前記実行データを前記要求ＣＰＵ時間としてスケジ
ューリング優先度を計算する。そして、処理が完了する
と、その処理に要したＣＰＵ占有時間を加えて、実行デ
ータを更新して保持する。

【００１１】

【実施例】この発明の実施例では、ＵＮＩＸシステムを
使用し、この発明のスケジューリング機能を備えたマル
チプログラム管理方法を説明する。

【００１２】ＵＮＩＸシステムは、パーソナルコンピュ
ータ、エンジニアリングワークステーション、ミニコン
ピュータ、スーパーコンピュータ等のあらゆるレベルの
計算機をサポートするオペレーティングシステム（Ｏ
Ｓ）として幅広く利用されているものである。

【００１３】図１は、この発明の実施例であるスケジュ
ーリング機能を備えたマルチプログラム実行管理方法の
概念を示す図である。図１を参照しながら、この発明の
実施例を説明する。

【００１４】スケジューリング優先度計算プログラム１
は、走行可能なプログラムのスケジューリング優先度を
算出する。スケジューリングプログラム２は、前記スケ
ジューリング優先度計算プログラム１により算出された
前記スケジューリング優先度により走行可能プログラム
待ち行列に各プログラムを割り振る。プログラム実行統
計情報記憶部３は、実行可能なプログラムごとに過去の
実行時データとして、これまでの実行回数、これまでの
実行においてＣＰＵを占有した時間の平均値である平均
ＣＰＵ時間、これまでの実行においてＣＰＵを占有した
時間の最大値である最大ＣＰＵ時間を記憶するととも
に、プログラムを新たに実行する場合、前記平均ＣＰＵ
時間と最大ＣＰＵ時間を前記スケジューリングプログラ
ム２に転送する。走行可能プログラム待ち行列記憶部４
は、前記スケジューリングプログラム２が各プログラム
を割り振った行列と、各走行プログラムごとに計算され
たスケジューリング優先度等の情報を記憶する。この、
記憶される情報の種類等については、後述する。

【００１５】複数の走行プログラムの同時実行を行うた
めに、スケジューリング優先度計算プログラム１は、最
初に走行可能プログラムの要求ＣＰＵ残量の総和(all
d) を求める。

【００１６】 all d=rest d(1)+rest d(2)+・・・・ +rest d(n-1)+rest d(n) … (1) rest d(i) は、各走行プログラムの要求ＣＰＵ残量（過
去の実行時にＣＰＵを占有した平均時間または、最大時
間と今回の走行中にＣＰＵを占有した時間の差）であ
る。

【００１７】次に、最近のＣＰＵ利用の評価値（p cpu)
と最近のＣＰＵ利用要求の評価値（p demand) を計算す
る際の減衰フィルタ(filter)を計算する。

【００１８】 filter=(2*load)/(2*load+1) … (2) loadは、単位時間あたりにＣＰＵを占有して走行したプ
ログラム数の平均である。

【００１９】そして、各走行プログラムに対し、新たに
最近のＣＰＵ利用の評価値（p cpu)と最近のＣＰＵ利用
要求の評価値（p demand) を計算する。

【００２０】 p cpu(i)=filter*(t(i)+p cpu(i)) … (3) p demand(i)=k*filter*((all d-rest d(i))/all d+p demand(i)) … (4) t(i)は、前回スケジューリング優先度を計算して、今回
スケジューリング優先度を計算しなおす迄に各プログラ
ムがＣＰＵを占有した時間である最近のＣＰＵ消費量。
k は、負の値の重み付け定数で、システムの使用環境に
合わせて設定されている。

【００２１】上記(1)(2)(3)(4)式の結果を用いて、各走
行プログラムのスケジューリング優先度(p usrpri(i))
を算出する。ここで算出されるスケジューリング優先度
は、値が大きい程、プログラムの優先度は、低くなる。

【００２２】 p usrpri(i)=PUSER+p cpu(i)+p demand(i)+p nice(i) … (5) PUSER は、優先度に最低値を与えるものでユーザプログ
ラムがシステムプログラムより優先度が高くなることを
防止している。また、p nice(i) は、ユーザが設定する
負荷要因値である。

【００２３】この式により算出された走行プログラムの
スケジューリング優先度は、０〜１２７の値をとり、１
２７以上の値となる場合には、１２７となる。また、PU
SERよりも小さい値を取る場合には、PUSER と同じ値に
なる。

【００２４】スケジューリング優先度計算プログラム１
において、上記式(1) 〜(5) により算出された各走行プ
ログラムのスケジューリング優先度は、スケジューリン
グ手段２に渡される。この各走行プログラムのスケジュ
ーリング優先度よりスケジューリング手段２において、
各走行可能プログラム待ち行列のどの列に置くかを決定
する。図２は、走行可能プログラム待ち行列の概念図で
ある。ＵＮＩＸシステムにおいては、この走行可能プロ
グラム待ち行列の列は３２列ある。上記算出されたスケ
ジューリング優先度の値を４で割って、その値が、走行
可能プログラム待ち行列の対応する列に各プログラムを
割り振る。

【００２５】走行可能プログラム待ち行列記憶部３は、
前記スケジューリング手段２で割り振られた各プログラ
ムを行列として記憶するとともに各プログラムに対応す
る最近のスケジューリング優先度（p usrpri(i) ）、最
近のＣＰＵ利用の評価値（pcpu(i)）、最近のＣＰＵ利
用要求の評価値（p demand(i) ）、負荷要因値（p nice
(i) ）、最近のＣＰＵ消費量（t(i)）、総ＣＰＵ消費量
（used(i) ）、拡張要求ＣＰＵ量（ext d(i)）、要求Ｃ
ＰＵ残量（rest d(i) ）を保持する。ここで“最近の
“と表現されているのは、上記(1) 〜(5) 式によりスケ
ジューリング優先度が新しく計算されるまでの値を示
す。

【００２６】そして、スケジューリングプログラム２
は、走行可能プログラム待ち行列の優先度の高い列から
走行可能プログラム待ち行列を走査し、最初に出会った
空でない走行可能プログラム待ち行列に記憶されている
プログラムを選択する。この選択されたプログラムにＣ
ＰＵの占有権を渡す。該プログラムは、許されたＣＰＵ
の占有時間、ＣＰＵを占有して実行される。しかしなが
ら、スケジューリング優先度を計算しなおす時間が経過
すると、該プログラムの実行は、中断される。そして、
再度スケジューリング優先度を計算する。該プログラム
のＣＰＵの占有時間が経過し、まだ、スケジューリング
優先度を計算しなおす時間が経過していない場合、さら
に走行可能プログラム待ち行列を走査して次に優先度の
高いプログラムの実行を行う。一方、走行可能プログラ
ム待ち行列の列に複数のプログラムが登録されている場
合、その列の最初の行に登録されているプログラムを選
択する。上記同様にこのプログラムを実行する。実行
後、このプログラムは、登録されている列の最後尾に移
動し、つぎに、先頭に来たプログラムの処理を行う。ス
ケジューリング優先度を計算しなおす時間を使い切るま
で、各プログラムの実行を行う。スケジューリング優先
度を計算しなおす時間になると、走行中プログラムの実
行を中断し、再度スケジューリング優先度の計算を行
う。その後、上記動作を繰り返し行う。

【００２７】また、新しいプログラムを走行するとき、
スケジューリングプログラム２は、そのプログラムの起
動コマンド名をプログラム実行統計情報記憶部３に渡
す。プログラム実行統計情報記憶部３は、この起動コマ
ンド名を受けたことによりスケジューリングプログラム
２へ、該プログラムの平均ＣＰＵ時間、最大ＣＰＵ時間
を転送する。スケジューリングプログラム２は、この平
均ＣＰＵ時間を要求ＣＰＵ残量としてセットする。ま
た、最大ＣＰＵ時間と平均ＣＰＵ時間の差を拡張要求Ｃ
ＰＵ量としてセットする。これは、プログラムが走行中
に要求ＣＰＵの残量が０となった場合、要求ＣＰＵ残量
にセットされる。

【００２８】プログラムの実行が終了すると、スケジュ
ーリングプログラム２は、実行に要したＣＰＵの占有時
間をプログラム実行統計記憶部３に転送する。プログラ
ム実行統計記憶部３は、これにより過去の実行データと
なる、平均ＣＰＵ時間、最大ＣＰＵ時間、実行回数のデ
ータを更新する。

【００２９】この発明の実施例に基づいて動作確認のシ
ミュレーションを下記の条件で行った。

【００３０】プログラムの実行に許される１回のＣＰ
Ｕの占有時間は、１０ms。

【００３１】スケジューリング優先度を計算しなおす
時間は、１s 。

【００３２】プログラムは、５つで、各走行プログラ
ムとも３つのコマンドから構成されている。

【００３３】各プログラムのコマンドの要求ＣＰＵ量
は、下記に示す。

【００３４】 プログラム１ − ２００ｓ・５００ｓ・１００ｓ プログラム２ − ２００ｓ・４００ｓ・１００ｓ プログラム３ − ２００ｓ・６００ｓ・１００ｓ プログラム４ − ２００ｓ・５００ｓ・１００ｓ プログラム５ − ２００ｓ・４００ｓ・１００ｓ 各プログラムの処理開始時刻は、順に０、１００、２
００、３００、４００ｓである。

【００３５】(4) 式の負の重み付け定数であるk は、
−０．８とした。

【００３６】１分間の走行プログラム数から１秒間の
平均走行プログラム数を算出して、平均走行プログラム
数（load) とした。

【００３７】ユーザが設定する負荷要因値であるp ni
ce＝０。

【００３８】図３は、シミュレーション結果を示す図で
ある。図３（Ａ）は、本発明の実施例によるシミュレー
ション結果である。図３（Ｂ）は、比較のために従来の
スケジューリング方法（従来例の、式(5) の右辺第３
項であるp demand(i) を外した）によるシミュレーショ
ン結果である。

【００３９】図３（Ａ）の比較の項は、各処理の実時間
と処理全体の実時間を従来例のによるシミュレーショ
ンとの増減を比較して１００分率で表示したものであ
る。

【００４０】この発明の実施例であるシミュレーション
において、５つのプログラム中３つのプログラム２・４
・５が実時間の短縮が図られている。また、全体でも
３．３％の実時間の短縮が図れた。更に、プログラム２
においては、１０．５％もの大幅な実時間の短縮が図ら
れている。

【００４１】

【発明の効果】以上のように、この発明によれば、最近
のＣＰＵ利用要求の評価値をスケジューリング優先度の
計算に反映させることにより、実行の終了が近づいたプ
ログラムの優先度が上がる。これにより、各実行可能プ
ログラムの実行の実時間の短縮が図れる。

【図面の簡単な説明】

【図１】この発明の実施例であるマルチプログラム実行
管理方法の概念を示す図である。

【図２】同実施例である走行可能プログラム待ち行列記
憶部の概念を示す図である。

【図３】同実施例に基づくシミュレーション結果を示す
図である。

【符号の説明】

１−スケジューリング優先度計算プログラム ２−スケジューリングプログラム ３−プログラム実行統計情報記憶部 ４−走行可能プログラム待ち行列記憶部

Claims (2)

【特許請求の範囲】
1. 【請求項１】 複数のプログラムを同時実行する際に、
   現在走行している各プログラムの実行の開始から現在ま
   でにＣＰＵを占有した時間であるＣＰＵ消費量と、各プ
   ログラムの実行に要するＣＰＵ占有時間に相当する要求
   ＣＰＵ時間と、一定時間内にＣＰＵを占有して走行した
   プログラムの平均走行数と、ユーザが設定した負荷要因
   値とにより各走行プログラムのスケジューリング優先度
   を計算し、該スケジューリング優先度に従って各走行プ
   ログラムに順序をつけ、各プログラムをこの順序に従っ
   て記憶し、この記憶された順序に従って各走行プログラ
   ムの実行を行うことを特徴とするマルチプログラム実行
   管理方法。
2. 【請求項２】 各走行プログラム毎に実行に要したＣＰ
   Ｕ占有時間の最大値と平均値を実行データとして保持
   し、プログラムを新たに実行する際、該プログラムの前
   記実行データを前記要求ＣＰＵ時間としてスケジューリ
   ング優先度を計算することを特徴とする請求項１記載の
   マルチプログラム実行管理方法。