JPS60169945A - スタツク制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、プロセッサ内に設けられるスタックメモリの
制御を行うスタック制御方式の改良に関する。

〔技術の背景〕

計算機システムにおいては、データ処理途中の演算結果
（動作環境）を一時的に格納しておくのに、メインメモ
リのワークエリアを利用することが行なわれている。一
方、メインメモリと演算結果のやりとりを行なうと、時
間がかかることから、近年プロセッサ内部に高速のスタ
ックメモリをハードウェアとして設け、このスタックメ
モリを利用して演算結果の一時格納を行うハードウェア
スタック機構が採用されている。

〔従来技術と問題点〕

係るハードウェアスタック機構を有する計算機システム
では、第１図に示す様にプロセッサユニット１とメイン
メモリ２とが外部バス３で接続されるとともにプロセッ
サユニット１内にはハード的に設けられたスタックメモ
リ４を備えており、プロセッサユニット１内の演算部等
と内部バスで接続される。

一般に計算機システムでは、複数のプロセス（タスク）
を同時に実行することが行なわれているので、スタック
メモリもこのプロセスに応じて分割使用される。しかし
ながら、従来のスタック制御方式では、第２図に示す如
く、スタックメモリ４が各プロセスに応じてブロックＰ
１〜Ｐ４に分割され、且つ各ブロックとしてプロセスの
大小にかかわらず一定の大きさの領域が割当てられてお
り、そしてスタック制御部５は演算部等の指定に応じて
スタックポインタ５ｏの示すアドレスにアクセスを行っ
ていた。

このため、非実行中のプロセスに対し割当てられたブロ
ック（例えばＰ２、Ｐ４）の空き領域は、いくら実行中
のプロセスに割当てられたブロック（例えばＰ３）が満
杯になっても使用できないことから、スタックの使用効
率が悪くなるという問題があった。しかも、この様に当
該ブロックが満杯になると、以降そのプロセスのスタッ
ク利用ができなくなるため、そのブロックＰ３の格納内
容をメインメモリ２へ移して（スワツピングと称す）、
そのブロックＰ３を空にして、当該プロセスのスタック
利用を行なわせる必要がある。このため当該プロセスの
実行が中断され、高速処理を阻害するという問題もあっ
た。

一般にスタックメモリの容量は、メインメモリが存在す
ることから、その効率を考え有限なものであることから
、スタックの有効利用が望まれていた。

〔発明の目的〕

本発明の目的は、ハードウェアスタック機構を有する計
算機システムにおいて、複数のプロセスを実行制御する
際にスタックを効率的に利用出来るスタック制御方式を
提供するにある。

〔発明の構成〕

上述の目的の達成のため、本発明は、スタックメモリの
アドレスを示すスタックポインタと、該スタックメモリ
内の各プロセスの占有状況を示すため該プロセスの識別
子情報、占有状況フラグ情報及び該スタックメモリ内の
占有位置情報を格納するテーブルと、該テーブルの情報
に基き該スタックポインタを制御するとともに該テーブ
ルの制御を行なう制御回路とを有し、該テーブル上の指
定されたプロセスに対応する占有位置情報に基き該スタ
ックポインタを制御するとともに該プロセスの実行に伴
ない該テーブルを書替え制御して該スタックメモリのス
タック割当てを可変にすることを特徴とする。

〔発明の実施例〕

以下、本発明を実施例により詳細に説明する。

第３図は本発明の一実施例プロツク図であり、図中、第
２図と同一のものは同一の記号で示してあり、５１は加
減算器であり、スタックポインタレジスタ５０の内容を
加減算するもの、５２ばオア回路であり、スタックポイ
ンタレジスタ５０に加減算器５１の内容又は後述するス
タックポインタ制御部からの開始アドレスをセットする
ためのもの、５３は制御テーブルであり、各プロセスの
スタック占有情報を格納するためのものであり、スタッ
ク占有情報として占有位置情報Ｂ−ＡＤＨ（スタック上
に同一プロセスが連続して存在する場合の基点アドレス
であり、以下基点アドレスと称ｔ）　、Ｐ−ＬＮＧ　（
連続した同一プロセスのスタック上での大きさを示し、
終点を基点からの相対アドレスで示したものであり、以
下長さと称す）と、占有識別子ＩＤ（テーブル上の情報
がどのプロセスのものであるかを示すもの）と、占有状
況フラグＳＦ（プロセスのその占有領域、ロケーション
での状態を示すフラグ）とが格納されている。

