JPS646488B2

JPS646488B2 -

Info

Publication number: JPS646488B2
Application number: JP55173910A
Authority: JP
Inventors: Buure Jannmarii
Original assignee: Bull SAS
Current assignee: Bull SAS
Priority date: 1979-12-11
Filing date: 1980-12-11
Publication date: 1989-02-03
Also published as: US4590555A; EP0030504A1; FR2471631B1; EP0030504B1; FR2471631A1; JPS56124964A; DE3070839D1

Description

【発明の詳細な説明】本発明は、データ処理装置もしくはデータ処理
システムにおいて複数の処理ユニツト（プロセツ
サ）の間にプロセスを割当て且つ同期化させる装
置に関し、より詳細には、複数の個別の処理ユニ
ツト（プロセツサ）と、「母線」と呼ばれるデー
タ伝送チヤンネル系統により各々の処理ユニツト
が、別の処理ユニツトを介さずに接続され得る主
記憶装置と、処理ユニツトを主記憶装置に選択的
に接続するために該母線に組合わせた接続手段と
を有するデータ処理装置もしくはシステムに関す
る。

本明細書において「プロセス」とは、ユーザー
により指示された仕事を行うためデータ処理装置
により実行され得る、１組の順序付けられた命令
及びこれらの命令に組合わされた１組のデータか
ら成るプログラムを意味する。

プロセスは処理ユニツトもしくはプロセツサに
より実行され得る。処理ユニツトは、プロセスに
固有の命令の実行を制御してプロセスに関連した
データを処理することのできるデータ処理装置の
ハードウエア装置である。

多数のプロセスが同時に同一の処理ユニツトに
与えられる時、これらのプロセスの実行の優先順
位を管理すること、並びに処理ユニツトにプロセ
スを通信することは非常に複雑である。しかしこ
れらの問題が解消されたデータ処理装置は知られ
ている。これらの問題の解決は、本出願人の仏国
特許第2253419号「データ・プロセツサのプロセ
ス管理方式」及び第2253417号「セマフオを用い
たプロセスの同期化」に記載されている。しかし
LSI即ち大規模集積回路技術を用いた高度に集積
化された計算機の開発により、複数のプロセツサ
もしくはマイクロプロセツサを組合わせて動作さ
せるデータ処理装置が有利になつた。この場合当
然提起される問題に、データ処理装置の処理ユニ
ツトへのプロセスの割付けがある。

処理ユニツトへのプロセスの割付けは時間のか
かる操作であり、その複雑さは使用される選択ア
ルゴリズムによる。選択アルゴリズムが複雑なほ
ど、データ処理装置の作動に必要なパラメーター
を収容したテーブルがじよう乱を受け易い。

従つて本発明の目的は、高性能であまり複雑で
ない、新規で改良された、処理ユニツトへのプロ
セスの割付け装置を提供することにある。

本発明の別の目的は、前記仏国特許に記載され
ているような単一の処理ユニツトにて複数のプロ
セスが実行されるデータ処理システムに用いられ
る概念を、複数の処理ユニツトを含むデータ処理
システムに拡大し得るようにすることにある。

本発明によれば、複数のプロセスは、デイスパ
ツチヤにより複数の処理ユニツトに割付けられ
る。デイスパツチヤは選択段階及び実行段階と呼
ばれる２つの段階でプロセスを処理ユニツトに割
付ける。SELECTとも称す選択段階では、実際
の処理ユニツトが候補プロセスに割当てられ、
EXECと呼ばれる実行段階では選択された実際の
各々の処理ユニツトが現在のプロセスの内容
（context）をからにし、それを新しいプロセスの
内容に置換する。

本発明の別の特徴によれば、実行を待つている
プロセスの状態又は実行中の処理ユニツトの状態
に変化が起こつた時にデイスパツチヤの呼び出し
が放たれ、デイスパツチヤによるこの呼び出し
は、変化がなされた処理ユニツトによりひき起こ
される。

次に図面に示した本発明の好ましい実施例につ
いて詳述する。

第１図に示したデータ処理装置は、記憶制御ユ
ニツト（MCU）２から制御される、読取り／書
込みを行う主記憶装置（MMU）１を備えてい
る。第１図のデータ処理装置はそのほかに、記憶
制御ユニツト２の入力部に単一の母線３により一
緒に接続される複数の中央処理ユニツトもしくは
プロセツサ４，６，８等を備えている。母線３は
命令及びデータのアドレス語を記憶制御ユニツト
２と一群の処理ユニツト４，６，８との間で伝送
する。

