JPH02242434A - タスクのスケジューリング方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、マルチプロセッサにおけるタスクのスケジュ
ーリング方法に係わり、特に構成の異なるプロセッサを
含むマルチプロセッサにおけるタスクのスケジューリン
グ方法に関する。

〔従来の技術〕

従来マルチプロセッサでは、これを構成する複数のプロ
セッサが、全く同じ構成を、従って同じ命令セラ１へを
持つことを条件としたものが多かった。

また構成が異なり、従って命令セットの異なるプロセッ
サを接続したマルチプロセッサやマルチコンピュータの
場合には、処理すべきタスクが入る待行列がプロセッサ
ごとに設けられており、タスクの実行に先立ってユーザ
またはＯ８がそのタスクをどのプロセッサの上で実行す
るか決定し、その決定したプロセッサの待行列にタスク
を入れておく必要があった。

また、特開昭６２−２０８１５７には、スケジューリン
グ方法ではないが、一部命令セットが異なる複数の計算
機からなる計算機システムのプログラム実行方法が記載
されている。その方法は、コンパイラがどの計算機の上
ででも実行可能なオブジェクトコードを出力するもので
ある。即ちコンパイラはプログラムを解析して、プロセ
ッサ間で共通の命令で実行できる部分と実行できない部
分に分ける。共通に実行できる部分については単一のオ
ブジェクトコードを出力するが、実行できない部分はプ
ロセッサの種類に対応した複数のオブジェクトコードを
出力する。そして、コンパイラは、実行できない部分の
直前に実行しているプロセッサの種類に応じたオブジェ
クトコードに分岐するためのプログラムを挿入する。

〔発明が解決しようとする課題〕

上記した従来のマルチプロセッサにおけるタスクのスケ
ジューリング方法あるいはマルチプロセッサ用のプログ
ラムコンパイル方式には以下のような問題がある。

即ち、同一構成のプロセッサのみでマルチプロセッサを
構成する場合には、ベクトルプロセッサを備えたプロセ
ッサやＡ　Ｉ処理用プロセッサなどの一つの機能を強化
したプロセッサをシステム中に加えるときに、一つだけ
のプロセッサを入替え一 ることかできず、全部のプロセッサをそれらのプロセッ
サにしなければならない。

プロセッサ毎に待行列を持つ方法では、同じ構成のプロ
セッサが複数あるときにプロセッサ間で負荷が偏る可能
性がある。

コンパイラが複数のオブジェクトコードを出力する方法
では、オブジェクトコードが大きくなる欠点とともに、
コンパイラを新しく作り直す必要があるという欠点があ
る。

本発明の目的は、複数のオブジェクトコードを出力する
コンパイラを作成することなしに、命令セットの一部ま
たは全部が異なるプロセッサよりなるマルチプロセッサ
上で、タスクにプロセッサを効率よく割付けるタスクの
スケジューリング方法を提供することにある。

本発明の別の目的は、ベクトルプロセッサを持ったプロ
セッサと持たないプロセッサのように、ある処理が速い
プロセッサと遅いプロセッサとを含むマルチプロセッサ
において、そのような処理があるタスクはその処理の速
いプロセッサに優先的に割当てることのできるタスクの
スケジューリング方法を提供することにある。

また、本発明の別の目的は、ある処理が速いプロセッサ
にその処理を含むタスクを優先的に割当てるとともに、
ある処理が不可能なプロセッサにはその処理を含むタス
クを割当てないようにするタスクのスケジューリング方
法を提供するにある。

〔課題を解決するための手段〕

上記の目的は、各タスクにそのタスクを実行できるプロ
セッサの種類を示すフラグを設けることにより達成され
、各タスクに、そのタスクを処理できる速度に応じた優
先度をプロセッサの種類ごとに示す優先度テーブルを設
けることにより達成され、また上記優先度に不能値を設
けこの値が指定された種類のプロセッサには当該タスク
の処理が不可能とすることにより達成される。

〔作　用〕

各タスクに設けるフラグは、システムに含まれるプロセ
ッサの種類の数だけのフラグ（１ビツト）から成る。各
フラグは、各プロセッサの種類に対応しており、そのタ
スクがその種類のプロセッサで実行可能かどうかを表す
。実行可能な状態にあるタスクは、どのプロセッサから
もアクセス可能な待行列に繋がれている。アイドルとな
ったプロセッサやりスケジューリングを行うプロセッサ
は、各自、その待行列の先頭からタスクのフラグを順番
に見ていき、自分のプロセッサで実行可能なタスクがあ
ったら、取り出してきて実行する。これにより、同一種
類のプロセッサ間では負荷の片よりか防がれる。

