JP4170227B2 - 多重処理環境における処理の実行 - Google Patents

Description

本発明は、コンピュータ装置により起動されるオペレーティングシステムにおいて異なる優先度で処理を実行する方法と、それに対応するシステムに関するものである。特に、マルチプロセッサを備えるオペレーティングシステム又は多重処理環境で共有リソースを使用して異なる優先度で処理を実行する方法と、それに対応するシステムに関するものである。

強力又は重要なリアルタイムシステムのソフトウェアは、時間重視の動作又は処理を実行することを担う高優先度のスレッドや、処理や、タスクや、ジョブ等を有する（これらの用語が本文を通じて交換可能に使用される）。一般的に、そのようなシステムはまた、バックグラウンド動作又は処理を実行することを担う低優先度のスレッドを有する。

低優先度のスレッドの処理は、高優先度のスレッド、及び高優先度のスレッドと低優先度のスレッドの間に優先度がある他のスレッド（以下において中間優先度のスレッドと称する）によって先取される。

スレッド、タスク、処理又はジョブは、他の部分と関係なく実行できるプログラムの一部である。マルチスレッドに対応するオペレーティングシステムは、スレッド部分が同時に実行できるプログラムをプログラマが設計することを可能にする。

異なる又は同じ優先度を備えたスレッドは、メモリ又はファイルや、メモリ又はファイルの一部等のような共有リソースを通じて通信し、又はそれを使用することがある。共有リソースへのアクセスは、１つのみのスレッドが所定のリソースへのアクセスを許可されることを確保するプログラムオブジェクトにより、一般的に保護又は処理される。例えば、それにより他のスレッドがデータの書き込みを終了する前に（又はその間に）、１つのスレッドがメモリから読み取ることを試みず、その逆も同様である。そのようなプログラムオブジェクトは一般的に相互排除と呼ばれ、それは‘相互排除オブジェクト’の略である。相互排除は、複数のプログラムスレッドがファイル及びメモリアクセスのような同じリソースを共有することを可能にするが、同時ではないプログラムオブジェクトである。プログラムが開始されると、相互排除は共有リソース毎に複数のスレッドで使用される固有の名前や識別子等を備えて作られる。この段階の後、リソースを必要とする如何なるスレッドは、リソースを使用する間に、他のスレッドから相互排除を‘ロック’しなければならない。データやリソース等がもはや必要なくなると、又はルーチンが終了すると、相互排除がロック解除又は解放される。相互排除はセマフォ（semaphore）又はバイナリ・セマフォ（binary semaphore）で実装されることがあり、そのセマフォ（semaphore）又はバイナリ・セマフォ（binary semaphore）は一般的にハードウェア又はソフトウェアのフラグである。マルチタスクのシステムにおいて、セマフォ（semaphore）は一般的に共通リソースの状態を‘ロック’し、又は示す値を備えた変数である。それは使用されるリソースの情報を取得するために使用される。リソースを必要とする処理はセマフォ（semaphore）を確認し、リソースの状態を判断し、例えば適切な相互排除を取得又はロックして、処理方法を決定する。

高優先度のスレッドが共有リソースに非常に長くアクセスすることを回避し、それによって以下に説明される通り高優先度のスレッドが時間重視のタスクを実行することを回避する共有リソースを通じて、高優先度と低優先度のスレッドが通信し、又はそれを使用する場合に、問題が生じることがある。低優先度のスレッドが所定の時間に共有リソースへのアクセスを‘所有’し、高優先度のスレッドが共有リソースへのアクセスを必要とし、それにより低優先度のスレッドが終了するまで待たなければならないことを仮定する。この状況において、中間優先度のスレッド（特定の共有リソースを使用する必要がない）は、低優先度のスレッドを先取することにより、高優先度のスレッドのアクセスを遅延させることがあり、それによって中間優先度のスレッドが使用する時間に等しい時間だけ高優先度（及び低優先度）のスレッドが待たなければならない時間を延ばす。そのことは、高優先度のタスクが期限までにその動作を実行できないことを引き起こすことがある。

この問題は、一般的に文字通り‘優先度の反転’と称され、図１ａと関連して詳細に説明される。

この特定の問題に対する１つの以前の解決策は、場合によっては‘優先度の進展’機構と称される‘優先度の承継’を実装することであり、所有しているスレッド（例えば低優先度のスレッド）が一時的に最高の優先度の待ち処理／スレッドに等しい優先度を獲得する。このようにして、中間優先度の処理は低優先度のスレッドを先取して、高優先度のスレッドのための待ち時間を更に遅延させることができない。優先度の承継の機構は、例えばN.J.Keelingの“Missed It!-How Priority Inversion messes up real-time performance and how the Priority Ceiling Protocol puts it right”（Real-Time Magazine 99-4,1994）に開示された２つの問題を有する。高優先度のスレッドが他のスレッドと複数のリソースを共有するときに１つの問題が生じ、それは優先度の承継に非常に長時間かかることを引き起こす。複数のスレッドが相互に複数のリソースを共有する場合にもう１つの問題が生じ、それによってスレッドが誤った順序でリソースを割り当てると優先度の承継がデッドロックを回避しなくなる。前記２つの問題に対して、‘優先度シーリング（priority ceiling）’と呼ばれる解決策がKeelingで提案され、所有しているスレッドが、一時的に共有リソースの相互排除を待つために割り当てられた全てのスレッドのうちの最高の優先度に等しい優先度を獲得する。

