Ans: An embedded system is some combination of computer hardware and software, either fixed in capability or programmable, that is specifically designed for a particular function.

OR

It can be defined as “A specialized computer system that is part of a larger system or machine”.

Embedded systems are the ones found in generally immutable machines, such as ATMs, internet kiosks, airport terminal displays, cell phones,or at the screen at McD that displays your order are all examples of embedded systems. Real-time systems are the ones that are designed to provide a result within a specific time-frame. If you are using a touch-screen to order a sandwich from a gas store chain, you don’t want to have to wait 20 seconds for it to display pictures of each of the ingredients. You want it “now”, or at least within a second or two of pushing the button.

Learn more »

Ans: There are five types of task classes:

(i) Periodic and aperiodic tasks
(ii) Sporadic task
(iii) Critical task
(iv) Noncritical task

(1) Periodic task: There are many tasks in real-time systems that are done repetitively. For example, one may wish to monitor the speed altitude and attitude of an aircraft every 100 ms. This sensor information will be used by periodic tasks that control surfaces of the aircraft in order to maintain stability and other desired characteristics. The periodicity of these tasks is known to the designer, and many tasks can be pre-scheduled.

(2) Aperiodic task: There are many other tasks that are aperiodic, that occur occasionally. For instance, when the pilot wishes to execute a turn a large number of subtasks. Associated with that action is self off aperiodic tasks cannot be predicted and sufficient completing power must be held in a reserve to execute them in a timely fashion.

(3) Critical tasks: Critical tasks are those whose timely executions is critical; if deadlines are missed, catastrophes occur. Example include life – support systems and the stability control of aircraft. If critical tasks are executed at a higher frequency then it is absolutely necessary.

(4) Noncritical tasks: Noncritical tasks are real times tasks. As the name implies, they are not critical to the application. However, they do deal with time-varying data and hence they are useless if not completed within a deadline. The goal in scheduling these tasks is to maximize the percentage of jobs successfully executed within their deadlines.

Learn more »

• “Packet-by-packet generalized processor-sharing algorithm”

– A rate allocating service discipline; provides each flow with at least its
proportional fair share of link capacity; isolates timing between flows

• Definitions:
– A packet switch has several inputs, feeding to an output link shared by n
established flows

• Each flow, i, is allocated a fraction ũi of the link
n
˜
• Total bandwidth allocated to all n connections is U = Σui where U≤ 1
i=1

• Assume an acceptance test rejects connections that would cause requested
bandwidth to exceed available bandwidth

– Define the “finish number”, fni, to represent job completion times
• Used in definition of scheduling algorithm Learn more »

• Messages take at most e(i)/wt(i) rounds to complete

• Implies delay through first switch = (e(i)/wt(i))RL

• At each subsequent switch, each round of packets arriving is sent
in the next round

– Implies one round delay at each hop

• Therefore, end-to-end delay for connection i with message size ei assigned weight wt(i) passing through r switches is bounded by:

W(i) ≤ (e(i)/wt(i) + r – 1)RL

• Can also be shown that jitter can be bounded by jitter < p(i) – e(i) + (r – 1)(RL – 1)  for messages of size ei with inter-arrival time of p(i)
Learn more »

• Self-suspension

– A job may invoke an external operation (e.g. request an I/O operation),
during which time it is suspended

– This means the task is no longer strictly periodic… again need to take into
account self-suspension time when calculating a schedule

• Context Switches

– Assume maximum number of context switches Ki for a job in Ti is known;
each takes tCS time units

– Compensate by setting execution time of each job, eactual = e + 2tCS
Learn more »

A ready job is blocked when it is prevented from executing by a

lower-priority job; a priority inversion is when a lower-priority

job executes while a higher-priority job is blocked

• These occur because some jobs cannot be preempted:

– Many reasons why a job may have non-preemptable sections

• Critical section over a resource

• Some system calls are non-preemptable

• Disk scheduling

– If a job becomes non-preemptable, priority inversions may occur, these

may cause a higher priority task to miss its deadline

– When attempting to determine if a task meets all of its deadlines, must

consider not only all the tasks that have higher priorities, but also non-

preemptable regions of lower-priority tasks

• Add the blocking time in when calculating if a task is schedulable

Learn more »

• Another well known fixed-priority algorithm is deadline monotonic
scheduling


• The deadline monotonic algorithm assigns task priority according
to relative deadlines – the shorter the relative deadline, the higher
the priority

• When relative deadline of every task matches its period, then rate
monotonic and deadline monotonic give identical results

• When the relative deadlines are arbitrary:

– Deadline monotonic can sometimes produce a feasible schedule in cases
where rate monotonic cannot

– But, rate monotonic always fails when deadline monotonic fails

• Deadline monotonic preferred to rate monotonic

– If deadline ≠ period

Learn more »

