2011年 秋期 応用情報技術者試験 問2

ハッシュ法と排他制御

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を戻す。

function Set(info)
    count ← 0
    idx ← Hash(info.key)
    while ((array[idx].key は 1 以上) かつ (array[idx].key は 999999999 以下)
           かつ (ア))
        count ← count + 1
        idx ← idx + 1
        if (イ)           // 配列の最後を検出
            idx ← 1                    // 配列の先頭に戻る
        endif
    endwhile
    if (count は N より小さい)
        array[idx] ← info              // info を格納
    else
        idx ← 0                        // オーバフロー発生
    endif
    return idx
endfunction

図1 データ格納関数Set()

function Get(key, info)
    count ← 0
    idx ← ウ
    while ((array[idx].key は 1 以上) かつ (array[idx].key は 999999999 以下)
           かつ (ア) かつ (エ))
        count ← count + 1
        idx ← idx + 1
        if (イ)           // 配列の最後を検出
            idx ← 1                    // 配列の先頭に戻る
        endif
    endwhile
    if (array[idx].key は key と等しい)
        info ← array[idx]              // データを info に格納
    else
        idx ← 0                        // データの取得失敗
    endif
    return idx
endfunction

図2 データ取得関数Get()

function Delete(key)
    idx ← Get(key, info)
    if (idx は 0 と等しくない)
        array[idx].key ← 0             // 配列要素を未使用に設定する
    endif
endfunction

図3 データ削除関数Delete()

画面プログラム

ユーザは、画面プログラムを使用して、infoの作成、検索、編集、削除を行う。

画面プログラムから配列arrayへのアクセスにはデータ管理プログラムを使用する。

複数のクライアントPCから同時に配列arrayにアクセスできるので、画面プログラムから配列arrayへのアクセスには排他制御が必要である。そこで、バイナリセマフォの確保関数Lock()、解放関数Unlock()を使用した占有ロックを用いて排他制御を実現する。

図4は画面プログラムの一部である。ユーザが画面から入力したkeyとdataが配列array内に存在しない場合は、データを配列arrayに格納している。

……  省略  ……
idx ← Get(key, info)             // データが配列array に格納済か確認
Lock()
if (idx は 0 と等しい)           // データ未格納の場合
    info.key ← key
    info.data ← data
    idx ← Set(info)              // データ格納
endif
Unlock()
……  省略  ……

図4 画面プログラムの一部

コーディングを完了したプログラムのテストを実施したところ、次のような障害が発生した。

①あるデータを削除すると、別のデータの取得に失敗した。削除するデータと取得できなくなるデータには関連があり、再現方法は容易に分かった。プログラムを修正して障害は解決した。

②複数のクライアントPCから図4の画面プログラムの操作を同時に行った場合に、同じkeyをもつデータが重複して配列arrayに格納されてしまった。この障害は、再現頻度が低く、原因究明に時間が掛かった。この障害についてもプログラムを修正して障害は解決した。