OS

【OS】デットロック

システムモデル

システムはリソースで構成されている。リソースのタイプは、R_1,R_2, ... R_mR_iW_iのインスタンスを持っている。

プロセスは、次のようにリソースを使用する。

request:プロセスはリソースを使用する前にリソースを要求する。リソースが使用できない場合は、wait stateに入る

use:リソースを獲得し、リソースを操作する

release:リソースを使用した後プロセスを解放する。

マルチスレッドアプリケーションのデッドロック

初期化された2つのmutex lockか作成される。

スレッド1がfirst_mutexを取得して、スレッド2がsecond_mutexを取得するとデットロックが発生する可能がある。

resource allocation graph

Resource-Allocation Graph

頂点(Vertices)と辺(edge)

P = {P_1, P_2, ... ,P_n} = T = {T_1, T_2, ... ,T_n}
システムを構成する全てのプロセス

R = {R_1, R_2, ... ,R_m}
システムにある全てのリソースタイプ

request edge: P_i \rightarrow R_j
プロセスP_iがリソースタイプのリソースR_jを要求している

assignment edge: R_i \rightarrow P_i
リソースR_jのインスタンスがプロセスP_jに割り当て当てられている。

claim edge: P_i \dashrightarrow R_j
プロセスP_iが将来にリソースタイプR_jを要求する

Resource-Allocation Graphの例

T1はリソースタイプがR_2のインスタンスを1つ持っているリソースタイプがR_1の割り当てを待っている。T2はR_1R_2のインスタンスを持っておりR_3のインスタンスの割り当てを待っている。T3はR_3のインスタンスを割り当てられている。T_1T_2はwaiting state

デットロックがあるリソースアロケーショングラフ

サイクルはあるがデットロックはないリソースアロケーショングラフ

特徴

グラフにサイクルがない場合
→デットロックは起きない

グラフにサイクルがある場合
→リソースタイプごとにインスタンスが1つの場合デットロックが起きる。
→リソースタイプごとにインスタンスが複数ある場合デットロックが起きる可能性

デッドロックになるための条件

デッドロック、4 つの条件同時保持される場合発生する可能性があります
→逆に言えば、一つの条件を満たさなければデットロックは起きない。

Mutual exclusion

一度に一つのプロセスのみがリソースを使用できる。別のプロセスがそのリソースを要求する場合、要求したプロセスはリソースが解放するまで待機する。

Hold and wait

少なくとも1つのリソースを保持しているプロセスは、 他のプロセスが保持している追加のリソースの取得を待機しています

No preemption

リソースは、そのプロセスがタスクを完了した後、それを保持しているプロセスによってのみ自発的に解放できま す。

Circular wait

{P_0, P_1, ... P_n}の待ち行列。P_0P_1に保持されたリソースを待いる。また、。P_1P_2に保持されたリソースを待っている・・・P_{n}P_0に保持されたリソースを待っている

デッドロックを処理する方法

デットロックを処理する方法は3つあります。
①プロトコルを使用してシステムがデットロック状態に入らないようにする。

②システムがデットロック状態に入ることはできるが、入ったら回復する

③問題を全て無視して、システムでデットロックが発生していないふりをする。これは、UNIXなどの様々なOSで使用されている。

デッドロック防止

デットロックに必要な4つの条件のいずれかを無効にする。

Mutual Exclusion

共有可能なリソース(読み取り専用ファイルなど)には、必要ない。共有できないリソースを保持する必要がある。

Hold and Wait

プロセスがリソースを要求するたびに、他のリソース を保持しないことを保証する必要があります。

方法

①実行を開始する前に、プロセスに全てのリソースを要求して割り当てられることを要求する

②プロセスにリソースが割り当てられてないない場合にのみプロセスがリソースを要求できるようにする

デメリット

リソース使用率が低い場合,Starvationの可能性がある

No Preemption

一部のリソースを保持しているプロセウスが、すぐに割り当てることができない別のリソースを要求すると、現在保持されている全てのリソースが解放される

横取りされたリソースは、プロセスが待機しているリソースリストに追加される

プロセスは、古いリソースとリクエストしている新しいリソースを取り戻すことができる場合のみ再起動される

Circular wait

全てのリソースタイプの全体的な順序付けを行い、各プロセスが列挙の昇順でリソースを要求することを要求する。

デッドロック回避

最も単純で有用なモデルは、各プロセスが必要とする各タイプのリソースの最大数を宣言することです。

デットロック回避アルゴリズムは、リソース割り当て状態を動的に調べて、Circular-waitが発生しないようにする。

リソース割り当ての状態は、使用可能なリソースと割り当てられたリソースの数、およびプロセスの最大需要によって定義される。

Safe State, Unsafe State, Deadlock State

safe state

デットロックは起きない

プロセスが利用可能なリソースを要求するとき、システムは即時割り当てがシステムを安全な状態なままにするかどうかお決定する必要があります。

システム内の全てのプロセスのシーケンス P_1, P_2, ... ,P_nが存在する場合システムはSafe stateにあり、各P_iについてP_iがまだ要求できるリソースは、現在利用可能なリソースかつP_j  j<I

つまり、

unsafe state

デットロックの可能性がある

deadlock state

 

回避のアルゴリズム

Resource allocation graph

