1

我似乎无法在网上找到一个多级反馈队列的好例子来展示会发生什么。鉴于以下问题，我不一定需要回答整个问题，只需要如何进行几次迭代：

  1. 进程A：p nice = 2，运行0.1s，休眠0.6s，运行0.2s
  2. 进程B：p nice = 1，运行0.3s，休眠1.0s，运行0.3s
  3. 进程C：p nice = 3，运行1.0s
  4. 进程D：p nice = 1，运行0.5s

使用所描述的调度算法进行纸笔调度，并记下每次上下文切换时下一个要运行的进程的名称。假设进程在调度运行后立即休眠或退出（即如果进程在 0.1 秒后退出，它将被调度两次），并且进程在上下文切换发生之前唤醒。假设系统的负载为 0.5。将计算的每一步四舍五入到小数点后 2 位。

调度程序分配范围在 0 到 127 之间的进程优先级，其中 0 是最高的。内核进程的优先级可以在 0-49 之间，用户进程可以使用 50-127 的优先级。准备好执行的进程驻留在 32 个运行队列之一中，每个运行队列包含 4 个相邻优先级的进程（prio/4 = 运行队列）。运行队列中的进程没有进一步排序。

在每次上下文切换时，都会选择最高优先级队列头部的进程来执行。在每个时间片 (0.1s) 之后，当前运行的进程被上下文切换。调度程序从其原始队列的头部删除进程，调整其优先级（如果需要 - 见下文），并将其放置在它所属的队列的末尾（因为它的优先级可能刚刚改变）。然后重新扫描运行队列以查找包含可运行进程的最高优先级队列。

创建进程时，它以基本优先级（对于用户进程，我们称之为 PUSER 将其设置为 50）和估计的 cpu 利用率 (estcpu) 为 0.0 开始。进程每执行一个quanta，它的estcpu就加1。一个进程执行4个quanta后，它的优先级按照以下公式重新计算：Prio = PUSER + (estcpu/4) + 2* p_nice（注: Prio 不会小于 PUSER) 其中 p_nice 是在创建进程时指定的值。它的范围可以从 -20 到 19，但对于用户进程，指定负值将被忽略并默认为 0。

编辑:: 这是我对这个问题的回答，有人愿意看一下吗？

或链接：http: //imgur.com/jJVD3AC

4

1 回答 1

1

首先要做的是设置起始状态并定义职权范围。P(X) t将是进程 X 在quantum 的优先级t；E(X) t将是进程 X 在quantum 的估计 CPU 使用率t；T(X) t将是在下一次状态改变之前剩下的量子数。S(X) t将是进程的状态——R = 可运行，S = 睡眠，D = 死亡。一个进程 X 有一个 niceness N(X)。有多个队列，Q n是优先级n…n+3的队列。我们正在处理用户进程，因此每个进程 X 的调度优先级为 P(X) t = PUSER + E(X) t /4 + 2 * N(X)，初始估计 CPU 由 E(X )0 = 0。

N(A) = 2; N(B) = 1；N(C) = 3；N(D) = 1。

最初，P(A) 0 = 54 (50 + 0 + 2 * 2)；P(B) 0 = 52，P(C) 0 = 56；P(D) 0 = 52。因此，A、B 和 D 在 Q 13上，C 在 Q 14上。为了相反，D 在 Q 13的前面，然后是 B，然后是 A。

对于下一个量程，调度程序选择 Q 13前面的进程，即 D。D 为该量程运行（最后还有 4 个量程要运行，并且 E(D) 1 = 1）。它被放置在 Q 13的背面，并且下一个过程 B 运行一个量子（因此 E(B) 2 = 1，它在打盹之前还剩下 2 个量子。它被放置在 Q 的背面13和 A 运行下一个量程，依此类推。

您需要设计一个“纸笔”符号来记录正在发生的事情。

        ---- A ----   ---- B ----   ---- C ----   ---- D ----
t   R    P  E  S  T    P  E  S  T    P  E  S  T    P  E  S  T    Q13     Q14
0   D   54  0  R  1   52  0  R  3   56  0  R 10   52  0  R  5    D,B,A   C
1   B   54  0  R  1   52  0  R  3   56  0  R 10   53  1  R  4    B,A,D   C
2   A   54  0  R  1   53  1  R  2   56  0  R 10   53  1  R  4    A,D,B   C
3   D   55  1  S  6   53  1  R  2   56  0  R 10   53  1  R  4    D,B,A   C
4   B   55  1  S  5   53  1  R  2   56  0  R 10   54  2  R  4    B,A,D   C

所以这个过程继续。最终，进程将进入休眠多个量程（请注意，休眠进程的剩余时间会在每个量程上减少，而不是在可能已安排好的时候），或者将死亡（不再运行）等。你需要请注意，该行记录了量程开始时的状态。

于 2015-05-14T05:44:39.130 回答