CH14-高级同步

本章将介绍高级同步的两个分类：无锁同步、实时同步。

当面临极端要求时，无锁同步会非常有帮助，但不幸的是无锁同步并非灵丹妙药。如在第五章的末尾所述，你应该在考虑采用无锁同步之前首先考虑分区、并行，以及在第八、九章所述的充分测试的脆弱 API。

避免锁

尽管锁在并行生产环境中吃苦耐劳，但在很多场景下可以通过无锁技术来大幅提高性能、扩展性和实时响应性。这种无锁技术的一个实际例子是第 5.2 节中所述的统计计数，它不但避免了锁，同时还避免了原子操作、内存屏障，甚至是计数器自增时的缓存未命中。我们已经介绍过的与无锁技术相关的例子有：

第 5 章中一些计数算法的快速路径。
第 6.4.3 中资源分配器缓存的快速路径。
第 6.5 中的迷宫求解器。
第 8 章中的数据所有权技术。
第 9 章中介绍的引用计数与 RCU 技术。
第 10 章中查找逻辑的代码路径。
第 13 章中介绍的大多数技术。

总的来说，无锁技术十分有用且已被大量应用。

然后，无锁技术最好是能够因此在设计良好的 API 之后，比如 inc_count、memblock_allock、rcu_read_lock 等等。因为对无锁的技术的混乱使用可能会引入一些难以解决的 BUG。

很多无锁技术的关键组件是内存屏障，下面的章节将会详细介绍。

无阻塞同步

术语“非阻塞同步(NBS)”描述 6 类线性化算法，这些算法具有前向执行保证。这些前向执行保证与构成实时程序的基础相混淆。

实时前向执行保证通常有些与之相关的确定时间。例如，“调度延迟必须小于 100ms”。相反，NBS 仅仅要求执行过程限定在有限时间内，没有确定的边界。
有时，实时前向执行具有概率性。比如，在软实时保证中“至少在 99.9% 的时间内，调度延迟必须小于 100ms”。相反，NBS 的前向执行保证传统上是无条件的。
实时前向执行保证通常以环境约束为条件。例如，仅仅当每个 CPU 至少有一定比例处于空闲时间，或者 IO 速度低于某些特定的最大值时，对最高优先级任务才能得到保证。相反，NBS 的前向执行保证通常是无条件的。
实时前向执行保证通常适用于没有软件 BUG 的情况下。相反，绝大多数 NBS 保证即使在面对错误终止 BUG 时也适用。
NBS 前向执行保证隐含线性化的意思。相反，实时前向执行保证通常独立于像线性化这样的约束。

不考虑这样的差异，很多 NBS 算法对实时程序极其有用。

在 NBS 层级中，目前有 6 种级别，大致如下：

无等待同步：每个线程在有限时间内运行。
无锁同步：至少某一个线程将在有限时间内运行。
无障碍同步：在没有争用的情况下，每个线程将在有限时间内运行。
无冲突同步：在没有争用的情况下，至少某一线程将在有限时间内运行。
无饥饿同步：在没有错误的情况下，每个线程将在有限时间内运行。
无死锁同步：在么有错误的情况下，至少某一个线程将在有限时间内运行。

第 1、2 类 NBS 于 1990 年代初期制定。第 3 类首次在 2000 年代初期制定。第 4 类首次在 2013 年制定。最后两类已经非正式使用了数十年，但是在 2013 年重新制定。

从原理上讲，任何并行算法都能够被转换为无等待形式，但是存在一个相对小的常用 NBS 算法子集，将在后续章节列出。

简单 NBS

最简单的 NBS 算法可能是使用获取——增加(atomic_add_return)原语对下整型计数器进行原子更新。

另一个简单的 NBS 算法用数组实现整数集合。在此，数组索引标识一个值，该值可能是集合的成员，并且数组元素标识该值是否真的是集合成员。NBS 算法的线性化准则要求对数组的读写，要么使用原子指令、要么与内存屏障一起使用，但是在某些不太罕见的情况下，线性化并不重要，简单使用易失性加载和存储就足够了。例如，使用 ACCESS_ONCE。

NBS 集合也可以使用位图来实现，其中每一个值可能是集合中的某一位。通常，读写操作可以通过原子位维护指令来实现。虽然 CAS 指令也可以使用。

5.2 一节中讨论的统计计数算法可被认为是无等待算法，但仅仅是用了一个狡猾的定义技巧，在该定义中，综合被考虑为近似值而不是精确值。由于足够大的误差区间是计算计数器综合的 read_count 函数的时间长度函数，因此不可能证明发生了任何非线性化行为。这绝对将统计计算算法划分为无等待算法。该算法可能是 Linux 内核中最常见的 NBS 算法。

另一个常见的 NBS 算法是原子队列，其中元素入队操作通过一个原子交换指令实现，随后是对新元素前驱元素的 next 指针的存储，如图 14.19 所示。该图展示了用户态 RCU 库的实现。当返回前向元素的引用时，第 9 行更新引用新元素的尾指针，该指针存储在局部变量 old_tail 中。然后第 10 行更新前向 next 指针，以引用最新添加的元素。最后第 11 行返回队列最初是否为空的标志。

虽然将单个元素出队需要互斥(因此出队是阻塞的)，但是将所有队列元素非阻塞的移除是可能的。不可能的是以非阻塞的方式将特定元素出队。入队可能是在第 9 行和第10 行之间失败，因此问题中的元素仅仅部分入队。这将导致半 NBS 算法，其中入队是 NBS 但是出队是阻塞式的。因此在实践中使用此算法的部分原因是，大多数产品软件不需要容忍随意的故障终止错误。

NBS 讨论

创建完全的非阻塞队列是可能的。但是，这样的队列要比上面列出的半 NBS 算法负责的多。这里的经验是，认真考虑你真的需要什么？放宽不相关的需求通常可以极大增加简单性和性能。

最近的研究指出另一种放宽需求的重要方式。结果是，不管是从理论上还是从实践上来说，提供公平调度的系统可以得到大部分无等待同步的优势，即使当算法仅仅提供 NBS 时也是这样。事实上，由于大量产品中使用的调度器都提供公平性，因此，与简单也更快的 NBS 相比，提供无等待同步的更复杂算法通常并没有实际的优势。

有趣的是，公平调度仅仅是一个有益的约束，在实践中常常得到满足。其他的约束集合可以允许阻塞算法实现确定性的实时响应。例如，如果以特定有限级的 FIFO 顺序来授予请求的公平锁，那么避免优先级翻转(如优先级继承或优先级上限)、有限数量的线程、有限长度的临界区、有限的加载，以及避免故障终止 BUG，可以让基于锁的应用获得确定性的响应时间。这个方法当然模糊了锁及无等待同步之间的区别，一切无疑都是好的。期望理论框架持续进步，进一步提高其描述如何在实践中构建软件的能力。

并行实时计算

什么是实时计算

将实时计算进行分类的一种传统方式，是将其分为硬实时和软实时。其中充满阳刚之气的硬实时应用绝不会错过其最后期限，而仅有阴柔之美的软实时应用，则可能被频繁(并且经常)错误其最后期限。

软实时

很容易发现软实时定义的问题。一方面，通过这个定义，任何软件都可以被说成是软实时应用：我的应用在 0.5ps 内计算 100 万点傅里叶变换；没门，系统时钟周期超过 300ps！如果术语软实时被滥用，那就明显需要某些限定条件。

