Linux 在自动驾驶中可靠吗

Controlling a laser with Linux is crazy, but everyone in this room is crazy in his own way. So if you want to use Linux to control an industrial welding laser, I have no problem with your using PREEMPT_RT." -- Linus Torvalds

What's the RT linux?

实时分为硬实时和软实时，硬实时要求绝对保证响应时间不超过期限，如果超过期限，会造成灾难性的后果，例如汽车在发生碰撞事故时必须快速展开安全气囊；软实时只需尽力使响应时间不超过期限，如果偶尔超过期限，不会造成灾难性的后果.

RTLinux、QNX和VxWorks这些操作系统提供了硬实时能力，Linux这种通用操作系统只能提供软实时能力。

目前Linux内核主线不支持软实时，而是RT patch+Linux内核主线的版本来生成相应的实时内核源代码。

自动驾驶中实时性需求

我们知道在自动驾驶中，需要对突发事件进行及时的响应。如前方突然出现障碍物，突然出现其他事物闯入航道。如果不能及时响应，则会出现灾难性的后果。那么从自动驾驶系统的角度来看，这些突发的事件，对系统有怎样的实时性要求？

从某个事件发生到负责处理这个事件的线程开始执行，过程如下，

• Sensor（Camera/lidar) 提供航道相关的视图。
• 自动驾驶系统进行视角融合。得到航道的相关信息。如障碍物是什么？障碍物是大小，距离等，交通信息，红绿灯，车道/人行道/车速限制等。
• 自动驾驶系统根据融合的视角信息和车辆行驶的数据，车速，位置，车轮的转速等信息做出决定车的下一步动作（加速，减速，刹车，转向等）。
• 自动驾驶系统把相关决定信息发送给车辆控制域中的执行器。
• 执行器执行相关的车辆控制，从而完成车辆的自动驾驶。

我们知道 在自动驾驶中 camera 一般是30/60FPS,而lidar是10fps。以120KM/h 计算。车速是34m/s ，一个camera frame 周期基本是33ms（30fps），也即自动驾驶系统每隔1.1米（120KM/h)收到一个camera sensor的数据，假设障碍物在高速行驶的航道中以距离车50m出现，则自动驾驶系统必须要在300ms内（安全刹车距离以40m计算）大概9 个camera frame 数据/3个lidar数据，识别出障碍物并下达相关指令给执行器。而自动驾驶系统（比较牛B 视角融合AI的算法）大概也需要3-5个（100ms）senor的数据，才能准确的识别相关的物体。所以实时性要求在自动驾驶中特别比较重要。

我们知道通常的linux （没有RT patch）的也是可以preempable 的kernel。通常normal thread 也会被RT thread preemp。 只要kernel enable了CONFIG_PREEMPT.既如此为什么还有RT patch?

然后在没有RT patch的Linux 中，并不是有了RT thread 都可以抢占。导致处理器不能及时响应抢占的因素有很多，主要的因素有：正在执行中断处理程序，或者正在执行禁止中断的临界区。

RT Patch 内核抢占模型

抢占可以分为user space抢占和kernel space抢占，user space抢占是指允许task在用户模式执行的时候被抢占，kernel space抢占是指允许task在内核模式执行的时候被抢占。user space抢占总是无条件支持的，并且不可以关闭。kernel space抢占取决于内核是不可抢占内核还是可抢占内核，在可抢占内核中，可以在一个临界区里面禁止内核抢占。

通用linux主要有以下几种抢占，

