Linux操作系统信号量机制的实时化改造

2013-08-10李长松蒋泽军

电子设计工程 2013年10期

李长松，蒋泽军

（1.西北工业大学计算机学院，陕西西安 710129；2.西北工业大学陕西西安 710129）

Linux操作系统因其源代码开放、运行效率高、功能强大、安全性好等特点，在高等院校、银行、研究机构甚至许多商业领域得到了广泛的应用。随着嵌入式行业的发展，Linux也越来越多的应用到一些具有实时性要求的领域。但是，由于Linux操作系统设计的初衷是通用的分时操作系统，其应用于实时系统时仍有诸多的不足之处需要改进[6]。

Linux是一个多用户多任务的操作系统，为了避免多个任务同时进入临界区而造成的运行结果不确定，Linux为用户提供了信号量[1，7]机制来实现进程间的同步。

本文在对System V信号量机制进行了深入的研究之后，发现其在应用于实时系统时存在的不足之处，并提出了对其进行改进的方法。

1 System V信号量机制

1.1 System V信号量机制

Linux使用System V引入的机制，来支持用户进程的进程间同步和通信，其中信号量机制用于进程间的同步。System V信号量在ipc/sem.c中实现，对应的头文件是＜sem.h＞。System V的信号量实际上是一个信号量集，其中包含一个或多个信号量。

1.1.1 System V信号量机制重要的数据结构

对于系统中的每个信号量集，内核维护一个strcut sem_array类型的数据结构，其主要成员包括：struct kern_ipc_permsem_perm； struct sem* sem_base； struct list_head sem_pending； int sem_nsems。其中 kern_ipc_perm 结构中含有当前这个特定信号量集的键值、访问权限等信息；sem_pending指向待决信号量操作链表，用于将信号量集与睡眠进程关联起来，该进程申请执行信号量的操作，但目前不允许其执行；sem_nsems为当前信号量集中所包含的信号量数；sem_base是信号量结构，用于维护信号量集中某个给定信号量的一组值，该数据结构中包含3个成员：int semval表示信号量的当前实际值，int sempid表示对其值最后一次进行操作的进程ID，struct list_head sem_pending是一个双向链表节点结构，当信号量集中只有一个信号量时，该结构指向待决信号量操作链表，用于将信号量与睡眠进程关联起来。

每一个在信号量集上被阻塞的进程对应一个struct sem_queue类型的结构，我们称之为待决信号量操作结构体，其主要成员包括：struct task_struct*sleeper为睡眠进程的进程描述符，int pid为睡眠进程的进程ID，struct sembuf*sops为睡眠进程的待决操作数组，int nsops为待决操作数组中元素的数目，该结构体通过一个list_head型成员被链接在相应的信号量集上，当该信号量集中只有一个信号量时，该结构体通过另一个list_head型成员被链接在该信号量的数据结构上。

待决操作数组sops用于描述在信号量上将要执行的操作，其数据结构的主要成员包括：unsigned short sem_num为信号量在信号量集中的索引，short sem_op为所要进行的操作，short sem_flg为操作标志。

1.1.2 System V信号量相关的系统调用

所有对信号量的操作都使用一个名为ipc的系统调用[2，4]来执行。 asmlinkage long sys_ipc （unsigned int call， int first，unsigned long second，unsigned long third，void__user*ptr，long fifth）；该系统调用不仅用于信号量，也可用于操作消息队列和共享内存，其第一个参数call用于将实际工作委托给其他函数，本节讨论用于信号量操作的函数。Call的值与对应所调用的函数关系如表1所示。

表1 函数调用对应表Tab.1 Function call corresponding table

sys_semctl函数对一个信号量集执行各种控制操作，包括获取/设置信号量集中某个/全部信号量的当前值，将某个信号量集删除等。

sys_semget函数创建一个信号量集或访问一个已存在的信号量集。

sys_semtimedop函数对信号量集中的一个或多个信号量进行操作，如果是对多个信号量进行操作，则这些操作要么全做要么一个都不做。

1.2 优先级反转现象描述

假设这样一种情况：系统中有3个具有不同优先级的任务H，M，L。其中H的优先级最高，M次之，L最低。H和L共享同一个由信号量保护的临界资源R，L最先就绪并获得临界资源R的使用权，这时具有较高优先级的任务H也获得就绪并申请访问临界资源R，但是由于R已经被L占有，所以H必须等待。而此时M任务就绪，并且由于其优先级高于正在运行的L而将其抢占。这样H任务必须等待优先级较低的M任务运行完毕才有机会获得运行，就好像是M任务比H任务有了更高的优先级。这就是所谓的优先级反转[3]现象。如果H任务是一个实时任务，这一问题将严重增加H的延迟时间，降低系统的实时性。

