高级分布式系统-第9讲 实时调度--可调度性分析

这篇具有很好参考价值的文章主要介绍了高级分布式系统-第9讲 实时调度--可调度性分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

高级分布式系统汇总:高级分布式系统目录汇总-CSDN博客

调度的目的:

分布式实时系统中,很多任务同时尝试访问共享资源(如处理器和网络),调度试图有效地利用这些资源来解决问题,以保证系统是正确的,换句话说是保证系统符合其所有的时间限制。

调度的运行可以采取操作系统形式,由操作系统直接控制硬件;也可采用中间件形式,中间件位于操作系统和应用程序之间。

调度的定义:

针对给定的系统资源和一组实时任务,确定每个任务何时何处执行的整个过程称为调度。

实时调度理论中,主要研究任务实时调度算法和可调度性分析。

实时调度的分类

静态调度与动态调度: 根据调度器做出调度决策的时刻进行区分。

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

静态调度

静态调度——调度器的调度决策是在编译时做出的,那么这种调度器是静态的(运行前的),调度器退化为分派器。

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

动态调度

动态调度——调度器的调度决策是在运行期间做出的,即从多个处于“就绪”状态的任务里选择一个任务。动态调度器非常灵活,适合在任务情形不断变化的情况下使用。

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

任务通常为进程和线程的统称,是实时操作系统获取资源、进行调度的基本单位。

非抢占式调度与抢占式调度: 以任务优先级为依据的两种调度方法

非抢占式调度——一旦处理器给予某个任务,这个任务就一直运行下去,不会被其他任务( 即使其他任务的优先级更高 ) 抢占,直到该任务自己释放处理器。

优先级:许多任务调度是以任务的优先级为基础的。在这种系统中 每 个任 务 都 与 优先 级 编 号 (priority number )相联系 ,优先级编号一般为整数 ,可以是固定的,也可以是变化的 。如下图(非抢占式):

低优先级任务 T1

高优先级任务 T2

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

抢占式调度——如果优先级高于当前运行任务的新任务准备运行,那么当前运行的任务可以被抢占(被中断),即可以切换到优先级更高的新任务 。

优先级:许多任务调度是以任务的优先级为基础的。在这种系统中每个任务都与优先级编号(priority number )相联系 ,优先级编号一般为整数 ,可以是固定的,也可以是变化的 。如左图(抢占式):

低优先级任务 T1

高优先级任务 T2

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

可调度性分析

可调度性分析:对于一组给定的任务,如果所有任务都能满足截止时间要求,那么这些任务是可调度的。当系统采用动态调度算法时,若有新任务需要加入系统,则应该进行可调度性分析。可调度性是评价任务调度算法优劣的重要指标 。

基于CPU利用率的分析

基于CPU利用率的分析——首先计算处理器利用率,然后通过一个与该利用率相关的测试条件来判定系统的可调度性。

基于最大响应时间的分析方法

基于最大响应时间的分析方法——将整个分析过程分为两个阶段:分析和判定。分析阶段分析各个任务的最大响应时间,判定阶段将分析阶段得到的任务最大响应时间与该任务的截止时间进行比较。如果所有任务的最大响应时间都不大于其截止时间,则系统是可调度的。

调度测试

基于CPU利用率的测试:一组处于“就绪”状态的任务是否可以通过调度,使得每个任务满足其截止时间要求,可以通过基于CPU利用率的分析方法进行判定,这种方法又称为可调度性测试。

可调度性测试分为三类:充要的(exact)、充分的(sufficient)和必要的( necessary)。

充要可调度性测试算法的复杂性属于一类NP完全(NP-complete) 问题,即使只有一个共享资源也难以实现。一般只做必要性、充分性测试。

任务分类:周期性的、零星的、不定期的

周期性任务按一定的周期到达并请求执行。

零星任务的请求时间是不可预知的,但任意两个请求时间之间存在一个最小时间间隔,可以将零星任务当成周期性任务处理,其任务周期为最小时间间隔。

不定期任务的请求时间不能预先确定,无规律可言。

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

周期性任务的可调度性测试:

【定理1】如果某任务组中的任务是周期性的,那么必要可调度性测试的条件是任务组里的各个任务的利用系数之和必须满足:

其中n为任务数,m为处理器个数。

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

零星任务和不定期任务的可调度性测试

零星任务可以按【定理1】进行必要可调度性测试,任务周期设置为任意两个请求时间之间的最小时间间隔。不定期任务的请求时间没有任何约束,前面介绍的必要可调度性测试条件无效 。

一般情况下,通过必要可调度性测试得到的肯定结论并不具备充分性。

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

不同性能调度器导致(a)不可调度,(b)可调度;不满足充分条件!

基于最大响应时间的分析方法

【定理2】任务间的关联关系得到满足的情况下,若任务的最大响应时间不大于任务的截止时间,则该任务称为可调度的。如果任务组中的所有任务都是可调度的,那么该任务组是可调度的。

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

1)排列最低优先级任务(本例为T4)的持续时间(周期)和截止时间。

2)画出能够抢占最低优先级任务的任务/ISR,并根据抢占情况移动低优先级任务。

