plugins/org.eclipse.app4mc.amalthea.model.help/docu/model_os.textile

h2. 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.

!../pictures/model_os_overview.svg!


h3. 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.
 
!../pictures/model_os_operatingsystem.png!


h3. 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.

!../pictures/model_os_scheduler.svg!

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

table(minimal){padding:10px; border:1px solid black; background:#f8f8f8}. 
|_. Name |_. Description |
| __requiresParentScheduler__ | __boolean__ attribute indicating whether a 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+. |

h4. 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.

h4. 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).

!../pictures/model_os_scheduling_parameters.svg!

h4. 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.

table(classic).
|_. Scheduling Algorithm  |\2_. Description and Parameters |
|\3{background:#e6ffe6;}. Fixed Priority |
|/3. **OSEK** |\2. 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. |
|/2. Process parameters | __priority__ <notextile>[1]</notextile> Integer: The priority of the process (a higher value means a higher priority). |
| __taskGroup__ <notextile>[1]</notextile> Integer: The OSEK task group number (if for two processes the number is equal, that means they are in the same task group). |
|/2. **FixedPriorityPreemptive** |\2. Fixed Priority Preemptive Scheduling (e.g. AUTOSAR), same as OSEK but without task groups. |
| Process parameters | __priority__ <notextile>[1]</notextile> Integer: The priority of the process (a higher value means a higher priority). |
|\3{background:#e6ffe6;}. Dynamic Priority |
|/2. **EarliestDeadlineFirst** |\2. 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__ <notextile>[1]</notextile> Time: The time after each activation at which the process must finish. |
|/3. **PriorityBasedRoundRobin** |\2. 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__ <notextile>[1]</notextile> Time: Length of each time slice. |
| Process parameters | __priority__ <notextile>[1]</notextile> Integer: The priority of the process (a higher value means a higher priority). |
|\3{background:#e6ffe6;}. Proportionate Fair (Pfair) |
|/2. **PfairPD2** |\2. Proportionate Fair PD<notextile><sup>2</sup></notextile> Scheduling (Pfair-PD<notextile><sup>2</sup></notextile>) |
| 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. |
|/2. **PartlyPfairPD2** |\2. Partly Proportionate Fair PD<notextile><sup>2</sup></notextile> Scheduling (PPfair-PD<notextile><sup>2</sup></notextile>) |
| 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. |
|/2. **EarlyReleaseFairPD2** |\2. Early Release Fair PD<notextile><sup>2</sup></notextile> Scheduling (ERfair-PD<notextile><sup>2</sup></notextile>) |
| 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. |
|/2. **PartlyEarlyReleaseFairPD2** |\2. Partly Early Release Fair PD<notextile><sup>2</sup></notextile> Scheduling (P-ERfair-PD<notextile><sup>2</sup></notextile>) |
| 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. |
|\3{background:#e6ffe6;}. Reservation Based Server |
|/4. **GroupingServer** |\2. 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. |
|/2. Algorithm parameters | __capacity__ <notextile>[1]</notextile> Time: The fixed budget that can be used by processes. It will be replenished periodically. |
| __period__ <notextile>[1]</notextile> Time: Amount of time after which the capacity will be replenished. |
| Definition attributes | &#9745; requires parent scheduler <br /> &#9745; passes parameters upwards <br /> &#9744; has exactly one child |
|/4. **DeferrableServer** |\2. 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. |
|/2. Algorithm parameters | __capacity__ <notextile>[1]</notextile> Time: The fixed budget that can be used by processes. It will be replenished periodically. |
| __period__ <notextile>[1]</notextile> Time: Amount of time after which the capacity will be replenished. |
| Defintion attributes | &#9745; requires parent scheduler <br /> &#9744; passes parameters upwards <br /> &#9745; has exactly one child |
|/4. **PollingPeriodicServer** |\2. 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. |
|/2. Algorithm parameters | __capacity__ <notextile>[1]</notextile> 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__ <notextile>[1]</notextile> Time: Amount of time after which the capacity will be replenished. |
| Defintion attributes | &#9745; requires parent scheduler <br /> &#9744; passes parameters upwards <br /> &#9745; has exactly one child |
|/4. **SporadicServer** |\2. 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. |
|/2. Algorithm parameters | __capacity__ <notextile>[1]</notextile> 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__ <notextile>[1]</notextile> Time: Amount of time after which the capacity will be replenished after it has last been consumed. |
| Defintion attributes | &#9745; requires parent scheduler <br /> &#9744; passes parameters upwards <br /> &#9745; has exactly one child |
|/4. **ConstantBandwidthServer** |\2. 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. |
|/2. Algorithm parameters | __capacity__ <notextile>[1]</notextile> Time: The fixed budget that can be used by processes. It will be replenished periodically. |
| __period__ <notextile>[1]</notextile> Time: Amount of time after which the capacity will be replenished. |
| Defintion attributes | &#9745; requires parent scheduler <br /> &#9744; passes parameters upwards <br /> &#9745; has exactly one child |
|/4. **ConstantBandwidthServerWithCapacitySharing** |\2. Constant Bandwidth Server (CBS) with capacity sharing (CASH). Consumes residual slack from other servers (work conserving). |
|/2. Algorithm parameters | __capacity__ <notextile>[1]</notextile> Time: The fixed budget that can be used by processes. It will be replenished periodically. |
| __period__ <notextile>[1]</notextile> Time: Amount of time after which the capacity will be replenished. |
| Defintion attributes | &#9745; requires parent scheduler <br /> &#9744; passes parameters upwards <br /> &#9745; has exactly one child |

h5. Further information

Details regarding proportionate fair (*Pfair*) scheduling and the variants of the *PD<notextile><sup>2</sup></notextile> Pfair* algorithm can be found in the dissertation "Effcient and Flexible Fair Scheduling of Real-time Tasks on Multiprocessors" by Anand Srinivasan (see "dissertation":https://www.cs.unc.edu/~anderson/diss/srinidiss.pdf 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":https://embedded.cs.uni-saarland.de/lectures/realtimesystems/resourceReservationServers.pdf at Saarland University).


h4. 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.

!../pictures/model_os_scheduler_association.svg!

table(classic). 
|_. 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" |


h3. 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.

!../pictures/model_os_osoverhead.png!

h4. ISR Overhead

* ISR category 1 & 2: Describes the overhead for ISRs of category one and two by adding a set of instructions that is executed at start and terminate of the ISR 

h4. API Overhead

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

* API Activate Task: Runtime overhead for the activation of a task or ISR by another task or ISR (inside the activating process)
* API Terminate Task: Runtime for explicit task termination call (inside a task)

* API Schedule: Runtime for task scheduling (on scheduling request)

* API Request Resource: Runtime overhead for requesting a semaphore (inside a runnable)
* API Release Resource: Runtime overhead for releasing a semaphore (inside a runnable)

* API Set Event: Runtime overhead for requesting an OS event (inside a task or ISR)
* API Wait Event: Runtime overhead for waiting for an OS event (inside a task or ISR)
* API Clear Event: Runtime overhead for clearing an OS event (inside a task or ISR)

* API Send Message: Runtime overhead for cross-core process activation or event (inside a task or ISR) 
* API Enforced Migration: Runtime overhead for migrating from one scheduler to another scheduler (inside a task or ISR)
           
* API Suspend OsInterrupts
* API Resume OsInterrupts

* API Request Spinlock
* API Release Spinlock

* API SenderReceiver Read
* API SenderReceiver Write

* API SynchronousServerCallPoint

* API IOC Read
* API IOC Write

h3(#os-data-consistency). 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:
* Provide a configuration for external tools that perform a data consistency calculation based on the stated information.
* Provide the results of a performed data consistency calculation which then have to be considered by external tools (e.g. by timing simulation).

!../pictures/model_os_data_consistency.png!

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:

# noProtection: data stability and coherency is NOT automatically ensured.
# automaticProtection: data stability and coherency HAS TO BE ensured according configuration either via custom protection or via model elements.
## customProtection: data stability and coherency IS ensured according configuration but not via model elements.
## 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:
* __period__			- between consecutive activations
* __process__			- within a Task or ISR
* __scheduleSection__	- between Schedule points (explizit schedule points, begin and end of process)
* __runnable__			- within a Runnable

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.


h3. Semaphore

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

!../pictures/model_os_semaphore.png!

table(classic). 
|_. Attribute  |_. Description |
| __name__ | Name of semaphore (inherited from ReferableBaseObject) |
| __semaphoreType__ | Defines how the semaphore is implemented |
| __initialValue__ | Initial number of processes that access the semaphore |
| __maxValue__ | Maximum number of processes that can concurrently access the semaphore |
| __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 |