しかし、優先度の承継と優先度シーリング（priority ceiling）の機構は、高優先度のスレッドと低優先度のスレッドとの間の共有リソースを介した通信に必ずしも常に使用できるわけではなく、それによって中間優先度のスレッド（高優先度と低優先度のスレッドの間の優先度を有する）は、高優先度のスレッドが時間通りにその動作を実行することを回避することがあり、それによって、場合によってはリアルタイムアプリケーションを無用なもの、誤ったもの等にする。更に、優先度の承継又は優先度シーリング（priority ceiling）の機構の選択肢は、例えばスレッドを実行するオペレーティングシステムに課された制限により、必ずしも利用可能であり、又は対応されているとは限らない。一例として、例えば２つの異なるオペレーティングシステムが所定の時間に単一のプロセッサで実行しており、１つのオペレーティングシステムが高優先度のスレッドを実行するリアルタイム・オペレーティングシステムであり、他方のオペレーティングシステムが低優先度のスレッドを実行する非リアルタイム・オペレーティングシステムである場合、低優先度のスレッドの優先度は、高優先度のスレッドの優先度に達するほど高く上げられることはできない。

多重処理環境で異なる優先度を備えた処理を実行する方法とシステムを提供することが本発明の目的であり、前記方法とシステムは、先行技術の問題を解決する。

このことは、低優先度の処理と高優先度の処理の実行を有する多重処理環境で、異なる優先度を備えた処理を実行する方法によって達成され、前記高優先度の処理と前記低優先度の処理が所定のリソースを共有し、前記低優先度の処理が前記共有リソースを使用する予定のときに、前記低優先度の処理の有効な優先度を上げるステップを有し、前記有効な優先度が、前記多重環境における他の処理の優先度より高く上げられることを特徴とする。

このようにして、高優先度の処理は他の処理によってできるだけ短い時間だけ遅延し、それによりそれが期限にそのタスクを実行することが可能となり、‘有効な’優先度が上げられたため、高優先度以外の他の処理が所定のリソースへの低優先度のアクセスを引き延ばすことがある。

有効な優先度は、高優先度のスレッドが他のタスクを終了するまで上げられることがある。

基本的な同期及び通信手段、並びに厳密な優先度の機構以外に、オペレーティングシステム又はオペレーティングシステム群からの対応は必要なく、スレッドは、同じ又は低い優先度を備えたスレッドにより、先取されることはできない。

好ましい実施例が請求項２に記載される。いくつかの更なる実施例において、例えば相互排除、Boolean又はセマフォ（semaphore）を使用して、追加処理が高優先度の処理と同期されることがある。

このように、低優先度の処理の‘有効な’優先度を上げることが、低優先度（同じ低優先度にとどまる）の代わりに所定のリソースにアクセスする追加スレッドを使用し、高優先度の処理と通信することにより、達成され、前記追加処理は、高優先度の処理以外のその他の処理によって引き伸ばされ、先取される等することはない。

他の好ましい実施例が請求項６に記載される。その他に、有効な優先度が高優先度の処理の優先度と同じに又はそれより大きく上げられる。

好ましくは、オペレーティングシステムはプリエンプティブ（pre-emptive）環境である。

１つの実施例において、マルチプロセッサ環境は、少なくとも所定の時間に単一のプロセッサで実行するリアルタイム・オペレーティングシステムと非リアルタイム・オペレーティングシステムとを有し、前記リアルタイム・オペレーティングシステムは、前記高優先度のスレッドと前記追加処理とを有し、前記非リアルタイム・オペレーティングシステムは前記低優先度のスレッドを有する。

このように、多重処理システムは、２つのセットのスレッド又は処理を有する。全てのスレッドは同じCPUで時間を競う。第１のセットのスレッドは厳密な優先度でスケジュールされ、同様にCPU時間を必要とするより高い優先度を備えたスレッドが存在する場合に、スレッドはCPU時間を獲得しない。第２のセットのスレッドは、第１のセットのスレッドの全てがCPU時間を必要としない場合にのみ、CPU時間を獲得する。事実上、第１のセットの全てのスレッドは、第２のグループのスレッドより高い優先度を有する。スレッドはセットの間で移動できない。全てのスレッドはメモリを共有し、相互にセマフォ（semaphore）と相互排除を使用できる。

一例として、第１のセットは、例えばRTX（VenturCom Inc.によるReal Time Extension）によりスケジュールされることがある。このセットは、リアルタイム処理を行う高優先度のスレッドのようなスレッドで使用されることがある。第２のセットは、（Microsoftによる）Windows(登録商標) NTによりスケジュールされることがある。このセットは、バックグラウンド処理及び制御処理を行う低優先度のスレッドのようなスレッドで使用されることがある。

