優先度逆転現象 lock (blocked) 𝜏1 高優先度 𝜏2 中優先度 unlock lock 𝜏3 低優先度

優先度継承プロトコル Pr( 𝜏 𝐿 )<Pr (𝜏 𝐻 ) として 　 𝜏 𝐿 が lock している mutex を 𝜏 𝐻 が lock しようとして ブロックしている間、 𝜏 𝐿 の優先度を 𝜏 𝐻 の優先度 Pr( 𝜏 𝐻 ) とする （優先度継承）

優先度継承プロトコル 𝜏𝐴 (10) lock (blocked) unlock 𝜏𝐵 (8) lock (blocked) unlock 𝜏𝐶 (6) lock unlock 𝜏𝐷 (2) 6 10 継承優先度

クリティカルセクションのネスト … lock r1 lock r2 unlock r2 unlock r1 r2に関する クリティカル

CSネスト時の優先度継承プロトコル 𝜏𝐴 (10) lock-r1 (blocked) lock-r2 (blocked) unlock-r2 𝜏𝐵 (8) 𝜏𝐶 (6) lock-r1 unlock-r2 lock-r2 𝜏𝐷 (2) 8 10 継承優先度

CSネスト時の優先度継承プロトコル 10⇒8とする仕組みが必要 𝜏𝐴 (10) lock-r1 (blocked) lock-r2 unlock-r2 𝜏𝐵 (8) 𝜏𝐶 (6) lock-r1 unlock-r2 unlock-r1 lock-r2 𝜏𝐷 (2) 8 10 8 継承優先度 10⇒8とする仕組みが必要

連続ブロック unlock -r1 unlock -r2 unlock -r3 𝜏𝐴 (10) lock-r3 lock-r1 (blocked) lock-r2 (blocked) lock-r3 (blocked) 𝜏𝐵 (8) 10 unlock lock-r2 unlock 𝜏𝐶 (6) 10 lock-r1 unlock 𝜏𝐷 (2) 10 継承優先度

シーリング優先度プロトコル Highest Locker Priority Protocol PC(𝑟): max 𝜏∈𝑟を𝑙𝑜𝑐𝑘するタスク集合 Pr(𝜏) 　タスク 𝜏 が mutex 𝑟 を lock している間、𝜏 の優先度を一 時的に PC(𝑟) 、もしくはそれ以上とする 各タスク 優先度固定 lock する mutex がシステム起動時に決定済

CSネスト時のシーリング優先度プロトコル PC 𝑟1 =8 PC(𝑟2)=10 lock-r1 lock-r2 unlock-r2 unlock-r1 𝑟2 𝜏𝐴 (10) unlock-r2 10 8 𝑟1 𝜏𝐵 (8) 𝜏𝐶 (6) lock-r1 lock-r2 𝑟1,𝑟2 𝜏𝐷 (2) 8

シーリング優先度プロトコル によるデッドロックの抑制 シーリング優先度プロトコル によるデッドロックの抑制 lock-r2 𝜏2 (10) lock-r1 lock-r2 unlock-r2 unlock-r1 𝜏1 (5) 10 継承優先度 PC(𝑟1)=10 PC(𝑟2)=10

シーリング優先度プロトコルによる 連続ブロックの回避 シーリング優先度プロトコルによる 連続ブロックの回避 𝜏𝐴 (10) 𝜏𝐵 (8) 𝜏𝐶 (6) lock-r1 unlock 𝜏𝐷 (2) 10 継承優先度

優先度シーリングプロトコル PC(𝑟): max 𝜏∈𝑟を𝑙𝑜𝑐𝑘するタスク集合 Pr(𝜏) CP(𝜏): max 𝑟∈他のタスクが𝑙𝑜𝑐𝑘している𝑚𝑢𝑡𝑒𝑥 PC(𝑟) 優先度継承プロトコル ＋ タスク 𝜏 のlock：　Pr(𝜏)≤CP(𝜏) ならブロック 各タスク 優先度固定 lock する mutex がシステム起動時に決定済

連続ブロックの回避 PC(𝑟1)=PC(𝑟2)=PC(𝑟3)=10 unlock -r1 unlock -r2 unlock -r3 𝜏𝐴 (10) lock-r3 (blocked) lock-r1 (blocked) lock-r3 lock-r2 𝜏𝐵 (8) lock-r2 (blocked) unlock unlock 𝜏𝐶 (6) lock-r1 unlock 𝜏𝐷 (2) 6 8 10 PC(𝑟1)=PC(𝑟2)=PC(𝑟3)=10

デッドロックの予防 PC(𝑟1)=10 PC(𝑟2)=10 lock-r2 (blocked) Pr 𝜏2 = 𝐶𝑃(𝜏2) なのでブロックされる 𝜏2 (10) 𝐶𝑃(𝜏2) 10 lock-r1 lock-r2 unlock-r2 unlock-r1 𝜏1 (5) PC(𝑟1)=10 PC(𝑟2)=10