Skip to main content

可重入 VI 和递归算法

重入执行是子 VI 的一个属性。默认情况下,VI 是不会被设置这个属性的;需要设置它时,可以在 VI 属性对话框中,选中 "重入执行" 选项。设置了这一属性的 VI,称为可重入 VI。

图 .12 设置 VI 的可重入属性

如果某个子 VI 被设置为可重入,那么在程序的不同地方调用这个子 VI 时,它会在内存中为每一处的调用各生成一个新的 VI 实例。即,尽管程序在不同地方调用的这个子 VI 的内容都相同,但是这些子 VI 在内存中却是相互独立的。如果是非可重入的子 VI,在内存中只能有一份实例,所有的调用者都访问这个实例。

被设置为重入执行后,还有两个选项:"为各个实例预分配副本" 表示每处调用生成的实例 VI 都拥有各自独立的数据区,它们之间的数据互不干扰。本书后续章节提到的可重入 VI,如无特殊说明,都是指这种可重入 VI。"在实例间共享副本" 是 LabVIEW 8.5 之后出现的选项,它是指这些实例 VI 使用同一块数据区。

同一 VI 的并行运行

图 4.13 是一个简单的 VI,它的程序框图有上下两部分,都调用了同一个子 VI。上下两部分的代码之间没有数据线相连。LabVIEW 是自动多线程的语言,图中的两个子 VI 是否会同时运行呢?

图 .13 并行的两个相同子 VI

如果程序中调用的是两个不同的子 VI,LabVIEW 有可能会同时在不同的线程执行它们;但对于两处调用相同的子 VI,那就得看子 VI 是如何设置的了。

如果子 VI"简单运算.vi" 是非可重入的,那么它们一定不会同时运行。LabVIEW 一定要等一个执行完,才会执行另一个。

非可重入的子 VI 在内存中只有一个实例,它的代码和数据都只有一份。在此处调用这个子 VI 时,它运行所需的数据内容可能都是不同的。若可以同时运行在多处调用的这个子 VI,子 VI 的运行状态和数据就可能发生混乱。所以 LabVIEW 要禁止这种情况的发生。

VI 的这一特性在有些场合表现出了非常好的优点。比如,一个用于读写某个特定文件的子 VI "foo.txt"。应用程序中可能有多处都调用了这个子 VI 来读写 "foo.txt",如果允许多个线程的程序同时读写它,就很容易造成其内容的混乱。同一子 VI 不可在不同线程同时运行的特性恰好保护了 "foo.txt",使它不被不同线程同时读写。

但在某些场合,这一特性又显得非常糟糕。比如,有一个用于读写所有文件的子 VI。不同的文件应当是可以同时被访问的,但这个子 VI 却不允许应用程序同时读写不同的文件。需要同时访问几个文件时,也必须一个一个的访问,暂时不能访问文件的那个线程只好等待着。这样,就造成了程序效率的低下。

在这种场合,需要把子 VI 设置为可重入,以避开同一子 VI 不可在不同线程同时运行的特性。一个线程正在运行这个子 VI 时,另一个线程也可以调用它。在 LabVIEW 中,形象地来看,就是在程序框图的某处,数据流入了一个子 VI;在这个框图另外一处,数据也可以片刻不停地同时流入这个子 VI。因此,叫做 "可重入"。前面已经讲过,应用程序每处调用可重入的子 VI 时,都生成了一个独立的实例。这就相当于,在应用程序中各处调用的是不同的子 VI,只不过这些子 VI 内部的代码相同而已。既然是不同的子 VI,当然也就可以在不同的线程中同时运行。

图 3.12 显示的是一个延时子 VI 的程序框图(延时 1 秒),而图 4.14 是一个调用了这个延时子 VI 的应用程序,它并行的调用了这个延时子 VI 两次,那么这个应用程序总的运行时间是多少呢?

图 .14 计算程序总运行时间