前記目的は、低優先度の処理（T1）と高優先度の処理（T4）を実行することに適した手段を有する、多重処理環境で異なる優先度を備えた処理を実行するためのシステムによって更に達成され、前記高優先度の処理（T4）と前記低優先度の処理（T1）が所定のリソース（SM4）を共有し、
−前記低優先度の処理（T1）が前記共有リソース（SM4）を使用する予定のときに、前記低優先度の処理（T1）の有効な優先度を一時的に上げるための手段を有し、前記有効な優先度が、前記多重環境における他の処理（T1、T2）の優先度より高く上げられること
を特徴とする。

本発明の他の好ましい実施例が従属項に定められる。

図１ａは、先行技術による異なる優先度を有する多様なスレッドの実行を示したものである。図示されているものは、例えば時間重視の動作を実行する高い優先度のスレッド、処理、タスク、ジョブ等（T4）と、例えばバックグラウンド処理を実行する低優先度又は相対的により低い優先度のスレッド（T1）と、T1とT4との間の優先度を有する中間優先度のスレッド（T2）である。全てのスレッドは、マルチプロセッサ又は多重処理環境を提供するオペレーティングシステムで実行されており、そこでは単一のスレッドのみが同時に動作中である。図は、時間の関数として、スレッド（T4、T2、T1）が動作中になるときを示している。高優先度（T4）と低優先度のスレッド（T1）はメモリのような共有リソースを使用し、前記共有メモリへのアクセスは相互排除（M）により保護される。‘wg’は‘待ち／獲得の相互排除（M）’命令、コマンド等を示し、‘r’は‘解放の相互排除（M）’を示す。

時系列の開始時にスレッド（T1）が実行しており、時間1に、スレッド（T1）が例えば（T1とT4の間の）共有メモリに書き込む必要があるため、スレッド（T1）が共有メモリを使用することを必要とすることを示す‘wg’命令を実行する。時間1の相互排除（M）は、他の処理に‘所有’されておらず、又は割り当てられていないため、スレッド（T1）は相互排除を所有し、それによってそれが解放されるまで共有リソースにアクセスする機会を獲得する。時間2に、スレッド（T1）はより高い優先度のスレッド（T4）によって先取され、時間3に、例えば共有メモリからの読み取りのため、共有リソースにアクセスを試みるため、スレッド（T4）は‘wg’命令を発行する。相互排除（M）はその時間に他の処理により所有されるため、相互排除（M）が解放され、先取されたスレッド（T1）が例えば共有メモリに書き込むことを継続するまで、スレッド（T4）が待たなければならない。時間T4において、T1が共有リソースを使用し終える前に、T4より低いがT1より高い優先度を有する他のスレッド（T2）が開始又は起動される。このスレッド（T2）は、より高い優先度のためT1を先取し、時間5で終了するまで実行される。相互排除（M9が他のスレッドにより所有されて解放されていないために、T4が待ち状態にあるため、スレッド(T2)はT4によって先取されない。この特定の例において、スレッド（T2）は、T4とT1とが共有するリソースを使用しない。

時間5において、スレッド（T2）が終了し、スレッド（T1）が動作中になる。時間6において、スレッド（T1）が共有リソースを使用し終え、相互排除（M）を解放し、その後にT4が相互排除（M4）を獲得して、それにより共有リソースにアクセスすることができる。時間7において、スレッド（T4）が共有リソースを使用し終え、相互排除（M）を解放し、スレッド（T1）が再度起動される。

このように、高優先度のスレッド（T4）は、より低い優先度であるが、リソースを共有するスレッド（T1）より高い優先度を有するスレッド（T2）によって、共有リソース等を実行及び／又はアクセスすることからロックされ、遅延し、回避されることがある。これは、高優先度のスレッドがその時間重視の動作を実行することができないことがあるため、特に時間重視のタスクを担う高優先度のスレッドにとって非常に不適当である。

図１ｂは、本発明による異なる優先度を有する多様なスレッドの実行を示したものである。図示されているものは、例えば時間重視の動作を実行する高い優先度のスレッド、処理、タスク、ジョブ等（T4）と、例えばバックグラウンド処理を実行する低優先度又は相対的により低い優先度のスレッド（T1）と、T1とT4との間の優先度を有する中間優先度のスレッド（T2）と、T4より低いが他のスレッド（T1とT2）より高い優先度を有する追加スレッド（T3）である。図は、時間の関数として、スレッド（T4、T3、T2、T1）が動作中になるときを示している。時間1において、低優先度のスレッド（T1）が高優先度のスレッド（T4）と共有するリソースにアクセスすることを必要とすることを指示する。この指示は、例えばセマフォ（semaphore）を使用又は設定することにより行われることがある。この指示が生じた場合、T4より低いが他のスレッド（T1とT2）より高い優先度を有する追加スレッドT3がT1を先取し、時間2において、共有リソースにアクセスするために‘wg’命令の実際の実行を行い、それによって共有リソースの相互排除（M）がロック、予約等される。このように、T3はT1に代わりに共有リソースにアクセスし、すなわちT1は共有リソースに直接アクセスしない。時間1において、‘s’で示される通り、好ましくはセマフォ（semaphore）を使用してT3とT1は同期される。一般的に、セマフォ（semaphore）は同期のために使用され、共有リソース又はメモリは通信のために使用される。その他に、メッセージが情報を通信し、メッセージの送受信が同期のために使用され得るように、メッセージの受け渡しが使用されることがある。

