Scheduling Flashcards
What is multiprogramming?
Keeping multiple programs in memory and running them so that CPU use is high
Most _______ will not be busy all the time
programs
_________ algorithms increase CPU use by switching between tasks
scheduling
An I/O-bound process/thread spends more time in ____
I/O
An example of an I/O bound process is …
web server connection handling
An CPU-bound process/thread pends more time in…
CPU
An example of a CPU-bound process is…
scientific computing
A long-term scheduler is also known as a ____ ________
job scheduler
a Long-term scheduler selects which processes should be brought into the ______ ______
ready queue
a Long-term scheduler controls the degree of _________________
multiprogramming
a Long-term scheduler is invoked _________
infrequently
a Long-term scheduler should have a good mix of __________ and ________ jobs in the system
CPU-Bound, I/O-bound
A short-term scheduler is also known as a ____ ________
CPU scheduler
A short-term scheduler selects which process should be executed next and allocates _____ to it
CPU
A short-term scheduler is invoked _________
frequently
A _______-term scheduler swaps processes in and out of ready queue to enhance performance
medium
Non-preemptive scheduling makes it so that once a process is __________ a CPU, it does not _______ unless it has to _____ or it ________
allocated, leave, wait, terminates
Preemptive scheduling makes it so that the __ can force a process from CPU at __________
OS, anytime
An OS will preempt a process when there is another _______ ______ process
higher priority
________ scheduling is harder to implement because data _______ needs to be maintained between processes and _____ data structures
preemptive, consistency, kernel
What does a dispatcher do?
Allocates CPU to a process selected by a scheduler to run
What steps are involved in the dispatcher allocates CPU?
- Switch context
- Switch to user mode
- Jumping to the proper location in the selected process and starting it
________ _______ is the time taken for the dispatcher to stop one process and start another
dispatch latency
A scheduler wants to maximize ___ ____________ and _________
CPU, utilization, throughput
A scheduler wants to minimize _________ time, ________ time, and _______ time
turnaround, waiting, response
What does turnaround time measure?
amount of time to execute a process from submission to termination
What are the 7 scheduling algorithms?
- First come first served
- Shortest Job First
- Shortest Remaining Time First
- Priority
- Round Robin
- Multilevel Queue Scheduling
- Multilevel Feedback Queue Scheduling
In ___________________ scheduling, the processes are executed in arriving order
First come first serve
The average waiting time for the FCFS scheduler is very ________
dynamic
What does the convoy effect describe in FCFS scheduling?
short processes wait for on long process to get of CPU
The _______ _____ leads to low CPU and device utilization
convoy effect
SJF schedules the process with the _______ CPU burst time
shortest
What does SJF always optimize?
average waiting time for a set of processes
The ______ of a CPU burst is available for _____-_____ schedulers, but not ______-_____ schedulers
length, long-term, short-term
In ________ SJF, it predicts the next burst based on previous bursts
approximate
SRTF is __________
preemptive
In priority scheduling, the process with the ______ priority is scheduled first
highest
What is priority?
An integer associated with each process
Priority scheduling can be both _________ and ______
preemptive, non-preemptive
What factors are priority for a process based on?
- Time limits
- Memory Requirements
- Number of Open Files
- External factors
Priority Scheduling is prone to _________, where ____ priority processes never _______
starvation, low, execute
A possible solution to starvation in priority scheduling is to have dynamic ______ scaling with age or something
priority
If priority is the inverse of CPU burst length, Priority Scheduling becomes…
SJF
In RR scheduling, a time quantum q is a length of _____ _______
CPU time
In RR scheduling, each ______ gets a small unit of ____ _______
process, CPU, time
In RR scheduling, after q elapses, the current process is _______ and added to the _______ ______
preempted, ready, queue
In RR scheduling, if there are n processes in the ready queue, how much time does each process get?
1/n
In RR scheduling, processes wait at most how long before executing?
(n-1)q
RR scheduling has a higher _______ time than ___, but has a better response time
turnaround, SJF
If q is ______, RR becomes like FCFS
large
If q is _______, RR has high overhead due to many context switches but is more responsive
small
A good rule of thumb for RR is that __% of CPU bursts should be shorter than q
80
In Multilevel Queue Scheduling, the _____ queue is partitioned into ______ queues
ready, multiple
In Multilevel Queue Scheduling, each queue has its own ___________ _________
scheduling algorithm
In Multilevel Queue Scheduling, there needs to be a master ________ that manages all the queues
scheduler
In Multilevel Feedback Queue Scheduling, a process can _______ ________ queues
move between
In Multilevel Feedback Queue Scheduling, the key idea is to move ________ to _____ priority queues if it takes too much CPU time
processes, lower
In Multilevel Feedback Queue Scheduling, what 4 things do we need to define?
- Number of queues
- Scheduling algorithm for each queue
- Method to move process up/down in queues
- Start queue for each process
Describe the life of a long process in Multilevel Feedback Queue Scheduling
- New job enters Q0
- Gets8 ms (RR)
- If it does not finish, move to Q1
- More 16 ms (RR)
- If still needs more, moved to Q2
- Will run until it finishes (FCFS)
Multilevel Feedback Queue Scheduling gives higher _________ and ________
responsiveness, throughput
In Multiple Processor scheduling, we need to divide _____ among _______ processors
load, multiple
To divide the load for Multiple Processor scheduling, we can use __________ or __________ multiprocessor
asymmetric, symmetric
A __________ multiprocessor has one processor that ________ all others
asymmetric, schedules
A ________ multiprocessor has a ______ for each process
symmetric, scheduler
In a symmetric multiprocessor, there can be a ready queue for ___ processors, or have a _____ ready queue for each processor
all, separate
______ ________ is when a process runs on a processor, some data is brought in to that processor’s cache
process affinity
What happens when a process migrates to another processor? (4 things)
- Cache of new processor has to be re-populated
- Cache of old processor has to be invalidated
- Performance penalty
- Extra interconnect traffic (NUMA effect)
the command __________ sets processor affinity for a program
taskset
What is load balancing in SMP?
Ensuring load is evenly distributed among processors
In SMP, loads can be balanced using ____ and ____ migration
push, pull
What is push migration?
A specific task periodically checks load on all processors and evenly distributes it by moving tasks
What is pull migration?
Idle processor pulls a waiting task from a busy processor
An issue of SMP is making a tradeoff between _____ _______ and __________ _______
load balancing, processor affinity
In ______________ time systems, a task must be finished within a deadline and different schedulers are used to ensure this
hard-real
In ___________ time systems, tasks have no strict deadline, but should be executed quickly
soft-real
Soft-real time systems use what type of scheduler?
priority based with preemption
What are the 2 separate scheduling classes in the Completely Fair Scheduler?
Real-time processes and normal processes
In the CFS, _______ processes have a higher priority and uses ______ and ____ scheduling algorithms
real time, FIFO, RR
In the CFS, ________ processes have a lower priority and uses the ______ scheduling algorithm
CFS
A nice value ranges from…
-20 to 19
A lower nice value means ______ priority
higher
In the CFS, each process gets a time portion based on _____ _______
nice value
Nice value -20 maps to global priority ____
100
Nice value 19 maps to global priority _____
139
In the CFS, _________ ____ ____ is used to automatically determine priority
Virtual run time
Virtual run is calculated with _____ run time and ______
physical, decay
Priority is ________ proportional to virtual run time
inversely
______ is allowed in the virtual run time
preemption
