调度器基本概念
- 优先级别：有多种方式产生React任务，如用户操作、网络IO、定时器等等。用户对于这些任务延时的容忍度是不同的，耐心程度从高到低大概是：网络IO>定时器>用户操作。如果在短时间内产生这三种任务，那么处理的优先级别应当是用户操作>定时器>网络IO。如果两个任务同时产生，优先级别决定了先执行哪个任务。
- 时间切片：React15前React Task要么不做，要么直接做完，并没有中断任务执行这一说法，也就是说粒度过大，往往会带来用户体验问题。而React16将任务细粒度降低，一个大任务拆分成多个小任务，在JS线程空闲的时候会产生事件执行这些任务，并且限定了每次空闲时候执行任务的时间（默认是5ms，如果超时会出让JS执行权给浏览器），这样能够很大程度避免浏览器掉帧现象。 下面是React16之后执行代码的Performance记录，图中可以发现在DragStart和DragEnd之间JS主线程有很多碎片化的任务，这些就是React采用时间切片，将较大块的任务拆解，并利用碎片化时间处理这些小任务：
前端跳槽突围课：React18底层源码深入剖析 - React底层任务调度机制
React调度器是按照浏览器的requestIdleCallback这个API实现的（因为兼容性原因没有直接使用该API），现在分别从存储结构以及调用方式讲解实现原理：
任务存储结构
每个React任务都有开始时间（StartTime）和任务到期时间（expirationTime），React调度器中使用两个优先队列存储任务，这两个队列分别是：TaskQueue、TimerQueue，前者存放即将执行的任务，后者则存放延时执行任务：
- TaskQueue是以任务到期时间为优先级别排序依据，到期时间小的排在前面。在任务队列中的任务会不断执行（在任务执行规定时间内执行）。
- TimerQueue中任务是以任务的开始时间（任务产生时间 delay）为优先级别排序依据，在等待队列中的任务会采用setTimeout定时器，等到任务等待时间过后再放到任务队列中。
任务调用方式
上面讲到一个任务从注册到运行，可能会经历两个步骤：先放到等待队列中等待执行，等到时候到了放到任务队列中执行（说可能的原因是如果任务不设置delay属性则不会放到等待队列中，而是直接放到任务队列中），那么调度器分别采用什么方式执行这两个任务的呢？ 答案是：
- 采用setTimeout方式通知内部模块将等待队列中已经开始的任务放到任务队列中。这里采用setTimeout作为异步任务通知API应该没有什么异议。
- 采用MessageChannel产生的异步任务通知任务队列的每次执行。 浏览器能够产生异步任务的有宏观任务和微观任务：
前端跳槽突围课：React18底层源码深入剖析 - React任务调度以及背后的算法
React中的任务池
其实这不是个纯算法题，说回React，大家肯定听过React中有个fiber任务吧，而且不同的fiber任务有不同的优先级，为了用户体验，React需要先处理优先级高的任务。
为了存储这些任务，React中有两个任务池，源码中定义如下：
代码语言：javascript
代码语言：javascript复制ini复制代码// Tasks are stored on a min heap
var taskQueue = [];
var timerQueue = [];taskQueue与timerQueue都是数组，前者存储的是立即要执行的任务，而后者存的则是可以延迟执行的任务。
源码中任务的初始结构定义如下：
代码语言：javascript
代码语言：javascript复制csharp复制代码 var newTask = {
id: taskIdCounter , // 标记任务id
callback, // 回调函数
priorityLevel, // 任务优先级
startTime, // 任务开始时间，时间点
expirationTime, // 过期时间，时间点
sortIndex: -1, // 任务排序，取值来自过期时间，因此值越小，优先级越高
};React中一旦来了新任务，就会先用currentTime记录当前时间(performance.now()或者Date.now())，如果任务有delay参数，那么任务开始执行时间startTime = currentTime delay;。接下来通过startTime > currentTime如果成立，证明任务是可以延期的，那么任务进入timerQueue，否则进入taskQueue。
React中的任务调度
那么问题来了，怎么找到优先级最高的任务呢，以taskQueue为例，它是动态的任务池，数据形式上就是个数组。Array.sort可行，但不是最优方案，每次sort，平均时间复杂度高达nlog(n)。这个时候我们需要了解个数据结构：最小堆，也叫小顶堆。
当然可能有人问了，为什么不是最大堆呢？这是因为taskQueue的newTask中的排序用的是sortIndex，这个值取自过期时间expirationTime，也就意味着优先级越高的任务越需要立马执行，那么过期时间自然也就越小了，换句话说就是，优先级越高，过期时间越小。当然有可能两个任务的过期时间一样，那这个时候就要看是谁先进的任务池了，也就是newTask中的id嘛，每次来了新任务，id都会加1。因此React源码中任务比较优先级的函数如下：
代码语言：javascript
代码语言：javascript复制javascript复制代码function compare(a, b) {
// Compare sort index first, then task id.
const diff = a.sortIndex - b.sortIndex;
return diff !== 0 ? diff : a.id - b.id;
}其实用到最小堆，也就是把taskQueue做成最小堆的数据结构，然后执行任务的时候，取最小堆的最小任务，如果任务执行完毕，那么需要把这个任务从taskQueue中删除，并重新调整剩下的任务池，依然保证它是最小堆的数据结构。当然，往taskQueue中插入新任务的时候，也要调整taskQueue，保证新的任务池仍然是最小堆。
