专栏首页LINUX阅码场Linux kernel 同步机制(下篇)

Linux kernel 同步机制(下篇)

上一部分,我们讨论了最基本常见的几类同步机制,这一部分我们将讨论相对复杂的几种同步机制,尤其是读写信号量和RCU,在操作系统内核中有相当广泛的应用。

  • 读写信号量(rw_semaphore)
  • BKL(Big Kernel Lock,只包含在2.4内核中,不讲)
  • Rwlock
  • brlock(只包含在2.4内核中,不讲)
  • RCU(只包含在2.6内核及以后的版本中)

一、读写信号量(RW_Semaphore)

读写信号量与信号量有相似也有不同,它是如下一种同步机制:读写信号量将访问者分为读者或者写者,读者在持有读写信号量期间只能对该信号量保护的共享资源进行读访问,而只要一个任务需要写,它就被归类为写者,其进行访问之前必先获得写者身份,在其不需写访问时可降级为读者。读写信号量可同时拥有不受限的读者数,写者是排他性的,独占性的,而读者不排他。若读写信号量未被写者持有或者等待,读者就可以获得读写信号量,否则必须等待直到写者释放读写信号量为止;若读写信号量没有被读者或写者持有,也没用写者等待,写者可以获得该读写信号量,否则等待至信号量全部释放(没有其他访问者)为止。

Structure Definition

若从上述结构定义看,最关键的前三个字段与mutex、信号量十分相似不再赘述,后面的OSQ字段在Mutex中提起过。由于内核有关读写信号量的实现有两种,取决于CONFIG_RWSEM_GENERIC_SPINLOCK的配置,但是一般默认该配置是关的,因此选用默认版本的实现进行解读。读写信号量同mutex一样,在最近的改进中均引入了OSQ lock机制实现自旋等待。

读写信号量与信号量之间的关系

读写信号量可能会引起进程阻塞,但是它允许N个读执行单元同时访问共享资源,而最多只允许有一个写执行单元访问共享资源;因此,读写信号量是一种相对放宽条件的、粒度稍大于信号量的互斥机制。信号量不允许任何操作之间有并发,即:读操作与读操作之间、读操作与写操作之间、写操作与写操作之间,都不允许并发;而读写信号量则只允许读操作与读操作之间的并发,但不允许读操作与写操作之间的并发,也不允许写操作与写操作之间的并发。因此读写信号量比较适合读多写少的情况,可良好地利用读者并发的特性。

Count 字段在读写信号量的表示含义

读写信号量中的count字段并不如信号量一般表示可用资源数量,而是标记了当前的访问情况,我们取32位的情况分析,默认是取32位配置。

先观察如下宏常量:

然后我们再考虑count,我们发现均是上述宏组合的结果,可以归类为以下几种情况:

所以可见count可以标记并区分许多访问情况, 尤其是当存在写者或阻塞时,其对应的有符号数(atomic_long_t)均为负数,可以作为判断的标记。

在传统的读写信号量中,会直接进阻塞,因此只有等待队列非空还是为空的问题,但是在最近的改进中存在自旋等待的问题,因此使得在锁的获取中可能出现自旋状态的写者偷出锁的情况。

__down_read & __up_read

根据count字段的含义,count + 1小于0说明原本存在写者或者等待队列非空,因此不能获得锁,rwsem_down_read_failed调用

一个读者释放后count - 1小于-1说明等待队列非空,因此还需唤醒等待的写者

Rwsem_down_read不能直接获取时调用,首先判断等待队列是否为空,为空则字段置为非空,并将count回退之前读的尝试,将当前task压入等待队列,如果当前没有人持有或正在获取锁锁,则唤醒等待队列的前面的进程,同时将唤醒进程的waiter.task置NULL,在调度中若发现自己的waiter.task为NULL,说明轮到本进程运行,置为TASK_RUNNING

down_write & up_write

一个写者获取锁后,如果返回的count不是0xffff0001,那么写者获取信号量失败

