Fusyn + RTNPTL：Linux 实时健壮的同步机制

本文主要叙述了目前 Linux 环境需要提供健壮和实时同步机制的必要性，并提出了实现的一个方案。这种同步机制对于 linux 进一步开拓服务器市场是非常重要的，尤其是电信市场。

1： 背景

自从多线程编程的概念出现在 Linux 中以来，Linux 多线程应用的发展总是与两个问题脱不开干系：兼容性、效率。 早期的 Linuxthreads 在兼容性和效率上都存在了严重的问题，特别是兼容性上的问题，严重阻碍了Linux上的跨平台应用（如Apache）采用多线程设计，从而使得 Linux 上的线程应用一直保持在比较低的水平。在 Linux 社区中，后来它被RedHat公司牵头研发的NPTL（Native Posix Thread Library）而替代。在技术实现上，NPTL仍然采用1:1的线程模型，并配合glibc和Linux内核在信号处理、线程同步、存储管理等多方面进行了优化。和LinuxThreads不同，NPTL没有使用管理线程，核心线程的管理直接放在核内进行，这也带了性能的优化。

虽然 NPTL 无论在兼容性还是在效率上面都大大优于Linuxthread。但是它并没有完全的符合POSIX规范，并不能提供实时的同步机制，而实时的同步机制对于服务器尤其是电信级别服务器是至关重要的。因为如果没有实时的同步机制，就非常容易引起优先级逆转的问题。这对于需要优先级服务的电信服务器来说是致命的。因此提供实时性的同步机制是完善Linux的一个重要环节。

另外在电信服务器上，如果只提供实时的同步机制是远远不够的。因为这些服务器需要提供99.9999% 的高可用性，这也就需要同步原语即使在异常情况下也能够提供高可用性。比如下面有两个线程A和B，它们分别用mutex来同步共享资源。

这里线程 B 先于线程 A 进入了临界区，线程 A 看到已经有人抢占了共享资源，它只好进入睡眠状态等待被 B 唤醒。然而不幸的是，线程 B 在领界区程序的执行过程中遇到了异常的情况，导致线程 B 的退出。这样线程 A 就只能沉睡下去永远无法被唤醒。如果线程 A 是一个有时间限制的客户服务，那就肯定无法按时完成客户的请求了。

鉴于以上的分析，我们认为为了让 Linux 在服务器市场上大展手脚，它至少需要提供实时并且健壮的同步机制。Intel OTC 的 Robust Mutex 正是为了提供这种服务而设立的一个项目。它不仅为 Linux 同步机制提供了实时的特性避免了优先级逆转， 也提供了健壮的同步原语，另外也引入了动态死锁的检测模块。在技术上，整个项目包括两个部分：Linux 内核补丁即 Fusyn 和 Glibc 即 RTNPTL。以下的章节将介绍它们的基本实现原理。

回页首

2: Fusyn

Fusyn 是 Linux 内核的一个补丁，它在内核层次上解决了以上的一些问题，主要提供了以下几个特性：

1. 用优先级继承(PI)和优先级保护(PP)的策略来避免优先级逆转

2. 基于优先级提供了实时的唤醒机制

3. 提供了健壮性的同步机制

4. 同时也提供了死锁的检测机制

为了能够和 NPTL 更好的相处，Fusyn 采用了层次化的设计原则，在第一层上是Fuqueue。它和NPTL的等待队列 wait queue 类似，不同的是它提供了基于优先级排列的等待队列，这样就为提供优先级的唤醒机制奠定了基础。基于 Fuqueue，Fusyn 建立了 Fulock 层次，这个层次记录了每个同步锁的拥有者的信息，为提供锁的健壮性打下了基础。

2.1 Fuqueue

Fuqueue 和 Linux 内核中的等待队列类似，不同于普通的等待队列是基于 FIFO 策略的，而 Fuqueue 如下图所示，它是一个基于优先级排列的等待队列。

因此当要唤醒下一个线程的时候，就会根据优先级进行唤醒，这样就提供了一些实时的特性。为了提供这种功能，结构体的定义如下：

