Apollo的博客

本文最初由Apollo发表于QQ空间：

很久都没有更新这个博客空间了，呵呵。

其实，或许是邮箱的原因噶，我已经把空间搬到了163去了。不过，似乎这里才是Apollo的博客的发源地。到百度输入 “Apollo的博客”第一个就是我的这个空间，呵呵。

其实，最近挺忙的，也没有什么空闲的时间去写博客了！~……

转自：http://www-128.ibm.com/developerworks/cn/java/j-csp3.html

2005 年 7 月 11 日

Abhijit Belapurkar 通过介绍 JCSP 开发高级主题，结束了由三部分组成的介绍适用于 Java 开发人员的 CSP 的系列文章，介绍的内容包括：JCSP 与 AOP 的相似性、JCSP 与 java.util.concurrent 的比较，以及用 JCSP 进行高级同步。

如果您从开始就一直阅读这个系列，那么到了现在，您应当同意 CSP 是一个值得研究的编程范式，而 JCSP 库则值得您添加到工具包中。在第 3 部分中，我只是给您提供了更多的研究 JCSP 理由。我将从讨论 CSP 的复合技术与面向方面编程（或 AOP） 的模块化技术之间的相似性开始。然后介绍 JCSP 的一些更高级的同步构造，并讨论适合应用它们的场景，还将更广泛地讨论使用 JCSP 进行多线程编程的好处，比如验证、维护以及可应用于分布式编程的一种方法。

我还要回答以下问题：如果已经采用了 java.util.concurrent 的并发性工具，那么是否还有学习 JCSP 的必要。（显然，我认为有这个必要！）

如果还没有阅读本文的 第 1 部分 和 第 2 部分，那么在继续我们的介绍之前，您可能需要这么做。

AOP 和 CSP

面向方面编程，即 AOP，是现在大多数 Java 开发人员都知道的一个术语。AOP 把系统当成方面或者关注点的的组合，而不是单纯地将系统看成是对象的组合。它试图通过把切入点组合成独立的模块，由模块代码解决一个特定关注，从而提高系统的模块性。这些模块可以用静态或动态编织技术编织在一起。

这个系列文章中已经介绍了很多内容，所以对您来说，应当很容易就可以看出 AOP 的概念 把模块编织在一起 与 CSP 的概念 组合进程网络 之间的相似性。两个技术之间的相似（绝对不是故意的！）主要是由于后者的复合性质。

一个基于安全性检测的示例被频繁地用作 AOP 的示例。在这个示例中，包含解决应用程序安全问题的代码的模块是以方面的形式编写和打包的；然后，这个方面将应用于整个应用程序中所有适当的业务对象。为了用 CSP 解决同样的问题，可以先从编写进程开始，编写一个包含业务对象的功能的进程，再编写另一个包含应用程序的安全性检测功能的进程。然后可以用 One2One 通道把两个进程连接起来。CSP 技术的优势与 AOP 技术类似：都可以将关注点分隔开。

不要错过本系列其余部分！ “适用于 Java 程序员的 CSP”是由三部分组成的介绍通信顺序进程（Communicating Sequential Processes —— CSP）的一个系列。CSP 是并发编程的一个范式，它承认了并发编程的复杂性，却没有把复杂性留给开发人员。请阅读本系列的其他部分： 第 2 部分：用 JCSP 进行并发编程 第 3 部分： JCSP 的高级主题

回页首

高级 JCSP 同步

通道不是进程间同步的惟一可用选择，也不总是最合适的选择。通道总是在以下两个进程间同步：阅读器和写入器。是否在运行多个阅读器/写入器并不重要，因为在 Any2One、One2Any 和 Any2Any 模型中，每种类型的进程都只有一个进程能够积极地参与到通道两边进行的会话中。

为了获得更高级的同步，即在多个进程之间的同步，JCSP 提供了 Barrier、Bucket 和 CREW 构造，还提供了一个叫作 ProcessManager 的类负责管理 CSProcess 实例。

回页首

Barrier 构造

barrier 是一个 JCSP 事件，可以充当多个进程之间的同步机制。每个 barrier 都能与多个进程相关联，任何在这个 barrier 上同步的进程都将被阻塞，直到其他进程已经同步为止。

必须用需要在 Barrier 类上同步的进程的数量来创建它，其中每个进程都运行在独立的线程中。在完成当前一轮工作之后，每个进程都调用 Barrier 实例的 sync() 方法，然后等候其他进程完成。

Barrier 内部

从内部来看，Barrier 包含一个成员变量，在创建 Barrier 对象时，这个成员变量被初始化为指定的进程总数。每当进程调用 sync() 方法时，这个变量就减一，并发出 wait() 调用。（您会想起已经介绍过的内容：Java 线程在能够调用 wait() 方法之前必须一直持有恰当的锁。在这里，由于将 Barrier 的 sync() 方法标记为同步的，所以 Barrier 实例本身充当着锁的作用。） 检测是在最后一个调用 sync() 的进程所在的线程上进行的。如果成员变量变成 0，则清楚地表明，所有进程已经完成了对 sync() 的调用 ，可以安全的发出 notifyAll() 了。这时，内部的计数器被重新设置回最初提供的进程总数，从而使得 Barrier 实例可以在下一轮同步中重复使用。

注意，Barrier 并没有把进程的身份和自身关联起来。所以，只有能得到 Barrier 对象，任何进程（除了要在 Barrier 上同步的进程之外）都能调用对象上的sync，从而将一个或多个合法进程排除在外。要想防止这个问题，可以对 Barrier 对象的可见性进行严格控制，只允许那些已经在 Barrier 上同步的进程集看到它。

似曾相识！

如果您认为 Barrier 工作方式的描述听起来很熟悉，那就对了。Parallel 构造自行控制运行多个 CSProcess 实例的基础就是 Barrier 构造的底层机制。

您会想起前面介绍过，在您调用 Parallel 实例上的 run 方法时，它创建了 (n-1) 个线程来运行前面 (n-1) 个 CSProcess 实例，然后在自己的线程中运行最后一个 CSProcess 实例。所有这些进程都在一个公共的 Barrier 实例上进行 sync，这个实例是在 Parallel 类的构造函数中创建的（而且通过负责运行 CSProcess 的每个 n-1 线程的构造函数，可以将实例传递给每个线程）。

Barrier 是一个比 Parallel 级别低的构造，因此，相应地也就带来了更多的复杂性，进程可以在任意时间从 Barrier 对象 enroll（登记）或 resign（退出）。例如，在一个工作进程运行时，它可能想与时钟同步（实际上是模拟时钟滴答） ，然后停下来休息一段时间（在此期间，它应当从 barrier 退出），接着再登记到 barrier，重新开始工作。

回页首

Bucket 构造

bucket 也是一个用于多进程的同步 barrier。bucket 构造和 barrier 构造之间的区别是：在前者中，所有进程都被阻塞，直到另外一个（外部）进程决定释放它们，而释放是通过“清空 bucket”进行的。

使用 Bucket 的方法只是创建一个 bucket 构造；然后，每个需要在该构造上面同步的进程都可以调用这个 bucket 的 fallInto() 方法。fallInto() 是一个同步的方法，它维护一个内部变量，用该变量来跟踪当前（等候）的进程数量（也就是说，每有一个调用 fallInto() 方法的进程，计数器变量就加 1。）在计数增加之后，调用进程执行 wait()，这导致调用进程受阻塞。当外部进程调用 Bucket 的（也是同步的） flush() 方法时，就发送一个 notifyAll() ，唤醒所有受阻塞的线程。阻塞进程的最后计数将从这个调用中输出。

Barrier 是确定性的，而 Bucket 是非确定性的。可以保证同步到 Barrier 的进程得到重新安排，从而得以执行（在一个时间周期后，受阻时间长短等于组中最慢的进程的执行时间），同步到 Bucket 的线程受阻塞的时间是不确定的，时间长短取决于清除进程何时决定发出释放这些进程的调用。

在必须按照先后顺序处理一组进程时，Barrier 很有用。这就是说，每个进行到步骤 n 的进程都不能进行步骤 n+1，直到同组中的其他所有进程都已经完成它们的步骤 n。在每个进程都要完成自己分配的任务并且停在 bucket 中，以表明自己可以进行下一步，这种情况下，Barrier 很有用。清除进程可以周期性地清除这个 bucket （可能用某些工作调度算法），从而释放目前在 bucket 中的所有进程，开始下一组任务。

回页首

CREW 构造

并发读/排它写（Concurrent-Read-Exclusive-Write）构造，即 CREW 锁，允许多个并行阅读器访问共享资源，条件是：（1）“读”访问不会修改资源；（2）之前没有写入器正在访问资源。当写入器正在访问资源时，它对资源拥有排它权限：不管是阅读器还是写入器，都不允许访问资源。

CREW 锁的使用是为了消除争用风险（因为竞争的阅读器/写入器进程之间任意的交叉），并且由于允许多个阅读器进程并行执行而提高了性能。是否真的会有性能提升则取决于以下因素：以读模式访问资源的频率与以写模式访问资源的频率的比较、读操作和写操作的时间，以及在同一时间在冲突模式下试图访问共享资源的进程数量。

请参阅 JCSP 发行版附带的 Javadoc（在 参考资料中），以获得 CREW 锁的内部实现的精彩描述。

回页首

管理 CSProcess 实例

在 第 2 部分 中，我介绍了如何用 Parallel 构造把较低级别的“构造块”进程组合成更高级别的进程网络。虽然对于许多编程场景，这些描述都是合适的，但在这篇文章的示例中，我假设已经知道了需要创建的所有进程的全部细节。但是对于某些应用程序来说，可能会发现有必要根据只能在运行时才能计算的某些条件，动态地创建一个或多个进程，而且还应当能够管理它们。

JCSP.net 我在本文示例中使用的 JCSP 库实际上使用的是同一 JVM 中运行的线程，当然，JVM 可能正运行在单处理器或多处理器机器上。倘若您对是否有可能组合对跨许多 JVM 的进程进行通信和同步的分层网络感到怀疑，那么答案是肯定的！JCSP 库的叫作 JCSP.net 的一个变体可以让您精确地做到这点。使用 JCSP.net 编程的最大好处是：跨物理网络运行的虚拟通道看起来差不多就像您在本文中已经遇到过的本地的、单一 JVM 的通道一样，虽然很显然会更复杂一些。请参阅 参考资料，学习关于 JCSP.net 可用的商业版本的更多内容。

JCSP 为这类场景提供了一个叫作 ProcessManager 的类。这个类接受 CSProcess 实例作为输入参数，允许用以下两种不同的方法之一启动进程。如果在ProcessManager 上调用 run() 方法，那么 ProcessManager 将启动托管的进程，然后等候进程终止（被管理的进程在 ProcessManager 的线程上运行，所以，后者的运行被阻挡，直到托管的进程完成为止）。另一个选项是调用 ProcessManager 上的 start() 方法，这使托管的进程在独立的线程中启动，在这种情况下，ProcessManager 自己仍然继续运行。

管理并行优先级

我在 第 2 部分 中提到：Parallel 构造并行地运行构造函数中传递给它的数组中包含的所有 CSProcess 实例。但是在某些情况下，可能必须要为这些进程赋予不同的优先级。JCSP 提供了一个叫作 PriParallel 的类，可以为传递给它的进程加上优先级。

受控制的进程的优先级是由进程在数组中的位置索引决定的。在数组中，放在前面的进程拥有更高的优先级。注意，JCSP 以底层线程的优先级机制实现进程的优先级；所以优先级实际的工作方式取决于底层的 JVM 实现。

回页首

越来越多的构造！

迄今为止讨论的构造（从第 2 部分开始到现在这里）都是 JCSP 库的核心构造。可以用它们来解决普通的和高级的并发性问题，现在应当可以让您开始编写所喜爱（也没有错误）的多线程程序了。当然，在 JCSP 库中，这些问题只是冰山之一角。请考虑以下有趣的构造的应用，您也可以自己对它们进行研究：

• BlackHoleChannel 实现 ChannelOutput 接口，包含一个空的 write() 方法。可以把任意数量的数据写入这个通道。如果想把现有进程用在不同的环境中，而 不 再使用某些输出，那么 BlackHoleChannel 类是最有用的。因为不能一直留着某个输出通道不处理（害怕造成死锁），所以最好的选择就是让进程在 BlackHoleChannel 的实例上产生输出，而 BlackHoleChannel 则有效地充当存放所生成数据的透明无底洞。
  
  
• Paraplex 是一个进程，它将其输入通道集上的多个对象流转化到单一输出通道。等到每个输入通道上都有一些可用输入之后（在输入到达的时候就接受，没有要求或规定特定的顺序），就可以将这些输入打包成数组（数据的尺寸与输入通道的数量相同），然后把数据通过输出通道发送为单一输出。如果需要用表格的形式表现某些数据，那么 Paraplex 可能会很方便。例如，假设有一个三列的表，每列均用数字填充。前两列用前面已经介绍过的 JCSP 进程生成的数字填充：NumbersInt 为第一列生成从 0 开始的自然数序列，SquaresInt 为第二列生成对应的平方序列。一个即插即用的叫作 FibonacciInt 的 JCSP 进程（随 JCSP 库一道立即可用）可以用来为第三列生成斐波纳契数系列。
  
  可以容易地用一个组合了三个输入通道的 ParaplexInt 实例来处理这三个列。每个输入通道都要附着在前面提到过的三个进程中的一个的实例上。然后，ParaplexInt 的单一输出通道向 CSProcess 传送数据，后者则接着读取带有三个元素的数组，并在适当的格式化表格中输出它们。
  
  
• Deparaplex 是一个类，它和 Paraplex 类相反， 它把数据从单一输入通道 分离 到一组输出通道。所以，Deparaplex 类可能读取一个数组对象（尺寸为 n），把数组中的每个元素逐个输出到它的 n 个输出通道上。然后，Deparaplex 进程会一直等候，直到它生成的每个元素都被写入的通道接受为止。

请参阅 JCSP 库的下载 （在 参考资料 中），以获得这结构造的更多文档，包括用例。

回页首

CSP 的好处

CSP 是基于成熟的数学理论的并发编程范式。因此，CSP 提供了丰富的设计模式和工具集，可以防范常见的多线程缺陷，例如争用风险、死锁、活动锁和资源耗尽。因为所有这些数学上的完善性都构建到了 JCSP 库中，所以可以直接用它根据规定好的指导原则来编写应用程序。 （也就是说，不必非得理解理论才能利用它；虽然清楚的了解会更有优势！）。因为存在正式的针对 Java 的 CSP 模型，所以可以分析并正式地验证用 JCSP 构造构建的任何多线程 Java 应用程序。

正如前面所指出的，AOP 的许多好处也适应于基于 CSP 的程序。基于 CSP 的程序的主要好处是关注点的分享。可以使用 CSP 作为程序的基础（例如通过 JCSP 库），还可以确保进程之间干净的解耦，因为它们只能通过通道进行交互，不能通过直接的方法调用进行交互。它还确保可以完美地把数据和应用程序逻辑封装在通道接口之后的进程之中。所有的副作用都被限制在进程的边界之内，编程实体之间的交互都是显式公开的。在基于 JCSP 的程序中，没有隐藏的互交 —— 在网络的每一级上，所有的管道都是可见的。

CSP 的第二个好处是它的复合性质。进程可以组合，从而构成更复杂的进程（复杂的进程还可以再组合起来构成更加复杂的进程），很容易地随时间推移进行修改和扩展。所以，基于 CSP 的应用程序设计特别简单并且易于理解，并且在进行维护的时候也非常健壮。CSP 的复合性质也促进了更好的重用；正如在第 2 部分的编程示例中看到的，可以用大量不同的设置使用一个 JCSP 进程，如果需要的话，可以将不希望的输出重定向到黑洞中。

用 CSP 进行并发编程的最后一个好处对于构建分布式系统的开发人员来说特别明显。在本文中，我描述了实现并发性的不同选项（运行在单一进程中的多线程、运行在一个器上的多进程和运行在多个处理器上的多进程）。通常，这些并发机制中的每一个都要求使用完全不同的执行机制、编程接口和设计范式。而一旦用 CSP 开发应用程序，那么可以在不影响（至少不非常显著）应用程序设计或代码的情况下决定在哪个平台上运行应用程序，比如，是在多线程平台上，还是单一处理器上的多进程平台上，亦或是在分布处理器上运行的多进程平台上。

回页首

JCSP 和 java.util.concurrent

大多数 Java 程序员都知道，java.util.concurrent 包是作为 J2SE 1.5 类库的标准组成部分引入的。因为JCSP 库出现的时间比这个包加入 Java 平台的时间早，所以您可能想知道是否需要两者都用，或者说您想知道，既然已经适应了 java.util.concurrent，为什么还要费力地学习 JCSP。

java.util.concurrent 包实际上是 Doug Lea 的一个很不错的流行的 util.concurrent 库的重新整理。这个包的设计目的是提供一个强壮的、高性能的标准化工具集，简化 Java 平台上的并发 —— 而这个目的已经实现了！毫无疑问！ 如果 java.util.concurrent 包中的工具适合您的应用程序，那么请使用它们，您将得到回报。

Java 中的通信线程 JCSP 不是 Java 平台上惟一可用的 CSP 实现。Java 中的通信线程（CTJ） 是另一个流行的 CSP 实现，由 Twente 大学的 Gerald Hilderink 和 Andy Bakkers 开发。请参阅 参考资料，以获得 JCSP 和 CTJ 的详细比较，比如说，比较它们的哲学、相似与不同、性能和使用场景。

但是，正如我希望的，本文中的讨论已经显示出：基于 CSP 的技术（通过 JCSP 库） 表现出的机制超出了 java.util.concurrent 的范围。可以把系统构建成通信进程的网络，并用它们组合成网中之网，实现这一点的范式既自然又简单。这不仅提高了编写多线程应用程序的体验，而且提高了产品 品质。用 JCSP 构建系统会产生干净的接口，很少有会造成产品不好维护和技术变化这类隐藏的副作用。正式的验证（即正式地推断应用程序的安全性和活动属性）对于安全敏感和高价值的财务应用程序来说也是强大的资产。

