問題12：状態遷移テスト（1）OSスケジューラ（1スイッチカバレッジ）

問題 #12

以下の状態遷移図は、オペレーティングシステム（OS）の汎用スケジューラの振る舞いを記述したものです。

• 状態： Ready, Running, Blocked1, Blocked2, Blocked3
• 遷移（イベント）：
  • Ready → Run → Running
  • Running → Block → Blocked1
  • Blocked1 → Unblock → Ready
  • Blocked1 → Suspend → Blocked2
  • Blocked2 → Resume → Blocked1
  • Blocked2 → Release → Blocked3
  • Blocked3 → Resume → Ready
  • Ready → Suspend → Blocked3

テストは常に「Ready」状態で開始し、システムが「Ready」状態に戻ったときに終了すると想定します。つまり、テスト入力はシーケンス（“Ready”, イベント, 次の状態, …, イベント, “Ready”）で構成され、最初と最後の状態を除くすべての状態は “Ready” とは異なります。

1スイッチカバレッジ（1-switch coverage）を達成するために必要な最小のテスト数はいくつか？

• a) 2
• b) 3
• c) 4
• d) 5

---

正解

c) 4

---

解説

1スイッチカバレッジとは、連続する2つの遷移（遷移のペア）をすべて網羅する基準です。今回のモデルで網羅すべき「遷移のペア（1スイッチ）」は、以下の 9個 です。

1. Ready → Running → Blocked1
2. Running → Blocked1 → Ready
3. Running → Blocked1 → Blocked2
4. Blocked1 → Blocked2 → Blocked1
5. Blocked1 → Blocked2 → Blocked3
6. Blocked2 → Blocked1 → Ready
7. Blocked2 → Blocked1 → Blocked2
8. Blocked2 → Blocked3 → Ready
9. Ready → Blocked3 → Ready

「Readyで始まり、Readyで終わる（途中はReadyを通らない）」という制約の下で、これらのペアを網羅する最小のテストパスを構成すると、以下の 4つ になります。

• テスト1: Ready → Running → Blocked1 → Ready
  • 網羅：(1), (2)
• テスト2: Ready → Running → Blocked1 → Blocked2 → Blocked1 → Ready
  • 網羅：(1), (3), (4), (6)
• テスト3: Ready → Running → Blocked1 → Blocked2 → Blocked1 → Blocked2 → Blocked3 → Ready
  • 網羅：(1), (3), (4), (7), (5), (8)
• テスト4: Ready → Blocked3 → Ready
  • 網羅：(9)

これら4つのテストを実行することで、すべての1スイッチを網羅できます。

---

ポイント

状態遷移テストにおけるカバレッジの考え方は、実務でも非常に重要です。

1. 0スイッチカバレッジ: すべての遷移（矢印）を少なくとも1回通る。
2. 1スイッチカバレッジ: すべての「遷移のペア（2連続の矢印）」を少なくとも1回通る。

1スイッチカバレッジを求められる場合、単純な遷移（0スイッチ）では見つからない「特定の状態を経由した後に発生する不具合」を検出できる可能性が高まります。試験では、今回のように「開始と終了の状態」に制約がある場合が多いため、図を描いてルートをパズルのように組み立てるのが定石です。