Embedded Hardware Operating Systems Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

A real time system is a system whose correctness includes its response time as well as its functional correctness. The system does not just run software to plough through the process. it needs to do it in a timely manner. A real time OS is a multitasking OS intended for real time applications. Such applications include embedded systems, industrial robots, spacecraft, industrial control, and scientific research equipment. The purpose of real time systems is to have a physical effect within a chosen time frame. a real time system consists of a controlling system and a controlled system. This interacts with its environment based on information available about the environment. On a real time computer, which controllers a device or process, sensors will provide reading sat periodic levels and the computer must respond by sending signals. There may be unexpected or irregular events and these must also receive a response.

In all cases there will be a time bound within which the response should be delivered. The ability of computer to meet these demands depends on its capacity to perform the necessary computations in the given time bounds. It may be that, even so, the system is unable to meet all possible unexpected demands.

In this case we say that the system lacks sufficient resources: a system with unlimited resources and capable of processing at infinite speed could satisfy any such timing constraint. Failure to meet the timing constraints for a response can have different consequences: there may be no effect at all, or the effect may be minor correctable. Each task occurring in a real time systems has some timing properties.

The timing properties of a given task refer to the following items

Ready time: it is the time at which the task is ready for processing

Deadline: time by which end of execution of the task.

Minimum delay: minimum time that must elapse before execution of the task started.

Execution time: maximum time to complete the process.

Runtime: time to complete the task without interruption

Weight: relative urgency of the task.

Examples for RTOS:

1. Flight control system

2. Intelligent highway system

3. Robotics


The basic requirements are described bellow

Multi-tasking and preemptable: the scheduler should have the possibility to pre-empt any process and give the resources to the other process. Multiple levels of interrupts should be supported to handle multiple priority levels.

Dynamic deadline identification: RTOS should identify the task with earliest deadline. To handle this approach is to convert the information into priority levels. The process gets highest priority when it has earliest deadline.

Predictable synchronization: the ability for multiple processes to communicate among themselves in a predictable time. When processes are sharing resources, synchronization is needed. For this many systems are using semaphores. If task is using shared resources other process has to wait for resources. This waiting time is unpredictable. To overcome this problem assigning deadlines with semaphores. Although this is not guarantee, that critical process has access over non critical processes. Other technique is using non blocking synchronization with FIFO queues. The worst case execution time of accessing a shared resource can thus be determined.

Sufficient priority level:

To implement priority based scheduling there has to be sufficient priority levels. Priority inversion occurs, when a highest priority task must wait on a lower priority task to release a resource in turn the lower priority task must wait on a medium priority task. There are 2 solutions for this problem

Priority inheritance protocol

Priority ceiling protocol(pap) both need sufficient priority levels

Predefined latencies:

The timing of API calls must provide expected latencies. There are 3 types of latencies

Task switching latency

Interrupt latency

Interrupt dispatch latency

Classification of real time scheduling algorithm is shown in below figure

Real-Time Scheduling Algorithms

Figure 1: real time scheduling algorithms

In general real time systems can be divided into 3 classes

Hard real time systems: all tasks must meet their deadlines. if missing a deadline is a fatal error or has disastrous consequences it is considered as hard.

Examples: Breaking system controller, sensory acquisition, lowlevel control, sensory motor planning, nuclear reactor control system.

An example of a hard real time system is a digital fly_by_wire control system of an aircraft

No lateness is accepted under any conditions; else the aircraft is not controllable. If the control system does not respond timely, the result is a hole in the ground

Cost of missing deadline is infinitely high. The lives of people depend on the correct working of the control system of the aircraft.

Firm real time systems:

Only some jobs are allowed to miss their deadline

Example: food processing plant control system.

Soft real time systems: Most of the modern operating systems can serve as the base for soft real time systems. This contains only tasked with no hard timing constraints. this is also known as "best effort" systems. jobs don't have deadlines.if some percentage of missed deadlines is accepted is called as soft.

Classic examples:

Multimedia streaming, reading date from keyboard, user command interpretation, message did playing, graphical activities, multimedia transmission and reception, networking, websites and services, telecom(cellular)networks, computer games, dvd player.