在许多情况下，这两个包不是互相排斥的：有些 JCSP 的核心要素非常有望会在 java.util.concurrent 提供的原子的低级机制顶部重新实现，新实现的开支可能要比目前使用的标准监视器机制的开支更少。

回页首

第 3 部分的结束语

在这篇介绍适用于 Java 程序员的 CSP 的系列文章中，介绍了许多基础知识。在 第 1 部分 中，我介绍了 Java 语言目前支持的多线程编程的构造。还解释了这些构造的起源，讨论了它们与 Java 平台多线程编程的 4 个常见缺陷（争用风险、死锁、活动锁和资源耗尽）之间的关系。在对第一部分进行总结时，我解释了为什么在任意、大型、复杂的多线程应用程序中，很难应用正式的理论消除编程 bug 或证明它们不存在。我推荐使用 CSP 作为这个困境的备选项。

在 第 2 部分 中，我介绍了 CSP 理论和它最流行的一个基于 Java 的实现 —— JCSP 库。我用了几个实例演示了基本的 JCSP 构造（ 例如进程、通道和警卫等）的使用。

在最后这篇文章中，我介绍了 JCSP 中的高级主题，其中包括它与面向方面编程的相似性，以及它与 Java 平台的其他一些并发编程包的比较。我还演示了一些用来解决更复杂的同步问题的 JCSP 构造，简要讨论了用 JCSP.net 包进行分布式编程的可能性。

我希望我已经表达得够清楚，用 JCSP 编写多线程 Java 应用程序有许多优势。下次您会发现，在您自己考虑（也可能要在躲避）多线程应用程序设计时，您可能想转而采用 JCSP 库。JCSP 提供了非常简化的并发编程方法，生成的程序既能对最常见的多线程应用程序开发缺陷进行验证，还易于理解、调试和长远维护它们。

致谢

非常感谢 Peter Welch 教授在我编写这个文章系列期间给予的鼓励。他在百忙之中抽出时间非常细致地审阅了草稿，并提供了许多宝贵的提高此系列文章的质量和准确性的建议。如果文章中还存在错误，那都是由于我的原因！我在文章中使用的示例基于或来自 JCSP 库的 javadoc 中提供的示例，以及 JCSP Web 站点上提供的 Powerpoint 演示文稿。这两个来源提供了需要探索的大量信息。

参考资料

• 您可以参阅本文在 developerWorks 全球站点上的 英文原文。
  
  
• Nicholas Lesiecki 撰写的“使用面向 Aspect 的编程改进模块性” （developerWorks，2002 年 1 月）第一次介绍了 AOP 的好处。
  
  
  
  
• 请参阅 developerWorks 上为期一年的 AOP@Work 系列，并从其中突出强调的部分学习更多关于方面编程的内容。
  
  
  
  
• 并发性专家 Brian Goetz 在“Java 理论与实践: JDK 5.0 中更灵活、更具可伸缩性的锁定机制”（developerWorks，2004 年 10 月）这篇文章中解释了 java.util.concurrent 的一些优势与不足。
  
  
  
  
• Goetz 在“Java 理论与实践: 流行的原子” （developerWorks，2004 年 11 月）这篇文章中解释了 java.util.concurrent 中原子类的重要性。
  
  
  
  
• C.A.R. Hoare 撰写的“Communicating Sequential Processes”把通信顺序进程的并行复合作为一个基本的编程结构化方法引入进来介绍（Communications of the ACM Archive，1978）。
  
  
  
  
• 可以免费获得 PDF 格式的 C.A.R. Hoare 撰写的 关于 CSP 的书籍。
  
  
  
  
• Bill Roscoe 撰写的 Theory and Practice of Concurrency （Prentice Hall, 1997） 是关于并发性和 CS 主题的最新书籍。
  
  
  
  
• 牛津大学计算机实验室负责的 CSP Archive 是学习更多关于 CSP 内容的好地方，除此之外，还有 WoTUG homepage。
  
  
  
  
• JCSP home page 由英国坎特伯雷市肯特大学负责。
  
  
  
  
• 可以从 QuickStone 科技获得 Network Edition of JCSP。
  
  
  
  
• FDR2 （故障偏差求精，Failures-Divergence Refinement）是面向基于 CSP 的程序的几个商业化模型检测工具之一。
  
  
  
  
• Gerald Hilderink、Jan Broenink 和 Andre Bakkers 在“Communicating Threads for Java”（IOS Press，1999）这篇论文中描述了 JCSP 库的一个替代品。
  
  
  
  
• Peter Welch 教授和其他人合著的论文“Using Java for Parallel Computing -- JCSP versus CTJ” （IOS Press, 2000）比较了 JCSP 和 CTJ。
  
  
  
  
• CSP 可以使用 Java 语言实现，也可以使用其他语言实现： C++CSP 是针对 C++ 的实现，而 J#.Net 是针对 .Net 的实现。
  
  
  
  
• Occam-pi 是一个语言平台，它打算用 pi-calculus 的移动特性来扩展 occam 语言的 CSP 想法。请从 occam-pi homepage 了解这个前沿研究的更多信息。
  
  
  
  
• 在学习 occam 时，您可能还想调查 occam 编程器的各种扩展。
  
  
  
  
• 在 developerWorks Java 技术专区 中可以找到 Java 编程各方面的文章。
  
  
• 请参阅 Developer Bookstore，以获得技术书籍的完整清单，其中包括数百本 Java 相关主题的书籍。
  
  
  
  
• 还请参阅 Java 技术专区教程页，以获得 developerWorks 上免费的、以 Java 为重点的教程。
  

关于作者

		Abhijit Belapurkar 拥有位于印度德里市的印度理工学院（IIT）计算机科学的理工学士学位。在过去的 11 年中，他一直工作在分布式应用程序的架构和信息安全领域，他在使用 Java 平台构建 n 层应用程序方面大约有 6 年的工作经验。他目前是作为高级技术架构师在 J2EE 领域工作，服务于印度班加罗尔的 Infosys 科技有限公司。

转自：http://www-128.ibm.com/developerworks/cn/java/j-csp2/

2005 年 7 月 07 日

在这篇由三部分构成的面向 Java 程序员的通信顺序进程 （CSP）介绍的第二期中，Abhijit Belapurkar 将介绍如何使用基于 Java 的 JCSP 库来编写能够确保没有并发问题（例如争用风险、 死锁、活动锁、资源耗尽）的 Java 应用程序。

CSP 是对并发对象之间的复杂交互进行建模的范式。使用 CSP 的主要优势之一是：对程序每一阶段所包含对象的行为进行精确地指定和验证。CSP 的理论和实践对于并发设计和编程领域有深远的影响。它是 occam 这样的编程语言的基础，对其他语言（例如 Ada）的设计也有影响。就像在本文 第 1 部分 简要讨论过的，由于适合在 Java 平台上进行安全、优雅的多线程编程，所以 CSP 对 Java 开发人员也是无价的。

在我的这篇由三部分组成的 Java 平台 CSP 编程介绍的第 2 部分中，我把重点放在 CSP 理论和实践上，特别是它在 Java 语言中多线程程序设计的应用。我将从 CSP 理论的概述开始介绍，然后介绍基于 Java 的 JCSP 库实现，JCSP 的核心是 CSP 。

CSP 基础

CSP 的基本构造是进程和进程之间各种形式的通信。CSP 中的每件事都是进程，甚至（子）进程网络也是进程。但是，在进程之间没有直接交互 —— 所有交互都通过 CSP 的同步对象（例如各级进程订阅的通信通道和事件边界）实现的。

CSP 进程 与典型的 Java 对象不同：封装在进程组件中的数据 和 操纵数据的算法都是私有的。也就是说，进程没有对外可以调用的方法（除了启动进程必须调用的方法之外），算法只能在进程自己的控制线程内执行。如果把这种方法与 Java 语言中的方法调用进行对比，就可以立即看出 CSP 是如何消除显式锁定的需求的：

不要错过本系列的其余部分! “适用于 Java 程序员的 CSP”是对通信顺序进程（Communicating Sequential Processes —— CSP）进行介绍的由三部分组成的一个系列。CSP 是并发编程的一个范式，它承认了并发编程的复杂性，却并没有把复杂性留给开发人员。请参阅本系列的其他部分： 第 2 部分：用 JCSP 进行并发编程 第 3 部分： JCSP 的高级主题

在 Java 语言中，在对象上调用的方法总是在调用者的线程中运行。但也有一个特殊的控制线程是通过系统中的多个对象进行工作的。对于大部分情况来说，对象没有自己的生命 —— 它们只是在运行线程调用它们的方法时才存在。因此，不同的执行线程可以在同一时间试图调用同一对象的同一方法，就像 第 1 部分所讨论的那样。显然，这种情况在 CSP 中永远不会发生。

通信通道和进程网络

进程间通信最简单的机制就是通过通道读写数据。CSP 中基本的通道构造是同步的（synchronous） 和 点对点的（point-to-point）；也就是说，它不包含内部缓冲，并且把一个进程连接到另外一个进程。从这个基本通道开始，有可能构建多个阅读器/写入器通道（即一对多、多对一和多对多）。

CSP 中的进程构成了复杂系统的基本构造块 —— 一个进程可以同一个或多个其他进程连接起来（全都设置成并行的），从而构成一个进程网络。可以把这个网络本身想像成一个进程，这个进程还可以递归地与其他进程、它们自己的网络或者其他类似东西组合在一起，形成一个为了最好地解决手上问题而设计的复杂排列的金字塔。

如果单独考虑，那么进程仅仅是一个独立的串行程序，它只与外部 I/O 设备交互。这个程序本身并不需要考虑在 I/O 通道另一端的进程是否存在或对方的性质。

CSP 理论已经在许多基于 Java 的框架中实现了，包括面向 Java 的通信顺序进程（Communicating Sequential Processes for Java，JCSP） 库。

关于 CSP 的更多内容 本文提供了对 CSP 复杂主题的一般性介绍。如果对于深入理论底层的数学机制有兴趣，那么请参阅 C.A.R. Hoare 的原文章以及他针对这一主题撰写的书。要想获得 CSP 理论的最新发展（这些年已经做了更新），请参阅 Bill Roscoe 撰写的书。要想获得广泛的参考来源，请参考牛津大学计算机实验室和 WoTUG 主页的 CSP 归档。还请参阅 参考资料，以获取所有这些参考和更多内容的链接。

回页首

JCSP 库

JCSP 库由英国坎特伯雷市肯特大学的 Peter Welch 教授和 Paul Austin 开发（请参阅 参考资料）。对于本文余下的大部分内容来说，我会把重点放在 CSP 概念在 JCSP 中的实现方式上。因为 Java 语言没有提供对 CSP 构造的自带支持，所以 JCSP 库内部使用 Java 语言 实际 支持的、自带的并发构造，例如 synchronized、wait 和 notify。为了帮助您正确地理解 JCSP 的工作方式，我将从这些 Java 构造的角度对 JCSP 库中某些类的内部实现进行了解释。

注意，后续章节中的示例基于或来自 JCSP 库的 Javadoc 文档，或者基于可以在 JCSP 主页上得到的演示文稿。

回页首

JCSP 中的进程

在 JCSP 中，进程实际上就是实现了 CSProcess 接口的类。清单 1 显示了这个接口：

清单 1. CSProcess 接口

package jcsp.lang;
public interface CSProcess
{
    public void run();
}

注意，CSProcess 接口看起来就像 Java 语言的 Runnable 接口，而且它也充当着类似的角色。虽然 JCSP 目前是用标准 Java API 实现的，但是并不需要这样，而且在未来可能真的不需要这样。出于这个原因，在 JCSP 中没有直接使用 Runnable 接口。

验证 JCSP 程序 Peter Welch 教授和其他人构建了一个正式的 CSP 模型，从而可以用 CSP 术语对多线程 Java 程序进行分析，并验证程序是否会造成导致争用风险、死锁和资源耗尽的 bug。因为 JCSP 库使用模型底部的监视器机制 （即 synchronized()、wait()、notify() 和 notifyAll()） ，所以基于 JCSP 的应用程序可以用各种软件工程工具进行验证，其中包括一些商业化支持的工具。请参阅 参考资料，学习关于 FDR2 的内容，这是一个针对基于 CSP 的程序的模型检测工具。

JCSP 定义了两个接口用于从通道读取对象和向通道写入对象。从通道读取对象的接口叫作 ChannelInput ，它只有一个方法，叫作 read()。如果进程调用一个实现 ChannelInput 接口的对象的这个方法，那么进程会阻塞，直到在通道另一端的进程实际向通道写入了一个对象。 一旦在通道上有对象可用，对象就被返回给调用进程。类似地，ChannelOutput 接口也只有一个方法，叫作 write(Object o)。如果进程调用 一个实现 ChannelOutput 接口的对象的这个方法，进程也会阻塞，直到通道接受对象。正如前面提到过的，最简单的通道类型没有缓冲，所以它在另一端（读取）的进程调用 read() 之前不会接受对象。

从现在开始，我将使用代码示例来演示这些和其他 JCSP 构造如何工作。在清单 2 中，可以看到一个非常简单的进程，它输出 1 到 100 之间的所有偶数：

清单 2. 生成 1 到 100 之间偶数的进程

import jcsp.lang.*;
public class SendEvenIntsProcess implements CSProcess 
{
    private ChannelOutput out;
    public SendEvenIntsProcess(ChannelOutput out)
    {
      this.out = out;
    }
    public void run()
    {
      for (int i = 2; i <= 100; i = i + 2)
      {
        out.write (new Integer (i));
      }
    }
}

与每一个写进程对应，必须有一个读进程。如果不存在这样的进程，则会造成 SendEvenIntsProcess 在 ChannelOutput 对象的 out 进行第一次写操作之后立即无限期阻塞。清单 3 演示了一个简单的读进程，该进程与清单 2 介绍的写进程对应：

清单 3. 对应的消费者进程

import jcsp.lang.*;
public class ReadEvenIntsProcess implements CSProcess
{
    private ChannelInput in;
    public ReadEvenIntsProcess(ChannelInput in)
    {
      this.in = in;
    }
    public void run()
    {
      while (true)
      {
        Integer d = (Integer)in.read();
        System.out.println("Read: " + d.intValue());
      }
    }
}

回页首

JCSP 中的通道

到目前为止，我只有两个独立的进程。下一步就是使用一个用作共享同步机制的公共通道把它们联系在一起，然后从中剔除一个进程。channel 接口是 JCSP 的 ChannelInput 和 ChannelOutput 接口的子接口，是读取和写入对象的公共接口。这个接口有许多可能的实现，就像下面描述的一样：

• 类 One2OneChannel，顾名思义，实现了“单一写入器/单一阅读器”类型的通道。
  
  
• 类 One2AnyChannel 实现了“单一写入器/多阅读器”对象通道。（注意，这不是广播机制，实际上，为了从通道读取对象，多个阅读器要进行相互竞争；在指定时间只有一个阅读器能使用通道和写入器进行沟通。）
  
  
• 类 Any2OneChannel 实现了 “多写入器/单一阅读器”对象通道。同上面的情况一样，写入进程彼此竞争使用通道。在指定时间，只有阅读器和众多写入器中的一个在实际使用通道。
  
  
• 类 Any2AnyChannel 实现了“多写入器/多阅读器”对象通道。读取进程彼此竞争使用的通道，写入进程也一样。在指定时间只有一个阅读器和一个写入器在实际使用通道。

在清单 3 的示例中，我只有一个写入器进程和一个阅读器进程，所以 One2OneChannel 类就足够了。驱动器程序的示例代码如清单 4 所示：

清单 4. 驱动器程序

import jcsp.lang.*;
public class DriverProgram
{
    public static void main(String[] args)
    {
      One2OneChannel chan = new One2OneChannel();
      new Parallel
      (
        new CSProcess[]
	    {
	      new SendEvenIntsProcess (chan),
	      new ReadEvenIntsProcess (chan)
	    }
      ).run ();
    }
}

正如代码表示的，我首先实例化一个新的 One2OneChannel 对象，然后把它传递给 SendEvenIntsProcess 和 ReadEventIntsProcess 进程的构造函数。这样做是因为 One2OneChannel 同时实现了两个接口 —— ChannelInput 和 ChannelOutput。

通道内部

因为通道在 JCSP 中是重要的概念，所以在进行下一步之前，要确定您确实理解了它们的工作方式。正如我在前面提到的，通道在默认情况下是非缓冲的，但是也可以把它们变成缓冲的。实现方式是：通道本身并不处理缓冲特性，而是把这个责任委托给其他类，其他类必须实现叫作 ChannelDataStore 的接口。JCSP 为这个接口提供了多个内置实现，其中包括以下几个实现：

• ZeroBuffer，对应默认的非缓冲特性。
  
  
• Buffer，为与之相关联的通道提供了一个阻塞的先进先出的缓冲语义。
  
  
• InfiniteBuffer，也提供先进先出语义，但是如果缓冲为空，那么可以将阅读器阻塞。写入器永远不会阻塞，因为缓冲可以无限扩展，或者至少到了底层内存系统设置的限制为止。

回页首

通道实战

考虑一个实际使用的通道示例。当我创建了如清单 4 所示的 One2OneChannel 实例时，我把它内部的 ChannelDatasource 设置成 ZeroBuffer 的一个新实例。ZeroBuffer 只能保存一个对象（或整数）。它有一个内部状态变量，该变量的起始值为 EMPTY，只要放进一个对象，该变量的值就变成 FULL 了。

当 SendEvenIntsProcess 进程在它的 out 通道上进行 write 操作时，会发生什么呢？One2OneChannel 类的 write() 方法是一个 synchronized() 方法。因此，发送方进程运行所在的线程（很快就会看到发送方进程和阅读器进程运行在独立的线程中）就会得到与这个通道实例相关联的监视器锁，并继续处理方法。在该方法中，业务的第一个顺序就是调用内部持有的 ZeroBuffer 实例的 put 方法，把对象（或者在这个示例中是整数）写到 ZeroBuffer 实例。这样就把缓冲的状态变成 FULL。这时，调用线程调用 wait，造成线程进入监视器的 等候集，后面进行的操作是释放监视器锁和阻塞线程。

