3
votes

I am trying to solve the following homework problem for an operating systems class:


The following processes are being scheduled using a preemptive, round robin scheduling algorithm. Each process is assigned a numerical priority, with a higher number indicating a higher relative priority.

In addition to the processes listed below, the system also has an idle task (which consumes no CPU resources and is identified as Pidle ). This task has priority 0 and is scheduled whenever the system has no other available processes to run.

The length of a time quantum is 10 units.

If a process is preempted by a higher-priority process, the preempted process is placed at the end of the queue.

+--+--------+----------+-------+---------+
|  | 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. Show the scheduling order of the processes using a Gantt chart.
b. What is the turnaround time for each process?
c. What is the waiting time for each process?
d. What is the CPU utilization rate?


My question is --- What role does priority play when we're considering that this uses the round robin algorithm? I have been thinking about it a lot what I have come up with is that it only makes sense if the priority is important at the time of its arrival in order to decide if it should preempt another process or not. The reason I have concluded this is because if it was checked every time there was a context switch then the process with the highest priority would always be run indefinitely and other processes would starve. This is against the idea of round robin making sure that no process executes longer than one time quantum and the idea that after a process executes it goes to the end of the queue.

Using this logic I have worked out the problem as such:

enter image description here

Could you please advise me if I'm on the right track of the role priority has in this situation and if I'm approaching it the right way?

1

1 Answers

2
votes

I think you are on the wrong track. Round robin controls the run order within a priority. It is as if each priority has its own queue, and corresponding round robin scheduler. When a given priority’s queue is empty, the subsequent lower priority queues are considered. Eventually, it will hit idle.

If you didn’t process it this way, how would you prevent idle from eventually being scheduled, despite having actual work ready to go?

Most high priority processes are reactive, that is they execute for a short burst in response to an event, so for the most part on not on a run/ready queue.

In code:

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);
        }
}