各々の処理ユニツト４，６，８はそれぞれ入出
力制御装置（IOC）５，７，９を経て周辺制御ユ
ニツト（PCU）１０，１１，１２に接続されて
いる。周辺制御ユニツト１０，１１，１２は、デ
ータ処理装置に含まれる別々の周辺装置ユニツト
（PU）１３に接続されている。主記憶装置
（MMU）１は、第１図の処理ユニツト４，６，
８により実行されるべき複数のプロセスを常時保
持している。

前述したように、プロセスとは、各々の処理ユ
ニツト４，６，８により実行され得る順序付けさ
れた１組の命令として定義される。或るプロセス
が、ある特別の処理ユニツトにおいて実行中であ
るとして、そのプロセスは、それを実行している
処理ユニツトの制御をいつでも離れて、その処理
ユニツトの制御を別のプロセスへと移行させるこ
とができる。

或るプロセスが処理ユニツトの制御を離れる
時、その状態は、主記憶装置１の適切な記憶領域
に保存しなければならない。

このように保存されたプロセスの状態は、中断
されたこのプロセスが制御ユニツトの制御を再び
受けるようになる前にその処理ユニツトを予め条
件づけるために利用することができる。

或るプロセスに割当てられた主記憶装置１の記
憶領域は、プロセス制御ブロツク（PCB）と呼
ばれ、第２図に図示されている。プロセス制御ブ
ロツクは複数の領域に分割されている。「優先」
と表示した領域は、プロセスが有する優先レベル
もしくは優先順位を規定する。「状態」と表示し
た領域はプロセスの状態を規定し、この「状態」
とは、特に、プロセスが中止されたこと、開始さ
れていないこと、実行準備状態にある他のプロセ
スと共に待ち行列にはいつていること、セマフオ
上で待ち行列にはいつていること、又は、或る処
理ユニツトにおいて実行中なこと、を指示し得
る。DCNと表示された領域はプロセスが実行さ
れる様式（decor）を示すもので、この領域は、
プロセスを実行する各処理ユニツトは、実際、独
自の機能的なアーキテクチヤを有しており、或る
プロセスは或る特別の様式と共にのみ実行され得
るという理由で用いられているものである。

領域DCNに記憶された様式（decor）がデータ
処理装置の様式もしくはアーキテクチヤと調和す
ることが必要である。

プロセスの領域DCNに対応する様式が、該プ
ロセスを実行するよう選択された処理ユニツトに
存在しない時はPCBは違法とみなされる。

領域STWA（ASW）はセグメントアドレステ
ーブルの開始アドレスを表わし、プロセスに割当
てられた識別子のアドレスを得るために役立つ。
領域Ｔ（SKW）は、パイルセグメントもしくはス
タツクセグメント中に在るパイルもしくはスタツ
クの頂点の、ポインターレジスターＴ内の値を収
容している。この領域Ｔ（SKW）中に収容された
語は、プロセスが実行されていない時パイルセグ
メントもしくはスタツクセグメントの頂点の、レ
ジスタ内の値を収容し、プロセスが実行状態を離
れるつど更新され、プロセスが処理ユニツトにお
いて実行にはいるつど処理ユニツトの真のレジス
ターＴの内容を更新するために使用される。領域
IC（ICW）はプロセスの実行が処理ユニツト上に
おいて停止した時点に存在した処理ユニツトの命
令カウンターの値を収容している。この領域は、
プロセスが実行の状態を離れるつど更新され、プ
ロセスが実行に再度移行するつどプロセスが実行
される処理ユニツトの命令カウンターを更新する
ために使用される。領域PRHM、PRSMは、デ
ータ処理装置の各処理ユニツトに対応した状態を
有する１ビツトマスクとして用いられる。ビツト
の「０」状態は、このビツト状態に対応する処理
ユニツト上にてプロセスが実行され得ることを指
示し、ビツトの「１」状態はそれができないこと
を指示する。プロセス制御ブロツクは、プロセス
が処理ユニツトの或るレジスターにおいて行なわ
れていて割込みにより中断された時、これらのレ
ジスターの内容を保護するための他の領域を有し
得る。このことの詳細については前述した本出願
人の仏国特許公報の同様のブロツクの記載を参照
されたい。

第３Ａ〜３Ｃ図に、プロセスを別々の処理ユニ
ツトに割当て得るようにするために各々の処理ユ
ニツトに備えるべき要素を示す。

第３Ａ図に示した要素は、本発明による割当て
−同期化装置を実施するように構成された中央情
報処理ユニツトの既知の構造を形成している。こ
の構造の詳細は、プランテイス・ホール・エデイ
シヨン刊行、コピーライト70、サミール・Ｓ・イ
ユツソン著、「マイクロプログラミング、原理及
びプラクテイス」に記載されている。

