JPS5935454B2 - 優先順位決定方法および装置 - Google Patents

Description

【発明の詳細な説明】 本発明はマルチプログラミングを行う計算機システムに
おいて、プログラムに中央処理装置（ＣＰＵ）を割当て
るための優先順位を動的に制御する優先順位決定方法お
よび装置に関する。

一般に、マルチプログラミング方式の計算機システムに
おいては、各プログラムはそれぞれある優先順位を割当
てられ、この優先順位に基いてデイスパツチングと称す
るＣＰＵの割当てが制仰される。即ち、最も優先順位の
高い第１のプログラムがＣＰＵで実行されている（ラン
）伏態にあり、これよりも優先順位の低い第２のプログ
ラムは、ＣＰＵさえ割当てられればＣＰＵで実行可能な
（レデイ）状態ｌこあると仮定する。このとき、第１の
プログラムが、例えば、Ｉ／Ｏ命令を実行し、１／０動
作が完了するまでウエイト（ＷＡＩＴ）状態に入ると（
第１図１）、次に優先順位の高い第２のプログラムがＣ
ＰＵで実行され、ラン状態となる（第１図２）。ここで
、第１のプログラムのＩ／Ｏ動作が完了すると、第１の
プログラムは実行可能なレデイ（ＲＥＡＤＹ）状態とな
るが（第１図４）、現在ＣＰＵで実行している第２のプ
ログラムの方が第１のプログラムよりも優先順位が低い
ので、直ちに、ＣＰＵを割当てられ、ラン（ＲＵＮ）状
態となる（第１図２）。その結果、第２のプログラムは
、ＣＰＵを取り上げられ、レデイ状態にもどされる（第
１図（２）。優先順位が多数ある場合でも、同様に、レ
デイ伏態にあるプログラムのうち最も優先順位の高いプ
ログラムがＣＰＵで実行されることｌこなり、優先順位
を高くすることによりＣＰＵをそのプログラムに優先的
′こ割当てることができる。

従来、計算機システムにおいては、プログラムの緊急度
あるいはＩ／０命令の発生頻度等に応じて各プログラム
にデイスパツチの優先順位が与えられており、前述のご
とくこの優先順位によりＣＰＵでのプログラムの実行が
制闘されている。

１／０命令の発生頻度が高いプログラムに高いデイスパ
ツチングプライオリテイを与えることにより、システム
全体のスルーブツトを高くできることが知られている。

そして、Ｉ／Ｏ命令の発生頻度としては、そのプログラ
ムのウエイト状態にある時間すなわちウエイト時間と（
ＣＰＵ時間十ウエイト時間）との比が一般に使用されて
いる。しかしながら、この従来の方式においては、優先
順位の大小は、ＣＰＵへの割当ての順位を表わすだけで
あり、必ずしも、プログラムのＣＰＵでの実行の度合い
ｌこ対応していない。このため、場合によつては、優先
順位の低いプログラムにＣＰＵが全く割当てられず、優
先順位がある程度低いと処理が全然進まないという事態
も発生することがある。本発明の目的はこのような欠点
を改良するための優先順位決定方法および装置を提供す
ることにある。

即ち、本発明によれば、各プログラムのＣＰＵでの相対
的な実行の度合いに関する指標（レデイ状態にある時間
とラン状態にある時間の比）として与えられた優先順位
、すなわち、外部優先順位が与えられる。

この外部優先順位により指定されるＣＰＵサービスが各
プログラムに与えられるように、本発明では、内部優先
順位が決定され、これに従つてＣＰＵでのデイスパツチ
が行われる。すなわち、本発明においては、一定時間毎
に、各プログラムへのＣＰＵのサービスの度合いを調べ
、これと与えられた外部優先順位とから、次の期間にお
ける内部優先順位が決定される。なお、本発明では、各
プログラムに対するＣＰＵでのサービスの割当ての度合
いは、各プログラムのＣＰＵでの実行時間（以下ラン時
間という）だけではなく、各プログラムがレデイ状態に
あつた時間（以下単にレデイ時間とよぶ）をも考慮して
計算される。

このような配慮は、次に述べるような計算機におけるプ
ログラムの動作の性質によるものである。

