応用情報技術者過去問題平成23年秋期午後問2(プログラミング)

応用情報技術者過去問題平成23年秋期午後問2

問2　プログラミング

ハッシュ法と排他制御に関する次の記述を読んで，設問1～3に答えよ。

　T社は，ソフトウェア開発を行う会社である。現在，LAN環境で利用するクライアントサーバシステム(以下，本システムという)を開発中である。
　本システムは，クライアントPC上で画面にデータを表示する画面プログラムと，画面プログラムが使用するデータをサーバ上で管理するデータ管理プログラムから構成される。

〔データ構造〕
　配列 array は，クライアントPCで使用するデータ info を格納する配列であり，配列の添え字は1～Nである。info のデータ型は構造体 INFO である。表1に構造体 INFO のメンバーを示す。構造体メンバーの初期値は，全て 0 (未使用を意味する)を設定する。

　ハッシュ関数 Hash(key) は，key を基にデータの格納位置を算出して，戻り値として戻す。格納位置は1～Nの整数となる。関数 Hash(key) が，異なる key から同じ格納位置を算出することを，シノニムの発生という。この影響で，格納位置の配列要素が既に使用されていて，データを格納できないことがある。この場合は，配列 array を格納位置の次から順次検索し，最初に見つかった未使用の配列要素にデータを格納する。配列 array の最後に到達しても未使用の配列要素がない場合には，配列 array の先頭に戻り，未使用の配列要素の検索を続ける。

〔データ管理プログラム〕
　図1のデータ格納関数 Set()，図2のデータ取得関数 Get()，図3のデータ削除関数 Delete() をデータ管理プログラムと呼ぶ。
　関数Get()は，データ取得に成功すると，取得したデータを引数 info に格納する。関数 Set() と関数 Get() は戻り値として格納位置を戻す。処理結果が正しくない場合は，戻り値として 0 を戻す。

〔画面プログラム〕
　ユーザは，画面プログラムを使用して，info の作成，検索，編集，削除を行う。
　画面プログラムから配列 array へのアクセスにはデータ管理プログラムを使用する。
　複数のクライアントPCから同時に配列 array にアクセスできるので，画面プログラムから配列 array へのアクセスには排他制御が必要である。そこで，バイナリセマフォの確保関数 Lock()，解放関数 Unlock() を使用した占有ロックを用いて排他制御を実現する。
　図4は画面プログラムの一部である。ユーザが画面から入力した key と data が配列 array 内に存在しない場合は，データを配列 array に格納している。

　コーディングを完了したプログラムのテストを実施したところ，次のような障害が発生した。
　①あるデータを削除すると，別のデータの取得に失敗した。削除するデータと取得できなくなるデータには関連があり，再現方法は容易に分かった。プログラムを修正して障害は解決した。
　②複数のクライアントPCから図4の画面プログラムの操作を同時に行った場合に，同じ key をもつデータが重複して配列 array に格納されてしまった。この障害は，再現頻度が低く，原因究明に時間が掛かった。この障害についてもプログラムを修正して障害は解決した。

設問1

図1及び図2中のア～エに入れる適切な字句を答えよ。

解答入力欄

ア：
イ：
ウ：
エ：

解答例・解答の要点

ア：countはNより小さい
イ：idxはNより大きい
ウ：Hash(key)
エ：array[idx].keyはkeyと等しくない

解説

〔アについて〕
データ格納関数 Set では、最初に変数 idx に info の格納位置を求めています。シノニムが発生していなければ、whileループ内の処理は1回も実行されずに初期値の idx が格納位置になりますが、シノニムが発生した場合には、whileループで idx を1ずつ増やしながら格納できる場所を探すことになります。

シノニムが発生し、array[idx] が使用済であるときには、array[idx].key に1以上999999999以下が設定されています。info を格納するためには、未使用の要素が見つかるまで順次探索することになりますから、要素が使用済である間繰り返すため、ループの継続条件として「array[idx].keyは1以上かつ array[idx].keyは999999999以下」という条件が設定されています。

ここで、仮に[ア]の継続条件がない場合を考えると、array の全ての要素が埋まっているときに、ループ処理が永遠に続いてしまうことに気付きます。array の全ての要素を探索しても未使用の要素が見つからなかった場合には、何周探索しても結果は同じですから、array を1周探索し終えたらループ処理を終了させなければなりません。

このために、関数 Set では変数 count を使用して、探索した要素数を保持しています。変数 count は使用済の要素に当たる度に1ずつプラスされていき、array の全要素を探索し終えたときには、count の値は array の要素数である N になっているはずです。count が N のときにはループを終了させることになりますから、逆にループを継続する条件としては「countがNより小さい」が適切であると判断できます。

∴ア＝countはNより小さい

〔イについて〕
空欄の条件を満たすときに idx に1を代入しているので、問題文の「配列 array の最後に到達しても未使用の配列要素がない場合には，配列 array の先頭に戻り…」という処理に対応していることがわかります。したがって、空欄には配列の最後まで探索しても、未使用の要素が見つからなかったときに真となる条件式が入ります。
図1の6行目では idx に1を加算しています。このとき idx の値が最後の添字である N を超えた場合には、配列の最後を超えたということなので、次にアクセスする添字を1に戻すことになります。したがって、[イ]には「idxはNより大きい」が当てはまります。

∴イ＝idxはNより大きい

〔ウについて〕
変数 idx に代入する処理であるため、データの格納位置を求める処理が入ると推測できます。データ取得関数 Get は配列 array 中から引数 key をもつ info を取得する関数であり、info の格納位置は key を引数にしてハッシュ関数 Hash を呼び出すことによって取得しますから、[ウ]には「Hash(key)」が当てはまります。

