TTK4145 - Sanntidsprogrammering

Modules

• Consistent abstraction

• Clear, central purpose and well-named to reflect that purpose

• Abstract enough to treat the class as a black box, without needing to understand its internal implementation

• Complete and self-contained services, ensuring no meddling with internal data

• Hide its implementation details from other classes as much as possible

• Independent and loosely coupled, avoiding assumptions about its users or derived classes

Routines

• Name describes exactly what is does

• Is the reason for creating it sufficient? (Reduce complexity, avoid duplicate code, abstraction, simplify boolean tests)

• Performs one well-defined task/is functionally cohesive

• All parts that would benefit from being put into their own … has been put into their own …

• Obvious and clear interface

• Loose coupling - the connections are small, intimate, visible and flexible

• Functions are preferred over procedures

Data Names

• Type names are descriptive enough to help document data declarations

• Variables are named well

  • Count/Index over Num

  • Avoid i, j or k as loop index

  • Booleans named so when they are true is obvious

• Are variables only used for the purpose for which they were named?

• Are well-named enumerated types used instead of makeshift flags or boolean variables?

• Are named constants used instead of magic numbers or magic strings?

• Do naming conventions distinguish among type names, enumerated types, named constants, local variables and global variables?

• Code is more read than written!

Data Organization

• Are extra variables used for clarity when needed?

• Are references to variables close together?

• Are data types simple so that they minimize complexity? (Data over objects)

• Is complicated data accessed through abstract access routines (abstract data types)?

Code Control

• Is the nominal path through the code clear?

• Are related statements grouped together?

• Have relatively independent groups of statements been packaged into their own routines?

• Does the normal case follow the if rather than the else?

• Are control structures so simple that they minimize complexity? (The code should be geometric)

• Does each loop perform one and only one function, as a well-defined routine would?

• Is nesting minimized? (Prefer longer functions over nesting, though none of them are particularly good)

• Have boolean expressions been simplified by using additional boolean variables, boolean functions and decision tables?

Layout

Does the program’s … show its logical structure?

Design

• Is the code straightforward, and does it avoid cleverness?

• Are implementation details hidden as much as possible?

• Is the program written in terms of the problem domain as much as possible rather than in the terms of computer-science or programming-language structures?

Patterns for intelligent design

State Machines, Permissible Inconsistencies, and Purity and Testability

State Machines

Framework for Looping and Reacting, Prevent Invalid States, Effective Design and Structured Reaction

Framework for Looping and Reacting

Create a pattern that reacts conditionally to inputs based on previous states

Prevent Invalid States

Make it hard to program incorrect behaviour by structuring the state machine to disallow invalid combinations

Effective Design

The state machine pattern ensures clear separation of states and transitions, minimizes invalid states, and simplifies debugging and testing

Structured Reaction

By defining clear state transitions and persistently storing essential data, the system reacts predictably to inputs, maintaining a reliable and manageable structure

Implementations steps for State Machines

Loop Initialization, Identify Inputs and Outputs, Persist State Information, Minimize Stored Data, State Enumeration and Reaction

Loop Initialization

Establish an infinite loop to continuously check inputs and generate outputs

Identify Inputs and Outputs

Determine discrete-time inputs (events/changes) and outputs to stream-line processing and reduce unnecessary activity.

Example inputs: Button press/release, floor sensor activation, stop button, timers.

Example outputs: Motor direction, door control, floor indicator, button lights

Persist State Information

Store minimal necessary inputs and outputs for conditional reactions.

Avoid duplication and invalid combinations by carefully analyzing and storing essential data

Example Stored Data: Button press status, current floor, movement status, door status and specific timers

Minimize Stored Data

Use heuristics to determine what needs to be stored and what can be derived or ignored.

Focus on essential states to reduce complexity: elevator’s position, stop button status, movement status, door status

Reduce to manageable combinations and identify invalid states to be avoided

State Enumeration and Reaction

Define a set of unique states based on stored data and possible inputs

Implement state transitions based on current state and received inputs

Use input-first or state-first approach depending on the structure that minimizes code duplication

Core and Shell

A way to structure code so that testable things are easy to test and not testable things don’t need much testing

Core

Pure Functions: Functions with explicit inputs and outputs, containing logic like decisions, algorithms, loops and conditions

No Side Effects: No access to global variables, network, disk or external communication

Testable: Easy to write tests for these functions because they are deterministic and independent of external state

Shell

State Management: Code that handles input, modifies state, and outputs results based on instructions from core functions

