基于多处理器的实时调度算法研究

《基于多处理器的实时调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章绪论第一章绪论§1.1研究背景和研究意义实时系统的产生和发展动力来源于现实世界的实际需求，现实世界的许多应用都与时间因素相关，如工业过程控制、武器防御系统、自动化导航、机械制造、机场调度、核电站控制系统等。这些系统的共同特点是系统中的任务不但执行结果要正确，而且它们必须在一定的时间内完成。实时系统不仅要保证任务之间的逻辑关系的正确性，而且要在指定的时间内响应各种事件。与非实时系统相比，实时系统的一个显著特点是它们试图同时实现计算机在逻辑上和时间上的正确性。为了达到系统的实时性和可预测性要求，在多处理器系统中就必须求助于实时调度

2、理论，即实时调度技术和任务可调度性分析方法，研究的范围包括任务使用资源策略和机制，以及提供判断系统性能是否可预测的方法和手段。比如什么时候调度任务以及在哪个处理器上运行等。实时调度算法是保证实时系统的实时性和可靠性[1]的重要手段之一。因此，实时调度理论成为实时系统研究的核心。由此可见，实时系统有以下特点：1.对外部事件的响应必须在一定时间内完成。例如，人们在自动取款机取款，计算机须在几秒钟内捕获卡片上的数据，如果未获取数据，该数据就会丢失。同样，要求的各种输出也必须在一定时间内完成。事实上，数据的获取、处理、已处理数据的输出，都需

3、在特定的时间内完成。这一时间的总和叫做系统的反应时间，其范围一般从几毫秒到几秒，缩短反应时间是设计实时系统的关键。2.必须满足一定的峰值负荷要求。一个实时系统的负荷可能是很不均匀的，有时负荷重，有时负荷轻，甚至有可能大部分时间没有被充分利用，但整个系统必须满足一定的峰值负荷要求。3.与实时系统相关的另一个重要问题是，由于输入数据由系统本身捕获，因此，该数据只有在系统中才有效，而且只能通过系统来访问。也就是说，在故障发生时，不仅失去由系统执行的功能，而且也会失去有关的数据，使系统不可能恢复工作，因此实时系统可靠性至关重要。实时任务调度

4、算法是实时系统设计和实现的关键。它的好坏，直接影响到系统的吞吐量，系统的响应时间，甚至是任务能否得以成功调度。由于实时系统的侧重点不同，实时调度亦有多种分类方式。以下是一些常见的实时调度分类[2−5]：1.按对实时性能要求的程度，实时任务可以分为硬实时和软实时两类。对于硬实时和软实时的定义并不统一，目前比较常用的有2种：从任务的时间结果上考虑，硬实时有很强的可确定性要求，具有明确的时间约束，任务必须在其截止期限内执行完毕，在某个限定时刻之前不能完成任务将导致整个应用失败，软实时也对时间敏感，但偶尔发生的不能满足严格实时要求的情况是允

5、许的，不过是不受欢迎的。从任务完成的价值函数上来考虑，硬实时任务在超过截止期后，任务的价值函数将大幅下降，甚至跌到负值，软实时任务在超过截止期后，任务的价值函数，随任务的延迟逐渐减小。–1–万方数据第一章绪论1.根据任务是在一个或多个处理器上运行，分为单处理器实时调度和多处理器实时调度。多处理器实时调度又可分为局部调度和全局调度。单处理器调度主要需要考虑是，在何时把系统唯一的处理器分配给哪个任务。而多处理器不仅要考虑任务在单个处理器上的运行情况，还要考虑把任务分配到哪一个处理器上运行，即处理器分配问题。2.根据调度顺序产生的时机和方

6、式可分为静态调度和动态调度。静态调度是在任务集运行之前就产生一个静态的调度表，在运行时总是按照调度表决定从就绪任务队列中选择哪个任务来运行，这类调度算法假设系统中实时任务的特性是已知的，如最坏情况执行时间、截止期、执行次序等。它的可调度性分析是脱机地进行。这类调度算法适合于问题需求确定，并且运行中不会有较大变化的情况，如简单的工业过程控制。静态调度算法的优点是运行开销小，可预测性强。但是它的灵活性较差，不适合动态变化的，或不可预测环境下的调度。动态调度算法是在任务运行期间才决定选择哪个就绪任务来运行，它所根据的是目前已处于就绪态的各

7、任务的相关属性，以此来决定当前的调度序列。这类算法能够对变化的环境做出反应，因此，这类调度算法比较灵活，适合于任务不断生成，并且在任务生成之前，其特性并不清楚的动态实时系统，如机器人控制系统。但是，动态调度算法的运行开销一般较前者大。3.根据任务的作业到达时刻规律的不同，可分为周期任务调度、突发任务调度和非周期任务调度。对于周期任务，其相邻两次作业到达时刻之间的间隔是一个固定的常数即周期。突发任务是指相邻两次作业到达时刻之间的间隔不固定，但有一个下限值。非周期任务的作业到达时刻没有规律。4.根据调度方法是否具有自适应功能，可分为自适

8、应调度和非自适应调度。由于实时任务的调度是直接影响多处理器实时系统性能的核心因素，因此研究多处理器实时系统的任务调度策略是十分有必要和有意义的。§1.1.1研究现状基于不同的硬件结构，实时调度可分为单处理器实时调度和多处理器实时调度。