如果延时子 VI 是非可重入的,则由于两处调用只能先后分别运行,程序总运行时间为 2 秒。若延时子 VI 是可重入的,则两处调用可以同时运行,程序总运行时间为 1 秒。

可重入 VI 的副本

若可重入 VI 的多个实例共用一份副本,就意味着它们共用同一数据区。不同实例运行时,可能会把不同数据写入这个唯一的数据空间中,这样就造成了数据的混乱。如果需要可重入 VI 不同实例会同时运行,并且它们运行时会使用不同的数据,那么就一定要把这个子 VI 设置为 "为各个实例预分配副本"。

图 4.15 是一个简单的子 VI,这个 VI 的功能是每执行一次,输出的数据加一。它利用了反馈节点。每次运行这个 VI 时,反馈节点首先输出上次 VI 运行后传递给它的数据。VI 在此基础上加一,再返回给反馈节点,以便下次调用时使用。反馈节点下方的 0 是它的初始值,第一次调用 VI 时,反馈节点给出初始值。

图 .15 计算调用次数的子 VI

图 4.16 是一个调用了 “运行次数” 子 VI 的应用程序。执行这个程序后,输出 "次数 1" 和 "次数 2" 分别是几?

图 .16 测试运行次数

运行结果同样与 “运行次数” 子 VI 的设置有关。程序中两个循环执行次数一为 10,一为 20。它们之间没有数据连线,所以可以被同时执行。但哪个循环先执行完是不确定的。

如果 “运行次数” 子 VI 是非可重入的,则每次运行程序 "次数 1" 和 "次数 2" 的值是不确定的,但它们之间必然有一个为 30。虽然循环运行次序不能确定,但是能够确定,运行次数子 VI 总共被调用了 30 次,所以它最后一次被调用后,输出的值一定是 30。只不过,哪个循环中的 VI 是最后一次被调用的并不确定。

如果运行次数子 VI 是可重入的,并且被设置为 "为各个实例预分配副本",那么图 4.16 中程序的执行的结果是确定的。"次数 1" 的值为 10,"次数 2" 的值为 20。由于子 VI 是可重入的,所以程序中的两处调用行为相当于调用两个不同的子 VI。他们分别运行,不论运行次序如何,左侧的子 VI 被调用了 10 次,而右侧的子 VI 被调用了 20 次。

如果运行次数子 VI 是可重入的,并且被设置为 "在实例间共享副本"。那么图 4.16 中程序的执行结果是不确定的:"次数 1" 和 "次数 2" 的值可能是小于 30 的任何一个数值。子 VI 可重入意味着程序中的两处子 VI 调用是可以同时运行的。但是,它们共用一个副本,这就造成了数据的混乱。假如,左侧子 VI 正在运行,内部记录运行次数的数据是 8,而这时右侧子 VI 也同时运行起来,并往内部记录运行次数的数据区写入一个数值 3。这样,左侧子 VI 再读出该数据是就是一个错误数值了。

"在实例间共享副本" 虽然会引起数据的混乱,但是它可以大大节约程序的内存。每生成一个副本,就会多消耗一份内存空间。因此,在确保不会发生数据混乱的情况下可以把可重入子 VI 设置为 "在实例间共享副本"。

递归算法

算法

递归是指一个 VI 直接调用自身,或者间接调用自身,比如:VI_1 调用 VI_2,VI_2 又调用 VI_1。如果大家还记得学习数学的时候有个归纳法,递归可以被看作是把归纳法写成程序。递归的策略是把一个大的复杂的问题转换为一个小的和原问题相似的问题,再进一步把问题拆成更小的问题,最终解决整个问题。理论上,任何需要使用递归调用的地方,都可以用循环结构来代替。但是在某些情况下,使用递归调用的确可以大大简化程序代码的复杂度,有助于缩短编程时间、提高程序可读性。所以,学会如何实现递归还是很有用的。

计算阶乘