Side Effects: Includes all variables, communication (input/output), network, disk operations, etc.

Simple Structure: Contains minimal or no loops and conditionals, making it straightforward but less critical to test exhaustively

Benefits of Shell and Core

Separation of Concerns, Ease of Testing, Simplified Action Code and Integration with State Machines

Separation by Modification

Group by Modification Needs: Split data and outputs based on modification requirements. Each group should have its own state machine, avoiding unnecessary data grouping and ensuring clear responsibility.

Parallel state machines reduce the total number of enumerated states. Smaller individual states are easier to maintain

BAD!

Interacting State Machines

Create interfaces for state machine interactions, minimize interactions and avoid shared data/references.

Simplifies testing by isolating processes. Avoids the need for explicit synchronization. Ensures within-program communication mirrors between-program communication

BAD!

CAP Theorem

Consistency, Availability and Partition tolerance. Can only have two out of three

Protocols for Paradoxes

Limit contradictions and manage message acceptance/discarding. Use additive approaches, avoid negation and limit reset points.

Minimizing accessibility

Encapsulation, Simplicity and Minimalism, Completeness

Encapsulation

By minimizing accessibility to the members of a class or module, you encapsulate the internal workings of the class. This means the internal data structures and algorithms can be changed without affecting the code that uses the class

Simplicity and Minimalism

Exposing fewer details about the internals of a module simplifies and minimises the interface. A simpler interface is easier to understand and use correctly. Users of the module do not need to understand its inner workings, only the public interface. Only want/need orthogonal variables in the interface

Completeness

A complete interface provides all necessary functionalities without exposing the internal data. This means that all required operations can be performed through the provided methods, which should be well-documented and intuitive

Functional cohesion of functions

Isolation of Responsibilities, Reduced Coupling, Simple Building Blocks, Coherent Abstraction level, Debugging

Isolation of Responsibilities

A cohesive routine’s clear and isolated functionality prevents if from being influenced by the caller’s specific needs, avoiding hidden dependencies and complexity

Reduced Coupling

Cohesive routines reduce interdependence between parts of the code, making the codebase more modular and maintainable

Simple Building Blocks

Routines focused on one task can serve as reusable, composable building blocks, aligning with the concept of separation of concerns

Reliability

The software behaves according to its specification

Fault

The bug

Error

The event / the manifestation of a fault

Failure

System failed to behave according to spec

Failure/error modes

Different ways a system can fail

Fault Prevention

Reduce number of faults

Fault Tolerance

The ability of a system to continue operating properly in the event of the failure of (or one or more faults within) some of its components

Full Fault Tolerance

Ensures the system continues operation as normal, at least for some time

Graceful Degradation

Reduces the functionality to only perform core tasks while the system waits for repairs

Fail Safe

The system stops all operation, but ensures its integrity. Ex, a failing pitch controller on a helicopter might resset the pitch to zero before shutting down

Redundancy

Extra elements introduced by system designers to detect and handle faults

Static Redundancy

Duplicate components that are present and operating simultaneously. Ex. N-version programming

Dynamic Redundancy

Extra/duplicate components are invoked when needed. This type of redundancy has four stages: detect, confine, recover, treat. Ex. recovery blocks

Forward Error Recovery

Continues with selected corrections, requiring a clear understanding of the error and its remedies to avoid worsening the situation

Backward Error Recovery

Steps back to a previous state (recovery point) and attempts the same action with an alternative method. Risk the domino effect if recovery points are not synchronized.

Often not acceptable since real time systems often have interactions with other systems that may depend on it to behave correctly. There is no time to waste in a real time system; when we report back to the module that initiated the failed operation, it might be too late to retry/fix

N-version programming

Developing multiple independent versions of the same software specification and executing them on different hardware platforms or using different algorithms. HW components often fail individually, while multiple instances of the same SW on the same computer will all fail together

Recovery blocks

An implementation of dynamic recovery applied to software. Defines all entries to a software block as a recovery point, and then have an acceptance test before the block can exit

Failure Mode Merging

Combining failure modes to simplify fault handling or recovery mechanisms. By merging to one error mode, even unknown errors can be handled because we only care that the program failed in some way

Acceptance Tests

Tests to check that everything is OK. Tests performed to validate whether a system meets the acceptance criteria set by the specifications. Has a merging of failure modes effect and can detect unexpected errors

Checkpoints

Markers within a system that record its state at a particular point in time, enabling rollback or recovery to that state in case of failure

