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

Linux kernel同步机制(上篇)

在现代操作系统里,同一时间可能有多个内核执行流在执行,因此内核其实像多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问,尤其是在多处理器系统上,更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。在主流的Linux内核中包含了如下这些同步机制包括:

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

本文章分为两部分,这一章我们主要讨论原子操作,自旋锁,信号量和互斥锁。

一、原子操作

原子操作的概念来源于物理概念中的原子定义,指执行结束前不可分割(即不可打断)的操作,是最小的执行单位。

原子操作与硬件架构强相关,其API具体的定义均位于对应arch目录下的include/asm/atomic.h文件中,通过汇编语言实现,内核源码根目录下的include/asm-generic/atomic.h则抽象封装了API,该API最后分派的实现来自于arch目录下对应的代码。

Structure Definition

typedefstruct{intcounter;}atomic_t;

原子操作主要用于实现资源计数, 许多引用计数(refcnt)就是通过原子操作实现,例如TCP/IP协议栈的IP碎片中,struct ipq中的refcnt字段,类型即为atomic_t。

atomic_add

原子操作的实现比较简单,以下为例。

原子操作的原子性依赖于ldrex与strex实现,ldrex读取数据时会进行独占标记,防止其他内核路径访问,直至调用strex完成写入后清除标记。自然strex也不能写入被别的内核路径独占的内存,若是写入失败则循环至成功写入。

API

原子操作的API包括如下, 以arm平台为例:

二 、自旋锁(spinlock)

自旋锁是这样一种同步机制:若自旋锁已被别的执行者保持,调用者就会原地循环等待并检查该锁的持有者是否已经释放锁(即进入自旋状态),若释放则调用者开始持有该锁。自旋锁持有期间不可被抢占。

Structure Definition

从定义出发, spinlock根本的实现依赖于具体架构实现中slock这个变量,由于spin_lock是大多locking机制的基础,我们看一看它的实现。

Lock & Unlock

核心unlock函数,使owner自增,保持数据同步。

核心lock函数,使slock +2^16, 当next==owner时,释放锁,否则进入循环等待。Prefetchw用于cache预加载数据。

由于slock与tickets共享同一块内存(union),slock 占32位4字节,tickets内部变量next与owner各16位2字节。以大端序为例,slock 高2字节与next共享,低2字节与owner共享,因此arch_spin_lock实际上是将tickets.next+1。假设初始时next与owner皆为0,此时next与owner不等,通过wfe指令进入一小段时间等待状态,而后读取新的owner值检查与next是否相等,不等则继续等待,相等则结束等待。

而owner的值由arch_spin_unlock控制,即unlock控制何时结束等待。

Spin_lock basic API

Spin_lock API & irq

性能上,spin_lock > spin_lock_bh > spin_lock_irq > spin_lock_irqsave。

安全上,spin_lock_irqsave > spin_lock_irq > spin_lock_bh >spin_lock。

Spin_lock 不同版本的使用

spin_lock用于阻止在不同CPU上的执行单元对共享资源的同时访问以及不同进程上下文互相抢占导致的对共享资源的非同步访问,而中断失效(spin_lock_irq)和软中断失效(spin_lock_bh)却是为了阻止在同一CPU上软中断或中断对共享资源的非同步访问。

  • 如果被保护的共享资源只在进程上下文访问和软中断上下文访问,那么当在进程上下文访问共享资源时,可能被软中断打断,从而可能进入软中断上下文来对被保护的共享资源访问,因此对于这种情况,对共享资源的访问最好使用spin_lock_bh和spin_unlock_bh来保护。
  • 如果被保护的共享资源只在进程上下文和tasklet或timer上下文访问,那么应该使用与上面情况相同,因为tasklet和timer是用软中断实现的。
  • 如果被保护的共享资源只在两个或多个tasklet或timer上下文访问,那么对共享资源的访问仅需要用spin_lock和spin_unlock来保护,不必使用_bh版本,因为当tasklet或timer运行时,不可能有其他tasklet或timer在当前CPU上运行。 如果被保护的共享资源只在一个软中断(tasklet和timer除外)上下文访问,那么这个共享资源需要用spin_lock和spin_unlock来保护,因为同样的软中断可以同时在不同的CPU上运行。
  • 如果被保护的共享资源在软中断(包括tasklet和timer)或进程上下文和硬中断上下文访问,那么在软中断或进程上下文访问期间,可能被硬中断打断,从而进入硬中断上下文对共享资源进行访问,因此,在进程或软中断上下文需要使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。
  • 在使用spin_lock_irq和spin_unlock_irq的情况下,完全可以用spin_lock_irqsave和spin_unlock_irqrestore取代,那具体应该使用哪一个也需要依情况而定,如果可以确信在对共享资源访问前中断是使能的,那么使用spin_lock_irq更好一些,因为它比spin_lock_irqsave要快一些。

