Scheduling Flashcards
(111 cards)
1
Q
Scheduling
A
Policies that the OS employs to determine the execution order of ready processes/threads (& which core to execute on multicore systems)
2
Q
⭐️ CPU utilization
A
Percentage of time CPU is busy executing jobs
3
Q
⭐️ Throughput
A
The number of processes completed in a given amount of time
4
Q
⭐️ Turnaround time
A
The time elapsed between the arrival and completion of a process
5
Q
⭐️ Formula for turnaround time
A
T_t = T_c - T_a
6
Q
⭐️ Waiting time
A
The time a process spends in the ready queue
7
Q
⭐️ Response time
A
The time elapsed between the process’ arrival and its first output
8
Q
⭐️ What two metrics does scheduling aim to maximize?
A
CPU utilization and throughput
9
Q
⭐️ What three metrics does scheduling aim to minimize?
A
Turnaround time, waiting time and response time
10
Q
What 5 assumptions for workloads do we make?
A
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)
11
Q
What’s preemption?
A
The ability of the OS to stop/pause a currently scheduled task in favour of a higher priority task
12
Q
⭐️ First In First Out (FIFO)
A
First Come, First Served (FCFS)
Policy: Jobs are executed in arrival time order
13
Q
⭐️ Convoy effect
A
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
14
Q
⭐️ What does the First In First Out scheduling algorithm suffer from?
A
Convoy effect
15
Q
⭐️ Shortest Job First (SJF)
A
Policy: The jobs with the shortest execution time are scheduled first
16
Q
⭐️ If all jobs start simultaneously & know their execution times in prior, what is the optimal scheduling algorithm in terms of average waiting time?
A
SJF
17
Q
⭐️ Shortest-Time-To-Complete-First (STCF)
A
Policy: Always switch to jobs with the shortest completion time
18
Q
⭐️ What are the two non-preemptive scheduling algorithms?
A
FIFO and SJF
19
Q
⭐️ What sort of scheduler is STCF?
A
Preemptive
20
Q
⭐️ What is a possible negative consequence of STCF?
A
Starvation
21
Q
⭐️ If all jobs know their execution times in prior, which scheduler is optimal in terms of minimizing average waiting time?
A
STCF
22
Q
⭐️ Response time
A
T_firstrun - T_arrival
23
Q
⭐️ Round-Robin (RR)
A
Policy: Each process executes for a time slice. Switches to another process regardless of whether it has completed its execution or not
24
Q
⭐️ If the job in a Round-Robin scheduler hasn’t yet completed its execution, what happens?
A
The incomplete job is added to the tail of the ready FIFO queue
25
⭐️ If there are n processes in the ready queue & the time quantum is q, no process waits more than ... time units
(n-1)q
26
⭐️ What 2 scheduling metrics depend on the time quantum size?
Turnaround time & response time
27
⭐️ How does a higher time quantum affect the turnaround time & response time?
Lower turnaround time & higher response time
28
⭐️ Round-Robin is a poor scheduler with regards to which metric?
Turnaround time
29
⭐️ Time quantum/time slice/scheduling quantum
A fixed and small amount of time units
30
⭐️ Round-Robin is a better scheduler with regards to minimizing which metric?
Average response time
31
⭐️ What scheduler is starvation-free?
RR
32
A long time slice in RR could cause it to behave like FIFO (T/F)
T
33
A short time slice in RR could lead to high scheduling overhead (T/F)
T
34
Compared to SJF and STCF, RR with an appropriate time slice can improve the average response time & waiting time for a task set (T/F)
T
35
Increasing the time slice in RR typically increases the average turnaround time (T/F)
F
36
What workload assumption is the incorporation of I/O based on?
Run-time of each job is known
37
How do we incorporate I/O with scheduling?
By treating each CPU burst as a sub job
38
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
39
RR is an good scheduling algorithm with regards to minimizing which metric?
Average response time
40
What is priority-based scheduling?
Scheduling based on priority levels assigned to each process, and the process with the highest priority always being scheduled
41
What are the three special priority-based scheduling algorithms?
FIFO, SJF, STCF
42
What are the 2 types of priority based scheduling?
Preemptive & non-preemptive
43
What are the 2 types of priority assignment methods?
External & internal (in relation to the OS)
44
In Unix-like OS what does a small number say about the priority?
Higher priority
45
What is a negative consequence of priority-based scheduling?
Starvation
46
What two forms of scheduling does a Multi-Level Queue (MLQ) combine?
Priority-based scheduling & RR
47
MLQ optimizes ... for computation-intensive programs
turnaround time
48
MLQ minimizes ... for interactive programs
response time
49
How does the MLQ algorithm work?
Maintains a number of queues with different priority levels. Jobs are assigned to a queue & jobs on the same queue have the same priority.
50
What is the advantage of the MLQ algorithm?
Low scheduling overhead
51
What is the disadvantage of the MLQ algorithm?
Inflexible
52
⭐️ Multi-Level-Feedback Queue (MLFQ) optimizes turnaround time by
running shorter jobs first
53
⭐️ Multi-Level-Feedback Queue minimizes response time by
attempting to make a system feel responsive for interactive users
54
⭐️ MLFQ is a flexible scheduling algorithm that allows processes to move across
different queues
55
⭐️ Multi-Level-Feedback-Queue (MLFQ) varies the priority of a job based on what?
Its observed behavior
56
⭐️ What 5 rules does the MLFQ have?
1. If Priority(A) > Priority(B), A runs
2. If Priority(A) = Priority(B), A & B run in RR using the time slice of the given queue
3. When a job enters the system, it's placed at the highest priority
4. Once a job uses up its time allotment at a given level, its priority is reduced
5. After some time period S, move all jobs in the system to the topmost queue (highest priority)
57
⭐️ What 3 problems do the 5 rules of the MLFQ algorithm solve?
1. Starvation
2. Gaming of the scheduler
3. Changed behavior over time
58
⭐️ What doesn't the MLFQ require prior knowledge of?
The CPU usage of a process
59
⭐️ What is the MLFQ scheduler defined by?
Number of queues
Time slice of each queue
Boosting period
Scheduling algorithm for each queue
60
⭐️ Can the scheduling algorithm for each queue in a MLFQ scheduler be different?
Yes!
61
⭐️ What does the high priority queue in a MLFQ scheduler optimize?
Response time - Good for interactive processes
62
⭐️ What does the low priority queue of a MLFQ scheduler optimize?
Turnaround time - Good for batch / CPU-intensive processes
63
⭐️ Fairness
To guarantee the fair usage of CPU (CPU time)
64
⭐️ What is a fair-share scheduler?
A scheduler that guarantees that each job obtains a certain percentage of CPU time
65
⭐️ What does a fair share scheduler strive to guarantee that each job receives?
A desired amount of CPU time
66
⭐️ What two scheduling metrics is a fair share scheduler not optimized for?
Turnaround & response time
67
Describe a probabilistic way to implement lottery scheduling
Time slice
Scheduler knows how many tickets exists
Scheduler picks a winning ticket from the ticket pool for each time slice
68
What is the objective of Completely Fair Scheduling (CFS)?
To fairly divide a CPU evenly among all competing processes.
69
What are the 2 goals of CFS?
Simple - low scheduling overhead
Fair - among processes
70
⭐️ CFS is an efficient & scalable scheduling algorithm, based on vruntime to determine...
execution order
71
⭐️ Describe the Completely Fair Scheduling method
1. Choose the process with the lowest virtual runtime (vruntime)
2. Run each process for a time slice
3. Determine the time slice based on sched_latency and the number of processes
72
⭐️ What is virtual runtime (vruntime)?
A per-process variable that denotes how long a process has executed
73
vruntime increases in proportion with what when it runs?
physical (real) time
74
vruntime is associated with a ... factor
decay
75
⭐️ what's the formula for vruntime?
vruntimei + (weight0 / weighti)*runtimei
76
⭐️ What is sched_latency?
Used to determine the time slice. Typical value is 48 ms
77
If the number of processes is infinite, the minimum time slice value is set to:
6 ms
78
Describe the equation for a process' time slice
sched_latency / the number of processes
79
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.
80
time_slice_k =
weight_k / (sum_weight_i) * sched_latency
81
⭐️ How does one enable control over process priority in CFS?
Niceness (user-space) values
82
What do positive niceness values imply?
Lower priority
83
What do negative niceness values imply?
Higher priority
84
⭐️ What sort of efficient data structure does a CFS deploy?
A red-black tree; balanced binary search tree
85
⭐️ What is the insertion, deletion and update complexity of the red-black tree deployed by CFS?
O(log N)
86
⭐️ What is the find min complexity of the red-black tree deployed by CFS?
O(1)
87
What is the red-black tree deployed by CFS ordered by?
vruntime, as a key
88
⭐️ What does the deploying of a red-black tree in CFS ensure?
Low scheduling overhead
89
⭐️ 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
90
How does CFS boost interactivity?
I/O-bound (interactive) processes typically have shorter CPU bursts and thus will have a lower vruntime --> higher priority
91
How are CPU-bursts scheduled when I/O is considered?
As sub-jobs
92
What two scheduling algorithms does MLFQ combine?
RR and priority-based scheduling
93
What does proportional share scheduling strive to guarantee for each job?
That they all receive a desired amount of CPU time
94
What is CFS based on?
vruntime; to determine the execution order
95
Priority-based scheduling ensures fairness & avoids starvation. (T/F)
False; Priority-based scheduling doesn't guarantee fairness due to prioritization & they may suffer from starvation
96
Is this statement amount MLQ true or false?
All queues must use the same scheduling algorithm
False
97
Is this statement amount MLQ true or false?
All queues implement RR with the same time slice
False
98
Is this statement amount MLQ true or false?
Processes can move between different queues
False
99
Is this statement amount MLQ true or false?
MLQ has less scheduling overhead compared to MLFQ
True
100
Which rule for MLFQ ensures that no task monopolizes high-priority queues?
Rule 4: Once a job uses up its time allotment at a given level, its priority is reduced
101
Which rule prevent starvation in a MLFQ?
Rule 5: After some time period S, move all the jobs in the system to the topmost queue
102
Is this statement true or false?
Proportional Share Scheduling targets minimizing turnaround time
False - PSS only targets fairness
103
Is this statement true or false?
CFS is an example of proportional-share scheduling
True
104
Is this statement true or false?
Lottery Scheduling (LS) ensures that all tasks receive an equal share of resources
False - the share in LS depends on the number of tickets a task gets
105
Is this statement true or false?
Proportional Share Scheduling (PSS) targets guaranteeing fairness among tasks
True
106
How does the Completely Fair Scheduling (CFS) algorithm select the next job to schedule?
Job with the smallest virtual runtime (vruntime)
107
CFS allocates a fixed time slice to all tasks (T/F)
False
108
What properties does CFS use to determine the time slice for each job?
- sched_latency
- priority (weight)
- the number of runnable jobs (N)
109
What data structure does CFS employ to implement its scheduling algorithm?
Red-black tree
110
What is the complexity of CFS in terms of updating its RB tree?
O (log(n))
111
⭐️ Select the option that consists of 2 starvation-free scheduling algorithms.
1. SJF, STCF
2. FIFO, SJF
3. SJF, RR
4. FIFO, RR
4. FIFO, RR