因此，我们应当这么说：一个特定软实时应用必须至少在一定比例的时间范围内，满足实时响应的要求。例如，我们可能这么说，它必须在 99.9% 的时间范围内，在 20ms 内执行完毕。

这当然带来的问题，当应用程序不能满足响应时间要求，应当做什么？答案根据应用程序而不同，不过有一个可能是，被控制的系统有足够的灵活性和惯性，对于偶尔出现的延迟控制行文，也不会出现问题。另一种可能的做法是，应用有两种方式计算结果，一种方式是快速且具有确定性，但是不太精确的方法，还有一种方式是非常精确，但是具有不确定的计算时间。合理的方法是并行启动这两种方法，如果精确的方法不能按时完成，就中止并使用快速但不精确方法所产生的结果。对于快速但不精确的方法，一种实现是在当前时间周期内不采取任何控制行为，另一种实现是采取上一个时间周期同样的控制行为。

简而言之，不对软实时进行精确的度量，谈论软实时就没有任何意义。

硬实时

相对的，硬实时的定义相当明确。毕竟，一个特定的系统，它要么是满足其执行期限，要么不满足。不幸的是，这种严格的定义意味着不可能存在任何硬实时的系统。事实上，你能够构建更强大的系统，也许还有额外的冗余性。但是另一个事实是，我们可以找到一把更大的锤子。

不过话说回来，由于这明显不仅仅是一个硬件问题，而实在是一个大的硬件问题，因此指责软件是不公平的。这表明我们定义硬实时软件为哪种总是能够满足其最后期限的软件，其前提是没有硬件故障。不幸的是，故障不仅仅是一个可选项。硬实时响应是整个系统的属性，而不仅仅是软件属性。

但是我们不能求全责备，也许我们可以像前面所述的软实时方法那样，通过发出通知消息的方法来解决问题。

如果一个系统在不能满足符合法律条文的最后期限是，总是立即发出告警通知。但是这样的系统是无用的。很明显，很明显，必须要求系统在一定比例的时间内，满足其最后期限，或者，必须禁止其连续突破其最后期限这样的操作达到一定次数。

显然，我们没办法来对硬实时或软实时给出一种明确无误的说法。

现实世界的实时

虽然像“硬实时系统总是满足最后期限的要求”这样的句子读起来很上口，无疑也易于记忆，但是，其他一些东西也是现实世界的实时系统所需要的。虽然最终规格难于记忆，但是可以对环境、负载及实时应用本省施加一些约束，以简化构建实时系统。

环境约束

环境约束处理“硬实时”所隐含的响应时间上的无限制承诺。这些约束指定允许的操作温度、空气质量、电磁辐射的水平及类型。

当然，某些约束比其他一些约束更容易满足。人们都知道市面上的计算机组件通常不能在低于冰点的温度下运行，这表明了对气候控制的要求。

一位大学老朋友曾经遇到过这样的挑战，在具有相当活跃的氯化合物条件下的太空中，操作实时系统。他明智的将这个跳转转交给硬件设计同事了。实际上，同事在计算机上环绕施加大气成分的约束，这样的约束是由硬件设计者通过物理密封来实现的。

另一个大学朋友在计算机控制系统上工作，该系统在真空中使用工业强度的电弧来喷镀钛锭。有时，有时，将不会基于钛锭的路径来确定电弧的路径，而是选择更短更优的路径。正如我们在物理课程中学习到的一样，电流的突然变化会形成电磁波，电流越大、变化越大，形成超高功率的电磁波。这种情况下，形成的电磁脉冲足以导致 400 米外的 rubber ducky 天线引线产生 1/4 伏的变化。这意味着附近的导体能看到更大的电压。这包含那些组成控制喷镀过程的计算机导体。尤其是，包括计算机复位线的电压，也足以将计算机复位。这使得每一位涉及的人感到惊奇。这种情况下，面临的挑战是使用适当的硬件，包括屏蔽电缆、低速光钎网络。也就是说，不太引人注目的电子环境通常可能通过使用错误检测及纠正这样的软件代码来处理。也就是说，重要的是需要记住，虽然错误检测及纠正代码可以减少错误几率，但是通常不能将错误几率降低到零，这可能形成另一种实时响应的障碍。

也存在一些其他情形，需要最低水平的能源。例如，通过系统电源线和通过设备的能源。系统与这些设备通信，这些设备是被监控或者控制的外部系统的一部分。

一些欲在高强度的震动、冲击环境下运行的系统，例如发动机控制系统。当我们从连续震动转向间歇性冲击，将会发现更多令人头疼的需求。例如，在我大学本科学习期间，遇到一台老旧的雅典娜弹道计算机，它被设计用于即使手榴弹在其附近引爆也能持续正常工作。最后一个例子，是飞机上的黑匣子，它必须在飞机发生意外之前、之中、之后都持续运行。

当然，在面对环境冲击和碰撞时，使硬件更健壮是有可能的。巧妙的机械减震装置可以减少震动和冲击的影响，多层屏蔽可以减少低能量的电磁辐射的影响，错误纠正代码可以减少高能量辐射的影响，不同的灌封、密封技术可以减少空气质量的影响，加热、制冷系统可以应付温度的影响。极端情况下，三模冗余可以减少系统部分失效导致的整体不正确几率。但是，所有这些方法都有一个共同点：虽然它们能减少系统失败的几率，但是不能将其减低为零。

尽管这些重要的环境约束通常是通过使用更健壮的硬件来处理，但是在接下来的两节中的工作负载及应用约束通常由软件来处理。

负载约束

和人一样的道理，通过使其过载，通常可以阻止实时系统满足其最后期限的要求。例如，如果系统被过于频繁的中断，他就没有足够的 CPU 带宽来处理它的实时应用。对于这种问题，一种使用硬件的解决方案是限制中断提交给系统的速率。可能的软件解决方案包括：当中断被频繁提交给系统时，在一段时间内禁止中断，将频繁产生中断的设备进行复位，甚至完全禁止中断，转而采用轮询。

由于排队的影响，过载也可能降低响应时间，因此对于实时系统来说，过度供应 CPU 贷款并非不正常，一个运行的系统应该有 80% 的空闲时间。这种方法也适用于存储和网络设备。某些情况下，应该讲独立的存储和网络硬件保留给高优先级实时应用所使用。当然，这些硬件大部分时间都处于空闲状态，这并非不正常。因为对于实时系统来说，响应时间比吞吐量更重要。

单谈，要想保持足够低的利用率，在整个设计和实现过程汇总都需要强大的专业知识。没有什么事情与之相似，一个小小的功能就不经意间将最后期限破坏掉。

应用约束

对于某些操作来说，比其他操作更易于提供其最后响应时间。例如，对于中断和唤醒操作来说，得到其响应时间规格是很常见的，而对于文件系统卸载操作来说，则很难得到其响应时间规格。其中一个原因是，非常难于阶段文件系统卸载操作锁需要完成的工作量，因为卸载操作需要将所有内存中的数据刷新到存储设备中。

这意味着，实时应用程序必须限定其操作，这些操作必须合理提供受限的延迟。不能提供合理延迟的操作，要么将其放到非实时部分中去，要么将其完全放弃。

也可能对应用的非实时部分进行约束。例如，非实时应用是否可以合法使用实时应用的 CPU？在应用个实时部分预期非常繁忙期间，是否允许非实时部分全速运行？最后，应用实时部分允许将非实时应用的吞吐量降低到多少？