ＳＰＣはスタックポインタ制御部であり、スタックポイ
ンタレジスタ５０に開始アドレスを与えるとともに制御
テーブル５３を書替え制御するものであり、以下の５４
〜６０によって構成される。

５４はアダー（加算器）であり、制御テーブル５３から
読出された基点アドレスＢ−ＡＤＲと長さＰ−ＬＮＧと
を加算してスタックポインタレジスタ５０にセントする
開始アドレスを得るもの、５５は比較回路であり、実行
プロセスのスタックポインタレジスタ５０の内容と、ス
タック上の当該実行プロセスの領域の次の領域に割当て
られたテーブル上の基点アドレスＢ−ＡＤＲとを比較し
て当該プロセスのスタック上の使用領域がフル（満杯）
になったかを検出するもの、５６はカウンタレジスタで
あり、プロセスの実行時に制御テーブル５３上の長さＰ
−ＬＮＧがセットされ、長さＰ−ＬＮＧをスタックポイ
ンタレジスタ５０の内容の変化と同期して変化させたも
のを保持しておくもの、５７は加減算器であり、カウン
タレジスタ５６の内容を加減算器５１の動作に応じて加
減算するもの、５８はオア回路であり、カウンタレジス
タ５６に制御テーブル５３の長さＰ−ＬＮＧ又は加減算
器５７の出力をセントするためのもの、５９は零検出器
であり、カウンタレジスタ５６の内容が零（即ち、プロ
セスの占有解除）となったことを検出するためのもの、
６０はテーブル制御部であり、図示しない演算部等の指
定プロセスに応じ、制御テーブル５３上の対応するスタ
ック占有情報を検索し、更に比較回路５５のフル信号に
応じ新たなスタック上の領域を割当てるため制御テーブ
ル５３を書替え、零検出器５９のゼロ信号に応じスタッ
ク上のそのプロセスに割当てられた領域の占有を解除す
るため制御テーブル５３を書替えるためのものである。

ＡＤＣはアドレス制御部であり、スタックポインタ制御
部ｓｐｃのテーブル制御部６０の指示に応じて制御テー
ブル５３をアクセスするものであり、制御テーブル５３
のためのアドレスカウンタと、リード（Ｒｅａｄ）　／
ライト（Ｗｒｉｔｅ）指示回路とを含むものである。

次に第３図実施例構成の動作について第４図乃至第６図
によって説明する。

第４図は占有状況フラグＳＦとスタック上での状態を示
す関係図であり、ステータス＝０の時、即ち５Ｆ＝Ｏの
時には、第４図（Ａ）に示す如くスタック４内のその領
域（ロケーション）が空き領域（未使用）となっている
ことを示し、ステータス＝１の時、即ち５Ｆ＝１の時に
は、第４図（Ｂ）に示す如くスタック４内のそのロケー
ションにプロセスが存在して使用されており、且つスタ
ック上での先頭のロケーションでないことを示し、ステ
ータス＝２の時、即ち５Ｆ＝２の時には、第４図（Ｃ）
に示す如くスタック４内のそのロケーションにプロセス
が存在して使用されており且つスタック上での先頭のロ
ケーションであることを示す。

次に第５図及び第６図の制御テーブル遷移図に従って第
３図構成の動作を説明する。

■演算部における実行プロセスが切換わると、その指定
プロセスがスタックポインタ制御部ＳＰＣに与えられる
。これに応じてテーブル制御部６０はアドレス制御部Ａ
ＤＣを動作せしめ、制御テーブル５３上の状況フラグＳ
Ｆ及び占有識別子ＩＤを順次読み出し、指定プロセスに
対応するスタック上の領域の有無を判定する。

