一、调度算法的原理和分类
1.进程调度简介
??进程调度的研究是整个操作系统理论的核心，在多进程的操作系统中，进程调度是一个全局性的、关键性的问题，它对系统的总体设计、系统的实现、功能设置以及各方面的性能都有着决定性的影响。进程运行需要各种各样的系统资源，如内存、文件、打印机和最宝贵的CPU等，所以说，调度的实质就是资源的分配。系统通过不同的调度算法(Scheduling Algorithm)来实现这种资源的分配。通常来说，选择什么样的调度算法取决于资源分配的策略(Scheduling Policy)。
??Linux是一个支持多任务的操作系统，而多个任务之间的切换是通过调度器来完成，调度器使用不同的调度算法会有不同的效果。
??Linux2.4版本使用的调度算法的时间复杂度为O(n),其主要原理是通过轮询所有可运行任务列表，然后挑选一个最合适的任务运行，所以其时间复杂度与可运行任务队列的长度成正比。
??而Linux2.6开始替换成名为0(1)调度算法 ，顾名思义，其时间复杂度为0(1)。
??此后，后面的版本开始使用CFS（Completely Fair Scheduler）调度算法。
??Linux的CFS调度器抢占处理器的要求是：新进程消耗的使用比比当前进程小，则新进程立刻投入运行。否则，将推迟进行。
一个好的调度算法应当考虑以下几个方面：
（1）公平:保证每个进程得到合理的CPU时间。
（2）高效:使CPU保持忙碌状态，即总是有进程在CPU上运行。
（3）响应时间:使交互用户的响应时间尽可能短。
（4）周转时间:使批处理用户等待输出的时间尽可能短。
（5）吞吐量:使单位时间内处理的进程数量尽可能多。
?很显然，这5个目标不可能同时达到，所以，不同的操作系统会在这几个方面中作出相应的取舍，从而确定自己的调度算法，例如UNIX采用动态优先数调度、5.3BSD采用多级反馈队列调度、Windows采用抢先多任务调度等。
2.按不同需求对调度的进程分类
第一种分类：
?I/O-bound
??1.频繁的进行I/O
??2.通常会花费很多时间等待I/O操作的完成
?CPU-bound
??1.计算密集型
??2.需要大量的CPU时间进行运算
前者需要更多的IO资源，比如多数的图形交互程序；后者则把时间花在了执行代码上。linux系统为了保证交互式应用和桌面的性能，更倾向于有限调度IO消耗型的进程。
第二种分类
?交互式进程（interactive process）
? ?1.需要经常与用户交互，因此要花很多时间等待用户输入操作
? ?2.响应时间要快，平均延迟要低于50~150ms
? ?3.典型的交互式程序：shell、文本编辑程序、图形应用程序等
?批处理进程（batch process）
? ?1.不必与用户交互，通常在后台运行
? ?2.不必很快响应
? ?3.典型的批处理程序：编译程序、科学计算
?实时进程（real-time process）
? ?1.有实时需求，不应被低优先级的进程阻塞
? ?2.响应时间要短
? ?3.典型的实时进程：视频/音频、机械控制等
? ?对于实时进程，采用FIFO, Round Robin或者Earliest Deadline First (EDF)最早截止期限优先调度算法的调度策略.
? ?Linux既支持普通的分时进程，也支持实时进程，Linux中的调度是多种调度策略和调度算法的混合。Linux的调度基于分时和优先级，随着版本的变化，分时技术在不断变化，优先级越来越复杂。Linux的进程根据优先级排队，根据特定的算法计算出进程的优先级，用一个值表示，这个值表示把进程如何适当的分配给CPU。，Linux中进程的优先级是动态的，调度程序会根据进程的行为周期性的调整进程的优先级，较长时间未分配到CPU的进程，通常优先级被提升，已经在CPU上运行了较长时间的进程，通常优先级被减低。
3.调度算法分类
（1）时间片轮转调度算法
? ? 时间片(Time Slice) 就是分配给进程运行的一段时间。在分时系统中，为了保证人机交互的及时性，系统使每个进程依次地按时间片轮流的方式执行，此时即应采用时间片轮转法进行调度。在通常的轮转法中，系统将所有的可运行(即就绪)进程按先来先服务的原则，排成一个队列， 每次调度时把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms不等。当执行的时间片用完时，系统发出信号，通知调度程序，调度程序便据此信号来停止该进程的执行，并将它送到运行队列的末尾，等待下一次执行。然后，把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证运行队列中的所有进程，在一个给定的时间( 人所能接受的等待时间)内，均能获得一时间片的处理机执行时间。
（2）优先权调度算法
? ? 为了照顾到紧迫型进程在进入系统后便能获得优先处理，引入了最高优先权调度算法。当将该算法用于进程调度时，系统将把处理机分配给运行队列中优先权最高的进程，这时，又可进一步把该算法分成两种方式。
? ? (a)非抢占式优先权算法(又称不可剥夺调度，Nonpreemptive Scheduling) 在这种方式下，系统一旦将处理机(CPU) 分配给运行队列中优先权最高的进程后，该机分配给另一个优先权高的进程。这种调度算法主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。
? ? (b)抢占式优先权调度算法(又称可剥夺调度，Preemptive Scheduling) 该算法的本质就是系统中当前运行的进程永远是可运行进程中优先权最高的那个。在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但是只要一出现了另一个优先权更高的进程时，调度程序就暂停原最高优先权进程的执行，而将处理机分配给新出现的优先权最高的进程，即剥夺当前进程的运行。因此，在采用这种调度算法时，每当出现一新的可运行进程，就将它和当前运行进程进行优先权比较，如果高于当前进程，将触发进程调度。 这种方式的优先权调度算法，能更好的满足紧迫进程的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。Linux 也采用这种调度算法。
(3)多级反馈队列调度
? ?其本质是:综合了时间片轮转调度和抢占式优先权调度的优点，即:优先权高的进程先运行给定的时间片，相同优先权的进程轮流运行给定的时间片。
(4)实时调度
? ?最后我们来看一下实时系统中的调度。什么叫实时系统，就是系统对外部事件有求必应、尽快响应。在实时系统中存在有若干个实时进程或任务，它们用来反应或控制某个(些)外部事件，往往带有某种程度的紧迫性，因而对实时系统中的进程调度有某些特殊要求。在实时系统中，广泛采用抢占调度方式，特别是对于那些要求严格的实时系统。因为这种调度方式既具有较大的灵活性，又能获得很小的调度延迟;但是这种调度方式也比较复杂。
二、调度的时机
? ?进程调度的Linux 的调度程序是一个叫Schedule()的函数，这个函数被调用的频率很高，由它来决定是否要进