Rtos

Introduction • What is real-time? – “a real-time system is a system whose correctness includes its response time as well as its functional correctness” – The system doesn't just run software to plough through the process; it needs to do it in a timely manner

Introduction • So, real-time systems care about timeliness, but just how timely isn't clear until you add a modifier to "real-time" – In other words, real-time is very much a gray region – "Response to what?" To "events", which are either external events, communicated to the system via its input/output interfaces (which include things like Ethernet as well as audio, keyboard, or mouse input), or to timer-triggered events within the system itself

Outline • • • • •

Basic definitions The challenges Can we use existing systems Proposed solutions Case studies of real-time oss.

Basic definitions • A task is the basic unit of execution. Each task has three important properties: 1. release time: the point in time from which the task can be executed. 2. deadline: the point in time by which the task must complete. 3. execution time: the time the task takes to execute • E.g. brakes controller

example • If we have the following set of tasks: task1: release=0 deadline=3 exec time=2 task2: release=2 deadline=5 exec time=1 task3: release=6 deadline=10 exec time=3 Then they must be scheduled during these periods:

0

1

2

3

4

5

6

7

8

9

10 11

Classification of task timing constraints • There are two types of timing constraints hard and soft. • Definitions: • if missing a deadline is a fatal error or has disastrous consequences it is considered hard (missing an occasional deadline is not acceptable) • otherwise (if some percentage of missed deadlines is acceptable) it is soft. • Classic examples: braking systems controller => hard multimedia streaming => soft

Soft real time systems • Contain only tasks with no hard timing constraints. • Also known as “best effort” systems • Most modern operating systems can serve as the base for a soft real time systems. • Examples: multimedia transmission and reception, networking, telecom (cellular) networks, web sites and services, computer games.

Soft real time systems • Less restrictive time by nature • Requires that critical processes receive priority over less critical ones. • Implementation of soft real time applications requires careful design of the scheduler and other related aspect of the operating system

Soft real time systems • System interactions must be known as well as the system must have priority scheduling giving the highest priority ti real time processes • In addition, the dispatch latency must be small

Hard real time systems • Contains tasks with hard timing constraints. • Requires formal verification/guarantees of being to always meet its hard deadlines (except for fatal errors). • Examples: air traffic control , vehicle subsystems control, medical systems

Hard real time systems • The scheduler than does one of two operations : – The first would be the allowance of the process, guaranteeing that the process will be completed on time – The second would be the rejection of the process. This is known as resource reservation. This type of guarantee requires that the scheduler knows the exact length of time each type of process the operating system to perform

Hard real time systems • Therefore, each operation must be guaranteed to take an optimal amount of time. • “Hard real time system are composed of special purpose software running on hardware dedicated to their critical process”

Classifications of real time systems • The type of system can be either a uniprocessor , mp or distributed system. • Moving to an mp or distributed real time systems adds lots of difficulty by requiring real time communication and synchronization mechanisms between the processors.

Classifications of real time systems • There are two different execution models: • In a preemptive model of execution a task may be interrupted (preempted) during its execution and another task run in its place. • In a non-preemptive model of execution after a task that starts executing no other task may execute until this task concludes or yields the CPU.

Classifications of real time systems • The task model for a real time system has two main types: 1. purely periodic: every task is cyclic and executes periodically, even IO is polled. The nature of tasks doesn’t vary much between cycles. 2. aperiodic/asynchronous: most tasks in the system aren’t periodic.

Classifications of real time systems • A static system is a system where all tasks are knows at design time including their release times (full apriory knowledge). • A dynamic systems is a system that can dynamically create and destroy tasks at runtime (No full apriory knowledge).

Classifications of real time systems • In many real time systems the tasks have different priorities. There are two possible models : • static-priorities : the priorities of tasks don’t change during execution • dynamic-priorities the priority of tasks may change during execution

Classifications of real time systems • Sets of tasks are classified according to the way they share resources: • We will call a task set dependent if the tasks in it share resources. • We will call a task set independent if they do not.

Outline • • • • •

Basic definitions The challenges Can we use existing systems Proposed solutions Case studies of real-time oss.

The main challenges • Processor sharing – scheduling • Resource sharing • Handling external input / communication

Scheduling • a scheduler needs to decide when to run each task in order to meet the deadlines imposed on the tasks. • In order to do this the scheduler needs to base its operation upon the properties of the tasks (release times, deadlines ,etc..).

Scheduling • If scheduling is done online, the overhead of scheduling needs to be reasonable (this can be hard because most of the optimal scheduling algorithms are np-hard, even for a single processor). • If the task model is dynamic we need the scheduler to decide if adding some new task would prevent it from filling obligations to currently running tasks (admissibility testing).

Resource sharing • When tasks share resources they become dependant on one another and this limits our flexibility when scheduling, requiring us to use synchronization mechanisms to protect critical sections in the tasks. • This raises the issues of deadlocks, process starvation and priority inversion.

Handling external input / communication • In real time system there will often be constraints on the minimal time until the system processes input/communication. • These constraints must be reflected in the scheduling of tasks, the handling of external interrupts and the communication infrastructure and protocols chosen.

