(57)【特許請求の範囲】
【請求項１】
データ格納部とオブジェクト参照部とオブジェクト領域回収部とを含むデータ管理装置において、前記データ格納部に格納されたデータを管理する方法であって、
前記データは、他のエントリに対する参照を含むエントリに格納され、前記データの集合であるセットごとに管理され、
前記セットは、前記データが前記セットに追加された順に、前記データを格納するエントリが連結された連結リストとして構成され、
前記エントリは、前記連結リストに挿入された挿入時刻シーケンス、及び、前記セットから削除されたか否かを示す削除識別情報を含み、
前記方法は、
前記データが前記セットから削除されている場合には、前記オブジェクト領域回収部が前記オブジェクト参照部とは異なるスレッドで前記連結リストから前記エントリを分離し、
前記オブジェクト参照部は、前記連結リストの先頭エントリから、連結されたエントリを辿ることによって、順次、前記エントリに格納されたデータを参照し、
前記参照されるデータを格納するエントリであるカレントエントリの挿入時刻シーケンスと、前記カレントエントリの直前に連結されたエントリである前エントリの挿入時刻シーケンスとを比較し、
前記オブジェクト参照部は、
前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも早い場合には、前記カレントエントリに格納されたデータを参照し、前記カレントエントリをカーソル位置エントリとし、
前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも遅い場合には、前記カレントエントリが前記前エントリから参照されなくなったと判定し、前記カーソル位置エントリから参照を再開することを特徴とするデータ管理方法。
【請求項２】
前記データ管理装置は、さらに、オブジェクト挿入部を含み、
前記方法は、前記セットに新たにデータを追加する場合には、さらに、前記オブジェクト挿入部が、前記連結リストの先頭に前記追加されるデータを格納するエントリを挿入することを特徴とする請求項１に記載のデータ管理方法。
【請求項３】
前記データ管理装置は、さらに、オブジェクト削除部を含み、
前記方法は、前記セットからデータを削除する場合には、さらに、前記オブジェクト削除部が削除する前記データを格納するエントリの前記削除識別情報を設定することを特徴とする請求項１に記載のデータ管理方法。
【請求項４】
前記エントリは、前記セットから削除された削除時刻シーケンスを前記削除識別情報として含み、
前記方法は、さらに、
前記オブジェクト参照部は、前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも早い場合には、前記削除時刻シーケンスに有効な値が設定されているか否かによって、前記エントリが前記セットから削除されたか否かを判定し、
前記オブジェクト参照部は、前記連結リストに含まれるデータの参照を開始した参照開始時刻シーケンスを取得し、
前記カレントエントリの削除時刻シーケンスに有効な値が設定されていないか、又は、前記カレントエントリの削除時刻シーケンスが前記参照開始時刻シーケンスよりも遅い場合には、前記オブジェクト参照部は、前記カレントエントリに格納されたデータを参照し、前記カレントエントリをカーソル位置エントリとすることを特徴とする請求項１に記載のデータ管理方法。
【請求項５】
前記方法は、前記カレントエントリの削除時刻シーケンスに有効な値が設定され、かつ、前記カレントエントリの削除時刻シーケンスが前記参照開始時刻シーケンスよりも早い場合には、前記オブジェクト参照部が前記カレントエントリの直後に連結されたエントリに格納されたデータを参照することを特徴とする請求項４に記載のデータ管理方法。
【請求項６】
前記データ管理装置は、前記データを参照する複数のスレッドを実行し、
前記エントリは、前記セットから削除された削除時刻シーケンスを前記削除識別情報として含み、
前記方法は、さらに、
前記オブジェクト領域回収部は、前記各スレッドで前記連結リストが最後に参照された時刻シーケンスのうち、最も早い時刻シーケンスを最早参照時刻シーケンスとして取得し、
前記オブジェクト領域回収部は、前記連結リストの先頭エントリから連結されたエントリを辿ることによって、順次、前記エントリに含まれる削除時刻シーケンスを取得し、
前記オブジェクト領域回収部は、前記取得された削除時刻シーケンスが、前記最早参照時刻シーケンスよりも早い場合には、前記取得された削除時刻シーケンスを含むエントリを前記連結リストから分離することを特徴とする請求項１に記載のデータ管理方法。
【請求項７】
前記連結リストから分離されたエントリは、前記セットに新たにデータが格納される場合に再利用され、
前記方法は、前記セットに新たにデータを追加する場合には、オブジェクト挿入部は、前記追加されるデータに対応するエントリを前記連結リストに連結する前に、前記エントリの挿入時刻シーケンスを更新することを特徴とする請求項６に記載のデータ管理方法。
【請求項８】
前記エントリは、前記エントリに対応するデータの更新履歴を含み、
前記更新履歴は、前記データが更新されるたびに対応する版が追加され、
前記版には、前記版に対応するデータが確定した版確定時刻シーケンスが含まれ、
前記削除識別情報は、前記エントリに含まれる最新の版に対応するデータが存在しない場合に、前記エントリが前記セットから削除されていると識別されることを特徴とする請求項１に記載のデータ管理方法。
【請求項９】
前記方法は、さらに、
前記オブジェクト参照部は、前記連結リストに含まれるデータの参照を開始した参照開始時刻シーケンスを取得し、
前記オブジェクト参照部は、前記カレントエントリに含まれる各版の版確定時刻シーケンスが前記参照開始時刻シーケンスよりも早い版のうち、最も新しい版を参照対象の版とし、前記参照対象の版を含む前記エントリに格納されたデータを参照することを特徴とする請求項８に記載のデータ管理方法。
【請求項１０】
前記方法は、前記参照対象の版に対応するデータが存在しない場合には、前記オブジェクト参照部は、前記カレントエントリの直後に連結されたエントリに格納されたデータを参照することを特徴とする請求項９に記載のデータ管理方法。
【請求項１１】
前記データ管理装置は、前記データを参照する複数のスレッドを実行し、
前記方法は、
前記オブジェクト領域回収部は、前記各スレッドで前記連結リストが最後に参照された時刻シーケンスのうち、最も早い時刻シーケンスを最早参照時刻シーケンスとして取得し、
前記オブジェクト領域回収部は、前記連結リストの先頭エントリから連結されたエントリを辿ることによって、順次、前記連結リストから削除されたエントリを取得し、
前記オブジェクト領域回収部は、前記取得されたエントリの削除時刻シーケンスが、前記最早参照時刻シーケンスよりも早い場合には、前記取得されたエントリを前記連結リストから分離することを特徴とする請求項８に記載のデータ管理方法。
【請求項１２】
データ格納部及びオブジェクト領域回収部を含むデータ管理装置において、前記データ格納部に格納されたデータを管理するために実行されるプログラムであって、
前記データは、他のエントリに対する参照を含むエントリに格納され、前記データの集合であるセットごとに管理され、
前記セットは、前記データが前記セットに追加された順に、前記データを格納するエントリが連結された連結リストとして構成され、
前記エントリは、前記連結リストに挿入された挿入時刻シーケンス、及び、前記セットから削除されたか否かを示す削除識別情報を含み、
前記オブジェクト領域回収部は、前記データが前記セットから削除されている場合に、前記プログラムが実行されているスレッドとは異なるスレッドで前記連結リストから前記エントリを分離し、
前記プログラムは、
前記連結リストの先頭エントリから、連結されたエントリを辿ることによって、順次、前記エントリに格納されたデータを参照する手順と、
前記参照されるデータを格納するエントリである参照エントリの挿入時刻シーケンスと、前記参照エントリの直前に連結されたエントリである前エントリの挿入時刻シーケンスとを比較する手順と、
前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも早い場合には、前記カレントエントリに格納されたデータを参照し、前記カレントエントリをカーソル位置エントリとする手順と、
前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも遅い場合には、前記カレントエントリが前記前エントリから参照されなくなったと判定し、前記カーソル位置エントリから参照を再開する手順と、を持つことを特徴とするデータ管理プログラム。
【請求項１３】
データ格納部とオブジェクト参照部とオブジェクト領域回収部とを含み、前記データ格納部に格納されたデータを管理するデータ管理装置であって、
前記データは、他のエントリに対する参照を含むエントリに格納され、前記データの集合であるセットごとに管理され、
前記セットは、前記データが前記セットに追加された順に、前記データを格納するエントリが連結された連結リストとして構成され、
前記エントリは、前記連結リストに挿入された挿入時刻シーケンス、及び、前記セットから削除されたか否かを示す削除識別情報を含み、
前記オブジェクト領域回収部は、
前記データが前記セットから削除されている場合には、前記オブジェクト参照部とは異なるスレッドで前記連結リストから前記エントリを分離し、
前記オブジェクト参照部は、前記連結リストの先頭エントリから、連結されたエントリを辿ることによって、順次、前記エントリに格納されたデータを参照し、
前記オブジェクト参照部は、
前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも早い場合には、前記カレントエントリに格納されたデータを参照し、前記カレントエントリをカーソル位置エントリとし、
前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも遅い場合には、前記カレントエントリが前記前エントリから参照されなくなったと判定し、前記カーソル位置エントリから参照を再開することを特徴とするデータ管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを管理する技術に関する。
【背景技術】
【０００２】
データ管理の分野では、データを表すオブジェクトの順序なし集合であるセット、及び、当該セットに対する操作手段をアプリケーションに対して提供することが一般的である。例えば、ＲＤＢ（Ｒｅｌａｔｉｏｎａｌ  ＤａｔａＢａｓｅ）では、行をオブジェクトとする順序なし集合である表が本発明でいうセットである。ＯＯＤＢ（Ｏｂｊｅｃｔ  Ｏｒｉｅｎｔｉｅｄ  ＤａｔａＢａｓｅ）では、オブジェクト及びセットという用語が直接利用される。また、セットに対する操作手段としては、例えば、セット内のオブジェクトを漏れ及び重複なく逐次参照するためにカーソルと呼ばれる反復子を用いられる。
【０００３】
従来、ＲＤＢＭＳなどのデータ管理手段では、記憶容量及び他の観点によって、セットをハードディスク上に構成していた。セットをハードディスク上に構成する場合、ハードディスクに対するランダムアクセスはレスポンスが遅いため、一定の大きさの領域を有し、シーケンシャルアクセスが可能な連続領域であるブロックを設け、ブロック内に同一セットに含まれるオブジェクトを近接して格納するのが一般的であった。この場合、オブジェクトの削除によって不要となった領域の回収は、ブロック内のオブジェクトの再詰め合わせ、及びブロックの回収によって実現する。ここで、ランダムアクセスの頻度を抑えつつ効率良く開放済み空き領域を再利用するためには、ブロック単位の回収、再利用が有効である。そのため、一般的に空領域開放処理では複数ブロックをまたがったオブジェクトの再詰め合わせを実行し、空きブロックを作成した上で、ブロック単位で領域を開放していた。以上の処理は、オブジェクトの移動を必要とする高負荷な処理である。
【０００４】
近年では、メモリ容量の増大及び高速アクセス要求の高まりによって、ＲＤＢＭＳなどのデータ管理手段であっても主記憶上にセットを構成する場合がある。主記憶上にセットを格納する場合、シーケンシャルアクセスに対するランダムアクセスによる性能ペナルティがほとんど無いため、高速アクセスの目的でセット内のオブジェクトを隣接領域に格納する必要が無い。そのため、主記憶上では、連結リストを代表とするグラフによって、特定ノードからリンクにより到達可能なノード集合としてセットを構成するのが一般的である。ここで、グラフによって構成されたセットから、オブジェクトを削除及び領域回収する場合には、削除対象オブジェクトを到達不可能にする内向きリンクを削除する。また、削除されたオブジェクトの領域は再利用する際に更新され、削除対象オブジェクトから他のオブジェクトを参照するための外向きリンクが破壊される。
【０００５】
プロセッサの時分割利用又は複数プロセッサをサポートする環境では、複数のスレッド（ここでは、プロセスは１つ以上のスレッドの集合と解釈する）から並行してセットにアクセスする可能性がある。セットに含まれている削除対象オブジェクトは、削除主体となったスレッドと異なる他のスレッドから参照されている可能性がある。異なるスレッドから削除対象オブジェクトを参照している状態で当該領域を再利用して外向きリンクを破壊すると、参照スレッドは当該ポインタを用いてリンクされた他のオブジェクト（到達可能オブジェクトグラフに属するものを含む）に到達できなくなる可能性がある。このような問題を回避するために、他のスレッドが該オブジェクトを参照していないことを保証した上で削除対象オブジェクトの領域を再利用する手法がある。単純な方法としては、例えば、オブジェクトの相互排他ロックを取得することである。
【０００６】
また、特許文献１には、他のスレッドが削除対象オブジェクトを参照していないことを保証する別の方法が開示されている。特許文献１に開示された技術では、オブジェクトグラフ内で削除対象オブジェクトへのリンクが削除された後に、既に当該削除対象オブジェクトを参照中のスレッドを待ち合わせ、すべてのスレッドが当該削除対象オブジェクトの参照を終了した時点で当該削除対象オブジェクトの領域を再利用する。なお、スレッドがオブジェクトの参照を終了したことを検知するためには、スレッドの実行履歴を利用している。
【特許文献１】米国特許第５４４２７５８号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
削除対象オブジェクトの領域を再利用する際に、当該オブジェクトを他のスレッドが参照していないことを保証するために、当該オブジェクトに相互排他ロックを利用する場合には、参照スレッドを含む当該オブジェクトにアクセスするすべてのスレッドで相互排他ロックを取得する必要がある。しかし、相互排他ロックは処理負荷が大きく、また、同一オブジェクトを参照するスレッドの同時実行を阻害する。また、相互排他のための命令は、マルチプロセッサ環境におけるプロセッサの同時実行性をも阻害する要因となる。そのため、参照主体のアプリケーション、更新対象オブジェクトの衝突が稀な更新アプリケーションにおいてもオブジェクトアクセスのオーバヘッドが高くなってしまう。
【０００８】
また、特許文献１に開示された技術では、対象オブジェクトを参照していないことを保証できる静止状態に各スレッドが予測可能、かつ、短期の有限時間内に到達することを想定し、スレッドの状態履歴を監視している。しかし、本発明が対象とするデータ管理手段であるカーソルを用いたオブジェクトの逐次参照では、特許文献１における静止状態は、次の参照可能なオブジェクトを発見した後にアプリケーションプログラムに制御が移った状態である。ここで、カーソルを用いたオブジェクトの逐次参照要求は、アプリケーションによって制御され、タイミングは予測可能ではなく、短期でない可能性がある。例えば、カーソルを用いたオブジェクトの連続する逐次参照要求の間にハードウェアアクセスやユーザインタラクションを伴う場合である。その場合、各スレッドの静止状態の履歴を監視する手法では、削除対象オブジェクトの領域再利用が滞ってしまうため、メモリの利用効率が悪化してしまう。
【０００９】
また、特許文献１に開示されているＯＳ内部のデータ構造を更新する場合では、スレッドの実行履歴は別の目的で既に取得されていることが示唆されており、その場合にはスレッド実行履歴を取得する追加コストは必要ないとされている。しかし、本発明が対象とするデータ管理手段で特許文献１に開示された技術を適用する場合、スレッドの実行履歴を取得する処理を新たに追加する必要があり、オブジェクト（データ）を逐次参照する処理におけるオーバヘッドが発生する。
【課題を解決するための手段】
【００１０】
本発明の代表的な一形態によれば、データ格納部とオブジェクト参照部とオブジェクト領域回収部とを含むデータ管理装置において、前記データ格納部に格納されたデータを管理する方法であって、前記データは、他のエントリに対する参照を含むエントリに格納され、前記データの集合であるセットごとに管理され、前記セットは、前記データが前記セットに追加された順に、前記データを格納するエントリが連結された連結リストとして構成され、前記エントリは、前記連結リストに挿入された挿入時刻シーケンス、及び、前記セットから削除されたか否かを示す削除識別情報を含み、前記方法は、前記データが前記セットから削除されている場合には、前記オブジェクト領域回収部が前記オブジェクト参照部とは異なるスレッドで前記連結リストから前記エントリを分離し、前記オブジェクト参照部は、前記連結リストの先頭エントリから、連結されたエントリを辿ることによって、順次、前記エントリに格納されたデータを参照し、前記参照されるデータを格納するエントリであるカレントエントリの挿入時刻シーケンスと、前記カレントエントリの直前に連結されたエントリである前エントリの挿入時刻シーケンスとを比較し、前記オブジェクト参照部は、前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも早い場合には、前記カレントエントリに格納されたデータを参照し、前記カレントエントリをカーソル位置エントリとし、前記カレントエントリの挿入時刻シーケンスが、前記前エントリの挿入時刻シーケンスよりも遅い場合には、前記カレントエントリが前記前エントリから参照されなくなったと判定し、前記カーソル位置エントリから参照を再開することを特徴とするデータ管理方法。
【発明の効果】
【００１１】
本発明の一形態によれば、相互排他ロックなどを利用せずに、集合（セット）に含まれるデータ（オブジェクト）が削除された場合であっても、集合（セット）に含まれるすべてのデータ（オブジェクト）が参照可能であることを保証することができる。
【発明を実施するための最良の形態】
【００１２】
本発明を実施するための最良の形態を具体的に説明する。
【００１３】
（第１の実施の形態）
図２は、本発明の第１の実施の形態のデータ管理システムのハードウェアモジュール構成、ソフトウェアモジュール構成及び関連を説明する図である。
【００１４】
本発明の第１の実施の形態のデータ管理システムは、マルチプロセッサコンピュータシステムであって、マルチスレッドで各処理が実行される。また、データ管理システム上には、データベースシステムが稼働している。
【００１５】
本発明の第１の実施の形態のデータ管理システムは、１又は複数のプロセッサ０２１、及び、主記憶００１を備える。プロセッサ０２１は、システムバス０２２を介して主記憶００１に接続する。
【００１６】
プロセッサ０２１は、主記憶００１に記憶されたプログラムを処理し、各種処理を実行する。主記憶００１は、プログラム及び当該プログラムで利用されるデータを記憶する。具体的には、主記憶００１は、スケジューラ００２、スレッドコンテクスト００３、プログラム格納部０１１、及び、データ格納部０１２を記憶する。
【００１７】
ここで、スレッドは、プログラム格納部０１１に記憶されたプログラムの実行ステップ位置であるプログラムカウンタを有し、プロセッサ０２１の実行時間を割当てることによってプログラムカウンタの指すステップを順次実行するプログラム実行単位である。また、スレッドによるプログラム実行において、データ格納部０１２に格納されたデータを参照及び更新する。
【００１８】
スケジューラ００２は、それぞれのスレッドコンテクスト００３に対し、時分割でプロセッサ０２１の利用時間を割当てることによって、スレッドの実行を制御する。スレッドに割当てられた時分割のプロセッサ利用時間が満了すると、スケジューラ００２は、現在のプログラムカウンタの値及びレジスタの値を対応するスレッドコンテクスト００３に保存し、新たに選択したスレッドにプロセッサ利用時間を与える。プロセッサの利用時間が満了したスレッドに再びプロセッサ利用権限が与えられると、対応するスレッドコンテクストからプログラムカウンタの値及びレジスタの値を回復し、中断位置からプログラムステップの実行を再開する。
【００１９】
スケジューラ００２によるスレッドへのプロセッサ０２１の利用時間割当は、基本的に、タイムスライスと呼ばれる一定の短期間を単位として行われる。その他、ＯＳリソースのウェイトロック待ち、ハードウェアリソースの応答待ちなどの状況に応じて、当初スレッドに割当てられたタイムスライス中であっても当該スレッドからプロセッサ実行時間が途中で剥奪され、他のスレッドに割当てられる場合がある。
【００２０】
図１は、本発明の第１の実施の形態のデータ管理システムにおけるソフトウェアモジュール構成図である。
【００２１】
データ管理システムの主記憶００１には、前述したように、スケジューラ００２、スレッドコンテクスト００３、プログラム格納部０１１及びデータ格納部０１２が格納される。
【００２２】
プログラム格納部０１１には、ステップの集まりであるプログラムが格納されている。具体的には、アプリケーションプログラム００４と、データ管理手段であるソフトウェアモジュールとが格納される。アプリケーションプログラム００４には、データ管理手段を利用して目的サービスを実行するロジックが定義されている。
【００２３】
データ管理手段であるソフトウェアモジュールには、オブジェクト挿入部００５、オブジェクト削除部００６、オブジェクト参照部００７及びオブジェクト領域回収部００８が含まれる。
【００２４】
また、データ格納部０１２には、エントリヒープ０１０、カウンタ０１３、データ０１４及びカーソルプール０１５が格納される。
【００２５】
オブジェクト挿入部００５は、アプリケーションプログラム００４からの要求によって動作し、データ管理手段であるエントリヒープ０１０内に連結リストとして構成されるセットに対してオブジェクトを挿入する手順を実行するソフトウェアモジュールである。
【００２６】
エントリヒープ０１０は、オブジェクト、当該オブジェクトに対応する連結リストのエントリ及び両者のための空領域を格納するための記憶領域である。
【００２７】
オブジェクト削除部００６は、アプリケーションプログラム００４からの要求によって動作し、カーソルが指すオブジェクトをセットから削除する手順を実行するソフトウェアモジュールである。
【００２８】
オブジェクト参照部００７は、アプリケーションプログラム００４からの要求によって動作し、セットに含まれるオブジェクトへの参照をアプリケーションプログラム００４に返却する手順を実行するソフトウェアモジュールである。この手順には、カーソルを初期化するオブジェクト逐次参照開始手順と、初期化済みカーソルを用いたオブジェクト逐次参照手順とが含まれる。
【００２９】
オブジェクト領域回収部００８は、データが削除されたことによって、すべてのスレッドからアクセスされることのない削除済みオブジェクト及びエントリによって使用されている領域を、再利用に備えて回収し、フリー領域として管理するための手順を実行するソフトウェアモジュールである。アプリケーションプログラム００４の直接的な要求、又は、オブジェクト挿入要求の延長などによって実行されてもよいが、本発明の第１の実施の形態では、バックグラウンドスレッドとしてアプリケーションプログラム００４の要求とは非同期に実行される。
【００３０】
システム時刻シーケンス生成部００９は、データ管理手段が利用するシステムで統一的なシステム時刻シーケンスを生成するソフトウェアモジュールである。システム時刻シーケンス生成部００９は問合せごとに異なる単調に進行する値としてシステム時刻シーケンスを応答する。複数のスレッドから並行に問合せを行った場合であってもそれぞれのスレッドに対して異なるシステム時刻シーケンスを応答することを保証する。なお、システム時刻シーケンスは実時刻と対応している必要は無い。事実上循環することない大きな値を格納可能であって、要求ごとにインクリメントするカウンタ０１３を用いて実装することができる。また、ハードウェアで実装された時計と連携してもよい。
【００３１】
アプリケーションプログラム００４は、データ管理手段によって管理されるデータの他に、アプリケーション用のデータ０１４を独自に管理してもよい。
【００３２】
また、アプリケーションプログラム００４の手順を実行するスレッドとデータ管理手段の手順を実行するスレッドは、同一であってもよいし、協調して動作する異なるスレッドであってもよい。本発明の第１の実施の形態ではアプリケーションプログラム００４、データ管理手段のソフトウェアモジュールであるオブジェクト挿入部００５、オブジェクト削除部００６及びオブジェクト参照部００７は直接連携し、データ管理手段のソフトウェアモジュールは、要求を行ったアプリケーションプログラム００４と同一のスレッドによって実行される。ただし、オブジェクト領域回収部００８は、アプリケーションプログラム００４を実行するスレッドと異なるスレッドで実行される。
【００３３】
オブジェクト削除部００６及びオブジェクト参照部００７は、オブジェクトを逐次参照するためのカーソルを利用する。データ管理手段によって扱われるすべてのカーソルは、カーソルプール０１５に格納される。オブジェクト削除部００６及びオブジェクト参照部００７を実行する各スレッドには、カーソルプール０１５に含まれるカーソルが１つ割当てられ、割り当てられたカーソルを利用して、エントリヒープ０１０に格納されたセットを走査する。
【００３４】
図５は、本発明の第１の実施の形態のデータ管理手段のデータ格納部０１２におけるデータ格納形式を説明する図である。
【００３５】
図６は、本発明の第１の実施の形態のデータ格納部０１２に格納されるエントリ２０４の構成例を示す図である。
【００３６】
オブジェクト２１４のセットは、オブジェクト２１４と１対１に対応するエントリ２０４の連結リストの形式で、エントリヒープ２０３に格納される。なお、本発明の第１の実施の形態では、オブジェクト２１４は、エントリ２０４の一部として格納することによって互いに対応付けられる。
【００３７】
セットアンカ２０１は、セットに対応する連結リストの先頭のエントリ２０４のアドレスを格納するポインタ変数である。
【００３８】
図６に示すように、エントリ２０４は、次エントリ２１１、挿入時刻シーケンス２１２、削除時刻シーケンス２１３、フリー次エントリ２１５、及び、オブジェクト２１４を含む。
【００３９】
次エントリ２１１は、セットに対応する連結リスト上における次エントリのアドレスを格納するポインタ変数である。挿入時刻シーケンス２１２は、エントリ２０４がセットに挿入された時刻シーケンスが格納される。削除時刻シーケンス２１３は、エントリ２０４がセットから削除された時刻シーケンスが格納される。フリー次エントリ２１５は、セットから削除された後、フリー領域として当該エントリ２０４が管理される場合に、他の解放されたエントリ２０４と連結するために、当該他の解放されたエントリ２０４のアドレスを格納するポインタ変数である。セットに新たにエントリ２０４を追加する場合には、フリー領域から空のエントリを取得し、各メンバに値を設定し、セットに対応する連結リストに当該エントリを挿入する。
【００４０】
ここで、連結リストを構成するエントリ２０４であって、アプリケーションプログラム００４からの削除要求によって削除時刻シーケンス２１３が設定されたエントリ２０４を削除済みエントリと呼ぶ。また、削除済みエントリであって、かつ、カーソルの参照時刻シーケンスよりも前の削除時刻シーケンス２１３の値を含むエントリを、当該カーソルにおける無効エントリと呼ぶ。一方、連結リストを構成するエントリ２０４であって、無効エントリでないものを、当該カーソルにおける有効エントリと呼ぶ。
【００４１】
エントリヒープ２０３には、セットに対応する連結リストを構成しないエントリ２０４及びオブジェクト２１４も共存する。アプリケーションデータがまだ格納されていない、又は、セットから削除されたオブジェクトがオブジェクト領域回収部００８によって対応する連結リストから分離されたエントリ２０４及びオブジェクト２１４である。本発明の第１の実施の形態では、このようなエントリ２０４及びオブジェクト２１４をフリーリストと呼ばれる連結リストとして管理する。これにより、利用及び再利用の際にフリーなエントリ２０４及びオブジェクト２１４を効率よくアクセスできる。エントリ２０４のフリー次エントリ２１５は、フリーリストを構成する際に、次のエントリ２０４を参照するために利用する。フリーアンカ２０２は、フリーリストの先頭のエントリ２０４を参照する連結リストのアンカである。
【００４２】
図７は、本発明の第１の実施の形態のデータ格納部０１２に格納されるエントリ２０４の別の構成例を示す図である。
【００４３】
次エントリ２１１、挿入時刻シーケンス２１２、削除時刻シーケンス２１３及びフリー次エントリ２１５は、図６に示したエントリと同じである。
【００４４】
また、オブジェクト２１４は、図６に示した構成ではメンバ変数としてエントリ２０４に内包されていたが、図７に示す構成ではエントリ２０４から独立に領域を確保し、エントリ２０４のメンバ変数であるオブジェクトポインタ２２１によって参照される。このように実装することによって、Ｃ、Ｃ＋＋などのプログラミング言語においてサイズが可変のオブジェクトの管理が容易になる。図７におけるオブジェクト２１４の領域管理は、エントリ２０４と同様にフリーリストを利用する。本発明の第１の実施の形態では、図７におけるオブジェクト２１４の領域管理は、ＯＳ及びプログラミング言語の実行環境によって実行されるものとし、管理手順に言及しない。
【００４５】
図４は、本発明の第１の実施の形態のカーソル１２０の構成を示す図である。
【００４６】
カーソル１２０は、セット内のオブジェクト２１４を漏れなく重複無くアクセスするための状態を保持する。また、カーソル１２０は、セット内のオブジェクト２１４を削除する際にオブジェクトを指定するためにも使用される。
【００４７】
カーソル１２０は、参照時刻シーケンス１２１、セットアンカ１２２、カーソル位置エントリ１２３及び探索条件１２４を含む。
【００４８】
参照時刻シーケンス１２１は、カーソル１２０が参照された時刻シーケンスを格納する。参照時刻シーケンス１２１は、エントリ２０４の削除時刻シーケンス２１３と比較することによって、オブジェクト逐次参照手段がエントリ２０４の有効又は無効を判断するために使用される。
【００４９】
セットアンカ１２２は、カーソル１２０に対応する連結リストの先頭に位置するエントリ２０４のアドレスを格納するポインタ変数である。スレッドごとに単一のセットのみを扱う場合には、スレッドごとに保持していればよいが、データ管理手段が複数のセットをサポートする場合には、走査対象の連結リストの先頭に位置するエントリ２０４を参照するセットアンカ１２２をカーソルごとに保持する必要がある。
【００５０】
カーソル位置エントリ１２３は、セットに対応する連結リストに含まれ、かつ、現在参照しているエントリ２０４のアドレスを格納するポインタ変数である。探索条件１２４は、セット内のオブジェクトを選択的にアクセスするための条件である。
【００５１】
図３は、本発明の第１の実施の形態のスレッドコンテクスト００３の構成例を示す図である。
【００５２】
プログラムカウンタ退避領域１０１は、該当スレッドに与えられたプロセッサ０２１の利用時間が満了した時点で、実行中のプログラムのステップを保存するための領域である。同様に、レジスタ退避領域１０２は、プロセッサ０２１の利用時間が満了した時点で、プロセッサ０２１のレジスタを保存するための領域である。一般に、プログラムカウンタ退避領域１０１及びレジスタ退避領域１０２は、ＯＳによって割り当てられ、管理される領域である。
【００５３】
前エントリ１０３、カレントエントリ１０４、及び、次エントリ１０５は、該当するエントリ２０４のアドレスを格納するポインタ変数である。前エントリ１０３、カレントエントリ１０４、及び、次エントリ１０５は、カーソル１２０を用いたオブジェクト逐次参照時、又は、オブジェクト領域回収時に連結リストを走査する際に利用される。同様に、前エントリ挿入時刻シーケンス１０６、カレントエントリ挿入時刻シーケンス１０７、及び、カレントエントリ削除時刻シーケンス１０８についても、連結リスト走査時に利用される。
【００５４】
最早参照時刻シーケンス１１０は、カーソルプール０１５に格納されたカーソル１２０の中で、最も早くアクセスされたカーソル１２０の参照時刻シーケンス１２１を格納する。最早参照時刻シーケンス１１０は、オブジェクト領域回収スレッドにおいて、エントリ２０４及び対応するオブジェクトの領域回収可否を判定するために、エントリ２０４の削除時刻シーケンス２１３との比較に用いられる。また、参照時刻シーケンス１１１は、最早参照時刻シーケンス１１０を求める際に使用される一時変数である。
【００５５】
その他、スレッドコンテクスト００３には、各スレッドで専用に利用されるスレッドローカル変数１１４が存在する。
【００５６】
前エントリ１０３、カレントエントリ１０４、次エントリ１０５、前エントリ挿入時刻シーケンス１０６、カレントエントリ挿入時刻シーケンス１０７、カレントエントリ削除時刻シーケンス１０８、最早参照時刻シーケンス１１０及びスレッドローカル変数１１４は、一般にＯＳ又はプログラミング言語の実行環境によって提供されるヒープ領域又はスタック領域に作成され、プログラムカウンタ退避領域１０１及びレジスタ退避領域１０２と関連付けて管理される。
【００５７】
ここで、本発明の第１の実施の形態のセットを参照する手順について説明する。
【００５８】
本発明の第１の実施の形態では、前述したように、アクセス順序を保証しないオブジェクトの集合であるセットが、オブジェクトに対応するエントリ２０４をリンクで線状に連結した連結リストとして構成されている。
【００５９】
オブジェクトをセットに挿入する場合には、オブジェクトに対応付されたエントリ２０４の挿入時刻シーケンス２１２に現在時刻シーケンスを設定し、連結リストの先頭に挿入する。このようにすることによって、連結リスト内で挿入時刻シーケンス２１２が降順（現在から過去）になるようにエントリ２０４が連結される。
【００６０】
また、セットからオブジェクトを削除する場合には、対応するエントリに削除時刻シーケンス２１３に現在時刻シーケンスを設定することによって、当該オブジェクトのエントリを削除済み状態とする。
【００６１】
カーソルを用いてセット内のオブジェクトを逐次参照する場合には、カーソルの現在位置から次エントリ２１１を辿り、連結リストを走査する。走査中のエントリが削除済み状態でないか、削除時刻シーケンス属性が参照スレッドの参照時刻シーケンス属性と比較して新しい場合は、該エントリをカーソルの新たな現在位置とし、当該オブジェクトへのアクセスをアプリケーションに通知する。
【００６２】
オブジェクト領域の再利用に備えて削除済みエントリで使用された領域の回収する場合には、回収時点で存在するすべての参照スレッドの参照時刻シーケンスを参照し、そのうちもっとも早い時刻シーケンスを最早参照時刻シーケンスとする。次に、エントリを連結リストの先頭から次エントリ用のリンクを辿り走査する。走査中のエントリが削除済みでかつ、削除時刻シーケンス属性が参照スレッドの最早参照時刻シーケンス属性と比較して古い場合は、該当エントリを連結リストから分離し、当該エントリ及び対応オブジェクトの領域を再利用対象とする。
【００６３】
以上説明したカーソルによってセット内のオブジェクトを逐次参照する場合において、カーソル位置エントリ１２３が削除済オブジェクトを参照したタイミングで削除済エントリが回収され、再利用された場合に、元の連結リストにおける次ノードへのリンクが保証されない。この場合に、削除対象オブジェクトの挿入時刻シーケンス属性が、直前エントリの挿入時刻シーケンス属性よりも新しいことを判定することによって、削除済みエントリの領域が再利用されたことを検知することが可能である。削除対象オブジェクトの領域が再利用されたことを検知した場合には、逐次参照要求前にカーソルが位置していた有効エントリまでポインタ変数を戻して、カーソル走査処理を再実行する。
【００６４】
以下、図８（図８Ａ〜図８Ｅ）を参照しながら、オブジェクトの逐次参照において、削除済みエントリの領域が再利用されたことを検知し、逐次参照要求前にカーソルが位置していた有効エントリまでポインタ変数を戻して、連結リスト走査処理を再実行する手順を具体的に説明する。
【００６５】
図８Ａは、本発明の第１の実施の形態のセットアンカ２０１Ａから参照される連結リストによって構成されているセットを表す図である。図８Ａの上段を「セットＡ」とし、下段を「セットＢ」とする。
【００６６】
前述したように、各エントリ２０４は挿入時刻シーケンス２１２の降順に並んでいる。例えば、エントリ２０４Ｆの挿入時刻シーケンス２１２をα、エントリ２０４Ｅの挿入時刻シーケンス２１２をβとすると、α＜βとなる。
【００６７】
また、カーソル１２０のカーソル位置エントリ１２３は、現在、エントリ２０４Ｃを参照している。アプリケーションプログラム００４からのオブジェクト逐次参照要求に従い、カーソルが次に移動すべきエントリはエントリ２０４Ｈである。エントリ２０４Ｃとエントリ２０４Ｈとの間にあるエントリ２０４は削除され、該当カーソルを用いる参照スレッドからは参照できない無効エントリである。削除済みエントリは、すべてのスレッドから参照不可能な無効エントリとされた場合に、当該領域が回収され再利用される可能性がある。他方で、カーソルが現在位置付いているエントリ２０４Ｃ及び次に位置付くエントリ２０４Ｈは該当カーソルを有するスレッドから参照可能な有効エントリであるため、少なくとも逐次参照要求処理の期間において、領域の回収及び再利用の対象外となる。
【００６８】
カーソル１２０のカーソル位置エントリ１２３がエントリ２０４Ｃを指している状態で逐次参照要求を受け付けると、まず、オブジェクト参照部００７は、スレッドコンテクスト００３の前エントリ１０３にカーソル１２０のカーソル位置エントリ１２３の値を設定し、カレントエントリ１０４に前エントリ１０３に対応するエントリ２０４Ｃの次エントリ２１１の値が設定する。
【００６９】
オブジェクト参照部００７は、スレッドコンテクスト００３のカレントエントリ１０４に対応するエントリ２０４が無効エントリである間は、カレントエントリ１０４の値を前エントリ１０３に代入し、カレントエントリ１０４に対応するエントリ２０４の次エントリ２１１の値をカレントエントリ１０４に代入することによって連結リストを走査する。
【００７０】
図８Ｂは、本発明の第１の実施の形態のスレッドコンテクスト００３の前エントリ１０３及びカレントエントリ１０４に対応するエントリがオブジェクト参照部００７によって移動された状態を示す図である。
【００７１】
図８Ｂでは、カレントエントリ１０４がエントリ２０４Ｆを参照し、前エントリ１０３がエントリ２０４Ｅを参照した状態になったことを示している。ここで、図８Ｂに示した状態で、エントリ２０４Ｆの領域がオブジェクト回収部００８によって回収されることを想定する。
【００７２】
図８Ｃは、本発明の第１の実施の形態のカーソル１２０に対応する連結リストから、オブジェクト回収部００８によってエントリ２０４Ｆが削除された場合を示す図である。
【００７３】
図８Ｃでは、エントリ２０４Ｆの領域が回収された状態を示している。この状態で、オブジェクト回収部００８はエントリ２０４Ｅの次エントリ２１１にエントリ２０４Ｇのポインタを設定する。なお、エントリ２０４Ｆの領域が回収された時点で、エントリ２０４Ｆの次エントリ２１１は必ずしも他の値に更新されているとは限らない。
【００７４】
さらに、回収されたエントリ２０４Ｆの領域が再利用される際に、オブジェクト挿入部００５がエントリ２０４Ｆの次エントリ２１１の値を他のエントリ２０４Ｉを指すように変更する場合が想定される。
【００７５】
図８Ｄは、本発明の第１の実施の形態のエントリ２０４Ｆが削除された後に、オブジェクト挿入部００５によって再利用され、他のエントリに連結された場合を示す図である。
【００７６】
図８Ｄに示す状態では、オブジェクト参照部００７がカレントエントリ１０４に対応するエントリ２０４Ｆの次エントリ２１１を参照してもエントリ２０４Ｇに到達することができず、さらには、カーソルが到達すべきエントリ２０４Ｈに到達することができないことがわかる。
【００７７】
ここで、図８Ｃから図８Ｄの遷移において、エントリ２０４Ｆの次エントリがエントリ２０４Ｉを参照するように変更することは、セットアンカ２０１Ｂから連結される連結リストによって構成されるセットＢにエントリ２０４Ｆを挿入する手順の一部である。この場合、前述したように、オブジェクト挿入部００５はエントリ２０４Ｆの挿入時刻シーケンス２１２に値が設定する。このとき、エントリ２０４Ｆに付与された新しい挿入時刻シーケンス２１２（γ）は、エントリ２０４Ｅの挿入時刻シーケンス２１２（β）よりも新しいことが保証されている。したがって、オブジェクトを逐次参照しているスレッドにおいて、オブジェクト参照部００７は前エントリ１０３に対応するエントリ２０４Ｅの挿入時刻シーケンス属性（β）よりもカレントエントリ１０４に対応するエントリ２０４Ｆの挿入時刻シーケンス属性（γ）の方が新しくなっていることによって、カレントエントリ１０４に対応するエントリ２０４Ｆの領域が再利用されたことを検知することができる。
【００７８】
図８Ｅは、本発明の第１の実施の形態の削除されたエントリ２０４Ｆが再利用されたことを検知した後にオブジェクト参照部００７がカレントエントリ１０４を移動させた状態を示す図である。
【００７９】
オブジェクト参照部００７は、エントリ２０４Ｆの領域が再利用されたことを検知すると、前エントリ１０３をカーソル１２０のカーソル位置エントリ１２３とし、さらに、カレントエントリ１０４をカーソル１２０のカーソル位置エントリ１２３に対応するエントリ２０４の次エントリ２１１として、連結リストの走査を再実行する。これにより、最悪でもエントリ２０４Ｃとエントリ２０４Ｈの間に存在する無効ノード数だけリスト走査を再実行することで、次にカーソルが到達すべき有効なエントリ２０４Ｈに到達することができる。
【００８０】
次に、本発明の第１の実施の形態のデータ管理方法の処理について説明する。オブジェクトの挿入手順、削除手順、参照手順、及び、オブジェクト領域の回収手順の説明に先立って、システム時刻シーケンスの取得手順について説明する。
【００８１】
図１４は、本発明の第１の実施の形態のシステム時刻シーケンスを取得する手順を示すフローチャートである。
【００８２】
プロセッサ０２１は、システム時刻シーケンス取得手順が開始されると（Ｓ３９１）、まず、スレッドコンテクスト００３の直前時刻シーケンス１１２にカウンタ０１３の値を代入する（Ｓ３９２）。次に、現在時刻シーケンス１１３に直前時刻シーケンス１１２の値に１を足したものを代入する（Ｓ３９３）。
【００８３】
プロセッサ０２１は、以下の処理をスケジューラによるスレッドのコンテクストスイッチ又は他のプロセッサで実行されるスレッドによって分離されることの無いアトミックな１ステップとして実行する。まず、カウンタ０１３の値が直前時刻シーケンス１１２の値と同じ、すなわち、カウンタ０１３の値がＳ３９２の処理から変化していないことをチェックし、変化がなければカウンタ０１３を現在時刻シーケンス１１３の値で更新する（Ｓ３９４）。ここで、カウンタ０１３の値が直前時刻シーケンス１１２の値と異なった場合には、カウンタ０１３の値を更新せずに、Ｓ３９４の処理が失敗したものとする。Ｓ３９４の処理は、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐなどのｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅ命令と呼ばれるプロセッサインストラクションによってアトミックに実行される。
【００８４】
次に、プロセッサ０２１は、Ｓ３９４の処理でｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅ命令が成功したか否かを判定する（Ｓ３９５）。Ｓ３９４の処理が失敗であった場合には（Ｓ３９５の結果が「Ｎｏ」）、Ｓ３９２を実行し、成功するまでＳ３９２、Ｓ３９３、Ｓ３９４及びＳ３９５の処理を繰り返す。
【００８５】
プロセッサ０２１は、Ｓ３９４の処理が成功した場合には（Ｓ３９５の結果が「Ｙｅｓ」）、現在時刻シーケンス変数の値をシステム時刻シーケンスとして返却し、システム時刻シーケンス取得手順を終了する（Ｓ３９６）。
【００８６】
次に、セットにオブジェクトを挿入する手順について説明する。
【００８７】
図１１は、本発明の第１の実施の形態のセットにオブジェクト２１４を挿入する手順を示すフローチャートである。
【００８８】
プロセッサ０２１は、アプリケーションプログラム００４によって、セットにオブジェクト２１４を挿入する要求を受け付けると、データ管理手段のオブジェクト挿入部００５を実行し、オブジェクト挿入手順を開始する（Ｓ３４１）。
【００８９】
プロセッサ０２１は、最初に、エントリヒープからフリーリストに含まれるエントリ２０４を１つ取得する（Ｓ３４２）。具体的には、フリーアンカ２０２に対応するエントリ２０４を取得する。このとき、フリーアンカ２０２に対応するエントリ２０４のフリー次エントリ２１５をフリーアンカ２０２に設定する。
【００９０】
プロセッサ０２１は、フリーリストから取得されたエントリ２０４のアドレスをスレッドコンテクスト００３のカレントエントリ１０４に格納する（Ｓ３４３）。以降、フリーリストから取得されたエントリ２０４をカレントエントリと呼ぶ。なお、本発明の第１の実施の形態では、エントリ２０４に内包されるオブジェクト２１４のフリー領域も同時に確保される。
【００９１】
プロセッサ０２１は、カレントエントリの削除時刻シーケンス２１３を無効値で初期化し、アプリケーションプログラム００４からの挿入要求データをオブジェクト２１４に代入する（Ｓ３４４）。
【００９２】
プロセッサ０２１は、スレッドコンテクスト００３の次エントリ１０５にセットアンカ２０１の値を格納する（Ｓ３４５）。さらに、システム時刻シーケンス生成部００９から時刻シーケンスを取得し、カレントエントリの挿入時刻シーケンス２１２に代入する（Ｓ３４６）。次に、カレントエントリの次エントリ２１１にスレッドコンテクスト００３の次エントリ１０５の値を代入する（Ｓ３４７）。
【００９３】
続いて、プロセッサ０２１は、以下のステップをシステム時刻シーケンス取得時の図１４のＳ３９４の処理と同様にアトミックな操作として実行する。まず、セットアンカ２０１の値が次エントリ１０５の値と同じ、すなわち、Ｓ３４５の処理後、セットアンカ２０１の値が変化していないことをチェックし、セットアンカ２０１をカレントエントリのアドレスで更新する（Ｓ３４８）。
【００９４】
プロセッサ０２１は、Ｓ３４８の処理が成功したか否かを判定する（Ｓ３４９）。Ｓ３４８の処理が失敗した場合には（Ｓ３４９の結果が「Ｎｏ」）、Ｓ３４５、Ｓ３４６、Ｓ３４７、Ｓ３４８及びＳ３４９の処理を成功するまで再度実行する。
【００９５】
プロセッサ０２１は、Ｓ３４８の処理が成功した場合には（Ｓ３４９の結果が「Ｙｅｓ」）、オブジェクト挿入手順を完了する（Ｓ３５０）。
【００９６】
以上のオブジェクト挿入手順によって、セットに対応する連結リストにおいて、各エントリの挿入時刻シーケンス２１２が連結リストの先頭から末尾に向けて現在から過去に変化するように保たれる。
【００９７】
次に、セットからのオブジェクトを削除する手順について説明する。
【００９８】
図１２は、本発明の第１の実施の形態のセットからオブジェクト２１４を削除する手順を示すフローチャートである。
【００９９】
プロセッサ０２１は、アプリケーションプログラム００４によって、セットからオブジェクト２１４を削除する要求を受け付けると、データ管理手段のオブジェクト削除部００６を実行し、オブジェクト削除手順を開始する（Ｓ３６１）。
【０１００】
プロセッサ０２１は、まず、カーソル１２０によって削除対象のオブジェクト２１４に対応するエントリ２０４を取得する。削除対象のオブジェクト２１４に対応するエントリ２０４は、この時点で、カーソル１２０のカーソル位置エントリ１２３に対応している。そして、システム時刻シーケンス生成部００９から現在時刻シーケンスを取得し、取得されたエントリ２０４の削除時刻シーケンス２１３に代入することによって（Ｓ３６２）、セットからのオブジェクトの削除を完了する（Ｓ３６３）。
【０１０１】
なお、該当する削除対象のオブジェクト２１４及び対応するエントリ２０４は、オブジェクト削除手順とは非同期に実行されるオブジェクト領域回収手順によって、セットに対応する連結リストから実際に分離される。
【０１０２】
次に、セットに対応する連結リストから削除済みエントリの領域を再利用のために回収するオブジェクト領域回収手順について説明する。
【０１０３】
図１３は、本発明の第１の実施の形態の削除済みエントリを再利用するために領域を回収する手順を示すフローチャートである。
【０１０４】
プロセッサ０２１は、何らかの契機によって削除済みエントリの領域の回収を開始する（Ｓ３７１）。本発明の第１の実施の形態では、ハードウェア時計を利用したインターバルタイマーによって定期的に処理が開始されるものとする。その他、エレメント・オブジェクトヒープの利用状況に関する統計情報を取得及び監視し、一定の境界条件を超えることを契機としてもよいし、オブジェクト挿入においてフリーなオブジェクト領域を確保しようとした際にフリーな領域が不足したことを検知することを契機としてもよい。
【０１０５】
次に、プロセッサ０２１は、オブジェクト領域回収スレッドのスレッドコンテクスト００３における最早参照時刻シーケンス１１０をシステム時刻シーケンス生成部００９から取得した現在のシステム時刻シーケンスで初期化する（Ｓ３７２）。
【０１０６】
続いて、プロセッサ０２１は、カーソルプール０１５に含まれるすべてのカーソル１２０について、最早参照時刻シーケンス１１０を設定するために、以下の処理を実行する（Ｓ３７３）。以下、ループの中で参照されるカーソルをカレントカーソルとする。
【０１０７】
プロセッサ０２１は、カレントカーソルの参照時刻シーケンス１２１をスレッドコンテクスト００３の参照時刻シーケンス１１１に代入する（Ｓ３７４）。次に、最早参照時刻シーケンス１１０が参照時刻シーケンス１１１よりも遅いか否かを判定する（Ｓ３７５）。
【０１０８】
プロセッサ０２１は、最早参照時刻シーケンス１１０が参照時刻シーケンス１１１よりも遅い場合には（Ｓ３７５の結果が「Ｙｅｓ」）、最早参照時刻シーケンス１１０に参照時刻シーケンス１１１の値を代入する（Ｓ３７６）。最早参照時刻シーケンス１１０が参照時刻シーケンス１１１よりも遅くない場合には（Ｓ３７５の結果が「Ｎｏ」）、Ｓ３７６の処理をスキップする。そして、ループ内の一連の処理を終了し（Ｓ３７７）、Ｓ３７３の処理に戻る。Ｓ３７３からＳ３７７の処理によって、オブジェクト領域回収手順の実行開始時点で、カーソルプール０１５に含まれるすべてのカーソルの中で最も早い参照時刻シーケンスが最早参照時刻シーケンス１１０に格納される。
【０１０９】
続いて、プロセッサ０２１は、スレッドコンテクスト００３の前エントリ１０３にセットアンカ２０１の値を代入する（Ｓ３７８）。そして、Ｓ３７８の処理で代入された前エントリ１０３の値がｎｕｌｌでないか否かを判定する（Ｓ３７９）。前エントリ１０３の値がｎｕｌｌの場合には（Ｓ３７９の結果が「Ｎｏ」）、オブジェクト領域回収手順を終了する（Ｓ３８８）。
【０１１０】
プロセッサ０２１は、前エントリ１０３の値がｎｕｌｌでない場合には（Ｓ３７９の結果が「Ｙｅｓ」）、前エントリ１０３に対応するエントリ２０４の次エントリ２１１の値を、カレントエントリ１０４に代入する（Ｓ３８０）。
【０１１１】
プロセッサ０２１は、Ｓ３８０の処理で代入されたカレントエントリ１０４の値がｎｕｌｌでないか否かを判定する（Ｓ３８１）。カレントエントリ１０４の値がｎｕｌｌの場合には（Ｓ３７９の結果が「Ｎｏ」）、オブジェクト領域回収手順を終了する（Ｓ３８８）。カレントエントリ１０４の値がｎｕｌｌでない場合には（Ｓ３７９の結果が「Ｙｅｓ」）、カレントエントリ１０４に対応するエントリ２０４の次エントリ２１１の値を、次エントリ１０５に代入する（Ｓ３８２）。
【０１１２】
次に、プロセッサ０２１は、カレントエントリ１０４の削除時刻シーケンス２１３の値が有効、かつ、カレントエントリ１０４の削除時刻シーケンス２１３が最早参照時刻シーケンス１１０よりも早いか否かを判定する（Ｓ３８３）。
【０１１３】
プロセッサ０２１は、カレントエントリ１０４の削除時刻シーケンス２１３の値が有効、かつ、カレントエントリ１０４の削除時刻シーケンス２１３が最早参照時刻シーケンス１１０よりも早い場合には（Ｓ３８３の結果が「Ｙｅｓ」）、前エントリ１０３に対応するエントリ２０４の次エントリ２１１に、次エントリ１０５の値を代入する（Ｓ３８４）。Ｓ３８４の処理によって、削除済み状態であるカレントエントリ１０４が連結リストから分離される。続いて、連結リストから分離されたカレントエントリ１０４をフリーアンカ２０２に連結されたフリーリストに連結する（Ｓ３８５）。
【０１１４】
プロセッサ０２１は、カレントエントリ１０４の削除時刻シーケンス２１３が無効値、又は、カレントエントリ１０４の削除時刻シーケンス２１３が最早参照時刻シーケンス１１０よりも遅い場合には（Ｓ３８３の結果が「Ｎｏ」）、前エントリ１０３にカレントエントリ１０４の値を代入する（Ｓ３８６）。
【０１１５】
プロセッサ０２１は、Ｓ３８５又はＳ３８６の処理が終了すると、カレントエントリ１０４に次エントリ１０５の値を代入し（Ｓ３８７）、Ｓ３８１の処理に戻る。
【０１１６】
なお、本発明の第１の実施の形態では、最早参照時刻シーケンスをカーソルプール０１５に含まれるカーソルから取得したが、必ずしもその必要はない。オブジェクト領域回収スレッドにおいて、オブジェクト逐次参照を行う参照スレッドの参照時刻シーケンスを取得することによって、領域回収の候補となっているエントリ２０４がすべての参照スレッドにとっても無効エントリであることを確認できればよい。
【０１１７】
次に、図９を参照しながら、セット内のオブジェクトを逐次参照するためのカーソル１２０の初期化手順について説明する。
【０１１８】
図９は、本発明の第１の実施の形態のセット内のオブジェクトを逐次参照するためのカーソル１２０を初期化する手順を示すフローチャートである。
【０１１９】
プロセッサ０２１は、まず、アプリケーションプログラム００４によって、セット内のオブジェクトが逐次参照するためのカーソル１２０を生成し、オブジェクト参照部００７を実行することによって、当該カーソル１２０を初期化する。カーソル初期化要求を受け付けると、オブジェクト参照部００７によって、カーソル初期化手順を開始する（Ｓ３０１）。
【０１２０】
プロセッサ０２１は、次に、カーソル１２０のセットアンカ１２２に走査対象であるセットに対応する連結リストの先頭エントリであるセットアンカ２０１の値を設定する。さらに、カーソル位置エントリ１２３に無効なアドレスｎｕｌｌ、参照時刻シーケンス１２１に無効値を設定することによって初期化する。また、アプリケーションプログラム００４によってセット内のオブジェクトを選択的に参照するための探索条件が指定されている場合には、探索条件１２４に指定された探索条件を設定する（Ｓ３０２）。以上の処理で、カーソル初期化手順は完了する（Ｓ３０３）。
【０１２１】
次に、初期化されたカーソル１２０を用いてセット内のオブジェクトを１つずつ参照する手順を説明する。
【０１２２】
図１０は、本発明の第１の実施の形態のカーソル１２０によってセット内のオブジェクトを参照する手順を示すフローチャートである。
【０１２３】
プロセッサ０２１は、アプリケーションプログラム００４によって、オブジェクト逐次参照要求を受け付けると、オブジェクト参照部００７を実行し、オブジェクト逐次参照手順を開始する（Ｓ３２０）。最初にオブジェクト逐次参照手順が呼び出される前に、カーソル１２０は初期化されているものとする。
【０１２４】
プロセッサ０２１は、まず、システム時刻シーケンス生成部００９からシステム時刻シーケンスを取得し、スレッドコンテクスト００３の参照時刻シーケンス１１１に代入する（Ｓ３２１）。続いて、カーソル１２０のカーソル位置エントリ１２３の値がｎｕｌｌであるか否かを判定する（Ｓ３２２）。
【０１２５】
プロセッサ０２１は、カーソル１２０のカーソル位置エントリ１２３の値がｎｕｌｌの場合には（Ｓ３２２の結果が「Ｙｅｓ」）、スレッドコンテクスト００３のカレントエントリ１０４に該当カーソル１２０のセットアンカ１２２の値を代入し、前エントリ挿入時刻シーケンス１０６に無効値を代入する（Ｓ３２３）。カーソル初期化後、本処理が最初に実行された場合には、カーソル位置エントリ１２３の値がｎｕｌｌであるため、Ｓ３２３の処理が実行される。
【０１２６】
一方、カーソル初期化直後でない場合には、カーソル位置エントリ１２３の値がｎｕｌｌでないため（Ｓ３２２の結果が「Ｎｏ」）、プロセッサ０２１は、スレッドコンテクスト００３のカレントエントリ１０４に、カーソル１２０のカーソル位置エントリ１２３に対応するエントリ２０４の次エントリ２１１の値を代入する。さらに、前エントリ挿入時刻シーケンス１０６に該当カーソル１２０のカーソル位置エントリ１２３に対応するエントリ２０４の挿入時刻シーケンス２１２の値を代入する（Ｓ３２４）。
【０１２７】
プロセッサ０２１は、次に、カレントエントリ１０４の値がｎｕｌｌか否かを判定する（Ｓ３２５）。カレントエントリ１０４の値がｎｕｌｌの場合には（Ｓ３２５の結果が「Ｙｅｓ」）、カーソル１２０の参照時刻シーケンス１２１をＳ３２１の処理で取得された時刻シーケンスである参照時刻シーケンス１１１の値で更新し、カーソル位置エントリ１２３にカレントエントリ１０４の値を代入し（Ｓ３３１）、オブジェクト逐次参照手順を終了する（Ｓ３３２）。
【０１２８】
プロセッサ０２１は、カレントエントリ１０４の値がｎｕｌｌでない場合には（Ｓ３２５の結果が「Ｎｏ」）、スレッドコンテクスト００３の次エントリ１０５にカレントエントリの次エントリ２１１の値を代入し、カレントエントリ削除時刻シーケンス１０８にカレントエントリの削除時刻シーケンス２１３の値を代入する（Ｓ３２６）。
【０１２９】
プロセッサ０２１は、カレントエントリ挿入時刻シーケンス１０７にカレントエントリの挿入時刻シーケンス２１２の値を代入する（Ｓ３２７）。Ｓ３２７の処理では、Ｓ３２６の処理で参照されたカレントエントリの領域が回収され、かつ、再利用されていないことを判定する目的でカレントエントリ挿入時刻シーケンス１０７が設定する。そのため、プラットフォームによっては、Ｓ３２６の処理とＳ３２７の処理との実行順序が実行時の最適化によって、変更されないようにフェンス命令と呼ばれる特殊なプロセッサインストラクションを必要とする場合がある。
【０１３０】
プロセッサ０２１は、前エントリ挿入時刻シーケンス１０６が無効値でなく、かつ、前エントリ挿入時刻シーケンス１０６がカレントエントリ挿入時刻シーケンス１０７よりも早い否かを判定する（Ｓ３２８）。前エントリ挿入時刻シーケンス１０６無効値でなく、かつ、前エントリ挿入時刻シーケンス１０６がカレントエントリ挿入時刻シーケンス１０７よりも早い場合には（Ｓ３２８の結果が「Ｙｅｓ」）、カレントエントリがセットに対応する連結リストから分離され、再利用されたことを意味する。そこで、Ｓ３２２の処理に戻り、カーソルの移動前のエントリから連結リストを再度走査する。
【０１３１】
プロセッサ０２１は、前エントリ挿入時刻シーケンス１０６が無効値か、または、前エントリ挿入時刻シーケンス１０６がカレントエントリ挿入時刻シーケンス１０７よりも遅い場合には（Ｓ３２８の結果が「Ｎｏ」）、さらに、カレントエントリ削除時刻シーケンス１０８が無効値でなく、かつ、参照時刻シーケンス１１１よりも早いか否かを判定する（Ｓ３２９）。
【０１３２】
カレントエントリ削除時刻シーケンス１０８が無効値でなく、かつ、参照時刻シーケンス１１１よりも早い場合には（Ｓ３２９の結果が「Ｙｅｓ」）、カレントエントリは、オブジェクトが削除されたために該当カーソルから参照できなくなった無効エントリである。そこで、プロセッサ０２１は、前エントリ挿入時刻シーケンス１０６にカレントエントリ挿入時刻シーケンス１０７の値を代入し、カレントエントリ１０４に次エントリ１０５の値を挿入し（Ｓ３３０）、Ｓ３２５以降の処理をさらに実行する。
【０１３３】
カレントエントリ削除時刻シーケンス１０８が無効値、又は、参照時刻シーケンス１１１よりも早くない場合には（Ｓ３２９の結果が「Ｎｏ」）、カレントエントリがカーソル１２０のカーソル位置エントリ１２３となる。このとき、カーソル１２０の参照時刻シーケンス１２１をＳ３２１の処理で取得された時刻シーケンスである参照時刻シーケンス１１１の値で更新する（Ｓ３３１）。さらに、カレントエントリのオブジェクト２１４の参照をアプリケーションプログラム００４に返却し、オブジェクト逐次参照手順を終了する（Ｓ３３２）。
【０１３４】
なお、本発明の第１の実施の形態では、オブジェクトの逐次参照要求ごとに該当カーソル１２０の参照時刻シーケンス１２１を更新したが、カーソル初期化時に１回だけ、参照時刻シーケンス１２１を更新してもよい。この場合、カーソル１２０の初期化後に削除されたオブジェクト２１４に対応するエントリ２０４は、該当カーソル１２０においてすべて有効なオブジェクトとなる。
【０１３５】
本発明の第１の実施の形態によれば、カーソルを用いたオブジェクトの逐次参照において、相互排他ロックの取得、アトミックなｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅインストラクションの実行、及び、スレッドの状態履歴の取得を行う必要が無いため、オブジェクトを参照するための処理コストを低くすることができ、高いレスポンス性能が得ることができる。
【０１３６】
本発明の第１の実施の形態によれば、削除済みエントリで使用されている領域を回収する場合に、相互排他ロック、及び、他のスレッドの状態履歴確認を行う必要がなく、オブジェクトの回収に必要な処理コストを低くすることができる。また、カーソルを用いたオブジェクトの逐次参照が削除済みエントリの領域回収、再利用の並行実行を妨げないため、メモリの利用効率を高くすることができる。
【０１３７】
本発明の第１の実施の形態によれば、オブジェクトの削除、削除済みエントリの領域回収、及び、再利用がカーソルを用いたオブジェクトの逐次参照の並行実行を妨げないため、参照アプリケーションの高いスループットを得ることができる。
【０１３８】
本発明の第１の実施の形態によれば、カーソルを用いたオブジェクトの逐次参照において、スレッド間の同時実行性を損なう相互排他ロック取得しない。したがって、マルチスレッド環境において、参照アプリケーションの高いスループットを得ることができる。
【０１３９】
本発明の第１の実施の形態によれば、カーソルを用いたオブジェクトの逐次参照において、共有メモリ型マルチプロセッサ（マルチコアプロセッサを含む）コンピュータシステムのシステムバスを占有してプロセッサ間の同実行性を損なうアトミックなｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅインストラクションを実行しない。そのため、プロセッサコアの利用効率が向上し、参照アプリケーションの高いスループットを得ることができる。
【０１４０】
（第２の実施の形態）
本発明の第２の実施の形態では、Ｍｕｌｔｉ  Ｖｅｒｓｉｏｎ  Ｃｏｎｃｕｒｒｅｎｔ  Ｃｏｎｔｒｏｌ（ＭＶＣＣ）によるトランザクションの同時実行制御がなされるシステムに本発明を適用する。
【０１４１】
トランザクションとは、アプリケーションプログラムがデータ群に対する一連の参照、挿入、更新及び削除が一貫性を持って行われる単位である。ＭＶＣＣでは、トランザクションが一貫性を持ってデータの挿入、更新、削除を行われることを前提に、当該データを参照する他のトランザクションは、挿入、更新、削除が確定しているトランザクション開始時点で最新のデータ集合を参照できることが特徴である。このため、ＭＶＣＣでオブジェクトを更新又は削除する場合は、更新又は削除後の新しい版とは別に更新削除前の古い版をトランザクションが参照する可能性がなくなるまで保持する。
【０１４２】
なお、第２の実施の形態において、第１の実施の形態と共通する内容については適宜説明を省略する。例えば、図２に示したハードウェアモジュール、ソフトウェアモジュール及び両者の関係は、本発明の第２の実施の形態においても同様である。
【０１４３】
図１５は、本発明の第２の実施の形態のデータ管理システムにおけるソフトウェアモジュール構成図である。
【０１４４】
アプリケーションプログラム００４、オブジェクト挿入部００５、オブジェクト削除部００６、オブジェクト参照部００７、オブジェクト領域回収部００８、システム時刻シーケンス生成部００９、エントリヒープ０１０、プログラム格納部０１１、データ格納部０１２、カウンタ０１３、アプリケーション用のデータ０１４、及び、カーソルプール０１５については、図１に示した第１の実施の形態と同様である。
【０１４５】
本発明の第２の実施の形態では、第１の実施の形態のソフトウェアモジュールの構成に加え、オブジェクト更新部４０１、トランザクション制御部４０２、及び、トランザクションプール４０３が含まれる。
【０１４６】
オブジェクト更新部４０１は、アプリケーションプログラム００４の要求を受け付け、エントリヒープ０１０内のカーソル１２０のカーソル位置エントリ１２３に対応するオブジェクトを更新するための手順を実行するソフトウェアモジュールである。
【０１４７】
トランザクション制御部４０２は、アプリケーションプログラム００４の要求を受け付け、トランザクションの開始及び終了などを制御する手順を実行するソフトウェアモジュールである。
【０１４８】
トランザクションプール４０３は、トランザクションの状態が保持されるトランザクション管理ブロックを管理する領域である。トランザクションプール４０３には、データ管理手段にアクセスするすべてのトランザクションに関するすべてのトランザクション管理ブロックが格納される。
【０１４９】
図１６Ａは、本発明の第２の実施の形態のトランザクションプール４０３内で管理されるトランザクション管理ブロック４１０の構成例を示す図である。
【０１５０】
トランザクション開始時刻シーケンス４１１は、該当するトランザクションを開始した時点のシステム時刻シーケンスを保持する。
【０１５１】
更新オブジェクト一覧４１２は、該当トランザクションにおいて挿入、更新又は削除したオブジェクトの一覧を保持する。具体的には、トランザクションにおいて挿入、更新又は削除したオブジェクトに対応するエントリ２０４のアドレスを連結リストで保持する形式を想定するが、オブジェクト集合を保持する方法はエントリ２０４へのポインタ変数の配列など、他の方法であってもよい。
【０１５２】
さらに、トランザクション管理ブロック４１０には、トランザクション状態４１３が含まれてもよい。
【０１５３】
図１６Ｂは、本発明の第２の実施の形態のデータ格納部０１２に格納されるエントリ２０４の構成例を示す図である。
【０１５４】
本発明の第２の実施の形態では、エントリ２０４は、一又は複数の版２３６及び一又は複数の版エントリ２３２によって構成される。
【０１５５】
各エントリ２０４について、次エントリ２１１、挿入時刻シーケンス２１２、及び、フリー次エントリ２１５は、図６に示した第１の実施の形態と同じである。第２の実施の形態では、エントリ２０４のメンバ変数に最新版エントリポインタ２３１が追加される。最新版エントリポインタ２３１は、最新の版に対応する版エントリ２３２のアドレスを格納するポインタ変数である。
【０１５６】
版エントリ２３２は、オブジェクトの挿入時に一つ作成され、オブジェクトが更新されるごとに追加される。版エントリ２３２は、版確定時刻シーケンス２３３、旧版エントリ２３４及び版ポインタ２３５をメンバ変数として含む。
【０１５７】
版２３６は、対応する版エントリ２３２の版ポインタ２３５によって参照される。すなわち、版ポインタ２３５は、対応する版２３６のアドレスを格納するポインタ変数である。
【０１５８】
また、版エントリ２３２は、エントリ２０４の最新版エントリポインタ２３１をアンカとし、版確定時刻シーケンス２３３の値の降順に旧版エントリ２３４によって連結された連結リストを構成する。旧版エントリ２３４は、最新版でない旧版に対応する版エントリ２３２のアドレスを格納するポインタ変数である。なお、オブジェクト削除時には、対応する版をもたない削除を表す版エントリ２３２を連結リストの先頭に追加する。
【０１５９】
版確定時刻シーケンス２３３は、挿入、更新、削除を実行したトランザクションがコミットした時点のシステム時刻シーケンスである。また、版２３６を参照しない削除を表す版エントリ２３２の版確定時刻シーケンス２３３は、対応するエントリ２０４の削除時刻シーケンスとなる。
【０１６０】
図１６Ｂに示した例では、まず、版エントリ２３２Ｃに対応する版２３６Ｃの値でオブジェクトがセットに挿入され、続いて、版エントリ２３２Ｂに対応する版２３６Ｂの値でオブジェクトが更新されている。さらに、版エントリ２３２Ａが版２３６を参照していないため、最後には削除されたことを示している。
【０１６１】
なお、データ管理手段のデータ格納部０１２におけるデータ格納形式は、図５に示した本発明の第１の実施の形態と同様である。
【０１６２】
ここで、削除済みエントリであって、かつ、参照トランザクションのトランザクション開始時刻シーケンスよりも前の削除時刻シーケンスを有するエントリを、当該トランザクションにおける無効エントリとする。他方、連結リストを構成するエントリ２０４であって、無効エントリでないエントリ２０４を、当該トランザクションにおける有効エントリとする。
【０１６３】
エントリヒープ２０３には、セットに対応する連結リストを構成しないエントリ２０４も共存している。本発明の第２の実施の形態では、第１の実施の形態と同様に、セットに対応する連結リストを構成しないエントリ２０４をフリーリストと呼ばれる連結リストによって管理する。
【０１６４】
版エントリ２３２及び版２３６についても、エントリ２０４と同様のフリーリストによって領域を管理するのが一般的であるが、本発明の第２の実施の形態では、版エントリ２３２及び版２３６の領域管理をＯＳ及びプログラミング言語実行環境が行うものとし、詳細には言及しない。
【０１６５】
本発明の第２の実施の形態のカーソル１２０及びスレッドコンテクスト００３の構成は、第１の実施の形態と同様であり、図４及び図３に示したとおりである。
【０１６６】
ここで、本発明の第２の実施の形態のデータ管理方法の処理について説明する。
【０１６７】
システム時刻シーケンスを取得する手順は、第１の実施の形態と同様であり、図１４に示したとおりである
次に、トランザクションを開始する手順について説明する。
【０１６８】
図１７は、本発明の第２の実施の形態のトランザクションを開始する手順を示すフローチャートである。
【０１６９】
プロセッサ０２１は、アプリケーションプログラム００４によってトランザクション開始要求を受け付けると、トランザクション制御部４０２を実行し、トランザクション開始手順を開始する（Ｓ５０１）。
【０１７０】
プロセッサ０２１は、まず、トランザクションプール４０３からトランザクション管理ブロック４１０を取得する（Ｓ５０２）。次に、取得されたトランザクション管理ブロック４１０の更新オブジェクト一覧４１２を初期化する（Ｓ５０３）。
【０１７１】
プロセッサ０２１は、システム時刻シーケンス生成部００９からシステム時刻シーケンスを取得し、トランザクション開始時刻シーケンス４１１に代入する（Ｓ５０４）。次に、トランザクション状態４１３をトランザクション実行中状態に設定し（Ｓ５０５）、トランザクション開始手順を終了する（Ｓ５０６）。
【０１７２】
次に、トランザクションを終了する手順について説明する。
【０１７３】
図１８は、本発明の第２の実施の形態のトランザクションを終了する手順を示すフローチャートである。
【０１７４】
プロセッサ０２１は、アプリケーションプログラム００４によってトランザクション終了要求を受け付けると、トランザクション制御部４０２を実行し、トランザクション終了手順を開始する（Ｓ５１１）。
【０１７５】
プロセッサ０２１は、まず、システム時刻シーケンス生成部００９からシステム時刻シーケンスを取得し、現在時刻シーケンス１１３に格納する。続いて、更新オブジェクト一覧４１２に含まれるすべてのオブジェクトに対応するエントリ２０４の更新確定時刻シーケンスを更新するループを実行する（Ｓ５１３）。エントリ２０４の更新確定時刻シーケンスとは、エントリ２０４の最新版エントリの版確定時刻シーケンス２３３に対応する。各オブジェクトに対応するエントリ２０４から最新版エントリポインタ２３１に対応する最新の版エントリ２３２の版確定時刻シーケンス２３３に現在時刻シーケンス１３３の値を代入し（Ｓ５１４）、ループの先頭に戻る（Ｓ５１５）。
【０１７６】
プロセッサ０２１は、更新オブジェクト一覧４１２に含まれるすべてのオブジェクトに対応するエントリ２０４の更新確定時刻シーケンスの更新が完了すると、更新オブジェクト一覧４１２に含まれるエントリ２０４を開放する（Ｓ５１６）。さらに、トランザクション状態４１３をトランザクション終了状態に変更する（Ｓ５１７）。最後に、該当トランザクション管理ブロック４１０を開放し（Ｓ５１８）、トランザクション終了手順を完了する（Ｓ５１９）。
【０１７７】
次に、セットにオブジェクトを挿入する手順について説明する。
【０１７８】
図２１は、本発明の第２の実施の形態のセットにオブジェクトを挿入する手順を示すフローチャートである。
【０１７９】
プロセッサ０２１は、アプリケーションプログラム００４によって、セットにオブジェクト２１４を挿入する要求を受け付けると、データ管理手段のオブジェクト挿入部００５を実行し、オブジェクト挿入手順を開始する（Ｓ５６１）。
【０１８０】
プロセッサ０２１は、最初に、エントリヒープからフリーリストに含まれるエントリ２０４を１つ取得する（Ｓ５６２）。具体的には、フリーアンカ２０２に対応するエントリ２０４を取得する。このとき、フリーアンカ２０２に対応するエントリ２０４のフリー次エントリ２１５をフリーアンカ２０２に設定する。
【０１８１】
プロセッサ０２１は、フリーリストから取得したエントリ２０４のアドレスをスレッドコンテクスト００３のカレントエントリ１０４に格納する（Ｓ５６３）。以降、フリーリストから取得されたエントリ２０４をカレントエントリとする。さらに、版エントリ２３２及び版２３６の領域をＯＳによってエントリヒープ０１０に割り当てる（Ｓ５６４）。
【０１８２】
続いて、プロセッサ０２１は、取得した版エントリ２３２を初期化する。具体的には、まず、版エントリ２３２の版ポインタ２３５に版２３６のアドレスを代入する。さらに、版確定時刻シーケンス２３３を無効値、旧版エントリをｎｕｌｌで初期化する。また、版２３６にアプリケーションプログラム００４からの挿入要求データを代入し、カレントエントリの最新版エントリポインタ２３１に版エントリ２３２のアドレスを代入する。最後に、カレントエントリをトランザクション管理ブロック４１０の更新オブジェクト一覧４１２に対応する連結リストに追加する（Ｓ５６５）。
【０１８３】
プロセッサ０２１は、スレッドコンテクスト００３の次エントリ１０５にセットアンカ２０１の値を格納する（Ｓ５６６）。さらに、システム時刻シーケンス生成部００９から時刻シーケンスを取得し、カレントエントリの挿入時刻シーケンス２１２に代入する（Ｓ５６７）。次に、カレントエントリの次エントリ２１１にスレッドコンテクスト００３の次エントリ１０５の値を代入する（Ｓ５６８）。
【０１８４】
続いて、プロセッサ０２１は、以下のステップをシステム時刻シーケンス取得時のＳ３９４と同様にアトミックな操作として実行する。まず、セットアンカ２０１が次エントリ１０５の値と同じ、すなわち、Ｓ３４５の処理後、セットアンカ２０１が変化していないことをチェックし、セットアンカ２０１をカレントエントリのアドレスで更新する（Ｓ５６９）。
【０１８５】
プロセッサ０２１は、Ｓ５６９の処理が成功したか否かを判定する（Ｓ５７０）。Ｓ３４８の処理が失敗した場合には（Ｓ５７０の結果が「Ｎｏ」）、Ｓ５６６、Ｓ５６７、Ｓ５６８、Ｓ５６９及びＳ５７０の処理を成功するまで再度実行する。
【０１８６】
プロセッサ０２１は、Ｓ５６９の処理が成功した場合には（Ｓ５７０の結果が「Ｙｅｓ」）、オブジェクト挿入手順を完了する（Ｓ５７１）。
【０１８７】
以上のオブジェクト挿入手順によって、セットに対応する連結リストにおいて、各エントリの挿入時刻シーケンス２１２が連結リストの先頭から末尾に向けて現在から過去に変化するように保たれる。
【０１８８】
次に、オブジェクトを更新する手順について説明する。
【０１８９】
図２２は、本発明の第２の実施の形態のオブジェクトを更新する手順を示すフローチャートである。
【０１９０】
プロセッサ０２１は、アプリケーションプログラム００４によって、セットに含まれるオブジェクトを更新する要求を受け付けると、データ管理手段のオブジェクト更新部４０１を実行し、オブジェクト更新手順を開始する（Ｓ５８１）。
【０１９１】
プロセッサ０２１は、最初に、カーソル１２０のカーソル位置エントリ１２３の値をスレッドコンテクスト００３のカレントエントリ１０４に格納する（Ｓ５８２）。以降、カレントエントリ１０４に対応するエントリ２０４をカレントエントリとする。
【０１９２】
プロセッサ０２１は、次に、版エントリ２３２及び版２３６の領域をＯＳによってエントリヒープ０１０に割り当てる（Ｓ５８３）。続いて、版エントリ２３２の版ポインタ２３５に版２３６のアドレスを代入し、版確定時刻シーケンス２３３を無効値で初期化する。また、旧版エントリ２３４にカレントエントリの最新版エントリポインタ２３１の値を代入し、版２３６にアプリケーションプログラム００４からの更新要求データを代入する。さらに、カレントエントリの最新版エントリポインタ２３１に版エントリ２３２のアドレスを代入する。最後に、トランザクション管理ブロック４１０の更新オブジェクト一覧４１２に対応する連結リストにカレントエントリを追加し（Ｓ５８４）、オブジェクト更新手順を完了する（Ｓ５８５）。
【０１９３】
次に、セットからオブジェクトを削除する手順について説明する。
【０１９４】
図２３は、本発明の第２の実施の形態のセットからオブジェクト２１４を削除する手順を示すフローチャートである。
【０１９５】
プロセッサ０２１は、アプリケーションプログラム００４によるセットからのオブジェクト削除要求によって、データ管理手段のオブジェクト削除部００６を実行し、オブジェクト削除手順を開始する（Ｓ５９１）。
【０１９６】
プロセッサ０２１は、まず、カーソル１２０によって削除対象のオブジェクト２１４に対応するエントリ２０４を取得する。削除対象のオブジェクト２１４に対応するエントリ２０４は、この時点で、カーソル１２０のカーソル位置エントリ１２３に対応している。以降、取得されたエントリをカレントエントリとする。
【０１９７】
プロセッサ０２１は、カレントエントリのアドレスをスレッドコンテクスト００３のカレントエントリ１０４に代入する（Ｓ５９２）。次に、版エントリ２３２の領域をＯＳによってエントリヒープ０１０に割り当てる（Ｓ５９３）。
【０１９８】
続いて、プロセッサ０２１は、版エントリ２３２の版ポインタ２３５をｎｕｌｌ、版確定時刻シーケンス２３３を無効値で初期化する。さらに、旧版エントリ２３４にカレントエントリの最新版エントリポインタ２３１の値を代入し、カレントエントリの最新版エントリポインタ２３１に版エントリ２３２のアドレスを代入する。最後に、カレントエントリをトランザクション管理ブロック４１０の更新オブジェクト一覧４１２に対応する連結リストに追加し（Ｓ５９４）、セットからのオブジェクトの削除を完了する（Ｓ５９５）。
【０１９９】
なお、削除対象のオブジェクト２１４及び対応するエントリ２０４は、オブジェクト削除手順とは非同期に実行されるオブジェクト領域回収手順によって、セットに対応する連結リストから実際に分離される。
【０２００】
次に、セットに対応する連結リストから削除済みエントリの領域を再利用するために回収するオブジェクト領域回収手順を説明する。
【０２０１】
図２４は、本発明の第２の実施の形態の削除済みエントリを再利用するために領域を回収する手順を示すフローチャートである。
【０２０２】
プロセッサ０２１は、ハードウェア時計を利用したインターバルタイマーによって、周期的に削除済みエントリの領域の回収を開始する（Ｓ６０１）。
【０２０３】
次に、プロセッサ０２１は、オブジェクト領域回収スレッドのスレッドコンテクスト００３における最早参照時刻シーケンス１１０をシステム時刻シーケンス生成部００９から取得した現在のシステム時刻シーケンスで初期化する（Ｓ６０２）。
【０２０４】
続いて、プロセッサ０２１は、トランザクションプール４０３に含まれるすべての使用中のトランザクション管理ブロック４１０について、最早参照時刻シーケンス１１０を設定するために、以下の処理を実行する（Ｓ６０３）。以降、ループの中で参照されるトランザクション管理ブロック４１０をカレントトランザクションとする。
【０２０５】
プロセッサ０２１は、カレントトランザクションのトランザクション開始時刻シーケンス４１１をスレッドコンテクスト００３の参照時刻シーケンス１１１に代入する（Ｓ６０４）。次に、最早参照時刻シーケンス１１０が参照時刻シーケンス１１１よりも遅いか否かを判定する（Ｓ６０５）。
【０２０６】
プロセッサ０２１は、最早参照時刻シーケンス１１０が参照時刻シーケンス１１１よりも遅い場合には（Ｓ６０５の結果が「Ｙｅｓ」）、最早参照時刻シーケンス１１０に参照時刻シーケンス１１１の値を代入する（Ｓ６０６）。最早参照時刻シーケンス１１０が参照時刻シーケンス１１１よりも遅くない場合には（Ｓ６０５の結果が「Ｎｏ」）、Ｓ６０６の処理をスキップする。そして、ループ内の一連の処理を終了し（Ｓ６０７）、Ｓ６０３の処理に戻る。Ｓ６０３からＳ６０７のループによって、オブジェクト領域回収手順の実行開始時点で、トランザクションプール４０３に含まれるすべてのトランザクションの中で最も早いトランザクション開始時刻シーケンスが最早参照時刻シーケンス１１０に格納される。
【０２０７】
続いて、プロセッサ０２１は、スレッドコンテクスト００３の前エントリ１０３にセットアンカ２０１の値を代入する（Ｓ６０８）。そして、Ｓ６０８の処理で代入された前エントリ１０３の値がｎｕｌｌでないか否かを判定する（Ｓ６０９）。前エントリ１０３の値がｎｕｌｌの場合には（Ｓ６０９の結果が「Ｎｏ」）、オブジェクト領域回収手順を終了する（Ｓ６１９）。
【０２０８】
プロセッサ０２１は、前エントリ１０３の値がｎｕｌｌでない場合には（Ｓ６０９の結果が「Ｙｅｓ」）、前エントリ１０３に対応するエントリ２０４の次エントリ２１１の値を、カレントエントリ１０４に代入する（Ｓ６１０）。
【０２０９】
プロセッサ０２１は、Ｓ６１０の処理で代入されたカレントエントリ１０４の値がｎｕｌｌでないか否かを判定する（Ｓ６１１）。カレントエントリ１０４の値がｎｕｌｌの場合には（Ｓ６１１の結果が「Ｎｏ」）、オブジェクト領域回収手順を終了する（Ｓ６１９）。カレントエントリ１０４の値がｎｕｌｌでない場合には（Ｓ６１１の結果が「Ｙｅｓ」）、カレントエントリ１０４に対応するエントリ２０４の次エントリ２１１の値を、次エントリ１０５に代入する（Ｓ６１２）。
【０２１０】
次に、プロセッサ０２１は、カレントエントリ１０４に対応するエントリ２０４の最新版エントリポインタ２３１に対応する版エントリ２３２（以降、カレント最新版エントリ）の版ポインタ２３５の値がｎｕｌｌ、かつ、カレント最新版エントリの版確定時刻シーケンス２３３の値が有効、かつ、カレント最新版エントリの版確定時刻シーケンス２３３が最早参照時刻シーケンス１１０よりも早いか否かを判定する（Ｓ６１３）。
【０２１１】
プロセッサ０２１は、Ｓ６１３の条件が成立する場合には（Ｓ６１３の結果が「Ｙｅｓ」）、前エントリ１０３に対応するエントリ２０４の次エントリ２１１に、次エントリ１０５の値を代入する（Ｓ６１４）。Ｓ６１４の処理によって、削除済みであるカレントエントリ１０４が連結リストから分離される。
【０２１２】
さらに、プロセッサ０２１は、カレントエントリ１０４に対応するすべての版エントリ２３２及び版２３６を開放する（Ｓ６１５）。続いて、連結リストから分離されたカレントエントリ１０４をフリーアンカ２０２に連結されるフリーリストに連結する（Ｓ６１６）。
【０２１３】
プロセッサ０２１は、Ｓ６１３の条件が成立しなかった場合には（Ｓ６１３の結果が「Ｎｏ」）、前エントリ１０３にカレントエントリ１０４の値を代入する（Ｓ６１７）。
【０２１４】
プロセッサ０２１は、Ｓ６１６又はＳ６１７の処理が終了すると、カレントエントリ１０４に次エントリ１０５の値を代入し、Ｓ６１１の処理に戻る（Ｓ６１８）。
【０２１５】
セット内のオブジェクトを逐次参照するためのカーソル１２０の初期化手順は、第１の実施の形態と同様であり、図９に示したとおりである
次に、初期化されたカーソル１２０を用いてセット内のオブジェクトを１つずつ参照する手順を説明する。
【０２１６】
図１９は、本発明の第２の実施の形態のカーソル１２０によってセット内のオブジェクトを参照する手順を示すフローチャートである。
【０２１７】
プロセッサ０２１は、アプリケーションプログラム００４によって、オブジェクト逐次参照要求を受け付けると、オブジェクト参照部００７を実行し、オブジェクト逐次参照手順を開始する（Ｓ５４１）。最初にオブジェクト逐次参照手順が呼び出される前に、カーソル１２０は初期化されているものとする。
【０２１８】
プロセッサ０２１は、まず、カーソル１２０のカーソル位置エントリ１２３の値がｎｕｌｌであるか否かを判定する（Ｓ５４２）。
【０２１９】
プロセッサ０２１は、カーソル１２０のカーソル位置エントリ１２３の値がｎｕｌｌの場合には（Ｓ５４２の結果が「Ｙｅｓ」）、スレッドコンテクスト００３のカレントエントリ１０４に該当カーソル１２０のセットアンカ１２２の値を代入し、前エントリ挿入時刻シーケンス１０６に無効値を代入する（Ｓ５４３）。カーソル初期化後、本処理が最初に実行された場合には、カーソル位置エントリ１２３の値がｎｕｌｌであるため、Ｓ５４３の処理が実行される。
【０２２０】
一方、カーソル初期化直後でない場合には、カーソル位置エントリ１２３の値がｎｕｌｌでないため（Ｓ５４２の結果が「Ｎｏ」）、プロセッサ０２１は、スレッドコンテクスト００３のカレントエントリ１０４に、カーソル１２０のカーソル位置エントリ１２３に対応するエントリ２０４の次エントリ２１１の値を代入する。さらに、前エントリ挿入時刻シーケンス１０６に該当カーソル１２０のカーソル位置エントリ１２３に対応するエントリ２０４の挿入時刻シーケンス２１２の値を代入する（Ｓ５４４）。
【０２２１】
プロセッサ０２１は、次に、カレントエントリ１０４の値がｎｕｌｌか否かを判定する（Ｓ５４５）。カレントエントリ１０４の値がｎｕｌｌの場合には（Ｓ５４５の結果が「Ｙｅｓ」）、カーソル位置エントリ１２３にカレントエントリ１０４の値を代入して（Ｓ５６０）、オブジェクト逐次参照手順を終了する（Ｓ５５４）。
【０２２２】
プロセッサ０２１は、カレントエントリ１０４の値がｎｕｌｌでない場合には（Ｓ５４５の結果が「Ｎｏ」）、スレッドコンテクスト００３の次エントリ１０５にカレントエントリ１０４に対応するエントリ２０４の次エントリ２１１の値を代入する。さらに、スレッドコンテクスト００３のスレッドローカル変数１１４の一つであるカレント版エントリポインタ変数にカレントエントリの最新版エントリポインタ２３１の値を代入する（Ｓ５４６）。以下、カレント版エントリポインタ変数に対応する版エントリ２３２をカレント版エントリとする。
【０２２３】
プロセッサ０２１は、スレッドコンテクスト００３のスレッドローカル変数１１４の一つであるカレント版ポインタ変数にカレント版エントリの版ポインタ２３５の値を代入する。さらに、カレントエントリ削除時刻シーケンス１０８にカレント版エントリの版確定時刻シーケンス２３３の値を代入する（Ｓ５４７）。
【０２２４】
次に、プロセッサ０２１は、カレントエントリ挿入時刻シーケンス１０７にカレントエントリの挿入時刻シーケンス２１２の値を代入する（Ｓ５４８）。Ｓ５４８の処理は、Ｓ５４６及びＳ５４７の処理で参照されたカレントエントリが領域回収されて、かつ、再利用されていないことを判定する目的の処理である。したがって、プラットフォームによってはＳ５４７及びＳ５４８の実行順序が実行時の最適化によって変更されないように、フェンス命令と呼ばれる特殊なプロセッサインストラクションを必要とする場合がある。
【０２２５】
プロセッサ０２１は、前エントリ挿入時刻シーケンス１０６が無効値でなく、かつ、前エントリ挿入時刻シーケンス１０６がカレントエントリ挿入時刻シーケンス１０７よりも早いか否かを判定する（Ｓ５４９）。前エントリ挿入時刻シーケンス１０６が無効値でなく、かつ、前エントリ挿入時刻シーケンス１０６がカレントエントリ挿入時刻シーケンス１０７よりも早い場合には（Ｓ５４９の結果が「Ｙｅｓ」）、カレントエントリがセットに対応する連結リストから分離され、再利用されたことを意味する。そこで、Ｓ５４２の処理に戻り、カーソルの移動前のエントリから連結リストを再度走査する。
【０２２６】
プロセッサ０２１は、前エントリ挿入時刻シーケンス１０６が無効値か、または、前エントリ挿入時刻シーケンス１０６がカレントエントリ挿入時刻シーケンス１０７よりも遅い場合には（Ｓ５４９の結果が「Ｎｏ」）、さらに、カレント版ポインタ変数の値がｎｕｌｌでなく、かつ、カレントエントリ削除時刻シーケンス１０８が無効値でなく、かつ、カレントエントリ削除時刻シーケンス１０８がトランザクション管理ブロック４１０のトランザクション開始時刻シーケンス４１１よりも早いか否かを判定する（Ｓ５５０）。
【０２２７】
Ｓ５５０の条件が成立する場合には（Ｓ５５０の結果が「Ｙｅｓ」）、カレントエントリは、オブジェクトが削除されたために該当カーソルから参照できなくなった無効エントリである。そこで、プロセッサ０２１は、前エントリ挿入時刻シーケンス１０６にカレントエントリ挿入時刻シーケンス１０７の値を代入し、さらに、カレントエントリ１０４に次エントリ１０５の値を代入し（Ｓ５５３）、Ｓ５４５以降の処理をさらに実行する。
【０２２８】
プロセッサ０２１は、Ｓ５５０の条件が成立しない場合には（Ｓ５５０の結果が「Ｎｏ」）、参照可能な版を探索する（Ｓ５５１）。参照可能な版を探索する手順については、図２０にて後述する。参照可能な版が見つかった場合、カレント版エントリポインタ変数に、対応する版エントリ２３２のアドレスが代入されている。
【０２２９】
そして、プロセッサ０２１は、参照可能な版が存在するか否か、すなわち、カレント版エントリポインタ変数の値がｎｕｌｌか否かを判定する（Ｓ５５２）。カレント版エントリポインタ変数の値がｎｕｌｌの場合には（Ｓ５５２の結果が「Ｙｅｓ」）、参照可能な版が存在しないため、Ｓ５５３の処理を実行することによってカレントエントリ１０４を変更し、Ｓ５４５から再度処理を実行する。
【０２３０】
プロセッサ０２１は、カレント版エントリポインタ変数の値がｎｕｌｌでない場合には（Ｓ５５２の結果が「Ｎｏ」）、カレントエントリがカーソル１２０のカーソル位置エントリ１２３となる（Ｓ５６０）。したがって、カレント版エントリポインタ変数に対応する版エントリ２３２の版２３６の参照をアプリケーションプログラム００４に返却し、オブジェクト逐次参照手順を終了する（Ｓ５５４）。
【０２３１】
図２０は、本発明の第２の実施の形態のトランザクションから参照可能な版を探索する手順を示すフローチャートである。
【０２３２】
プロセッサ０２１は、図１９に示したオブジェクト逐次参照手順によって、参照可能な版の探索が開始されると（Ｓ５５５）、まず、カレント版エントリポインタ変数の値がｎｕｌｌか否かチェックする（Ｓ５５６）。
【０２３３】
プロセッサ０２１は、カレント版エントリポインタ変数の値がｎｕｌｌの場合には（Ｓ５５６の結果が「Ｙｅｓ」）、参照可能な版が存在しないと判定し、参照可能な版の探索を終了する（Ｓ５５９）。
【０２３４】
プロセッサ０２１は、カレント版エントリポインタ変数の値がｎｕｌｌでない場合には（Ｓ５５６の結果が「Ｎｏ」）、カレント版エントリの版確定時刻シーケンス２３３が有効、かつ、トランザクション開始時刻シーケンス４１１よりも早いか否かを判定する（Ｓ５５７）。
【０２３５】
プロセッサ０２１は、カレント版エントリの版確定時刻シーケンス２３３が有効、かつ、トランザクション開始時刻シーケンス４１１よりも早い場合には（Ｓ５５７の結果が「Ｙｅｓ」）、参照可能な版が発見されたものとし、参照可能な版の探索を終了する（Ｓ５５９）。
【０２３６】
プロセッサ０２１は、カレント版エントリの版確定時刻シーケンス２３３が無効、又は、トランザクション開始時刻シーケンス４１１よりも遅い場合には（Ｓ５５７の結果が「Ｎｏ」）、カレント版エントリポインタ変数にカレント版エントリの旧版エントリ２３４の値を代入し（Ｓ５５８）、Ｓ５５６の処理に戻る。
【０２３７】
本発明の第２の実施の形態によれば、ＭＶＣＣによるトランザクションの同時実行制御がなされるシステムにおいても、第１の実施の形態と同様に、相互排他ロックの取得などを必要とせずに高いレスポンス性能が得ることができる。
【図面の簡単な説明】
【０２３８】
【図１】本発明の第１の実施の形態のデータ管理システムにおけるソフトウェアモジュール構成図である。
【図２】本発明の第１の実施の形態のデータ管理システムのハードウェアモジュール構成、ソフトウェアモジュール構成及び関連を説明する図である。
【図３】本発明の第１の実施の形態のスレッドコンテクストの構成例を示す図である。
【図４】本発明の第１の実施の形態のカーソルの構成を示す図である。
【図５】本発明の第１の実施の形態のデータ管理手段のデータ格納部におけるデータ格納形式を説明する図である。
【図６】本発明の第１の実施の形態のデータ格納部に格納されるエントリの構成例を示す図である。
【図７】本発明の第１の実施の形態のデータ格納部に格納されるエントリの別の構成例を示す図である。
【図８Ａ】本発明の第１の実施の形態のセットアンカから参照される連結リストによって構成されているセットを表す図である。
【図８Ｂ】本発明の第１の実施の形態のカーソルの前エントリ及びカレントエントリに対応するエントリをオブジェクト参照部が移動した状態を示す図である。
【図８Ｃ】本発明の第１の実施の形態のカーソルに対応する連結リストからエントリがオブジェクト回収部により分離された場合を示す図である。
【図８Ｄ】本発明の第１の実施の形態のエントリがオブジェクト回収部に分離された後に、オブジェクト挿入部に再利用されることによって、他のエントリに連結された場合を示す図である。
【図８Ｅ】本発明の第１の実施の形態の削除済みエントリが再利用されたことをオブジェクト参照部が検知した後にオブジェクト参照部がカレントエントリを移動させた状態を示す図である。
【図９】本発明の第１の実施の形態のセット内のオブジェクトを逐次参照するためのカーソルを初期化する手順を示すフローチャートである。
【図１０】本発明の第１の実施の形態のカーソルによってセット内のオブジェクトを参照する手順を示すフローチャートである。
【図１１】本発明の第１の実施の形態のセットにオブジェクトを挿入する手順を示すフローチャートである。
【図１２】本発明の第１の実施の形態のセットからオブジェクトを削除する手順を示すフローチャートである。
【図１３】本発明の第１の実施の形態の削除済みエントリを再利用するために領域を回収する手順を示すフローチャートである。
【図１４】本発明の第１の実施の形態のシステム時刻シーケンスを取得する手順を示すフローチャートである。
【図１５】本発明の第２の実施の形態のデータ管理システムにおけるソフトウェアモジュール構成図である。
【図１６Ａ】本発明の第２の実施の形態のトランザクションプール内で管理されるトランザクション管理ブロックの構成例を示す図である。
【図１６Ｂ】本発明の第２の実施の形態のデータ格納部に格納されるエントリの構成例を示す図である。
【図１７】本発明の第２の実施の形態のトランザクションを開始する手順を示すフローチャートである。
【図１８】本発明の第２の実施の形態のトランザクションを終了する手順を示すフローチャートである。
【図１９】本発明の第２の実施の形態のカーソルによってセット内のオブジェクトを参照する手順を示すフローチャートである。
【図２０】本発明の第２の実施の形態のトランザクションから参照可能な版を探索する手順を示すフローチャートである。
【図２１】本発明の第２の実施の形態のセットにオブジェクトを挿入する手順を示すフローチャートである。
【図２２】本発明の第２の実施の形態のオブジェクトを更新する手順を示すフローチャートである。
【図２３】本発明の第２の実施の形態のセットからオブジェクトを削除する手順を示すフローチャートである。
【図２４】本発明の第２の実施の形態の削除済みエントリを再利用するために領域を回収する手順を示すフローチャートである。
【符号の説明】
【０２３９】
００１    主記憶
００２    スケジューラ
００３    スレッドコンテクスト
００４    アプリケーションプログラム
００５    オブジェクト挿入部
００６    オブジェクト削除部
００７    オブジェクト参照部
００８    オブジェクト領域回収部
００９    システム時刻シーケンス生成部
０１０    エントリヒープ
０１１    プログラム格納部
０１２    データ格納部
０１３    カウンタ
０１４    データ
０１５    カーソルプール
０２１    プロセッサ
０２２    システムバス
１０１    プログラムカウンタ退避領域
１０２    レジスタ退避領域
１０３    前エントリ
１０４    カレントエントリ
１０５    次エントリ
１０６    前エントリ挿入時刻シーケンス
１０７    カレントエントリ挿入時刻シーケンス
１０８    カレントエントリ削除時刻シーケンス
１１０    最早参照時刻シーケンス
１１１    参照時刻シーケンス
１１２    直前時刻シーケンス
１１３    現在時刻シーケンス
１１４    スレッドローカル変数
１２０    カーソル
１２１    参照時刻シーケンス
１２２    セットアンカ
１２３    カーソル位置エントリ
１２４    探索条件
１３３    現在時刻シーケンス
２０１    セットアンカ
２０２    フリーアンカ
２０３    エントリヒープ
２０４    エントリ
２１１    次エントリ
２１２    挿入時刻シーケンス
２１３    削除時刻シーケンス
２１４    オブジェクト
２１５    フリー次エントリ
２２１    オブジェクトポインタ
２３１    最新版エントリポインタ
２３２    版エントリ
２３３    版確定時刻シーケンス
２３４    旧版エントリ
２３５    版ポインタ
２３６    版
４０１    オブジェクト更新部
４０２    トランザクション制御部
４０３    トランザクションプール
４１０    トランザクション管理ブロック
４１１    トランザクション開始時刻シーケンス
４１２    更新オブジェクト一覧
４１３    トランザクション状態
【図１】
0004585579.tif 000002
【図２】
0004585579.tif 000003
【図３】
0004585579.tif 000004
【図４】
0004585579.tif 000005
【図５】
0004585579.tif 000006
【図６】
0004585579.tif 000007
【図７】
0004585579.tif 000008
【図８Ａ】
0004585579.tif 000009
【図８Ｂ】
0004585579.tif 000010
【図８Ｃ】
0004585579.tif 000011
【図８Ｄ】
0004585579.tif 000012
【図８Ｅ】
0004585579.tif 000013
【図９】
0004585579.tif 000014
【図１０】
0004585579.tif 000015
【図１１】
0004585579.tif 000016
【図１２】
0004585579.tif 000017
【図１３】
0004585579.tif 000018
【図１４】
0004585579.tif 000019
【図１５】
0004585579.tif 000020
【図１６Ａ】
0004585579.tif 000021
【図１６Ｂ】
0004585579.tif 000022
【図１７】
0004585579.tif 000023
【図１８】
0004585579.tif 000024
【図１９】
0004585579.tif 000025
【図２０】
0004585579.tif 000026
【図２１】
0004585579.tif 000027
【図２２】
0004585579.tif 000028
【図２３】
0004585579.tif 000029
【図２４】
0004585579.tif 000030