Concurrency 面接の質問

Concurrency 面接で問われる内容

Concurrency 面接の質問例

• プロセスとスレッドの違いを説明し、スレッディングがマルチプロセッシングより優れている例を挙げてください。
  良い回答が押さえる点

  • プロセスは独立したメモリ空間を持つ
  • スレッドは同じプロセス内でメモリを共有
  • スレッドのコンテキストスイッチは軽量
  • スレッド間の通信は共有メモリで高速
  • マルチスレッドはメモリを節約

  サンプル回答を見る

  プロセスは独立したアドレス空間とリソースを持ち、スレッドは同一プロセス内でメモリやファイルディスクリプタを共有します。スレッドの作成とコンテキストスイッチはプロセスよりも軽量であるため、多数の並行タスクを効率的に処理できます。例えば、Webサーバでは各リクエストをスレッドで処理することで、プロセスをフォークするよりもメモリ消費が少なく、高速な切り替えが可能です。また、スレッド間のデータ共有は共有メモリを介して行えるため、プロセス間通信（IPC）よりもオーバーヘッドが低いです。ただし、スレッドはメモリを共有するため、同期の問題に注意が必要です。

• 競合状態とは何ですか？それを含むJava/C++の簡単なコードスニペットを示し、ロックを使って修正してください。
  良い回答が押さえる点

  • 競合状態は複数スレッドが共有データに同時アクセスすることで発生
  • 非アトミックな操作が割り込まれるとデータ不整合が起きる
  • Javaのインクリメント i++ は非アトミック
  • ロックでクリティカルセクションを保護する

  サンプル回答を見る

  競合状態とは、複数のスレッドが共有データに同時にアクセスし、その結果がスレッドの実行順序によって予測不能になる現象です。例えば、カウンタをインクリメントする操作は読み取り、加算、書き込みの3ステップからなり、スレッド間で割り込まれると値が失われます。以下にJavaのコード例を示します。

  // 競合状態を含むコード
  class Counter {
      private int count = 0;
      public void increment() { count++; } // 非アトミック
      public int getCount() { return count; }
  }
  
  // 修正後：synchronizedでロック
  class SafeCounter {
      private int count = 0;
      public synchronized void increment() { count++; }
      public synchronized int getCount() { return count; }
  }

• 条件変数を使用して、C++またはJavaでスレッドセーフな境界キュー（ブロッキングキュー）を実装してください。
  良い回答が押さえる点

  • ブロッキングキューはスレッドセーフで、空の場合に取得をブロック、満杯の場合に追加をブロック
  • C++のstd::condition_variableとstd::mutexを使用
  • JavaのReentrantLockとConditionを使用
  • C++実装でunique_lockとwait/notify_oneを利用

  サンプル回答を見る

  条件変数を使ったスレッドセーフな境界キューをC++で実装します。内部でstd::mutexとstd::condition_variableを使用し、キューが空のときはdequeueが待機し、満杯のときはenqueueが待機します。

  #include <queue>
  #include <mutex>
  #include <condition_variable>
  
  template<typename T>
  class BoundedQueue {
      std::queue<T> q;
      size_t capacity;
      std::mutex mtx;
      std::condition_variable not_full, not_empty;
  public:
      BoundedQueue(size_t cap) : capacity(cap) {}
  
      void enqueue(T item) {
          std::unique_lock<std::mutex> lock(mtx);
          not_full.wait(lock, [this]() { return q.size() < capacity; });
          q.push(std::move(item));
          not_empty.notify_one();
      }
  
      T dequeue() {
          std::unique_lock<std::mutex> lock(mtx);
          not_empty.wait(lock, [this]() { return !q.empty(); });
          T item = std::move(q.front());
          q.pop();
          not_full.notify_one();
          return item;
      }
  };
  // 時間計算量: enqueue, dequeue とも O(1) (平均)
  // 空間計算量: O(capacity)

• プログラムでデッドロックを検出するにはどうすればよいですか？デッドロック検出アルゴリズムの擬似コードを書いてください。
  良い回答が押さえる点

  • デッドロックは複数スレッドが互いにリソースを待ち合う状態
  • 検出にはリソース割り当てグラフまたは待機グラフを使用
  • サイクル検出が必要
  • 擬似コードでは各スレッドとリソースをノードとしてサイクルを探索

  サンプル回答を見る

  デッドロック検出は、リソース割り当てグラフでサイクルを検出することで行います。各スレッドとリソースをノードとし、スレッドがリソースを保持している場合はエッジ、リソースを待っている場合は逆向きのエッジを引きます。サイクルが存在すればデッドロックです。以下に擬似コードを示します。

  // デッドロック検出アルゴリズムの擬似コード
  // 入力: 待機グラフ (各スレッドが待っているリソース)
  // 出力: デッドロックがあればTrue
  
  function detectDeadlock(threads, resources):
      graph = buildWaitForGraph(threads, resources)
      visited = set()
      stack = []
      
      for each node in graph.nodes:
          if node not in visited:
              if dfsCycle(node, visited, stack):
                  return True
      return False
  
  function dfsCycle(node, visited, stack):
      visited.add(node)
      stack.push(node)
      for neighbor in node.neighbors:
          if neighbor not in visited:
              if dfsCycle(neighbor, visited, stack):
                  return True
          else if neighbor in stack:
              return True  // サイクル発見
      stack.pop()
      return False

