Cachy：树外Linux调度器提高CPU缓存使用率

Cachy-Sched是一个利用CPU缓存的Linux调度器，它基于最高响应率NEXT(HRRN)策略。

删除除空闲CPU平衡之外的所有平衡代码。没有定期平衡，仅应用空闲CPU平衡。一旦一个任务被分配给一个CPU，它就会一直使用它，直到另一个CPU空闲，然后这个任务可能会被拉到新的CPU上。禁用周期性平衡的原因是为了利用任务的CPU缓存。

一项任务在每个滴答中都会被抢占。如果时钟以250 Hz计时(即CONFIG_HZ_250=y)，则任务运行4毫秒，然后在运行队列中有其他任务时被抢占。

此调度程序是为桌面使用而设计的，因为它与响应性有关。这对服务器来说可能不是坏事。

Cachy可能适合手机或Android，因为它的响应度很高。Cachy需要集成到Android中，我不认为目前的版本没有做好推特和适应Android黑客的准备。

选择内核版本的分支，并安装文件夹linux-(Version)-cachy，这是可以打补丁的Linux内核。

或者自己打补丁下载linux内核(与补丁版本相同的https://www.kernel.org/))(即如果补丁文件名为cachy-5.7.6.patch，则下载https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.7.6.tar.xz)。

Dmesg|grep-i；cachy CPU"；[0.059697]cachy CPU调度器v5.7.10，作者：Hamad Al Marri。感谢我妻子萨拉的耐心。

挑选下一个任务的复杂度为O(N)，其中n是运行队列中的任务数(每个CPU都有自己的运行队列)。

注：O(N)听起来很可怕，但通常对于具有4个CPU的计算机(用于桌面或移动作业)，可运行任务的最大数量可能不超过10(在挑选下一次运行时)-空闲任务被排除在外，因为它们在休眠时出列，在醒来时排队。大量CPU(4+)的Cachy调度器延迟通常比CFS少，因为不需要树平衡或任务平衡-同样适用于台式机和移动设备。

CACHY是一种基于最高响应率NEXT(HRRN)策略的调度策略，HRRN是一种响应率最高的进程下一次运行的调度策略。每个进程都有一个响应比值R=(w_t+s_t)/s_t，其中w_t是进程等待时间，s_t是进程运行时间。如果两个进程的运行时间相似，等待时间较长的进程将首先运行。HRRN的目的是防止饥饿，因为它争取了进程的等待时间，也增加了响应时间。

如果两个进程在整数舍入后具有相同的R，则比较除法余数。R值的完整计算见下文：

U64 r_curr，r_se，w_curr，w_se；struct task_struct*t_curr=task_of(Curr)；struct task_struct*t_se=task_of(Se)；U64 VR_curr=Curr->；sum_exec_run+1；U64 VR_se=se->；sum_exec_run+1；s64 diff；w_curr=(现在-t_curr-。//调整优先级w_curr*=(140-t_curr->；prio)；w_se*=(140-t_se->；prio)；r_curr=w_curr/vr_curr；r_se=w_se/vr_se；diff=(S64)(R_Se)-(S64)(R_Curr)；//相等时取余数(diff=0){r_Curr。Diff=(S64)(R_Se)-(S64)(R_Curr)；}如果(diff>；0)返回1；返回-1；

计算等待时间，然后乘以(140-t_curr->；PRIO)，其中t_curr是任务。

正常策略中的最高优先级为100，因此等待时间乘以140-100=40。

正常策略中的正常优先级为120，因此等待时间乘以140-120=20。

最低优先级为139，因此等待时间乘以140-139=1。

此计算适用于正常策略中范围为100-139的所有任务。

下面的结果是Cachy和CFS在20次运行中获得的最好结果。有时CFS更快，但在此测试中通常Cachy更快。

Uname-aLinux SUSE 5.7.6-cachy-1-default#1 SMP Fri Jul 24 18：00：47 AEST 2020 x86_64 GNU/Linuxsudo perf stat-e上下文开关、周期、指令、L1-dcache-Load、L1-dcache-Load-Misses、LLC-Load、LLC-Load-Misses、分支。BRANCH-MISSES-A-B STRESS-NG--cpu4-t2m--cpu-method all--metrics-Brief Stress-NG：INFO：[12260]调度猪：4个cpuStress-NG：INFO：[12260]成功运行在120.06秒(2分钟，0.06秒)Stress-ng：INFO：[12260]压力源BOOOP实时用户时间BOOPS/s BOGO OPS/SSEST-NG：INFO：[12260](秒)(实时)(USR+SYS时间)压力-NG：信息：[12260]CPU 87526 120.03 478.67 0.02 729.23 182.84'的性能计数器统计；系统范围'；：36,459上下文开关1,248,551,472,864个周期(62.50%)1,337,471,008,174条指令#1.07 insn/周期(75.00%)133,423,744,677条L1-dcache-Loads(65.93%)12,176,291,467 L1-dcache-Load-未命中#9.13%所有L1-dcache命中(53.11%)2,969,067,073个LLC-Loads(34.21。

Uname-aLinux SUSE 5.7.7-1-default#1 SMP Wed Jul 1 19：03：27 UTC 2020(Cba119b)x86_64 GNU/Linuxsudo perf stat-e上下文开关、周期、指令、L1-dcache-Load、L1-dcache-Load-Misses、LLC-Load、LLC-Load-Misses、分支。BRANCH-MISSES-A-B STREST-NG--cpu 4-t 2M--cpu-method all--metrics-Brief Stress-NG：INFO：[2862]调度猪：4个cpuStress-NG：INFO：[2862]成功运行在120.08秒(2分钟，压力-ng)压力-ng：INFO：[2862]压力源BOOOP实时用户时间BOOPS/s BOGO-OPS/sStress-ng：INFO：[2862](秒)(实时)(USR+SYS时间)压力-NG：INFO：[2862]CPU 86378 120.04 478.73 0.01 719.58 180.43'的性能计数器统计；系统范围'；：31,631上下文开关1,234,757,563,294周期(62.50%)1,320,229,149,505条指令#1.07 INSN/周期(75.00%)131,542,662,029 L1-dcache-Loads(62.32%)12,147,505,410 L1-dcache-Load-未命中#9.23%所有L1-dcache命中(56.44%)4,326,450,020 LLC-Load(40.23