Two Wrongs

(don't make a right)

Reading Notes: Guide for Ravenscar in High Integrity Systems

by ~kqr

I often read technical texts in order to understand something. I'm bad at taking notes as I read. I should do that more often, because

  1. my memory sucks, and
  2. other people may be interested in the abridged version of the texts I read.

The last couple of days (my focus has been down the drain...) I have been slowly making my way through "Guide for the Use of the Ada Ravenscar Profile in High Integrity Systems".

It should be noted that ultimately, I'm doing this reading for my own, which means I skip parts of the text that don't concern my personal needs. If you want the full details of everything, you should read the original. If you're just curious about what something is on the surface, these notes may be enough.

Table of Contents

I wish I had time to hyperlink these. I should really start writing these articles in something like org mode to get that automatically. Oh well. Here's an overview of what this article contains:

  1. The Meaning of "Real-Time"
  2. Activity Types
  3. Deadlines
  4. Task States
  5. Traditional Methods for High-Integrity Multi-Tasking
  6. Ravenscar
  7. Ravenscar Restrictions
  8. Sequential Elaboration
  9. Example Usage
  10. Working Under Ravenscar

The Meaning of "Real-Time"

This is not in the article I'm reading, but I'm including it for the sake of completeness. A "real-time" system is a system that must respond to events in a timely manner. Something like a video game might intuitively sound like a real-time system, but in practise only very few components of video games are actually designed with actual deadlines in mind. Most operations in a video game are meant to finish "as soon as possible", not "within 10 milliseconds".

This concept will be more clear when we get to the section on different types of deadlines.

Activity Types

  • Cyclic activities: happen with regular intervals
  • Sporadic activities: happen in response to events

Deadlines

  • Hard deadlines: must be met in all conditions. If they are missed, the system has failed entirely.

    This can be the case with medical systems where failing to turn off the high-energy radiation beam within a few milliseconds cause tissue damage or death. It doesn't have to be that serious, though: in any system (intrusion detection systems?) where an attacker may be able to trigger a "non-average" scenario, we want deadlines to be met also under these conditions. In other words, systems with hard deadlines are systems that cannot be victims of denial of service attacks.

  • Firm deadlines: must be met under "average" or "normal" conditions. Once the deadline has passed, the completion of the task no longer has any value. Failing to meet the deadline seriously degrades system performance.

    In this category we may find in-car GPS correction calculations – it's not disastrous if the deadline is missed because we're still have a human driver that is responsible for driving safely, but the environment may have changed enough that the old calculations are based on incorrect numbers and we need to re-do the calculations with new numbers anyway.

  • Soft deadlines: must also be met under "average" or "normal" conditions. Even if the deadline is missed, there is still value in completing the task. Failing to meet the deadline degrades system performance.

    Something like system-level services in regular operating systems should belong here (but they clearly don't – I think few operating systems are designed with deadlines in mind). We want the base level operations on our computers to be responsive at all times, but we want the operation to be performed even if it for some reason becomes delayed.

  • Non-critical deadlines: should be met, but failure to meet it only degrades system performance and does not count strictly as a failure.

    I'm a bit fuzzy on where to draw the line between soft and non-critical deadlines, but the way I understand it is that it's more of a distinction of the kind of operation the deadline belongs to. If the deadline belongs to one of the primary functional requirements of the system, it is a soft deadline. If it belongs to an auxiliary system not required for the primary functionality, it is a non-critical deadline.

Task States

  • Ready to run:can execute instructions once processor time is available
  • Suspended: cannot execute until some event occurs
    • Can become ready synchronously, i.e. as a result of an operation performed by the currently running task
    • Can also become ready asynchronously, i.e. as a result of an external event unrelated to the currently running task
  • Blocked: waiting for access to shared resource currently owned by another task

Traditional Methods for High Integrity Multi-Tasking

  • Get rid of separate processes with independent control entirely
  • Instead, model processes as reentrant procedures
    • which are strictly limited in how much they are allowed to do
  • Have a central cyclic executive that calls the procedures in a deterministic manner
  • This is easy to analyse in terms of real-timeyness, but it leads to poor software design

Ravenscar

  • We want to have real processes with separate threads of control
  • But we also want to be able to analyse the schedulability of the program to ensure deadlines are met
  • Ravenscar is a set of restrictions on Ada which together limit the concurrency features in such a way that analysis is possible
  • Ravenscar is only concerned with concurrency analysis – it does not have any opinion on the sequential parts of the program

In this article, I'm going to use the term processes, which in terms of Ada means "tasks and protected objects" – the concurrency mechanisms used by Ravenscar.

Ravenscar Restrictions

Ravenscar guarantees that

  • The set of independent processes and interrupts is fixed and constant after program elaboration by
    • Only allowing creation of processes in the declarative part of library-level packages (the number of processes cannot increase during run-time)
    • Forbidding termination of processes (the number of processes cannot decrease during run-time)
      • however, what happens if a task actually terminates is implementation-defined
      • for example, with GNAT, task termination under Ravenscar counts as "erroneous execution" which is frighteningly similar to "undefined behaviour" in CC
    • Forbidding run-time changes to priorities and interrupt handlers
  • Synchronisation and communication between processes happen only through protected objects and suspension objects by
    • Forbidding select statements and entries in tasks
  • The program has deterministic memory usage by
    • Forbidding implicit heap allocations
  • There is a deterministic execution model by
    • Only allowing one entry for each protected object, which prevents non-determinism caused by multiple open entries and choosing which is served first
    • Only allowing one process to block at that entry, preventing non-determinism caused by differing queue lengths
    • Only allowing simple barriers (i.e. a single boolean variable) which reduces variability in execution time of the barrier
    • Forbidding relative delays, which are trouble if a process is preempted after calculating the relative delay, but before actually suspending at the delay
    • Only allowing delays to be calculated using the high-precision Ada.Real_Time library
    • Forbidding potentially blocking calls in protected subprograms; these are primarily
      • task entry calls
      • delay statements
      • language-standard defined operations like file I/O

Sequential Elaboration

  • In standard Ada, tasks are started as part of program elaboration, not after it
    • This means a task or interrupt handler can start running before the full program is initialised
      • Thus, an unfortunate processs may read, e.g., a global constant that has not yet been initialised
  • To solve this, the Ada standard is revised to include the pragma Partition_Elaboration_Policy (Sequential)
    • This pragma simply makes sure non-environment processes are not started until the program is otherwise fully elaborated

Example Usage

I won't copy and paste the example code both because it's superfluous and because I don't know copyright law well enough. I'll share some of my takeaways though.

  • Cyclic tasks with precedence
    • Imagine a set of tasks X, Y and Z in decreasing priority, such that X has the highest priority and Z the lowest
    • None of the tasks peform any blocking operation, and they all have relatively short deadlines (say, 20 milliseconds, in our example)
    • All three tasks read a common "start time" from a protected object
    • All three tasks delay until (Start_Time + Milliseconds (2000))
    • Then, technically, the execution on a monoprocessor should always be first X, then Y, then Z in short succession, followed by the program idling for roughly two seconds, and then it repeats
  • Event-triggered tasks
    • Sit in a loop, and at the beginning of the loop they wait on an entry or suspension object
    • Once they are released by that entry or suspension object, they perform their action associated with the event
    • If they need to know more about the event to run, they should wait at a protected entry
  • Priority of protected objects
    • Protected objects must have a priority ceiling higher than any of the calling tasks
      • This prevents deadlocking where the task is waiting for a protected object that is not allowed to resume because it has a lower priority than the task waiting for it
      • The default priority is System.Priority'Last which works but may be unnecessarily high and cause other high-priority tasks to miss deadlines they would otherwise meet
    • Suspension objects vs. protected entries
      • Both are used for synchronisation
      • Protected entries can communicate data as part of this synchronisation (in other words, protected entries can have out parameters)
      • Protected entries can also execute other (non-blocking) code as part of the signalling operation
      • Suspension objects do not have parameters and cannot execute code – synchronisation is all they do
  • Two protected entries
    • Useful e.g. to read and write from a buffer – we want to block writes if the buffer is full, and block reads if the buffer is empty
    • Use two protected objects (e.g. one for reading and one for writing)
    • They signal each other with regular procedures when they need to start blocking
    • They allow external code to wait on each

Working Under Ravenscar

These are my own "big take-away points" from the guide. I hope these capture a decent intuition for what Ravenscar is and how it's meant to be used.

  • Ravenscar only cares about the concurrency of the program. In other words, Ravenscar only touches the following two features of Ada:
    • Tasks
      • fixed set of parallel threads of control that run from program start to program termination
      • the code running in a task is essentially sequential – notably, tasks are not by themselves used for synchronisation and communication
    • Protected objects
      • used for communication (protected procedures for writing to a shared value, protected functions for reading from a shared value)
      • also used for synchronisation (protected entries allow processes to wait until some condition in the protected object is met)

If you enjoyed this article, you might like others tagged with