時間3において、高優先度のスレッドT4がT3を先取し、時間4の前に共有リソースにアクセスすることを試みる。しかし、共有リソースが既に（T1の代わりに）T3により使用されているため、時間4で‘wg’命令を発行した後に、Tは待ち状態になる。T4は待ち状態‘w’であるため、T3（次に高い優先度を有する）が実行を再開する。時間5において、T3が共有リソースをし終え、相互排除（M）のための解放命令を発行し、その後に共有リソースにアクセスし得るようにT4がT3を先取し、相互排除（M）を取得又はロック‘g’する。時間6において、T4が共有リソースを使用し終え、相互排除（M）を解放‘r’する。時間7において、T4が例えば時間重視のタスクを実行し終え、T3が動作中になる。時間8において、T3が終了され、例えばセマフォ（semaphore）を使用／設定することで示されるように、T1と再度同期される。その後、スレッドT2がT1を先取し、時間9で終了されるまで実行し、それによってT1が再開する。

T3とT1は、例えば共有メモリを介して及び／又はセマフォ（semaphore）を使用して、如何なる適切な機構によって通信されることがある。T3は、T4のみにより先取される（T2のような如何なる中間のスレッドにより先取されない）ことが可能であり、それが相互排除（M）を所有する限りT1を待たないため、なるべく短く相互排除（M）を所有する。通常は、例えば最終的にT1により解放されるセマフォ（semaphore）を待つことで、T1がT3に全く命令又は情報を与えていない場合、T3はT1を待つことができる。しかし、T3がT1の代わりに相互排除（M）にアクセスするときに、このことは生じない。

一般的に、T4が共有リソースに対する待ち状態にある後であって、T3が共有リソースを使用し終えるまでの短期間の間に、T4はT3により依然としてブロックされるが、この時間中に、T3はT1によって（又は間接的にT2によって）引き延ばされない。

一般的に、T1は、共有リソースにアクセスする必要があるときにより高い‘有効な’優先度を与えられる。１つの実施例において、このことは、T4より低く、他のスレッド（T1とT2）より高い追加スレッド（T3）を使用することで達成され、T1とT3は同期されて、T3はT1の代わりに共有リソースにアクセスする。

このように、T1とT4の間で共有されたリソースを使用しない中間のスレッド（T2）が高優先度のスレッド（T4）を遅延させることを可能とせず、それにより例えば高優先度のスレッドの時間重視のタスクが時間通りに実行されることを確保する。

１つの実施例において、T3の優先度は、ちょうどT4と残り（T1とT2）との間である必要がある。しかし、T1とT2とT3より大きい新しい優先度を備えた新しい処理は、図１ａに関連して説明されたように、T4を遅延させることがある。従って、好ましくはT3の優先度はT4の優先度よりわずかに低く、他のもの（T1とT2）より高い。このように、T4以外の処理はT3を先取りすることがなく、T4を更に遅延させることがない。

更なる実施例において、例えば同期されてT1の代わりに共有リソースにアクセスする追加スレッドT3により実施される低優先度のスレッド（T1）の有効な優先度は、T4の優先度と同じ、又はその他にそれより高く上げられる。そのことをスレッドT5と呼ぶ。しかし、そのスレッドはT4のリアルタイムの性能を損なうことがあるため、よく注意してプログラムされるべきである。しかし、一般的に、本発明による目的のためにT5はほとんどCPU時間を使用しない。その選択肢が図１ｃ（T4より高く上げられた有効な優先度）と図１ｄ（T4の優先度と同じ有効な優先度）に示される。図１ｄにおいて、実線がT4を示し、破線がT5を示し、帯がいずれかのスレッド（T4又はT5）が動作中になるときを示す。ここで、T1が追加スレッドT5と同期される時間T１の後に、T4と他のスレッド（T2）がT5を先取することがないことが示されている。T5は時間2と3で相互排除（M）を待ち、獲得し、解放する。時間4において、T4が動作中になり、それぞれ時間7と8でT2とT1が動作中になる前に、時間5と6で相互排除（M）を待ち、獲得し、解放する。このように、追加スレッド（T2）は、時間重視のスレッド（T4）を遅延させない。T4とT4が同じ優先度を有する場合（図１ｄ）、例えばRTXのようないくつかのオペレーティングシステムにおいて、依然としてT5を先取することができない。全く起こりそうにないが、T4がちょうど重要なタスクを有することになった場合、時間1においてT4又はT5のいずれかが開始してもよい。T4がT5の前に開始する場合、T5がT1の代わりに共有リソースにアクセスする前に、その時間重視のタスクを終了し、その後に、T4が図１ｄ（時間1から時間7）に示されるように共有リソースにアクセスする。T5がT5の前に開始する場合、それは図に示された状況に対応する。