现实世界的实时规格

正如前面章节所见，现实世界的实时规格需要包装环境约束，负载及应用本身的约束。此外，应用的实时部分允许使用的操作，必然受限于硬件及软件实现方面的约束。

对于每一个这样的操作，这些约束包括最大响应时间(也可能包含一个最小响应时间)，以及满足响应时间的几率。100% 的几率表示相应的操作必须提供硬实时服务。

某些情况下，响应时间以及满足响应时间的几率，都十分依赖于操作参数。例如，在本地局域网中的网络操作很有可能在 100ms 内完成，这好于穿越大陆的广域网上的网络操作。更进一步来说，在铜制电缆和光纤网络上的网络操作，更有可能不需要耗时的重传操作就能完成，而相同的操作，在有损 WIFI 网络之上，则更有可能错误严格的最后期限。类似的可以预期，从固态硬盘 SSD 读取数据，将比从老式 USB 连接的旋转硬盘读取更快完成。

某些实时应用贯穿操作的不同阶段。例如，一个控制胶合板的实时系统，它从旋转的原木上剥离木材薄片。这样的系统必须：将原木装载到车床；将原木固定在车床上，以便将原木中最大的柱面暴露给刀片；开始旋转原木；持续的改变刀具位置，以将原木切割为木板；将残留下来的、太小而不能切割的原木移除；同时，等待下一根原木。5 个阶段的每一步，都有自身的最后期限和环境约束，例如，第 4 步的最后期限远比第 6 步严格，其最后期限是毫秒级而不是秒级。因此，希望低优先级任务在第 6 阶段运行，而不要在第 4 阶段运行。也就是说，应当小心选择硬件、驱动和软件装置，这些选择将被要求支持第 4 步更严格的要求。

每种阶段区别对待的方法，其关键优势是，延迟额度可以被细分，这样应用的不同部分可以被独立的开发，每一部分都有其自己的延迟额度。当然，与其他种类的额度相比，偶尔会存在一些冲突，即哪些组件应当获得多大比例的额度。并且，从另一个角度来说，与其他种类的额度相比，严格的验证工作是需要的，以确保正确聚焦与延迟，并且对于延迟方面的问题给出早期预警。成功的验证工作几乎总是包含一个好的测试集，这样的测试集对于学究来说并不总是感到满意，但是好在有助于完成相应的任务。事实上，截止 2015 年初，大多数现实世界的实时系统使用验收测试，而不是形式化证明。

也就是说，广泛使用测试条件来验证实时系统有一个确实存在的缺点，即实时软件仅仅在特定硬件上，使用特定的硬件和软件配置来进行验证。额外的硬件及配置需要额外的开销，也需要耗时的测试。也许形式验证领域将大大改进，足以改变这种状况，但是直到 2015 年初，形式验证还需要继续进行大的改进。

除了应用程序实时部分的延迟需求，也存在应用程序非实时部分的性能及扩展性需求。这些额外的需求反映出一个事实，最终的实时延迟通常都是通过降低扩展性和平均性能来实现的。

软件工程需求也是很重要的，尤其是对于大型应用程序来说，更是如此。这些大型应用程序必须被大型项目组锁开发和维护。这些工程需求往往偏重于增加模块化和故障的隔离性。

以上所述，仅仅是产品化实时系统中，最后期限及环境约束所需工作的一个大概说明。我们期望，它们能够清晰展示那些实时计算方面教科书式方法的不足。

谁需要实时计算

如果说，所有计算实际上都是实时计算，这可能会引起争议。举一个极端的例子，当在线购买生日礼物的时候，你可能在接受者生日之前礼物能够到达。甚至是前年之交的 Web 服务，也存在亚秒级的响应约束，这样的需求并没有随着时间的推移而缓解。虽然如此，专注于那些实时应用更好一点，这些实时应用的实时需求并不能由非实时系统及其应用所实现。当然，由于硬件成本的降低，以及带宽和内存的增加，实时和非实时之间的界限在持续变化，不过这样的变化并不是坏事。

实时计算用于工业控制应用，范围涵盖制造业到航空电子；科学应用，也许最引人注目的是用于大型天文望远镜上的自适应光学；军事应用，包含前面提到的航空电子；金融服务应用，其第一台挖掘出机会的计算机最有可能获得大多数最终利润。这 4 个领域以“产品探索”、“声明探索”、“死亡探索”、“金钱探索”为特征。

金融服务应用于其他三种应用之间的微秒差异在于其他的非物质特征，这意味着非计算机方面的延迟非常小。与之相对的是，其他三类应用的固有延迟使得实时响应的优势很小，甚至没有什么优势。所以金融服务应用，相对于其他实时信息处理应用来说，更面临着装备竞争，有最低延迟的应用通常能够获胜。虽然最终的延迟需求仍然可以由第 15.1.3.4 节中描述的内容来指定，但是这些需求的特殊性质，已经将金融和信息处理应用的需求变为“低延迟”，而不是实时。

不管我们到底如何称呼它，实时计算总是有实实在在的需求。

谁需要并行实时计算

还不太清楚谁真正需要并行实时计算，但是低成本多核系统的出现已经将并行实时计算推向了前沿。不幸的是，传统实时计算的数学基础均假设运行在单 CPU 系统中，很少有例外。例如，有一些现代平方计算硬件，其方式适合于实时计算周期，一些 Linux 内核黑客已经鼓励学术界进行转型，以利用其优势。

一种方法是，意识到如下事实，许多实时系统表现为生物神经系统，其相应范围包含实时反映和非实时策略与计划，如图 15.4 所示。硬实时反应运行在单 CPU 上，它从传感器读数据并控制动作。而应用的非实时策略与计划部分，则运行在余下的 CPU 上面。策略与计划活动可能包括静态分析、定期校准、用户接口、支撑链活动及其他准备活动。高计算负载准备活动的例子，请回想 15.1.3.4 节讨论的应用。当某个 CPU 正在进行剥离原木的高速实时计算时，其他 CPU 可以分析下一原木的长度及形状，以确定如何放置原木，以最大可能的获得更多数量的高品质模板。事实证明，很多应用都包含非实时及实时组件。因此这种方法通常能用于将传统实时分析与现代多核硬件相结合。

另一个不太有用的方法，是将所有其他硬件线程关闭，只保留其中一个硬件线程，这就回到了单处理器实时数学计算。不过，这种方法失去了潜在的成本和能源优势。也就是说，获得这些优势需要克服第 3 章所述的并行计算困难。而且，不但要处理一般情况，更要处理最坏的情况。

因此，实现并行实时系统可能是一个巨大的挑战。处理这些挑战的方法将在随后的章节给出。

实现并行实时系统

我们将着眼于两种类型的实时系统：事件驱动及轮询。事件驱动的实时系统有更多事件处理空闲状态，对实时事件的响应，是通过操作系统向上传递给应用的。可选的系统可以在后台运行非实时的工作负载，而不是使其处于空闲状态。轮询实时系统有一个特点，存在一个绑在 CPU 上运行的实时线程，该线程运行在一个紧凑循环中，在每一轮轮询中，线程轮询输入事件并更新输出。该循环通常完全运行在用户态，它读取并写入硬件寄存器，这些寄存器被映射到用户态应用程序的地址空间。可选的，某些应用将轮询循环放到内核中，例如，通过使用可加载内核磨矿将其放到内核中。

