软件工程师面试中最常见的 5 道并发编程问题

并发术语：定义关键术语

并发编程的最佳实践

1）读写锁

2. 用餐哲学家

3. Uber乘车问题

4. 异步到同步问题

5. 理发店问题

实践你的并发技能

（背景介绍：我曾面试过数百名Facebook和微软的软件工程师候选人。我自己也因为准备不足而多次编程面试失败。）

并发和多线程是面试中经常被问到的一些高阶主题，但扎实的基础可以让求职者在众多竞争者中脱颖而出。简而言之，这些技能对软件工程师来说是极大的加分项。它们能让面试官了解以下几点：

• 候选人是否具备构建高效项目的能力
• 候选人是否具备有效利用资源的能力
• 候选人是否展现出专业知识和技术深度

如果您正在寻找完整的并发编程面试课程，硅谷资深人士兼并发编程专家CH Afzal创建了Python、Java、C#和Ruby课程。

并发编程面试对于想要成为一名成功的软件工程师至关重要，但很多工程师却对并发编程面试题感到恐惧（包括我面试时也是如此！）。这主要有几个原因：

• 并发是一个非常复杂的话题，很多初级开发人员甚至高级开发人员都没有机会实现并发程序。
• 抽象概念的数量可能会令人困惑。选择合适的抽象概念并非易事。
• 封装、关注点分离、松耦合等重要原则都适用。
• 入门级多线程教材中教授的大部分内容在技术上都是正确的，但并不能解决当前的问题。

好消息是，在Educative，我们已经与数百名候选人进行了交流，并与曾在微软、Netflix、Cloudera 和 Oracle 等世界顶级科技公司进行过面试的 CH Afzal 合作，详细探讨了一些最常见的面试问题。

除了涵盖一些顶级公司最常问的并发面试题之外，我还会提供一些关键术语的定义、并发最佳实践、解决问题的技巧以及开发人员在解决这些问题时面临的常见陷阱。

并发术语：定义关键术语

线

线程是进程中最小的执行单元，它按顺序执行指令。一个进程可以运行多个线程。通常，进程会有一些所有线程共享的状态，而每个线程也拥有一些私有状态。进程中所有线程共享的全局状态是可见且可访问的，因此，当任何线程尝试读取或写入此全局状态时，都需要格外小心。

关键部分

临界区是指任何可能被应用程序的多个线程并发执行的代码片段，它会暴露应用程序用于访问的任何共享数据或资源。

你可以把临界区想象成一座桥，它一次只能承载一辆车（即一个线程）。

互斥锁

互斥锁（Mutex）顾名思义，意味着互斥。它用于保护共享数据，例如链表、数组或任何基本数据类型。互斥锁只允许单个线程访问资源或临界区。

一旦某个线程获取了互斥锁，所有其他尝试获取同一互斥锁的线程都会被阻塞，直到第一个线程释放互斥锁为止。释放后，大多数实现会（基于一些启发式算法）随机选择一个等待的线程来获取互斥锁并继续执行任务。

此示例中的互斥锁被比作商店试衣间，一次只允许一位顾客（即一个试衣间里的一根线）进入。

信号

另一方面，信号量用于限制对一组资源的访问。可以将信号量想象成拥有数量有限的权限。如果一个信号量已经发放了所有权限，那么任何请求权限的新线程都会被阻塞，直到之前拥有权限的线程将权限返回给该信号量为止。

信号量也可用于线程间的通信。这是一个重要的区别，因为它允许线程协同完成任务。

这里的例子是苹果商店外排起的长队，上面写着每次只允许 50 位顾客进入店内。

--

并发编程的最佳实践

尽量减少可变数据的共享

出于两个原因，你应该尽量减少可变数据的共享：性能（想想阿姆达尔定律）和安全性。安全性主要体现在数据竞争上。数据竞争是指至少两个线程同时访问同一个共享变量，并且至少有一个线程试图修改该变量的情况。

