写一个设备的分配与调度简单方案-Linux进程调度：完全公平调度器CFS.pdf

写⼀个设备的分配与调度简单⽅案_ Linux进程调度 ：完全公平 调度器CFS 对于分时操作系统来 ，表⾯上看起来同时多个进程在运⾏，其实系统内部同⼀时间只有⼀个进程在运⾏，但进程是以⽐较快的速度在切 换。这样就引⼊了进程切换和进程调度的概念了。进程调度应该是操作系统的核⼼功能了，它⾮常的复杂。 尽管刚出Linux开发为的是桌⾯操作系统，但现在服务器，嵌⼊式设备，个⼈pc都会使⽤它，不同领域对进程调度的差异⾮常⼤，所以要考 虑整体的平衡性。Linux进程在调度器中被分为三种 ： 1. 交交互互式式进进程程 ：⼤量的⼈机交互，所以会有⼤量的睡眠状态，等待⽤户操作。例如 ：编辑器，这类进程需要⽐较⾼的响应速度。 2. 批批处处理理进进程程 ：这类进程需要⼤量的CPU资源，但是响应延迟可以忍受，⽐如 ：视频编码，算法 ； 3. 实实时时进进程程 ：对调度延迟要求最⾼。⽐如 ：视频播放 在在LLiinnuuxx 中中，，线线程程和和进进程程⼀⼀视视同同仁仁 ，，所所以以讲讲到到进进程程调调度度 ，，也也包包含含 了了线线程程调调度度。。 Linux调调度度器器 的的简简史史 Linux进程调度，有⼀段⾮常有趣的历史。在2.5版本之前，Linux采⽤传统的UNIX调度算法。由于没有考虑到SMP，所以SMP不⽀持。性 能表现就⾮常不好。 所以在后来的2.5版本中，进⾏了⼤改。采⽤了O （1）的算法，之所以O(1)，因为它的运⾏时间是常量，与系统的任务数量是⽆关的。该 调度器增加了对SMP的⽀持。但是在许多的桌⾯交互进程的响应时间却表现不是很好。 在之后的2.6版本中，调度器再⼀次的⼤的改动。2.6.23的版本中，完完全全公公平平调调度度器器 （（CCFFSS））最终成为Linux调度算法。 Linux的进程调度基于调度类。每个调度类都有⼀个特定优先级。每⼀个不同的调度类，都有不同的调度算法，就是为了满⾜不同的需要。 也许⼿机中的Linux和服务器的Linux调度器准则也是不⼀样。 Linux内核有两个调度类 ：CCFFSS和和实实时时调调度度类类。。 CFS CFS 调度程序并不采⽤严格规则来为⼀个优先级分配某个长度的时间⽚，⽽是为每个任务分配⼀定⽐例的 CPU 处理时间。每个任务分配的 具体⽐例是根据nice值来计算的。nice值的范围从 -20 到 + 19，数值较低的nice值表⽰较⾼的相对优先级。具有较低nice值的任务，与具 有较⾼nice值的任务相⽐，会得到更⾼⽐例的处理器处理时间。默认nice值为 0。 为为什什么么叫叫nniiccee？？当当⼀⼀个个任任务务增增加加 了了它它的的nniiccee，， 明明它它的的优优先先级级降降低低 了了，，进进⽽⽽对对其其他他任任务务变变得得nniiccee CFS 调度程序没有直接分配优先级。相反，它通过每个任务的变量 vruntime 以便维护虚拟运⾏时间，进⽽记录每个任务运⾏多久。虚拟 运⾏时间与基于任务优先级的衰减因⼦有关，更低优先级的任务⽐更⾼优先级的任务具有更⾼衰减速率。对于正常优先级的任务 （nice值为 0），虚拟运⾏时间与实际物理运⾏时间是相同的。下⾯分析⼀下 CFS 调度程序是如何⼯作的。 假设有两个任务，它们具有相同的nice值。⼀个任务是 I/O 密集型⽽另⼀个为 CPU 密集型。通常，I/O 密集型任务在运⾏很短时间后就会 阻塞以便等待更多的 I/O ；⽽ CPU 密集型任务只要有在处理器上运⾏的机会，就会⽤完它的时间⽚。 因此，I/O 密集型任务的虚拟运⾏时间最终将会⼩于 CPU 密集型任务的，从⽽使得 I/O 密集型任务具有更⾼的优先级。这时，如果 CPU 密集型任务在运⾏，⽽ I/O 密集型任务变得有资格可以运⾏ （如该任务所等待的 I/O 已成为可⽤)，那么 I/O 密集型任务就会抢占 CPU 密 集型任务。 实实时时调调度度 采⽤ SCHED_FIFO 或 SCHED_RR 实时策略来调度的任何任务，与普通 （⾮实时的）任务相⽐，具有更⾼的优先级。 Linux 采⽤两个单独的优先级范围，⼀个⽤于实时任务，另⼀个⽤于正常任务。实时任务分配的静态优先级为 0〜99，⽽正常任务分配的 优先级为 100〜139。 这两个值域合并成为⼀个全局的优先级⽅案，其中较低数值表明较⾼的优先级。正常任务，根据它们的nice值，分配⼀个优先级 ；这⾥ -20 的nice值映射到优先级 100，⽽ + 19 的nice值映射到 139。下图显⽰了这个⽅案。 CFS 性性 能能 Lin