不管选择何种类型，用来实现实时系统的方法都依赖于最后期限。如图 15.5 所示。从图的顶部开始，如果你可以接受超过 1s 的响应时间，就可以使用脚本语言来实现实时应用。实际上，脚本语言通常是奇怪的用户，并不是我推荐一定要用这种方法。如果要求延迟大于几十毫秒，旧的 Linux 内核也可以使用，同样的，这也不是我推荐一定要用这种方法。特定的实时 Java 实现可以通过几毫秒的实时响应延迟，即使在垃圾回收器被使用时也是这样。如果仔细配置、调整并运行在实时友好的硬件中，Linux 2.6 及 3.x 内核能够提供几百微秒的实时延迟。如果小心避免垃圾回收，特定的 Java 实现可以提供低于 100ms 的实时延迟。(但是请注意，避免垃圾回收就意味着避免使用 Java 大型标准库，也就失去了 Java 的生成效率优势)。打上了 -rt 实时补丁的 Linux 内核可以提供低于 20ms 的延迟。没有内存转换的特定实时系统(RTOSes)可以提供低于 10ms 的延迟。典型的，要实现低于微秒的延迟，需要手写汇编代码，甚至需要特殊硬件。

当然，小心的配置及调节工作，需要针对所有调用路径。特别是需要考虑硬件或固件不能提供实时延迟的情况，这种情况下，想要弥补其消耗的时间，软件是无能为力的。并且，那些高性能的硬件有时会牺牲最坏情况下的表现，以获得吞吐量。实际上，在禁止中断的情况允许紧致循环，可以提供高质量随机数生成器的基础。而且，某些固件窃取时钟周期，以进行各种内置任务，在某些情况下，它们还会视图通过重新对受影响 CPU 的硬件时钟进行编程，来掩盖其踪迹。当然，在虚拟化环境中，窃取时钟周期是其期望的行为，不过人们仍然努力在虚拟化环境中实现实时响应。因此，对你的硬件和固件的实时能力进行评估，是至关重要的。存在一些组织，它们进行这种评估，包括开源自动开发实验室(OSADL)。

假设有合适的实时硬件和挂进，栈中更上一层就是操作系统，这将在下一节讨论。

实现并行实时操作系统

存在一些可用于实现实时系统的策略。其中一种方法是，将长剑非实时系统置于特定目的的实时操作系统之上，如图 15.6 所示。其中绿色的 “Linux 进程” 框表示非实时任务，这些进程运行在 Linux 内核中，而黄色的“RTOS 进程”框表示运行在 RTOS 之中的实时任务。

在 Linux 内核拥有实时能力之前，这是一种非常常见的方法，并且至今仍然在用。但是，这种方法要求应用被分割为不同的部分，其中一部分运行在 RTOS 之中，而另外的部分运行在 Linux 之中。虽然有可能使两种运行环境看起来类似，例如，通过将 RTOS 侧的 POSIX 系统调用转发给 Linux 侧的线程。这种方法还是存在一些粗糙的边界。

另外，RTOS 必须同时与硬件和内核进行交互，因此，当硬件和内核更改时，需要大量的维护工作。而且，每一个这样的 RTOS 通常都有其独有的系统调用接口和系统库集合，其生态系统和开发者都相互对立。事实上，正是这些问题，驱使将 Linux 和 RTOS 进行结合，因为这种方法允许访问 RTOS 的全实时能力，同时允许应用的非实时代码完全访问 Linux 丰富而充满活力的开源生态系统。

虽然，在 Linux 仅仅拥有最小实时能力的时候，将 Linux 内核与 RTOS 绑在一起，不失为明智而且有用的临时应对措施，这也将激励将实时能力添加到 Linux 内核中。实现这一目标的进展情况如图 15.7 所示。上面的进展展示了抢占禁止的 Linux 内核图。由于抢占被禁止的原因，它基本没有实时能力。中间的展示的一组图其中包含了抢占 Linux 主线内核，其实时能力的增加过程。最后，最下面的行展示了打上 -rt 补丁包的 Linux 内核，它拥有最大化的实时能力。来自于 -rt 补丁包的功能，已经被添加到主线分支，因此随着时间的推移，主线 Linux 内核的能力在不断增加。但是，最苛刻的实时应用仍然使用 -rt 补丁包。

如图 15.7 顶部所示的不可抢占内核以 CONFIG_PREEMPT=n 的配置进行构建，因此在 Linux 内核中的执行是不能被抢占的。这就意味着，内核的实时响应延迟由 Linux 内核中最长的代码路径所决定，这是在是有点长。不过，用户态的执行是可抢占的，因此在右上角所示的实时 Linux 进程，可以在任意时刻抢占左上角的，运行在用户态的非实时进程。

图 15.7 中部所示的可抢占内核，以 CONFIG_PREEMPT=n 的配置进行构建，这样大多数运行在 Linux 内核中的、进程级的代码可以被抢占。这当然极大改善了实时响应延迟，但是在 RCU 读端临界区、自旋锁临界区、中断处理、中断关闭代码段，以及抢占禁止代码段中，抢占仍然是禁止的。禁止抢占的部分，由图中间行中，最左边的红色框所示。可抢占 RCU 的出现，允许 RCU 读端临界区被抢占，如图中间部分所示。线程化中断处理函数的实现，允许设备中断处理被抢占，如图最右边所示。当然，在此期间，大量其他实时功能被添加，不过，在这种图中不容易将其表示出来。这将在 15.4.1.1 节讨论。

最后一个方法是简单将所有与实时任务无关的东西，都从实时任务中移除，将所有其他事务都从实时任务所需的 CPU 上面清除。在 3.10 Linux 内核中，这是通过 CONFIG_NO_HZ_FULL 配置参数来实现的。请注意，这种方法需要至少一个守护 CPU 执行后台处理，例如运行内核守护任务，这是非常重要的。当然，当在特定的、非守护 CPU 上面，如果仅仅只有一个可运行任务，那么该 CPU 上面的调度时钟中断被关闭，这移除了一个重要的干扰源和 OS 颠簸。除了少数例外情况，内核不会强制将其他非守护 CPU 下线，当在特定 CPU 上只有一个可运行任务时，这会简单的提供更好的性能。如果配置适当，可以郑重向你保证，CONFIG_NO_HZ_FULL 将提供近乎裸机系统的实时线程级性能。

当然，这有一些争议，这些方法到底是不是实时系统最好的方式。而且这些争议已经持续了相当长一段时间。一般来说，正如后面章节所讨论的那样，答案要视情况而定。15.4.1.1 节考虑事件驱动的实时系统，15.4.1.2 节考虑使用 CPU 绑定的轮序循环的实时系统。

事件驱动的实时支持

操作系统为事件确定的实时应用所提供的支持是相当广泛的。不过，本节只关注一部分内容，即时钟、线程化中断、优先级继承、可抢占 CPU、可抢占自旋锁。

很明显，定时器对于实时操作系统来说是极其重要的。毕竟，如果你不能指定某些事件在特定事件完成，又怎能在某个事件点得到其响应？即使在非实时系统中，也会产生大量定时器，因此必须高效处理它们。作为示例的用法，包括 TCP 连接重传定时器(它们几乎总是会在触发之前被中止)，定时延迟(在 sleep(1) 中，它几乎不被中断)，超时 poll 系统调用(它通常会在触发之前就被中止)。对于这些定时器，一个好的数据结构是优先级队列，对于这样的队列，其添加删除原语非常快速，并且与已经入队的定时器数量相比，其时间复杂度是 O(1)。

