临界区:就是访问和操作共享数据的代码段
竞争条件:两个执行线程有可能处于同一个临界区中同时执行
原子操作:如同原子一样不能分割的操作,按照顺序执行完
现在我们来讨论一个更为复杂的竞争条件,相应的解决方法也更为复杂。假设需要处理一个队列上的所有请求。我们假定该队列是通过链表得以实现,链表中的每个结点就代表一个请求。有两个函数可以用来操作此队列:一个函数将新请求添加到队列尾部,另一个函数从队列头删除请求,然后处理它。内核各个部分都会调用这两个函数,所以内核会不断地在队列中加入请求,从队列中删除和处理请求。对请求队列的操作无疑要用到多条指令。如果一个线程试图读取队列,而这时正好另一个线程正在处理该队列,那么读取线程就会发现队列此刻正处于不一致状态。很明显,如果允许并发访问队列,就会产生危害。当共享资源是一个复杂的数据结构时,竞争条件往往会使该数据结构遭到破坏。
锁提供的就是这种机制:它就如同一把门锁,门后的房间可想象成一个临界区。在一个指定时间内,房间里只能有一个执行线程存在,当一个线程进入房间后,它会锁住身后的房门﹔当它结束对共享数据的操作后,就会走出房间,打开门锁。如果另一个线程在房门上锁时来了,那么它就必须等待房间内的线程出来并打开门锁后,才能进入房间。这样,线程持有锁,而锁保护了数据。
到底什么数据需要加锁呢,大多数内核数据结构都需要加锁!有一条很好的经验可以帮助我们判断:如果有其他执行线程可以访问这些数据,那么就给这些数据加上某种形式的锁﹔如果任何其他什么东西都能看到它,那么就要锁住它。记住:要给数据而不是给代码加锁。
锁的争用(lock contention),或简称争用,是指当锁正在被占用时,有其他线程试图获得该锁。说一个锁处于高度争用状态,就是指有多个其他线程在等待获得该锁。由于锁的作用是使程序以串行方式对资源进行访问,所以使用锁无疑会降低系统的性能。被高度争用(频繁被持有,或者长时间持有——两者都有就更糟糕〉的锁会成为系统的瓶颈,严重降低系统性能。即使是这样,相比于被几个相互抢夺共享资源的线程撕成碎片,搞得内核崩溃,还是这种同步保护来得更好一点。当然,如果有办法能解决高度争用问题,就更好不过了。
扩展性〈scalability〉是对系统可扩展程度的一个量度。对于操作系统,我们在谈及可扩展性时就会和大量进程、大量处理器或是大量内存等联系起来。其实任何可以被计量的计算机组件都可以涉及可扩展性。理想情况下,处理器的数量加倍应该会使系统处理性能翻倍。而实际上,这是不可能达到的。
1.自死锁
如果一个执行线程试图去获得一个自己已经持有的锁,它将不得不等待锁被释放,但因为它正在忙着等待这个锁,所以自己永远也不会有机会释放锁,最终结果就是死锁:
获得锁
再次试图获得锁等待锁重新可用
-….….
2.ABBA死锁
线程一 线程二
获得锁A 获得锁B
试图获得锁B 试图获得锁A
等待锁B 等待锁A
每个线程都在等待其他线程持有的锁,但是绝没有一个线程会释放它们一开始就持有的锁所以没有任何锁会在释放后被其他线程使用。
如果每个临界区都能像增加变量这样简单就好了,可惜现实总是残酷的。现实世界里,临界区甚至可以跨越多个函数。举个例子,我们经常会碰到这种情况:先得从一个数据结构中移出数据,对其进行格式转换和解析,最后再把它加入到另一个数据结构中。整个执行过程必须是原子的,在数据被更新完毕前,不能有其他代码读取这些数据。显然,简单的原子操作对此无能为力,这就需要使用更为复杂的同步方法——锁来提供保护。
Linux内核中最常见的锁是自旋锁( spin lock)。自旋锁最多只能被一个可执行线程持有。如果一个执行线程试图获得一个被已经持有(即所谓的争用)的自旋锁,那么该线程就会一直进行忙循环一旋转一等待锁重新可用。要是锁未被争用,请求锁的执行线程便能立刻得到它,继续执行。在任意时间,自旋锁都可以防止多于一个的执行线程同时进入临界区。同一个锁可以用在多个位置,例如,对于给定数据的所有访问都可以得到保护和同步。
自旋锁相当于坐在门外等待同伴从里面出来,并把钥匙交给你。如果你到了门口,发现里面没有人,就可以抓到钥匙进入房间。如果你到了门口发现里面正好有人,就必须在门外等待钥匙,不断地检查房间是否为空。当房间为空时,你就可以抓到钥匙进入。正是因为有了钥匙(相当于自旋锁),才允许一次只有一个人(相当于执行线程)进入房间(相当于临界区)。
有时,锁的用途可以明确地分为读取和写人两个场景。例如,对一个链表可能既要更新又要检索。当更新(写入)链表时,不能有其他代码并发地写链表或从链表中读取数据,写操作要求完全互斥。另一方面,当对其检索(读取)链表时,只要其他程序不对链表进行写操作就行了。只要没有写操作,多个并发的读操作都是安全的。任务链表的存取模式,就非常类似于这种情况,它就是通过读-写自旋锁获得保护的。
当对某个数据结构的操作可以像这样被划分为读/写或者消费者/生产者两种类别时,类似读/写锁这样的机制就很有帮助了。为此,Linux内核提供了专门的读一写自旋锁。这种自旋锁为读和写分别提供了不同的锁。一个或多个读任务可以并发地持有读者锁﹔相反,用于写的锁最多只能被一个写任务持有,而且此时不能有并发的读操作。有时把读/写锁叫做共享/排斥锁,或者并发/排斥锁,因为这种锁以共享(对读者而言)和排斥(对写者而言〉的形式获得使用。
Linux 中的信号量是一种睡眠锁。如果有一个任务试图获得一个不可用(已经被占用)的信号量时,信号量会将其推进一个等待队列,然后让其睡眠。这时处理器能重获自由,从而去执行其他代码。当持有的信号量可用(被释放)后,处于等待队列中的那个任务将被唤醒,并获得该信号量
让我们再一次回到门和钥匙的例子。当某个人到了门前,他抓取钥匙,然后进入房间。最大的差异在于当另一个人到了门前,但无法得到钥匙时会发生什么情况。在这种情况下,这家伙不是在徘徊等待,而是把自己的名字写在一个列表中,然后打盹去了。当里面的人离开房间时,就在门口查看一下列表。如果列表上有名字,他就对第一个名字仔细检查,并在胸部给他一拳,叫醒他,让他进入房间。在这种方式中,钥匙(相当于信号量)继续确保一次只有一个人(相当于执行线程)进入房间(相当于临界区)。这就比自旋锁提供了更好的处理器利用率,因为没有把时间花费在忙等待上,但是,信号量比自旋锁有更大的开销。生活总是一分为二的。
结论:
- 1.·由于争用信号量的进程在等待锁重新变为可用时会睡眠,所以信号量适用于锁会被长时间持有的情况。
- 2.·相反,锁被短时间持有时,使用信号量就不太适宜了。因为睡眠、维护等待队列以及唤醒所花费的开销可能比锁被占用的全部时间还要长。
- 3.·由于执行线程在锁被争用时会睡眠,所以只能在进程上下文中才能获取信号量锁,因为在中断上下文中是不能进行调度的。
- 4.·你可以在持有信号量时去睡眠(当然你也可能并不需要睡眠),因为当其他进程试图获得同一信号量时不会因此而死锁(因为该进程也只是去睡眠而已,而你最终会继续执行的)。
- 5.你占用信号量的同时不能占用自旋锁。因为在你等待信号量时可能会睡眠,而在持有自旋锁时是不允许睡眠的。
计数信号量和二值信号量
最后要讨论的是信号量的一个有用特性,它可以同时允许任意数量的锁持有者,而自旋锁在一个时刻最多允许一个任务持有它。信号量同时允许的持有者数量可以在声明信号量时指定。这个值称为使用者数量(usage count)或简单地叫数量〈count)。通常情况下,信号量和自旋锁一样,在一个时刻仅允许有一个锁持有者。这时计数等于1,这样的信号量被称为二值信号量(因为它或者由一个任务持有,或者根本没有任务持有它)或者称为互斥信号量(因为它强制进行互斥)。另一方面,初始化时也可以把数量设置为大于1的非0值。这种情况,信号量被称为计数信号量(counting semaphone),它允许在一个时刻至多有count个锁持有者。计数信号量不能用来进行强制互斥,因为它允许多个执行线程同时访问临界区。相反,这种信号量用来对特定代码加以限制,内核中使用它的机会不多。在使用信号量时,基本上用到的都是互斥信号量(计数等于1的信号量)。
直到最近,内核中唯一允许睡眠的锁是信号量。多数用户使用信号量只使用计数1,说白了是把其作为一个互斥的排他锁使用——好比允许睡眠的自旋锁。不幸的是,信号量用途更通用,没多少使用限制。这点使得信号量适合用于那些较复杂的、未明情况下的互斥访问,比如内核于用户空间复杂的交互行为。但这也意味着简单的锁定而使用信号量并不方便,并且信号量也缺乏强制的规则来行使任何形式的自动调试,即便受限的调试也不可能。为了找到一个更简单睡眠锁,内核开发者们引入了互斥体(mutex)。确实,这个名字容易和我们的习惯称呼混淆。所以这里我们澄清一下,“互斥体( mutex)”这个称谓所指的是任何可以睡眠的强制互斥锁,比如使用计数是1的信号量。但在最新的Linux内核中,“互斥体(mutex)”这个称谓现在也用于一种实现互斥的特定睡眠锁。也就是说,互斥体是一种互斥信号。
- DEFINE_MUTEX(name);
- //动态初始化 mutex,你需要做:
- mutex_init (&mutex);
- //对互斥锁锁定和解锁并不难:
- mutex_lock ( &mutex);
- /*临界区*/
- mutex_unlock ( &mutex);
结论:
- 1.任何时刻中只有--个任务可以持有mutex,也就是说,mutex的使用计数永远是1。
- 2.给mutex上锁者必须负责给其再解锁——你不能在一个上下文中锁定一个mutex,而在另一个上下文中给它解锁。这个限制使得mutex 不适合内核同用户空间复杂的同步场景。最常使用的方式是:在同一上下文中上锁和解锁。
- 3.递归地上锁和解锁是不允许的。也就是说,你不能递归地持有同一个锁,同样你也不能再去解锁一个已经被解开的mutex.
- 4.当持有一个mutex时,进程不可以退出。
- 5. mutex不能在中断或者下半部中使用,即使使用mutex_trylock()也不行。
- 6.mutex 只能通过官方API管理﹔它只能使用上节中描述的方法初始化,不可被拷贝、手动初始化或者重复初始化。
-
2.5总结
需求 | 加锁方法 |
低开销加锁 | 自旋锁 |
短期锁定 | 自旋锁 |
长期加锁 | mutex |
中断上下文 | 自旋锁 |
持有睡眠的锁 | mutex |
顺序锁,通常简称seq锁,是在2.6版本内核中才引入的一种新型锁。这种锁提供了一种很简单的机制,用于读写共享数据。实现这种锁主要依靠一个序列计数器。当有疑义的数据被写入时,会得到一个锁,并且序列值会增加。在读取数据之前和之后,序列号都被读取。如果读取的序列号值相同,说明在读操作进行的过程中没有被写操作打断过。此外,如果读取的值是偶数,那么就表明写操作没有发生(要明白因为锁的初值是0,所以写锁会使值成奇数,释放的时候变成偶劫).