三、信号量(Semaphore)

Linux内核的信号量在概念和原理上与用户态的System V的IPC机制信号量是一样的,但是它不可能在内核之外使用,因此它与System V的IPC机制信号量完全不同。

信号量是这样一种同步机制:信号量在创建时设置一个初始值count,用于表示当前可用的资源数。一个任务要想访问共享资源,首先必须得到信号量,获取信号量的操作为count-1,若当前count为负数,表明无法获得信号量,该任务必须挂起在该信号量的等待队列等待;若当前count为非负数,表示可获得信号量,因而可立刻访问被该信号量保护的共享资源。当任务访问完被信号量保护的共享资源后,必须释放信号量,释放信号量通过把count+1实现,如果count为非正数,表明有任务等待,它也唤醒所有等待该信号量的任务。

Structure Definition

可以发现,信号量是基于spinlock实现的,对其封装以满足高级的功能,例如全局共享资源的配置,并通过等待队列较为灵活的调度。信号量与接下来要讲的mutex都建立在自旋锁实现的执行同步上。

了解了信号量的结构与定义,我们来看看最核心的两个实现down ,up。

down & up

down用于调用者获得信号量,若count大于0,说明资源可用,将其减一即可。

若count<0,将task加入等待队列,并进入等待队列,并进入调度循环等待,直至其被__up唤醒,或者因超时以被移除等待队列。

up用于调用者释放信号量,若waitlist为空,说明无等待任务,count+1,该信号量可用。

若waitlist非空,将task从等待队列移除,并唤醒该task,对应__down条件。

Semaphore API

四、互斥锁(Mutex)

Linux 内核互斥锁是非常常用的同步机制,互斥锁是这样一种同步机制:在互斥锁中同时只能有一个任务可以访问该锁保护的共享资源,且释放锁和获得锁的调用方必须一致。因此在互斥锁中,除了对锁本身进行同步,对调用方(或称持有者)必须也进行同步。当互斥锁无法获得时,task会加入等待队列,直至可获得锁为止。

Structure Definition

互斥锁从结构上看与信号量十分类似,但将原本的int类型的count计数,改成了atomic_long_t的owner以便同步,保证释放者与持有者一致。

mutex_lock & mutex_unlock

上图简单的表现了mutex_lock与mutex_unlock实现的对称性,___mutex_trylock_fast用于owner为0的特殊状态,用于快速加锁,实现核心在slowpath版本上。

*might_sleep指在之后的代码执行中可能会sleep。

由于mutex实现的具体步骤相当复杂,这里选讲比较核心简单的两块。Mutex有关等待队列的处理比较复杂,有兴趣阅读相关内核书籍。

当且仅当lock当前的owner没有变化时(没有其他mutex抢先拥有该锁),此时获得锁,返回NULL, owner 为 curr | flags,owner本身对应task指针。若该锁已被占用,owner和当前task不匹配,返回owner对应指针。

当unlock时,不考虑等待队列的影响,则与上述类似,当且仅当之前持有锁的owner可以解锁,解锁时本来应将lock的owner置为初始0,但是这里保留了mutex的flag以便后续操作。

