優先度逆転現象 lock (blocked)

Presentation on theme: "優先度逆転現象 lock (blocked) "— Presentation transcript:

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

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

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

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

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

6 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とする仕組みが必要

7 連続ブロック 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 継承優先度

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

9 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

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

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

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

13 連続ブロックの回避 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

14 デッドロックの予防 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