• No Forced Preemption (Server)，不可抢占内核，CONFIG 是CONFIG_PREEMPT_NONE。这是传统的抢占模型，目标是使吞吐量最大化。大多数时候提供良好的延迟，但是没有保证，可能偶尔出现长的延迟。这种模型主要用于服务器和科学计算系统。如果希望使内核的处理能力最大化，不考虑调度延迟，那么应该选择这种模型。
• Voluntary Kernel Preemption (Desktop)，自愿内核抢占，CONFIG是CONFIG_PREEMPT_VOLUNTARY。这种模型通过增加抢占点的方式减小延迟。在内核里面选择性地增加了一些抢占点，目的是减小最大调度延迟和对交互事件提供更快的响应，代价是稍微降低吞吐量。当低优先级进程在内核模式执行的时候，在预定的抢占点自愿被抢占。这种模型主要用于桌面系统。它减少了长延迟（几百毫秒到几秒）的发生，但是没有消除
• Preemptible Kernel (Low-Latency Desktop)，低延迟可抢占内核，CONFIG是CONFIG_PREEMPT__LL。这种模型使除了临界区以外的所有内核代码是可以抢占的。当低优先级进程在内核模式执行的时候，可以非自愿地被抢占。这种模型提供了很低的响应延迟，最坏情况的延迟时间是几毫秒，代价是稍微降低吞吐量和稍微增加运行时开销。这种模型主要用于有毫秒级别延迟需求的桌面系统和嵌入式系统。
• Preemptible Kernel (Basic RT)，基本实时内核，CONFIG是CONFIG_PREEMPT_RTB。这种模型基本上和低延迟可抢占内核相同，但是开启了完全抢占内核的初步修改。
• Fully Preemptible Kernel (RT)，完全抢占内核，也称为实时内核，CONFIG是CONFIG_PREEMPT_RT_FULL。这种模型把自旋锁和读写锁替换为可以抢占的、支持优先级继承的锁，强制中断线程化，并且引入各种机制来打破长的、不可抢占的临界区。这种模型主要用于延迟要求为100微秒或稍低（几十微秒）的实时系统。

RT PATCH + Linux

为了RT 线程能实时的抢占从而保证系统的实时性，RT patch 主要做了如下工作，

• 中断线程化，内核中处理中断下半段的函数，几乎都使用内核线程执行中断处理函数。
• 为了减小时钟中断处理程序的执行时间，把高精度定时器的到期模式分为软中断到期模式和硬中断到期模式，大多数高精度定时器使用软中断到期模式，在软中断里面执行。
• 如果使用内核线程执行中断处理函数，那么原来禁止硬中断的临界区不需要禁止硬中断，为了兼顾非实时内核和实时内核，引入本地锁，非实时内核把本地锁映射到禁止内核抢占和禁止硬中断，实时内核把本地锁映射到基于实时互斥锁实现的自旋锁。
• 实现可抢占RCU，把RCU保护的读端临界区变成可以抢占的。
• 把自旋锁和读写锁替换为可以抢占的、支持优先级继承的锁。
• 互斥锁、伤害/等待互斥锁和读写信号量支持优先级继承。
• 更改CFS的调度周期。把调度rq的深度有32改为8.
• Normal 线程的最大调度周期从32x4=128ms 到8x4=32ms，从而保证normal线程也能在一定的时间窗口得到执行。

RT thread 调度策略

Linux内核为RT task 提供了2种调度器：SCHED_DEADLINE和SCHED_RT，其中SCHED_RT又分为先进先出调度（SCHED_FIFO）和轮流调度（SCHED_RR）。

SCHED_DEADLINE主要为周期性RT线程进行调度.,其有三个输入参数，运行时间runtime、截止期限deadline和周期period。每个周期运行一次，在截止期限之前执行完，一次运行的时间长度是runtime。

SCHED_FIFO 是根据任务的先进先出来调度线程。没有时间片，如果没有更高优先级的实时task，那么它将一直在处理器运行，知道任务完成。

SCHED_RR轮流调度有时间片，task用完时间片以后加入优先级对应运行队列的尾部，把处理器让给优先级相同的其他实时进程。

先进先出调度和轮流调度的主要区别是对优先级相同的实时进程的处理策略不同：前者不会把处理器让给优先级相同的实时进程，后者会把处理器让给优先级相同的实时进程。

中断线程化

中断线程化是使用内核线程执行中断处理函数，内核线程的名称是“irq/<irq>-<devname>”（<irq>是Linux中断号，<devname>是设备名称），调度策略是SCHED_FIFO，实时优先级是50。

函数request_threaded_irq()用来注册中断处理函数，原型如下。

include/linux/interrupt.h

extern int __must_check

