タスク状態とスケジューリング規則

タスク状態

タスク状態は、大きく次の5つに分類される。この内、広義の待ち状態は、さらに3つの状態に分類される。また、実行状態と実行可能状態を総称して、実行できる状態と呼ぶ。

実行状態 (RUNNING)

現在そのタスクを実行中であるという状態。ただし、タスク独立部を実行している間は、別に規定されている場合を除いて、タスク独立部の実行を開始する前に実行していたタスクが実行状態であるものとする。

実行可能状態 (READY)

そのタスクを実行する準備は整っているが、そのタスクよりも優先順位の高いタスクが実行中であるために、そのタスクを実行できない状態。言い換えると、実行できる状態のタスクの中で最高の優先順位になればいつでも実行できる状態。

広義の待ち状態

そのタスクを実行できる条件が整わないために、実行ができない状態。言い換えると、何らかの条件が満たされるのを待っている状態。タスクが広義の待ち状態にある間、プログラムカウンタやレジスタなどのプログラムの実行状態を表現する情報は保存されている。タスクを広義の待ち状態から実行再開する時には、プログラムカウンタやレジスタなどを広義の待ち状態になる直前の値に戻す。広義の待ち状態は、さらに次の3つの状態に分類される。

待ち状態 (WAITING)

何らかの条件が整うまで自タスクの実行を中断するシステムコールを呼び出したことにより、実行が中断された状態。

強制待ち状態 (SUSPENDED)

他のタスクによって、強制的に実行を中断させられた状態。

二重待ち状態 (WAITING-SUSPENDED)

待ち状態と強制待ち状態が重なった状態。待ち状態にあるタスクに対して、強制待ち状態への移行が要求されると、二重待ち状態に移行させる。

T-Kernelでは「待ち状態(WAITING)」と「強制待ち状態(SUSPENDED)」を明確に区別しており、タスクが自ら強制待ち状態(SUSPENDED)になることはできない。

休止状態 (DORMANT)

タスクがまだ起動されていないか、実行を終了した後の状態。タスクが休止状態にある間は、実行状態を表現する情報は保存されていない。タスクを休止状態から起動する時には、タスクの起動番地から実行を開始する。また、別に規定されている場合を除いて、レジスタの内容は保証されない。

未登録状態 (NON-EXISTENT)

タスクがまだ生成されていないか、削除された後の、システムに登録されていない仮想的な状態。

実装によっては、以上のいずれにも分類されない過渡的な状態が存在する場合がある(システム状態参照)。

実行可能状態に移行したタスクが、現在実行中のタスクよりも高い優先順位を持つ場合には、実行可能状態への移行と同時にディスパッチが起こり、即座に実行状態へ移行する場合がある。この場合、それまで実行状態であったタスクは、新たに実行状態へ移行したタスクにプリエンプトされたという。また、システムコールの機能説明などで、「実行可能状態に移行させる」と記述されている場合でも、タスクの優先順位によっては、即座に実行状態に移行させる場合もある。

タスクの起動とは、休止状態のタスクを実行可能状態に移行させることをいう。このことから、休止状態と未登録状態以外の状態を総称して、起動された状態と呼ぶことがある。タスクの終了とは、起動された状態のタスクを休止状態に移行させることをいう。

タスクの待ち解除とは、タスクが待ち状態の時は実行可能状態に、二重待ち状態の時は強制待ち状態に移行させることをいう。また、タスクの強制待ちからの再開とは、タスクが強制待ち状態の時は実行可能状態に、二重待ち状態の時は待ち状態に移行させることをいう。

一般的な実装におけるタスクの状態遷移を[図1]に示す。実装によっては、この図にない状態遷移を行う場合がある。

図 1. タスク状態遷移図

T-Kernelの特色として、自タスクの操作をするシステムコールと他タスクの操作をするシステムコールを明確に分離しているということがある[表1]。これは、タスクの状態遷移を明確にし、システムコールの理解を容易にするためである。自タスク操作と他タスク操作のシステムコールを分離しているということは、言い換えると、実行状態からの状態遷移とそれ以外の状態からの状態遷移を明確に分離しているという意味にもなる。

表 1. 自タスク、他タスクの区別と状態遷移図

 

自タスクに対する操作

(実行状態からの遷移)

他タスクに対する操作

(実行状態以外からの遷移)

タスクの待ち状態(強制待ち状態を含む)への移行

tk_slp_tsk

実行状態 → 待ち状態

tk_sus_tsk

実行可能、待ち状態 → 強制待ち、二重待ち状態

タスクの終了 tk_ext_tsk

実行状態 → 休止状態

tk_ter_tsk

実行可能、待ち状態 → 休止状態

タスクの削除 tk_exd_tsk

実行状態 → 未登録状態

tk_del_tsk

休止状態 → 未登録状態

注意補足事項
 

待ち状態と強制待ち状態は直交関係にあり、強制待ち状態への移行の要求は、タスクの待ち解除条件には影響を与えない。言い換えると、タスクが待ち状態にあるか二重待ち状態にあるかで、タスクの待ち解除条件は変化しない。そのため、資源獲得のための待ち状態(セマフォ資源の獲得待ち状態やメモリブロックの獲得待ち状態など)にあるタスクに強制待ち状態への移行が要求され、二重待ち状態になった場合にも、強制待ち状態への移行が要求されなかった場合と同じ条件で資源の割付け(セマフォ資源やメモリブロックの割付けなど)が行われる。