Error Detection - Learn by heart list

Replication checks, Reversal checks, Reasonableness checks, Dynamic Reasonableness checks, Timing checks, Coding checks, Structural checks

Replication checks

In N-version programming, … checks start a recovery routine if one or more of the N results are incorrect, useful in systems with uncertainty about correct results

Reversal checks

Applied when input-output relationship is one-to-one, enabling reversal calculation and comparison to detect errors

Reasonableness checks

Validate system knowledge, such as range checks for date and time validation or assertions

Dynamic reasonableness checks

Compare current output to previous output, detecting abnormal jumps or changes in system behaviour

Timing checks

Implemented with a watchdog timer, ensuring each process resets within a set interval, specifically for time failures

Coding checks

Utilize extra information sent with data for comparison, common in communication protocols, like using checksum to verify data integrity

Structural checks

Ensure correct data structure, like verifying the number of items in a list, useful for detecting unexpected changes

Coordinating recovery points

A method for avoiding the domino effect. Using backward error recovery in a multi-thread system involves rolling back threads. As there usually is inter-thread communication, rolling back one thread can trigger rollback in other threads, hence the domino effect.

No

Is it possible to achieve fault tolerance without redundancy?

Acceptance test for allocate()

• Number of free items reduced with one

• Number of allocated items increased with one

• Sum of allocated and unallocated items is constant

• Compare number of allocated items with applications view of allocated items

• Checksum of allocated items

• Check non-existence of references to unallocated items

Reliable storage

Find fault model: Write - failed, wrong data, wrong place. Read - failed, old data, bad data, wrong place

Detect, merge error modes, inject errors: Enhance buffer with address, checksum, versionID and status bit in addition to data itself. All errors → fail. Induce “decay thread” for error injection testing

Handling with redundancy: Implement multiple copies of the buffer (using version ID for latest). All errors in read will rewrite the data that caused the error to repair it. Repair thread periodically checks data for errors and repairs as necessary. RAID and ECC. Refresh thread

Reliable communication

Find fault model: Message lost, reordered, modified, delayed, duplicate, wrong recipient

Detect, merge error modes, inject errors: All errors → message lost. Add checksum, version ID, sequence number on message, sessions. Send acknowledgement on well received message. Error injection by throwing some messages away

Handling with redundancy: Acknowledgement, timeout and resending. Sequence numbers, sessions/connections, retransmission buffers

Reliable calculations

Fault mode: 1 mode; not to do the next correct side effect

Detect, merge fault modes inject errors: all failed acceptance tests → panic/stop

Handling with redundancy: checkpoint/restart, process pairs, persistent processes

Atomicity

An action is considered atomic when the tasks executing it operate independently of any other tasks. During its execution, no active task is aware of the ongoing activities within the action. State changes are only revealed after the action is concluded.

Transactions

Atomic actions with backward recovery as standard error recovery. Are either done correctly or not done at all, no inbetween

Heuristic transactions

A resource manager makes the decision to commit or abandon the transaction without waiting for a global decision from the transaction coordinator.

Interposition

The ability to insert additional processing or functionality between the initiation and completion of a transaction, without directly modifying the transactional logic itself

Atomic actions as module design pattern

No successfully for low-level SW design: Because it it too abstract and requires extensive infrastructure. Atomic actions also do not have a reasonable composition, which leads to a unstructured forest of actions. We don’t get help from the structures to structure the functionality as AC do not have a fixed structure.

Might work good on system level for distributed systems: If we imagine a distributed system of servers using each other’s services, atomic actions may be a good way to ensure consistency and manage interactions

Drawbacks of transactions

Heavy infrastructure

Sometimes errors are acceptable

Performance and HW overhead

Transactions are a specialised skill set - not common knowledge among engineers

Infrastructure required for transactions might not be fully developed or integrated in the chosen platform/tools.

Boundaries for atomic actions

Start: To establish which participants may be affected, and to set a safe, consistent, starting point (if an error has occurred, it must have happened after the start point.)

Side: Limiting communication (restricting messages, locking variables...) to members to hinder error spreading out of the Action.

End: Ensuring a consistent system before leaving the action so that any errors do not spread / have consequences after end of Action.

Realization of boundaries

Start: In static systems this might be hard coded. If not; membership list, action manager to keep track of members of each action, recovery point if preparing for backward error recovery.

Side: Resource locking of resources in action. Transaction ID must be part of all communication, so all threads wanting to act on a message must join the transaction.