request_threaded_irq(unsigned int irq, irq_handler_t handler,

irq_handler_t thread_fn,

unsigned long flags, const char *name, void *dev);

参数handler指定主函数，主函数在硬中断上下文里面被调用，需要检查中断是不是对应的外围设备发送的。如果中断是对应的外围设备发送的，那么handler函数返回IRQ_HANDLED或IRQ_WAKE_THREAD。如果不需要进一步的处理，那么返回IRQ_HANDLED。如果需要进一步的处理，那么返回IRQ_WAKE_THREAD，中断处理程序将会唤醒中断处理线程，执行参数thread_fn指定的函数。如果多个外围设备共享同一个硬件中断号（即多个外围设备的中断请求线连接到中断控制器的同一个引脚，现在这种用法很少），那么参数handler必须指定一个函数。其他情况通常把参数handler设置为空指针。

参数thread_fn指定中断处理线程调用的函数。如果参数thread_fn是空指针，那么不创建中断处理线程。

如果参数handler是空指针，但是参数thread_fn不是空指针，那么使用默认的主函数irq_default_primary_handler()。函数irq_default_primary_handler()的代码如下，这个函数直接返回IRQ_WAKE_THREAD。

少数中断不能线程化，典型的例子是时钟中断。对于不能线程化的中断，注册处理函数的时候必须设置标志IRQF_NO_THREAD。

高精度定时器

在实时内核中，把高精度定时器的到期模式分为软中断到期模式（HRTIMER_MODE_SOFT）和硬中断到期模式（HRTIMER_MODE_HARD），

软中断到期模式的高精度定时器，到期的时候在类型为HRTIMER_SOFTIRQ的软中断里面执行定时器回调函数。在实时内核中，软中断由软中断线程执行，或者在进程开启软中断的时候执行。

硬中断到期模式的高精度定时器，到期的时候在时钟中断处理程序里面执行定时器回调函数。

如果没有指定到期模式，那么在实时内核中默认使用软中断到期模式。

为了减小时钟中断处理程序的执行时间，大多数高精度定时器应该使用软中断到期模式。少数高精度定时器必须使用硬中断到期模式，如下。

(1)必须在硬中断里面执行，例如进程调度器周期性地调度进程。

(2)对延迟很敏感，例如函数nanosleep()把睡眠时间精确到纳秒。

软中断线程化

在非实时内核中，一部分软中断在中断处理程序的后半部分执行，有时间限制：最多执行10轮，并且总时间不超过2毫秒。剩下的软中断由软中断线程执行.每个处理器有一个软中断线程，名称是“ksoftirqd/<cpu>”（<cpu>是处理器编号），调度策略是SCHED_NORMAL，优先级是120。

在实时内核中，软中断由软中断线程执行，或者在进程开启软中断的时候执行。中断处理程序的后半部分唤醒当前处理器上的软中断线程.

更改RCU读端临界区不可抢占的问题

Linux内核支持3种RCU

• 不可抢占RCU（RCU-sched），不允许进程在读端临界区被其他进程抢占。
• 加速版不可抢占RCU（RCU-bh）是针对不可抢占RCU的改进，在软中断很多的情况可以缩短宽限期。
• 可抢占RCU（RCU-preempt），也称为实时RCU。可抢占RCU允许进程在读端临界区被其他进程抢占。编译内核时需要开启配置宏CONFIG_PREEMPT_RCU。

实时内核强制开启可抢占RCU的配置宏CONFIG_PREEMPT_RCU。

优先级反转问题

什么是优先级反转（priority inversion）问题？

假设进程1的优先级低，进程2的优先级高。进程1持有互斥锁，进程2申请互斥锁，因为进程1已经占有互斥锁，所以进程2必须睡眠等待，导致优先级高的进程2等待优先级低的进程1。

如果存在进程3，优先级在进程1和进程2之间，那么情况更糟糕。假设进程1仍然持有互斥锁，进程2正在等待。进程3开始运行，因为它的优先级比进程1高，所以它可以抢占进程1，导致进程1持有互斥锁的时间延长，进程2等待的时间延长。

优先级继承（priority inheritance）

