3 ＜テスト設計＞マルチコア用プログラムを対象としたテストの勘所

シングルコア用プログラムをマルチコア用プログラムへ移植する際に、移植元のプログラムでは問題が発生しなかったにもかかわらず、移植先のプログラムで不具合が発生するケースがよくある。

これは、並列に処理するプログラムには、逐次的に処理するプログラムでは考えなくてよかった、特有の欠陥が潜んでいる可能性があるためである。そこでソフトウェアテストの分野では、並列処理のプログラムやシステムに対するテストの難しさの原因、およびテスト手法について、長らく議論されてきた。

本章では、マルチコア用プログラムに潜む欠陥として、並列処理プログラムに特有の「安全性の破壊」、「生存性の破壊」、「公平性の破壊」の三つについて説明する。

こうしたマルチコア用プログラムの欠陥を効率的に検出できる「バックツーバックテスト（back-to-back testing）」を紹介する。

  • 本章の対象読者
    • 知識・経験：レベル1（入門者）シングルコアの知識・開発経験のみ
    • プロセス ：実装、テスト
    • ドメイン ：組込み全般
    • キーワード：
      • ソフトウェアテスト、並列処理プログラム、競合、相互排除、排他制御、デッドロック、スタベーション、飢餓、ライブロック、バックツーバックテスト
  • 本章を読んで得られるもの
    • マルチコア用プログラムに特有の欠陥についての理解が深まる。
    • マルチコア用プログラムを対象としたテスト設計が行えるようになる。

3.1 マルチコア用プログラムとテスト

マルチコアプロセッサを使ったシステムの開発では、マルチコア用プログラムを対象としたテストが課題となっている。各プロセッサメーカがCPUの動作周波数を、これ以上飛躍的に向上させることは困難。一つのプロセッサチップに複数のCPUコアを内蔵するマルチコアへ向かっている。

マルチコアやマルチスレッドを用いることにより、ソフトウェア処理の並列性を高め、システム全体の処理性能を引き上げようという考え方。しかし、ソフトウェアが複数のCPUコアを効率的に利用できなければ、意味がなくなる可能性がある。並列コンピューティングに対応したプログラミングスキルが必要になる。

マルチコア用プログラム（並列処理プログラム）では、シングルコア用プログラム（逐次処理プログラム）では発生しない、並列処理特有の欠陥が発生してしまう。複数のプロセスが利用できる共有資源に対して、複数のプロセスからの同時アクセスにより、競合が発生する場合がある。

複数のプロセスの処理が共有資源にアクセスする時は、ロックなどを使った排他制御（相互排除）が必要である。排他制御とは、あるプロセスに資源を独占的に利用させている間、他のプロセスがその資源を利用できないようにすることによって、データの一貫性（整合性）を保つ処理のことである。

従来の逐次処理の欠陥の知識に加えて、並列処理特有の欠陥の知識を理解することが不可欠である。ただし、並列プログラミングで発生するバグを発見することは容易ではない。こうしたバグの多くが、プログラミング作業の終わりの段階で見つかることになる。

3.1.1 マルチコア用プログラムの事例

マルチコア用プログラムの動作確認は難しい。以下に、コンパクトデジカメの事例を紹介する。このシステムは二つのCPUコアを搭載している。

  • Core 0：キャプチャ処理（イメージセンサからベイヤ配列のRGBデータを取り込む）
  • Core 1：現像処理（RAWデータをJPEGデータに変換する）

これら二つのデータ処理を同時並行に実行する。

ユーザが次の被写体を素早く狙えるように、キャプチャ処理と現像処理を別々のCPUコアで実行する。画像データは共有メモリに格納されており、両方のCPUコアからアクセス可能である。CPUコア間の通信には、AMP（asynchronous multi-processing）対応のリアルタイムOSの機能を利用する。

しかし，最初の機種の開発では、多くのトラブルを経験した。

  • メモリ競合（排他制御）
  • キャッシュコヒーレンシにかかわる不具合

シングルコア用プログラム（逐次処理プログラム）では発生しない並列処理特有の欠陥が、マルチコア用プログラム（並列処理プログラム）で発生した。

3.1.2 並列プログラムのテスト

