ELEN90066 Final Preparation

2017-10-23

ELEN90066 …

Some points in review, quiz and something I think might be in exam.

What is a PCB?

Board that has copper traces to allow flow of electricity through various components (might electronics, electrical, mechanical, and so on)
Allows signals between physical devices
Solder allows devices to be connected to PCBs

FR4 is a standard fiberglass PCB material
Consists of copper foil laminated on one or both sides (for single/double sided)
Multi-layered PCB has multiple layers laminated

What are the different types of PCBs

Single-sided
Double-sided
Multi-layered PCBs

Explain the difference between interrupt and polling.

Polling is a method to check whether an event has occurred (such as button press)
- CPU cycles are wasted
- Reaction time in known
Interrupts are raised when an event occurs (button press) by preempting the current task
- CPU does not waste time in checking the button press condition. Interrupts set a flag (semaphore) in the microcontroller
- Reaction time is unknown and may vary depending on the interrupt priority level.

What is a real time system?

Flight control system
Global Positioning System (GPS)
Transport system
Navigation
Smartphone
Power generation

The correctness of the system behaviour depends not only on the logical results of the computations, but also on the physical time when these results are produced.

What are the main differences between a soft real-time system and a hard real-time system?(Quiz in lec 16)

hard real-time
- meet at least one hard deadline
- must sustain a guaranteed temporal behaviour under all specified load and fault conditions
- Example: driverless car must stop
Firm/soft real-time
- permitted to miss a deadline occasionally
- Example: an interactive Web-based system

For an autonomous vehicle, what kind of realtime system is necessary? And Why?(Quiz in lec 16)

Hard real-time system

It have severe consequences if deadline is missed, such as traffic accidents.

Lec 17

Temporal requirements
- Delay and jitter
  - jitter: the difference between the maximum and the minimum values of the delay of the computer
- Minimum error detection and latency
  - Most hard real time – safety critical
  - Error be detected within short time
  - Error-detection latency must be in the same order of magnitude as the sampling period of the fastest critical control loop
  - Only then possible to take action
- Delay and jitter in networked environments

Dependability Requirements
- Reliability
  - Reliability $R(t)$ of a system is the probability that a system will provide the specified service until time $t$
  - For a constant failure rate of $\lambda$ failures/h, then reliability at time t is $R(t) = e^{-\lambda (t - t_{0} )}$
- Safety
  - Safety is reliability regarding critical failure modes
  - Cost of a failure can be orders of magnitude higher than the utility of the system
- Maintainability
  - Time interval required to repair a system after failure
  - Mean-Time-To-Failure (MTTF)
  - Mean Time To Repair (MTTR) is defined for a system with constant repair rate.
- Availability (A)
  - Measure of the delivery of correct service with respect to the alternation of correct and incorrect service
  - $A = \frac{MTTF}{MTTF+MTTR} = \frac{MTTF}{MTBF}$
  - MTTF+MTTR = Mean Time Between Failures (MTBF)
- Security
  - Authenticity and integrity of information
  - Concerns are confidentiality, privacy, and authenticity of information
- Porformance
  - Some networks are physically more vulnerable than others to data corruption by electromagnetic interference – Reliability
  - Networks and operating systems are used that can be vulnerable to internet-based attacks and viruses – IoT
  - The performance of the system depends not only on the QoS of the network but also on how the network is used (e.g., sample time, message scheduling, node prioritization, etc.)

Give an example where the predictable rare-event performance determines the utility of a hard real-time system

Nuclear power plant monitoring and shutdown system is a hard real-time system. The sole purpose of a nuclear power plant monitoring and shutdown system is reliable performance in a peak-load alarm situation. The utility of system failure will lead to catastrophic situations.

What happens when nodes have different time in a distributed WSN(wireless sensor network)?

Events can be misrepresented in time

What is the difference between an instant, a duration and an event?

Intants are points in time on a directed timeline.
Duration is a section of the timeline between two different instants.
Event taks place at an instant of time and does not have a duration.

All clocks of an ensemble are externally synchronized with an accuracy A. What is at most precision with which the ensemble is also internally synchronized?

LEC 19

Global time t is reasonable if for all local implementations, $\Pi$ is the precision, MIGHT BE diffrence of the same tick in macro of clock i and clock j in Lecture Slides.

$$ g^{global} > \Pi $$

The reasonableness condition ensures that:

the synchronization error is less than one macrogranule
for any event e, $|t^j(e) - t^k(e)| \leq 1$

Fundamental Limits of Time Measurement

