JPH04195577A - マルチプロセッサにおけるタスクスケジューリング方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野コ 本発明は、バッファ記憶装置を持つマルチプロセッサに
おけるオペレーティングシステムの制御方式に関する。

［従来の技術］ 高い処理性能が要求される今日の大規模計算機システム
においては、主記憶装置をいくつかの処理装置によって
共有する密結合マルチプロセッサ構成を採用することが
多い。このようなマルチプロセッサシステムでは、シス
テム内に存在する複数のタスクをシステム内の処理装置
によって実行するため処理装置に対して処理を割当てる
方式として、処理単位ごとに処理装置に対して負荷に応
じて割当てる負荷分散方式、また１つあるいは複数の専
用化された処理装置においてシステム内の特定の処理を
集中処理する機能分散方式などが知られているが、上記
の密結合マルチプロセッサ構成では、処理装置をビジー
率１．　Ｏ０％まで容易に使用可能な負荷分散方式が一
般的に用いられる。

負荷分散方式を用いた上記システムでは、ソフトウェア
の処理単位であるタスクを順にシステムの処理待ちキュ
ーにキューイングしておき、空きとなった処理装置がこ
の処理待ちキューをサーチして実行可能なタスクが存在
すればそれを選択し実行する（以下このような選択、実
行をディスパッチという）タスクディスパッチングアル
ゴリズムによって上記の負荷分散を実現している。この
ような制御方式を用いたとき、１つのタスクに着目した
場合、該タスクがシステム内のある処理装置上で実行さ
れているときに、割込みなどの外部要因や、Ｏ８機能の
呼出し等のタスク処理にともなって発生する内部要因な
どによって実行を中断されたとする。Ｏ８にて必要な処
理を行なった後、新たなタスクを実行するときに、従来
は新たに実行されるタスクはその処理装置において前に
実行していたタスクとは無関係に決定される。また１つ
のタスクが実行を開始してから実行が中断されるまでの
時間はタスクの性質とシステムの状態の両方に依存し、
一定の値とはならない。

もう一つの本発明の背景となる従来技術としてバッファ
記憶装置に関する技術がある。今日計算機で処理される
処理の増加に伴い、計算機に要求される主記憶装置の容
量は著しく増大している。

しかしながら、主記憶素子に用いられる半導体メモリ素
子の容量は一般にメモリ素子の速度及び消費電力と相反
する関係にあり、処理装置の高速に対応した高速なメモ
リ素子を多数使用することはコスト面、スペース面、消
費電力のいずれにおいても得策ではない。このため、処
理装置内部に高速かつ小容量のバッファ記憶装置を持ち
、低速かつ大容量の主記憶装置に対する主記憶アクセス
をバイパスすることによって等価的に改善する構成が一
般的である。このようなバッファ記憶装置は主記憶素子
に比べて小容量かつ高速の素子を用いており、全体の容
量も小さなものである。このようなバッファ記憶装置は
プログラムの用いるデータは短期的にはメモリ空間のあ
る特定の部位に集中して発生するというプログラムの性
質に依存しており、このようなバッファ記憶装置では読
み込んだデータを再利用しつつ新たに必要となったデー
タと入れ換えながら使用する。具体的には、バッファ記
憶装置内のデータのうち、゛その時点で用いているデー
タをバッファ記憶装置内に読み込み、使用していないデ
ータを捨てる、ないしは主記憶に対して書き戻して小さ
なバッファ記憶装置によってメモリ空間の全体を扱うよ
うにする。また、特に高速なシステムにおいては、処理
装置と主記憶装置の速度に大きな非難が生じるため、処
理装置内のバッファ記憶装置と主記憶装置の間に速度差
を緩和するための中間のバッファ記憶装置を置く構成も
知られている。このような構成の公知な例としては、特
許公報特公昭６２−９９４２、特公昭６１−５０３４．
２、特開昭６４−５１５４３などがある。

このようなバッファ記憶装置を持つシステムでは、処理
装置の求めるデータがバッファ記憶装置内にあり、参照
あるいは更新がバッファ記憶装置を介して行うことがで
きたとき（以下１ＮＢＳであるという）には高速に動作
可能であるが、バッファ記憶装置内に求めるデータがバ
ッファされていなかった時（以下、ＮｉＢ５であるとい
う）には低速な主記憶装置を起動して所定のデータを参
照あるいは更新する必要がある。このため処理に要する
時間はバッファされていた場合に比べ数倍から数十倍必
要となる。したがって性能を高めるためには主記憶参照
時に１ＮＢｓとなる割合を高めることが重要であり、こ
のための技術方式はキャッシュ技術方式の中心課題とし
て、これまでも様々な検討が行われている。最近の公報
では、特許公報特開平１−１３３　］、　６２は、特定
のデータをバッファ記憶にとり込まないように制御する
技術を開示している。また、特開平１−２０５２５０で
はバッファ記憶に階層構成を取り入れる場合の技術を開
示している。

さらに、本発明の背景となる従来技術に、密結合マルチ
プロセッサにおけるバッファ記憶の一致制御技術がある
。バッファ記憶装置は主記憶の写しであり、複数台の処
理装置から同じ主記憶領域に対して更新を行った際、主
記憶の更新を矛盾なく行なうとともにバッファ記憶装置
の内容を更新しなければならない。これに関する従来技
術として、特許公報特公昭５７−３３６２７にはメモリ
のアクセスを上記観点のもとに制御する装置の構成法が
開示されている。また、特許公報特公昭５１−３６１７
９、特公昭５］−４９５３５、特公昭５３−２５４５７
及び特公昭５７−３３６２３では、他バッファ記憶装置
に操作を行おうとする主記憶データがバッファされてい
たとき、そのデータをバッファ記憶装置間で転送する各
種の技術が開示されている。また特許公報特開昭６２−
１２５２５０には、ソフトウェアによって明示的にバッ
ファ記憶の一致制御を行なう構成法が開示されている。

［発明が解決しようとする課題］ 従来例で説明した負荷分散制御を行なう密結合マルチプ
ロセッサシステムにおいては、１つのタスクに着目する
と、そのタスクが外的要因、あるいはタスク処理に伴な
う要因（Ｏ３機能の呼出しなど）によって実行を中断し
た時点では、そのタスクがそれまで実行していた処理装
置、あるいは系のバッファ記憶装置にはそのタスクの使
用する主記憶領域がバッファされている。一方そのタス
クが再び実行可能となった場合には、従来技術において
は前に実行していた処理装置とは特に関係なく処理装置
が選ばれ実行される。このため、そのタスクの実行を実
行する処理装置が以前そのタスクを実行した処理装置（
以下前実行装置と呼ぶ）と異なる場合、前実行装置内に
バッファされているそのタスクの残存データは無駄にな
るばかりでなく、そのタスクが他処理装置で実行された
場合に、そのタスクの使用領域に対する書き込みなどに
ともなって主記憶とバッファ記憶装置の内容を一致させ
る処理、具体的には従来技術の項で上げた処理を実行す
る必要があるため、前実行装置の実行性能が低下すると
いう２つの問題がある。

本発明は、上記問題点を解決するため、バッファ記憶の
効率を最適にするようタスクを実行する処理装置を選択
する技術手段を与えることを目的とする。

［課題を解決するための手段］ 本発明では、上記問題を解決するため、あるタスクをあ
る処理装置に対して割り付ける際、そのタスクをその処
理装置に割り付ける場合の各処理装置でのバッファ記憶
装置の利用効率を評価し、その結果に基づいてタスクを
割り付けるべき処理装置を決定する技術手段を提供する
。これを実現するため、タスク割り付けの際に以下２つ
の技術手段を用いる。

■あるタスクの使用する領域がある処理装置のバッファ
記憶装置内にどれだけ存在するかを直接的、あるいは間
接的方法で推定し、その値があるしきい値以上ならばそ
の処理装置に対してそのタスクを割り当てる。

■すべての処理装置に対して■で調べたバッファ記憶装
置内のそのタスクの使用する領域が上記しきい値以下な
らば、そのタスクを任意の空きである処理装置に割当て
る。

第１の項目はバッファ記憶装置を有効に活用するため、
第２の項目は、負荷分散を速やかに行なうための処理で
ある。この方法を用いるにあたっては、各処理装置中の
バッファ記憶装置内に、あるタスクに属するデータがど
れだけ残っているかを評価値として知る直接的、あるい
は間接的方法が必要となる。このとき、上記戦略を有効
に機能させるために必要な評価値とは、バッファ記憶装
置内のデータの量ではなく、複数のバッファ記憶装置間
での比較を行なうことのできる指標である。

評価値の算出は評価情報に基づいて行う。本発明では評
価値の算出のために以下２つのいずれかの技術手段を用
いる。

■専用ハードウェアインターフェースを設け、直接デー
タ量をハードウェアから調べ、この情報を評価情報とし
て評価値を算出する。。

■そのタスクが当該処理装置において最後に実行された
時刻（中断時刻）を記録し、これを評価情報とし、バッ
ファ記憶装置内のデータの量を中断時刻からの経過時間
とそのタスクの性質をもちいて算呂した評価式を用いて
推定する。評価式の１つの例として、中断時刻からの経
過時刻を用いることができる。

また、上記技術手法は以下のように拡張できる。

システム内のタスクに対して、そのうちのいくつかのタ
スクに共通なリソースが存在する場合、そのようなリソ
ースをもちいてタスクの使用するリソースによる類似度
を定義することができる。また、定型化された処理を主
に行なうシステムにおいては、その間の上記のタスク間
類似度はあらかじめ設計者によって設定可能である。こ
のとき、各処理装置において前に実施していたタスクの
時系列と、中断点からのバッファ効率の低下についての
推定式から、割り付けようとするタスクに対して、各処
理装置内のバッファ記憶装置内に有るデータとそのタス
クの使用するデータとの類似度を評価し、それを上記技
術手段における評価値として用いることができる。

［作用コ 以上の方法を用いて、タスクの割り付けを実施すること
によって、以下２つの利点がある。

（１）当該タスクがその処理装置において前に実行され
ていた時にその処理装置内のバッファ記憶装置に読みこ
まれたデータを有効に再利用することができる。また、
当該タスクと共通のデータを使用する別タスクによって
該処理装置のバッファ記憶上に読みこまれたデータを有
効に使用するこができる。このため、バッファ記憶装置
のデータの再利用効率が改善され、バッファ記憶装置に
求めるデータが存在する確率が向上する。

（２）選択された処理装置以外の処理装置のバッファ記
憶装置内には当該タスクの使用するデータの量は、その
タスクを実行しようとする処理装置のバッファ記憶装置
内に比べて少ないため、他処理装置に対してのバッファ
記憶−数制御にともなう干渉は少なく抑えられる。

このため、従来技術の問題のうちタスク割り付けによっ
て発生しており上記課題として記載した問題点は取り除
かれ、該問題点により発生していたバッファ記憶の利用
効率低下に伴なうオーバヘッドが取り除かれる。

［実施例コ （１）第一の実施例 以下図面に即し、本発明の第一の実施例を説明する。第
１図は、任意のレディであるタスクを処理装置に割り付
ける処理のフローチャートを示し、第２図は第１図の処
理を実施する計算機システムの例である。第３図は第１
図のアルゴリズムの効果を説明する際に使用する説明図
である。第４図は、この実施例でのタスク制御ブロック
（ＴＣＢ）キューの構造を示す。タスク制御ブロック（
ＴＣＢ）キューは主記憶装置、ディスク記憶装置、拡張
記憶装置などに貯蔵されている。第５図は新規に登録さ
れたタスクを第３図で示されるキューに接続し、第１図
で示される処理にて扱うために必要とする前処理のフロ
ーチャートである。第６図は、実行終了したタスクを第
４図で示されるキューから外す後処理である。第７図は
アフイニテイグループを説明する際の説明図である。第
８図は第５図の処理において使用するアフイニテイグル
ープを登録するアフイニティグループ制御テーブルの構
造を示す図である。

初めにこの実施例の前提となる第２図の計算機システム
について説明する。このシステムは、２台の処理装置１
〜２を持ち、各処理装置内には各々専用のバッファ記憶
装置（以下ＢＳと呼ぶ）４〜５を持つ。この処理装置１
〜２は１台の主記憶装置３に接続される。処理装置内の
バッファ記憶装置は、以下に説明するように制御される
。

処理装置１が命令を主記憶から読み出す、あるいは命令
を実行するために必要な主記憶空間上のデータを読み呂
す、あるいは主記憶空間内に所定のデータを書き込むと
き（以下この３つの処理を合わせて主記憶アクセスと呼
ぶ）には、まず対象とする主記憶空間のデータの写しが
自処理装置内のＢＳＡ内にあるかどうかを検索する。こ
のとき、ＢＳＪ内に操作対象となる主記憶領域の写しく
以下簡単にターゲットデータと呼ぶ）が存在していた時
には、ＢＳ４に対して主記憶アクセスを行なう。

ターゲットデータがＢＳ４内に存在しなかった場合（以
下ＮｉＢ５と呼ぶ）、またはＢＳ４にストアスル一方式
の制御を採用している場合の主記憶に対する書き込みに
対しては、処理装置１に接続された主記憶装置３に対し
て主記憶アクセスの要求内容を送出する。ＮｉＢ５であ
った場合は、主記憶装置３に対して、ターゲットデータ
を含むある一定サイズの主記憶の写しく以下ブロックと
呼ぶ）を主記憶装置３からＢＳへ転送するために要求を
主記憶装置３に対して送出する。主記憶装置３は読みだ
しの要求に対しては、その要求に対して主記憶の所定領
域を読み出し、必要なデータを処理装置１内のＢＳ４に
転送する。また書き込みの要求に対しては、対象となる
主記憶領域を更新する。処理装置１では、転送されたデ
ータを所定の命令フェッチないしは演算に使用するとと
もにＢＳ４にそのデータを登録し、再利用可能とする。

本実施例のような構成と制御を行うシステムにおいては
、そのタスクの使用する主記憶上のデータは、そのタス
クが該データを使用するたびに、必要に応じて主記憶装
置から所定データが読み込まれバッファ記憶装置に登録
される。このためあるタスクの使用するデータのうち、
バッファ記憶装置に登録されている量は徐々に増加する
。一方、これに対してそれまでにバッファ記憶装置に登
録されていた領域は、新たなデータの登録によって徐々
に追い出され、減少していく。したがって第２図のよう
なバッファ記憶装置を有するシステムにおいて、バッフ
ァの利用効率の向上によって計算機システムの性能向上
を行うためには、バッファ記憶内に残存しているデータ
を再利用してバッファ記憶装置と主記憶装置間のデータ
転送回数を削減し、これによってデータ転送オーバヘッ
ドを減らすことが有効な手段となる。

以上説明を行った第２図に示すシステムにおいて、本発
明を適用したタスク割り付は処理方式の実施例を第１図
を用いて説明する。この実施例では、現在時刻を知るた
めの計時機能をもちい、本発明の処理のための専用のハ
ードウェアを使用しない。このため、本実施例は計時機
構を持つ既存の一般的な計算機システムに適用可能であ
る。

タスクの状態は、以下では簡単のため実行中、実行可能
（レディ）及び実行不可能の３状態でのいずれかとする
。タスクに対して優先順位別グルーピングによる属性を
導入したときには、各優先順位グループ別に同様のアル
ゴリズムによるタスク選択を行えばよい。

まず、第２図の計算機システム内の処理装置が、システ
ム内に存在する実行可能状態のタスクを選択する処理に
ついて説明する。この処理の流れは第１図にフローチャ
ートによって示したものである。この処理は、空きとな
った処理装置によって新たに処理すべきタスクを選択す
るために実行されるものであり、以下に示す考え方によ
ってタスクが選択される。

第３図に示す処理装置内のＢＳ４〜５に着目した場合、
タスクＡＩＯの実行後その処理装置において別のタスク
Ｂｌｌが実行された場合には、タスクＢｌｌがその実行
に伴いタスクＢの用いるデータをバッファ記憶内に読み
込んでいくために、タスクＢの実行開始時点でバッファ
記憶装置に残存していたタスクＡ、　１０のデータは上
記説明のようにほぼ単調に追い出され減少していくと考
えられる。一方ある時点で第３図に示すようにタスクＡ
ＩＯの使用するデータ５０１および５１１が処理装置２
のＢＳ５よりも処理装置１のＢＳ４に多くバッファされ
ており、タスクＢｌｌの使用するデータ５０２および５
１２が処理装置１のＢＳ４よりも処理装置２のＢＳ５に
多くバッファされていたとするとき、タスクＢｌｌは次
に実行する際に処理装置２において実行した方がバッフ
ァ記憶装置の利用効率上有利である。この減少する割合
は２つのタスクＡとＢの性質に依存するが、この実施例
ではその平均的振舞を推定または評価し、そのタスクが
実行を終了した時刻を評価情報とし、そのタスクが実行
を終了してからの経過時間によってそのタスクに関する
バッファ記憶装置内の残存するデータの量を推定し、充
分なバッファ再利用効果が得られると判断される時間に
基づき対象とするタスク終了時点からの経過時間のしき
い値を作成し、そのしきい値以内にタスクを再実行する
ときには可能な限り残存するバッファ記憶内のデータを
再利用するよう処理装置を選択する戦略を用いて、第１
図に示したタスク割り付は処理を行なう。

