Click here to Skip to main content
Click here to Skip to main content
Technical Blog

Real-time scheduling

, 3 Feb 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
Real-time scheduling in operating systems.

Definition

A real-time operating system is a system that

  • schedules execution of tasks in a timely deterministic manner, and
  • is scalable.

The scheduler follows a set of algorithms that determine which task executes at each moment. Preemptive priority-based scheduling is a mandatory property of the operating system we evaluate for use in our application.

A task or ‘thread’ in this context is a sequential execution stream in a multi-tasking OS (cfr. Simple Platform Abstraction).

Key characteristics for a real-time system are

  • reliability (stability),
  • predictability (it must be deterministic),
  • performance (the faster the better),
  • compactness to code size (space is money) and
  • scalability (one starts with 2 tasks and eventually one ends up with a seven-headed dragon).

The RTOS we are looking at follow the ‘scheduler paradigm’ (cfr. Operating systems for embedded systems). There are two main levels or categories of execution that can code-execute logic:

  • The interrupt level and
  • The task level.

About interrupts and tasks

An interrupt is an asynchronous exception of which the source is an internal or external hardware device (note: if the OS supports system calls then software interrupts are possible as well). Implementation dependent Programmable Interrupt Controllers (PICs) prioritize multiple interrupt sources so that at any time the highest priority interrupt is presented to the core CPU for processing. Nesting interrupts refers to the ability of a higher priority interrupt source to preempt the processing of a lower priority interrupt. That means the higher priority interrupt will interrupt the lower priority interrupt, the higher priority interrupt will run to completion (unless interrupted by a higher priority interrupt), and then the lower priority interrupt will resume. The above explanation refers to so-called maskable interrupts: lower priority interrupts are masked (prevented from running) by higher priority interrupts. Non-maskable interrupts are also possible; these have the highest priority (sometimes even higher than the RTOS itself) and cannot be prevented from happening. Click on the figure to enlarge it.

interrupt handling scheme

When interrupts are not running, the core has time for running scheduled tasks (Threads at task level). Of course, these tasks can (and should) also be prioritized.

The figure shows an example of  what a cpu or micro-controller is doing in a running system (find the timer tick!).

The performance of an embedded (real-time) system is proportional to:

  • the latencies involved with the interrupt and
  • the task handling scheme.

Interrupt latency is the time from when the interrupt request is triggered until the ISR ( = the code of the interrupt service routine)  is running. Context information handling (of a task or interrupt) is additional overhead and increases the latency but should also be deterministic and known. Task switching latency is the time when a task should be made to ‘run’, involving the time it takes to store the context information of the running task and restoring the context information of the to-be-run task.

Interrupt priorities are assigned within the PIC; the system designer usually has full or at least some control on them (this is PIC platform specific). But how to determine the priorities of the various tasks? Generally, the more important the task, the higher the priority it should get assigned. This is true for interrupts and tasks, but more criteria are important and should be considered.

Scheduling schemes

Rate Monotonic Scheduling (RMS) is a scheme where priorities are assigned based on the execution rate (how many times per second it should run). Tasks (both ISRs and Threads, thus all schedulable entities in this context) must be periodical and must be independent (e.g. no shared resources). The higher the required execution rate (frequency), the higher the priority.

Earliest Deadline First (EDF) schedules tasks according to frequency (e.g. number of times per seconds the task should run), deadline (to task completion) and task execution duration. A good maximum task execution duration estimation is very important.

Caveats for real-time system implementations

  • Deadlocks: true for general software as well.
  • Priority inversion: the higher priority task may be blocked waiting for a lower priority task to execute, and tasks with priorities in between have a higher priority in running, thus both lower priority as higher priority task do not run. This can be solved by either giving the lower priority task a priority boost (it usually gets the priority of the blocked high priority task or higher), or by designing the system so that no priority inversion can occur by using e.g. lock-less queues, etc…

priority inversion

Usage advice with reference to the simple platform abstraction

  • Only strict and minimal essential tasks are done in interrupt: a small interrupt service routine (ISR) responds to the generated interrupt.
  • The ISR possibly queues essential data for later processing and signals the related task (no longer running in interrupt context): sometimes this is called the Interrupt Service Task, Thread (IST) or Bottom Half (e.g. Linux).
  • The IST awakes – whenever the scheduler determines it should run given the assigned priorities – as a response to the signal, and starts or resumes processing.
  • The IST runs to completion (unless interrupted by a higher priority task or any interrupt), and will again block on a signal or on timeout expiration.
  • An IST has a timeout, and it will be ready to run when this timeouts expires anyway.
  • An IST is usually signaled from an ISR, but it can also be signaled by another IST.
interrupt service routing to interrupt service task

References

Real-time concepts for Embedded Systems – Qing Li, Caroline Yao.

Embedded Systems Architecture – Tammy Noergaard.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Gert Boddaert
Technical Lead rtos.be
Belgium Belgium
Gert Boddaert is an experienced embedded software architect and driver developer who worked for companies such as Agfa Gevaert, KBC, Xircom, Intel, Niko, (Thomson) Technicolor, Punch Powertrain, Fifthplay, Cisco and Barco. For more obscure details, please take a look at his LinkedIn profile. Anyway, he started out as a Commercial Engineer – option “Management Informatics”, but was converted to the code-for-food religion by sheer luck. After writing higher level software for a few years, he descended to the lower levels of software, and eventually landed on the bottom of embedded hell… and apparently still likes it down there.
 
His favourite motto: “Think hard, experiment and prototype, think again, write (easy and maintainable) code”,
 
favourite quote: “If you think it’s expensive to hire a professional to do the job, wait until you hire an amateur.” – by Red Adair,
 
I can be contacted for real-time embedded software development projects via http://www.rtos.be and http://www.rtos.eu
Follow on   Google+

Comments and Discussions

 
QuestionIllustration package Pinmembertricychloramine22-Feb-13 10:27 
AnswerRe: Illustration package PinmemberGert Boddaert28-Feb-13 4:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.1411022.1 | Last Updated 3 Feb 2013
Article Copyright 2013 by Gert Boddaert
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid