(57)【特許請求の範囲】
【請求項１】
不正アドレスへのアクセスを防止するメモリ保護機能を有するＯＳの管理下で、複数のユーザプログラムが処理されるシングルプロセッサのコンピュータにおいて、
前記ＯＳのカーネルが、
一のユーザプログラムに制御を移すときに、所定の定数を所定のレジスタに設定し、
前記一のユーザプログラムが前記所定の定数が示すアドレスにアクセスすると、前記メモリ保護機能を利用して例外処理を検出し、
前記例外処理が検出されたとき、前記一のユーザプログラムのアトミック性を必要とするプロセスの先頭に処理を戻す、各手順を実行させている、
コンピュータ。
【請求項２】
請求項１に記載のコンピュータにおいて、
前記所定のレジスタは、ユーザプログラムからもアクセス可能である、コンピュータ。
【請求項３】
請求項１に記載のコンピュータにおいて、
前記各手順により、システムコールを必要としないテストアンドセット命令が実現される、コンピュータ。
【請求項４】
不正アドレスへのアクセスを防止するメモリ保護機能を有するＯＳの管理下で、複数のユーザプログラムが処理されるシングルプロセッサのコンピュータに組み込まれたＯＳであって、
前記コンピュータに、
一のユーザプログラムに制御を移すときに、所定の定数を所定のレジスタに設定し、
前記一のユーザプログラムが前記所定の定数が示すアドレスにアクセスすると、前記メモリ保護機能を利用して例外処理を検出し、
前記例外処理が検出されたとき、前記一のユーザプログラムのアトミック性を必要とするプロセスの先頭に処理を戻す、各手順を実行させる、ＯＳ。
【請求項５】
請求項４に記載のコンピュータに組み込まれたＯＳにおいて、
前記所定のレジスタは、ユーザプログラムからもアクセス可能である、ＯＳ。
【請求項６】
請求項４に記載のコンピュータに組み込まれたＯＳにおいて、
前記各手順により、システムコールを必要としないテストアンドセット命令が実現される、ＯＳ。
【請求項７】
請求項４〜６のいずれか一項記載のＯＳが記録された記録媒体。
【請求項８】
不正アドレスへのアクセスを防止するメモリ保護機能を有するＯＳの管理下で、複数のユーザプログラムが処理されるシングルプロセッサのコンピュータにおける前記ＯＳのカーネルの制御方法において、
一のユーザプログラムに制御を移すときに、所定の定数を所定のレジスタに設定し、
前記一のユーザプログラムが前記所定の定数が示すアドレスにアクセスすると、前記メモリ保護機能を利用して例外処理を検出し、
前記例外処理が検出されたとき、前記一のユーザプログラムのアトミック性を必要とするプロセスの先頭に処理を戻す、各手順を含む、制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ、その制御方法及びその制御方法を記録した記録媒体に関する。
【０００２】
【発明の背景】
コンピュータには、大別して、単一の処理装置で単一のジョブ（ユーザプログラム）を実行するシングルプロセッサ−シングルタスク・システムと、単一の処理装置で複数のジョブを実行するシングルプロセッサ−マルチタスク・システムと、複数の処理装置で複数のジョブを実行するマルチプロセッサ−マルチタスク・システムとが知られている。
【０００３】
この内、マルチプロセッサ・システムは、一般に、複数のプロセッサが複数のジョブを、夫々独立して並行処理を行っている。
【０００４】
一方、シングルプロセッサ−マルチタスク・システムでは、通常、複数のジョブ（ユーザプログラム）を見かけ上、同時に実行している。
【０００５】
しかし、プロセッサが単一でありながら処理すべきジョブが複数個有るため、コンピュータ資源の占有に関して競合状態という、不具合が発生する場合がある。
【０００６】
このようなコンピュータにおいては、基本ソフトであるＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）の制御によって、競合状態を回避しながら複数のユーザプログラムが時分割で処理されている。
【０００７】
このようなシングルプロセッサ・システムでは、効率良く安全にユーザプロセスレベルで排他制御を行うために専用命令が用意されている場合もある。しかし、プロセッサの種類によっては、このような専用命令が用意されていない場合が多い。この場合、効率良く且つ安全にユーザプロセスレベルで排他制御を行う手段がなかった。
【０００８】
【課題を解決するための手段】
本発明は、上述の問題点に鑑みて、マルチジョブを処理するシングルプロセッサ・システムにおいて、専用命令なしで、効率良く且つ安全にユーザプロセスレベルで排他制御を実行できる新規なコンピュータ、その制御方法及びその制御方法を記録した記録媒体を提供することを目的とする。
【０００９】
本発明に係るコンピュータは、不正アドレスへのアクセスを防止するメモリ保護機能を有するＯＳの管理下で、複数のユーザプログラムが処理されるシングルプロセッサのコンピュータであって、前記ＯＳのカーネルが、一のユーザプログラムに制御を移すときに、所定の定数を所定のレジスタに設定し、前記一のユーザプログラムが前記所定の定数が示すアドレスにアクセスすると、前記メモリ保護機能を利用して例外処理を検出し、前記例外処理が検出されたとき、前記一のユーザプログラムのアトミック性を必要とするプロセスの先頭に処理を戻す、各手順を実行させている。
【００１０】
上述のコンピュータに於いて、前記所定のレジスタは、ユーザプログラムからもアクセス可能にすることもできる。
【００１１】
上述のコンピュータに於いて、前記各手順により、システムコールを必要としないテストアンドセット命令が実現される。
【００１２】
更に、本発明に係るＯＳは、不正アドレスへのアクセスを防止するメモリ保護機能を有するＯＳの管理下で、複数のユーザプログラムが処理されるシングルプロセッサのコンピュータに組み込まれたＯＳであって、前記コンピュータに、一のユーザプログラムに制御を移すときに、所定の定数を所定のレジスタに設定し、前記一のユーザプログラムが前記所定の定数が示すアドレスにアクセスすると、前記メモリ保護機能を利用して例外処理を検出し、前記例外処理が検出されたとき、前記一のユーザプログラムのアトミック性を必要とするプロセスの先頭に処理を戻す、各手順を実行させる。
【００１３】
更に、上述のコンピュータに組み込まれたＯＳにおいて、前記所定のレジスタは、ユーザプログラムからもアクセス可能にすることもできる。
【００１４】
更に、上述のコンピュータに組み込まれたＯＳにおいて、前記各手順により、システムコールを必要としないテストアンドセット命令が実現をすることもできる。
【００１５】
更に、本発明に係る記録媒体は、上述のＯＳが記録された記録媒体である。
【００１６】
更に、本発明に係るＯＳのカーネルの制御方法は、不正アドレスへのアクセスを防止するメモリ保護機能を有するＯＳの管理下で、複数のユーザプログラムが処理されるシングルプロセッサのコンピュータにおける前記ＯＳのカーネルの制御方法であって、一のユーザプログラムに制御を移すときに、所定の定数を所定のレジスタに設定し、前記一のユーザプログラムが前記所定の定数が示すアドレスにアクセスすると、前記メモリ保護機能を利用して例外処理を検出し、前記例外処理が検出されたとき、前記一のユーザプログラムのアトミック性を必要とするプロセスの先頭に処理を戻す、各手順を含む。
【００３４】
【発明の実施の形態】
最初に、本発明が実施される際に対象となるコンピュータについて説明する。
【００３５】
図１に示すように、本発明が実施される際に対象となるコンピュータは、少なくともＣＰＵ１と、メモリ２と、入力装置３と、出力装置４とを備えている。ここで、このＣＰＵ１は、少なくとも特権モード（「カーネルモード」ともいう。）及び非特権モード（「ユーザモード」ともいう。）の機能と、メモリ管理機構（論理アドレスから物理アドレスヘの変換機能，メモリ保護機能等）とを備えている。
【００３６】
ここで、「特権モード」とは、次に説明するオペレーティングシステムの実行において、通常のユーザプログラムの中では使用できないような、特別なハードウェア資源の制御操作（制御命令，特権命令）でコンピュータが動作している状態をいう。
【００３７】
「メモリ管理機構」は、メモリ２を管理する機構のことであり、アドレス変換機能，メモリ保護機能等をもっている。アドレス変換機能は、論理アドレス空間と物理アドレス空間の対応付けを行う。メモリ保護機能は、例えば、ＯＳが使用している領域をユーザが誤って使用しないように、メモリ領域をシステム領域（ＯＳ用）とユーザ領域（ユーザ用）に予め分けて設定しておき、ユーザが実行中にシステム領域に対してアクセスしてしまった場合にエラ−検出を行う機能である。このため、メモリ保護機能は、各メモリ領域に対して、実行可能か否か、書き込み可能か否か等の属性を設定している。
【００３８】
次に、上記コンピュータに使用されるＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）５について説明する。図２に示すように、ＯＳ５は、少なくとも、カーネル６，ユーザインターフェース等からを有し、プログラムの読み込み・実行、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ），メモリ，外部周辺機器等のようなコンピュータ資源の管理等を行う基本ソフトをいう。本発明で対象となるＯＳ５は、プリエンプティブ・スケジューリング（ｐｒｅｅｍｐｔｉｖｅ  ｓｃｈｅｄｕｌｉｎｇ）による多重プロセスの実行機能とプロセス間のメモリ保護機能とを持っている。プリエンプティブ・スケジューリングは、次にどのユーザプロセスを動かす（選択・実行）かを決定する際に、各ユーザプロセスが能動的に切り替え（コンテキストスイッチ）を行うだけでなく、タイマ割り込み等を用いて受動的にも行うことをいう。
【００３９】
図３に示すように、この様なＯＳ５の上では、各ユーザプログラムは、同時に複数存在して、見かけ上は同時に実行される。言い換えると、ＯＳ５は、各ユーザプログラムに対して、ＣＰＵ１，メモリ，ＨＤＤといったコンピュータ資源をあたかも同時に占有しているかのように見せている。
【００４０】
ＯＳ５の核となる部分は、カーネル６と呼ばれる。カーネル６は、主に、接続されたハードウェア資源の動作，各ユーザプログラムの実行等を管理する。カーネル６は、ＣＰＵ１の特権モード（カーネルモード）で実行される。これに対して、各ユーザプログラムの実行は、ＣＰＵ１の非特権モード（ユーザモード）で行われ、各資源の直接的な操作は制限される。資源や操作の種類により、一層多くの特権モードを設けることもある。
【００４１】
各ユーザプログラムの実行単位は、ユーザプロセスと呼ばれる。各ユーザプロセスは、メモリなどの資源の確保・解放、入出力装置３，４とのやりとりを、カーネル６を介して行う。カーネル６に対するサービス要求は、システムコール（ｓｙｓｔｅｍ  ｃａｌｌ）と呼ばれる。カーネル６は、このほかに外部デバイスからの入出力や割り込みに対する処理、各ユーザプロセス間の制御の切り替え等を行っている。
【００４２】
ユーザプログラムからのシステムコールにより、ユーザプロセスは、ユーザモードからカーネルモードに能動的に遷移する。この遷移は、外部デバイスからの割り込みでも発生する。
【００４３】
カーネル６は、見かけ上ユーザプロセスを同時に複数実行するため、刻々と各ユーザプロセスの実行状態を記録している。この実行中の状態（即ち、ユーザ用ＣＰＵレジスタ，仮想記憶の状態等）を、コンテキスト（ｃｏｎｔｅｘｔ）と呼ぶ。そして、この実行状態の切り替えをコンテキストスイッチ（ｃｏｎｔｅｘｔ  ｓｗｉｔｃｈ）と呼ぶ。通常、コンテキストスイッチは、ユーザプログラムからのシステムコールをきっかけに行われる。この際、カーネル６が、次にどのユーザプロセスを動かすかを決めることをスケジューリング（ｓｃｈｅｄｕｌｉｎｇ）と呼ぶ。
【００４４】
上述したように、ＣＰＵ１のメモリ管理機構は、論理アドレスを物理アドレスに変換する機能をもっていて、プログラムが用いる論理アドレスを実際に存在するメモリの物理アドレスへマップ（対応付け）する。また、メモリ保護機能によって、各メモリ領域に実行可能か、書き込み可能かなどの属性を設定できる。
【００４５】
このメモリ管理機構を利用して、カーネル６は、各々のユーザプロセスがユーザ空間を占有しているように見せている。即ち、各ユーザプロセスは、独立したユーザ空間を持っているかのように動作し、他方のユーザプロセスのユーザ空間へのアクセスはできない。
【００４６】
しかし、このままでは複数のユーザプロセスが相互に通信しながら仕事を進めるときに不便が生じる。そのため、カーネル６は、メモリ空間の一部に対して、各ユーザプロセス間で共有することができる機能を提供している。この様な空間は、共有メモリと呼ばれる。
【００４７】
ＣＰＵ１のメモリ管理機構により、カーネル６は、ユーザプロセスの読出し専用メモリヘの書き込み，存在しないメモリ空間ヘのアクセス等を検出して、例外処理（ｅｘｃｅｐｔｉｏｎ  ｈａｎｄｌｉｎｇ）へ制御を移すことができる。この例外処理は、カーネル６内で行われ、カーネル６は、通常そのプロセスを異常終了等させる。
【００４８】
更に、ＭＩＰＳ  ＣＰＵのレジスタについて説明する。
【００４９】
本実施例では、ＣＰＵ１は、ＭＩＰＳ  ＣＰＵを使用している。ＭＩＰＳ  ＣＰＵは、ＭＩＰＳテクノロジーズが開発したＲＩＳＣ型ＣＰＵをいう。本発明で使用されるＭＩＰＳ  ＣＰＵは、複数個、例えば３２個の汎用レジスタを持っている。汎用レジスタであるため、スタックポインタ専用レジスタ，メモリアドレス専用レジスタ等のような用途別のレジスタはない。各々のレジスタは、ハードウェア的には、レジスタ番号０（名称ｚｅｒｏ）からは常に０が読めることを除き、全く等価である。
【００５０】
しかし、ユーザは、ソフトウェアを作成する際に各レジスタを識別出来ないと困るので、各レジスタの使用方法が決められている。例えば、本実施例では、レジスタ０〜３１の用途を表−１に示すように決定している。
【表１】
0003598282.tif 000002
このようにＭＩＰＳ  ＣＰＵでは、レジスタ番号２６−２７（名称ｋ０，ｋ１）は、用途が「例外処理内で利用」と決められている。従って、例外処理内で利用するレジスタが、ユーザからアクセス出来ることになる。換言すれば、このユーザから見えることとなる。なお、一部上記の利用法を変えた規則もあるが、レジスタ番号２６−２７（名称ｋ０，ｋ１）が、ユーザから見えることに関しては変わらない。
【００５１】
なお、ＭＩＰＳ  ＣＰＵは、プロセッサ自体の制御のためにコプロセッサ０（ＣｏＰｒｏｃｅｓｓｏｒ  ０，以下「ＣＰ０」と略す。）を有している。例外処理が発生すると、ＣＰＵは、例外の要因をＣＰ０の  Ｃａｕｓｅレジスタに、発生場所をＣＰ０のＥＰＣレジスタに記録する。例外処理内では、これらのレジスタを参照して、要因毎に対応する処理を行う。
【００５２】
更に、複数のユーザプロセス間における競合状態（ｒａｃｅ  ｃｏｎｄｉｔｉｏｎ）と相互排他（ｍｕｔｕａｌ  ｅｘｃｌｕｓｉｏｎ）について説明する。
【００５３】
複数のユーザプロセスが共有メモリを読み書きして動作するとき、誰が（どのユーザプロセスが）、何時、どう動いたか（どのような処理を行ったか）によって、最終的な結果が、本来得られるべき結果と異なるということが起こりえる。このような状態は、競合状態と呼ばれる。そして、本来競合してはいけないプログラムの一部分を、クリティカルセクションと呼んでいる。クリティカルセクションヘの進入を制限するため、相互排他の機構が必要となる。相互排他を実行するか否かを決定するために用いられる変数を、排他変数と呼ぶ。
【００５４】
以下に、１つの資源を２つのユーザプロセスが使用する簡単な競合状態と相互変数を、簡易な具体例を挙げて説明する。判り易さのために、１つの試着室を２人で使用する場合を考える。
【００５５】
ここで、ＡさんとＢさんの２人は、プロセスＡ，Ｂを夫々表し、１つの試着室は共有メモリを表している。二人が同時に試着室の使用しては（即ち、競合状態を起こしては）困るから、ＡさんとＢさんの試着室の使用はクリティカルセクションとなる。試着室の使用を相互排他する為に、「空き／使用中」を表示する札を設ける必要がある。従って、この表示札が、排他変数となる。
【００５６】
２人は、ともに以下のような手順で試着室へ入る。ＡさんとＢさんが、次の表に示すように、手順のステップ毎に交互に動作を行ったとする。
【表２】
0003598282.tif 000003
表−２で判るように、時点８では、二人が同時に試着室に入ってしまう状態、即ち競合状態が発生する。
【００５７】
ここで、「表示札を見る」から「表示札を空きから使用中に変える」までの手順（処理）がアトミック（不可分な関係）に行われる場合は、競合状態の発生はなく、問題はない。しかし、アトミックに行われない場合には、競合状態の問題が発生する。なお、ここで、アトミックな処理とは、ひとまとまりの処理として実行される処理群であり、処理群実行中に異常，割り込み等が発生したしたときには、その処理結果を破棄又は保留してしまうことを意味している。
【００５８】
ＣＰＵ１には、このような競合状態を回避するため、手順「表示札を見る」から手順「表示札を空きから使用中に変える」までをアトミック（不可分な関係）に処理する命令が用意されていることが多い。このような命令を、テストアンドセット命令（ｔｅｓｔ  ａｎｄ  ｓｅｔ）と呼んでいる。
【００５９】
Ｌｉｎｕｘ（ＯＳの一つであり、Ｕｎｉｘ（登録商標）の一種）には、システムコールｃｌｏｎｅ（）が用意されている。これは、伝統的なシステムコールｆｏｒｋ（）をプロセス空間を共有するように変更したものである。一般に、Ｌｉｎｕｘシステムに用いられているｇｌｉｂｃ（ＦＳＦ開発の基本ライブラリ）には、このシステムコールを使ったスレッド（ｔｈｒｅａｄ，起動中のタスクから起動できる小さいモジュール）の実装が提供されている（以下、この実装を、「Ｌｉｎｕｘ−ｔｈｒｅａｄ」という）。スレッド間の相互排他の効率的な実装には、ユーザプロセルレベルでの効率的なテストアンドセット命令の実装が必要となる。このため、一般にこれらはＣＰＵ１の命令として提供されている。
【００６０】
具体的に説明する。通常、ＭＩＰＳ  ２  ＩＳＡ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ａｒｃｈｉｔｅｃｔｕｒｅ）以上のＭＩＰＳアーキテクチャでは、アトミックなテストアンドセット命令のために、ｌｌ／ｓｃ命令（ｌｏａｄ−ｌｉｎｋｅｄ／ｓｔｏｒｅ−ｃｏｎｄｉｔｉｏｎａｌ）が用意されている。ｌｌ命令（ｌｏａｄ−ｌｉｎｋｅｄ）でロードした時のアドレスを覚えておき、ｓｃ命令（ｓｔｏｒｅ−ｃｏｎｄｉｔｉｏｎａｌ）を実行する迄の間に、他のＣＰＵ１がこの近傍に書き込みを行った場合又は例外処理（ｅｘｃｅｐｔｉｏｎ  ｈａｎｄｌｉｎｇ）が起きた場合には、ｓｃ命令で書き込みを行わない、というメカニズムをもっている。このｌｌ／ｓｃ命令は、シングルプロセッサ・システムにおいて、Ｌｉｎｕｘの様なオペレーションシステム上で安全なテストアンドセット命令の実装に不可欠なものといえる。
【００６１】
しかし、ＭＩＰＳ  １  ＩＳＡには、このような専用命令は用意されていない。また、組み込み用途に設計されたＭＩＰＳアーキテクチャのＣＰＵには、これらの命令を持たないものもある。本出願人であるＳＣＥＩ（Ｓｏｎｙ  Ｃｏｍｐｕｔｅｒ  Ｅｎｔｅｒｔａｉｎｍｅｎｔ  Ｉｎｃ．）製のＥｍｏｔｉｏｎ  Ｅｎｇｉｎｅと呼ばれるＣＰＵ（以下、「ＥＥ」と称する。）やＶｒ４１００などでは、ｌｌ／ｓｃ命令が省略されている。従って、これらのＣＰＵでは、何らかの手段を用いて、競合状態の発生を回避する必要が生じてくる。
【００６２】
以下、ＥＥ，Ｖｒ４１００及びＭＩＰＳ  １に関して、簡単に説明する。
【００６３】
（１）  Ｖｒ４１００では、ｌｌ／ｓｃ命令のような専用命令は用意されていない。従って、アトミック性が確保されず、複数のユーザプロセスが同時にクリティカルセクションに突入し、競合状態になる（巻末参考資料（１）及び（２）参照）。
【００６４】
（２）ＥＥの例
【００６５】
ＥＥは、ｌｌ／ｓｃ命令が用意されていない代わりに、ｅｉ／ｄｉ命令が用意されている。ｅｉ／ｄｉ命令は、割り込み禁止を禁止／許可するための命令であり、クリティカルセクションの出入口で用いれば、テストアンドセット命令のアトミック性を確保できる（巻末参考資料（３）参照）。
【００６６】
しかし、ユーザレベルでこれらの実行を許可してしまうと、誰もがシステム全体を停止するプログラムを簡単に実行できてしまう。即ち、ｅｉ／ｄｉ命令では、安全に排他制御を行うことが出来ない。このため、ｅｉ／ｄｉ命令をＬｉｎｕｘのような保護されたユーザ環境では、事実上使用できない（巻末参考資料（４）参照）。
【００６７】
（３）  ＭＩＰＳ  １  ＩＳＡ
【００６８】
元々、ＭＩＰＳ  １  ＩＳＡには、ｌｌ／ｓｃ命令が用意されていない。ＭＩＰＳ  １  ＩＳＡ用の相互排他の実装として、
【００６９】
（ａ）  システムコールによるテストアンドセット命令
【００７０】
（ｂ）  Ｌａｍｐｏｒｔアルゴリズムの実装、がある。
【００７１】
しかし、（ａ）のシステムコールによるテストアンドセット命令を用いると、競合しない場合でも、必ず例外処理（ｅｘｃｅｐｔｉｏｎ  ｈａｎｄｌｉｎｇ）とコンテキストスイッチ（ｃｏｎｔｅｘｔ  ｓｗｉｔｃｈ）が起きるという性能上の大きな問題点がある。後述のオーバーヘッドを参照されたい。
【００７２】
一方、（ｂ）  Ｌａｍｐｏｒｔアルゴリズムを実装するには、次のような問題がある（巻末参考資料（５）参照）。
【００７３】
同時に実行されるユーザプロセスの状態を表す変数ｂ［ｉ］を実装するため、同時実行の全てのユーザプロセスが共有するメモリが必要となる。クリティカルセクションに入っていないユーザプロセスでも、終了する際には、ｂ［ｉ］を正しくクリアする必要がある。ＭＩＰＳ  ＡＢＩグループで配布された実装では、この監視のために、デーモン（ｄａｅｍｏｎ）を起動するようになっているが、原理的に異常終了の検出を正しく判断することは出来ないし、検出にも時間がかかることが判明した。
【００７４】
更に、ユーザプロセス側で、変数ｂ［ｉ］の領域を動的に確保しようとすると、本来ＯＳのもつプロセスやスレッド数の制限とは別の制限が出来てしまうことが判明した。
【００７５】
メモリ領域の効率的な利用を考え、ｍｍａｐ（）やｓｈｍｇｅｔ（）のような処理で単一の共通の変数ｂ［ｉ］のための領域をとることもできる。しかし、こうすると、他のプロセスのための変数ｂ［ｉ］を、誰でも書き換えられることになってしまう。これでは、全く無関係の排他変数に対する待ち合わせを妨害出来てしまうことが判明した。
【００７６】
安全に変数ｂ［ｉ］を操作するために、各プロセスからは、読み込み専用として、カーネルを使って書き換えることも考えられるが、こうするとシステムコール（ｓｙｓｔｅｍ  ｃａｌｌ）による実装と同じようなオーバーヘッドが発生してしまうことになる。
【００７７】
ＭＩＰＳ  ＡＢＩグループで配布された実装では、ｘ，ｙ，ｂ［ｉ］の領域を確保し且つアクセス制限を確保するためにＳＹＳＶ  ＩＰＣの共有メモリ機能を利用している。しかし、この共有メモリには、終了時に明示的に共有メモリセグメントを取り除かなくてはいけないという問題点があるため、異常終了の監視をデーモンで行う必要があることが判明した。
【００７８】
また、デフォルトでは、ｇｅｔｅｕｉｄ（）で得られた値をｋｅｙとして、アクセスも自分のｕｉｄに限定しているので、対象とする排他変数の共有もこの範囲に限られる。このことは、この範囲を越えた共有を行いたい場合には、別途、環境変数の設定が必要となり、汎用性に欠けることが判明した。
【００７９】
本発明は、これらの問題点を解決するために、Ｌｉｎｕｘスレッド（ｔｈｒｅａｄ）の実装に必要な一般的で、且つ制限の少ない機能を提供する。この場合、競合の起きない場合のオーバーヘッドを極力少なくし、且つセキュリティホールやシステムの安定度を低くしないことを目標とし、テストアンドセット命令（ｔｅｓｔ  ａｎｄ  ｓｅｔ）の仕組みを実装することとした。
【００８０】
本発明は、ＯＳメモリ保護機能と、カーネル作業用レジスタとを利用して、シングルプロセッサ・システムにおいて、専用のＣＰＵ命令を必要としない安全なユーザレベル排他制御を可能にしている。
【００８１】
例えば、ＥＥには、命令ｌｌ／ｓｃが用意されていないため、カーネル作業用のレジスタと、カーネルが提供するメモリ保護機構を利用して、システムコール（ｓｙｓｔｅｍ  ｃａｌｌ）が不用なテストアンドセット命令を実装した。この実装は、ｌｌ／ｓｃ命令がない、他のシングルプロセッサのＭＩＰＳアーキテクチャＣＰＵに利用することが出来る。
【００８２】
本発明において、対象としているのはシングルプロセッサ・システムなので、現在進行中のオペレーションが他のユーザプロセスに割り込まれなければ、そのオペレーションのユーザプロセスレベルのアトミック性を保証できる。
【００８３】
オペレーションのアトミック性が保証できるということは、
（１）或る区間の一連の操作について、他のユーザプログラムから一度も割り込みなしで実行出来たことを保証すること、又は
（２）たとえ他のユーザプログラムから割り込まれても、割り込まれたことを検出でき且つ或る区間の一連の操作を無効化してやり直しをすること。即ち、他のユーザプロセスからの割り込み検出とオペレーションの無効化とはアトミック状態になっている必要があること、を意味する。
【００８４】
本発明では、（２）他のユーザプログラムから割り込まれても、割り込まれたことを検出でき且つ或る区間の一連の操作を無効化してやり直しをすること、を実現している。
【００８５】
幸いにも、ＭＩＰＳでは、カーネル作業用のレジスタがユーザにも見えるので、本発明では、このレジスタと、カーネルが提供するメモリ保護機能とを利用して、一連の「検出と無効化」によって、必要とされるアトミック性を実現することにした。
【００８６】
更に、検出と無効化によるアトミック性の実現について説明する。
【００８７】
図６は、本発明を容易に理解できるようにするため、一連の「検出と無効化」処理のない従来のシングルプロセッサによるマルチタスク処理を説明するフローチャートである。これに対して、図７は、一連の「検出と無効化」処理による、本発明のシングルプロセッサによるマルチタスク処理を説明するフローチャートである。
【００８８】
図７に示すように、ステップＳ１０で、ユーザプロセス＃１が実行される。ステップＳ１１で、ユーザプロセス＃２から割り込み要求の有無が判定される。割り込み要求有りの場合、ステップＳ１２で、カーネルはスケジューリングを行い、次にどのユーザプロセスを実行するかが決定される。
【００８９】
ユーザプロセス＃２の実行が選択されると、ステップＳ１３で、カーネルにより切替（コンテキストスイッチ）が行われ、ステップ１４で、ユーザプロセス＃２が実行される。
【００９０】
ステップＳ１５で、ユーザプロセス＃１から割り込み要求の有無が判定される。割り込み要求有りの場合、ステップＳ１６で、カーネルはスケジューリングを行い、次にどのユーザプロセスを実行するかが決定される。
【００９１】
ステップＳ１７で、カーネル作業用レジスタに定数ＡＣＣＥＳＳ＿ＭＡＧＩＣが設定され、ついで前ステップでユーザプロセス＃１の実行が選択されると、ステップＳ１８で、カーネルにより切り替え（コンテキストスイッチ）が行われ、ステップＳ１９で、ユーザプロセス＃１が実行される。
【００９２】
ステップ２０で、定数ＡＣＣＥＳＳ＿ＭＡＧＩＣの有無が検出され、有りの場合、アトミック性を必要とする一連の処理が無効化され、ステップＳ１０に戻って、ユーザプロセス＃１が再度実行される。
【００９３】
これに対して、図６の「検出と無効化」処理のない従来のシングルプロセッサによるマルチタスク処理では、図７のステップＳ１７，Ｓ２０，Ｓ２１が無く、定数ＡＣＣＥＳＳ＿ＭＡＧＩＣの設定、検出、処理の無効化が行われない。このため、ステップＳ１０で実行されたユーザプロセス＃１の処理結果と、ステップＳ１４で実行されたユーザプロセス＃２の処理結果とが競合を起こし、その結果、ステップＳ１９で実行されるユーザプロセス＃１の処理に不具合を生じることがある。
【００９４】
以上の状況を実際のアルゴリズムで説明する。
【００９５】
はじめに、ｇｌｉｂｃ（団体ＦＳＦ（Ｆｒｅｅ  Ｓｏｆｔｗａｒｅ  Ｆｏｕｎｄａｔｉｏｎ）で開発したＯＳの基本ライブラリ）のＬｉｎｕｘ  スレッドで必要とされているテストアンドセット命令（ｔｅｓｔ  ａｎｄ  ｓｅｔ；「ｔｓｔ」と表示する。）を用意する。このテストアンドセット命令ｔｓｔは、以下の作業を行う。
【００９６】
引数（ａｄｄｒ）で与えられたアドレスの内容が０なら、１で置き換える。戻り値（ｒｅｔｕｒｎ  ｖａｌｕｅ）は、元のアドレスの内容である。ライブラリは、排他変数の値１を使用中という意味として、
【００９７】
ｗｈｉｌｅ  （ｔｓｔ（ｍｕｔｅｘ＿ｖａｒ））；
【００９８】
クリティカルセクション
【００９９】
ｍｕｔｅｘ＿ｖａｒ＝０；
として利用する。
【０１００】
この手続き内での割り込みを検出して、割り込みが起こった場合には、ｍｕｔｅｘ＿ｖａｒへの書き込みを無効化する。このために、カーネル作業用のレジスタｋ１を用いる。カーネルからユーザプログラムに制御を移すときに必ずｋ１に特定の値（定数）ＡＣＣＥＳＳ＿ＭＡＧＩＣをセットする。このＡＣＣＥＳＳ＿ＭＡＧＩＣのアドレスに、ユーザプログラムがアクセスすると、メモリ保護機能を利用して、無効アドレス空間のアクセス違反割り込み（ｓｅｇｍｅｎｔａｔｉｏｎ  ｖｉｏｌａｔｉｏｎ）が発生するように、この値を決めておく。
【０１０１】
図８は、多重プロセス実行機能を有するシングルプロセンサにおいて、１のユーザプログラムがテストアンドセット命令を実行する一例を示している。このプログラムにおいては、もし競合状態が発生すると、シーケンス（ｌｉ  ｔ０，１）でストアに不具合が発生する。従って、シーケンス（ａ）から（ｂ）迄の一連の処理のアトミック性が保証されることが必要となっている。
【０１０２】
カーネルによる無効アドレス空間のアクセス違反割り込み処理内で、テストアンドセット命令の手続き内でＡＣＣＥＳＳ＿ＭＡＧＩＣアドレスへのアクセス違反となったことを検出した場合、この手続きの先頭へ制御を戻す。こうすることで、シーケンス（ａ）から（ｂ）までに割り込みがあり、ａｄｄｒの内容が０から１へと変化した場合、テストアンドセット命令ｔｓｔがやり直される。この様子を、以下に図９に示す。
【０１０３】
図９は、左半分は図８で説明した、１のユーザプログラムのシーケンス（ＵｓｅｒＰｒｏｃ  ＃１）が記載されている。右半分は、１のユーザプログラムの実行と競合関係を生じる可能性のある他のユーザプログラムのシーケンス（ＵｓｅｒＰｒｏｃ  ＃２）が記載されている。両者間には（中心部には）、ＯＳのカーネルが実行するプリエンプティブ・スケジューリング（ｐｒｅｅｍｐｔｉｖｅ  ｓｃｈｅｄｕｌｉｎｇ）のシーケンスが記載されている。
【０１０４】
１のユーザプログラムのシーケンス（／／ａ０  ｈｏｌｄｓ  ｍｕｔｅｘ＿ａｄｄｒ）によって、アドレスａ０にｍｕｔｅｘ＿ａｄｄｒが書き込まれる。
【０１０５】
他のユーザプログラムのシーケンスを実行するため、タイマ割り込み（ｔｉｍｅｒ  ｉｎｔｒ．）により、処理が切り替わる（ｃｏｎｔｅｘｔ  ｓｗ）。
【０１０６】
しかし、他のユーザプログラムのシーケンスの実行中に、アドレスａ０に書き込まれた内容ｍｕｔｅｘ＿ａｄｄｒが変更される可能性がある。
【０１０７】
再び、１のユーザプログラムのシーケンスを実行するため、タイマ割り込み（ｔｉｍｅｒ  ｉｎｔｒ．）により、処理が切り替わる（ｃｏｎｔｅｘｔ  ｓｗ）。
【０１０８】
このとき、カーネルは、レジスタｋ１に定数ＡＣＣＥＳＳ＿ＭＡＧＩＣを書き込む（ｌｉ  ｋｉ，  ＡＣＣＥＳＳ＿ＭＡＧＩＣ）。
【０１０９】
処理が切り替わり（ｃｏｎｔｅｘｔ  ｓｗ）、シーケンスＮＯＰからＳＷが実行される。
【０１１０】
しかし、その後、カーネルによって、定数ＡＣＣＥＳＳ＿ＭＡＧＩＣの検出（ｃｏｎｆｉｒｍ  ｗｒｉｔｉｎｇ  ｔｏ  ＡＣＣＥＳＳ＿ＭＡＧＩＣ）され、次に、無効化（ｓｅｔ  ｒｅｓｔａｒｔ  ａｄｄｒ  ｔｏ  ｔｓｔ（））が実行される。
【０１１１】
こうして、途中まで実行されていた１のユーザプログラムのシーケンスは、再度実行されることにより、その結果、図８のシーケンス（ａ）〜（ｂ）の一連の処理のアトミック性が保証される。
【０１１２】
シーケンス（ａ）から（ｂ）までの間で、他のプロセスにより、排他変数が０から１へ変化した場合には、このアルゴリズムでなければ変数値が置き換えられてしまう。しかし、このアルゴリズムでは、置き換えが起きない。また、これにより、不用なクリティカルセクションへの突入も起きない。
【０１１３】
ここで、オーバーヘッドに関し、検討する。
【０１１４】
システムコールでテストアンドセット命令を実装した場合には、競合状態が起きない場合でも、常にコンテキストスイッチが発生してしまう（巻末資料（６）参照）。
【０１１５】
一方、今回実装した方法では、競合状態が起きない場合には、単にテストアンドセット命令ｔｓｔ手続きをユーザレベルで実行するだけなので、コンテキストスイッチは発生しない。
【０１１６】
競合状態にある場合には、無効アドレス空間内のアクセス違反割り込み（Ｓｅｇｍｅｎｔａｔｉｏｎ  Ｖｉｏｌａｔｉｏｎ）が発生する。この場合のコストは、システムコールによる実装と大差はない（巻末参考資料（７）参照）。
【０１１７】
一般に、競合状態になることは非常に少ないため、システムコールによる実装と比べてかなり性能が改善される。
【０１１８】
本出願人は、エンタテイメントシステムとしてプレイステーション２を開発した。このエンタテイメントシステムには、ＥＥ（Ｅｍｏｔｉｏｎ  Ｅｎｇｉｎｅ）と呼ばれるＣＰＵが採用されている。ＥＥ用にポーティング（移殖）されたＬｉｎｕｘに、共通のテストアンドセット命令の手続きを提供する／ｄｅｖ／ｔｓｔというソフトウェア・デバイスドライバを実装した。
【０１１９】
ｇｌｉｂｃのＬｉｎｕｘスレッドのサポートルーティンは、このデバイスをｏｐｅｎ，  ｍｍａｐ，  ｃｌｏｓｅして、テストアンドセット命令の手続きを呼び出す。このため、一度初期化してしまえば、テストアンドセット命令の手続きを呼び出すシステムコールは不要となる。
【０１２０】
また、異常終了した際にもｍｍａｐを利用しているため、不要な資源が残ったままになることはない。
【０１２１】
ｍｍａｐされるｔｓｔ手続きは、競合状態にある場合でも、極力コンテキストスイッチが起きないようにｓｗ実行前にｋ１をテストするように改良した（巻末参考資料（８）参照）。
【０１２２】
更新時のメインテナンス性を考慮して、ｏｐｅｎして、ｒｅａｄするとｍｍａｐすべきアドレスが読めるようにした。ライブラリは、そのアドレスへＭＡＰ＿ＦＩＸＥＤで１ｐａｇｅ分ｍｍａｐして、ｓｙｓｔｅｍ  ｃａｌｌのｔｅｓｔ  ａｎｄ  ｓｅｔの代わりにｍｍａｐした先を呼び出すことになる。
【０１２３】
上述した実施例の効果について説明する。
【０１２４】
性能評価用マシン上のＥＥ版Ｌｉｎｕｘにて、以下を評価した。
【０１２５】
（１）競合が起きない場合の速度差
【０１２６】
（２）競合も起きる場合、一定時間内で完了する処理数の差
【０１２７】
（１）の測定のため、ｐｏｓｉｘ  （Ｐｏｒｔａｂｌｅ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）  １００３．１ｂセマフォー（ｓｅｍａｐｈｏｒｅ）を単純に繰り返し呼ぶ評価用プログラム１を作り、システムコール版のテストアンドセット命令と本実施例とで比較した。他にプロセスを動作させない状態で各々３回測定し、平均値を用いた（巻末参考資料（９）参照）。
【０１２８】
システムコール（ｓｙｓｔｅｍ  ｃａｌｌ）を使わないため、他にプロセスが動いていない状態で処理速度が約４．８倍に向上した。
【０１２９】
（２）の測定のため、典型的な生産者−消費者問題をＰＯＳＩＸ  １００３．１ｂセマフォーを使い実装（評価用プログラム２）し、一定時間内の資源の処理回数（生産消費数）をシステムコール版のテストアンドセット命令と本実施例とで比較した。１つの条件ごとに２０秒間の測定を１０回繰り返し、平均値を用いた（巻末参考資料（１０）参照）。
【０１３０】
スレッド数の大小により、約１．３から１．７倍、処理回数が向上した。
【０１３１】
本実施例により、オーバーヘッドが減少しているため、スレッド数の大小に関わらず処理回数が改善された。スレッドが多く、システム全体の負荷が大きくなる状態になると効果が大きくなる。
【０１３２】
上述したように、本実施例では、システムコール（ｓｙｓｔｅｍ  ｃａｌｌ）を使用せずに、テストアンドセット命令（ｔｅｓｔ  ａｎｄ  ｓｅｔ）を実装することにより、オーバーヘッドを減少させ、単独の処理速度を４倍以上、一定時間内の処理回数を３割以上改善することが出来た。
［参考資料］
【０１３３】
参考資料（１）：図１０は、アトミックでないテストアンドセット命令のシーケンス例である。
【０１３４】
参考資料（２）：図１１は、ユーザプロセス２つが同時にクリティカルセクションへ突入するシナリオの例である。
【０１３５】
参考資料（３）：図１２は、ｄｉ／ｅｉ命令を使ったテストアンドセット命令のシーケンス例である。
【０１３６】
参考資料（４）：図１３は、システムを停止させるプログラムの例である。
【０１３７】
参考資料（５）：図１４は、ランポートのアルゴリズムの例である。
【０１３８】
参考資料（６）：図１５は、システムコールによる実装の例である。
【０１３９】
参考資料（７）：図１６は、競合状態にある場合のシーケンス例である。
【０１４０】
参考資料（８）：図１７は、ソフトウェアデバイスドライバｄｅｖ／ｔｓｔで提供されるテストアンドセット命令ｔｓｔの手続例である。
【０１４１】
巻末資料（９）：図１８は、評価用プログラム１を示した図である。
【０１４２】
参考資料（１０）：図１９〜図２３は、評価用プログラム２を示した図である。
【０１４３】
【発明の効果】
以上説明したように、本発明の効果は次の通りである。
【０１４４】
本発明によれば、マルチジョブを処理するシングルプロセッサ・システムにおいて、専用命令なしで、効率良く且つ安全にユーザプロセスレベルで排他制御を実行できる新規なコンピュータ、その制御方法及びその制御方法を記録した記録媒体を提供することが出来る。
【図面の簡単な説明】
【図１】図１は、本発明の対象であるコンピュータの一例のブロック図を示している。
【図２】図２は、ＯＳの概念図である。
【図３】図３は、コンピュータ資源の同時占有を説明する概念図である。
【図４】図４は、ユーザプロセスとカーネルとの関係を説明する図である。
【図５】図５は、各プロセス間の制御の移り変わりを示す図である。
【図６】図６は、シングルプロセッサのマルチタスク処理のフローチャートである。
【図７】図７は、シングルプロッセサのマルチタスク処理のフローチャートである。
【図８】図８は、処理プログラムの一例のプログラムを示す図である。
【図９】図９は、アトミック領域への割り込みのシーケンス図である。
【図１０】図１０は、参考資料としてのアトミックに実装されていないプログラムを示す図である。
【図１１】図１１は、参考資料としてのクリティカルセクションへ突入するシーケンス図である。
【図１２】図１２は、参考資料としてのｄｉ／ｅｉ命令を使ったプログラムを示す図である。
【図１３】図１３は、参考資料としてのシステムを停止させるプログラムを示す図である。
【図１４】図１４は、参考資料としてのランポートのアルゴリズムを示す図である。
【図１５】図１５は、参考資料としてのシステムコールによる実装を示すシーケンス図である。
【図１６】図１６は、参考資料としての競合状態にある場合のシーケンス図である。
【図１７】図１７は、参考資料としてのソフトウェアデバイスドライバｄｅｖ／ｔｓｔで提供されるテストアンドセット命令ｔｓｔ手続を示す図である。
【図１８】図１８は、参考資料としての評価用プログラム１を示す図である。
【図１９】図１９は、参考資料としての評価用プログラム２の１番目の図である。
【図２０】図２０は、参考資料としての評価用プログラム２の２番目の図である。
【図２１】図２１は、参考資料としての評価用プログラム２の３番目の図である。
【図２２】図２２は、参考資料としての評価用プログラム２の４番目の図である。
【図２３】図２３は、参考資料としての評価用プログラム２の５番目の図である。
【符号の説明】
１：ＣＰＵ，    ２：メモリ，    ３：入力装置，    ４：出力装置，
５：ＯＳ，    ６：カーネル
【図１】
0003598282.tif 000004
【図２】
0003598282.tif 000005
【図３】
0003598282.tif 000006
【図４】
0003598282.tif 000007
【図５】
0003598282.tif 000008
【図６】
0003598282.tif 000009
【図７】
0003598282.tif 000010
【図８】
0003598282.tif 000011
【図９】
0003598282.tif 000012
【図１０】
0003598282.tif 000013
【図１１】
0003598282.tif 000014
【図１２】
0003598282.tif 000015
【図１３】
0003598282.tif 000016
【図１４】
0003598282.tif 000017
【図１５】
0003598282.tif 000018
【図１６】
0003598282.tif 000019
【図１７】
0003598282.tif 000020
【図１８】
0003598282.tif 000021
【図１９】
0003598282.tif 000022
【図２０】
0003598282.tif 000023
【図２１】
0003598282.tif 000024
【図２２】
0003598282.tif 000025
【図２３】
0003598282.tif 000026