亚线程和动态亚线程树的设计与研究
2008-07-28
作者：邢 丰 戴梅萼 周 健 余
摘 要： 提出了一种对线程进行合理分组的方法，即亚线程技术，并提出了动态亚线程树的设计思想" title="设计思想">设计思想和运行机制。
关键词： 多线程 亚线程 动态亚线程
多线程是近年来非常流行的一项编程技术。尤其是在网络传输和资源共享软件的设计中，在多媒体的采集和处理、并行计算、并行处理等方面，更是由于高效性和可靠性要求而使线程技术得到广泛使用。多线程技术保证了程序模块间的分离度，而且可通过合理划分功能模块而减少通信量，实现广泛的数据共享，从而使系统性能得到很大提高。
但是，随着线程数目的增多，共享数据的管理将变得相当复杂。线程的增多导致对共享数据区的访问非常频繁，从而增加了系统的额外开销。为此，本文提出了基于线程分组的亚线程机制。
在设计中，只要分组合理，亚线程之间的调用就不会过于频繁，从而可减少多个线程频繁访问共享数据而引起的混乱。由此，亚线程机制可以有效地提高系统性能，同时保证数据的安全。
1 亚线程机制的设计思想
1.1 亚线程和亚线程树
亚线程在结构上是基于线程的分组。每个亚线程由一定数目的线程和共享数据组成。编程时，把互相之间有紧密关系或存在频繁通信关系的线程及共享数据分到同一个亚线程中。亚线程内部的互相调用和通信几乎不受限制，只有亚线程之间的访问会受到一定限制。
一般说，线程是被个别创建的。在亚线程机制中，每个线程被分到某个亚线程中，一旦确定，便不再改变。
总之，亚线程可分为根亚线程和普通亚线程两类。最基本的亚线程叫根亚线程。若创建线程时不指定亚线程，该线程就会自动归属于根亚线程。除了根亚线程之外的亚线程都是普通亚线程。
在亚线程机制中，采用亚线程树来实现总体设计。亚线程树是程序中所有亚线程构成的树形结构" title="树形结构">树形结构。在这种树形结构中，一个亚线程通常从属于其它亚线程。所以，在构建一个新的亚线程时，必须指定它从属于哪个亚线程。若未指定，则会自动归属于根亚线程。这样，一个应用程序" title="应用程序">应用程序中的所有亚线程最终都会直接或间接归属于根亚线程。
亚线程树结构如图1所示。
在采用进程-线程结构的应用程序中，亚线程是介于进程和线程之间的中间结构。实验表明，由于亚线程的加入，使系统效率得到很大提高。
1.2 亚线程机制的具体实例
在本课题组完成的863项目《远程机器人控制系统》中采用了进程-线程结构，在此基础上加入了亚线程后，形成进程-亚线程-线程机制。
此系统主要功能是：通过图像传输和命令传输，对远程机器人进行相应控制，并通过加密技术实现对信息的即时加密。系统采用Client/Server结构。表1和表2分别为Server端和Client端的线程和亚线程列表。
在Server端，亚线程树结构如图2所示。其中，图像采集、图像压缩和图像传送三个线程的处理对象都是视频文件；命令接收和命令执行两个线程的处理对象都是命令；文件加密线程和文件解密线程的处理对象都是文件；文字发送线程和文字接收线程则负责文字通信。基于上述特点，这些线程构成了图2所示的亚线程树结构。
在Client端，程序运行后，每连接一个机器人站点就建立一个进程。每个进程中的亚线程结构如图3所示。各亚线程的构建方法与Server端类似。
加入亚线程机制后，亚线程间的数据访问受到限制。例如文字发送、接收线程和S/C同步线程基本不访问加密解密的文件，亚线程管理器" title="管理器">管理器甚至可以禁止这些线程去访问传输的文件。又如，对传输的视频数据，除了Server端的图像采集、压缩和传送线程，以及Client端的图像接收、解压缩和显示线程外，不能被其他任何线程访问。这样，通过亚线程机制优化了整个应用程序的运行，并保证了数据的安全。此外，由于主要操作都归为亚线程内部操作，所以，大大提高了程序执行的效率。
1.3 亚线程机制的特点
亚线程机制的特点是，允许对一个亚线程中的所有线程同时操作。例如，可通过调用相应的方法来设置其中所有线程的优先级，也可以启动或阻塞所有线程。
亚线程机制的另一重要特点是为安全性提供了很好前提。它通过分组来区分不同安全级别的线程，对不同亚线程中的线程进行不同处理，还可以通过亚线程的分层结构来支持不对等安全措施。在亚线程机制中，一个线程只能修改所属亚线程树中的其它线程，这种修改包括修改线程优先级别和挂起或唤醒线程等操作。
由于一个亚线程只能访问那些从自己的根亚线程树分支出来的线程，而不能访问其他任何线程。因此，可有效保证数据的安全。
2 动态亚线程树的运行机制
动态亚线程树是对亚线程机制的进一步优化，它通过在亚线程结构基础上加入亚线程管理器和动态亚线程机制来实现。
2.1 亚线程管理器
亚线程管理器的功能是对亚线程进行调控，它独立于所有亚线程。
具体设计时，亚线程管理器由一个表格和一个控制组件构成。表格纪录各种信息，具体内容随应用程序不同而异。例如，包括亚线程间的交互信息，整个系统中包含的线程和亚线程名，各线程和亚线程对应的父亚线程名，线程及亚线程之间的通信次数和频率等。控制组件则根据这些信息做出相应的调整。
2.2 动态亚线程机制
大多数情况下，在线程的整个生命周期中，基本功能、通信对象以及处理对象都较固定，因此，亚线程机制可以有效地优化应用程序的执行效率。但有时有些线程的通信对象不固定，处理的对象也不固定。如果将这样的线程永久归入某一个亚线程，就会降低程序的执行效率。
动态亚线程机制可以较好地解决这个问题。动态亚线程机制的核心是可以动态地调整亚线程树的内部结构。采用这种机制后，一个线程调用其它亚线程中的对象或者与其他亚线程通信后，相关线程的标识符和通信次数会被根亚线程管理器纪录下来。若此后多次发生类似的通信，亚线程管理器就会据此对亚线程树进行调整，将该线程归入联系最多的亚线程中。另外，如果两个亚线程之间出现频繁通信，那么亚线程管理器会经过评测和判断来合并两个亚线程。
图4是采用动态亚线程机制时，亚线程树调整结构的简单示例。从图4中可以看到，亚线程管理器统计结果中，线程6和亚线程1中的线程通信为20+15+17=42次，远远大于与亚线程2内部的通信。这种情况下，亚线程管理器通过评测机构会得出应该调整结构的判断，于是将线程6归入亚线程1中。
具体说，亚线程的调整有以下几种类型：
①一段时间内，T1不属于Y2，但线程T1和亚线程Y2的通信明显比较频繁，这种情况下，T1应归入Y2。
② 一段时间内，线程T1与多个亚线程的通信都很频繁，这种情况下应将线程T1复制到那些亚线程中，即在相应的亚线程中重新创建与T1相同的线程，并进行相应规划。
③ 一段时间内，两个亚线程Y1和Y2的相互通信非常频繁，则将两个亚线程进行合并。
随着多线程的广泛应用，越来越需要有一种合理的管理机制来管理多线程以免造成调度的混乱。
亚线程机制可以有效地管理应用程序内部多个线程之间的相互访问和调度。对应的树状" title="树状">树状结构保证了数据访问和信息交互的安全。通过动态调整亚线程内部结构以及整个亚线程树的树状结构，又可以动态优化多线程应用程序的整体性能。
参考文献
1 Ian Foster. The Nexus Approach to Integrating Multithreading and Communication. Journal of Parallel and Distributed Computing, 1996
2 Koray ?魻ner, Luiz Barroso, Sasan Iman, etc. The Design of RPM: An FPGA-based Multiprocessor Emulator, 1995
3 Ka Wong Chong, Yijie Han,Tak Wah Lam. On the Parallel Time Complexity of Undirected Connectivity and Minimum Spanning Trees. SODA,ACM-SIAM Symposium on Discrete Algorithms, 1999
4 Chen Huinan. An Object Oriented Multi-Thread Dialog Model. The Journal of China Universities of Posts and Telecommunications,1998；5（1）
5 James M. Barton Nawaf Bitar Silicon, A Scalable MultiDiscipline. Multiple-Processor Scheduling Framework for IRIX, 1995