以下第１図の処理を説明する。この処理ではタスクの制
御情報（ＴＣＢ）をキューイングした第４図に示す構造
を持つＴＣＢキューを用意する。

空きとなった処理装置は自処理装置上で実行するタスク
を選択する際、このＴＣＢキューから以下の処理にした
がって実行可能状態のタスクを１つ選択する。各タスク
のＴＣＢ　１０〜１１は、そのタスクを実行する際の制
御情報の他に前にそのタスクが実行されていた処理装置
の番号１．１０３、および実行を打ち切られた時刻ＴＢ
１０４をデータとして保持している。そのデータは、前
にそのタスクが実行を打ち切られた際の事後処理時（た
とえば割込み、マクロの処理など）に書き込まれる。こ
の処理については後述する。

以下実行するタスクを選択する第１図の処理を、ステッ
プごとに説明する。

■始めに、ＴＣＢキューの先頭にポインタを設定する。

また作業変数ＣｎｔをＯに初期化する。

この変数は、以下のステップで該キューの何個の要素を
試したかを記録し、ある−足回数でタスク割り付は選択
最適化の試行を打ち切りディスパッチ処理のステップの
過度の増加を抑えるために用いる。（Ｓ　ｔ　ｅ　ｐ　
１００１）■ポインタのさしているタスク制御ブロック
を調べ、そのタスクが実行可能状態でないならば、その
タスクを選択し実行することはできない。

この場合は次のタスクを調べる処理に分岐する。

（ＳｔｅｐｌＯ０２） ■次に、ポインタのさしているタスク制御ブロック１０
より、前に中断した時刻を示すフィールド（Ｔｓ、　　
ｌ　Ｏ４）　、及び前に実行していた処理装置の番号を
示すフィールド（Ｉ、、１．０３）を読み込む。（Ｓｔ
ｅｐｌＯ０３） ■前ステップで読み込んだｌ１１１０３と、自処理装置
番号とを比較する。同一なら、このタスクを選択し、実
行する処理に分岐する。

（ＳｔｅｐｌＯ０４，１００８） ■前のステップである５ｔｅｐｌＯ０４での比較結果が
異なっていた場合には、Ｔ、１０４と現在時刻との差を
調べる。これがあらかじめ設定したＢＳのライフタイム
によるしきい値（Ｌｉｍｌ　）以下であった時には、こ
のタスク１０を選ばず次のタスクを選ぶ処理に行く。こ
の処理で選択されないタスクは、上記しきい値に比べ短
期間以前に他処理装置によって実行されており、この他
処理装置内のバッファ記憶装置内にそのタスクが使用し
ていた主記憶領域の写しが多く残存している。このため
、このタスクを選択し実行した場合、この他処理装置内
の残存する主記憶の写しが利用できないばかりでなく、
その領域に対する書き込みによってその写しを持つ処理
装置に対してバッファ記憶の一致制御を実行する必要が
生じ、処理性能低下の要因となる。

このようなタスクについては、このタスクが前に走行し
ていた処理装置が空き、そのタスクを再選択して走行す
ることを期待し、ＴＣＢキューに残す。（ＳｔｅｐｌＯ
０５） ■以下は調べていたタスクを選択せず、次のタスクを試
す処理である。まず、何個のタスクを調べてきたかを変
数Ｃｎｔによって調べ、それが設定した試行回数の上限
以上なら、タスクサーチをうちきりＴＣＢキューの先頭
にもっとも近い実行可能なタスクを選択する。先頭のタ
スクを選ぶものはＦｉＦｏによる公正さを確保し、同時
にタスクの沈み込みを防止するためである。

同時にこのタスクはもつとも古いものであるため、この
タスクを選択する場合他処理装置に対するバッファ一致
制御にともなう外乱が最小であると推定される。

（Ｓｔｅｐｌ、００６．　１００９） ■同様に、試すべきタスクが尽きたときにはキュー先頭
にもっとも近い実行可能なタスクを選択する。先頭を選
ぶ理由は、前のケースと同じである。　（ＳｔｅｐｌＯ
０７） ■ポインタを次のタスクに設定し、Ｃｎｔに１を加え、
５ｔｅｐｌＯ０２からの手順を繰り返す。

（ＳｔｅｐｌＯｌｏ） 以上第１図の処理をステップごとに説明した。

タスクキュー内に実行可能タスクがない時の処理は、処
理を明確化するためフローチャートより除いた。必要な
処理は、５ｔｅｐｌＯ１０の後に追加される処理であり
、全タスクのチエツクを行ったことを検出して処理装置
を実行可能タスクを待つ状態とする処理である。また本
実施例ではタスク間にプライオリティによる実行優先順
位の差がない場合の処理を示したが、プライオリティを
持つ場合の拡張はＴＣＢキューをプライオリティごとに
分けるなどの方法によって容易に実現できる。

タスクの中断処理は、中断されたタスクの中断時刻をタ
スクの前終了時刻フィールドＴ、１０４に、またその時
の処理装置番号をタスクの前処理装置フィールドｌＢ１
０３にそれぞれ書き込む処理を行ない、タスクの中断理
由にしたがって実行可能状態もしくは実行不可能状態の
いずれかとしてＴＣＢキューに登録する。

このアルゴリズムにおいてＣ１１ｍ、即ちサーチの打切
り値は、処理装置数とタスク中断の頻度に依存するが、
処理装置数からその数倍程度に設定すれば本発明の効果
は生かされる。これはバッファ記憶装置に同時に存在可
能なタスク数はシステムに依存するが一般に数個であり
、この数に処理装置数を掛けた数よりシステム内の実行
可能なタスク数が多い場合に全タスクに対して公正なサ
ービスを行った場合、バッファ記憶内にそのタスクの使
用するデータが残っている間にタスクを実行することが
できないためである。すなわち第１図に示す処理におい
てタスクを設定数だけ試行しても条件を満たすタスクが
ない場合とは、即ちＴＣＢキュー内の実行可能タスクが
多い状態であり、多くの処理待ちタスクがシステム内に
存在する。本実施例に示す処理はバッファ効果を向上さ
せることによってシステムのスループットを向上させる
ことを狙ったものであるが、そのために同じタスクを繰
り返し実行する場合が多く、多くの処理待ちタスクがあ
る過負荷の環境下ではタスクの沈み込みが発生する可能
性がある。そのような状態の下では処理の公正化の観点
からもとのタスクを選択しないほうが良い。以上の理由
より、本発明が有効であるような状態では、実行可能状
態のタスクを処理装置数程度骨試す間に自処理装置で前
に実行されていたタスクが見つかる可能性が高い。また
このような観点から、第１図のフローチャートでは前実
行タスクを再選択することが適当でない場合には最初の
タスクを選択するようにしている。また、上記の理由か
ら、この打切り数を少なく設定した場合、タスクの実行
待ち時間が減少しレスポンスは向上するが、バッファ効
率が向上する効果は減少しスループットは低下する。

この処理に用いるＢＳのライフタイム（Ｌｉｍｌ）は、
そのシステムで走行するタスクの性質、ＢＳの容量、シ
ステムの構成などに依存し、システムごとに異なるもの
である。この時間を短く設定した場合には、使用できた
はずのバッファ内のデータを使用しないためバッファ効
率が低下し、逆に長く取ったときには、同一タスクを実
行する確率があるためタスクの遷移回数が少なくなり、
結果としてタスクの実行待ち時間が増加する。この値の
設定法としては、ｏＳのシステムチューニングの１つの
設定パラメータとして、値を変えながらバッファ効率と
タスクの実行待ち時間を測定し、システムにあった最適
値を求めるやりかたが実用的である。また、システムの
性能が悪化しない設定値の範囲が広いため、システムの
目的に見合った標準値を○Ｓ提供元にて設定することも
可能である。

次に、新規に登録されたタスクを第２図の計算機システ
ム内の処理装置に対して割り付ける処理を、第５図のフ
ローチャートにしたがって説明する。この処理では、共
通のデータを使用するタスクによるグルービングを行な
い、それに応じて可能な限りバッファ効果の高い処理装
置を用いて実行するよう、処理装置を決定する。

この処理では、そのタスクの制御ブロック中の前終了時
刻フィールドＴＢ１０４及び、前処理装置フィールド１
，１．０３の値が設定され、ＴＣＢキューにつながれる
。以下記載する処理では、あるタスク間の共通のデータ
使用についての情報はあらかじめ与えられるものとする
。このようなタスク間の共通データに関する情報は、例
えばコンパイラやリンカによってそのタスクの使用デー
タを解析することで得る事ができる。また、ある種のシ
ステムはシステムで走行するタスクの性質の概要をあら
かじめ知ることができる。このようなシステムの例とし
ては、データベースからの情報検索を行なうシステムや
定型処理を主とするオンラインシステムなどがある。こ
のようなシステムにおいては、１つのサブシステムを１
つの空間を用いて走行させ、サブシステムを多数走らせ
ることによって負荷の処理を行なう。このため、サブシ
ステムが自仮想空間内で作業領域として使用する部分が
、他仮想空間内の領域と重なることはないとみなせ、空
間内にあるタスク間で共有する自空間内のデータの量も
その空間内の共有作業領域として指定した量で評価する
ことができる。このため、このような共有データの存在
と、その大きさは、サブシステムの設計時に知ることが
できる。

