论文总字数：26194字

摘 要

实时系统因其能够保证任务实时完成的特性，在航空、航天、核工业等对任务需要精密控制的关键产业中具有关键意义。随着科技的发展与普及，以5G终端、智能家居等为代表的现代计算机技术产品已经走进了千家万户。为了满足安全性和用户体验等需要，商用计算机系统和嵌入式系统的实时性需求乃大势所趋。而目前主流的计算机系统和嵌入式系统，包括Windows、Linux等，都是非实时操作系统，不能满足用户日益增长的实时性需求。虽然Linux内核自带实时任务优先级，但因其缺乏实时任务调度机制和调度算法的支持，只能在一定条件下勉强实现软实时任务调度。因此，对Linux内核中的调度算法进行改进，使其实现软实时任务调度，有着可行性的基础和重要的实际意义。

因此，本文基于现有实时应用中的一种改进版完全公平调度算法，在Linux内核上进行了系统实现，并验证了它对软实时任务调度的有效性。本文主要研究工作如下：(1)对Linux-4.4.4源码中的完全公平调度（Completely Fair Scheduling, CFS）算法相关代码进行了详细解读，结合算法原理理解了相关代码含义与作用；(2)根据改进版算法原理对源码进行了相应的修改，以完成实现软实时任务调度的目标，并通过实验验证其有效性。

实验结果表明，改进后的完全公平调度算法能够在相对公平的基础上，保证关键任务的优先抢占执行，很好地完成了实现软实时任务调度的预期目标。本实现在很大程度上加深了本人对Linux系统的认识和理解，为以后的深入研究学习打下了良好的基础。

关键词：软实时任务调度；Linux内核；CFS改造；实现

Abstract

Because of the characteristics of the ability to guarantee the on-time completion of its tasks, real-time systems are of crucial significance to the essential industries which requires to have its tasks in the most accurate control, such as aerospace and nuclear industry. With the technology developing and popularizing, Modern computer technology products charactered by 5G terminals and smart home have been prevalent. In order to satisfy the needs of more than security and user experience, the real-time property support to commercial computer and embedded systems is the general trend. However, the current prevailing computer and embedded systems including Windows and Linux are not real-time operating systems, which can not satisfy the users’ ever-growing demand to real-time property. Though the current Linux kernel does support real-time task priority, it can only support soft real-time task scheduling narrowly under certain circumstances, as a result of lacking the real-time task scheduling mechanism and algorithms. Thus it is feasible and of great practical importance to improve the existing scheduling algorithms in the Linux kernel to implement the soft real-time task scheduling.

In this principle, this paper systematically implements the improved completely fair scheduling algorithm from a recent real-time application, as well as confirming its efficiency to schedule the soft real-time tasks. This paper mainly works in the following two aspects. The first one is thoroughly reading the relating sections in the Linux-4.4.4 source code, and understanding their meanings and effects in accordance with its principle. The other one is making the corresponding modification according to the modified version with the aiming at the implementation of soft real-time task scheduling, and then checking its availability in experiment.

The result of the experiment shows that the modified completely fair scheduling algorithm guarantees the preemptive executing privilege of the special tasks on the foundation of relative fairness, reaching the prospective target of implementing the soft real-time task scheduling in the Linux kernel. The implementing work deepens my acknowledge and comprehension to the Linux operating system in a large degree, grounding me for the further study.

Key Words: soft real-time task scheduling; Linux kernel; CFS modification; implementation

目 录

摘 要 I

Abstract II

目 录 I

第1章 绪论 1

1.1 研究背景及意义 1

1.2 国内外研究现状 1

1.3 本文研究内容及路线 3

1.4 本文组织结构 3

第2章 CFS算法 4

2.1 算法简介 4

2.2 算法原理 4

2.3 数据结构 5

2.4 调度相关过程 6

2.4.1 进程创建 7

2.4.2 进程唤醒 7

2.4.3 进程调度 8

2.4.4 时钟周期中断 8

2.5 本章小结 9

第3章 改进的CFS算法 10

3.1 算法原理 10

3.2 数据结构 10

