トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 優先順位検索方法
【発明者】 【氏名】林 孝則
【住所又は居所】東京都品川区大崎２丁目１番１７号 株式会社明電舎内
【要約】 【課題】大きなビットマップの場合でも検索性能の向上を図る。

【解決手段】ＯＳのスケジューラでは、実行待ちタスクの中から優先度の高いタスクを効率的に見つけ出すために、優先度毎にタスクをキューに繋ぐ手段を採っている。所が、優先度数が多い場合には、高優先度のキューから順に空きか、否かをチェックすると、ビットマップＢＴＭ自体が大きくなって検索が効率的でない。そこで、各キューが空きか、否かをビットマップＢＴＭに表現した。例えば、サイズ「１０２４」のビットマップＢＴＭ］には、インデックスＩＮＤを付ける。スケジューラは、インデックスＩＮＤ付きビットマップＢＴＭから「１」である最大の位置番号を検索して、キューが空きでない最高の優先度を取得し、対応するキューから次に実行するべきタスクを選択するようにする。
【特許請求の範囲】
【請求項１】
タスクの動作の優先順位を管理する方法であって、その優先順位を、ワード配列を用いてビットマップで表現し、このビットマップにワード毎のインデックスを付して、各ワード毎にビット「１」が立っているかどうかを、他のデータを用いて管理し、他のデータの各ビットと１対１の対応関係を持ち、ビット「１」が立っているとき、ワードに「１」のビットがあることを確認した後、他のデータを用いて最下位の「１」ビットを検索することを特徴とする優先順位検索方法。
【請求項２】
前記ビットマップのサイズが大きいときには、ビットマップ毎にインデックスを２段以上にすることを特徴とする請求項１記載の優先順位検索方法。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】
この発明は、タスクの動作の優先順位を管理する方法であって、特にビットマップにワード毎にインディックスを付して検索性能の向上を図った優先順位検索方法に関するものである。
【０００２】
【従来の技術】
コンピュータ装置に設けられているＣＰＵには、上記タスク動作の優先順位を管理する手段が備えられている。この優先順位を管理するために、タスク動作の優先順位と１対１に対応するビットマップを用い、このビットを検索することにより、次に動作させるタスクの検索を行っている（例えば、特許文献１参照。）。
【０００３】
上記のようなタスクの優先順位と１対１に対応するビットマップの場合、例えば、優先度が３２ビット以下であると、ビットマップが１ワードに収まって効率的である。しかし、優先度が上記ＣＰＵの１ワードに収まらない長いビットマップにおいては、ワード配列を用いた、図５に示すようなビットマップを用いている。
【０００４】
図５は、３２ビット・ワードを３２個並べてサイズ「１０２４」のビットマップを表現した説明図である。図５において、１個の四角形の桝目が「１」ビットを表し、その四角形の桝目内の数字はビットの（０から始まる）位置番号で、その位置番号は、「００００」から「１０２３」まである。
【０００５】
上記のようなビットマップにおいて、ビットの並び順で最初の「１」であるビットを検索するには、ビットマップを構成するワード配列のワードを順番に調べていって「０」でない最初のワードを見つけ、そのワード内で「１」のビットを探す方法が採られている。（後述の図６、図７のフローチャート参照）
また、ビットマップに対する上記のような検索は、高速に行いたいので、専用のＣＰＵ命令を持たせることもある。
【０００６】
図６は、長いビットマップから「１」のビットを検索するフローチャートで、この図６においては、図５で示したビットマップから、「１」であるビットで最大の位置番号を持つものを探して、その位置番号を得ることを条件とするものである。なお、位置番号「０」（００００）のビットは、必ず「１」であるとする。
【０００７】
図６において、まず、ステップＳ１で位置番号「３１」をワード「Ｗ」とし、ステップＳ２でワード「Ｗ」が「０」か（ＹＥＳ）、「０」でないか（ＮＯ）を判定し、「ＹＥＳ」ならステップＳ３で「Ｗ−１」をワード「Ｗ」とする処理をした後、ステップＳ２にて再び処理を行なう。ステップＳ２で「ＮＯ」ならステップＳ４の処理を行なう。
【０００８】
ステップＳ４の処理は、後述する図７に示す処理を呼び出して行なう。ステップＳ４では、ワード「Ｗ」で「１」である最下位ビット位置を探して「ｂ」とする。この「ｂ」は、ステップＳ５に示す式に入力して演算処理され、位置番号「ｎｕｍ」を得る。
【０００９】
図７は、１ワードのビットマップから「１」のビットを検索するフローチャートで、１ワードのビットマップ（ｗｏｒｄ）から、「１」であるビットで最下位のものを探してＬＳＢを「０」、ＭＳＢを「３１」とするビット位置を得ることを条件とするものである。なお、ワードは「０」でないものとする。
【００１０】
図７において、ステップＳ１１にて「０」を位置番号「ｎｕｍ」とした後、ステップＳ１２にて下位１６ビットが「０」であるかどうかを判定し、「ＹＥＳ」ならステップＳ１３の処理を行ない、「ＮＯ」ならステップＳ１４の判定処理を行なう。ステップＳ１３では、下位１６ビットが「０」ならば上位１６ビットに「１」がある処理（ｎｕｍ←ｎｕｍ＋１６）を、また、左へ１６ビットシフトの処理（ｗｏｒｄ←ｗｏｒｄ＞＞１６）を行なう。
【００１１】
次に、ステップＳ１４では、下位８ビットが「０」であるかどうかを判定し、「ＹＥＳ」ならステップＳ１５の処理を行ない、「ＮＯ」ならステップＳ１６の判定処理を行なう。ステップＳ１５では、下位８ビットが「０」ならば上位８ビットに「１」がある処理（ｎｕｍ←ｎｕｍ＋８）を、また、左へ８ビットシフトの処理（ｗｏｒｄ←ｗｏｒｄ＞＞８）を行なう。以下順次、４ビット、２ビット、１ビットの処理をステップＳ２１まで行なう。
【００１２】
【特許文献１】
特開平５−３４２０２２号公報（第２頁−第３頁、図１−図４）。
【００１３】
【発明が解決しようとする課題】
通常、ビットマップの検索は、配列の添字順に線形に行われるので、演算時間はビットマップの長さに比例して長くなる。従って、ビットマップが長いと検索性能の低下が生じる。このため、専用のＣＰＵ命令が無い場合は、特にその検索性能の低下が著しくなる問題が起こる。
【００１４】
この発明は、上記の事情に鑑みてなされたもので、ビットマップにインデックスを付けることにより、大きなビットマップの場合でも検索性能の向上を図ることができる優先順位検索方法を提供することを課題とする。
【００１５】
【課題を解決するための手段】
この発明は、上記の課題を達成するために、第１発明は、タスクの動作の優先順位を管理する方法であって、その優先順位を、ワード配列を用いてビットマップで表現し、このビットマップにワード毎のインデックスを付して、各ワード毎にビット「１」が立っているかどうかを、他のデータを用いて管理し、他のデータの各ビットと１対１の対応関係を持ち、ビット「１」が立っているとき、ワードに「１」のビットがあることを確認した後、他のデータを用いて最下位の「１」ビットを検索することを特徴とする優先順位検索方法である。
【００１６】
第２発明は、前記ビットマップのサイズが大きいときには、ビットマップ毎にインデックスを２段以上にすることを特徴とする優先順位検索方法である。
【００１７】
【発明の実施の形態】
以下この発明の実施の形態を図面に基づいて説明する。図１はこの発明の実施の第１形態を示す説明図で、この実施の第１形態は、優先度付き実行待ちタスクから最高優先度のタスクを探す方法である。
【００１８】
リアルタイムＯＳ（オペレーティング・システム）のスケジューラでは、実行待ちタスクの中から優先度の高いタスクを効率的に見つけ出すために優先度毎にタスクをキュー（待ち行列）に繋ぐ手段を採っている。
【００１９】
ここで、優先度数が少ない（例えば、一桁）場合には、キューの数も少ないので、高優先度のキューから順に空きか、否かのチェックを行なっていっても大した負荷にはならない。例えば、優先度が「３２」ビット以下であると、ビットマップが「１」ワードに収まって効率的である。
【００２０】
しかし、優先度数が多い（例えば、数十〜数千）場合には、高優先度のキューから順に空きか、否かをチェックするのでは、ビットマップ自体が大きくなって検索が効率的でない。そこで、各キューが空きか、否かをビットマップに表現して、検索の効率化を図ることを、見出したのが、上記図１の実施の第１形態である。
【００２１】
図１は、ビットマップＢＴＭにインデックスＩＮＤを付けて検索の効率化を図った説明図で、３２ビット・ワードを３２個並べてサイズ「１０２４」のビットマップＢＴＭにインデックスＩＮＤを付けたものである。そして、インデックスＩＮＤの各ビットは、図１に示したように対応付けた各ワードが「０」のとき「０」とし、「０」でないときに「１」とする。
【００２２】
図１において、優先度は「０」〜「１０２３」を採り、数字が大きいほど優先度が高いものとする。ＯＳ（オペレーティング・システム）は予め実行可能キューが空きでない優先度に対応するビットマップＢＴＭの位置番号のビットを「１」にしてあるものとする。また、アイドルタスクがあるために、優先度「０」のキューは空きでなく、ビットマップＢＴＭの位置番号「０」は必ず「１」であるとする。
【００２３】
スケジューラは、インデックス付きビットマップＢＴＭから「１」である最大の位置番号を検索して、キューが空きでない最高の優先度を取得し、対応するキューから次に実行するべきタスクを選択する。
【００２４】
インデックス付きビットマップＢＴＭの検索では、まずインデックスＩＮＤに対して図７に示すフローチャート（アルゴリズム）を使用して「１」である最下位ビットの位置を得、これから「１」である最大の位置番号のビットを含むワードの添字番号を計算する。
【００２５】
次に、この「０」でないワードに対して図７に示すアルゴリズムを使用して、「１」である最下位ビットを得、これと先ほどのワードの添字番号とからビットマップの位置番号を図２に示すフローチャートのように計算する。
【００２６】
図２はインデックス付きビットマップで「１」のビットを検索するフローチャートで、このフローチャートでは、図１に示したビットマップから、「１」であるビットで最大の位置番号を持つものを探して、その位置番号を得る。なお、位置番号「０」のビットは、必ず「１」であるとする。
【００２７】
図２において、ステップＳ３１で図７の処理を呼び出し、インデックスで「１」である最下位ビット位置をワード「Ｗ」とする。そのワード「Ｗ」をステップＳ３２の処理で「３１−Ｗ」をワード「Ｗ」とする。
【００２８】
その後、ステップＳ３３で再び図７の処理を呼び出して、ワード「Ｗ」で「１」である最下位ビット位置を「ｂ」と処理する。この「ｂ」をステップＳ３４に示す式（ｎｕｍ←Ｗ＊３２＋３１−ｂ）で演算処理して終了し、その演算結果として位置番号「ｎｕｍ」を得る。
【００２９】
図３はこの発明の実施の第２形態を示す説明図で、この第２形態は、大きなビットマップから「１」のビットを検索するものである。上記第１形態では、サイズ「１０２４」以下程度のビットマップから「１」であるビットで位置番号が最大のものを検索した。
【００３０】
さらに、大きいビットマップでも、第１形態で示したインデックスを、１ワードから２ワード以上にすれば同じ様な処理ができる。このように処理に基づいた方法が図３に示すインデックスを２段以上にしたものである。
【００３１】
図３は、インデックスを、主インデックスＭ−ＩＮＤ、副インデックスＳＢ１−ＩＮＤ〜ＳＢｎ−ＩＮＤとして、ビットマップが大きくなった場合の例で、３２ビット・ワードを「１０２４」個並べてサイズ「３２７６８」のビットマップを２段インデックスで作った例である。主インデックスＭ−ＩＮＤおよび副インデックスＳＢ１−ＩＮＤ，ＳＢ２−ＩＮＤの各ビットは、図３で対応付けた各ワードが「０」のとき「０」とし、「０」でないときに「１」とする。
【００３２】
ビットマップがさらに大きい場合、３段、４段のインデックスへの拡張も容易である。インデックスの段数を増加することで一段ごとに３２倍ずつ大きなビットマップを扱える。
【００３３】
図４は、実施の第２形態における２段インデックス付きビットマップで「１」のビットを検索するフローチャートで、このフローチャートでは、図３で示したビットマップから、「１」であるビットで最大の位置番号を持つものを探してその位置番号を得る。なお、位置番号「０」のビットはかならず「１」であるとする。
【００３４】
図４において、ステップＳ４１で図７の処理を呼び出して、インデックスで「１」である最下位ビット位置を「Ｗ」とする。次に、ステップＳ４２で「３１−Ｗ」を「Ｗ」とする。
【００３５】
その後、図７の処理を呼び出して、ステップＳ４３で副索引［Ｗ］で「１」である最下位ビット位置を「Ｘ」とする。次にこの「Ｘ」をステップＳ４４で「３１−Ｘ」をワード「Ｘ」とする。
【００３６】
ステップＳ４４で得られたワード「Ｘ」をステップＳ４５で図７の処理を再び呼び出して、ワード「Ｘ」で「１」である最下位ビット位置を「ｂ」として、ステップＳ４６の式（Ｗ＊１０２４＋Ｘ＊３２＋３１−ｂ）を用いて演算し、位置番号「ｎｕｍ」とする。
【００３７】
上記各実施の形態においては、コンピュータ装置を用いて処理される。コンピュータ装置には、図示しないが外部記憶装置などの入出力装置などが使用されている。
【００３８】
【発明の効果】
以上述べたように、この発明によれば、ビットマップにインデックスを付けることにより、サイズ「１０００」程度のビットマップで検索性能を向上させることができる。また、インデックス付けを複数多段で行なうことにより、更に大きなビットマップでも検索性能を向上させることができる。
【図面の簡単な説明】
【図１】この発明の実施の第１形態を示す説明図。
【図２】インデックス付きビットマップで「１」のビットを検索するフローチャート。
【図３】この発明の実施の第２形態を示す説明図。
【図４】実施の第２形態における２段インデックス付きビットマップで１のビットを検索するフローチャート。
【図５】３２ビット・ワードを３２個並べてサイズ「１０２４」のビットマップを表現した説明図。
【図６】長いビットマップから「１」のビットを検索するフローチャート。
【図７】１ワードのビットマップから「１」のビットを検索するフローチャート。
【符号の説明】
ＩＮＤ…インデックス
ＢＴＭ…ビットマップ
ｎｕｍ…位置番号
【出願人】 【識別番号】０００００６１０５
【氏名又は名称】株式会社明電舎
【住所又は居所】東京都品川区大崎２丁目１番１７号
【出願日】 平成１４年１１月１４日（２００２．１１．１４）
【代理人】 【識別番号】１０００９６４５９
【弁理士】
【氏名又は名称】橋本 剛
【公開番号】 特開２００４−１６４３５０（Ｐ２００４−１６４３５０Ａ）
【公開日】 平成１６年６月１０日（２００４．６．１０）
【出願番号】 特願２００２−３３０１８８（Ｐ２００２−３３０１８８）