稍后，阅读器线程调用通道上的 read 操作（这也是一个同步的方法，所以阅读器线程在继续处理之前必须得到监视器锁）。因为内部缓冲的状态是 FULL，所以可用数据将被返回，并发出一个 notify()。notify() 唤醒发送方线程，然后发送方线程退出监视器等候集，并重新申请监视器锁。

在反过来的场景中，如果阅读器线程调用通道上的 read 方法时，通道的内部缓冲状态是 EMPTY，那么阅读器线程就不得不 wait，在这种情况下，发送方线程要在把数据对象写入内部缓冲之后通知阅读器线程。

回页首

Parallel 构造

在 清单 4 中，您可能已经注意到驱动器程序引入了一个新类，叫作 Parallel。Parallel 类是由 JCSP 以预定义 CSProcess 的形式提供的，它接受一组独立的 CSProcess 实例，并“平行地”运行它们 （除了最后一个之外，所有进程都在独立的线程中运行；最后一个进程由 Parallel 对象在自己的控制线程中运行）。 Parallel 进程的 run 方法只有在所有的部件进程终止的时候才终止。所以 Parallel 进程是一种把多个独立进程组织起来的机制，它用通道（在驱动器程序中示例中）作为“线”把进程连在一起。

了解 Parallel 构造的另一个途径是说：它可以把小的、简单的组件组合成更高层次的进程。实际上，Parallel 允许通过迭代把前面迭代中创建的组件与新的组件连接起来，创建出任意复杂程度的完全连接的进程网络。生成的进程网络可以像一个 CSProcess 对象一样公开和使用。

回页首

Parallel 示例

JCSP 库提供了一组即插即用的组件，不过仅仅是出于教育的目的，正好适合我的目的：进入其中几个的内部实现，可以很好的表现如何在 JCSP 中组合成网络化的并发进程。我用下面的示例进程来表现 JCSP 中 Parallel 构造的内部工作方式：

• PlusInt 在两个输入流中都接受整数，把整数加在一起，然后把结果输出到输出流。
  
  
• Delta2Int 平行地把到达它的输入流的每个整数广播到它的两个输出通道。
  
  
• PrefixInt 在它的整数输入流之前加上一个（用户配置的）整数。（也就是说，在这个进程的输出通道上有整数可用之前，第一个输出是预先配置的整数。后面的输出才是从输入流得到的整数。）
  
  
• IntegrateInt 是一个用 Parallel 构造组合了前三个进程的进程。它的功能是输出来自它的输入通道的整数的中间汇总值。

IntegrateInt 类的 run 方法如清单 5 所示：

清单 5. IntegrateInt 进程

import jcsp.lang.*;
public class IntegrateInt implements CSProcess 
{
  private final ChannelInputInt in;
  private final ChannelOutputInt out;
  public IntegrateInt (ChannelInputInt in, ChannelOutputInt out)
  {
    this.in = in;
    this.out = out;
  }
  public void run()
  {
      One2OneChannelInt a = new One2OneChannelInt ();
      One2OneChannelInt b = new One2OneChannelInt ();
      One2OneChannelInt c = new One2OneChannelInt ();
      new Parallel 
      (
        new CSProcess[]
        {
          new PlusInt (in, c, a),
          new Delta2Int (a, out, b),
          new PrefixInt (0, b, c)
        }
      ).run ();
  }
}

注意，与 请单 4 中使用的通道相比，这个示例中使用了不同种类的通道。 IntegrateInt 类使用 ChannelInputInt 和 ChannelOutputInt 通道，顾名思义，可以用它们传递 int 类型的整数。相比之下，清单 4 中的驱动器程序使用了 ChannelInput 和 ChannelOutput，它们是 对象 通道，可以用来在通道中从发送方给接收方发送任意对象。出于这个原因，在清单 4 中传递 int 值之前，我不得不把 int 值包装成 Integer 对象。

在清单 5 中，还需要注意观察什么呢？实际上，PrefixInt 进程的第一个输出是 0，它是通过 PlusInt 进程添加到输入通道到达的第一个整数上的。这个结果被写入通道 a，它构成了 Delta2Int 进程的输入通道。Delta2Int 进程把整数结果写到 out （进程的整体输出通道）并把它发送到 PrefixInt 进程。然后 PrefixInt 进程把整数作为输入发送给 PlusInt 进程，并添加到流中的第二个整数，如此类推。

IntegrateInt 进程组成的图示如图 1 所示：

图 1. IntegrateInt 进程

回页首

网络中的网络

IntegrateInt 进程就是这样由三个小进程组成，它本身可以当作一个复合进程来用。JCSP 库提供了一个叫作 SquaresInt 的进程，顾名思义，它生成一个整数流，整数流是自然数 （1、2、3、4，等等）的平方。这个进程的代码如清单 6 所示：

清单 6. SquaresInt 进程

public class SquaresInt implements CSProcess 
{
  private final ChannelOutputInt out;
  public SquaresInt (ChannelOutputInt out)
  {
    this.out = out;
  }
  public void run()
  {
      One2OneChannelInt a = new One2OneChannelInt ();
      One2OneChannelInt b = new One2OneChannelInt ();
      new Parallel 
      (
        new CSProcess[]
        {
          new NumbersInt (a),
          new IntegrateInt (a, b),
          new PairsInt (b, out)
        }
      ).run ();
  }
}

我可以肯定您已经注意到清单 6 显示的两个新进程。NumbersInt 是一个内置进程，它只是在其输出通道中输出从 0 开始的自然数。PairsInt 进程则把连续的一对输入值相加并输出结果。这两个新进程和 IntegrateInt 一起构成了 SquaresInt 进程，如图 2 中的图表所示：

图 2. SquaresInt 进程

SquaresInt 的工作方式

在进入下一部分之前，先来考虑 SquaresInt 进程的内部工作方式。在下面可以看到 SquaresInt 内部每个通道上的交通流向：

Channel "a":	[0, 1, 2, 3, 4, 5, 6, 7, 8, ...ad infinitum]
Channel "b":	[0, 1, 3, 6, 10, 15, 21, 28, 36, ...ad infinitum]
Channel "out":	[1, 4, 9, 16, 25, 36, 49, 64, 81 ...ad infinitum]

您有没有看这样的模式：写入通道 a 的整数造成它们也被写入通道 b，因此也写到通道 out？在第一次“滴答”当中，NumbersInt 进程把整数 0 写入通道 a。IntegrateInt 进程也把整数 0 （是当前汇总的值）写入通道 b。PairsInt 进程在这次滴答中什么都不产生，因为它需要处理两个输入。在第二次滴答中，NumbersInt 进程在它的输出通道上写入整数 1。这造成 IntegrateInt 进程把汇总值修改成 0+1=1，所以把整数 1 写入通道 b。

这时, PairsInt 有了两个整数输入可以处理 —— 整数 0 来自前一次滴答，整数 1 来自当前滴答。它把它们加在一起，并把输出 0+1=1 写到通道 out。请注意 1 是 1 的平方，所以我们现在可能是在正确的轨道上。继续把示例前进到下一个（第三个）滴答，NumbersInt 进程把把整数 2 写入通道 a。这使 IntegrateInt 进程把汇总值更新为 1 （前一个汇总值） + 2 （新值） = 3 并把这个整数写入通道 b。

PairsInt 进程看到最后两个整数是什么？它们是 1 （在前一次滴答期间） 和 3 （在当前滴答期间）。所以，进程把这两个整数加在一起，并把 1+3=4 写入通道 out。您会注意到 4 是 2 的平方，这意味着 SquaresInt 工作起来就像它应当工作的那样。实际上，应当继续运行这个程序到任意数量的滴答，这样就可以验证写入通道 out 的整数总是在序列中的下一个整数的平方。我在下一节精确地这一操作。

数学问题

就在您纳闷的时候，我想解释一下生成平方值的数学基础。假设在 NumbersInt 进程已经把整数输出到某个 n-1 的时候，您偷看到了箱子内部。IntegrateInt 进程最后生成（而且通过共享通道 b 放到 PairsInt 进程）的中间汇总会是 [1+2+3+...+(n-1)] = (n-1)(n-2)/2。

在下一次滴答期间，NumbersInt 会输出 n，这造成 IntegrateInt 进程的中间汇总增长为 (1+2+3+...+n) = n(n-1)/2。然后这个汇总会通过共享通道 b 传给 PairsInt 进程。 PairsInt 会把这两个数加在一起，生成 [(n-1)(n-2)/2 + n(n-1)/2] = [(n-2) + n](n-1)/2 = (2n-2)(n-1)/2 = (n-1)exp2。

接下来，NumbersInt 进程会产生(n+1)。与之对应，IntegrateInt 进程会把 n(n+1)/2 送到 PairsInt 进程。然后 PairsInt 会生成 [n(n-1)/2 + n(n+1)/2] = nexp2。针对所有的 n 对这进行通用化，就会按照期望的那样产生全部平方。

回页首

JCSP 中的确定性

以上示例演示了 CSP 的复合语言 —— 即如何用 Parallel 构造把细致的无状态的组件组成分层的网络。所有这类相互通信的平行进程的分层网络的卖点就是：它们是完全确定的。在这个上下文环境中 确定 意味着什么呢？它意味着这类分层网络的输出只取决于提供给它的输入，而不用考虑网络运行的运行时环境（JVM）的特性。也就是说，进程网络独立于 JVM 的调度策略，也独立于它所分布的多处理器。（我在这里假设的是个单一节点，但是，没有什么固有的东西会防碍把这个讨论引入物理上分布在多个节点上而在进程之间通过线路进行通信的进程网络上。）

确定性会是工具包中的强大工具，因为它可以让您清晰地推断出程序的行为，不必担心运行时环境对它可能产生的影响。同时，确定性不是并发性编程惟一可能的技术或必需的技术。因为下一个（也是最后一个）实例将显示，非确定性在 JSP 中也是同样强大的实用概念。

回页首

JCSP 中的非确定性

非确定是许多真实的应用程序的因子，在这些应用程序，可见的输出是某个功能或者事件发生的顺序。换句话说，当结果取决于设计的调度，而 不是 取决于事件时，就是非确定性在并发应用程序中发挥作用的地方了。您将会看到，JCSP 显式地处理这类问题。

例如，假设一个进程对于 下面要做什么 有许多备选项，每个备选项都有一个与之关联的 警卫（guard），警卫必须处于“就绪（ready）”状态，这样才能让备选项得以考虑。进程可以从可用的备选项（也就是就绪的）中选择一个选项；选择本身可能基于不同的策略，可能是任意选择、最高优先级选择或者公平选择。

事件选择策略

在 JCSP 的特定上下文中，提供了一个叫作 Guard 的抽象类，竞争进程选择的事件必须继续它。进程本身使用另一个预先提供的类，叫作 Alternative，这些警卫对象必须以对象数组的形式传递给它的构造函数。Alternative 类为三种事件选择策略提供了方法。

Alternative 类的 select() 方法对应着 任意选择 策略。select() 方法调用一直受阻塞，直到一个或多个警卫就绪为止（请记住，所有竞争的警卫对于 Alternative 类来说都是已知的）。其中一个就绪的警卫被随机选中，它的索引（在传递进去的警卫数组中）也被返回。

priSelect() 方法对应着 最高优先级 策略。也就是说，如果不止一个警卫就绪，则返回索引值最低的那个；这里面的假设是：在数组中传递给 Alternative 构造函数的警卫已经按照优先级顺序进行降序排序了。

最后，方法 fairSelect 是在多个就绪警卫中进行 公平 选择：在这个方法的连续调用中，在其他就绪而且可用的警卫没被选中之前，不会有某个就绪的警卫被选中两次。所以，如果警卫的总数是 n，那么在最坏的情况下，就绪的警卫没获得选中的次数不会连续超过 n 次。

如果进程不关心如何选择多个就绪警卫，那么任意选择策略最合适；如果进程想保证没有资源耗尽或者最差服务次数，例如在实时系统中，那么任意选择就不太适用了。在前面的情况下，推荐使用 fairSelect 方法，而在后面的情况下，用 priSelect() 方法最好。

警卫类型

大体来说，JCSP 提供了三类警卫：

• 通道警卫 总是对应着进程等候从中读取数据的通道。也就是说，只有在通道另一端的进程已经输出数据，而该数据还没有被进程输入的时候，警卫才就绪。
  
  
• 计时器警卫 总是和设置（绝对）超时对应。也就是说，如果超时，则计时器警卫就会就绪。
  
  
• 跳过警卫 总是就绪。

JCSP 中的通道警卫 可以是以下类型：AltingChannelInput/AltingChannelInputInt，只要在对应的通道中有了对象或整数数据，则这两个通道将就绪；或者 AltingChannelAccept，如果在通道中出现不可接受的“CALL”（这一点后面有更多介绍），则通道就会就绪。这些都是抽象类，它们拥有 One2One 和 Any2One 类型通道形式的具体实现。JCSP 中的计时器 警卫属于 CSTimer 类型，而 跳过警卫 则是以 Skip 类的形式提供的。

回页首

运作中的警卫

我用一个简单的示例，演示如何用 JCSP 警卫实现并发应用程序中的非确定性，借此总结对 JCSP 的介绍。假设您必须开发一个乘法（或者 倍增） 设计，读取的整数在输出通道以固定速率到达，可以用某个乘数乘以它们，然后把它们写入其输出通道。设备可以用一个初始乘数开始，但是这个乘数每 5 秒钟自动加倍。

这个故事中介绍的方法是这样的：系统中存在着第二个控制器进程，它能通过专用通道向设备发送 suspend operation 信号。这使设备中止自身，并把乘数的当前值通过第二个通道发送给控制器。

在中止的时候，设备只应当允许全部进入的整数不经变化地通过它的输出通道。控制器进程 —— 可能在用设备发送给它的乘数做了某些计算中的一种 —— 通过专用通道把一个新乘数发送回设备。（请注意：只要设备处于 中止 状态，就会被迫接受这个乘数。）

更新过的乘数插入到设备，并充当设备的唤醒信号。设备现在继续执行它的放大操作，用新更新的乘数乘上输入的整数。计时器这时也重置，所以新的乘数也在 5 秒之后被设置成加倍数值，如此类推。

图 3 中的图表说明了这个放大设备：

图 3. 放大设备

回页首

ScaleInt 进程

放大设备的源代码在清单 7 中显示。这个示例中的非确定性是因为：output 的值基于 in 和 inject 流的值（同时还基于这些值到达的顺序）。

清单 7. ScaleInt 进程

import jcsp.lang.*;
import jcsp.plugNplay.ints.*;
public class ScaleInt implements CSProcess
{
  private int s;
  private final ChannelOutputInt out, factor;
  private final AltingChannelInputInt in, suspend, inject;
  public ScaleInt (int s, AltingChannelInputInt suspend, AltingChannelInputInt in, 
    ChannelOutputInt factor, AltingChannelInputInt inject, ChannelOutputInt out)
  {
    this.s = s;
	this.in = in;
	this.out = out;
	this.suspend = suspend;
	this.factor = factor;
	this.inject = inject;
  }
  public void run()
  {
	final long second = 1000;               // Java timings are in millisecs
	final long doubleInterval = 5*second;
	final CSTimer timer = new CSTimer ();
	final Alternative normalAlt = new Alternative (new Guard[] {suspend, timer, in});
	
	final int NORMAL_SUSPEND=0, NORMAL_TIMER=1, NORMAL_IN = 2;
	final Alternative suspendedAlt = new Alternative (new Guard[] {inject, in});
	
	final int SUSPENDED_INJECT=0, SUSPENDED_IN = 1;
	
	long timeout = timer.read () + doubleInterval;
	timer.setAlarm (timeout);
	while (true)
	{
	  switch (normalAlt.priSelect ())
	  {
		case NORMAL_SUSPEND:
		  suspend.read ();              // don't care what's sent
		  factor.write (s);             // reply with the crucial information
		  boolean suspended = true;
		  while (suspended)
		  {
		    switch (suspendedAlt.priSelect ())
			{
			  case SUSPENDED_INJECT:    // this is the resume signal as well
			    s = inject.read ();     // get the new scaling factor
				suspended = false;      // and resume normal operations
				timeout = timer.read () + doubleInterval;
				timer.setAlarm (timeout);
				break;
			  case SUSPENDED_IN:
			    out.write (in.read ());
				break;
			}
		  }
		  break;
		case NORMAL_TIMER:
		  timeout = timer.read () + doubleInterval;
		  timer.setAlarm (timeout);
		  s = s*2;
		  break;
		case NORMAL_IN:
		  out.write (s * in.read ());
		  break;
	  }
    }
  }
}
import jcsp.lang.*;
import jcsp.plugNplay.ints.*;
public class Controller implements CSProcess
{
  private long interval;
  private final ChannelOutputInt suspend, inject;
  private final ChannelInputInt factor;
  public Controller (long interval, ChannelOutputInt suspend, ChannelOutputInt inject, 
    ChannelInputInt factor)
  { 
    this.interval = interval;
    this.suspend = suspend;
    this.inject = inject;
    this.factor = factor;
  }
  public void run ()
  {
	int currFactor = 0;
	final CSTimer tim = new CSTimer ();
	long timeout = tim.read ();
	while (true)
	{
	  timeout += interval;
	  tim.after (timeout);        // blocks until timeout reached
	  suspend.write (0);          // suspend signal (value irrelevant)
	  currFactor = factor.read ();			
	  currFactor ++;              // compute new factor
	  inject.write (currFactor);  // inject new factor
	}
  }
}
import jcsp.lang.*;
import jcsp.plugNplay.ints.*;
public class DriverProgram
{
  public static void main(String args[])
  {
	try
	{
	  final One2OneChannelInt temp = new One2OneChannelInt ();
	  final One2OneChannelInt in = new One2OneChannelInt ();
	  final One2OneChannelInt suspend = new One2OneChannelInt ();
	  final One2OneChannelInt factor = new One2OneChannelInt ();
	  final One2OneChannelInt inject = new One2OneChannelInt ();
	  final One2OneChannelInt out = new One2OneChannelInt ();
		
	  new Parallel
	  (
		new CSProcess[]
		{
		  new NumbersInt (temp),
		  new FixedDelayInt (1000, temp, in),
		  new ScaleInt (2, suspend, in, factor, inject, out),
		  new Controller (6000, suspend, inject, factor),
		  new PrinterInt (out, "--> ", "\n")
		}
	  ).run ();
	}
	catch (Exception e)
	{
		e.printStackTrace();
	}
  }
}

