Executable::RoundRobin (microkernel)

Round-robin scheduler

The kernel uses the round-robin scheduler for debugging, kernel, and idle threads. In the round robin scheduler, tasks are executed serially with fixed quantums given after each clock-tick. This is because it is the lowest-priority scheduler and is used for kernel-background tasks which don't have any priority.

Algorithm

The scheduler keeps tasks in a circular-list. Each task in the list is executed serially, and last-ran task is stored in the mostRecent field. Whenever the core scheduler calls for task-allocation or a task-update then the round-robin scheduler returns mostRecent->next.

Task Receiving

Whenever the CPU gets tasks from another CPU, then the round-robin scheduler (on the receiving processor) will insert the list of tasks into the circular list. It is a O(1) operation as the list of tasks are inserted as one element at the end of the list. This is one reason why kernel-threads execute on the round-robin scheduler - fast task transfers & runqueue-balancing.

Task Sending

Whenever a CPU disposes tasks to another CPU, the round robin scheduler just removes a chain of tasks from the list as one element. It is a O(n), where 'n' is the no. of tasks to transfer, unless the no. of tasks is greater than or equal to the no. of tasks on the CPU (then the operation becomes O(1)).

The round robin scheduler can also reduce the operation time by getting the nth element from the end of the list making the operation O(m-n), where 'm' is the count of tasks in the list.

Which tasks are not to be put in the round-robin scheduler?

The interactive tasks should not be put in the round-robin scheduler as they will not get higher-priority on the CPU-bound tasks.

Why should CPU-bound tasks be put in the round-robin scheduler?

If CPU-bound tasks are given the CFS scheduler (developed in the future), then the kernel-tasks will never execute as the CPU-bound tasks will always steal their quantum by staying the interactive-scheduling space.