优先级在循环调度中扮演什么角色？

Question

我正在尝试解决一个操作系统课程的作业问题：

---

以下进程使用抢占式的循环调度算法进行调度。每个进程都被分配一个数字优先级，数字越高表示相对优先级越高。

除了下面列出的进程外，系统还有一个空闲任务（不消耗CPU资源，并被标识为P_idle）。该任务的优先级为0，并在系统没有其他可用进程运行时进行调度。

一个时间片的长度为10个单位。

如果一个进程被一个更高优先级的进程抢占，那么被抢占的进程将被放置在队列的末尾。

+--+--------+----------+-------+---------+
|  | Thread | Priority | Burst | Arrival |
+--+--------+----------+-------+---------+
|  | P1     |       40 |    15 |       0 |
|  | P2     |       30 |    25 |      25 |
|  | P3     |       30 |    20 |      30 |
|  | P4     |       35 |    15 |      50 |
|  | P5     |        5 |    15 |     100 |
|  | P6     |       10 |    10 |     105 |
+--+--------+----------+-------+---------+

a. 使用甘特图显示进程的调度顺序。
b. 每个进程的周转时间是多少？
c. 每个进程的等待时间是多少？
d. CPU利用率是多少？

---

我的问题是 --- 在考虑使用轮转算法时，优先级扮演什么角色？我一直在思考这个问题，我得出的结论是，只有在到达时优先级很重要，以便决定是否应该抢占另一个进程。我得出这个结论的原因是，如果每次进行上下文切换时都进行检查，那么具有最高优先级的进程将无限制地运行，而其他进程则会挨饿。这与“轮流”确保没有任何进程执行超过一个时间量子并且进程执行后进入队列末尾的想法相违背。

使用这种逻辑，我解决了这个问题：

请问我是否正确理解了优先级在这种情况下的作用，并且是否以正确的方式处理这个问题？

- giraffesyo

Answer 1

我认为你的想法有些偏离。轮询控制一个优先级内的运行顺序。可以将每个优先级看作是一个队列，对应的轮询调度程序会执行队列中的任务。当一个给定优先级的队列为空时，会考虑其下一低优先级的队列，最终会到达空闲状态。

如果不按照这种方式处理，即使实际工作已准备就绪，如何防止最终调度空闲状态呢？

大多数高优先级进程都是被动的，也就是说，它们在响应事件后会短暂地执行一次，因此在大部分时间内不在运行/就绪队列中。

代码示例：

void Next() {
   for (int i = PRIO_HI; i >= PRIO_LO; i--) {
        Proc *p;
        if ((p = prioq[i].head) != NULL) {
           Resume(p);
           /*NOTREACHED*/
        }
   }
   panic(“Idle not on runq!”);
}

void Stop() {
      unlink(prioq + curp->prio, curp);
      Next();
}
void Start(Proc *p) {
      p->countdown = p->reload;
      append(prioq + p->prio, p);
      Next();
}
void Tick() {
        if (--(curp->countdown) == 0) {
           unlink(prioq + curp->prio, curp);
           Start(curp);
        }
}

- mevets

---

以那种方式来看，这很有道理。感谢您花时间向我解释。 - giraffesyo