Rwsem_down_write_failed的基本逻辑与read相似,回退先前count的变化,对waitlist的处理,等待获取锁,有兴趣可以自己阅读源码。

一个写者释放锁后,如果count返回小于0,说明等待非空,将其唤醒。

RW_Semaphore API

二、读写锁(rw_lock)

读写锁实际是一种特殊的自旋锁,它把对共享资源的访问者划分成读者和写者,读者只对共享资源进行读访问,写者则需要对共享资源进行写操作。这种锁相对于自旋锁而言,能提高并发性,因为在多处理器系统中,它允许同时有多个读者来访问共享资源,最大可能的读者数为实际的逻辑CPU数。写者是排他性的,一个读写锁同时只能有一个写者或多个读者(与CPU数相关),但不能同时既有读者又有写者。

在读写锁保持期间也是抢占失效的。如果读写锁当前没有读者,也没有写者,那么写者可以立刻获得读写锁,否则它必须自旋在那里,直到没有任何写者或读者。如果读写锁没有写者,那么读者可以立即获得该读写锁,否则读者必须自旋在那里,直到写者释放该读写锁。

Structure Definition

从结构上看,读写锁与自旋锁基本相似,实际上二者的实现也十分相似,二者的关系可以类比读写信号量与信号量的关系。

arch_read_lock & arch_read_unlock

Read_lock实现上判断lock+1是否为负,为负说明有写者持有锁(0x80000000),此时调用wfe进入一小段自旋状态后再度执行;若非负,则将lock+1更新至lock中。

对应read_lock,read_unlock仅仅需要将lock -1 更新至lock。

arch_write_lock & arch_write_unlock

write_lock 在尝试获得锁时,检查lock是否为0,不为0则说明有读者或者写者持有锁,此时wfe进入一小段等待直到lock为0,若lock为0则赋值lock获得锁。

Write_unlock只需将lock置零即可。

从这里可以看出,读写锁的实现上以及功能上,相当于针对自旋锁对于读多写少的场景提高并发度,设计原理与读写信号量十分类似。

RW_Lock API

三、顺序锁(seqlock)

顺序锁是对读写锁的一种优化:读者绝不会被写者阻塞,也就说,读者可以在写者对被顺序锁保护的共享资源进行写操作时仍然可以继续读,不必等待写者完成写操作,写者也不需要等待所有读者完成读操作才去进行写操作。但是,写者与写者之间仍然是互斥的。写操作的优先级大于读操作。

顺序锁有一个限制,它必须要求被保护的共享资源不含有指针,因为写者可能使得指针失效,但读者如果正要访问该指针,将导致OOPs。如果读者在读操作期间,写者已经发生了写操作,那么,读者必须重新读取数据,以便确保得到的数据是完整的。顺序锁适用于读多写少的情况。

这种锁对于读写同时进行的概率比较小的情况,性能是非常好的,而且它允许读写同时进行,更大地提高了并发性。顺序锁的一个典型的应用在于时钟系统。

Structure Definition

从结构上看,也是依赖于自旋锁的,seqcount用于同步写者访问的顺序以更新读者访问,自旋锁的作用在于实现写操作之间的互斥,读者访问不受限制。

write_seqlock & write_sequnlock

顺序锁对写操作之间必须互斥,实现上调用spin_lock进行互斥,另外对seqcount操作以同步读者的访问。

seqcount的计数符合以下规则:进入临界区时加一,离开临界区时也加一

read_seqretry & read_seqbegin

read_seqcount_begin返回当前seqlock的seqcount, 在读完后,需调用read_seqretry查看读者读完后的seqcount是否与读之前一致,一致则结束,不一致则说明有写操作正在或已经执行,需要重新读一次以更新数据。另外read_seqbegin返回的是lock.seqcount/2,实际上是写操作发生的次数。

seqlock API

其他_irqsave,_irq,_bh版本均是与其他锁类似的。

四、RCU(Read-Copy Update)