对于System V的信号量集，优先级反转的问题更加复杂，这是因为System V信号量集中可以包含多于一个信号量，并且进程每次对System V信号量所保护资源的申请和释放都可能多于一个。

System V信号量存在的另外一个问题是，其不对实时进程和普通进程做区分，当请求信号量集的进程无法一次性获得信号量集中的所有信号量时一律将其插入到sem_pending队列的尾部，并且唤醒进程的操作是从队列的头部选取可以获得运行的进程。这种情况下，相当于在信号量集上阻塞的实时进程和非实时进程有相同的机会获得信号量集，而与他们的优先级大小无关，这样势必会导致实时进程延迟的增加。

2 System V信号量机制的实时化改造

2.1 优先级继承机制简介

既然优先级反转问题会增大实时任务的延迟时间，我们需要想办法来避免这一问题。对于优先级反转问题一般有优先级天花板和优先级继承两种解决方案。

优先级天花板是指，当任务申请访问某一临界资源时，立即将其优先级提升到能够申请访问该资源的任务中最高的优先级。这种方案所存在的问题是优先级反转只是在很少情况下才会发生的事情，如果不进行任何判断直接将申请访问临界资源的任务优先级提高，势必会为系统增加许多不必要的开销。而且在实际系统中很难预测可能访问临界资源的任务集合。因此本文采用优先级继承机制。

优先级继承机制的原理是：当较高优先级的任务H试图获得临界资源R时，如果此时R已经被较低优先级的任务L占用，那么为了使H能够尽快获得调用运行，而将L的优先级临时提升到和H相同的水平，从而让L以H的优先级参与调度，尽快让L执行并释放掉H正在请求的临界资源R，待L释放R时再将其优先级还原到优先级继承前的水平。

优先级继承的可传递性指的是：当较高优先级的任务H将优先级借给较低优先级的任务L后，L又去申请另外一个临界资源S，而S已经被另外一个较低优先级的任务A占用，这时应该同样将A的优先级临时提升到与H相同的水平，待A释放资源S后再将其优先级还原。

2.2 将优先级继承机制运用于System V信号量

System V信号量功能十分强大，它可以同时保护几个同种类型或不同类型的临界资源，但是这也导致了将优先级继承机制运用于System V信号量时有诸多的复杂之处。

首先System V信号量均采用信号量集的实现形式，在一个信号量集中包含1个或多个信号量，用户可以同时对信号量集中的一个或多个信号量进行操作。而优先级继承机制是针对某一个信号量的，这就要求在信号量集中的每一个互斥信号量上实现优先级继承机制。其次，System V信号量包括计数信号量和互斥信号量，优先级继承机制是针对互斥信号量的，对计数信号量则不做修改。互斥信号量一般指其初始值为1的信号量，而System V信号量机制规定，对信号量的申请、释放即通常所说的P、V操作均不限定于1。这一规则使我们很难判断一个System V信号量是否属于互斥信号量。本文对于这一问题的解决方案是，规定只将初始值为1的信号量视为互斥信号量，而对于初始值为n申请、释放单位也为n的情况，视为应用程序编程的不规范，应由用户自己避免。

此外为了让被阻塞的实时进程尽快得到运行，当其申请信号量集失败时，我们将其按照优先级顺序插入到待决操作链表，而对于非实时进程则直接将其插入到待决操作链表的尾部，这样做可以保证实时进程按照优先级由高到低的顺序获得信号量，而非实时进程是FIFO的顺序，并且所有实时进程均排在非实时进程前面。这样做可以有效减少实时进程申请信号量的延迟时间。

2.2.1 对Linux内核源码相关结构体的修改

首先，需要修改信号量结构体struct sem，增加下列成员：bool if_twovalue；若为互斥信号量此项为1，否则为0；struct task_struct*owner；互斥信号量被某进程持有时，owner指向其进程结构体；int old_prio；记录进程的原始优先级；unsigned long old_policy；记录进程的原始调度策略。

2.2.2 函数体的修改

对Linux源码函数体的修改主要包括初始化、申请信号量未成功、申请信号量成功、释放信号量4个部分。在此分别描述如下：

