OS Model

This part of the AMALTHEA model describes the provided functionality of an operating system. Therefore the concepts of scheduling, overheads, and semaphores are supported, which are described in detail in the following chapter.

Operating System

The basic element in the OS Model is the operating system. There can be multiple operating systems in one model. The operating system type can be used to describe a generic operating system. It is also possible to use the vendor operating system type to define a vendor specific OS. An operating system contains a number of task schedulers and interrupt controllers. A task scheduler controls the execution of a task on one or multiple processor cores. An interrupt controller is the controller for the execution of ISRs and can be also mapped to multiple cores. The mapping of tasks and ISRs to their controller and the mapping of the controller to the cores can be done in the Mapping Model. An operating system can also contain a description of the overhead it produces. For this there is a more detailed explanation below.

Scheduler, Scheduler Definitions, and their Parameters

Schedulers refer to a definition which specifies the scheduling algorithm that decides if and when to schedule a processes. Each scheduler definition may refer to algorithm and process parameters (type is a SchedulingParameterDefinition). Algorithm parameters are set per scheduler whereas process parameters may have different values per process allocation (task or ISR). Each scheduler can have schedulingParameters which assign values to the algorithm parameters of their definition, i.e., a deferrable server scheduler should have a value for the algorithm parameter capacity. Schedulers can have computation items (a subset of the runnable items) that characterize the runtime behavior (algorithmic overhead) of the scheduler.

There are additional attributes in the scheduler definition to define the behavior of the scheduler in a hierarchy (parent and child schedulers):

Name Description
requiresParentScheduler boolean attribute indicating whether the scheduler requires a parent scheduler, defaults to false.
passesParametersUpwards boolean attribute that specifies that scheduler parameters set for a TaskAllocation will be passed on to the parent scheduler (if this scheduler does not have a parameter with this name), defaults to false.
hasExactlyOneChild boolean attribute that indicates if the scheduler can schedule only one schedulable entity or if it can schedule multiple ones, defaults to false.

Scheduler Definition

A scheduler definition is contained in the OS Model. There may be multiple scheduler definitions in the model. The definition has a name which is also used to uniquely identify standard scheduler definitions (like OSEK, EarliestDeadlineFirst, etc.) There is a number of standard scheduler definitions that are known in AMLATHEA they can be added automatically to each model and should not be changed. Scheduler definitions refer to algorithm and process parameters. Algorithm parameters can be set for each scheduler that uses the scheduler definition. Process parameters can be set for scheduler associations or task allocations.

Scheduling Parameter Definition and Scheduling Parameter

Scheduling parameter definitions are contained in the OS Model an may be referred to by multiple scheduler definitions. They have a type, can consist of many values (default is false), can be mandatory (default is true), and may provide a default value that shall be used if they are not mandatory. Scheduling parameters are key value pairs where the key is the definition and the value is some literal of type Value. The type specified in the scheduling parameter definition dictaes possible literals of their value, e.g. type Integer allows BigInteger, long, and integer literals. Standard scheduler definitions have only mandatory parameters (if there is no default value provided).

Standard Scheduler Definitions

The following gives a tabular overview of the standard scheduler definitions supported by AMLATHEA. The user can also define custom schedulers and parameters, but they may not be supported by tools importing AMALTHEA models.

