为什么要调度

现在都是做事情做任务的个数要远远多于计算机中处理机的个数，处理机就要合理分配资源给目标，这样才能做到办事效率最大化。

否则就是等一个进程执行完，下一个进程才能执行。而在执行的过程中，会需要一些外设输入或等待其他资源，这个过程是很花费时间的，把这些时间利用起来，去执行其他的进程，这样处理机的利用率就会大大增加。

从层次上来看：

  • 对作业的调度（高级调度）：对后备状态的作业分配资源。发生频率底
  • 对内存的调度（中级调度）：将不运行或不能运行的进程调出内存。发生频率中等。
  • 对进程的调度（低级调度）：对就绪队列中的进程分配处理机资源。发生频率高。

不能进行调度的情况：

（先标记上请求调度的标志，以下情况完成后了回来再进行调度。）

  • 在处理中断的过程中。

    中断处理的过程很复杂，在实现上很难做到进程的调度或切换。

  • 进程在操作系统的内核程序里的临界区中。

    进入到临界区前，理论上要加锁的，在解锁前，处理机不应该切换到其他进程运行。

  • 在原子操作过程中。

    在原子操作过程中，连中断都要屏蔽，更不要说进程的调用或切换了。

比较典型的几个调度算法：

  • 先来先服务： 选择最先进入队列的

    选择最先进入队列的，直到完成了，或阻塞才释放处理机； 属于不可抢占式的。

    对执行时间长的作业或进程有利，对短的不利。短的可能会产生饥饿现象。

    一般是 优先级相同的进程，再判断 先来先服务。

  • 短作业优先： 选择运行时间最短的

    对队列中评估执行时间，选择最短的那个执行。

    对执行时间短的作业或进程有利，对长的不利。长的可能会产生饥饿现象。

  • 优先级调度： 选择优先级最高的

    优先级用于描述作业或进程需要运行的紧急程度。

    有抢占式、也有非抢占式的实现。

  • 高响应比优先： 兼顾等待时间 和 要求服务的时间

    主要用于作业调度。

    结合了 先来先服务 和 短作业优先。

    响应比： （等待时间 + 要求服务的时间） / 要求服务的时间 。

    • 等待时间相同的，服务时间短的优先。 （短作业优先）
    • 服务时间相同的，等待时间长的优先。 （先来先服务）

  • 时间片轮转： 从就绪队列头开始，依次选择每个进程，每次仅能运行一个时间片。

    主要用于分时系统。

    运行进程时，如果时间片完了，该进程还没运行完，该进程就退到就绪队列的尾部。

    如果时间片够大，没次进程都能运行完，就退化成了先来先服务。

  • 多级反馈队列：时间片轮转和优先级调度的结合。

    实现思想：（动态调整 时间片 和 优先级）

    有多个就绪队列，优先级依次降低，时间片依次倍增。

    进来一个进程，放到第一级队列的末尾，按 先来先服务执行。

    到他了，如果执行完了，就完了。如果没有执行完，就到下一级队列的末尾，再按先来先服务。

    只有当上一级队列里 的进程为空时，才能执行下一级队列里的进程。

切换进程的实现：

在切换前要 保存好当时的现场信息，以后再切换回来时，可以找得到原来信息，接着上次的情况继续执行。

这个 现场信息 就保存在 内核里面的堆栈中，在内核里还要维护这个堆栈指针。