(itron-club 1669) Re: 優先度上 限プロトコルについて (長文注意)

[NAKAMURA Katsuyuki <milkyway __at__ ss.iij4u.or.jp>]

中村です。

多くの方々からコメントをいただき、ありがとうございました。
長文のコメントお許し下さい。

1) uITRON 4.0仕様の優先度上限プロトコル
uITRON4.0の仕様書を持っていますので、それを確認してから、
質問すべきであったと反省しています。

Takanori Hayashi wrote:
>実際、μITRON仕様書を読むとそのようなことが書かれています。正確には
>優先度上限プロトコルの派生プロトコルを実装したというところでしょうか。
># μITRON4.01 4.5.1ミューテックスの【補足説明】から(p.176)
>> ここでいう優先度上限プロトコルは，広い意味での優先度上限プロトコルで，
>> 最初に優先度上限プロトコルとして提案されたアルゴリズムではない．厳密に
>> は，highest locker protocolなどと呼ばれているアルゴリズムである．
上記記述を確認しました。

高田先生の書かれた「ハードリアルタイムスケジューリング理論の概要(2)
(第2回 ITRON HRT研究会資料)」から引用すると、
>Highest locker Protocol(このプロトコルには、広
>く認められた名称がない。Ceiling semaphore proto-
>colと呼んでいるケースもある。次に紹介するpriority
>ceiling protocolという名前が、このプロトコルを差し
>ている場合もある)
だそうです。なんだかややこしいですね。

「リアルタイムOSと組み込み技術の基礎　実践uITRONプログラミング」
TECH I Vol.17 CQ出版社 pp.40-41
>この方式は厳密にはhighest looker protocolと呼ばれているものである

#図2.23の優先度上限プロトコルの説明はuITRON4.0仕様に基づいている。

2) A Priority Inheritance Approach
さて、その優先度上限プロトコルを考え出した人の著書
「SYNCHRONIZATION IN REAL-TIME SYSTEMS A Priority Inheritance
Approach」 Rajkumar著のpp.26-27によれば、

Definition: The priority ceiling of a semaphore is defined as the priority of the
highest priority job that may lock this semaphore. 
中略
Recall that the priority of job J1 is assumed to be higher than
that of job J2. Thus, the priority ceilings of both semaphore S1
and S2 are equal to the priority of job J1.
中略
At time t0, J2 is initiated and begins execution.
At time t1, J2 locks semaphore S2.
At time t2, job J1 is initiated and preempts job J2.
At time t3, job J1 tries to enter its critical section by making
an indivisible system call to execute P(S1). However, the run-
time system finds that S2 is locked, and p(J1) < c(S2). Hence,
the run-time system suspends job J1 without locking S1. Job
J2 now inherits the priority of job J1 and resumes execution.

と書かれています。c(S2) = p(J1)ですから、
p(J1) < c(S2)は明らかに矛盾すると思うのですが・・・
p(J1) =<c(S2)ではないかと思うのですが・・・

「HARD REAL-TIME COMPUTING SYSTEMS Predictable Scheduling
Algorithms and Applications」 Buttazzo著のpp.202-204によれば、

At time t2, J1 attempts to lock S2, but it is blocked by the protocol
because P1 is not greater than C(S2). Then, J2 inherits the priority of J1
and resumes its execution.

となっています。

3) Pスレッド
Pスレッドの場合のmutexの実装がどうなっているのか気になりましたので、
調べてみました。
「POSIXスレッドプログラミング」 David R.Butenhof著
アジソン・ウェスレイ社刊　pp.211-212

プライオリティ最高限度mutexがuITRON仕様の優先度上限プロトコル
(つまり highest locker protocol)に相当するようです。

いい勉強になりました。
本来あるべき優先度上限プロトコルの実装をみれば、さらに勉強に
なるでしょうが・・・

以上

----
中村　勝之