第３Ａ図に示した本発明による装置部分は、主
記憶装置（MMU）１、主記憶装置１の記憶制御
ユニツト（MCU）２、制御要素（OC）１５、命
令レジスター（RI）１４、論理演算ユニツト
（ALU）１７、アキユミユレーターレジスター
（ACC）１６、BUSY（「使用中」）レジスター１
９、デコーダー２０、優先レジスター２１及び命
令カウンター（IC）１８を備えている。これら
の各要素は、アドレス母線Ａ、制御母線Ｃ、デー
タ母線Ｄ及び試験母線Ｔとして表わした、母線３
の部分である導線を介し互に接続されている。制
御母線Ａは記憶制御ユニツト２の入力１を命令カ
ウンター（IC）１８の出力２に接続している。
命令カウンター１８は実行中の命令のアドレスを
収容している。主記憶装置（MMU）において読
出されたり書込まれたりするデータ及び命令は、
主記憶装置（MMU）１の端子２に接続されたデ
ータ母線Ｄを介して処理ユニツトに転送され、そ
して命令レジスター（RI）１４の入力１、アキ
ユミユレーターレジスター（ACC）１６の入力
１、BUSYレジスター１９の入力１、優先レジ
スター２７の入力１と出力２、及び論理演算ユニ
ツト１７の入力２に転送される。命令レジスター
１４は出力２により制御要素１５の入力１に接続
されている。制御要素１５はサミール・Ｓ・イユ
ツソンの前記著書第491〜500頁に記載された型式
のマイクロプログラムされた構造を有する。

制御要素１５は出力Q₁〜Qnを有し、これら出
力上には、処理ユニツトの種々の要素を選択的に
付勢するのを制御する信号C₁〜Cnが引き出され
る。制御要素１５は、第７Ａ図、第７Ｂ図、第８
Ａ図、第８Ｂ図、第８Ｃ図のフローチヤートに関
連した動作を行うマイクロプログラムを格納して
いる。

制御要素１５は試験母線Ｔに入力２において接
続され、従つて処理ユニツトの試験装置群から送
出される試験結果を受取る。従つて制御要素１５
は、実行されるべき命令の型式及び特別の試験結
果に従つて、制御要素１５に書込まれたマイクロ
プログラムの開始アドレスにおいての分岐を実行
し得る。これらのマイクロプログラムの実行によ
つて、制御要素１５のQ₁〜Qn出力に接続した母
線Ｃに特別の命令が発生される。

アキユミユレーターレジスター（ACC）１６
の出力２は論理演算ユニツト１７の入力１に接続
されている。論理演算ユニツト１７は入力１及び
２に与えられる２つのオペランド（第１のオペラ
ンドはアキユミユレーターレジスター１６中に収
納されており、第２のオペランドは母線Ｄに発生
する）について論理演算を行う。２つのオペラン
ドについての演算の結果は、ユニツト１７の出力
３から母線Ｄに戻され、従つて母線Ｄを経てアキ
ユミユレーターレジスター１６の入力１へと再転
送されるか、もしくは制御要素１５の出力によつ
てユニツト１７と同時に可能化される該プロセツ
サの別のレジスタに転送される。

BUSYレジスター１９の出力２は、出力２を
試験母線Ｔに接続したデコーダー２０の入力１に
接続されている。デコーダー２０は入力１に与え
られるビツトの所定の結合に応答して２進の１信
号を出力し、ビジーレジスター１９が２進の１及
び０の所定の結合を含んでいるということを制御
要素１５に指示する。制御要素（OC）１５は、
デコーダー２０によつて与えられた信号に応答し
て、制御信号C₁〜C₇をそれぞれ記憶制御ユニツ
ト（MCU）２の入力２、命令レジスター（RI）
１４の入力３、論理演算ユニツト（ALU）１７
の入力４、アキユミユレーターレジスター
（ACC）１６の入力３、BUSYレジスター１９の
入力３、優先レジスター２１の入力３及び命令カ
ウンター（IC）１８の入力３に発生させる。

第３Ｂ図に示した回路は、制御母線である母線
Ｃ、データ母線である母線Ｄ及び試験母線である
母線Ｔの回りに形成されている。

母線Ｃは、制御線C₈によりRCPMKレジスター
２４の入力３に接続されていると共に、制御線
C₉によりセレクター２５の入力Ｃにも接続され
ている。制御線C₉により制御されるセレクター
２５はPSTRレジスターバンク２６のｎ個のレジ
スターの選択を確実にする。IQWレジスター２
２の出力２はNOR回路２３を経て母線Ｔに接続
されている。第３Ｂ図の回路はそのほかに作業レ
ジスター群２６−２を有し、作業レジスター群２
６−２は母線Ｄに既知のように接続され、制御線
C₉−２により制御される。

第３Ｃ図には、制御母線Ｃ、データ母線Ｄ上
の、処理ユニツト４，６，８からの信号に応答
し、試験母線Ｔに与えられる信号を出力する、記
憶制御ユニツト２内に含まれる回路が示されてい
る。