Real time systems are less restrictive time by nature. Soft real time systems requires careful design of the scheduler and other related aspects of os. These systems requires that critical processes receive priority over less critical ones. The system interactions must be known as well as the system must have priority scheduling giving the highest priority to real time processes. In addition, the dispatch latency must be small.

Hard real time systems:

Tasks contains with hard timing constraints

These systems requires formal verification of being to always meet its hard deadlines

E.g.: air traffic control, vehicles subsystems control, medical systems

The scheduler then does one of two operations given below

allowance of the process:

Guaranteeing that the process will be completed on time.

Rejection of the process:

This is known as the resource reservation. In this type scheduler knows the exact length of the time of each process the os to perform.

Therefore, each task takes an optimal amount time. These systems are composed of special purpose s/w running on h/w dedicated to their critical process.

The goals of the scheduling a real time system:

Meeting a timing constraints of the system

Preventing simultaneous access to resources and devices

Reduce the cost of the context switches

Reduce the communication cost.

Covering reliability, security, safety.

Given real time systems, the appropriate scheduling approach should be designed based on the properties of the system and the tasks occurring in it. These properties are as follows

1. soft/hard/firm real time tasks

2. periodic/aperiodic/sporadic tasks

3. pre-emptive/nonpreemptive tasks

4. Single processer/ multiprocessor systems

5. Fixed (static) /dynamic priority tasks

6. Static /dynamic systems

7. Independent and dependent tasks

Uniprocesser scheduling algorithms:

These are divided into 2 major subjects

1. Offline: generates scheduling information prior to system execution

2. Online: generates scheduling information

Online again 2 types



Classification of real time systems:

There are 2 different types of execution models:


In the execution time the task may be interrupted and another task run in its place


Can minimize response time to events.


Requires considerable computational resources for scheduling


No other task will be executed till the end of the current executing task.


Reasonable when

Task execution times ~= task switching times.

Less computational resources needed for scheduling


Can leads to starvation (not met the deadline) especially for those real time tasks ( or high priority tasks).

The task model for a real time system has 2 types

Purely periodic:

Every task is cyclic and executes periodically, even I/O is polled. The nature of tasks doesn't vary much between cycles

Aperiodic: most tasks in the system are not periodic.

Basic requirements of RTOS:

Multi threading and preemptibility

Thread priority

Thread synchronization mechanisms

Priority inheritance

Predefined latencies

Task switching latency: time to save the context of a current executing task and switch to another task

Interrupt latency:

This is the time elapsed between the execution of the current instruction of the interrupt task and the first instruction in the interrupt handier

Interrupt dispatch latency: this is the time to go from the last instruction in the interrupt handler to the next scheduled to run

Priority inversion: occurs when higher priority task must wait on a low priority task to release a resource

Priority ceiling:

Each resource has an assigned priority

Priority of thread is the highest of all priorities of the resources its holding

Priority inheritance:

The thread holding a resource inherits the priority of the thread blocked on that resource

Pre-emptive scheduling: in a pre-emptive kernel, when the event makes a higher priority task ready to run, the current task is immediate suspended and the high priority task is given contrail of the CPU

Re-entrancy function: can be used by more than 1 task without fear of date corruption.

Non Re-entrancy: cannot be shared by more than 1 task unless mutual exclusion to the functions is ensured by either using a semaphore, by disabling interrupts during critical sections of code Compilers specially designed for embedded software will generally provide reentrantnruntime libraries.

Real-time Scheduling:

Clock driven scheduling:

All parameters about tasks(release time, execution time, deadline) know in advance.

Schedule can be commuted offline or at some regular time instances.

Minimal runtime overhead.

This is not suitable for many of the applications.

Weighted round robin scheduling:

Tasks scheduled in first in first out manner

Time quantum given to jobs is proportional to its weight

E.g.: high speed switching network

Not suitable for precedence constrained tasks.

E.g.: task 1 run only after task 2.

Priority scheduling:

Processor allocated to processes according to priorities of the task

Processor never left idle when there is a ready task Priorities

Static: at design time

Dynamic: at runtime

Earliest deadline first:

Highest priority is given to the earliest deadline.

Least slack time first

Slack = relative deadline-execution left

Rate monotonic scheduling :

This algorithm for periodic tasks

Tasks priority inversely proportional to its period

Resource allocation:

The issues with scheduling applicable here

Resources can be allocated in

Weighted round robin

Priority based