また、各タスクに設ける優先度情報テーブルは、システ
ムに含まれるプロセッサの種類の数の大きさの整数配列
とする。各配列要素は、各プロセッサの種類に対応して
おり、そのタスクがその種類のプロセッサに対して持つ
優先度を示し、そのタスクを高速に実行できるプロセッ
サについては、高い優先度を入れておく。優先度を最低
にしたときはその種類のプロセッサでは、そのタスクが
実行不可能であることを表すとする。以上のようなテー
ブルを備えた各タスクは、実行可能な状態にあるとき、
どのプロセッサからもアクセス可能な待行列に繋がれて
いる。アイドルとなったプロセッサやスケジューリング
を行うプロセッサは、各自、待行列のタスクを見ていき
、自分のプロセッサで実行可能で、優先度が最も高いタ
スクを取り出してきて実行する。

この方法により、命令セットが違うプロセッサやある処
理が特別に速いプロセッサを含むマルチプロセッサで効
率良く、タスクにプロセッサを割振ることができる。

〔実施例〕

以下、本発明の実施例について図面を参照して説明する
。第１図は本発明の一実施例を示すもので、プロセッサ
１０１１〜１０１３は、全て共有バス１０３を通してメ
インメモリ１０４にアクセス可能である。

このうちプロセッサ１．０３．１．１０Ｆ、２は同一の
命令セットを持つタイプ０のプロセッサ、プロセッサ】
０１３は別の命令セットを持つタイプ１のプロセッサと
する。このプロセッサのタイプはプロセッサ種類識別子
１０２１〜１０２３で示されている。

メインメモリ１０４には未処理タスク１０６１〜１ｏ６
３の待行列が記憶されている。この待行列は各タスク同
志を各タスクがもつポインタ１５６１．１５６２で繋ぐ
ことにより形成されている。待行列の先頭はヘッダ１０
５である。タスク１０６４〜１０６６は、現在プロセッ
サ１０１１〜１０１３で実行されている。待行列中のタ
スク１０６１〜１０６３には実行可否フラグ１０７１〜
１０７３が設けられており、各ビット位置のフラグがプ
ロセッサ種類に対応している。そしてフラグが″］ノ′
のときは対応する種類のプロセッサでそのタスクを実行
でき、００″のときは実行できない。例えば実行可否フ
ラグ１０７１は、タスク】０６１をタイプ２とタイプ１
のプロセッサでは実行できるが、タイプ０のプロセッサ
では実行できないことを示している。

第２図は、プロセッサ種類識別子１０２１〜１０２３の
内容を示しており、３ビツトより成っていて１ビツトの
みが１”になっている。このプロセッサ種類識別子１０
２１〜１０２３は、実行可否フラグ１０７１〜Ｊ０７３
との論理的な積和をとることにより、その種類のプロセ
ッサでそのタスクを実行できるか否かを調べられるよう
に構成されている。

第３図はスケジューラプログラム（以下では単にスケジ
ューラとも呼ぶ）のフローチャートを示す。このスケジ
ューラは、各プロセッサｌ０１１〜１０１３に設けられ
ており、当該プロセッサが実行していたタスクが終了し
たときと、スケジュールのためのタイマ割込みが入った
ときに起動される。

タイマ割込みは、各プロセッサに一定時間間隔で入る。

今プロセッサ１０１１にタイマ割込みが入って、スケジ
ューラが起動されたとすると、まずステップ２０１で自
プロセッサの種類を示す識別子１０２１を読み込む。読
み込んだ値は“１００　”である。次にステップ２０２
で待行列のヘッダ１０５の指すタスク１０６１を見る。