可以解决优先级反转问题。如果低优先级的进程持有互斥锁，高优先级的进程申请互斥锁，那么把持有互斥锁的进程的优先级临时提升到申请互斥锁的进程的优先级。在上面的例子中，把进程1的优先级临时提升到进程2的优先级，防止进程3抢占进程1，使进程1尽快执行完临界区，减少进程2的等待时间。

实时互斥锁（rt_mutex）实现了优先级继承。锁的等待者按优先级从高到低排序，如果优先级相等，那么先申请锁的进程的优先级高。持有锁的进程，如果它的优先级比优先级最高的等待者低，那么把它的优先级临时提升到优先级最高的等待者的优先级，代码如下。如果普通进程1持有锁，实时进程2等待锁，那么把普通进程1的优先级临时提升到实时进程2的优先级，普通进程1变成实时进程。

rt_mutex_lock() -> __rt_mutex_lock() -> rt_mutex_lock_state()

-> __rt_mutex_lock_state() -> rt_mutex_fastlock() -> rt_mutex_slowlock()

-> rt_mutex_slowlock_locked() -> task_blocks_on_rt_mutex()

实时内核使用实时互斥锁实现互斥锁（mutex）和伤害/等待互斥锁（ww_mutex），支持优先级继承。互斥锁的定义如下，可以看到在实时内核中互斥锁等同于实时互斥锁。

实时内核使用实时互斥锁实现读写信号量（rw_semaphore），支持优先级继承。

在实时内核中，自旋锁（spinlock_t）和读写锁（rwlock_t）是基于实时互斥锁实现的，临界区是可以抢占的，支持优先级继承。

自旋锁的修改

自旋锁（spinlock_t）保护的临界区是不可抢占的，导致实时进程不能被及时调度。实时内核使用实时互斥锁实现自旋锁，临界区是可以抢占的，支持优先级继承，spin_lock_irq()和spin_lock_irqsave()不会禁止硬中断。

少数使用自旋锁保护的临界区不允许抢占，内核定义了原始自旋锁（raw_spinlock），提供传统的自旋锁。在非实时内核中，spinlock和raw_spinlock完全相同。

选择spinlock和raw_spinlock的时候，最好坚持3个原则。

• 尽可能使用spinlock。
• 绝对不允许被抢占和睡眠的地方，使用raw_spinlock，否则使用spinlock。
• 如果临界区足够小，那么使用raw_spinlock。

对读写锁的修改

读写锁（rwlock_t）保护的临界区是不可抢占的，导致实时进程不能被及时调度。实时内核使用实时互斥锁实现读写锁，临界区是可以抢占的，支持优先级继承，read_lock_irq()、read_lock_irqsave()、write_lock_irq()和write_lock_irqsave()不会禁止硬中断。为了降低实现的复杂性，只允许一个进程获取读锁，进程可以递归获取读锁。

少数使用读写锁保护的临界区不允许抢占，内核定义了原始读写锁（raw_rwlock），提供传统的读写锁。在非实时内核中，rwlock和raw_rwlock完全相同。

选择rwlock和raw_rwlock的原则，与选择spinlock和raw_spinlock的原则相同。

修改使用禁止内核抢占或硬中断保护的临界区

对于使用禁止硬中断保护的临界区，因为在实时内核中使用内核线程执行大多数中断处理函数，所以大多数临界区不需要禁止硬中断。

对于使用禁止内核抢占保护的临界区，在实时内核中大多数临界区可以修改为可以抢占的。

为了在实时内核中把这两种临界区修改为可以抢占的，实时内核从3.0版本开始引入local_irq_lock，在合并到内核主线5.8版本的时候把名称改为local_lock（本地锁）。local_lock为使用禁止内核抢占或硬中断保护的临界区提供了命名的作用域。

非实时内核把local_lock映射到禁止内核抢占和禁止硬中断，

• local_lock(&llock)映射到preempt_disable()。
• local_unlock(&llock)映射到preempt_enable()。
• local_lock_irq(&llock)映射到local_irq_disable()。
• local_unlock_irq(&llock)映射到local_irq_enable()。
• local_lock_irqsave(&llock)映射到local_irq_save()。
• local_unlock_irqrestore(&llock)映射到local_irq_restore()。