下面看一个最简单的例子:计算阶乘。计算某个正整数的阶乘就是用那个数去乘所有比它小的正整数。比如 3 的阶乘写作 3! = 3*2*1;类似的 6!= 6*5*4*3*2*1。如果用循环来计算 n 的阶乘,就是把所有小于 n 的正整数乘起来就行了:

images/image412.png

但是我们还可以换一种方法来考虑如何计算阶乘:我们不是直接从原始的数据开始计算,而是用归纳的方法,一步一步的来简化问题,比如 6 的阶乘,它可以通过先计算 5 的阶乘,再把结果乘以 6。用公式来描述就是 0! = 1, n! = n * (n-1)! |(n≧1),或者写成函数的形式为:F (0) = 1, F (n) = n * F (n-1) |(n≧1)。数学归纳法中一定要有一个基本情况,对于阶乘的问题,基本情况是 0,0 的阶乘等于 1,这是人为定义出来的。有的读者可能已经注意到了,用归纳法表示的阶乘与直接计算阶乘不是完全一模一样,归纳法把阶乘计算推广到了所有非负整数,而直接计算,只能计算正整数的阶乘。算是归纳法的一个小优势吧。

下面我们把归纳法公式转换为程序,只要照着公式一模一样的写就可以了。建立一个新的 VI,把 VI 的可重入属性设置为 "让各个实例间共享空间" (Shared clone reentrant execution)。首先处理基本情况,当输入为 0 时,输出为 1:

images_2/w_20211205152006.png

当输入大于等于 1 时,VI 调用自身,但是输入的值需要减 1;然后把子 VI 输出乘以输入值,输出结果就可以了:

images_2/w_20211205152014.png

计算斐波纳契数列

阶乘这个问题过于简单,可能现不出递归的优势。我们可以再考虑一个稍微更复杂一点的问题:斐波纳契数列。 这个问题是意大利人斐波那契在描述兔子生长的数目时用到的:

  • 第一个月初有一对刚诞生的兔子
  • 第二个月之后(第三个月初)它们可以生育
  • 每月每对可生育的兔子会诞生下一对新兔子
  • 兔子永不死去

每个月兔子的总数量用数学归纳法来描述就是:

  • F (0)=0
  • F (1)=1
  • F (n)=F (n-1) + F (n-2) |(n≧2)

这个问题的数学归纳法公式简洁明了,非常适合用递归算法来解决。首先,还先编写归纳法的基本情况,也就是递归的结束条件,当输入为 0 和 1 时,分别输出 0 和 1:

images_2/w_20211205160922.png

当输入 n 大于等于 2 时,VI 调用自身两次,一次输入 n-1,另一次输入 n-2;然后把两个子 VI 输出的结果想加,输出结果即可:

images_2/w_20211205160932.png

递归程序的一个效率问题

读者可以用一个不大于 20 的输入数据实验一下,看结果是否正确。但是千万不要输入太大的数据,因为上面这个 VI 计算斐波纳契数列,功能上虽然正确,效率上却存在一个明显缺陷。在上图的程序,假如输入数值为 20,程序分为两支:

  • 上面的分支去计算 19 的斐波纳契数,在其内部又需要分两支,一支计算 18 的斐波纳契数……;
  • 下面的分支去计算 18 的斐波纳契数,可是 18 的斐波纳契数已经在上面那个分支里计算过了啊,现在又要重复计算一遍!

这样的算法,输入值每增加 1,程序的计算量就要翻倍。这是编写递归程序容易出现的一个严重效率问题:同样的计算,在不同的地方被运行了很多次。使用循环通常可以解决这个问题:求 n 的斐波纳契数,可以从小到大计算,先算出 0 的斐波纳契数,再计算 1 的斐波纳契数,再计算 2 的斐波纳契数…… 循环迭代 n 次,得到 n 的斐波纳契数。

