0
$\begingroup$

In my Operating Systems class I have an exercise to sketch out how a round-robin algorithm would apply to a specific scenario, which is the following:


Exercise


Now the correction that I was provided with by the lecturer is the following:


Correction of the exercise by the lecturer


But I do not understand how this is correct. After referring to the lecture that was given on this specific topic, I understood that Round-Robin maintains a queue with threads and each thread has a time quantum of tens of milliseconds of CPU time. When a thread has exhausted its time quantum CPU time it goes straight to the end of the queue. I also know that, threads that do not full use their time quantum CPU time, will be put in a separated queue, resulting in multilevel queue. After my understanding, this last part is ignored here. Here is the resolution of the exercise that I came up with:


My version of the exercise


The "-" stand for executing time, the "v^v^v" stands for blocking time, pretty much like in the correction picture. Note that my version, and the version of the correction match up until the 1st pink dashed line.

Finally, the question is: How come that after the 1st pink dashed line, A is assigned to the CPU? (in the correction version), instead of B, which is, after my understanding, the next process in the queue to be executed(See "Ready queue") in my version of the exercise.

Please note that there are priorities, but according to the definition of round-robin fashion, priorities are not considered for it(I know that in most OSs the plain vanilla round-robin is not applied, but please ignore that); priorities are there for other parts of the exercise which have nothing to do with this issue.

$\endgroup$
1
$\begingroup$

A round robin scheduler has a fifo queue of processes in state runnable. At each time step the scheduler runs the process at the head of the queue for one quantum.

At the end of each time quantum the running process is interrupted and placed at the tail of the queue. If the process blocks (requests i/o) during the time quantum it is typically completely removed from the queue.

The difference between your solution and your instructor's solution is the assumption you are making about what happens when a process's i/o request finishes, and the process again becomes runnable. Your instructor assumes that the process is placed on the tail of the queue. You seem to be assuming that the process is placed at the head of the queue.

Either choice (placing the newly unblocked process at the tail or at the head) is reasonable, but they have different consequences as described by @Gille's answer to a broader question.

If you place the newly unblocked process at the tail of the queue then you maintain the guarantee that no process will ever be starved. In practice however, i/o-bound jobs are sometimes given higher priority, both to reduce the latency of those jobs, and to maximize throughput of i/o devices. You could implement this increase in priority by putting newly unblocked processes at the head of the queue instead of the tail, but you would lose your starvation-freeness guarantees.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.