单核与多核的CPU调度算法

1、多核CPU调度算法1.1全局队列调度算法操作系统维护一个全局的任务等待队列，每个进程在执行阶段可以使用全部 的处理器资源。当系统中有一个CPU核心空闲时，操作系统就从全局任务等待队 列中选取Ready进程开始在此核心上执行。优点：CPU核心利用率较高，能保证全局资源的充分利用。缺点：多处理器同时查找工作时，可能会降低处理器效率。且同一进程可能 在不同内核上执行，造成的进程迁移开销较大。1.2局部队列调度算法操作系统为每个CPU内核维护一个局部的任务等待队列，将所有进程分配到 与处理器对应的进程队列中。当系统中有一个CPU内核空闲时，便从该核心的任 务等待队列中选取恰当的任务执行。优点：充分利用

2、局部缓存，降低了进程迁移的开销。任务基本上无需在多个 CPU核心间切换，有利于提高CPU核心局部Cache命中率。目前多数多核CPU操 作系统采用的是基于全局队列的任务调度算法。缺点：可能造成某些处理器超负荷，而某些处理器空闲，即资源分配不均衡 不充分，引起全局资源的不充分利用。简单单核CPU调度算法2.1 先到先服务调度算法：FCFS (first-come,first-served )当一个进程进入到Ready队列，其PCB就被链接到队列的尾部。当CPU空闲 时，CPU被分配给位于队列头的进程(即当前Ready队列中已等待时间最长的进 程)。接着，该运行进程从队列中被删除。缺点：对于一个进

3、程队列，其总的周转时间太长，且当进程的I/O较为密集 时，效率将会变得相当低，CPU利用率也会变得很低。优点：实现方式简单，适用于长程调度和处理器密集的进程调度。常与优先 级策略结合提供一种更有效率的调度方法。2.2最短作业优先调度算法：SJF (shortest-job-first)SJF是一种非抢占式的调度算法，其实现原则是取Ready队列中处理时间最 短的进程加载入CPU，进入CPU执行的进程执行完后才释放CPU，然后加载第二 个进程进入CPU执行。缺点：忽视了作业等待时间，会出现starvation现象，且作业执行时间无 法提前知道，也很难预估。优点：算法实现简单，能有效地降低作业的平

4、均等待时间，提高系统吞吐量， 是理论上的最优调度算法。2.3最短剩余时间优先调度算法：SRTF (Shortest Remaining Time First)SRTF调度算法是抢占式的SJF调度算法，调度程序总是首先选择预期剩余 时间最短的进程加载进入CPU执行。缺点：总是选择预期剩余时间最短的进程，会造成starvation现象。有处 理时间预估，效率不足够高。优点：不偏向长进程，没有额外的中断，因此开销较低。且对于一个进程队 列，总的周转时间较短，执行效率较高，对短进程的响应较快。2.4优先级调度算法每个进程都有一个自己的优先级，Ready队列采用优先级队列实现，CPU每 次取Ready队

5、列队首的进程。通常情况，当两个进程的优先级相同时，我们在相 同优先级的进程之间采用FCFS调度算法。优先级可以通过内部或外部方式来定 义。缺点：会出现starvation现象（也称无穷阻塞），且不适用于分时系统或交 互式事务处理环境。优点：主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统 中。可以采用老化技术，每个进程执行以后其优先级降低，以此来克服 starvation 的缺点。2.5轮转法调度算法轮转法（RR）调度算法是专门为分时系统设计的，是一种基于时钟的抢占策 略。定义一个小时间单元，称为时间量或时间片。时间片通常为10ms到100ms。 将Ready队列作为循环队列处理。

6、CPU调度程序循环就需队列，为每个进程分配 不超过一个时间片间隔的CPU。如果上下文切换时间约为时间片的10%，那么约 10%的CPU时间会浪费在上下文切换上。缺点：时间片长度设计较难，当时间片长度过大时，会退化成FCFS调度算 法。调度I/O密集型进程时效率较低。由于轮询调度在调度过程中不考虑瞬时信 道条件，因此它将导致较低的整体系统性能。优点：对不同的分组业务流队列进行同样的无差别的循环调度服务，对于等 长业务流队列是公平的，不存在starvation现象。2.6最高响应比优先调度算法首先需要理解一个概念，叫作响应比。响应比的计算表达式为其中R为响应比，w为等待处理器的时间，s为预计服务的

7、时间。当进程被立即 调用时，R等于归一化周转时间。调度算法的过程是，当进程完成执行或被阻塞时，选择R值最大的Ready 进程加载进入CPU执行。缺点：需要预估服务时间s，效率不太高。优点：能克服starvation现象。复杂单核CPU调度算法3.1多级队列调度算法 （multilevel queue-scheduling algorithm）将Ready队列分成多个独立的队列，对Ready队列和每个独立的队列采用不 同的调度算法进行执行。常用的方式是，Ready队列采用优先级调度算法，不同 队列根据实际情况采用合适的调度算法即可。优点：综合了多种调度算法，避免了 starvation现象，最大

8、限度地提高了 调度效率，也提高了 CPU利用率。3.2多级反馈队列调度算法UNIX OS采用的调度算法。其详细过程如下：进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程， 则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进 程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间 片为N，那么Q1中的作业在经历了 N个时间片后若还没有完成，则进入Q2队列 等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这 个时间片后，CPU马上分配给新到达的作业（抢占式）。优点：既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。多核CPU调度算法与单核CPU调度算法对比从上面的不同CPU调度算法，我们不难发现，单核CPU调度算法是多核CPU 调度算法的基础，多核CPU调度算法是单核CPU调度算法的延伸和综合使用。我 以大篇幅介绍了单核CPU的调度算法，而以少量的篇幅介绍了多核CPU调度算