选择语言:

www.4808.com

您的位置:www.4808.com > www.4808.com >

使命 A 只好 期待使命 C 施行完毕

时间:2019-11-27 点击:

  动态优先级安排算法的特点和实现_工学_高档教育_教育专区。摘要:本文从及时操做系统的安排功能入手,简单引见了及时安排算法的分类和品种,并次要会商动态优先级安排算法的特点和实现。接下来本文引见了两类动态优先级安排算法:截止时间优先安排算法和最短空闲时间优先安排算法的定义及实现体例。然后将静态安排取动态安排进行比力,凸起动态优先级安排的特点,同时指出其可能导致的优先级反转、死锁等不良后果。然后具体引见了优先级反转的定义以及处理该问题的两种方案:采用优先级承继

  动态优先级安排算法的特点和实现 摘要:本文从及时操做系统的安排功能入手,简单引见了及时安排算法的分类和品种, 并次要会商动态优先级安排算法的特点和实现。 接下来本文引见了两类动态优先级安排算法: 截止时间优先安排算法和最短空闲时间优先安排算法的定义及实现体例。 然后将静态安排取 动态安排进行比力,凸起动态优先级安排的特点,同时指出其可能导致的优先级反转、死锁 等不良后果。 然后具体引见了优先级反转的定义以及处理该问题的两种方案: 采用优先级继 承和谈取采用优先级天花板和谈。 环节词:嵌入式系统 动态优先级 安排算法 优先级反转 正在嵌入式的及时操做系统中, 安排是一个很是主要的功能, 用来确定多使命下使命 施行的挨次和正在获得 CPU 资本后可以或许施行的时间长度。 操做系统通过一个安排法式 (Scheduler) 来实现安排功能。 安排法式以函数的形式存正在, 用来实现操做系统的安排算法。安排法式本身并不是一个使命,而是一个函数挪用,可正在内 核的各个部门进行挪用。安排法式是影响系统机能(如吞吐率、延迟时间等)的主要部门。 正在设想安排法式是、时,凡是要分析考虑如下要素: ●CPU 的利用率(CUP utilization); ●输入/输出设备的吞吐率; ●响应时间(responsive time); ●公允性; ●截止时间。 这些要素之间具有必然的冲突性。好比可通过让更多的使命处于停当形态来提高 CPU 的利用率,但这明显会降低系统的响应时间。因而,安排法式的设想需要优先考虑最主要的 需求,然后正在各类要素之间进行折中处置。 能够把一个安排算法(Scheduling Algorithms)描述为是正在一个特按时辰用来确定将要 运转的使命的一组法则。从 1973 年 Liu 和 Layland 起头关于及时安排算法的研究工做以来 (1973 年,Liu 和 Layland 颁发了 一篇名为“Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”的论文),接踵呈现了很多安排算法和方式。 对于大量的及时安排方式而言,存正在着以下几类次要的划分方式: ●离线(off-line)和正在线(on-line)安排; ●抢占(preemptive)和非抢占(non-preemptive)安排; 1 ●静态(static)和动态(dynamic)安排; ●最佳(optimal)和试探性(heuristic)安排。 以下次要会商动态优先级安排算法的特点和实现。 一、动态优先级安排算法的定义 优先级驱动策略指按照使命的优先级的凹凸确定使命的施行挨次。 按照使命优先级简直 定机会,安排算法分为静态安排和动态安排两类。正在静态安排算法中,所有使命的优先级正在 设想时就确定下来了,且正在运转过程中不会发生变化(如 RMS)。正在动态安排算法中,任 务的优先级则正在运转过程中确定,并可能不竭地发生变化(如 EDF)。静态安排算法合用于 可以或许完全把握系统中所有使命及当时间束缚(如截止时间、运转时间、优先挨次和运转过程 中的达到时间)特征的环境。静态安排比力简单,可是缺乏矫捷性,晦气于系统扩展;动态 安排有脚够的矫捷性来处置变化的系统环境,可是需要耗损更多的系统资本。 正在动态安排中, 使命的优先级可按照需要进行改变, 也可能跟着时间按照必然的策略自 动发生变化。 二、动态优先级安排算法的分类 1、截止时间优先安排算法 RMS 安排算法(Rate-Monotonic Scheduling algorithm,比率枯燥安排算法)的 CPU 利用 率比力低,正在使命比力多的环境下,可安排上限为 68%。Liu 和 Layland 又提出了一种采用动 态安排的、 具有更高 CPU 利用率的安排算法——截止时间优先安排算法 EDF Earliest Deadline ( First)。正在 EDF 中,使命的优先级按照使命的截止时间来确定。使命的绝对截止时间越近, 使命的优先级越高;使命的绝对截止时间越远,使命的优先级越低。当有新的使命处于停当 形态时,使命的优先级就有可能需要进行调整。同 RMS 一样,Liu 和 Layland 对 EDF 算法的 阐发也是正在一系列假设的根本长进行的。正在 Liu 和 Layland 的阐发中,EDF 不要求使命为周 期使命,其他假设前提取 RMS 不异。 例如正在系统中有 3 个历程需要施行,别离为 P1、P2、P3,其施行需破费的时间各为 1、 2、1l,而施行周期为 3、5、4,正在时间单元 4 时,由于 P1 的施行时限为 6,P2 的施行时限 为 10,P3 的施行时限为 8,所以 P1 的优先级最高,历程切换到 P1:正在时间单元 6 时,因 为 P1 的施行时限为 9,P2 的施行时限为 10,P3 的施行时限为 12,所以 P1 的优先级最高, 历程又再次切换到 P1,而非 P2:正在时间单元 7 时,由于 P1 的施行时限为 12,P2 的施行时 限为 10, 的施行时限为 12, P3 所以 P2 的优先级最高, 历程切换到 P2。 后续流程以此类推。 2 EDF 算法是最优的单处置器动态安排算法 其可安排上限为 100%。 EDF 安排算法下, 算法是最优的单处置器动态安排算法, 正在 对于给定的一组使命,使命可安排的充实需要前提为 使命可安排的充实需要前提为 Ci T ∑ -i n i=1 ≤1 对于给定的一组使命, ,若是 EDF 不克不及满脚其安排性要求,则没有其他安排算法可以或许满 则没有其他安排算法可以或许满 脚这组使命的安排性要求。 。 同基于固定优先级的静态安排性比,采用基于动态优先级安排的 EDF 算法的显著长处 同基于固定优先级的静态安排性比 正在于 EDF 的可安排上限为 100% 100%,使 CPU 的计较能力可以或许被充实操纵起来。 。EDF 也存正在不脚 之处,正在及时系统中不容易实现 正在及时系统中不容易实现,而且,同 RMS 比拟,EDF 具有更大的安排开销 具有更大的安排开销,需要正在 系统运转的过程中动态地计较确定使命的优先级。 系统运转的过程中动态地计较确定使命的优先级 别的, 正在系统呈现姑且过载的环境下, 正在系统呈现姑且过载的环境下 EDF 算法不克不及确定哪个使命的截止时间会得不到满脚。 算法不克不及确定哪个使命的截止时间会得不到满脚 为此, 和 Layland 提出了一种夹杂的调 Liu 度算法,即大大都使命都采用 RMS 进行安排,只要少量使命采用 EDF 安排算法 即大大都使命都采用 安排算法。虽然夹杂 的安排算法不克不及达到 100%的 CUP 利用率,大确实分析了 EDF 和 RMS 安排算法的长处 的 安排算法的长处,使 这个安排比力容易实现。 2、最短空闲时间优先安排算法 最短空闲时间优先安排算法 正在最短空闲时间优先安排算法(least-laxity-first scheduling)中,使命的优先级按照使命 正在最短空闲时间优先安排算法 使命的优先级按照使命 的空闲时间前进履态分派。 使命的空闲时间越短, 使命的空闲时间越短 使命的优先级越高; 使命的空闲时间越长, 使命的空闲时间越长 使命的优先级越低。使命的空闲时间可通过下式来暗示 使命的空闲时间可通过下式来暗示,即 使命的空闲时间=使命的绝对截止时间 使命的绝对截止时间-当前时间-使命的残剩时间 四、静态安排取动态安排之间的比力 静态安排取动态安排之间的比力 动态安排的呈现时为了确保低优先级使命也能被安排。 动态安排的呈现时为了确保低优先级使命也能被安排 这种公允性对于所有使命都划一 主要的系统比力合适,对于需要绝对可预测性的系同一般晦气用动态安排。这些系统中,正在 对于需要绝对可预测性的系同一般晦气用动态安排。 呈现姑且过载的环境下, 要求安排算法可以或许选择最告急的使命施行, 要求安排算法可以或许选择最告急的使命施行 而放弃那些不太告急的 使命。 而动态安排的优先级只反映了使命的时间特征, 而动态安排的优先级只反映了使命的时间特征 没有把使命的告急程度表现到优先级 中去。 动态安排的安排价格凡是都比静态安排高, 动态安排的安排价格凡是都比静态安排高 此次要是因为正在每一个安排点都需要对使命 3 的优先级进行从头计较,而静态安排中使命的优先级则一直连结不变,不需要进行计较。 然而,要留意,动态优先级安排算法的会导致优先级反转、死锁,以至系统解体。 五、优先级反转 优先级反转是指因为资本合作, 低优先级的使命正在施行, 而高优先级的使命正在期待的现 象。当具有分歧优先级的使命中存正在彼此依赖关系时,就可能发生优先级反转。 例如当系统内低优先级的使命 C 占用着高优先级使命 A 要利用的资本时,使命 A 只好 期待使命 C 施行完毕,并该资本后才能被安排施行。这时,若是有中优先级使命 B 进 入停当,了使命 C 的 CPU 利用权,使得系统只要先让 B 运转完毕,且使命 C 从头运转 竣事并资本后,使命 A 才能运转。如许,使命 A 和 B 的优先级发生了。正在这种情 况下, 高优先级的使命的优先级现实上曾经降到了低优先级的程度, 从而发生优先级反转现 象,中优先级的使命抢占低优先级的使命,时间可能不确定,因而称为优先级反转。 雷同地, 当一个较高优先级的使命请求一个较低优先级使命拥有的资本时, 较低优先级 的使命却锁住了该资本, 即便较高优先级的使命停当, 它也必需期待低优先级的使命资 源后才能继续运转。正在这种环境下,低优先级的使命占用资本的时间是已知的,因而称为有 界优先级反转。有界优先级反转实例当优先级发生反转时,某些使命的施行时间削减,同时 其他使命的施行时间耽误,导致使命错失时限,进而惹起时序反常。 优先级反转是由分歧优先级使命间的资本同步惹起的, 正在现实使用中是不成避免的, 但 能够利用资本节制和谈将其降到最低限度。 处理优先级反转问题的常用方式次要有两种: 采 用优先级承继和谈取采用优先级天花板和谈。 1.优先级承继和谈 为防止发生优先级的反转, 多使命内核应对应动态地改变使命的优先级。 若是一个使命 拥有被高优先级使命所请求的资本, 那么, 该使命的优先级会临时提拔到取被该使命堵塞的 所有使命中优先级最高的使命同样的优先级程度, 当该使命退出临界区时, 再恢复到最后的 优先级,这种方式称为优先级承继。目前,良多贸易内核都具有优先级承继的功能。优先级 承继和谈法则如下表所示。 优先级承继和谈法则 和谈法则号 1 2 3 描述 若是资本 R 正在利用,则使命 T 被堵塞;若是资本 R 是空闲的,则资本 R 被分 配给使命 T 当较高优先级的使命 T,请求资本 R 时,使命 T 的优先级被提拔到 T’的优 先级品级 当使命 T 资本 R 后,前往到先前的优先级 优先级承继的例子如下:使命 A 是高优先级的,使命 C 是低优先级的。使命 C 起首获 4 得共享资本 S,而使命 A 也请求该资本,优先级承继和谈要求使命 C 以使命 A 的优先级施行 临界区,如许,使命 C 正在施行临界区时,其优先级比它本身的优先级高,这时,中优先级的 使命 B 不克不及抢占使命 C 了,当使命 C 退出临界区时,又恢复到本来的优先级,使使命 A 仍 为最高优先级的使命,如许,使命 A 便不会被中优先级的使命堵塞了。 正在优先级承继和谈中, 使命 T 进入临界区而堵塞了更高优先级的使命, 则使命 T 将承继 被堵塞使命的优先级,曲到使命 T 退出临界区。优先级承继和谈是动态的,一个不相关的较 高优先级使命仍可进行使命抢占, 这是基于优先级可抢占安排模式的赋性, 而且使命优先级 正在反转期间,被提拔优先级的使命的优先级能够继续被提拔,即优先级承继具有传送性。虽 然正在优先级承继和谈中,使命的堵塞时问是有界的,但可能呈现堵塞链,从而会加长堵塞时 间,以至形成死锁。 2.天花板优先级和谈 优先级承继和谈具有死锁和堵塞链问题,而天花板优先级(CeilingPriority)和谈能够处理 这些问题。若是每个使命的优先级是已知的,对于给定资本(或节制该资本拜候的信号量), 其优先级天花板是所有可能需要该资本的使命中最高的优先级。 例如, 资本 R 被三个使命 A, B 和 C 所需要,使命 A 具有优先级 5,使命 B 具有优先级 7,使命 C 具有优先级 10,那么资 源 R 的优先级天花板为 10。 当一个使命 T 请求资本 R 时,其遵照的天花板优先级和谈如下表所示。 天花板优先级和谈法则 和谈法则号 1 2 描述 若是资本 R 正在利用,则使命 T 被堵塞 若是资本 R 是空闲的,则资本 R 被分派给使命 T。若是资本 R 的优先级天花 板比使命 T 的优先级高,则使命 T 的优先级被提拔到资本 R 的优先级天花板 品级。正在肆意给按时间,使命 T 的施行优先级等于所有它拥有的资本中最高 优先级天花板 当具有最高优先级天花板的资本被时,将使命 T 所拥有资本的最高优先 级天花板分派给它 当具有最高优先级天花板的资本被时,将使命 T 所拥有资本的最高优先 级天花板分派给它 3 4 利用天花板优先级和谈时, 一旦某使命获得该资本或暂无其他较高优先级的使命合作同 样资本时, 则此使命便承继该资本的优先级天花板, 即便没有其他较高优先级的使命合作同 样的资本, 也要承继该资本的优先级天花板。 这意味着拜候某临界资本的所有使命的临界区 具有同样的天花板品级。 3.优先级天花板和谈 5 优先级天花板是制拜候临界资本的信号量的优先级天花板(简单的说,就是某个临 界资本的优先级天花板),信号量的优先级天花板是所有利用该信号量的使命中具有最高优 先级的使命的优先级。正在肆意时辰,一个运转系统的当前优先级天花板(priority ceiling)是此 时所有正正在利用的资本中具有最高优先级的优先级天花板。 例如, 系统中有 3 个资本正正在使 用,资本 R1 的优先级天花板为 4,资本 R2 的优先级天花板为 6,资本 R3 的优先级天花板 为 9,则系统当前的优先级天花板为 9。 正在优先级天花板和谈下,一个请求使命只能够被一个使命堵塞,大奖网登录不会发生传送堵塞(即 发生堵塞链),也不会发锁。当一个使命 T 请求资本 R 时,其拜候节制和谈法则如下表 所示。 优先级天花板和谈法则 和谈法则号 1 2 描述 若是资本 R 正在利用,使命 T 不克不及获得所申请的资本 R,则使命 T 被堵塞 若是资本 R 空闲且使命 T 的优先级比当前优先级天花板的高,即便命 T 的优 先级高于所有当前被其他使命所获取的资本的优先级天花板,则资本 R 分派 给使命 T;当使命 T 的优先级低于当前优先级天花板时,即便请求的资本 R 空闲时,使命 T 仍会被堵塞,即优先级天花板堵塞 若是当前天花板属于使命 T 当前连结的资本之一,则空闲资本 R 分派给使命 T;反之,使命 T 被堵塞 使命 T 将按被分派的优先级施行,除非该使命正在临界区施行过程中堵塞了其 他高优先级的使命。若是使命 T 堵塞了高优先级的使命,则使命 T 将承继被 它堵塞的具有最高优先级使命的优先级,而且按此优先级继续施行,曲到它 每个优先级天花板高于或等于使命 T 的优先级的资本,然后,恢复到原 来的优先级 3 4 结论:正在动态优先级安排算法中,会按照使命的资本需求来动态的分派使命的优先级, 虽然正在使命创立是付与了优先级, 可是使命的优先级能够用内核供给的挪用进行改动。 动态 改变使命的优先级使得嵌入式使用愈加顺应于外部事务的矫捷性, 成立实正的及时响应系统。 然而,正在利用这种功能时,要留意不要,免得导致优先级反转、死锁,以至系统解体。 参考文献: [1]张友生从编。系统阐发师教程。大学出书社,2010 年 2 月。 [2]探矽工做室,胡继阳,李维仁,柯力群,龙著。嵌入式系统导论。中国铁道出 版社,2005 年 06 月第 1 版。 [3]朱珍平易近,隋雪青,段斌编著。嵌入式及时操做系统及其使用开辟。邮电大学出 版社,2006 年 12 月第一版。 6 [4]罗蕾从编。嵌入式及时操做系统及使用开辟。航空航天大学出书社,2005 年 1 月第 1 版。 7



友情链接:

Copyright 2019-2022 http://www.eflames.cn 版权所有 未经协议授权禁止转载