scheduler_algorithm.c File Reference

Round Robin algorithm. More...

Macros
#define	__DEBUG_HEADER__   "[SCHALG]"
	Change header.
#define	__DEBUG_LEVEL__   LOGLEVEL_NOTICE
	Set log level.

Functions
static void	__update_task_statistics (task_struct *task)
	Updates task execution statistics. More...
static bool_t	__is_periodic_task (task_struct *task)
	Checks if the given task is actually a periodic task. More...
static task_struct *	__scheduler_rr (runqueue_t *runqueue, bool_t skip_periodic)
	Employs time-sharing, giving each job a time-slot, and is also preemptive since the scheduler forces the task out of the CPU once the time-slot expires. More...
static task_struct *	__scheduler_priority (runqueue_t *runqueue, bool_t skip_periodic)
	Is a non-preemptive algorithm, where each task is assigned a priority. Processes with highest priority are executed first, while processes with same priority are executed on first-come/first-served basis. Priority can be decided based on memory requirements, time requirements or any other resource requirement. More...
static task_struct *	__scheduler_cfs (runqueue_t *runqueue, bool_t skip_periodic)
	It aims at giving a fair share of CPU time to processes, and achieves that by associating a virtual runtime to each of them. It always tries to run the task with the smallest vruntime (i.e., the task which executed least so far). It always tries to split up CPU time between runnable tasks as close to "ideal multitasking hardware" as possible. More...
static task_struct *	__scheduler_aedf (runqueue_t *runqueue)
	Executes the task with the earliest absolute deadline among all the ready tasks. More...
static task_struct *	__scheduler_edf (runqueue_t *runqueue)
	Executes the task with the earliest absolute DEADLINE among all the ready tasks. When a task was executed, and its period is starting again, it must be set as 'executable again', and its deadline and next_period must be updated. More...
static task_struct *	__scheduler_rm (runqueue_t *runqueue)
	Executes the task with the earliest next PERIOD among all the ready tasks. More...
task_struct *	scheduler_pick_next_task (runqueue_t *runqueue)
	Picks the next task (in scheduler_algorithm.c). More...

Detailed Description

Round Robin algorithm.

Copyright

(c) 2014-2024 This file is distributed under the MIT License. See LICENSE.md for details.

Function Documentation

__is_periodic_task()

static bool_t __is_periodic_task ( task_struct *  task )

inlinestatic

Checks if the given task is actually a periodic task.

Parameters

task	the task to check.

Returns

true if the task is periodic, false otherwise.

__scheduler_aedf()

static task_struct* __scheduler_aedf ( runqueue_t *  runqueue )

inlinestatic

Executes the task with the earliest absolute deadline among all the ready tasks.

Parameters

runqueue

list of all processes.

Returns

the next task on success, NULL on failure.

__scheduler_cfs()

static task_struct* __scheduler_cfs ( runqueue_t *  runqueue, bool_t  skip_periodic  )

inlinestatic

It aims at giving a fair share of CPU time to processes, and achieves that by associating a virtual runtime to each of them. It always tries to run the task with the smallest vruntime (i.e., the task which executed least so far). It always tries to split up CPU time between runnable tasks as close to "ideal multitasking hardware" as possible.

Parameters

runqueue	list of all processes.
skip_periodic	tells the algorithm if there are periodic processes in the list, and in that case it needs to skip them.

Returns

the next task on success, NULL on failure.

__scheduler_edf()

static task_struct* __scheduler_edf ( runqueue_t *  runqueue )

inlinestatic

Executes the task with the earliest absolute DEADLINE among all the ready tasks. When a task was executed, and its period is starting again, it must be set as 'executable again', and its deadline and next_period must be updated.

Parameters

runqueue

list of all processes.

Returns

the next task on success, NULL on failure.

__scheduler_priority()

static task_struct* __scheduler_priority ( runqueue_t *  runqueue, bool_t  skip_periodic  )

inlinestatic

Is a non-preemptive algorithm, where each task is assigned a priority. Processes with highest priority are executed first, while processes with same priority are executed on first-come/first-served basis. Priority can be decided based on memory requirements, time requirements or any other resource requirement.

Parameters

runqueue	list of all processes.
skip_periodic	tells the algorithm if there are periodic processes in the list, and in that case it needs to skip them.

Returns

the next task on success, NULL on failure.

When implementing this algorithm, beware of the following pitfal. If you have the following runqueue (reports task position in the runqueue, priority and name): Position | Priority | Name 1 | 120 | init 2 | 120 | shell 3 | 122 | echo 4 | 128 | ps If you pick the first task every time (i.e., init), and use its prio (i.e., 120), what would happen if inside the for-loop when you check "if the entry has a lower priority", you use a lesser-than sign? First, it will check against init itself, so 120 < 120 is false. Then, it will check against shell, again, 120 < 120 is false. As such, shell or the other processes will never be selected. There are different ways of solving this problem, each of which requires changes only inside this same function. Good luck.

__scheduler_rm()

static task_struct* __scheduler_rm ( runqueue_t *  runqueue )

inlinestatic

Executes the task with the earliest next PERIOD among all the ready tasks.

When a task was executed, and its period is starting again, it must be set as 'executable again', and its deadline and next_period must be updated.

Parameters

runqueue

list of all processes.

Returns

the next task on success, NULL on failure.

__scheduler_rr()

static task_struct* __scheduler_rr ( runqueue_t *  runqueue, bool_t  skip_periodic  )

inlinestatic

Employs time-sharing, giving each job a time-slot, and is also preemptive since the scheduler forces the task out of the CPU once the time-slot expires.

Parameters

runqueue	list of all processes.
skip_periodic	tells the algorithm that periodic processes in the list should be skipped.

Returns

the next task on success, NULL on failure.

__update_task_statistics()

static void __update_task_statistics ( task_struct *  task )

static

Updates task execution statistics.

Parameters

task	the task to update.

scheduler_pick_next_task()

task_struct* scheduler_pick_next_task

(

runqueue_t *

runqueue

)

Picks the next task (in scheduler_algorithm.c).

Parameters

runqueue

Pointer to the runqueue.

Returns

The next task to execute.