操作系统】 2.2 调度概念以及调度算法

@[toc]

1.调度的概念

:star: 调度：在同一时刻，有很多任务需要处理，由于资源有限，这些事情没法同时处理。处理机会以某种规则来决定处理这些任务的顺序。

2.调度的三个层次

:star: 高级调度：由于内存优先，有时无法将用户提交的作业全部放入内存，所以需要调度，高级调度就是按照一定的规则从外村的作业后备队列种挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次，所以发送的频率很低。作业调入时会建立PCB，调出时才撤销PCB。

:star2: 低级调度：内存种存在很多进程，但CPU资源有限，所以不可能同时运行这么多进程。低级调度（处理机调度）就是按照某种策略从就绪队列种选取一个进程，将处理及分配给它。进程调度时操作系统种最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一半几十毫秒一次。

:star2: 中级调度：当内存不足时，可将某些进程的数据调出外村，等内存空闲或者进程需要运行时在重新调入内存。展示调到外存等待的状态为挂起状态，被挂机的进程PCB会被组织成挂起队列。当内存充足时，中级调度（内存调度）就会按照某种策略绝对将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出，调入内存。因为中级调度发送的频率要比高级调度高。

:chestnut: 我们使用手机时经常会出现这样一种情况：有时候切换程序切换的很快，有时候很慢。很快可能是因为程序就在内存当中，很慢可能是因为进程已经被调出内存了，调入回来还需要时间。

3.七状态模型

:hourglass_flowing_sand: 就绪态--就绪挂起：一个处于就绪态的进程，如果此时内存不够用了，那么可能就会被操作系统给转移到外存去，加入到就绪挂起队列中。如果内存够了，或者这个进程急需处理，那么又会被调入内存中，变为就绪态。

:sweat_drops: 阻塞态--阻塞挂起 ：阻塞态的进程是仍然在内存中的，如果此时内存不够用了，可能就把它调入外存，加入到阻塞挂起队列中，内存够了可能就会被调回内存中，变为阻塞态。

:tent: 阻塞挂起--就绪挂起 ：如果处于阻塞挂起的进程已经获得了它想要的资源或服务，那么就会直接调入就绪挂起队列中，等待内存资源。

:rabbit: 运行态--就绪挂起 ：一个正准备下处理机的进程，由于资源不够，可能会直接调入到外存的就绪挂起队列中，不用在经过就绪态。

4.三层调度的联系和对比

5. 进程调度的时机

:swimming_man: 进程调度：就是按照某种规则从就绪队列中选择一个进程为其分配处理机。

:ice_cream: 需要进程调度与切换的情况

• 主动放弃处理机

  • 进程正常终止
  • 运行过程中遇到了一次而终止
  • 进程主动请求阻塞（如等待 I/O)

• 被动放弃处理机

  • 分配进程的时间片用完了
  • 有更紧急的事需要处理（如 I/O 中断）
  • 有更高优先级的进程进入就绪队列

:dog: 不能进程调度与切换的情况

• 在处理中断的过程中，中断处理过程很复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。（家里正在修热水器呢，你却非要把电闸开开要做其他事？）
• 进程在操作系统的内核程序临界区中。
• 在原子操作过程中，原子操作不可中断，要一气呵成。（此时如果你非要中断去做其他事不就坏事了吗）

:ear_of_rice: 操作系统的临界区

:grey_question: 进程在操作系统内核程序临界区中不能进行调度与切换，但程序在临界区中能进行处理机调度。这是为啥呢？

:star: 临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源。实现对这种资源的共享。

:star: 临界区：访问临界资源的那段代码，每次只允许一个进程进入临界区，进入后就不允许其他进程进入。使用临界区时，一般不允许其允许时间过长，只有临界区中有进程，那么其他进入此临界区的进程都会被挂起而进入等待状态，并在一定程度上影响程序的运行性能。

:star: 内核程序临界区：用来访问某种内核数据结构的，比如进程的就绪队列。

:sailboat: 进程访问内核程序临界区：进程如果访问就绪队列这种临界区的话，为了实现互斥访问，就会将就绪队列上锁，不允许其他进程访问，如果此时进行进程调度，那么临界区还没有解锁，切换的进程也要访问临界区就没有办法访问，所以也没有办法进行进程调度。内核程序临界区访问你的临界资源如果不尽快释放的话，既有可能影响到操作系统内核的其他管理工作，因此在访问内核程序临界区期间不能进行调度与切换。（操作系统内核程序都非常重要，耽误不得，一个进程切换和调度都要花费时间，其他程序都要等着，所以每个进程都要快速处理）

:lantern: 进程访问普通程序临界区：比如一个进程想要使用打印机资源，那么就会给打印机上锁，不允许其他进程使用，但是打印机这种设备速度很慢，为了让CPU不要闲着，就可以进程调度和切换。因为普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。

6.进程调度的方式

:star2: 非剥夺调度方式 ：又称非抢占式，只允许进程主动放弃处理机，在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。特点：实现简单，系统开销小，但是无法及时处理紧急任务，适合于早期的批处理系统。

:star2: 剥夺式调度方式 ：又称抢占式，当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的进程。特点：可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断），适合分时操作系统、实时操作系统。

7.进程的切换与过程

:star: 狭义的进程调度：是指从就绪队列中选中一个要运行的进程（这个进程可以时刚刚被暂停执行的进程，也可以是另一个进程），如果切换另一个进程就需要进程切换

:star: 进程切换：指一个进程让出处理机，由另一个进程占用处理机的过程。