用于此目的的经典数据结构是日历队列，在 Linux 内核中被称为时钟轮。这个古老的数据结构也被大量用于离散时间模拟。其思想是时间时能度量的，例如，在 Linux 内核中，时间度量周期是调度时钟中断的周期。一个特定时间可以被表示为整型数，任何视图在一个非整型数时刻提交一个定时器，都将被取整到一个最接近的整数时间值。

一种简单的实现是分配一个一维数组，以时间的地界位进行索引。从原理上来说，这可以运转，但是在那些创建大量长周期超时定时器的实际系统中(例如为 TCP 会话而创建的 45 分钟保活超时定时器)，这些定时器几乎总是被中止。长周期的超过定时器对于小数组来说会导致问题，这是因为有太多时间浪费在跳过那些还没有到期的定时器上。从另一个方面来说，一个大道足以优雅的容纳大量长周期定时器的数组，会浪费很多内存，尤其是处于性能和可扩展性考虑，每个 CPU 都需要这样的数组。

解决该冲突的一个常规办法是，以多级分层的方式提供多个数组。在最底层，每一个数组元素表示一个单位时间。在第二层，每个数组元素表示 N 个单位时间，这里的 N 是每个数组的元素个数。在第三层，每一个数组元素表示 N2 个单位时间，一次类推。这种方法允许不同的数组以不同的位进行索引，如图 15.9 所示，它表示一个不太实际的、小的 8 位时钟。在此图中，每一个数组有 16 个元素，因此时钟低 4 位(0xf)对低阶(最右边)数组进行索引，接下来 4 位(0x1)对上一级进行索引。这样，我们有两个数组，每一个数组有 16 个元素，共计 32 个元素。远小于单一数组所需要的 256 的元素。

这个方法对于基于流量的系统来说运行的非常好。每一个特定时间操作的时间复杂度是小于常数的 O(1)，每个元素最多访问 m+1 次，其中 m 是层数。

不过，时钟轮对于实时系统来说并不好，有两个原因。第一个原因是：需要在定时器精度和定时器开销之间进行权衡：定时器处理仅仅每毫秒才发生一次，这在很多(但非全部)工作环境是可以接受的。但是这也意味着不能保证定时器低于 1ms 的精度；从另一个角度来说，每 10us 进行一次定时器处理，对于绝大部分(但非全部)环境来说，这提供了可以接受的定时精度，但是这种情况下，处理定时器是如此频繁，以至于不能有时间去做任何其他事情。

第二个原因是需要将定时器从上级级联移动到下级。再次参照 15.9，我们将看到，在上层数组(最左边)的元素 1x 必须向下移动到更低(最右边)数组中，这样才能在它们到期后被调用。不幸的是，可能有大量的超时定时器等待移动，尤其是有较多层数时。这种移动操作的效率，对于面向吞吐量的系统来说是没有问题的，但是在实时系统中，可能导致有问题的延迟。

当然，实时系统可以简单宣策一个不同的数据结构，例如某种形式的堆或者树，对于插入或删除这样的数据维护操作来说，这样会失去 O(1) 时间复杂度，而变成 O(log n)。对于特定目的的 RTOS 来说，这可能是一个不错的选择。对于像 Linux 这样的通用操作系统来说，其效率不高。Linux 这样的通用操作系统通常支持非常大量的定时器。

Linux 内核的 -rt 补丁所做的选择，是将两种定时器进行区分处理，一种是调度延后活动的定时器，一种是对类似于 TCP 报文丢失这样的低可能性粗无偶进行调度的定时器。其中一个关键点是：错误处理通常并不是对时间特别敏感，因此时钟轮的毫秒级精度就足够了。另一个关键点是：错误处理超定时器通常会在早期就被中止，这通常是发生在它们被级联移动之前。最后一点是：与执行事件的定时器相比，系统通常拥有更多的执行错误处理的超时定时器。对于定时事件来说，O(log n) 的数据结构能够提供可接受的性能。

简而言之，Linux 内核的 -rt 补丁将时钟轮用于超时错误处理，将树这样的数据结构用于定时器事件，为所需要的服务类型提供不同的定时器类型。

线程化中断用于处理那些显著降低实时延迟的事件源，即长时间运行的中断处理程序，如图 15.12 所示。这些延迟对那些在单次中断后，发送大量事件的设备来说尤其验证，这意味着中断处理程序将运行一个超长的时间周期以处理这些事情。更糟糕的是，在中断处理程序正在运行时，设备可能产生新的事件，这样的总段处理程序可能会无限期运行，因为无限期的降低实时响应。

处理这个问题的方法是，使用如图 15.13 所示的线程化中断。中断处理程序运行在可抢占 IRQ 线程上下文，它运行在可配置的优先级。设备中断处理程序仅仅运行一小段时间，其运行时间仅仅可以使 IRQ 线程知道新事件的产生。如图所示，线程化中断可以极大的提升实时延迟，部分原因是运行在 IRQ 线程上下文的中断处理程序可以被高优先级实时线程抢占。

但是天下没有免费的午餐，线程化中断有一些缺点。其中一个缺点是增加了中断延迟。中断处理程序并不会立即运行，其执行被延后到 IRQ 线程中。当然，除非设备在实时应用关键路径执行时产生中断，否则也不会存在问题。

另一个缺点是写得不好的高优先级实时代码可能会中断处理程序饿死，例如，会阻止网络代码运行，导致调试问题非常困难。因此，开发者在编写高优先级实时代码时必须非常小心。这被称为蜘蛛侠原则：能力越大、责任越大。

优先级继承用于处理优先级反转。优先级反转可能是这样产生的，在处理其他事情时，锁被可抢占中断处理程序获得。假定一个低优先级线程获得某个锁，但是他被一组中优先级线程所抢占，每个 CPU 都至少有一个这样的中优先级线程。如果一个中断产生，那么一个高优先级 IRQ 线程将抢占一个中优先级线程，但是直到它决定火红的被低优先级所获得的锁，才会发生优先级反转。不幸的是，低优先级线程直到它开始运行才能释放锁，而中优先级线程会阻止它这样做。这样一来，直到某个中优先级线程释放它的 CPU 之后，高优先级 IRQ 线程才能获得锁。简而言之，中优先级线程间接阻塞了高优先级 IRQ 线程，这是一种典型的优先级反转。

注意，这样的优先级饭庄在非线程化中断中不会发生，这是因为低优先级线程必须在持有锁的时候，禁止中断，这也阻止了中优先级线程抢占它。

在优先级继承方案中，视图获得锁的高优先级线程将其优先级传递给获得锁的低优先级线程，直到锁被释放。这组织了长时间的优先级反转。

当然，优先级继承有其限制。比如，如果能够设计你的应用，已完全避免优先级反转，将很有肯能获得稍微好一些的延迟。这不足为怪，因为优先级继承在最坏的情况下，增加了两次上下文切换。也就是说，优先级继承可以将无限期的延迟转换为有限增加的延迟，并且在许多应用中，优先级继承的软件工程优势可能超过其他延迟成本。

另一个限制是，它仅仅处理特定操作系统环境中，基于所的优先级反转。它所能处理的一种优先级反转情况是，一个高优先级线程等待网络 Socket 消息，而该消息被低优先级进程所写入，但是低优先级线程被一组绑定在 CPU 上的中优先级进程所抢占。