但是很多时候,使用循环编写的代码,不如递归简洁易读。使用递归算法也是有办法解决上面的重复计算问题的。读者可以思考一下,有什么简单的方法能够即使用递归,又避免重复计算?

编写递归程序的步骤

从以上的例子中可以总结出,编写递归算法可遵循以下的步骤:

  1. 明确一个递归结束的条件,也就是归纳法的基本情况。如果递归调用的结束条件设置不当,可能会引起程序死循环甚至崩溃。
  2. VI 中先放置一个条件结构,检查当前输入是否满足递归结束条件。如果满足返回基础条件设定的结果。
  3. 输入值若不满足递归结束条件,则想办法把问题拆分成可以用更小或更简单的相似问题,然后使用更小或更简单的输入调用算法 VI 自身,得到子问题的结果。
  4. 对子问题的结果进行归并处理,得到当前问题的结果。

在考虑是否使用递归算法时需要注意一些事项:

  • 递归算法解题通会使得某些问题的解决变得非常简洁,可读性好于非递归算法。
  • 合作伙伴如果没有递归编程经验可能会比较难以理解程序代码。
  • 任何需要使用递归算法的地方,都可以用循环来代替。递归算法的运行效率通常低于循环算法。
  • 参与递归调用的 VI 必须被设置为 "让各个实例间共享空间" (Shared clone reentrant execution) 的可重入 VI。这一设置在 VI 属性对话框的 "执行" 页面:

images_2/w_20211205161710.png

普通 VI 为什么不能被递归调用

这和大多数其它编程语言都不一样,其它的编程语言如果支持递归,那么一般不需要对函数做什么特别的设置,直接就可以进行递归调用。但是在 LabVIEW 中,普通 VI(非可重入的 VI)是不能通过静态调用的方法来实现递归的。即,不能把一个 VI 当作自身的子 VI。

其它多数编程语言会为每一次函数调用都分配一个不同的数据区共子函数使用。对于一个非可重入的子 VI,VI 每次被调用的时候都从同一片数据区读取数据,这是处于效率的考虑。因为这个设置,在每一个时间,同一个子 VI 只能被运行一次。因为 LabVIEW 需要借此来保证多线程时的数据安全。假如,同时有多个线程在同时读写同一块内存里的数据,就很可能发生一些不可预料的错误,比如线程 A 写入一个数据 5.0 在内存里,然后读出继续使用,我们是希望读出的数据为 5.0 的。但多线程情况下,很可能还有一个 B 线程在 A 写入 5.0 后立即在同一内存地址写入了一个不同的数据比如 7.0,这时线程 A 再读出的数据就是错误的了。关于多线程和内存管理的问题,本书会在 LabVIEW 的运行机制多线程编程 章节内做更详细讨论。

递归算法中,子 VI 总是在调用还没结束的时候就再次被调用的。因此,非可重入的子 VI 不能用于递归调用。被设置为 “为每个实例预分配空间” 可重入 VI,尽管是可以被同时调用多次,但是不能被用于地递归调用。为了保证每处调用时使用不同的数据区,LabVIEW 在静态调用 “为每个实例预分配空间” 的可重入子 VI 时,把数据区设置在了调用它的父 VI 中。也就是说,子 VI 的数据区是在程序运行前,就开辟好了的。而在递归调用时,是无法在程序运行前就确定子 VI 要被调用多少次的,调用次数是动态的,LabVIEW 无法知道需要为它准备多少个独立的数据区,所以也就不可以静态递归调用。

数据空间分配方式

LabVIEW 8.6 之后,在设置 VI 为可重入时,有两个数据空间分配选项:“让各个实例间共享空间” 和 “为每个实例预分配空间”。(见上图)(Shared clone reentrant execution & Preallocated clone reentrant execution)