*这里的owner实际上是task_struct的指针,也就是地址,由于task_struct的地址是L1_cache对齐的,因此实际上指针地址后三位为0,因此linux内核利用这三个比特位用于设置mutex的标志位,不影响指针地址的表示也更高效利用了冗余的比特位。

Mutex 的改进

最初的互斥锁仅支持睡眠等待,然而经过漫长时间的改进,如今的互斥锁已经可以支持自旋等待,通过MCS锁机制实现。在内核中可以选择配置以支持,CONFIG_MUTEX_SPIN_ON_OWNER。

如上是4.9内核中mutex中常用有效的字段,目前最常用的算法是OSQ算法。自旋等待机制的核心原理是当发现持有者正在临界区执行并且没有其他优先级高的进程要被调度(need_resched)时,那么mutex当前所在进程认为该持有者很快会离开临界区并释放锁,此时mutex选择自旋等待,短时间的自旋等待显然比睡眠-唤醒开销小一些。

在实现上MCS保证了同一时间只有一个进程自旋等待持有者释放锁。MCS 的实现较为复杂,具体可参考一些内核书籍。MCS保证了不会存在多个cpu争用锁的情况,从而避免了多个CPU的cacheline颠簸从而降低系统性能的问题。

经过改进后,mutex的性能有了相当大的提高,相对信号量的实现要高效得多。因此我们尽量选用mutex。

Mutex 的使用条件

Mutex虽然高效,灵活,但存在若干限制条件,需要牢记:

  • 同一时刻只有一条内核路径可以持有锁
  • 只有锁持有者可以解锁
  • 不允许递归加锁解锁
  • 进程持有mutex时不可退出
  • Mutex 可能导致睡眠阻塞,不可用于中断处理与下半部使用

Mutex API

未完待续...

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

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

原始发表时间:2020-08-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 郭健: Deadline调度器之(二):细节和使用方法

    Linux内核的DL调度器是一个全局EDF调度器,它主要针对有deadline限制的sporadic任务。注意:这些术语已经在本系列文章的第一部分中说明了,这里...

    Linux阅码场
  • 郭健:deadline调度器之(一):原理

    实时系统是这样的一种计算系统:当事件发生后,它必须在确定的时间范围内做出响应。在实时系统中,产生正确的结果不仅依赖于系统正确的逻辑动作,而且依赖于逻辑动...

    Linux阅码场
  • Linus Torvalds佛系归来:彬彬有礼地指出糟糕的内核代码

    转载自 |  https://www.solidot.org/story?sid=58460

    Linux阅码场
  • PAT 1049 Counting Ones (30分) 编程之美--1的个数

    The task is simple: given any positive integer N, you are supposed to count the ...

    vivi
  • p0p3与IMAP

    py3study
  • 开发数字资产交易平台,场外otc交易系统开发

    历经多次变革,数字资产市场也没有尘埃落定,而整个市场是在不断地发展,新型模式的出现,也将数字资产的发展推向一个又一个高潮。对于现在这个数字资产市场来说,开发有关...

    v13823115027
  • Python3网络爬虫(四):使用User Agent和代理IP隐藏身份

    运行平台:Windows Python版本:Python3.x IDE:Sublime text3 一、为何要设置User Agent     有一...

    Jack_Cui
  • TKDE|Foresee Urban Sparse Traffic Accidents: A Spatiotemporal Multi-Granularity Perspective

    本文以交通事故预测为应用背景,提出了一个基于多源时空数据的多步、多粒度稀疏事件预测模型。其中集中归纳总结并缓解了时空稀疏问题、短期状态变化感知与多步预测问题。

    微风、掠过
  • 多线程编程学习四(Lock 的使用)

    一、前言     本文要介绍使用Java5中 Lock 对象,同样也能实现同步的效果,而且在使用上更加方便、灵活,主要包括 ReentrantLock 类的使用...

    JMCui
  • JDK并发包总结

    线程1, 线程2分别去获取lock1, lock2, 触发死锁. 最终通过DeadlockChecker来触发线程中断.

    用户1216491

扫码关注云+社区

领取腾讯云代金券