Scheduling Algorithm Description and Parameters
Fixed Priority
OSEK OSEK compliant Scheduling. A fixed priority preemptive scheduling algorithm with task groups. Tasks belonging to the same task group are scheduled cooperatively (they do not preempt each other), preemptive otherwise. Tasks with the same priority also behave cooperatively.
Process parameters priority [1] Integer: The priority of the process (a higher value means a higher priority).
taskGroup [1] Integer: The OSEK task group number (if for two processes the number is equal, that means they are in the same task group).
FixedPriorityPreemptive Fixed Priority Preemptive Scheduling (e.g. AUTOSAR), same as OSEK but without task groups.
Process parameters priority [1] Integer: The priority of the process (a higher value means a higher priority).
Dynamic Priority
EarliestDeadlineFirst Earliest Deadline First (EDF): Task with the closest deadline in relation to the current point in time will be scheduled next. First introduced in: Liu, Chung Laung, and James W. Layland. “Scheduling algorithms for multiprogramming in a hard-real-time environment.” Journal of the ACM (JACM) 20.1 (1973): 46-61.
Process parameters deadline [1] Time: The time after each activation at which the process must finish.
PriorityBasedRoundRobin Round Robin scheduling algorithm assignes equally sized time slices to each process that it schedules. The priority describes the order in which the processes will be executed. If two processes have the same priority, the order of these two is random (non-deterministic).
Algorithm parameters timeSliceLength [1] Time: Length of each time slice.
Process parameters priority [1] Integer: The priority of the process (a higher value means a higher priority).
Proportionate Fair (Pfair)
PfairPD2 Proportionate Fair PD2 Scheduling (Pfair-PD2)
Algorithm parameters quantSize [0..1] Time = 1ns: Length of the minimum schedulable time slot used in Pfair scheduling. It is assumed that execution times are an integer multiple of this time slot length.
PartlyPfairPD2 Partly Proportionate Fair PD2 Scheduling (PPfair-PD2)
Algorithm parameters quantSize [0..1] Time = 1ns: Length of the minimum schedulable time slot used in Pfair scheduling. It is assumed that execution times are an integer multiple of this time slot length.
EarlyReleaseFairPD2 Early Release Fair PD2 Scheduling (ERfair-PD2)
Algorithm parameters quantSize [0..1] Time = 1ns: Length of the minimum schedulable time slot used in Pfair scheduling. It is assumed that execution times are an integer multiple of this time slot length.
PartlyEarlyReleaseFairPD2 Partly Early Release Fair PD2 Scheduling (P-ERfair-PD2)
Algorithm parameters quantSize [0..1] Time = 1ns: Length of the minimum schedulable time slot used in Pfair scheduling. It is assumed that execution times are an integer multiple of this time slot length.
Reservation Based Server
GroupingServer This is not a scheduler algorithm. Schedulers using this definition act as a logical grouping of tasks/child-schedulers, e.g. a partition for some tasks for budget accounting reasons. This scheduler does not take any scheduling decisions, and a parent scheduler is mandatory.
Algorithm parameters capacity [1] Time: The fixed budget that can be used by processes. It will be replenished periodically.
period [1] Time: Amount of time after which the capacity will be replenished.
Definition attributes ☑ requires parent scheduler
☑ passes parameters upwards
☐ has exactly one child
DeferrableServer Deferrable Server (DS): provides a fixed budget, in which the budget replenishment is done periodically. First introduced in: Strosnider, Jay K., John P. Lehoczky, and Lui Sha. “The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments.” IEEE Transactions on Computers 44.1 (1995): 73-91.
Algorithm parameters capacity [1] Time: The fixed budget that can be used by processes. It will be replenished periodically.
period [1] Time: Amount of time after which the capacity will be replenished.
Defintion attributes ☑ requires parent scheduler
☐ passes parameters upwards
☑ has exactly one child
PollingPeriodicServer Polling Server (PS): provides a fixed budget periodically that is only available at pre-defined times. If the process is not using the budget at that point in time the budget is lost.
Algorithm parameters capacity [1] Time: The fixed budget that can be used by processes (usually directly after it has been replenished). The capacity will be consumed even if there is no process using it. It will be replenished periodically.
period [1] Time: Amount of time after which the capacity will be replenished.
Defintion attributes ☑ requires parent scheduler
☐ passes parameters upwards
☑ has exactly one child
SporadicServer Sporadic Server (SS): provides a fixed budget, in which the budget replenishment is performed with a pre-defined replenishment delay after it was consumed. First introduced in: Sprunt, Brinkley, Lui Sha, and John Lehoczky. “Aperiodic task scheduling for hard-real-time systems.” Real-Time Systems 1.1 (1989): 27-60.
Algorithm parameters capacity [1] Time: The fixed budget that can be used by processes. It will be replenished after the specified amount of time has passed since it has last been consumed.
replenishmentDelay [1] Time: Amount of time after which the capacity will be replenished after it has last been consumed.
Defintion attributes ☑ requires parent scheduler
☐ passes parameters upwards
☑ has exactly one child
ConstantBandwidthServer Constant Bandwidth Server (CBS): provides a fixed utilization for executing jobs, in which the deadline for execution is independent on the execution time of jobs. First introduced in: Abeni, Luca, and Giorgio Buttazzo. “Integrating multimedia applications in hard real-time systems.” Proceedings 19th IEEE Real-Time Systems Symposium (Cat. No. 98CB36279). IEEE, 1998.
Algorithm parameters capacity [1] Time: The fixed budget that can be used by processes. It will be replenished periodically.
period [1] Time: Amount of time after which the capacity will be replenished.
Defintion attributes ☑ requires parent scheduler
☐ passes parameters upwards
☑ has exactly one child
ConstantBandwidthServerWithCapacitySharing Constant Bandwidth Server (CBS) with capacity sharing (CASH). Consumes residual slack from other servers (work conserving).
Algorithm parameters capacity [1] Time: The fixed budget that can be used by processes. It will be replenished periodically.
period [1] Time: Amount of time after which the capacity will be replenished.
Defintion attributes ☑ requires parent scheduler
☐ passes parameters upwards
☑ has exactly one child
Further information

Details regarding proportionate fair ( Pfair) scheduling and the variants of the PD2 Pfair algorithm can be found in the dissertation “Effcient and Flexible Fair Scheduling of Real-time Tasks on Multiprocessors” by Anand Srinivasan (see dissertation at University of North Carolina at Chapel Hill).