即ち、計算機において、実行されるプログラムｌこは、
ｌ／０命令を多発するものや演算中心でほとんどＩ／０
命令を出さないものがある。Ｉ／０デバイスの動作は、
ＣＰＵの処理速度に比べて低速であり、一度１／０命令
をだすと、プログラムは中断され、このため、Ｉ／Ｏ命
令を多発するプログラムは、優先順位が等しくても、Ｉ
／０命令をあまりださないプログラムに比べてＣＰＵで
のサービスをより多く受けられないこと６こなり、単に
ＣＰＵでサービスをうけたラン時間だけで、プログラム
の実行の度合いを決定することは適当でない。また、優
先順位が等しいとすると、レデイ時間は、ほぼ等しく優
先順位を高めると、レデイ時間は短くなる。従つて、レ
デイ時間が短いということは、サービスをうける度合い
が高いことを示している。本発明はこれらの性質を利用
しており、一定期間毎に、プログラムのラン時間とレデ
イ時間とが測定され、これらの値からプログラムの実行
の度合いが計算される。

このプログラムの実行の度合いが、与えられた外部優先
順位で指定された度合いと比較され、次の期間における
内部優先順位が決定され、これにより前記次の期間に対
して外部優先順位で指定された目標が達成されるように
なる。ずなわち、外部優先順位を等しく与えた場合を考
えると、レデイ時間とラン時間との比が等しくなるよう
にデイスパツチングプライオリテイが与えられることに
なり、Ｉ／Ｏ命令を多発するプログラムは短いＣＰＵ時
間に対応してレデイ時間も短くなるように比較的高いデ
イスパツチングプライオリテイが与えられ、演算中心の
プログラムには、長いＣＰＵ時間に対応してレデイ時間
も長くなるように比較的低いデイスパツチングプライオ
リテイが与えられることになり、かつ、あまりに低いデ
イスパツチングプライオリテイが与えられたために、Ｃ
ＰＵの割当てが全くなされなかつたような場合には、次
周期におけるデイスパツチングプライオリテイが上げら
れるように作用するため、従来のように、演算中心でＩ
／Ｏ命令の発生頻度が低いために低いデイスパツチング
プライオリテイが割当てられ、ＣＰＵが与えられず処理
が全然進まない等の欠点をなくすことができる。

次に図面を参照して本発明を詳細に説明する。第２図お
よび第３図はこの発明の一実施例を示す図である。本実
施例においては、ある与えられた内部優先順位Ｐで動作
しているある期間におけるレデイ時間とラン時間との比
Ｒを計算し、目標として与えられた外部優先順位の値Ｐ
Ｅと前述のＲとの比をとり、この値を内部優先順位Ｐに
乗することにより、内部優先順位を修正し、この修正さ
れた値を次の時間間隔におけるデイスパツチのための内
部優先順位として使用することにより、各プログラムの
ＣＰＵによるサービスの受け方を目標に近づけようとす
るものである。

また、以下の本実施例においては、マルチプログラム状
態で実行されるプログラムの数はＮより少なく、また、
各プログラムには、番号１（ト）くＮ）が割あてられて
いるものとする。

また、本実施例においては、プログラムの実行の度合い
としてレデイ時間とラン時間の比が使われる。さらに、
プログラム番号１によりアドレスされる管理テーブル１
が第２図に示すように用意されている。管理テーブル１
の各ワードは、一定時間間隔Ｔｐの間でレデイ状態（こ
あつた時間の累計を保持する第２のフイールドＴ２、ラ
ン状態にあつた時間の累計を保持する第１のフイールド
ｔ１、プログラムがレデイ状態にあつた時刻を保持する
第３のフイールドＴ１、現時点での内部優先順位を保持
する第４のフイールドＰおよび各プログラムに与えられ
た外部優先順位を保持する第５のフイールドＰＥをもつ
。また、参照英字Ｔはタイマ（時計装置）を示し、これ
は、１０μｓ（マイクロセカンド）毎に１ずつカウント
アツプするカウンタで構成され、現時点における時刻Ｔ
ＯＤを計時するとともに一定時間間隔Ｔｐ（ここでは、
５００ミリセカンド毎）に制御回路４に対して割込みｔ
を起す。参照英字ＴｄはプログラムがＣＰＵにデイスパ
ツチされた時刻を保持するレジスタであり、この出力お
よび管理テーブル１の第１から第３のフイールドＴｌ，
ｔ２およびｔ１の値は、切換ゲートＳＷｌを介して演算
回路２の一方の人力に印加される。また、タイマＴの出
力ＴＯＰｌ管理テーブル１の第２のフイールドＴ２の出
力および演算回路２に接続された第１のラツチ（Ｔｗ）
３の出力は切換ゲートＳＷｌを介して演算回路２の他の
入力に印加されている。演算回路２の出力は第２のラツ
チ５にも印加され、このラツチ５の出力は切換ゲートＳ
Ｗｌを介して演算回路２の人力に印加される。また、制
御回路４は計時装置Ｔからの計時割込みＩｔｌプログラ
ムｉがＣＰＵに割当てられたことを示す信号Ｓａｌプロ
グラムＩＯＣＰＵでの実行が中断されたことを示す信号
Ｓｂおよびプログラムｉがレデイ状態になつたを示す信
号Ｓｃを受け取り、これらの信号を起動信号として管理
テーブルの読出し、書込み、演算回路への指令、レジス
タやラツチへの格納および切換ゲートの設定等の制御指
令を出す。次に、この制御回路４の制御の下に行われる
本発明の動作を説明する。なお、時計装置Ｔにより設定
される時間間隔Ｔｐの開始時点においては、次の期間に
おける各プログラムの内部優先順位の値Ｐ（１）が決定
されており、この値は管理テーブル１の第４のフイール
ドＰに格納されているものとし、デイスパツチはこの内
部優先順位に基づいておこなわれる。

