并发程序设计



1.顺序程序设计

 顺序程序设计(sequential programming)方法是指，程序模块按语句次序顺序执行，具有如下特性：

 执行的顺序性。

 环境的封闭性。

 执行结果的确定性。

 计算结果的可再现性。



2.并发程序设计

 并发程序设计(concurrent programming)方法是指，将一个程序分成若干可同时执行的程序模块，每个程序模块和它执行时所处理的数据就组成一个进程。具有如下特性：

 并发性——[color=red]进程的执行在时间上可以重叠[/color]，在单处理器系统中可以并发执行；在多处理器系统中可以并行执行。

 共享性——进程可以共享变量，通过引用共享变量就能互相交换信号，[color=red]程序的运行环境不再是封闭的。[/color]

 制约性——进程并发执行或协作完成同一个任务时，会产生相互制约关系，必须对它们并发执行的次序和相对执行速率加以协调。

 交互性——由于进程可共享变量，一个程序的执行可能影响其他程序的执行结果，因此这种交互必须是有控制的，否则会出现不正确的结果。即使程序自身能正确运行，由于程序的运行环境不再是封闭的，[color=red]程序结果仍可能是不确定的[/color]，[color=red]计算过程具有不可再现性。[/color]



 采用并发程序设计的目的是：充分发挥硬件的并行性，消除处理器I/O设备的互等现象，提高系统效率。硬件能并行工作仅仅有了提高效率的可能性，而硬件并行工作的实现还需要软件技术去利用和发挥，这种软件技术就是并发程序设计。在程序设计语言、数据库管理系统和其他一些应用软件中，通过引入线程来改善系统和应用程序的性能。

 并发多线程程序设计是指，在一个进程中包含多个并行执行的控制流。其主要优点是使系统性能获得很大提高，具体表现为快速切换线程、减少系统管理开销、线程通信易于实现、并发程度提高、节省内存空间等。

一  传统程序测试：
 
(一)是否关心软件内部和实现划分：
 
1.黑盒测试：又称功能测试，通过测试来检验每个功能是否正常。从用户的角度，从输入数据和输出数据的对应关系出发进行测试。
 
2.白盒测试：又称结构型测试，按照程序内部的结构来测试程序。六种：语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖和路径覆盖发现错误的能力呈由弱至强的变化。
 
3.灰盒测试：是介于白盒测试与黑盒测试之间的，可以这样理解，灰盒测试关注的是输出对于输入的正确性，同时也关注内部表现。
 

 
 
(二)从是否执行程序来划分：
 
1.静态测试：是指不运行被测程序本身，仅通过分析或检查源程序的语法、结构、过程、接口等来检查程序的正确性。对需求规格说明书、软件设计说明书、源程序做结构分析、流程图分析、符号执行来找错。
 
2.动态测试：指通过运行被测程序，检查运行结果与预期结果的差异，并分析运行效率和健壮性等性能，这种方法由三部分组成：构造测试实例、执行程序、分析程序的输出结果。
 

 
 
(三)从软件开发阶段划分：
 
1.单元测试
 
2.集成测试
 
3.确认测试
 
4.系统测试
 

 
 
二 并发程序测试：
 
(一)并发程序测试概述：
 
1.并发测试过程中，不仅需要检查程序输入和输出结果的正确性，还需要验证并发程序中某些同步序列的正确性。同步序列：并发程序的一次执行过程中，由一些并发单元之间的交互或同步活动形成的序列。
 
2.并发错误类型：
 
*根据规格说明和程序实现的一致性要求，可将并发程序的同步序列分为有效同步序列和可行同步序列。
 
*有效同步序列：给定某并发程序CP和输入X，若同步序列Q被程序规约允许，则称Q是CP的有效同步序列。
 
*可行同步序列：若同步序列Q被程序实现允许，则称Q为可行同步序列。反之，不可行。
 
*当满足下述任一条件时，并发程序在输入X下是错误的：在输入X下至少有一个同步序列可行但不是有效，或者至少有一个同步序列有效但不可行。
 
*在所有可能的输入的条件下都是正确的，那么并发程序CP是正确的。
 

 
 
(二)非确定性测试：
 