最后一个限制包含读写锁。假设我们有非常多的低优先级线程吗，也许有数千个，每个读线程持有一个特定的读写锁。如果所有这些线程都被中优先级线程抢占，而每 CPU 都有至少一个这样的中优先级线程。最终，假设一个高优先级线层被唤醒并试图获得相同读写锁的锁。我们要如何去大量提升持有这些读写锁的线程优先级，这本身更没有什么问题，但是在高优先级线程获得写锁之前，他可能要等待很长一段时间。

有不少针对这种读写锁优先级反转难题的解决方案。

在同一时刻，仅仅允许一个读写锁有一个读请求(这是被 Linux 内核的 -rt 补丁所采用的传统方法)。
在同一时刻，对于某个特定读写锁，仅仅允许 N 个读请求。其中 N 是 CPU 个数。
在同一时刻，对于某个特定读写锁，仅仅允许 N 个读请求。其中 N 是由开发者指定的某个数值。Linux 内核的 -rt 补丁将在某个事件采取这种方法的几率还是比较大的。
当读写锁被正在运行的低优先级线程获得读锁时，防止高优先级线层获得其写锁(这是优先级上限协议的一个变种)。

某些情况下，可以通过将读写锁转换为 RCU，来避免读写锁优先级反转。

有时，可抢占 RCU 可被用作读写锁的替代品。在它可以被使用的地方，它允许读者和写者并发运行，这防止了低优先级的读者对高优先级的写者加以任何类型的优先级反转。但是，要使其有用，能够抢占长时间允许的 RCU 读端临界区是有必要的。否则，长时间运行的 RCU 读端临界区将导致过长的实时延迟。

因此，可抢占 RCU 实现被添加到 Linux 内核中。通过在当前读端临界区中，跟踪所有可抢占任务的链表这种方式，该实现就不必分别跟踪每一个任务的状态。以下情况下，允许终止一个优雅周期：所有 CPU 都已经完成所有读端临界区，这些临界区在当前优雅周期之前已经有效；在这些已经存在的临界区运行期间，被抢占的所有任务都已经从链表移除。这种实现的简单版本如 15.15 所示。__rcu_read_lock 函数位于第 1~5 行，而 __rcu_read_unlock 函数位于第 7~22 行。

__rcu_read_lock 函数第 3 行递增一个每任务计数，该计数是嵌套调用 __rcu_read_lock 的计数，第 4 行放置编译器将 RCU 读端临界区后面的代码与 __rcu_read_lock 之前的代码之间进行乱序。

__rcu_read_unlock 函数第 11 行检查嵌套计数是否为 1，换句话说，检查当前是否为 __rcu_read_unlock 嵌套调用的最外一层。如果不是，第 12 行递减该计数，并将控制流程返回到调用者。否则，这是 __rcu_read_unlock 的最外层，这需要通过第 14~20 行对终止临界区进行处理。

第 14 行防止编译器将临界区中的代码与构成 rcu_read_unlock 函数的代码进行乱序。第 15 行设置嵌套计数为一个大的负数，以防止与包含在中断处理程序中的读端临界区产生破坏性竞争。第 16 行防止编译器将这一行的赋值与第 17 行对特殊处理的检查进行乱序。如果第 17 行确定需要进行特殊处理，就在第 18 行调用 rcu_read_unlock_special 进行特殊处理。

有几种情况需要进行特殊处理，但是我们将关注其中一种情况，即当 RCU 读端临界区被抢占时的处理。这种情况下，任务必须将自己从链表中移除，当它第一次在 RCU 读端临界区中被抢占时，它被添加到这个链表中。不过，请注意这些链表被锁保护很重要。这意味着 rcu_read_unlock 不再是有锁的。不过，最高优先级的线程不会被抢占，因此，对那些最高优先级线程来说，rcu_read_unlock 将不会视图去获取任何锁。另外，如果小心实现，锁可以被用来同步实时软件。

无论是否需要特殊处理，第 19 行防止编译器将第 17 行的检查与第 20 行进行乱序，第 20 行将嵌套计数置 0。

在大量读的数据结构中，对于大量读者的情况下，这个可抢占 RCU 实现能到达实时响应，而不会有优先级提升方法所固有的延迟。

由于在 Linux 内核中，持续周期长的基于自旋锁的临界区的原因，可抢占自旋锁是 -rt 补丁集的重要组成部分。这个功能仍然没有合入主线，虽然从概念上来说，用睡眠锁代替自旋锁是一个简单的方案，但是已经证实这是有争议的。不过，对于那些想要实现低于 10us 延迟的实时任务来说，它是非常有必要的。

当然了，有其他不少数量的 Linux 内核组件，他们对于实现显示世界的延迟非常重要，例如最近的最终期限调度策略。不过，本节中的列表，已经可以让你对 -rt 补丁集所增加的 Linux 内核功能，找到好的感觉。

轮询实时支持

乍看之下，使用轮询可能会避免所有可能的操作系统的干扰问题。毕竟，如果一个特定的 CPU 从不进入内核，内核就完全不在我们的视线之内。要将内核排除在外的传统方法，最简单的是不使用内核，许多实时应用确实是运行在裸机之上，特别是那些运行在 8 位微控制器上的应用程序。

人们可能希望，在现代操作系统上，简单通过在特定 CPU 上运行一个 CPU 绑定的用户态线程，避免所有干扰，以获得裸机应用的性能。虽然事实上更复杂一些，但是这已经能够实现了，这是通过 NO_HZ_FULL 实现的。该实现由 Frederic Weisbcher 引入，并已经被接收进 Linux 内核 3.10 版本。不过，需要小心对这种环境进行适当的设置，因为对一些 OS 抖动来源进行控制是必要的。随后的讨论包含对不同 OS 抖动源的控制，包括设备中断、内核线程和守护线程序、调度器实时限制、定时器、非实时设备驱动、内核中的全局同步、调度时钟中断、页面异常，最后，还包括非实时硬件及固件。

中断是大量 OS 抖动源中很突出的一种。不幸的是，大多数情况下，中断是绝对需要的，以实现系统与外部世界的通信。解决 OS 抖动与外部世界通信之间的冲突，其中一个方法是保留少量守护 CPU，并强制将所有中断移动到这些 CPU 中。Linux 源码树中的文件 Documentation/IRQ-affinity.txt 描述了如何将设备中断绑定到特定 CPU、直到 2015 年初，解决该问题的方法如下所示：

echo 0f > /proc/irq/44/smp_affinity

该命令将第 44 号中断限制到 CPU 0~3。请注意，需要对调度时钟中断进行特殊处理，这将在随后章节进行讨论。

第二个 OS 抖动源是来自于内核线程和守护线程。个别的内核线程，例如 RCU 优雅周期内核线程，可以通过使用 taskset 命令、sched_setaffinity 系统调用或者 cgroups，来将其强制绑定到任意目标 CPU。

每 CPU 线程通常更具有挑战性，有时它限制了硬件配置及负载均衡布局。要防止来自于这些内核线程的 OS 干扰，要么不将特定类型的硬件应用到实时系统中，其所有中断和 IO 初始化均运行在守护 CPU 中，这种情况下，特定内核 Kconfig 或者启动参数被选择，从而将其事务从工作 CPU 中移除；要么工作 CPU 干脆不受内核管理。针对内核线程的建议可以在 Linux 内核源码 Documentation 目录 kernek-per-CPU-kthreads.txt 中找到。

