像鸟一样思考，以获得更好的并行编程。

引言

编写并行应用程序很难，对吧？我的意思是，它一定很难，否则我们会随处看到并行程序。我们只会看到那些毫不费力地利用所有可用核心的流畅的并行应用程序。然而，多线程应用程序却成了例外，而不是规则。

似乎编写并行程序存在两个主要障碍：

• 学习你所选语言中可用的并行编程的构造和/或约定

• 可视化你的并行程序将如何运行

第一项看起来很明显：花一个下午的时间学习你所选编程语言中的并行特性，然后你就可以开始——并行程序就会从你的编译器中冒出来。但通常一个下午会变成几天，然后又变成更长的时间，因为你需要驯服你所选语言并行特性的含义、复杂性和后果。

第二项似乎简单到不值得一提。毕竟，开发新程序的第一步是可视化其主要组件以及它们将如何运行。但我们通常将新程序可视化为顺序代码组件，我们会在稍后（如果必须的话）“附加”一些并行功能。正是这种思维框架从一开始就将我们引向了错误的道路。

相反，我们需要像看待鸟儿一样看待程序。或者更确切地说，像看待鸟群一样。

背景

Avian Computing项目的启动方式是通过改进我们对并行编程的思考方式来提升并行编程。Avian Computing鼓励我们将并行程序可视化为鸟群，其中每只鸟（线程）独立且异步地运行，但它们作为一个鸟群协同工作以实现程序的目标。

我们都熟悉鸟类：它们孵化、四处飞翔寻找食物、产卵并孵化自己的幼鸟，然后死去。Avian Computing将这些基本的鸟类行为转化为一种编码框架，开发人员可以利用它来快速原型化工作的并行程序。构建这个工作原型所获得的深度知识和见解可以简化最终软件产品的开发。

Avian Computing的实现

Concurrency Explorer (ConcX) 是Avian Computing概念的一个免费开源实现，使用Java编写。ConcX为用户提供了一个GUI界面，可以在其中创建和配置新的“鸟”。一旦配置好，“鸟”就可以被启动，并在进度条上监控它们的活动。可以为配置好的“鸟”群保存为一个“flock”，以便随时重新加载和运行。

一旦孵化（启动），每只“鸟”（线程）都会遵循标准的生命周期；它寻找食物、消化找到的匹配食物、储存任何产生的食物，然后小睡一会儿。在配置的“耐力”时间限制内未能找到食物的“鸟”将因饥饿而死亡。活得太久的“鸟”将因年老而死亡。成功吃到足够食物达到可配置设定的“鸟”将会繁殖（复制自身）。这个标准的生命周期允许使用简单且自然的词汇来处理线程管理的复杂性，这些词汇在概念上几乎是直观理解的。

ConcX依赖于Linda协调语言，将对象放入和检索共享的虚拟关联内存中，这种内存称为元组空间。Linda于1986年由Sudhir Ahuja、David Gelernter和Nicholas Carriero创立。Linda是多个大型产品的基础，包括Sun的JavaSpaces、IBM的TSpaces等。

ConcX使用一种简化的Linda元组空间，称为TupleTree。通常，“鸟”会被配置成在TupleTree中吃和储存食物荚。例如，任何被配置成吃RedPod的“鸟”都可以吃RedPod，而其他“鸟”则会忽略它。消化完食物荚后，“鸟”会将处理过的对象作为另一种食物荚（例如BluePod）存回TupleTree，以便另一只“鸟”可以吃。

Linda（及其衍生品TupleTree）提供了一种安全、简单且健壮的消息传递机制。在ConcX中，TupleTree允许对象被共享，而用户代码无需进行特殊编码或考虑，因为TupleTree会同步（锁定或以其他方式提供对底层数据存储的独占访问）所有与数据存储交互的方法。

让TupleTree负责所有锁定，可以确保任何“鸟”接收到的食物荚（对象）都只由该“鸟”独占拥有，而不会在用户代码中充斥着锁定和互斥量等。这意味着任何接收到食物荚的“鸟”都可以自由地对该食物荚进行任何更改，而不会受到其他“鸟”的争用或干扰。在进行任何必要的更改后，该“鸟”可以将食物荚放回TupleTree，在那里不同种类的“鸟”会吃掉它并进行更改。

一种简单的鸟类并行思维示例

