P3L1 - Scheduling Flashcards
What is the role of the CPU Scheduler?
To decide how and when the processes (and their threads) access the shared CPUs
T/F: Scheduler concerns itself with both user level tasks and kernel level tasks
True!
When do you need to run the scheduler?
Whenever the CPU becomes idle
What is a common amount of time given to a task?
Timeslice
What are the steps that occur when the scheduler selects a task to be scheduled?
- Switch to new task
- Enter user mode
- Set program counter
- Execution begins!
What is the structure of the ready queue known as?
runqueue
_____ scheduling assumes that once a task is assigned to a CPU, it will run on that CPU until its finished
Run to Completion
What are some common metrics for comparing schedulers?
- Throughput
- Average job completion time
- Average job wait time
- CPU utilization
_____ algorithm has tasks scheduled in the order in which they arrive?
First come First serve (FCFS)
What is an alternative to using execution time when choosing tasks to schedule?
Priority levels
When scheduling based on priority levels, which task should run first?
The task with the highest priority level
What is an effective way to be able to quickly tell a task’s priority
Maintain a separate runqueue for each priority level
What is one dangerous situation that can occur with priority scheduling?
Starvation
What is starvation in the context of scheduling?
When low priority tasks are essentially never scheduled because higher priority tasks continually enter the system and take precedence
What is one mechanism to protect against starvation?
Priority aging - The priority of a task is not just the numerical property but a function of the actual priority and the amount of time the task has spent in the runqueue
What is priority inversion?
When the highest priority task that SHOULD run cannot run because the lowest priority task is holding a mutex it needs
What is one way to combat priority inversion?
Temporarily boost the priority of the mutex owner long enough to allow it to complete
Define a timeslice?
The maximum amount of uninterrupted time that can be given to a task
T/F: A task may run for a smaller amount of time than what the timeslice specifies?
True!
What is one use of timeslices?
To allow tasks to be interleaved
What are the downsides of timeslicing?
The overhead - We have to interrupt the running task, execute the scheduler ,and have to context switch to the new task
How long should a timeslice be?
CPU intensive tasks –> Prefer longer timeslice values
I/O intensive tasks –> Prefer shorter timeslice values
T/F: A runqueue data structure is only LOGICALLY a queue?
True! It can be implemented as multiple queues or even a tree
____ is a structure that maintains multiple distinct queues, each differentiated by their timeslice values
Multi queue
T/F: The topmost level of a multi queue has the larger timeslice value!
False! It holds the lowest
How did the Linux O(1) Scheduler get its name?
It can add/select tasks in constant time regardless of the number of tasks in the system
How many priority levels does the Linux O(1) scheduler have?
140 priority levels
What are levels 0-99 used for in the Linux O(1) scheduler?
real time tasks
What are levels 100-139 used for in the Linux O(1) scheduler?
timesharing tasks
What is the feedback for the Linux O(1) scheduler?
How long a task spent sleeping during its timeslice
How is the runqueue implemented for the Linux O(1) scheduler?
As two arrays - active and expired
Which of the two arrays of the Linux O( 1) schedulers runqueue is used for selecting the next task to run?
Active
What are some downsides of the Linux O(1) scheduler?
- A task cannot run again until everything in the active array is complete
- It makes no fairness guarantees
What scheduler replaced the Linux O(1) scheduler?
The CFS (Completely Fair Scheduler)
What type of data structure is used for the runquee for the CFS?
A red-black (self balancing) tree
How are tasks ordered in the runqueue for CFS?
Based on amount of time that they spent running on the CPU - vruntime
How long does selection take for CFS?
Constant time
How long does addition take for CFS?
Log(# of tasks)
Describe a shared memory multiprocessor
Multiple CPUs each with their own private L1/L2 cache, as well as a LLC which may or may not be shared. Lastly there is a DRAM shared across CPU’s
Describe a multicore system
Each CPU can have multiple internal cores each with its own private L1/L2 cache, a shared LLC and DRAM
T/F: It makes sense to schedule tasks on CPUs close to memory holding their state?
True! Keeps the cache hot
What is the scheduling type known as in which we keep tasks on the CPU closest to the memory node where their state is?
NUMA-aware scheduling
What is hyperthreading?
CPU support for multiple execution contexts (2)
How do we know if a thread is CPU bound or memory bound?
Use historic information like hardware counters that are updated as the processor executes and keep information about various aspects of execution
Is CPI a good metric for informing scheduling decisions?
No, its more or less the same across applications