第３Ｃ図に示される回路は、母線Ｃ，Ｄ及びＴ
の回りに前述のように組織されるフリツプフロツ
プSPLK２７と、カウンターΣEXECi２９と、フ
リツプフロツプ３２とを含む。

フリツプフロツプ（SPLK）２７は、母線Ｃか
ら導線C₁₁に到来する制御信号によりＪ入力及び
Ｋ入力において制御される。フリツプフロツプ
（SPLK）２７のＱ出力は、ANDゲート２８の入
力１に接続してあり、ANDゲート２８の入力２
は母線Ｃから導線C₁₀に到来する信号により制御
される。このようにANDゲート２８によりフリ
ツプフロツプ（SPLK）２７の状態についての試
験を行い得る。カウンター（ΣEXECi）２９は、
初期値を受けるように、母線Ｄに入力１において
接続され、端子３を母線Ｃに接続する導線C₁₂に
母線Ｃから供給される信号により制御される。カ
ウンター２９の出力２はORゲート３０の入力１
に接続してあり、ORゲート３０の出力２はAND
ゲート３１の入力１に接続してあり、ANDゲー
ト３１は、入力２において、入力２を母線Ｃに接
続する導線C₁₃上に母線Ｃにより供給される信号
により制御される。AND３１の出力３は母線Ｔ
に接続されている。ANDゲート３１は、導線C₁₃
上にて制御される時、カウンター２９の状態の試
験を可能にする。フリツプフロツプ
（CONTEST）３２は、Ｊ入力及びＫ入力におい
て、母線Ｃから導線C₁₄上に到来する制御信号に
より制御される。フリツプフロツプ３２のＱ出力
はANDゲート３３の入力１に接続され、ANDゲ
ート３３の入力２はANDゲート３３を母線Ｃに
接続している導体C₁₅上に母線Ｃから到来する制
御信号を受ける。ANDゲート３３の出力３は母
線Ｔに接続されている。ANDゲート３３により
フリツプフロツプ（CONTEST）３２のＱ出力
の状態を試験できる。第３Ｃ図の回路はそのほか
に、Ｊ入力及びＫ入力において導線C₁₆により制
御されるフリツプフロツプ（HG）２７−２を有
し、フリツプフロツプ（HG）２７−２のＱ出力
は直接母線Ｔに接続されている。第３Ｃ図に示し
た回路要素の作用は次の通りである。フリツプフ
ロツプ（SPLK）２７及び（HG）２７−２は、
セマフオと、セマフオにおいて待機中のプロセス
の待ち行列と、データ処理装置中の種々の処理ユ
ニツトの状態を更新するため実行を待つているプ
ロセス又はデータ処理装置において実行の候補に
なつているプロセスの待ち行列とを保護するため
のシステム・ロツクとして用いられる。

フリツプフロツプ（CONTEST）３２は、デ
ータ処理システムが、実行を待つているプロセス
の待ち行列に変更をもたらす操作を行おうとする
とき、制御要素１５からフリツプフロツプ３２の
Ｊ端子に２進の１信号を与えることにより、論理
「１」にセツトされる。この変更は、待ち行列に
別のプロセスを付加することにより、或るプロセ
スを待ち行列から取出すことにより、又は待機し
ているプロセスの順序を変更することにより起こ
り得る。カウンター（ΣEXECi）２９の状態によ
り、処理ユニツトへのプロセスの割付け作業が全
部終了したことを確認できる。カウンター２９
は、選択操作の間に或るプロセスに割付けるべき
処理ユニツトが指定されるつど１だけ増分され、
割付けが終了するつど１だけ減分される。

処理ユニツトへのプロセスの割付けは、システ
ム中の処理ユニツトの現在の状態を記憶してい
る、主記憶装置（MMU）１中にある第４図のテ
ーブルCPSTTの助けを借りて行なわれる。各々
の処理ユニツトの状態は、第４図にフオーマツト
を示した状態語の助けを借りてこのテーブル
CPSTTに記憶される。第４図において、ビツト
１から３の長さのビツト位置を占めるデータフイ
ールドCPSTは、次の意味の内１つを有し得る。

CPST＝000、データ処理システムの構成中に
処理ユニツトが存在しないことを意味する。

CPST＝001、処理ユニツトが利用できないこ
とを意味する。

CPST＝010、処理ユニツトがあいていること
を意味する。この状態では処理ユニツトはプロセ
スを実行できるが、それを行つてはいない。

CPST＝011、処理ユニツトが或るプロセスを
実行中であることを意味する。

16ビツトから16ビツトの長さに亙つているデー
タフイールドは、後述する役目をもつ主記憶装置
（MMU）１中に位置されたセグメントGOのアド
レスを指示する。セグメントGOの性質及び機能
は本出願人の前述した仏国特許に記載されてい
る。