したがってそのソフトウェア設計者があらかじめ把握し
ている情報を本アルゴリズム実行前に与えればよいため
、上記の情報の把握を動的に実施する必要はない。また
、このようなシステムはもっと高いシステム性能が要求
されるものであり、かつタスク数も多いため本発明が特
に有効である。

以下、使用する用語の定義を第７図に即して説明する。

４つのタスクＡ２０．Ｂ２１．Ｃ２２゜Ｄ２３があり、
タスクＡ、　２０とタスクＢ２１は同じであるデータ２
２０をともに利用し、タスクＣ２２とタスクＤ２３は別
のあるデータ２２１をともに利用することなどがあらか
じめ判っているものとする。このときタスク間に、共通
に使用するデータの量によって距離を導入することがで
きる。

すなわち共通して使用するデータの量の多いタスクは距
離が近いものと考える。この時、この距離を利用してタ
スク間でクラスタリングを行なう事ができる。この結果
を用い、タスクを適当なりラスタ単位でグループ化する
。ここで、上記のタスクＡ、　２０と８２１が１つのグ
ループ２１０に属しているとし、同様にＣ２２とＤ２３
が１つのグループ２１１に属しているとする。ここで定
義したグループをアフイニテイグループと呼ぶ。

同一アフィニテイグループのタスクが連続して同一処理
装置上で走行したばあい、バッファ記憶上の同一データ
を該タスク群が連続して使用するため、バッファ記憶の
利用効率を向上することができる。

第５図は、ある処理装置上で実行を要求されたタスクが
ＴＣＢキューにつながれるまでの前処理のフローである
。以下、この処理をステップごとに説明する。以下、タ
スク制御ブロック中のＴ８１Ｏ４および■１１１ｏ３の
操作にあたって、あらかじめ用意した制御テーブルを用
いる。このようなテーブルの構成の一例を第８図に示す
。

この例では、１つのグループの制御テーブル４００は、
タスクによって構成されるアフイニテイグループを記載
したものであり、テーブルのエントリとしてグループの
識別子４０１、そのグループの現在ＴＣＢキュー内にあ
るタスクの数４０３とそのタスクの制御ブロックへのポ
インタ４０４〜４０７を用意する。

■ある処理装置上で新規のタスクを登録するとき、始め
にそのシステムのアフイニテイグループテーブルを調べ
、新規タスクが属するアフイニティグループをチエツク
する。

（Ｓｔｅｐ１５０１．１５０２．１５０４）■新規登録
タスクがシステムに登録されているアフィニティグルー
プの１つに属するものであったとき、そのタスクをその
グループに属する他タスクと同じ処理装置に割り付ける
ことがバッファ性能面でもっとも適当である。これには
、まずそのアフィニティグループに属するタスクのうち
、現在ＴＣＢキューに在るものの有無をチエツクする。

この実施例ではこのチエツク処理の高速化を目的とし、
アフィニティグループテーブルエントリ内に、そのグル
ープのタスクのうちＴＣＢキュー内にあるものの数をフ
ィールド４０３に持つため、その数が１以上であること
を見ればよい。

（Ｓｔｅｐ１５０５） ■同一アフイニテイグループに属しＴＣＢキューに存在
するタスクがあるならば、そのタスクが前に走行してい
た処理装置に対して新規登録タスクを割り付けることに
よってバッファ記憶装置の効率を改善することができる
。すなわち、新規登録タスクに対して、１．１０３を、
上記手順によって見いだした既存のタスクのＴＣＢを調
べこのＴＣＢ内の１．１０３の値と同じ値に設定し、新
規登録タスクをＴＣＢキューの最後に実行可能状態とし
て追加する。この時、新規に登録したタスクに対してそ
のＴ、１０４は、その時点の現在時刻か、１．１０３を
得たタスクのＴ１１１０４をそのまま用いればよい。ま
た、この登録によってそのタスクの属するアフィニティ
グループのエントリの処理中のタスク４０３の数は１つ
増加する。

（Ｓｔｅｐ１５０６，１５０７） ■一方、該アフイニテイグループに属するタスクのうち
、ＴＣＢキュー内にあるものがない、すなわち該グルー
プのタスクにその時点でシステムで処理されているもの
がないとき、そのタスクはどの処理装置上で実行しても
良い。このため、処理装置の負荷状態を参照して適当な
処理装置に割り当てる。このときのｌＢ１０３は任意の
値でよく、ＴＢ１０４は経過時間がどのバッファ記憶装
置のライフタイムよりも十分大きな値となるよう設定す
ることによって上記目的が達成される。また、この登録
によってそのタスクの属するアフイニテイグループのエ
ントリの処理中のタスク４０３の数は同様に１つ増加す
る。

（Ｓｔｅｐ１５０９〜１５１０） ■またどのアフィニテイグループにも属さないタスクに
ついては、アフィニティグループテーブルに対しては何
もせず、ＩＩｌとＴＢの設定は■と同様に行う。

（Ｓｔｅｐ１５０３） 第６図は、タスクが実行を終了する場合の処理を示す。

終了処理として、本発明の適用によって新たに必要とな
るものは、アフィニティグループの制御テーブルの管理
であり、自グループの実行中のタスクの数４０３，４１
３，４２３から１引いておく処理をおこなう事を目的と
する。以下第８図の制御テーブル４００からタスク３０
を削除する場合を例にとりステップごとに説明する。

■該タスク３０の属するアフィニティグループの制御テ
ーブルを読み込む。このタスク３０の場合は制御テーブ
ルは、第８図の制御テーブル４００である。（Ｓｔｅｐ
ｌ、６０１，１６０２゜１６０５．１６０６） ■制御テーブル４００内の自グループの処理中のタスク
数４０３から１を引く。

（Ｓｔｅｐ１６０３） ■制御テーブルから、終了したタスクへのポインタを削
除する。必要なら、テーブル領域を詰める。　　（Ｓｔ
ｅｐ１６０４．） 以上でタスク終了の本発明の実施に伴なう追加処理は終
了する。また、アフィニティグループに属さないタスク
の終了時は、本処理を行なう必要はない。なお、この処
理は他処理装置からの更新との整合性を取るため、割込
み禁止とし必要に応じ排他制御を行いつつ実行しなけれ
ばならない。

以上説明した実施例は、始めにも述べたように、タスク
に対する付加的な情報を別途ソフトウェアやハードウェ
アから読み込み、制御に使用することは行なっていない
。しかしながら、例えばタスクの所要メモリサイズ、共
通領域のアクセス頻度、各処理装置の利用率、バッファ
記憶装置のヒツト率などを加味すれば、より最適化した
制御も可能になる。その例として、所要するメモリサイ
ズの小さいタスクを特定の処理装置に集中させ外乱を軽
減する制御などが可能である。

また、本実施例ではアフィニティグループを新規タスク
の登録時のみに用いる例を示したが、レディタスク選択
時に用いる事も可能である。この場合には、第５図のよ
うな処理を第１図の処理に組み込み、第１図の処理を変
更する必要がある。

また実施例の説明の際、バッファ記憶制御方式に間して
説明を行ったが、これはバッファ記憶装置の内容がどの
ように置き替わるかを示すためであり、制御方式の差異
は第１図の処理におけるバッファ記憶のデータのライフ
タイムの違いとして現れる。また本発明の効果は、上記
の第２図のようなバッファ記憶装置構成に限定されるも
のではない。

（２）第２の実施例 以下、図面を用いて第２の実施例を説明する。

対象とする処理装置構成は、第１の実施例と同様に第２
図に示すものである。第９図は本実施例で使用するｉＰ
アフィニティピットをＯにクリアする処理を示す。第１
Ｏ図は本実施例でのＴＣＢキ二一ニー造を示す。第１１
図は本実施例におけるタスクの選択処理を示したもので
ある。

まず、この実施例における処理の考え方を説明する。各
ジョブに対して、そのタスクを前に実行していた処理装
置に対して優先して割り付けることを指示するフラグを
設ける。さらにこのフラグを用いて、処理装置に対して
実行可能状態のタスクを割り付ける処理の際にこのフラ
グを調べ、′１″であった時にはその処理装置に対して
そのタスクを割当てるように制御する。