“为每个实例预分配空间” 是旧版本 LabVIEW(8.6 之前)设置可重入 VI 时的唯一选项。它是指程序在运行前,编译的时候就为每个可重入 VI 的实例分配好各自的数据空间。比如说这个子 VI 被主 VI 在 3 处不同的地方调用了,那么就分配 3 份数据副本给它。但是,这种分配数据空间的方式有两个主要的问题。

其一,很多时候程序运行前不能预期会有几处调用到了这一个可重入子 VI,比如递归算法就是如此。递归每迭代一次,就需要生成一个新的递归 VI 的实例。而递归的深度与输入数据有关,在程序运行时才能确定,因此无法预先得知应当分配多少个副本数据空间,也就没法设置为这种模式。

其二,这种设置方式控件效率太低。假设一个可重入 VI A,它在主 VI 中有三处被调用,分别是实例 1、2、3。假设程序总共运行 3 秒,第 0 秒运行实例 1;第 1 秒运行实例 2;第 2 秒运行实例 3。在这个程序整个运行时间内,始终为可重入 VI A 开辟了三份数据空间,但是每份数据空间都只被使用了很短一段时间,其余时间都没被用到。若是能够重复利用它们,程序可以节约不少内存。

为了解决以上两点问题,LabVIEW 又新添了一种为可重入 VI 分配数据空间的方式:“让各个实例间共享空间”。笔者觉得这个名称可能会容易让人误解为:只为可重入 VI 分配一份数据空间,然后它所有的实例都是用这同一份数据空间。实际情况当然不是这样的,否则就无法保证可重入 VI 功能的正确性了。

事实上,采用 “让各个实例间共享空间” 时,每个可重入 VI 的实例依然会有它们各自独立的数据空间。程序在逻辑功能上与 “为每个实例预分配空间” 的方式没有任何区别。唯一的不同在于,数据空间并不是程序一起动就分配好了的,而是只有当一个实例 VI 被运行到的时候,才为它分配数据空间,而这个实例 VI 运行结束后,它的数据空间就又被回收回去了。两个同时运行的实例 VI 是绝对不会共享同一个数据空间的;两个不同时运行的实例 VI 倒是可以分享同一片数据空间,这已是名称中 “共享” 的由来。总的来说,如果起名为 “动态分配空间” 可能会更好理解一些。

还是以上文的可重入 VI A 为例,若它被设置为 “让各个实例间共享空间”,程序开始时,只需要为可重入 VI A 准备一份数据空间,供实例 1 使用;程序第 1 秒的时候,实例 1 运行结束,它的数据空间被收回,因此实例 2 还可以继续使用这份数据空间;第 2 秒时,轮到实例 3 继续使用者份数据空间。若我们改变一下应用程序的逻辑,把实例 3 在第 2.5 秒的时候就运行起来,由于原有的一份数据空间还在被实例 2 所使用,它不能再分配给实例 3,这时候,LabVIEW 就会为可重入 VI A 再开辟一份数据空间,供实例 3 使用。

“让各个实例间共享空间” 的设置虽然提高的程序的空间效率,但它并非只有优点。数据空间的开辟回收都是需要时间和额外的运算资源,因此这个设置是以牺牲时间效率为代价来换取空间效率的提高。

对于一个可重入 VI,如果它在应用程序中被调用的地方并不是很多,或者它的各个实例常常会同时运行的,那么就应该把它设为 “为每个实例预分配空间”;反之,这个可重入 VI 会被应用程序频繁的调用,而且每个实例运行的时间都很短,它们的运行时间不大可能会有重叠,就应当把它设置为 “让各个实例间共享空间”。用于递归调用时,必须使用 “让各个实例间共享空间” 方式。

练习

  • 编写一个 VI 使用循环结构计算给定数值(一个 100 以内的正整数)的斐波纳契数,因为输出的结果可能非常大,使用 DBL 作为输出数据类型。
  • 编写一个 VI 使用递归算法计算给定数值(一个 100 以内的正整数)的斐波纳契数。效率需要与上题中的循环算法相当。