In resources are non perceptible

E.g.: semaphore


Real-time Scheduling

Real-time scheduling algorithms have been an active topic of research since the late 1960's. Real-time scheduling algorithms work either dynamically or statically. Static scheduling algorithms and techniques have more computer time to devote to scheduling because scheduling is completed before the target system begins. As you might expect, unless all Information about all tasks is known before the system is brought online, the system may not use a static scheduling algorithm.

The dynamic scheduling algorithms are further divided into static priority and dynamic priority. As you might expect, unless all information about all tasks

Stays unchanged throughout each of the tasks' lifetimes, the system may not use a static priority algorithm.

Many dynamic scheduling algorithms studied in research use a simple heuristic.

Example dynamic priority scheduling algorithms are the Earliest Deadline First (EDF) and First- In First-Out (FIFO).

An example of a static priority dynamic scheduling algorithm is the Rate Monotonic (RM). The RM schedules the tasks in order of increasing period, where period is equal to the amount of time between requests. In dynamic scheduling practice, techniques that combine simple heuristic algorithms may be used. The RM is the optimal static priority dynamic real-time scheduling algorithm and "any periodic task set of any size will be able to meet all deadlines all of the time if the rate monotonic

Algorithm is used and the total (processor) utilization is not greater than .693".The application of the RM results have proven to be effective when used in combination with other techniques for scheduling periodic and aperiodic task loads as well.

Real-time Operating Systems:

Real-time Operating Systems are available in open-source and commercially in all price ranges. They differ in size (memory space), and in available options/features. RTOS that are more expensive typically require expensive software tools to complete development of applications.

Examples of RTOS are VxWorks, RTLinux, LynxOS, QNX, and Windows CE.

Embedded platforms are more frequently the target for RTOS. Relatively few RTOS have been written for the PC (there is a version of QNX that runs on the PC). A recently available open-

Source RTOS for PC's is KURT .


An ordinal number which represents the relative importance of a task

Static priority:

The priority of the task is not automatically adjusted by the system. This priority is typically changed by the user.

Dynamic priority:

The priority of the task is automatically adjusted by the system according to the behaviour and the system loading

This imposes an overhead on the system

This can improve response times and eliminate indefinite postponing

Rate monotonic algorithm:

The most commonly used scheduling is static scheduling algorithm is (RM) scheduling algorithm

Schedulable utilization = 0.693

If U < 0.693, schedulability is guaranteed

Tasks may be schedulable even if U > 0.693

The RM algorithm assigns different priorities proposal to the frequency of the tasks

The task with low frequency (shortest) gets high priority and the task with high frequency (long period) get the lowest static priority.

Rate monotonic algorithm is a dynamic pre-emptive algorithm based on static priorities RM algorithm provides no support for the dynamically changing task periods and priorities and tasks that may priority inversion

Priority inversion occurs in RM systems where in order to enforce rate monotonicity; a non critical task with higher frequency of execution is assigned a higher priority than a critical task with lower frequency of execution. A priority ceiling protocol: can be used to counter priority inversion, wherein a task blocking a higher priority task inherits the higher priority for the duration of the blocked task The priority ceiling protocol is used to scheduling a set dependant periodic tasks that share resources protected by semaphores

Earliest deadline first:

Earliest deadline first scheduling can be used for the both static real time scheduling and dynamic real ]time scheduling

A dynamic priority algorithm which uses the deadline of a task as the priority

It gives the highest priority to the earliest deadline task

Execution profile of two periodic tasks

Process A

Arrives 0 20 40 …

Execution Time 10 10 10 …

End by 20 40 60 …

Process B

Arrives 0 50 100 …

Execution Time 25 25 25 …

End by 50 100 150 …

Figure 2:

Minimum laxity firstŒ(hybrid task)

Laxity is assigned to each of the task in the system. The priority is given according to that. The highest priority is given to the minimum laxity tasks

Laxity is defined as the time difference between completion deadline and its remaining processing time requirement

MLF considers the execution time of a task, which edf does not

A task with zero laxity must be scheduled right away and executed with out pre-emption or it will fail to meet its deadline.

The negative laxity indicates that the task will miss the deadline, no matter when it is picked up for execution. This is the major problem

This is impractical to implement because laxity ties. This will cause system performance to remarkably degrade.