このフラグはタスクが、実行を中断した際に“１′とし
、その後そのタスクが実行されないまま長い時間が経過
し、そのタスクの処理装置内のバッファ記憶に取り込ん
だデータの再利用効果が期待できなくなった時点で、該
フラグを′Ｏ″に落とす処理を行う。そのタスクが最後
に実行されたときから現在までどれだけの時間が経過し
たかは任意の処理装置から把握可能であり、アイドル状
態の処理装置によって各タスクの状態を調べ、所定の経
過時間が過ぎているものに対してフラグを“０”とする
処理を実行させ、上記制御を実現する。

以下、第９図に上記フラグをｕ　ＯＩＩにリセットする
処理を示す。この処理を含むプログラムモジュールは、
処理装置に対して割り付けるべきタスクがないとき、あ
るいタイマ等によって一定時間おきなどに実行されるも
のである。ここで考えるタスク制御ブロックのプールの
構造は第１の実施例同様、キュー構造とじＴＣＢキュー
と呼ぶ。またキュー中のタスクの状態を示す制御ブロッ
クの構造を第１０図に示す。各タスクの制御ブロック３
０は、第１の実施例と同様の構造に、上記のフラグを追
加したものである。以下、前に実行されていた処理装置
に対して割り付けることを指示するビットをＩＰアフィ
ニティピットＩＰＡＦ３０５と呼ぶ。ＩＰアフィニティ
ビットＩＰＡＦ３０５はＢＳ中にそのタスクの用いるデ
ータが十分残っていると推定したときに“１″となるよ
うに制御されるものである。この処理手順では、以下の
手順にしたがい、ＴＣＢキューを調べ、ＩＰアフィニテ
ィビットＩＰＡＦ３０５をＩＩ　ＯＩＩにクリアする。

■ＴＣＢキューの先頭にポインタを設定する。

（Ｓｔｅｐ２００１） ■キューに登録されたタスクがあれば、５ｔｅｐ２００
３以下の処理を行う。タスクがなければ、処理終了であ
る。（Ｓ　ｔ　ｅ　ｐ　２００２）■ポインタＰの指す
タスク制御ブロック３０のＩＰアフイニテイピットＩＰ
ＡＦ３０５を調べる。それがＩｔ　Ｏ”の時は処理不要
であり、次のタスクを選択する処理５ｔｅｐ２００７に
行く。１”であったならば、５ｔｅｐ２００４以下の処
理を実施する。（Ｓｔｅｐ２００３） ■次にポインタＰの指すタスクが、前に実行を打ち切ら
れている時間Ｔａ３０４を読みだし、それを現在時刻Ｔ
、と比較する。このときその値があらかじめシステムに
応じて設定しであるＢＳのブロックのライフタイムより
大きければ、ＢＳ中に前のデータは残っていないと判断
しＩＰアフィニティビットＩＰＡＦを１１０″にする。

小さかった場合には、そのタスクに対して何もしない。

（Ｓｔｅｐ２００４，２００５．２００６）■ポインタ
の指すタスク制御ブロックに対する処理は終了した。ゆ
えに次のタスクを調べるよう、ポインタを更新する。　
（Ｓｔｅｐ２００７）以上ＩＰアフイニテイピットＩＰ
ＡＦ３０５を“Ｏ″とする処理について説明した。次に
ＩＰアフィニテイピットを使用したタスクの割り付は処
理を第１Ｉ図に即し、ステップごとに説明する。

■始めに、ＴＣＢキューの先頭にポインタを設定する。

また作業変数ＣｎｔをＯに初期化する。

Ｃｎｔの目的は第一の実施例の第１図の処理と同じであ
る。（Ｓｔｅｐ２１０１） ■ポインタのさしているタスク制御ブロック３゜を調べ
、そのタスクが実行可能状態でないならば、そのタスク
を選択し実行することはできない。この場合は次のタス
クを調べる処理に分岐する。　　（Ｓｔｅｐ２１０２） ■次に、ポインタのさしているタスク制御ブロック３０
より、■Ｐアフィニティ■、ＡＦ３ｏ５と前に実行して
いた処理装置の番号を示すフィールドＩ、３０３を読み
込む。

（Ｓｔｅｐ２１０３） ■前ステップで読み込んだ１．３０３と、自処理装置番
号とを比較する。同一なら、このタスクを選択し、実行
する処理に分岐する。

（Ｓｔｅｐ２１０４，２１０８） ■前のステップである５ｔｅｐ２１０４での比較結果が
異なっていた場合には、そのタスクのＩＰアフイニティ
ビットＩＰＡＦ３０５を調べ、それが“ｌ”であったと
きには、このタスク３０を選ばず次のタスクを選ぶ処理
に行く。このタスクを選択しない理由は、第１の実施例
と同様である。

（Ｓｔｅｐ２１０５） ■以下はポインタのさしているタスクを選択せず、タス
クを試す処理である。まず、作業変数Ｃｎｔを調べてこ
れまでにいくつのタスクを調べてきたかを見て、それが
設定した試行回数上限を越えていた場合にはタスクサー
チを打切りＴＣＢキューのもっとも先頭に近い実行可能
なタスクを選択する。先頭側を選ぶ理由は第一の実施例
と同様である。

（Ｓｔｅｐ２１０６，２１０９） ■同様に、試すべきタスクが尽きたときにはキュー先頭
にもっとも近い実行可能なタスクを選択する。先頭を選
ぶ理由は、■と同じである。

（Ｓｔｅｐ２１０７） ■ポインタを次のタスクに設定し、Ｃｎｔに１を加え、
５ｔｅｐ２１０２からの手順を繰り返す。

（Ｓｔｅｐ２１１０） 新規にタスクを登録する際、削除する際の処理について
は第１の実施例と同様である。登録のとき、新規タスク
に対してはｉＰアフィニティピットはＯとして登録する
。

（３）第３の実施例 この実施例が適用されるシステム構成と、処理の考え型
は第一の実施例と同様である。ここでは、タスクの中断
時に中断された処理を再実行するがどうかを判定し、可
能なら中断時点から実行することによってバッファ効率
を改善しようとするもので、Ｏ８のタスク割り付は処理
には変更を加えない。第１２図は本実施例で使用する前
タスク表の概念を説明するための説明図である。第１３
図は本実施例での割込みによって中断された場合のタス
クの中断処理の流れを示す。第１４図は前タスク表を更
新する処理を示す。第１５図は前タスク表を用いてタス
クを再実行するかどうかを判定する処理を示す。第１６
図はタスクが内部要因によって中断した場合の前タスク
表の更新について示す。

この実施例では、各処理装置で割込みなどによって走行
中で継続実行可能なタスクの実行が中断されたとき、割
込み処理を終了した後刻込み処理に要した時間が十分に
小さかった場合、割り込まれたタスクを再実行し、バッ
ファ効率を高めることを狙ったものである。

この実施例では、各処理装置に一つづつ、主記憶上に前
実行タスクを記憶するための作業領域４０（以下、前タ
スク表とよぶ）を用意する。この筋タス−り表４０は、
第１２図に示す表形式であり、以下３つのデータを記憶
する。

■前に実行していたタスクの識別子４０１■そのタスク
の中断時刻４０２ ■前に実行していたタスクが継続実行可能がどうかを示
すフラグ４０３（以下継続実行フラグと呼ぶ） この実施例では、タスクＡの実行を割込みなどによって
中断するとき、第１３図に示す処理を行なう。

■タスク識別子が割込みによって中断されたとき＊Ｊ御
はＯ８の割込みハンドラに移る。割込みハンドラでは、
まず前タスク表４０を更新する処理を行なう。（Ｓｔｅ
ｐ３００１） ■その後、割込み処理を行なう制御プログラムを起動し
、割込み処理を行なう。

（Ｓｔｅｐ３００２，３００３） ■割込み処理の終了後（ＯＳによっては、割込み処理を
行なうモデュールの起動後）、タスクの再選択処理を行
なう。このとき、前タスク表を参照し、前に実行してい
たタスクの中断時点からの経過時間があるしきい値以下
ならば前に実行していたタスクを再実行し、タスク残バ
ッファデータを利用する。

（Ｓｔｅｐ３００４〜３００５）ａ ■またしきい値以上であったときには、通常のタスク選
択処理を行ない、別のタスク、例えばＢを選択する。（
Ｓｔｅｐ３００７） 以下、前タスク表更新処理５ｔｅｐ３００１、再実行の
判定処理５ｔｅｐ３００４についてさらに詳細に説明す
る。第１４図に、前タスク表を更新する処理３００１の
処理詳細をフローチャートにて示す。以下、ステップご
とに説明する。

■その処理装置の前タスク表のアドレスを得る。

（Ｓｔｅｐ３１０１） ■実行中断時点のタスク識別子、中断時刻を前タスク表
に代入する。