3)确定每个任务和ISR可能发生的抢占,并进行恰当移动。

4)重复上述过程,直到最低优先级任务的持续时间结束。

5)判断每个任务是否满足其截止时间要求。

【定理3】设某任务组中的任务是相互独立的、周期性的。在所有任务同时到达的最坏情形下,如果每个任务满足其第一个截止时间要求,那么所有任务的截止时间将始终得到满足。

[例2]设任务组由表中的3个相互独立的任务构成,T1的优先级最高,T3的优先级最低。试判断系统的可调度性

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

【定理3】续:每个任务的响应时间为Ri。计算推导如下:

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统

高级分布式系统-第9讲 实时调度--可调度性分析,高级分布式系统,分布式,高级分布式系统文章来源地址https://www.toymoban.com/news/detail-807099.html

到了这里,关于高级分布式系统-第9讲 实时调度--可调度性分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 系统设计面试指南之分布式任务调度

    任务是需要资源(CPU 时间、内存、存储、网络带宽等)在指定时间内完成的一段计算工作。 通过智能地将资源分配给任务以满足任务级和系统级目标的系统称为任务调度程序。 任务调度程序: 及时决定和分配资源给任务的过程称为任务调度。 当我们在 Facebook 发表评论时。我

    2024年02月05日
    浏览(61)
  • 分布式调度引擎elastic-job3源码分析(六)-失效转移

      调度引擎是关键的基础设施,不但是定时执行任务,更是大规模分布式任务引擎,分布式并行处理平台,管理计算节点集群,提供高吞吐的可伸缩的数据处理能力。 公司日益增长的业务,对调度引擎高吞吐,高并发的要求也快速增长,需构建一个无中心,管理大集群,健壮

    2023年04月08日
    浏览(63)
  • 高级分布式系统-第10讲 分布式控制系统

    高级分布式系统汇总:高级分布式系统目录汇总-CSDN博客 自动化是关于一切人造系统自动、智能、自主、高效和安全运行的科学与技术 计算机控制技术是实现自动化的主要方法和手段 分布式控制技术是伴随着机器大工业生产而诞生的特殊计算机控制技术 指利用计算机(通常

    2024年01月19日
    浏览(62)
  • 高级分布式系统-第15讲 分布式机器学习--分布式机器学习算法

    高级分布式系统汇总:高级分布式系统目录汇总-CSDN博客 按照通信步调,大致可以分为同步算法和异步算法两大类。 同步算法下,通信过程中有一个显式的全局同步状态,称之为同步屏障。当工作节点运行到 同步屏障 ,就会进入等待状态,直到其工作节点均运行到同步屏障

    2024年01月18日
    浏览(45)
  • 开源 IoT 物联网分布式实时数据分析服务

    随着物联网设备增长,也产生了大量的数据,这些数据具有高速、多样和实时的特点。如果你的物联网数据 不及时、不准确、不具有可操作性 ,那么你在收集的这些数据就变得毫无价值。为了有效地利用这些数据,我们需要一种能够快速响应、灵活扩展和支持复杂查询的系

    2024年02月12日
    浏览(59)
  • 高级分布式系统-第14讲 分布式控制经典理论

    高级分布式系统汇总:高级分布式系统目录汇总-CSDN博客 模糊控制是一种以模糊集合论、模糊语言变量以及模糊逻辑推理为数学基础的控制方法,它模拟人的思维,构造一种非线性控制,以满足复杂的不确定的过程控制的需要,属于智能控制范畴。 由于模糊控制是对人的思维

    2024年02月01日
    浏览(40)
  • 高级分布式系统-第12讲 分布式控制经典理论

    高级分布式系统汇总:高级分布式系统目录汇总-CSDN博客 分布式控制系统的设计,是指在给定系统性能指标的条件下,设计出控制器的控制规律和相应的数字控制算法。 根据偏差的比例(Proportional)、积分(Integral)、微分(Derivative)进行控制(简称PID控制),一种广泛应用

    2024年01月20日
    浏览(50)
  • 使用Docker部署开源分布式任务调度系统DolphinScheduler

    🔥 博客主页 : 小羊失眠啦. 🎥 系列专栏 : 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。 本篇教程和大家分享一下DolphinSc

    2024年02月05日
    浏览(60)
  • 高级分布式系统-第15讲 分布式机器学习--联邦学习

    高级分布式系统汇总:高级分布式系统目录汇总-CSDN博客 两种常见的架构:客户-服务器架构和对等网络架构 联邦学习在传统的分布式机器学习基础上的变化。 传统的分布式机器学习:在数据中心或计算集群中使用并行训练,因为有高速通信连接,所以通信开销相对很小,计

    2024年02月01日
    浏览(47)
  • 开源分布式任务调度系统DolphinScheduler本地部署与远程访问

    本篇教程和大家分享一下DolphinScheduler的安装部署及如何实现公网远程访问,结合内网穿透工具实现公网访问DolphinScheduler内网并进行远程办公,帮助开发人员进行远程任务调度及管理,提高工作效率。 DolphinScheduler是一款开源的分布式任务调度系统,它可以帮助开发人员更加方

    2024年02月03日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包