また、管理テーブル１上のラン時間ｔ１（１）およびレ
デイ時間Ｔ２（１）はともに１になつているとする。あ
る時刻において、あるプログラムｉに対してＣＰＵが割
当てられると、制御回路４には、信号Ｓａが印加され、
これにより第２図ａに示す動作が行われる。即ち、計時
装置Ｔの値で示されるこのときのＴＯＤが、レジスタＴ
ｄに格納され、この値とこのプログラムｉがレデイにな
つた時刻Ｔ３（１）との差、即ち、このプログラムｉが
デイスパツチされるまでにレデイ状態であつた時間が演
算回路２により計算され、第１のラツチ３（Ｔｗ）に格
納される。次に、この値と管理テーブル１の第２のフイ
ールドＴ２（１）に格納されているレデイ時間とが演算
回路２により加算され、その結果が第１のラツチ３を介
して管理テーブル１の同一記憶位置Ｔ２（１）にもどさ
れ、プログラムｉのレデイ時間の累積が行われる。また
、プログラムｉを実行中に、このプログラムｉがＩ／０
命令を出したりあるいはこのプログラムｉよりも高い優
先順位をもつプログラムｉがレデイ状態になつたために
、このプログラムｉが続けてＣＰＵで実行不可能になつ
たとき、信号Ｓｂが制御回路４に印加され、第２図ｂに
示すような動作が開始される。

即ち、このときの時刻ＴＯＤとレジスタＴｄの値との差
、即ち、今回のデイスパツチでプログラムｉがラン状態
にあつた時間が演算回路２により計算され、ラツチ３に
格納される。

次に、この値が管理テーブル１の第１のフイールドのｉ
番目の語ｔ１（１）の値に加えられ、同じ管理テーブル
の同一記憶位置に格納され、これにより、プログラムｉ
のラン時間の累積が行われる。プログラムｉが出してい
たＩ／Ｏ命令が完了したためあるいはプログラムｉが実
行中にそれよりも更に高い優先順位をもつプログラムα
が実行可能になつたために、ＣＰＵを取り上げられるこ
とによつてプログラムｉがレデイ状態になつたときには
信号Ｓｃが制御回路４に印加され、第２図ｃに示すよう
に、そのときの時刻、即ち、計時装置Ｔの値が管理テー
ブル１の第３のフイールドＴ３のｉ番目の語Ｔ３（１）
に格納され、これによりプログラムがレデイ状態になつ
た時間の更新を行う。

計時装置Ｔにより計時割込みが発生すると、即ち一定時
間間隔Ｔｐが経過すると、割込み発生信号１ｔが制御回
路４に印加され、これにより第２図ｄに示す動作が開始
される。まず、プログラム番号１としてＯが印加され、
管理テーブル１の第２のフイールドＴ２（１）に格納さ
れているレデイ時間の累積値および第１のフイールドｔ
１（１）に格納されているラン時間の累積値が読み出さ
れ、演算回路２により、その比Ｒ（１）が計算され、こ
の値が第２のラツチ５に格納される。

