时限调度算法给出的调度顺序_时间片轮转法进行进程调度

时限调度算法给出的调度顺序_时间片轮转法进行进程调度调度算法-时间轮一.背景在我们的业务场景中,经常会使用到定时任务功能,比如定时发送消息,定时执行数据同步,比如之前的文章介绍的分布式事务中的本地事务表方式的解决方案等等,特别是在现在大数据量和分布式服务环境下,定时任务调度越来越频繁,所以对应的定时任务调度的算法实现也越来越完善。在之前的单机环境下,我们可以使用ScheduledThreadPool起一个延迟任务线程池,定时的执行任务,又或者使用spring提供的@Schedule注解配合上cron表达式开启一个定时任务,又或者是lin

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

调度算法 – 时间轮

一. 背景

在我们的业务场景中,经常会使用到定时任务功能,比如定时发送消息,定时执行数据同步,比如之前的文章介绍的分布式事务中的本地事务表方式的解决方案等等,特别是在现在大数据量和分布式服务环境下,定时任务调度越来越频繁,所以对应的定时任务调度的算法实现也越来越完善。在之前的单机环境下,我们可以使用 ScheduledThreadPool 起一个延迟任务线程池,定时的执行任务,又或者使用spring提供的 @Schedule 注解配合上 cron表达式 开启一个定时任务,又或者是linux环境下的 corntab 表达式启动一个定时服务。而由于微服务的诞生,各个服务之间的解耦和职责拆分,定时任务调度被独立成一个中间件服务,比如著名的 XXL-JOB ,quartz,elastic-job 等等的分布式任务调度系统,而且我们公司也自主研发了一套分布式任务调度系统,也是参考了这些开源的分布式任务调度系统得到的启发。

不管是ScheduledThreadPool还是@Schedule单机环境的定时任务,还是xxl-job,quartz这一类独立部署的分布式任务调度系统,最核心的还是他们采用了什么 调度算法 ,如何实现任务在指定的时间被调度执行的,又如何保证在批量任务的情况下不会占用过多资源的,在学习这些调度思想的时候,偶然发现了一个很高效,逻辑很简洁的算法,就是 时间轮 算法,各位小伙伴注意:这里 并不是说 上面所有调度框架都是基于时间轮实现的,仅仅是介绍一下背景。

在介绍时间轮之前,我们可以思考一个问题, 延迟任务定时任务 有什么区别和关联。

首先,延迟任务就是指在距离当前时间点之后多久之后执行目标任务,而定时任务则是在指定时间点执行目标任务。那么我们可以思考,是不是这两种任务可以相互转换,比如延迟任务我们是可以计算出它的执行的具体时间点,所以可以转为定时任务,而定时任务可以计算出来下一次任务距离当前时间点的时间间距,那么也是可以转化为延迟任务。既然两种任务类型可以相互转换,那是不是可以用一种调度算法将他们实现和设计,这就是 时间轮算法

二. 时间轮

时限调度算法给出的调度顺序_时间片轮转法进行进程调度

时间轮,从名字大家就可以感觉出来,就是类似一个轮盘,类似一个时间钟表盘一样,我们假设现在这个时钟就是12个刻度,每个刻度的间隔时间是1小时,现在有三个任务,分别是:

1. 3点钟执行
2. 5点钟执行
3. 9点钟执行

那么,我们就将这三个任务放在对应的时间节点上,当指针指在了对应的时间点,就执行它上面的任务。

时限调度算法给出的调度顺序_时间片轮转法进行进程调度

难道时间轮就这么简单?别着急,让我们慢慢完善和扩展。

从上面的思想中我们会考虑几个问题:

1. 如果某个时间点有多个任务怎么办?
2. 我们该怎么设计资源分配,比如线程资源,才可以实现即高效又不占用过多资源?
3. 如果有的任务刷新频率很快,而有的频率很低怎么设计?
4. 如果任务是可以指定固定执行次数的怎么办?
5. 上例是以小时为节点的调度,如果是秒呢?或者既有很小的秒级别,又或者有以周和月为单位的任务该怎么设计?

对于这几个问题,我们一个一个的来解答。

  1. 如果某个时间点有多个任务怎么办?

对于轮盘上的时间节点对应的任务,我们可以使用一个队列存储,当时钟指针到达该节点的时候,执行这个队列上的所以任务。用图形表示出来就是:

