P3L1 - Linux Schedulers: O(1) vs CFS Flashcards
The Linux O(1) scheduler gets its name from the fact that it can add/select a task in ________ time, regardless of the number of tasks in the system.
The Linux O(1) scheduler gets its name from the fact that it can add/select a task in constant time, regardless of the number of tasks in the system.
Linux O(1) is a preemptive, priority-based scheduler, with ____ priority levels.
The priority levels are broken into two classes:
Priorities ___ to ___ are for real-time tasks
Priorities ___ to ___ are for timesharing tasks.
Linux O(1) is a preemptive, priority-based scheduler, with 140 priority levels.
The priority levels are broken into two classes: priorities from 0 to 99 are for real-time tasks, while 100 to 139 are for timesharing tasks.
User processes have priorities in the timesharing class, with the default priority in the middle at ____.
Priority levels can be adjusted with so-called ____ ______ which span from -20 to 19, corresponding to 120 - 20 to 120 + 19.
There is a system call to adjust the priority of a user process.
User processes have priorities in the timesharing class, with the default priority in the middle at 120.
Priority levels can be adjusted with so-called nice values which span from -20 to 19, corresponding to 120 - 20 to 120 + 19.
There is a system call to adjust the priority of a user process.
The O(1) scheduler borrows from the MLFQ scheduler in that each priority level is associated with a different ________ value.
As well, the O(1) scheduler uses feedback from how tasks behaved in the ______ in order to understand how to prioritize tasks in the _______.
The O(1) scheduler borrows from the MLFQ (multi-level feedback queue) scheduler in that each priority level is associated with a different timeslice value.
As well, the O(1) scheduler uses feedback from how tasks behaved in the past in order to understand how to prioritize tasks in the future.
The scheduler assigns the _______ timeslice values to the low-priority, CPU bound tasks
The scheduler assigns the _______ timeslice values to the more interactive tasks.
- Explain why this design make sense although it is contrary to something we learned previously …
The scheduler assigns the smallest timeslice values to the low-priority, CPU bound tasks
The scheduler assigns the largest timeslice values to the more interactive tasks.
- This is contrary to original idea of giving low priority, CPU intensive tasks a large time slice!!!
- Giving the lowest priority tasks the smallest timeslices ensures that low priority tasks - which only run after all higher priority tasks expire - do not block the higher priority tasks for too long.
- The lower priority tasks get their small window to accomplish their work, and then quickly yield back to more important tasks.
The feedback for the task depends on how long the task spent sleeping during its timeslice.
Sleeping refers to time spent idling or waiting.
If a task spends more time sleeping, this means it is a more _______ task, and its priority is _______ (priority - 5).
If a task spends less time sleeping, this means it is a more __________ __________ task, and its priority is lowered (priority + 5).
The feedback for the task depends on how long the task spent sleeping during its timeslice.
Sleeping refers to time spent idling or waiting.
If a task spends more time sleeping, this means it is a more interactive task, and its priority is boosted (priority - 5).
If a task spends less time sleeping, this means it is a more computationally intensive task, and its priority is lowered (priority + 5).
The runqueue in the O(1) scheduler is implemented as two arrays of tasks: _______ and _______.
Each array element points to the ______ runnable task at that _______ level.
The runqueue in the O(1) scheduler is implemented as two arrays of tasks: active and expired.
Each array element points to the first runnable task at that priority level.
How does scheduling in O(1) work?
The scheduler chooses the next task to run from the _______ array.
If a task yields the CPU to wait on an event or is preempted due to a higher priority task becoming runnable, the time it has spent on the _____ is compared to the timeslice.
If it is ____ than the timeslice, the task is placed back on the active queue for that priority level.
Only after the entire timeslice has been exhausted will the task move to the ______ array.
The expired array contains the _____ tasks.
Once there are no more tasks in the active array, the empty active array and the expired array will be _______.
The scheduler chooses the next task to run from the active array.
If a task yields the CPU to wait on an event or is preempted due to a higher priority task becoming runnable, the time it has spent on the CPU is compared to the timeslice.
If it is less than the timeslice, the task is placed back on the active queue for that priority level.
Only after the entire timeslice has been exhausted will the task move to the expired array.
The expired array contains the inactive tasks.
Once there are no more tasks in the active array, the empty active array and the expired array will be swapped.
True or False?
The O(1) scheduler sometimes schedules tasks from the active array and sometimes from the expired array depending on the task priority.
False. The scheduler will not schedule tasks from the expired array while there are still tasks in the active array.
Giving the lowest priority tasks the smallest timeslices ensures that …
Giving the lowest priority tasks the smallest timeslices ensures that … low priority tasks - which only run after all higher priority tasks expire - do not block the higher priority tasks for too long.
One problem with the O(1) is that once a task enters the expired queue, it will not get a chance to run again until all other tasks in the active queue have executed for their timeslices. This is a problem for ______ tasks
One problem with the O(1) is that once a task enters the expired queue, it will not get a chance to run again until all other tasks in the active queue have executed for their timeslices. This is a problem for interactive tasks
Linux Schedulers Quiz
What was the main reason the O(1) scheduler was replaced by the CFS scheduler?
Interactive tasks could wait unpredictable amounts of time to be scheduled - because they need to wait till the active queue clears in order to be scheduled.
What is the ‘fairness’ guarantee?
Fairness is the concept that in a given time interval, a task should be able to run for an amount of time that is relative to its priority.
CFS uses a ________ tree as a runqueue structure. These are self-balancing trees, which ensure that all of the paths from the root of the tree to the leaves are approximately the same size.
Tasks are ordered in the tree based on the amount of ______ that they spent running on the ______, a quantity known as _______. CFS tracks this quantity to the ________.
CFS uses a red-black tree as a runqueue structure. These are self-balancing trees, which ensure that all of the paths from the root of the tree to the leaves are approximately the same size.
Tasks are ordered in the tree based on the amount of time that they spent running on the CPU, a quantity known as vruntime (virtual runtime). CFS tracks this quantity to the nanosecond.
The red-black balanced tree runqueue has the property that for a given node:
all nodes to the left have _____ vruntimes and therefore need to be scheduled ______ , while
all nodes to the right, have _____ vruntimes and therefore can wait ______.
The red-black balanced tree runqueue has the property that for a given node:
all nodes to the left have lower vruntimes and therefore need to be scheduled sooner, while
all nodes to the right, have larger vruntimes and therefore can wait longer.