∴ウ＝Hash(key)

〔エについて〕
シノニムが発生したときにデータの格納位置を探すループ処理の継続条件が入ります。関数 Get では目的の key をもつ info が見つかればその info を取得し、そうでなければ見つかるまで順次探索を繰り返しますから、ループの終了条件は「array[idx].key と key が等しい」ことです。逆にループを継続する条件は「array[idx].keyはkeyと等しくない」ということになります。

∴エ＝array[idx].keyはkeyと等しくない

設問2

本文中の下線①の障害について，(1)，(2)に答えよ。

障害の原因を40字以内で述べよ。
データ管理プログラムの修正の組合せとして適切な文章を解答群の中から二つ選び，記号で答えよ。

解答群

関数 Delete()中の"array[idx].key←0"の 0 を－1 に変更する。
関数 Get()中のif文の条件"array[idx].key は key と等しい"を削除して，無条件にデータを取得する。
関数 Get()中のwhile文の条件"(array[idx].key は 1 以上)かつ(array[idx].key は 999999999 以下)"を"(array[idx].key は 0 以外)"に変更する。
関数 Set()中でオーバーフローを検出した場合は，配列 array を動的に拡張してデータを格納する。
関数 Set()中のif文の条件"countはNより小さい"を削除して，無条件にデータを格納する。
関数 Set()中のwhile文の条件"array[idx].key は 1 以上"を削除する。

解答入力欄

解答例・解答の要点

シノニムの発生を考慮せずに配列要素を削除するから (24文字)

解説

あるデータを削除する操作は、データ削除関数 Delete を使用するので、この関数と関数 Get の組合せにより何らかの問題が発生していると想像できます。

データを削除する場面では、関数 Delete は array[idx].key に0を代入し、未使用にすることで削除しています。しかし、このように削除すると、データ取得でシノニムが発生したデータの格納位置の探索を行う際に、データの取得失敗と判定されてしまいます。

例えば、以下のようにシノニムが発生した2つのデータが並んで格納されているとします。
このとき、前の要素（key=11）が関数 Delete により未使用にされたとします。
その後、後ろの要素（key=22）を関数 Get で取得しようとすると、whileループが1度も実行されないため初期値の idx を格納位置として使用してしまうことになります。その結果、array[idx].key が key と等しくならず、図2の16行目で"データの取得失敗"となってしまいます。これが不具合の詳細です。

障害の原因としては様々な答え方があると思いますが、模範解答に加え、
- シノニムを無視してデータを削除するから
- 関数Deleteの削除処理はシノニムの発生を考えていないから
などの解答が考えられるでしょう。

∴シノニムの発生を考慮せずに配列要素を削除するから
この障害の原因は、主に2箇所あります。

1つ目は、図3の4行目にあるデータの削除箇所です。
データの削除では、未使用を表す0を代入するのではなく、削除された要素であること示すために特別な数字（-1）を代入するようにします。
これは「ア」が当てはまります。

2つ目は、図2の4行目のシノニムの発生を考慮した探索を行う条件式です。
条件式を"(array[idx].key は 0 以外)"に変更することで、-1、1～999999999のときに探索を続けるようになります。これにより、シノニムが発生しているときでも目的のデータを見つけるまでwhileループを継続させることができます。
これは「ウ」が当てはまります。

よって、プログラムの修正に必要なのは「ア」と「ウ」の組合せです。どちらか一方だけの変更では、関数 Get のループ処理が継続するようにならないので、両方の変更が必要です。
- 正しい。
- if文の条件を無くすと key の一致判定がなくなり、削除された要素を取得してしまうため誤りです。
- 正しい。
- 障害の原因となっているのは、関数 Delete と関数 Get なので、関数 Set を変更する必要はありません。
- 「エ」と同じ理由で誤りです。
- 「エ」と同じ理由で誤りです。

設問3

本文中の下線②の障害について，原因を25字以内で述べよ。

解答入力欄

o：

解答例・解答の要点

o：データの取得後に排他制御を開始するから (19文字)

解説

配列 array の更新処理を同時に行った場合に不具合が発生しているので、排他制御に何らかの欠陥があると推察されます。

図4のプログラムを見ると、1行目でデータ取得を試みた後に、2行目で排他制御を行っています。これだと、複数のクライアントが同時に同じ key 値をもつデータを格納しようとした場合に、両者とも関数 Get から idx = 0（データ取得失敗＝データは未格納である）を受け取ることになります。その結果、関数 Set が2回実行され、同じ key のデータが重複して格納されてしまう不具合が起こります。

例えば、2人のクライアント（Aさん、Bさん）が次の順序で図4のプログラムを実行すると重複格納が起こります。

Aさんは、関数 Get を呼出し、idx に0が代入される
Bさんは、関数 Get を呼出し、idx に0が代入される
Aさんは、array を Lock する
idx = 0 なので、Aさんは、関数 Set を呼出し、array にデータを格納する
Aさんは、array を Unlock する
Bさんは、array を Lock する
idx = 0 なので、Bさんは、関数 Set を呼出し、array にデータを格納する
Bさんは、array を Unlock する

このように、array をロックする前に別のクライアントが関数 Get を呼出し、データは格納されていないと判断してしまうと、データが存在しているにもかかわらず同じ key のデータを重複して格納してしまうことになります。

したがって、障害の原因としては、「データの取得後に排他制御を開始するから」「排他制御の前にデータ取得を実行しているから」「データ取得時に排他制御が行われていないから」などの解答が適切となります。

∴データの取得後に排他制御を開始するから

平成23年秋期午後問題一覧

問1　問2　問3　問4　問5　問6　問7　問8　問9　問10　問11　問12　採点講評