RCU是读写锁的高性能版本,既允许多个读者同时访问被保护的数据,又允许多个读者和多个写者同时访问被保护的数据(注意:是否可以有多个写者并行访问取决于写者之间使用的同步机制),读者没有任何同步开销,而写者的同步开销则取决于使用的写者间同步机制。

对于被RCU保护的共享数据结构,读者不需要获得任何锁就可以访问它,但写者在访问它时首先拷贝一个副本,然后对副本进行修改,最后使用一个回调(callback)机制在适当的时机(所有引用该数据的CPU都退出对共享数据的操作时)把指向原来数据的指针重新指向新的被修改的数据。有一个专门的垃圾收集器探测读者的信号,一旦所有读者都已发送信号告知它们不在使用被RCU保护的数据结构,垃圾收集器就调用回调函数完成最后的数据释放或修改操作。

RCU不能替代读写锁,当写比较多时,对读者的性能提高不能弥补写者导致的损失,但是大多数情况下RCU的表现高于读写锁。

RCU Basic API

RCU 临界区管理

之前的同步机制中,均是利用锁或原子操作实现的,一个锁管理一个临界区,并通过加锁解锁控制进程进入或者离开临界区。一个程序中可以存在若干的临界区,因此可以对应存在若干把锁分别管理,这是之前所有锁机制的基础。

然而RCU并不基于锁机制实现,RCU字段是耦合在进程描述符和CPU变量中的,是一种与系统强耦合的同步机制,RCU负责管理进程内所有的临界区,进程通过调用rcu_read_lock与rcu_read_unlock标记读者临界区,通过rcu_assign_pointer、list_add_rcu将数据纳入保护区,当写者copy出新数据时在读者全部退出临界区后,将新数据指针更新,旧数据将在垃圾收集器的检查中被释放,但存在延迟。

RCU 限制条件

  • RCU只保护动态分配并通过指针引用的数据结构
  • 在被RCU保护的临界区中,任何内核路径都不能睡眠(经典实现中)

RCU callback的实现

rcu_head 是RCU回调函数的关键结构。此外,回调机制主要涉及两个基本函数__call_rcu(用于注册), __rcu_reclaim(用于调用)。

__call_rcu仅仅将func注册进rcu_head, 便立刻返回。该func一般用于回收释放copy后遗留的旧数据垃圾,但是RCU采用了延时执行防止读者还在读旧数据时回收数据造成崩溃。

Rcp主要用于全局控制,而rcu的回调函数以链式组织,next用于遍历链。

__rcu_reclaim用于回收rcu先前分配的旧数据,回调函数也是回收操作的一种。

实际上,synchronize_rcu在等待读者全数退出临界区时,也通过call_rcu注册了回调函数。

相对麻烦的是回收阶段,RCU通过一个垃圾收集器检查需要回收的旧数据并调用回调函数释放,准确的说调用rcu_check_callbacks检查是否有需要执行的回调函数,而后调用rcu_process_callbacks执行必要的rcu 回调函数。

那么问题来了,谁去调用rcu_check_callbacks函数呢?时钟系统,每当时间片消耗完或者出现时钟中断,时钟系统都将调用rcu_check_callbacks进行及时检查处理,避免过量的旧数据垃圾造成内存浪费。

RCU read

rcu_read_lock与rcu_read_unlock的经典实现是不可抢占的,从代码看,这两个函数仅仅用于开关抢占。

RCU read之所以禁止抢占,主要是由于写者必须等待读者完全执行完退出临界区方能修改数据指针。一旦读者被抢占,那么其退出临界区的过程将会阻塞,进而阻塞写者,这对性能是一种不小的开销。但是现在的linux 内核版本中提供了可抢占的版本,只是对抢占深度做了把控。

RCU Synchronize

可是RCU是如何获知所有读者已经离开临界区?RCU read实现中并没有设置字段标记进出临界区,RCU是通过什么判断的呢?既然RCU read过程不可抢占,那么换言之,若所有 CPU 都已经过一次上下文切换,则所有前置 reader 的临界区必定全部退出。