Modified least laxity first:

This is same as llf algorithm. If the laxity tie occurs, the running task continues to run with no pre-emption as far as the deadlines of other tasks are not missed. The mllf algorithm defers the context switching until necessary and it is safe even if laxity tie occurs. It allows the laxity inversion where a task with the latest laxity may not be scheduled immediately. Laxity inversion applies the current running task.

Maximum urgency first algorithm:

This is the combination of static and dynamic priority scheduling, also called mixed priority scheduling. In this each task is given as urgency. Which is combination of both static and dynamic priority? In this algorithm, each task is given an urgency which is defined as a combination of two fixed priorities. Static and dynamic priority that is inversely proposal to the laxity.

The MUF algorithm assigns priorities in 2 phases

Assign static priority to tasks

Deals with the run time behaviour of the muf scheduler.

1st phase:

It sorts the tasks from the shortest period to the longest period. Then it defines the critical set as the first n tasks such that the total cpu load factor doesnot exceed 100%. These tasks are guaranteed not to fail even during a transient overload.

2nd phase: muf scheduler follows an algorithm to select a task for execution.

This is executed when new task is arrived in the queue.

The algorithm is as follows

If there is only 1 task, pick it up and start executr it.

If more than one highly critical task, select the one with the highest dynamic priority. Here least laxity is considered to be the highest priority.

If same laxity exits, select the one with highest user priority

Comparing different algorithms:


RMS may not guarantee schedulability even when U < 1

Low overhead: Priorities do not change for a fixed task set


EDF guarantee schedulability as long as U <= 1

High overhead: Task priorities may change dynamically

Assume a single processor system with 2 tasks

T1= (2, 1)

T2= (5, 2.5)

The total utilization is 1.0 no slack time

This is one case of the cases where EDS works better than RM/DM

H=10 figure 3: timing diagram

Schedulability tests:

Simulating schedules is both tedious and error-prone… can we

Demonstrate correctness without working through the schedule?

Yes, in some cases. This is a schedulability test

A test to demonstrate that all deadlines are met, when scheduled using a

Particular algorithm

- An efficient schedulability test can be used as an on-line acceptance test;

Clearly exhaustive simulation is too expensive

Schedulable Utilization

• Recall: a periodic task Ti is defined by the 4-tuple (φ

i, pi, ei, Di)

with utilization ui = ei / pi

• Total utilization of the system where 0 ≤ U ≤ 1

• A scheduling algorithm can feasibly schedule any system of

Periodic tasks on a processor if U is equal to or less than the

Maximum schedulable utilization of the algorithm, UALG

- If UALG = 1, the algorithm is optimal

• Why is knowing of UALG important? It gives a schedulability test,

Where a system can be validated by showing that U ≤ UALG

Schedulable Utilization: EDF

A system of independent preempt able periodic tasks With Di = pi can be feasibly scheduled on one processor using EDF if and only if U ≤ 1

- UEDF = 1 for independent, preempt able periodic tasks with Di = pi

result also holds if deadline longer than period: UEDF = 1 for

Independent preempt able periodic tasks with Di ≥ pi

- Result is independent of i

- Result can also be shown to apply to strict LST

Schedulable Utilization: EDF

What happens if Di < pi for some i? The test doesn't work…

- E.g. T1 = (2, 0.8), T2=(5, 2.3, 3)

• However, there is an alternative test:

- The density of the task, Ti, is ƒ¤

i = ei / min(Di, pi)

- The density of the system is ƒ„€ = ƒ¤1 + ƒ¤2 + … + ƒ¤n

- Theorem: A system T of independent, preemptable periodic tasks can be

Feasibly scheduled on one processor using EDT if ƒ„€ â‰¤ 1.

• Note:

- This is a sufficient condition, but not a necessary condition - i.e. a system

Is guaranteed to be feasible if ƒ„€ â‰¤ 1, but might still be feasible if ƒ„€ > 1

(Would have to run the exhaustive simulation to prove)

J1,1 J1,2 J1,3 J1,4 J2,2

0 1 2 3 4 5 6 7

J2,1 J2,1 J2,2

J2,1 is preempted and misses deadline

Schedulable Utilization of RM

• Theorem: a system of n independent preemptable periodic tasks

with Di = pi can be feasibly scheduled on one processor using RM

