Preemptive Operating System Flashcards
(137 cards)
1
Q
What are 3 characteristics of reactive systems?
A
respond to external events, require real-time responses, and may require chain reaction among multiple processors
2
Q
What is most important in an embedded system?
A
time
3
Q
What is a task?
A
a functional description of a connected set of operations (can also mean a collection of processes)
4
Q
What is a process?
A
a unique execution of a program
5
Q
True or false: Only one copy of a program may run at one time?
A
false, several copies may run simultaneously or at different times
6
Q
Fill in the blank: A process has its own _______.
A
state (registers, memory)
7
Q
What manages processes?
A
the operating system
8
Q
What does multiple tasks mean?
A
multiple processes
9
Q
What do processes help with?
A
timing complexity
10
Q
How do processes help with timing complexity?
A
multiple rates and asynchronous input
11
Q
In multi-rate systems are tasks asynchronous or synchronous?
A
they can be both
12
Q
Can synchronous tasks recur at different rates?
A
yes
13
Q
Processes run at different rates based on what?
A
computational needs of tasks
14
Q
What is an example of tasks with differing rate requirements?
A
in engine control: spark control, crankshaft sensing, fuel/air mixture, oxygen sensor, and Kalman filter
15
Q
How do real-time systems conform to external timing constraints?
A
performing computations
16
Q
What are the 2 types of deadline frequencies?
A
periodic and aperiodic
17
Q
What are 3 types of deadlines?
A
hard, soft, and firm
18
Q
What is a hard deadline?
A
failure to meet deadline causes system failure
19
Q
What is a soft deadline?
A
failure to meet deadline causes degraded response
20
Q
What is a firm deadline?
A
late response is useless but some late responses can be tolerated
21
Q
What is an example of a hard deadline application?
A
braking system control
22
Q
What are examples of soft deadline applications?
A
web browsing, video loading
23
Q
What are examples of firm deadline applications?
A
video conferencing, satellite-based surveillance
24
Q
What is the release time?
A
the time at which the process becomes ready
25
What is a deadline?
the time at which the process must finish
26
What is a periodic process?
a process that executes in almost every period
27
What is an aperiodic process?
a process that executes on demand
28
Which type of process (periodic or aperiodic) is harder to analyze and why?
aperiodic because you must consider worst-case combinations of process activation
29
What is a period?
interval between process activations
30
What is the rate?
reciprocal of period (aka frequency)
31
Can the initiation rate be higher than the period?
yes, several copies of the process can run at once
32
What is the process execution time?
execution time in absence of preemption
33
What are the possible time units for process execution time?
seconds or clock cycles
34
What are some sources of variation for process execution time?
data dependencies, memory system, and CPU pipeline
35
What does it mean for a task to have a data dependency?
they must execute in a certain order
36
What do task graphs show?
data/control dependencies between processes
37
In the setting of task graphs, what is a task?
a connected set of processes
38
What is a task set?
one or more tasks
39
What is CPU utilization?
the fraction of the CPU that is doing useful work
40
What do we assume when we calculate CPU utilization?
that there is no scheduling overhead
41
How do you simply calculate CPU utilization?
(CPU time for useful work)/(total available CPU time)
42
What are the 3 states that a process can be in?
execution on the CPU, ready to run, or waiting for data
43
What does a task graph assume?
all tasks run at same rate and tasks do not communicate
44
In reality, do tasks communicate with each other?
yes some communication is necessary
45
What is interprocess communication (IPC)?
OS provided mechanisms so that processes can pass data
46
What are the 2 types of semantics for IPC?
blocking and non-blocking
47
What does blocking mean regarding IPC?
sending process waits for response
48
What does non-blocking mean regarding IPC?
sending process continues
49
What are some different IPC styles?
shared memory, message passing, and signal
50
What is the shared memory IPC style?
processes have some memory in common and must cooperate to avoid destroying/missing messages
51
What is the message passing IPC style?
processes send messages along a communication channel with no common address space
52
What is the signal IPC style?
similar to interrupt but a software creation and is generated by a process and passed by the OS
53
What problem can happen with shared memory?
race conditions
54
What is a critical region?
a section of code that cannot be interrupted by another process
55
What are some examples of critical regions?
writing shared memory, and accessing I/O devices
56
What is a semaphore?
OS primitive for controlling access to critical regions
57
What is the atomic test-and-set?
single bus operation reads memory location, tests it, writes it
58
What is the protocol of the atomic test-and-set?
get access to semaphore (P()), perform critical region operations, release semaphore (V())
59
How do you run periodic processes?
you need code to control the processes
60
What is the simplest implementation of running periodic processes?
process = subroutine
61
How many loops does the simplest implementation of running periodic processes use?
one while loop
62
What is the problem with using one while loop to control processes?
no control over execution timing
63
What is the timed loop implementation?
encapsulate set of all processes in single function that implements a task set, the use a timer to control the execution of the task
64
What is the problem with the timed loop implementation?
no control over timing of individual processes
65
What is the multiple timers implementation?
each task has its own function and timer
66
What is the problem with the multiple timers implementation?
may not have enough timers to implement all the rates
67
Are the while loop, timed loop, and multiple timers implementations sufficient for real-time systems?
no
68
How do real-time systems handle implementing processes?
OS scheduling support
69
What resources does the OS control?
who gets CPU, when I/O happens, how much memory is allocated
70
What is the most important resource?
the CPU itself
71
How is CPU access controlled?
by the scheduler
72
What does the OS need to keep track of?
process priorities, scheduling state, process activation record
73
When can processes be created?
statically before system starts or dynamically during execution
74
What are some types of conventional scheduling?
FCFS (first come first serve) and SJF (Shortestjob first)
75
What is SJF scheduling?
associates each process with the length of its next CPU burst and uses these lengths to schedule the process with the shortest time
76
Why is SJF optimal?
it gives the minimum average waiting time for a set of processes
77
What is the difficulty with SJF?
knowing the length of the next CPU request
78
True or false: With SJF you can exactly calculate the length of the next CPU burst?
false, you can only estimate
79
How can you estimate the length of the next CPU burst for SJF?
exponential averaging T(n+1) = a*tn + (1-a) Tn (tn = actual length of nth CPU burst, Tn+1 = predicted value for the next CPU burst, Tn = previously expected value)
80
What is preemptive SJF scheduling?
once a new process comes in, its burst length is compared with the currently running process, then the shorter one is chosen, and then the remaining processes are scheduled in terms of shortest to longest burst length
81
What is priority-driven scheduling?
each process has a priority and CPU goes to highest priority ready process
82
What kind of scheduling policies are there?
fixed priority and time-varying priorities (aging)
83
What must we avoid with scheduling?
starving processes of CPU access (fairness)
84
What is a problem with priority scheduling?
since embedded systems must meet deadlines, some may be missed if a low-priority process is not run for a while
85
What is the scheduling problem?
can we meet all deadlines and how much CPU do we need to meet the deadlines
86
What makes schedulability analysis NP-hard?
resource constraints
87
What is scheduling feasibility?
showing that the deadlines are met for all timings of resource requests
88
What is a simple processor feasibility analysis?
assuming no resource conflicts and constant execution times, and requiring T>=Ei*Ti (can't use more than 100% of the CPU)
89
What is the hyperperiod?
least common multiple of the task periods
90
What must you do to find all task interactions?
hyperperiod schedule
91
When can hyperperiod be very long?
if task periods are not chosen carefully
92
What is TDMA scheduling algorithm?
scheduling in time slots (same process activation regardless of workload
93
What is the schedulability of TDMA?
always uses the same CPU utilization and assumes constant process execution times, so it can't handle unexpected loads
94
What do we assume with TDMA?
schedule based on LCM of process period and it's a trivial scheduler, time slots don't have to be equal in size
95
What is the round-robin scheduling algorithm?
schedules processes only if ready, similar to TDMA
96
What are some variations of constant system period?
constant system period, and start round-robin again after finishing a round
97
What do we assume with round-robin?
schedule based on LCM, best done with equal time slots for processes, simple schedule that can be implemented in hardware
98
What is the scheduling feasibility of round-robin?
can be adapted to handle unexpected load, may have unused CPU cycles
99
What is the overhead for round-robin?
not all CPU available for processes due to scheduling using some CPU time
100
When can overhead be ignored?
if it is a small fraction of total execution time
101
How do we evaluate a scheduling policy?
ability to satisfy all deadlines, CPU utilization, and scheduling overhead
102
What are two general types of RTOS scheduling?
rate monotonic and earliest-deadline-first
103
What is rate monotonic scheduling also known as?
RMA
104
What is the RMA model?
all processes run on single CPU, no context switch time, not data dependencies, process execution time is constant, deadline is at end of period, highest-priority ready process runs
105
What is response time?
time required to finish process
106
What is the critical instant?
scheduling state that gives worst response time (occurs when all higher priority processes are ready to execute)
107
What are RMS priorities?
optimal (fixed) priority assignment: shortest period process gets highest priority, period inversely proportional to period, break ties arbitrarily
108
Fill in the blank: With RMS as the number of tasks approaches infinity, the maximum CPU utilization approaches ________.
69%
109
Can RMS use 100% of the CPU?
no
110
Why can't RMS use 100% of the CPU?
it must keep the idle cycles available to handle worst-case scenario
111
What is the biggest positive about RMS?
it guarantees all processes will always meet their deadlines
112
What type or scheduling scheme is EDF?
earliest deadline first, dynamic priority scheduling scheme
113
What is the meaning of aging priority?
the process closest to its deadline has highest priority
114
Since the priorities are dynamic, what has to happen with EDF?
requires recalculating process priorities at every timer interrupt
115
How is EDF different from RMS?
it can use 100% of the CPU but it may fail to meet deadlines
116
Is EDF used in practice?
no its too expensive
117
What are measures to take if your set of processes is unschedulable?
change deadline requirements, reduce execution times of processes, or get a faster CPU
118
What is priority inversion?
low-priority process keeps high-priority process from running
119
What problems can priority inversion cause?
low-priority process takes I/O device and high-priority device needs I/O but can't get it until low-priority process is done (deadlock)
120
What can be done to solve priority inversion?
give system resources priorities and have processes inherit requested resource priority
121
How can we evaluate RTOS performance?
simplify assumptions: context switch costs no CPU time, know exact execution time of processes, WCET/WBET don't depend on context switches
122
What can push the limits of a tight schedule?
non-zero context switching time
123
Why is it hard to calculate the effects of context switches?
the time depends on the order of the context switches
124
How does context switching compare to common task periods in practice?
it is usually much much smaller
125
How does process execution time different from our assumptions?
process execution time is not constant
126
How can extra CPU time from non constant processes cause problems?
if next process runs earlier, it can cause a new preemptions
127
What other problems can processes cause?
they can cause caching problems
128
How does worst-case execution time with bad behavior differ from execution time with good cache behavior?
it is much worse
129
What is power management?
determining how system resources are scheduled/used to control power consumption
130
How does the OS manage power?
the same way it manages time
131
How does the OS reduce power?
shutting down unused units
132
What are a few simple power management policies?
request-driven or predictive shutdown
133
What is request-driven power management?
power-up once request is received (which adds delay to response)
134
What is predictive shutdown?
trying to predict how long you have before next request
135
What are positives and negatives of predictive shutdown?
may start up in advance of request meaning no response delay, but if the prediction is wrong it may incur additional delay while starting up
136
What is probabilistic shutdown?
assuming service requests are probabilistic, you shutdown after time T_on then turn back on after T_off
137
What does probabilistic shutdown optimize?
power consumption and response time
