Preemptive Operating System Flashcards

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is most important in an embedded system?

A

time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a task?

A

a functional description of a connected set of operations (can also mean a collection of processes)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a process?

A

a unique execution of a program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Fill in the blank: A process has its own _______.

A

state (registers, memory)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What manages processes?

A

the operating system

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does multiple tasks mean?

A

multiple processes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What do processes help with?

A

timing complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How do processes help with timing complexity?

A

multiple rates and asynchronous input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

In multi-rate systems are tasks asynchronous or synchronous?

A

they can be both

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Can synchronous tasks recur at different rates?

A

yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Processes run at different rates based on what?

A

computational needs of tasks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How do real-time systems conform to external timing constraints?

A

performing computations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the 2 types of deadline frequencies?

A

periodic and aperiodic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are 3 types of deadlines?

A

hard, soft, and firm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is a hard deadline?

A

failure to meet deadline causes system failure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a soft deadline?

A

failure to meet deadline causes degraded response

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is a firm deadline?

A

late response is useless but some late responses can be tolerated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is an example of a hard deadline application?

A

braking system control

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are examples of soft deadline applications?

A

web browsing, video loading

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What are examples of firm deadline applications?

A

video conferencing, satellite-based surveillance

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the release time?

A

the time at which the process becomes ready

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is a deadline?

A

the time at which the process must finish

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is a periodic process?

A

a process that executes in almost every period

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is an aperiodic process?

A

a process that executes on demand

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Which type of process (periodic or aperiodic) is harder to analyze and why?

A

aperiodic because you must consider worst-case combinations of process activation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is a period?

A

interval between process activations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is the rate?

A

reciprocal of period (aka frequency)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Can the initiation rate be higher than the period?

A

yes, several copies of the process can run at once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is the process execution time?

A

execution time in absence of preemption

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What are the possible time units for process execution time?

A

seconds or clock cycles

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What are some sources of variation for process execution time?

A

data dependencies, memory system, and CPU pipeline

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What does it mean for a task to have a data dependency?

A

they must execute in a certain order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What do task graphs show?

A

data/control dependencies between processes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

In the setting of task graphs, what is a task?

A

a connected set of processes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What is a task set?

A

one or more tasks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What is CPU utilization?

A

the fraction of the CPU that is doing useful work

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

What do we assume when we calculate CPU utilization?

A

that there is no scheduling overhead

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

How do you simply calculate CPU utilization?

A

(CPU time for useful work)/(total available CPU time)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

What are the 3 states that a process can be in?

A

execution on the CPU, ready to run, or waiting for data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

What does a task graph assume?

A

all tasks run at same rate and tasks do not communicate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

In reality, do tasks communicate with each other?

A

yes some communication is necessary

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

What is interprocess communication (IPC)?

A

OS provided mechanisms so that processes can pass data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

What are the 2 types of semantics for IPC?

A

blocking and non-blocking

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

What does blocking mean regarding IPC?

A

sending process waits for response

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

What does non-blocking mean regarding IPC?

A

sending process continues

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

What are some different IPC styles?

A

shared memory, message passing, and signal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

What is the shared memory IPC style?

A

processes have some memory in common and must cooperate to avoid destroying/missing messages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

What is the message passing IPC style?

A

processes send messages along a communication channel with no common address space

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

What is the signal IPC style?

A

similar to interrupt but a software creation and is generated by a process and passed by the OS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

What problem can happen with shared memory?

A

race conditions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

What is a critical region?

A

a section of code that cannot be interrupted by another process

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

What are some examples of critical regions?

A

writing shared memory, and accessing I/O devices

56
Q

What is a semaphore?

A

OS primitive for controlling access to critical regions

57
Q

What is the atomic test-and-set?

A

single bus operation reads memory location, tests it, writes it

58
Q

What is the protocol of the atomic test-and-set?

A

get access to semaphore (P()), perform critical region operations, release semaphore (V())

59
Q

How do you run periodic processes?

A

you need code to control the processes

60
Q

What is the simplest implementation of running periodic processes?

A

process = subroutine

61
Q

How many loops does the simplest implementation of running periodic processes use?

A

one while loop

62
Q

What is the problem with using one while loop to control processes?

A

no control over execution timing

63
Q

What is the timed loop implementation?

A

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
Q

What is the problem with the timed loop implementation?

A

no control over timing of individual processes

65
Q

What is the multiple timers implementation?

A

each task has its own function and timer

66
Q

What is the problem with the multiple timers implementation?

A

may not have enough timers to implement all the rates

67
Q

Are the while loop, timed loop, and multiple timers implementations sufficient for real-time systems?

A

no

68
Q

How do real-time systems handle implementing processes?

A

OS scheduling support

69
Q

What resources does the OS control?

A

who gets CPU, when I/O happens, how much memory is allocated

70
Q

What is the most important resource?

A

the CPU itself

71
Q

How is CPU access controlled?

A

by the scheduler

72
Q

What does the OS need to keep track of?

A

process priorities, scheduling state, process activation record

73
Q

When can processes be created?

A

statically before system starts or dynamically during execution

74
Q

What are some types of conventional scheduling?

A

FCFS (first come first serve) and SJF (Shortestjob first)

75
Q

What is SJF scheduling?

A

associates each process with the length of its next CPU burst and uses these lengths to schedule the process with the shortest time

76
Q

Why is SJF optimal?

A

it gives the minimum average waiting time for a set of processes

77
Q

What is the difficulty with SJF?

A

knowing the length of the next CPU request

78
Q

True or false: With SJF you can exactly calculate the length of the next CPU burst?

A

false, you can only estimate

79
Q

How can you estimate the length of the next CPU burst for SJF?

