进程管理（二）

进程调度

我们还不知道操作系统调度程序采用的上层策略（policy）。接下来会介绍一系列的调度策略（sheduling policy）。

调度指标

相关指标：周转时间（turnaround time）、响应时间（response time）。

T 周转时间= T 完成时间−T 到达时间

T 响应时间= T 首次运行−T 到达时间

基础调度算法

先进先出（FIFO）

我们可以实现的最基本的算法，被称为先进先出（First In First Out 或FIFO）调度，有时候也称为先到先服务（First Come First Served 或FCFS）。

优点：

  • 它很简单，而且易于实现。

缺点：

  • 存在护航效应：一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后，会等很长时间。

最短任务优先（SJF）

策略：先运行最短的任务，然后是次短的任务，如此下去。

优点：

  • 改善了平均周转时间和平均带权周转时间，缩短作业的等待时间。
  • 提高系统的吞吐量。

缺点：

  • 存在护航效应：一些耗时较多的潜在资源消费者被排在轻量级的资源消费者之后，会等很长时间。
  • 未能依据作业的紧迫程度来划分执行的优先级。

最短完成时间优先（STCF）

向SJF 添加抢占，称为最短完成时间优先（Shortest Time-to-Completion First，STCF）或抢占式最短作业优先（Preemptive Shortest JobFirst ，PSJF）调度程序。

策略：每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。

优点：

  • “最短的”平均等待时间、平均周转时间
  • 同样提高系统的吞吐量。

缺点：

  • 同样存在护航效应：一些耗时较多的潜在资源消费者被排在轻量级的资源消费者之后，会等很长时间。
  • 同样未能依据作业的紧迫程度来划分执行的优先级。

时间片轮转

策略：RR 在一个时间片（time slice，有时称为调度量子，schedulingquantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。

优点：

  • 对于所有任务都是公平的。

缺点：

  • 缺点由于高频率的进程切换,因此会有一定的开销.
  • 同样未能依据作业的紧迫程度来划分执行的优先级。

时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应变差。

高级调度算法

多级反馈队列

MLFQ 中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何时刻，一个工作只能存在于一个队列中。MLFQ 总是优先执行较高优先级的工作（即在较高级队列中的工作）。每个队列中可能会有多个工作，因此具有同样的优先级。在这种情况下，我们就对这些工作采用轮转调度。

其中详细规则：

  • 规则1：如果A 的优先级 > B 的优先级，运行A（不运行B）。
  • 规则2：如果A 的优先级 = B 的优先级，轮转运行A 和B。
  • 规则3：工作进入系统时，放在最高优先级（最上层队列）。
  • 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
  • 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。MLFQ 有趣的原因是：它不需要对工作的运行方式有先验知识，而是通过观察工

比例份额

比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的CPU 时间，而不是优化周转时间和响应时间。

彩票调度最精彩的地方在于利用了随机性（randomness）。当你需要做出决定时，采用随机的方式常常是既可靠又简单的选择。

多处理器调度

由于计算机的架构师们当时难以让单核CPU 更快，同时又不增加太多功耗，所以这种多核CPU 很快就变得流行。

多处理器架构

为了理解多处理器调度带来的新问题，必须先知道它与单CPU 之间的基本区别。区别的核心在于对硬件缓存（cache）的使用，以及多处理器之间共享数据的方式。

image-20230321092128233

缓存一致性问题：

基本解决方案：

通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性。在基于总线的系统中，一种方式是使用总线窥探（bussnooping）。每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。如果CPU 发现对它放在缓存中的数据的更新，会作废（invalidate）本地副本（从缓存中移除），或更新（update）它（修改为新值）。

同步问题：

跨CPU 访问（尤其是写入）共享数据或数据结构时，需要使用互斥原语（比如锁），才能保证正确性（其他方法，如使用无锁（lock-free）数据结构，很复杂，偶尔才使用。

具体来说，随着CPU数量的增加，访问同步共享的数据结构会变得很慢。

调度方式：

  1. 单队列调度

    单队列多处理器调度（Single Queue Multiprocessor Scheduling，SQMS）：将所有需要调度的工作放入一个单独的队列中。但是为了保证在多CPU 上正常运行，调度程序的开发者需要在代码中通过加锁（locking）来保证原子性。

    image-20230321094004237

  2. 多队列调度

    正是由于单队列调度程序的这些问题，有些系统使用了多队列的方案，比如每个CPU一个队列。这样一来，每个CPU 调度之间相互独立，就避免了单队列的方式中由于数据共享及同步带来的问题。

    image-20230321094031010