论文部分内容阅读
摘要：NPTL（本地POSIX线程库）具有较好的性能和稳定性，已成为Glibc的首选线程库。同步是为了达到多线程协同工作目的而设计的一种机制。线程库中同步函数的底层实现大多用汇编语言编写，因此，在将NPTL移植到不同嵌入式硬件平台时，必须重写相关代码。通过引入一个虚拟的锁设备，实现原子操作，进而实现同步函数，最小化硬件平台的相关性，方便地实现不同嵌入式平台上NPTL的同步机制。
关键词：线程；同步；原子操作
中图分类号：TP316文献标识码：A文章编号：1009-3044(2008)31-0880-02
Implementation of Thread Library’s Synchronization Mechanism in Embedded System
JIANG Lan-fan
(Software College, Fuzhou University, Fuzhou 350108, China)
Abstract: NPTL(Native Posix Thread Library) have better performance and stability, and have already become the preferred thread library of Glibc. Synchronization is a Mechanism designed to harmonize works between multithread. The bottom implementation of synchronization functions are mostly programmed with assembly language, therefore, related coeds should be rewritten when migrating NPTL to different hardware platforms. Atomic action can be implemented by introducing a virtual lock device, furthermore, synchronization functions can be accomplished. Relativity of hardware platform can be minimized in this way, therefore, NPTL’s synchronization Mechanism can be expediently realized in different embedded platforms.
Key words: thread; synchronization; atomic action
1 引言
NPTL（Native Posix Thread Library）[1]使用Linux2.6内核的新特性重写了Linux的线程库，取代历史悠久而备受争议的LinuxThreads成为Glibc的首选线程库[2]。与传统的LinuxThreads线程库相比，它在性能和稳定性方面都进行了重大的改进。
目前，NPTL支持的硬件平台有限，尤其在嵌入式领域，普遍使用的Linux线程库仍是LinuxThreads。因此，研究NPTL在嵌入式系统中移植的关键技术具有一定的现实意义。
多个线程并发执行能极大地提高程序的运行效率[3]。但线程之间资源共享的机制也使得多个线程经常需要同时对某一资源进行访问，形成对共享资源的访问冲突[4]。解决冲突的一个好办法就是在设计中引入同步机制。线程库中同步函数的底层实现大多用汇编语言编写，因此，在将NPTL移植到不同嵌入式硬件平台时，必须重写相关代码。
通过引入一个虚拟的锁设备，以系统调用的方式进入核心态以实现原子操作，进而实现同步函数，将硬件平台相关性最小化，使得移植过程中能够方便地实现NPTL的同步机制。
2 原子操作
所谓原子操作，就是该操作绝对不会在执行完毕前被任何其它任务或事件打断，也就是说，它是最小的执行单位。原子操作的三个步骤是：读数据、修改数据、然后重新写入新数据。原子操作是同步机制实现的基础。
设计中主要在线程库中实现3个原子操作函数，其定义及功能说明如下：
1) int cmpxchg(volatile void *ptr, int old, int new)；
此函数比较old值和ptr所指的内存中的值，如果相等，把ptr所指的内存中的值设置为new；如果不相等，则不进行这个设置操作。无论是否进行这个设置操作，函数的返回值都是ptr所指的内存中原来的数值。
2) int xchg(int x, void *ptr);
此函数不进行比较操作，直接将ptr所指的内存地址中的值设为x，并返回ptr所指的内存地址中原来的数值。
3) int atomic_dec_and_test(int *ptr);
此函数原子地将ptr所指内存地址中的值减去1，如果得到的值为0，则返回1，其他情况都返回0。
2.1 原子操作的核心实现
在系统中添加一个虚拟设备文件“lock”，使用该设备文件的ioctl系统调用进入核心态，通过传入参数的不同便可分别实现3个原子操作函数。
2.1.1 虚拟设备驱动的实现
嵌入式Linux操作系统使用数据结构file-operation为所有的设备文件都提供了统一的操作函数接口。不同类型的文件有不同的file-operation成员函数。每个进程对设备的操作最终都会转换成对file-operations结构的访问。在驱动程序中，需根据功能要求，完成file-operations结构中各函数的实现，不需要的函数接口可以直接在file-operations结构中初始化为NULL[5]。file_operations变量会在驱动程序初始化时，注册到系统内部，当操作系统对设备进行操作时，会调用驱动程序注册的file-operations结构中的函数，以实现相应功能。
由于并不对应一个具体的硬件设备，因此在初始化操作中，并不需要向系统申请资源，只需向系统注册该字符设备即可。驱动程序的open、close函数不做任何操作，直接返回0。驱动中file_operations结构的实现如下：
static struct file_operations lock_fops = {
ioctl: lock_ioctl,
open: lock_open,
release: lock_close,
};
2.1.2 ioctl的实现
ioctl是设备驱动程序中对设备的I/O通道进行管理的函数。所谓对I/O通道进行管理，就是对设备的一些特性进行控制，例如串口的传输波特率等。ioctl函数是文件结构file_operations中的一个属性分量，如果在驱动程序中提供了对ioctl的支持，用户就可以在用户程序中使用ioctl函数控制设备的I/O通道。核心驱动程序中的ioctl函数的实现形式为：
int lock_ioctl(struct inode *inode, struct file *file, unsigned int cmd, unsigned long arg);
在ioctl函数中，一般用一个switch-case结构来实现，每一个case对应参数cmd传入的一个命令码，做出一些相应的操作。在核心驱动程序中定义的命令码要与应用程序中定义的命令码一致，以保证命令的正确发送。对应不同的cmd，所传入的参数个数不同。若应用程序所需传入的参数个数大于1，在用户程序中调用ioctl时，可将所需传入的参数放入一个数组中，此时arg表示用户程序中参数数组的起始地址。实现所对应的伪码为：
定义全局命令码；
int lock_ioctl(…)
{
Switch(cmd){
case cmpxchg()函数的调用:
关中断；
将各项参数从用户空间挎贝到内核空间；//可用copy_from_user函数实现
从指定内存中将值挎贝至内核空间；//可用get_user函数实现
if(指定内存中的值与old的值相等) //cmpxchg(ptr, old, new)
将new值挎贝至用户空间指定内存；//可用put_user函数实现
开中断；
return 指定内存中的原值；
case xchg()函数的调用：
关中断；
将各项参数从用户空间挎贝到内核空间；
从指定内存中将值挎贝至内核空间；
将用户指定的值挎贝至用户指定地址；
开中断；
return 指定内存中的原值；
case atomic_dec_and_test()函数的调用:
关中断；
从指定内存中将值挎贝至内核空间；
将得到的值减1；
将减1后的值挎贝至用户指定内存；
开中断；
if(减1后的值为0)return 1;
elsereturn 0;
}}
2.2 原子操作函数的实现
核外线程库中的3个原子操作函数都是通过对“lock”设备文件执行ioctl系统调用实现的，主要过程大体相似，只是在使用各原子操作函数时，所需指定的参数个数不同。因此，在调用ioctl时，所需传入核心的参数个数若大于1个，则将各参数封装进一个数组中，再传入数组的首地址；若只需传入1个参数，则直接传入该参数的地址即可。具体实现伪码为：
定义与核心实现相对应的全局命令码；
int 原子操作函数(…)
{
用数组保存需要的各项参数；
利用open系统调用打开设备文件“/dev/lock”；
用不同的命令码对已打开的设备文件调用ioctl，并保存ioctl的返回值；
关闭设备文件；
返回相应ioctl调用的返回值；
}
3 同步操作的实现
同步操作是基于原子操作及Linux 2.6核心的futex(快速用户空间互斥体)机制实现的。用于同步操作的全局变量有3个状态：0代表没有上锁，即资源可用；1代表上了锁即资源已被占用，但没有线程在等待此资源；2代表有一个或多个线程在等待这个资源被释放。采用lll_lock(int *val)/lll_unlock(int *val)函数对来实现NPTL中的同步操作。
3.1 lll_lock()函数的实现
对于lll_lock(int *val)函数，针对不同的*val值，将进行不同的操作：
1) *val==0：在这种情况下，表示资源可用，即当前线程可以获得这把锁，同时要把*val设置为1。
2) *val==1：当前线程被阻塞并进入内核睡眠。在这种情况下，意味着资源已被其它线程占用，那么当前线程只能等待。此时，将*val设置为2，然后利用futex系统调用将当前线程挂起。当前线程将在“*val==2”这个futex值上睡眠，直到另外一个线程使用futex系统调用将其唤醒。
3) *val==2：和*val=1情况基本一致，也是进入内核睡眠，只是不需要再设置*val的值。
lll_lock()函数实现的伪码如下：
lll_lock(int *val)
{
if(cmpxchg(val,0,1)) /*若*val的值为0，则表示此资源可用，上锁成功*/
{ /*若*val的值不为0，则表示此资源已被占用*/
if(*val的原值为1)
c=xchg(2,val); //原子地将val的值置为2，表示有线程在等待此资源
do{
利用futex系统调用将当前线程在val为2时挂起；
c=xchg(2,val);
} while(c)//循环等待直至val的值为0
}}
3.2 lll_unlock()函数的实现
与lll_lock()函数类似，在lll_unlock()函数中，针对不同的*val值，也将进行不同的操作：
1) *val==2：在这种情况下，表示有线程在等待此资源，此时进行解锁操作，即将*val的值置0，同时利用futex系统调用唤醒在val上等待的一个线程。
2) *val==1：在这种情况下，表示没有线程在等待此资源，此时只需进行解锁操作，不需用futex系统调用进入内核。
lll_unlock()函数实现的伪码如下：
lll_unlock(int *val)
{
if(!atomic_dec_and_test(val))
{//*val减1后不为0，即*val原值为2，表示有线程在此资源上等待
xchg(0, val);//解锁操作，原子地将*val的值置0
利用futex系统调用唤醒在val上等待的一个线程；
}}
4 结束语
同步是为了达到多线程协同工作目的而设计的一种机制。通过添加一个虚拟的锁设备，利用该设备文件的ioctl系统调用，根据传入参数的不同实现不同的原子操作，进而在应用层实现同步函数，将硬件平台相关性最小化，使得移植过程中能够方便地在嵌入式平台上实现NPTL线程库的同步机制。
参考文献
[1] Drepper U,Molnar I.The Native Posix Thread Library for Linux[EB/OL].http://people.redhat.com/drepper/nptl-design.pdf.
[2] 杨沙洲.Linux 线程库性能测试与分析[EB/OL].http://www.ibm.com/developerworks/cn/linux/l-nptl/index.html.
[3] 刘学超,杨宏伟,李玉霜.Java中同步线程的实现[J].商场现代化,2007(4):69-71.
[4] 黄丹,邵惠鹤.基于Windows CE平台的多线程编程[J].微计算机信息,2007,23(12):53-55.
[5] 谭跃,蒋新华.Linux中字符设备驱动程序开发的研究[J].福建电脑,2007(11):86-87.
关键词：线程；同步；原子操作
中图分类号：TP316文献标识码：A文章编号：1009-3044(2008)31-0880-02
Implementation of Thread Library’s Synchronization Mechanism in Embedded System
JIANG Lan-fan
(Software College, Fuzhou University, Fuzhou 350108, China)
Abstract: NPTL(Native Posix Thread Library) have better performance and stability, and have already become the preferred thread library of Glibc. Synchronization is a Mechanism designed to harmonize works between multithread. The bottom implementation of synchronization functions are mostly programmed with assembly language, therefore, related coeds should be rewritten when migrating NPTL to different hardware platforms. Atomic action can be implemented by introducing a virtual lock device, furthermore, synchronization functions can be accomplished. Relativity of hardware platform can be minimized in this way, therefore, NPTL’s synchronization Mechanism can be expediently realized in different embedded platforms.
Key words: thread; synchronization; atomic action
1 引言
NPTL（Native Posix Thread Library）[1]使用Linux2.6内核的新特性重写了Linux的线程库，取代历史悠久而备受争议的LinuxThreads成为Glibc的首选线程库[2]。与传统的LinuxThreads线程库相比，它在性能和稳定性方面都进行了重大的改进。
目前，NPTL支持的硬件平台有限，尤其在嵌入式领域，普遍使用的Linux线程库仍是LinuxThreads。因此，研究NPTL在嵌入式系统中移植的关键技术具有一定的现实意义。
多个线程并发执行能极大地提高程序的运行效率[3]。但线程之间资源共享的机制也使得多个线程经常需要同时对某一资源进行访问，形成对共享资源的访问冲突[4]。解决冲突的一个好办法就是在设计中引入同步机制。线程库中同步函数的底层实现大多用汇编语言编写，因此，在将NPTL移植到不同嵌入式硬件平台时，必须重写相关代码。
通过引入一个虚拟的锁设备，以系统调用的方式进入核心态以实现原子操作，进而实现同步函数，将硬件平台相关性最小化，使得移植过程中能够方便地实现NPTL的同步机制。
2 原子操作
所谓原子操作，就是该操作绝对不会在执行完毕前被任何其它任务或事件打断，也就是说，它是最小的执行单位。原子操作的三个步骤是：读数据、修改数据、然后重新写入新数据。原子操作是同步机制实现的基础。
设计中主要在线程库中实现3个原子操作函数，其定义及功能说明如下：
1) int cmpxchg(volatile void *ptr, int old, int new)；
此函数比较old值和ptr所指的内存中的值，如果相等，把ptr所指的内存中的值设置为new；如果不相等，则不进行这个设置操作。无论是否进行这个设置操作，函数的返回值都是ptr所指的内存中原来的数值。
2) int xchg(int x, void *ptr);
此函数不进行比较操作，直接将ptr所指的内存地址中的值设为x，并返回ptr所指的内存地址中原来的数值。
3) int atomic_dec_and_test(int *ptr);
此函数原子地将ptr所指内存地址中的值减去1，如果得到的值为0，则返回1，其他情况都返回0。
2.1 原子操作的核心实现
在系统中添加一个虚拟设备文件“lock”，使用该设备文件的ioctl系统调用进入核心态，通过传入参数的不同便可分别实现3个原子操作函数。
2.1.1 虚拟设备驱动的实现
嵌入式Linux操作系统使用数据结构file-operation为所有的设备文件都提供了统一的操作函数接口。不同类型的文件有不同的file-operation成员函数。每个进程对设备的操作最终都会转换成对file-operations结构的访问。在驱动程序中，需根据功能要求，完成file-operations结构中各函数的实现，不需要的函数接口可以直接在file-operations结构中初始化为NULL[5]。file_operations变量会在驱动程序初始化时，注册到系统内部，当操作系统对设备进行操作时，会调用驱动程序注册的file-operations结构中的函数，以实现相应功能。
由于并不对应一个具体的硬件设备，因此在初始化操作中，并不需要向系统申请资源，只需向系统注册该字符设备即可。驱动程序的open、close函数不做任何操作，直接返回0。驱动中file_operations结构的实现如下：
static struct file_operations lock_fops = {
ioctl: lock_ioctl,
open: lock_open,
release: lock_close,
};
2.1.2 ioctl的实现
ioctl是设备驱动程序中对设备的I/O通道进行管理的函数。所谓对I/O通道进行管理，就是对设备的一些特性进行控制，例如串口的传输波特率等。ioctl函数是文件结构file_operations中的一个属性分量，如果在驱动程序中提供了对ioctl的支持，用户就可以在用户程序中使用ioctl函数控制设备的I/O通道。核心驱动程序中的ioctl函数的实现形式为：
int lock_ioctl(struct inode *inode, struct file *file, unsigned int cmd, unsigned long arg);
在ioctl函数中，一般用一个switch-case结构来实现，每一个case对应参数cmd传入的一个命令码，做出一些相应的操作。在核心驱动程序中定义的命令码要与应用程序中定义的命令码一致，以保证命令的正确发送。对应不同的cmd，所传入的参数个数不同。若应用程序所需传入的参数个数大于1，在用户程序中调用ioctl时，可将所需传入的参数放入一个数组中，此时arg表示用户程序中参数数组的起始地址。实现所对应的伪码为：
定义全局命令码；
int lock_ioctl(…)
{
Switch(cmd){
case cmpxchg()函数的调用:
关中断；
将各项参数从用户空间挎贝到内核空间；//可用copy_from_user函数实现
从指定内存中将值挎贝至内核空间；//可用get_user函数实现
if(指定内存中的值与old的值相等) //cmpxchg(ptr, old, new)
将new值挎贝至用户空间指定内存；//可用put_user函数实现
开中断；
return 指定内存中的原值；
case xchg()函数的调用：
关中断；
将各项参数从用户空间挎贝到内核空间；
从指定内存中将值挎贝至内核空间；
将用户指定的值挎贝至用户指定地址；
开中断；
return 指定内存中的原值；
case atomic_dec_and_test()函数的调用:
关中断；
从指定内存中将值挎贝至内核空间；
将得到的值减1；
将减1后的值挎贝至用户指定内存；
开中断；
if(减1后的值为0)return 1;
elsereturn 0;
}}
2.2 原子操作函数的实现
核外线程库中的3个原子操作函数都是通过对“lock”设备文件执行ioctl系统调用实现的，主要过程大体相似，只是在使用各原子操作函数时，所需指定的参数个数不同。因此，在调用ioctl时，所需传入核心的参数个数若大于1个，则将各参数封装进一个数组中，再传入数组的首地址；若只需传入1个参数，则直接传入该参数的地址即可。具体实现伪码为：
定义与核心实现相对应的全局命令码；
int 原子操作函数(…)
{
用数组保存需要的各项参数；
利用open系统调用打开设备文件“/dev/lock”；
用不同的命令码对已打开的设备文件调用ioctl，并保存ioctl的返回值；
关闭设备文件；
返回相应ioctl调用的返回值；
}
3 同步操作的实现
同步操作是基于原子操作及Linux 2.6核心的futex(快速用户空间互斥体)机制实现的。用于同步操作的全局变量有3个状态：0代表没有上锁，即资源可用；1代表上了锁即资源已被占用，但没有线程在等待此资源；2代表有一个或多个线程在等待这个资源被释放。采用lll_lock(int *val)/lll_unlock(int *val)函数对来实现NPTL中的同步操作。
3.1 lll_lock()函数的实现
对于lll_lock(int *val)函数，针对不同的*val值，将进行不同的操作：
1) *val==0：在这种情况下，表示资源可用，即当前线程可以获得这把锁，同时要把*val设置为1。
2) *val==1：当前线程被阻塞并进入内核睡眠。在这种情况下，意味着资源已被其它线程占用，那么当前线程只能等待。此时，将*val设置为2，然后利用futex系统调用将当前线程挂起。当前线程将在“*val==2”这个futex值上睡眠，直到另外一个线程使用futex系统调用将其唤醒。
3) *val==2：和*val=1情况基本一致，也是进入内核睡眠，只是不需要再设置*val的值。
lll_lock()函数实现的伪码如下：
lll_lock(int *val)
{
if(cmpxchg(val,0,1)) /*若*val的值为0，则表示此资源可用，上锁成功*/
{ /*若*val的值不为0，则表示此资源已被占用*/
if(*val的原值为1)
c=xchg(2,val); //原子地将val的值置为2，表示有线程在等待此资源
do{
利用futex系统调用将当前线程在val为2时挂起；
c=xchg(2,val);
} while(c)//循环等待直至val的值为0
}}
3.2 lll_unlock()函数的实现
与lll_lock()函数类似，在lll_unlock()函数中，针对不同的*val值，也将进行不同的操作：
1) *val==2：在这种情况下，表示有线程在等待此资源，此时进行解锁操作，即将*val的值置0，同时利用futex系统调用唤醒在val上等待的一个线程。
2) *val==1：在这种情况下，表示没有线程在等待此资源，此时只需进行解锁操作，不需用futex系统调用进入内核。
lll_unlock()函数实现的伪码如下：
lll_unlock(int *val)
{
if(!atomic_dec_and_test(val))
{//*val减1后不为0，即*val原值为2，表示有线程在此资源上等待
xchg(0, val);//解锁操作，原子地将*val的值置0
利用futex系统调用唤醒在val上等待的一个线程；
}}
4 结束语
同步是为了达到多线程协同工作目的而设计的一种机制。通过添加一个虚拟的锁设备，利用该设备文件的ioctl系统调用，根据传入参数的不同实现不同的原子操作，进而在应用层实现同步函数，将硬件平台相关性最小化，使得移植过程中能够方便地在嵌入式平台上实现NPTL线程库的同步机制。
参考文献
[1] Drepper U,Molnar I.The Native Posix Thread Library for Linux[EB/OL].http://people.redhat.com/drepper/nptl-design.pdf.
[2] 杨沙洲.Linux 线程库性能测试与分析[EB/OL].http://www.ibm.com/developerworks/cn/linux/l-nptl/index.html.
[3] 刘学超,杨宏伟,李玉霜.Java中同步线程的实现[J].商场现代化,2007(4):69-71.
[4] 黄丹,邵惠鹤.基于Windows CE平台的多线程编程[J].微计算机信息,2007,23(12):53-55.
[5] 谭跃,蒋新华.Linux中字符设备驱动程序开发的研究[J].福建电脑,2007(11):86-87.