在 Linux 内核中，运行在实时优先级的 CPU 绑定线程受到的第三个 OS 抖动是调度器本身。这是一个故意为之的调试空能，设计用于确保重要的非实时任务每秒至少分配到 30ms 的 CPU 时间，甚至是在你的实时应用存在死循环 BUG 时也是如此。不过，当你正在运行一个轮询实时应用时，需要禁止这个调度功能。可以用如下命令完成此项工作。

echo -1 > /proc/sys/kernel/sched_rt_runtime_us

当然，你必须以 Root 身份运行以执行以上命令，并且需要小心考虑蜘蛛侠原理。一种将风险最小化的方法，是将中断和内核线程、守护线程从所有运行 CPU 绑定线程的 CPU 中卸载，正如前面几段中所述那样。另外，应当认真阅读 Documentation/scheduler 目录中的材料。sched-rt-group.txt 中的材料尤为重要，当你正在使用 cgroups 实时功能时更是如此，这个功能通过 CONFIG_RT_GROUP_SCHED Kconfig 参数打开，这种情况下，你也应当阅读 Documentation/cgroups 目录下的材料。

第四个 OS 抖动来自于定时器。绝大多数情况下，将某个 CPU 配置于内核之外，将防止定时器被调度到该 CPU 上。一个重要的例外是再生定时器，即一个特定定时器处理函数触发同样的定时器在随后某个事件内再次发生。如果由于某种原因，这样的定时器在某个 CPU 上已经启动，该定时器被在该 CPU 上持续周期性运行，反复造成 OS 抖动。一个粗暴但是有效的移除再生定时器的方法，是使用 CPU 热插拔将所有运行 CPU 绑定实时应用线程的 CPU 卸载，并重新将这些 CPU 上线，然后启动你的实时应用。

第五个 OS 抖动来自于驱动设备，这些驱动不是用于实时用途。举一个老的典型例子，在 2005 年，VGA 驱动会在禁止中断的情况下，通过将帧缓冲置 0，以清除屏幕，这将导致数十毫秒的 OS 抖动。一种避免设备驱动引入 OS 抖动的方法，是小心选择那些已经在实时系统中大量使用的设备，由于已被大量使用，其实时故障已经被修复。另一个方法是将设备中断和使用该设备的代码限制到特定守护 CPU 中。第三个方法是测试设备支持实时负载的能力，并修复其实时 BUG。

第六个 OS 抖动源来自于一些内核全系统同步算法，也许最引人注目的是全局 TLB 刷新算法。这可以通过避免内存 unmap 操作来避免，特别是要避免在内核中的 unmap 操作。直到 2015 年年初，避免内核 unmap 操作的方法是避免卸载内核模块。

第七个 OS 抖动源来自于调度时钟中断及 RCU 回调。这些可以通过打开 NO_HZ_FULL Kconfig 参数来构建内核，然后 nohz_full= 参数启动内核来加以避免，该参数指定运行实时线程的工作 CPU 列表。例如，nohz_full=2-7 将保留 CPU 2~7 作为工作 CPU，余下 CPU 0~1 作为守护 CPU。只要在每一个工作 CPU 上，没有超过一个可运行任务，那么工作 CPU 将不会产生调度时钟中断。并且每个工作 CPU 的 RCU 回调将在守护 CPU 上被调用。由于其上仅仅只有一个可运行任务，因此那些抑制了调度时钟的 CPU 被称为处于自适应节拍模式。

作为 nohz_full= 启动参数的另一种可选方法，你可以用 NO_HZ_FULL_ALL 来构建内核，它将保留 CPU0 作为守护 CPU，其他所有 CPU 作为工作 CPU。无论哪种方式，重要的是确保保留足够多的守护 CPU，以处理其他所负担的系统其他部分的守护负载，这需要小心的进行评估和调整。

当然，天下没有免费的午餐，NO_HZ_FULL 也不例外。正如前面所提示的那样，NO_HZ_FULL 使得内核/用户之间的切换消耗更大，这是由于需要增加进程统计，也需要将切换事件通知给内核子系统(如 RCU)。开启 POSIX CPU 定时器的进程，其上的 CPU 也被阻止进入“自适应节拍模式”。额外的限制、权衡、配置建议可以在 Documentation/timers/NO_HZ.txt 中找到。

第八个 OS 抖动源是页面异常。由于绝大部分 Linux 实现使用 MMU 进行内存保护，运行在这些系统中的实时应用需要遵从页面异常的影响。使用 mlock 和 mlockall 系统调用来将应用页面锁进内存，以避免主要的页面异常。当然，蜘蛛侠原理仍然适用，因为锁住太多内存可能会阻止其他工作顺利完成。