ステップ２０３では待行列にタスクがないか調べ、未処
理のタスクがなかったときはアイドル処理のステップ２
０４へ移る。第１図ではタスク１０６１が有るからステ
ップ２０５でタスクの実行可否フラグとプロセッサ種類
識別子の論理的な積和Ｓを求める。これは両者の各ビッ
トごとのアンドをとり、それらの結果をオアしたもので
、どこかのビット同志のアンドが１１１　ＩＩになれば
それは当該タスクを当該プロセッサで実行できることを
示す。今の場合、実行可否フラグ１０７１は”　１１０
　”であり、プロセッサ種類識別子１０２１は”００１
”だったので、各ビットごとのアンドは全て“０”従っ
てＳ−Ｏで、プロセッサ１０１１ではタスク１０６１は
実行できないことがわかる。そこでステップ２０７へ進
み、待行列の次のタスクを見る。続くステップ２０３で
タスクがないか調べ、タスク１０６２が見つかるとステ
ップ２０５で実行可否フラグ１０７２とプロセッサ種類
識別子１０２１の論理的積和Ｓを求める。今度は”　Ｏ
Ｏ１”と”　ＯＯ１”なので各ビットのアンドは“ＯＩ
Ｉ　　ＩＩ　Ｏ”１″となり、そのオアはＩＩ　１１１
つまり実行可能なことがわかる。それでステップ２０８
でタスク１０６２を待行列から取り除く。このときプロ
セッサ１０１１で実行中であったタスク（タイマ割込み
で中断された）はステップ２０９で待行列の後端に接続
される。これら待行列のタスクの出２人はポインタ変更
により行われる。

そしてステップ２０９で待行列から取り除いたタスク１
０６２を実行する。

第４図は、各プロセッサによるタスクの実行例をタイム
チャートで示したものである。同図ではプロセッサ１０
１１〜１０１３による処理のタイムチャートがＰＯ〜Ｐ
２で示されており、タイマ割込み３０１〜３０９および
タスクの終了３５０によりスケジューラプログラムが動
作し、タスク３６０〜３７０が各プロセッサ上で実行さ
れている様子を示している。即ち、最初はプロセッサ１
０１１〜１０１３は、それぞれタスクＴ３．Ｔ４．Ｔ５
を実行していたとする。プロセッサ１０１１にタイマ割
込み３０１が入ると、第３図で説明したようにこのプロ
セッサにはタスクＴ１がスケジュールされる。次にプロ
セッサ１０１２にタイマ割込み３０４が入ってタスクＴ
２が実行され、プロセッサ１０】３にタイマ割込み３０
７が入り、タスクＴＯが実行される。プロセッサ１０１
２では、実行されていたタスクＴ２の終了３５０により
、タスクＴ３が再び実行される。以下、同様に処理が続
く。

第５図は、第１図のタスク１０６１〜１０６６を実現す
るだめのタスクテーブルを表す。タスク識別子１５０は
タスクに付けたシリアル番号であり、信号をタスクに送
るときなどにタスクを識別するのに使われる。タスクの
状態１５１はタスクが現在どのような状態にあるかを表
しており、以下のようなものがある。

Ｕｓｅｒ　Ｒｕｎｎｉｎｇ・・・・プロセッサ上でタス
クのユーザプログラムを実行している状態。

Ｋｅｒｎｅｌ　Ｒｕｎｎｉｎｇ・・・・プロセッサ上で
ユーザプログラム実行中にシステムコールを行ったり、
割込みが入ったりしたためシステムプログラムを実行し
ている状態。

Ｒｅａｄｙ　ｔｏ　Ｒｕｎ・・・・タスクは実行できる
状態になっているが、まだ、プロセッサが割当てられて
いない。タスクは待行列に繋がれている。

５ｌｅｅｐ・・・・・Ｉｌｏの応答待ちなど、ある事象
が起るのを待っている状態。

優先度１５２はタスクが実行される優先度を表す数値で
、この数値が大きいほど先にプロセッサで実行される。

プロセッサが割り当てられるのを待っているタスクの待
行列は、この優先度が大きい順に並べられる。

実行可否フラグ１０７は、第１図のフラグ１０７１〜１
０７３と同じものであり、本発明の実現のために設けら
れた。これは当該タスクがどの種類のプロセッサで実行
できるかの情報が入る。シグナル・フィールド１５３は
、タスク間でタスクの中断、終了。

エラーなどの情報を送るシグナルが入るフィールドであ
る。タイマー１０８は、タスクの実行時間、システムの
実行時間などの時間の情報が入るフィールドである。リ
ージョン・テーブル１５４は、タスクで使われるプログ
ラムやデータが記憶されているリージョンのページテー
ブルを指すポインタとリージョンの大きさの情報が入っ
ている。レジスタ退避領域１５５には、タスクがタイマ
ー割込みにより中断されたときなどに、中断される前の
タスクのレジスタの情報を退避する領域である。中断さ
れたタスクがスケジュールにより再開されるときには、
ここに退避してあったレジスタの情報をもとにタスクを
再開する。ポインタ１５６．１．５７は第１図で述べた
タスクを待行列に繋ぐときのポインタである。

