Preemptive Operating System Flashcards
What are 3 characteristics of reactive systems?
respond to external events, require real-time responses, and may require chain reaction among multiple processors
What is most important in an embedded system?
time
What is a task?
a functional description of a connected set of operations (can also mean a collection of processes)
What is a process?
a unique execution of a program
True or false: Only one copy of a program may run at one time?
false, several copies may run simultaneously or at different times
Fill in the blank: A process has its own _______.
state (registers, memory)
What manages processes?
the operating system
What does multiple tasks mean?
multiple processes
What do processes help with?
timing complexity
How do processes help with timing complexity?
multiple rates and asynchronous input
In multi-rate systems are tasks asynchronous or synchronous?
they can be both
Can synchronous tasks recur at different rates?
yes
Processes run at different rates based on what?
computational needs of tasks
What is an example of tasks with differing rate requirements?
in engine control: spark control, crankshaft sensing, fuel/air mixture, oxygen sensor, and Kalman filter
How do real-time systems conform to external timing constraints?
performing computations
What are the 2 types of deadline frequencies?
periodic and aperiodic
What are 3 types of deadlines?
hard, soft, and firm
What is a hard deadline?
failure to meet deadline causes system failure
What is a soft deadline?
failure to meet deadline causes degraded response
What is a firm deadline?
late response is useless but some late responses can be tolerated
What is an example of a hard deadline application?
braking system control
What are examples of soft deadline applications?
web browsing, video loading
What are examples of firm deadline applications?
video conferencing, satellite-based surveillance
What is the release time?
the time at which the process becomes ready
What is a deadline?
the time at which the process must finish
What is a periodic process?
a process that executes in almost every period
What is an aperiodic process?
a process that executes on demand
Which type of process (periodic or aperiodic) is harder to analyze and why?
aperiodic because you must consider worst-case combinations of process activation
What is a period?
interval between process activations
What is the rate?
reciprocal of period (aka frequency)
Can the initiation rate be higher than the period?
yes, several copies of the process can run at once
What is the process execution time?
execution time in absence of preemption
What are the possible time units for process execution time?
seconds or clock cycles
What are some sources of variation for process execution time?
data dependencies, memory system, and CPU pipeline
What does it mean for a task to have a data dependency?
they must execute in a certain order
What do task graphs show?
data/control dependencies between processes
In the setting of task graphs, what is a task?
a connected set of processes
What is a task set?
one or more tasks
What is CPU utilization?
the fraction of the CPU that is doing useful work
What do we assume when we calculate CPU utilization?
that there is no scheduling overhead
How do you simply calculate CPU utilization?
(CPU time for useful work)/(total available CPU time)
What are the 3 states that a process can be in?
execution on the CPU, ready to run, or waiting for data
What does a task graph assume?
all tasks run at same rate and tasks do not communicate
In reality, do tasks communicate with each other?
yes some communication is necessary
What is interprocess communication (IPC)?
OS provided mechanisms so that processes can pass data
What are the 2 types of semantics for IPC?
blocking and non-blocking
What does blocking mean regarding IPC?
sending process waits for response
What does non-blocking mean regarding IPC?
sending process continues
What are some different IPC styles?
shared memory, message passing, and signal
What is the shared memory IPC style?
processes have some memory in common and must cooperate to avoid destroying/missing messages
What is the message passing IPC style?
processes send messages along a communication channel with no common address space
What is the signal IPC style?
similar to interrupt but a software creation and is generated by a process and passed by the OS
What problem can happen with shared memory?
race conditions
What is a critical region?
a section of code that cannot be interrupted by another process
What are some examples of critical regions?
writing shared memory, and accessing I/O devices
What is a semaphore?
OS primitive for controlling access to critical regions
What is the atomic test-and-set?
single bus operation reads memory location, tests it, writes it
What is the protocol of the atomic test-and-set?
get access to semaphore (P()), perform critical region operations, release semaphore (V())
How do you run periodic processes?
you need code to control the processes
What is the simplest implementation of running periodic processes?
process = subroutine
How many loops does the simplest implementation of running periodic processes use?
one while loop
What is the problem with using one while loop to control processes?
no control over execution timing
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
What is the problem with the timed loop implementation?
no control over timing of individual processes
What is the multiple timers implementation?
each task has its own function and timer
What is the problem with the multiple timers implementation?
may not have enough timers to implement all the rates
Are the while loop, timed loop, and multiple timers implementations sufficient for real-time systems?
no
How do real-time systems handle implementing processes?
OS scheduling support
What resources does the OS control?
who gets CPU, when I/O happens, how much memory is allocated
What is the most important resource?
the CPU itself
How is CPU access controlled?
by the scheduler
What does the OS need to keep track of?
process priorities, scheduling state, process activation record
When can processes be created?
statically before system starts or dynamically during execution
What are some types of conventional scheduling?
FCFS (first come first serve) and SJF (Shortestjob first)
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
Why is SJF optimal?
it gives the minimum average waiting time for a set of processes
What is the difficulty with SJF?
knowing the length of the next CPU request
True or false: With SJF you can exactly calculate the length of the next CPU burst?
false, you can only estimate
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)
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
What is priority-driven scheduling?
each process has a priority and CPU goes to highest priority ready process
What kind of scheduling policies are there?
fixed priority and time-varying priorities (aging)
What must we avoid with scheduling?
starving processes of CPU access (fairness)
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
What is the scheduling problem?
can we meet all deadlines and how much CPU do we need to meet the deadlines
What makes schedulability analysis NP-hard?
resource constraints
What is scheduling feasibility?
showing that the deadlines are met for all timings of resource requests
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)
What is the hyperperiod?
least common multiple of the task periods
What must you do to find all task interactions?
hyperperiod schedule
When can hyperperiod be very long?
if task periods are not chosen carefully
What is TDMA scheduling algorithm?
scheduling in time slots (same process activation regardless of workload
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
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
What is the round-robin scheduling algorithm?
schedules processes only if ready, similar to TDMA
What are some variations of constant system period?
constant system period, and start round-robin again after finishing a round
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
What is the scheduling feasibility of round-robin?
can be adapted to handle unexpected load, may have unused CPU cycles
What is the overhead for round-robin?
not all CPU available for processes due to scheduling using some CPU time
When can overhead be ignored?
if it is a small fraction of total execution time
How do we evaluate a scheduling policy?
ability to satisfy all deadlines, CPU utilization, and scheduling overhead
What are two general types of RTOS scheduling?
rate monotonic and earliest-deadline-first
What is rate monotonic scheduling also known as?
RMA
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
What is response time?
time required to finish process
What is the critical instant?
scheduling state that gives worst response time (occurs when all higher priority processes are ready to execute)
What are RMS priorities?
optimal (fixed) priority assignment: shortest period process gets highest priority, period inversely proportional to period, break ties arbitrarily
Fill in the blank: With RMS as the number of tasks approaches infinity, the maximum CPU utilization approaches ________.
69%
Can RMS use 100% of the CPU?
no
Why can’t RMS use 100% of the CPU?
it must keep the idle cycles available to handle worst-case scenario
What is the biggest positive about RMS?
it guarantees all processes will always meet their deadlines
What type or scheduling scheme is EDF?
earliest deadline first, dynamic priority scheduling scheme
What is the meaning of aging priority?
the process closest to its deadline has highest priority
Since the priorities are dynamic, what has to happen with EDF?
requires recalculating process priorities at every timer interrupt
How is EDF different from RMS?
it can use 100% of the CPU but it may fail to meet deadlines
Is EDF used in practice?
no its too expensive
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
What is priority inversion?
low-priority process keeps high-priority process from running
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)
What can be done to solve priority inversion?
give system resources priorities and have processes inherit requested resource priority
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
What can push the limits of a tight schedule?
non-zero context switching time
Why is it hard to calculate the effects of context switches?
the time depends on the order of the context switches
How does context switching compare to common task periods in practice?
it is usually much much smaller
How does process execution time different from our assumptions?
process execution time is not constant
How can extra CPU time from non constant processes cause problems?
if next process runs earlier, it can cause a new preemptions
What other problems can processes cause?
they can cause caching problems
How does worst-case execution time with bad behavior differ from execution time with good cache behavior?
it is much worse
What is power management?
determining how system resources are scheduled/used to control power consumption
How does the OS manage power?
the same way it manages time
How does the OS reduce power?
shutting down unused units
What are a few simple power management policies?
request-driven or predictive shutdown
What is request-driven power management?
power-up once request is received (which adds delay to response)
What is predictive shutdown?
trying to predict how long you have before next request
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
What is probabilistic shutdown?
assuming service requests are probabilistic, you shutdown after time T_on then turn back on after T_off
What does probabilistic shutdown optimize?
power consumption and response time
