关于海量数据处理软件的程序设计

关于海量数据处理软件的程序设计

柳 毅，马鸣锦，蒋烈辉

（解放军信息工程大学　河南郑州　450002）

　　摘　要：程序员在开发应用软件的过程中需要解决诸多难题，其中关于海量数据的处理问题就是诸多难点之一。本文从数据结构设计、程序流程组织和编程技术的使用等几个方面来介绍一个关于海量数据处理软件的开发方法。
    关键词：多线程；循环队列；同步；互斥

1　引 言
　 　在现实社会里，尤其在医学、股票和气象等领域中经常存在着对海量数据进行分析的需求。一种解决这类问题的方法是在数据处理前先主观确定一个标准，然后将 数据进行无量纲化及归一化处理。这样常常导致运算结果不仅含有诸多主观因素，而且在运算前就改动了数据的原始性，通常这类方法运算相对复杂，因此也难以被 人们掌握。另一种解决的方法是建立一个适合于并行算法的数据模型，推导出能够解决实际问题的理论公式，通过设计一个高效的并行算法，在高性能的并行处理机 上来实现最终的分析。然而大型的并行处理机对使用低端设备的用户来说是可望而不可及的，为了解决在微机上进行海量数据处理的问题，本文从程序设计的角度阐 述了一个海量数据的处理方法，即通过使用良好的编程方法和合理的数据结构，使设计出的程序在功能完善的基础上，达到执行效率的最优和空间开销的最省。
2　理论依据（方法）
　 　导致数据处理软件运行缓慢的原因，主要是因为程序中有串行分量的存在，要改善整个系统的执行效率，最好是利用提高运算部分的并行负载量的方法，这种方法 可以用在诸如医学数据检测这样求解规模可扩放、数据间相对孤立的问题中。通过提取出问题中存在的可并行工作的分量，然后用程序实现这些并行分量的并行执 行，这样才能提高海量数据的处理速度。
2．1　线程与临界资源
　　众所周知，Win 32系统的应用程序是以进程的方式来工作的。一个进程就是操作系统调入内存来执行的一个应用程序，系统为每个进程分配4 GB的虚拟地址空间装载代码和数据。而线程作为一种操作系统对象存在进程的内部，他是程序中最基本的执行实体，其自身不占用系统额外的开销而是共享进程分 配到的空间，通过线程可以实现程序执行的并发性、独立性和异步性。每个线程都有自己的一组CPU寄存器和堆栈，操作系统为每个独立的线程安排CPU时间、 调度其状态，使线程可以分别处于工作态、挂起态和就绪态，从而实现不同线程间的切换。多线程技术的主要优势在于充分利用CPU的空闲时间片，可以用尽量少 的时间来对用户的要求做出响应，使得系统的整体运行效率得到较大的提高，增强了应用程序的灵活性。通常每个应用程序中至少存在一个线程，他被称为主线程或 默认线程，应用程序也可以根据需要动态地创建多个线程来执行不同的任务。但由于Win 32系统管理作。当线程工作完后，其使用的资源将自动释放。程序员在开发海量数据处理软件时，就可以利用Windows编程方法中的多线程技术分别设计出 功能不同的两类线程：一类是对原始数据进行分析处理，得出运算结果的消费类线程；另一类是负责为消费类线程提供原始数据的生产类线程。软件高效运行的实质 就是多个这两类线程协同工作的结果，整个程序的执行效率也会大幅度提升。
　　从程序设计的角度看，尽管多线程技术能够改善整个程序的执行效率。但 是，由于线程是根据其自身优先级的高低以抢占方式使用系统资源的，所以如果线程对系统资源使用不当，就可能会造成两个功能模块因为相互等待对方使用的资源 而产生死锁现象，从而导致整个操作系统的崩溃。为了协调多线程有效地使用临界状态下的系统资源，还需要用互斥和同步等方法对其线程进行合理地控制。
2．2　数据结构的选择
　　当确定使用多线程技术来提高软件的执行速度后，如何设计数据结构来配合多线程高效工作，如何使应用程序运行时占用的内存空间最少就成为下一步要解决的主要问题。
　 　通过对数据的使用特性进行分析，可以发现尽管原始数据十分庞大，但都是以顺序地方式被程序读取的，因此可以先将他们存贮在一个单向的、先进先出的数据结 构—队列中。由于队列是单向的，当其中的数据被使用后，需要原始数据的消费类线程必须等待生产类线程重新添满数据队列后才能开始工作，这无疑在一定程度上 影响了软件的执行效率。使用首尾相接的循环队列可以解决这个问题。通过建立一个足够大的循环队列，可以让程序反复地利用这块内存空间，从而达到节省代码存 贮空间与程序运行空间的目的。同时可以保证数据处理线程总能得到要加工的数据，以流水的方式进行工作。
3　实际应用
　 　下面是一个关于心电检测系统的设计，这个系统的设计目标是快速分析24 h的（ECG）心电数据判断其中是否含有疾病的特征分量。其中原始的心电数据共12路分别对应着12个导联的心电信号，其中每路数据的采样频率为250 Hz，这样每分钟将产生180 kB的数据，每小时的数据量可达10．8 MB，24 h的数据总量将超过260 MB。面对这样大量的数据，检测软件需要对这些心电数据进行复杂的数学运算，提取出心电波形，确定其中P，R，T波等几个关键波形的具体位置，从而进一步 判断出是否有心脏疾病的存在。
3．1　总体设计
　　由于用户要求系统在进行波形检测和疾病诊断的基础上，还可以动态地显示 心电波形及最终的检测结果，同时响应用户输入的其他消息，如波形的前、后滚动显示，波形的放大与缩小等功能。如果程序只使用单线程工作的话，是无法满足这 些需求的，所以本系统根据实现功能的需要专门设计了几类线程来分别完成波形的显示功能（消费类线程）、疾病的诊断功能（消费类线程）和完成添加循环区数据 的功能（生产类线程）。图1显示了本系统中几个基本功能模块的工作流程。

