Concurrency 面试题

Concurrency 面试涵盖内容

Concurrency 面试题示例

• 解释进程和线程的区别。给出一个例子说明线程比多进程更好。
  好回答应覆盖

  • 进程是操作系统资源分配的最小单位，拥有独立地址空间；线程是CPU调度的最小单位，共享进程资源。
  • 进程间通信（IPC）开销大，线程间通过共享内存通信更高效。
  • 创建和销毁线程比进程更快，因为线程共享代码和数据段。
  • 上下文切换线程比进程代价低，因为线程共享地址空间，TLB刷新少。

  查看范例答案

  进程和线程都是并发执行的基本单位。进程拥有独立的地址空间、文件描述符等资源，而线程是进程内的执行流，共享进程的资源（如堆、全局变量）。多进程适合隔离性强、安全性要求高的场景，但创建开销大、通信复杂；多线程适合需要频繁数据共享和低延迟的场景。例如，Web服务器处理多个客户端请求时，使用线程池（每个请求一个线程）比创建新进程更高效，因为线程共享服务器状态，无需额外的进程间通信。

• 什么是竞态条件？用 Java/C++ 展示一个包含竞态条件的简单代码片段，并使用锁修复它。
  好回答应覆盖

  • 竞态条件是指多个线程同时访问共享数据，且最终结果依赖于执行顺序。
  • 经典示例：两个线程对共享计数器加1，不保护会导致丢失更新。
  • 使用互斥锁（如Java的synchronized或C++的std::mutex）可以保证原子性。
  • 锁会引入开销和潜在死锁，但能强制串行化访问。

  查看范例答案

  竞态条件是并发编程中的常见问题，当多个线程同时读写共享变量且至少有一个写操作时，结果依赖于指令执行的交错顺序。例如，两个线程分别执行count++，这实际上会分解为读取、加1、写入三步，如果交错执行，可能导致count只增加1而不是2。使用锁（如Java的synchronized块或C++的std::lock_guard）可以确保同一时刻只有一个线程执行临界区，从而避免竞态条件。但要注意锁的粒度和死锁风险。

  // 竞态条件示例
  public class RaceExample {
      private int count = 0;
  
      public void increment() {
          count++;  // 非原子操作
      }
  
      public int getCount() {
          return count;
      }
  
      public static void main(String[] args) throws InterruptedException {
          RaceExample example = new RaceExample();
          Thread t1 = new Thread(() -> { for (int i = 0; i < 1000; i++) example.increment(); });
          Thread t2 = new Thread(() -> { for (int i = 0; i < 1000; i++) example.increment(); });
          t1.start(); t2.start();
          t1.join(); t2.join();
          System.out.println(example.getCount());  // 可能小于2000
      }
  }
  
  // 使用锁修复
  public class SafeRaceExample {
      private int count = 0;
      private final Object lock = new Object();
  
      public void increment() {
          synchronized (lock) {
              count++;
          }
      }
  
      // 其他方法相同，结果总是2000
  }

• 使用条件变量在 C++ 或 Java 中实现一个线程安全的有界队列（阻塞队列）。
  好回答应覆盖

  • 有界阻塞队列需要线程安全，支持当队列满时生产者阻塞，队列空时消费者阻塞。
  • 使用互斥锁保护队列操作，条件变量用于通知等待线程。
  • C++中可用std::mutex和std::condition_variable；Java中可用ReentrantLock和Condition。
  • 需要注意虚假唤醒，条件变量在等待时应用循环检查条件。

  查看范例答案

  线程安全的有界队列常用于生产者-消费者模式。关键在于：当队列满时，生产者线程等待，消费者取出元素后通知生产者；当队列空时，消费者等待，生产者放入元素后通知消费者。使用互斥锁可保证队列操作的原子性，条件变量用于线程间通信。注意，等待条件变量时应使用while循环检查条件（如在C++中while (queue.size() == capacity) cv.wait(lock);），防止虚假唤醒。以下Java实现使用ReentrantLock和两个Condition。

  import java.util.LinkedList;
  import java.util.Queue;
  import java.util.concurrent.locks.Condition;
  import java.util.concurrent.locks.ReentrantLock;
  
  public class BoundedBlockingQueue<T> {
      private final Queue<T> queue = new LinkedList<>();
      private final int capacity;
      private final ReentrantLock lock = new ReentrantLock();
      private final Condition notFull = lock.newCondition();
      private final Condition notEmpty = lock.newCondition();
  
      public BoundedBlockingQueue(int capacity) {
          this.capacity = capacity;
      }
  
      public void put(T item) throws InterruptedException {
          lock.lock();
          try {
              while (queue.size() == capacity) {
                  notFull.await(); // 队列满，阻塞
              }
              queue.add(item);
              notEmpty.signal(); // 通知消费者
          } finally {
              lock.unlock();
          }
      }
  
      public T take() throws InterruptedException {
          lock.lock();
          try {
              while (queue.isEmpty()) {
                  notEmpty.await(); // 队列空，阻塞
              }
              T item = queue.poll();
              notFull.signal(); // 通知生产者
              return item;
          } finally {
              lock.unlock();
          }
      }
  
      public int size() {
          lock.lock();
          try {
              return queue.size();
          } finally {
              lock.unlock();
          }
      }
  }
  
  // 时间复杂度：put和take为O(1)，空间复杂度O(capacity)