if U ≤ n⋅(21/n - 1)

- URM(n) = nâ‹…(21/n - 1)

- For large n →€ ln 2

(i.e. n →€ 0.69314718056…)

- [Proof in book - complicated!]

- U ≤ URM(n) is a sufficient, but not necessary, condition - i.e. a feasible rate

monotonic schedule is guaranteed to exist if U ≤ URM(n), but might still be

Possible if U > URM (n)


In this chapter we present the timing diagrams of the schedules provided by some real-time Scheduling algorithms, namely the earliest deadline ¬rst (EDF), the rate-monotonic (RM), and The least laxity ¬rst (LLF) algorithms, on two given sets of tasks.

Table 2: The repetition periods, computation times, and deadlines of the tasks



Example A.1

Figure 4: The timing diagram of task denned in Table 2, before scheduling

Figure 5: The timing diagram of task denned in Table 2, before scheduling

Example A.1: Consider a system consisting of three tasks t1,t2 and t3, that have the Repetition periods, computation times, the ¬rst invocation times and deadlines denned in Table 2. The deadline di, Of each task pi and tasks are preemptive. Figures 4, 5 and 6 present

The timing diagram of each task t1,t2,t3 ,respectively, before scheduling.

Earliest deadline ¬rst algorithm

Figure 6: The timing diagram of task denned in Table 2, before scheduling

Figure 7: The timing diagram of the schedule provided by any of the earliest deadline ¬rst, rate monotonic, least laxity ¬rst algorithms on the tasks set denned in Table 2

Figure 7 presents a portion of the timing diagram of the schedule provided by the EDF Algorithm on the tasks set de¬ned in Table 2. Between time interval 0 and 17 we observe that no deadline is missed.

􏰫 Rate monotonic algorithm

As shown in Figure 7, if we schedule the tasks set by the RM algorithm, no deadline is

Missed between time interval 0 and 17.

ô°« Least laxity ¬rst algorithm

Similar to the previous two scheduling algorithms, the least laxity ¬rst algorithm pro-

Videos a schedule such that all deadlines are met between time interval 0 and 17 (see

Figure 7).

Table 3: The repetition periods, computation times and deadlines of the tasks t1,t2,t3


Example A.2

Figure 8: The timing diagram of task Defined in Table 3, before scheduling

Figure 9: The timing diagram of task t2 defined in Table 3, before scheduling

Figure 10: The timing diagram of task t3 defined in Table 3, before scheduling

Example A.2: Consider a system consisting of three tasks T1,t2

and t3, that have the Repetition periods, computation times, ¬rst invocation times and deadlines denned in Table 3. The tasks are pre-emptive. The timing diagrams in Figures 8, 9 and 10 present the timing Diagram of each task t1,t2,t3

, respectively, before scheduling.


Earliest deadline ¬rst algorithm

As presented in Figure 11, the uniprocessor real-time system consisting of the tasks

set denned in Table 3 is not EDF-schedulable, because while the execution of the ¬rst

Invocation of the task t2 is not ¬nished yet, the new invocation of the task arrives. In

other words, an overrun condition happens.

Figure 11: The timing diagram of the schedule provided by the earliest deadline algorithm on the tasks set denned in Table 3

Rate monotonic algorithm

As shown in Figure 12, the uniprocessor real-time system consisting of the tasks set

Defined in Table 3 is not RM-schedulable. The reason is that the deadline of the ¬rst

Invocation of the task Is missed. The execution of the ¬rst invocation is required to be

¬nished by time 6, but the schedule could not make it.

ô°ƒ Least laxity ¬rst algorithm

Figure 13 presents a portion of the timing diagram of the schedule provided by the least

laxity ¬rst algorithm on the tasks set denned in Table 3. As shown in the ¬gure, the

deadline of the third invocation of the task t1cannot be met. we conclude that the

uniprocessor real-time system consisting of the tasks set denned in Table 3 is not LLF-


Figure 12: The timing diagram of the schedule provided by the rate monotonic algorithm on the tasks set denned in Table 3

Figure 13: The timing diagram of the schedule provided by the least laxity ¬rst algorithm on the tasks set denned in Table 3


Real time system must satisfy explicit boundary response time constraints, otherwise risk serve consequences including failure. Failure happens when a system cannot satisfy one or more of the requirements laid out in the formal system specifications