An overview regarding Reservation Servers is given in the lecture “Resource Reservation Servers” by Jan Reineke (see lecture at Saarland University).

Scheduler Association

A hierarchy of schedulers can be specified with intermediate objects of class SchedulerAssociation. If set, the parent scheduler takes the initial decision who is executing. If the child-scheduler is not a grouping of tasks, it can take scheduling decisions if permission is granted by the parent. The association also contains the relevant scheduling parameters for the scheduler in the hierarchical context.

Attribute Description
parent Refers to the parent scheduler
child Derived attribute that is computed based on the containment reference “parentAssociation” from Scheduler to SchedulerAssociation
schedulingParameters See chapter "Scheduling Parameters"

Os Overhead

It is possible to define the overhead that is produced by an operating system. The defined overhead can be assigned to an operating system definition. Each overhead information is defined as a set of instructions that has to be executed when the corresponding OS function is used. The instructions can be either a constant set or a deviation of instructions. It is possible to define the overhead for the ISR category one and two and for a number of operating system API functions.

ISR Overhead

API Overhead

There exists also an overhead for API calls. The following API calls are considered:

OS Data Consistency

The OsDataConsistency class provides a way to configure an automatic data consistency mechanism of an operating system. It is used to cover the following two use cases:

To distinguish the different use cases and to consequently also indicate the workflow progress for achieving data consistency, OsDataConsistencyMode allows to define the general configuration of the data consistency. The following modes are available:

  1. noProtection: data stability and coherency is NOT automatically ensured.
  2. automaticProtection: data stability and coherency HAS TO BE ensured according configuration either via custom protection or via model elements.
    1. customProtection: data stability and coherency IS ensured according configuration but not via model elements.
    2. handeldByModelElements: data stability and coherency IS ensured via model elements.

The DataStability class defines for which sequence of runnables data has to be kept stable. Furthermore, it can be stated whether all data is considered for stability or just those accessed multiple times.

DataStabilityLevel:

The NonAtomicDataCoherency class defines for which sequence of runnables data has to be kept coherent. Like for data stability it can be stated whether all data is considered for coherency or just those accessed multiple times.

Semaphore

With this object, a semaphore or locking mechanism can be described which restricts the access of several processes to one resource at the same time.

Attribute Description
name Name of semaphore (inherited from ReferableBaseObject)
semaphoreType Defines how the semaphore is implemented (see below)
initialValue Initial number of already used/locked resources
maxValue Maximum possible number of available locks/resources
ownership Defines if the lock can only be released by the process that acquired it
priorityCeilingPrototcol Defines if the priority ceiling protocol is activated. If it is activated, a process that accesses the semaphore gets a higher priority as the processes that can also access the same semaphore

The different types of semaphores are summarized in the following table. For the ownership there are two possibilities: true – central (only the process that acquired the lock can release it), false – decentral (any process can release it). The priority ceiling property specifies whether the locking mechanism can be used with the priority ceiling protocol to avoid priority inversion, or not. The waiting behavior specifies how a requesting process is allowed to wait for the lock (during a SemaphoreAccess, see Software Model). The access type specifies how different access types will be interpreted, i.e., spinlocks can only be requested exclusively, since there is only one lock.

Semaphore type Description & Properties
CountingSemaphore This locking mechanism enables multiple processes to concurrently access the semaphore. The number of allowed concurrent accesses is specified by maxValue. Since counting semaphores can be released by processes other than the ones that acquired it, the priority ceiling protocol can not be applied. Additionally, an exclusive access means that the requesting process waits until all counting semaphores are available and will acquire all of them. The next release access will then release all counting semaphores.
value specification initial: 0..N (already locked); range: 0..N
ownership true/false, central/decentral
priority ceiling false
waiting behavior active/passive
access type request, exclusive, release
Resource A resource is similar to a counting semaphore. Multiple concurrent accesses are allowed up to maxValue. However, since ownership is required, only processes that acquired the resource before can release it. The priority ceiling protocol can also be applied if needed. An exclusive access means the same as for counting semaphores, albeit with the ownership restriction.
value specification initial: 0 (all available); range: 0..N
ownership true, central: Process
priority ceiling true/false
waiting behavior active/passive
access type request, exclusive, release
Spinlock Spinlocks can be used like a resource with maxValue =1, however, only active waiting is supported during a request access. Since there is only one spinlock, any request is always exclusive.
value specification initial: 0 (unlocked); range: 0..1
ownership true, central: Process
priority ceiling true/false
waiting behavior active only
access type request = exclusive, release
Mutex Mutexes (MUTual EXclusive lock access) are very similar to spinlocks. As opposed to spinlocks, processes can also passively wait until they are available. Again, requests are always exclusive.
value specification initial: 0 (unlocked); range: 0..1
ownership true, central: Process
priority ceiling true/false
waiting behavior active/passive
access type request = exclusive, release