嵌入式Linux中的进程同步无竞争态读写

嵌入式Linux中的进程同步无竞争态读写
2010年06月10日
　　Linux作为一个开源、稳健的操作系统，支持多种平台，拥有丰富的开发工具和应用软件，尤其是其内核可裁减的特性，非常适合嵌入式系统。在数据实时性、准确度要求很高的情况下，系统在对数据的采集和处理过程中，由于其进程协调性问题，往往会造成数据的丢失。利用经典进程同步模型，可解决嵌入式Linux系统中数据同步读写冲突的问题。
　　引言
　　在对实时采集更新的数据进行处理时，往往会遇到数据更新速度与数据处理的速度不匹配的问题。这种情况下，会出现数据丢失而导致数据处理结果不准确，甚至会带来不可预测的后果，因此需要一种机制来协调数据更新与数据处理，从而保证数据的完整性和处理结果的准确性。作为一个多任务、多用户操作系统，Linux支持多个进程在系统中并发运行，由于进程本身的动态特性，用来描述实时数据处理非常合适，因此，解决好Linux进程间的同步与通信问题就能解决实时数据处理的问题。
　　在Linux环境下，进程通常存在运行(running)、阻塞(blocked)、就绪(ready)、终止(terminated)四种状态。当多个进程并发执行时，往往会出现进程间的竞态。我们希望进程能协调彼此间的行为，使得一个进程只有在其他的进程执行到一个特定的点时才会执行一个动作，即控制同步；同时，当并发进程访问共享数据时不应当出现竞争条件。这一点通过在访问共享数据时执行互斥来确保，即数据访问同步。
　　实现同步的基本技术是阻塞一个进程，直到一个特定条件满足为止；实现数据访问同步是通过阻塞一个进程直到另外的进程完成访问共享数据。
　　1 有限长度缓冲区的生产者一消费者问题模型
　　当仅存在单个生产者和消费者时，生产进程和消费进程所对应的是同样的数据结构，它们共享同一个数据空间。生产进程和消费进程如何进行相互协调，使得消费进程每次使用的数据都是生产进程新生产写人的，又使生产进程新写入的数据不会覆盖还未被消费进程读出使用的数据，是该问题模型实现的关键问题。
　　在生产者一消费者问题模型中，生产者进程不断生产产品并把它们放入缓冲区，消费者进程不断从缓冲区中取走产品进行消费。当缓冲区中产品已经放满时，表示生产速度高于消费速度，出现了供过于求，此时生产者必须等待产品被消费；当缓冲区为空时，表示消费速度高于生产速度，出现了供不应求，此时消费者进程必须等待产品的生产。生产和消费的进程必须达到同步运行，才能实现供需平衡。
　　处理读写同步的两种常见的策略被称为"强读者同步(strongreadersynchronization)"和"强写者同步(strongwritersynchronization)"。在强读者同步中，总是给读者以优先权，只要写者当前没有进行写操作，读者就可以获得访问权；在强写者同步中，写者总是获得优先权，只要强读者当前没有进行读操作，写者就可以获得访问权。而生产者消费者同步与单纯的读写同步又有不同，消费者可以通过访问资源对资源进行删除或销毁。
　　一个有限长度缓冲区的生产者消费者问题模型，是由若干生产者和消费者进程以及一个有限的缓冲池构成的。每个缓冲区能够存储一个信息记录，一个生产者一次生产一个信息记录。产生一个记录之后，等待单独进入一个空的缓冲区后将记录写入缓冲区。一个消费者进程一次消费一个信息记录。当它需要消费时，它等待单独进入一个满的缓冲区后将记录读出。
　　通过上面的描述可以得出，解决生产者一消费者问题模型的方案需要满足以下几个条件：
　　.生产者不应覆盖一个满的缓冲区；
　　.消费者不应使用一个空的缓冲区；
　　.生产者和消费者应按互斥方式访问数据缓冲区；
　　.数据必须按照先进先出(FIFO)方式；
　　.不能出现忙等待。
　　必须避免数据写进程不断、反复地检查缓冲区直到找到一个空缓冲区为止，而读进程也必须避免不断检查直到找到一个满缓冲区为止。这相当于系统内部产生忙等待，是在仅使用临界段(CS)算法实现进程同步时难以避免的问题。
　　针对问题模型解决方案的限制条件，采用信号量方式解决实时更新数据处理的进程同步问题，即上述的生产者一消费者问题模型。
　　信号量是一个非负值的共享整数值，只能用于初始化和不可分操作。不可分操作是指在对一个数据D进行操作时不能与任何其他对D的操作重叠的操作。定义操作P和V为不可分操作。P和V的不可分性意味着这些操作不能并发执行，避免了对信号量的竞争条件。定义P和V的操作语义为： 
　　
　　由上述定义的语义看，对一个信号量S的操作，P和V为改变S的值，或者挂起或唤醒一个对S进行P操作的进程。被挂起的进程为阻塞状态，因而避免了忙等待问题。一个二进制的信号量只取0和1，用来实现互斥。
　　在P和V操作中，对进程的阻塞和唤醒需要操作系统的进程管理组件的参与，因此信号量会被操作系统实现而不是应用程序实现。
　　生产者一消费者问题模型描述：    
　　
　　2 结构设计
　　对于有限缓冲区的生产者消费者问题模型的执行包括以下部件：共享数据一缓冲区组、操作一缓冲区的访问、进程一生产者消费者。
　　在生产者一消费者同步中，由生产者创建资源，与单纯的读程序不同，消费者可以通过访问资源，将资源删除或销毁。由于生产者进程和消费者进程共享一个缓冲区，因此在插入和删除条目时必须同步。实现中必须避免表l所列的同步异常问题。 
　　
　　生产者一消费者问题的传统的信号量解决方案使用了2个信号量，分别用来表示缓冲区中的条目数和空闲槽的数目。当进程需要特定类型的资源时，它可以通过函数调用对相应的信号量进行减量操作；同样，当进程释放资源时，它可以通过函数调用来对相应的信号量进行增量操作。由于信号量永远不会降到零以下，所以进程不能使用不存在的资源。因此，始终将计数信号量初始化为开始时可用的资源数。
　　定义循环队列缓冲区存放待处理数据，控制台数据处理进程从该循环队列缓冲区中消费数据，并将该数据存储位标记为"废弃"。数据采集写进程仅能将数据存放于标记为"废弃"的循环队列缓冲区中，如图1所示。
　　
　　在没有多个生产者或消费者的情况下，如果仔细实现，循环缓冲区就不需要锁。生产者是唯一允许修改写入索引以及该索引指向的数组位置的进程。只要写入者在更新写入索引之前将新的值保存到缓冲区，则读取者将始终看到一致的数据结构；同时，读取者是唯一可以访问读取索引以及该索引指向位置的数据的进程。只要确保两个指针不要互相重叠，生产者和消费者可以在无竟态的情况下访问该缓冲区，如图2所示。
　　
　　对于只有单个生产者和消费者，通过使用修正的使用信号量方式的生产者一消费者问题模型解决方案来实现。   
　　
　　以上用信号量方式解决了优先缓冲区问题，信号量"empty"和"full"的值分别指示空和满的缓冲区的数量，如图3所示。缓冲区指针i和j用来确保缓冲区按先进先出的顺序提供并使用。只要系统中存在一些满的和空的缓冲区，数据更新进程和数据处理进程就能无竞态并发执行。笔者在ARM嵌入式平台HHARM2410-R5上按照上述方案成功实现了用例测试。   
　　
　　3 讨论
　　以上的结构设计，将生产者与消费者分别简化为一个。当存在多个生产者和消费者的情况时，可以上述修正的解决方案为基础，设计多个计数器来统计并行读者（reader）、并行写者（writer）、读者或待读者（pre_reader）、写者或待写者（pre_writer）的数量。计数器的值在进程中的相应位置进行增减。读者和写者在被允许阅读和写入之前必须被阻塞，这可以通过P操作来完成。当读者或写者在进程被阻塞时控制开始阅读或书写的条件并未满足。这些条件随着任意一个计数器值的变化而改变，所以，进程在完成阅读或书写后必须执行相应的V操作。
　　在实行多读、多写进程同步解决方案时，必须要避免不同计数器的竞争条件