実行準備状態のプロセスは第５図に示すように
主記憶装置（MMU）１中にリンクされている。
符号JPにより表したプロセスは、それらの実行
のために必要な優先順位もしくは優先レベルの関
数として待ち行列中に配分されている。第５図に
はｎ個の優先レベルに対応するｎ個の待ち行列を
示す。各レベルにおいて各々のプロセスはリンク
により互いに結合されており、これらのリンク
は、各々のプロセスから始まつて、それに接続さ
れたプロセスを認識し得るようになつている。或
る優先レベル上にリンクされた最後のプロセス
は、次に低い優先順位のプロセス待ち行列の先頭
のプロセスにそれを結合するリンクを備えてい
る。最高優先順位の待ち行列の先頭のプロセス
は、システム・ベースと呼ばれる記憶装置
（MMU）１の領域中のポインターIQWとして表
されている。この領域はマイクロプログラミング
により展開され、記憶装置（MMI）１の固定領
域の一部をそれ自身形成するベースアドレスレジ
スター（BAR）３５を介しアクセスできる。第
５図に示した待ち行列の管理を容易にするため
に、各優先順位の待ち行列の各最後のプロセスの
アドレスを与える優先順位テーブルが記憶装置
（MMU）１に用意されている。

待ち行列の管理はプログラミングにおいて周知
の問題であり、この問題の１つの解決は本出願人
の前記仏国特許に記載されている。

第６図に、本発明で使用されるプロセスのリン
クのフオーマツトを示す。ビツト０〜15は待ち行
列における次のプロセスのリンクのアドレスを与
える。第16ビツトであるビツトＲはプロセスが実
行され始める時論理１にされる。第17ビツトであ
るＤビツトは同期化の目的に使用される。第18ビ
ツトであるSUビツトは同期化の終了時に使用さ
れる。SUビツトの論理状態が１であると、それ
は、プロセスが中止され、処理ユニツトにより使
用され得ないことを示す。第24〜27ビツト即ち
PRIビツトはプロセスの優先順位を示す。第32〜
47ビツト即ちJPビツトはリンクに対応するプロ
セスの名称を表わす。第48〜63ビツトは処理ユニ
ツトのマスクを表わす。このフイールドの各ビツ
トは１つの処理ユニツトに対応しているので、第
５図に従つて16個までの処理ユニツトを割付ける
ことができる。各々の「０」ビツトはそのランク
（位置）の後方において、プロセスを開始し得る
処理ユニツトの番号を指示する。マスク
（CPMK）は、プロセスが所属する様式、処理ユ
ニツトのCPSTTテーブルにて読出された処理ユ
ニツトの状態、並びに各々のプロセス制御ブロツ
ク中に在るPRSMマスクから構成される。この
マスクは一例として或るプロセスの開始命令
“START PROCESS”が実行される時、そのプ
ロセスがセマフオ上の待ち行列から取出される時
に計算される。

第７Ａ図、第７Ｂ図、第８Ａ図〜第８Ｃ図を参
照して、デイスパツチヤの作用について説明す
る。

第７Ａ図、第７Ｂ図は、候補プロセスに処理ユ
ニツトを割付ける選択機能を実行するために用い
るマイクロプログラムの機能をフローチヤートに
より表わしている。このフローチヤートは各々の
処理ユニツト中において第３Ａ図の制御要素
（OC）１５の記憶装置内に格納されている。この
制御要素１５のプログラミングについての詳細
は、サミール・Ｓ・イユツソンの前記文献に記載
されている。「選択」マイクロプログラムの展開
は前述した種々のハードウエア装置を用いて行な
われる。「選択」操作SELECTは、待機中の全プ
ロセスの中から実行され得るプロセスを選択する
ことに存する。この操作はシステムのプロセス状
態に変更をもたらす処理ユニツトにより行なわれ
る。これは一例として、或るプロセスがセマフオ
においてメツセージを待つており、処理ユニツト
Pnにおいて実行中のプロセスがこのメツセージ
をもつて来た場合で、処理ユニツトPnが選択機
能の実行を引き受ける。プロセスの状態に変更を
もたらすことは、変更をもたらす処理ユニツトに
よりフリツプフロツプ（CONTEST）３２が
「１」論理レベルにセツトされることにより行な
われる。フリツプフロツプ（CONTEST）３２
が「１」にセツトされると、変更をもたらした処
理ユニツトは、「選択」機能を実行するように条
件付けられる。第７Ａ図に示した「選択」マイク
ロプログラムの展開は、最初にシステム・ロツク
のフリツプフロツプ（SPLK）２７の試験を行う
ことに存する（ブロツク1001）。フリツプフロツ
プ（SPLK）２７が論理「１」のレベルにあると
処理ユニツトはそれのBUSYレジスター１９の
状態を確認して（ブロツク1005）、割付けられる
べきプロセスがあるか否かを調べる。BUSY（使
用中）の状態にあると、すなわち、割付けられる
べきプロセスが処理ユニツト内にあるということ
を示すならばそれは次の命令（ブロツク1006）を
実行し、その命令の実行終了後にフリツプフロツ
プ（SPLK）２７の試験に戻る（ブロツク1001）。
フリツプフロツプ（SPLK）２７の状態が０であ
つたら、「選択」を実行する処理ユニツトはフリ
ツプフロツプ２７を「１」状態に移行させ、これ
によりシステムの他の処理ユニツトによる記憶装
置（MMU）１のテーブル及びセマフオへのアク
セスが阻止される。ブロツク1003ではカウンター
（ΣEXECi）２９の状態についての試験が行なわ
れる。カウンター２９の状態が０でないと、フリ
ツプフロツプ（SPLK）２７は「０」にリセツト
され（ブロツク1004）、「選択」機能はそれ以上実
行できなくなる。これは前の段階においての全部
の実行候補プロセスが割付けられた場合にのみ
「選択」機能が実行され得ることを意味する。