If a single event is observed by two different nodes, there is always the possibility that the time-stamps differ by one tick.
A one-tick difference in the time-stamps of two events is not sufficient to re-establish the temporal order of the events from their timestamps
True duration of an interval is bounded by: $d{obs} - 2g^{global} \lt d{true} \lt d_{obs} + 2g^{global}$
The temporal order of two events can be recovered from their time-stamps if the difference between their time-stamps is equal to or greater than 2 ticks.

Master-Slave Synchronization

Master periodically sends the value of its time counter in synchronization messages to all nodes
The slave records the time-stamp of message arrival
Difference between the master’s time and the recorded slave’s time-stamp of message arrival
Corrected by the known latency of the message transport
This gives a measure of the deviation of the clock of the master from the clock of the slave
The slave then corrects its clock by this deviation to bring it into agreement with the master’s clock

QUIZ

Scenario:

You have an ensemble of N clocks in a private network. Each clock has a perfect oscillator, ie., the drift rates of all the local clocks are zero

Question:

Is it possible to internally synchronize the clocks greater than precision $\Pi$?

IMPOSSIBILITY

It is not possible to internally synchronize the clocks of an ensemble consisting of N nodes to a better precision than

$$ \Pi = \epsilon （1 - \frac{1}{N})$$

$\epsilon$ : jitter

$\Pi$ : precision

LEC 20

Synchronize from another machine that provides time information: time server

Cristian’s Algorithm

$$T_p = T_{server} + \frac{T_1 - T_0}{2}$$

Elapsed time : $T_1 = T_0$
Timestamp guess : $\frac{T_1 - T_0}{2}$
Set time of the process P: $T_{server} + \frac{T_1 - T_0}{2}$

Limitations of Cristian’s Algorithm

Suitable for deterministic LAN environment of Intranet
Problem of failure of single time sever
- Redundancy through a group of servers (multicasting)
- However, how to decide if replay varies (Byzantine)
Imposter server providing false clock readings
- Subject to malicious interference

Berkeley Algorithm

Request timestamps from all slaves
Compute a fault-tolerant average
- A subset of clocks are chosen such that they do not differ much in time
- If a clock deviates from a specified limit from the rest, it is ignored
- Then, average is computed
- Offset is sent to the slaves and maser corrects its own clock
Send offset to clients

Why synchronization is difficult in wireless devices?

Non-deterministic delay
- Send time and Access time
  - dependent on factors such as the instantaneous load on the sender’s CPU and the network.
  - the most nondeterministic and difficult to estimate
- Propagation Time
  - Depends on the physical media
  - For LAN this is typically negligible. For UTP copper cable (speed $2 \times 10^9$), 200 meters, delay 1us.
- Receive Time
  - Depends on interpreting the received message

Reference Broadcast Synchronization

Strategically give up this part

LEC 21

Limitations of current real-time systems
…

Desirable features of real-time systems

Timeliness (explicit timing constraints)
Predictability (scheduling decision)
Efficiency (space, weight, energy, memory)
Robustness (manage peak load conditions)
Fault tolerance (software and hardware failures)
Maintainability (modular structure)

Scheduling Concepts

Process:
- a process is a computation that is executed by the CPU in a sequential fashion
Scheduling policy:
- the assignment of the CPU to execute a set of concurrent tasks according to a predefined criterion
Scheduling algorithm:
- the set of rules that, at any time, determines the order in which tasks are executed
Dispatching:
- The specific operation of allocating the CPU to a task selected by the scheduling algorithm
Waiting task
- task waiting for CPU availability if another task is currently being executed
Active task
- a task that can potentially execute on the processor, independently of its actual availability
Running task
- the task in execution
Ready task
- a task waiting for the processor

Why preemption is important?

In dynamic real-time systems, preemption is important:

Tasks performing exception handling may need to preempt existing tasks so that responses to exceptions may be issued in a timely fashion
When tasks have different levels of criticality , preemption permits executing the most critical tasks, as soon as they arrive.
It allows higher efficiency (executing a real-time task sets with higher processor utilization)

Limitations of preemption

Preemption destroys program locality
Introduces a runtime overhead that inflates the execution time of tasks
Limiting preemptions in real-time schedules can have beneficial effects in terms of schedulability

Schedule

A preemptive schedule is a schedule in which the running task can be arbitrarily suspended at any time, to assign the CPU to another task according to a predefined scheduling policy.
Feasible schedule: if all tasks can be completed according to a set of specified constraints.
Schedulable: A set of tasks is said to be schedulable if there exists at least one algorithm that can produce a feasible schedule.

Real-time Constraints

