pthreadについて（スケジューリング）

スケジューリングの設定とプライオリティ逆転の回避法

9. スケジューリング（プライオリティ逆転）

9.6 プライオリティ逆転

　低いプライオリティを持つスレッド（A）が、あるmutexをロックし処理を行っていたとします。その最中に高いプライオリティを持つスレッド（B）が出現しmutexをロックしようとした場合、（A）がmutexをロックしているので、（B）はサスペンドします。

　複数のスレッドが1つのmutexに対してlockを獲得する順番は、仕様として明確にはされていませんが、通常、pthread_mutex_lockにたどり着いた順番になっているようです。

　つまり先ほどのプログラムの通りプライオリティが低い順でスレッドが起動されると、プライオリティが高いスレッドほど、mutexのロック獲得が遅く、結果的に遅く起動する事になります。

　これをプライオリティ逆転と言い、より早く処理して欲しいがためにプライオリティを設定しているにも関わらず、皮肉にも逆順で処理されてしまいます。

　さらに、私は経験は無いですが、プライオリティが低いスレッドがスレッド切り替えポイントでサスペンドし、プライオリティが高いスレッドはmutex_lock待ち状態、いわゆるプライオリティ逆転によるデッドロックも環境によっては発生する可能性があります。

　また、プライオリティ逆転の発生は実装依存な所もあります。私の環境の場合、Fedora 8では発生しませんでしたが、Fedora Core 6ではプライオリティ逆転が発生しました。当章の以降はFedora Core 6環境で行います。

---
root # diff sched_fifo.c sched_inversion_fifo.c
1c1
< /* gcc sched_fifo.c -o sched_fifo -W -Wall -g -lpthread */
---
> /* gcc sched_inversion_fifo.c -o sched_inversion_fifo -W -Wall -g -lpthread */
85d84
<     pthread_mutex_unlock( &m2 );
94a94
>     pthread_mutex_unlock( &m2 );
root #
---

　上記の通り、プログラムsched_inversion_fifo.cはsched_fifo.cとほとんど大差の無いプログラムです。違いはスレッド内でmutex_lock/unlockをループを挟んでいるかの違いだけです。

　しかし実行すると、Fedora Core 6では見事にプライオリティが低い順に処理が行われました。

root # ./sched_inversion_fifo f
 0 policy FIFO, priority [1 - 99] 1
 1 policy FIFO, priority [1 - 99] 33
 2 policy FIFO, priority [1 - 99] 66
 3 policy FIFO, priority [1 - 99] 99
 0 End!!40000
 1 End!!        40000
 2 End!!                40000
 3 End!!                        40000
 0 policy FIFO, priority 99 timesec:[2.495810]
 1 policy FIFO, priority 99 timesec:[5.408099]
 2 policy FIFO, priority 99 timesec:[8.544846]
 3 policy FIFO, priority 99 timesec:[11.962321]
root #

　もちろんSCHED_RRで行っても同様の結果です。

root # ./sched_inversion_rr r
 0 policy RR, priority [1 - 99] 1
 1 policy RR, priority [1 - 99] 33
 2 policy RR, priority [1 - 99] 66
 3 policy RR, priority [1 - 99] 99
 0 End!!40000
 1 End!!        40000
 2 End!!                40000
 3 End!!                        40000
 0 policy RR, priority 99 timesec:[2.524910]
 1 policy RR, priority 99 timesec:[5.558175]
 2 policy RR, priority 99 timesec:[8.740194]
 3 policy RR, priority 99 timesec:[12.143566]
root #

　スケジューリングを行う際、プライオリティ逆転、特にそれによるデッドロックは避けなくてはいけません。主な対策は2つあります。プライオリティ継承mutexとプライオリティ最高限度mutexです。以下に対策を述べます。

9.6.1 プライオリティ継承mutex

　主に2点の特徴があります

1. プライオリティの低いスレッド（A）がmutex_lockし処理している時にプライオリティの高いスレッド（B）が現れた時、（A）のプライオリティは一時的に（B）と同じプライオリティまで引き上げられます。
2. 全スレッドがmutexをlockしようと待っている時、待っているスレッドの中で1番プライオリティが高いスレッドがmutex_lockを行います。
3. コード記述量も少なく、プロセスへの影響もありません。

　サンプルsched_prio_inherit_fifo.cを試してみてください。プライオリティ順に処理がなされているのが分かります。

root # ./sched_prio_inherit_fifo f
 0 policy FIFO, priority [1 - 99] 1
 1 policy FIFO, priority [1 - 99] 33
 2 policy FIFO, priority [1 - 99] 66
 3 policy FIFO, priority [1 - 99] 99
 3 End!!                        40000
 2 End!!                40000
 1 End!!        40000
 0 End!!40000
 0 policy FIFO, priority 99 timesec:[11.966973]
 1 policy FIFO, priority 99 timesec:[9.197179]
 2 policy FIFO, priority 99 timesec:[6.240074]
 3 policy FIFO, priority 99 timesec:[3.241246]