並列処理プログラムを対象としたソフトウェアテストの技術は、長年、研究されてきた。並列処理のプログラムやシステムに対するテストの難しさの原因、およびテスト手法については、1980年ころから議論。当時、「コンピュータシステムの処理性能向上のため、並列分散処理の時代が来る」と言われていた。

実際は、ハードウェアの発展、特にCPUの動作周波数の向上が著しかったため、並列処理が強く望まれる応用領域は限られていた。並列処理が持つ本質的な難しさやその原因については、このころから指摘されており、現在もそれほど変わっていない。

3.2 マルチコア用プログラム特有の欠陥

マルチコア用プログラム特有の欠陥は、以下の3種類に分類できる。

  • 安全性の破壊
    • 排他制御の失敗により、データの一貫性（整合性）が失われる欠陥
  • 生存性の破壊
    • 同期の失敗により、デッドロックと呼ばれる状態が発生する欠陥
  • 公平性の破壊
    • ある処理だけが不当に実行されないライブロック（スタベーション、飢餓）と呼ばれる状態が発生する欠陥

3.2.1 安全性の破壊

安全性の破壊とは、プロセス間で利用される共有資源の排他制御の失敗により、データの一貫性（整合性）が失われる欠陥である。

例えば、二つのプロセスで同じ変数の値（仮にx=0とする）を読み出し、一方のプロセスが1加え（x=x+1）、もう一方のプロセスが2加えて（x=x+2）から値を書き込んだとする。

この場合、値を同時に読み込んでしまうと、後に書き込んだ値だけが有効になるので、結果が一意に定まらない状況が生じる（x=1 or 2 or 3）。

並列処理が行われているプログラムのテストでは、同期が適切に制御されているかどうかを確認するため、さまざまなタイミングでデータの読み書きを行うテストが要求される。

ホテルの部屋、列車や飛行機の座席のオンライン予約などでも、この問題は起きる。

図 1: 安全性の破壊の例

3.2.2 生存性の破壊

生存性の破壊とは、プロセス間の同期の失敗によって、プロセスが永久に待ち状態となってしまうデッドロックと呼ばれる状態が発生する欠陥。

デッドロックの例としては、Dijkstraが提案した「哲学者の食事問題」が有名である。

  • 中央にスパゲティが盛られた円卓のまわりに5人の哲学者が座っている。
  • それぞれの前に皿が1枚置かれ、その皿の両側にフォークが1本置かれている。
  • 各哲学者から見ると、左右に1本ずつフォークが置かれているように見えるが、テーブル全体では5本しかフォークはない。
  • 哲学者は2本のフォークを使って食事をしなければならないとする。
図 2: 哲学者の食事問題

全員が1本ずつフォークを取ってしまうと、誰も永久に食事ができなくなってしまう。(デッドロックの状態)

図 3: 生存性の破壊の例

3.2.3 公平性の破壊

公平性の破壊とは、ある処理（プロセス）だけが不当に実行されないライブロック（スタベーション、飢餓）と呼ばれる状態が発生する欠陥。

ライブロックの例として、先ほどの「哲学者の食事問題」にルールを追加して考える。

  • 追加ルール
    • 一方のフォークを取った状態で、もう一方のフォークを5分間待った場合は、いったんフォークを置いて5分間待ってから、再度食事を試みる、という規則を設定する。

システムが異なった状態に変化していくので、デッドロックは回避できた。 しかし、もし5人の哲学者がまったく同時に食卓に着いたとしたら、いっせいに左のフォークを取って5分間右のフォークを待ち、左のフォークをいっせいに置いて5分間待つ、という状況が発生する。 この状態をライブロックと称し、このようにデッドロックを回避してもこの状態は回避できない場合がある。

図 4: 公平性破壊の例

3.3 マルチコア用プログラムを対象としたテスト設計

マルチコア用プログラムを対象としたテスト設計を行う際には、以下のことに気をつける。

  • 逐次処理でも発生する欠陥を見つける。
    • 従来のテスト設計技法の活用
    • 仕様ベース、構造ベース、経験ベースのテスト
  • 並列処理特有の欠陥を見つける。
    • 安全性の破壊、生存性の破壊、公平性の破壊
    • すべての実行列を考慮
    • 適切なロックを考慮
    • 適切な実行順序（タイミング）を考慮

3.3.1 バックツーバックテスト

