概述

cpu调度是多任务操作系统的基础，目的是使cpu尽可能用于执行指令，提高效率。因为进程间存在竞争，需要OS选择一个进程来进行状态的转换，这个过程就叫做cpu调度。

• 长程调度
  • "道"：内存中所允许运行的最大进程数目。由于资源有限，所以并不是每个用户创建的进程都能立刻被载入内存运行。
  • 每个用户创建的进程开始处于new状态，他首先被放到外存的进程池中，当内存中进程数量没达到上限时，操作系统的调度程序才从new状态选择一个进入内存，并转化为ready。从new->ready的操作就叫做长程调度，又称作业调度或者高级调度。可调度后备队列。
• 短程调度
  • 又称为cpu调度或低级调度，在就绪队列中可能不止一个进程，在cpu空闲时，操作系统需要从就绪队列中挑选一个进程让他运行。这个操作就叫短程调度，又叫进程调度，即ready-->running。可调度就绪队列、阻塞队列、挂起队列
• 中程调度(交换)
  • 从本质上讲，他不属于进程管理的范畴，而属于内存管理。简而言之，中程调度就是一个进程在内存和外存之间的换进换出。目的是节省内存。可调度就绪队列和阻塞队列
• 调度队列
  • 为了方便进行cpu调度，操作系统需要对不同状态的进程进行组织和管理。为此设置了调度队列，主要有就绪队列和设备队列。所有设备队列中的进程都是处于等待状态(在哪个设备队列，就在等待哪个设备)。

调度过程

• 调度过程由OS的两个部件完成，即调度程序和分派程序。
• 调度程序 根据某种策略选择内存中的一个就绪进程
• 分派程序 负责具体的进程切换工作
  • 具体过程如下，1) 利用定时器把cpu的控制权转交给cpu调度程序，让调度程序选择一个需要运行的进程；2) 进行进程状态切换，ready-->running。3) 系统切换到用户态，跳转到用户程序的适当位置重新运行。
• cpu调度存在系统开销。分派延迟----分派程序终止一个进程运行，并启动另外一个进程运行所花的时间。

cpu调度方式

• 常用的方式有2种，抢占和非抢占。
• 非抢占，cpu一旦分配给某个进程，就只能等该进程运行结束，或者该进程资源让出cpu(如java中的Thread.yield())，他实现简单，适合批处理系统。但是其响应时间长，不适合交互时系统。
• 抢占，调度程序可自由回收分配cpu，可以防止单一进程长时间独占cpu
• 二者最大区别在于是否自愿放弃cpu

cpu调度的时机

• 运行转换到等待(非抢占，比如要进行IO，该进程就会主动放弃cpu)
• 运行转换到就绪(抢占，由于OS把cpu分配给别的进程了)
• 终止(非抢占，即某个进程运行完毕)
• 等待转换到就绪(抢占，如就绪队列中的某进程优先级高，那他就会抢占正在运行进程的cpu)
• 调度的时机不止上述几种。

cpu脉冲周期

• cpu调度的核心是提高cpu的效率，如何来衡量呢？常用指标有：
  • cpu利用率，即固定时间内cpu使用时间的比率
  • 吞吐量，单位时间内运行完的进程数
  • 周转时间，进程从提交到运行结束的时间
  • 等待时间，进程等待调度的时间片总和
  • 响应时间，从进程提交到首次运行的时间
  • 其中周转时间 = 等待时间 + 运行时间

为了达到cpu调度的高利用率、高吞吐量、低时间消耗，需要具体的调度算法。以下所有调度算法都是单核单处理器情况下的调度。

调度算法1---适用于长程调度(作业调度)

• 从外存new状态，load到就绪队列的过程
• 先来先服务调度(FCFS):按进程请求CPU得先后顺序
  • 实现简单，可用FIFO队列实现
  • 属于非抢占调度
• 短作业优先调度(SJF)
  • 非抢占式
  • 抢占式 当有比当前进程剩余时间片更短的进程到来时，新来的进程将抢占当前进程获得cpu运行。它也被称为最短剩余时间优先，SRTF，Shortest rest time first。
  • 优点是平均等待时间最小，缺点是存在饥饿问题。
  • 其难点在于如何知道进程下一个CPU区间的长度

调度算法2---适合于短程调度（进程调度）

• 优先级调度算法（PR）
  • 为每个进程分配优先级，就绪队列的排队策略是优先级高的在前，低的在后。优先级可以是动态或者静态(容易导致饥饿问题)的。PR算法同样分为两种。
  • 抢占式 高优先级对cpu进行抢占
  • 非抢占式
• 时间片轮转调度算法(RR)
  • 专门为分时系统设计，类似于FCFS，但增加了抢占。其原理是把一段时间分成若干碎片，每个需要运行的进程获得一个碎片运行，也就是在这段时间内，每个进程都得到运行。他能满足对响应时间的要求，算法首先定义一个小单位的cpu时间，如10-100ms，称为时间片。调度时将就绪队列作为循环队列，为每个进程分配不超过1个时间片的cpu，时间片用完后，进程就插入就绪队列的末尾。一般其平均等待时间长，平均响应时间短。其性能很大程度上依赖时间片的大小。时间片很大时，RR等同于FCFS。时间片如果很小，又等同于共享处理器，进程之间的切换频繁，增加了系统开销。

调度算法3

• 上面介绍的算法都有各自的局限，不能适用于不同类型的进程。
• 多级队列调度(MLQ)
  • 针对不同进程使用不同的调度算法，其做法是允许系统中存在多个就绪队列，每个就绪队列有自己的调度算法。如Windows种设置前台和后台服务哪个优先的选项。
  • cpu空闲时，选哪个队列的哪个进程呢？可以固定优先数
• 多级反馈队列调度(MLFQ)
  • MLQ中，进程不能在不同就绪队列间移动。MLFQ则可以移动。

• 多处理器架构有两种，SMP(对称多处理器)和ASMP(非对称多处理器)
• 他需要额外考虑2点，负载均衡(即如何将任务平分给不同的处理器)和亲和性(进程在某个给定的cpu上尽可能的长时间运行，而不被迁移到其他处理器的倾向，处理器迁移一般需要对数据进行同步，产生额外开销。)
• 常用调度方法有2种，
  • 单队列调度：系统有一个就绪队列，当任意一个cpu空闲时，就从就绪队列中选择一个进程到该cpu上运行。优点是实现简单，容易从单核推广到多核；缺点是1)不具有亲和性，一个进程可能在不同时间被调度到不同cpu。2)多核同时访问一个队列，会有加锁的问题，从而严重影响调度的性能。
  • 多队列调度：系统由多个就绪队列，一般一个cpu一个，每个就绪队列有自己的调度算法，各个队列的调度相对独立。优点是亲和性好、不需要加锁。缺点是负载可能不均衡(一个解决策略是偷进程，一个负载较低的cpu会定时的偷看一下其他cpu就绪队列中的负载情况，从而选择性的偷取进程。这样能使得各个cpu的负载相对比较均衡)。