朴素的UNIX之-Linux CFS一个注释

Vecloud

本系列名为朴素的UNIX，但是也包括各个类UNIX系统的细节，本系列文章整理自本人几年来的学习笔记，着重分析各个UNIX，类UNIX的实现思想以及感悟。
本文比较短，只是分析一下Linux CFS调度器的一个细节。
在进程寻找下一个将被运行的进程时，难道仅仅只是在红黑树上取下左下角的进程吗？事实上最朴素的实现就是这样，但是考虑到优化的话，就没有这么简单了。要考虑CPU缓存的利用率，即如果一个进程A抢占了进程B，那么在A进程的上下文中，pick next是选择进程B呢还是选择红黑树的左下角进程呢？另外如果进程A刚被唤醒，企图抢占进程B，但是没有成功，那么下一个是选择红黑树的左下角进程呢还是选择进程A呢？是的，这些都是问题。
我们看一下pick next的实现：

staticstructsched_entity*pick_next_entity(structcfs_rq*cfs_rq){structsched_entity*se=__pick_next_entity(cfs_rq);structsched_entity*left=se;if(cfs_rq->next&&wakeup_preempt_entity(cfs_rq->next,left)<1)se=cfs_rq->next;/**Preferlastbuddy,trytoreturntheCPUtoapreemptedtask.*/if(cfs_rq->last&&wakeup_preempt_entity(cfs_rq->last,left)<1)se=cfs_rq->last;clear_buddies(cfs_rq,se);returnse;}很显然，要把红黑树最左下角的进程和另外两个进程，即next和last最比较，next是抢占失败的进程，而last则是抢占成功后被抢占的进程，这三个进程到底哪一个是最优的next进程呢？Linux CFS实现的判决条件是：
1.尽可能满足需要刚被唤醒的进程抢占其它进程的需求；
2.尽可能减少以上这种抢占带来的缓存刷新的影响。
Linux CFS实现是怎么做到的呢？Linux保存了两个变量，即抢占失败的进程和抢占成功后被抢占的进程，在权衡的时候，优先选择的顺序是：
抢占成功后被抢占的进程>抢占失败的进程>红黑树最左下角的进程

到底能不能选择前两个进程，则是wakeup_preempt_entity函数来决定的，代码太多无益，看下面的图解即可：

这个CFS的细节在Linux 2.6.23最初实现CFS时并没有实现。因此从最朴素的时×××始，你才能逐渐理解细节的来龙去脉，看Changelog是有好处的。不得不说，读史使人明智。