■スタック上で該プロセスが初めて起動される時は、そ
のプロセスのスタック上のロケーションを確保するため
、テーブル制御部６０は再度制御テーブル５３の状況フ
ラグＳＦを読み出し、第５図（Ａ）の如く、５Ｆ＝２、
即ちスタックの先頭（Ｐ　ｋ）を見つけ、スタックの先
頭の状況フラグＳＦを２”から“１”へ書替え、更に先
頭であったエリアｐｋの次のエリアの状況フラグＳＦを
“２”とし、占有識別子ＩＤを当該プロセスであるＰＮ
に書替える。更に当該プロセスＰｊ！のスタック上の基
点ＢＰβをスタ・ツク上の前のロケーションの最終アド
レスよりめる。即ち、前のロケーションの最終アドレス
は（ＢＰｋ＋ＬＰｋ’）であるので、アダー５４でこれ
をめ、選択回路５２を介しスタックポインタレジスタ５
（Ｈこ初期設定した後、スタックポインタレジスタ５０
の内容（即ち、ＢＰＩ２）を制御テーブル５３のＩＤ＝
ＰＩ２に対応するＢ−ＡＤＲ欄に書込み、一方、文１応
するｐ−ｔ、Ｎｃ＋ｌａにはカウンタレジスタ５６の内
容゛Ｏ”を書込む。これによらてスタ・ツク上Ｇこおい
てプ１コセスＰｌのロケーションが確保されたことにな
る。

■一方、スタック上で該プロセスが起動されたことがあ
り係るプロセスにより占有された領域力（有る場合は、
テーブル制御部６０は、制御テーフ゛ル５３上のＩＤ欄
がＰｌに対応するＢ−ＡＤＨ欄の内容ＢＰβ、Ｐ−ＬＮ
Ｇ欄の内容ＬＰＪを読み出し、アダー５４に与え（ＵＰ
Ｉ！、＋ＬＰｌの加算を行い、開始アドレスとしてスタ
ックポインタレジスタ５０にセントし、且つカウンタレ
ジスタ５６にＬＰｊ２をセットする。

■この様にして、スタックポインタレジスタ５０に（Ｂ
Ｐｊｌ＋ＬＰ６）及びカウンタレジスタ５６にＬＰβに
セントされた後、更に演算部等からのり一ド／ライト命
令毎に加減算器５１．５７が同期動作し、スタックポイ
ンタレジスタ５０の内容及びカウンタレジスタ５６の内
容を加減算してスタックポインタレジスタ５０及びカウ
ンタレジスタ５６にセントする。従ってスタックポイン
タレジスタ５０にはスタック４上の絶対アドレスがカウ
ンタレジスタ５６にはスタック４上の基点アドレスＢＰ
ｌからの相対アドレスが保持されることになる。スタッ
クポインタレジスタ５０の内容によってスタック４がア
クセスされるので、そのアドレスヘッドのり一ド／ライ
トが可能となる。

一方、加減算器５１．５７はリード時には減算を行いス
タック上の使用ロケーションを縮め、ライト時には加算
を行い、スタック上の使用ロケーションを伸ばす。

この様にして、プロセスＰｇの制御が終了し別のプロセ
スに切換わると、第５図（Ｂ）に示す如く、テーブル制
御部６０はアドレス制御部ＡＤＣに書込み１行来を行い
、カウンタレジスタ５６の内容ＰＡ’を当該プロセスの
ための制御テーブル５３上のＰ−ＬＮＧ欄に書込む。

■この様にプロセスＰＡによるスタックメモリ４の使用
中に、テーブル制御部６０は実行中のブＩ：ＪセスＰＩ
！、のロケーションの次のロケーションの基点アドレス
（例えばＩ３Ｐｍ）をアドレス制御部へ〇Ｃを介し読出
し、比較回路５５でスタックポインタレジスタ５０の内
容と比較せしめる。この比較は、プロセスＰｌがスタッ
クメモリ４上の現在使用中のロケーションを使いきった
か否かを判定するためのものであり、次のロケーション
の基点アドレスとスタックポインタ５０の内容とが一致
すると、使用中のロケーションを使いきったことになる
。この様に使用中のロケーションを使ｔｌ）きり、更に
プロセスＰβのスタックが伸びる場合には、スタック上
の使用可能な新たなロケーションを確保しなければなら
ない。そこで、比較回路５５から前述の一致によりフル
信号が発生すると、テーブル制御部６０はアドレス制御
部ＡＤＣを介してカウンタレジスタ５６の内容を制御テ
ーブル５３のＩＤ欄がＰｊ２に対応するＰ−ＬＮＧ欄に
書込む。