カウンターΣEXECiの状態が零であれば、イン
ジケータCONTESTは零に戻される（ブロツク
1008）。

ブロツク1009では処理ユニツトはIQW語をシ
ステム・ベースにおいて探し、第16ビツトから16
ビツトに亙るこの語の領域の内容について試験が
行なわれる（ブロツク1010）。この内容がからで
あつたら、フリツプフロツプ（SPLK）２７は
「０」にリセツトされ（ブロツク1011）、からでな
かつたら、候補プロセスへの処理ユニツトの割当
てがなされ得る（ブロツク1013）。割付け機能を
規定するために使用されるアルゴリズムは種々あ
り、実際、システムの処理手段の重要性に依存す
る。しかしプログラマーは次の規則に従つて最も
適切なアルゴリズムを容易に選定することができ
る。

(イ) プロセスの選択は、実行準備状態にあるプロ
セスの待ち行列中の優先順位により規定される
プロセス自身の優先順位を留意して行うべきで
ある（これについては特に第５図を参照するこ
とが適当である）。

(ロ) 既に実行中のプロセスは選択され得ない。従
つて実行準備状態のプロセスの待ち行列中にお
いてプロセスリンクのビツトＲ及びSUの状態
を確認すべきである。

(ハ) 実行中でないプロセスについては処理ユニツ
トの選択はそのプロセスを実行する可能性をも
つものについて行うべきである。これの確認は
マスク（CPMK）の状態について行うべきで
ある。

(ニ) アルゴリズムは、「使用中」状態及び「あき」
状態の処理ユニツトの中から選択を行い得るよ
うにすべきであり、「使用中」状態にある処理
ユニツトの場合、選択される処理ユニツトは、
その候補プロセスに比べて優先順位の劣るプロ
セスを実行中の処理ユニツトである。

(ホ) 或るプロセスを１以上の処理ユニツトに割付
け得る場合、このプロセスについて既に作業し
たことがあるものの方に選択指向を向けるべき
である。そのプロセスのリンク中にあるビツト
RHUの状態を勘案すべきである。

割付けの結果は、選択された処理ユニツトの番
号を実行すべきプロセスの番号JPに関連付ける
ように、その処理ユニツトの作業レジスターに転
送される。

割付け作業が終了したら「選択」マイクロプロ
グラムは第７Ｂ図のフローチヤートに従つて第５
図の待ち行列を更新させ始める。ブロツク1016で
は、選択された処理ユニツトが確認され、ブロツ
ク1018では、選択された各々の処理ユニツトにつ
いて、第５図の待ち行列中のプロセスリンクが更
新され、１つの処理ユニツトが選択されるつどカ
ウンター（ΣEXECi）２９が１増分され、この処
理ユニツトについてEXEC機能の実行が求められ
る。

第８Ａ図〜第８Ｃ図は、選択された各々の処理
ユニツトについてEXEC機能を実行するために生
ずるマイクロプログラムの機能を表わしている。

第８Ａ図において、ブロツク2001では、選択さ
れた処理ユニツトは、「あき」又は「使用中」で
あり得るその状態を確認する。「使用中」状態に
あつたらその処理ユニツトは、或るプロセスを実
行中であるが、その実行を中止し、そのプロセス
を第５図の待ち行列中に配列し新しく割付けられ
たプロセスを引受けなければならない。ブロツク
2003では‘ROLL OUT'と呼ばれる連鎖が実行
される。この連鎖は、処理ユニツトの各レジスタ
ーの全コピーをからにし、プロセス制御ブロツク
（PCB）を更新する連鎖である。フリツプフロツ
プ（SPLK）２７は、EXEC機能を実行する処理
ユニツトによりブロツク2004において「１」にセ
ツトされ、これによりプロセス制御ブロツク及び
セマフオで待つている行列のセマフオに他の処理
ユニツトがアクセスすることが禁止される。

