(57)【特許請求の範囲】
【請求項１】
一つのプロセッサにより複数のタスクの管理を行うタスク管理システムにおいて、
任意のタスクに関する情報のうち、少なくとも上記タスクの優先度情報を含む上記タスクのスケジューリングに関係する情報を保持するデータブロックであるアクティビティと、
上記タスクに関する情報のうち、上記アクティビティに記録されていない情報を保持するデータブロックであるコンテキストと、
実行可能なタスクの中から、もっとも優先度が高いものを選択するために設けられたディスパッチキューと、
タスクの相互排除の機構であるミューテックスの所有を待つタスクを記録するミューテックス待ちキューと、
タスクが所有しているミューテックスを記録する所有オブジェクトキューと
を備え、
一つのタスクに関する情報を、上記アクティビティと上記コンテキストに分割して管理し、
上記アクティビティを上記ディスパッチキューへの挿入または削除の対象としており、
あるタスクの優先度を他のタスクが継承する際には、上記ディスパッチキュー、上記ミューテックス待ちキュー、および上記所有オブジェクトキューを用いて、上記アクティビティと、上記コンテキストの対応関係だけを変化させて処理するようにしたことを特徴とするタスク管理システム。
【請求項２】
請求項１記載のタスク管理システムにおいて、
上記優先度継承を行う条件変数によってタスクの実行を停止させる必要が生じても、上記ディスパッチキューに対して即座に操作を行うことなく、その他の条件変数によって、タスクの実行を停止させる必要が生じるまで、上記ディスパッチキューに対する操作を延期することを特徴とするタスク管理システム。
【請求項３】
一つのプロセッサにより複数のタスクの管理を行うタスク管理方法において、
一つのタスクに関する情報を、任意のタスクに関する情報のうち、少なくとも上記タスクの優先度情報を含む上記タスクのスケジューリングに関係する情報を保持するデータブロックであるアクティビティと上記タスクに関する情報のうち、上記アクティビティに記録されていない情報を保持するデータブロックであるコンテキストに分割して管理し、
上記アクティビティを実行可能なタスクの中から、もっとも優先度が高いものを選択するために設けられたディスパッチキューへの挿入または削除の対象としており、
あるタスクの優先度を他のタスクが継承する際には、上記ディスパッチキュー、タスクの相互排除の機構であるミューテックスの所有を待つタスクを記録するミューテックス待ちキュー、およびタスクが所有しているミューテックスを記録する所有オブジェクトキューを用いて、上記アクティビティと、上記コンテキストの対応関係だけを変化させて処理するようにしたことを特徴とするタスク管理方法。
【請求項４】
請求項３記載のタスク管理方法において、
上記優先度継承を行う条件変数によってタスクの実行を停止させる必要が生じても、上記ディスパッチキューに対して即座に操作を行うことなく、その他の条件変数によって、タスクの実行を停止させる必要が生じるまで、上記ディスパッチキューに対する操作を延期することを特徴とするタスク管理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば、オペレーティング・システム（ＯＳ）に適用して好適なタスク管理システムに関するものである。
【０００２】
【従来の技術】
従来から、タスクの応答時間の上限がデッドラインとなる規定値以下となることを保証しつつ、タスクの実行によって占有可能なプロセッサの時間の有効利用を高めることは、リアルタイムＯＳの重要な設定目標の一つであった。この設計目標を達成するために、以下のスケジューリング手法を採用することが考えられる。
【０００３】
まず、第１により優れたディスパッチポリシの採用が考えられる。
このようなディスパッチポリシの一つとして、ＥＤＦ（Ｅａｒｌｉｓｔ  Ｄｅａｄｌｉｎｅ  Ｆｉｒｓｔ）ポリシ（参照文献：Ｃ．Ｌ．Ｌｉｕ  ａｎｄ  Ｊ．Ｗ．Ｌａｙｌａｎｄ，“Ｓｃｈｅｄｕｌｉｎｇ  ａｌｏｇｏｒｉｔｈｍｓ  ｆｏｒ  ｍｕｌｔｉｐｒｏｇｒａｍｍｉｎｇ  ｉｎ  ａ  ｈａｒｄ  ｒｅａｌ  ｔｉｍｅ  ｅｎｖｉｒｏｎｍｅｎｔ，”Ｊｏｕｒｎａｌ  ｏｆ  ＡＣＭ，Ｖｏｌ．２０，Ｎｏ．１，ｐｐ．４６−６１，１９７３．）が知られている。ＥＤＦポリシは、デッドラインと周期が等しい周期タスクのスケジューリングを行う手法の中で、もっとも高いプロセッサ利用率を達成可能であることが知られている。ただし、タスク間の干渉がないことや、プロセッサ数が１であることなどの前提条件がある。
【０００４】
次に、第２に低優先度タスクによって高優先度タスクがブロックされる時間の最小化が考えられる。優先度継承プロトコル（参照文献：Ｌｕｉ  Ｓｈａ，Ｒａｇｕｎａｔｈａｎ  Ｒａｊｋｕｍａｒ，ａｎｄ  Ｊｏｈｎ  Ｐ．Ｌｅｈｏｃｚｋｙ，“Ｐｒｉｏｒｉｔｙ  ｉｎｈｅｒｉｔａｎｃｅ  Ｐｒｏｔｏｃｏｌｓ：ＡｎＡｐｐｒｏａｃｈ  ｔｏ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ，”ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，Ｖｏｌ．３９，Ｎｏ．９，ｐｐ．１１７５−１１８５，Ｓｅｐｔｅｍｂｅｒ  １９９０，）を採用することによって、低優先度タスクによって高優先度タスクがブロックされる時間を減少させることが可能である。なお、ここでは、基本優先度継承プロトコルや優先度シーリングプロトコルなどの総称として優先度継承プロトコルという用語を用いている。
【０００５】
【発明が解決しようとする課題】
しかし、上述した従来のスケジューリング手法では、以下に挙げるような不都合がある。
第１に、ＥＤＦポリシを採用したスケジューラは、従来のＯＳで広く使われている固定した優先度を用いる静的優先度スケジューラに比べ、オーバーヘッドが大きくなるという不都合があった。
【０００６】
第２に、優先度継承プロトコルを採用したスケジューラは、一般的なケースでの実行時間を示すオーバーヘッドが大きくなる。特に、上述したＥＤＦスケジューラと組み合わせた場合、静的優先度スケジューラを用いた場合に比べてオーバーヘッドが大きくなるという不都合があった。
【０００７】
これらの点について以下に、詳述する。
ＥＤＦスケジューラが静的優先度スケジューラと比べてオーバーヘッドが大きくなる原因の一つは、ＥＤＦスケジューラが扱う必要がある優先度の範囲が広いことである。この広さのために、ディスパッチキューを効率的に実現することが難しくなる。
【０００８】
一般的に、ディスパッチキューにタスクを追加する処理または除去する処理は、きわめて頻繁に実行されるため、可能な限り効率的に実現されることが望ましい。一方、ディスパッチキューの中からもっとも優先度が高いタスクを選択する処理は、追加の処理または除去の処理ほど頻繁に実行されないものの、その頻度は高いものとなる。
【０００９】
静的優先度スケジューリングを行うシステムでは、これらの二つの操作を効率的に実現するために、図９に示すデータ構造を用いてディスパッチキューを実現することが多い。この実現方法では、各優先度９１毎に配列の１〜ｎの一要素が割り当てられている。この要素は、同一優先度のタスクが接続された双方向リンクリストの起点となる。図９の左下部になるビット配列９２は、各双方向リンクリストにタスク９３〜９５または９６〜９７が接続されているか否かを示す値「１」を保持している。
【００１０】
このデータ構造では、タスクの追加または削除の処理は、ともに一定の、かつ、実用上十分短い時間で行える。また、もっとも優先度が高いタスクを選択する処理は、ビット配列９２の中でもっとも最初に「１」が現れる位置を計算することによって行える。これは、リストに接続されているタスクが存在するときに、ビット配列９２に「１」が格納される場合である。「０」が格納される場合は、最初に現れる「０」を検索する必要がある。静的優先度スケジューラを使用する場合、優先度がとりうる範囲として２５６前後が一般的である。そのため、この計算に要する時間は実用上問題とならない。さらに、リストの起点になる配列とビット配列の大きさも十分に小さい。
【００１１】
これとは、対照的に、ＥＤＦスケジューリングを使用する場合は、時刻がとりうる全範囲を優先度として使用する必要がある。ここで、時刻を、より範囲の小さい値に対応づける手法も提案されている。しかし、システム稼働中に多数のタスクの優先度を付け替える処理が発生する可能性があるという問題がある。そのため、より広い範囲の優先度に対して効率的な処理が行える手法が必要となる。
【００１２】
このような手法として、直線リスト、ヒープ、スプレー木、カレンダーキュー（参考文献：Ｒａｎｄｙ  Ｂｒｏｗｎ，“Ｃａｌｅｎｄａｒ  Ｑｕｅｕｅｓ：ＡＦａｓｔＯ（１）Ｐｒｉｏｒｉｔｙ  Ｑｕｅｕｅ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｆｏｒ  ｔｈｅ  Ｓｉｍｕｌａｔｉｏｎ  Ｅｖｅｎｔ  Ｓｅｔ  Ｐｒｏｂｌｅｍ，”Ｖｏｌｕｍｅ３１，Ｎｕｍｂｅｒ１０，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，Ｏｃｔｏｂｅｒ  １９８８．）などが知られている。
【００１３】
ところが、これらのデータ構造によって達成可能な性能は、図９に示したデータ構造によって達成可能な性能に比べて低い。そのため、ＥＤＦスケジューリングを採用したシステムにおいて、１回のディスパッチキュー操作に要するコストを下げることは難しい。
【００１４】
優先度継承プロトコルを採用した同時に二つのタスクの実行をできないようにするミューテックス（Ｍｕｔｅｘ：ＭｕｔｕａｌＥｘｃｌｕｓｉｏｎ（相互排除））が、通常のミューテックスに比べ、オーバーヘッドが大きくなる理由の一つとして、優先度継承による優先度の変化が挙げられる。一般的に、タスクの優先度が変化した際には、ディスパッチキューに対して何らかの操作を行う必要がある。これは、操作に要するコストが大きいＥＤＦスケジューラの場合に特に問題となる。
【００１５】
優先度継承プロトコルのオーバーヘッドには、上述の要素に加えて、ミューテックスを待つタスクを優先度順に列を作って待つキューイングをすることによって発生するものもある。さらに、現在どのミューテックスがロックしているか保持する優先度シーリングプロトコルを採用した場合には、ミューテックスのロック操作の度に、他のタスクによってロックされているミューテックスの中から最大のシーリング値が設定されているものを検索する必要がある。
【００１６】
ＥＤＦスケジューリングと優先度継承プロトコルは優れた特性を備えているものの、それらを採用しない場合に比べてオーバーヘッドが増大する傾向がある。
【００１７】
そこで、本発明は、かかる点に鑑みてなされたものであり、オーバーヘッドを減少させるために、ディスパッチキューを操作することなく、優先度を継承することができ、ミューテックス待ち状態への移行時または復帰時に必要だったキュー操作の回数を大幅に削減することができ、ミューテックス待ちキューを、優先度を考慮せずに操作できるタスク管理システムを提供することを課題とする。
【００１８】
【課題を解決するための手段】
本発明のタスク管理システムは、一つのプロセッサにより複数のタスクの管理を行うタスク管理システムにおいて、任意のタスクに関する情報のうち、少なくとも上記タスクの優先度情報を含む上記タスクのスケジューリングに関係する情報を保持するデータブロックであるアクティビティと、上記タスクに関する情報のうち、上記アクティビティに記録されていない情報を保持するデータブロックであるコンテキストと、実行可能なタスクの中から、もっとも優先度が高いものを選択するために設けられたディスパッチキューと、タスクの相互排除の機構であるミューテックスの所有を待つタスクを記録するミューテックス待ちキューと、タスクが所有しているミューテックスを記録する所有オブジェクトキューとを備え、一つのタスクに関する情報を、上記アクティビティと上記コンテキストに分割して管理し、上記アクティビティを上記ディスパッチキューへの挿入または削除の対象としており、あるタスクの優先度を他のタスクが継承する際には、上記ディスパッチキュー、上記ミューテックス待ちキュー、および上記所有オブジェクトキューを用いて、上記アクティビティと、上記コンテキストの対応関係だけを変化させて処理するようにしたものである。
【００１９】
また、本発明のタスク管理方法は、一つのプロセッサにより複数のタスクの管理を行うタスク管理方法において、一つのタスクに関する情報を、任意のタスクに関する情報のうち、少なくとも上記タスクの優先度情報を含む上記タスクのスケジューリングに関係する情報を保持するデータブロックであるアクティビティと上記タスクに関する情報のうち、上記アクティビティに記録されていない情報を保持するデータブロックであるコンテキストに分割して管理し、上記アクティビティを実行可能なタスクの中から、もっとも優先度が高いものを選択するために設けられたディスパッチキューへの挿入または削除の対象としており、あるタスクの優先度を他のタスクが継承する際には、上記ディスパッチキュー、タスクの相互排除の機構であるミューテックスの所有を待つタスクを記録するミューテックス待ちキュー、およびタスクが所有しているミューテックスを記録する所有オブジェクトキューを用いて、上記アクティビティと、上記コンテキストの対応関係だけを変化させて処理するようにしたものである。
【００２０】
従って本発明によれば、以下の作用をする。
継承する必要がある情報を他の情報から分離し、この情報を第３のデータブロックへの挿入または削除の対象とする。すなわち、優先度を保持する第１のデータブロックと、その他の情報を保持する第２のデータブロックによって一つのタスクを表現する。そして、第１のデータブロックを第３のデータブロックへの挿入または削除の対象とする。
【００２１】
この分割によって、両者の対応関係を変化させるだけで優先度を継承させることが可能となる。これにより、第１のデータブロックの第３のデータブロック内の位置関係は変化しておらず、第１のデータブロックの関係だけが変化する。
【００２２】
また、継承前における第１のデータブロックから第２のデータブロックに対して、一つのポインタを示す現在最も効果が現れている対応づけから、継承後における第１のデータブロックから第２のデータブロックに対して、一つのポインタを示す現在最も効果が現れている対応づけに更新する操作だけで、移動と同等の処理が行われる。
【００２３】
【発明の実施の形態】
本発明の実施の形態を以下に説明する。
本実施の形態のタスク管理システムは、優先度継承プロトコルを採用した排他制御機構を、従来の手法に比べて効率的に実現するものである。
【００２４】
図１は、本実施の形態に適用されるコンテキストとアクティビティを示す図である。
上述した従来の技術で示した手法で優先度継承を行う際には、以下の二つの処理が行われる。第１に、タスクの優先度を変化させる。第２に、タスクがディスパッチキューに接続されていた場合には、変化した優先度に従って適切な位置に移動させる処理を行う。
【００２５】
本実施の形態では、これらの処理を簡略化するために、継承する必要がある情報を他の情報から分離し、この情報をディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１への挿入または削除の対象とする。すなわち、図１に示すように、優先度（ｐｒｉｏｒｉｔｙ）３を保持するデータ構造であるアクティビティ（ａｃｔｉｖｉｔｙ）２と、その他の情報を保持するデータ構造であるコンテキスト（ｃｏｎｔｅｘｔ）４によって一つのタスクを表現する。そして、アクティビティ（ａｃｔｉｖｉｔｙ）２をディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１への挿入または削除の対象とする。
【００２６】
図１において、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１は、アクティビティ（ａｃｔｉｖｉｔｙ）２に対して、優先度に基づくもっとも緊急な対応づけ（ｔｈｅ＿ｍｏｓｔ＿ｕｒｇｅｎｔ＿ａｃｔｉｖｉｔｙ）Ｄ１を行っている。
【００２７】
アクティビティ（ａｃｔｉｖｉｔｙ）２は、自身に対して列の後者の対応づけ（ｓｕｃｃｅｓｓｏｒ）Ｄ２を行っている。優先度（ｐｒｉｏｒｉｔｙ）３はアクティビティ（ａｃｔｉｖｉｔｙ）２に対して、列の前者の対応づけ（ｐｒｅｄｅｃｅｓｓｏｒ）Ｄ３を行っている。
【００２８】
コンテキスト（ｃｏｎｔｅｘｔ）４はアクティビティ（ａｃｔｉｖｉｔｙ）２に対して、優先度（ｐｒｉｏｒｉｔｙ）３に関係しない本来の対応づけ（ｂａｓｅ＿ａｃｔｉｖｉｔｙ）Ｄ４を行っている。アクティビティ（ａｃｔｉｖｉｔｙ）２はコンテキスト（ｃｏｎｔｅｘｔ）４に対して、現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ５を行っている。
【００２９】
コンテキスト（ｃｏｎｔｅｘｔ）４はアクティビティ（ａｃｔｉｖｉｔｙ）２に対して、現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ６を行っている。
【００３０】
この分割によって、両者の対応関係を変化させるだけで優先度を継承させることが可能となる。
図２は、優先度継承によるコンテキストおよびアクティビティの関係の変化を示す図である。図２は、図２Ａに示す継承前から図２Ｂに示す継承後における優先度が継承される前後で、コンテキストおよびアクティビティの対応関係が変化する様子を表している。ここでは、キューイングの対象がアクティビティ（ａｃｔｉｖｉｔｙ）であることと、後述するように実行可能でないアクティビティ（ａｃｔｉｖｉｔｙ）もキューイングされることから、このデータ構造をディスパッチキュー（ｔｈｅ＿ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）と呼ぶ。
【００３１】
図２から分かるように、アクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３とアクティビティ（ａｃｔｉｖｉｔｙ）Ｂ１６のディスパッチキュー（ｔｈｅ  ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１内の位置関係は変化しておらず、アクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３とコンテキスト（ｃｏｎｔｅｘｔ）Ａ１２、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５の関係だけが変化している。
【００３２】
また、図２Ａに示す継承前におけるアクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３からコンテキスト（ｃｏｎｔｅｘｔ）Ａ１２に対して、一つのポインタを示す現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ１１から、図２Ｂに示す継承後におけるアクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３からコンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５に対して、現在有効な対応づけを示すポインタ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ１４に更新する操作だけで、移動と同等の処理が行われている。
【００３３】
さらに、従来の技術に示した手法では、アクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３がディスパッチキュー（ｔｈｅ＿ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１から除去されていたのに対して、本実施の形態による手法では、アクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３はそのままディスパッチキュー（ｔｈｅ＿ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１に残される。この処理は、後述する遅延デキューイングによって、この省略が可能となる。
【００３４】
ここで、両者の対応関係の変化の判断は、ミューテックス（ａ＿ｍｕｔｅｘ）１４の所有者であるコンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５が行い、この対応関係の変化を認識する。
【００３５】
図２Ａにおいて、アクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３はコンテキスト（ｃｏｎｔｅｘｔ）Ａ１２に対して、現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ１１を行っている。
【００３６】
アクティビティ（ａｃｔｉｖｉｔｙ）Ｂ１６はコンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５に対して、現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ１３を行っている。
【００３７】
ミューテックス（ａ ｍｕｔｅｘ）１４はコンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５に対して、所有の対応づけＤ１２を行っている。
【００３８】
図２Ｂにおいて、アクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３はコンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５に対して、現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ１４を行っている。
【００３９】
ミューテックス（ａ ｍｕｔｅｘ）１４はコンテキスト（ｃｏｎｔｅｘｔ）Ａ１２に対して、待ちの対応づけＤ１５を行っている。
【００４０】
アクティビティ（ａｃｔｉｖｉｔｙ）Ｂ１６はコンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５に対して、現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ１３を行っている。
【００４１】
ミューテックス（ａ ｍｕｔｅｘ）１４はコンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５に対して、所有の対応づけＤ１２を行っている。
【００４２】
上述したように、ミューテックス（ａ＿ｍｕｔｅｘ）１４のためにタスクが待ち状態へ遷移しても、アクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３のディスパッチキュー（ｔｈｅ＿ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１からの除去を即座に行う必要はない。
【００４３】
図２に示した状況では、アクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３をディスパッチキュー（ｔｈｅ＿ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１に留めておくとディスパッチ対象として選択される可能性が生じるときまで、ディスパッチキュー（ｔｈｅ＿ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１から除去する処理を延期することが可能である。
【００４４】
ここでは、このようにディスパッチキュー（ｔｈｅ＿ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１からアクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３を除去する処理を延期することを、遅延デキューイングと呼ぶ。また、ミューテックス（ａ＿ｍｕｔｅｘ）１４による待ち状態と、その他の要因による待ち状態を区別し、それぞれ、ミューテックス（ａ＿ｍｕｔｅｘ）１４による待ち状態をウエイティング（ｗａｉｔｉｎｇ）状態と呼び、その他の要因による待ち状態をスリーピング（ｓｌｅｅｐｉｎｇ）状態と呼ぶ。
【００４５】
遅延デキューイングとは、スリーピング（ｓｌｅｅｐｉｎｇ）状態に移行するときまで、ディスパッチキュー（ｔｈｅ  ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１からタスクを除去する処理を遅らせることをいう。ここでは、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５がスリーピング（ｓｌｅｅｐｉｎｇ）状態に移行するときまで、ディスパッチキュー（ｔｈｅ  ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１からアクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３およびアクティビティ（ａｃｔｉｖｉｔｙ）Ｂ１６を除去する処理を遅らせるようにする。
【００４６】
例えば、図２のコンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５がアクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３の継承後にスリーピング（ｓｌｅｅｐｉｎｇ）状態へ移行した場合は、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５が優先度に関係しない本来の対応づけを行っているアクティビティ（ａｃｔｉｖｉｔｙ）Ｂ１６と、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ１５によって直接または間接にブロックされている全コンテキスト（ｃｏｎｔｅｘｔ）が優先度に関係しない本来の対応づけを行っているアクティビティ（ａｃｔｉｖｉｔｙ）Ａ１３を、ディスパッチキュー（ｔｈｅ  ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）１１から除去する。
【００４７】
さらに、スリーピング（ｓｌｅｅｐｉｎｇ）状態にあるタスクが所有しているミューテックス（ａ ｍｕｔｅｘ）１４を他のタスクが獲得しようとしたときは、このタスクも遅延デキューイングの対象とする。
【００４８】
一般的に、ミューテックス（ａ ｍｕｔｅｘ）を所有したままタスクがミューテックス（ａ ｍｕｔｅｘ）以外の要因によって待ち状態へ遷移することはまれである。そのため、多くの場合に、結果として、優先度変更に伴うキュー操作が不要なだけでなく、ミューテックス（ａ ｍｕｔｅｘ）待ちに伴うキュー操作も多くの場合に不要となる。
【００４９】
上述したように、ミューテックス（ａ ｍｕｔｅｘ）待ちキューにタスクが優先度順に並ぶように操作することは、優先度継承プロトコルを採用したミューテックス（ａ ｍｕｔｅｘ）が、そうでないミューテックス（ａ ｍｕｔｅｘ）よりも非効率的となる原因の一つである。そこで、この実施の形態では、ＬＩＦＯ（Ｌａｓｔ  Ｉｎ  Ｆａｓｔ  Ｏｕｔ）順にキューを操作することによって、優先度キューイングと同等の効果を得られる手法を提案する。
【００５０】
ＬＩＦＯ順キュー操作で優先度順キュー操作と同じ結果を得るためには、以下の条件が満たされることを保証すればよい。第１に、優先度順は変わらない。第２に、プロセッサは一つである。
【００５１】
つまり、第１の条件は、順列を示すキューに接続されているタスクの優先度は、新たにキューに挿入されるタスクの優先度を超えないことを示す。
【００５２】
この条件が満たせなくなるのは、ミューテックス（ａ ｍｕｔｅｘ）獲得時にミューテックス（ａ ｍｕｔｅｘ）の所有者がウエイティング（ｗａｉｔｉｎｇ）状態にあった場合だけである。この場合は、所有者に対して優先度が継承されることによって、この所有者がミューテックス（ａ ｍｕｔｅｘ）待ちキューの中でしめる位置が不適切なものになる可能性がある。さらに、この所有者が待っているミューテックス（ａ ｍｕｔｅｘ）の所有者が、やはり、ウエイティング（ｗａｉｔｉｎｇ）状態にあった場合にも、同様の議論が成り立つ。
【００５３】
ところが、所有者が継承する優先度は、キューに接続されている他のタスクの優先度よりも高いことが明らかであるため、この所有者をミューテックス（ｍｕｔｅｘ）待ちキューの先頭に移動させる処理を行うことによって、この条件を満たすことが可能である。
【００５４】
図３は、優先度継承の際の待ちキュー内移動処理を示す図である。図３Ａは優先度継承前、図３Ｂは優先度継承後である。
図３Ａにおいて、ミューテックス（ｍｕｔｅｘ）Ｂ２２の待ちキューに、コンテキスト（ｃｏｎｔｅｘｔ）Ａ２３、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４、コンテキスト（ｃｏｎｔｅｘｔ）Ｃ２５が接続されている。
【００５５】
また、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４は、ミューテックス（ｍｕｔｅｘ）Ａ２１を所有している。
【００５６】
このとき、コンテキスト（ｃｏｎｔｅｘｔ）Ｄ２６が、ミューテックス（ｍｕｔｅｘ）Ａ２１を獲得しようとしたならば、図３Ｂに示すように、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４にコンテキスト（ｃｏｎｔｅｘｔ）Ｄ２６の優先度が継承される。この結果、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４が待ちキューの先頭に移動する。
【００５７】
図３Ａにおいて、ミューテックス（ｍｕｔｅｘ）Ａ２１は、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４に対して、所有の対応づけＤ２１を行っている。
ミューテックス（ｍｕｔｅｘ）Ｂ２２は、コンテキスト（ｃｏｎｔｅｘｔ）Ａ２３に対して、待ちキューの先頭の対応づけＤ２２を行っている。コンテキスト（ｃｏｎｔｅｘｔ）Ａ２３は、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４に対して、後続の対応づけＤ２３を行っている。コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４は、コンテキスト（ｃｏｎｔｅｘｔ）Ｃ２５に対して、後続の対応づけＤ２４を行っている。
【００５８】
コンテキスト（ｃｏｎｔｅｘｔ）Ｄ２６は、Ｄ２５に示すように、ミューテックス（ｍｕｔｅｘ）Ａ２１を所有しようとしている。
【００５９】
図３Ｂにおいて、ミューテックス（ｍｕｔｅｘ）Ｂ２２は、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４に対して、待ちキューの先頭の対応づけＤ２６を行っている。コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４は、コンテキスト（ｃｏｎｔｅｘｔ）Ａ２３に対して、後続の対応づけＤ２７を行っている。コンテキスト（ｃｏｎｔｅｘｔ）Ａ２３は、コンテキスト（ｃｏｎｔｅｘｔ）Ｃ２５に対して、後続の対応づけＤ２８を行っている。
【００６０】
コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４は、Ｄ２９に示すように、コンテキスト（ｃｏｎｔｅｘｔ）Ｄ２６の優先度を継承する。Ｄ３０に示すように、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４とコンテキスト（ｃｏｎｔｅｘｔ）Ａ２３の位置が逆転する。
【００６１】
ミューテックス（ｍｕｔｅｘ）Ａ２１は、コンテキスト（ｃｏｎｔｅｘｔ）Ｂ２４に対して、所有の対応づけＤ３１を行っている。
【００６２】
なお、図３Ａに示した所有Ｄ２１および図３Ｂに示した所有Ｄ３１の対応づけは、後述するオーナーシップ（ｏｗｎｅｒｓｈｉｐ）クラスをミューテックスのｔｈｅ ｏｗｎｅｒｓｈｉｐに設定することにより行う。
【００６３】
なお、図示はしないが、図３Ｂにおいて、ミューテックス（ｍｕｔｅｘ）Ｂ２２と並列するミューテックス（ｍｕｔｅｘ）Ｃに対しても、同様に、優先度継承の際の待ちキューの移動が行われる。
【００６４】
図４は、ミューテックス機構の実現に関連するクラスとそれらの間の関連を示す図である。
図中のディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１、アクティビティ（ａｃｔｉｖｉｔｙ）３２およびコンテキスト（ｃｏｎｔｅｘｔ）３４は上述した通りである。
【００６５】
ここでは、その他の三つのクラスについて説明する。この三つのクラスは、それぞれ、以下の機能を有している。
第１に、ミューテックス（ｍｕｔｅｘ）クラス３６について説明する。
ミューテックス（ｍｕｔｅｘ）クラス３６は、ミューテックス（ｍｕｔｅｘ）を表現するクラスである。オーナーイズスリーピング（ｏｗｎｅｒ＿ｉｓ＿ｓｌｅｅｐｉｎｇ）属性３７は、このミューテックス（ｍｕｔｅｘ）を所有しているタスクが、遅延デキューイングの対象となっているときツゥルー（ｔｒｕｅ）、それ以外の場合にはフォールス（ｆａｌｓｅ）となる。
【００６６】
第２に、アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）クラス３５について説明する。
あるタスクによるミューテックス（ｍｕｔｅｘ）獲得要求を表現するクラスである。ミューテックス（ｍｕｔｅｘ）を獲得しようとしたが、すでに他のタスクによって所有されていたとき、このオブジェクトが生成される。その後、獲得に成功したときにこのオブジェクトは破棄される。
【００６７】
第３に、オーナーシップ（ｏｗｎｅｒｓｈｉｐ）クラス３８について説明する。
ミューテックス（ｍｕｔｅｘ）の所有を表現するクラスである。あるタスクがミューテックス（ｍｕｔｅｘ）を所有しようとしてから解放するまでの間、存在し続ける。属性のインヘリテッド（ｉｎｈｅｒｉｔｅｄ）３９は、ミューテックス（ｍｕｔｅｘ）が所有されている間に、所有権を示すオーナーシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクトに対応するタスクが他のタスクの優先度を継承したときにツゥルー（ｔｒｕｅ）となる。優先度を継承していなかったときはフォールス（ｆａｌｓｅ）となる。
【００６８】
次に、オブジェクト間の関係を説明する。
これらのクラスは、それぞれ独立に動作するのではなく、図４に示されているように他のクラスのオブジェクトへの参照の対応づけとして、例えば、ｔｈｅ＿ｆｉｒｓｔ＿ｒｅｑｕｅｓｔを保持している。これらの参照は、以下に挙げるデータ構造を構成するために必要とされている。
【００６９】
第１に、ミューテックス（ｍｕｔｅｘ）待ちキューについて説明する。
あるミューテックス（ｍｕｔｅｘ）３６を所有しようとしたとき、すでに他のタスクによって所有されていた場合は、所有者がミューテックス（ｍｕｔｅｘ）３６を解放するまで待つことになる。ミューテックス（ｍｕｔｅｘ）待ちキューは、このようにして待つことになったタスクを記録するデータ構造である。ミューテックス（ｍｕｔｅｘ）待ちキューは、アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）オブジェクト３５を要素とする双方向リンクリストとして構成されている。
【００７０】
ミューテックス（ｍｕｔｅｘ）オブジェクト３６のファーストリクエストの対応づけ（ｔｈｅ＿ｆｉｒｓｔ＿ｒｅｑｕｅｓｔ）Ｄ３７が先頭の要素を指している。
【００７１】
アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）オブジェクト３５の列の後者の対応づけ（ｓｕｃｃｅｓｓｏｒ）Ｄ３９は後続する要素３５−１，３５−２・・・へのポインタであり、列の前者の対応づけ（ｐｒｅｄｅｃｅｓｓｏｒ）Ｄ４０は先行する要素３５−１，３５−２・・・へのポインタである。先頭の要素３５の（ｐｒｅｄｅｃｅｓｓｏｒ）Ｄ４０と末尾の要素３５−ｎの（ｓｕｃｃｅｓｓｏｒ）Ｄ３９は、それぞれ、どのオブジェクトも指さない特別なポインタ値を保持している。なお、Ｃ，Ｃ＋＋言語で実装する際にはヌル（ＮＵＬＬ）ポインタをこのために用いることが可能である。
【００７２】
第２に、所有オブジェクトキューについて説明する。
所有オブジェクトキューは、あるタスクが所有しているミューテックス（ｍｕｔｅｘ）３６を記録するために利用される。このキューの中には、タスクが保持している所有権であるオーナシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８，３８−１，３８−２・・・が新しいものから順に並べられている。もっとも新しいオーナシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８は、コンテキスト（ｃｏｎｔｅｘｔ）オブジェクト３４のニューエストオーナーシップ（ｔｈｅ＿ｎｅｗｓｔ＿ｏｗｎｅｒｓｈｉｐ）の対応づけＤ４４を参照することによって得られる。
【００７３】
後続のオーナシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８−１，３８−２・・・は、オーナシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８の列の後者の対応づけ（ｓｕｃｃｅｓｓｏｒ）Ｄ４５を参照することによって得られる。末尾のオーナシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８−ｎの列の後者の対応づけ（ｓｕｃｃｅｓｓｏｒ）Ｄ４５は、どのオブジェクトも指さない特別のポインタ値を保持している。
【００７４】
図４において、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１は、アクティビティ（ａｃｔｉｖｉｔｙ）３２に対して、優先度に基づくもっとも緊急な対応づけ（ｔｈｅ＿ｍｏｓｔ＿ｕｒｇｅｎｔ＿ａｃｔｉｖｉｔｙ）Ｄ３１を行っている。
【００７５】
アクティビティ（ａｃｔｉｖｉｔｙ）３２は、自身に対して列の後者の対応づけ（ｓｕｃｃｅｓｓｏｒ）Ｄ３２を行っている。優先度（ｐｒｉｏｒｉｔｙ）３３はアクティビティ（ａｃｔｉｖｉｔｙ）３２に対して、列の前者の対応づけ（ｐｒｅｄｅｃｅｓｓｏｒ）Ｄ３３を行っている。
【００７６】
コンテキスト（ｃｏｎｔｅｘｔ）３４はアクティビティ（ａｃｔｉｖｉｔｙ）３２に対して、優先度（ｐｒｉｏｒｉｔｙ）３３に関係しない本来の対応づけ（ｂａｓｅ＿ａｃｔｉｖｉｔｙ）Ｄ３５を行っている。アクティビティ（ａｃｔｉｖｉｔｙ）３２はコンテキスト（ｃｏｎｔｅｘｔ）３４に対して、現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ３６を行っている。
【００７７】
コンテキスト（ｃｏｎｔｅｘｔ）３４はアクティビティ（ａｃｔｉｖｉｔｙ）３２に対して、現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４を行っている。
【００７８】
ミューテックス（ｍｕｔｅｘ）クラス３６は、アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）クラス３５に対して、ファーストリクエストの対応づけ（ｔｈｅ＿ｆｉｒｓｔ＿ｒｅｑｕｅｓｔ）Ｄ３７を行っている。
【００７９】
アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）クラス３５は、ミューテックス（ｍｕｔｅｘ）クラス３６に対して、ウエイティングフォーの対応づけ（ｗａｉｔｉｎｇ＿ｆｏｒ）Ｄ３８を行っている。
【００８０】
アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）クラス３５は、３５−１，３５−２・・・に対して、列の後者の対応づけ（ｓｕｃｃｅｓｓｏｒ）Ｄ３９を行っている。アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）クラス３５は、３５−１，３５−２・・・に対して、列の前者の対応づけ（ｐｒｅｄｅｃｅｓｓｏｒ）Ｄ４０を行っている。
【００８１】
アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）クラス３５は、オーナーシップ（ｏｗｎｅｒｓｈｉｐ）クラス３８に対して、オーナーシップ（ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）の対応づけＤ４１を行っている。
【００８２】
ミューテックス（ｍｕｔｅｘ）クラス３６は、オーナーシップ（ｏｗｎｅｒｓｈｉｐ）クラス３８に対して、ミューテックスオーナーシップ（ｔｈｅ＿ｍｕｔｅｘ＿ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）の対応づけＤ４２を行っている。
【００８３】
オーナーシップ（ｏｗｎｅｒｓｈｉｐ）クラス３８は、コンテキスト（ｃｏｎｔｅｘｔ）３４に対して、オーナー（ｔｈｅ＿ｏｗｎｅｒ）の対応づけＤ４３を行っている。コンテキスト（ｃｏｎｔｅｘｔ）３４は、オーナーシップ（ｏｗｎｅｒｓｈｉｐ）クラス３８に対して、ニューエストオーナーシップ（ｔｈｅ＿ｎｅｗｓｔ＿ｏｗｎｅｒｓｈｉｐ）の対応づけＤ４４を行っている。
【００８４】
オーナーシップ（ｏｗｎｅｒｓｈｉｐ）クラス３８は、３８−１，３８−２・・・に対して、列の後者の対応づけ（ｓｕｃｃｅｓｓｏｒ）Ｄ４５を行っている。
【００８５】
次に、ミューテックス（ｍｕｔｅｘ）の所有を示すロック操作、ミューテックス（ｍｕｔｅｘ）の解放を示すアンロック操作、上述した遅延デキューイング操作および遅延デキューイングからの復帰操作の手順を以下に説明する。
【００８６】
図５は、ロック手順の動作を示すフローチャートである。図５に示すロック手順は、ミューテックス（ｍｕｔｅｘ）の動作を示すものである。
図５において、ステップＳ１で、所有されているか否かを判断する。ステップＳ１で所有されていないときはステップＳ２へ進み、ステップＳ２で、所有オブジェクトキューの先頭にオーナーシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクトを挿入してロック操作を成功する。
【００８７】
ステップＳ１で所有されているときはステップＳ３へ進み、ステップＳ３で、オーナーがスリーピング状態（ｏｗｎｅｒ＿ｉｓ＿ｓｌｅｅｐｉｎｇ）であるか否かを判断する。
【００８８】
ステップＳ３でオーナーがスリーピング状態（ｏｗｎｅｒ＿ｉｓ＿ｓｌｅｅｐｉｎｇ）であるときは、ステップＳ４へ進み、ステップＳ４で、現行コンテキスト（ｃｏｎｔｅｘｔ）を遅延デキューイングする。
【００８９】
ステップＳ５で、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１の優先度に基づくもっとも緊急なアクティビティ（ｔｈｅ＿ｍｏｓｔ＿ｕｒｇｅｎｔ＿ａｃｔｉｖｉｔｙ）Ｄ３１、コンテキスト（ｃｏｎｔｅｘｔ）３４への現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ｃｏｎｔｅｘｔ）Ｄ３６をディスパッチして、ステップＳ１へ戻る。
【００９０】
具体的には、ステップＳ３〜ステップＳ５の判断および処理は、図４の説明に対応し、現行コンテキスト（ｃｏｎｔｅｘｔ）の状態を保持した後に、優先度の高いアクティビティ（ａｃｔｉｖｉｔｙ）により現行コンテキスト（ｃｏｎｔｅｘｔ）の切り替えを行って、コンテキスト（ｃｏｎｔｅｘｔ）をプロセッサに取り込んでディスパッチ（ｄｉｓｐａｔｃｈ）を実行する。そして、この状態を現行コンテキスト（ｃｏｎｔｅｘｔ）に保存する。
【００９１】
ステップＳ３でオーナーがスリーピング状態（ｏｗｎｅｒ＿ｉｓ＿ｓｌｅｅｐｉｎｇ）でないときは、ステップＳ６へ進み、ステップＳ６で、ｍにロック対象ミューテックス（ｍｕｔｅｘ）を代入する。ステップＳ７で、ｏにｍを所有しているコンテキスト（ｃｏｎｔｅｘｔ）を代入する。
【００９２】
ステップＳ８で、ｏはウエイティング（ｗａｉｔｉｎｇ）状態であるか否かを判断する。ステップＳ８でｏはウエイティング（ｗａｉｔｉｎｇ）状態であるときは、ステップＳ９へ進み、ステップＳ９で、ｍに対応するオーナーシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８のインヘリテッド（ｉｎｈｅｒｉｔｅｄ）属性３９にツゥルー（ｔｒｕｅ）を代入する。
【００９３】
ステップＳ１０で、ｏに対応するアクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）オブジェクト３５をｍの待ちキューの先頭に移動する。ステップＳ１１で、ｍにｏが待っているミューテックス（ｍｕｔｅｘ）を代入して、ステップＳ７へ戻る。ステップＳ８〜ステップＳ１１の判断および処理は、上述した図３の説明に対応する。
【００９４】
ステップＳ８でｏはウエイティング（ｗａｉｔｉｎｇ）状態でないときは、ステップＳ１２へ進み、ステップＳ１２で、アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）オブジェクト３５を生成する。
【００９５】
ステップＳ１３で、生成したアクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）オブジェクト３５をロック対象ミューテックス（ｍｕｔｅｘ）の待ちキューの先頭に挿入する。ステップＳ１４で、現行アクティビティ（ａｃｔｉｖｉｔｙ）にｏを対応づける。ステップＳ１５で、ｏをディスパッチする。
【００９６】
具体的には、現行コンテキスト（ｃｏｎｔｅｘｔ）の実行を停止し、これ以後、ｏが現行コンテキスト（ｃｏｎｔｅｘｔ）となる。
【００９７】
ステップＳ１６で、アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）オブジェクト３５を破棄する。ステップＳ１７で、所有オブジェクトキューの先頭にオーナーシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクトを挿入してロック操作が成功する。
【００９８】
図６は、アンロック手順の動作を示すフローチャートである。
図６において、ステップＳ２１で、オーナーシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクトを所有オブジェクトキューから除去する。
【００９９】
ステップＳ２２で、ミューテックス待ちキューは空か否かを判断する。ステップＳ２２でミューテックス待ちキューが空であるときは、ステップＳ２３へ進み、ステップＳ２３で、ミューテックス（ｍｕｔｅｘ）のオーナーシップ（ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）にＮＵＬＬを代入してアンロック操作を成功する。
【０１００】
ステップＳ２２でミューテックス待ちキューが空でないときは、ステップＳ２４へ進み、ステップＳ２４で、ｒにミューテックス待ちキューの先頭要素を代入する。ステップＳ２５で、ミューテックス待ちキューの先頭要素を除去する。
【０１０１】
ステップＳ２６で、オーナーシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８のインヘリテッド（ｉｎｈｅｒｉｔｅｄ）属性３９がツゥルー（ｔｒｕｅ）であるか否かを判断する。ステップＳ２６でオーナーシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８のインヘリテッド（ｉｎｈｅｒｉｔｅｄ）属性３９がツゥルー（ｔｒｕｅ）であるときは、直ちに成功となる。
【０１０２】
ステップＳ２６でオーナーシップ（ｏｗｎｅｒｓｈｉｐ）オブジェクト３８のインヘリテッド（ｉｎｈｅｒｉｔｅｄ）属性３９がツゥルー（ｔｒｕｅ）でないは、ステップＳ２７へ進み、ステップＳ２７で、現行アクティビティ（ａｃｔｉｖｉｔｙ）にｒのオーナーシップ（ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）のオーナー（ｔｈｅ＿ｏｗｎｅｒ）を対応づける。
【０１０３】
具体的には、アクティビティ（ａｃｔｉｖｉｔｙ）はそのままで、先頭から待っていたコンテキスト（ｃｏｎｔｅｘｔ）に対応させる。
【０１０４】
ステップＳ２８で、ｒのオーナーシップ（ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）のオーナー（ｔｈｅ＿ｏｗｎｅｒ）をディスパッチ（ｄｉｓｐａｔｃｈ）する。
【０１０５】
ステップＳ２９で、ミューテックス（ｍｕｔｅｘ）のオーナーシップ（ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）にｒ＝オーナーシップ（ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）を代入してアンロック操作を成功する。
【０１０６】
図７は、遅延デキューイング手順の動作を示すフローチャートである。図７は、ミューテックス（ｍｕｔｅｘ）の動作を示すものである。なお、パラメータとしてコンテキスト（ｃｏｎｔｅｘｔ）オブジェクトが与えられている。図７の動作は、例えば、スリープ（ｓｌｅｅｐ）プリミティブから読み出される。
【０１０７】
図７において、ステップＳ３１で、与えられたコンテキスト（ｃｏｎｔｅｘｔ）３４の現在有効なアクティビティ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４は、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１に接続されているか否かを判断する。
【０１０８】
ステップＳ３１で与えられたコンテキスト（ｃｏｎｔｅｘｔ）３４の現在有効なアクティビティ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４は、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１に接続されているときは、ステップＳ３２へ進み、ステップＳ３２で、現在有効なアクティビティ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４を、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１から削除する。
【０１０９】
ステップＳ３３で、ｐに与えられたコンテキスト（ｃｏｎｔｅｘｔ）３４の所有オブジェクトキューの先頭要素を代入する。ステップＳ３１で与えられたコンテキスト（ｃｏｎｔｅｘｔ）３４の現在有効な対応づけ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４は、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１に接続されていないときは、直ちにステップＳ３３へ進む。
【０１１０】
ステップＳ３４で、ｐ＝ＮＵＬＬであるか否かを判断する。ステップＳ３４でｐ＝ＮＵＬＬであるときは、直ちに成功する。ステップＳ３４でｐ＝ＮＵＬＬでないときは、ステップＳ３５へ進み、ステップＳ３５で、ｍをｐのミューテックス（ｍｕｔｅｘ）とする。ステップＳ３６で、ｍのオーナーイズスリーピング（ｏｗｎｅｒ＿ｉｓ＿ｓｌｅｅｐｉｎｇ）をツゥルー（ｔｒｕｅ）とする。ステップＳ３７で、ｂをｍのファーストリクエストの対応づけ（ｔｈｅ＿ｆｉｒｓｔ＿ｒｅｑｕｅｓｔ）Ｄ３７とする。
【０１１１】
ステップＳ３８で、ｂ＝ＮＵＬＬであるか否かを判断する。ステップＳ３８でｂ＝ＮＵＬＬであるときは、ステップＳ４１へ進み、ステップＳ４１で、ｐにｐの後続（ｓｕｃｃｅｓｓｏｒ）を代入して、ステップＳ３４へ戻る。
【０１１２】
ステップＳ３８でｂ＝ＮＵＬＬでないときは、ステップＳ３９へ進み、ステップＳ３９で、ｂのオーナーシップ（ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）のオーナー（ｔｈｅ＿ｏｗｎｅｒ）を遅延デキューイングする。ステップＳ４０で、ｂにｂの後続（ｓｕｃｃｅｓｓｏｒ）を代入して、ステップＳ３８へ戻る。
【０１１３】
図８は、遅延デキューイングからの復帰手順の動作を示すフローチャートである。なお、パラメータとしてコンテキスト（ｃｏｎｔｅｘｔ）オブジェクトが与えられている。
【０１１４】
図８において、ステップＳ５１で、与えられたコンテキスト（ｃｏｎｔｅｘｔ）３４の現在有効なアクティビティ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４は、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１に接続されているか否かを判断する。
【０１１５】
ステップＳ５１で与えられたコンテキスト（ｃｏｎｔｅｘｔ）３４の現在有効なアクティビティ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４が、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１に接続されていないときは、ステップＳ５２へ進み、ステップＳ５２で、現在有効なアクティビティ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４を、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１に挿入する。
【０１１６】
ステップＳ５３で、ｐに与えられたコンテキスト（ｃｏｎｔｅｘｔ）３４の所有オブジェクトキューの先頭要素を代入する。ステップＳ５１で与えられたコンテキスト（ｃｏｎｔｅｘｔ）３４の現在有効なアクティビティ（ｅｆｆｅｃｔｉｖｅ＿ａｃｔｉｖｉｔｙ）Ｄ３４が、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）３１に接続されているときは、直ちにステップＳ５３へ進む。
【０１１７】
ステップＳ５４で、ｐ＝ＮＵＬＬであるか否かを判断する。ステップＳ５４でｐ＝ＮＵＬＬであるときは、直ちに成功する。ステップＳ５４でｐ＝ＮＵＬＬでないときは、ステップＳ５５へ進み、ステップＳ５５で、ｍをｐのミューテックス（ｍｕｔｅｘ）とする。ステップＳ５６で、ｍのオーナーイズスリーピング（ｏｗｎｅｒ＿ｉｓ＿ｓｌｅｅｐｉｎｇ）をフォールス（ｆａｌｓｅ）とする。ステップＳ５７で、ｂをｍのファーストリクエストの対応づけ（ｔｈｅ＿ｆｉｒｓｔ＿ｒｅｑｕｅｓｔ）Ｄ３７とする。
【０１１８】
ステップＳ５８で、ｂ＝ＮＵＬＬであるか否かを判断する。ステップＳ５８でｂ＝ＮＵＬＬであるときは、ステップＳ６１へ進み、ステップＳ６１で、ｐにｐの後続（ｓｕｃｃｅｓｓｏｒ）を代入して、ステップＳ５４へ戻る。
【０１１９】
ステップＳ５８でｂ＝ＮＵＬＬでないときは、ステップＳ５９へ進み、ステップＳ５９で、ｂのオーナーシップ（ｔｈｅ＿ｏｗｎｅｒｓｈｉｐ）のオーナー（ｔｈｅ＿ｏｗｎｅｒ）に対して遅延デキューイングからの復帰処理を行う。ステップＳ６０で、ｂにｂの後続（ｓｕｃｃｅｓｓｏｒ）を代入して、ステップＳ５８へ戻る。
【０１２０】
上述したように、達成可能なプロセッサ利用率を高めるためには、第１にＥＤＦスケジューリングの採用、第２に優先度継承プロトコルの採用の二つの手法が有効であるが、ともにオーバーヘッドが増加するという問題があった。
【０１２１】
そこで、本実施の形態で提案した手法によれば、以下の最適化を可能とすることによって、この問題を解決することができる効果がある。
第１に、ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）を表現するデータ構造を操作することなく、優先度を継承する。これによって、ＥＦＤスケジューリングがもつディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）の操作による高いオーバーヘッドという問題を回避することができる。同時に、優先度継承プロトコルのオーバーヘッドを削減することもできる。
【０１２２】
第２に、ミューテックス（ｍｕｔｅｘ）待ち状態への移行または復帰時に必要だったキュー操作の回数を削減することができる。これによって、ＥＦＤスケジューリングがもつディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）の操作による高いオーバーヘッドという問題を緩和することができる。
【０１２３】
第３に、ミューテックス（ｍｕｔｅｘ）待ちキューの操作を、優先度を考慮せずに行う。これによって、優先度継承プロトコルのオーバーヘッド発生要因の一つを除去することができる。
【０１２４】
この結果、ＥＤＦスケジューリングと優先度継承プロトコルの採用に伴うオーバーヘッドの増加を抑えつつ、より高いプロセッサ利用効率を達成することが可能となる。また、この手法を省電力リアルタイムスケジューリング手法と組み合わせることによって、より高い消費電力削減効果を得ることができる。
【０１２５】
【発明の効果】
この発明のタスク管理システムは、単一のプロセッサによりタスクの管理を行うタスク管理システムにおいて、任意のタスクに関する情報のうち、タスクのスケジューリングに関係する情報を保持する第１のデータブロックと、第１のデータブロックに記録されていない情報を保持する第２のデータブロックと、実行可能なタスクの中から、もっとも優先度が高いものを選択するために設けられた第３のデータブロックとを備え、一つのタスクに関する情報を、第１のデータブロックと第２のデータブロックに分割して管理し、第１のデータブロックを第３のデータブロックへの挿入または削除の対象としており、あるタスクの優先度を他のタスクが継承する際には、第１のデータブロックと第２のデータブロックの対応関係だけを変化させるようにしたので、第１に、第３のデータブロックを操作することなく、優先度を継承することによって、ＥＦＤスケジューリングがもつ第３のデータブロックの操作による高いオーバーヘッドという問題を回避することができ、同時に、優先度継承プロトコルのオーバーヘッドを削減することもできる。
【０１２６】
第２に、相互排除待ち状態への移行または復帰時に必要だったキュー操作の回数を削減することによって、ＥＦＤスケジューリングがもつ第３のデータブロックの操作による高いオーバーヘッドという問題を緩和することができる。
【０１２７】
第３に、相互排除待ちキューの操作を、優先度を考慮せずに行うことによって、優先度継承プロトコルのオーバーヘッド発生要因の一つを除去することができる。
【０１２８】
この結果、ＥＤＦスケジューリングと優先度継承プロトコルの採用に伴うオーバーヘッドの増加を抑えつつ、より高いプロセッサ利用効率を達成することができるという効果を奏する。
【０１２９】
また、この発明のタスク管理システムは、上述において、優先度継承を行う条件変数によってタスクの実行を停止させる必要が生じても、第３のデータブロックに対して即座に操作を行うことなく、その他の条件変数によって、タスクの実行を停止させる必要が生じるまで、第３のデータブロックに対する操作を延期するので、相互排除を所有したままタスクが相互排除以外の要因によって待ち状態へ遷移することはまれであるため、結果として、優先度変更に伴うキュー操作が不要なだけでなく、相互排除待ちに伴うキュー操作も多くの場合に不要とすることができるという効果を奏する。
【図面の簡単な説明】
【図１】本実施の形態に適用されるコンテキストとアクティビティを示す図である。
【図２】優先度継承によるコンテキストとアクティビティの関係の変化を示す図であり、図２Ａは継承前、図２Ｂは継承後である。
【図３】優先度継承の際の待ちキュー内移動処理を示す図であり、図３Ａは継承前、図３Ｂは継承後である。
【図４】ミューテックス機構の実現に関連するクラスとそれらの間の関連を示す図である。
【図５】ロック手順の動作を示すフローチャートである。
【図６】アンロック手順の動作を示すフローチャートである。
【図７】遅延デキューイング手順の動作を示すフローチャートである。
【図８】遅延デキューイングからの復帰手順の動作を示すフローチャートである。
【図９】静的優先度スケジューリングにおけるディスパッチキューの表現を示す図である。
【符号の説明】
１……ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）、２……アクティビティ（ａｃｔｉｖｉｔｙ）、３……コンテキスト（ｃｏｎｔｅｘｔ）、１１……ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）、１２……コンテキスト（ｃｏｎｔｅｘｔ）Ａ、１３……アクティビティ（ａｃｔｉｖｉｔｙ）Ａ、１４……ミューテックス（ｍｕｔｅｘ）、１５……コンテキスト（ｃｏｎｔｅｘｔ）Ｂ、１６……アクティビティ（ａｃｔｉｖｉｔｙ）Ｂ、２１……ミューテックス（ｍｕｔｅｘ）Ａ、２２……ミューテックス（ｍｕｔｅｘ）Ｂ、２３……コンテキスト（ｃｏｎｔｅｘｔ）Ａ、２４……コンテキスト（ｃｏｎｔｅｘｔ）Ｂ、２５……コンテキスト（ｃｏｎｔｅｘｔ）Ｃ、２６……コンテキスト（ｃｏｎｔｅｘｔ）Ｄ、３１……ディスパッチキュー（ｄｉｓｐａｔｃｈ＿ｑｕｅｕｅ）、３２……アクティビティ（ａｃｔｉｖｉｔｙ）、３３……優先度（ｐｒｉｏｒｉｔｙ）、３４……コンテキスト（ｃｏｎｔｅｘｔ）、３５……アクワイヤーメントリクエスト（ａｃｑｕｉｒｅｍｅｎｔ＿ｒｅｑｕｅｓｔ）クラス、３６……ミューテックス（ｍｕｔｅｘ）クラス、３７……オーナースリーピング属性（ｏｗｎｅｒ＿ｉｓ＿ｓｌｅｅｐｉｎｇ）、３８……オーナーシップ（ｏｗｎｅｒｓｈｉｐ）クラス、３９……インヘリテッド（ｉｎｈｅｒｉｔｅｄ）属性
【図１】
0003870729.tif 000002
【図２】
0003870729.tif 000003
【図３】
0003870729.tif 000004
【図４】
0003870729.tif 000005
【図５】
0003870729.tif 000006
【図６】
0003870729.tif 000007
【図７】
0003870729.tif 000008
【図８】
0003870729.tif 000009
【図９】
0003870729.tif 000010