【０００１】
【発明の属する技術分野】
この発明は、タスクの動作の優先順位を管理する方法であって、特にビットマップにワード毎にインディックスを付して検索性能の向上を図った優先順位検索方法に関するものである。
【０００２】
【従来の技術】
コンピュータ装置に設けられているＣＰＵには、上記タスク動作の優先順位を管理する手段が備えられている。この優先順位を管理するために、タスク動作の優先順位と１対１に対応するビットマップを用い、このビットを検索することにより、次に動作させるタスクの検索を行っている（例えば、特許文献１参照。）。
【０００３】
上記のようなタスクの優先順位と１対１に対応するビットマップの場合、例えば、優先度が３２ビット以下であると、ビットマップが１ワードに収まって効率的である。しかし、優先度が上記ＣＰＵの１ワードに収まらない長いビットマップにおいては、ワード配列を用いた、図５に示すようなビットマップを用いている。
【０００４】
図５は、３２ビット・ワードを３２個並べてサイズ「１０２４」のビットマップを表現した説明図である。図５において、１個の四角形の桝目が「１」ビットを表し、その四角形の桝目内の数字はビットの（０から始まる）位置番号で、その位置番号は、「００００」から「１０２３」まである。
【０００５】
上記のようなビットマップにおいて、ビットの並び順で最初の「１」であるビットを検索するには、ビットマップを構成するワード配列のワードを順番に調べていって「０」でない最初のワードを見つけ、そのワード内で「１」のビットを探す方法が採られている。（後述の図６、図７のフローチャート参照）
また、ビットマップに対する上記のような検索は、高速に行いたいので、専用のＣＰＵ命令を持たせることもある。
【０００６】
図６は、長いビットマップから「１」のビットを検索するフローチャートで、この図６においては、図５で示したビットマップから、「１」であるビットで最大の位置番号を持つものを探して、その位置番号を得ることを条件とするものである。なお、位置番号「０」（００００）のビットは、必ず「１」であるとする。
【０００７】
図６において、まず、ステップＳ１で位置番号「３１」をワード「Ｗ」とし、ステップＳ２でワード「Ｗ」が「０」か（ＹＥＳ）、「０」でないか（ＮＯ）を判定し、「ＹＥＳ」ならステップＳ３で「Ｗ−１」をワード「Ｗ」とする処理をした後、ステップＳ２にて再び処理を行なう。ステップＳ２で「ＮＯ」ならステップＳ４の処理を行なう。
【０００８】
ステップＳ４の処理は、後述する図７に示す処理を呼び出して行なう。ステップＳ４では、ワード「Ｗ」で「１」である最下位ビット位置を探して「ｂ」とする。この「ｂ」は、ステップＳ５に示す式に入力して演算処理され、位置番号「ｎｕｍ」を得る。
【０００９】
図７は、１ワードのビットマップから「１」のビットを検索するフローチャートで、１ワードのビットマップ（ｗｏｒｄ）から、「１」であるビットで最下位のものを探してＬＳＢを「０」、ＭＳＢを「３１」とするビット位置を得ることを条件とするものである。なお、ワードは「０」でないものとする。
【００１０】
図７において、ステップＳ１１にて「０」を位置番号「ｎｕｍ」とした後、ステップＳ１２にて下位１６ビットが「０」であるかどうかを判定し、「ＹＥＳ」ならステップＳ１３の処理を行ない、「ＮＯ」ならステップＳ１４の判定処理を行なう。ステップＳ１３では、下位１６ビットが「０」ならば上位１６ビットに「１」がある処理（ｎｕｍ←ｎｕｍ＋１６）を、また、左へ１６ビットシフトの処理（ｗｏｒｄ←ｗｏｒｄ＞＞１６）を行なう。
【００１１】
次に、ステップＳ１４では、下位８ビットが「０」であるかどうかを判定し、「ＹＥＳ」ならステップＳ１５の処理を行ない、「ＮＯ」ならステップＳ１６の判定処理を行なう。ステップＳ１５では、下位８ビットが「０」ならば上位８ビットに「１」がある処理（ｎｕｍ←ｎｕｍ＋８）を、また、左へ８ビットシフトの処理（ｗｏｒｄ←ｗｏｒｄ＞＞８）を行なう。以下順次、４ビット、２ビット、１ビットの処理をステップＳ２１まで行なう。
【００１２】
【特許文献１】
特開平５−３４２０２２号公報（第２頁−第３頁、図１−図４）。
【００１３】
【発明が解決しようとする課題】
通常、ビットマップの検索は、配列の添字順に線形に行われるので、演算時間はビットマップの長さに比例して長くなる。従って、ビットマップが長いと検索性能の低下が生じる。このため、専用のＣＰＵ命令が無い場合は、特にその検索性能の低下が著しくなる問題が起こる。
【００１４】
この発明は、上記の事情に鑑みてなされたもので、ビットマップにインデックスを付けることにより、大きなビットマップの場合でも検索性能の向上を図ることができる優先順位検索方法を提供することを課題とする。
【００１５】
【課題を解決するための手段】
この発明は、上記の課題を達成するために、第１発明は、タスクの動作の優先順位を管理する方法であって、その優先順位を、ワード配列を用いてビットマップで表現し、このビットマップにワード毎のインデックスを付して、各ワード毎にビット「１」が立っているかどうかを、他のデータを用いて管理し、他のデータの各ビットと１対１の対応関係を持ち、ビット「１」が立っているとき、ワードに「１」のビットがあることを確認した後、他のデータを用いて最下位の「１」ビットを検索することを特徴とする優先順位検索方法である。
【００１６】
第２発明は、前記ビットマップのサイズが大きいときには、ビットマップ毎にインデックスを２段以上にすることを特徴とする優先順位検索方法である。
【００１７】
【発明の実施の形態】
以下この発明の実施の形態を図面に基づいて説明する。図１はこの発明の実施の第１形態を示す説明図で、この実施の第１形態は、優先度付き実行待ちタスクから最高優先度のタスクを探す方法である。
【００１８】
リアルタイムＯＳ（オペレーティング・システム）のスケジューラでは、実行待ちタスクの中から優先度の高いタスクを効率的に見つけ出すために優先度毎にタスクをキュー（待ち行列）に繋ぐ手段を採っている。
【００１９】
ここで、優先度数が少ない（例えば、一桁）場合には、キューの数も少ないので、高優先度のキューから順に空きか、否かのチェックを行なっていっても大した負荷にはならない。例えば、優先度が「３２」ビット以下であると、ビットマップが「１」ワードに収まって効率的である。
【００２０】
しかし、優先度数が多い（例えば、数十〜数千）場合には、高優先度のキューから順に空きか、否かをチェックするのでは、ビットマップ自体が大きくなって検索が効率的でない。そこで、各キューが空きか、否かをビットマップに表現して、検索の効率化を図ることを、見出したのが、上記図１の実施の第１形態である。
【００２１】
図１は、ビットマップＢＴＭにインデックスＩＮＤを付けて検索の効率化を図った説明図で、３２ビット・ワードを３２個並べてサイズ「１０２４」のビットマップＢＴＭにインデックスＩＮＤを付けたものである。そして、インデックスＩＮＤの各ビットは、図１に示したように対応付けた各ワードが「０」のとき「０」とし、「０」でないときに「１」とする。
【００２２】
図１において、優先度は「０」〜「１０２３」を採り、数字が大きいほど優先度が高いものとする。ＯＳ（オペレーティング・システム）は予め実行可能キューが空きでない優先度に対応するビットマップＢＴＭの位置番号のビットを「１」にしてあるものとする。また、アイドルタスクがあるために、優先度「０」のキューは空きでなく、ビットマップＢＴＭの位置番号「０」は必ず「１」であるとする。
【００２３】
スケジューラは、インデックス付きビットマップＢＴＭから「１」である最大の位置番号を検索して、キューが空きでない最高の優先度を取得し、対応するキューから次に実行するべきタスクを選択する。
【００２４】
インデックス付きビットマップＢＴＭの検索では、まずインデックスＩＮＤに対して図７に示すフローチャート（アルゴリズム）を使用して「１」である最下位ビットの位置を得、これから「１」である最大の位置番号のビットを含むワードの添字番号を計算する。
【００２５】
次に、この「０」でないワードに対して図７に示すアルゴリズムを使用して、「１」である最下位ビットを得、これと先ほどのワードの添字番号とからビットマップの位置番号を図２に示すフローチャートのように計算する。
【００２６】
図２はインデックス付きビットマップで「１」のビットを検索するフローチャートで、このフローチャートでは、図１に示したビットマップから、「１」であるビットで最大の位置番号を持つものを探して、その位置番号を得る。なお、位置番号「０」のビットは、必ず「１」であるとする。
【００２７】
図２において、ステップＳ３１で図７の処理を呼び出し、インデックスで「１」である最下位ビット位置をワード「Ｗ」とする。そのワード「Ｗ」をステップＳ３２の処理で「３１−Ｗ」をワード「Ｗ」とする。
【００２８】
その後、ステップＳ３３で再び図７の処理を呼び出して、ワード「Ｗ」で「１」である最下位ビット位置を「ｂ」と処理する。この「ｂ」をステップＳ３４に示す式（ｎｕｍ←Ｗ＊３２＋３１−ｂ）で演算処理して終了し、その演算結果として位置番号「ｎｕｍ」を得る。
【００２９】
図３はこの発明の実施の第２形態を示す説明図で、この第２形態は、大きなビットマップから「１」のビットを検索するものである。上記第１形態では、サイズ「１０２４」以下程度のビットマップから「１」であるビットで位置番号が最大のものを検索した。
【００３０】
さらに、大きいビットマップでも、第１形態で示したインデックスを、１ワードから２ワード以上にすれば同じ様な処理ができる。このように処理に基づいた方法が図３に示すインデックスを２段以上にしたものである。
【００３１】
図３は、インデックスを、主インデックスＭ−ＩＮＤ、副インデックスＳＢ１−ＩＮＤ〜ＳＢｎ−ＩＮＤとして、ビットマップが大きくなった場合の例で、３２ビット・ワードを「１０２４」個並べてサイズ「３２７６８」のビットマップを２段インデックスで作った例である。主インデックスＭ−ＩＮＤおよび副インデックスＳＢ１−ＩＮＤ，ＳＢ２−ＩＮＤの各ビットは、図３で対応付けた各ワードが「０」のとき「０」とし、「０」でないときに「１」とする。
【００３２】
ビットマップがさらに大きい場合、３段、４段のインデックスへの拡張も容易である。インデックスの段数を増加することで一段ごとに３２倍ずつ大きなビットマップを扱える。
【００３３】
図４は、実施の第２形態における２段インデックス付きビットマップで「１」のビットを検索するフローチャートで、このフローチャートでは、図３で示したビットマップから、「１」であるビットで最大の位置番号を持つものを探してその位置番号を得る。なお、位置番号「０」のビットはかならず「１」であるとする。
【００３４】
図４において、ステップＳ４１で図７の処理を呼び出して、インデックスで「１」である最下位ビット位置を「Ｗ」とする。次に、ステップＳ４２で「３１−Ｗ」を「Ｗ」とする。
【００３５】
その後、図７の処理を呼び出して、ステップＳ４３で副索引［Ｗ］で「１」である最下位ビット位置を「Ｘ」とする。次にこの「Ｘ」をステップＳ４４で「３１−Ｘ」をワード「Ｘ」とする。
【００３６】
ステップＳ４４で得られたワード「Ｘ」をステップＳ４５で図７の処理を再び呼び出して、ワード「Ｘ」で「１」である最下位ビット位置を「ｂ」として、ステップＳ４６の式（Ｗ＊１０２４＋Ｘ＊３２＋３１−ｂ）を用いて演算し、位置番号「ｎｕｍ」とする。
【００３７】
上記各実施の形態においては、コンピュータ装置を用いて処理される。コンピュータ装置には、図示しないが外部記憶装置などの入出力装置などが使用されている。
【００３８】
【発明の効果】
以上述べたように、この発明によれば、ビットマップにインデックスを付けることにより、サイズ「１０００」程度のビットマップで検索性能を向上させることができる。また、インデックス付けを複数多段で行なうことにより、更に大きなビットマップでも検索性能を向上させることができる。
【図面の簡単な説明】
【図１】この発明の実施の第１形態を示す説明図。
【図２】インデックス付きビットマップで「１」のビットを検索するフローチャート。
【図３】この発明の実施の第２形態を示す説明図。
【図４】実施の第２形態における２段インデックス付きビットマップで１のビットを検索するフローチャート。
【図５】３２ビット・ワードを３２個並べてサイズ「１０２４」のビットマップを表現した説明図。
【図６】長いビットマップから「１」のビットを検索するフローチャート。
【図７】１ワードのビットマップから「１」のビットを検索するフローチャート。
【符号の説明】
ＩＮＤ…インデックス
ＢＴＭ…ビットマップ
ｎｕｍ…位置番号[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a method for managing priorities of task operations, and more particularly to a priority search method in which a bitmap is indexed for each word to improve search performance.
[0002]
[Prior art]
The CPU provided in the computer device has means for managing the priority of the task operation. In order to manage the priority, a bit map corresponding to the priority of the task operation in a one-to-one correspondence is used to search for this bit, thereby searching for a task to be operated next (for example, see Patent Document 1). 1).
[0003]
In the case of a bitmap corresponding to the task priorities one-to-one as described above, for example, if the priority is 32 bits or less, the bitmap fits in one word and is efficient. However, in a long bitmap whose priority does not fit in one word of the CPU, a bitmap using a word array as shown in FIG. 5 is used.
[0004]
FIG. 5 is an explanatory diagram expressing a 32-bit word by arranging 32 32-bit words. In FIG. 5, one square cell represents "1" bit, and the number in the square cell is a position number (starting from 0) of a bit, and the position numbers are from "0000" to "1023". is there.
[0005]
To search for the first "1" bit in the bit order in the bitmap as described above, the first word that is not "0" is checked by sequentially examining the words of the word array constituting the bitmap. And a method of searching for a “1” bit in the word. (Refer to the flowcharts of FIGS. 6 and 7 described below)
In addition, since the above search for the bitmap is desired to be performed at high speed, a dedicated CPU instruction may be provided.
[0006]
FIG. 6 is a flowchart for searching for a bit of "1" from a long bitmap. In FIG. 6, the bitmap shown in FIG. 5 is searched for a bit of "1" having the largest position number. And the position number must be obtained. It is assumed that the bit of the position number “0” (0000) is always “1”.
[0007]
6, first, in step S1, the position number "31" is set to the word "W", and in step S2, it is determined whether the word "W" is "0" (YES) or not "0" (NO). If "YES", a process of changing "W-1" to the word "W" is performed in step S3, and then the process is performed again in step S2. If "NO" in the step S2, the process of the step S4 is performed.
[0008]
The process in step S4 is performed by calling a process shown in FIG. In step S4, the least significant bit position that is "1" in the word "W" is searched for and set to "b". This “b” is input to the equation shown in step S5 and is subjected to arithmetic processing to obtain a position number “num”.
[0009]
FIG. 7 is a flowchart for searching for a bit of “1” from a bit map of one word, searching for the least significant bit of “1” from a bit map (word) of one word and setting the LSB to “0”. , MSB are set to "31". Note that the word is not “0”.
[0010]
In FIG. 7, after "0" is set to the position number "num" in step S11, it is determined in step S12 whether the lower 16 bits are "0", and if "YES", the process in step S13 is performed. If "NO", the determination processing of step S14 is performed. In step S13, if the lower 16 bits are "0", a process in which the upper 16 bits have "1" (num ← num + 16) and a process of shifting 16 bits to the left (word ← word >> 16) are performed.
[0011]
Next, in step S14, it is determined whether or not the lower 8 bits are "0". If "YES", the process in step S15 is performed, and if "NO", the determination process in step S16 is performed. In step S15, if the lower 8 bits are "0", a process in which the upper 8 bits have "1" (num ← num + 8) and a process of shifting left by 8 bits (word ← word >> 8) are performed. Thereafter, processing of 4 bits, 2 bits, and 1 bit is sequentially performed until step S21.
[0012]
[Patent Document 1]
JP-A-5-342022 (pages 2 to 3, FIGS. 1 to 4).
[0013]
[Problems to be solved by the invention]
Normally, the search of the bitmap is performed linearly in the order of the subscripts of the array, so that the operation time increases in proportion to the length of the bitmap. Therefore, if the bitmap is long, the search performance is reduced. For this reason, when there is no dedicated CPU instruction, there is a problem that the search performance is significantly reduced.
[0014]
The present invention has been made in view of the above circumstances, and an object of the present invention is to provide a priority search method capable of improving search performance even for a large bitmap by indexing the bitmap. I do.
[0015]
[Means for Solving the Problems]
In order to achieve the above object, a first aspect of the present invention is a method for managing the priority of a task operation. The priority is expressed by a bit map using a word array, and An index is assigned to each word in the map, and whether or not bit “1” is set for each word is managed using other data, and has a one-to-one correspondence with each bit of other data. , When the bit "1" is set, it is confirmed that the word has the bit of "1", and then the least significant "1" bit is searched using other data. Is the way.
[0016]
A second invention is a priority search method characterized in that when the size of the bitmap is large, the index is set to two or more stages for each bitmap.
[0017]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings. FIG. 1 is an explanatory diagram showing a first embodiment of the present invention. This first embodiment is a method of searching for a task with the highest priority from tasks with a priority to be executed.
[0018]
The scheduler of a real-time OS (operating system) employs means for connecting tasks to a queue (queue) for each priority in order to efficiently find a task with a high priority from tasks waiting to be executed.
[0019]
Here, when the number of priorities is small (for example, one digit), the number of queues is also small. Therefore, even if checking is performed in order from the queue with the highest priority to whether or not it is empty, it does not become a significant load. . For example, if the priority is less than or equal to "32" bits, the bitmap will fit in a "1" word, which is efficient.
[0020]
However, when the number of priorities is large (for example, several tens to several thousands), it is not efficient to search in order from a high priority queue to see if the queue is empty, because the bitmap itself becomes large and the search is not efficient. Therefore, the first embodiment of FIG. 1 has been found to express whether each queue is empty or not in a bitmap to improve the efficiency of the search.
[0021]
FIG. 1 is an explanatory diagram in which an index IND is added to a bitmap BTM to improve the efficiency of search. In this figure, 32 32-bit words are arranged and a bitmap BTM having a size of “1024” is provided with an index IND. Each bit of the index IND is set to “0” when the associated word is “0” as shown in FIG. 1, and is set to “1” when the associated word is not “0”.
[0022]
In FIG. 1, the priority ranges from “0” to “1023”, and the higher the number, the higher the priority. It is assumed that the OS (operating system) has previously set the bit of the position number of the bitmap BTM corresponding to the priority at which the executable queue is not empty to “1”. It is also assumed that the queue of priority “0” is not empty because there is an idle task, and the position number “0” of the bitmap BTM is always “1”.
[0023]
The scheduler searches the indexed bitmap BTM for the maximum position number “1”, acquires the highest priority in which the queue is not empty, and selects the next task to be executed from the corresponding queue.
[0024]
In the search of the indexed bitmap BTM, first, the position of the least significant bit which is “1” is obtained for the index IND by using the flowchart (algorithm) shown in FIG. Calculate the subscript number of the word containing the bits of.
[0025]
Next, using the algorithm shown in FIG. 7 for the word other than "0", the least significant bit of "1" is obtained, and the position number of the bit map is figured out from this and the subscript number of the previous word. The calculation is performed as shown in the flowchart of FIG.
[0026]
FIG. 2 is a flowchart for searching the bit of "1" in the indexed bitmap. In this flowchart, the bitmap shown in FIG. 1 is searched for the bit having "1" having the largest position number. Get the position number. It is assumed that the bit of the position number “0” is always “1”.
[0027]
In FIG. 2, the process of FIG. 7 is called in step S31, and the least significant bit position whose index is “1” is set as a word “W”. The word “W” is set to the word “W” in the process of step S32 and “31−W” is set to the word “W”.
[0028]
Thereafter, in step S33, the process of FIG. 7 is called again, and the least significant bit position of “1” in the word “W” is processed as “b”. This “b” is processed by the equation (num ← W * 32 + 31−b) shown in step S34 and the processing is terminated, and the position number “num” is obtained as the calculation result.
[0029]
FIG. 3 is an explanatory diagram showing a second embodiment of the present invention. In the second embodiment, a bit of "1" is searched from a large bit map. In the first embodiment, the bit having the maximum position number of the bit “1” is searched from the bitmap having the size of “1024” or less.
[0030]
Further, even for a large bitmap, the same processing can be performed by changing the index shown in the first embodiment from one word to two or more words. Thus, the method based on the processing is such that the index shown in FIG.
[0031]
FIG. 3 shows an example in which the index is set to the main index M-IND and the sub-indexes SB1-IND to SBn-IND, and the bitmap becomes large. In this example, "1024" 32-bit words are arranged and the size is "32768". This is an example in which a bitmap is created using a two-stage index. Each bit of the main index M-IND and the sub-indexes SB1-IND and SB2-IND is set to "0" when each word associated in FIG. 3 is "0", and is set to "1" when each word is not "0". .
[0032]
If the bitmap is even larger, it is easy to expand to a three-stage or four-stage index. By increasing the number of index stages, a bitmap that is 32 times larger for each stage can be handled.
[0033]
FIG. 4 is a flowchart for searching for the bit of “1” in the two-stage indexed bitmap according to the second embodiment. In this flowchart, from the bitmap shown in FIG. Find the one with the position number and get the position number. It is assumed that the bit of the position number “0” is always “1”.
[0034]
In FIG. 4, the process of FIG. 7 is called in step S41, and the least significant bit position whose index is “1” is set to “W”. Next, "31-W" is set to "W" in step S42.
[0035]
Thereafter, the process of FIG. 7 is called, and the least significant bit position of “1” in the sub index [W] is set to “X” in step S43. Next, this “X” is made into a word “X” by “31-X” in step S44.
[0036]
The process of FIG. 7 is called again in step S45 for the word “X” obtained in step S44, and the least significant bit position of “1” in word “X” is set to “b”, and the expression (W * 1024 + X * 32 + 31-b) to obtain a position number "num".
[0037]
In each of the above embodiments, processing is performed using a computer device. Although not shown, an input / output device such as an external storage device is used for the computer device.
[0038]
【The invention's effect】
As described above, according to the present invention, the indexing of a bitmap can improve the search performance with a bitmap having a size of about "1000". Also, by performing indexing in multiple stages, search performance can be improved even with a larger bitmap.
[Brief description of the drawings]
FIG. 1 is an explanatory view showing a first embodiment of the present invention.
FIG. 2 is a flowchart for searching for a “1” bit in an indexed bitmap.
FIG. 3 is an explanatory view showing a second embodiment of the present invention.
FIG. 4 is a flowchart for searching for one bit in a two-stage indexed bitmap according to the second embodiment;
FIG. 5 is an explanatory diagram expressing a 32-bit size bitmap by arranging 32 32-bit words.
FIG. 6 is a flowchart for searching for a “1” bit from a long bitmap.
FIG. 7 is a flowchart for searching for a bit of “1” from a bit map of one word.
[Explanation of symbols]
IND: Index BTM: Bitmap num: Position number