リソースタイプが一つのインスタンスの時に使用する

アルゴリズム

プロセスP_iがリソースR_jを要求する時を考える。

要求は、要求エッジを割り当てエッジに交換しても、リソース割り当てグラフにサイクルが形成されない場合にのみ許可できる。

Assignment edgeからclaim edgeにすることによりサイクルをなくす

Banker’s  algorithm

リソースタイプが複数のインスタンスの時に使用する。

アルゴリズム

各プロセスはリソースの最大使用量を要求することにより回避する

Available
m次元のベクトル。available[j]=kは、リソースタイプがR_jのインスタンスがk個ある。

Max
n×mの行列。 max[i, j]=kは、P_iがリソースタイプR_jのインスタンスがk個要求する

Allocation
n×mの行列。allocation[i, j]=kは、プロセスP_iが持っているリソースタイプR_jのインスタンスk個

Need
n×mの行列。need[i, j]=kは、プロセスP_iが実行できるようになるまで必要なリソースタイプR_jのインスタンスk個
need[i, j] = Max[i, j] – Allocation[i, j]

Banker’s algorithmの例

Safety Algorithm

Banker’s algorithmにおいてシステムが安全な状態にあるかそうでないかを確かめる方法

ステップ1
Work  = Available Finish[I] = false  (0 \leq i \leq n-1)

ステップ2
次の両方が満たされるものを探し、見つかったらスッテプ3に見つからない場合はステップ4に移動する
Finish[I] = false Need \leq Work(Available)

ステップ3
次を実行したのちステップ2に移動する
Work = work + Allocation Finish[I] = true

ステップ4
検証終了をする。
もし、Finish[I] == true (0 \leq i \leq n-1)の時は安全なシステムになる。

safe stateの例

total resources:12

process holding max claims
A 4 6
B 4 11
C 2 7

safe sequence: A, C, B

unsafe stateの例

total resources:12

process holding max claims
A 4 6
B 4 11
C 2 9

safe sequenceは存在しない

Resource-Request algorithm for process P_i

Request_iP_iのRequestの要求ベクトル。Request_i[j] = kは、プロセスP_iが要求しているk個のリソースでリソースタイプがR_j

ステップ1
Request_i \leq Need_iだったらステップ2へ移動する
そうでない場合は、プロセスが最大の主張を超えているためにエラー状態

ステップ2
Request_i \leq Availableだったらステップ3へ移動する
そうでない場合は、リソースが利用できないのでP_iは待たなければならない

ステップ3
次のように状態を変更して要求されたリソースをP_iに割り当てるふりをする
Available = Available - Request_i Allocation_i = Allocation_i + Request_i Need_i = Need_i - Request_i

安全な場合は、リソースはP_iに割り当てられる
安全ではない場合は、P_iは待たなければならず、古いリソース割り当ての状態が復元される。

デットロック検出

全てのリソースタイプのインスタンスがひとつ

P_i -> P_j:P_iP_jを待っている。グラフ内のサイクルを検索するアルゴリズムを定期的に呼び出し、サイクルがある場合は、デットロックが存在する。グラフのサイクルを検出するアルゴリズムはO(n2) (nは頂点の数)

アルゴリズム

Available
m次元のベクトルで各タイプの利用可能なリソースの数

Allocation
n×mの行列で現在、各プロセスに割り当てられた各タイプのリソースの数を定義

Request
n×mの行列で、各プロセスの現在の要求を示している。Request[i][j] = kだったら、プロセスP_iが要求するk個のリソースタイプがR_jのリソース

ステップ1
以下のように初期化をする
Work = Available Allocation_i \neq 0のときFinish[I] = falseでそうでない時は、Finish[I] = true (1 \leq I \leq n)

ステップ2
両方を満たすインデックスiを探し、もしない場合はステップ4に移動する
Finish[I] == false Request_i \leq Work

ステップ3
以下を実行しステップ2へ移動する
Work = Work + Allocation_i Finish[I] = true

ステップ4
検出終了する。もし1\leqi\leq nにおいてFinish[i] == falseがある場合は、システムはデットロックの状態にある。さらに言えば、Finish[i] == falseの場合はP_iはデットロックされる。

wait-for graphの例

あげたい写真があるがあげることができなかったので、言葉で説明します。全てのリソースタイプのインスタンスが1つのリソースアロケーショングラフがある。そして、P1R_1のインスタンスをもっていて、P_2R_1のインスタンスを要求する場合wait-for graphは、 P_2 \rightarrow P_1になっている。そして、wait-forgraph にサイクルがある場合は、デットロックが生じている。

デッドロックからの回復

デットロックされたプロセスを全て停止する
→簡単な方法だが多くのコストがかかる

デットロックサイクルが取り除かれるまでプロセスを停止する
→オーバーヘッドが多い。なぜなら、それぞれのプロセスを停止した後にシステムがデットロックを起こしているかを決定するためにデットロックを探知するアルゴリズムを呼び出さないといけない。

プリエンプションが必要な場合3つの問題がある

Selecting a victim (最小化することが目的)

Rollback

安全な状態に戻り、その状態のプロセスを再起動します

Starvation

-同じプロセスが常に被害者として選択される可能性があり、コス ト要因にロールバックの数が含まれる