1.不确定性测试使用的测试输入不包含任何同步序列信息，除了对被测程序提供必要的输入数据，它不控制被测程序的具体执行过程。不确定性测试期望通过并发程序的多次执行尽可能多地执行不同的同步序列，以增加发现错误的机会。
 

 
 
2.非确定性测试的步骤：
 
*选取一组输入数据；
 
*使用输入数据执行被测并发程序，记录每次执行的输出数据和执行的同步序列；
 
*判断输出数据是否正确以及对应的同步序列是否有效，如果输出数据不等于预期结果或者同步序列无效，都表示并发程序中存在错误。
 
*重复2到3，直至到达结束条件。
 

 
 
3.非确定性测试的问题：
 
*同一输入下并发程序的一部分同步序列可能重复执行，而另一部分同步序列可能从未得到执行，测试效率低且充分性得不到保证。
 
*非确定性测试是基于程序实现的测试方法，不能检测出规格说明有效但是不可行的同步序列。
 

 
 
(三)确定性测试：
 
1.确定性测试：在给定测试输入下通过程序运行时控制技术，使其按照给定的同步序列执行，从而检查程序的输出结果是否正确，并判断给定的同步序列(有效)是否可行。
 
2.确定性测试步骤：
 
*选取一组输入数据和一个同步序列集合；
 
*控制并发程序在给定输入下按照同步序列集合中的同步序列执行；
 
*将程序执行结果与预期结果比较，除了要检查程序输出是否为预期输出外，还要检查程序是否能够执行给定的同步序列。如果输出数据域预期输出不符或同步序列不可行，都表示并发程序存在错误。
 
*重复执行2和3，直到在任意输入数据下同步序列集合中的同步序列都已执行。
 
3.确定性测试的问题：
 
*同步序列的选取是难点。
 
*确定性执行被测程序的技术实现：目前有两种方法。第一种，通过语言自身提供的机制确定化程序事件的执行顺序，即基于语言的方式。第二种，通过修改编译器或底层操作系统确定程序的执行过程，即基于实现的方式，对java而言就是修改java虚拟机。
 
*基于语言的方式：易于实现，但对被测程序插装可能引入新的错误。
 
*基于实现的方式：无需修改被测程序，但实现难度大，不易实现。
 

 
 
(四)可达性测试：
 
(1)定义：可达性测试结合了确定性测试和非确定性测试的优点，动态生成被测程序的同步序列，而且在给定输入的前提下能够穷尽被测程序的可行的同步序列。(这样就可以判断可行的同步序列是否是有效的，从而判断并发程序是否有错，所有可行的同步序列包括所有有效的同步序列)。
 
(2)可达性测试的步骤：
 
*给定输入下，以非确定性测试执行被测并发程序，收集执行的同步序列。
 
*对收集到的同步序列执行竞争分析，计算出竞争变体。
 
*以竞争变体为前缀确定性执行被测并发程序，然后以非确定性方式执行程序后续部分，收集执行的同步序列。
 
*对每一个新的可行的同步序列，重复执行2和3，直到给定测试输入下没有新的可行的同步序列产生。
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 

一、并发程序设计的概念
 
1.顺序程序设计及其特性
 程序是实现算法的操作（指令）序列
 每个程序在处理器上执行是严格有序的，称为程序执行的内部顺序
 程序设计的一般习惯是顺序程序设计：把一个具体问题的求解过程设计成一个程序或者若干个严格顺序执行的程序系列，这称为程序执行的外部顺序
 特性
 {
 1.程序执行的顺序性：程序指令执行是严格按序的
 2.计算环境的封闭性：程序运行如同独占受操作系统保护的资源
 3.计算结果的确定性：程序执行结果与执行速度和执行时段无关
 4.计算过程的可再见性：程序对相同数据集的执行轨迹是确定的
 }
 
2.并发程序设计的概念‘
 进程的并发执行
 {
 多道程序设计让多个程序同时进入内存去竞争处理器以获得运行机会
 OS允许计算机系统在一个时间段内存在多个正在运行的进程，即允许多个进程并发执行
 OS保证按照“顺序程序设计“方法编制的程序在并发时不受影响，如同独占计算机
 这些按照顺序程序设计思想编制的进程在OS中并发执行属于无关的并发进程
 }
 
