四、锁之外的办法
(1)免锁算法
经常用于免锁的生产者/消费者任务的数据结构之一是循环缓冲区。它在设备驱动程序中相当普遍,如以前移植的网卡驱动程序。内核里有一个通用的循环缓冲区的实现在 。
(2)原子变量
完整的锁机制对一个简单的整数来讲显得浪费。内核提供了一种原子的整数类型,称为atomic_t,定义在
。原子变量操作是非常快的, 因为它们在任何可能时编译成一条单个机器指令。
以下是其接口函数:
void atomic_set(atomic_t *v, int i); /*设置原子变量 v 为整数值 i.*/ atomic_t v = ATOMIC_INIT(0); /*编译时使用宏定义 ATOMIC_INIT 初始化原子值.*/
int atomic_read(atomic_t *v); /*返回 v 的当前值.*/
void atomic_add(int i, atomic_t *v);/*由 v 指向的原子变量加 i. 返回值是 void*/ void atomic_sub(int i, atomic_t *v); /*从 *v 减去 i.*/
void atomic_inc(atomic_t *v); void atomic_dec(atomic_t *v); /*递增或递减一个原子变量.*/
int atomic_inc_and_test(atomic_t *v); int atomic_dec_and_test(atomic_t *v); int atomic_sub_and_test(int i, atomic_t *v); /*进行一个特定的操作并且测试结果; 如果, 在操作后, 原子值是 0, 那么返回值是真; 否则, 它是假. 注意没有 atomic_add_and_test.*/
int atomic_add_negative(int i, atomic_t *v); /*加整数变量 i 到 v. 如果结果是负值返回值是真, 否则为假.*/
int atomic_add_return(int i, atomic_t *v); int atomic_sub_return(int i, atomic_t *v); int atomic_inc_return(atomic_t *v); int atomic_dec_return(atomic_t *v); /*像 atomic_add 和其类似函数, 除了它们返回原子变量的新值给调用者.*/
|
atomic_t 数据项必须通过这些函数存取。 如果你传递一个原子项给一个期望一个整数参数的函数, 你会得到一个编译错误。需要多个 atomic_t 变量的操作仍然需要某种其他种类的加锁。
(3)位操作
内核提供了一套函数来原子地修改或测试单个位。原子位操作非常快, 因为它们使用单个机器指令来进行操作, 而在任何时候低层平台做的时候不用禁止中断. 函数是体系依赖的并且在
中声明. 以下函数中的数据是体系依赖的.
nr 参数(描述要操作哪个位)在ARM体系中定义为unsigned int:
void set_bit(nr, void *addr); /*设置第 nr 位在 addr 指向的数据项中。*/
void clear_bit(nr, void *addr); /*清除指定位在 addr 处的无符号长型数据.*/
void change_bit(nr, void *addr);/*翻转nr位.*/
test_bit(nr, void *addr); /*这个函数是唯一一个不需要是原子的位操作; 它简单地返回这个位的当前值.*/
/*以下原子操作如同前面列出的, 除了它们还返回这个位以前的值.*/
inttest_and_set_bit(nr, void *addr); int test_and_clear_bit(nr, void *addr); int test_and_change_bit(nr, void *addr); |
以下是一个使用范例:
/* try to set lock */ while (test_and_set_bit(nr, addr) != 0) wait_for_a_while();
/* do your work */
/* release lock, and check. */ if (test_and_clear_bit(nr, addr) == 0) something_went_wrong(); /* already released: error */
|
(4)seqlock
2.6内核包含了一对新机制打算来提供快速地, 无锁地存取一个共享资源。 seqlock要保护的资源小, 简单, 并且常常被存取, 并且很少写存取但是必须要快。seqlock 通常不能用在保护包含指针的数据结构。seqlock 定义在 。
/*两种初始化方法*/ seqlock_t lock1 = SEQLOCK_UNLOCKED;
seqlock_t lock2; seqlock_init(&lock2);
|
这个类型的锁常常用在保护某种简单计算,读存取通过在进入临界区入口获取一个(无符号的)整数序列来工作. 在退出时, 那个序列值与当前值比较; 如果不匹配, 读存取必须重试.读者代码形式:
unsigned int seq; do { seq = read_seqbegin(&the_lock); /* Do what you need to do */ } while read_seqretry(&the_lock, seq);
|
如果你的 seqlock 可能从一个中断处理里存取, 你应当使用 IRQ 安全的版本来代替:
unsigned int read_seqbegin_irqsave(seqlock_t *lock, unsigned long flags); int read_seqretry_irqrestore(seqlock_t *lock, unsigned int seq, unsigned long flags);
|
写者必须获取一个排他锁来进入由一个 seqlock 保护的临界区,写锁由一个自旋锁实现, 调用:
void write_seqlock(seqlock_t *lock); void write_sequnlock(seqlock_t *lock);
|
因为自旋锁用来控制写存取, 所有通常的变体都可用:
void write_seqlock_irqsave(seqlock_t *lock, unsigned long flags); void write_seqlock_irq(seqlock_t *lock); void write_seqlock_bh(seqlock_t *lock);
void write_sequnlock_irqrestore(seqlock_t *lock, unsigned long flags); void write_sequnlock_irq(seqlock_t *lock); void write_sequnlock_bh(seqlock_t *lock);
|
还有一个 write_tryseqlock 在它能够获得锁时返回非零.
(5)读取-复制-更新
读取-拷贝-更新(RCU) 是一个高级的互斥方法, 在合适的情况下能够有高效率. 它在驱动中的使用很少。
五、开发板实验
在我的SBC2440V4开发板上作completion的实验,因为别的实验都要在并发状态下才可以实验,所以本章的我只做了completion的实验。我将《Linux设备驱动程序(第3版)》提供的源码做了修改,将原来的2.4内核的模块接口改成了2.6的接口,并编写了测试程序。实验源码如下:
模块程序链接:complete模块
模块测试程序链接:测试程序
[Tekkaman2440@SBC2440V4]#cd /lib/modules/ [Tekkaman2440@SBC2440V4]#insmod complete.ko [Tekkaman2440@SBC2440V4]#echo 8 > /proc/sys/kernel/printk [Tekkaman2440@SBC2440V4]#cat /proc/devices Character devices: 1 mem 2 pty 3 ttyp 4 /dev/vc/0 4 tty 4 ttyS 5 /dev/tty 5 /dev/console 5 /dev/ptmx 7 vcs 10 misc 13 input 14 sound 81 video4linux 89 i2c 90 mtd 116 alsa 128 ptm 136 pts 180 usb 189 usb_device 204 s3c2410_serial 252 complete 253 usb_endpoint 254 rtc
Block devices: 1 ramdisk 256 rfd 7 loop 31 mtdblock 93 nftl 96 inftl 179 mmc [Tekkaman2440@SBC2440V4]#mknod -m 666 /dev/complete c 252 0 [Tekkaman2440@SBC2440V4]#cd /tmp/ [Tekkaman2440@SBC2440V4]#./completion_testr& [Tekkaman2440@SBC2440V4]#process 814 (completion_test) going to sleep [Tekkaman2440@SBC2440V4]#./completion_testr& [Tekkaman2440@SBC2440V4]#process 815 (completion_test) going to sleep [Tekkaman2440@SBC2440V4]#ps PID Uid VSZ Stat Command 1 root 1744 S init 2 root SW< [kthreadd] 3 root SWN [ksoftirqd/0] 4 root SW< [watchdog/0] 5 root SW< [events/0] 6 root SW< [khelper] 59 root SW< [kblockd/0] 60 root SW< [ksuspend_usbd] 63 root SW< [khubd] 65 root SW< [kseriod] 77 root SW [pdflush] 78 root SW [pdflush] 79 root SW< [kswapd0] 80 root SW< [aio/0] 707 root SW< [mtdblockd] 708 root SW< [nftld] 709 root SW< [inftld] 710 root SW< [rfdd] 742 root SW< [kpsmoused] 751 root SW< [kmmcd] 769 root SW< [rpciod/0] 778 root 1752 S -sh 779 root 1744 S init 781 root 1744 S init 782 root 1744 S init 783 root 1744 S init 814 root 1336 D ./completion_testr 815 root 1336 D ./completion_testr 816 root 1744 R ps [Tekkaman2440@SBC2440V4]#./completion_testw process 817 (completion_test) awakening the readers... awoken 814 (completion_test) write code=0 [Tekkaman2440@SBC2440V4]#read code=0 [Tekkaman2440@SBC2440V4]#ps PID Uid VSZ Stat Command 1 root 1744 S init 2 root SW< [kthreadd] 3 root SWN [ksoftirqd/0] 4 root SW< [watchdog/0] 5 root SW< [events/0] 6 root SW< [khelper] 59 root SW< [kblockd/0] 60 root SW< [ksuspend_usbd] 63 root SW< [khubd] 65 root SW< [kseriod] 77 root SW [pdflush] 78 root SW [pdflush] 79 root SW< [kswapd0] 80 root SW< [aio/0] 707 root SW< [mtdblockd] 708 root SW< [nftld] 709 root SW< [inftld] 710 root SW< [rfdd] 742 root SW< [kpsmoused] 751 root SW< [kmmcd] 769 root SW< [rpciod/0] 778 root 1752 S -sh 779 root 1744 S init 781 root 1744 S init 782 root 1744 S init 783 root 1744 S init 815 root 1336 D ./completion_testr 818 root 1744 R ps [1] - Done ./completion_testr [Tekkaman2440@SBC2440V4]#./completion_testw process 819 (completion_test) awakening the readers... awoken 815 (completion_test) write code=0 [Tekkaman2440@SBC2440V4]#read code=0 [Tekkaman2440@SBC2440V4]#ps PID Uid VSZ Stat Command 1 root 1744 S init 2 root SW< [kthreadd] 3 root SWN [ksoftirqd/0] 4 root SW< [watchdog/0] 5 root SW< [events/0] 6 root SW< [khelper] 59 root SW< [kblockd/0] 60 root SW< [ksuspend_usbd] 63 root SW< [khubd] 65 root SW< [kseriod] 77 root SW [pdflush] 78 root SW [pdflush] 79 root SW< [kswapd0] 80 root SW< [aio/0] 707 root SW< [mtdblockd] 708 root SW< [nftld] 709 root SW< [inftld] 710 root SW< [rfdd] 742 root SW< [kpsmoused] 751 root SW< [kmmcd] 769 root SW< [rpciod/0] 778 root 1752 S -sh 779 root 1744 S init 781 root 1744 S init 782 root 1744 S init 783 root 1744 S init 820 root 1744 R ps [2] + Done ./completion_testr [Tekkaman2440@SBC2440V4]#ps PID Uid VSZ Stat Command 1 root 1744 S init 2 root SW< [kthreadd] 3 root SWN [ksoftirqd/0] 4 root SW< [watchdog/0] 5 root SW< [events/0] 6 root SW< [khelper] 59 root SW< [kblockd/0] 60 root SW< [ksuspend_usbd] 63 root SW< [khubd] 65 root SW< [kseriod] 77 root SW [pdflush] 78 root SW [pdflush] 79 root SW< [kswapd0] 80 root SW< [aio/0] 707 root SW< [mtdblockd] 708 root SW< [nftld] 709 root SW< [inftld] 710 root SW< [rfdd] 742 root SW< [kpsmoused] 751 root SW< [kmmcd] 769 root SW< [rpciod/0] 778 root 1752 S -sh 779 root 1744 S init 781 root 1744 S init 782 root 1744 S init 783 root 1744 S init 821 root 1744 R ps [Tekkaman2440@SBC2440V4]#./completion_testw process 822 (completion_test) awakening the readers... write code=0 [Tekkaman2440@SBC2440V4]#./completion_testr process 823 (completion_test) going to sleep awoken 823 (completion_test) read code=0
|
实验表明:如果先读数据,读的程序会被阻塞(因为驱动在wait_for_completion,等待写的完成)。如果先写,读程序会比较顺利的执行下去(虽然也会休眠,但马上会被唤醒!)。其原因可以从completion的源码中找答案。completion其实就是自旋锁的再包装,具体细节参见completion的源码。