时限调度算法给出的调度顺序_时间片轮转法进行进程调度

  1. 我们该怎么设计资源分配,比如线程资源,才可以实现即高效又不占用过多资源?

对于指针,我们只利用一个独立的线程进行轮转,因为它不会处理任务和逻辑,所以一个线程足够,而每当走到一个任务队列的时候,我们可以考虑启动一个新线程(保证实时性,但是不好控制线程资源),或者提前初始化好一个线程池专门处理任务使用,再或者我们可以考虑使用fork-join二分法实现的多任务处理方案(可以控制和管理线程资源,但可能存在延迟)等等,不管使用哪一种实现和设计,都要保证在不会占用过量线程和资源的情况下,尽可能实现实时性,因为定时任务的延迟时间不易过长。

  1. 如果有的任务刷新频率很快,而有的频率很低怎么设计?

假设现在有两个任务:

1. 每天的3点执行任务
2. 每周1的早上8点执行任务

对于这两个例子,假设我们的时间轮还是以小时为单位的刻度节点,那么该怎么设计呢?这里我们可以考虑加一个 圈数的属性round ,这个属性就是表示:当指针到达该节点的时候,任务是否应该被执行,实现思想就是:为这个round属性赋予初始值,这个初始值是根据业务场景来的,即每当指针到达该节点的时候,判断round是否等于0,如果大于0,则不执行该任务,并且对round进行减一的操作,只有round等于0的时候,才执行该任务,执行之后同时对round赋予新的初始值,以此循环。

时限调度算法给出的调度顺序_时间片轮转法进行进程调度

  1. 如果任务是可以指定固定执行次数的怎么办?

在基于上面的完善和扩展之后,我又有新的想法,就是一个任务,是不是可以指定它的执行次数,即任务A执行3此后丢弃,任务B执行10次后丢弃,没达到阈值仍正常执行。同样的,我们可以添加一个字段 阈值:threshold ,表示阈值,初始值就是需要执行的次数,每当指针达到该队列,且round = 0的之后,执行该任务后对threshold做 减一 操作,如果threshold 等于0 ,则将该任务从任务队列中移除,而对于那些没有固定次数,永远执行的任务,可以将threshold设置为 -1 ,表示不限制次数。

时限调度算法给出的调度顺序_时间片轮转法进行进程调度

  1. 上例是以小时为节点的调度,如果是秒呢?或者既有很小的秒级别,又或者有以周和月为单位的任务该怎么设计?

    上面的问题解决了之后,还剩最后一个问题,就是这个时钟的刻度我们该如何设计。因为真实情况下,任务的调度肯定差距很大,我们的第一反应是将刻度尽可能的增加,比如每个刻度表示一秒,我们创建一年的时间轮,那么就是31536000个刻度,这个肯定不现实,大家也不会这么去实现。所以我们可以采用 多层级时间轮+第三方扩展 的方式实现真正业务场景中的调度算法。

    多层级时间轮 的意思就是:我们可以设计和创建多个时间轮,这些时间轮的刻度差是分级别的,比如我们创建三个时间轮,一个时间轮的刻度是秒,另一个时间轮的刻度是小时,最后一个时间论的刻度是日;其中只有 最小的秒级别的时间轮真正的执行任务 ,而其他两个时间轮只是负责将快要达到执行时间的任务下传给更小的刻度级别的时间轮:

    时限调度算法给出的调度顺序_时间片轮转法进行进程调度

    这样就实现了多层级的时间轮概念模型,肯定又有小伙伴想了,最大的刻度是日,但是日的刻度还是小,我还有以周或者月为周期的任务怎么办呢,别着急,这就是我要说的借助 第三方扩展 的方式,对于上面的方式,可以比较精细的计算和执行任务调度了,那么对于粗粒度的任务,我们可以先存储到第三方服务中,比如 mysql,redis,file system,log 等等方式,这些地方可以持久化或者非持久化存储时间比较久远的任务,然后每天 定时的从这些地方搂满足条件的数据到刻度为日级别的时间轮中 ,这样的话,从粗粒度到细粒度,就完整的实现了一套任务调度算法的实现方案了。

时限调度算法给出的调度顺序_时间片轮转法进行进程调度

三. 总结