以上に説明した第１図の実施例では、スケジューラプロ
グラムは各プロセッサに設けられており、各プロセッサ
は自分のスケジューリングを自分で行うものとしたが、
これを負荷の最も軽い状態にあるプロセッサでスケジュ
ールするようにすることもできる。第６図はそのように
した実施例を示している。これは第１図の構成と殆ど同
じであるが、異なるのはシステム中のプロセッサの種類
を記憶した表１１０をメインメモリに記憶している点で
ある。表１１０へは、システム立ち上げ時に各プロセッ
サが自分のプロセッサ種類識別子１０２１〜１０２３を
読み出して表１１０に書き込み、これによってスケジュ
ーラ１０９は今スケジュールしようとしているプロセッ
サの種類を識別する。

第７図はこの実施例におけるスケジューラプログラムの
フローチャートであり、スケジュールのためのタイマ割
込みが入ったときにいずれか負荷の低いプロセッサで実
行される。第６図の状態、即ちプロセッサ１０】２にタ
イマ割込みが入って、スケジューラプログラムが実行さ
れたとすると、まずステップ７０１で待行列のヘッダ１
．０５の指すタスク】０６１を見る。ステップ７０２で
、この見たところにタスクがないか調べる。未処理のタ
スクがなかったときは、スケジューラプログラムは何も
せずに終了するが、今はタスク１０６１が有ったのでス
テップ７０３へ進む。ステップ７０３では、タスクの実
行可否フラグで実行可能となっているプロセッサの内（
これをメインメモリ１０４の表１１０を用いて調べる）
、アイドルのプロセッサがあればそのプロセッサを選び
、なければ現在処理しているタスクの処理時間を第５図
のタイマ１０８より調べ、それが最も長いプロセッサを
選ぶ。第６図では実行可否フラグが”　１　］　０　”
なので実行可能なプロセッサの梅類はタイプ１とタイプ
２である。これに該当するのはプロセッサ１．０１３ｔ
、かないのでこのプロセッサがここでは選択される。ス
テップ７０４では選択したプロセッサが実行していたタ
スクを中断し、その状態をセーブする。選択されたプロ
セッサ１ｏ１３ではタスクＴ５が実行されていたから、
このタスクを中断し、中断したときのレジスタの内容を
タスクＴ５のタスクテーブル内のレジスタ退避領域１５
５に退避する。ステップ７０５では、中断したタスクＴ
５を待行列に入れる。入れる場所はタスクテーブルに書
かれている優先順位１５２が大きい順に並ぶように挿入
する。最後にステップ７０６で選択したタスク１０６１
　（Ｔ６）を待行列より取り出して、選択したプロセッ
サ１．０１３で実行させる。

第８図は、各プロセッサによるタスクの実行例を示すタ
イムチャートで示したものである。プロセッサ１０１１
〜１０１３による処理のタイムチャートがＰＯ〜Ｐ２で
示されており、スケジューラプログラムＳの終了３３０
〜３３２の時にコンテキストスイッチ３４０〜３４２に
よって実行タスクが切り換えられる。

最初、プロセッサ１０１１〜１０１３はそれぞれタスク
Ｔ３、スケジューラプログラムＳ、タスクＴ５をそれぞ
れ実行していたとする。第７図を用いて説明したように
、スケジューラＳはプロセッサ■０１３で実行していた
タスクＴ５をコンテキストスイッチ３４２により中断さ
せ、タスクＴＯを実行させる。スケジューラＳが終了す
るとプロセッサ１０１２は以前に実行していたタスクＴ
４の実行に戻る。一定時間が過ぎると再びタイマ割込み
３１０が入り、スケジューラＳが実行される。このスケ
ジューラは、第６図のタスクＴ１を待行列より取り出し
てくる。

タスクＴ１の実行可否フラグ１０７２は“００１”なの
でタイプＯのプロセッサで実行できる。これはプロセッ
サ１０１１，１．０１２であるが、どちらのプロセッサ
もタスクを実行中なので現在実行しているタスクの実行
時間の長い方のプロセッサを選択する。

