操作系统 - 彩票进程调度

在多道程序设计环境中，CPU调度算法是决定就绪队列中哪个进程应该接下来执行的策略。与试图优化周转时间或等待时间的传统调度算法不同，彩票进程调度旨在为每个进程提供一定比例的CPU时间。

什么是彩票进程调度？

彩票进程调度遵循概率调度方法。调度程序将彩票分配给系统中的进程，这些进程通过彩票分配CPU时间。彩票可能不会均匀分配。如果一个进程拥有更多彩票，它就有相对较高的选择概率。因此，拥有更多彩票的进程具有更高的优先级。为了使所有进程都具有相同的优先级，调度程序会向它们分配相同数量的彩票。

这种调度也称为比例共享调度和公平共享调度。

彩票进程调度具有以下实现步骤：

彩票分配 - 最初，系统中的每个进程都被分配一些数量的彩票。每张彩票都有一个唯一的号码，并且系统中分配的彩票总数始终相同。
抽奖 - 调度程序通过抽取一张随机彩票进行抽奖。通常，使用随机数生成器在系统中分配的所有彩票号码中生成一个彩票号码。
调度和执行 - 拥有中奖彩票号码的进程将在下一个时间段内被选中执行。所选进程要么运行到完成，要么运行到时间段结束，以较小者为准。如果没有进程拥有中奖彩票，则再次进行抽奖。
彩票调整 - 所有被分配彩票的进程都运行完成之后，调度程序结束当前执行。如果新的进程进入系统，调度程序将从头开始重新启动整个过程。

彩票通常根据每个进程的优先级进行操作。高优先级进程分配的彩票比低优先级进程多，从而增加了它们被选中执行的机会。但是，在彩票调度中操作彩票有几种不同的方法：

在这种方法中，分配给每个进程的彩票数量是固定的，并且不会随着时间的推移而改变。例如，高优先级进程可能会被分配100张彩票。另一方面，低优先级进程可能只被分配10张彩票。这种方法易于实现，但可能不会导致最有效或最公平的资源分配。

在这种方法中，分配给每个进程的彩票总数可能会随着时间的推移而根据系统的行为而波动。例如，如果一个高优先级进程正在占用资源并使其他进程处于饥饿状态，则可以减少其彩票数量，以使其他进程有更大的机会被选中。尽管此方法具有更高的计算开销，但它可能导致更有效和更公平的资源分配。

在这种方法中，分配给每个进程的彩票总数由优先级以外的其他因素决定。其他因素，包括它已经消耗的处理能力数量，也起作用。即使具有相同的优先级，已经消耗大量处理能力的进程分配的彩票数量可能少于使用很少CPU时间的进程。这种方法可能难以实现，但可以帮助防止进程独占资源。

让我们考虑一个有三个进程P0、P1和P2的情况，调度程序已向它们分配了总共100张彩票，如下表的前两列所示：

进程	彩票号码	彩票比例 $\mathrm{= \: \frac{分配的彩票数}{彩票总数} \: \times \: 100}$
P0	0-10, 41-50	20/100 = 20%
P1	11-40	30/100 = 30%
P2	51-60	50/100 = 50%

进程

彩票号码

彩票比例

$\mathrm{= \: \frac{分配的彩票数}{彩票总数} \: \times \: 100}$

0-10, 41-50

20/100 = 20%

11-40

30/100 = 30%

51-60

50/100 = 50%

在第三列中，我们计算了分配给每个进程的彩票比例。

假设彩票调度程序为前25次抽奖生成以下彩票号码：

12, 34, 78, 55, 01, 23, 44, 54, 64, 94, 29, 89, 05, 36, 76, 62, 22, 32, 42, 51, 73, 85, 18, 81, 25

生成的调度将是：

P0、P1、P2、P2、P0、P1、P0、P2、P2、P2、P1、P2、P0、P1、P2、P2、P1、P1、P0、P2、P2、P2、P1、P2、P1

进程的比例份额计算如下：

$$\mathrm{PX的比例份额 \: = \: \frac{PX的中奖次数}{抽奖总数} \: \times \: 100}$$

使用此公式，我们得到每个进程的比例份额如下：

$$\mathrm{P0的比例份额 \: = \: \frac{5}{25} \: \times \: 100 \: = \: 20 \%}$$

$$\mathrm{P1的比例份额 \: = \: \frac{8}{25} \: \times \: 100 \: = \: 32 \%}$$

$$\mathrm{P2的比例份额 \: = \: \frac{12}{25} \: \times \: 100 \: = \: 48 \%}$$

我们可以观察到，进程的CPU时间比例份额非常接近分配给它们的彩票比例。随着抽奖次数的增加，这些值会接近完美。

打印页面