Scheduling Flashcards
Scheduling
Policies that the OS employs to determine the execution order of ready processes/threads (& which core to execute on multicore systems)
CPU utilization
Percentage of time CPU is busy executing jobs
Throughput
The number of processes completed in a given amount of time
Turnaround time
The time elapsed between the arrival and completion of a process
Waiting time
The time a process spends in the ready queue
Response time
The time elapsed between the process’ arrival and its first output
What two metrics does scheduling aim to maximize?
CPU utilization and throughput
What three metrics does scheduling aim to minimize?
Turnaround time, waiting time and response time
What assumptions for workloads do we make?
Each job runs for the same amount of time
All jobs arrive at the same time
All jobs only use the CPU
Run-time of each job is known
Once started, each jobs runs to completion (preemption)
First In First Out (FIFO)
First Come, First Served (FCFS)
Policy: Jobs are executed in arrival time order
Convoy effect
A scheduling phenomenon in which a number of jobs wait for one job to get off a core, causing overall device and CPU utilization to be suboptimal
What is a possible negative consequence of the First In First Out scheduling algorithm?
Convoy effect
Shortest Job First (SJF)
Policy: The jobs with the shortest execution time are scheduled first
If all assumptions for workloads are true, what is the optimal scheduling algorithm in terms of average waiting time?
SJF
Shortest-Time-To-Complete-First (STCF)
Policy: Always switch to jobs with the shortest completion time
What are the two non-preemptive scheduling algorithms?
FIFO and SJF
What sort of scheduler is STCF?
Preemptive
What is a possible negative consequence of STCF?
Starvation
Response time
T_firstrun - T_arrival
Round-Robin is a better scheduler with regards to which metric?
Response time
Time quantum/time slice/scheduling quantum
A fixed and small amount of time units
Round-Robin (RR)
Policy: Each process executes for a time slice. Switches to another process regardless of whether it has completed its execution or not
If the job in a Round-Robin scheduler hasn’t yet completed its execution, what happens?
The incomplete job is added to the tail of the ready FIFO queue
RR is a good scheduler in terms of…
response time
RR is a poor scheduler in terms of…
turnaround time
What scheduler is starvation-free?
RR
What workload assumption is the incorporation of I/O based on?
Run-time of each job is known
How do we incorporate I/O with scheduling?
By treating each CPU burst as a job; then processes performing I/O can run frequently, while other CPU intensive jobs run
STCF is an optimal scheduling algorithm with regards to minimizing which performance metric?
Average turnaround time; if all jobs know their execution times in prior
RR is an good scheduling algorithm with regards to minimizing which metric?
Average response time
What is priority-based scheduling?
Scheduling based on priority levels assigned to each process
What are the three priority-based scheduling algorithms?
FIFO, SJF, STCF
What is a negative consequence of priority-based scheduling?
Starvation
What two forms of scheduling does a Multi-Level Queue (MLQ) combine?
Priority-based scheduling & RR
MLQ optimizes … for computation-intensive programs
turnaround time
MLQ minimizes … for interactive programs
response time
Multi-Level-Feedback Queue (MLFQ) optimizes turnaround time by
running shorter jobs first
Multi-Level-Feedback Queue minimizes response time by
attempting to make a system feel responsive for interative users
Multi-Level-Feedback-Queue (MLFQ) varies the priority of a job based on what?
Its observed behavior
Allotment
The amount of time a job can spend at a given priority level before the scheduler reduces its priority
What rules does the MLFQ have?
- If Priority(A) > Priority(B), A runs
- If Priority(A) = Priority(B), A & B run in RR using the time slice of the given queue
- When a job enters the system, it’s placed at the highest priority
- Once a job uses up its time allotment, its priority is reduced
- After some time period, move all jobs in the system to the topmost queue (highest priority)
What doesn’t the MLFQ require prior knowledge of?
The CPU usage of a process
What is the MLFQ scheduler defined by?
Number of queues
Time slice of each queue
Boosting period
Scheduling algorithm for each queue
What does the high priority queue in a MLFQ scheduler optimize?
Response time
What does the low priority queue of a MLFQ scheduler optimize?
Turnaround time
Fairness
To guarantee the fair usage of CPU (CPU time)
What is a fair-share scheduler?
A scheduler that guarantees that each job obtains a certain percentage of CPU time
Describe a probabilistic way to implement lottery scheduling
Time slice
Scheduler knows how man tickets exists
Scheduler picks a winning ticket from the ticket pool for each time slice
What is the objective of Completely Fair Scheduling (CFS)?
To fairly divide a CPU evenly among all competing processes.
Describe the Completely Fair Scheduling method
Choose the process with the lowest virtual runtime
Run each process for a time slice
Determine the time slice based on sched_latency and the number of processes
What is virtual runtime (vruntime)?
Denotes how long a process has executed
What is sched_latency?
Used to determine the time slice. Typical value is 48 ms
Describe the equation for a process’ time slice
sched_latency / the number of processes
What parameter do we have in addition to sched_latency to ensure that there are never too many processes running?
min_granularity. Set to 6 ms.
How does one enable control over process priority in CFS?
Niceness (user-space) values
What do positive niceness values imply?
Lower priority
What do negative niceness values imply?
Higher priority
What sort of tree does a CFS deploy?
A red-black tree; balanced binary search tree
What is the insertion, deletion and update complexity of the red-black tree deployed by CFS?
O(log N)
What is the find min complexity of the red-black tree deployed by CFS?
O(1)
What is the red-black tree deployed by CFS ordered by?
vruntime, as a key
What does the deploying of a red-black tree in CFS ensure?
Low scheduling overhead
How does CFS deal with I/O and sleep?
Setting the vruntime of a wake-up process to the minimum value found in the RB-tree
How does CFS boost interactivity?
I/O-bound (interactive) processes typically have shorter CPU bursts and thus will have a lower vruntime –> higher priority
How are CPU-bursts scheduled when I/O is considered?
As sub-jobs
What two scheduling algorithms does MLFQ combine?
RR and priority-based scheduling
What does proportional share scheduling strive to guarantee for each job?
That they all receive a desired amount of CPU time
What is CFS based on?
vruntime; to determine the execution order
What are the three types of multiprocessors?
- Multicore processor
- Multiprocessor
- Multithreaded cores
What does the cache of a CPU contain?
Small & fast form of memory
Holds copies of popular data found in main memory
What sorts of locality does the cache utilize?
Temporal and spatial
What does the main memory of a CPU contain?
Holds all the data
Is access to the main memory faster or slower than access to the cache?
Slower
What does a multiprocessor with cache have to ensure the consistency of?
Shared resource data stored in multiple caches
Define cache affinity
The storing of certain states that a process has in the cache of a CPU
Will a process run faster or slower if its executed on the same CPU as it has cache affinity for?
Faster
What sort of affinity should a multiprocessor scheduler consider when making its scheduling decision?
cache affinity
What does Single-Queue Multiprocessor Scheduling (SQMS) do?
Puts all jobs that need to be scheduled into a single queue
What sort of multiprocessing does SQMS use? (asymmetric/symmetric)
Asymmetric
How many processors/cores manage the scheduling queue when using SQMS?
One
What are the pros of SQMS?
Simple
Reduced data sharing
What are the cons of SQMS?
Locking has to be inserted -> lack of scalability
Cache affinity
What does Multi-Queue Multiprocessor Scheduling (MQMS) consist of?
Multiple scheduling queues
Does each processor in MQMS have its own scheduler?
Yes
What sort of multiprocessing does MQMS use? (asymmetric/symmetric)
Symmetric
What are the pros of MQMS?
Better cache affinity
Scalability
What are the cons of MQMS?
Load imbalance
What is the solution to load imbalance in MQMS?
Migration; switching jobs between processors
Define processor affinity
The binding of jobs to specific cores
Define soft affinity
Jobs are expected to execute on a single processor, but it’s possible to migrate them between processors
What term does this define: jobs are specified to a subset of processors?
Hard affinity
What sort of processing is described below?
Jobs are scheduled to different cores to minimize power consumption while providing the required performance by using heterogeneous cores on a single chip
Heterogeneous multiprocessing
What is a simple but unscalable method for scheduling on multiprocessor systems?
SQMS
What is the widely used scheduling method for modern multiprocessor systems?
MQMS
What architecture introduce new challenges for scheduling?
Heterogeneous architecture