第８図ではプロセッサ１０１１の方が長かったとして、
このプロセッサ１０１１でタスクＴＩを実行させている
。以下同様に一定時間間隔でタイマ割込みにより、いず
れかのプロセッサでスケジューラが実行され、待行列の
タスクがスケジュールされていく。

第９図は本発明の別の実施例を示す図である。

本実施例では各プロセッサ１０１１〜１０１３は、その
識別子１０２１〜１０２３に示されているように、構成
が異なっており、命令セットが一部異なっている。メイ
ンメモリ１０４内の待行列に繋がれたタスク１０６１〜
１０６３の各々には、各種類のプロセッサがタスクに対
してどのような優先度を持つかを記憶したテーブル１０
８１〜１０８３が設けられている。テーブル１０８１の
最初の行は、プロセッサ種類識別子００１を持つタイプ
０のプロセッサがタスク１０６１に対して０の優先度を
持っていること、すなわち、タイプ０のプロセッサは、
このタスクを実行できないことを表している。以下の行
はタイプ］−のプロセッサが１０の優先度をもち、タイ
プ２のプロセッサは２０の優先度を持つことを表す。

第１０図は第９図の実施例で使用するスケジューラプロ
グラムのフローチャートである。このスケジュールプロ
グラムは第３図のスケジューラプログラムと同様に、実
行していたタスクが終了したときと、スケジュールのた
めのタイマー割込みが入ったときに実行される。タイマ
ー割込みは、各プロセッサに一定時間間隔で入る。第９
図の状態でプロセッサ１０１３にタイマー割込みが入っ
て、スケジューラプログラムが実行される場合を説明す
る。まず、ステップ１００１で自分のプロセッサのプロ
セッサ種類識別子１０２１を読込む。読込んだ値は０１
０である。次にステップ１００２で待行列のへラダ１０
５にタスクが接続されているか調べている。タスクが接
続されていない場合は、処理すべきタスクが無いことを
示しているのでアイ１くル処理１００３を行う。ここで
はタスク１０６１が接続されているのでＹｅＳの方に進
み、ステップ１００４で待行列に接続されているタスク
のうち、プロセッサ種類識別子に対応した優先度が最大
のタスクを選択する。第９図ではタスク１０６１〜１０
６３が待行列に接続されており、プロセッサ種類識別子
０１０に対応した優先度は、それぞれ１０．０．２０で
ある。よって、優先度２０を持つタスク１０６３が選択
される。選択されたタスクの優先度は０ではないので、
ステップ１００５からステップ１００６へ進む（もし１
選択されたタスクの優先度がＯだった場合は、自プロセ
ッサの種類では実行できるタスクがないということなの
で、アイドル処理１００３を行う）。ステップ１００６
ではタスク１０６３を待行列から取り除く。即ちポイン
タ１５６２をなくする。最後にステップｔｏ　０７でタ
スク１０６３を実行する。

第１ｊ図は、第９図の各タスクを実現するためのタスク
テーブル１０６を示す。第５図のテーブルと比較して異
なるのは、第５図の実行可否フラグ１０７がなくなり、
第５図の優先度１５２がプロセッサ種類ごとの優先度１
５８になった以外は同じである。

実行可否フラグで表現していたプロセッサの種類ごとに
よるタスク実行の可否は、優先度１５８が０か否かで表
現している。

第１２図は本発明の別の実施例を示す図である。

第９図の実施例では、各プロセッサがスケジューラプロ
グラムを持ち、自プロセッサのスケジューリングを行う
としたが、本実施例ではプロセッサの種類を記憶した表
１１０をメインメモ１月０４に記憶しておき、これを用
いていずれかのプロセッサがそのとき必要なスケジュー
リングを行う。このため、システム立ち上げ時に各プロ
セッサが自分のプロセッサ種類識別子１０２１〜１０２
３を読み出して表１１０に書き込んでおく。

第１３図は本実施例におけるスケジューラのフローチャ
ートを示す。スケジューラプログラムは、スケジュール
のためのタイマー割込みが入ったときにいずれか負荷の
低いプロセッサで実行される。

