基本情報技術者

【基本情報技術者試験】デッドロック

2022年2月15日

今回のテーマはデッドロックです。
デッドロック・・・発生させたら大問題のやつですね。

問題

2相ロッキングプロトコルに従ってロックを獲得するトランザクションA,Bを図のように同時実行した場合に,デッドロックが発生しないデータ処理順序はどれか。ここで,read と update の位置は,アプリケーションプログラムでの命令発行時点を表す。また,データWへの read は共有ロックを要求し,データX,Y,Zへの update は各データへの専有ロックを要求する。

基本情報技術者令和元年秋期 午前問29の図

read Wupdate Yupdate Xupdate Z
read Wupdate Yupdate Zupdate X
update Xread Wupdate Yupdate Z
update Yupdate Zupdate Xread W

基本情報技術者令和元年秋期 午前問29 ※図は過去問を参考に作成したものです。

基本情報技術者試験や応用情報技術者試験で出題されるデッドロックの問題。システム開発の現場でもよく耳にする言葉であり、エンジニアであれば知っておきたい知識です。

本記事では、デッドロックについて図解で分かりやすく解説しています。

本記事で学べること

  • 排他制御ロックについて理解する
  • デッドロックについて理解する
  • 基本情報技術者試験の過去問の解き方を学ぶ

排他制御とロック

排他制御とは

排他制御とは、共有資源を複数のタスク(プログラム)が同時に操作しても問題なく動作できる仕組みのことです。

例えば、次の図のように共有資源に対して「+1」を加算するプログラムAとプログラムBがあるとします。

排他制御をしていない場合

本来であれば、共有資源の値が「10」でその値に対してプログラムAとプログラムBが1ずつ加算するので「12」になるはずです。

しかし、上記図では「プログラムA」と「プログラムB」が同時に共有の領域にアクセスしたため、どちらも領域から取得した「10」という値をもとに計算した結果、「12」ではなく「11」になっています。

スポンサーリンク

このように排他制御をしていないと、整合性の保たれないデータになってしまう可能性があります。

このような事態を防ぐために、共有資源に書き込みを行うときは共有資源をロックし、他タスク(プログラム)の操作を禁止するなどの制御を行います。このような制御のことを排他制御といいます。

排他制御の代表的な手法の1つとしてロックがあり、ロックには「共有ロック」と「占有ロック」があります。

共有ロックとは

共有ロックとは、対象データをロックしている間、他のタスク(プログラム)はそのデータを読み込むことはできるが、書き込むことができないロックのことです。

共有ロック

占有ロックとは

占有ロックとは、データがロックされている間、他のタスク(プログラム)はそのデータを読み込むことも書き込むこともできないロックのことです。

占有ロック

デッドロック

ロックを使用する場合、注意しなければいけないことがあります。それが「デッドロック」です。

デッドロックとは、お互いがロック解除待ち状態となり、処理が止まってしまう現象のことです。

ロックの流れ

資源をロックするときは、次のような流れでロックします。

デッドロック通常時
  1. 資源Aのデータをロックする
  2. タスクAの処理(資源Aのデータを更新するなど)
  3. タスクAの処理が終わったので、ロックを解除する

デッドロックの流れ

それでは、具体的にデッドロックがどのような流れで発生するか説明していきます。

今回の例では、次の2つのタスク(プログラム)を同時に実行しています。

  • タスクAの処理:「資源A」を更新してから「資源B」を更新する
  • タスクBの処理:「資源B」を更新してから「資源A」を更新する

[手順1] 更新対象データをロックする

共有資源に対して更新処理を行うため、まずは占有ロックを取得します。

  • タスクA:資源Aの占有ロックを取得する
  • タスクB:資源Bの占有ロックを取得する
デッドロックの手順1

[手順2] 占有ロックを取得したデータに対して更新処理を行う

占有ロックを取得したデータを更新します。

  • タスクA:資源Aを更新する
  • タスクB:資源Bを更新する
デッドロックの手順2

[手順3] タスクAがロック解除待ちで待機状態になる

タスクAは資源Bを更新するため、資源Bの占有ロックを取得します。しかし、資源Bは既にタスクBが占有ロックをかけているので、資源Bの占有ロックが解除されるまで待機します。