上面的类 ScaleInt 对应着放大设备。正如前面提到的，这个类必须实现 CSProcess 接口。因为上面的代码演示了许多概念，所以我将逐个讨论它的不同方面。

两个备选项

在 ScaleInt 类中，我们感兴趣的第一个方法是 run()。在 run() 方法中，要做的第一件事是创建 Alternative 类的两个实例，每个都有一组不同的 Guard 对象。

第一个 Alternative 实例由变量 normalAlt 表示，它是为设备正常操作的时候使用的。与之关联的警卫列表如下所示：

• suspend 是 One2OneChannelInt 的实例。正如前面提到过的，One2OneChannelInt 实现了单一阅读器/写入器整数通道，通道是零缓冲、完全同步的。这是控制器进程向设备发送中止信号的通道。
  
  
• timer 是 CSTimer 的实例，它被设置成每 5 秒触发一次，每次触发时，设备会把乘数的当前值加倍。
  
  
• in 是 One2OneChannelInt 的实例，设备通过它接收输入的整数。

第二个 Alternative 实例由 suspendedAlt 表示，它是供设备在已经被 Controller 中止的情况下使用的。与之关联的警卫如下如示：

• inject 是 One2OneChannelInt 的实例，由控制器进程使用，用来向设备发送新的乘数（也充当唤醒信号）。
  
  
• in 是前面已经看到的 One2OneChannelInt 相同的实例；设备通过这个通道接收输入整数。

两个 Alternative 实例被用在不同的情况下等候警卫就绪，列表的顺序是隐式的优先级顺序。例如，如果 normalAlt 的 suspend 和 timer 警卫恰好同时就绪，那么和 suspend 警卫对应的事件首先被处理。

警卫就绪

下一个我们感兴趣的是在每个警卫就绪的时候，发生了什么。我首先研究 normalSelect，假设设备操作正常（也就是说，还没有被中止）：

• 如果控制器向设备发送了 suspend 信号，那么这个事件以最高优先级得到处理。作为响应，设备把乘数的当前值通过叫作 factor 的通道发送给控制器。然后将叫作 suspended 的内部标志设置为 true，然后进入循环，等候别人发送信号，以继续其操作。在循环内部，设备调用第二个 Alternative 实例上的 priSelect() 方法 （suspendedAlt）。
  
  这个 Alternative 实例包含两个警卫：第一个表示控制器向设备发送乘数的事件，第二个表示整数到达设备的输入通道。在前一种情况下，设备用从 inject 通道读取的值来更新乘数（保存在变量 s 中），并将 suspended 标志设置回 false （这样就保证了在下一次迭代时可以退出内部循环），用当前计时器的值作为基值重新设置闹钟。在后一种情况下，设备只是从它的输入通道读取整数，并把整数写入输出通道（也就是说，在设备中止时，不许使用乘数的要求）。
  
  
• 具有下一个优先级得到处理的事件是闹钟到期事件。这造成设备把当前乘数加倍，用当前计时器的值作为基值重新设置闹钟，然后返回，继续等候下一个事件。
  
  
• 第三个可能是事件是从设备的输入通道接收整数的事件。与之对应的是，设备读取整数，用当前乘数 s 乘上它，并将结果写入设备的输出通道。

Controller 类

下一个要考虑的类是 Controller 类。请记住，控制器类的任务是周期性地（大概是基于复杂的计算）向设备进程插入乘数值。在这个示例中，周期基础只是一个计时器，该计时器按照规律的、配置好的间隔到期。每次到期时，控制器就在 suspend 上写一个 0（也就是说，它将中止设备），并在叫作 factor 的输入通道上读取当前的乘数。

这时，控制器只是把这个值加一，然后通过一对一通道 （叫作 inject，专门用于为这个目的） 将它插回设备。这就通知设备继续工作的方式，这时计时器被重新设置成在适当间隔后到期。

DriverProgram 类

最后剩下的类是驱动器类 DriverProgram。这个类创建适当的通道和 CSProcess 实例数组。它用 JCSP 提供的类 NumbersInt 生成一系列自然数，通过temp 通道传递给另一个叫作 FixedDelayInt 的内置类。顾名思义，FixedDelayInt 将来自其输入通道的值在固定延迟（在示例代码中，该延迟是 1 秒）之后发送到它的输出通道。

这个自然数的流每隔一秒就被发送到 ScaleInt 进程的 in 通道。ScaleInt 进程的 out 通道的输出传递给 JCSP 提供的 PrinterInt 进程，然后该进程再接着把整数值输出到 System.out。

回页首

第 2 部分的结束语

在这个由三部分组成的介绍适用于 Java 程序员的 CSP 的系列文章的第 2 部分中，我解释并演示了并发编程中的 CSP 理论。然后是对 CSP 构造的概述，其中介绍了最流行的基于 Java 的 CSP 库 —— JCSP。由于 Java 语言没有对 CSP 构造提供自带的支持，所以 JCSP 库内部采 Java 支持 的自带构造，例如 synchronized()、wait() 和 notify()。为了帮助您正确地理解 JCSP 是如何工作的，我从 Java 构造的角度解释了一些 JCSP 类库的内部实现，然后在几个实际示例中演示了它们的用法。

这里所进行的讨论可以作为本系列最后一篇文章的绝好基础。在最后一篇文章中，我将解释 CSP 和 AOP 的相似性，并简要地对 CSP 解决并发性的方法和新的 java.util.concurrent 包解决并发性的方法进行比较，还将介绍许多用 JCSP 进行高级同步 的技术。

致谢

非常感谢 Peter Welch 教授在我编写这个文章系列期间给予的鼓励。他在百忙之中抽出时间非常细致地审阅了草稿，并提供了许多宝贵的提高系列质量和准确性的建议。文章中如果还存在错误的话，那都是由于我的原因！我在文章中使用的示例基于或来自 JCSP 库的 javadoc 中提供的示例，以及 JCSP Web 站点上提供的 Powerpoint 演示文稿。这两个来源提供了需要探索的大量信息。

参考资料

• 您可以参阅本文在 developerWorks 全球站点上的 英文原文。
  
  
• Brian Goetz 编写的由三部分组成的 “Threading lightly”是解决 Java 平台上同步问题的巧妙而系统的方法。（developerWorks，2001 年 7 月）
  
  
  
  
• Allen Holub 撰写的“如果我是国王：关于解决 Java编程语言线程问题的建议” （developerWorks，2000 年 10 月）是一篇启蒙性的、至今仍有意义的、关于 Java 平台多线程编程错误的概述。
  
  
  
  
• C.A.R. Hoare 开创性的论文“Communicating Sequential Processes”把通信顺序进程的并行组成作为一种基本的编程结构化方法提了出来（Communications of the ACM Archive，1978）。
  
  
  
  
• 可以免费获得 PDF 格式的 C.A.R. Hoare 撰写的 关于 CSP 的书籍。
  
  
  
  
• Bill Roscoe 撰写的 Theory and Practice of Concurrency （Prentice Hall, 1997） 是最关于并发性和 CS 主题的最新书籍。
  
  
  
  
• 牛津大学计算机实验室负责的 CSP Archive 是学习更多关于 CSP 内容的好地方，除此之外，还有 WoTUG homepage。
  
  
  
  
• Peter Welch 教授和 Jeremy Martin 合著的“Formal Analysis of Concurrent Java Systems” （IOS Press, 2000） 是在 Java 语言中实践 CSP 的良好起点。
  
  
  
  
• JCSP homepage 由英国坎特伯雷市肯特大学负责。
  
  
  
  
• FDR2 （故障偏差求精，Failures-Divergence Refinement） 是面向基于 CSP 的程序的几个商业化模型检测工具之一。
  
  
  
  
• CSP 的实现可用于 Java 语言之外的其他语言：C++CSP 是针对 C++ 的实现，而 J#.Net 是针对 .Net 的实现。
  
  
  
  
• Occam-pi 是一个语言平台，它期望用 pi-calculus 的移动特性扩展 occam 语言的 CSP 想法。请从 occam-pi homepage 学习这个尖端的研究。
  
  
  
  
• 在学习 occam 时，您可能还想调查 occam 编程器的各种扩展。
  
  
  
  
• 在 developerWorks Java 技术专区 可以找到 Java 编程各方面的文章。
  
  
• 请参阅 Developer Bookstore，以获得技术书籍的完整清单，其中包括数百本 Java 相关主题的书籍。
  
  
  
  
• 还请参阅 Java 技术专区教程页，以获得 developerWorks 上免费的、以 Java 为重点的教程。
  

关于作者

		Abhijit Belapurkar 拥有位于印度德里市的印度理工学院（IIT）计算机科学的理工学士学位。在过去的 11 年中，他一直工作在分布式应用程序的架构和信息安全领域，他在使用 Java 平台构建 n 层应用程序方面也已经有大约 6 年的工作经验。他目前作为高级技术架构师在 J2EE 领域工作，服务于印度班加罗尔的 Infosys 科技有限公司。

转自：http://www-128.ibm.com/developerworks/cn/java/j-csp1.html

虽然使用 Java™ 语言进行多线程应用程序编程并不难掌握，但是许多开发人员都在为了正确地应用它们而挣扎。结果，多线程程序要比我们想像的更容易发生细微的错误，这导致一些开发人员为了避免使用多线程而不惜代价，即使在并发和平行能够很明显能够产生最好的设计的时候，他们也不采用多线程。在这篇由三部分组成的系列文章中，developerWorks 的定期投稿者 Abhijit Belapurkar 为您铺设了一条有助于克服对多线程编程恐惧、感受它的好处的道路。文章从多线程编程最常见问题的概述开始，这些问题包括：竞争冒险（race hazard）、死锁、活动锁、资源耗尽（resource starvation），等等。

在 Java 平台上进行多线程编程是件让人望而生畏的事，这一点得到了广泛认可。实际上，一般的理论似乎是：最好把多线程编程留给 Java 高手。Sun Microsystems 通过（在 EJB 规范中—— 请参阅参考资料）把以下内容描述成 EJB 架构的目标之一，也间接地、更深入地讨论了这个观念：

应用程序开发人员不必理解低级事务和状态管理细节、不必理解多线程、连接池或者其他复杂的低级 API。

如果以这个观念为起点，那么您也就不会惊讶为什么许多 Java 开发人员要避开设计和开发多线程应用程序。但事实上，许多（即使不是大多数）企业级问题使用某种形式的多线程来解决最合适，而 EJB 和类似的框架并不像它们声称的那样，总是最容易的解决方案。

在这篇由三部分组成的系列文章中，我介绍了一个理论，该理论承认了并发编程的复杂性，并且没有试图隐藏这种复杂性，或者使它不那么难于学习和应用。通信顺序进程（Communicating Sequential Processes —— CSP） 是一个精确的并发数学理论，可以用来构建多线程应用程序，确保构建的程序中不出现并发的常见问题，而且更重要的是，这一点 能够得到证实。

在介绍 CSP 理论和它基于 Java 语言的实现 —— JCSP 库 —— 之前，我希望能够确定我们有一个共同的讨论框架。我先从 Java 平台的并发编程技术概述开始，接着提供了多线程应用程序开发缺陷的深入概述，这些缺陷包括：竞争冒险、死锁、活动锁和资源耗尽等。最后，通过一些具体的讨论结束本文，这些讨论包括为什么 不能像您喜欢的那样验证多线程 Java 应用程序，并确定现有变通方法中您最偏爱的变通方法。

不要错过连载剩下的部分！ “面向 Java 程序员的 CSP”是由三部分组成的、介绍通信顺序进程（Communicating Sequential Processes —— CSP）的系列文章中的一篇。CSP 是并发编程的一个范式，它承认了并发编程的复杂性，却并没有把复杂性留给开发人员。请参阅本系列的其他部分： 第 2 部分：用 JCSP 进行并发编程 第 3 部分： JCSP 的高级主题

有了这些基础，就可以完全地体会 JCSP 的好处了。这是 Java 平台多线程编程的一个概念性和实践性的解决方案，我将在 第 2 部分 对其进行探讨，还将在 第 3 部分 探讨 Java 平台上更高级的 CSP 应用程序。

请注意，为了方便读者，这篇文章的三个部分同时发布。本文假设读者对于 Java 语言的并发编程有一般性的了解，虽然我在文章中也提供了关于这一主题的一个概述。请参阅 参考资料 一节，以获得更详细的信息。

Java 语言的并发编程

就其自身来说，并发编程是一种技术，提供了操作的同时执行，不论是在单一系统上还是分布在大量系统上。这类操作实际是一些指令顺序，例如单独某个顶级任务的子任务，这类操作能够并行执行，或者是作为线程，或者是作为进程。线程和进程之间的本质区别在于：进程通常是独立的（例如独立的地址空间），所以只能通过系统提供的进程间通信机制进行交互，而线程通常共享单一进程的状态信息，能够直接共享系统资源和内存中的对象。

可以使用下面两种方法之一，通过多个进程来实现并发。第一种方法是在同一个处理器上运行进程，由操作系统处理进程之间的上下文环境切换。（可以理解，这种切换要比同一进程内多线程之间的上下文环境切换更慢。）第二种方法是构建大规模的并行和复杂的分布式系统，在不同的物理处理器上运行多个进程。

从内建支持的角度来说，Java 语言通过线程提供并发编程；每个 JVM 都能支持许多线程同时执行。可以用以下两种方法之一在 Java 语言中创建线程：

• 继承 java.lang.Thread 类。在这种情况下，已经重写的子类的 run() 方法必须包含实现线程运行时行为的代码。要执行这个代码，需要实例化子类对象，然后调用对象的 start() 方法，这样就可以在内部执行 run() 方法了。
  
  
• 创建 Runnable 接口的定制实现。这个接口只包含一个 run() 方法，在这个方法中，要放置应用程序代码。要执行这个代码，需要实例化实现类的对象，然后在创建新 Thread 时，把对象作为构造函数的参数传入。然后调用新创建的线程对象的 start() 方法，开始执行控制的新线程。

Back to top

线程安全性和同步

如果 Java 对象中的某个方法能够安全地运行在多线程环境中，那么就称该方法是 线程安全的。要获得这种安全性，必须有一种机制，通过该机制，运行同一方法的多个线程就能够同步其操作，这样，在访问相同的对象或代码行时，就会只允许一个线程被处理。这种同步要求线程使用叫作 信号 的对象彼此进行沟通。

有一种类型的信号叫作 互斥信号 或 互斥体。顾名思义，这个信号对象的拥有权是互斥的，也就是说，在任意指定时间，只有一个线程能够拥有互斥体。其他想获得所有权的线程会被阻塞，它们必须等待，直到拥有互斥体的线程释放互斥体。如果多个线程按顺序排队等候同一互斥体，那么在当前拥有者释放它的时候，只有一个等候线程能够得到它；其他线程将继续阻塞。

在 1970 年代初，C.A.R. Hoare 和其他人共同开发了一个叫作 监视器 的概念（请参阅 参考资料）。 一个 监视器 就是一个代码主体，它的访问受到互斥体的保护。任何想执行这个代码的线程，都必须在代码块顶部得到关联的互斥体，然后在底部再释放它。因为在指定时间只有一个线程能够拥有互斥体，所以这就有效地保证了只有拥有它的线程才能执行监视器的代码块。（受保护的代码不需要相邻 —— 例如，Java 语言中的每个对象都有一个与之关联的监视器。）

任何想在 Java 语言中进行线程编程的开发人员，都会立即把上面的内容当成 synchronized 关键字所带来的效果。可以确保包含在 synchronized 块中的 Java 代码在指定时间只被一个线程执行。在内部，可以由运行时将 synchronized 关键字转换成某一种情况：所有的竞争线程都试图获得与它们（指线程）正在操作的对象实例关联的那个（惟一的一个）互斥体。成功得到互斥体的线程将运行代码，然后在退出 synchronized 块时释放互斥体。

等候和通知

wait/notify 构造在 Java 语言的线程间通信机制中也扮演了重要的角色。基本的想法是：一个线程需要的某个条件可以由另外一个线程促成。这样，条件的 wait 就可以得到满足。一旦条件为真，那么引发条件的线程就会 notify 等候线程苏醒，并从中止的地方继续进行。

wait/notify 机制要比 synchronized 机制更难理解和判断。要想判断出使用 wait/notify 的方法的行为逻辑，就要求判断出使用它的所有方法的逻辑。一次判断一个方法，把该方法和其他方法隔离开，是对整体系统行为得出错误结论的可靠方式。显然，这样做的复杂性会随着要判断的方法的数量增长而迅速提高。

Back to top

线程状态

我前面提到过，必须调用新创建的线程的 start() 方法来启动它的执行。但是，仅仅是调用 start() 方法并不意味着线程会立即开始运行。这个方法只是把线程的状态从 new 变成 runnable。只有在操作系统真正安排线程执行的时候，线程状态才会变成 running （从 runnable）。

典型的操作系统支持两种线程模型 —— 协作式和抢占式。在协作式 模型中，每个线程对于自己对 CPU 的控制权要保留多久、什么时候放弃有最终意见。在这个模型中，因为可能存在某个无赖线程占住控制权不放，所以其他线程可能永远无法得到运行。在 抢占式 模型中，操作系统本身采用基于时钟“滴答”的计时器，基于这个计时器，操作系统可以强制把控制权从一个线程转移到另外一个线程。在这种情况下，决定哪个线程会得到下一次控制权的调度策略就有可能基于各种指标，例如相对优先级、某个线程已经等待执行的时间长短，等等。