（Ｓｔｅｐ３１０２，３１０３） ■当該タスクを継続実行することが可能かどうかを判定
し、可能なとき継続実行フラグを′１″′に、不可能な
とき“Ｑ　１１にセットする。

（Ｓｔｅｐ３１０４．．３１０５．３１０６）第１４図
に示す処理は必要に応じて、割込み禁止かつ排他制御を
おこなった状態で処理されなければならない。

第１５図に、前タスク表から前実行タスクを再実行する
かどうかを判定する処理をフローチャートにて示す。以
下処理をステップごとに説明する。

■その処理装置の前タスク表を読み込む。

（Ｓｔｅｐ３２０１） ■前タスク表に登録されているタスクが継続実行可能で
あるかどうかを、継続実行フラグが１″であるかどうか
を判定することによってテストする。（Ｓ　ｔ　ｅ　ｐ
　３２０２） ■現在時刻と前タスク表の中の中断時刻との差があらか
じめ与えられたしきい値（Ｌ　ｊ　ｍ　１　）以内かど
うかを判定する （Ｓｔｅｐ３２０３〜３２０４）　　。

■前のテストの結果しきい値以下であるときには前実行
タスクを再実行する。

（Ｓｔｅｐ３２０５） ■テストの結果しきい値以上であった時には、通常のデ
ィスパッチャにいく。

（Ｓｔｅｐ３２０６） この処理に用いるしきい値は第一の実施例と同様の手段
を用いて設定する。また第１５図に示す処理は必要に応
じて、割込み禁止かつ排他制御をおこなった状態で処理
されなければならない。

第１６図では、タスクＡが他のタスクの同期待ち、Ｉ１
０発行などの理由で実行可能でない状態に変わり処理を
終了したときのフローを示す。このときは前タスク表を
読み込み（Ｓ　ｔ　ｅ　ｐ３３０１）、表中の継続実行
可能であることを示すフラグ４０３をリセットしく５ｔ
ｅｐ３３０２）　、通常のタスクディスパッチ処理を行
なう。なお、第１６図において、ＳｖＣはスーパーバイ
ザコール命令のことである。

以上で第３の実施例の説明を終了する。本実施例は始め
に説明したようにＯ８のタスク割り付は処理には変更を
加えない。このため、第１３図のタスク中断処理に第１
実施例記載のタスク中断処理を追加組み合わせることに
よって、第１の実施例の処理と併用することが可能であ
る。

（４）第４の実施例 次に第１の実施例の変型として第１７図に示す計算機シ
ステムに対して第１の実施例と同様の処理を構成した場
合について、図を用いて説明する。

第１７図は、第４の実施例でのシステム構成について示
す。第１８図は第４の実施例のタスク選択処理を示した
ものである。

この実施例のシステムは、４台の処理装置５０〜５３を
持ち、各処理装置内に各々専用のバッファ記憶装置６０
〜６３（以下ＢＳと呼ぶ）を持つ。

この処理装置５０〜５３は２台ずつ組となって、処理装
置２台当り１つのシステム制御装置７０および７１にそ
れぞれ接続されている。このシステム制御装置７ｏおよ
び７１内にも、１台のシステム制御装置７０〜７１は、
１台の処理装置によって共有される共有バッファ記憶装
置７２〜７３（以下ＷＳと呼ぶ）を持つ。１台の主記憶
装置３に接続される。以上示した２つの階層を持つバッ
ファ記憶装置の制御は、以下に説明するように行われる
。

処理装置５０〜５３内のＢ５６０〜６３の動作は第１の
実施例のＢＳ４〜５の動作と同様の為、ここでは繰り返
さない。唯一の相違点はＢＳ内に求めるデータがなかっ
たとき、第１の実施例では処理装置５０の要求する命令
やデータを主記憶装置３から読み出したのに対して、本
実施例ではシステム制御装置７０内のＷＳ７２から読み
出しを試みる点である。システム制御装置７０は、処理
装置５０内のＢ５６０からの要求に対して以下に記載す
る処理を行って、要求されたブロックをＢＳに対して送
出する。処理装置５０側ではシステム制御装置７０から
その応答として転送されてきたブロックをＢ５６０に登
録し、同時にそのデータを用いて命令処理を継続する。

この関係は他処理装置５１〜５３、他システム制御装置
７１においても言うまでもなく同じである。

システム制御装置７０は処理装置５０からのブロックの
転送要求を受は付けた際、上に記載したように自装置内
のＷＳ７２を検索する。ＷＳ７２中に求めるブロックが
存在していた時には、該ブロックを要求元の処理装置５
０に送出する。一方ＷＳ７２を検索した結果求めるデー
タがＷＳ中に存在していなかった時の処理はＷＳ制御方
式によって異なるが、本実施例でのストアイン制御を用
い複数コピーを許す制御を採用する。このような制御を
採用したバッファ記憶の構成例に関しては。

例えば特許公報特開昭５７−１０９１８０に記載があり
、その場合の処理を簡略化して示すと以下のようになる
。

■自装置７０内のＷＳ７２内の１つのブロックを選び、
それを主記憶３に書き戻して主記憶内を最新の値に更新
し、そのブロックのＷＳ７２での登録を取り消す。この
処理によってＷＳ７２内に空きブロックを作る。

■他システム制御装置内のＷＳ７３（以下、他ＷＳと呼
ぶ）を検索する。他ＷＳ７３中に求めるデータを含むブ
ロックが存在する場合には、他ＷＳ７３から自ＷＳ７２
に該ブロックを転送し他ＷＳでの該ブロックの登録を取
り消す。このとき、自ＷＳ７２での転送先は前の処理で
空きとした領域である。他ＷＳに所定のブロックが存在
しなかった時には、求めるデータを主記憶装置３から読
み畠す。

■上記処理によって、自ＷＳ７２に読みこまれたブロッ
クを、要求元の処理装置５０に転送し、処理を終了する
。

本実施例のような構成と制御を行うシステムにおいては
、Ｂ５６０〜６３は処理装置における命令実行に追従し
つる速度をもち、Ｗ３７２〜７３はそれに比べてやや低
速な、ＢＳと主記憶の中間的な速度を持つ。このため、
上記構成を取るシステムでは、ＢＳの総容量をＷＳの総
容量の数分の１から数十分の１とする構成が、良好なコ
ストと性能を実現するために適当であることが多い。こ
のような容量差をつけバッファ記憶装置を実現した場合
、新しいデータ領域の転送に伴うＢＳとＷＳ中の各ブロ
ックが、他のより新しいブロックに置き変わるまでの時
間、いわばブロックの寿命は平均的にはＷＳの側が容量
比に従って数倍長い。またある時点で存在するブロック
の集合に着目すれば、その時点から時間が立つにつれて
着目した集合の要素は新しいブロックに少しずつおきか
わり、ブロック数はほぼ単調に減少していく。したがっ
て第１７図のようなバッファ記憶装置を有するシステム
においてバッファの利用効率の向上によって計算機シス
テムの性能向上を行うためには、バッファ記憶内に残存
しているデータを再利用してバッファ記憶装置階層間あ
るいはバッファ記憶装置と主記憶装置間のデータ転送回
数を削減することによってデータ転送オーバヘッドを減
らすことが有効な手段となる。

以上説明を行ったシステムにおいて、以下では第１の実
施例の第１図に相当するタスク割り付は処理について第
１８図に即し説明する。

タスクの状態は、第１の実施例と同様に実行中と実行可
能（レディ）と実行不可能の３状態で表されるものとす
る。また、この実施例で使用するＴＣＢキューの構造は
第１の実施例と同じ第４図に示すものである。

以下処理ではＷ３７２〜７３の容量はＢ５６０〜６３の
容量に比べ１桁程度大きいため、あるタスクが実行を中
断した時点でｗ　ｓ　＋＝登録されていた該タスクの使
用するデータの量は大きく、かつ一定時間経過後に残存
するデータの量も一般に大きい。このため、ＢＳとＷＳ
に対して各々対象とするタスク終了時点からの経過時間
のしきい値を別々に設け、そのしきい値以内にタスクを
再実行するときには可能な限り残存するバッファ記憶内
のデータを再利用するよう処理装置を選択する６以下第
１８図の処理を説明する。空きとなった処理装置は自処
理装置上で実行するタスクを選択する際、このタスクキ
ューから以下の処理にしたがって実行可能状態のタスク
を１つ選択する。

以下実行するタスクを選択する第１８図の処理を、ステ
ップごとに説明する。

■始めに、ＴＣＢキューの先頭にポインタを設定する。

また作業変数ＣｎｔをＯに初期化する。

この変数の用法は、第１の実施例に同じ。

（Ｓ　ｔ　ｅ　ｐ　　　４．　ＯＯ１，）■ポインタの
指しているタスク制御ブロックを調べ、そのタスクが実
行可能状態でないならば、そのタスクを選択し実行する
ことはできない。