A

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
Q

What is preemptive SJF scheduling?

A

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
Q

What is priority-driven scheduling?

A

each process has a priority and CPU goes to highest priority ready process

82
Q

What kind of scheduling policies are there?

A

fixed priority and time-varying priorities (aging)

83
Q

What must we avoid with scheduling?

A

starving processes of CPU access (fairness)

84
Q

What is a problem with priority scheduling?

A

since embedded systems must meet deadlines, some may be missed if a low-priority process is not run for a while

85
Q

What is the scheduling problem?

A

can we meet all deadlines and how much CPU do we need to meet the deadlines

86
Q

What makes schedulability analysis NP-hard?

A

resource constraints

87
Q

What is scheduling feasibility?

A

showing that the deadlines are met for all timings of resource requests

88
Q

What is a simple processor feasibility analysis?

A

assuming no resource conflicts and constant execution times, and requiring T>=Ei*Ti (can’t use more than 100% of the CPU)

89
Q

What is the hyperperiod?

A

least common multiple of the task periods

90
Q

What must you do to find all task interactions?

A

hyperperiod schedule

91
Q

When can hyperperiod be very long?

A

if task periods are not chosen carefully

92
Q

What is TDMA scheduling algorithm?

A

scheduling in time slots (same process activation regardless of workload

93
Q

What is the schedulability of TDMA?

A

always uses the same CPU utilization and assumes constant process execution times, so it can’t handle unexpected loads

94
Q

What do we assume with TDMA?

A

schedule based on LCM of process period and it’s a trivial scheduler, time slots don’t have to be equal in size

95
Q

What is the round-robin scheduling algorithm?

A

schedules processes only if ready, similar to TDMA

96
Q

What are some variations of constant system period?

A

constant system period, and start round-robin again after finishing a round

97
Q

What do we assume with round-robin?

A

schedule based on LCM, best done with equal time slots for processes, simple schedule that can be implemented in hardware

98
Q

What is the scheduling feasibility of round-robin?

A

can be adapted to handle unexpected load, may have unused CPU cycles

99
Q

What is the overhead for round-robin?

A

not all CPU available for processes due to scheduling using some CPU time

100
Q

When can overhead be ignored?

A

if it is a small fraction of total execution time

101
Q

How do we evaluate a scheduling policy?

A

ability to satisfy all deadlines, CPU utilization, and scheduling overhead

102
Q

What are two general types of RTOS scheduling?

A

rate monotonic and earliest-deadline-first

103
Q

What is rate monotonic scheduling also known as?

A

RMA

104
Q

What is the RMA model?

A

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
Q

What is response time?

A

time required to finish process

106
Q

What is the critical instant?

A

scheduling state that gives worst response time (occurs when all higher priority processes are ready to execute)

107
Q

What are RMS priorities?

A

optimal (fixed) priority assignment: shortest period process gets highest priority, period inversely proportional to period, break ties arbitrarily

108
Q

Fill in the blank: With RMS as the number of tasks approaches infinity, the maximum CPU utilization approaches ________.

A

69%

109
Q

Can RMS use 100% of the CPU?

A

no

110
Q

Why can’t RMS use 100% of the CPU?

A

it must keep the idle cycles available to handle worst-case scenario

111
Q

What is the biggest positive about RMS?

A

it guarantees all processes will always meet their deadlines

112
Q

What type or scheduling scheme is EDF?

A

earliest deadline first, dynamic priority scheduling scheme

113
Q

What is the meaning of aging priority?

A

the process closest to its deadline has highest priority

114
Q

Since the priorities are dynamic, what has to happen with EDF?

A

requires recalculating process priorities at every timer interrupt

115
Q

How is EDF different from RMS?

A

it can use 100% of the CPU but it may fail to meet deadlines

116
Q

Is EDF used in practice?

A

no its too expensive

117
Q

What are measures to take if your set of processes is unschedulable?

A

change deadline requirements, reduce execution times of processes, or get a faster CPU

118
Q

What is priority inversion?

A

low-priority process keeps high-priority process from running

119
Q

What problems can priority inversion cause?

A

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
Q

What can be done to solve priority inversion?

A

give system resources priorities and have processes inherit requested resource priority

121
Q

How can we evaluate RTOS performance?

A

simplify assumptions: context switch costs no CPU time, know exact execution time of processes, WCET/WBET don’t depend on context switches

122
Q

What can push the limits of a tight schedule?

A

non-zero context switching time

123
Q

Why is it hard to calculate the effects of context switches?

A

the time depends on the order of the context switches

124
Q

How does context switching compare to common task periods in practice?

A

it is usually much much smaller

125
Q

How does process execution time different from our assumptions?

A

process execution time is not constant

126
Q

How can extra CPU time from non constant processes cause problems?

A

if next process runs earlier, it can cause a new preemptions

127
Q

What other problems can processes cause?

A

they can cause caching problems

128
Q

How does worst-case execution time with bad behavior differ from execution time with good cache behavior?

A

it is much worse

129
Q

What is power management?

A

determining how system resources are scheduled/used to control power consumption

130
Q

How does the OS manage power?

A

the same way it manages time

131
Q

How does the OS reduce power?

A

shutting down unused units

132
Q

What are a few simple power management policies?

A

request-driven or predictive shutdown

133
Q

What is request-driven power management?

A

power-up once request is received (which adds delay to response)

134
Q

What is predictive shutdown?

A

trying to predict how long you have before next request

135
Q

What are positives and negatives of predictive shutdown?

A

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
Q

What is probabilistic shutdown?

A

assuming service requests are probabilistic, you shutdown after time T_on then turn back on after T_off

137
Q

What does probabilistic shutdown optimize?

A

power consumption and response time