如果出于某些原因，处在 running 状态的线程需要等候某个资源（例如，等候设备的输入数据到达，或者等候某些条件已经设定的通知），或者在试图获得互斥体的时候被阻塞，因此线程决定睡眠，那么这时它可以进入 blocked 状态。当睡眠周期到期、预期输入到达，或者互斥体当前的拥有者将其释放并通知等候线程可以再次夺取互斥体时，阻塞的线程重新进入 runnable 状态。

当线程的 run() 方法完成时（或者正常返回，或者抛出 RuntimeException 这样的未检测到异常），线程将终止。这时，线程的状态是 dead。当线程死亡时，就不能通过再次调用它的 start() 方法来重新启动它，如果那么做，则会抛出 InvalidThreadStateException 异常。

Back to top

四个常见缺陷

正如我已经展示过的，Java 语言中的多线程编程是通过语言支持的大量精心设计的构造实现的。另外，还设计了大量设计模式和指导原则，来帮助人们了解这种复杂性带来的许多缺陷。除此之外，多线程编程会很容易地在不经意间把细微的 bug 带进多线程代码，而且更重要的是，这类问题分析和调试起来非常困难。接下来要介绍的是用 Java 语言进行多线程编程时将会遇到（或者可能已经遇到过）的最常见问题的一个列表。

争用条件

据说 争用条件 存在于这样的系统中：多个线程之间存在对共享资源的竞争，而胜出者决定系统的行为。Allen Holub 在他撰写的文章 “programming Java threads in the real world” （请参阅 参考资料）提供了一个带有这样 bug 的简单的多线程程序示例。在冲突的访问请求之间进行不正确同步的另一个更可怕的后果是 数据崩溃，此时，共享的数据结构有一部分由一个线程更新，而另一部分由另一个线程更新。在这种情况下，系统的行为不是按照胜出线程的意图进行，系统根本不按照任何一个线程的意图行动，所以两个线程最后都将以失败告终。

死锁

死锁 的情况是指：线程由于等候某种条件变成真（例如资源可以使用），但是它等候的条件无法变成真，因为能够让条件变成真的线程在等候第一个线程“做某件事”。这样，两个线程都在等候对方先采取第一步，所以都无法做事。请参阅 Allen Holub 撰写的文章 （请参阅 参考资料），以获得在多线程 Java 代码中如何发生死锁的示例。

活动锁

活动锁 与 死锁 不同，它是在线程实际工作的时候发生的，但这时还没有完成工作。这通常是在两个线程交叉工作的时候发生，所以第一个线程做的工作被另一个线程取消。一个简单的示例就是：每个线程已经拥有了一个对象，同时需要另外一个线程拥有的另外一个对象。可以想像这样的情况：每个线程放下自己拥有的对象，捡起另外一个线程放下的对象。显然，这两个线程会永远都运行在上锁这一步操作上，结果是什么都做不成。（常见的真实示例就是，两个人在狭窄的走廊相遇。每个人都礼貌地让到另一边让对方先行，但却在相同的时间都让到同一边了，所以两个人还都没法通过。这种情况会持续一些时间，然后两个人都从这边闪到那边，结果还是一点进展也没有。）

资源耗尽

资源耗尽，又称为 线程耗尽，是 Java 语言的 wait/notify 原语无法保证 live-ness 的后果。Java 强制这些方法要拥有它们等候或通知的对象的锁。在某个线程上调用的 wait() 方法在开始等候之前必须释放监视器锁，然后在从方法返回并获得通知之后，必须再次重新获得锁。因此，Java 语言规范（请参阅 参考资料） 在锁本身之外，还描述了一套与每个对象相关的 等候集（wait set）。一旦线程释放了对象上的锁（在 wait 的调用之后），线程就会放在这个等候集上。

多数 JVM 实现把等候线程放在队列中。所以，如果在通知发生的时候，还有其他线程在等候监视器，那么就会把一个新线程放在队列尾部，而它并不是下一个获得锁的线程。所以，等到被通知线程实际得到监视器的时候，通知该线程的条件可能已经不再为真，所以它不得不再次 wait。这种情况可能无限持续下去，从而造成运算工作上浪费（因为要反复把该线程放入等候集和从中取出）和线程耗尽。

贪心哲学家的寓言

演示这种行为的原型示例是 Peter Welch 教授描述的“聪明人没有鸡肉”（请参阅 参考资料）。在这个场景中考虑的系统是一所由五位哲学家、一位厨师和一个食堂组成的学院。所有的哲学家（除了一位）都要想想（在代码示例中，考虑的时间是 3 秒）之后才去食堂取饭。而“贪心的”哲学家则不想把时间浪费在思考上 —— 相反，他一次又一次地回到食堂，企图拿到鸡肉来吃。

厨师按照一批四份的定量准备鸡肉，每准备好一批，就送到食堂。贪心的哲学家不断地去厨房，但他总是错过食物！事情是这样的：他第一次到的时候，时间太早，厨师还没开火。因此贪心的哲学家只好干等着（通过 wait() 方法调用）。在开饭的时候（通过 notify() 方法调用），贪心的哲学家再一次回到食堂排队等候。但是这次，在他前来等候的时候，他的四位同事已经到了，所以他在食堂队列中的位置在他们后面。他的同事们把厨房送来的一批四份鸡肉全部拿走了，所以贪心的哲学家又要在一边等着了。 可怜（也可能是公平的） ，他永远处在这个循环之外。

Back to top

验证的问题

一般来说，很难按照普通的规范对 Java 编程的多线程程序进行验证。同样，开发自动化工具对于常见的并发问题（例如死锁、活动锁和资源耗尽）进行完整而简单的分析也不太容易——特别是在任意 Java 程序中或者在缺乏并发的正式模型的时候。

更糟的是，并发性问题出了名的变化多端、难于跟踪。每个 Java 开发人员都曾经听说过（或者亲自编写过）这样的 Java 程序：经过严格分析，而且正常运行了相当一段时间，没有表现出潜在的死锁。然后突然有一天，问题发生了，结果弄得开发团队经历许多的不眠之夜来试图发现并修补根本原因。

一方面，多线程 Java 程序容易发生的错误非常不明显，有可能在任意什么时候发生。另一方面，完全有可能这些 bug 在程序中从不出现。问题取决于一些不可知的因素。多线程程序的复杂本质，使得人们很难有效地对其进行验证。没有一套现成的规则可以找出多线程代码中的这类问题，也无法确切地证明这些问题不存在，这些导致许多 Java 开发人员完全避开多线程应用程序的设计和开发，即使用并发和并行的方式对系统进行建模会非常棒，他们也不使用多线程。

确实想进行多线程编程的开发人员通常准备好了以下一个或两个解决方案（至少是一部分）：

• 长时间艰苦地测试代码，找出所有出现的并发性问题，诚心地希望到应用程序真正运行地时候已经发现并修复了所有这类问题。
  
  
• 大量运行设计模式和为多线程编程建立的指导原则。但是，这类指导原则只在整个系统都按照它们的规范设计的时候才有效，没有设计规则能够覆盖所有类型的系统。

虽然知道的人不多，但是对于编写（然后验证）正确的多线程应用程序这一问题，还有第三个选项。使用称为通信顺序进程（ Communicating Sequential Processes，CSP）的精确的线程同步的数学理论，可以在设计时最好地处理死锁和活动锁之类的问题。CSP 由 C.A.R. Hoare 与 20 世纪 70 年代后期设计，CSP 提供了有效的方法，证明用它的构造和工具构建的系统可以免除并发的常见问题。

Back to top

第 1 部分的结束语

在这份面向 Java 程序员的 CSP 全面介绍的第一部分中，我把重点放在克服多线程应用程序开发常见问题的第一步上，即了解这些问题。我介绍了 Java 平台上目前支持的多线程编程构造，解释了它们的起源，讨论了这类程序可能会有的问题。我还解释了用正式理论在任意的、大型的和复杂的应用程序中清除这些问题（即竞争冒险、死锁、活动锁和资源耗尽）或者证明这些问题不存在的困难。

在 第 2 部分 中，有了这个基本框架在脑子里，我将介绍 CSP 和它基于 Java 的实现 —— JCSP 库。您会发现，CSP 是一个复杂的数学理论，有大量强大的应用程序 （我会在 第 3 部分 将讨论一些更高级的程序），其中包括多线程编程常见问题的解决方法。

要想了解 JCSP 如何把 CSP 的精华提炼成一个好理解的 Java 构造框架，那么请您现在就跳转至 “第 2 部分：用 JCSP 进行并发编程”。

致谢

我非常感谢 Peter Welch 教授在我编写这个文章系列期间给予的鼓励。他在百忙之中抽出时间，非常细致地审阅了本文的草稿，并提供了许多宝贵的提高本系列质量和准确性的建议。文章中如果还存在错误，那么都是由于我的原因！我在文章中使用的示例基于或来自 JCSP 库的 javadoc 中提供的示例，以及 JCSP Web 站点上提供的 Powerpoint 演示文稿。这两个来源都提供了大量将探索的信息。

Resources

• Brian Goetz 撰写的由三部分组成的 “Threading lightly”系列是解决 Java 平台上同步问题的巧妙而系统的方法。（developerWorks，2001 年 7 月）。
  
  
  
  
• Brian 的 Java theory and practice 专栏定期介绍多线程编程。 “Concurrency made simple (sort of) ”（developerWorks，2002 年 11 月）首次研究了 util.concurrent，这是一个广泛采用的用于 Java 平台的并发工具包。
  
  
  
  
• Allen Holub 编程了大量 Java 平台多线程编程的内容。他撰写的“Programming Java threads in the real world” （JavaWorld，1998 年 10 月）提供了线程问题的示例，例如争用条件和死锁。
  
  
  
  
• 还请参阅 Holub 有名的苛评“If I were king: A proposal for fixing the Java programming language's threading problems”（developerWorks，2000 年 10 月）。
  
  
  
  
• 英国坎特伯雷市肯特大学的 Peter Welch 教授设计了“Wot, no chickens?”问题，举例说明 Java 程序中的资源耗尽。
  
  
  
  
• C.A.R. Hoare 开创性的论文“Communicating Sequential Processes”将通信顺序进程的并行组合作为一种基本的编程构造方法进行介绍（Communications of the ACM Archive，1978）。
  
  
  
  
• Hoare 撰写的“Monitors:?an operating system structuring concept” （Communications of the ACM Archive,1974）第一次向全世界介绍了监视器的概念，他采用了非常有表现力的示例，包括单一资源调度器、有边界缓存、闹钟、缓冲池、磁头优化器，以及一个有问题的读取器和写入器版本。
  
  
  
  
• Enterprise JavaBeans 是若干个试图向 Java 程序员隐藏多线程编程复杂性的框架之一。
  
  
  
  
• 请参阅 Java Language Specification。
  
  
  
  
• 在 developerWorks 的 Java 技术专区 中，可以找到 Java 编程各方面的文章。
  
  
• 请参阅 Developer Bookstore，以获得技术书籍的完整清单，其中包括数百本 Java 相关主题 的书籍。
  
  
  
  
• 还请参阅 Java 技术专区教程页，从 developerWorks 获得免费的、以 Java 为重点的教程。
  

About the author

		Abhijit Belapurkar 从印度德里市的印度理工学院（IIT）获得了计算机科学方面的理工学士学位。在过去的 11 年中，他一直工作在分布式应用程序的架构和信息安全领域，并在使用 Java 平台构建 N-层应用程序方面拥有大约 6 年的经验。他当前在印度班加罗尔市的 Infosys Technologies Limited 担任 J2EE 方面的高级技术架构师。

转自：http://www-128.ibm.com/developerworks/cn/java/j-jtp1126/

对于每个项目，象许多其它应用程序基础结构服务一样，通常无需从头重新编写并发实用程序类（如工作队列和线程池）。这个月，Brian Goetz 将介绍 Doug Lea 的 util.concurrent 包，这是一个高质量的、广泛使用的、并发实用程序的开放源码包。可以通过本文的 论坛提出您对本文的想法，以飨笔者和其他读者。（您也可以单击本文顶部或底部的“讨论”参加论坛。）

当项目中需要 XML 解析器、文本索引程序和搜索引擎、正则表达式编译器、XSL 处理器或 PDF 生成器时，我们中大多数人从不会考虑自己去编写这些实用程序。每当需要这些设施时，我们会使用商业实现或开放源码实现来执行这些任务原因很简单 ― 现有实现工作得很好，而且易于使用，自己编写这些实用程序会事倍功半，或者甚至得不到结果。作为软件工程师，我们更愿意遵循艾萨克・牛顿的信念 ― 站在巨人的肩膀之上，有时这是可取的，但并不总是这样。（在 Richard Hamming 的 Turing Award 讲座中，他认为计算机科学家的“自立”要更可取。）

探究重复发明“车轮”之原因

对于一些几乎每个服务器应用程序都需要的低级应用程序框架服务（如日志记录、数据库连接合用、高速缓存和任务调度等），我们看到这些基本的基础结构服务被一遍又一遍地重写。为什么会发生这种情况？因为现有的选择不够充分，或者因为定制版本要更好些或更适合手边的应用程序，但我认为这是不必要的。事实上，专为某个应用程序开发的定制版本常常并不比广泛可用的、通用的实现更适合于该应用程序，也许会更差。例如，尽管您不喜欢 log4j，但它可以完成任务。尽管自己开发的日志记录系统也许有一些 log4j 所缺乏的特定特性，但对于大多数应用程序，您很难证明，一个完善的定制日志记录包值得付出从头编写的代价，而不使用现有的、通用的实现。可是，许多项目团队最终还是自己一遍又一遍地编写日志记录、连接合用或线程调度包。

表面上看起来简单

我们不考虑自己去编写 XSL 处理器的原因之一是，这将花费大量的工作。但这些低级的框架服务表面上看起来简单，所以自己编写它们似乎并不困难。然而，它们很难正常工作，并不象开始看起来那样。这些特殊的“轮子”一直处在重复发明之中的主要原因是，在给定的应用程序中，往往一开始对这些工具的需求非常小，但当您遇到了无数其它项目中也存在的同样问题时，这种需求会逐渐变大。理由通常象这样：“我们不需要完善的日志记录／调度／高速缓存包，只需要一些简单的包，所以只编写一些能达到我们目的的包，我们将针对自己特定的需求来调整它”。但情况往往是，您很快扩展了所编写的这个简单工具，并试图添加再添加更多的特性，直到编写出一个完善的基础结构服务。至此，您通常会执著于自己所编写的程序，无论它是好是坏。您已经为构建自己的程序付出了全部的代价，所以除了转至通用的实现所实际投入的迁移成本之外，还必须克服这种“已支付成本”的障碍。

回页首

并发构件的价值所在

编写调度和并发基础结构类的确要比看上去难。Java 语言提供了一组有用的低级同步原语： wait() 、 notify() 和 synchronized ，但具体使用这些原语需要一些技巧，需要考虑性能、死锁、公平性、资源管理以及如何避免线程安全性方面带来的危害等诸多因素。并发代码难以编写，更难以测试 ― 即使专家有时在第一次时也会出现错误。 Concurrent Programming in Java（请参阅 参考资料）的作者 Doug Lea 编写了一个极其优秀的、免费的并发实用程序包，它包括并发应用程序的锁、互斥、队列、线程池、轻量级任务、有效的并发集合、原子的算术操作和其它基本构件。人们一般称这个包为 util.concurrent （因为它实际的包名很长），该包将形成 Java Community Process JSR 166 正在标准化的 JDK 1.5 中 java.util.concurrent 包的基础。同时， util.concurrent 经过了良好的测试，许多服务器应用程序（包括 JBoss J2EE 应用程序服务器）都使用这个包。

填补空白

核心 Java 类库中略去了一组有用的高级同步工具（譬如互斥、信号和阻塞、线程安全集合类）。Java 语言的并发原语 ― synchronization 、 wait() 和 notify() ― 对于大多数服务器应用程序的需求而言过于低级。如果要试图获取锁，但如果在给定的时间段内超时了还没有获得它，会发生什么情况？如果线程中断了，则放弃获取锁的尝试？创建一个至多可有 N 个线程持有的锁？支持多种方式的锁定（譬如带互斥写的并发读）？或者以一种方式来获取锁，但以另一种方式释放它？内置的锁定机制不直接支持上述这些情形，但可以在 Java 语言所提供的基本并发原语上构建它们。但是这样做需要一些技巧，而且容易出错。

服务器应用程序开发人员需要简单的设施来执行互斥、同步事件响应、跨活动的数据通信以及异步地调度任务。对于这些任务，Java 语言所提供的低级原语很难用，而且容易出错。 util.concurrent 包的目的在于通过提供一组用于锁定、阻塞队列和任务调度的类来填补这项空白，从而能够处理一些常见的错误情况或者限制任务队列和运行中的任务所消耗的资源。

回页首

调度异步任务

util.concurrent 中使用最广泛的类是那些处理异步事件调度的类。在本专栏七月份的文章中，我们研究了 thread pools and work queues，以及许多 Java 应用程序是如何使用“ Runnable 队列”模式调度小工作单元。

可以通过简单地为某个任务创建一个新线程来派生执行该任务的后端线程，这种做法很吸引人：

new Thread(new Runnable() { ... } ).start();

虽然这种做法很好，而且很简洁，但有两个重大缺陷。首先，创建新的线程需要耗费一定资源，因此产生出许许多多线程，每个将执行一个简短的任务，然后退出，这意味着 JVM 也许要做更多的工作，创建和销毁线程而消耗的资源比实际做有用工作所消耗的资源要多。即使创建和销毁线程的开销为零，这种执行模式仍然有第二个更难以解决的缺陷 ― 在执行某类任务时，如何限制所使用的资源？如果突然到来大量的请求，如何防止同时会产生大量的线程？现实世界中的服务器应用程序需要比这更小心地管理资源。您需要限制同时执行异步任务的数目。