ConcX提供的Addx场景是一个简单的例子，说明了Avian Computing的概念如何产生更简单的并行代码。Addx场景的目标是处理一系列值，对每个值执行一系列数学运算，直到计算出最终值并保存。数学运算必须始终按相同的顺序执行。

在标准的顺序编码中，我们会设想一个循环，开始获取下一个值，执行第一个数学运算，然后是第二个数学运算，第三个数学运算，依此类推，直到计算出最终值，保存该值，然后循环重复。这看起来相对简单，并且会以可能的最快速度运行。其最大吞吐量将取决于执行单个线程的处理器速度。

为了更快地处理更多值，使用多个处理器是可取的，而这时就会变得棘手。通常的解决方案是创建一个线程池，每个线程执行上面描述的顺序代码。但这会使处理复杂化，因为并行代码必须确保输入值仅由一个线程处理，并且不跳过任何输入值，同时保证不会发生死锁和活锁。非常难以想象线程之间可能互相干扰的所有方式——在客户现场，常常会展示出新的、令人惊讶的故障模式。更不用说还要为每个运行环境（笔记本电脑与大型机等）提供多个预配置和编译好的应用程序版本。

Addx（Avian）解决方案是配置任意数量的鸟群，每只鸟只吃一种食物，只对该食物执行一项数学运算，然后将其作为另一种食物保存。通过正确配置吃的和储存的食物，可以确保数学运算的正确顺序。例如，Bird1吃Food1，对其进行数学运算，并将其保存为Food2。Bird2吃Food2，对其进行数学运算，并将其保存为Food3。Bird3吃Food3，依此类推。这也可以更简洁地表达为：

Food1-->Bird1-->Food2-->Bird2-->Food3-->Bird3. . . .Foodn-->Birdn。

下图的简化图说明了Avian的并行性。

• 在下面的生命周期1中，所有五只鸟几乎同时开始飞行，但只有Add1Bird找到了食物。它对该值执行操作，然后将其作为只有Add2Bird吃的食物类型放回TupleTree。
• 在生命周期2中，Add1Bird和Add2Bird都找到了食物，因此它们都执行了各自的操作，然后将它们的食物放回TupleTree。
• 在生命周期3中，Add1Bird、Add2Bird和Add3Bird都找到了它们的食物类型，处理它们，并将它们放回TupleTree。

在大约第五个生命周期循环（寻找食物、消化食物、储存食物、小睡）后，所有五只鸟都在同时从TupleTree中进食、处理它们的荚，并将更新后的荚存回树中。上面只画了5只鸟，但很容易想象将这个图放大到包含20只、50只或100只鸟，它们都将并发运行（飞行），都遵循相同简单自然的模式。就像真实的鸟一样，如果任何一只鸟寻找食物而没有找到，它就会等一会儿再试一次。

重要提示：这些鸟儿不像在这个简化图中所显示的那样同步运行。每只鸟都以自己的个体速度经历生命周期，因为每次小睡，它都会睡一段随机的时间（在可配置的范围内）。这意味着一只快速小睡的鸟会比一只长时间小睡的鸟更快地完成其生命周期。随着时间的推移，小睡时间往往会趋于平均，所以一开始快的鸟儿稍后会变慢。在现实生活中，可能需要3、10或15个周期后，Add5Bird（或其他任何鸟）才开始进食。

配置鸟

ConcX提供了GUI界面来添加、配置和启动“鸟”。GUI界面还在“鸟”飞行时提供实时的动态状态更新。下面的截图显示了运行Addx场景的五只“鸟”。屏幕右侧的进度条实时显示了每只“鸟”的个人成功情况。每只“鸟”的进度条越长，表示该“鸟”成功进食的次数越多。

由于每只“鸟”都有用户可选的食物类型，因此可以轻松地重新排列数学运算的执行顺序。只需更改它们选择的食物并重新运行。如果任何“鸟”配置不正确，它就找不到食物，其进度条也不会增长。

食物供应选项卡包含食物荚进度条，动态显示可用食物荚的数量，也是实时的。运行结束后，TupleTree选项卡会显示一个包含食物荚的时间戳列表，以及每个食物荚内容物的简要摘要，以及在每个食物荚上执行的事务以及由哪个“鸟”执行的。

上面描述的这些功能都已集成到Concurrency Explorer中，以便您能够交互式地探索和开发并行程序。一旦您理解了如何将程序分解成可以并行运行的子步骤，您就可以用您选择的编程语言来编写您的应用程序。

