精华内容
下载资源
问答
  • 实时调度

    2020-03-25 12:57:32
    实时调度 实时调度的基本条件 实时系统必须提供必要的调度信息 运行时间 到达之间 完成截止时间/开始截止时间 资源要求 优先级 实时系统的处理能力足够强(在有限的周期内,能够计算完成用户需要的任务) ...

    实时调度

    实时调度的基本条件
    • 实时系统必须提供必要的调度信息
      • 运行时间
      • 到达之间
      • 完成截止时间/开始截止时间
      • 资源要求
      • 优先级
    • 实时系统的处理能力足够强(在有限的周期内,能够计算完成用户需要的任务)
      • 计算机处理能力是一个周期内完成3个任务,但是分配了四个任务,一定完成不了
    • 允许采用抢占式调度方式
    • 具有快速的切换机制(为抢断提供条件)
      • 对中断的快速响应
      • 快速的任务分配能力

    实时调度算法的分类

    根据实时任务的性质
    • 硬实时调度算法:所有任务确定时间内必须完成
    • 软时间调度算法:大部分任务再确定时间内完成
    按照调度方式
    非抢占式调度算法(不允许剥夺正在执行的进程)
    • 时间片转轮调度算法
      • 响应时间:秒级
      • 同分时操作系统,给所有的任务分配时间片,按时间片轮流执行
    • 非抢占式优先权调度算法
      • 响应时间:百毫秒级
      • 为所有进程安排优先权,优先权高的先执行,允许后来的高优先权的程序插队,先执行
    抢占式调度算法(允许剥夺正在执行的进程)
    • 基于时钟中断的抢占的优先权调度算法
      • 响应时间:几十毫秒级
      • 每到时钟中断的时候,高优先级的程序可以剥夺正在占用CPU执行的程序的使用权。
      • 相当于在非抢占式优先权中,允许进程在时钟中断的时候进行抢占
    • 立即抢占优先权调度
      • 响应时间:几毫秒或者几百微妙
      • 一旦有优先级高于当前任务的任务出现,立即中断正在执行的任务,切换至当前优先级最高的任务

    常见的调度算法——最早截止时间优先(EDF)

    1. 基本思想:截止时间越早,优先级越高
    2. 截止时间:开始截止时间和完成截止时间
    3. 调度方式:抢占式调度算法
    4. 例子

    非抢占式

    在这里插入图片描述

    • 任务按照1,2,3,4的顺序到达,但是开始截止时间是按照1,3,4,2的顺序,所以真正执行的顺序是1,3,4,2

    抢占式
    在这里插入图片描述

    • 任务到达的顺序是A,B,C,D,E,开始截止时间的顺序是B,C,E,D,A,再结合任务的执行时间发现在A执行完毕的情况,B一定超时,系统报错,所以允许B抢占A的执行资源。
    常见的实时调度算法——最低松弛度优先(LLF)
    1. 基本思想:任务松弛度越低,优先级越高
    2. 任务松弛度:必须完成的时间 - 本身运行的时间 - 当前时间(简而言之,松弛时间就是允许在拖延的时间)
    3. 调度方式:抢占式调度算法
    4. 例子
      在这里插入图片描述
      在这里插入图片描述

    注意:最低松弛度的计算时间点:任务开始截止时间和任务运行完成时间

    展开全文
  • 3.4实时调度

    2020-11-29 11:00:26
    实时调度(一种特殊的系统调度) 实现实时调度的基本条件 提供必要的信息 开始/完成截止时间 就绪时间 资源要求 处理时间 优先级 系统处理能力强 采用抢占式调度机制 具有快速切换机制 实时调度算法的分类 ...

    实时调度(一种特殊的系统调度)

    在这里插入图片描述

    实现实时调度的基本条件

    1. 提供必要的信息
    • 开始/完成截止时间
    • 就绪时间
    • 资源要求
    • 处理时间
    • 优先级
    1. 系统处理能力强
    2. 采用抢占式调度机制
    3. 具有快速切换机制

    实时调度算法的分类

    • 根据任务性质不同可分为硬实时调度和软实时调度

    • 根据调度方式的不同可分为抢占式和非抢占式
      在这里插入图片描述

    • 根据调度时间的不同分为静态和动态调度算法

    • 在多处理机情况下可分为集中式和分布式调度算法

    常用的两种实时调度算法

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 3.4实时调度 3.4.1实现实时调度的基本条件 1、提供必要的信息

    3.4实时调度

    3.4.1实现实时调度的基本条件

    1、提供必要的信息

    • 就绪时间:该任务成为就绪状态的时间。
    • 开始截止时间或完成截止时间:只需知道一个。
    • 处理时间:从开始执行到完成所需时间。
    • 资源要求:任务执行时所需的一组资源。
    • 优先级:根据任务性质赋予不同优先级。

    2、系统处理能力强

    假如系统中有m个周期性的硬实时任务,处理时间为Ci,周期时间表示为Pi;

    • 则单机系统中必须满足条件:
      ∑( Ci / Pi )≤1
    • 多处理机系统:
      ∑( Ci / Pi )≤N

    3、采用抢占式调度机制

    • 硬实时任务: 广泛采用抢占机制。
    • 小的实时系统: 可采用非抢占调度机制(简化调度程序和对任务调度时所花费的系统开销)。

    4、具有快速切换机制

    • 对外部中断的快速响应能力。
    • 快速的任务分派能力。

    3.4.2实时调度算法的分类

    可以按照不同方式对实时调度算法加以分类:

    • 按照实时任务性质:
      • 针对硬实时任务的调度算法
      • 针对软实时任务的调度算法
    • 按照调度方式:
      • 非抢占式
      • 抢占式

    1、非抢占调度算法

    • 非抢占式轮转调度算法:适用于要求不太严格的场合!
      在这里插入图片描述

    • 非抢占式优先调度算法:适用于要求较为严格的场合!
      在这里插入图片描述

    2、抢占式调度算法

    • 基于时钟的抢占式优先权调度算法:

      • 某高优先级任务到达后并不立即抢占,而等下一个时钟中断时抢占。在这里插入图片描述
    • 立即抢占的优先权调度算法:

      • 一旦出现外部中断,只要当前任务未处于临界区,就立即抢占处理机。在这里插入图片描述

    3.4.3最早截至时间优先算法EDF(Earliest Deadline First)

    • 该算法是根据任务的截止时间确定任务的优先级;
    • 具有最早截止时间的任务排在队列的前面。

    1.非抢占式调度方式用于非周期性实时任务

    在这里插入图片描述

    2.抢占式用于周期性实时任务

    • 假如在一个实时系统中,有两个周期性实时任务A和B;
      • 任务A要求每20ms执行一次,执行时间为10ms;
      • 任务B要求每50ms执行一次,执行时间为25ms。
      • 计算是否可调度
        10/20+25/50=1, 可调度!
    • 采用最早截至时间优先调度过程
      在这里插入图片描述
      与固定优先级算法对比:
      在这里插入图片描述

    3.4.4最低松弛度优先LLF(Least Laxity First)算法

    • 最短空闲时间优先;
    • 用松弛度来表示任务紧急程度;
    • 松弛度=完成截止时间-运行时间-当前时间;
      • 例如,任务A在200ms时必须完成,本身运行时间100ms,则必须在100ms之前调度执行,A任务的紧急(松弛)程度为100ms;
        任务B在400ms时必须完成,需运行150ms,其松弛程度为250ms。
    • 该算法主要用于可抢占调度方式中。
    • 假如在一个实时系统中,有两个周期性实时任务A,B,任务A要求每20ms执行一次,执行时间为10ms;任务B要求每50ms执行一次,执行时间为25ms;
      由此可得知AB任务每次必须完成的时间分别为A1、A2、A3…和B1、B2、B3…如下图:
      在这里插入图片描述
      采用最低松弛度优先
      在这里插入图片描述

    3.4.5优先级倒置

    1.优先级倒置的形成

    • ★ “优先级倒置”的现象
      高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。
    • ★例子
      • 有三个完全独立的进程P1、P2和P3,P1的优先级最高,P2次之,P3最低。
      • P1和P3通过共享的一个临界资源进行交互。下面是一段代码:
        P1: …P(mutex); CS-1; V(mutex);…
        P2: … program2…;
        P3: …P(mutex); CS-3; V(mutex) ;…
        在这里插入图片描述

    2.优先级倒置的解决方法

    一种简单的解决方法-中断禁止:

    • 假如进程P3在进入临界区后,P3所占用的处理机就不允许被抢占。
    • 如果系统中的临界区都较短且不多,该方法是可行的。
    • 反之,如果P3临界区非常长,则高优先级进程P1仍会等待很长的时间,其效果是无法令人满意的。
    • 还要防止P3在临界区出现死循环。

    一个比较实用的解决方法-优先级继承

    • 当高优先级进程P1要进入临界区使用临界资源R时,如果已有一个低优先级进程P3正在使用该资源;
    • 此时一方面P1被阻塞,另一方面由P3继承P1的优先级,并一直保持到P3退出临界区
      在这里插入图片描述
    展开全文
  • 实时调度算法

    千次阅读 2018-09-29 15:32:35
    实时调度算法的分类 根据实时任务性质分类 硬实时调度算法:即任务必须在确定的时间内完成 软实时调度算法:即大部分任务必须在确定的时间内完成 根据调度方式分类 关于抢占式和非抢占式的定义这里不讲解 非抢占...

    必要的名词解释

    开始截止时间:某个任务必须在某个时间之前开始执行

    实时调度算法的分类

    根据实时任务性质分类
    • 硬实时调度算法:即任务必须在确定的时间内完成
    • 软实时调度算法:即大部分任务必须在确定的时间内完成
    根据调度方式分类
    关于抢占式和非抢占式的定义这里不讲解
    
    • 非抢占式
    • 抢占式

    最早截止时间优先算法

    EDF(Earliest DeadLine First)
    这个算法的含义就是,谁完成任务的截止时间早,谁就先执行。好比我们在排队买票的时
    候,经常出现有人说,不好意思,我赶时间让我先。
    

    EDF在非抢占式调度方式的应用

    我们通过一个例子来讲解(t 是时间轴)

    在这里插入图片描述

    1. 首先任务 1 先到达并且执行任务
    2. 在任务 1 执行的过程中,任务 2,3 到达。也就是任务 1 执行完时,有任务 2,3 等待被执行
    3. 比较任务 2,3 的截止时间,也就是最上面的开始截止时间,可得到,任务 3 先执行
    4. 同样的分析方式,可以得出任务 4 先于任务 2 执行
    5. 所以执行顺序是 1,3,4,2

    EDF在抢占式调度方式的应用

    我们通过一个例子来讲解

    在这里插入图片描述

    首先,该图的二,三行是为了说明常用的优先级调度不能适用于实时系统,这里不细说,可以不用管,我们直接观察第一行和最后一行。

    1. 在 t = 0 时,A1 和 B1 同时到达。此时比较二者的截止时间(最后期限),可以看出 A1 的截止时间早,所以 A1 先运行。

    2. A1 执行 10ms 后因为 A2 还没有到,所以不存在比较,直接切换 B1 执行。

    3. 当 B1 执行了 10ms 后,A2 到达,比较二者的截止时间,A2 先于 B1。所以A2 抢占处理机,B1 中断。

    4. 此后的调度方式按照上面的分析即可完成

      EDF 在抢占式和非抢占式的区别就是,抢占式就是,当新任务 A 来到的时
      候,如果 A 的截止时间比正在执行的任务 B 的截止时间提前,那么就中断 
      B ,抢夺处理机控制权,转而运行 A。
      

    最低松弛度优先算法

    LLF(Least Laxity First)
    这个算法的思想就是,根据任务的紧急程度判断。任务越紧急,松弛度就越低,优先级就越高
    

    松弛度 = 必须完成的时间 - 本身运行时间 - 当前时间

    先举一个下例子。比如此时时间轴为 0ms,任务 A 和 B 同时到达,需要确定先执行哪个任务。

    任务 A 需要在 200ms 这个时刻(或之前)完成,而 A 本身要运行 100ms。所以 A 的松弛度就是 200 - 100 - 0 = 100ms。

    此时还有一个任务 B ,必须在 400ms 时刻(或者之前)完成,本身需要运行 150ms,所以松弛度为 400 - 150 - 0 = 250

    所以,松弛度低(任务越紧急)先执行。

    下面给出一个测试,如果大家掌握了上面的思想就可以轻松完成
    

    假如一个实时系统中有两个周期性实时任务 A 和 B,任务 A 每 20ms 运行一次,一次运行 10ms 。

    任务 B 每 50ms 运行一次,一次运行 25ms。

    通过观察下图,画出 A 和 B 在 LLF 算法下的调度时间轴图。

    在这里插入图片描述

    下面给出答案
    在这里插入图片描述

    完!

    展开全文
  • 实时系统与实时调度

    2020-12-22 00:47:45
    2.11 实时系统与实时调度 一些概念 计算结果存在时效性,过期无意义,如新闻 实时系统:系统可及时(即使)响应外部请求,在规定时间内完成对该事件的处理,并控制所有实时任务协调一致运行 实时任务:具有及时性...
  • 3.4 实时调度

    2019-06-07 17:20:19
    1.实现实时调度的基本条件 (1)提供必要的信息(2)系统处理能力强(3)采用抢占式调度机制(4)具有快速切换机制 2.实时调度算法的分类 (1)非抢占式轮转调度算法(时间片轮转) (2)非抢占式优先调度算法 ...
  • 多处理器与实时调度多处理器调度实时调度 多处理器调度 实时调度
  • 实时调度算法研究

    2013-05-02 10:38:19
    实时调度算法研究
  • 3.3 实时调度

    2018-11-20 21:16:00
    1.实时系统:指系统能够在限定的响应时间内提供所需水平的服务。 指计算的正确性不仅取决于程序的逻辑正确性...为了实现实时调度,系统应向调度程序提供有关任务的下述信息: 就绪时间:该任务成为就绪状态的时间。 ...
  • 实时调度

    2016-07-17 18:11:27
    2.7 实时调度类 按照POSIX标准的强制要求,除了“普通”进程之外,Linux还支持两种实时调度类。调度器结构使得实时进程可以平滑地集成到内核中,而无须修改合兴调度器,这显然是调度类带到的好处。 rt_task宏...
  • 实时调度是为了完成实时处理任务而分配计算机处理器的调度方法。 实时处理任务要求计算机在用户允许的时限范围内给出计算机响应信号。实时处理任务可分为  硬实时任务(hardrea[—timetask)和软实时任务(softreal—...
  • 实时调度器 建造 cmake -B BUILD . cmake --build BUILD
  • 操作系统 实时调度

    2020-12-19 12:51:37
    为保证系统能正常工作,实时调度必须能满足实时任务对截止时间的要求。 实现实时调度应具备一定的条件。 实现实时调度的基本条件 提供必要的信息: 就绪时间,是指某任务成为就绪状态的起始时间,在周期任务的...
  • 智能制造系统采用大量先进的信息技术,为车间实时调度提供技术基础.各类信息技术在生产制造过程中的广泛应用使得制造系统积累了大量与生产调度相关的数据,因此,通过利用历史生产调度数据和智能装备收集到的实时生产...
  • Linux实时调度机制研究Linux实时调度机制研究Linux实时调度机制研究
  • 针对多处理器实时调度中的EDZL调度算法,利用多任务之间的相互干涉关系,找出与多处理器之间的时间约束条件,提出了一种可调度性判定的方法,并对给出的判定方法进行了证明。给出了一种判定多处理器实时EDZL可调度性...
  • 常用实时调度算法

    千次阅读 2018-06-13 12:20:51
    实现实时调度的基本条件提供必要的调度信息(就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级)系统处理能力强。在实时系统中,若处理机的处理能力不够强,则有可能因处理机忙不过来而致使某些...
  • 4、实时调度算法 linux内核中提供了两种实时调度策略:SCHED_FIFO和SCHED_RR,其中RR是带有时间片的FIFO。这两种调度算法实现的都是静态优先级。内核不为实时进程计算动态优先级。这能保证给定优先级别的实时进程...
  • 在此基础上,通过优化实时调度框架的方式,确定调度剪枝规则,并对系统数据的调度分支界定流程进行完善,实现新型电力系统能量备用实时调度模型的搭建。分析对比实验结果可知,与传统模型相比,应用云平台下型电力...
  • 针对网络实时调度问题,提出实时调度系统体系结构与任务模型。综合考虑任务截止期、执行时间及间隔时间等属性,定义任务迫切度;根据不同任务的重要程度,提出基于服务质量的任务松紧度。通过迫切度和松紧度对优先级...
  • linux实时调度策略

    千次阅读 2018-09-17 20:48:41
    SCHED_FIFIO与SCHED_RR两种实时调度策略, FIFO:只能被高优先级的实时进程抢占 RR:耗尽事先分配的时间后就不能再运行了。轮流调度其他同一优先级的实时进程。   软实时:内核调度进程尽力使进程在它的限定时间...
  • 基于BS结构的库群实时调度系统,廖胜利,李志福,水电站群实时发电调度作为衔接水电日前计划与电站AGC调度的中间环节,通过对水库水位的不断校核,调整日前计划过程,对可能产生的
  • 文章目录实时调度一、实时系统与实时任务1.实时系统2.实时任务二、实时操作系统的特征补充:(中断)三、实时调度算法分类1.非抢占式调度算法2.抢占式调度算法四、实时调度常用算法1.最早截止时间EDF算法2.最低松弛...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,025
精华内容 2,810
关键字:

实时调度