时间轮算法,是一种批量任务调度算法的思想,针对于不同的场景,我们可以扩展更多的实现和逻辑,总体来说,就是采用多层级时间轮的设计模式,利用时间刻度的思想,将任务排列到任务队列中,并对队列中的任务赋予round和threshold属性,实现一整套完整的调度算法实现逻辑。大家如果想看代码实现,可以去看 Netty HashedWheelTimer 的源码,它采用的就是时间轮的思想,只不过和本篇介绍的有细微不同,不过核心思想是相同的。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188237.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 单调队列-原理详解(deque实现)[通俗易懂]

    单调队列-原理详解(deque实现)[通俗易懂]一、单调队列的概念:单调队列,即单调递减或单调递增的队列。二、单调队列的性质:1.队列中的元素在原来的列表中的位置是由前往后的(随着循环顺序入队)。2.队列中元素的大小是单调递增或递减的。三、单调队列的特点:从队尾入列,队首或队尾出列。四、例题分析:那么单调队列用什么用呢?单调队列一般用于求区间内的最值问题。看几道题,理解上述内容:1.洛谷P1886…

  • YIQ颜色空间_简述RGB颜色

    YIQ颜色空间_简述RGB颜色首先,我们先来了解下有关颜色的基本概念一、色彩的基本概念1、彩色的三要素亮度:即人眼对光的明亮程度的感受。色调:人眼能看到的颜色种类,与光的波长有关饱和度:颜色深浅程度。与各种颜色混入白光的比例有关。以上色调+饱和度=色度2、三基色原理三基色可以通过适当比例的混合组成自然界中任何一种颜色由于人眼对于红绿蓝三种色光最为敏感,并且由这三种颜色能组成的颜色范围最广,故一般选用…

    2022年10月28日
  • RBF神经网络理论与实现「建议收藏」

    RBF神经网络理论与实现「建议收藏」前言最近发现有挺多人喜欢径向基函数(RadialBasisFunction,RBF)神经网络,其实它就是将RBF作为神经网络层间的一种连接方式而已。这里做一个简单的描述和找了个代码解读。之前也写过一篇,不过排版不好看,可以戳这里跳转国际惯例,参考博客:维基百科径向基函数《模式识别与智能计算——matlab技术实现第三版》第6.3章节《matlab神经网络43个案例分析》第7章节tensorflow2.0实现RBF理论基本思想用RBF作为隐单元的“基”构成隐藏层空间

    2022年10月24日
  • java queryinterface_COM编程中的接口查询QueryInterface的实现原理

    java queryinterface_COM编程中的接口查询QueryInterface的实现原理我们都知道,COM组件编程中,QueryInterface实现的接口之间的查询,通过这个接口,我们可以获取该组件中其他的接口。但是,QueryInterface实现的原理,并不是大家都很清楚,也没有哪本书仔细讲了这点。我将个人心得写下来,供有需要的人查看。首先,我们看一下基本的COM实现。一般来说,COM是通过多继承实现多个接口,如下图而对应的QueryInterface实现如下HRESULT…

  • KETTLE 使用教程

    KETTLE 使用教程Kettle的建立数据库连接、使用kettle进行简单的全量对比插入更新:kettle会自动对比用户设置的对比字段,若目标表不存在该字段,则新插入该条记录。若存在,则更新。Kettle简介:Kettle是一款国外开源的ETL工具,纯java编写,可以在Window、Linux、Unix上运行,数据抽取高效稳定。Kettle中文名称叫水壶,该项目的主程序员MATT希望把各种数据放到一个…

  • Java课设–学生成绩管理系统一

    Java课设–学生成绩管理系统一写在前面这个项目是Java课程的课设,一共花了5天的时间去完成它,在这期间感谢一些博主的帮助,让我了解到了一些新的技术知识,所以打算写这一系列博客来介绍一整个课设项目,也为了帮助之后的人,如有错误,请联系我。为了更好的让读者了解到整个项目的设计流程,我将项目拆分成几个部分来就行解说,这一小节是一个总述,主要介绍课设的整个框架和最终效果,代码我会放到后面的github链接上,欢迎大家star。如果有一些参考没有加上联系,希望大家可以联系我,因为写的时候查的比较快,没有记录到博主的链接,敬请谅解!!!一、

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号