デッドロックの手順3

[手順4] タスクBがロック解除待ちで待機状態になる

タスクBは資源Aを更新するため、資源Aの占有ロックを取得します。しかし、資源Aは既にタスクAが占有ロックをかけているので、資源Aの占有ロックが解除されるまで待機します。

デッドロックのイメージ図

上記の結果「タスクA」と「タスクB」は、どちらも待機状態となり身動きが取れなくなっています。(タスクA、タスクBともに処理がとまってしまう)この現象がデッドロックです。

基本情報技術者試験 過去問の解説

スポンサーリンク

基本情報技術者令和元年秋期 午前問29

問題

2相ロッキングプロトコルに従ってロックを獲得するトランザクションA,Bを図のように同時実行した場合に,デッドロックが発生しないデータ処理順序はどれか。ここで,read と update の位置は,アプリケーションプログラムでの命令発行時点を表す。また,データWへの read は共有ロックを要求し,データX,Y,Zへの update は各データへの専有ロックを要求する。

基本情報技術者令和元年秋期 午前問29の図

read Wupdate Yupdate Xupdate Z
read Wupdate Yupdate Zupdate X
update Xread Wupdate Yupdate Z
update Yupdate Zupdate Xread W

基本情報技術者令和元年秋期 午前問29 ※図は過去問を参考に作成したものです。

設問に書かれているreadは共有ロック、 updateは専有ロックをあらわしています。

共有ロック または 専有ロック中に新たなロックを取得できるかどうかは次の表のとおりです。

共有ロック占有ロック
共有ロック中×
占有ロック中××

それでは、解答のア~エの動きを順番に確認していきます。

解答ア 不正解:デッドロックが発生する

基本情報技術者令和元年秋期 午前問29 解答ア
  1. AがデータWを共有ロックする
  2. BがデータWを共有ロックする
  3. AがデータXを占有ロックする
  4. BがデータYを占有ロックする
  5. AがデータYに占有ロックを要求するも、Bが占有ロック中なのでロックが解除されるまで待機
  6. BがデータXに占有ロックを要求するも、Aが占有ロック中なのでロックが解除されるまで待機

AとBがお互いロック解除待ちで待機状態となりデッドロック発生

解答イ 不正解:デッドロックが発生する

基本情報技術者令和元年秋期 午前問29 解答イ
  1. AがデータWを共有ロックする
  2. BがデータWを共有ロックする
  3. AがデータXを占有ロックする
  4. BがデータYを占有ロックする
  5. AがデータYに占有ロックを要求するも、Bが占有ロック中なのでロックが解除されるまで待機
  6. BがデータZを占有ロックする
  7. BがデータXに占有ロックを要求するも、Aが占有ロック中なのでロックが解除されるまで待機

AとBがお互いロック解除待ちで待機状態となりデッドロック発生

解答ウ 正解:デッドロックは発生しない

基本情報技術者令和元年秋期 午前問29 解答ウ
  1. AがデータWを共有ロックする
  2. BがデータXを占有ロックする
  3. AがデータXに占有ロックを要求するも、Bが占有ロック中なのでロックが解除されるまで待機
  4. BがデータWを共有ロックする
  5. BがデータYを占有ロックする
  6. BがデータZを占有ロックする
  7. Bの処理終了。ロックを解除する
  8. AがデータXを占有ロックする(データXのロックが解除されたので、待機していた処理が動き出す)
  9. AがデータYを占有ロックする
  10. AがデータZを占有ロックする
  11. Aの処理終了。ロックを解除する

デッドロックは発生せず、AとBは処理終了

解答エ 不正解:デッドロックが発生する

基本情報技術者令和元年秋期 午前問29 解答エ
  1. AがデータWを共有ロックする
  2. BがデータYを占有ロックする
  3. AがデータXを占有ロックする
  4. BがデータZを占有ロックする
  5. AがデータYに占有ロックを要求するも、Bが占有ロック中なのでロックが解除されるまで待機
  6. BがデータXに占有ロックを要求するも、Aが占有ロック中なのでロックが解除されるまで待機

AとBがお互いロック解除待ちで待機状態となりデッドロック発生

デッドロックが発生しなかったのは「ウ」だけです。結果「ウ」が正解です。

helpful