3.3.1.1 バックツーバックテスト(B2Bテスト)の定義

「二つ以上の異なるコンポーネントまたはシステムに対して同じ入力で実行し、出力を比較する。その結果、相違がある場合はそれを分析する」。（ 参考文献5 ）

適用例として車載機器に対する機能安全規格（ISO 26262）では、モデルベース開発のユニットテストや統合テストでの検証方法として規定されている。

図 5: IPAモデルベースシステムズエンジニアリングとSysML

3.3.1.2 バックツーバックテストのマルチコア用プログラムへの適用ポイント

並列処理特有の欠陥の検出には、バックツーバックテスト(B2Bテスト)が有効。

あらかじめ実行したシングルコア用プログラムの出力と、マルチコア用プログラムの出力を比較することで、マルチコア化によりプログラムの機能性が損なわれていないことの検証に適用できる。

データの精度や時間応答性に対して、完全一致が求められるのか、一定の閾値範囲内での許容誤差を設けるのか、B2Bテスト前に事前検討が必要となる。

CPUクロックに依存した応答性など、ペリフェラル側の挙動にも影響するかどうか検討した上で、B2Bテストの環境を構築する必要がある。

図 6: バックツーバックテストのマルチコア用プログラムへの適用ポイント

3.3.2 タイミングを考慮したテスト

マルチコア用プログラムのテストでは、タイミング（適切な実行順序）の考慮が重要。 複数考えられる実行列のうち、たった一つだけをテストして終わってしまってはいけない。

  • 実行列の洗い出し
  • 実行列の強制実行

さまざまなタイミングでプログラムを実行させることにより、再現しにくい並列処理特有の、タイミング依存の欠陥を検出する。

例えば、Javaマルチスレッドのテストフレームワークとして提案されているConTestである。

3.4 まとめ

各プロセッサメーカは、一つのプロセッサチップに複数のCPUコアを内蔵するマルチコアに向かっており、その性能を引き出すため、マルチコア用プログラムの開発が必要になっている。

高品質なマルチコア用プログラムを開発するためには、マルチコアの特性を考慮したテストが重要になる。十分なテストを実施するためには、マルチコア特有の欠陥を理解していないといけない。

  • 安全性の破壊
  • 生存性の破壊
  • 公平性の破壊

マルチコア用プログラムを対象としたテスト設計を実施しよう！

従来のシングルコア用プログラムで起こる欠陥も忘れずに…。

  • バックツーバックテスト
  • タイミングを考慮したテスト

3.5 参考文献

  1. 古川 善吾、伊東 栄典、片山 徹郎；「並行処理プログラムの試験」、情報処理、Vol.39、No.1、pp.7-12 （1998年）．
  2. M. Ben-Ari；Principles of Concurrent Programming, Prentice Hall, 1982.
  3. R.N. Taylor, D.L. Levine, and C. D. Kelly；“Structural Testing of Concurrent Programs”, IEEE Trans. Softw. Eng., Vol.18, No.3, pp.206-215 (1992).
  4. 片山 徹郎、菰田 敏行、古川 善吾、牛島 和夫；「並行処理プログラムにおけるテストケースの定義と生成ツールの試作」、情報処理学会論文誌、Vol.34、No.11、pp.2223-2232（1993年）.
  5. Japan Software Testing Qualifications Board (JSTQB)；「JSTQBソフトウェアテスト標準用語集 日本語版 Version 2.3.J02」,　http://jstqb.jp/dl/JSTQB-glossary.V2.3.J02.pdf（2019年2月12日アクセス）
  6. Japan Software Testing Qualifications Board (JSTQB)；「ISTQBテスト技術者資格制度Foundation Level シラバス 日本語版 Version 2011.J02」,　http://jstqb.jp/dl/JSTQB-SyllabusFoundation_Version2011.J02.pdf（2019年2月12日アクセス）
  7. 内海 武之、高木 智彦、八重樫 理人、古川 善吾；「back-to-backテストを実行するテストツールの実装と評価」、情報処理学会 第73回全国大会、Vol.1、pp.499-500（2011年）.
  8. IBM Developer；「ConTestを使用したマルチスレッド・ユニットのテスト」、https://www.ibm.com/developerworks/jp/java/library/j-contest/ （2019年2月12日アクセス）