如果你的程序存在数据竞争，它的行为将未定义。这意味着所有结果都有可能发生，因此，对程序进行推理毫无意义。

尽量减少等待时间

等待至少有两个缺点。首先，线程等待时无法执行任何操作，因此性能会下降。更糟糕的是：如果等待操作占用大量资源，底层 CPU 将会被完全占用。

优先选择不可变数据

发生数据竞争的前提条件是数据可变。如果数据不可变，则不会发生数据竞争。你只需要保证不可变数据以线程安全的方式初始化即可。

注意死锁（和活锁）

在开发依赖互斥锁和信号量来保护关键部分的应用程序时，您应该仔细检查您的代码，以确保没有潜在的死锁（或活锁）。

接下来，我将讲解一些我建议重点练习的问题。

要查看这些问题的详细解决方案，您可以查看我们的Python、Java、C#和Ruby并发课程。

1）读写锁

问题陈述

假设你有一个应用程序，其中有多个读者和一个写者。现在你需要设计一个锁，允许多个读者同时读取数据，但一次只能有一个写者写入数据。

解决问题的提示：

1. 定义类将要公开的 API。在本例中，您需要两个用于写入的 API 和两个用于读取的 API。它们分别是：

   • 获取读取锁
   • 释放读取锁
   • 获取写锁
   • 释放写锁

2. 仔细考虑你需要满足的每个用例。例如：在允许读取器进入临界区之前，我们需要确保没有正在写入的写入器。临界区内存在其他读取器是可以接受的，因为它们不会进行任何修改。在允许写入器进入临界区之前，我们需要确保临界区内既没有读取器也没有写入器。

首先，我们来看一下 Reader 的使用场景。您可以让多个 Reader 获取读取锁，为了跟踪所有 Reader，您需要一个计数器。每当一个 Reader 获取读取锁时，计数器就加一；每当一个 Reader 释放读取锁时，计数器就减一。

释放读锁很容易，但在获取读锁之前，你需要确保当前没有其他写入者正在写入数据。同样，你需要一个变量来跟踪是否有写入者正在写入。由于在任何给定时间点只能有一个写入者，你可以使用一个布尔变量来表示是否已获取写锁。

此外，您还需要一个条件变量，以便读者和写者在对方操作期间保持等待状态。您可以使用带有条件变量的互斥锁来保护代码中操作共享变量的部分。

常见陷阱

避免将互斥变量的获取和释放拆分到两个方法中。虽然这样做看似效率更高，因为写入线程在操作期间只需获取和释放一次条件变量，但这种方法的致命缺陷在于，如果写入线程在两次方法调用之间终止，整个系统就会陷入死锁。

读写锁问题的另一个常见陷阱是饥饿。如果一个写者到达时临界区内已有读者，它可能会一直排队等待，直到读者离开。只要在当前读者离开之前有新的读者到达，临界区内就始终至少有一个读者。为了避免这种情况，可以为读者添加互斥锁，并允许写者锁定它。

--

2. 用餐哲学家

问题陈述

想象一下，五位哲学家围坐在一张圆桌旁。他们只做两件事：一是思考，二是吃饭。然而，他们只有五把叉子。每位哲学家都需要用到左边的叉子和右边的叉子才能吃饭。

设计一个解决方案，使每位哲学家都有机会吃到自己的食物，而不会造成僵局。

解决问题的技巧

1. 思考一下循环等待的情况以及如何避免这种情况。

   • 你可以对条件变量施加排序，以帮助防止死锁。

2. 把每个岔路口想象成一种资源，岔路口两侧的两位哲学家都可以尝试获取它。直观上，我们可以用一个许可值为 1 的信号量来表示岔路口。然后，我们可以把每位哲学家想象成一根线，它试图获取左右两侧的岔路口。