Timing
Precedence relations
- Certain applications have computational activities that cannot be executed in arbitrary order
- Some precedence relations defined at the design stage
- Precedence relations are described through a directed acyclic graph G
- Notation of Precedence relations
  - $J_a < J_b$, $J_a$ is a predecessor of task $J_b$, G contains a directed path from node $J_a$ to node $J_b$
  - $J_a \rightarrow J_b$, $J_a$ is an immediate predecessor of $J_b$, $J_a$, G contains an arc directed from node $J_a$ to node $J_b$
- EXAMPLE: Visual Recognition of Objects
Resources
- Any software structure that can be used by the process to advance its execution
- Types
  - Private resource : a resource dedicated to a particular process
  - Shared resource : a resource that can be used by more than on task
  - Mutually exclusive resource : a resource R that cannot be accessed by a task if another task is inside the R, manipulating its data structures
  - Critical section : a piece of code executed under mutual exclusion constraints

Real-time Systems Scheduling

LEC 22

Notation: All algorithms are classfied using $\alpha | \beta | \gamma$

$\alpha$ the machine environment on which the task set has to be scheduled (uniprocessor, multiprocessor, distributed architecture, and so on).
$\beta$ task and resource characteristics (preemptive, independent versus precedence constrained, synchronous activations, and so on).
$\gamma$ the optimality criterion (performance measure) to be followed in the schedule

example

1|prec|Lmax
- Denotes the problem of scheduling a set of tasks with precedence constraints on a uniprocessor machine in order to minimize the maximum lateness.
- If no additional constraints are indicated in the second field, preemption is allowed at any time, and tasks can have arbitrary arrivals.
3 | no prem | $\sum(f_i)$
- Denotes the problem of scheduling a set of tasks on a three-processor machine.
- Preemption is not allowed and the objective is to minimize the sum of the finishing times.
- Since no other constraints are indicated in the second field, tasks do not have precedence nor resource constraints but have arbitrary arrival times.
2 | sync | $\sum (Late_i)$
- Denotes the problem of scheduling a set of tasks on a two processor machine.
- Tasks have synchronous arrival times and do not have other constraints. The objective is to minimize the number of late tasks.

Earliest Due Date (EDD)

Assume, all task are activated at time t = 0.

Each job $J_i$ can be completely characterized by :

A computation time $C_i$
Relative deadline $D_i$

We need to show that, in the worst case, all tasks can complete before their deadlines.

For each task, the worst-case finishing time $f_i$ is less than or equal to its deadline $d_i$:

$$ \forall _i = 1,2,…,n f_i \leq d_i $$

Earliest Deadline First (EDF)

From the name and lecture slides, I guess it executes task whose deadline is the earliest.

Earliest Deadline First * (EDF *)

Precedence Constraints

The problem of scheduling a set of n tasks with precedence constraints and dynamic activations can be solved in polynomial time complexity only if tasks are preemptable
The basic idea of their approach is to transform a set J of dependent tasks into a set J* of independent tasks by an adequate modification of timing parameters
Basically, all release times and deadlines are modified so that each task cannot start before its predecessors and acnnot preempt their successors.

Modification of Release time

Given two tasks $J_a$ and $J_b$, such that $J_a \rightarrow J_b$
If $J_a \rightarrow J_b$, then the release time of $J_b$ can be replaced by $max(r_b,r_a + C_a)$.
In general, $ r_j ^ \star = max( r_j, r_i ^ \star + C_i) , J_i \rightarrow J_j $

Modification of Deadlines

Given two tasks $J_a$ and $J_b$, such that $J_a \rightarrow J_b$
If $J_a \rightarrow J_b$, then the deadline of $J_a$ can be replaced by $min(d_a,r_a + C_a)$.
In general, $d_i ^ \star = max( d_i, d_j ^ \star + C_j), J_i \rightarrow J_j$

Optimality Proof

Show that if there exists a feasible schedule for the modified task set under EDF then the original task set is also schedulable (ignoring precedence relations)
Show that the original task set meets the timing constraints also schedulable (ignoring precedence relations).
This can be done by using, $d_i^{\star} \leq d_i, r_i^{\star} \geq r_i$
In addition, show that the precedence relations in the original task set are not violated. In particular, show that
- a task cannot start before its predecessor
- a task cannot preempt its predecessor

LEC 23

Periodic Tasks

Are a major computational load in embedded systems
Arise from sensory data acquisition, low-level serving, control loops, action planning, and system monitoring
Activities need to be cyclically executed at specific rates
OS has to guarantee that each periodic instance is regularly activated at its proper rate and meets deadline

Processor Utilization Factor (PUF)

Time Scheduling

Rate Monotonic Scheduling

Earliest Deadline First