3．2　详细设计
　　为了更好地实现24 h心电数据的处理工作，程序首先根据检测任务的特点把12路的心电数据等量地分配给12个同等优先级的检测线程进行处理，每个检测线程分别完成指定导联的数据检测。
　 　为了加速程序的运行，还需要设计一个读数据的线程，为12个检测线程提供要处理的原始数据。存放数据的缓冲区为一个循环队列组，在一个循环队列中存放的 原始数据可供单个检测线程顺序读取3次。这里还需要设置一个标志数组FlagE［0…11］，其中数组的每1位代表1个循环队列。标志数组的初始值全为 0，当有一路检测线程需要数据时就置数组的相应标志位为1。程序运行时，读数据线程一次性写满缓冲区空间，在启动检测线程的同时将自身的运行状态转为挂起 态。
　　检测线程每次从缓冲区中读取部分的心电数据进行分析，检测线程的处理工作包括：计算P，R，T波的位置，QRS波的大小以及病人的平均心 率，同时把检测结果写入文件中。检测线程处理完数据后把FlagE［0…11］数组中相应位置的标志置1，然后继续顺序读取缓冲区中另一部分原始数据。当 12检测线程　　96把FlagE［0…11］中的标志位置全为1时，说明缓冲区中缺少原始心电数据。添加数据的线程将从挂起态转为运行态更新循环队列中 的原始数据，读入缓冲区中的新数据将覆盖掉无用的旧数据，同时FlagE［0…11］数组中标志被清全为0。这时程序中的检测线程与读数据线程达到了并行 工作的状态。由于系统以随机的方式来调度线程工作，会导致某些检测线程需要的原始数据没有被及时地提供，即FlagE［0…11］中相应的标志位已经置 1，这时需要检测线程自动挂起等待新数据填满后再开始工作。线程对内存空间缓冲区的使用情况如图2所示。

　　在这里每个检测线程独占1个读数据指针，共产生12个读指针，而1个写缓冲区数据指针为12个检测线程共享。其中充当数据缓冲区作用的是一个循环队列组，其数据结构的建立描述如下：

　　判定循环队列的状态是满还是空的方法为：尾指针加1除以队列的最大容量等于头指针，作为队列满的标志。
    队列满　（cq．rear＋1）mod maxsize＝cq．front
    返回函数值为循环队列cq中所含元素个数。
　　这样，就可以保证数据处理线程总能得到要加工的原始数据，并以流水的方式进行工作。同时，程序只需使用少量的内存空间就可以完成海量数据的处理工作。
3．3　线程的控制
　 　由于波形检测线程（消费类线程）、读数据线程（生产类线程）和心电波形显示线程（消费类线程）都存在着对原始心电数据缓冲区和检测结果数据缓冲区这些临 界资源的访问。为了防止这些线程访问临界资源时不会产生死锁现象，在程序中主要采用互斥、信号量同步的方式来对线程进行控制和管理。其中，控制线程协同工 作的具体模式可以归结为如下3种类型。
　　（1）当生产类线程向缓冲池中写数据时，消费类线程不能同时从缓冲池中读数据。生产类线程与消费类线程是互斥的访问关系。
　　（2）当多个生产类线程同时向缓冲池中写数据时，各生产类线程之间是以互斥方式来工作的。
　　（3）当多个消费类线程同时从缓冲池中读数据时，各消费类线程之间是以信号量同步的方式对数据区进行访问。具体模式如图3所示。

　　本系统是使用Delphi 5．0这一编程工具开发的。Delphi5．0编程语言为类PASCAL语言，他封装了大量的API函数并且提供了大量的控制多线程访问系统临界区资源的函数。下面就是程序中使用到的一些具体的控制线程访问的方法。
    （1）互斥访问
　 　在写缓冲区线程与检测线程同时对原始数据缓冲池进行操作时，需要首先调用CreateMutex（）函数来创建一个互斥量，使程序以互斥方式访问临界区 时。然后，需要使用WaitForSingleObject（）函数来防止多个线程同时进入同步区的代码。代码退出同步区后，应使用 ReleaseMutex（）函数来释放互斥量，让其他线程获得进入互斥区的机会。使用完互斥对象后，应当调用CloseHandle（）函数来关闭他。
    （2）信号量
　 　信号量是在互斥的基础上建立的，他增加了资源计数的功能，允许预定数目的线程同时进入要同步的代码区。当十二个检测线程同时来读取循环队列中的数据时就 需要采用信号量的方式。首先用CreateSemaphore（）函数来创建一个信号量对象，同时在同步区中也需要使用 WaitForSingleObject（）函数来阻止其他未获得允许的线程的进入，用ReleaseSemaphore函数来释放信号量，最后使用 CloseHandle（）来关闭信号量对象的句柄。
　　通过使用这样一些函数来控制多线程合理地访问循环队列里的数据，就能使设计出的程序在功能完善的基础上，达到运行高效和空间使用最省的目的。
4　结　论
　 　这是一套应用Delphi语言编程实现的软件，他把循环队列这一基本的数据结构和多线程技术完美地结合在一起。由于多线程减少了并行程序之间的通信量， 所以程序中的串行部分所占的比例要小于传统的编程方法，同时循环队列的使用也提高了内存空间的利用率。由于程序中包含大量的除法运算，还可以采用算术的优 化算法，使程序有更高的并行效率。从运行结果来看，使用多线程技术提高了程序的并行效率和加速比，从而实现了软件设计的目的。