实时内核把local_lock映射到一个每处理器自旋锁。函数local_lock()用来获取一个每处理器本地锁。

修改使用禁止软中断保护的临界区

在实时内核中，软中断由软中断线程执行，或者在进程开启软中断的时候执行，使用禁止软中断保护的临界区和软中断线程使用本地锁“softirq_ctrl.lock”互斥

对实时APP的设计需求

Linux内核对用户空间的内存（包括栈、代码段、数据段以及使用函数malloc()或mmap()动态分配的内存）使用惰性分配的策略，在内存不足的时候回收物理页，导致实时进程在访问页的时候触发页错误异常，影响实时性。

为了避免页错误异常造成的延迟，对实时应用程序的要求如下，

• 在启动的时候创建所有线程，不要在运行的过程中动态创建线程。
• 在启动的时候预留需要的内存，不要在运行的过程中使用函数malloc()或mmap()动态分配内存。
• 主动把线程的用户栈扩大到最大的需求。
• 使用函数mlockall(MCL_CURRENT)锁定映射到进程的虚拟地址空间的所有页，确保所有已经分配的虚拟内存区域映射到物理页，并且不允许内核回收这些物理页。
• 在运行的过程中不要调用可能引入或生成页错误异常的函数。例如调用fork()创建子进程，fork()使用写时复制技术，进程第1次写的时候触发页错误异常。例如调用fopen()打开文件，这个函数会动态分配内存，可能生成页错误异常。

业界使用

三星与特斯拉合作发布了一组23个补丁，用于使特斯拉的完全自动驾驶（FSD）SoC适用于主线Linux内核。这23个补丁使特斯拉的完全自动驾驶SoC能够从上游Linux内核启动，而目前使用的是下游内核构建。特斯拉不仅利用Coreboot支持开源。

的AMD GPU Linux驱动，甚至支持将其添加到主线Linux内核中。Tesla FSD SoC支持包括设备树的添加和对内核的各种修改，以提供这种基本支持，该技术主要是建立在现有的三星Exynos SoC驱动路径上。由于利用了内核中现有的三星驱动代码，特斯拉FSD SoC的支持只新增大约3.7万行的新代码。

特斯拉的FSD SoC是在2019年初推出的14纳米SoC，除了12个Cortex-A72内核外，还有一个Mali G71 GPU，两个神经处理单元，以及其他额外的IP块。

特斯拉FSD SoC对Linux内核的支持目前正在LKML上进行审查，以便可能被纳入未来的主线内核版本。

https://lore.kernel.org/lkml/20220113121143.22280-1-alim.akhtar@samsung.com/

AGL

Automotive Grade Linux是一个协作开源项目，由Linux 基金会管理，它将汽车制造商，供应商和技术公司聚集在一起，以加速开发和采用完全开放的联网汽车软件堆栈。他们的宗旨是：“以Linux为核心，建立一个通用的、基于Linux的联网汽车内部使用开源平台，以实现新功能和技术的快速开发。

Automotive Grade Linux (AGL) is a collaborative open source project that is bringing together automakers, suppliers and technology companies to build a Linux-based, open software platform for automotive applications that can serve as the de facto industry standard. Adopting a shared platform across the industry reduces fragmentation and allows automakers and suppliers to reuse the same code base, leading to rapid innovation and faster time-to-market for new products.

As a “code first” organization, AGL’s goals are to:

• Build a single platform for the entire industry
• Develop 70-80% of the starting point for a production project
• Reduce fragmentation by combining the best of open source
• Develop an ecosystem of developers, suppliers, expertise all using a single platform

Although initially focused on infotainment, AGL is the only organization planning to address all software in the vehicle: infotainment, instrument cluster, heads-up-display (HUD), telematics/ connected car, advanced driver assistance systems (ADAS), functional safety and autonomous driving.

RT PATCH

(1)仓库“http://git.kernel.org/cgit/linux/kernel/git/rt/linux-rt-devel.git”。

(2)仓库“http://git.kernel.org/cgit/linux/kernel/git/rt/linux-stable-rt.git”。