注意仕様決定の理由
 

T-Kernelにおいて待ち状態(自タスクによる待ち)と強制待ち状態(他のタスクによる待ち)を区別しているのは、それらが重なる場合があるためである。それらが重なった状態を二重待ち状態として区別することで、タスクの状態遷移が明確になり、システムコールの理解が容易になる。それに対して、待ち状態のタスクはシステムコールを呼び出せないため、複数の種類の待ち状態(例えば、起床待ち状態とセマフォ資源の獲得待ち状態)が重なることはない。T-Kernelでは、他のタスクによる待ちには一つの種類(強制待ち状態)しかないため、強制待ち状態が重なった状況を強制待ち要求のネストと扱うことで、タスクの状態遷移を明確にしている。

タスクのスケジューリング規則

T-Kernelにおいては、タスクに与えられた優先度に基づくプリエンプティブな優先度ベーススケジューリング方式を採用している。同じ優先度を持つタスク間では、FCFS(First Come First Served)方式によりスケジューリングを行う。具体的には、タスクのスケジューリング規則はタスク間の優先順位を用いて、タスク間の優先順位はタスクの優先度によって、それぞれ次のように規定される。実行できるタスクが複数ある場合には、その中で最も優先順位の高いタスクが実行状態となり、他は実行可能状態となる。タスク間の優先順位は、異なる優先度を持つタスク間では、高い優先度を持つタスクの方が高い優先順位を持つ。同じ優先度を持つタスク間では、先に実行できる状態(実行状態または実行可能状態)になったタスクの方が高い優先順位を持つ。ただし、システムコールの呼出により、同じ優先度を持つタスク間の優先順位が変更される場合がある。

最も高い優先順位を持つタスクが替わった場合には、ただちにディスパッチが起こり、実行状態のタスクが切り替わる。ただし、ディスパッチが起こらない状態(ハンドラ実行中やディスパッチ禁止状態など)になっている場合には、実行状態のタスクの切替えは、ディスパッチが起こる状態となるまで保留される。

注意補足事項
 

T-Kernelのスケジューリング規則では、優先順位の高いタスクが実行できる状態にある限り、それより優先順位の低いタスクは全く実行されない。すなわち、最も高い優先順位を持つタスクが待ち状態に入るなどの理由で実行できない状態とならない限り、他のタスクは全く実行されない。この点で、複数のタスクを公平に実行しようというTSS(Time Sharing System)のスケジューリング方式とは根本的に異なっている。

ただし、同じ優先度を持つタスク間の優先順位は、システムコールを用いて変更することが可能である。アプリケーションがそのようなシステムコールを用いて、TSSにおける代表的なスケジューリング方式であるラウンドロビン方式を実現することができる。

同じ優先度を持つタスク間では、先に実行できる状態(実行状態または実行可能状態)になったタスクの方が高い優先順位を持つことを、図の例を用いて説明する。[図2]は、優先度1のタスクA、優先度3のタスクE、優先度2のタスクB、タスクC、タスクDがこの順序で起動された後のタスク間の優先順位を示す。この状態では、最も優先順位の高いタスクAが実行状態となっている。

ここでタスクAが終了すると、次に優先順位の高いタスクBを実行状態に遷移させる[図3]。その後タスク Aが再び起動されると、タスクBはプリエンプトされて実行可能状態に戻るが、この時タスクBは、タスクCとタスクDのいずれよりも先に実行できる状態になっていたことから、同じ優先度を持つタスクの中で最高の優先順位を持つことになる。すなわち、タスク間の優先順位は[図2]の状態に戻る。

次に、[図3]の状態でタスクBが待ち状態になった場合を考える。タスクの優先順位は実行できるタスクの間で定義されるため、タスク間の優先順位は[図4]の状態となる。その後タスクBが待ち解除されると、タスクBはタスクCとタスクDのいずれよりも後に実行できる状態になったことから、同じ優先度を持つタスクの中で最低の優先順位となる[図5]。

以上を整理すると、実行可能状態のタスクが実行状態になった後に実行可能状態に戻った直後には、同じ優先度を持つタスクの中で最高の優先順位を持っているのに対して、実行状態のタスクが待ち状態になった後に待ち解除されて実行できる状態になった直後には、同じ優先度を持つタスクの中で最低の優先順位となる。

なお、タスクが強制待ち状態(SUSPENDED)から実行できる状態になった直後にも、同じ優先度を持つタスクの中で最低の優先順位となる。仮想記憶システムにおいては、ページイン待ちを強制待ち(SUSPENDED)によって行うため、このようなシステムにおいては、ページイン待ちによってタスクの優先順位が変化する。

図 2. 最初の状態の優先順位

図 3. タスクBが実行状態になった後の優先順位

図 4. タスクBが待ち状態になった後の優先順位

図 5. タスクBが待ち解除された後の優先順位