• Well-known fixed-priority algorithm is rate monotonic scheduling

• It assigns priorities to tasks based on their periods

– Priority is assigned as "The shorter the period, the higher the priority"

– The rate (of job releases) is the inverse of the period, so jobs with higher
rate have higher priority

• It is very widely studied and used
• For example, let us consider a system of 3 tasks:

– T1 = (4, 1)
– T2 = (5, 2)
– T3 = (20, 5)

⇒ rate = 1/4
⇒ rate = 1/5
⇒ rate = 1/20

– Relative priorities assigned by the rate monotonic scheduling is : T1 > T2 > T3

Learn more »

–Every job is executed by the operating system on a processor and may depend on some   resources. 

–A processor, P, is an active component on which jobs scheduled. For example:

1. Threads scheduled on a CPU

2. Data scheduled on a transmission link

3. Read/write requests scheduled to a disk

4. Transactions scheduled on a database server etc
.

–  Each processor has a speed attribute which determines the rate of progress a job makes toward completion

– May represent instructions-per-second for a CPU, bandwidth of a network, etc.

–  Two processors are of the same type if they are functionally identical and can be used interchangeably

–  A resource, R, is a passive entity upon which jobs may depend

–  E.g. memory, sequence numbers, mutexes, database locks, etc.

–  Resources have different types and sizes, but do not have a speed attribute

–  Resources are usually reusable, and are not consumed by use

Learn more »

Solutions:

Pre-emptive SJF CPU Scheduling algorithems

Total wait time =6
Total turn around time =20
Average wait time=6/3=2
Average turn around time=20/3=6.66

Learn more »

Solutions:

Non-premptive priority CPU Scheduling

Total wait time= 10

Average Wait time =10/3=3.33

Total Turn around time = 20

average turn around time=20/3=6.66

Learn more »

Solutions:

Least Recently Used algorithm Scheduling

Learn more »

Consider the following set of processes with the length of CPU  burst time and arrival time given in milliseconds.

 Illustrate the execution of these process using FCFS CPU Scheduling algorithems. Also calculate wait timeand turn around timeof each process and calculate average waiting time and average turn around time for above situation. Also draw a gantt chart.

Solutions:

First Come first service scheduling

Now calculate average wait time 

Average Wait time =10/4=2.5

average turn around time=22/4=5.5

Gantt Chart 

Gantt Chart of the first Come first Service algorithm

 

 

 

Learn more »

The Kalman filter, also known as linear quadratic estimation (LQE), is an algorithm that uses a series of measurements observed over time, containing noise (random variations) and other inaccuracies, and produces estimates of unknown variables that tend to be more precise than those based on a single measurement al

What is a Kalman Filter and What Can It Do?

A Kalman filter is an optimal estimator- ie infers parameters of interest from indirect, inaccurate and uncertain observations. It is recursive so that new measurements can be processed as they arrive. (cf batch processing where all data must be present). 

Why is Kalman Filtering so popular?

• Good results in practice due to optimality and structure.
• Convenient form for online real time processing.
• Easy to formulate and implement given a basic understanding.
• Measurement equations need not be inverted.

Examples:

• Determination of planet orbit parameters from limited earth observations.
• Tracking targets - eg aircraft, missiles using RADAR.
• Robot Localisation and Map building from range sensors/ beacons.

The Kalman filter keeps track of the estimated state of the system and the variance or uncertainty of the estimate. The estimate is updated using a state transition model and measurements. denotes the estimate of the system's state at time step k before the k-th measurement y_k has been taken into account; is the corresponding uncertainty.

 

The algorithm works in a two-step process. In the prediction step, the Kalman filter produces estimates of the current state variables, along with their uncertainties. Once the outcome of the next measurement (necessarily corrupted with some amount of error, including random noise) is observed, these estimates are updated using a weighted average, with more weight being given to estimates with higher certainty. Because of the algorithm's recursive nature, it can run in real time using only the present input measurements and the previously calculated state; no additional past information is required.

From a theoretical standpoint, the main assumption of the Kalman filter is that the underlying system is a linear dynamical system and that all error terms and measurements have a Gaussian distribution (often a multivariate Gaussian distribution).

Extensions and generalizations to the method have also been developed, such as the extended Kalman filter and the unscented Kalman filter which work on nonlinear systems. The underlying model is a Bayesian model similar to a hidden Markov model but where the state space of the latent variables is continuous and where all latent and observed variables have Gaussian distributions.

Applications of Kalman Filter

• The Kalman filter has numerous applications in technolog
• Guidance, navigation and control of vehicles, particularly aircraft and spacecraft.
• The Kalman filter is a widely applied concept in time series analysis used in fields such as signal processing and econometrics.

For More download this.
Kalman Filter on Wikipedia
More Information on Kalman Filter

Learn more »