• 如何以编程方式检测死锁？为死锁检测算法编写伪代码。
  好回答应覆盖

  • 死锁检测可通过有向图（资源分配图）判断是否存在循环等待。
  • 计算机系统可维护每个线程等待的资源以及每个资源被哪个线程持有。
  • 检测算法周期性地检查图是否有环，或者在线程请求资源时增量检查。
  • 如果检测到死锁，通常需要终止线程或回滚。

  查看范例答案

  死锁检测的常见方法是构建资源分配图（RAG），其中节点表示线程和资源类型，有向边从线程指向资源表示请求，从资源指向线程表示持有。然后检查图中是否存在环。如果存在环，则可能发生死锁（如果资源只有一个实例，环意味着死锁；如果有多个实例，需进一步分析）。伪代码如下：使用DFS或拓扑排序检测环，若发现环，则报告死锁。在实际系统中，检测可以周期性触发，或当线程请求资源时增量检查。

  // 死锁检测伪代码（资源分配图检测环）
  // 假设有线程集合T，资源类型集合R，每个资源类型有实例数量
  
  function detectDeadlock(T, allocation, request, available):
      // 使用银行家算法或资源分配图简化版
      // 使用深度优先搜索找环
      graph = buildGraph(T, allocation, request) // 构建图
      visited = set()
      recStack = set()
      for node in graph.allNodes():
          if dfs(node, visited, recStack):
              return true
      return false
  
  function dfs(node, visited, recStack):
      visited.add(node)
      recStack.add(node)
      for neighbor in node.neighbors:
          if neighbor not in visited:
              if dfs(neighbor, visited, recStack):
                  return true
          elseif neighbor in recStack:
              return true
      recStack.remove(node)
      return false
  
  // 时间复杂度O(V+E)，V节点数，E边数；空间O(V)

• 无锁编程中的 ABA 问题是什么？提供具体场景和解决方案。
  好回答应覆盖

  • ABA问题是CAS操作中，值从A变为B再变回A，CAS无法检测到变化，误认为未被修改。
  • 典型场景：无锁栈中，线程1比较栈顶A准备弹出，但线程2弹出A、压入B再压入A，线程1的CAS成功，但此时A的next可能已变，导致栈结构损坏。
  • 解决方案：使用带版本号/标记的原子引用（如AtomicStampedReference in Java），比较引用和版本号。
  • 双重检查或lock-free算法中使用指针标记。

  查看范例答案

  ABA问题是CAS操作中的一个隐患。例如，在一个无锁栈上，线程1读取栈顶为节点A（包含指向下一个节点的指针next），然后线程2弹出A并压入B再压入A'（A'是新的A节点但next不同），此时线程1的CAS比较栈顶仍然是A，但实际栈结构已变，CAS成功后指向旧的next导致错误。解决方案是使用带时间戳或版本号的原子引用，例如Java的AtomicStampedReference，将引用和版本号一起比较。或者使用double CAS（如ABA问题的硬件解决方案）。在C++中可以使用std::atomic<std::shared_ptr>或标签指针（pointer tagging）。

• 设计一个尊重 robots.txt 并使用线程池的并发网络爬虫。展示主要组件。
  好回答应覆盖

  • 并发爬虫需考虑抓取策略、URL去重、robots.txt规则限制。
  • 使用线程池控制并发级别；每个任务负责下载并解析页面。
  • 尊重robots.txt：在添加URL前检查其robots规则（可缓存）。
  • 主要组件：URL调度器、下载器线程池、解析器、URL过滤器（含robots检查）、存储。

  查看范例答案

  设计一个并发网络爬虫，需平衡效率和对目标服务器的礼貌。使用线程池（如Java的ExecutorService）管理固定数量的工作线程，每个线程从共享的URL队列中取出URL，先检查robots.txt缓存（避免重复请求），若允许则下载页面解析链接，过滤后添加回队列。URL队列需支持去重（如使用布隆过滤器或HashSet），并按照广度优先策略排序。robots.txt解析器负责读取和缓存每个站点的规则，线程安全地共享。主要组件包括：1) CrawlerManager - 控制爬虫生命周期；2) URLFrontier - 维护待抓取URL（带优先级）；3) Fetcher - 使用HttpClient下载；4) Parser - 提取链接和内容；5) URLFilter - 检查robots.txt和去重。

  import java.util.concurrent.*;
  import java.util.*;
  import java.net.*;
  
  public class ConcurrentCrawler {
      private final ExecutorService pool;
      private final Set<String> visited = ConcurrentHashMap.newKeySet();
      private final Map<String, RobotsRule> robotsCache = new ConcurrentHashMap<>();
      private final BlockingQueue<String> urlQueue = new LinkedBlockingQueue<>();
  
      public ConcurrentCrawler(int threadCount) {
          this.pool = Executors.newFixedThreadPool(threadCount);
      }
  
      public void start(String seedUrl) {
          urlQueue.add(seedUrl);
          for (int i = 0; i < Runtime.getRuntime().availableProcessors(); i++) {
              pool.submit(new CrawlTask());
          }
      }
  
      class CrawlTask implements Runnable {
          @Override
          public void run() {
              while (!Thread.interrupted()) {
                  try {
                      String url = urlQueue.take();
                      if (visited.add(url)) {
                          // 检查robots.txt
                          RobotsRule rule = getRobotsFor(url);
                          if (!rule.allows(url)) continue;
  
                          String content = download(url);
                          List<String> links = parseLinks(content, url);
                          for (String link : links) {
                              if (!visited.contains(link)) {
                                  urlQueue.add(link);
                              }
                          }
                          // 模拟处理延迟
                          System.out.println("Crawled: " + url);
                      }
                  } catch (InterruptedException e) {
                      break;
                  }
              }
          }
      }
  
      private RobotsRule getRobotsFor(String url) {
          try {
              URI uri = new URI(url);
              String host = uri.getHost();
              return robotsCache.computeIfAbsent(host, k -> {
                  return new RobotsRule(/* download and parse robots.txt */);
              });
          } catch (Exception e) { return new RobotsRule(); }
      }
  
      private String download(String url) { /* ... */ return ""; }
      private List<String> parseLinks(String content, String base) { /* ... */ return Collections.emptyList(); }
  
      public void shutdown() { pool.shutdownNow(); }
  
      static class RobotsRule {
          boolean allows(String url) { return true; } // 简化
      }
  }

