(57)【要約】【課題】再利用対象になっていないデータ要素の数を減少させ、使用メモリ量を削減すること。また、スレッドが処理対象とするデータ要素の比較対象となる削除済リストのデータ要素を増大させることで、メモリ・リサイクル処理の効率を高めること。【解決手段】本発明のメモリ管理方法においては、削除したデータ要素を全スレッドからアクセス可能な先入先出方式のリスト構造で管理する。また、そのリスト構造に含まれるデータ要素を再利用可能状態に移行させる際は、最初に、削除したデータ要素を管理するリスト構造のスナップショットを取る。スナップショットを取った後で、再利用可能状態への移行可否の判定に必要なデータをアクセスして、スナップショットに含まれるデータ要素について、再利用可能状態への移行可否の判定を行う。【選択図】  図１
2014170430.tif 000002
【特許請求の範囲】
【請求項１】
全スレッドのいずれかが使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有する削除済リストと、
いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含む未使用リストと、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収手段であって、まず、移行開始時の前記削除済リストのスナップショットを取り、続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定し、その結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行する、データ要素回収手段と、
を備える情報処理装置。
【請求項２】
前記削除済リストは、前記削除済リストにリストされたデータ要素の数をカウントするカウンタを含み、
前記データ要素回収手段は、前記削除済リストのスナップショットとして、前記移行開始時の前記カウンタが有するデータ要素の数を複写し、該複写したデータ要素の数だけデータ要素の移行を制御する請求項１に記載の情報処理装置。
【請求項３】
各スレッドが処理対象としているデータ要素とその前と後とにリンクするデータ要素とをポイントするポインタを、全スレッドについて記憶するハザード・ポインタを、さらに備え、
前記データ要素回収手段は、前記削除済リストのスナップショットを取った後に、前記ハザード・ポインタを複写し、該複写したハザード・ポインタがポイントするデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定する請求項２に記載の情報処理装置。
【請求項４】
前記データ要素回収手段は、前記ハザード・ポインタを複写する場合に、有意でないポインタまたは重複するポインタを複写せず、ポインタを昇順または降順にソートする請求項３に記載の情報処理装置。
【請求項５】
前記削除済リストは、先頭のデータ要素をポイントする先頭ポインタと、所定のデータ領域に前記新たなネクストポインタが設定された少なくとも１つのデータ要素と、末尾のデータ要素をポイントする末尾ポインタと、をさらに含み、
全スレッドのいずれかが使用中リストからデータ要素を削除した場合に、前記使用中リストから前記削除済リストへの前記削除されたデータ要素の移行を制御するデータ要素削除手段であって、前記末尾ポインタと、前記末尾ポインタがポイントするデータ要素の前記所定のデータ領域とに、前記削除したデータ要素をポイントするネクストポインタを記憶し、前記削除したデータ要素の前記所定のデータ領域に末尾のデータ要素を示すデータを記憶し、前記カウンタを１つ増加する、データ要素削除手段を、さらに備える請求項２乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
使用中リストと、削除済リストと、未使用リストとを有し、複数のスレッドが前記データ要素を前記リストの間で並列に移行させる情報処理装置の制御方法であって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収ステップであって、
移行開始時の前記削除済リストのスナップショットを取るステップと、
続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含むデータ要素回収ステップ、を有する情報処理装置の制御方法。
【請求項７】
使用中リストと、削除済リストと、未使用リストとを有し、複数のスレッドが前記データ要素を前記リストの間で並列に移行させる情報処理装置の制御プログラムであって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収ステップであって、
移行開始時の前記削除済リストのスナップショットを取るステップと、
続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含むデータ要素回収ステップ、をコンピュータに実行させる情報処理装置の制御プログラム。
【請求項８】
使用中リストと、削除済リストと、未使用リストとを有し、前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収方法であって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
移行開始時の前記削除済リストのスナップショットとして、移行を制御するデータ要素の数である、前記削除済リストにリストされたデータ要素の数をカウントするカウンタが有するデータ要素の数を複写するステップと、
前記削除済リストのスナップショットを取った後に、各スレッドが処理対象としているデータ要素とその前と後とにリンクするデータ要素とをポイントするポインタを、全スレッドについて記憶するハザード・ポインタを複写するステップと、
前記複写したハザード・ポインタがポイントするデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止するステップと、
前記判定の結果、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含むデータ要素回収方法。
【請求項９】
使用中リストと、削除済リストと、未使用リストとを有し、前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収プログラムであって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
移行開始時の前記削除済リストのスナップショットとして、移行を制御するデータ要素の数である、前記削除済リストにリストされたデータ要素の数をカウントするカウンタが有するデータ要素の数を複写するステップと、
前記削除済リストのスナップショットを取った後に、各スレッドが処理対象としているデータ要素とその前と後とにリンクするデータ要素とをポイントするポインタを、全スレッドについて記憶するハザード・ポインタを複写するステップと、
前記複写したハザード・ポインタがポイントするデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止するステップと、
前記判定の結果、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
をコンピュータに実行させるデータ要素回収プログラム。
【請求項１０】
複数のスレッドがリスト構造のメモリを並列にアクセスするためのメモリ管理方法であって、
削除したデータ要素を全スレッドからアクセス可能な先入先出方式のリスト構造で管理し、
前記リスト構造に含まれるデータ要素を再利用可能な状態に移行させる際は、最初に、前記リスト構造のスナップショットを取り、
前記スナップショットを取った後で、前記再利用可能な状態への移行の可否判定に必要なデータをアクセスし、
前記可否判定に必要なデータを用いて、前記スナップショットに含まれるデータ要素について、前記再利用可能な状態への移行の可否判定を行うメモリ管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のスレッドが並列処理をする場合のメモリ管理技術に関する。
【背景技術】
【０００２】
上記技術分野において、クリティカルセクションを形成することなく、複数のスレッドからのアクセスを矛盾なく実施する方法として、非特許文献１に示されているようなcmpxchg命令が知られている。マルチプロセッサ命令の典型例であるcmpxchg命令は、ＣＡＳ(Compare And Swap)操作により、命令実行中に他の命令によりメモリが変更されないようにする。
【０００３】
特許文献１および非特許文献２は、上記ＣＡＳ操作を用いて、リスト構造化されたデータへのデータ要素の挿入や、リスト構造化されたデータからのデータ要素の削除において、正しい実行結果が得られるアルゴリズムを提案している。すなわち、非特許文献２においては、リスト構造化されたデータからのデータ要素の削除処理を、論理的な削除のＣＡＳ操作と物理的な削除のＣＡＳ操作とにより実行する。そして、論理的に削除されたが物理的に削除されていないデータ要素を表わすマークビットを設けることで、削除命令処理中に他の命令が介入することを防いでいる。
【０００４】
また、特許文献１および非特許文献２は、削除したデータ要素に割り当てられたメモリ領域を再利用しても、別スレッドによるリストの検索操作に悪影響を及ぼさないことを保障する技術を開示する。すなわち、検索スレッドがリストを検索する際は、参照するデータ要素のアドレスを特定のメモリ領域（以降、ハザード・ポインタと言う）に記録することで、物理的に削除されたデータ要素が再利用可能かどうかを、そのデータ要素がハザード・ポインタに登録されているか否かによって判定する。ここで、ハザード・ポインタには、リストを検索する可能性のある各スレッドに固定された領域が割り当てられている。また、物理削除されたデータ要素のアドレスは、スレッド別に用意されている削除済リストに記録され、再利用可能なデータ要素は、未使用リストに蓄えられる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許公開第2004/0107227号公報
【非特許文献】
【０００６】
【非特許文献２】Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M
【非特許文献２】Maged M. Michael, High Performance Dynamic Lock-Free Hash Tables and List-Based Sets, ACM SPAA’02.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記特許文献１および非特許文献２に記載の技術では、データ要素を削除して削除済リストに挿入する操作と、削除済リストのデータ要素をハザード・ポインタと比較した後、未使用リストに移行する操作とが同時に実行されることを防止するため、削除済リストがスレッド別に用意されている。これにより、使用中リストを参照しているスレッドが不正な内容を持つデータ要素をアクセスする危険性をなくしている。
【０００８】
その結果、削除されているが未使用リストには移行されていないために再利用対象にはなっていない状態にあるデータ要素の数が、システムで実行されているスレッド数に比例する形で多くなる。また、削除済リストから未使用リストに移行する操作の対象となるデータ要素は、その操作を行うスレッドが削除したデータ要素のみのため、数が少なくなってしまい、メモリ・リサイクルの処理効率が低くなってしまう。
【０００９】
本発明の目的は、上述の課題を解決する技術を提供することにある。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、本発明に係る情報処理装置は、
全スレッドのいずれかが使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有する削除済リストと、
いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含む未使用リストと、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収手段であって、まず、移行開始時の前記削除済リストのスナップショットを取り、続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定し、その結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行する、データ要素回収手段と、
を備える。
【００１１】
上記目的を達成するため、本発明に係る方法は、
使用中リストと、削除済リストと、未使用リストとを有し、複数のスレッドが前記データ要素を前記リストの間で並列に移行させる情報処理装置の制御方法であって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収ステップであって、
移行開始時の前記削除済リストのスナップショットを取るステップと、
続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含むデータ要素回収ステップ、を有する。
【００１２】
上記目的を達成するため、本発明に係るプログラムは、
使用中リストと、削除済リストと、未使用リストとを有し、複数のスレッドが前記データ要素を前記リストの間で並列に移行させる情報処理装置の制御プログラムであって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収ステップであって、
移行開始時の前記削除済リストのスナップショットを取るステップと、
続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含むデータ要素回収ステップ、をコンピュータに実行させる。
【００１３】
上記目的を達成するため、本発明に係る方法は、
使用中リストと、削除済リストと、未使用リストとを有し、前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収方法であって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
移行開始時の前記削除済リストのスナップショットとして、移行を制御するデータ要素の数である、前記削除済リストにリストされたデータ要素の数をカウントするカウンタが有するデータ要素の数を複写するステップと、
前記削除済リストのスナップショットを取った後に、各スレッドが処理対象としているデータ要素とその前と後とにリンクするデータ要素とをポイントするポインタを、全スレッドについて記憶するハザード・ポインタを複写するステップと、
前記複写したハザード・ポインタがポイントするデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止するステップと、
前記判定の結果、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含む。
【００１４】
上記目的を達成するため、本発明に係るプログラムは、
使用中リストと、削除済リストと、未使用リストとを有し、前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収プログラムであって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
移行開始時の前記削除済リストのスナップショットとして、移行を制御するデータ要素の数である、前記削除済リストにリストされたデータ要素の数をカウントするカウンタが有するデータ要素の数を複写するステップと、
前記削除済リストのスナップショットを取った後に、各スレッドが処理対象としているデータ要素とその前と後とにリンクするデータ要素とをポイントするポインタを、全スレッドについて記憶するハザード・ポインタを複写するステップと、
前記複写したハザード・ポインタがポイントするデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止するステップと、
前記判定の結果、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
をコンピュータに実行させる。
【００１５】
上記目的を達成するため、本発明に係る方法は、
複数のスレッドがリスト構造のメモリを並列にアクセスするためのメモリ管理方法であって、
削除したデータ要素を全スレッドからアクセス可能な先入先出方式のリスト構造で管理し、
前記リスト構造に含まれるデータ要素を再利用可能な状態に移行させる際は、最初に、前記リスト構造のスナップショットを取り、
前記スナップショットを取った後で、前記再利用可能な状態への移行の可否判定に必要なデータをアクセスし、
前記可否判定に必要なデータを用いて、前記スナップショットに含まれるデータ要素について、前記再利用可能な状態への移行の可否判定を行う。
【発明の効果】
【００１６】
本発明によれば、使用中リストから削除したデータ要素を管理する削除済リストを全スレッドからアクセス可能な先入先出方式のリスト構造とすることで、再利用対象になっていないデータ要素の数を減少させ、使用メモリ量を削減できる。また、スレッドが処理対象とするデータ要素の比較対象となる削除済リストのデータ要素を増大させることで、メモリ・リサイクル処理の効率を高めることができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１実施形態に係る情報処理装置の構成を示すブロック図である。
【図２】本発明の第２実施形態に係る情報処理装置の構成を示すブロック図である。
【図３】本発明の第２実施形態に係るプログラムの構成を示す図である。
【図４】本発明の第２実施形態に係る情報処理装置のメモリ管理処理を説明する図である。
【図５】本発明の第２実施形態に係るデータ要素の構成を示す図である。
【図６】本発明の第２実施形態に係る情報処理装置のデータ要素削除処理の手順を示すフローチャートである。
【図７】本発明の第２実施形態に係る情報処理装置のデータ要素回収処理の手順を示すフローチャートである。
【図８】本発明の第２実施形態に係る情報処理装置のデータ要素挿入処理の手順を示すフローチャートである。
【図９】本発明の第２実施形態に係る情報処理装置におけるスレッドによるデータ要素回収処理の開始時点の状態を示す図である。
【図１０】本発明の第２実施形態に係る情報処理装置におけるスレッドによるデータ要素回収処理の途中の状態を示す図である。
【図１１】本発明の第２実施形態に係る情報処理装置におけるスレッドによるデータ要素回収処理の終了時点の状態を示す図である。
【図１２】情報処理装置の基礎となるメモリ管理処理を説明する図である。
【発明を実施するための形態】
【００１８】
以下に、図面を参照して、本発明の実施の形態について例示的に詳しく説明する。ただし、以下の実施の形態に記載されている構成要素は単なる例示であり、本発明の技術範囲をそれらのみに限定する趣旨のものではない。明細書および図面において使用する「移行」との文言は、一義的には、メモリ内の１つのリスト構造から他のリスト構造へデータ要素のリンクを単に繋ぎ替える論理的な処理を表わしている。しかしながら、「移行」処理は、データ要素を１つのリスト構造から他のリスト構造へ、メモリ内の他のアドレス空間へ物理的に移動する処理を排除するものではない。
【００１９】
［第１実施形態］
本発明の第１実施形態としての情報処理装置１００について、図１を用いて説明する。情報処理装置１００は、複数のスレッドが並列処理をする装置である。
【００２０】
図１に示すように、情報処理装置１００は、削除済リスト１２０と、未使用リスト１３０と、データ要素回収部１４０と、を含む。削除済リスト１２０は、全スレッドのいずれかが使用中リスト１１０からデータ要素を削除した場合に、削除されたデータ要素を使用中リスト１１０から移行するリストである。そして、削除済リスト１２０は、使用中リスト１１０で使用した次のデータ要素をポイントするネクストポインタ１１１を保持するために、新たなネクストポインタ１２１による先入先出方式のリスト構造を有する。また、未使用リスト１３０は、いずれのスレッドからもアクセスの可能性がない削除済リスト１２０中のデータ要素を削除済リスト１２０から移行するリストである。そして、未使用リスト１３０は、全スレッドにより再使用可能なデータ要素を含む。データ要素回収部１４０は、削除済リスト１２０から未使用リスト１３０へのデータ要素の移行を制御する。すなわち、まず、移行開始時の削除済リスト１２０のスナップショットを取る。続いて、全スレッドのいずれかが処理対象としているデータ要素がスナップショットを取った削除済リスト１２０にあるか否かを判定する（１４１）。その結果、全スレッドのいずれかが処理対象としているデータ要素についてはスナップショットを取った削除済リスト１２０から未使用リスト１３０への移行を停止する。一方、全スレッドのいずれもが処理対象としていないデータ要素についてはスナップショットを取った削除済リスト１２０から未使用リスト１３０へ移行する。
【００２１】
本実施形態によれば、使用中リストから削除したデータ要素を管理する削除済リストを全スレッドからアクセス可能な先入先出方式のリスト構造とすることで、再利用対象になっていないデータ要素の数を減少させ、使用メモリ量を削減できる。また、スレッドが処理対象とするデータ要素の比較対象となる削除済リストのデータ要素を増大させることで、メモリ・リサイクル処理の効率を高めることができる。
【００２２】
［第２実施形態］
次に、本発明の第２実施形態に係る情報処理装置について説明する。本実施形態に係る情報処理装置は、全スレッドに共通の先入先出方式の削除済リストを設ける。そして、削除済リストから未使用リストへのデータ要素回収処理において、まず、削除済リストのスナップショットを取り、そのスナップショットに基づいて削除済リストの全スレッドのデータ要素を回収する。本実施形態によれば、使用中リストから削除したデータ要素を管理する削除済リストを全スレッドからアクセス可能な先入先出方式のリスト構造とすることで、再利用対象になっていない状態にあるデータ要素の数を減少させ、使用メモリ量を削減できる。また、削除済リストのデータ要素をハザード・ポインタと比較した後に未使用リストに移行する操作対象となるデータ要素を増大させることで、メモリ・リサイクル処理の効率を高めることができる。
【００２３】
《情報処理装置の基礎となる処理》
図１２は、情報処理装置の基礎となるメモリ管理処理を説明する図であり、まず、その処理の概略を説明する。
【００２４】
図１２のハザード・ポインタには、リストを検索する可能性のある各スレッドに固定された領域が割り当てられている。また、物理削除されたデータ要素のアドレスは、スレッド別に用意されている削除済みデータ要素のポインタを格納する削除済リストに記録される。また、再利用可能なデータ要素は、未使用リストに蓄えられる。図１２の技術では、使用中リストから削除されたデータ要素はまず削除済リストに記録された後、再利用可能かどうかの判定を経て未使用リストに移行する。データ要素として割り当てられるのは未使用リストに繋がれたデータ要素であり、削除済リストに記録されている段階のデータ要素は再利用の対象とはなっていない。
【００２５】
ここで、削除済リスト内にあらかじめ決められた数のデータ要素のポインタが溜まっている状態で、さらに、スレッド別削除済リストに対応するスレッドがデータ要素を物理削除したとする。すなわち、スレッド別削除済リストにあらかじめ決められた数以上のデータ要素を溜めようとすると、スレッド別削除済リストにある全データ要素について、未使用リストに移行可能かどうかの判定が行われる。そして、移行可能と判定されたデータ要素については未使用リストに移行する。すなわち、スレッド別削除済リストから削除された後、未使用リストに繋ぎこまれる。ここで、未使用リストに移行可能かどうかの判定とは、スレッド別削除済リストに繋がれた判定対象であるデータ要素のポインタと、ハザード・ポインタに記録されているアドレスとの比較である。ハザード・ポインタに記録されているアドレスの総てと一致しない場合は移行可能であり、逆に、どれか１つでも一致するものがあれば移行不可と判定される。これにより、検索スレッドが参照しているデータ要素、すなわち、再利用すると問題を生じる可能性のあるデータ要素を、スレッド別削除済リストから未使用リストに移行してしまう、という不正な操作を防止している。
【００２６】
しかしながら、図１２のメモリ管理処理では、削除済リストがスレッド別に用意されているため、削除されているが未使用リストには移行されていないために再利用対象にはなっていない状態にあるデータ要素の数が、システムで実行されているスレッド数に比例する形で多くなる。また、削除済リストから未使用リストに移行する操作の対象となるデータ要素は、その操作を行うスレッドが削除したデータ要素のみのため、数が少なくなってしまい、メモリ・リサイクルの処理効率が低くなってしまう。
【００２７】
《情報処理装置の構成》
図２は、本実施形態に係る情報処理装置２００の構成を示すブロック図である。
【００２８】
図２を参照すると、本実施形態の情報処理装置２００は、スレッド２１１〜２１ｍを実行する複数のプロセッサ２０１〜２０ｍとメモリ２２０とから構成されている。
【００２９】
メモリ２２０は、全スレッド２１１〜２１ｍがアクセスできるスレッド共通領域２４０と、各スレッド別にメモリ領域が割り当てられるスレッド固有領域２３０とに分かれている。スレッド共通領域２４０には、スレッドが実行するプログラム２５０と、データ要素がリスト構造で繋がれた使用中リスト２６０、削除済リスト２７０、未使用リスト２８０、ハザード・ポインタ２９０と、スレッドがプログラムを実行する際に使用するデータ（不図示）とが格納されている。スレッド固有領域２３０に割り当てられているスレッド別のメモリ領域２３１〜２３ｍには、それぞれ変数Ｓとポインタ配列ＰＡの格納領域が確保されている。
【００３０】
《プログラムの構成》
図３は、本実施形態に係るプログラム２５０の構成を示す図である。なお、図３には、情報処理装置２００において本実施形態を実現するプログラムが図示されており、情報処理装置２００に装備された汎用のＯＳ(Operating System)や他機能を実現するプログラム、あるいはアプリケーションプログラムが図示されていない。
【００３１】
図３を参照すると、プログラム２５０には、使用中リストに対する３種類の処理、すなわち、検索処理２５１と、データ要素挿入処理２５２と、データ要素削除処理２５３と、データ要素回収処理２５４と、が含まれている。これらの処理は、それぞれ概略つぎのように動作する。
【００３２】
検索処理２５１は、検索プログラムにより実現され、使用中リスト２６０の先頭に位置するデータ要素から順にnextポインタ（次ポインタ）を辿ることで、使用中リスト２６０に格納されているデータ要素を走査し、目的とするデータ項目を含むデータ要素を探し出す処理である。
【００３３】
データ要素挿入処理２５２は、データ要素挿入プログラムにより実現され、未使用リスト２８０から１個のデータ要素を取り外し、そのデータ領域に必要なデータを格納した後、そのデータ要素を使用中リスト２６０に挿入する処理である。
【００３４】
データ要素削除処理２５３は、データ要素削除プログラムにより実現され、まず検索処理２５１を行って削除対象となるデータ要素を探し出し、見つかった場合はそのデータ要素を使用中リスト２６０から取り外して削除済リスト２７０に格納する処理である。削除済リスト２７０に格納する際は、データ要素のリンク情報を格納する領域としてd_nextポインタ（新たな次ポインタ）を使用してリンクさせる。これにより、nextポインタ領域に格納されている使用中リスト２６０におけるリンク情報は保持されたままとなる。
【００３５】
データ要素回収処理２５４は、データ要素回収プログラムにより実現され、削除済リスト２７０に格納されているデータ要素について、まずハザード・ポインタ２９０に格納されている総てのポインタとの比較を行う。そして、比較の結果、どのポインタとも一致しないデータ要素を未使用リスト２８０に移行する処理である。比較の結果、どれか１つでもハザード・ポインタ２９０に格納されているポインタと一致するデータ要素については、未使用リスト２８０への移行は行わず、削除済リスト２７０に残す。
【００３６】
《メモリ管理処理》
図４は、本実施形態に係る情報処理装置２００のメモリ管理処理を説明する図である。
【００３７】
図４を参照すると、本実施形態では、使用中リスト２６０は、データ要素のnextポインタで繋がれたデータ要素４６２〜４６４のリストと、リストの先頭に位置するデータ要素のアドレスを保持するheadポインタ（先頭ポインタ）４６１とを有する。データ要素中のnextポインタおよびheadポインタが“ＮＵＬＬ”の場合は、その次の位置にはデータ要素が繋がれていないことを意味する。
【００３８】
削除済リスト２７０は、データ要素のd_nextポインタで繋がれたデータ要素４７２，４７３のリストと、リストの先頭と末尾に位置するデータ要素のアドレスを保持するheadポインタ４７１とtailポインタ（末尾ポインタ）４７４と、削除済リスト２７０に繋がれたデータ要素の数を保持する変数n（４７５）とを有する。本例の削除済リスト２７０では、制御を簡単にするため、１個のデータ要素が存在し、headポインタ４７１とtailポインタ４７４とがその１個のデータ要素のアドレスを保持する状態を、データ要素数（変数nの値）が“０”と定義する。また、データ要素中のd_nextポインタが“ＮＵＬＬ”の場合は、その次の位置にはデータ要素が繋がれていないことを意味する。
【００３９】
未使用リスト２８０は、使用中リスト２６０と同様、データ要素のnextポインタで繋がれたデータ要素４８２，４８３のリストと、リストの先頭に位置するデータ要素のアドレスを保持するheadポインタ４８１とを有する。データ要素４８２，４８３中のnextポインタおよびheadポインタ４８１が“ＮＵＬＬ”の場合は、その次の位置にはデータ要素が繋がれていないことを意味する。
【００４０】
ハザード・ポインタ２９０は、１スレッド当たり３個のデータ要素が固定的に割り当てられるポインタの配列である。本実施形態における使用中リスト２６０は、上位のアプリケーションに対して検索処理、挿入処理、削除処理のインタフェースを提供する。検索処理は、非特許文献２に記載されている従来技術と同じアルゴリズムで実行される。ハザード・ポインタ２９０に設定するアドレスは、処理中のデータ要素（current）、currentの次に位置するデータ要素（next）、currentの前に位置するデータ要素（prev）の３つのポインタである。また、使用中リスト２６０の走査を１個進めて処理対象のデータ要素をnextに移行すると、旧currentは新prev、旧nextは新currentとなり、新currentとなったデータ要素のnextポインタが新nextとなる。
【００４１】
データ要素挿入処理２５２では、未使用リスト２８０からデータ要素を１個取り出し、そのデータ項目領域にアプリケーションからのデータを設定した後、非特許文献２に記載されているアルゴリズムで使用中リスト２６０へのデータ要素挿入を実行する。すなわち、データ項目領域に設定された値で決まる位置を検索処理で探し出す。その状態において、currentのポインタを新しいデータ要素のnextポインタに設定する。その後、prevが示すデータ要素のnextポインタをＣＡＳ命令によってcurrentから新しいデータ要素のアドレスに変更する。
【００４２】
データ要素削除処理２５３では、非特許文献２に記載されているアルゴリズム、すなわち、論理削除と物理削除との１段階で使用中リスト２６０から取り外す。本実施形態によるデータ要素削除処理２５３では、使用中リスト２６０から取り外したデータ要素を削除済リスト２７０の末尾、すなわち、削除済リスト２７０内のtailポインタ４７４で示されるデータ要素の次の位置に繋ぎ込む。そして、削除済リスト２７０内の変数n（４７５）、すなわち、削除済リスト２７０にあるデータ要素数に１を加える。また、削除済リスト２７０におけるリスト構造を形成するためのリンク情報、すなわち、次の位置にあるデータ要素を示すポインタは、データ要素のd_next領域に記録する。これにより、データ要素のnext領域に記録されている値、すなわち、そのデータ要素が使用中リスト２６０に存在していた時のリンク情報は破壊されずに残る。なお、データ要素を削除済リスト２７０の末尾に繋ぎ込む操作や、データ要素数に１を加える操作は、プロセッサのＣＡＳ命令等を用いることで、排他制御を用いることなく実行することが可能である。データ要素削除処理２５３において、削除済リスト２７０内の変数ｎ（４５７）に１を加えた結果、それがあらかじめ決められた数（Ｔｈ）になるとデータ要素回収処理２５４を呼び出す。
【００４３】
データ要素回収処理２５４では、まず、データ要素回収処理開始時の削除済リスト２７０の状態をスナップショットにより複写する。本例では、データ要素回収処理開始時の変数n（４５７）の値をスレッド固有領域にある変数Ｓにコピーする。すなわち、変数ｎ（４５７）の値を変数Ｓにコピーする操作は、データ要素回収処理開始以降の削除済リスト２７０への削除済みデータ要素の追加処理の影響を排除するために、データ要素削除処理開始時における削除済リスト２７０のスナップショットを採取したことを意味する。なお、データ要素回収処理開始時の削除済リスト２７０を複写してもよい。
【００４４】
次に、ハザード・ポインタ２９０に記録されているポインタをスレッド固有領域にある、データ要素回収処理を実行するスレッドの配列をＰＡにコピーする。コピーの方法としては、ハザード・ポインタ２９０の配列をそのままＰＡにコピーする以外に、ハザード・ポインタの配列データ要素の内の有意でない“ＮＵＬＬ”のものはコピーしない、または、重複する値は除去する、といった方法も可能である。あるいは、ポインタ値の昇順または降順にソートして並べ替える、といった方法も可能である。これらの方法によれば、ハザード・ポインタ２９０の配列を要約してＰＡにコピーすることで、次の比較操作を高速化できる。
【００４５】
次に、削除済リストの先頭からＳ個のデータ要素、すなわち、ステップで採取した削除済リストのスナップショットについて、ＰＡにコピーされたポインタとの比較を行い、未使用リスト２８０への移行可否を判定する。比較の結果、ＰＡにコピーされたアドレスの総てと一致しない場合は移行可能と判定される。逆に、どれか１つでも一致するものがあれば移行不可と判定される。移行可能と判定されたデータ要素は未使用リストに移行される。一方、移行不可と判定されたデータ要素は削除済リストに残す。これにより、ハザード・ポインタ２９０に登録されているデータ要素、すなわち、検索スレッドが参照しており、再利用すると問題を生じる可能性のあるデータ要素の削除済リスト２７０から未使用リスト２８０への移行を防止する。
【００４６】
なお、最初に削除済リスト２７０のスナップショットを取ることなく、ハザード・ポインタ２９０の配列からＰＡへのコピーを行った後、その操作が完了した時点において削除済リスト２７０に蓄えられている全データ要素を対象に未使用リスト２８０への移行可否判定を行うと、次のような不正が発生する。例えば、ハザード・ポインタ２９０に記録されているポインタをスレッド固有領域にある、データ要素回収処理を実行するスレッドの配列をＰＡにコピーする操作が完了した時点よりも後から、削除済リスト２７０へ追加された削除済みデータ要素も、データ要素回収処理対象となってしまう。そのため、検索スレッドが参照しているデータ要素、すなわち、再利用すると問題を生じる可能性のあるデータ要素を、削除済リスト２７０から未使用リスト２８０に移行可能と判定してしまう可能性が残ってしまう。つまり、本実施形態においては、最初に削除済リストのスナップショットを取り、その後で未使用リスト２８０への移行可否判定に必要なデータであるハザード・ポインタ２９０の配列にアクセスする、という手順を踏むことにより、前述の問題が起きる可能性を防止している。
【００４７】
（データ要素の構成）
図５は、本実施形態に係るデータ要素の構成を示す図である。
【００４８】
図５のデータ要素５１０は、使用中リスト２６０および未使用リスト２８０に存在している間のデータ要素の構成である。データ要素５１０は、nextポインタ５１１を含む管理データ領域とデータ項目領域から構成されている。データ項目領域は、上位のアプリケーションプログラムが扱うデータを格納する領域である。また、管理データ領域は、リスト構造を構成するための情報を格納する領域であり、その領域内のnextポインタは、データ要素が使用中リスト２６０および未使用リスト２８０に存在している間、リスト構造を構成するためのリンク情報を格納する。
【００４９】
図５のデータ要素５２０は、削除済リスト２７０に存在している間のデータ要素の構成である。データ要素５２０は、nextポインタ５２１を含む管理データ領域とd_nextポインタ５２２を含むデータ項目領域から構成されている。管理データ領域のnextポインタ５２１は、削除済リスト２７０中では使用されず、使用中リスト２６０におけるnextポインタを保持している。データ項目領域には、削除済リスト２７０に存在している間、リスト構造を構成するためのd_nextポインタ５２２が所定の領域に記憶される。なお、データ項目領域は、そのデータ要素が削除済リスト２７０に存在している間はアプリケーションにとって意味のある値は格納されないため、d_nextポインタ５２２と共用しても問題は生じない。
【００５０】
《情報処理装置の処理手順》
図６〜図８を参照して、本実施形態に係る情報処理装置２００のメモリ管理処理に関連する処理手順を説明する。なお、図６〜図８の各処理手順は、スレッド２１１〜２１ｍが実行するものである。
【００５１】
（データ要素削除処理）
図６は、本実施形態に係る情報処理装置２００のデータ要素削除処理２５３の手順を示すフローチャートである。
【００５２】
ステップＳ６０１において、スレッドは、検索処理２５１により削除するデータ要素を探し出す。ステップＳ６０３において、スレッドは、論理削除として削除するデータ要素のnextポインタにマークビットをセットする。物理削除として、ステップＳ６０５において、スレッドは、削除するcurrentデータ要素のnextポインタを、前のprevデータ要素のnextポインタにコピーする。
【００５３】
削除済リスト２７０へのリンクとして、ステップＳ６０７において、スレッドは、currentポインタを、削除済リスト２７０のtailポインタ４７４と末尾のデータ要素のd_nextポインタとにコピーする。ステップＳ６０９において、スレッドは、削除するデータ要素のd_nextポインタにNULLをセットする。そして、ステップＳ６１１において、スレッドは、変数ｎ（４７５）を１つ増加させる。
【００５４】
データ要素回収処理２５４の起動判定として、ステップＳ６１３において、スレッドは、変数ｎ（４７５）が閾値Ｔｈ以上になったか否かを判定する。変数ｎ（４７５）が閾値Ｔｈ未満の場合は、データ要素削除処理２５３を終了する。変数ｎ（４７５）が閾値Ｔｈ未満の場合は、ステップＳ６１５において、スレッドは、データ要素回収処理２５４を起動して、データ要素削除処理２５３を終了する。
【００５５】
（データ要素回収処理）
図７は、本実施形態に係る情報処理装置２００のデータ要素回収処理２５４の手順を示すフローチャートである。
【００５６】
まず、ステップＳ７０１において、スレッドは、変数ｎ（４７５）の値をスレッド固有領域にある変数Ｓにコピーする。以下、Ｓにコピーされた値をＳと表記する。削除済リスト２７０は先入先出方式でデータ要素の追加と取出が行われるので、これ以降、削除済リスト２７０に追加されたデータ要素は、削除済リスト２７０の先頭からＳ番目より後にリンクされることになる。すなわち、変数ｎ（４７５）の値を変数Ｓにコピーする操作は、データ要素削除処理実行時における削除済リスト２７０のスナップショットを採取したことを意味する。スナップショットの終了後に、ステップＳ７０３において、スレッドは、ハザード・ポインタ２９０に記録されているポインタをスレッド固有領域２３０にあるＰＡにコピーする。
【００５７】
次に、ステップＳ７０５において、スレッドは、初期設定として、currentポインタ（以下、currentと略す）にheadポインタ４７１の値を代入して、currentに削除済リスト２７０の先頭データ要素をポイントさせる。また、データ要素回収処理２５４の対象としたデータ要素の数をカウントするカウンタ（以下、countと略す）をゼロとする。
【００５８】
ステップＳ７０７において、スレッドは、currentのポイントするcurrentデータ要素が、ハザード・ポインタ２９０のコピーであるＰＡの任意の１要素と一致するか否かを判定する。ＰＡのどの要素とも一致しない場合（ＮＯ）、ステップＳ７０９において、スレッドは、currentデータ要素を削除済リスト２７０から取り外し、未使用リスト２８０の後尾に追加する。そして、ステップＳ７１１において、スレッドは、変数ｎ（４７５）を１つ減少させる。ＰＡのいずれかの要素と一致した場合（ＹＥＳ）、ステップＳ７１３に進む。
【００５９】
ステップＳ７１３において、スレッドは、current = currentデータ要素のd_nextとして、d_nextによって削除済リスト２７０の次にリンクするデータ要素をポイントする。また、count = count + 1で処理数を１つ増加する。そして、ステップＳ７１５において、スレッドは、処理が完了したデータ要素数を示すcountがスナップショット時の削除済リスト２７０を表わす変数Ｓ未満であるか否かを判定する。変数Ｓ未満であればまだ未処理のデータ要素が残っているので、ステップＳ７０７に戻って、スレッドはデータ要素回収処理２５４を継続する。変数Ｓ以上であれば、スナップショット時の削除済リスト２７０内の全データ要素が処理を完了したので、スレッドはデータ要素回収処理２５４を終了する。これにより、ハザード・ポインタ２９０に登録されているデータ要素、すなわち、検索スレッドが参照しており、再利用すると問題を生じる可能性のあるデータ要素の削除済リスト２７０から未使用リスト２８０への移行を防止することができる。
【００６０】
（データ要素挿入処理）
図８は、本実施形態に係る情報処理装置２００のデータ要素挿入処理２５２の手順を示すフローチャートである。
【００６１】
ステップＳ８０１において、スレッドは、検索処理２５１で、データ要素を挿入する位置を探し出す。未使用リスト２８０からのデータ要素取得として、ステップＳ８０３において、スレッドは、未使用リスト２８０の先頭のデータ要素のnextポインタを、未使用リスト２８０のheadポインタにコピーする。未使用リスト２８０は後入先出方式であり、先頭に挿入したデータ要素を先に取り出す。
【００６２】
ステップＳ８０５において、スレッドは、未使用リストの先頭のデータ要素のデータ項目領域に、アプリケーションからのデータを設定する。
【００６３】
次に、使用中リスト２６０の目的位置へのデータ要素挿入として、ステップＳ８０７において、スレッドは、挿入位置をポイントするcurrentポインタを、未使用リストの先頭のデータ要素のnextポインタにコピーする。そして、ステップＳ８０９において、スレッドは、未使用リストの先頭のデータ要素のアドレスを、挿入位置前のprevポインタが示すデータ要素のnextポインタにコピーする。
【００６４】
《メモリ管理の具体例》
図９〜図１１を参照して、本実施形態に係る情報処理装置２００におけるメモリ管理の具体例を説明する。なお、図９は、図４の使用中リスト２６０からデータ要素４６３が削除された後の動作を説明している。
【００６５】
（データ要素回収処理の開始時点）
図９は、本実施形態に係る情報処理装置２００におけるスレッドによるデータ要素回収処理２５４の開始時点の状態を示す図である。
【００６６】
図９においては、使用中リスト２６０からデータ要素４６３が削除されて、削除済リスト２７０の後尾に移行している。ここで、変数ｎ（４７５）は１つ増加して、ｎ0になったとする。このｎ0が削除済リスト２７０の閾値Ｔｈ以上であるとする。
【００６７】
図９においては、データ要素回収処理２５４が開始され、まず、削除済リスト２７０のスナップショットとして、現在の変数ｎ0がＳにコピーされる。なお、図９においては、スレッド２１１による処理を想定している。また、削除済リスト２７０のスナップショット後に、ハザード・ポインタ２９０の内容がＰＡにコピーされる。また、countが０に初期設定される。
【００６８】
（データ要素回収処理の途中）
図１０は、本実施形態に係る情報処理装置２００におけるスレッドによるデータ要素回収処理２５４の途中の状態を示す図である。
【００６９】
図９においては、削除済リスト２７０のデータ要素４７２がどのスレッドの処理対象でもないため、削除済リスト２７０から未使用リスト２８０の先頭に移行している。countはＳ未満なので、さらにデータ要素回収処理２５４は継続する。
【００７０】
一方、他のスレッドによるデータ要素削除処理２５３で、使用中リスト２６０から新たにデータ要素４６２が削除され、削除済リスト２７０の後尾に移行している。削除済リスト２７０のデータ要素数を表わす変数ｎ（４７５）は、データ要素４７２の減少（−１）とデータ要素４６２の増加（＋１）となる。ここで、データ要素回収処理２５４のデータ要素数を表わすＳは、データ要素回収処理開始時の数を保持しているので、削除済リスト２７０内のデータ要素において、データ要素回収処理２５４に対象となるのは先頭からデータ要素４６３までで、新たに追加されたデータ要素４６２は対象外となる。
【００７１】
（データ要素回収処理の終了時点）
図１１は、本実施形態に係る情報処理装置２００におけるスレッドによるデータ要素回収処理２５４の終了時点の状態を示す図である。
【００７２】
図１１においては、削除済リスト２７０のデータ要素４６３がどのスレッドの処理対象でもないため、削除済リスト２７０から未使用リスト２８０の先頭に移行している。countはＳとなったので、データ要素回収処理２５４は終了する。したがって、データ要素回収処理開始後に削除済リスト２７０に追加されたデータ要素４６２に対しては、データ要素回収処理２５４は実行されない。
【００７３】
一方、他のスレッドによるデータ要素挿入処理２５２で、未使用リスト２８０の先頭のデータ要素４７２が使用中リスト２６０に挿入されている。
【００７４】
以上に説明したように、本実施形態によれば、使用中リストから削除したデータ要素を管理する削除済リストを全スレッドからアクセス可能な先入先出方式のリスト構造とすることで、再利用対象になっていない状態にあるデータ要素の数を減少させ、使用メモリ量を削減できる。また、削除済リストのデータ要素をハザード・ポインタと比較した後に未使用リストに移行する操作対象となるデータ要素を増大させることで、メモリ・リサイクル処理の効率を高めることができる。
【００７５】
また、本実施形態の活用例として、複数のスレッドが並行して複数のデータ要素をリストなどの構造データに動的に挿入あるいは削除することのできる情報処理システムにおいて、メモリ領域や処理負荷が少ないメモリ回収方法や装置、プログラムといった用途に適用できる。
【００７６】
［他の実施形態］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。また、それぞれの実施形態に含まれる別々の特徴を如何様に組み合わせたシステムまたは装置も、本発明の範疇に含まれる。
【００７７】
また、本発明は、複数の機器から構成されるシステムに適用されてもよいし、単体の装置に適用されてもよい。さらに、本発明は、実施形態の機能を実現する制御プログラムが、システムあるいは装置に直接あるいは遠隔から供給される場合にも適用可能である。したがって、本発明の機能をコンピュータで実現するために、コンピュータにインストールされる制御プログラム、あるいはその制御プログラムを格納した媒体、その制御プログラムをダウンロードさせるＷＷＷ(World Wide Web)サーバも、本発明の範疇に含まれる。特に、少なくとも、非一時的コンピュータ可読媒体（non-transitory computer readable medium）は本発明の範疇に含まれる。
【００７８】
［実施形態の他の表現］
上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
全スレッドのいずれかが使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有する削除済リストと、
いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含む未使用リストと、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収手段であって、まず、移行開始時の前記削除済リストのスナップショットを取り、続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定し、その結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行する、データ要素回収手段と、
を備える情報処理装置。
（付記２）
前記削除済リストは、前記削除済リストにリストされたデータ要素の数をカウントするカウンタを含み、
前記データ要素回収手段は、前記削除済リストのスナップショットとして、前記移行開始時の前記カウンタが有するデータ要素の数を複写し、該複写したデータ要素の数だけデータ要素の移行を制御する付記１に記載の情報処理装置。
（付記３）
各スレッドが処理対象としているデータ要素とその前と後とにリンクするデータ要素とをポイントするポインタを、全スレッドについて記憶するハザード・ポインタを、さらに備え、
前記データ要素回収手段は、前記削除済リストのスナップショットを取った後に、前記ハザード・ポインタを複写し、該複写したハザード・ポインタがポイントするデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定する付記２に記載の情報処理装置。
（付記４）
前記データ要素回収手段は、前記ハザード・ポインタを複写する場合に、有意でないポインタまたは重複するポインタを複写せず、ポインタを昇順または降順にソートする付記３に記載の情報処理装置。
（付記５）
前記削除済リストは、先頭のデータ要素をポイントする先頭ポインタと、所定のデータ領域に前記新たなネクストポインタが設定された少なくとも１つのデータ要素と、末尾のデータ要素をポイントする末尾ポインタと、をさらに含み、
全スレッドのいずれかが使用中リストからデータ要素を削除した場合に、前記使用中リストから前記削除済リストへの前記削除されたデータ要素の移行を制御するデータ要素削除手段であって、前記末尾ポインタと、前記末尾ポインタがポイントするデータ要素の前記所定のデータ領域とに、前記削除したデータ要素をポイントするネクストポインタを記憶し、前記削除したデータ要素の前記所定のデータ領域に末尾のデータ要素を示すデータを記憶し、前記カウンタを１つ増加する、データ要素削除手段を、さらに備える付記２乃至４のいずれか１項に記載の情報処理装置。
（付記６）
使用中リストと、削除済リストと、未使用リストとを有し、複数のスレッドが前記データ要素を前記リストの間で並列に移行させる情報処理装置の制御方法であって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収ステップであって、
移行開始時の前記削除済リストのスナップショットを取るステップと、
続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含むデータ要素回収ステップ、を有する情報処理装置の制御方法。
（付記７）
使用中リストと、削除済リストと、未使用リストとを有し、複数のスレッドが前記データ要素を前記リストの間で並列に移行させる情報処理装置の制御プログラムであって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収ステップであって、
移行開始時の前記削除済リストのスナップショットを取るステップと、
続いて、全スレッドのいずれかが処理対象としているデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止し、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含むデータ要素回収ステップ、をコンピュータに実行させる情報処理装置の制御プログラム。
（付記８）
使用中リストと、削除済リストと、未使用リストとを有し、前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収方法であって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
移行開始時の前記削除済リストのスナップショットとして、移行を制御するデータ要素の数である、前記削除済リストにリストされたデータ要素の数をカウントするカウンタが有するデータ要素の数を複写するステップと、
前記削除済リストのスナップショットを取った後に、各スレッドが処理対象としているデータ要素とその前と後とにリンクするデータ要素とをポイントするポインタを、全スレッドについて記憶するハザード・ポインタを複写するステップと、
前記複写したハザード・ポインタがポイントするデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止するステップと、
前記判定の結果、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
を含むデータ要素回収方法。
（付記９）
使用中リストと、削除済リストと、未使用リストとを有し、前記削除済リストから前記未使用リストへのデータ要素の移行を制御するデータ要素回収プログラムであって、
前記使用中リストは、全スレッドのいずれかが使用中であるデータ要素のリスト構造を有し、
前記削除済リストは、全スレッドのいずれかが前記使用中リストからデータ要素を削除した場合に、前記削除されたデータ要素を前記使用中リストから移行する削除済リストであって、前記使用中リストで使用した次のデータ要素をポイントするネクストポインタを保持するために、新たなネクストポインタによる先入先出方式のリスト構造を有し、
前記未使用リストは、いずれのスレッドからもアクセスの可能性がない前記削除済リストのデータ要素を前記削除済リストから移行する未使用リストであって、全スレッドにより再使用可能なデータ要素を含み、
移行開始時の前記削除済リストのスナップショットとして、移行を制御するデータ要素の数である、前記削除済リストにリストされたデータ要素の数をカウントするカウンタが有するデータ要素の数を複写するステップと、
前記削除済リストのスナップショットを取った後に、各スレッドが処理対象としているデータ要素とその前と後とにリンクするデータ要素とをポイントするポインタを、全スレッドについて記憶するハザード・ポインタを複写するステップと、
前記複写したハザード・ポインタがポイントするデータ要素が前記スナップショットを取った削除済リストにあるか否かを判定するステップと、
判定の結果、全スレッドのいずれかが処理対象としているデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへの移行を停止するステップと、
前記判定の結果、全スレッドのいずれもが処理対象としていないデータ要素については前記スナップショットを取った削除済リストから前記未使用リストへ移行するステップと、
をコンピュータに実行させるデータ要素回収プログラム。
（付記１０）
上記目的を達成するため、本発明に係る方法は、
複数のスレッドがリスト構造のメモリを並列にアクセスするためのメモリ管理方法であって、
削除したデータ要素を全スレッドからアクセス可能な先入先出方式のリスト構造で管理し、
前記リスト構造に含まれるデータ要素を再利用可能な状態に移行させる際は、最初に、前記リスト構造のスナップショットを取り、
前記スナップショットを取った後で、前記再利用可能な状態への移行の可否判定に必要なデータをアクセスし、
前記可否判定に必要なデータを用いて、前記スナップショットに含まれるデータ要素について、前記再利用可能な状態への移行の可否判定を行うメモリ管理方法。
【図１】
2014170430.tif 000003
【図２】
2014170430.tif 000004
【図３】
2014170430.tif 000005
【図４】
2014170430.tif 000006
【図５】
2014170430.tif 000007
【図６】
2014170430.tif 000008
【図７】
2014170430.tif 000009
【図８】
2014170430.tif 000010
【図９】
2014170430.tif 000011
【図１０】
2014170430.tif 000012
【図１１】
2014170430.tif 000013
【図１２】
2014170430.tif 000014