单核与多核的cpu调度算法.docx免费

1. 多核CPU调度算法 1.1全局队列调度算法 操作系统维护一个全局的任务等待队列，每个进程在执行阶段可以使用全部的处理器资源。当系统中有一个CPU核心空闲时，操作系统就从全局任务等待队列中选取Ready进程开始在此核心上执行。 优点：CPU核心利用率较高，能保证全局资源的充分利用。 缺点：多处理器同时查找工作时，可能会降低处理器效率。且同一进程可能在不同内核上执行，造成的进程迁移开销较大。 1.2局部队列调度算法 操作系统为每个CPU内核维护一个局部的任务等待队列，将所有进程分配到与处理器对应的进程队列中。当系统中有一个CPU内核空闲时，便从该核心的任务等待队列中选取恰当的任务执行。 优点：充分利用局部缓存，降低了进程迁移的开销。任务基本上无需在多个CPU核心间切换，有利于提高CPU核心局部Cache命中率。目前多数多核CPU操作系统采用的是基于全局队列的任务调度算法。 缺点：可能造成某些处理器超负荷，而某些处理器空闲，即资源分配不均衡不充分，引起全局资源的不充分利用。 2. 简单单核CPU调度算法 2.1 先到先服务调度算法：FCFS（first-come,first-served） 当一个进程进入到Ready队列，其PCB就被链接到队列的尾部。当CPU空闲时，CPU被分配给位于队列头的进程（即当前Ready队列中已等待时间最长的进程）。接着，该运行进程从队列中被删除。 缺点：对于一个进程队列，其总的周转时间太长，且当进程的I/O较为密集时，效率将会变得相当低，CPU利用率也会变得很低。 优点：实现方式简单，适用于长程调度和处理器密集的进程调度。常与优先级策略结合提供一种更有效率的调度方法。 2.2 最短作业优先调度算法：SJF（shortest-job-first） SJF是一种非抢占式的调度算法，其实现原则是取Ready队列中处理时间最短的进程加载入CPU，进入CPU执行的进程执行完后才释放CPU，然后加载第二个进程进入CPU执行。 缺点：忽视了作业等待时间，会出现starvation现象，且作业执行时间无法提前知道，也很难预估。 优点：算法实现简单，能有效地降低作业的平均等待时间，提高系统吞吐量，是理论上的最优调度算法。 2.3 最短剩余时间优先调度算法：SRTF（Shortest Remaining Time First） SRTF调度算法是抢占式的SJF调度算法，调度程序总是首先选择预期剩余时间最短的进程加载进入CPU执行。 缺点：总是选择预期剩余时间最短的进程，会造成starvation现象。有处理时间预估，效率不足够高。 优点：不偏向长进程，没有额外的中断，因此开销较低。且对于一个进程队列，总的周转时间较短，执行效率较高，对短进程的响应较快。 2.4 优先级调度算法 每个进程都有一个自己的优先级，Ready队列采用优先级队列实现，CPU每次取Ready队列队首的进程。通常情况，当两个进程的优先级相同时，我们在相同优先级的进程之间采用FCFS调度算法。优先级可以通过内部或外部方式来定义。 缺点：会出现starvation现象（也称无穷阻塞），且不适用于分时系统或交互式事务处理环境。 优点：主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。可以采用老化技术，每个进程执行以后其优先级降低，以此来克服starvation的缺点。 2.5 轮转法调度算法 轮转法（RR）调度算法是专门为分时系统设计的，是一种基于时钟的抢占策略。定义一个小时间单元，称为时间量或时间片。时间片通常为10ms到100ms。将Ready队列作为循环队列处理。CPU调度程序循环就需队列，为每个进程分配不超过一个时间片间隔的CPU。如果上下文切换时间约为时间片的10%，那么约10%的CPU时间会浪费在上下文切换上。 缺点：时间片长度设计较难，当时间片长度过大时，会退化成FCFS调度算法。调度I/O密集型进程时效率较低。由于轮询调度在调度过程中不考虑瞬时信道条件，因此它将导致较低的整体系统性能。 优点：对不同的分组业务流队列进行同样的无差别的循环调度服务，对于等长业务流队列是公平的，不存在starvation现象。 2.6 最高响应比优先调度算法 首先需要理解一个概念，叫作响应比。响应比的计算表达式为 R 其中R为响应比，w为等待处理器的时间，s为预计服务的时间。当进程被立即调用时，R等于归一化周转时间。 调度算法的过程是，当进程完成执行或被阻塞时，选择R值最大的Ready进程加载进入CPU执行。 缺点：需要预估服务时间s，效率不太高。 优点：能克服starvation现象。 3. 复杂单核CPU调度算法 3.1 多级队列调度算法（multilevel queue-scheduling algorithm） 将Ready队列分成多个独