线程池解决了以上两个问题 — 线程池具有可以同时提高调度效率和限制资源使用的好处。虽然人们可以方便地编写工作队列和用池线程执行 Runnable 的线程池（七月份那篇专栏文章中的示例代码正是用于此目的），但编写有效的任务调度程序需要做比简单地同步对共享队列的访问更多的工作。现实世界中的任务调度程序应该可以处理死线程，杀死超量的池线程，使它们不消耗不必要的资源，根据负载动态地管理池的大小，以及限制排队任务的数目。为了防止服务器应用程序在过载时由于内存不足错误而造成崩溃，最后一项（即限制排队的任务数目）是很重要的。

限制任务队列需要做决策 ― 如果工作队列溢出，则如何处理这种溢出？抛弃最新的任务？抛弃最老的任务？阻塞正在提交的线程直到队列有可用的空间？在正在提交的线程内执行新的任务？存在着各种切实可行的溢出管理策略，每种策略都会在某些情形下适合，而在另一些情形下不适合。

回页首

Executor

Util.concurrent 定义一个 Executor 接口，以异步地执行 Runnable ，另外还定义了 Executor 的几个实现，它们具有不同的调度特征。将一个任务排入 executor 的队列非常简单：

Executor executor = new QueuedExecutor();
...
Runnable runnable = ... ;
executor.execute(runnable);

最简单的实现 ThreadedExecutor 为每个 Runnable 创建了一个新线程，这里没有提供资源管理 ― 很象 new Thread(new Runnable() {}).start() 这个常用的方法。但 ThreadedExecutor 有一个重要的好处：通过只改变 executor 结构，就可以转移到其它执行模型，而不必缓慢地在整个应用程序源码内查找所有创建新线程的地方。 QueuedExecutor 使用一个后端线程来处理所有任务，这非常类似于 AWT 和 Swing 中的事件线程。 QueuedExecutor 具有一个很好的特性：任务按照排队的顺序来执行，因为是在一个线程内来执行所有的任务，任务无需同步对共享数据的所有访问。

PooledExecutor 是一个复杂的线程池实现，它不但提供工作线程（worker thread）池中任务的调度，而且还可灵活地调整池的大小，同时还提供了线程生命周期管理，这个实现可以限制工作队列中任务的数目，以防止队列中的任务耗尽所有可用内存，另外还提供了多种可用的关闭和饱和度策略（阻塞、废弃、抛出、废弃最老的、在调用者中运行等）。所有的 Executor 实现为您管理线程的创建和销毁，包括当关闭 executor 时，关闭所有线程，另外还为线程创建过程提供了 hook，以便应用程序可以管理它希望管理的线程实例化。例如，这使您可以将所有工作线程放在特定的 ThreadGroup 中，或者赋予它们描述性名称。

回页首

FutureResult

有时您希望异步地启动一个进程，同时希望在以后需要这个进程时，可以使用该进程的结果。 FutureResult 实用程序类使这变得很容易。 FutureResult 表示可能要花一段时间执行的任务，并且可以在另一个线程中执行此任务， FutureResult 对象可用作执行进程的句柄。通过它，您可以查明该任务是否已经完成，可以等待任务完成，并检索其结果。可以将 FutureResult 与 Executor 组合起来；可以创建一个 FutureResult 并将其排入 executor 的队列，同时保留对 FutureResult 的引用。清单 1 显示了一个一同使用 FutureResult 和 Executor 的简单示例，它异步地启动图像着色，并继续进行其它处理：

清单 1. 运作中的 FutureResult 和 Executor

  Executor executor = ...
   ImageRenderer renderer = ...
       FutureResult futureImage = new FutureResult();
       Runnable command = futureImage.setter(new Callable() {
          public Object call() { return renderer.render(rawImage); }
       });
    // start the rendering process
       executor.execute(command);
       // do other things while executing
       drawBorders();
       drawCaption();
    // retrieve the future result, blocking if necessary
       drawImage((Image)(futureImage.get())); // use future

FutureResult 和高速缓存

还可以使用 FutureResult 来提高按需装入高速缓存的并发性。通过将 FutureResult 放置在高速缓存内，而不是放置计算本身的结果，可以减少持有高速缓存上写锁的时间。虽然这种做法不能加快第一个线程把某一项放入高速缓存，但它 将减少第一个线程阻塞其它线程访问高速缓存的时间。它还使其它线程更早地使用结果，因为它们可以从高速缓存中检索 FutureTask 。清单 2 显示了使用用于高速缓存的 FutureResult 示例：

清单 2. 使用 FutureResult 来改善高速缓存

public class FileCache {
  private Map cache = new HashMap();
  private Executor executor = new PooledExecutor();
  public void get(final String name) {
    FutureResult result;
    synchronized(cache) {
      result = cache.get(name);
      if (result == null) {
        result = new FutureResult();
        executor.execute(result.setter(new Callable() {
          public Object call() { return loadFile(name); }
        }));
        cache.put(result);
      }
    }
    return result.get();
  }
}

这种方法使第一个线程快速地进入和退出同步块，使其它线程与第一个线程一样快地得到第一个线程计算的结果，不可能出现两个线程都试图计算同一个对象。

回页首

结束语

util.concurrent 包包含许多有用的类，您可能认为其中一些类与您已编写的类一样好，也许甚至比从前还要好。它们是许多多线程应用程序的基本构件的高性能实现，并经历了大量测试。 util.concurrent 是 JSR 166 的切入点，它将带来一组并发性的实用程序，这些实用程序将成为 JDK 1.5 中的 java.util.concurrent 包，但您不必等到那时侯才能使用它。在以后的文章中，我将讨论 util.concurrent 中一些定制的同步类，并研究 util.concurrent 和 java.util.concurrent API 中的不同之处。

参考资料

• 您可以参阅本文在 developerWorks 全球站点上的 英文原文.
  
  
• 请参加本文的 论坛。（您也可以单击本文顶部或底部的 讨论参加论坛。）
  
  
• Doug Lea 的 Concurrent Programming in Java, Second Edition 是一本围绕 Java 应用程序中多线程编程方面可能出现的难解问题的权威著作。
  
  
  
• 下载 util.concurrent 包。
  
  
  
• PooledExecutor 的 javadoc 页面说明了所提供的各种队列、溢出和关闭选项。
  
  
  
• JSR 166 正在对 JDK 1.5 的 util.concurrent 库进行标准化。
  
  
  
• 请在 Brian 的 Java theory and practice专栏 阅读所有文章。七月份的文章 thread pools and work queues与九月份的文章 线程泄露尤其适用于本文。
  
  
  
• 在 developerWorksJava 技术专区 可以找到数百篇与 Java 技术相关的参考资料。
  

关于作者

		Brian Goetz 是一位软件顾问，在过去的 15 年里他一直是一位专业软件开发人员。他是 Quiotix 的首席顾问，该公司是位于加利福尼亚 Los Altos 的软件开发和咨询公司。请在业界流行的出版物上查阅 Brian 已发表的和即将发表的文章。

今天是冬至了，回来看看我的空间

昨晚，一个朋友说来到这里，但是发现很久没有更新了，问我怎么回事。其实，我不是说过了吗，我最近写blog都是在163那里，而这里都比较少来了，呵呵

今天，发生了不少事情，其实

早上发现自己居然还有2本书是过期了，麻烦了，又要罚钱了！~……

中午去还了一本，打算下午再去还一本的，因为还有一本是在宿舍，中午也还不了~~~~~~

中午打电话回家，冬至嘛，呵呵！~……居然发现，我和爸爸之间也没有什么说，除了每次都差不多的叮咛……

午觉睡得很香，差不多3点才醒过来，然后去了实验室，所以也就忘记还书了，呵呵！~

跟老师讨论了等高线的问题，发现有些细节问题还可以深入研究

4点左右，估计今年的冬至实验室不会有什么活动的了，于是打算跟表哥联系，去他家吃饭。就在这时候，收到LML的短信，这是一条让我非常SX，非常TK的短信？或者，这是一条让我JT的短信？我也不想理她（它）了，让她（它）随风而去吧，gone with the wind!~^

冬至啦，要吃点东西，呵呵！~……打电话给表哥说，去他家吃饭，然后出发

公交车不算很挤，路上也不算很挤，1小时左右就到了，刚刚好可以吃晚饭，呵呵

YKT和DZ两个小家伙还是那么可爱，很可爱，呵呵！~……

回来路上，顺便发短信给LXJ师姐和SJ啦，反正在车上也无聊。说真的，第一次见到师姐的名字“珏”，我的第一反应就是“钰”、“玉”，以为读“yu ”，想不到是读“jue”，惭愧惭愧，呵呵！~……

回来，记得要还书了，还要跑一趟图书馆，汗！~……

顺便在那里看一下书吧，还有报纸，呵呵！~……

其实，像这种流水账式的blog，好像很无聊，但是，当自己有空再看看的时候，你也会发现，其实它也不是很无聊的。当然，有时候，对某个特定问题，也许自己的印象特别深刻，感触特别多，那样，完全可以就那件事而写一份日记

何况，我还是有坚持写日记的，当夜深人静的时候，坐在床上，拿着笔，即使是没有灯光，也可以凭感觉而在日记本上写下自己的心事，而这些心事或者是自己不会放在blog上的，这些，也许才是自己灵魂更深刻的认识与体会，呵呵！~……

转：http://www.swarmagents.com/complex/bottomup/nnintro.htm

人工神经网络简介

作者
Andrew Blais

神经网络也许是计算机计算的将来，一个了解它的好方法是用一个它可以解决的难题来说明。假设给出 500 个字符的代码段，您知道它们是 C、C++、Java 或者 Python。现在构造一个程序，来识别编写这段代码的语言。一种解决方案是构造一个能够学习识别这些语言的神经网络。这篇文章讨论了神经网络的基本功能以及构造神经网络的方法，这样就可以在编码时应用它们了。

根据一个简化的统计，人脑由百亿条神经组成 — 每条神经平均连结到其它几千条神经。通过这种连结方式，神经可以收发不同数量的能量。神经的一个非常重要的功能是它们对能量的接受并不是立即作出响应，而是将它们累加起来，当这个累加的总和达到某个临界阈值时，它们将它们自己的那部分能量发送给其它的神经。大脑通过调节这些连结的数目和强度进行学习。尽管这是个生物行为的简化描述。但同样可以充分有力地被看作是神经网络的模型。

阈值逻辑单元（Threshold Logic Unit，TLU）
理解神经网络的第一步是从对抽象生物神经开始，并把重点放在阈值逻辑单元（TLU）这一特征上。一个 TLU 是一个对象，它可以输入一组加权系数的量，对它们进行求和，如果这个和达到或者超过了某个阈值，输出一个量。让我们用符号标注这些功能，首先，有输入值以及它们的权系数：X₁, X₂, ..., X_n 和 W₁, W_2, ..., W_n。接着是求和计算出的 X_i*W_i ，产生了激发层 a，换一种方法表示：

a = (X1 * W1)+(X2 * W2)+...+(Xi * Wi)+...+ (Xn * Wn)

阈值称为 theta。最后，输出结果 y。当 a >=theta 时 y=1，反之 y=0。请注意输出可以是连续的，因为它也可以由一个 squash 函数 s（或 sigma）判定，该函数的自变量是 a，函数值在 0 和 1 之间，y=s(a)。

图 1. 阈值逻辑单元，带有 sigma 函数（顶部）和 cutoff 函数（底部）

TLU 会分类，假设一个 TLU 有两个输入值，它们的权系数等于 1，theta 值等于 1.5。当这个 TLU 输入 <0,0>、<0,1>、<1,0> 和 <1,1> 时，它的输出分别为 0、0、0、1。TLU 将这些输入分为两组：0 组和 1 组。就像懂得逻辑连接（布尔运算 AND）的人脑可以类似地将逻辑连接的句子分类那样，TLU 也懂得一点逻辑连接之类的东西。

TLU 能够用几何学上的解释来阐明这种现象。它的四种可能输入对应于笛卡尔图的四个点。从等式 X₁*W₁ + X₂*W₂ = theta，换句话说，也即 TLU 转换其分类行为的点开始，它的点都分布在曲线 X₂ = -X₁ + 1.5 上。这个方程的曲线将 4 个可能的输入分成了两个对应于 TLU 分类的区域。这是 TLU 原理中更为普通的实例。在 TLU 有任意数目的 N 个输入的情况下，一组可能的输入对应于 N 维空间中的一个点集。如果这些点可以被超平面 — 换句话说，对应于上面示例中的线的 N 维的几何外形切割，那么就有一组权系数和一个阈值来定义其分类刚好与这个切割相匹配的 TLU。

TLU 的学习原理
既然 TLU 懂得分类，它们就知道素材。神经网络也可假定为可以学习。它们的学习机制是模仿大脑调节神经连结的原理。TLU 通过改变它的权系数和阈值来学习。实际上，从数学的观点看，权系数阈值的特征有点武断。让我们回想一下当 SUM(Xi * Wi) >= theta 时 TLU 在临界点时输出的是 1 而不是 0，这相当于说临界点是出现在 SUM(X_i * W_i)+ (-1 * theta) >= 0 的时候。所以，我们可以把 -1 看成一个常量输入，它的权系数 theta 在学习（或者用技术术语，称为培训）的过程中进行调整。这样，当 SUM(X_i * W_i)+ (-1 * theta) >= 0 时，y=1，反之 y=0。

在培训过程中，神经网络输入：

1. 一系列需要分类的术语示例
2. 它们的正确分类或者目标

这样的输入可以看成一个向量：<X₁, X₂, ..., X_n, theta, t>，这里 t 是一个目标或者正确分类。神经网络用这些来调整权系数，其目的使培训中的目标与其分类相匹配。更确切地说，这是有指导的培训，与之相反的是无指导的培训。前者是基于带目标的示例，而后者却只是建立在统计分析的基础上（请参阅本文随后的参考资料）。权系数的调整有一个学习规则，一个理想化的学习算法如下所示：

清单 1. 理想化的学习算法

fully_trained = FALSE
DO UNTIL (fully_trained):
    fully_trained = TRUE
    FOR EACH training_vector = <X1, X2, ..., Xn, theta, target>::
                               # Weights compared to theta
        a = (X1 * W1)+(X2 * W2)+...+(Xn * Wn) - theta
        y = sigma(a)
        IF y != target:
            fully_trained = FALSE
        FOR EACH Wi:
        MODIFY_WEIGHT(Wi)      # According to the training rule

    IF (fully_trained):
        BREAK

您或许想知道，“哪些培训规则？”有很多，不过有一条似乎合理的规则是基于这样一种思想，即权系数和阈值的调整应该由分式 (t - y) 确定。这个规则通过引入 alpha (0 < alpha < 1) 完成。我们把 alpha 称为学习率。W_i 中的更改值等于 (alpha * (t - y)* Xi)。当 alpha 趋向于 0 时，神经网络的权系数的调整变得保守一点；当 alpha 趋向于 1 时，权系数的调整变得激进。一个使用这个规则的神经网络称为感知器，并且这个规则被称为 感知器学习规则。Rosenblatt 于 1962 年（请参阅参考资料）下的结论是，如果 N 维空间的点集被超平面切割，那么感知器的培训算法的应用将会最终导致权系数的分配，从而定义了一个 TLU，它的超平面会进行需要的分割。当然，为了记起 Keynes，最终我们都切断了与外界的联系，专心思考。但是在计算时间之外，我们仍濒临危险，因为我们需要自己的神经网络对可能输入的空间进行不止一次的切割。

文章开始的难题举例说明了这个，假设给您 N 个字符的代码段，您知道是 C、C++、Java 或者 Python。难的是构造一个程序来标识编写这段代码的语言。用 TLU 来实现需要对可能的输入空间进行不止一次的分割。它需要把空间分成四个区域。每种语言一个区域。把神经网络培训成能实现两个切割就可完成这种工作。第一个切割将 C/C++ 和 Java/Python 分开来，另一个将 C/Java 和 C++/Python 分开。一个能够完成这些切割的网络同样可以识别源代码样本中的语言。但是这需要网络有不同结构，在描述这个不同之处之前，先来简单地看一下实践方面的考虑。

图 2. 初步的（不完整的）感知器学习模型

考虑到排除取得 N 个字符代码所需的计算时间，统计从 ASCII 码的 32 到 127 的范围内可视 ASCII 码字符出现的频率，并在这个统计以及关于代码语言的目标信息的基础上培训神经网络。我们的方法是将字符统计限制到 C、C++、Java 和 Python 代码字符库中最常用的 20 个非字母数字字符。由于关注浮点运算的执行，我们打算用一种规格化因素将这 20 字符统计分开来，并以此培训我们的网络。显然，一个结构上的不同是我们的网络有 20 个输入节点，但这是很正常的，因为我们的描述已经暗示了这种可能性。一个更有意思的区别是出现了一对中间节点，N1 和 N2，以及输出节点数量从两个变成了四个（O1 到 O4）。

我们将培训 N1，这样当它一看到 C 或 C++，设置 y1=1，看到 Java 或 Python，它将设置 y1=0。同理培训 N2，当它一看到 C 或 Java，设置 y2=1，看到 C++ 或 Python，设置 y2=0。此外，N1 和 N2 将输出 1 或 0 给 Oi。现在如果 N1 看到 C 或 C++，而且 N2 看到 C 或者 Java，那么难题中的代码是 C。而如果 N1 看到 C 或 C++，N2 看到 C++ 或 Python，那么代码就是 C++。这个模式很显而易见。所以假设 Oi 已被培训并根据下面表格的情况输出 1 或 0。

映射到输出（作为布尔函数）的中间节点

如果这样可行的话，我们的网络就可以从代码示例中识别出语言了。这个想法很好。但是在实践上却有些难以置信。不过这种解决方案预示了 C/C++ 和 Java/Python 输入被一个超平面切割了，同样 C/Java 和 C++/Python 输入被另一个切割。这是一个网络培训的解决方案，迂回地解决了这个输入空间的设想。

