Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1638744
  • 博文数量: 197
  • 博客积分: 10046
  • 博客等级: 上将
  • 技术积分: 1983
  • 用 户 组: 普通用户
  • 注册时间: 2006-08-07 12:36
个人简介

在外企做服务器开发, 目前是项目经理, 管理两个server开发的项目。不做嵌入式好久了。

文章分类
文章存档

2011年(2)

2010年(6)

2009年(18)

2008年(30)

2007年(100)

2006年(41)

分类: LINUX

2006-08-08 12:29:24

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

日期:2006-08-07 作者:廖光灯 来自:IBM DW


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

自从多线程编程的概念出现在 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来同步共享资源。



图1:传统的多线程编程

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

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

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

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

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

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

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

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

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



图2:优先级队列

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



图3:结构体

在定义中,成员 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 的实现中,我们定义了以下结构体:



图4:结构体

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



图5:结构体

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

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



图6:结构体

基于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。

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

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

为了在用户级别提供这些特性,基于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实现如下:



图7:lll_fuqueue_wait实现

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

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



图8:健壮同步机制的引入

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

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



图9:PI

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



图10:Volanomark测试结果

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

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

  1. Robust Mutex 主页: http://developer.osdl.org/dev/robustmutexes/
  2. "I would hate user space locking if it weren't that sexy". Published in OSL 2004.

原文链接:http://www-128.ibm.com/developerworks/cn/linux/l-fusyn-rt/

阅读(1029) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~