3.3 系统调用 11

3.4 核心模块 12

3.5 本章小结 15

第4章 算法实现 16

4.1 实验步骤 16

4.1.1 下载、解压源码 16

4.1.2 修改源码 16

4.1.3 配置编译项 18

4.1.4 执行编译 18

4.1.5 生成启动项 20

4.1.6 重启测试 21

4.2 调试记录 21

4.3 实验结果 28

4.4 本章小结 29

第5章 总结与展望 30

5.1 本文总结 30

5.2 研究展望 30

参考文献 31

致 谢 32

第1章 绪论

1.1 研究背景及意义

近年来，随着计算机硬件技术和软件技术的不断更迭发展，各种新概念层出不穷，例如云计算、物联网、5G等，“万物互联”已经迈向了“万物智联”。作为联系计算机硬件和软件，为用户有效利用计算机提供良好运行环境支持的系统软件——操作系统^[1]，更是一直以来国内外专家、学者的研究热点。虽然它的庞大和复杂让许多人望之却步，但这激起了更多的人探索它的奥秘的兴趣和热情。

由于很多嵌入式系统对实时性有很高的要求，例如自动驾驶、航空航天等，微小的时延可能会造成很严重的后果。所以，硬实时系统已被广泛研究，并显现了它们在任何条件下都能够有效满足所有任务的截止期的优点。然而，在实际应用的系统中，许多组件可以容许超出截止期限些许，而不会影响它们功能上的正确性，只要时延量像预期一样可控、可限。这个观测经验促进了软实时系统的发展，以提高资源利用效率。^[2]

相比于微软的Windows操作系统，Linux操作系统因为开源而受到了更多研究爱好者的青睐。因Linux内核默认的调度策略并不能很好地支持实时任务调度，所以在用户日益增长的实时性需求的趋势下，目前的Linux系统调度机制渐显落伍，需要进行改造升级才能适应社会需要。

1.2 国内外研究现状

研究与改造Linux内核一直以来都是国内外专家学者的研究热点。涂碧波、李胜利等人提出了一种增强Linux实时性的技术，为克服Linux构建实时系统的两个固有障碍——Linux核心的不可切换性及中断信号的延迟性，提出了两个针对性的改善措施——降低Linux内核的延迟，及防止中断信号的延迟。^[3]

邢群科、郝红卫等人基于一个x86体系结构的PC机，设计实现了在实时调度领域占有重要地位的两个调度算法——速率单调（RM）算法和最早截止期限优先（EDF）算法，并在不同的工作负载下，以任务截止期错失率为衡量指标，对两种算法进行了性能分析和比较。^[4]

李孝杰、何先波等人对不确定环境下的嵌入式实时系统中的EDF调度算法进行了持续的研究和分析，对EDF算法进行了一次又一次改进，以改善经典实时调度算法按任务的确定执行时间进行调度会浪费各种资源的问题。^{[5, 6]}

在软实时系统及算法研究方面，国外学者的研究成果颇丰。Hyunjong Choi、Hyoseung Kim等人提出了一种名为“作业类级固定优先级调度”的算法。该算法不同于经典的任务级固定优先级调度，它采用了任务中作业的面向需求的分类法，以减少对其他任务造成的最坏情况下的时间干扰。在此方法下，每个作业都与一个“作业类”相关联，该“作业类”由之前满足截止期限的作业数来决定。它能够充分利用软实时系统的软约束，以提高系统资源利用效率。^[2]

Youcheng Sun、Marco Di Natale等人提出了一种基于自由偏移的单处理器系统的一般性软实时可调度性分析框架。而之前的软实时可调度性分析研究为了绕开临界时刻定理（critical instant theorem）不适用于软实时系统的限制，只能将初始偏移限定为一个已知的固定值。而这个限定条件不光很严苛，更有局限性的是，所有固定偏移的系统分析对时间漂移和错误很敏感，而这些时间漂移和错误在实际系统中很难避免。该框架克服了上述限制，极大地推动了软实时可调度性分析研究工作的发展。^[7]

请支付后下载全文，论文总字数：26194字

相关图片展示：