很不幸，第九个 OS 抖动源是硬件和固件。因此使用那些涉及用于实时用途的系统是重要的。OSADL 运行产期的系统测试，参考其网站(http://osadl.org)定会有所收获。

1 cd /sys/kernel/debug/tracing 
2 echo 1 > max_graph_depth 
3 echo function_graph > current_tracer 
4 # run workload 
5 cat per_cpu/cpuN/trace

不幸的是，OS 抖动源列表觉不完整，因为它会随着每个新版本的内核而变化。这使得能够跟踪额外的 OS 抖动源是有必要的。加入 CPU N 运行一个 CPU 绑定的用户态线程。上面的命令片段将给出所有该 CPU 进入内核的时间列表。当然，第 5 行的 N 必须被替换为所要求的 CPU 的编号，第 2 行中 1 可以增加，以显式内核中函数调用的级别。跟踪结果有助于跟踪 OS 抖动源。

正如你所见到那样，在像 Linux 这样的通用 OS 上，运行 CPU 绑定实时线程来获得裸机性能，需要对细节进行耐心细致的关注。自动化将是有用的，某些自动化也得到了应用，但是鉴于其用户相对较少，预期其出现将相对缓慢。不过，在通用操作系统上获得几乎裸机系统的能力，将有望简化某些类型的实时系统建设。

实现并行实时应用

开发实时应用是一个宽泛的话题，本节仅仅涉及某些方面。

实时组件

在所有工程领域，健壮的组件集对于生产率和可靠性来说是比不可少的。本节不是完整的实时软件组件分类——这样的分类需要一整本书，这是一个可用组件类型的简要概述。

查看实时软件组件的一个很自然的地方，是实现无等待同步的算法，实际上，无锁算法对于实时计算也非常重要。不过，无等待同步仅仅保证在有限时间内推进处理过程，并且实时计算需要算法更严格的保证在有限时间内将处理过程向前推进。毕竟，一个世纪也是有限的时间，但是在你的最终期限是以毫秒计算时，它将无意义。

不过，有一些重要的无等待算法，以提供限期响应时间。包含原子测试和设置、原子交换、原子读加、基于唤醒数组的单生成者/单消费者 FIFO 队列，以及不少每线程分区算法。另外，最近的研究已经证实，在随机公平调度及不考虑错误终止故障的情况下，无锁算法确保提供相同的延迟。这意味着，无锁栈及队列将适用于实时用途。

在实践中，锁通常用于实时应用，尽管理论上讲并不完全如此。不过，在严格的约束中，基于所的算法也存在有限延迟。这些约束包括以下几点：

公平调度器。在固定优先级调度器的通常情况下，有限延迟通常提供给最高有限级的线程。
充足的带宽以支持负载。支持这个约束的一个实现原则也许是“正常运行，在所有 CPU 上至少存在 50% 的空闲时间”，或者更正式的说“提供的负载足够低，以允许工作负载在所有时刻都能够被调度”。
没有错误终止故障。
获得、切换、释放延迟均有限期的 FIFO 锁原语。同样，通常情况下的锁原语是带有优先级的 FIFO，有限延迟仅仅是提供给最高优先级的线程。
某些防止无限优先级反转的方法。本章前面部分提到的优先级上限及优先级继承就足够了。
有限的嵌套锁获取。我们可以有无限数量的锁，但是在同一个时刻，只要一个特定线程绝不获得超过一定数量的锁就行了。
有限数量的线程。与前面的约束相结合，这个约束意味着等待特定锁的线程数量是有限的。
消耗在任何特定临界区上的有限时间。对于有限的等待特定锁的线程数量，以及有限的临界区长度，其等待时间也是有限度的。

这个结果打开用于实时软件的算法及数据结构的宝藏，它也验证尝试的实时实践。

当然，仔细的、简单的应用设计也是十分重要的。世上最好的实时组件，也不能弥补那些缺乏深思熟虑的设计。对于并行实时应用来说，同步开销明显是设计的关键组件。

轮询应用

许多实时应用由绑定 CPU 的单个循环构成，该循环读取传感器数据，计算控制规则，并输出控制。如果提供传感器数据及控制输出的硬件寄存器被映射到应用地址空间，那么该循环就完全不可以使用系统调用。但是请当心蜘蛛侠原则，更多的权利伴随着更多的责任，在这种情况下，其责任是指避免通过对硬件寄存器的不恰当引用而破坏硬件。

这种方式通常运行在裸机上面，这没有操作系统带来的优势(或者说也没有其带来的干扰)。不过，需要增加硬件能力及增加自动化水平来提升软件功能，如用户界面、日志及报告，所有这些都可以受益于操作系统。

在裸机上运行，同时仍然想要获得通用擦做系统的所有特征和功能，其中一个方法是使用 Linux 内核的 NO_HZ_FULL 功能，该功能在 15.4.1.2 节中描述。该支持首先在 Linux 内核 3.10 版本中可用。

流应用程序

一种流行的大数据实时应用获得多种输入源的输入，内部处理它，并输出警告和摘要。这些流应用通常是高度并发的，并发的处理不同信息源。

实现流应用程序的一种方法是使用循环数组缓冲 FIFO，来联结不同的处理步骤。每一个这样的 FIFO，仅仅有一个线程向其放入数据，并有一个(大概是不同的线程)线程从其中取出数据。扇入扇出点使用线程而不是数据结构，因此，如果需要合并几个 FIFO 的输出，一个独立的线程将从一个 FIFO 中输入数据，并将它输出到另外一个 FIFO，该线程是唯一的处理者。类似的，如果一个特定 FIFO 的输出需要被分拆，一个单独的线程将从这个 FIFO 进行获取输入，并且将其输出到多个 FIFO 中。

该规则看起来严格，但是它允许在线程间的通信有最小的同步开销，当试图满足严格的延迟约束时，最下的同步开销是重要的。当每一步中的处理量小，因而同步开销与数据处理相比，同步负载所占比例更大时，这显得尤其重要。

不同的线程可能是 CPU 绑定的，这时，15.4.2.2 节中的建议是适用的。另一方面，如果不同线程阻塞等待其输入 FIFO 的数据，那么 15.4.2.4 节中的建议是适用的。

事件驱动应用

对于事件驱动应用，我们将展示一个奇特的例子，将燃料注入中型工业发动机。在正常的操作条件下，该发动机要求一个特定的时间点，以一度的间隔将燃料注入到顶端正中。我们假设 1500-RPM 的旋转速度，这样就是每秒 25 转，或者大约每秒 9000 个旋转刻度，转换为没刻度即为 111ms。因此，我们需要在大约 100ms 内调度燃料注入。

假设事件等待被用于初始化燃料注入，但是如果你正在构造一个发动机，我希望你提供一个旋转传感器。我们需要测试时间等待功能，可能使用图 15.17 所示的测试程序。不幸的是，如果运行这个程序，我们将遇到不可接受的时钟抖动，即使在 -rt 内核中也是如此。

一个问题是，POSIX CLOCK_REALTIME 并不是为了实时应用，很奇怪吧。相反的，它所表示的“实时”是与进程或者线程所消耗的 CPU 总时间相对。对于实时用途，应当使用 CLOCK_MONOTOMIC。但是，即使做了这样的改变，结果仍然是不可接受的。

另一个问题是，线程必须通过使用 sched_setscheduler 系统调用来提供实时优先级。但是即使有了这个改变还是不够的，因为我们仍然能遇到缺页异常。我们也必须使用 mlockall 系统调用来锁住应用的内存，以防止缺页异常。应用的所有这些改变，结果可能最终是可接受的。

在其他情况下，可能需要进一步调整。可能需要将时间关键的线程绑定到他们自己的 CPU 中，并且可能需要将中断从这些 CPU 中移除。也需要谨慎选择硬件和驱动，并且可能需要谨慎选择内核配置。

从这个例子可以看出，实时计算真不是省油的灯。

RCU 的角色

假设你正在编写一个并行实时应用，该应用需要访问可能会随着温度、湿度和气压的变化而变化的数据。对该应用的实时响应约束相当严格，因此不允许自旋或阻塞，这样就排除掉了锁；也不允许使用重试循环，这样一来排除掉了顺序锁和危险指针。幸运的是，温度和压力通常是受控制的，因此默认的编码数据集通常是足够的。

但是，温度、湿度和压力偶尔会偏离默认值较远，这时有必要提供替换默认值的数据。由于温度、湿度和压力是逐渐变化的，虽然需要在几分钟内完成，但提供更新的值并非紧急事项。该应用将使用一个名为 cur_cal 的全局指针，该指针通常引用 default_cal，这是一个静态分配并初始化的结构，并包含命名为 a/b/c 的默认校准值。否则，cur_dal 将指向提供当前校准值的动态分配结构。

上面的代码清单展示了如何使用 RCU 来解决这个问题。查找逻辑是确定的，如第 9~15 行中的 calc_control，并能符合实时要求。更新逻辑则比较复杂，如第 17~35 行的 update_cal 所示。

该示例展示了 RCU 如何为实时应用提供确定的读端数据结构访问。

实时 vs. 快速

在实时与快速计算之间进行选择可能是一件困难的事情。因为实时系统通常造成非实时系统的吞吐量损失，在不需要使用的时候，使用实时计算会带来问题。另一方面，在需要实时计算时，使用错误也会带来问题。

基于经验法则，使用以下 4 个问题来助你选择：

平均的长期吞吐量是唯一目标吗？
是否允许重负载降低响应时间？
是否有高内存压力，排除使用 mlockall 系统调用？
应用的基本工作项是否需要超过 100ms 才能完成？

如果每一个问题的答案都是“是”，则应当选择“快速”而不是“实时”，否则，则可以选择“实时”。请明智选择，并且如果你选择了“实时”，请确保硬件、固件、操作系统都恩能够胜任。

Feedback

Was this page helpful?

Glad to hear it! Please tell us how we can improve.

Sorry to hear that. Please tell us how we can improve.