Erlang/Elixir Erlang 源码阅读 -- scheduler
我们先从问题出发，看看 Erlang 为了解决并发问题做了哪些努力。
1. Erlang scheduler 解决的问题
1.1 多线程 && callbcak
任务可以先简单的划分为 CPU 和 IO 两种操作，相比之下，IO 操作速度非常慢。如果在进行 IO 操作的同时， CPU 忙等，效率会非常低。
系统为了解决这个问题，提供了线程。在进行 IO 操作的时候，线程会被挂起，直到 I/O 操作成功，才有可能被唤醒。
由于并发要做到在逻辑上同时执行，那么一个线程执行一段时间，就需要让其他线程执行。所以系统线程实现了抢占式调度。
系统的调度是指令级的，比如 A = A + 1 需要多个指令，如果两个线程同时这行 A = A + 1，由于读取值和存入值的顺序不同，会造成 A 的值不同。也就是所说的线程安全。
我们看到，系统线程解决了两个问题，傻等 IO 和线程间基于时间的公平调度，但带来了线程安全问题。
JavaScript 使用 callback 避免了 CPU 的忙等。并发能力也不错。实质上是，在进行 IO 操作的时候，只发起 IO 操作的 request，而不等 IO 操作结束，直接返回，当 IO 操作结束的时候，再执行对应的 callback。
而 callback 一旦嵌套，就很难维护。可以在语言层面解决这个问题，比如 ActionCable 使用单独的线程同时监听多个 file descriptor（event loop），有 IO ready 的时候执行相应的 callback。并把这些细节完全的隐藏在框架之下。而 rust 的 Tokio 在提供全局的 event loop 同时，提供了 reactor 模型来避免 callback 嵌套的问题。
callback 是语言级别的，保证了操作的原子性，也就不会有线程安全之类的问题。
我们再来看公平调度这个问题，callback 模式，可以抽象为，CPU 计算，异步 I/O 请求，I/O ready 后执行 callback。
我们假设这样一个场景， 1 秒有 1000 个请求打到服务器，刚好第一个请求需要计算 1s，而 callback 模式需要先完成这 1s 的运算， 才能让 CPU 处理其他请求，也就是说，其他请求的延迟至少有 1s。这样显然是不公平的。更好的做法是，第一个请求执行一小段时间，让 CPU 去处理其他请求。
所以 callback 模式解决 IO 忙等，避免了并发安全，但没有解决公平调度。
1.2 Erlang
1.2.1 三个问题
首先 Erlang 使用 Reactor 模型，避免了线程安全之类的问题。使用单独的的线程调度 IO 任务，解决了 IO 忙等。
公平调度本质上是执行任务一段时间，再执行另一个任务的能力。如果像系统一样按照时间分片来调度话，同样会破坏操作的原子性。所以 Erlang 使用 reduction 来做调度。
简单来说，可以把 reduction 理解为一次 Erlang 方法的执行。Erlang 给每个 process 分配 4000（当前版本，以前是 2000，这块就不细说） 个 reductions，如果 4000 个 reductions 执行完了，就执行另外一个 process。
使用方法作为调度的好处是，保证了原子性，而函数的调用次数也可以较好的反应执行时间。Erlang 给 IO 请求和 bif、nif 分配了不同的 reduction，这样就可以更好的保证公平性。
Erlang 的 reduction 实际计算比较复杂，比如 ets:lookup 是 ets table 里 item 数量 * 2，也就是执行完一次 ets:lookup，必然会有一次调度。
%% 1k
Foo = fun() ->
receive
start ->
ets:lookup(test_1k,1),
receive
stop ->
stop
end
end
end.
ets:new(test_1k, [named_table, bag, public, {read_concurrency, true}]).
lists:map(fun(I) -> ets:insert(test_1k, {I, I}) end, lists:seq(1, 1000)).
Pid = spawn(Foo).
process_info(Pid).
;; 2000 reductions
Pid ! start.
process_info(Pid).
;; 4000 reductions
1.2.2 多核
目前，CPU 大多是多个核心，也就是同一时间，在物理上可以执行多个指令。系统线程可以利用多核。而 JavaScript 是单线程，只有靠多个进程来利用多核资源。
假设 CPU 是双核的，物理核数是 2，我们起两个 JavaScript 节点，这样看起来就可以很好的利用多核 CPU 资源。
但如果请求是随机的，就有可能现两个节点中，一个有任务，另一个节点空闲的情况。当然在两个节点前可以加个 load balance 来缓解，但依然没有办法完全解决。
Erlang 使用多个 scheduler，每个 scheduler 在一个系统 thread 里运行。scheduler 的 thread 会和 CPU 动态绑定（两个 scheduler 在一个 cpu 就无法利用多核了），
如果一个 scheduler 空了的话，就会去偷（恩，源代码中写的就是偷）其他 scheduler 的 process。每隔一定的 reduction，还会做一次迁移。
如果一个 scheduler 闲太久了，就会让它去睡觉，可以省资源，也同时避免了无用的调度。去睡觉前还会 spin 一段时间，等待别人给他任务，因为唤醒一个 scheduler 比较耗时。
1.3 OTP
调度、并发安全、Reactor 模型仅仅是 Erlang 一部分，Erlang 的 OTP 为并发这个问题提供了一套完善的解决方案。
比如知乎在使用 go 重写的时候，发现 goroutine 没有父子 goroutine 的概念，很坑。而 Erlang 有 supervisor、link、monitor，做这件事非常自然。
再如 let it crash 哲学，如果 process 出问题了，直接让他死掉，再重启 process，这样就解决了软件工程 90% 的问题。
而这些只是 Erlang 的冰山一角。Erlang 不仅仅提供了并发能力，并且提供了一套完善的并发机制。
唠叨了这么多，有点跑题，下面来看下源码。
2. 源码阅读
这块写出来后，感觉这块有点枯燥。。。
2.1 Basic - Process types
一种是 dirty 的，比如 nif、I/O 操作，这些都不会再执行中 yield，会阻塞 scheduler，所以 Erlang 使用单独的 thread 处理这些 process。 一种是 normal，就是由 Erlang 代码实现的，这种可以随时在执行完一个方法后 yield，不会阻塞 scheduler。
Erlang 会分别创建两种线程来处理相应的任务。
normal 的 thread 数目，默认是由 logical processor(cpu core or hardware thread) 决定的，Erlang 实现了 Erlang process，所以系统线程数目大于 logical processor 的数目，一般并不会带来更好的性能。
2.2 调度函数 erts_schedule
Erlang 根据需要，创建完系统线程后，erts_schedule 在 process_main 和 erts_dirty_process_main 里被调用。也就是说，erts_schedule 会同时处理 dirty 和 normal 两种调度。
erts_schedule 大体分为三个部分：
- internal_sched_out_proc
- check_activities_to_run
- pick_next_process
internal_sched_out_proc 会处理 process 调出后的操作。
check_activities_to_run，检查是否有需要执行的活动，包括 reblance scheduler，检查 timer 等。
pick_next_process 则是选择一个合适的 process 来执行。
2.2.1 internal_sched_out_proc
internal_sched_out_proc 首先计算、设置 reductions，之后会调用 schedule_out_process。
在 schedule_out_process 会选择需要将 process 移入对应的 run queue，如果是 dirty 的，就会被移入 diry scheduler 的 run queue 里，如果不是 dirty 的话，会先检查是否需要 migration，之后再移入。
而在 pick_next_process 里，发现选出的 process 是 dirty 相关的话，会直接跳到 internal_sched_out_proc 这个 tag，
也就是说，一个 process 如果是 dirty 的话，会从 normal scheduler migrate 到 dirty scheduler。一个 normal process 执行完之后，可能会被 migrate 到其他 normal scheduler 里。
2.2.2 check_activities_to_run
执行完 internal_sched_out_proc 后会执行 check_activities_to_run，check_activities_to_run 大体包括：
2.2.3 check_timers
首先是检查 timer，esdp->last_monotonic_time >= erts_next_timeout_time(esdp->next_tmo_ref)，
scheduler 的最后一次的时间，如果大于下次 timeout 的时间，则 erts_bump_timers，由此可以看出 Erlang timeout 是软实时的，是由 esdp(ErtsSchedulerData) 记录一个 timer 的引用，每次调用 erts_schedule 才会被处理。
所谓的软实时是指，是指如果设置 10 秒的 timeout，这个 timeout 不会在 10 秒之前被触发，但无法保证一定在 10s 执行。
2.2.4 check_balance
check_balance 的触发条件是，check_balance_reds < 0，而 check_balance_reds 的定义是
#define ERTS_RUNQ_CHECK_BALANCE_REDS_PER_SCHED (2000*CONTEXT_REDS)
#define ERTS_RUNQ_CALL_CHECK_BALANCE_REDS \
(ERTS_RUNQ_CHECK_BALANCE_REDS_PER_SCHED/2)
CONTEXT_REDS 是 4000，也就是大约 2000 * 2000 个 reductions 之后会执行一次 check_balance。
在进入 check_balance 的时候，发现有 scheduler 在执行 check_balance，则将自身 check_balance_reds 设置为 INT_MAX，来避免同时执行。
check_balance 根据之前的情况，预测一个 scheduler 的执行能力，设置迁移路径。如果一个 scheduler 负载过低，则将其设置为 inactive。
inactive 的 scheduler run queue 会被清空，并进入 sleep 状态，而 Erlang node 负载高的时候，再被再次唤醒。
check_balance 之后，会根据路径做 immigrate。
2.2.5 suspend_scheduler
对于 dirty scheduler，且没有 process 可执行，会被挂起。
2.2.6 check_cpu_bind
erlang 默认会根据 logical processors（logical processors 指的是 CPU 核数或者硬件线程） 数目来创建 scheduler thread（系统线程）。这样就可以利用多核的能力。
所以当 thread 被分配给错误的 CPU core 的时候，使用 check_cpu_bind 来纠正这种情况。
2.2.7 handle_aux_work
auxiliary(辅助) work，在这里会处理一些诸如 cancel_timer 的工作。
2.2.8 empty_runq
在 check_balance 里，会把一个 scheduler 设置为 inactive，empty_runq 用来清空 run queue。
2.2.9 try_steal_task
如果没有任务执行时(!runq_got_work_to_execute)，会调用 try_steal_task。
try_steal_task 先给自己上了一把锁，防止别人这个时候偷自己的，然后先偷 inactive run queue，之后偷 active queue（偷的方法名很也有趣 check_possible_steal_victim，可以翻译成找个倒霉蛋）。
ERTS_LC_CHK_RUNQ_LOCK(rq, rq_locked);
get_no_runqs(&active_rqs, &blnc_rqs);
偷的时候，就是从其他 run queue 拿 process 的过程。
2.2.10 pick_next_process
根据 run queue 的当前的最高(ErtsRunQueue 有多个 priority queue)的优先级，挑选一个存在的、且不在执行中的 process，如果不存在这样的 process，则再次跳到 pick_next_process 这个 tag。
如果当前 process 是 dirty 的，则 unlock 这个 process(erts_proc_unlock(p, ERTS_PROC_LOCK_STATUS))，并跳转到 sched_out_proc， 之后跳到 internal_sched_out_proc，就如之前所说，dirty process 会被丢到dirty scheduler 里。
如果不是 dirty 的，除了会计算 reds 之外，还会做一些 gc 之类的操作。
3. 最后
可以说 Erlang 提供了优秀的并发能力和一套完善的并发机制。