关于 delta 规则
另一种培训的规则叫做 delta 规则。感知器培训规则是基于这样一种思路 — 权系数的调整是由目标和输出的差分方程表达式决定。而 delta 规则是基于梯度降落这样一种思路。这个复杂的数学概念可以举个简单的例子来表示。从给定的几点来看，向南的那条路径比向东那条更陡些。向东就像从悬崖上掉下来，但是向南就是沿着一个略微倾斜的斜坡下来，向西像登一座陡峭的山，而北边则到了平地，只要慢慢的闲逛就可以了。所以您要寻找的是到达平地的所有路径中将陡峭的总和减少到最小的路径。在权系数的调整中，神经网络将会找到一种将误差减少到最小的权系数的分配方式。

将我们的网络限制为没有隐藏节点，但是可能会有不止一个的输出节点，设 p 是一组培训中的一个元素，t(p,n) 是相应的输出节点 n 的目标。但是，设 y(p,n) 由以上提到的 squash 函数 s 决定，这里 a(p,n) 是与 p 相关的 n 的激活函数，或者用 (p,n) = s( a(p,n) ) 表示为与 p 相关的节点 n 的 squash 过的激活函数。为网络设定权系数（每个 Wi），也为每个 p 和 n 建立 t(p,n) 与 y(p,n) 的差分，这就意味着为每个 p 设定了网络全部的误差。因此对于每组权系数来说有一个平均误差。但是 delta 规则取决于求平均值方法的精确度以及误差。我们先不讨论细节问题，只是说一些与某些 p 和 n 相关的误差：?* square( t(p,n) - y(p,n) )（请参阅参考资料）。现在，对于每个 Wi，平均误差定义如下：

清单 2. 查找平均误差

sum = 0
FOR p = 1 TO M:         # M is number of training vectors
    FOR n = 1 TO N:     # N is number of output nodes
        sum = sum + (1/2 * (t(p,n)-y(p,n))^2)
average = 1/M * sum

delta 规则就是依据这个误差的定义来定义的。因为误差是依据那些培训向量来说明的，delta 规则是一种获取一个特殊的权系数集以及一个特殊的向量的算法。而改变权系数将会使神经网络的误差最小化。我们不需要讨论支持这个算法的微积分学，只要认为任何 Wi 发生的变化都是如下所示就够了：

alpha * s'(a(p,n)) * (t(p,n) - y(p,n)) * X(p,i,n).

X(p,i,n) 是输入到节点 n 的 p 中的第 i 个元素，alpha 是已知的学习率。最后 s'( a(p,n) ) 是与 p 相关的第 n 个节点激活的 squashing 函数的变化（派生）率，这就是 delta 规则，并且 Widrow 和 Stearns （请参阅参考资料）向我们展示了当 alpha 非常小的时候，权系数向量接近某个将误差最小化的向量。用于权系数调节的基于 delta 规则的算法就是如此。

梯度降落（直到误差小到适当的程度为止）

step 1: for each training vector, p, find a(p)
step 2: for each i, change Wi by:
            alpha * s'(a(p,n)) * (t(p,n)-y(p,n)) * X(p,i,n)

这里有一些与感知器算法相区别的重要不同点。显然，在权系数调整的公式下有着完全不同的分析。delta 规则算法总是在权系数上调整，而且这是建立在相对输出的激活方式上。最后，这不一定适用于存在隐藏节点的网络。

反向传播
反向传播这一算法把支持 delta 规则的分析扩展到了带有隐藏节点的神经网络。为了理解这个问题，设想 Bob 给 Alice 讲了一个故事，然后 Alice 又讲给了 Ted，Ted 检查了这个事实真相，发现这个故事是错误的。现在 Ted 需要找出哪些错误是 Bob 造成的而哪些又归咎于 Alice。当输出节点从隐藏节点获得输入，网络发现出现了误差，权系数的调整需要一个算法来找出整个误差是由多少不同的节点造成的，网络需要问，“是谁让我误入歧途？到怎样的程度？如何弥补？”这时，网络该怎么做呢？

图 3：“代码识别”反向传播的神经网络

反向传播算法同样来源于梯度降落原理，在权系数调整分析中的唯一不同是涉及到 t(p,n) 与 y(p,n) 的差分。通常来说 W_i 的改变在于：

alpha * s'(a(p,n)) * d(n) * X(p,i,n)

其中 d(n) 是隐藏节点 n 的函数，让我们来看（1）n 对任何给出的输出节点有多大影响；（2）输出节点本身对网络整体的误差有多少影响。一方面，n 影响一个输出节点越多，n 造成网络整体的误差也越多。另一方面，如果输出节点影响网络整体的误差越少，n 对输出节点的影响也相应减少。这里 d(j) 是对网络的整体误差的基值，W(n,j) 是 n 对 j 造成的影响，d(j) * W(n,j) 是这两种影响的总和。但是 n 几乎总是影响多个输出节点，也许会影响每一个输出结点，这样，d(n) 可以表示为：

SUM(d(j)*W(n,j))

这里 j 是一个从 n 获得输入的输出节点，联系起来，我们就得到了一个培训规则，第 1 部分：在隐藏节点 n 和输出节点 j 之间权系数改变，如下所示：

alpha * s'(a(p,n))*(t(p,n) - y(p,n)) * X(p,n,j)

第 2 部分：在输入节点 i 和输出节点 n 之间权系数改变，如下所示：

alpha * s'(a(p,n)) * sum(d(j) * W(n,j)) * X(p,i,n)

这里每个从 n 接收输入的输出节点 j 都不同。关于反向传播算法的基本情况大致如此。

将 Wi 初始化为小的随机值。

使误差小到适当的程度要遵循的步骤

通常把第 1 步到第 3 步称为正向传播，把第 4 步到第 7 步称为反向传播。反向传播的名字由此而来。

识别成功
在掌握了反向传播算法后，可以来看我们的识别源代码样本语言的难题。为了解决这个问题，我们提供了 Neil Schemenauer 的 Python 模型 bpnn（请参阅参考资料）。用它的模型解决问题真是难以置信的简单，在我们的类 NN2 里定制了一个类 NN，不过我们的改变只是调整了表达方式和整个过程的输出，并没有涉及到算法。基本的代码如下所示：

清单 3：用 bpnn.py 建立一个神经网络

# Create the network (number of input, hidden, and training nodes)
net = NN2(INPUTS, HIDDEN, OUTPUTS) 

# create the training and testing data
trainpat = []  
testpat = []  
for n in xrange(TRAINSIZE+TESTSIZE):  
    #... add vectors to each set 

# train it with some patterns 
net.train(trainpat, iterations=ITERATIONS, N=LEARNRATE, M=MOMENTUM)  

# test it 
net.test(testpat)  

# report trained weights 
net.weights()

当然我们需要输入数据，实用程序 code2data.py 提供了这个功能。它的界面很直观：只要将一堆扩展名各不相同的文件放到一个子目录 ./code 中，然后运行这个实用程序，并列举那些扩展名作为命令选项。例如：

python code2data.py py c java

您得到的是一堆 STDOUT 上的向量，可以把这些向量输入到另一个进程或者重定向到一个文件，它的输出如下所示：

清单 4：Code2Data 的输出向量

0.15 0.01 0.01 0.04 0.07 0.00 0.00 0.03 0.01 0.00 0.00 0.00 0.05 0.00 > 1 0 0
0.14 0.00 0.00 0.05 0.13 0.00 0.00 0.00 0.02 0.00 0.00 0.00 0.13 0.00 > 1 0 0
[...]

让我们回忆一下输入值都是不同特殊字符出现的规格化数目，目标值（在大于号以后）是 YES/NO，它代表包含这些字符的源代码文件的类型，不过对于什么是什么来说，并没有非常明显的东西。数字可以是输入或期望的 任意值，这才是最重要的。

下一步是运行实际的 code_recognizer.py 程序。这需要（在 STDIN 中）像上面一样的向量集。这个程序有一个包，它能够根据实际文件推断出需要多少输入节点（计算在内的和期望的），选择隐藏节点的数目是一个诀窍。对于源代码的识别，6 到 8 个隐藏节点似乎工作得很好。如果打算试验网络从而发现对于这些不同的选项它是如何做的，您可以覆盖命令行中的所有参数，但每一次运行还是会耗费一些时间。值得注意的是， code_recognizer.py 将它的（大的）测试结果文件发送到 STDOUT，而将一些友好的消息放在 STDERR 里。这样在大部分时间里，为了安全保管，您将会把 STDOUT 定向到一个文件，并监视针对进程和结果概要的 STDERR。

清单 5：运行 code_recognizer.py

> code2data.py py c java | code_recognizer.py > test_results.txt 
Total bytes of py-source: 457729 
Total bytes of c-source: 245197 
Total bytes of java-source: 709858 
Input set: ) ( _ . = ; " , ' * / { } : - 0 + 1 [ ] 
HIDDEN = 8 
LEARNRATE = 0.5 
ITERATIONS = 1000 
TRAINSIZE = 500 
OUTPUTS = 3 
MOMENTUM = 0.1 
ERROR_CUTOFF = 0.01 
TESTSIZE = 500 
INPUTS = 20 
error -> 95.519... 23.696... 19.727... 14.012... 11.058... 9.652...  
8.858... 8.236... 7.637... 7.065... 6.398... 5.413... 4.508...  
3.860... 3.523... 3.258... 3.026... 2.818... 2.631... 2.463...  
2.313... 2.180... 2.065... 1.965... 1.877... 1.798... 1.725...  
[...] 
0.113... 0.110... 0.108... 0.106... 0.104... 0.102... 0.100...  
0.098... 0.096... 0.094... 0.093... 0.091... 0.089... 0.088...  
0.086... 0.085... 0.084... 
Success rate against test data: 92.60% 

不断减少误差是个很好的兆头，这至少在一段长时间里所获得的一种进步，且最后的结果必然是深入人心的。就我们的观点而言，网络完成了一项值得尊敬的工作，来识别代码 — 我们将会乐意倾听，对于您的数字向量它是如何做的。

总结
本文从某种程度上阐述了神经网络的基础，使您能够开始在您自己的编码过程中应用它们。我们鼓励您运用在这里学到的东西，并尝试编写您自己的对于这个难题的解决方案。（请参阅于我们的解决方案的参考资料）。

参考资料

• 我们的代码识别程序是基于 Neil Schemenauer 的反向传播模块。
• 关于有指导培训和无指导培训的差异，以及神经网络的一般介绍，请参阅由 D. Michie、D.J. Spiegelhalter 以及 C.C. Taylor 编辑的 Machine Learning, Neural and Statistical Classification，具体内容请参阅第 6 章。
• 关于 Rosenblatt 的感知器结果，请参阅他的 Principles of Neurodynamics, 1962, New York: Spartan Books。
• 关于一些 delta 规则的详细信息，请参阅 Kevin Gurney 的著作 An Introduction to Neural Networks 1997, London: Routledge。也可以参阅 Neural Nets 早期的在线版本。
• 关于 delta 规则的证明，请参阅 B. Widrow 和 S.D. Stearns 的 Adaptive Signal Processing, 1985, New Jersey: Prentice-Hall。
• 关于包含图形界面的感知器的执行，请参阅 Omri Weisman 和 Ziv Pollack 撰写的 The Perceptron 。
• 什么是没有 FAQ 的科目？请参阅在任何时候都适用的 Neural Net FAQ。
• 关于广泛的链接集合，请参阅 The Backpropagator's Review。
• 大学课程对于任何科目的初学者来说都是丰富的信息来源，请参阅课程的 清单。
• Neural Network Package 是一个用 Java 编写的 LGPL 程序包。您可以用它试验这里讲过的所有算法。
• 请参阅 Neural Networks at your Fingertips，它讨论了一组 C 程序包，这些包说明了 Adaline 网络、反向传播、Hopfield 模型以及其它，有一个 The Back-propagation Network 特别有趣，它是一个 C 程序包，说明了一个分析日斑数据的网络。
• 在 Neural Networking Software，您将会找到有友好的图形界面的同时支持 DOS 和 Linux 的神经网络代码。
• NEURObjects 提供了开发神经网络的 C++ 的库文件，它的优点在于面向对象。
• Stuttgart Neural Network Simulator（SNNS），正如名字所示，是用有 GUI 的 C 程序编写的，它的手册内容极为丰富，同时支持友好的 Linux 平台。

ACM入门之STL简介

转自： http://www.math.org.cn/forums/index.php?showtopic=26338

2005年，《自然》杂志发表了Martin A. Nowak and Karl Sigmund （Nature 437, 1291，27 October 2005)合写的一份长篇述评，他们对大量文献做出综合分析后，介绍了近年“进化博弈论”对于“间接互惠”问题的研究进展，并试图解释如何从进化论角度来理解人类社会合作。

******************************************************************************

附图

图1：直接互惠和间接互惠。图a，直接互惠指A帮助B，B也帮助A。图b，间接互惠分，为两种情况：“上行互惠”（左图）建基于最近的一个积极经历——A刚刚受到过帮助，感觉受到推动以帮助B来回报；B由于受到A的帮助，转而帮助C。“下行互惠”（右图）建基于声誉——A已经帮助了B，建立了声誉，因此受到C的帮助。对间接互惠的数学研究显示，自然选择可能支持那种依据声誉的助人的策略。而上行互惠更难以理解，但这种情况的确发生在经济学实验中。无论是上行互惠还是下行互惠，帮助他人的决定都可被认为是一种方向错误的感激行为。就上行互惠而言，受惠者（B，C）因为别人的所作所为被感激从而受惠；就下行互惠而言，受惠者（B，A）得到的感激来自并没有受过他们恩惠的人。　
　
　　在进化论的传统观念中，自然选择机制会有利于那些从牺牲他者利益中获益的强者和自私者。但我们发现，许多生物系统（特别是人类社会）建立在“利他的”与“合作的”互动基础之上。那么，进化论必须解释的一个问题是：自然选择如何可能促进非自私的行为？最近《自然》杂志发表了哈佛大学和维也纳大学的两位学者合写的一份长篇述评，作者诺瓦克（Martin Nowak）和西格蒙德（Karl Sigmund）对几十篇文献做出综合分析，展示出近年“进化博弈论”对于“间接互惠”问题的研究进展，试图从进化论角度来理解人类社会合作。

*****************************************************************************
附图 

图2：声誉的建立。在对间接互惠基础模型的一种自然延伸情境中，施惠人A和受惠人B之间的一个行为受到一群人的观察。观察者、施惠人和受惠人可以将信息告知其他人，既可以向别人传递所发生的行为，也可以转达他们对行为的评价。在此过程中，存在许多误解的可能性：不同的人对行为本身或施惠人的意图可能做出不同的阐释；一些个体可能从不同的来源接受到相互冲突的信息；一些个体则可能一点信息也无法接受；人们还可能拥有不同的评价模式。因此，一个人的声誉并不简单地是一个有目共睹的标签，而其实每个人都有自己的一份关于别人声誉的清单。尽管语言可能有助于将这些清单调正一致，但声誉最终还是取决于观察者的看法。

　　在社会科学和经济学中，“利他行为”的定义是：一个要付出代价的行动，但将所获得的利益转让给他人。在进化生物学中，“代价”和“获益”可以用“达尔文适合度”（darwinian fitness）来衡量。“互惠利他主义”的原始定义是，两个人交换利他行为，因而在总体上双方都获得净受益。在直觉上，我们容易理解那种直接的互利行为——“我帮助你，你也帮助我”。【见图1a】在这种“直接互惠”合作中，双方都获得了好处，没有人遭受损失。比如在著名的“囚徒困境”博弈中，双方同时选择合作比双方同时选择背叛对彼此都更有利。当然，如果只有一方选择合作，而另一方选择背信，则对背信的一方最为有利，对选择合作的一方则最为不利。但这种依靠背叛来获益的动机可以在（可能受到报复的）多次回合的博弈中减弱。因此，只要未来博弈的机率足够高，合作就能够维持。

　　比较难以理解的是那种“间接互惠”——“我帮助你，其他人来帮助我”。【见图1b】当然，我们可以推测，如果大家都知道一个人从不帮助别人，那么他也将得不到任何人的帮助。在这种思路中，间接互惠的基础是“声誉”（reputation），但人们为什么要在乎与己无关的其他人（第三方）的所作所为呢？ 正是在这个问题上，近年来社会科学（特别是经济学）的方法与进化论的方法出现了汇合交叉，形成了新的理论和解释模型，也出现了许多出色的实验，推动了对于“间接互惠”的认识和理解。

***********************************************************************

附图

图3：间接互惠的两个问题。B在先前的表现中有背信的行为，因而其声誉很差。图a，如果A出于B先前的背信而惩罚他，决定不帮助B，那么A的声誉为何应该降低？图b，尽管B是个背信之人，而如果A仍然帮助B，那么A的声誉为何应该升高？因为帮助背信弃义之徒会动摇合作的稳定性。

　　在“间接互惠”的情景设计中，每个人都参加多次会合的博弈，但任何两人之间最多发生一次博弈，因此背信者不会直接遭到受害者的报复。在这种情况下，“报复策略”仍然可能维持某种合作的平衡，如果所有博弈者都使用报复策略，那么就没有人愿意偏离合作。

今天浏览新闻的时候，在网易看到了这么一则新闻，看后总是感觉，太聪明了，虽然，这是一个不大不小的创意，但是，真正的把握它确实是需要不凡的洞察力和创新能力。在这个故事中，我深受启发的是，创意往往是很简单的，留心处处皆学问，呵呵。

以下内容转自网易 ： http://discover.163.com/07/0531/16/3FR8U143000125LI.html

高跟鞋向来是一把令时尚女性既爱又恨的双刃剑。一方面，它能使女性身姿挺拔、体态优美、魅力倍增；另一方面，穿高跟鞋引起的脚部肿痛、走路不稳，以及时刻存在的安全隐患，又让人对它无可奈何。