図２ａは、本発明による方法の実施例を示したものであり、低優先度のスレッド（T1）が既に共有リソースにアクセスしている間に、高優先度のスレッド（T4）が共有リソースにアクセスすることを試みる。前記方法は、ステップ（200）で開始する。ステップ（201）において、多重処理環境の処理／スレッドが、その優先度に従って通常通り実行される。ステップ（202）において、低優先度のスレッド（T1）が共有メモリ（SM）のような共有リソースにアクセスする必要があるか否かについてテスト、指示等が行われる。そうでない場合、前記方法は通常通りステップ（201）で処理を実行する。そうである場合、前記方法はステップ（203）に進み、本発明に従ってT1の‘有効な’優先度が上げられる。ステップ（204）において、T1は、例えば共有リソースのための相互排除（M）を獲得することにより、共有リソースへのアクセスを確保し、T1がSMを使用し始める。ステップ（205）において、T1が相互排除（M）を所有している間に高優先度のスレッド（T4）が共有リソースにアクセスすることを試みるか否かが判断される。そうである場合、ステップ（206）において、T4は相互排除（M）が解放されるのを待ち、待ち状態に入る。T4が共有リソース（SM）にアクセスする必要がない場合又はT4が待っている場合、ステップ（207）において、T1は共有リソース（SM）のための相互排除（M）を終了して解放する。T1が共有リソース（SM）を終了すると、ステップ（208）においてT4が待っているか否かが判断される。そうでない場合、T1がその処理（共有リソース（SM）へのアクセス以外のものも含む）を終了し、T1の‘有効な’優先度が通常の低優先度まで低くされる。T1が共有リソース（SM）を使用し終えた（ステップ（207））直後であって、T1がその他のタスクを終了する前に、‘有効な’優先度が低くされることがある。ステップ（209）の後に、前記方法はステップ（201）に進み、処理が通常通り動作される。T4がステップ（208）で待っている場合、T4はT1を先取し、例えばステップ（210）で相互排除（M）を獲得することにより、共有リソース（SM）へのアクセスを確保し、その後にステップ（211）でT4がSMを終了し、ステップ209に進む前にステップ（212）で場合によっては他のタスクを終了する。

このように、ステップ（203）の前に他の処理、スレッド等（T4以外）がT1を先取することなく、それによってT4が非常に長く引き延ばされないことを確保する。ステップ（203）の後であってステップ（204）の前に、T4が共有リソースにアクセスする必要があることが生じることがある。この場合、それは即座に相互排除を獲得し、共有リソースを使用し、再び相互排除を解放する。T4がT1（又はT3）を先取することを回避する１つの方法は、図１ｃと図１ｄと関連して示された通り、T4の優先度と同じ又はそれより高い有効な優先度を有することによる。

前述及び後述の通り、T1の‘有効な’優先度を上げるステップが実施されると、T1の代わりに共有リソースにアクセスする追加スレッド（T3）を使用して、T4より低く、他の処理より高い優先度を有して、ステップ（203）がT1の代わりにT3を起動し、ステップ（204、207、209）においてT1の代わりにT3を読み取る。T1とT3は、好ましくはステップ（203）とステップ（209）で同期される。この実施は、図３と関連して詳細に説明される。

図２ｂは、本発明による方法の実施例を示したものであり、低優先度のスレッド（T1）が既に共有リソースにアクセスしている間に、高優先度のスレッド（T4）が共有リソースにアクセスすることを試みない。ステップ（220-224、225）は、図２ａのステップ（200-204、207）に対応する。ステップ（225）でT1が共有リソース（SM）にアクセスすることを開放した後に、ステップ（226）において、例えばBoolean（B4）、セマフォ（semaphore）又はメッセージ受け渡しを使用して、情報、データ等が待つという信号、指示等がT4に与えられる。

ステップ（227）において、T4はT1を先取し、例えば相互排除（M）を獲得することにより、共有リソースへのアクセスを確保する。ステップ（228）において、T4はリソース（SM）を使用して解放する。ステップ（229）において、T4は、もしあれば共有リソース（SM）にアクセスすることに関係しない他のタスクを終了する。ステップ（230）において、T1が実行を再開し、終了する。‘有効な’優先度が低くされ（ステップ（225）でも行われることがある）、前記方法はステップ（221）に戻る。しかし、ステップ（226）の前にT2がT1を先取することがあるため、ステップ（230）の代わりにステップ（225）で‘有効な’優先度を削減するほど有利ではなく、T4に信号が与えられる前に長い時間を必要とすることがある。