End: Acceptance test, any vote or synchronisation; two-phase commit protocol

Optimistic Concurrency Control

Assumes that conflicts are rare. Transactions proceed without restrictions, but before committing changes, they check if accessed data has been modified by other transactions. If conflict arises, the transaction is rolled back. This is an alternative to locking, so it reduces locking overhead and improves system concurrency. May result in more transaction retries in more high-contention environments.

Log

An alternative to recovery points. Tracks every single change, and is able to save before-state (undo), store intended effect/new values (redo) and use checkpoints where all active operations are tracked.

Log manager

Handles the creation, maintenance and retrieval of log records, centralizing log management. Facilitates easier recovery and inspection

Transaction manager

Responsible for coordinating and managing transactions in a database system. Handles the initiation, execution and termination of transactions

Resource manager

Manages access to shared resources in a multi-user environment. Ensures that resource access aligns with transactional requirements by working closely with the transaction manager. Prevents conflicts and ensures data integrity by managing simultaneous access to resources

Two-Phase Commit Protocol

All participating systems either commit or roll back changes together, maintaining consistency. Coordinating transition on committing a transaction between phases (growing and shrinking) to avoid partial updates

Two-Phase Execution

To manage resource locking and ensure atomicity by dividing the execution into a phase where resources are acquired (growing) and a phase where they are released (shrinking). To reduce risk of deadlocks and ensure consistency

Read/Write- Locking of accessed resources

Control access to resources by allowing multiple readers and a single writer, preventing conflicts and ensuring data integrity. Reduces risk of race conditions and ensures safe data modifications

Key properties of atomic actions

Isolation, No Communication, State Consistency, and Indivisibility

Mechanisms to share errors in a multi-thread

Asynchronous notification, polling error status variable, message-based systems, asynchronous transfer of control (ATC)

Extended commit protocol

Share error status during commit protocol, forward error recovery can be triggered by coordinator

Asynchronous transfer of control

Handle errors asynchronously within the AA-frame. Enables one thread to interrupt another thread with termination mode, ensuring that the interrupted thread does not continue from where it left off after the interruption

Resumption model

After handling an error or signal, the execution resumes from the point where it was interrupted.

Often less used due to the need of polling and rechecking, state corruption and more difficult error handling.

Termination model

After handling an error or signal, the program control is transferred to a specific error handling block or routine, which manages the error and determines the subsequent steps. Assumes the program cannot continue in the same context, and must handle the error separately

Problems solved by setjmp and longjmp

Transforming a ‘Signal’ into ‘Termination Mode’, Zero-overhead error handling, General exception handling

Semaphore

A shared non-negative integer equipped with two methods; wait and signal. Atomic and eliminates the need for busy waiting.

wait(S)

If the value of the semaphore, S, is greater than zero then decrement its value by one; otherwise delay the task until S is greater than zero (and decrement its value)

signal(S)

Increment the value of the semaphore, S, by one

Critical Regions

An imagined language support for mutual exclusion and guards. Named code blocks are regions and they are mutually exclusive. Ensures mutual exclusion in critical regions of code to protect variables from concurrent access. Processes are blocked from entering a region if another task is active within it. Condition synchronization is managed through guards—logical conditions that must be true for a task to enter the region. If the guard is false, the task is delayed. There is no guaranteed order of access for tasks waiting to enter the same region. The guards can evaluate any variable. This becomes a problem since they must be polled continuously and can still be wrong when evaluating (NB ifs don’t work). Also the critical regions can be anywhere in the code, which is bad code quality. Imaginary because useless.

Monitors

A region with a collection of procedures and local variables, ie. module. There are condition variables, instead of guards, that can only be accessed from inside the …

Double Interactions

Involve two separate calls.

First Call (Non-blocking announcement): Checks conditions and signals intent without waiting to complete, essentially “registering” the request

Second Call (Blocking): This call actually performs the operation and wits until it can be safely executed

Non-Atomicity: The state might change between calls, leading to inconsistencies and difficult error recovery

Boundary Issues: State changes between calls complicate maintaining clear system boundaries

Usage in Ada: Ada doesn’t natively support this pattern easily, requiring careful design for consistency and synchronization

Requeue

Allows an ongoing operation (entry call) to be redirected to another entry. Allows for more complex synchronization patterns and can help manage situations where the state needs to be reassessed or additional conditions need to be met

Entry Families

A way to define multiple entries indexed by a parameter, forming an “array” of entries. Provides granular control by associating different conditions or actions with different indexes.