次に、テーブル制御部６０は、アドレス制御部ＡＤＣを
介し制御テーブル５３の５Ｆｌｌｉｉをサーチする。こ
れによって第６図（Ａ）の如（，５Ｆ＝０のロケーショ
ンを発見したら、そこは空きロケーションであるから、
制御テーブル５３上の対応するＩＤ１ｌｉにプロセスＰ
ｊ！を且つＳＦ欄を５Ｆ＝１にテーブル制御部６０がア
ドレス制御部ＡＤＣを制御して冑・込み、ロケーション
を確保する。

そして、プロセスＰｊ！の実行を行なうため、当該Ｂ−
ＡＤＲ欄の内容（ＢＰｘ）とＰ−ＬＮＧ欄の内容（ＬＰ
ｘ＝０）との和をアダー５４よりスタックポインタレジ
スタ５０に、Ｐ−ＬＮ（Ｊｌの内容をカウンタレジスタ
５６に設定し、プロセスの実行を継続する。

■一方、前述の制御テーブル５３のＳＦ欄のサーチによ
って５Ｆ＝Ｏのロケーションを発見できなかった場合に
は、５Ｆ＝２即ちスタックの先頭の１」ケージジノを見
つける。このことはスタックの先頭まで空きロケーショ
ンがなかったことになる。そこで、スタックの先頭にプ
ロセスＰＩｌのための新しいロケーションを生成する。

第６図（Ｂ）に示す如くテーブル制御部６０がＩＤ欄Ｐ
ｚで５Ｆ＝２を発見したとすると、先づアドレス制御部
ＡＤＣを介し制御テーブル５３の■ＤＩＩｉｌＰｚの５
Ｆｌｌｉを５Ｆ＝１にし、更に次のエリアのＳＦ欄を５
Ｆ＝２、ＩＤ欄をＩＤ−Ｐｊ！とする。更に当該プロセ
スＰβのスタック上の基点ＢＰ４を、スタック上の前の
ロケーションの最終アドレスよりめる。即ち、前のロケ
ーションの最終アドレスは（１３Ｐｚ＋ＬＰｚ）である
ので、アダー５４でこれをめ、選択回路５２を介しスタ
ンクボインタレジスタ５０に初期設定した後、スタック
ポインタレジスタ５０の内容（即ち、ＢＦ２り・を制御
テーブル５３のＩＤ＝Ｐｊ２に対応するＢ−へＤＲ欄に
書込み、一方、対応するＰ−ＬＮＣ欄にはカウンタレジ
スタ５６の内容“Ｏ″を書込む。これによってスタック
の先頭においてプロセスＰｌの新たなロケーションが確
保されたことになる。

そして、前述のスタックポインタレジろ夕５０及びカウ
ンタレジスタ５６の設定によって、プロセスの実行が継
続される。

■逆に、プロセスＰｌによるスタックメモリ４の使用中
に、スタックの縮みを零検出器５９で検出している。即
ち、零検出器５９はカウンタレジスタ５６が零になった
か否かを検出しており、カウンタレジスタ５６の内容が
零になると当該ロケーション内でプロセスが存在しなく
なったことになる。零検出器５９はこれを検出するとゼ
ロ信号をテーブル制御部６０へ与え、占有解除処理を行
なわしめる。即ち、第６図（Ｃ）に示す如く、制御テー
ブル５３の当該ロケーションの５Ｆｔｉ＋をｓ　Ｆ＝ｏ
とし、更にＰ−ＬＮＣ欄を０″と書替える様テーブル制
御部６０がアドレス制御部ＡＤＣを介して制御する。

