2.2.1调度的概念、层次

当一堆任务需要处理时，由于资源有限，这些任务不能同时处理完，就要按照一定的规则来决定一定的顺序来处理这些任务。

调度的层次

• 高级调度(作业调度):当用户打开的作业太多，内存不够了，操作系统会开始调度这些作业，会按照一定的规则从作业后备队列中挑选出一个作业调入内存(建立PCB)，调出时撤销PCB。我的理解:高级调度就是操作系统对外存与内存的调度(面向作业)

• 中级调度(内存调度):当内存不够时，一些暂时没有运行的进程会被调出内存，调到外存去，此时该进程为挂起状态，当内存足够且该进程可以运行的时候，会被调到内存，转变为就绪态，进入就绪队列中。中级调度是为了提高内存利用率和系统吞吐量，中级调度是外存与内存的调度(面向进程)

• 低级调度(进程调度/处理机调度):按照某种规则从就绪队列中选取进程，交给处理机。他是最基本的调度，频率最高,低级调度是cpu与内存的调度

2.2.2 调度的时机切换与方式

狭义进程调度：从就绪队列中选取一个进程

进程切换：一个进程让出处理机，另一个进程占用处理机的过程

广义进程调度包含上边两个步骤

时机

• 需要进行调度的情况：

  • 当前运行的进程主动放弃处理机

  • 进程正常终止

  • 进程发生异常

  • 进程主动请求阻塞

  • 被动放弃

  • 分给进程的时间片用完

  • 有更紧急的事需要处理

  • 有更高优先级的进程进入就绪队列

• 不能进行调度的情况：

  • 在处理中断的时候

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

  • 在原语过程中

方式

• 非抢占方式：只允许进程主动放弃处理机

• 抢占方式：可以优先处理更紧急的任务

进程的切换与过程

进程的切换的过程包含两个步骤：

1. 对原进程各种数据进行保存

2. 对新进程各种数据的恢复

tips： 进程切换是有代价的，所以进程切换不是越频繁越好

2.2.3 调度器和闲逛进程

2.2.4调度算法的评价指标

• CPU利用率：忙碌的总时间/总时间

• 系统吞吐量：总共完成了多少道作业/总共花了多长时间

• 周转时间：作业完成时间-作业提交时间

• 平均周转时间：所有作业周转时间之和/作业数

• 带权周转时间：周转时间/作业执行时间：最小为1,越小越好

• 平均带权周转时间:所有作业的带权周转时间/作业数

• 系统响应时间：作业提交到作业完成的时间

• 等待时间：作业在外存等待CPU服务的时间之和

• 响应时间：从用户提交请求到首次产生响应所用的时间

• 响应比：等待时间/(等待时间+运行时间)

2.2.5常见的调度算法

• 先来先服务(FCFS)：按照作业到达的先后顺序进行调度

  • 特点:非抢占，不会导致进程饥饿

  • 只考虑等待时间而不考虑运行时间

  • 优点：公平

  • 缺点：对长作业有利，对短作业不友好

• 短作业/进程优先算法(SJF/SPF)

  • 非抢占式短作业优先(SJF)：按照当前已经到达的且剩余运行时间的长短来进行调度，时间越少，优先级越高

  • 抢占式短作业优先算法(SRTN):就是在SPF的基础上，每当就绪队列改变时，就会计算正在运行的进程剩余运行时间和当前新进就绪队列进程的运行时间谁短，如果新入队的短，就将新进程抢占处理机

  • 每次调度前选择当前已经到达的且剩余运行时间最短的作业进程

  • 只考虑运行时间而不考虑等待时间

  • 优点：实现最短的平均周转时间和平均等待时间，抢占式是比非抢占更短的，

  • 缺点：对长作业不友好，会导致长进程饥饿

  • tips:题目提到的短作业优先算法是默认非抢占式的

• 高响应比优先(HRRN)：按照作业等待时间和运行时间之和的比值来决定调度顺序

  • 响应比：(等待时间+运行时间)/运行时间

  • 非抢占式。不会导致饥饿

  • 当上一个进程主动放弃CPU时，计算就绪队列中每个进程的响应比，取高响应比的进程上CPU

  • 综合考虑了等待时间和运行时间

  • 优点：适合长作业和短作业，但是需要精确的估计作业的运行时间，否则可能会导致短作业等待时间过长

• 时间片轮转调度算法(RR):按照各个进程到达就绪队列的顺序，轮流让各个进程上cpu上运行一个时间片(ms),如果在在一个时间片内没有完成该进程，则在时间片到点后下处理及，进入就绪队列的队尾，以此类推。

  • 时间片太大和太小都不好，太大会退化为先来先服务算法，太小会频繁切换进程，一般来说，时间片的设计要让切换进程的开销占所有开销的1%以下

  • 可抢占，不会导致饥饿

  • 优点：公平，响应快，适用于分时操作系统

  • 缺点：不区分任务紧急程度，且由于高频率的进程切换，会有一定开销

• 优先级调度：为每个进程分配一个优先级，按照优先级进行调度

  • 优先数越大，优先级越高

  • 优先数相同的，先进就绪队列的先上处理机

  • 非抢占式优先级调度

  • 抢占式优先级调度：同理，每当就绪队列改变时，会比较新入队的进程的优先级和当前正在运行的进程的优先级

  • 优先级分为静态和动态

  • 静态：创建进程后就一直不变

    • 通常：

    • 系统进程优先级高于用户进程

    • 前台进程优先级高于后台进程

    • 操作系统更偏好I/O型进程（或称I/O繁忙型进程）
      注：与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）

  • 动态：有一个初始值，之后会根据情况动态的调整优先级

    • 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级

    • 如果某进程占用处理机运行了很长时间，则可适当降低其优先级

    • 如果发现一个进程频繁地进行/O操作，则可适当提升其优先级

  • 优点：灵活调整各个进程的重要程度

  • 缺点：可能会导致饥饿

• 多级反馈队列调度：

  • 过程：

  1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

  2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时
     间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。
     如果此时已经是在最下级的队列，则重新放回该队列队尾

  3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片(优先处理高级队列的进程)

  • 该算法是对以上调度算法的折中权衡

  • 可抢占,可能会导致饥饿

  

• 多级队列调度算法：该算法在多级反馈队列调度的基础上减去了进程在各个队列来回走的步骤，也就是说，系统会将进程进行优先级分类，各优先级的进程进入各优先级队列中，这时候会有两种分类：固定优先级和时间片划分。一般是用时间片划分，给各个队列分配不同的时间片，然后在各个队列上的进程也可以采用不同的调度算法，

  我的理解：这个相对于多级反馈队列调度：来说，更为阶级固化，每个进程在最开始都被定义好优先级了，而不是像多级反馈队列调度一样，皆平等。