そこで、第１２図のように、プロセッサ１０１１にタイ
マー割込みが入って、ここでスケジューラプログラム１
０９が実行された場合を説明する。まず、ステップ１３
０Ｉで待行列のヘッダ１．０５の指すタスク１０６１を
見る。ステップ１３０２でタスクがないか調べ、未処理
のタスクがなかったときは、スケジューラプログラムは
なにもせずに終了する。ここでは、タスク１０６１が有
ったのでステップ１３ｏ３へ進み、タスク１０６Ｉの優
先度テーブル１０８１を見て、優先度が最も高くなって
いるプロセッサ種類を選択する。

ここでは優先度２０をもつプロセッサ種類識別子１００
（タイプ２）のプロセッサが選択される。ステップ１３
０４では選択されたプロセッサ種類のプロセッサを表１
１０より調べ、プロセッサ１０１２がその種類のプロセ
ッサであることがわかる。ここではその種類のプロセッ
サが１つしがながったが、複数あったときは現在そのプ
ロセッサが実行しているタスクの実行時間が最も長いプ
ロセッサを選択する。ステップ１３０５では選択したプ
ロセッサが実行していたタスクを中断し、その状態をセ
ーブする。選択されたプロセッサ１０１２ではタスクＴ
４が実行されているから、このタスクを中断し、中断し
たときのレジスタの内容をタスク１０６５　（Ｔ４）の
タスクテーブルのレジスタ退避領域１５５　（第１１図
）に退避する。ステップ１３０６では、中断したタスク
Ｔ４を待行列の最後に入れる。最後にステップ１３０７
で選択したタスク１０６１を待行列より取り出して、選
択したプロセッサ１０１２で実行させる。

第１４図は本発明の別の実施例を示す図である。

本実施例では３個のプロセッサ１０１１〜１０１３がネ
ットワーク３００に接続され、各々はローカルメモリ３
１０１〜３１０３を有している。第１図、第６図、第９
図、第１２図の実施例では、各プロセッサ全てからアク
セス可能なメインメモリ１０４に待行列を記憶させてい
たが、本実施例では待行列はマスターとなるプロセッサ
１０１１のローカルメモリ３１０１に記憶されている。

このプロセッサ１０１１以外のプロセッサがスケジュー
リングのために待行列にアクセスする必要があるときは
、ネットワーク３００とプロセッサ１０月を通してロー
カルメモリ３１０１にアクセスする。実行可能か否か、
および優先度に基づくスケジューリングの方法は既に述
べた実施例と同じである。

第１５図は本発明の別の実施例を示す図である。

本実施例は、第１４図の実施例の変形例であり、マスタ
ーとなるプロセッサがなく、すべてのローカルメモリに
同一の待行列が記憶されている。即ち各ローカルメモリ
３１０１〜３１０３のヘッダ１０５１〜１０５３には、
同一のタスク１０６１．１０６２が繋がれており、各プ
ロセッサは、自分のローカルメモリの待行列を見てスケ
ジューリングする。待行列の更新は、他の全てのプロセ
ッサに許可を得てから、自分のローカルメモリ内で行う
とともに、各自のローカルメモリでも更新するよう、他
プロセッサに指示するメツセージをネットワーク３００
に放送する。

第１６図は、本発明の別の実施例を示す図であり、第１
５図の実施例の各ローカルメモリ３１０１〜３１０３を
１つの仮想共有メモリ３２０としてアクセスする構成と
したものである。どのプロセッサからでも任意のローカ
ルメモリへアクセスでき、スケジューリングに用いる待
行列もこの仮想共有メモリに記憶させる。

第１７図は仮想共有メモリ３２０の論理アドレスと物理
アドレスのマツピングの例を示す。仮想共有メモリの論
理アドレス空間５００の各アドレス領域がローカルメモ
リ３１０１〜３１０３の物理アドレス空間５１０１〜５
１０３に対応づけられる。この対応づけを行うためのア
ドレス変換テーブルが第８図に示されており、例えばあ
るプロセッサが論理アドレスＯをもつページをアクセス
したとする。このページのプロセッサ番号ＩＤＯが自プ
ロセッサの番号であれば、自分のローカルメモリ内の物
理アドレス０のページより読み出す。プロセッサ番号が
異なる場合は、アクセスしたプロセッサは１番号ＩＤＯ
をもつプロセッサに物理アドレス０のページを転送する
ように、ネットワーク３００を通してメツセージを送る
。メツセージを受けたプロセッサは要求されたページを
メツセージにして要求元に送る。この実施例においても
、タスクごとの実行可否あるいは優先度にもとづく制御
は先の実施例と同様である。