この場合は次のタスクを調べる処理に分岐する。

（Ｓｔｅｐ　　４００２） ■次に、ポインタＰｎｔｒのさしているタスク制御ブロ
ックより、前に中断した時刻を示すフィールド（ＴＢ、
１０４）　、及び前に実行していた処理装置の番号を示
すフィールド（Ｉ　ａ、　１０３）を読み込む。　（Ｓ
ｔｅｐ４００３） ■前ステップで読み込んだＩ、１０３と、自処理装置番
号とを比較する。同一なら、このタスクを選択し、実行
する処理に分岐する。

（Ｓｔｅｐ４００４，４０１２） ■前のステップである５ｔｅｐ４００４での比較結果が
異なっていた場合には、ＴＢ１０４と現在時刻Ｔ、どの
差を調べる。これがあらかじめ設定したＢＳのライフタ
イムによるしき値（Ｌｉｍｌ）以下であった時には、こ
のタスクを選ばず次のタスクを選ぶ処理に行く。このタ
スクを選択しない理由は、第１の実施例の５ｔｅｐｌＯ
０５での理由とまったく同じである。

（Ｓｔｅｐ４００５） ■５ｔｅｐ４００５での比較結果がＢＳでのライフタイ
ムによるしきい値より大きがった場合には、ｌＢ１０３
で示される処理装置と、自処理装置が同じシステム制御
装置に接続されているかどうかを調べる。接続されてい
る場合には、そのタスクを選択する。（Ｓｔｅｐ４００
６）■５ｔｅｐ４００６で調べた結果、接続されていな
い場合には、ＴＢ１０４と現在時刻Ｔ０との差とあらか
じめ設定したＷＳのライフタイムによるしきい値（Ｌｉ
ｍ２、前に説明したようにＬｉｍ１（Ｌｉｍ２である）
とを比較する。Ｔ、とＴ。

どの差がＷＳのライフタイムによるしきい値より大きい
とき、ＷＳでのデータのバッファ効果も期待できないた
め、このタスクはどの処理装置で実行しても性能上大き
な差はない。この処理ではタスクの沈み込みを防ぐため
、この時点でポインタの指すタスクを選択する。Ｔ、と
Ｔやとの差がＷＳのライフタイムによるしきい値より小
さいときは、このタスクを選ばず次のタスクを選ぶ処理
に行く。　（Ｓｔｅｐ４００７）■以下はポインタのさ
しているタスクを選択せず、次のタスクを試す処理であ
る。まず、何個のタスクを調べてきたかを変数Ｃｎｔに
よって調べ、それがあらかじめ設定しである試行回数の
上限Ｃ１ｉｍ以上なら、タスクサーチをうちきりレディ
キューの先頭のタスクを選択する。先頭のタスクを選ぶ
理由は第１の実施例に同じ。

（Ｓｔｅｐ４００８，４００９） ■同様に、試すべきタスクが尽きたときにはＴＣＢキュ
ー先頭のタスクを選択する。先頭を選ぶ理由は、５ｔｅ
ｐ４００９と同じである。

（Ｓｔｅｐ４０１０） ［相］ポインタを次のタスクに設定し、Ｃｎｔに１を加
え、５ｔｅｐ４００２がらの手順を繰り返す。

（Ｓｔｅｐ４０１１） 以上第１６図の処理をステップごとに説明した。

上記処理はタスク間にプライオリティによる実行優先順
位の差がない場合の処理を示したが、プライオリティを
持つ場合の拡張はＴＣＢキューをプライオリティごとに
分けるなどの方法によって第１の実施例同様容易に実現
できる。

タスクの新規登録処理、中断処理などは第１の実施例と
まったく変わらない。

またこの処理に用いるＢＳ、ＷＳのライフタイム（Ｌｉ
ｍｌ、Ｌｉｍ２）の設定に関しては、第１の実施例で説
明したものと同様の考慮を払えばよい。

以上で４つの実施例について説明を行った。この実施例
では、第２図及び第１７図を例とする密結合マルチプロ
セッサにおいて本発明を実施した際の処理について説明
したが、疎結合のマルチプロセッサ（共通領域としてデ
ィスクを備える）に関してもデータの書き込みをともな
う共通領域へのバッファリングで類似の問題が発生する
。これに対しては、第１の実施例において主記憶装置３
を共通領域に置き換えて適用することにより本発明が実
施可能である。実施にあたって考慮すべき点はバッファ
内のデータのライフタイムの設定のみである。

また、本発明においては様々の部位において変型、ある
いはハードウェアのサポートなどが可能である。例えば
、本実施例で記載したタスクのディスパッチャの一部を
マイクロコードによって記載する事も可能である。

またハードウェアの情報、例えば当該タスクに属するバ
ッファ記憶装置内のデータの量を把握する事ができるよ
うにバッファ記憶装置を構成し、そのデータを用いてデ
ィスパッチするタスクを選択することも可能である。簡
単な場合として、例えば空間を切り替えた際にバッファ
記憶をパージするインプリメントを持つシステムにおい
ては、注目するタスクと違う空間で動作するタスクが走
行した後には該処理装置では注目するタスクの使用する
データは残らないと見なして、注目するタスクのために
処理装置を選択することができる。

勿論さらに複雑な変型も適当なハードウェアサポートに
より可能である。

また、本発明はバッファ記憶装置の効率を高めることに
よってシステムのスループットを高めるための技術であ
るが、特定のタスクが多く走行する傾向があるためのタ
スクのレスポンス面は悪化する可能性がある。タスクの
レスポンスが重視されるシステムにおいて、レスポンス
改善のため、タスク間にプライオリティを導入してサー
ビスを受けていないタスクのプライオリティを上げるこ
とによって対処することも可能であるが、別解として従
来のディスパッチ方式を数回に一回起動するなどの手段
による従来の方式との折衷も可能である。

また、タスク間に本実施例のアフィニティグループ以外
の類似性など、バッファ記憶効率のみならず他の何らか
のシステムに関係したパラメータを導入して、第１の実
施例に沿ってタスクディスパッチングを行うことも可能
である。

本発明は熱論これらの変型を排除するものではない。

口発明の効果コ 本発明の実施により、バッファ記憶装置を持つ計算機シ
ステムにおいて、タスクが切り替わった際及びタスクを
システムに新規登録する際のバッファ記憶装置の効率を
向上させることが可能である。このため、システムの性
能を向上させることができる。

【図面の簡単な説明】

第１図は、任意のレディであるタスクを処理装置に割り
付ける処理のフローチャートを示し、第２図は第１図の
処理を実施する計算機システムの例である。第３図は第
１図のアルゴリズムの効果を説明する際に使用する説明
図である。第４図は、この実施例でのタスク制御ブロッ
ク（ＴＣＢ）キューの構造を示す。第５図は新規に登録
されたタスクを第３図で示されるキューに接続し、第１
図で示される処理にて扱うために必要とする前処理のフ
ローチャートである。第６図は、実行終了したタスクを
第４図で示されるキューから外す後処理である。第７図
はアフィニティグループを説明する際の説明図である。 第８図は第５図の処理において使用するアフイニティグ
ループを登録するアフィニティグループ制御テーブルの
構造を示す図である。 第９図は第２の実施例で使用するＩＰアフイニティピッ
トをＯにクリアする処理を示す。第１０図は第２の実施
例でのＴＣＢキューの構造を示す。 第１１図は第２の実施例におけるタスクの選択処理を示
したものである。 第１２図は第３の実施例で使用する前タスク表の概念を
説明するための説明図である。第１３図は本実施例での
割込みによって中断された場合のタスクの中断処理の流
れを示す。第１４図は前タスク表を更新する処理を示す
。第１５図は前タスク表を用いてタスクを再実行するか
どうかを判定する処理を示す。第１６図はタスクが内部
要因によって中断した場合の前タスク表の更新について
示す。 第１７図は、第４の実施例でのシステム構成について示
す。第１８図は第４の実施例のタスク選択処理を示した
ものである。

Claims (8)