同様にフリツプフロツプ（HG）２７−２は、
格納されている基準テーブルを更新する或る操作
がなされたことを誤り診断システムに通報するた
めに「１」にセツトされる（ブロツク2006）。ブ
ロツク2007では実行準備状態にあるプロセスの待
ち行列中において停止したプロセスに対応するプ
ロセスリンクの更新を実行する。この更新は、対
応のリンクのビツトＲを「０」にすることに存す
る（ブロツク2008）。ブロツク2008では、処理ユ
ニツトに対応するCPSTTテーブルのCPST領域
において、処理ユニツトが「あき」になつている
というEXEC機能を指示することにより、その
CPSTTテーブルの更新を行う。CPSTTテーブ
ルの更新がなされたら、フリツプフロツプ
（HG）２７−２は「０」にリセツトされ（ブロ
ツク2010）、フリツプフロツプ（SPLK）２７も
「０」にリセツトされ（ブロツク2011）、マイクロ
プログラムは第８Ｂ図で「３」の段階に移行す
る。ブロツク2001に戻り、試験により処理ユニツ
トが「あき」の状態にあることが示されたら、前
の各段階は実行されず、マイクロプログラムは第
８Ｂ図の「３」に進行する。実行されるべく選択
されたプロセスに対応するプロセスリンクはブロ
ツク2012、2013において記憶装置（MMU）１中
にて探され、処理ユニツトの作業レジスターの１
つに格納される。

リンクのビツトＲはブロツク2014において試験
される。ビツトＲが１である場合、見出されたリ
ンクに対応するプロセスは処理ユニツトにおいて
実行中であり、EXEC操作は継続され得ない。そ
れに反し、ビツトＲが「０」ならば、リンクのビ
ツトＤについて試験が行なわれる（ブロツク
2016）。ビツトＤが１ならば、選択された新しい
プロセスの開始に必要なパラメーターは、ブロツ
ク2017において処理ユニツトの各レジスターに格
納されるが、ビツトＤが「０」ならば、選択され
たプロセスは、待機中か又は中止されたかの２つ
の状態のどちらかである。この場合マイクロプロ
グラムは第８Ｃ図の点４に移り、その処理ユニツ
トは「あき」になる。ブロツク2017が終了した
時、フリツプフロツプ（SPLK）２７は試験され
「１」にセツトされる。試験の結果が「０」で、
今開始されたプロセスに対応するプロセス制御ブ
ロツクPCBの状態語に、そのプロセスが実行状
態になつたことを示すために、フリツプフロツプ
（HG）２７−２が１にセツトされたら、ビツト
Ｒを「１」とし、ビツトＤを「０」とし、そのプ
ロセスが開始されたところの処理ユニツトの番号
を領域RHUに書込むことによつて、第５図にお
ける待ち行列中の対応リンクを更新する。同様に
EXEC機能を実行している処理ユニツトに対応す
るCPST語に「使用中」表示を入れることによ
り、処理ユニツトのCPSTTテーブルがブロツク
2021において更新される。更新操作が終了したら
フリツプフロツプHG２７−２及びSPLK２７は
ブロツク2022、2023において「０」にリセツトさ
れる。EXEC操作はブロツク2025においてカウン
ター（EXEC）２９を１減分することにより終了
する。

以上に説明した装置部分及びマイクロプログラ
ムは本発明の単なる例示であり、本発明の範囲内
でその他のいろいろの変形が可能なことは言うま
でもない。

【図面の簡単な説明】

第１図は本発明によるデータ処理装置の構成
図、第２図はプロセス制御ブロツクのフオーマツ
トを示す説明図、第３Ａ図、第３Ｂ図はプロセス
を別々の処理ユニツトに割付け得るように各々の
処理ユニツトが有すべき要素部分を示す回路図、
第３Ｃ図はプロセスを別々の処理ユニツトに割当
てるため記憶制御ユニツトに配設される要素部分
を示す回路図、第４図は主記憶装置中に記憶され
た処理ユニツトの状態のテーブル要素のフオーマ
ツトを示す説明図、第５図は実行準備状態にある
プロセスの待ち行列の主記憶装置内での構成を示
す説明図、第６図は実行準備状態にあるプロセス
のリンクを可能にするプロセスリンクのフオーマ
ツトの説明図、第７Ａ図と第７Ｂ図は「選択」操
作を実行するために用いるマイクロプログラムの
展開を示すフローチヤート、第８Ａ図ないし第８
Ｃ図はEXEC操作を実行するために用いられるマ
イクロプログラムの展開を示すフローチヤートで
ある。１……主記憶装置、２……記憶制御ユニツト、
３……母線、４，６，８……中央処理ユニツト、
５，７，９……入出力制御装置。