〔発明の効果〕

本発明によれば、アーキテクチャが異なり、命令セット
も一部異なるプロセッサよりなるマルチプロセッサがあ
るとき、ユーザは、タスクをどのプロセッサで実行させ
るかを意識する必要がないのでタスクの管理効率が大幅
に向上する。

また、本発明によれば、命令セットは共通であるが、ベ
クトルプロセッサなどにより、ある種の処理が強化しで
あるプロセッサを含むマルチプロセッサで、タスクの処
理内容により最適なプロセッサを割当てるスケジューリ
ングが提供されるのでシステムのスループットが向上す
る。

【図面の簡単な説明】

第１図は本発明の一実施例を示す図、第２図はシステム
を構成するプロセッサの種類とプロセッサ種類識別子の
対応を示す図、第３図は第１図の実施例で用いるスケジ
ューラのフローチャート、第４図は第１図の実施例の動
作例を示すタイムチャート、第５図は第１−図の実施例
におけるタスクテーブルの構成例を示す図、第６図、第
７図および第８図は本発明の別の実施例を示す図、用い
るスケジューラのフローチャート、および動作例を示す
タイムチャート、第９図、第１（）図および第１１図は
本発明の別の実施例を示す図、用いるスケジューラのフ
ローチャート、およびタスクテーブルの構成例を示す図
、第１２回および第１３図は本発明の別の実施例で示す
図および用いるスケジューラのフローチャート、第１４
図及び第１５図はそれぞれ各プロセッサがローカルメモ
リを有してネットワークで結合されたシステムでの本発
明の実施例を示す図、第１６図は各プロセッサが有する
ローカルメモリを１つの仮想メモリとしてアクセスする
ようにしたシステムでの本発明の実施例を示す図、第１
７図および第１８図は第１ｂ図の実施例における論理空
間と物理空間の対応っけの説明図および上記２つの空間
の対応っけを行うアドレス変換テーブルの説明図である
。 １０］１−１０］３−・・プｏ　セラ＋ｊ、１０２１〜
１０２３−プロセッサ種類識別子、１ｏ；３・・・共有
バス、１０４・・・メインメモリ、１０５・・・ヘッダ
、１０６１〜１ｏ６６・・・タスク、１０７１〜１０７
３・・・実行可否フラグ、１０８１〜１ｏ８３・・・優
先度テーブル、］、０９・・・スケジューラプログラム
、１１０・・・プロセッサ種類識別子表、３１０１〜３
１ｏ３・・・ローカルメモリ、３ｚＯ・・・仮想共有メ
モリ。 代理人弁理士　　秋　本　正　実 ］ｎ］］ 第 図 １Ｇ］３ 第 図 第 図 第 図

Claims (1)