3. 当一位哲学家想吃饭时，他需要左右两边各一把叉子。所以：

   • 哲学家A(0)需要4号和0号叉子
   • 哲学家B(1)需要叉子0和1
   • 哲学家C(2)需要叉子1和2
   • 哲学家D(3)需要2号和3号叉子。
   • 哲学家E(4)需要叉子3和4

4. 每个线程（哲学家）都需要告诉你它的 ID，然后你才能尝试锁定相应的分支。

常见陷阱

开发者常遇到的一个陷阱是循环等待，这是科夫曼条件中的四个条件之一。循环等待指的是两个或多个进程都在等待其他进程持有的资源。为了避免这种陷阱，你应该对条件变量施加顺序约束（例如，将叉子编号为 0 到 4），并让每个哲学家选择编号最小的叉子。

饥饿也是另一个常见的陷阱。想象一下，你试图让哲学家0挨饿。最初，2和4在桌旁，1和3饿着肚子。想象一下，2起身，1坐下；然后4起身，3坐下。现在你们处于初始位置的镜像。如果3起身，4坐下，然后1起身，2坐下，我们就回到了起点。我们可以无限重复这个循环，哲学家0就会挨饿。

--

3. Uber乘车问题

问题陈述

想象一下，在一场政治会议结束后，共和党人和民主党人都想离开会场，同时叫了优步。为了防止在车上发生冲突，优步的软件开发人员设计了一种算法：车上要么全是民主党人，要么全是共和党人，要么是两名民主党人和两名共和党人。其他任何组合都可能导致斗殴。

作为 Uber 开发人员，您的任务是将乘车请求者建模为线程。一旦出现合适的乘客组合，线程即可开始接单。每个线程seated()在被系统选中接单时都会调用相应的方法。当所有线程都就位后，四个线程中的任何一个都可以调用该方法drive()通知司机开始行程。

解决问题的技巧

1. 首先，将问题建模为一个类。你可以使用两个方法：一个由民主党人调用，另一个由共和党人调用，目的都是为了搭车回家。当他们中的任何一人搭上下一班车时，都会调用该seated()方法。

2. 为了组成允许的乘客组合，你需要统计请求乘车的民主党人和共和党人的数量。

   • 为此，您可以创建两个变量，并在锁/互斥锁内修改它们。在本题中，您可以使用 Mutex 类的对象来操作民主党和共和党的票数。

3. 如果你的第一个线程是民主党发起的，seatDemocrat()并且没有其他可用的参与者，那么应该将其置于等待状态，这可以通过信号灯来实现。你应该避免使用障碍物，因为无法确定未来的政党（例如民主党或共和党）。

4. 使用两个不同的信号量democratsWaiting。republicansWaiting这将确保你的第一个民主党线程能够lock()锁定互斥锁变量，发现没有其他请求者存在，释放锁对象，然后继续等待信号democratsWaiting量。

5. 想想民主党主题帖需要检查哪些使用场景：

   • 如果已经有 3 位民主党人在等候，那么我们就打democratsWaiting三次信号，让这四位民主党人一起乘坐下一班 Uber。
   • 如果有两个或两个以上的共和党线程在等待，并且至少有两个民主党线程（包括当前线程）在等待，那么当前的民主党线程可以向信号灯republicansWaiting发出两次信号，释放两个等待的共和党线程，并向democratsWaiting信号灯发出一次信号，释放另一个民主党线程。这四个线程将组成下一班列车，由两个共和党线程和两个民主党线程组成。
   • 如果上述两个条件不成立，则当前的民主党线程应该在信号量处等待democratsWaiting并释放互斥锁，以便其他线程现在可以进入临界区。

6. 关键在于理解，由于两种方法开头都存在锁定，所以每条线程都是依次进入关键部分的seatDemocrat()。seatRepublican()骑行过程中，两种类型的骑手是否平均分配，或者完全由一种类型的骑手组成，取决于线程进入关键部分的顺序。