在定义中，成员 wlist 是一个按优先级排列的队列，而 fuqueue_ops 为一些 fuqueue相关的函数指针，如改变优先级函数 fuqueue_waiter_chprio() 和取消等待函数fuqueue_waiter_cancel() 等。为了使用优先级等待队列，可以先用 fuqueue_init() 函数进行初始化，当需要根据优先级插入到等待队列睡眠的时候，可以利用 fuqueue_wait() 函数。如果想根据优先级唤醒下一个线程，fuqueue_wake 则可以实现这种功能。另外为了能够提供 fulock 避免优先级逆转的功能，也实现了fuqueue_waiter_chprio() 函数，这个函数能够设置某一个线程的优先级并重新排序等待队列。而 fuqueue_waiter_cancel 则用来取消等待唤醒等待线程。

为了让 fuqueue 的功能也能够直接在用户空间得到应用，我们需要为它增加数据结构来记录用户空间同步锁和 fuqueue 队列的对应信息，在 Fusyn 的实现中，我们定义了以下结构体：

在这里 vlocator 被用来在内核空间代表用户空间的同步锁，也即每一把用户空间的同步锁都在内核中存在了一个 vlocator 结构体，这样 ufuqueue 结构体就可以容易的把 fuqueue 等待队列和用户空间的同步锁直接联系起来。那么在 Linux 的同步原语的实现中，同步锁在内核中怎么标志呢？在 NPTL 的实现当中，线程间的同步锁用锁的虚拟地址表示，而进程间的同步锁则需要借助于文件系统来表示。因此结构体 vl_key 的定义如下：

另外在 vlocator 的实现中，它采用了类似 JAVA 的垃圾回收机制，当refcount为零时，就有垃圾回收器对其进行回收。基于 ufuqueue 结构体，我们提供了 sys_ufuqueue_wait，sys_ufuqueue_wake 和sys_ufuqueue_ctl 三个系统调用，这样 GLIBC 就可以直接利用以上的 3 个系统调用利用fuqueue 提供的优先级队列的服务了。

2.2 Fulock

基于以上介绍的优先级队列fuqueue，我们在fuqueue之上构造了提供健壮同步锁的Fulock。基本原理是跟踪每一个同步锁的目前占有者信息。结构体定义如下：

基于fulock结构体，fusyn提供了两个函数接口fulock_lock和fulock_unlock，当调用fulock_lock的时候，它通过olist_node成员把fulock结构体挂入到线程结构体task_struct的成员struct plist fulock_olist中去，同时在fulock中设置owner的信息。而释放的时候则相反。这样，当一个锁的拥有者非法退出的时候，do_exit()函数则对每一个它拥有的锁进行释放并唤醒一个正在等待的线程，同时并设置锁的状态为FULOCK_FL_DEAD，使被唤醒的线程的返回值为-EOWERDEAD。基于EOWERDEAD标志，返回线程可以判断锁是否可以继续运行并通过函数fulock_ctl来设置其状态。

和Fuqueue一样，为了扩展到用户空间的同步锁，fulock也引入了ufulock和一些系统调用：sys_ufulock_lock, sys_ufulock_unlock和sys_ufulock_ctl。

2.3 其他

除了以上的功能，fusyn还提供了PI和PP机制来避免优先级逆转，当使用PI或PP机制的时候，每一个线程遍历它所拥有锁的队列找出一个最高的优先级，然后暂时的设置自己为那个最高优先级。当它释放每一个锁的时候，再根据队列重新调整自己的优先级。通过这种办法就可以解决优先级逆转的问题。

另外，Fusyn也引入了死锁的检测机制，每当调用fulock_lock的时候，它都会通过调用函数__fulock_check_deadlock进行死锁的检测。

回页首

3: RTNPTL

为了在用户级别提供这些特性，基于Fusyn，我们也需要在通常的NPTL线程库中添加相应的接口，目前支持的同步机制包括：mutex，rwlock，conditional variable 和semaphore。

首先，RTNPTL定义了一些通用变量，如同步锁类型以及避免优先级逆转的协议,定义如下

Enum {
            PTHREAD_MUTEX_NOROBUST_NP,
            PTHREAD_MUTEX_ROBUST_NP,
            PTHREAD_MUTEX_ROBUST2_NP
            };
            Enum {
            PHTREAD_PRIO_NONE=1,
            PTHREAD_PRIO_INHERIT,
            PTHREAD_PRIO_PROTECT
            };
            