1. 对原来运行进程各种数据的保存（保护现场）
2. 对新的进程各种数据的恢复（恢复现场），包括程序计数器，程序状态字，各种数据寄存器等出理解现场信息，这些信息一半都保存在进程控制块）

:star: 广义的进程调度：包含了选中一个进程和进程切换两个步骤。

:notebook: 注意：进程切换是有代价的，因此如果过于频繁的执行进程调度、切换，必然会使整个系统的效率较低，是系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

8.调度算法的评价指标

:star: CPU利用率 ：指CPU工作的时间占总时间的比例

:star: 系统吞吐量 ：单位时间内完成作业的数量

:star2: 周转时间 ：是指作业被提交给系统开始，到作业完成为止的这段时间间隔。它包括四个部分：作业在外存后备队列上等待作业调度的时间，进程在就绪队列上等待进程调度的时候，进程在CPU上的执行时间，进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发送多次。

:writing_hand: 带权周转时间 ：作业周转时间/作业实际运行的时间。值越大，表示等待时间时间越多，用户满意度越低。

:sweet_potato: 等待时间 ：指作业/进程处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

• 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是被服务的，所以不计入等待时间。
• 对于作业来说，除了考虑建立进程后的等待时间，还要加上作业在外存后被队列中的等待时间。

一个作业总共被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响等待时间，也有平均等待时间来衡量标准。

:taco: 响应时间 ：指从用户提出请求到首次产生响应所用的时间。对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务，回应。

调度算法

学习过程中思考的问题

1. 算法思想
2. 算法规则
3. 用于作业调度还是进程调度
4. 抢占式/非抢占式
5. 是否可能饥饿（很久得不到响应）

先来先服务（FCFS）

1. 算法思想：公平
2. 算法规则：按照作业/进程到达的先后顺序进行服务，每次从就绪队列中选择最先进入队列的进程，然后一直允许，知道进程完成退出或被阻塞，才会继续从队列中学组第一个进程接着允许。
3. 用于作业调度还是进程调度：用于作业调度时，考虑的是哪个作业先到后备队列中，用于进程调度时，考虑的时哪个进程先到就绪队列中
4. 抢占式/非抢占式：非抢占式
5. 优缺点：优点：公平，算法实现简单。 缺点：排在后面的短作业长时间得不到响应，带权周转时间很大，对短作业来说用户体验不好。
6. 是否可能饥饿（很久得不到响应）：可能，假设一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。FCFS对长作业有利，适用于CPU繁忙型作业的系统，而不是用于I/O繁忙型的系统。如果I/O次数多的话，CPU就会浪费大量的时间。

短作业优先（SJF）

1. 算法思想：优先选择运行时间最短的进程来运行，有助于提高系统的吞吐量。追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
2. 算法规则：最短的作业/进程优先得到服务
3. 用于作业调度还是进程调度：即可用于作业调度也可以用于进程调度。
4. 抢占式/非抢占式：非抢占式
5. 优缺点：优点：”最短的“平均等待时间、平均周转时间 ； 缺点：不公平，对都安作业有利，对长作业不利。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
6. 是否可能饥饿（很久得不到响应）：长作业可能会饥饿，加入一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断地往后推，周转时间变长，致使长作业长时间不会被运行。

最短剩余时间优先（SRNT）

思想：每当有进程进入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行经常重新回到就绪队列中，另外，当一个经常完成时也需要调度。

高响应比优先算法（HRRN）

前面的先来先服务算法和短作业优先算法都没有很好的权衡短作业和长作业，此时就有了高效应比优先算法，权衡了短作业和长作业

1. 算法思想：要综合考虑作业/进程的等待时间和要求服务的时间
2. 算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比，选择响应比最高的的作业/进程为其服务。
3. 用于作业调度还是进程调度：即可用于作业调度也可以用于进程调度。
4. 抢占式/非抢占式：非抢占式，只有当当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
5. 是否可能饥饿（很久得不到响应）：不会

• 如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应比」就越高，这样短作业的进程容易被选中运行；
• 如果两个进程「要求的服务时间」相同时，「等待时间」越长，「响应比」就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会；

时间片轮转调度算法（RR)

1. 算法思想：公平地、轮流地位各个进程服务，让每个进程在一定时间讲个内都可以得到响应。
2. 算法规则：按照各进程到达就绪队列的顺序，轮流让各个经常执行一个时间片，若进程在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排列。
3. 用于作业调度还是进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
4. 抢占式/非抢占式：抢占式，若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式算法，由时钟装置发出时钟中断来通知CPU时间片已到。
5. 是否可能饥饿（很久得不到响应）：不会

时间片的长度是一个很关键的点：

• 如果时间片设的太短会导致过多的进程上下文切换，降低了CPU效率
• 如果设的太长有可能引起短作业进程的相应时间边长。

优先级调度算法

1. 算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
2. 算法规则：每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
3. 用于作业调度还是进程调度：用于进程调度和作业调度
4. 抢占式/非抢占式：都有，非抢占式只需在进程主动放弃CPU时进行调度，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
5. 是否可能饥饿（很久得不到响应）：不会

进程的优先级可以分为，静态优先级或动态优先级：

• 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
• 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

多级反馈调度算法

1. 算法思想：对其他调度算法的折中权衡
2. 算法规则：

• 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
• 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
• 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；

1. 用于作业调度还是进程调度：用于进程调度
2. 抢占式/非抢占式：抢占式
3. 是否可能饥饿（很久得不到响应）：不会

• 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
• 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

对于短作业，很可能在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

感谢：小林 x 图解计算机基础