我们主要分析以下两种:

  • rcu_check_callbacks
  • synchronize_rcu

user其实在调用中真实的传入是user_tick,值为1指用户时间,0指系统时间,由于RCU必须在内核态执行,因此user为1说明必然不处于lock~unlock的时段,很有可能已经发生过rcu_read,因此发送一个RCU_SOFTIRQ软中断,调用rcu_process_callbacks。

synchronize_rcu的核心是wait_rcu_gp函数。

该函数通过注册一个func为wakeme_after_rcu的rcu_head并等待该rcu_head完成回调来判断之前的rcu读者已经全部退出。

由于该rcu_head注册较晚,当且仅当当前的读者都已退出临界区,该rcu_head的回调才可能执行,因此当该func回调完成,就必然已经满足同步条件。最后销毁该多余的head内存。

如下图:

RCU Example

Input.c 中的使用为例。

Grab_device即挂载设备,注意这里的rcu_assign_pointer用于将dev->grab加入rcu保护的共享区,handle(处理函数)是其值。在这里完成了向rcu注册数据的过程。

Input_pass_value处理所有的输入事件,首先我们read_lock标记进入临界区不可抢占,读出dev->grab并以处理输入事件,最后read_unlock退出临界区。

Release device与挂载相对,释放过程即将原本的handler变为NULL, 最后调用synchronize_rcu通知所有输入事件handler移除

五、同步机制之间的比较

(全文完!)

本文分享自微信公众号 - Linux阅码场(LinuxDev)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 谢宝友: 深入理解RCU之七:分级RCU实现

    本文是为那些希望非常深层次的理解RCU的骨灰级黑客准备的。这些黑客应当首先阅读《深入理解RCU》系列文章的第1~6篇。骨灰级代码狂也可能有兴趣直接看看本文。

    Linux阅码场
  • 从big.LITTE到DynamIQ

    兰新宇,坐标成都的一名软件工程师,从事底层开发多年,对嵌入式,RTOS,Linux和虚拟化技术有一定的了解,有知乎专栏“术道经纬”进行相关技术文章的分享,欢迎大...

    Linux阅码场
  • 宋牧春: Linux内核内存corruption检查机制KASAN实现原理

    http://www.wowotech.net/memory_management/424.html

    Linux阅码场
  • 大数据投融资周报(2月3日——2月9日,共17起)

    【数据猿导读】 本期投融资周报共收录17起投融资事件,13家中国企业,2家美国大企业,1家澳大利亚企业,1家埃及企业 编辑 | sharon 官网 | www....

    数据猿
  • Oculus发布Touch控制器挂接口,用以将现实物品带入虚拟场景

    VRPinea
  • 观点 | 深度学习:简单而有局限性的求解方式

    选自Keras Blog 作者:Francois Chollet 机器之心编译 参与:路雪、李泽南 在人工智能,特别是深度学习破解了一个又一个难题,在很多任务上...

    机器之心
  • 切入物流分拣市场,3D机器视觉还有多长的路要走?

    赵青骨子里是个不安分的人。2009年硕士毕业后,他因为不想进入公务员体系或国企按部就班的工作而加入了宝洁。七年后,同样因为这点不安分,他毅然离开创办了熵智科技。

    AI掘金志
  • apollo本地启动

    使用apollo最新的1.1版本:https://github.com/ctripcorp/apollo 导入idea设置启动配置

    似水的流年
  • kubernetes-6:使用yaml方式进行apollo容器化

    http://toutiao.com/item/6698283305726378504/

    千里行走
  • 从此,激光雷达和摄像头,就是一个东西了?

    最近几年,放在摄像头上的深度学习研究,发展很蓬勃。相比之下, 激光雷达 (LiDAR) 身上的学术进展并不太多。

    量子位

扫码关注云+社区

领取腾讯云代金券