root #

　sched_inversion_fifo.cとのプログラムの比較をした結果が下記です。

root # diff sched_inversion_fifo.c sched_prio_inherit_fifo.c
1c1,2
< /* gcc sched_inversion_fifo.c -o sched_inversion_fifo -W -Wall -g -lpthread */
---
> /* gcc sched_prio_inherit_fifo.c -o sched_prio_inherit_fifo -W -Wall -g -lpthread */
> #define _GNU_SOURCE
12c13
< pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;
---
> pthread_mutex_t m2;
24a26
>     pthread_mutexattr_t attr;
34a37,41
>
>     pthread_mutexattr_init( &attr );
>     pthread_mutexattr_setprotocol(  &attr, PTHREAD_PRIO_INHERIT );
>     pthread_mutex_init( &m2, &attr );
>
root #

　具体的な方法についてはプログラムの差分を参照して欲しいのですが、上記の通りmutexに属性を設定する事でmutexへのプライオリティ継承の設定を行っています。それ以外の処理方法やスレッド側の処理に一切変更がありません。

9.6.2 プライオリティ最高限度mutex

　主に2点の特徴があります。

1. プライオリティの低いスレッド（A）がmutexをlockした時、（A）はmutexの属性として設定されたプライオリティに引き上げられます。
2. 全スレッドがmutexをlockしようと待っている時、待っているスレッドの中で1番プライオリティが高いスレッドがmutex_lockを行います。
3. スレッド呼び出し元（例えばmain関数等）がプライオリティ最高限度mutexをlockする必要がある場合、プロセス自身もスケジューリング処理を行う必要があります。

　サンプルsched_prio_ceiling_fifo.cを試してみてください。プライオリティ順に処理がなされているのが分かります。

root # ./sched_prio_ceiling_fifo f
 0 policy FIFO, priority [1 - 99] 1
 1 policy FIFO, priority [1 - 99] 33
 2 policy FIFO, priority [1 - 99] 66
 3 policy FIFO, priority [1 - 99] 99
 3 End!!                        40000
 2 End!!                40000
 1 End!!        40000
 0 End!!40000
 0 policy FIFO, priority 99 timesec:[11.592717]
 1 policy FIFO, priority 99 timesec:[9.040339]
 2 policy FIFO, priority 99 timesec:[6.282895]
 3 policy FIFO, priority 99 timesec:[3.259127]
root #

　sched_inversion_fifo.cとのプログラムの比較をした結果が下記です。

root # diff sched_inversion_fifo.c sched_prio_ceiling_fifo.c
1c1,2
< /* gcc sched_inversion_fifo.c -o sched_inversion_fifo -W -Wall -g -lpthread */
---
> /* gcc sched_prio_ceiling_fifo.c -o sched_prio_ceiling_fifo -W -Wall -g -lpthread */
> #define _GNU_SOURCE
12c13
< pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;
---
> pthread_mutex_t m2;
24a26
>     pthread_mutexattr_t attr;
34a37,45
>
>     thread_param.sched_priority = sched_get_priority_min
      ( SCHED_FIFO );
>     sched_setscheduler( 0, SCHED_FIFO, &thread_param );
>
>     pthread_mutexattr_init( &attr );
>     pthread_mutexattr_setprotocol( &attr, PTHREAD_PRIO_PROTECT );
>     pthread_mutexattr_setprioceiling(
      &attr,sched_get_priority_max( SCHED_FIFO ));
>     pthread_mutex_init( &m2, &attr );
>
root #

　上記の通り、プロセス側でもスケジューリング処理を行う必要があるのと、mutexにプライオリティ最高限度の設定が必要です。それ以外の処理方法やスレッド側の処理に一切変更がありません。

　プライオリティ逆転を回避するには、どちらを使っても良いと思います。細かな処理は置いといて単にプライオリティ逆転を防ぎたいのであればプライオリティ継承mutex、より細かな設定ができるのがプライオリティ最高限度mutexです。

9.7 所感

　以上でスケジューリングの説明を終えます。

　個人的にはスケジューリング処理の使用は控えた方がよいと思います。特権を持っていないと使用できなかったり、移植性も怪しいです。特権が無くても使用できるsched_yield関数も、必要性が無ければ使用は避けた方がよいと思います。処理が無駄に遅くなるだけです。

　もし使用する場合、プライオリティ逆転による性能劣化やサスペンドが発生する可能性がありますので、プライオリティ逆転の回避を心がけるようにしましょう。

　次回はスレッドのキャンセル処理とその危険性について述べる予定です。