　　不过，随着可调式高跟鞋的问世，这些恼人的问题将迎刃而解。

　　高低可调

　　据英国媒体２３日报道，美国费城女子劳伦·汉德尔与兄弟戴维·汉德尔共同开发出一种可调节鞋跟高度的高跟鞋。

　　戴维是一名放射线学者。２０多年前，当他乘车经过纽约第五大道时，看到许多女性在上班途中穿着运动鞋，走进办公室前则要匆忙换上放在手提包里的高跟鞋，戴维被这一幕所触动。回到家中，看到儿子正兴奋地玩着变形金刚，他决定运用玩具的拆折原理，为女性发明一种更方便的高跟鞋。

　　戴维在鞋跟中设置一根可以拔出的小钢棒，将它折至足弓下面的鞋底处，鞋跟高度就会降低。需要恢复高跟时，再把它拉直即可。为避免高跟状态时出现鞋跟不稳的情况，他还在鞋跟中安装了联轴装置，确保钢棒会被折到合适位置。

　　通过这样的简单装置，普通高跟鞋３.２５英寸（合３.８厘米）的鞋跟能在转眼间降至１.５英寸（２.５厘米）。“半秒钟的时间，你就能通过一双鞋体会到不同的高度，”戴维的姐姐劳伦说。

　　式样美观

　　在戴维产生制造可调式高跟鞋的构想并完成设计之后，劳伦为鞋设计了２３种式样，从传统样式到露跟女鞋应有尽有。随后，劳伦请意大利的制鞋专家负责鞋的制作。

　　这批名为Camileon的高跟鞋制作过程十分讲究。鞋面采用的是产自意大利的皮革，鞋跟要刷上６层漆以防止磨损和保持光泽。

　　劳伦认为，除去调节高低跟带来的舒适功能外，鞋的美观与否、对女性吸引力如何，同样十分重要。

　　“我希望女士们看到这些鞋后脱口而出的是‘我喜欢这鞋的式样！’”劳伦说，“如今终于有一种鞋能同时满足女士们时尚、舒适和方便的需要。”

　　这款可调式高跟鞋的售价在２６０至３０５美元之间，４个月前开始在美国零售，英国顾客也可以通过网络订购。

　　女性福音

　　据英国《每日邮报》报道，本周英国一项对１０００名女性进行的调查显示，４５％的被调查者在穿高跟鞋时曾经跌倒或扭伤脚踝。不过，另外一份调查表明，尽管对穿高跟鞋带来的不适头疼不已，女士们仍然不愿意为此放弃穿高跟鞋。可调式高跟鞋的出现，无疑为爱美女性带来了福音。

　　劳伦说，在过去，职场女性全天都要穿高跟鞋，非常容易把脚扭伤。如果不愿意这样，她们只能在包里带上一双鞋，需要放松的时候换上。还没有一双鞋能同时解决美观和舒适的问题。

　　“需求是发明的源泉，我们发明出这款鞋完全证明了这个道理，”劳伦说。

　　“鞋问世后的反响令我们始料未及，当我们听到或读到顾客们的赞美之词时，我们感到莫大的满足，觉得为设计和生产这些鞋付出的努力都是值得的，”她说，“我们希望，世界上所有想要或者需要穿高跟鞋的女性都能享受到这种可调式高跟鞋带来的好处。”（蔡莹）

很久没有回家了，现在已经都毕业了，还不回家看看？也说不过去吧！大学四年，除了寒假肯定要回家之外，似乎很少回家了。暑假，我看一下，大一暑假有回，1个月左右，大二暑假没有回家，大三暑假，没有回家，不过赶上中秋和在国庆假期，所以回去了一次。

现在已经是大四毕业了，虽然新的学习，生活早已开始，暑假期间也有很多事情要做。但是我总觉得我应该回家看一看，至少，家中的妹妹非常想我回去和她玩了，呵呵。

所以，我决定，回家一周左右吧，顺便看望一下以前的同学，朋友。呵呵。

The 7 Habits of Highly Effective People

美国公司员工人手一册的书！美国政府机关公务员人手一册的书！美国军队官兵人手一册的书！全球销量超亿册！
史蒂芬·柯维的“高效能人士的七个习惯”对公司的运作系统的发展起到了重要的作用。

习惯一：积极主动的心态（BE PROACTIVE）
即采取积极主动的态度，为自己过去、现在和将来的行为负责，并依据原则及价值观，而非情绪和外在的环境来做出决定。积极主动的人是改变的主动者，他们扬弃被动的受害者角色，发挥人类特有的四项天赋——自觉、良知、想象力和自主意志，由内而外的来创造新的天地。积极主动者选择创造自己的生命，而不是选择被动的逆来顺受，这也是每个人最基本的决定。积极主动的心态使你从生不逢时的自怨自艾中解脱出来，面对现实，不再一味的埋怨和等待，从自身开始积极的思考和行动来创造新的未来。

习惯二：从设定目标开始（BEGIN WITH THE END IN MIND）
所有的事情都经过两次的创造：先是在脑海里酝酿，其次才是实质性的创造。个人、家庭、团队和组织在做任何计划时，均先拟出远景和目标，并据此塑造未来，全身心地投入自己最重视的原则、价值观和目标上。对个人、家庭或组织而言，宗旨和使命是远景的最高形式，它是主要的决策，主宰了所有其它的决定。

习惯三：要事第一的做事原则（PUT FIRST THINGS FIRST）
要事第一，是你的梦想的组织和实践，是你的目标、远景、价值观及要事处理顺序。次要的事不必摆在第一，要事也不能放在第二。无论迫切性如何，个人和组织针对要事而来。重点是：一定要把实现你的目标的要事放在第一位去思考和处理。

习惯四：双赢思维是协作的基础（THINK WIN/WIN）
双赢思维是一种基于互敬，需求互惠的思考框架和心意。目的是为了获得更丰盛的机会、财富和资源，而非你死我活的的敌对式竞争。双赢即非损人利己（赢-输），亦非损己利人（输-赢）。我们的工作伙伴及家庭成员都要从互相依赖的角度来思考（是“我们”而非“我”）。双赢思维鼓励我们共同解决问题，并协助个人找到互惠的解决办法，是资讯、力量、认可和报酬的分享。

习惯五：真正沟通来源于知彼解己（SEEK FIRST TO UNDERSTAND,THEN TO BE UNDERSTOOD）
当我们舍弃说教，改以了解的心态去倾听别人，便能开启真正的沟通，增强彼此的关系。对方获得了解后，会觉得受到尊重和认可，进而开放心扉，坦然而谈，双方对彼此的了解也就更流畅自然。知彼需要仁慈心；认识自己更需要勇气，能平衡两者的关系，则能大幅的提升沟通的效率。

习惯六：协同效应（SYNERGIZE）
协同是创造第三种选择：即非按照我的方式，亦非遵循你的方式，而是第三种远胜过个人之见的办法。它是相互尊重的结果：不但了解彼此，而且彼此称许差距及互补，互相欣赏对方解决问题及掌握机会的手法。个人的力量是团队和家庭协同效应的基础，能使整体获得一加一大于二的成效。实践协同的人际关系和团队建设会扬弃敌对的态度（1+1=1/2），不以妥协为目标（1+1=1），也不仅止于简单的组合（1+1=2），他们要的是创造式的合作（1+1=3或更多）。

习惯七：不断更新（SHAPPEN THE SAW）
不断的更新是，如何在四个基本的生活方面（身体、精神、心智、社会情感）中不断的更新自己。身体：适当运动和营养保持健康；精神：荡涤心灵尘埃，陶冶精神，掌握人生方向；心智：不要停止自我教育，读书和写作是砥砺心智的重要途径；社会情感：历练待人处事之道。习惯七可以提升其他六个习惯的实施效率。对组织而言，七个习惯提供了远景、更新及不断的改善，使组织不至于呈现老化及疲态，并能够迈向新的成长之径。对家庭而言，七个习惯透过固定的个人及家庭活动，使家庭效能升级，使家庭日新月异。

前三个习惯（习惯一到习惯三）是有关个人成功的习惯，可以大幅的提高您的自信。您将更能认清自己的本质、内心深处的价值观以及个人独特的才干和能力。凡是秉持自己的信念而活，就能产生自尊、自重和自制力。至于追求公众成功的三个习惯（习惯四到习惯六），能够帮助您重建以往恶化、甚至断绝了的人际关系。原本不错的交情则更加巩固。习惯七可加强前面六个习惯，时时为您充电，达到真正的独立与成功的互相依赖。

 +++++++++++++++++++++++

高效能人士的7个习惯

 只有事业，是成功吗？
“我曾为自己定下许多目标，也都一一达成。我的事业十分成功，但却牺牲了个人与家庭的幸福，这值得吗？……”；“我要做的事太多了，时间总是不够用，每天都觉得很紧张，匆匆忙忙。我无法过着理想中既充实又自在的生活，而且别无选择……”；“我拥有财富和成就感，可失去了内心的平静……”这无疑是诸多成功人士的生活写照。

 《高效能人士的7个习惯》告诉我们：仅有事业成功只能算成功了一半，唯有兼顾事业、家庭、人际关系、个人成长等人生其它层面的和谐发展才是真正的成功。作者倡导有识之士应告别旧习惯：人的行为总是一再重复，但要取得卓越不只是单一举动，而是要靠良好的习惯。要提升自我，赢得革命性的效果，必须从观念着手，暂时牺牲眼前的安适与利益，树立克服 “惯性”的信念，并且“由内而外全面地造就自己”。作者史蒂芬.柯维认为：观念是态度与行为的根本，观念决定行为，行为形成习惯，而习惯左右着我们的成败，成功其实是习惯使然。

杀鹅取卵到何时？
伊索寓言《鹅和金蛋》讲了这样一个故事：一天，一个很穷的农夫在鹅窝里发现了一个金光闪闪的蛋，更让他喜出望外的是这个蛋是纯金的。这之后，农夫每天都可以从鹅窝里拿到一个金蛋。然而，当他日益富有的时候，他也越来越贪婪，以至于没有耐心等待每天只有一个金蛋，他想一次拿到鹅身体里的所有金子，于是他杀了这只鹅，但结果却是什么都没得到。

在我们的生活和事业中，常常有像愚蠢的农夫那样以牺牲产能（鹅）的代价来提高产出（金蛋）的事。我们往往更关心的是效率而不是效能，为了提高效率而忽视效能，这使我们破坏了取得成果的能力。而惟有产出与产能取得平衡，才能达到卓越的效能。日常活中，足以印证这个道理的例子比比皆是。比如：你曾经因为想多做点儿事而彻夜不眠，结果弄得精疲力竭，身体不适；但倘若是好好睡一觉，第二天则可以精力充沛地做更多的事。产出与产能平衡是效率的精髓，放之四海而皆准，也是成功者七个习惯的基础。

习惯一：别指望谁能推着你走
如果你不向前走，谁又会推你走呢？因此，积极主动的态度，是实现个人愿景的原则。
我们常说：“我不会……，因为遗传……”、“我迟到，因为……”、“我的计划没完成，因为……”我们总是在找借口或是抱怨，在不满中消耗自己的生命。而人类与动物的区别正是人能主动积极地创造、实现梦想，来提升我们的生命品质。所以，有效能的人士为自己的行为及一生所做的选择负责，自主选择应对外界环境的态度和应对方法；

他们致力于实现有能力控制的事情，而不是被动地忧虑那些没法控制或难以控制的事情；他们通过努力提升效能，从而扩展自身的关切范围和影响范围。 积极的心态能让你拥有“选择的自由”。我们虽然不能控制客观环境，但我们可以选择对客观现实做何种反应。积极的涵义不仅仅是采取行动，还代表对自己负责的态度。个人行为取决于自身，而非外部环境，并且人有能力也有责任创造有利的外在环境。

习惯二：忠诚于自己的人生计划
我们经常在人生的道路上迷失方向，因徘徊和迷途消耗了生命。而高效能的人懂得设计自己的未来。他们认真地计划自己要成为什么人，想做些什么，要拥有什么，并且清晰明确地写出，以此作为决策指导。因此，“以终为始”是实现自我领导的原则。这将确保自己的行为与目标保持一致，并不受其他人或外界环境的影响。我们将这个书面计划称之为“使命宣言”。 任何一个存在的社会组织都需要“使命宣言”，任何一个企业或个人也不例外。“使命宣言”需要阶段性地评估以及持续修正和改良。 确立目标后全力以赴，就是我们所说的在正确的时间做正确的事，并把事情做对。为什么很多人成功了反而感到失落？许多人在埋头苦干时，尚未发掘人生的终极目标，只是为忙碌而忙碌着，未曾洞悉自己心灵深处的所欲所求，也不曾审视过自己的人生信条：你到底要做什么？什么是你生命中最重要的？你生活的重心是什么？只有确立了符合价值观的人生目标，才能凝聚意志力，全力以赴且持之以恒地付诸实现，才有可能获得内

心最大的满足。

习惯三：选择不做什么更难
每个人的时间都是有限的，所以要做重要的事，即你觉得有价值并对你的生命价值、最高目标具有贡献的事情；要少做紧急的事，也就是你或别人认为需要立刻解决的事。消防队的最大贡献应是做好防火工作，而不只是忙于到处救火。因此，“要事第一”是自我管理的原则。

有效能的人只会有少量非常重要且需立即处理的紧急、危机事件，他们将工作焦点放在重要但不紧急的事情上，来保持效益与效率的平衡。

“有效管理”是把最重要的事放在第一位的重点管理。先由领导决定什么是重点后，自己掌握住重点并时刻把它放在第一位，以免被感觉、情绪或冲动左右。要想集中精力于当前的要务；就必须先排除次要事情的牵绊，要勇于说“不”。

习惯四：远离角斗场的时代
懂得利人利己的人，把生活看作一个合作的舞台，而不是角斗场。一般人遇事多用二分法：非强即弱，非胜即败。其实，世界给了每个人足够的立足空间，他人之得并非自己之失。因此，“双赢思维”成为人们运用于人际领导的原则。 我们从小就参与各种比赛、考试，培养了一种你赢我输、你死我活的竞争心态。试想一下，谁又甘心在竞赛中认输呢？树立双赢思维就是要在人际交往中不断寻求互利，以达成双方都满意并致力于合作的协议计划。 具有双赢思维的人，往往有三种个性品格：正直、成熟和富足心态。他们忠于自己的感受、价值观和承诺；有勇气表达自己的想法及感觉，能以豁达体谅的心态看待他人的想法及体验；相信世界有足够的发展资源和空间，人人都能共享。

利人利己观念的形成是以诚信、成熟、豁达的品格为基础的。豁达的胸襟源于个人崇高的价值观与自信的安全感，所以不怕与人共名声、共财势，从而肯尝试无限的可能性，充分发挥创造力和宽广的选择空间。

习惯五：换位思考的沟通
如果一位眼科医生为病人配眼镜，他先摘下自己的眼镜让病人试戴，其理由是：“我已经戴了10多年，效果很好，就给你吧，反正我家里还有一副。”那么，谁都知道这是行不通的。如果医生还说：“我戴得很好，你再试试，别心慌。”在病人看到的东西都扭曲了的同时，医生还反复说：“只要有信心，你一定能看得到。” 那就真叫人哭笑不得了。我们常说遇事要将心比心。因此，“知彼解己”是交流的原则。 这位医生尚未诊断就开处方，谁敢领教？但与人沟通时，我们常犯这种不分青红皂白、妄下断语的毛病。因此我必须强调：“了解他人”与“表达自我”是人际沟通不可缺少的要素。首先要了解对方，然后争取让对方了解自己，才是进行有效人际交流的关键，要改变匆匆忙忙去建议或解决问题的倾向。

要培养设身处地的“换位”沟通习惯。欲求别人的理解，首先要理解对方。人人都希望被了解，也急于表达，但却常常疏于倾听。众所周知，有效的倾听不仅可以获取广泛的准确信息，还有助于双方情感的积累。当我们的修养到了能把握自己、保持心态平和、能抵御外界干扰和博采众家之言时，我们的人际关系也就上了一个台阶。

 习惯六：1+1可以大于2
统合综效是对付阻碍成长与改变的最有力途径。助力通常是积极、合理、自觉、符合经济效益的力量；相反，阻力则消极、不合逻辑、情绪化和不自觉。不设法消除阻力的后果就等于向弹簧施加作用力，结果还是要反弹。如果将双赢思维、换位沟通与统合综效原则整合，不仅可以化解阻力，甚至可以化阻力为助力，“统合综效” 就是创造性合作的原则。 集思广益的合作威力无比。许多自然现象显示：全体大于部分的总和。不同植物生长在一起，根部会相互缠绕，土质会因此改善，植物比单独生长更为茂盛；两块砖头所能承受的力量大于单独承受力的总和。这些原理也同样适用于人，但也有例外。只有当人人敞开胸怀，以接纳的心态尊重差异时，才能众志成城。

习惯七：过着身心平衡的生活
身心和意志是我们达成目标的基础，所以有规律地锻炼身心将使我们能接受更大的挑战，静思内省将使人的直觉变得越来越敏感。当我们平衡地在这两方面改善时，则加强了所有习惯的效能。这样我们将成长、变化，并最终走向成功。 人生最值得投资的就是磨练自己。生活与工作都要靠自己，因此自己是最值得珍爱的财富。工作本身并不能给人带来经济上的安全感，而具备良好的思考、学习、创造与适应能力，才能使自己立于不败之地；拥有财富，并不代表有永远的经济保障，拥有创造财富的能力才真正可靠。

以上这七个习惯是相辅相成的。前三个习惯在于我们本身，确立目标就要全力以赴，着重于如何进行个人修炼，由依赖转向独立，实现“个人成功”；第四、五、六个习惯，即建立共赢、换位沟通、集思广益，都将促进团队沟通与合作；而第七个习惯涵盖了前六个，督促我们从身心开始完善。通过培养这些习惯，我们可以循序渐进地获得实质性的变革，成为真正的高效能人士。