自旋锁
自旋锁是内核中最基础的锁机制。
自旋锁不会引起调用者睡眠,如果自旋锁已经被别的执行单元持有,调用者就一直循环在那里看是否该自旋锁的持有者已经释放了锁,"自旋"一词就是因此而得名。
自旋锁适用于锁使用者保持锁时间比较短的情况。
使用自旋锁需要注意有可能造成的死锁情况:
-
static DEFINE_SPINLOCK(xxx_lock);
-
-
unsigned long flags;
-
spin_lock_irqsave(&xxx_lock, flags);
-
... critical section here ..
-
spin_unlock_irqrestore(&xxx_lock, flags);
代码中spin_lock_irqsave会禁止本地cpu中断的抢占。以上代码在任何情况下都是安全的。但问题是关中断的代价太大。
如果把spin_lock_irqsave/spin_unlock_irqrestore换成spin_lock/spin_unlock会有什么问题吗?
答案是,如果中断中调用了spin_lock,可能会引起死锁!
例如:
-
spin_lock(&lock);
-
...
-
<- interrupt comes in:
-
spin_lock(&lock);
值得注意的是,如果产生中断的cpu和进程中调用spin_lock的cpu不是同一个,则不会有问题。这也是irq版本的spin_lock函数实现时只需要禁止本地cpu中断的原因。
结论:要想在进程中用spin_lock代替spin_lock_irqsave,条件是中断中不会使用相应的spin_lock
何时使用自旋锁?
不允许睡眠的上下文且临界区操作较短时使用自旋锁。
读写自旋锁
如果读写锁当前没有读者,也没有写者,那么写者可以立刻获得读写锁,否则它必须自旋在那里,直到没有任何写者或读者。如果读写锁没有写者,那么读者可以立即获得该读写锁,否则读者必须自旋在那里,直到写者释放该读写锁。
读写锁适合于对数据结构的读次数比写次数多得多的情况。
注意:读写锁需要比spinlocks更多的访问原子内存操作,如果读临界区不是很大,最好别使用读写锁。
读写锁代码:
-
rwlock_t xxx_lock = __RW_LOCK_UNLOCKED(xxx_lock);
-
-
unsigned long flags;
-
-
read_lock_irqsave(&xxx_lock, flags);
-
.. critical section that only reads the info ...
-
read_unlock_irqrestore(&xxx_lock, flags);
-
-
write_lock_irqsave(&xxx_lock, flags);
-
.. read and write exclusive access to the info ...
-
write_unlock_irqrestore(&xxx_lock, flags);
读写锁比较适合链表等数据结构,特别是查找远多于修改的情况。
另外,可以灵活的使用read-write和irq版本的自旋锁。例如,如果中断中只是用了读锁,进程中就可以使用non-irq版本的读锁和irq版本的写锁。
注意:RCU比读写锁更适合遍历list,但需要更关注细节。目前kernel社区正在努力用RCU代替读写锁。
信号量
semaphore和spin lock的区别是semaphore会引起睡眠。
查看semaphore的数据结构可以发现,semaphore除了拥有spinlock,还有一个计数器和一个等待队列。当某个进程获取信号量的count值小于等于0时,被添加到wait_list中。
-
struct semaphore {
-
raw_spinlock_t lock;
-
unsigned int count;
-
struct list_head wait_list;
-
};
何时使用semaphore?
允许睡眠的上下文、临界区操作较长、计数值大于1时使用semaphore
信号量也有读写信号量,在此略过。
mutex
mutex可以理解成计数值只有0和1的semaphore
既然有了semaphore,内核为何还需要mutex?
因为内核中对二值信号量的需求很大,单独提供一个mutex更利于代码编写和清晰度。
mutex缺点:
为了实现某些性能上的优化,mutex数据结构比semaphore更大(这已经违背了mutex刚设计时的意愿),这也会消耗更多的CPU cache和memory footprint.
何时使用mutex?
允许睡眠的上下文、临界区操作较长、计数值只为0或1时使用mutex
kernel文档建议,在任何需要加锁且mutex可以满足需求的情况都应该使用mutex而不是其他锁。
RCU
RCU(Read-Copy Update)即读-拷贝,更新。对于用RCU保护的资源,读者不需要任何等待,而写者访问它时,需要先拷贝一个副本,然后对副本修改,最后在适当的时机把指向原来数据的指针指向新的数据。这个“适当的时机”指的是没有任何读者操作该资源时。
RCU相关API:
-
rcu_read_lock()
-
读者进入临界区
-
rcu_read_unlock()
-
读者退出临界区
-
synchronize_rcu()
-
由写者调用,当读者都退出老更新前的临界区后,写者才可以返回该函数。
-
call_rcu()
-
由写者调用,但不阻塞。该函数的参数中有一个回调函数,当读者都退出更新前的临界区后,调用该回调函数。
-
rcu_assign_pointer()
-
给临界区资源赋新值
-
rcu_dereference()
-
使用临界区资源
RCU 写者的典型流程:
1. 拷贝一份临界区资源,此时有两份临界区资源,这里称为老资源和新资源
2. 用新资源代替老资源,使得之后的读者访问的是新资源
3. 等待读取老临界区的读者全部退出
4. 此时,老资源已没有读者操作,释放该资源
内核提供了对list,hlist等常用数据结构的RCU版本。对于RCU,对共享数据的操作必须保证能够被没有使用同步机制的读者看到,所以内存栅是非常必要的。内存栅只在alpha架构上才使用。
RCU代替读写锁:
-
@@ -13,15 +14,15 @@
-
struct list_head *lp;
-
struct el *p;
-
-
- read_lock();
-
- list_for_each_entry(p, head, lp) {
-
+ rcu_read_lock();
-
+ list_for_each_entry_rcu(p, head, lp) {
-
if (p->key == key) {
-
*result = p->data;
-
- read_unlock();
-
+ rcu_read_unlock();
-
return 1;
-
}
-
}
-
- read_unlock();
-
+ rcu_read_unlock();
-
return 0;
-
}
-
-
@@ -29,15 +30,16 @@
-
{
-
struct el *p;
-
-
- write_lock(&listmutex);
-
+ spin_lock(&listmutex);
-
list_for_each_entry(p, head, lp) {
-
if (p->key == key) {
-
- list_del(&p->list);
-
- write_unlock(&listmutex);
-
+ list_del_rcu(&p->list);
-
+ spin_unlock(&listmutex);
-
+ synchronize_rcu();
-
kfree(p);
-
return 1;
-
}
-
}
-
- write_unlock(&listmutex);
-
+ spin_unlock(&listmutex);
-
return 0;
-
}
用RCU保护数据结构:
-
struct foo {
-
int a;
-
char b;
-
long c;
-
};
-
DEFINE_SPINLOCK(foo_mutex);
-
-
struct foo *gbl_foo;
-
-
/*
-
* Create a new struct foo that is the same as the one currently
-
* pointed to by gbl_foo, except that field "a" is replaced
-
* with "new_a". Points gbl_foo to the new structure, and
-
* frees up the old structure after a grace period.
-
*
-
* Uses rcu_assign_pointer() to ensure that concurrent readers
-
* see the initialized version of the new structure.
-
*
-
* Uses synchronize_rcu() to ensure that any readers that might
-
* have references to the old structure complete before freeing
-
* the old structure.
-
*/
-
void foo_update_a(int new_a)
-
{
-
struct foo *new_fp;
-
struct foo *old_fp;
-
-
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
-
spin_lock(&foo_mutex);
-
old_fp = gbl_foo;
-
*new_fp = *old_fp;
-
new_fp->a = new_a;
-
rcu_assign_pointer(gbl_foo, new_fp);
-
spin_unlock(&foo_mutex);
-
synchronize_rcu();
-
kfree(old_fp);
-
}
-
-
/*
-
* Return the value of field "a" of the current gbl_foo
-
* structure. Use rcu_read_lock() and rcu_read_unlock()
-
* to ensure that the structure does not get deleted out
-
* from under us, and use rcu_dereference() to ensure that
-
* we see the initialized version of the structure (important
-
* for DEC Alpha and for people reading the code).
-
*/
-
int foo_get_a(void)
-
{
-
int retval;
-
-
rcu_read_lock();
-
retval = rcu_dereference(gbl_foo)->a;
-
rcu_read_unlock();
-
return retval;
-
}
以下是写者不阻塞的代码:
-
struct foo {
-
int a;
-
char b;
-
long c;
-
struct rcu_head rcu;
-
};
-
-
/*
-
* Create a new struct foo that is the same as the one currently
-
* pointed to by gbl_foo, except that field "a" is replaced
-
* with "new_a". Points gbl_foo to the new structure, and
-
* frees up the old structure after a grace period.
-
*
-
* Uses rcu_assign_pointer() to ensure that concurrent readers
-
* see the initialized version of the new structure.
-
*
-
* Uses call_rcu() to ensure that any readers that might have
-
* references to the old structure complete before freeing the
-
* old structure.
-
*/
-
void foo_update_a(int new_a)
-
{
-
struct foo *new_fp;
-
struct foo *old_fp;
-
-
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
-
spin_lock(&foo_mutex);
-
old_fp = gbl_foo;
-
*new_fp = *old_fp;
-
new_fp->a = new_a;
-
rcu_assign_pointer(gbl_foo, new_fp);
-
spin_unlock(&foo_mutex);
-
call_rcu(&old_fp->rcu, foo_reclaim);
-
}
-
-
void foo_reclaim(struct rcu_head *rp)
-
{
-
struct foo *fp = container_of(rp, struct foo, rcu);
-
-
foo_cleanup(fp->a);
-
-
kfree(fp);
-
}
何时使用RCU?
读操作远多于写操作、且写操作不是特别紧急时使用RCU
顺序锁
顺序锁为写者赋予更高的优先级,写者永远不会等待读者。缺点是读者有时不得不读多次数据以获取正确的结果。
顺序锁的数据结构中除了有spinlock外,还有一个顺序号。如果成功获得锁,顺序锁的顺序号会加1,以便读者能够检查出是否在读期间有写者访问过。读者在读取数据前后两次读顺序值,如果两次值不相同,则说明读取期间有新的写者操作过数据了,那么本次读取就是无效的。
典型使用:
读端:
-
do {
-
seqnum = read_seqbegin(&seqlock_a);
-
//读操作代码块
-
...
-
} while (read_seqretry(&seqlock_a, seqnum));
写端:
-
spin_lock(&lock);
-
write_seqlock(&seqlock_a)
-
...
-
write_sequnlock(&seqlock_a)
-
spin_unlock(&lock);
写者通过调用write_seqlock()和write_sequnlock()获取和释放顺序锁。write_seqlock()函数获取seqlock_t数据结构中的自旋锁,然后使顺序计数器sequence加1;write_sequnlock()函数再次增加顺序计数器sequence,然后释放自旋锁。这样可以保证写者在整个写的过程中,计数器sequence的值是奇数,并且当没有写者在改变数据的时候,计数器的值是偶数。
read_seqbegin()返回顺序锁的当前顺序号;如果局部变量seq的值是奇数(写者在read_seqbegin()函数被调用后,正更新数据结构),或seq的值与顺序锁的顺序计数器的当前值不匹配(当读者正执行临界区代码时,写者开始工作),read_seqretry()就返回1,说明本次读取失败,需要重新读取 。
并不是每一种资源都可以使用顺序锁来保护。一般来说,必须在满足下述条件时才能使用顺序锁:
1. 读者的临界区资源不包括被写者修改和被读者取值的指针,否则,写者有可能使指针失效,读者读取时会产生OPPs。
2. 读者的临界区代码没有副作用。
何时使用顺序锁?
读操作远多于写操作、且写操作很紧急时使用顺序锁。
小结
本文对Linux内核的多种锁的同步机制进行了分析对比,如有疏漏或错误,请各位不吝指正。
阅读(3991) | 评论(0) | 转发(0) |