并发程序设计：把一个具体问题求解设计成若干个可同时执行的程序模块的方法
 
3.并发程序设计的特性
 {
 1.并行性：多个进程在多道程序系统中并发执行或者在多出力系统中并行执行，提高了计算效率
 2.共享性；多个进程共享软件资源
 3.交往性：多个进程并发执行时存在制约
 增加了程序设计难度
 }
 
二、并发程序的制约关系
 
1.无关与交往的并发进程
 无关的并发进程：一组并发进程分别在不同的变量集合上运行，一个进程的执行与其他并发进程的进展无关
 交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响到其他并发进程的结果
 2.与时间相关的程序设计错误
 对于一组交往的并发进程，执行的相对速度无法相互控制
 如果程序设计不当，可能会出现各种”与时间有关的“错误
 表现一：结果错误
 表现二：永远等待
 3.进程互斥与同步的概念
 交往的并发进程在执行时必须进行支援，才能保证得到合理的结果
 进程互斥：并发进程之间因相互争夺独占性资源而产生的竞争制约关系
 进程同步并发进程之间为完成共同任务基于某个条件来协调执行先后关系而产生的协作制约关系
 
三、临界区
 
1.临界区的基本概念
 互斥与临界区
 {
 临界资源：互斥共享变量所代表的资源：即一次只能被一个进程使用的资源
 临界区指并发进程中与互斥共享变量相关的程序断
 多个并发进程访问临界资源时，存在竞争制约关系
 如果两个进程同时停留在相关的临界区内，就会出现与时间相关的错误
 }
 
临界区的描述
 临界区一定跟一个临界资源有关，临界区又是一个代码段
 两个进程的临界区具有相同的临界资源，就是相关的临界区，必须互斥进入，两个临界区不相关，则没有限制
 