初始化：在struct sem中新增加if_twovalue、owner两个成员后，需要在初始化信号量初始值的同时对其进行初始化，为此需要修改函数static int semctl_main（struct ipc_namespace*ns，int semid，int semnum，int cmd，int version，union semun arg），在该函数中将owner初始化为NULL，如果信号量的初始值为1，把if_twovalue项初始化为1，否为为0。

申请信号量成功：在进程申请信号量成功的情况下，如果此信号量的if_twovalue项为1，则表示该信号量为互斥信号量，进程在持有该信号量期间有可能发生优先级反转，需要在信号量结构体中记录进程的进程描述符，以方便在发生优先级反转时，对该进程执行优先级继承，为此需要修改函数 staticinttry_atomic_semop（structsem_array*sma，structsembuf*sops，int nsops，struct sem_undo*un，int pid），在该函数中做判断，如果信号量为二值信号量，则将该进程的进程描述符记录在信号量的owner项中。如果最后进程没有成功申请到该信号量集，则需将信号量集中所有信号量结构的owner项还原为NULL。

申请信号量未成功：如果是普通进程申请信号量集，不对其申请过程进行任何修改。而对于实时进程，如果其申请互斥信号量时被阻塞，则将其优先级暂时“借给”该信号量当前的持有者。然后将其待决操作结构体按优先级由高到低的顺序插入到信号量集的待决操作链表中，如果其只申请了一个信号量，则还需要将其待决操作结构体按优先级由高到低的顺序插入到相应信号量的待决操作链表中。为此修改函数asmlinkagelongsys_semop（intsemid， struct sembuf__user*sops，unsigned nsops）；在该函数中判断，如果被阻塞进程为实时进程，则将进程的待决操作结构体按优先级由高到低的顺序插入到信号量集的待决操作链表中，否则将其插入到信号量待决操作链表的尾部。如果信号量集中只有一个信号量，还需要将进程的待决信号量操作结构体与该信号量结构体链接起来。由于执行优先级继承是针对信号量集中的单个信号量的，所以依次对信号量集中的每一个信号量做判断，如果为互斥信号量、当前已被某一进程所持有、信号量操作为-1并且被阻塞进程的优先级比持有该信号量的进程优先级高，则将持有信号量进程的原始优先级和调度策略保存在信号量结构体中，并用被阻塞进程的优先级和调度策略分别为其赋值。

在执行了优先级继承时，还需要保证优先级继承的可传递性，考虑这样一种情况：H、M、L是优先级从高到低的3个任务，R、S是保护某两个临界资源的信号量。M已经持有R信号量，而L已经持有S信号量并且在申请R信号量时被阻塞。此时H任务就绪并申请S信号量，则按照上面优先级继承的规则H任务被阻塞在信号量S上，并将自己的优先级继承给L。但是L此时为阻塞状态，所以为了让L将继承自H的优先级传递给M，必须在优先级继承之后，调用wake_up_process对L执行一次唤醒操作，L被唤醒之后会将其继承到的优先级传递给M。

释放信号量：在进程释放信号量时，将相应信号量结构struct sem的owner项重新置为NULL。并且需要判断该进程是否继承了其他进程的优先级，如果是则需要将其优先级还原，为此修改函数static int try_atomic_semop（struct sem_array*sma，struct sembuf*sops，int nsops，struct sem_undo*un，int pid），在该函数中做判断，如果当前信号量为互斥信号量且信号量操作为+1时，将信号量结构体的owner项置为NULL，并使用信号量结构体中的old_prio和old_policy两项将进程的优先级和调度策略还原。

3 改造后的System V信号量性能测试

对System V信号量进行改进后，需要对其进行测试来确定是否达到了预期的目的，测试的主要指标是实时进程申请信号量的延迟时间受其他进程影响的程度。

为了更好的表现优先级继承后的效果，我们设计了这样一组进程：3 个进程 H（High）、M（Middle）、L（Low），其中 H 为实时进程，M、L为普通进程，其优先级分别为-5、5（值越低优先级越高），H、L竞争一个信号量S，H获得信号量后计算延迟时间，然后释放信号量并sleep 230 ms，L在获得信号量后进行大约500 ms的数学计算然后释放信号量，M则一直在进行数学运算。我们测试了只有H、L两个进程时的延迟时间std作为基准，然后测试了有H、M、L 3个进程且未执行优先级继承时的延迟时间orig以及有H、M、L 3个进程且实现了优先级继承时的延迟时间pinh，测试结果如图1所示。