1。任务切换现在有一个CPU，但是要执行两个程序，我们需要开发一个任务调度器。只有两个程序，soeasy！让他们交替执行即可。为了实现切换，我们提供了一个API，一段时间后两个程序会主动调用这个API，然后在这个API内部实现任务切换。所谓切换，其实就是将当前进程的上下文（也就是CPU的一堆寄存器值）保存到进程的TCB（进程控制块，每个进程对应的内存数据结构）中.然后在另一个进程TCB中加载上下文寄存器的值，开始运行。这是一种主动协作的调度。2.抢先然而，理想很美好，现实却很骨感。这些程序可能不会那么听话，可能会长时间不调用我们的API交出CPU，甚至造成死循环，另一个程序永远没有机会执行。看来不能靠程序来交出执行权，调度器需要有抢占CPU的能力！如何抓住它？我们可以利用时钟中断！因为一旦中断事件到来，CPU就不得不执行中断处理程序。只要在时钟中断的处理函数中增加一个调度入口，就可以抢占CPU的执行权。为了公平起见，我们决定让每个进程执行一小段时间。我们称这个时间片为100ms，然后依次执行。看起来像这样：我们将CPU编程为每1毫秒发送一次。时钟中断。每次时钟中断到来时，检查当前线程运行时间是否足够100ms，如果不够，则将当前线程的运行时间增加1ms，然后中断处理结束，让它继续运行。如果检查发现时间已经到了100ms，则切换到另一个进程运行。100ms几乎是人察觉不到的，所以我以为是两个线程同时运行。一个最简单的任务调度器就完成了。3、阻塞进程逐渐多了，3、4、5……我们用一个队列来存放它们，先进先出，叫做就绪队列，意思是准备好排队等待执行的队列。所有就绪的进程依次排队等待我们的调度程序执行。没过多久我们就发现，有些进程经常占厕所，在休眠或者等待锁的时候，白白占用CPU闲置，导致队列中的其他进程报错。那么我们再对调度器做一个优化：当有进程在等待锁、I/O等待或者休眠时，调度器也需要介入，即使分配给它的时间片还没有用完，也必须主动交了。出CPU，放入另一个等待队列，等待满足等待条件，再返回就绪队列。现在，我们的调度程序不再允许CPU猪钓鱼。4.优先级后来进程数进一步增加，6,7,...,100。每个进程执行100ms，转一圈需要10000ms=10s。打字程序只有在按下键盘10秒后才会做出反应。系统卡死，几乎无法使用。我们可以把每个进程的执行时间缩短到10ms，反过来变成1000ms=1s。情况好多了，但还是有点卡。而且，不停的进程越来越多，200个、300个，甚至更多，绕一圈的时间还是越来越长。但是继续压缩时间也不好，否则过多的时间会花在切换上，实际执行时间会减少。问题归根结底是进程太多后，按顺序轮换不合适。有些进程必须有VIP权限，可以优先执行。这个怎么样，给每个进程设置一个优先级，从1到40，一共40个优先级，数字越大，优先级越高。调度时遍历队列，找到优先级最高的进程执行。现在，我们只需要将输入程序等交互过程设置为高优先级，再次按下键盘后，很快就会得到响应。5.O(1)复杂度每次调度都要遍历所有进程，这个复杂度是O(N)。进程少点无所谓，但是多了就有点烦了，效率太低了。将所有进程排在一个大队列中并不是明智的做法。要不我们按照优先级拆分成不同的队列吧！每个优先级都有一个单独的就绪队列，也就是40个队列，他们单独排队，查找效率更高。调度时，按照优先级顺序依次检查各个队列，看是否有进程可以执行。找到后，将其从队列中取出执行。队列中具有相同优先级的进程将依次执行。为了快速知道每个优先级队列中是否有进程，我们再做一个位图，40位，每个位代表一个优先级队列，如果为1，我们就知道这个优先级队列中有一个进程需要执行，因为0没有任何意义。关于这个优先级队列，可以这样定义：structpriority_queue{intnr_active;//所有队列中的进程总数unsignedlongbitmap[BITMAP_SIZE];//位图结构list_headqueue[MAX_PRIO];//队列数组};现在找起来很方便，不管进程有多少，都可以在O(1)的时间复杂度内找到要调度的进程。6、饥饿问题系统运行一段时间后，发现一个重要的问题：由于高优先级进程的存在，低优先级的程序很难得到执行的机会，而且是容易被“饿死”。除非高优先级进程执行完毕，或者正在休眠等待，否则只要它还停留在就绪队列中，其他进程就没有机会了。这不行，虽然你的优先级很高，但你也得给别人吃的。好像流程执行完后，不能立马放回原来的队列，必须等这一轮大家都执行完了才执行。如果不放回原来的队列，应该放在哪里呢？简单地得到另一个优先级队列，称它为过期队列，并将原来的优先级队列称为活动队列。调度时，进程从活动队列中提取。完成一个调度后，放入expired队列，等待原队列中的进程一个一个执行完，active队列会为空，都来到expired队列，然后交换两个队列，启动所有再次。好吧，为了避免内存复制。把active和expired定义成指针，到时候直接交换两个指针，省事！封装原始队列：structrunqueue{structpriority_queue*active;structpriority_queue*已过期；结构priority_queue数组[2];};这样，所有的进程都在两个队列里转了一圈，现在也有低优先级的进程得到了满足的机会，不会被饿死。7.优先级和时间片目前为止，进程虽然有优先级，但这只影响其调度顺序，不影响其执行时间。所有进程时间片仍然是100ms。现在，高优先级的程序抗议：我执行的任务很重要，需要给我更长的CPU时间片！于是，一个新的需求来了：不同优先级的进程需要有不同的运行时间片。如果优先级高，时间片要长一些；如果优先级低，时间片应该更短。这个要求很容易处理。基于中间优先级20，我们将优先级为20的进程的时间片设置为100ms。优先级每升高1级，时间片为+5ms，每降低一级，时间片为-5ms。.Priority----timeslice15ms210ms315ms...1890ms1995ms20100ms#base21105ms...39195ms40200ms现在，高优先级的进程不仅可以先执行，而且分配的运行时间也更多。上面的时间片分配算法并不完美，它有一个问题：如果现在只有两个优先级为20和21的进程在运行，时间片分别为100ms和105ms，那么这两个进程分别可以获得的CPU时间比例为100/(100+105)=48.7%和105/(100+105)=51.2%。优先级增加1，CPU时间增加2.5%，貌似没什么问题。现在如果只有优先级为1和2的两个进程在运行，时间片分别为5ms和10ms，那么这两个进程分别可以获得的CPU时间比例为5/(5+10)=33.3%和10/(5+10)=66.7%。优先级2只比优先级1进程高一个级别，获得的CPU时间比例翻了一倍！优先级也增加了1，为什么差距这么大？公平呢？8.公平调度：时间分配现在，让我们换个思路，用相对时间片代替绝对时间片。比如我们的调度周期设置为100ms。这100ms被分配给所有可以运行的进程。100ms后，所有就绪进程循环执行。那么问题来了，如何让进程来瓜分这100ms呢？当然是按优先级划分的。我们为不同优先级的进程设置不同的权重。优先级高则权重值高，权重值多。优先级越低，权重值越小。权重值设置多少为好？不用着急，已经有人帮我们想好了，就是下面这个数组。很难想知道为什么是这些数字而不是其他数字，但我们不要担心。constintsched_prio_to_weight[40]={88761,71755,56483,46273,36291,29154,23254,18705,14949,11916,9548,7620,6100,4904,3906,3121,2501,1991,1586,1277,1024,820,655,526,423,335,272,215,172,137,110,87,70,56,45,36,29,23,18,15,};现在，每个进程对应自己的优先级Weight，从100ms的调度周期开始分配时间。不知道大家有没有注意到，如果进程太多，分配的时间可能会很少。我们要设置一个最小值，否则每天都去调度切换，实际执行的时间会少一些。这个最小值意味着进程在切换之前至少要运行这么长时间。9、公平调度：解决了进程选择时间分配的问题，还有一个问题：调度时，如何选择下一个要执行的进程？我们已经按照权重给每个人分配了时间，但是一定有一些进程因为I/O、锁、睡眠等原因没有用完分配的时间。这些过程应该得到补偿。一旦满足执行条件，就应该优先执行。自愿放弃CPU的进程运行的时间必须少于分配的时间。或者，将进程按照运行时间排序，选择运行时间最短的进程运行？但是，不同的进程有不同的优先级，分配的时间也有自己的长短。如果能消除权重导致的时间分配不均的问题，用运行时间来排序就好了。我们再做一次虚拟运行时间并恢复重量的影响怎么样？例如，一个高优先级的进程会分配很多时间。在计算它的运行时间时，让它慢慢过去。低优先级的进程分配的时间少，在统计它的运行时间的时候，让它通过的快一些。这样，当所有进程都没有任何sleep、wait、I/O时，每个人都用完了自己的时间，去掉权重后的虚拟时间应该是一样的，是整个的1/N调度周期！这才叫公平！现在只需要按照虚拟时间对所有进程进行排序，前面的虚拟时间短，调度的时候会选择运行。好主意，应该用什么样的数据结构来组织管理过程呢？大批？插入不方便。链表？找到插入位置的时间复杂度是O(N)。使用二叉搜索树似乎是一个很好的解决方案。左节点的虚拟时间小于父节点和右节点的虚拟时间。只要找到最左边的节点，就是要调用的过程，时间复杂度为O(LogN)。但是二叉搜索树有问题。一不小心，很容易变成“跛脚”树，时间复杂度又会增加。红黑树不存在这个问题，它有自己的平衡，或者就是它！根据虚拟时间，将所有要运行的进程组织成一棵红黑树，只要找到整棵树最左边的节点就是要运行的进程。但是为了更高效，当树的调整更新导致最左边的节点发生变化时，应该缓存起来，这样在调度的时候可以直接获取到缓存节点。完美的！综上所述，上面介绍的进程调度模型其实就是Linux中O(1)调度算法和CFS(CompletelyFairSchedulingAlgorithm)调度算法的雏形。为了便于理解，文中进行了一定程度的简化。包括但不限于：在实际的Linux中，有140个进程优先级，分为实时进程和非实时进程。在实际的Linux中，一个进程通过一个叫做nice值的东西映射到一个优先级（对其他进程的友好程度，nice越大，越友好，越谦虚，优先级越低）。优先级数字越大，优先级越高，反之则越低。在实际的Linux中，一个进程的优先级分为静态和动态，会随着运行而变化，并不是固定不变的。在多核模式下，为了防止加锁带来的性能损失，每个CPU核都有自己的调度队列。在实际的Linux中，参与调度的是线程，而不是进程。但是早期的linux没有线程的概念，调度是基于进程的。引入线程后，线程也被称为轻量级进程。现在我们通常说进程和线程在语义上是不同的，要注意区别。看完这篇文章，再看Linux的调度算法应该就容易多了。