2.临界区管理的三个要求
 {
 1.一次之多允许一个进程停留在相关的临界区
 2.一个进程不能无限制地停留在临界区内
 3. 一个进程不能无限制的等待进入临界区
 临界区可以嵌套使用

 
 
第七章 使用Akka构建高并发程序
   
1 新并发模型Actor
2 Akka之 Hello Word
3 有关消息投递的一些说明
4 Actor的生命周期
5 监督策略
6 选择Actor
7 消息收件箱Inbox
8 消息路由
9 Actor的内置状态转换
10 询问模式Actor中的Future
11 多个Actor同时修改数据Agent
12 像数据库一样操作内存数据软件事务内存STM
13 一个有趣的例子并发粒子群的实现
     
131 什么是粒子群算法
132 粒子群算法的计算过程
133 粒子群算法能做什么
134 使用Akka实现粒子群
 
 
 
 
 
第七章 使用Akka构建高并发程序
 
提供了一种称为Actor的并发模型，其粒度比线程更小，因此可以在系统中大量使用Actor。不仅适用于单机，也适用于分布式程序。
 
7.1 新并发模型：Actor
 
在Actor模型中，失去了对象的方法调用，并不是通过调用Actor对象的一个方法告诉Actor需要做什么，而是给Actor发送一条消息。当Actor收到一条消息后，它可能会根据消息的内容做出某些行为，包括更改自身状态。但其状态修改是Actor自己进行的，而非外部调用的。
 
7.2 Akka之 Hello Word
 
在Akka中，UntypedActor就是所说的Actor。之所以强调无类型，是因为Akka中，还支持一种有类型的Actor，其可以使用系统其他类型构造，可以缓解java单继承的问题。
使用Actor进行并行程序开发时，关注点已经不在线程上，只需关注Actor对象即可，而Actor对象之间的交流和普通对象的函数调用有着明显的区别，它们是通过显示的消息发送来传递消息的。
当系统中有多个Actor存在时，Akka会自动在线程池中选择线程来执行actor，因此多个不同的Actor可能会被同一个线程执行，一个Actor可能被不同的线程执行。
 
7.3 有关消息投递的一些说明
 
整个Akka应用是消息驱动的。消息是Actor之外的重要核心组件，在Actor之间传递的消息应该满足不变性。因此，Akka中的消息推荐使用不可变对象，即final修饰的。
消息投递的三种策略： 
 
  
至多一次投递。每一条消息最多会被投递一次，可能会导致消息投递失败，消息丢失
至少一次投递。每一条消息至少会被投递一次，直到成功为止。不会发生消息丢失，但是可能会发生消息重复
精确的消息投递。保证所有消息都会被成功投递一次，既不会有丢失也不会重复。
实际上，没必要在Akka层保证消息的可靠性，成本太高，也没有必要。消息的可靠性可以在应用层确保。
顺序性：在一定程度上保持消息的顺序性。如A1向A2顺序发送了M1、M2和M3，三条消息，A3向A2顺序发送了M4、M5和M6三条信息 
 
  
如果M1没有丢失，那它一定先于M2和M3被A2收到
如果M2没有丢失，那它一定先于M3被A2收到
如果M4没有丢失，那它一定先于M5和M6被A2收到
如果M5没有丢失，那它一定先于M6被A2收到
对A2来说，来自A1和A3的消息可能交织在一起，没有顺序保证。消息的传递不具有传递性。如A向C发送了M1，接着，A向B发送了M2，B将M2转给了C，那么C收到M1和M2没有先后顺序保证
 
7.4 Actor的生命周期
 
一个Actor在actorOf函数被调用后开始建立，Actor实例创建后，会回调preStart方法。如果actor在工作过程中出现异常，需要重启，会回调preRestart方法（老的实例上），接着系统会创建一个新的actor实例，虽然是新的，但表示同一个actor，当新实例创建后，postRestart方法会被调用，表示启动完成。stop方法可以停止actor，其停止时，postStop会被调用，同时这个actor的监视者会收到Terminated消息。
 
7.5 监督策略
 
两种： 
 
  
OneForOneStrategy（默认策略）
父Actor只会对出问题的子Actor进行处理。
AllForOneStrategy
父Actor会对所有的子都进行处理
 
7.6 选择Actor
 
ActorSelection类可以根据path匹配规则，批量获取actor
 
7.7 消息收件箱（Inbox）
 
可以方便地对Actor进行消息发送和接收，大大方便了应用程序与Actor之间的交互。
 
7.8 消息路由
 
路由器组件，实现消息调度的封装。提供几种消息路由策略如，轮询选择actor进行消息发送，随机消息发送，将消息发送给最为空闲的actor，组内消息广播。
 
7.9 Actor的内置状态转换
 
一个actor内部消息处理函数可以拥有多个不同的状态，在特定的状态下，可以对同一条消息进行不同的处理，状态之间也可以任意切换。
 
7.10 询问模式：Actor中的Future
 
7.11 多个Actor同时修改数据：Agent
 
提供了对一个变量的异步更新。
 
7.12 像数据库一样操作内存数据：软件事务内存（STM）
 
具有隔离型、原子性和一致性。但不具有持久性。确保多个actor协作完成一项任务的问题。
 
7.13 一个有趣的例子：并发粒子群的实现
 
粒子群算法（PSO）是一种进化算法。与遗传算法非常类似，可以用来解决一些优化问题。可以将一些NP问题转变为一个多项式问题。但是有代价的，进化算法不保证可以从结果中得到最优解。
 
7.13.1 什么是粒子群算法
 
一种基于迭代的优化算法。广泛应用于函数优化与神经网络训练等方面。源于鸟类的觅食的群体表现。
 
7.13.2 粒子群算法的计算过程
 
初始化所有粒子，粒子的位置随机生成。计算每个粒子当前的适应度，并将此设为当前粒子的个体最优值（记为pBest）
所有粒子将自己的个体最优值发送给管理者Master。Master获得所有粒子的信息后，筛选出全局最优的解（记为gBest）
Master将gBest通知所有粒子，所有粒子便知道全局最优点的位置
接着，所有粒子根据自己的pBest和全局gBest，更新自己的速度，在有了速度后，再更新自己的位置
如果粒子产生了新的个体最优点，则发送给Master，在此，转到步骤2
 
7.13.3 粒子群算法能做什么
 
最优化计算。
 
7.13.4 使用Akka实现粒子群
 
由于粒子数量过大，因此一般的线程模型无法满足，但Actor本身作为轻量级的并发单元，一个线程可以对应多个actor，因此适合进行这种并发计算。