常见陷阱

在这个问题中，可能会出现“饥饿”现象，这可能是由于调度错误导致只有民主党人或共和党人才能乘车造成的。为了避免这种情况，你应该统计所有已请求乘车的人数。然后，你可以使用两个不同的信号量来区分等待的共和党人和等待的民主党人，这样，当前正在等待的线程就可以发出正确的信号量来安排下一单优步行程。

--

4. 异步到同步问题

问题陈述

假设我们有一个AsyncExecutor类，它通过一个方法异步执行一些有用的任务execute()。此外，该方法接受一个函数对象作为回调函数，并在异步执行完成后被调用。异步工作是通过模拟实现的sleep。传入的回调函数会在异步处理完成后被调用，以便调用者执行任何所需的操作。

你的任务是在不改变原始类的情况下使执行同步（假设你得到的是二进制文件而不是源代码），以便主线程等待异步执行完成。

解决问题的技巧

1. 要求主线程阻塞直到异步执行完成，这暗示着需要使用某种通知/信号机制。

   • 乍一看，你可能会想使用信号量，但实际上，你可以使用条件变量和互斥锁对来实现相同的功能。

2. 由于您无法修改原始代码，您可以SynchronousExecutor从给定的AsyncExecutor类继承一个新类并重写该execute()方法。关键在于super()在重写的方法内部调用原始的异步实现。

常见陷阱

在这个问题中，共享资源可能对异步和同步代码段都变得无法使用。如果它们一直互相等待，等待循环永无止境，会发生什么？这类似于死锁。你可以通过设置一个信号机制来避免这种情况，该机制会通知主线程继续执行。

--

5. 理发店问题

问题陈述

一家理发店包括一个有n个椅子的等候室和一个理发椅。如果没有顾客，理发师就休息。如果有顾客进入理发店，但所有椅子都已坐满，则顾客离开。如果理发师正在忙碌，但还有空位，则顾客可以坐到空位上。如果理发师睡着了，顾客会叫醒理发师。请编写一个程序来协调理发师和顾客之间的互动。

解决问题的技巧

1. 首先，确定该问题的不同状态转换。我们来逐一分析：
   • 顾客进入商店，如果所有 N 个座位都已坐满，他就离开。这暗示着需要统计等候的顾客人数。
   • 如果N把椅子中有一把空着，顾客就可以坐下等待理发师叫号。这相当于使用信号灯，找到空椅子的顾客会在信号灯上等待，直到理发师叫号。
   • 如果顾客进入理发店，而理发师正在睡觉，则意味着店内没有其他顾客。刚刚进入的顾客线程会唤醒理发师线程。这听起来像是使用某种信号机制来唤醒理发师线程。

常见陷阱

这里常见的陷阱是程序陷入死锁。理发师和新来的顾客同时查看彼此的状态，因此会陷入死锁，因为在那一刻：

• 理发师见没人坐在椅子上，以为候客室空无一人，便睡着了。
• 顾客以为理发师很忙，所以没有试图叫醒理发师，只是耐心地等待理发师。

开发者可能遇到的另一个陷阱是资源饥饿。这是因为在某些解决方案中，无法保证顾客按到达顺序得到服务，因此他们会不断等待分配给其他进程的资源。可以使用队列来避免资源饥饿，顾客到达后会依次添加到队列中，这样理发师就可以按照先到先得的原则为他们服务。

--

实践你的并发技能

提高并发问题处理能力的唯一方法就是练习。

如果您正在寻找上述问题的详细答案，以及其他顶级并发面试题，包括男女通用浴室问题和线程安全单例，我强烈建议您查看我们的Python、Java、Ruby和C#并发面试课程。

另外，还可以试试AI模拟面试！

面试顺利！

延伸阅读：

• Java多线程和并发：破解高级面试题
• 多线程和并发基础知识
• Python 并发：理解 asyncio