前述及び後述の通り、T1の‘有効な’優先度を上げるステップが実施されると、T1の代わりに共有リソースにアクセスする追加スレッド（T3）を使用して、T4より低く、他の処理より高い優先度を有して、ステップ（223）がT1の代わりにT3を起動し、ステップ（224、225、226、230）においてT1の代わりにT3を読み取る。T1とT3は、好ましくはステップ（223）とステップ（230）で同期される。例えば相互排除（M）又はBoolean（B4）及びセマフォ（semaphore）（S4）を使用して、必要に応じてステップ（226）でT3とT4が好ましくは同期される。しかし、いくつかのアプリケーションについては情報が待っていることをT4に単に信号で送出することで十分であるため、全ての場合においてT3とT4は同期される必要はない。この実施は、図３と関連して詳細に説明される。その他、他のところで説明された通り、‘有効な’優先度を上げることが、T4の優先度と同じ又はそれより大きい優先度を有するスレッドによって実施されることがある。

図３は、本発明による追加スレッド（T3）の実施例のためのフローチャートを示したものである。この特定の実施例において、追加スレッド（T3）（低優先度のスレッド（T1）の代わり）は、相互排除（M）により保護され、Boolean（B4）とセマフォ（semaphore）（S4）によって同期される共有メモリ（SM4）を介して、高優先度のスレッド（T4）と通信する。T3は、セマフォ（semaphore）S1AとS1Bにより同期される共有メモリ（SM1）を介して低優先度のスレッド（T1）と通信する。この特定の実施例において、情報、データ等は、追加スレッド（T3）を介して、共有メモリ（SM1）を使用する低優先度のスレッド（T1）から共有メモリ（SM4）を使用する高優先度のスレッド（T4）に転送される。

ステップ（301）において、前記方法が開始され、そこでパラメータ等の処理と初期値が設定される。この特定の例において、Boolean（B4）はfalseに設定され、情報、データ等がT4に準備済／利用可能でないことを示す。

ステップ（303）において、T3の実施例は、T1がT4への情報の送信／T4との通信の必要があるという指示を待つ。待ち状態の間、他の処理（T1とT3を含む）が通常通り動作されることがある。待ち状態は、例えばセマフォ（semaphore）（S1A）を待つことにより、すなわちT1が共有リソース（SM1）にアクセスすることを待ち、例えば共有メモリ（SM1）に情報又はデータを入れ、次に相互排除（M）が解放されるのを待つことにより、行われることがある。相互排除（M）が利用可能になった場合／後、T3が共有メモリ（SM4）にアクセスできるように、それがT3によって予約／保持される。ステップ（304）において、共有メモリ（SM1）からの内容が共有メモリ（SM4）にコピーされる。情報が転送された後、他の処理が共有リソースを使用し得るように相互排除（M）が解放される。ステップ（305）において、利用可能な情報があることをT4に示すために、Boolean（B4）が‘true’に設定される。ステップ（306）において、前記方法は、T4が共有メモリ（SM4）で情報、データ等にアクセス／使用したか否かを示すセマフォ（semaphore）（S4）を待つ。T4が前記情報を使用した後に、ステップ（307）において、セマフォ（semaphore）（S1B）が開放され、共有リソース（SM1）が他の目的のために使用されることがあること、すなわち、T4が終了したことをT1に示す。その後、新しい通信が行われる必要があるまで、前記方法が初めから行われる。

追加スレッド（T3）のこの例示的な実施例の擬似コードは以下の通りである。
Boolean B4:=false
永久に以下を実行する
{
S1Aを待つ; //T1がSM1に情報を入れるまで待つ
Mを待つ;
SM1からSM4にコピーする;
Mを解放する;
B4:=true //情報が存在することをT4に知らせる
S4を待つ; //T4がSM4の情報を使用するまで待つ
S1Bを解放する; //SM１が他の情報で満たされることができることをT1に知らせる
}
この実施例において、T4は多くの場合（例えばwhileループで）以下を実行する。
if(B4==true)
{
B4:=false;
Mを待つ;
SM4の情報を使用する;
Mを解放する;
S4を解放する
}
B4とS4はいくつかのアプリケーションで有用なことがある特別の同期を提供するが、更に実施例を複雑にする。その他に、B4とS4は実施例から取り除かれてもよい。

その他に、前記方法は、周期バッファ及び／又は異なる同期手段若しくは機構を使用してもよい。更に、SM1からSM4へのコピー動作（304）は、T1からT4へのデータ転送のためのみに使用されているため、省略されてもよく、又は他の動作（例えば情報がT4からT1に転送される場合にはSM4からSM1へのコピー動作等）に交換されてもよい。他の例は、‘リモート・プロシージャ・コール’を使用することであり、第１のプロシージャのパラメータがT1からT4にコピーされ、T4がプロシージャを実行し、プロシージャがその結果をT1にコピーし戻す。しかし、これには前述の例より更に同期を必要とする。それはまた、反対方向に動作され得る。