使用代码

Add3Bird的完整Java代码如下所示。它只有43行，其中近一半（19行）是注释或空白（要么是空白行，要么是用于视觉分隔的单个大括号）。Add3Bird唯一需要重写的方法是afterDigestion，它所做的只是给任何非空食物荚加3。找到食物荚并将其放回树中，这些都由BasicBird框架处理，从而为开发人员简化了工作。

public class <code>Add3Bird</code> extends BasicBird {
    /**
     * Overrides afterDigestion in BasicBird with the instructions on how to add
     * 3 to the value of the food that it ate. This bird expects the value being
     * summed to be kept in the pod’s desc instead of the pod’s seed kernel.
     * If mPod1 is non-null, it tries to add 3 to that one's desc. If mPod2 is non-null,
     * it tries to add 3 to that one’s desc.
     */
    @Override
    protected void afterDigestion(int eatResults) {
        int contentsValue;

        if(eatResults == PUT_BACK_1 || eatResults == PUT_BACK_FILE_1) {
            return;  //don't update the value
        }

        if (!mPod1.isEmpty()) {
            try {
                String localContents = mPod1.getDesc();
                contentsValue = Integer.parseInt(localContents);
            } catch (NumberFormatException nfe) {
                mPod1.addToPodHistory("Non-numeric value in contents");
                contentsValue = 0;
            }

            contentsValue += 3;
            mPod1.setDesc(Integer.toString(contentsValue));
        }

        if (!mPod2.isEmpty()) {
            try {
                String localContents = mPod2.getDesc();
                contentsValue = Integer.parseInt(localContents);
            } catch (NumberFormatException nfe) {
                mPod2.addToPodHistory("Non-numeric value in contents");
                contentsValue = 0;
            }

            contentsValue += 3;
            mPod2.setDesc(Integer.toString(contentsValue));
        }
    }

最重要的是，上面的代码中没有锁定、同步或互斥量，因为这一切都由TupleTree和ConcX框架处理。所有的多线程并行代码都在后台管理，因此用户可以专注于如何将主要任务分解成“鸟”可以原子地并行处理的、大小合适的块。

虽然上述任务可能显得过于简单，但它实际上只是更复杂场景的一个模板。例如，如果Add1Bird被替换成一个抓取10毫秒音频块的“鸟”，Add2Bird被替换成一个对其执行快速傅里叶变换的“鸟”，Add3Bird被替换成一个尝试将其输出与其他先前处理结果进行匹配的“鸟”，等等。如果第二只“鸟”跟不上第一只“鸟”，与其试图修改它以运行得更快（并可能引入错误），首选的Avian解决方案是只需添加第二只“鸟”的一个实例（或10个实例）。

或者，如果AddxBirds被替换成发票“鸟”，它们独立且并行地找到要开票的客户，找到其使用费用，找到其经常性费用，找到其账单地址，并将这些结果格式化成一张发票。通过将这些步骤分开并将中间结果存储在食物荚中，并行处理发票突然变得容易了。

关注点

Avian Computing的开发旨在鼓励用户基于固有并行模型（如鸟群）来可视化他们的并行程序。蜂群、鱼群或马群也可以作为模型，因为它们都包含多个独立且异步运行但又协同工作的参与者。

ConcX是为开发者/实验者而设计的。它是一个交互式环境，允许用户启动和停止各种组合和配置的“鸟”。“鸟”在飞行时都有一个进度条，会不断更新以显示其成功度以及它们的可用食物供应。飞行后，可以检查鸟群的结果以及每只“鸟”事件的时间戳历史记录。

Avian Computing的概念及其ConcX实现共同被设计为“训练轮”，以帮助我们单线程的思维方式思考和谈论并行程序。

要了解更多关于Avian Computing的基本概念以及为什么我们需要帮助来思考并行程序，请访问Avian Computing网站。如果您准备尝试一下，可以从Avian网站或SourceForge下载ConcX-2.x.zip（jar文件、lib文件和flock文件）。请务必同时下载“Getting Started with Avian Computing”用户指南，因为它包含了安装信息以及大约十几项并行场景，如并行计算Pi、哲学家就餐问题、理发店场景等。

历史

2018年1月17日：首次提交

2018年2月12日：取消代码样本注释