【特許請求の範囲】
1. （１）複数台の処理装置と主記憶装置を有し、該処理装
   置はそれぞれ緩衝記憶装置を有し、該緩衝記憶装置は前
   記主記憶装置の一部分の写しを保持し、その時点で該緩
   衝記憶装置内に保持していない主記憶領域を読み込む際
   該緩衝記憶装置内の他の部分の写しを該緩衝記憶装置か
   ら削除する計算機システムにおいて、タスク制御ブロッ
   クキュー内の各タスク制御ブロックにはタスクが実行さ
   れる処理装置の処理装置番号のための領域と該タスクが
   実行される処理装置の緩衝記憶装置に残存する該タスク
   に係る写しのデータ量を評価するための評価情報のため
   の領域が設けられ、処理装置はタスク実行中断時には該
   処理装置の処理装置番号及び中断時における前記評価情
   報を実行中断したタスクのタスク制御ブロックに登録し
   、そして、処理装置は、該計算機システムで処理される
   複数のタスクから該処理装置にて実行するタスクを選択
   する場合、前記タスク制御ブロックキュー内のタスク制
   御ブロックを順次読み込み、前記処理装置番号と前記評
   価情報による評価に基づき実行処理するタスクを選択し
   、かつ、該評価の結果、他処理装置の緩衝記憶装置に残
   存する該タスクに係る写しのデータ量が予め定められた
   所定量より大であるタスクのときは該タスクを選択せず
   、該タスクを他処理装置が選択できるようにしたことを
   特徴とするマルチプロセッサにおけるタスクスケジュー
   リング方式。
2. （２）複数台の処理装置と主記憶装置を有し、該処理装
   置はそれぞれ緩衝記憶装置を有し、該緩衝記憶装置は前
   記主記憶装置の一部分の写しを保持し、その時点で該緩
   衝記憶装置内に保持していない主記憶領域を読み込む際
   該緩衝記憶装置内の他の部分の写しを該緩衝記憶装置か
   ら削除する計算機システムにおいて、タスク制御ブロッ
   クキュー内の各タスク制御ブロックにはタスクが実行さ
   れる処理装置の処理装置番号のための領域と該タスクが
   実行される処理装置の緩衝記憶装置に残存する該タスク
   に係る写しのデータ量を評価するための評価情報のため
   の領域が設けられ、処理装置はタスク実行中断時には該
   処理装置の処理装置番号及び中断時における前記評価情
   報を実行中断したタスクのタスク制御ブロックに登録し
   、そして、処理装置は、該計算機システムで処理される
   複数のタスクから該処理装置にて実行するタスクの選択
   をする場合、前記タスク制御ブロックキュー内のタスク
   制御ブロックを順次読み込み、読み込んだタスクのタス
   ク制御ブロック内の処理装置番号と自処理装置番号とが
   一致するときにはこのタスクを選択し、一致しないとき
   には、タスク制御ブロック内の評価情報による評価を行
   い、該評価の結果、他処理装置の緩衝記憶装置に残存す
   る該タスクに係る写しのデータ量が予め定められた所定
   量より小であるタスクのときはこのタスクを選択し、所
   定量より大であるタスクのときは、このタスクを他処理
   装置が選択できるようにすべくこのタスクを選択せず、
   次のタスクの選択処理に移るようにしたことを特徴とす
   るマルチプロセッサにおけるタスクスケジューリング方
   式。
3. （３）特許請求の範囲第１項または特許請求の範囲第２
   項における複数台の処理装置が、該処理装置の１部ある
   いはすべてによって共有される緩衝記憶装置を有するマ
   ルチプロセッサにおけるタスクスケジューリング方式。
4. （４）特許請求の範囲第１項または特許請求の範囲第２
   項において、前記評価情報を時刻とし、前記中断時にお
   ける前記評価情報をタスクが中断したときの時刻とし、
   前記評価を、評価情報としての時刻と現在時刻との差と
   予め定められた所定値との差に基づき行うようにしたマ
   ルチプロセッサにおけるタスクスケジューリング方式。
5. （５）特許請求の範囲第１項または特許請求の範囲第２
   項において、共通して使用するデータの量の多いタスク
   をまとめて一連のタスクからなるグループとし、該一連
   のタスクからなるグループとグループに属さないタスク
   とをもとにして前記タスク制御ブロックキューを構成し
   たマルチプロセッサにおけるタスクスケジューリング方
   式。
6. （６）複数台の処理装置と主記憶装置を有し、該処理装
   置はそれぞれ緩衝記憶装置を有し、該緩衝記憶装置は前
   記主記憶装置の一部分の写しを保持し、その時点で該緩
   衝記憶装置内に保持していない主記憶領域を読み込む際
   該緩衝記憶装置内の他の部分の写しを該緩衝記憶装置か
   ら削除する計算機システムにおいて、タスク制御ブロッ
   クキュー内の各タスク制御ブロックにはタスクが実行さ
   れる処理装置の処理装置番号のための領域と、該タスク
   が実行される処理装置の緩衝記憶装置に残存する該タス
   クに係る写しのデータ量を評価するための評価情報のた
   めの領域と、該評価の結果のためのフラグ領域とが設け
   られ、処理装置はタスク実行中断時には該処理装置の処
   理装置番号及び中断時における前記評価情報を実行中断
   したタスクのタスク制御ブロックに登録し、アイドル状
   態にある処理装置は、前記タスク制御ブロックキュー内
   のタスク制御ブロックを順次読み込み、読み込んだタス
   クのタスク制御ブロック内の前記評価情報に基づきこの
   時点での緩衝記憶装置に残存する該タスクに係る写しの
   データ量が予め定められた所定量より“大”であるか“
   小”であるかを評価し、この評価結果を前記フラグ領域
   に書き込み、処理装置は、該計算機システムで処理され
   る複数のタスクから該処理装置にて実行するタスクの選
   択をする場合、前記タスク制御ブロックキュー内のタス
   ク制御ブロックを順次読み込み、読み込んだタスクのタ
   スク制御ブロック内の処理装置番号と自処理装置番号と
   が一致するときにはこのタスクを選択し、一致しないと
   きには、タスク制御ブロック内のフラグ領域を参照し、
   評価結果が“小”であるときはこのタスクを選択し、評
   価結果が“大”であるときは、このタスクを他処理装置
   が選択できるようにすべくこのタスクを選択せず、次の
   タスクの選択処理に移るようにしたことを特徴とするマ
   ルチプロセッサにおけるタスクスケジユーリング方式。
7. （７）特許請求の範囲第１項または特許請求の範囲第２
   項において、主記憶装置上に各処理装置毎に作業領域を
   設け、割込みによるタスク実行処理中断時に処理装置は
   この時点における評価情報及び中断したタスクの継続実
   行が可能か否かを示すフラグ情報を前記作業領域に格納
   し、割込み処理終了後、該処理装置は、前記作業領域の
   フラグ情報が継続実行可能を示しかつ評価情報に基づく
   評価結果が緩衝記憶装置に残存する該タスクに係る写し
   のデータ量が予め定められた所定量より“大”であるこ
   とを示す場合には中断したタスクを継続実行し、該場合
   以外の場合には、該計算機システムで処理される複数の
   タスクから該処理装置にて実行するタスクを選択する処
   理へ移るようにしたマルチプロセッサにおけるタスクス
   ケジユーリング方式。
8. （８）主記憶装置と、該主記憶装置に接続されそれぞれ
   が共用緩衝記憶装置を備える複数のシステム制御装置と
   、該システム制御装置に接続されそれぞれ緩衝記憶装置
   を備える複数の処理装置とからなり、前記共用緩衝記憶
   装置は前記主記憶装置の一部分の写しを保持し、前記緩
   衝記憶装置は前記共用緩衝記憶装置の一部分の写しを保
   持する計算機システムにおいて、タスク制御ブロックキ
   ュー内の各タスク制御ブロックにはタスクが実行される
   処理装置の処理装置番号のための領域と該タスクが実行
   される処理装置の緩衝記憶装置に残存する該タスクに係
   る写しのデータ量を評価するための評価情報のための領
   域が設けられ、処理装置はタスク実行中断時には該処理
   装置の処理装置番号及び中断時における前記評価情報を
   実行中断したタスクのタスク制御ブロックに登録し、そ
   して、処理装置は、該計算機システムで処理される複数
   のタスクから該処理装置にて実行するタスクの選択をす
   る場合、前記タスク制御ブロックキュー内のタスク制御
   ブロックを順次読み込み、読み込んだタスクのタスク制
   御ブロック内の処理装置番号と自処理装置番号とが一致
   するときにはこのタスクを選択し、一致しないときには
   、タスク制御ブロック内の評価情報による評価を行い、
   該評価の結果値が予め定められた第一のしきい値より小
   さくて他処理装置の緩衝記憶装置に残存する該タスクに
   係る写しのデータ量が予め定められた所定量より大であ
   るタスクのときはこのタスクを選択せずに次のタスク選
   択処理に移り、前記評価の結果値が第一のしきい値より
   大きいときには、該タスクに係る処理装置が同じ共用緩
   衝記憶装置を使用している場合にはこのタスクを選択し
   、使用していない場合には前記評価の結果値が予め定め
   られた第二のしきい値より大きいときはこのタスクを選
   択し、小さいときにはこのタスクを選択せずに次のタス
   ク選択処理に移るようにしたことを特徴とするマルチプ
   ロセッサにおけるタスクスケジューリング方式。