多级反馈队列调度 - 纸笔示例
Multilevel Feedback Queue scheduling - Paper & Pencil example
我似乎无法在网上找到一个多级反馈队列的好例子来说明会发生什么。鉴于以下问题，我不一定需要回答整个问题，只需要如何进行几次迭代：
- 进程A：p nice = 2, 运行 0.1s, sleep 0.6s, 运行 0.2s
- 进程B: p nice = 1, 运行 0.3s, sleep 1.0s, 运行 0.3s
- 进程C: p nice = 3, 运行 for 1.0s
- 进程D: p nice = 1, 运行 for 0.5s
使用描述的调度算法进行pencil-and-paper调度，并记下
每个 context-switch 下一个 运行 的进程名称。假设进程睡眠或退出
在它们被安排到 运行 之后，（即如果进程在 0.1 秒后退出，它将被安排
两次），并且进程在上下文切换发生之前就被唤醒。假设负载
系统是0.5。将计算的每一步四舍五入到小数点后两位。
调度程序分配的进程优先级在 0 到 127 之间，0 是最高的。
内核进程的优先级可以在 0-49 之间，用户进程可以使用 50-127 的优先级。
准备执行的进程驻留在 32 个 运行 队列之一中，每个 运行 队列
包含 4 个相邻优先级的进程（prio/4 = 运行 队列）。 运行 队列中的进程不是
进一步订购。
在每次上下文切换时，最高优先级队列头部的进程被选择执行。
在每个量程 (0.1s) 之后，当前 运行ning 进程被上下文切换。调度器
从其原始队列的头部删除进程，调整其优先级（如果需要 - 见下文），
并将它放在它所属的队列的末尾（因为它的优先级可能刚刚改变）。
然后重新扫描 运行 队列以查找包含 运行 可用进程的最高优先级队列。
创建进程时，它以基本优先级开始
（对于用户进程，我们称它为 PUSER，将其设置为 50）并且估计 cpu 利用率 (estcpu) 为 0.0。
每当一个进程执行了一个量程，它的 estcpu 就会增加 1。在一个进程之后
已经执行了4个quanta，其优先级按照以下公式重新计算：
Prio = PUSER + (estcpu/4) + 2* p_nice （注：Prio不会变得小于PUSER）
其中 p_nice 是创建进程时指定的值。它的范围从 -20 到 19，
但对于用户进程，指定负值将被忽略并默认为 0。
编辑：：这是我对这个问题的回答，有人愿意看一下吗？
或link：http://imgur.com/jJVD3AC
首先要做的是设置起始状态和定义职权范围。 P(X)t 将是进程 X 在时间片 t 的优先级； E(X)t 将是进程 X 在量程 t 的估计 CPU 使用率； T(X)t 将是下一次状态更改之前剩余的量子数。 S(X)t 将是进程的状态 — R = 运行nable，S = sleeping，D = dead。一个过程 X 有一个 niceness N(X)。有多个队列，Qn是优先级n…n+3的队列。我们处理的是用户进程，所以每个进程 X 的调度优先级为 P(X)t = PUSER + E(X)t/ 4 + 2 * N(X)，初始估计CPU由E(X)0 = 0.
给出
N(A) = 2; N(乙) = 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在Q13上，C在Q上14。为了对比，D在Q13前面，后面是B，后面是A.
对于下一个quantum，调度器选择Q13前面的进程，也就是D.D运行s这个quantum（并且有4量子最后留给 运行，E(D)1 = 1)。它放在Q13的后面，下一个进程B是运行一个量子（所以E(B)2 = 1，它在打瞌睡之前还剩2个quanta，放在Q13的后面，下一个quantum放在A运行s，并且等等。
您需要设计一个 'pencil and paper' 符号来记录正在发生的事情。
---- 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
所以这个过程继续。最终，进程将休眠一定数量的量子（请注意，休眠进程的剩余时间在每个量子上都会减少，而不是在它可能已被调度时），或者将死亡（再也不会 运行 ），等等.你需要仔细理解，该行记录了一个量子开始时的状态。
我似乎无法在网上找到一个多级反馈队列的好例子来说明会发生什么。鉴于以下问题，我不一定需要回答整个问题，只需要如何进行几次迭代：
- 进程A：p nice = 2, 运行 0.1s, sleep 0.6s, 运行 0.2s
- 进程B: p nice = 1, 运行 0.3s, sleep 1.0s, 运行 0.3s
- 进程C: p nice = 3, 运行 for 1.0s
- 进程D: p nice = 1, 运行 for 0.5s
使用描述的调度算法进行pencil-and-paper调度，并记下 每个 context-switch 下一个 运行 的进程名称。假设进程睡眠或退出 在它们被安排到 运行 之后，（即如果进程在 0.1 秒后退出，它将被安排 两次），并且进程在上下文切换发生之前就被唤醒。假设负载 系统是0.5。将计算的每一步四舍五入到小数点后两位。
调度程序分配的进程优先级在 0 到 127 之间，0 是最高的。 内核进程的优先级可以在 0-49 之间，用户进程可以使用 50-127 的优先级。 准备执行的进程驻留在 32 个 运行 队列之一中，每个 运行 队列 包含 4 个相邻优先级的进程（prio/4 = 运行 队列）。 运行 队列中的进程不是 进一步订购。
在每次上下文切换时，最高优先级队列头部的进程被选择执行。 在每个量程 (0.1s) 之后，当前 运行ning 进程被上下文切换。调度器 从其原始队列的头部删除进程，调整其优先级（如果需要 - 见下文）， 并将它放在它所属的队列的末尾（因为它的优先级可能刚刚改变）。 然后重新扫描 运行 队列以查找包含 运行 可用进程的最高优先级队列。
创建进程时，它以基本优先级开始 （对于用户进程，我们称它为 PUSER，将其设置为 50）并且估计 cpu 利用率 (estcpu) 为 0.0。 每当一个进程执行了一个量程，它的 estcpu 就会增加 1。在一个进程之后 已经执行了4个quanta，其优先级按照以下公式重新计算： Prio = PUSER + (estcpu/4) + 2* p_nice （注：Prio不会变得小于PUSER） 其中 p_nice 是创建进程时指定的值。它的范围从 -20 到 19， 但对于用户进程，指定负值将被忽略并默认为 0。
编辑：：这是我对这个问题的回答，有人愿意看一下吗？
或link：http://imgur.com/jJVD3AC
首先要做的是设置起始状态和定义职权范围。 P(X)t 将是进程 X 在时间片 t 的优先级； E(X)t 将是进程 X 在量程 t 的估计 CPU 使用率； T(X)t 将是下一次状态更改之前剩余的量子数。 S(X)t 将是进程的状态 — R = 运行nable，S = sleeping，D = dead。一个过程 X 有一个 niceness N(X)。有多个队列，Qn是优先级n…n+3的队列。我们处理的是用户进程，所以每个进程 X 的调度优先级为 P(X)t = PUSER + E(X)t/ 4 + 2 * N(X)，初始估计CPU由E(X)0 = 0.
N(A) = 2; N(乙) = 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在Q13上，C在Q上14。为了对比，D在Q13前面，后面是B，后面是A.
对于下一个quantum，调度器选择Q13前面的进程，也就是D.D运行s这个quantum（并且有4量子最后留给 运行，E(D)1 = 1)。它放在Q13的后面，下一个进程B是运行一个量子（所以E(B)2 = 1，它在打瞌睡之前还剩2个quanta，放在Q13的后面，下一个quantum放在A运行s，并且等等。
您需要设计一个 'pencil and paper' 符号来记录正在发生的事情。
---- 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
所以这个过程继续。最终，进程将休眠一定数量的量子（请注意，休眠进程的剩余时间在每个量子上都会减少，而不是在它可能已被调度时），或者将死亡（再也不会 运行 ），等等.你需要仔细理解，该行记录了一个量子开始时的状态。