Outline • • • • •

Basic definitions The challenges Deficiencies in modern operating systems Proposed solutions Case studies of real-time oss.

Why most modern OSs are unsuitable • The basic guiding concept for most operating systems and schedulers is to strive for good average performance while in real time systems meeting the deadlines is far more important than average performance. • many modern operating features are problematic in a hard real time setting.

Windows • Windows (NT based) suffers from most of the same problems Linux does. • Windows doesn’t support the specification of timing constraints for tasks.

Windows • Interrupts may be delayed for an arbitrarily long time in critical sections of the kernel. • Handling of interrupts is done in two parts the second part the deferred procedure call is executed later in a FIFO manner and this may cause delays if a lot of DPCs are awaiting dispatch. • Requests for synchronization objects such as semaphores are also done in FIFO, leading to similar unpredictable delays.

Windows • The windows scheduler supports threads on an OS level. Each thread is given a priority . • The scheduler has compensation for input bound threads and anti-starvation mechanisms. • Windows has a “real time” priority for threads but other real-time threads and the kernel can preempt a task with real time priority . • A “real time” priority is higher than some parts of the OS, causing most non-real-time apps to become unusable

Fixing the problems • Fixing these problems in either OS would require either some form of “hack” into the operating systems design or a massive rewrite of the kernel. • This has been tried using both of the operating systems rt-linux, rialto.

Outline • • • • •

Basic definitions The challenges Deficiencies in modern operating systems Proposed solutions Case studies of real-time OSs.

Scheduling • •

•

Scheduling algorithm properties: An algorithm is said to be optimal if for each task set for which a feasible scheduling is possible the algorithm will find one (assumes tasks are independent). Schedulable utilization is the maximal utilization of a task set such that a task load under this utilization will be scheduled successfully by the algorithm.

Priority driven algorithms • This is a family of algorithms which gives the tasks priorities according to some criterion and schedules at each point the task with the highest priority. They are efficient in that if there are tasks ready to execute the CPU is always busy. • This approach is attractive because in case of performance degradation the most important tasks will be affected the least.

Rate monotonic • This algorithm assumes a periodic task model with preemption. • The Algorithm: is a priority driven algorithm where the tasks are assigned priorities proportional to their cycle length, the shorter the cycle the higher the priority.

example • If we have the following set of tasks: task1: period=deadline=3 execution time=1 task2: period=deadline=5 execution time=3

Then the schedule will look like this: 1 1

0

1

2

1

3

4

3

2

4

2

5

2

6

7

8

9

10

The problem with static priority driven algorithms • This simple example shows that a schedulable set of tasks can’t be scheduled based on static priorities task1: period=deadline=4 execution time=2 task2: period=deadline=10 execution time=5 Task 1 must have higher priority

1

3

2 1

1 Task 2 must have higher priority

0

1

2

3

4

5

6

7

8

9

10

EDF algorithm • The Earliest Deadline First algorithm is a priority driven algorithm in which the tasks get priorities according to how close their nearest deadline is. The closer the deadline the higher the priority.

example • If we have the following set of tasks: task1: period=deadline=3 execution time=1 task2: period=deadline=5 execution time= 3

Then the schedule will look like this: 1 1

0

1

2

4

3

2 2

3

4

5

2

6

7

8

9

10

EDF properties • The algorithm is optimal. • The schedulable utilization of the algorithm is 1 . • Priorities must only be recalculated when a new task arrives, as time advances equally for all tasks. • the algorithm behaves unpredictably at overloads, and suffers more from overloads than RM.

LST algorithm • The slack time of a task is the amount of time until the task must be scheduled or miss it’s deadline. • The least slack time algorithm is a priority driven algorithm in which the tasks receive priorities according the their slack times. The shorter the slack time the higher the priority. • The LST algorithm is optimal

Priority inversion • The priority inversion problem exists in the preemptive model when tasks are dependant on one another (share resources). it causes a high priority task to wait for a low priority task to conclude because it is holding a critical resource. • This problem can be at least partially solved by priority inheritance, or the priority ceiling protocol based on a similar concept.

Outline • • • • •

Basic definitions The challenges Deficiencies in modern operating systems Proposed solutions Case studies of real-time OSs

Case study • We will go over how some actual implementations of real time operating systems tackled these problems. • VxWorks

VxWorks • A dedicated real time system, not intended as a general purpose OS. • lacks many modern os features that interfere with real time performance (flat memory model, no paging).

VxWorks • Scheduling is done using a preemptive priority driven approach, priorities are chosen arbitrarily by the user (0-256). • Priorities can be changed by the user at runtime but this is discouraged. • A user can lock a task so that it can’t be preempted even by higher priority tasks or interrupts. • This allows the use of the fixed priority response time analysis to check schedulability offline.

VxWorks - summary • A dedicated and widely used real time system. • Offers the user maximal control , but also passes him responsibility for the deadlines. • Lacks many modern OS features.

Summary • This talk reviewed: - The basic concepts of real time systems - The challenges of building a real time system - The use of generic OSs as real time systems - Some Solutions to the Challenges. - The approaches taken by some real systems

questions

End