for a set of jobs the general scheduling problem asks for an order according to which the tasks are to be executed such that various constants are satisfied. For a given set of tasks, we are asked to devise a feasible allocation. The release time, the deadline, and execution time of the jobs are some of parameters that should be considered for the scheduling. The dead line mat hard, firm, soft. Tasks may have precedence constraints. A task may be periodic, a periodic, or sporadic. The scheduler may be non pre-emptive or pre-emptive. Less critical tasks must allowed to be pre-empted by higher critical ones. The number of processors is another parameter to be considered. The available processer may identical are differs.


In this the concepts of rtos and task and algorithm s are described. Also the concept of utilization bound and optimality criteria, which leads to design appropriate scheduling algorithms, are addressed.

List of open problems:

If real time tasks are hard , pre-emptive and have fixed priorities, periodic, then find the minimum number of processors required to guarantee that all deadlines are met. Some heuristic algorithms have already been proposed, however we believe better algorithms with improved performance can developed in future.

If a system has p identical processors, real time tasks are pre-emptive and have fixed priorities. Hard tasks are periodic. Communication cost is negligible. Find a scheduler that minimizes mean response time while guaranteeing that all deadlines are met.

Suppose there exist m identical processors, real-time tasks are preemptive and have fixe priorities, a penalty function p(ti) is assigned to each soft real-time task, and a reward(ti) is determined for each firm real-time task. Communication cost is negligible. Find a schedule that guarantees all deadlines are met and is p(t)/r(t) minimized.

Consider the conditions of problem (3), except that communication cost is non-trivial. Give a schedule that minimizes the communication cost. Minimizing the number of migrations is one way to reduce the communication cost. Consider the conditions of problem (3), except that communication cost is non trivial. Give a schedule that minimizes the communication cost. Minimizing the number of migrations is one way to reduce the communication cost.

Suppose there exist identical processors, real-time tasks are aperiodic, preemptive, and have fixed priorities. Communication cost is negligible. Find a schedule that not only guarantees that all deadlines are met, but also minimizes mean response time. Find the utilization bound of the algorithm.

Consider the conditions of problem (5), except that tasks are non-preemptive. Find a Schedule that not only guarantees that all deadlines are met, but also minimizes mean response time. Find the utilization bound of the algorithm.

Solve above things when task are dynamic priority.

Solve above when tasks are uniform

We may apply either of the following approaches to solve each of the above problems: the vast majority of the optimization allocating/scheduling problems on real-time systems With more than two processors are NP-hard. In those cases where the problems Listed above are NP-hard, one of the following approaches could be used.

Since the problem is NP-hard, one should strive to obtain a polynomial-time guaranteed approximation Algorithm. Indeed, for some scheduling problems, a heuristic algorithm May be found that runs in polynomial time in the size of the problem and Delivers an approximate solution whose ratio to the optimal solution is guaranteed To be no larger than a given constant or a certain function of the size of the problem. However, for most NP-hard problems guaranteeing such an approximate solution Is itself an NP-complete problem? In this case, the amount of improvement of the Heuristic algorithm with respect to the existing algorithms should be measured via Simulation. A challenging problem in real-time systems theory is calculating the utilization Bounds associated with each allocation/schedule algorithm. The obtained utilization bound allows not only to test the schedulability of any given task set for the scheduling algorithm, but also it allows to quantify the effect of certain parameters such as the number of the processors, the size of the tasks, and the number of Preemptions on schedulability. Calculation of utilization bounds of multiprocessor Scheduling for real-time systems is one of the major research directions that should be further investigated.

If we reduce the scheduling problem into a known NP-complete problem , such as bin-packing or discrete knapsack problem, the existing approximation algorithms for problem can be applied to the scheduling problem. Consider each of the aforementioned problems. The second possibility is developing a polynomial time algorithm that provides an optimal feasible schedule for the problem. The optimality of the algorithm should be proved. We must prove that the algorithm may fail to meet a deadline only if no other scheduling algorithm can meet the deadline. In order to prove optimality, we need to have the utilization bounds associated with the algorithm. The utilization bounds enable an admission controller to decide whether an incoming task can meet its deadline based on utilization-related metrics. In fact, the utilization bounds express the sufficient conditions required for feasibility of the algorithm.