T3のこの例示的な実施例に関連して、図１ｂはT1がT4のために共有メモリ（MS4）に（T3を介して）データ、情報等を書き込むが、T1がそれに書き込み終える前にT4が共有メモリ（SM4）にアクセスすることを試みる場合を表すことがある。

擬似コードのラインは、以下に従って図１ｂの時間に対応することがある。
{S1Aを待つ; （T=1に対応する）
Mを待つ; （T=2）
SM1からSM4にコピーする; （T=2とT=5の間）
Mを解放する; （T=5）
B4:=true; （T=7の前）
S4を待つ; （T=7）
S1Bを解放する; （T=8）}
T1（T3）が終了される前にT4が既にSM4にアクセスを得る試みをするため、‘B4:=true’は、図１ｂの場合に実際に使用されない。そうでない場合、それは情報を取り出すためにSM4にアクセスしなければならないという信号をT4に送出する。

図４は、本発明によるシステムの実施例のブロック図を示したものである。図示されているものは、通信バス（404）又はそれと同様のものを介して、メモリ及び／又はストレージ（402）並びに他の装置又は機能（403）に接続された１つ以上のマイクロプロセッサ（401）を有する本発明によるシステム（400）である。マイクロプロセッサ（401）は、スレッドを使用してオペレーティングシステム、専門プログラム等のような他のソフトウェアと同様に、本発明による方法を実行するため、及び本発明によるスレッドを同期するための多様な処理、スレッド等（T1、T2、T3、T4）を実行する役割を行う。

メモリ又はストレージ（402）は、スレッドT4とT3によって共有される共有メモリ（SM4）若しくはファイル又はその一部のような共有リソース（402’）と、スレッドT3とT1によって共有される他の共有メモリ（SM1）又はファイルとを有する。例えば共有リソースは、例えば１つのスレッドがメモリに書き込み、他のものがそれから読み取ることがあるメモリを有する共有入出力（I/O）装置であってもよい。図示されているものはまた、図３と関連して説明された例示的な実施例の多様なスレッドを同期することに関してどの同期手段が使用されるかである。SM4の場合、それはBoolean（B4）とセマフォ（semaphore）（S4）であり、相互排除（M）がSM4へのアクセスを制御する。SM1の場合、それは第１のセマフォ（semaphore）（S1A）と第２のセマフォ（semaphore）（S1B）である。

他の装置又は機能（403）は、例えばディスプレイ、通信装置、ネットワーク装置等であってもよい。

本発明を使用し得るシステムの１つの例は、例えばデジタルビデオ等を放送するケーブルシステム、地上波システム、衛星システム等で使用されることがあるMPEG-2の再多重化装置である。また、セットトップボックス又はデジタルテレビセットのようなデジタルビデオ又はオーディオの受信機は、本発明によるシステムを有し得る。MPEG-2ストリームは、例えばRTXのリアルタイム・オペレーティングシステムのもとで動作するソフトウェア・スレッドにより、リアルタイムに処理される。一般的に、多くの制御ソフトウェアは、例えばWindows(登録商標) ＮＴの非リアルタイム・オペレーティングシステムのもとで同じプロセッサで動作する。高優先度のスレッド（T4）は、リアルタイム・オペレーティングシステムRTXのもとでのストリーム処理スレッドであってもよく、低優先度のスレッド（T1）は、Windows(登録商標) ＮＴのもとでの制御処理スレッドであってもよい。RTXは優先度の進展を提供するが、それはRTXのスレッドとWindows(登録商標) ＮＴのスレッドの間で利用可能ではない。従って、本発明によると、Windows(登録商標) ＮＴの中断、繰延処理呼び出し等のような中間優先度のスレッド（T2）によって、時間重視のスレッド（T4）が長時間引き延ばされることが回避される。このように、Windows(登録商標) ＮＴのスレッドからRTXのスレッドへの制御コマンドの通信、RTXのスレッドからWindows(登録商標) ＮＴのスレッドへのエラーメッセージの通信等が、前述の欠点なしで達成される。

先行技術による異なる優先度を有する多様なスレッドの実行を示したものである。 本発明による異なる優先度を有する多様なスレッドの実行を示したものである。 本発明の他の実施例による異なる優先度を有する多様なスレッドの実行を示したものである。 本発明の他の実施例による異なる優先度を有する多様なスレッドの実行を示したものである。 本発明による方法の実施例を示したものであり、低優先度のスレッド（T1）が既に共有リソースにアクセスしている間に、高優先度のスレッド（T4）が共有リソースにアクセスすることを試みる。 本発明による方法の実施例を示したものであり、低優先度のスレッドが既に共有リソースにアクセスしている間に、高優先度のスレッドが共有リソースにアクセスすることを試みない。 本発明による追加スレッド（T3）の実施例のフローチャートを示したものである。 本発明によるシステムを示したものである。

Claims (15)

