锁的实现

锁的实现

锁必须是原子性操作实现,决不能中途打断,由处理器原语支持。锁的意义在于将操作做为一个执行单元以一种原子方式执行而不被打断,多线程下也不会互相干扰。但是锁会影响性能,这是因为一个加锁的临界资源 在被访问前必须获取对应的锁,获取该锁的线程将以独占的方式访问临界区。如果此时有其他线程同时访问临界区,则会因为无法获取这个锁而阻塞,显然,在临界区强行通过加锁使线程执行串行化是需要牺牲一定的性能的。

Semaphore | 信号量

信号量又称为信号灯,它是用来协调不同进程间的数据对象的,而最主要的应用是共享内存方式的进程间通信。本质上,信号量是一个计数器,它用来记录对某个资源(如共享内存)的存取状况。一般说来,为了获得共享资源,进程需要执行下列操作:

  1. 测试控制该资源的信号量。

  2. 若此信号量的值为正,则允许进行使用该资源。进程将信号量减 1。

  3. 若此信号量为 0,则该资源目前不可用,进程进入睡眠状态,直至信号量值大于 0,进程被唤醒,转入步骤(1)。

  4. 当进程不再使用一个信号量控制的资源时,信号量值加 1。如果此时有进程正在睡眠等待此信号量,则唤醒此进程。

信号量与普通整型变量的区别:

  • 信号量(semaphore)是非负整型变量,除了初始化之外,它只能通过两个标准原子操作:wait(semap) , signal(semap) ; 来进行访问;

  • 操作也被成为 PV 原语(P 来源于 Dutch proberen"测试",V 来源于 Dutch verhogen"增加"),而普通整型变量则可以在任何语句块中被访问;

信号量与互斥锁之间的区别主要在于互斥量用于线程的互斥,信号量用于线程的同步;这是互斥量和信号量的根本区别,也就是互斥和同步之间的区别。

Semaphore 实现

Semaphore 对象里包含一个 count 值和一个队列对象,另外有两个对外 public 的方法,wait()和 signal(),需要特别注意的事,count 值代表的资源数量是不能为负的。为了理解这些属性和方法,我们可以类比一个现实生活中的例子。大家去餐厅吃饭,假设这个餐厅有 10 个座位,有 20 个吃货随机出发去这个餐厅吃饭,那么对应关系是这样的:

  • count = 10,10 个座位。

  • queue,餐厅位置有限,为了避免混乱,餐厅肯定会吃货们排队。

  • wait(),吃货到了餐厅找服务员要位置点餐,这个行为就是 wait。

  • signal(),吃货吃完了买单离开位置,这个行为就是 signal。

这其实是一个信号量应用的典型场景,这里关键在于正确理解 wait 和 signal 发生时都有哪些细节步骤。

  • wait():具体到餐厅到例子,20 个人随机出发去餐厅吃饭,有 10 个人先到,然后挨个执行 wait。前 10 个人执行 wait 的时候是有位置的,所以 count>0,这 10 个人每人都消耗掉一个座位开始吃饭。到第 11 个人到了都时候,count==0,没有位置了,所以被 suspend,开始加入排队都队列等待。后续所有人都慢慢的到来,但和第 11 个人一样,都只能排队。

  • signal():过了一段时间之后,有个人吃好结账离开了餐厅。这时候如果没有人在排队,位置数量 count++,没有其它事情发生。但如果有人在排队,比如上面的情况,有 10 个人在等待位置,餐厅会把排在第一个的人安排到刚才空出来的位置,count 值没有变化,但队列的人少了一个。

对于 wait 和 signal 还有两点需要特别注意。也是平时我们使用 Semaphore 时比较容易产生错误的地方。

  • wait 和 signal 都是原子操作。可以简单理解为上面代码里 wait(), signal()两个函数都是加锁的。这个特性其实让 semaphore 的行为变得更简单清晰。大家想象,如果到餐厅的 10 个人是同时到达的,但不是依次询问餐厅是否有位置,而是 10 张嘴同时说话,同时找餐厅要位置,显然情况会变得复杂不好处理。

  • wait 或者 signal 调用的顺序是不确定的。上面的例子中每个人都是随机时间出发,到达餐厅的顺序也是随机的,并不一定先出发的就先到。同理每个人吃饭的时间长短也不一定,有人快有人慢,所以吃好离开餐厅的时间点也是随机的。这里每个人都代表一个线程,因为操作系统线程调度策略导致到底哪个线程先执行也是不确定的。

Mutex | 互斥量

理解了 Semaphore,再看 Mutex 就很简单了。可以把 Mutex 理解成 count==1 的 Semaphore。在使用 Mutex 的场景下,永远都只允许有一个线程在占有资源,其它的线程都必须等待。