次に、管理テーブル１の第５のフイールドＰＥ（１）に
格納されている外部優先順位と第４のフイールドＰ（１
）に格納されている内部優先順位とが読み出され、演算
回路２により乗算が実行され、この結果がラツチ３に格
納される。次に、この値が、先に第２のラツチ５に格納
されているレデイ／ラン時間の比で除算され、その結果
が第１のラツチ３を介して管理テーブル１の第４のフイ
ールドＰのプログラムに対応した記憶位置Ｐ（１）に格
納され、次の期間における内部優先順位として使用され
る。また、ｔ１（１），Ｔ２（１）には、初期値として
値１が格納される。なお、この値１は単位時間１０μｓ
を示し、除算に際し、値０が除数に印加されないように
１とされている。これらの動作をプログラム番号Ｎ−１
まで繰り返し、次の期間Ｔｐにおける優先順位の計算お
よびラン時間ならびにレデイ時間の累積値の初期化を行
う。なお、本発明の一実施例の説明では、説明簡単化の
ため、制御回路の具体的な構成については触れていない
が、上記説明で示した動作を行うための制御回路は、通
常の論理回路の組合わせであるいはマイクロプログラム
方式の制御回路により容易に実現できることは明らかで
ある。

また、本実施例の上記信号Ｓａ，Ｓｂは本発明の優先順
位決定装置が用いられる情報処理装置内に設けられたプ
ログラムのデイスパツチを行うためのデイスパツチヤ一
により発生され、また、上記信号Ｓｃは前記情報処理装
置内に設けられた割り込み処理機構により発生されるが
、本発明の要旨に直接関係ないので詳しい説明を省く。

【図面の簡単な説明】

第１図はプログラム処理の状態を示す遷移図、第２図は
本発明の優先順位決定方法および装置の動作を説明する
ためのフロウチヤートおよび第３図は本発明における優
先順位決定装置の一実施例を示す図である。 第３図において、参照数字１は管理テーブル、参照数字
２は演算回路、参照数字３，５はラツチ、参照数字４は
制御回路、参照英字Ｔは刻時装置、参照英字Ｔｄはレジ
スタおよび参照英字ＳＷｌ，ＳＷ２は切換ゲートをそれ
ぞれ示す。

Claims (1)

1. 【特許請求の範囲】 １ 複数個のプログラムを実行するマルチプログラミン
   グ方式の計算機システムにおける各プログラムの優先順
   位を定めかつ中央処理装置への割当ての優先順位を制御
   する優先順位決定方法において、各プログラム毎に各プ
   ログラムがある時間間隔において前記中央処理装置で実
   行されている状態にあつた時間すなわちラン時間および
   各プログラムが前記処理装置で実行可能な状態にあつた
   時間すなわちレディ時間を調べ、これらの時間を次の時
   間間隔における優先順位決定のための要因として使用す
   ることを特徴とする優先順位決定方法。 ２ 複数個のプログラムを実行するマルチプログラミン
   グ方式の計算機システムにおいて、各プログラム毎に各
   プログラムが中央処理装置で実行されていた時間すなわ
   ちラン時間、前記処理装置に対する割当てを待つていた
   実行可能な時間すなわちレディ時間および前記実行可能
   になつた時刻をそれぞれ保持する記憶位置をもつ第１、
   第２および第３の保持手段と、現時点における各プログ
   ラムの優先順位を保持する第４の保持手段と、前記中央
   処理装置にある１つのプログラムが割当てられた時刻を
   保持する第５の保持手段と、一定時間間隔毎に内容がカ
   ウントアップされる計時装置と、前記中央処理装置にお
   いて前記ある１つのプログラムの実行が中断された時点
   でこの時点における時刻と前記第５の法持手段に格納さ
   れている時刻との差によりそのプログラムの前記ラン時
   間を計算し、この値を前記第１の保持手段のそのプログ
   ラムに対応した記憶位置に格納されているこれまでのそ
   のプログラムの前記ラン時間の累積時間値に加えこの加
   算値を前記第１の保持手段の前記記憶位置に格納し、ま
   たあるプログラムが実行可能な状態になつた時点で前記
   計時装置の値を前記第３の保持手段におけるそのプログ
   ラムに対応した記憶位置に格納し、前記中央処理装置に
   前記ある１つのプログラムが割当てられた時点で前記計
   時装置の値と前記第３の保持手段におけるそのプログラ
   ムに対応する記憶位置に格納された値との差によりこの
   プログラムの前記レディ時間を計算し、この値を前記第
   ２の保持手段の前記プログラムに対応した記憶位置に格
   納されている累積値に加えこれを新たな累積値として前
   記第２の保持手段の前記記憶位置に格納し、一定時間間
   隔毎に各プログラムに対応する前記第１および第２の保
   持手段の記憶位置に格納された値をもとに前記一定時間
   間隔における前記レディ時間の累積値と前記ラン時間の
   累積値とを知りこれらを用いて次の一定時間間隔におけ
   る各プログラムの優先順位の値を計算し、その結果を前
   記第４の保持手段に格納する動作を行なう演算手段およ
   び制御手段とから構成されたことを特徴とする優先順位
   決定装置。