Erlang并发机制 – 任务迁移算法 -

jzhihui

浏览: 266078 次
性别:
来自: 杭州

最近访客更多访客>>

chenzehe

邱董233

独孤丨九剑

zzship

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

Erlang并发机制 – 任务迁移算法

博客分类：

Erlang

erlang

一般情况下，在SMP环境中，每个调度器都会绑定到一个CPU核心，为了保证调度器可以充分的利用CPU资源，那么就必要确保每个调度器任务队列的长度大致相同，Erlang通过任务迁移算法来完成这个功能。Characterizing the Scalability of Erlang VM on Many-core Processors这篇文章中对这个算法进行了详细的说明，不过，就我自己感觉来说，边看代码，边看上述论文里的描述，可能更容易理解。这篇算是一个总结文档。

Erlang中每隔固定时间（R15B中这个值是2000*2000）会做一次任务检查，查看各个任务队列上的任务是否分布均衡。主要要做下面几个工作：

1) 确定活跃调度器数量；

2) 确定每个调度器的负载，根据每个队列当前的负载确定调度器之间的迁移阈值，高于这个阈值的队列需要迁出任务，低于的需要迁入任务；

3) 根据2)的结果，确定每个队列的迁移路线；

4) 在调度到一个需要迁入任务的队列时，从目标迁出队列迁移一个任务，直到达到迁移阈值。

在继续说明之前，需要了解到，在虚拟机实现上，上面提到的固定时间（2000*2000）又被切分成两个区间（每个区间1000*2000个reduction）。第一个区间时间到的时候，只做一件事，就是检查每个调度器任务队列的状态，如果队列处理等待状态，就会对该队列设置一个标记，否则清除该标记。第二个区间时间到时，才会完整的执行上述4个步骤。

活跃调度器数量

确定任务检查完成以后，活跃（active）调度器的数量。

任务检查涉及到的调度器运行时状态有2种：active，inactive（这两种状态的调度器统称online调度器；offline调度器处于suspend状态）。调度器处理active状态说明调度器的任务队列里任务充足，调度器一直在工作；处理inactive说明调度器没有工作，处理等待状态，如果其它调度器任务繁重，可以唤醒inactive的调度器。活跃调度器的数量N_active主要由下面几个方面确定：

1) 在整个检查区间内从未进入等待状态的调度器数量N_{full_shed}；

2) 在第二个区间内没有进入等待状态的调度器数量 N_{half_shed}；

3) 当前在线调度器数量N_online；

4) 当前活跃调度器数量 N_{active_current}；

5) 上次任务检查时确定的活跃调度器数量N_{active_begin}；

6) 上次任务检查引起调度器数量增加时的调度器数量 N_{prev_rise}；

7) 最小调度器数量N_min；

确定活跃调度器数量的流程如下图所示。

迁移阈值

如果确定的活跃调度器数量小于当前在线调度器数量，说明当前负载较低，有部分调度器处于空闲状态，这部分调度器将会标记为inactive，然后其对应的任务队列上的任务会迁移到其它active调度器上。

如果确定的活跃调度器数量等于当前在线调度器数量，说明系统满载。会根据每个调度器任务队列运行情况，对每个优先级的任务队列都会计算一个可用性值（availability，avail）：

1) 如果调度器在任务检查间隔内（2000*2000）一直处于等待状态，则avail=1；

2) 如果某个调度器所有优先队列上运行的reduction数量的和为0（未执行任务任务），那么这个调度器上所有优先队列的avail=0；

3) max和port优先队列的avail=1；

4) high、normal、low队列（normal和low共享一个队列，共享avail值）的avail按如下方式计算：

其中redp_n为第n个调度器在所有优先队列上执行的reduction数量；red_max,n为第n个调度器在max队列上执行的reduction数量；red_high,n为第n个调度器在high队列上执行的reduction数量。

5) 最后如果一个调度器在任务检查间隔内没有处于等待状态，则根据其所执行redcution数量的历史统计及该检查间隔内未处于等待状态队列的调度器个数对每个优先队列的avail做个调整。

最后，会根据每个优先队列的avail值及任务检查间隔内每个优先队列的最大队列长度（maxlength）为每个队列计算任务迁移阈值（migration_limit）：

如果migration_limit ==0，则相应队列不需要迁入、迁出任务；如果不为0，则迁入、迁出任务的数量不能超过这个值。假设任务队列中只有normal优先级的任务（一般情况下，用户创建的进程都处于normal优先级），并且每个优先队列的avail值都相同，那么迁移阈值的计算就是对所有队列的最大长度的和做平均（如下图）。

确定每个队列的迁移路线

每个队列有了任务迁移的阈值后，根据其与相应调度器最大队列长度的差值，对队列由小到大进行排序（需要迁入的队列，差值为负，排在前面，迁出的排在后面）。排序后，队列尾（迁移任务者）对应到队列头（迁入任务者），依次确定为迁移路线：

比如在上面的图中，队列长度为14的任务将会迁移到队列长度为4的队列，队列长度为10的任务将会迁移到队列长度为5的队列。当然，一般情况下，肯定会有不匹配，如果有队列有多余的任务没有迁移完，则会从最小差值（上图队列长度为4）队列开始扫描，确定为迁移路线；如果有多余的队列需要迁入任务，则会从最大差值队列（队列长度为14）队列开始扫描，确定为迁移路线。如下图（有多余队列需要迁入任务）。

迁移路线确定后，在调度时，就会在相应的迁入、迁出队列之间传递任务，直到达到相应队列的迁入、迁出阈值。

最后，如果经过任务迁移逻辑后，当前的调度队列还是没有任务可以执行，调度器会尝试从其它调度队列偷一个任务过来（一般情况下，如果所有调度器都处于active状态，则会从最近的调度器偷取任务）。