更に当該プロセスＰｌの実行でスタックが縮む場合には
、テーブル制御部６０ばアドレス制御部ＡＤＣを介し制
御テーブル５３のＩＤ欄、ＳＦ欄を９・−チし、５Ｆ＝
１で且つＩ　Ｄ＝Ｐ　Ｉ！の同一プ１コセスＰＲに対す
るロケーションを見付ける。そして、前述の場合と同様
にスタックポインタレジスタ５０に当該Ｂ−ＡＤＲ欄Ｂ
ＰｌとＰ−ＬＮＣ；４５］　Ｌ　Ｐ　１と和（アダー５
４の出力）を、カウンタレジスタ５６にＬＰβを設定し
、当該プロセスＰρの実行をＩＩＩ続する。

この様にして制御テーブル５３の占有情報に基きスタッ
クポインタを制御するとともに占有情報を古替えること
によりスタック上の各プロセスの割当てロケーションを
可変にすることが可能となる。

以上本発明を一実施例にり説明したが、本発明は本発明
の主旨に従い種々の変形が可能であり、本発明からこれ
らを排除するもので６よなｌ、）。

〔発明の効果〕

以上説明した様に、本発明によれば、スタ・ツクメモリ
のアドレスを示すスタ・ツクポインタと、該スタックメ
モリ内の各プロセスの占有状況を示１−ため該プロセス
の識別子情報、占有状況フラク゛１青報及び該スタ・ツ
クメモリ内の占有位置情報を格納するテーブルと、該テ
ーブルの情報Ｇこ基き該スタックポインタを制御すると
ともに該テーブルの制御を行なう制御回路とを有し、該
テーブル上の１′行定されたプロセスに対応する占有位
置情報に基き該スタックポインタを制御するとともに該
プロセスの実行に伴ない該テーブルを書替え制御して該
スタックメモリのツク・ツク割当てを可変にすることを
特徴としているので、プロセスに対するスタックメモリ
上の割当て領域がプロセスの実行に伴ない可変にするこ
とができるという効果を奏するので、スタックメモリを
効率的しこ利用出来る。また、プロセスに対する使用エ
リアが不足してスワツピングしなければならない場合が
減少するとし）う効果も奏し、スタ・ツクメモリを設け
た高速イヒの利点を−Ｍ高めることもできる。

更に、テーブルの書替えによって実行してし）るので、
容易にしかも簡単に実現できるとも）う効果も奏する。

【図面の簡単な説明】

第１図は、ハードウエアスタ・ツク機構を有″４−る８
１算機システム構成図、第２図は従来のスタ・ツク制御
方式構成図、第３図は本発明の一実Ｔｉ缶伊１構成図、
第４図は第３図構成における占有１犬況フラク゛、とス
タック上での状態を示す関係図、第５図及び第６図は第
３図構成におけるテーブルの内容遷移図である。 図中、１−プロセツサユ二ット、４−・スタ・ツクメモ
リ、５−スタック制御部、５０−・−スタ・ツクポイン
タレシス外５３−制御テーフ゛ル、ｓ　ｐ　ｃ−・・ス
タックポインク制御部、ＡＤＣ・・・−アドレス制御部
。 特許出願人　富士通株式会社 代理人弁理士　山　谷　晧　榮 第　１　図 第　２　閏 第　４　図 （Ａ）　（Ｕ　（ｃ） ＳＦ璽Ｑ　５Ｆ＝ｊ　ＳＦζ２ 第　５　図 （Ａ） 第　６　目 （Ａ） （Ｃ）

Claims (1)

【特許請求の範囲】
1. スタックメモリのアドレスを示すスタックポインタと、
   該スタックメモリ内の各プロセスの占有状況を示すため
   該プロセスの識別子情報、占有状況フラグ情報及び該ス
   タックメモリ内の占有位置情報を格納するテーブルと、
   該テーブルの情報に基き該スタックポインタを制御する
   とともに該テーブルの制御を行なう制御回路とを有し、
   該テーブル上の指定されたプロセスに対応する占有位置
   情報に基き該スタックポインタを制御するとともに該プ
   ロセスの実行に伴ない該テーブルを書替え制御して該ス
   タックメモリのスタック割当てを可変にすることを特徴
   とするスタック制御方式。