P3L1. Scheduling Flashcards
Name three ways an OS scheduler could choose to schedule tasks and the benefit of each.
- Assign tasks immediately
- Benefit: Keeps scheduling simple
- Algorithm: First Come First Serve
- Assign simple tasks first
- Benefit: Mazimize throughtput
- Algorithm: Shortest Job First
- Assign complex tasks first
- Benefit: Maximize all aspects of the platform (utilization of CPU, devices, memory, etc)
- Algorithm: ?
What does a CPU scheduler do?
- Decides how and when processes (and their threads) access shared CPUs.
- Schedules tasks running user-level processes/threads as well as kernel-level threads.
When does the CPU scheduler run?
The CPU scheduler runs when:
- CPU becomes idle
- a new task becomes ready
- timeslice expired timeout
What happens once the scheduler selects a thread to be scheduled onto the CPU?
The thread is dispatched onto the CPU:
- perform context switch
- enter user mode
- set program counter
- new thread starts executing
How does the CPU scheduler choose which task should be run next? And how is this done?
Which task should be selected depends on the scheduling policy/algorithm.
How this is done depends on the runqueue data structure.
The runqueue data structure and the scheduling algorithm are tightly coupled. e.g., certain scheduling policies demand a certain runqueue data structure.
What is “run-to-completion” scheduling?
This type of scheduling assumes that as soon as a task is assigned to a CPU it will run until it completes.
What is First-Come First-Service (FCFS)?
What kind of runqueue data structure is needed to support it?
Pros/Cons?
Tasks are scheduled in the order of arrival.
To make a decision all the scheduler needs to know the head of the queue and how to dequeue tasks, so a FIFO queue would make a good runqueue data structure.
Pros:
- Simple
Cons:
- Wait time is poor even if there’s only one long task in the system that has arrived in front of other shorter tasks.
Say we have a First-Come First-Servce (FCFS) policy with run-to-completion scheduling, and tasks T1, T2, and T2, which take 1 second, 10 seconds, and 1 second to run.
What is the throughput?
What is the average completion time?
What is the average wait time?
Throughput
3 tasks / 12 seconds = 0.25 tasks / second
Average Completion Time
(1 + 11 + 12) / 3 = 8 seconds
T1 completes after 1 second, T2 after 11 seconds, T3 after 12 seconds
Average Wait Time
(0 + 1 + 11) / 3 = 4 seconds
What is Shortest Job First (SJF)?
What kind of runqueue data structure is needed to support it?
Pros/Cons?
Schedules tasks in order of their execution time.
The scheduler needs to know the tail of the queue, and also how to insert tasks in a specific order. We could use an ordered queue data structure or a tree where the leftmost node is always the shortest execution time.
Pros:
- TODO
Cons:
- TODO
What is the formula for throughput?
jobs completed / time to complete all jobs
What is the formula for average completion time?
sum of times to complete each job / jobs completed
What is the formula for average wait time?
sum of time each job spent waiting / jobs completed
What is preemptive scheduling?
This type of scheduling assumes that when a task is assigned to a CPU it can be interrupted so that another task can be scheduled.
When scheduling jobs with the Shortest Job First (SJF) policy, how can the scheduler determine a task’s execution time?
The scheduler can use heuristics based on history of job running time.
- how long did a task run last time?
- how long did a task run last n times? (windowed average)
What is Priority scheduling?
What kind of runqueue data structure is needed to support it?
Pros/Cons?
Tasks have different priority levels. The scheduler will run the highest priority task next.
We can support this by having a queue per priority (the scheduler just selects the next job off the appropriate queue) or we can use a tree ordered based on priority.
Pros:
- TODO
Cons:
- Starvation: low priority task stuck in runqueue. We can protect against this with “priority aging” where priority is a function of the task’s actual priority and the time spent in the run queue.
What is priority inversion?
Give an example of how this could happen.
Priority inversion is a scenario in scheduling in which a high priority task is indirectly preempted by a lower priority task effectively inverting the relative priorities of the two tasks.
e.g., If the low priority task holds a lock that a higher priority task needs, the low priority task has to be scheduled first, inverting the priorities of the tasks.
Say we have a low priority task that holds a lock that a high priority task needs. How can we ensure that the low priority task will run and release the lock soon so the high priority task can obtain the lock?
We can temporarily boost the priority of the mutex owner and then lower again after it releases the lock.
What is Round Robin Scheduling?
- pick up first task form queue (like FCFS)
- task may yeild to wait on I/O (unlike FCFS)
Round Robin w/ priorities
- include preemption
Round Robin w/ interleaving
- timeslicing
What is a timeslice (aka time quantum)?
The maximum amount of uninterrupted time given to a task.
Using timeslices allows tasks to be interleaved, timesharing the CPU. This is less important for I/O-bound tasks since they are constantly releasing the CPU but for CPU-bound tasks this is critical since it’s the only way we can achieve time sharing.
What is Timeslice Scheduling?
Pros/Cons?
We run tasks for a maximum time = timeslice between switching to a new task.
Pros:
+ Shorter tasks finish sooner
+ More responsive
+ Lengthy I/O operations initiated sooner
Cons:
- Overhead (we have to interrupt task, invoke scheduler, context switch to new task) but we can minimize the overhead by ensuring timeslice is > context switch time
How long should a timeslice be?
CPU-bound tasks prefer longer timeslices
- limits context switching overhead
- keeps CPU utilization and throughput high
I/O-bound tasks prefer shorter timeslices
- I/O-bound tasks can issue I/O operations earlier
- keeps CPU and device utilization high
- better user-perceived performance
What is the formula for calculating CPU utilization?
Over a consistent, recurring interval:
sum of time tasks spend running on the CPU / sum of time tasks spent running on the CPU + sum of time spent context switching between tasks
How do we avoid task starvation? (i.e., a task with a low priority never gets a chance to run b/c there are always higher priority tasks in the queue)
TODO
How do we know if a task is CPU or I/O intensive?
How do we know how I/O intensive a task is?
- history based heuristics
What is the Multi-Level Feedback Queue (MLFQ)?
Created by Fernando Corbato
We create a multi-level runtime queue and follow this algorithm:
1) When a task is first created we put it in the first queue, which has the smallest timeslice.
2) If the task yields voluntarily (e.g., I/O) then we keep it at this level, else if that task uses up the whole timeslice we push it to the next queue, which has a longer timeslice.
3) If a task in the second or third queue yields voluntarily then it gets a priority boost
MLFQ != Priority Queues
- different treatment of threads at each level
- incorporates feedback
How does the Linux O(1) Scheduler Work?
Pros/Cons?
O(1) == constant time to select/add task, regardless of task count
premtive, priority-based
TODO
Pros:
- TODO
Cons:
- performance of interactive tasks (b/c tasks don’t get a chance to run again until all tasks on the active queue have run there’s often a “jitter”)
- no fairness guarantees
How does the Linux Completely Fair Scheduler (CFS) work?
Pros/Cons?
TODO
What is cache affinity and why is it important to CPU scheduling?
We want the OS scheduler to keep a task on the same CPU as much as possible so that the cache is more likely to be hot, which gives us a performance boost.
What is a per-CPU runqueue & scheduler and why might it improve performance?
Load balance across CPUs based on queue lenght or CPU idle time.
Can improve cache affinity (liklihood that cache will be hot b/c we’re running the same task there multiple times instead of on a different cpu each time)
What is NUMA and NUMA-aware scheduling?
Non-Uniform Memory Access
- multiple memory nodes
- memory node closer to a “socket” of multiple processors
- access to local memory node faster than access to remote memory node
NUMA-aware scheduling
- keep tasks on the CPU closer to memory node where their state is
What is hyperthreading?
- multiple hardware-supported execution contexts
- still 1 CPU but context switching is very fast (b/c we just switch the register we use, no need to reload data)
What are the pros/cons of co-scheduling compute and memory bound threads?
Pros:
- avoid/limit contention on processor pipeline
- all components (CPU and memory) well utilized
Cons:
- still leads to interference and degredation, but minimal
How can we determine if a thread is CPU-bound or memory-bound?
Use historic information
“Sleep time” won’t work b/c the thread is not sleeping when waiting on a memory reference. Software takes too much time to compute so we need some hardware-level information
Instead, hardware counters can help the scheduler estimate the kind of resources a thread needs.