Claims

【特許請求の範囲】１いくつかの個々の処理ユニツト（CPU）と、
伝送チヤンネルもしくは母線３の系統を介して前
記各処理ユニツトが接続され得る少なくとも１つ
の記憶装置（MMU）と、該記憶装置に１つの処
理ユニツトを選択的に接続するように前記母線と
関連した手段（MCU）と、デイスパツチングを
行う手段、すなわちいくつかの処理ユニツト
（CPUi）間で履行するようプロセス（JP）の候
補を割付ける手段とを備えたデータ処理装置にお
いて、候補プロセスの処理ユニツトへの前記履行は、
選択された処理ユニツト（CPUi）へのプロセス
の割付けを決定する選択段階（SELECT）、及び
前記選択された処理ユニツト（CPUi）の各々が、
その割付けられたプロセスに関するデイスパツチ
ング動作の残りを実行する実行段階（EXEC）、
の２つの段階で行なわれ、１つ以上の処理ユニツトが、前記選択段階
（SELECT）を実行するための処理手段１５を備
え、該処理手段１５は、第１のインジケータ
（CONTEST）の値に応答して前記選択段階
（SELECT）を実行するよう付勢され、前記第１
のインジケータ（CONTEST）は、デイスパツ
チング状態が現れたいずれの処理ユニツトによつ
ても第１の所定の値にセツトされ、前記データ処理装置は、前記実行段階
（EXEC）をさらに実行する処理ユニツトの数を
示すシステム・カウント（ΣEXECi）を備え、前記データ処理装置は、第２のシステム・イン
ジケータ（SPLK）を備え、前記処理手段１５を備えた処理ユニツトは、以
下に述べる条件：前記第１のインジケータ（CONTEST）が前
記第１の所定の値を有すること；前記第２のインジケータ（SPLK）が第１の所
定の値を有すること、この場合、該第２のインジ
ケータ（SPLK）は前記処理ユニツトによつて第
２の所定の値にセツトされる；いずれの処理ユニツトも実行段階（EXEC）を
実行していないということを前記システム・カウ
ント（ΣEXECi）の値が示していること；が満たされたならば前記選択段階（SELECT）
を実行することを許容され、この場合、前記第１のインジケータ
（CONTEST）は第２の所定の値にリセツトさ
れ、そして前記第２のインジケータ（SPLK）
は、前記許容された処理ユニツトにより前記選択
段階（SELECT）の実行の終わりで前記第１の
所定の値にリセツトされることを特徴とするデー
タ処理装置。２前記許容された処理ユニツトにより実行され
る前記選択段階（SELECT）の間、前記特定の
プロセス（NJP）が特定の選択された処理ユニ
ツト（CPUi）に割付けられるごとに、前記許容
された処理ユニツトは、前記特定の選択された処
理ユニツト（CPUi）において実行段階（EXEC）
の活性を行い、この場合、前記カウント
（ΣEXECi）は１だけ増分され（ステツプ1018、
第７Ｂ図）そしていずれかの特定の選択された処理ユニツトがそ
の実行段階（EXEC）を終了するごとに、前記カ
ウント（ΣEXECi）が１だけ減分される特許請求の範囲第１項記載のデータ処理装置。３プロセスの処理ユニツトへの前記割付けは、
各プロセスの状態（Ｒ、第６図）及び優先順位
（PRI、第６図）に従つて、かつ各処理ユニツト
の状態（CPST、第４図）に従つて決定される特
許請求の範囲第１項または第２項記載のデータ処
理装置。４前記第１のインジケータ（CONTEST）は、
いずれかのプロセスの状態変化もしくはいずれか
の処理ユニツトの状態変化を生じる何等かの動作
に応答して前記第１の所定の値にセツトされる特
許請求の範囲第１項乃至第３項いずれか記載のデ
ータ処理装置。５各選択された処理ユニツト（CPUi）が、前記選択された処理ユニツトがその実行要求
（EXEC）を受信するすぐ前にプロセス（CJP）
を実行していた場合に（ビジーである場合に）、
そのレジスタの内容（CONTEXT）を記憶装置
（MMU）にセーブするための手段（2003、第８
Ａ図）と、新しく割付けられたプロセス（NJP）を実行
するために必要な情報を該レジスタにロードする
ための手段（2017、第８Ｂ図）と、を備えている特許請求の範囲第１項乃至第４項い
ずれか記載のデータ処理装置。