• 解释 Java 内存模型：'volatile' 提供了什么保证？使用共享标志的示例。
  好回答应覆盖

  • Java内存模型规定了线程如何通过共享内存通信，以及重排序规则。
  • volatile保证可见性和禁止指令重排序（防止内存屏障两侧重排）。
  • 对volatile变量的读/写直接在主存中操作（或通过缓存一致性协议）。
  • 但volatile不保证原子性（如count++仍需要锁）。

  查看范例答案

  Java内存模型（JMM）定义了线程对共享变量的访问规则。volatile提供了可见性保证：一个线程对volatile变量的写操作对其他线程立即可见（通过happens-before关系）。此外，volatile禁止编译器和处理器对该变量的重排序（加内存屏障）。它常用于线程间标志位或状态指示。需要注意的是，volatile不能替代锁实现复合操作，例如count++需要原子性，仍需要加锁或使用AtomicInteger。一个典型例子是使用volatile boolean stop标志停止线程：主线程设置stop=true，工作线程读取stop检查，因为volatile保证可见性，所以能正确退出。

  public class VolatileExample {
      private volatile boolean stop = false;
  
      public void worker() {
          while (!stop) {
              // 工作循环
          }
          System.out.println("Worker stopped");
      }
  
      public void shutdown() {
          stop = true; // 写入 volatile，对其他线程立即可见
      }
  
      public static void main(String[] args) throws InterruptedException {
          VolatileExample example = new VolatileExample();
          Thread t = new Thread(example::worker);
          t.start();
          Thread.sleep(1000);
          example.shutdown(); // 设置标志，工作线程随后退出
          t.join();
      }
  }

• 如果有一个高争用的计数器，你会使用互斥锁、原子操作还是无锁方法？比较性能和权衡。
  好回答应覆盖

  • 互斥锁（mutex）实现简单，但高争用下会导致线程阻塞和上下文切换，性能下降。
  • 原子操作（如AtomicInteger）通过CAS无阻塞，争用较低时性能好，但高争用下CAS自旋消耗CPU。
  • 无锁方法（如LongAdder/StripedCounter）将计数分散到多个单元，减少争用。
  • 选择需根据场景：低争用用原子操作，高争用用无锁分片；如果延迟敏感且线程数少，也可考虑锁。

  查看范例答案

  对于高争用计数器，互斥锁是最简单的方案，但每次更新都需要内核态线程同步，导致上下文切换和缓存失效，性能差。原子操作（CAS）避免了阻塞，但在高争用下大量CAS失败导致自旋，浪费CPU。更优的无锁方法如Java的LongAdder（或类似StripedCounter）将计数器分片到多个Cell，每个线程更新自己的Cell，最后求和，显著降低了争用。在非常高的争用下，LongAdder性能比AtomicLong高一个数量级，但占用更多内存。如果线程数固定且较少，锁的简单性可能更佳。总体权衡：原子操作适合中等以下争用；无锁分片适合高争用；互斥锁只适合低并发或对延迟不敏感的场景。

如何准备

• 练习从头实现经典并发原语（互斥锁、信号量、条件变量）。
• 研究真实世界的 bug：死锁、活锁和优先级反转。知道如何通过线程转储进行诊断。
• 理解并发与并行的区别，以及何时使用每种方法。
• 学习无锁技术：CAS、事务内存和风险指针。
• 准备讨论在争用下的性能指标（吞吐量与延迟）。

常见问题