然后，为了更好的实现Glibc中的各种同步机制，我们实现了通用的底层接口，如__lll_rtmutex_timedlock，__lll_rtmutex_unlock，__lll_rtmutex_ctl 等。通过这些接口，上层的各种同步原语可以得到较为简单的实现。和 NPTL 不同，这里的底层函数是调用了 Fusyn提供的系统调用接口，这里给出 __lll_rtmutex_timedlock 函数实现的一些基本步骤如下：

1：先对用户空间 vfulock 进行判断，看锁是否已经被人占有。

2：如果锁还没有被人占有，就调用 Fusyn提供的系统调用sys_ufulock_lock，格式如下：result = INTERNAL_SYSCALL (ufulock_lock, err, 3, vfulock, flags, timeout);这个调用会让线程进入到Linux内核进行等待，直到别的线程已经退出临界区或者拥有锁线程的退出的时候，函数返回相应的返回值。

3：由于ufulock_lock会返回不同意义的结果，如果是ENOTRECOVERABLE，那么就马上返回结果ENOTRECOVERABLE给线程，否则就重新返回第1步进行抢锁。

在mutex，rwlock，conditional variable 和semaphore的同步机制实现中，除了调用这些底层的同步机制，我们在它们各自的原语实现中实现了一些特有的特性。这样在用户空间的程序，就可以先对同步锁设置属性PTHREAD_MUTEX_ROBUST_NP使它成为健壮锁，然后就可以直接调用Glibc提供的一些同步接口如pthread_mutex_lock等来提供实时健壮的特性了。

如果我们在用户空间中，只想使用同步机制的实时特性而不需要健壮性，这就需要在GLIBC的实现中提供实时的一套实时接口。因此我们在GLIBC中也实现了底层的实时相关的通用函数供上层调用，它们为lll_fuqueue_timedwait，lll_fuqueue_wait, lll_fuqueue_wake和lll_fuqueue_ctl。lll_fuqueue_wait实现如下：

这里lll_fuqueue_wait是通过调用Fusyn提供的fuqueue系统调用从而提供优先级的特性的。类似的还包括lll_fuqueue_wake和lll_fuqueue_ctl。这样当用户空间程序只想用实时特性的时候，就只需要直接调用Posix提供的相应接口而不需要设置锁的健壮性了。

回页首

4: 实验

基于以上特性的支持，在我们的实验中调整了线程的代码，我们很容易的避免了在图一出现的问题。这里我们假设同步锁已经被设置为健壮的属性，调整线程A的代码如下：

由于提供了健壮的同步机制，这样当线程B还在临界区的时候异常退出，同步机制就可以通知在等待的相应的线程，因此在线程A中，和以往不同，在调用Pthread_mutex_lock的同时，可以判定返回值是否是EOWNERDEAD,也即锁的拥有者是否已经退出，如果是，就进一步检查它自己是否可以恢复环境，并对此进行相应的处理。通过这样的机制，我们可以轻松的避免线程A永远等待的情况了。同理，在我们的实验中我证明了实时特性的有效性。

除了提供健壮的同步机制以外，它还提供了避免优先级逆转策略PI 和PP的两种接口，用法非常简单，只要在初始化同步机制的时候指定响应的策略PI或者PP就可以在我们的程序中避免优先级逆转，下图给出了PI策略中的线程优先级的变化，从图中可以明显看出同步锁拥有者的优先级提升。

最后，我们也对 Fusyn 架构进行了性能上的测试，因为我们并不希望引入太多的额外开销。我们通过了开源的网络测试工具 volanomark 对其性能进行测试，测试环境为 2 P3 933, 512MB RAM 和 Fedora Core2， 得到结果如下：

从图中可以看出，我们的机制并没有引入了大的额外开销，因此我们有理由相信它适合被更多的应用程序所应用。

回页首

5: 结束语

本文首先介绍了目前 Linux 提供实时健壮同步机制的必要性，并给出了一种实现方案。同时对这个方案在内核和 glibc 库的实现给予了介绍，最终给出了一些实验结果。