1. 【特許請求の範囲】 １、全てが同一構成ではない複数のプロセッサと該プロ
   セッサの各々によりアクセス可能な主メモリが共有バス
   で接続されて成るマルチプロセッサシステムでのタスク
   のスケジューリング方法において、各プロセッサに自プ
   ロセッサのスケジュール手段と自プロセッサの種別を示
   す識別子の認識手段とを有せしめ、主メモリに未処理タ
   スクの待行列を格納し、かつ各タスクには自タスクを実
   行可能なプロセッサの種別を示す実行可否フラグを含む
   タスクテーブルを設けるとともに、いずれかのプロセッ
   サにスケジューリングが必要となった場合に、当該プロ
   セッサのスケジュール手段は、上記主メモリの待行列に
   繋がれたタスクを順次読み出し、自プロセッサの識別子
   と上記読み出したタスクの上記実行可否フラグとの比較
   から実行可能と判断した最初のタスクを実行タスクとす
   ることを特徴とするタスクのスケージューリング方法。 ２、全てが同一構成ではない複数のプロセッサと該プロ
   セッサの各々によりアクセス可能な主メモリが共有バス
   で接続されて成るマルチプロセッサシステムでのタスク
   のスケジューリング方法において、いくつかのプロセッ
   サにスケジュール手段を有せしめ、主メモリに未処理タ
   スクの待行列と各プロセッサの種別を示す識別子表とを
   格納し、かつ各タスクには自タスクを実行可能なプロセ
   ッサの種別を示す実行可否フラグを含むタスクテーブル
   を設けるとともに、いずれかのプロセッサにスケジュー
   リングが必要となった場合に、上記スケジュール手段を
   有するプロセッサの１つが、タスク処理中であればその
   処理を中断してスケジュール手段を起動し、上記主メモ
   リの待行列に繋がれたタスクを順次読み出し、該読み出
   したタスクの上記実行可否フラグと上記スケジューリン
   グが必要なプロセッサの上記識別子表から読み出した識
   別子との比較から実行可能と判断した最初のタスクを実
   行タスクとすることを特徴とするタスクのスケジューリ
   ング方法。 ３、全てが同一構成ではない複数のプロセッサと該プロ
   セッサの各々によりアクセス可能な主メモリが共有バス
   で接続されて成るマルチプロセッサシステムでのタスク
   のスケジューリング方法において、各プロセッサに自プ
   ロセッサのスケジュール手段と自プロセッサの種別を示
   す識別子の認識手段とを有せしめ、主メモリに未処理タ
   スクの待行列を格納し、かつ各タスクには自タスクを実
   行する上での各プロセッサ種別ごとの優先度を示す優先
   度テーブルを含むタスクテーブルを設けるとともに、い
   ずれかのプロセッサにスケジューリングが必要となった
   場合に、当該プロセッサのスケジュール手段は、上記主
   メモリの待行列に繋がれたタスクを順次読み出し、自プ
   ロセッサの識別子に対して最も優先度の高いタスクを各
   タスクの上記優先度テーブルを参照して選び出し、該選
   び出したタスクを実行タスクとすることを特徴とするタ
   スクのスケジューリング方法。 ４、全てが同一構成ではない複数のプロセッサと該プロ
   セッサの各々によりアクセス可能な主メモリが共有バス
   で接続されて成るマルチプロセッサシステムでのタスク
   のスケジューリング方法において、いくつかのプロセッ
   サにスケジュール手段を有せしめ、主メモリに未処理タ
   スクの待行列と各プロセッサの種別を示す識別子表とを
   格納し、かつ各タスクには自タスクを実行する上での各
   プロセッサ種別ごとの優先度を示す優先度テーブルを含
   むタスクテーブルを設けるとともに、いずれかのプロセ
   ッサにスケジューリングが必要となった場合に、上記ス
   ケジュール手段を有するプロセッサの１つが、タスク処
   理中であればその処理を中断してスケジュール手段を起
   動し、上記主メモリの待行列に繋がれたタスクを順次読
   み出し、上記スケジューリングが必要なプロセッサの識
   別子に対して最も優先度の高いタスクを各タスクの上記
   優先度テーブルを参照して選び出し、該選び出したタス
   クを実行タスクとすることを特徴とするタスクのスケジ
   ューリング方法。 ５、前記優先度に実行不能を示す不能値を設け、あるタ
   スクに対して上記不能値が指定された種別のプロセッサ
   には当該タスクを割り当てないことを特徴とする請求項
   ３または４記載のタスクのスケジューリング方法。 ６、前記主メモリに代って各プロセッサ対応にローカル
   メモリを設け、前記共有バスに代って各プロセッサ間を
   結合するネットワークを設けるとともに、前記待行列は
   マスターとして指定された１つのプロセッサ対応のロー
   カルメモリに格納し、上記待行列への他プロセッサから
   のアクセスを上記ネットワークを介して行うことを特徴
   とする請求項１、２、３、４または５記載のタスクのス
   ケジューリング方法。 ７、前記主メモリに代って各プロセッサ対応にローカル
   メモリを設け、前記共有バスに代って各プロセッサ間を
   結合するネットワークを設けるとともに、前記待行列は
   すべてのプロセッサ対応のローカルメモリに格納し、待
   行列の更新時には上記ネットワークを介してすべてのロ
   ーカルメモリで行うようにしたことを特徴とする請求項
   １、２、３、４または５記載のタスクのスケジューリン
   グ方法。 ８、前記主メモリに代って各プロセッサ対応にローカル
   メモリを設け、前記共有バスに代って各プロセッサ間を
   結合するネットワークを設けるとともに、すべてのロー
   カルメモリの物理空間アドレスを論理空間のアドレスに
   対応づけるためのアドレス変換手段を各プロセッサに設
   けることにより単一の仮想メモリを形成し、該仮想メモ
   リを各プロセッサの共有メモリとしたことを特徴とする
   請求項１、２、３、４または５記載のタスクのスケジュ
   ーリング方法。