1. 低優先度の処理と高優先度の処理との実行を有する多重処理環境で、異なる優先度を備えた処理を実行する方法であって、
   前記高優先度の処理と前記低優先度の処理とが所定のリソースを共有し、
   前記方法は、前記低優先度の処理が前記共有リソースを使用する予定のときに、前記低優先度の処理の有効な優先度を一時的に上げるステップを有し、
   前記有効な優先度が、前記多重処理環境における他の処理の優先度より高く上げられ、
   前記方法は、前記低優先度の処理の代わりに実行する追加処理を用いるステップを有し、
   前記有効な優先度を上げるステップが、前記低優先度の処理の代わりに前記共有リソースにアクセスする前記追加処理を実行する／割り当てるステップを有し、前記追加処理が前記有効な優先度と同じ優先度を有し、
   前記有効な優先度は、前記追加処理が前記低優先度の処理の代わりに実行されていない場合、前記低優先度の処理の優先度と同じであり、
   前記有効な優先度は、前記追加処理が前記低優先度の処理の代わりに実行されている場合、前記追加処理の優先度と同じであることを特徴とする方法。
2. 請求項１に記載の方法であって、
   前記追加処理が前記低優先度の処理と同期されることを特徴とする方法。
3. 請求項１に記載の方法であって、
   前記多重処理環境が、少なくとも所定の時間に単一のプロセッサで実行するリアルタイム・オペレーティングシステムと非リアルタイム・オペレーティングシステムとを有し、
   前記リアルタイム・オペレーティングシステムが、前記高優先度のスレッドと前記追加処理とを有し、
   前記非リアルタイム・オペレーティングシステムが前記低優先度のスレッドを有することを特徴とする方法。
4. 請求項２に記載の方法であって、
   前記追加処理と前記低優先度の処理とが、第１のセマフォ（semaphore）と第２のセマフォ（semaphore）を使用して同期される方法。
5. 請求項１に記載の方法であって、
   前記有効な優先度が、
   少なくとも前記低優先度の処理が前記共有リソースにアクセス若しくは使用するまで、又は
   前記低優先度の処理が前記共有リソースにアクセス若しくは使用する間に、前記高優先度の処理が前記共有リソースにアクセス若しくは使用することを試みた場合に、少なくとも前記高優先度の処理が前記共有リソースにアクセス若しくは使用するまで
   上げられることを特徴とする方法。
6. 請求項１に記載の方法であって、
   前記低優先度の処理の前記有効な優先度が、前記高優先度のものより低くなり、他の処理のものより高くなるように上げられることを特徴とする方法。
7. 請求項４に記載の方法であって、
   前記共有リソースへのアクセスが相互排除によって制御され、
   それにより前記追加処理が、前記追加処理が前記相互排除を所有する限り、前記低優先度の処理の実行を待たないことを特徴とする方法。
8. 請求項１に記載の方法であって、
   前記共有リソースが、
   共有メモリと、
   共有ファイルと、
   共有入出力装置と
   のグループから選択されることを特徴とする方法。
9. 請求項１に記載の方法であって、
   前記高優先度の処理が時間重視のタスクを実行することを特徴とする方法。
10. 低優先度の処理と高優先度の処理とを実行するように適合された手段を有する、多重処理環境で異なる優先度を備えた処理を実行するためのシステムであって、
    前記高優先度の処理と前記低優先度の処理とが所定のリソースを共有し、
    前記システムは、前記低優先度の処理が前記共有リソースを使用する予定のときに、前記低優先度の処理の有効な優先度を一時的に上げるための手段を有し、
    前記有効な優先度が、前記多重処理環境における他の処理の優先度より高く上げられ、
    前記有効な優先度を上げるための手段は、前記低優先度の処理の代わりに前記共有リソースにアクセスする前記追加処理を実行する／割り当てるように構成され、追加処理が前記有効な優先度と同じ優先度を有し、
    前記有効な優先度は、前記追加処理が前記低優先度の処理の代わりに実行されていない場合、前記低優先度の処理の優先度と同じであり、
    前記有効な優先度は、前記追加処理が前記低優先度の処理の代わりに実行されている場合、前記追加処理の優先度と同じであることを特徴とするシステム。
11. 請求項１０に記載のシステムであって、
    前記低優先度の処理と前記追加処理とを同期するように構成された同期手段を有することを特徴とするシステム。
12. 請求項１０に記載のシステムであって、
    少なくとも所定の時間に単一のプロセッサで実行するリアルタイム・オペレーティングシステムと非リアルタイム・オペレーティングシステムとを有する単一のプロセッサを有し、
    前記リアルタイム・オペレーティングシステムが、前記高優先度のスレッドと前記追加処理とを有し、
    前記非リアルタイム・オペレーティングシステムが前記低優先度のスレッドを有することを特徴とするシステム。
13. 請求項１ないし９のうちのいずれか１項に記載の方法を１つ以上の処理ユニットに実行させるための命令を保存したコンピュータ読み取り可能媒体。
14. 請求項１０に記載のシステムを有するセットトップボックス。
15. 請求項１０に記載のシステムを有するテレビセット。

Images