• ロックフリープログラミングにおけるABA問題とは何ですか？具体的なシナリオと解決策を提供してください。
  良い回答が押さえる点

  • ABA問題はCAS操作で値がA→B→Aと変化する場合に発生
  • CASは現在地を確認するが、中間の変更に気づかない
  • データ構造のポインタ操作でよく発生
  • 解決策はタグやバージョン番号を追加する

  サンプル回答を見る

  ABA問題は、Compare-And-Swap（CAS）を用いたロックフリープログラミングで、ある値がAからBに変わり、再びAに戻ったとき、CASが値を変更したと誤認識する問題です。例えば、スタックのpop操作で、スレッドが読み取ったheadポインタが、別のスレッドによって変更された後に元のアドレスに戻ると、CASが成功してしまい、データ破壊を引き起こします。解決策として、ポインタにバージョン番号やタグを付加し、CASで同時に比較することで、見かけ上の同一値を区別します。JavaではAtomicStampedReferenceがこれを提供します。

• robots.txtを尊重し、スレッドプールを使用する並行Webクローラを設計してください。主要なコンポーネントを示してください。
  良い回答が押さえる点

  • robots.txtのパース
  • スレッドプールでワーカースレッド管理
  • URLフロンティアをFIFOキューで管理
  • 重複URLの排除
  • HTTPリクエストの並行処理

  サンプル回答を見る

  並行Webクローラは、robots.txtを尊重し、スレッドプールを使用して効率的にページをダウンロードします。主要コンポーネントは、URLフロンティア（訪問すべきURLのキュー）、URLフィルター（robots.txtと重複排除）、HTTPダウンローダー（スレッドプールで実行）、パーサー（HTMLからリンク抽出）、およびリンク正規化器です。robots.txtのパースは最初にドメインごとに行い、許可されたパスのみをキューに追加します。スレッドプールはタスク数を制限し、リソースの使いすぎを防ぎます。

• Javaメモリモデルを説明してください：'volatile'が提供する保証は何ですか？共有フラグの例を使用してください。
  良い回答が押さえる点

  • Javaメモリモデルはスレッド間の可視性と順序を定義
  • volatileは読み書きの可視性を保証
  • volatileはアトミック性を保証しない
  • 共有フラグでスレッド停止に使用できる

  サンプル回答を見る

  Javaメモリモデル（JMM）は、スレッドが共有変数をどのように読み書きするかのルールを定めます。volatileは、変数への書き込みが他のスレッドに即座に可視になることを保証し、また、volatile変数へのアクセスがリオーダーされないことを保証します。ただし、複合操作（++など）のアトミック性は保証しません。共有フラグの例では、あるスレッドがフラグをtrueにセットすると、他のスレッドはその変更を直ちに確認できるため、ループの停止に使えます。

• 高競合のカウンターがある場合、ミューテックス、アトミック、ロックフリーアプローチのどれを使用しますか？パフォーマンスとトレードオフを比較してください。
  良い回答が押さえる点

  • ミューテックスはロック競合時にコンテキストスイッチが発生
  • アトミック操作はCASを使用し軽量
  • ロックフリーは複雑だが高競合で有利
  • アトミックは単純なカウンタに適する
  • ロックフリーはABA問題などに注意

  サンプル回答を見る

  高競合のカウンタでは、ミューテックスはスレッドがロックを待つ間にスリップするため、オーバーヘッドが大きくなります。アトミック操作（JavaのAtomicIntegerなど）はCASを使用し、競合が激しいとリトライが発生しますが、ミューテックスより軽量です。ロックフリーアプローチ（例: 分散カウンタ）は複雑ですが、競合を大幅に減らせます。一般に、単純なカウンタではアトミックが適切です。ミューテックスは競合が少ない場合や複雑なクリティカルセクションに使われ、ロックフリーは極めて高い性能が求められる特殊なケースです。

準備方法

• 古典的な並行性プリミティブ（ミューテックス、セマフォ、条件変数）をゼロから実装する練習をしましょう。
• 実際のバグ（デッドロック、ライブロック、優先順位の逆転）を研究し、スレッドダンプで診断する方法を知りましょう。
• 並行性と並列性の違いを理解し、それぞれを使用する場面を知りましょう。
• ロックフリーテクニック（CAS、トランザクショナルメモリ、ハザードポインター）を学びましょう。
• 競合下でのパフォーマンス指標（スループット vs レイテンシ）について議論できるように準備しましょう。

よくある質問