\subsubsection{Task}
\label{task}

A task, named $Generic_{-}Task$ is specified by the following definitions:\\

(1) Run any type of program (including any operating system 
function such as a scheduler). \\

(2) Statically defined in an \addressspace.\\


\begin{center}
Standard attributes
\end{center}

$Name$ : It is the unique name of the \task.\\

$Task_{-}Type$: It defines the type of the task.

Annexes (A1) give the different types of task.\\

$Cpu_{-}Name$: It is a string, which defined the \processor where 
is running the \task.\\

$Address_{-}Space_{-}Name$: It is a string, which defines the name of 
the \addressspace hosting the task.\\

$Core_{-}Name$: It is a string, which defined the \core where 
is running the \task. This attribute is restricted to multicore architectures
where tasks to core affinities have to be enforced.\\


$Capacity$: It is a natural, and it corresponds to the worst case execution time of the task.\\

$Deadline$: The \task must end its activation before its deadline. A
deadline is a relative information : to get the absolute date
at which a task must end an activation, you should add to the deadline
the time when the task was awoken/activated. 
The deadline must be equal to the
period if you define a Rate Monotonic scheduler.\\

$Start_{-}Time$: It is a natural, which defines the first release time of a \task.\\

$Completion_{-}Time$: It defines the time at which a cyclic task is completed, i.e. from when the task must not be dispatched. This attribute has 0 as default value. If set with 0, the dispatching rules of the task are not changed.

$Priority$: It is a priority range.

It allows the scheduler to choose the \task to run.\\

$Blocking_{-}Time$: It's the worst case  shared resource waiting time of the task. 
This duration
could be set by the user or computed by
Cheddar  shared resources 
accesses  are described.\\

$Policy$: It defines the scheduling policy of a task. Policy can be
$SCHED_{-}RR$, or $SCHED_{-}FIFO$ or $SCHED_{-}OTHERS$ and
describes how the scheduler chooses a task when several
tasks have the same priority level.\\

$Offsets$: An offset stores two information : an
activation number and a value. It allows to
change the wake up time of a task on a
given activation number. For an activation
number, the task wake up time will be
delayed by the amount of time given by the value field.\\

$Text_{-}Memory_{-}Size$: Size of the text segment of the task in order to perform memory
requirement analysis.\\

$Stack_{-}Memory_{-}Size$: Size of the memory stack of the task in order to perform memory
requirement analysis.\\

$Parameters$: A parameter is similar to the deadline, the period, to
capacity ..., but used by user-defined schedulers. 

A user can define new task parameters. 
A user-defined task scheduled has a value, a name and a type. The types
currently available to define user-defined task
parameters are : string, integer boolean and double.\\

$Criticality$: The field indicates how the task is critical. Currently
used by the \textit{MUF} scheduler or any user-defined
schedulers.\\

$Context_{-}Switch_{-}Overhead$: It is an integer modeling the corst of the 
context swith for the task \\

$maximum_{-}number_{-}of_{-}memory_{-}request_{-}per_{-}job$ : 

$access_{-}memory_{-}number$ : 

$cfg_{-}name$ : 

$cfg_{-}relocatable$ : 

$cache_{-}access_{-}profile_{-}name$ : 
 
$mils_{-}confidentiality_{-}level$ : It defines the level of confidentiality of a task.
 $mils_{-}confidentiality_{-}level$ can be $UnClassified$, or $Classified$,
or $Secret$, or $Top_{-}Secret$ \\

$mils_{-}integrity_{-}level$ : It defines the level of integrity of a 
task. $mils_{-}integrity_{-}level$ can be $Low$, or $Medium$, or $High$ \\

$mils_{-}component$ : It defines the type of a task according to the 
classification of components in mils architecture. It can be SLS for Single 
Level Secure component, or MLS for Multi-Level Secure component, or MSLS for
 Multi Single-Level Secure component.\\

$mils_{-}task$ : It defines a task as a common application or a particular 
element of mils architecture. It can be application, or MMR for MILS Message Router, 
or Guard, or Collator, or Downgrader, or Upgrader \\

$mils_{-}compliant$ : It is a boolean that specifies if a task models a component
 of MILS or not. \\

$Energy_{-}Consumption$ : It is an integer modelling the energy consumption of the task.\\



\begin{center}
Legality rules
\end{center}

(L1) The \task name must not be empty.\\

(L2) The \task name must be valid identifier.\\

(L3) In the case of $Parametric_{-}Type$, The $Activation_{-}Rule$ should be a valid identifier.\\

(L4) The $Cpu_{-}Name$ must not be empty.\\

(L5) The $Address_{-}Space_{-}Name$ must not be empty.\\

(L6) In the case of $Periodic_{-}Type$, the $Period$ must be greater than 0.\\

(L7) In the case of $Periodic_{-}Type$, the $Jitter$ must be greater than or equal to 0.\\

(L8) In the case of $Aperiodic_{-}Type$, the $Period$ shouldn’t exist.\\

(L9) In the case of $Sporadic_{-}Type$, the $Period$ shouldn’t exist.\\

(L10) In the case of $Parametric_{-}Type$, the $Activation_{-}Rule$ must not be empty.\\

(L11) In the case of $Frame_{-}Task_{-}Type$, the $Period$ must be greater than or equal to 0 \\
		
(L12) The $Capacity$ must be greater than 0.\\

(L13) The $Context_{-}Switch_{-}Overhead$ must be greater than or equal to 0.\\

(L14) The $Criticality$ must be greater than or equal to 0.\\

(L15) The $Deadline$ must be greater than or equal to 0.\\

(L16) The $Deadline$ must be less than the $Jitter$.\\

(L17) The $Start_{-}Time$ must be greater than or equal to 0.\\

(L18) The $Blocking_{-}Time$ must be greater than or equal to 0.\\

(L19) The $Text_{-}Memory_{-}Size$ must be greater than or equal to 0.\\

(L20) The $Stack_{-}Memory_{-}Size$ must be greater than or equal to 0.\\

(L21) The $Priority$ must be between $Priority_{-}Range_{-}First$ and $Priority_{-}Range_{-}Last$.\\

(L22) We can't have simultaneously $Priority \ne 0$ $Policy$ = $Sched_{-}Others$.\\

(L23) We can't have simultaneously $Priority = 0$ $Policy \ne Sched_{-}Others$.\\

%(L25) gerer les contraintes sur les offsets  ...\\

\begin{center}
Annexes
\end{center}

(A1) The types of $Generic_{-}Task$.\\

\indent \indent (A11) $Periodic_{-}Type$: In this case, the \task is periodic, 
and we have two more attributes in order to characterize the \task:\\

\indent \indent \indent \indent (A111) $Period$: It is the time between two task activations. 
The period is a
constant delay for a periodic task. It's an average delay
for a \textit{poisson} process task. If you have selected a
\processor that owns a Rate Monotonic or a Deadline
Monotonic scheduler, you have to give a period for each
of its tasks.\\

\indent \indent \indent \indent (A112) $Jitter$: The $Jitter$ of \task 
is an upper bound on the delay that
\task may suffer between the time it is supposed to be released and the
time that it is actually released.

The jitter is a maximum lateness on the task wake up
time. This information can be used to express task
precedencies and to applied method such as the Holistic
task response time method.\\

\indent \indent (A12) $Aperiodic_{-}Type$ In this case, the \task is called aperiodic task.

An aperiodic task is only activated once.\\

\indent \indent (A13) $Sporadic_{-}Type$: A sporadic task is a task which is activated 
many times with a minimal delay between two successive activations. 

If the \task type is $user_-defined$, the task activation delay is defined by the user.\\

\indent \indent (A14) $Poisson_{-}Type$. In this case, 
the task is called \textit{poisson} task. 

It is a subtype of \textit{Periodic} task, with two more attributes.\\

\indent \indent \indent \indent (A141) $Seed$: If you define a \textit{poisson} 
process task or a user-defined
task, you can set here how random activation delay
should be generated (in a deterministic way or not). The
\textit{Seed} button proposes you a randomly generated seed
value but of course, you can give any seed value. This
seed value is used only if the Predictable button is
pushed. If the Unpredictable button is pushed instead,
the seed is initialized at simulation time with \textit{gettimeofday}.\\

\indent \indent \indent \indent (A142) $Predictable$: It is a boolean, which guides 
the \textit{seed} value (see the $Seed$ definition).\\

\indent \indent (A15) $Parametric_{-}Type$. In this case, the task is called 
parametric task, and it is characterized by one more attribute.\\  

\indent \indent \indent \indent (A151) $Activation_{-}Rule$: The name of the rule 
which defines the way the task
should be activated. Only used with user-defined task.\\

\indent \indent (A16) $Scheduling_{-}Task_{-}Type$: It is one of the types of \task.\\

\indent \indent (A17) $Frame_{-}Task_{-}Type$. In this case, the task type is called frame task, 
and it is characterized by one more attribute.\\

\indent \indent \indent \indent (A171) $Interarrival$: It defines the duration 
between the release of two tasks. It is specified through the $Period$ attribute.\\


\indent \indent (A18) $Periodic_{-}Inner_{-}Periodic_{-}Type$. In this case, the task type
is  Periodic inner periodic task model. Such model of task allows the modelling of burst
of activation. A burst is composed of several periodic releases. For those inner periodic
release, the $Period$ attribute is used. The tasks is inactive between two bursts. 
Timing behavior is expressed will the following attributes.\\

\indent \indent \indent \indent  (A181)  
$Outer{-}Period$ : It is an integer which specifies the number of periodic activitation in a 
burst.\\

\indent \indent \indent \indent  (A182)  
$Outer_{-}Duration$ : It is an integer which specifies the delay between two bursts.\\



\indent \indent (A19) $Sporadic_{-}Inner{-}_Periodic_{-}Type$. In this case, the task is
 type is Sporadic inner periodic. uch model of task allows the modelling of burst
of activation. A burst is composed of several periodic releases. For those inner periodic
release, the $Period$ attribute is used. The tasks is inactive between two bursts. 
Delays between burst are expressed with  $Outer_{-}Duration$ and
$Outer{-}Period$ excepts that $Outer{-}Period$ is not a fixed amount of time but a random
delay computed according to a poisson process with $Outer{-}Period$ as average delay.\\


(A2) The types of $Policies$ \cite{McCormick11}.\\

\indent \indent (A21) $Sched_{-}Fifo$: With this policy, ready processes in a 
given priority
level get the $Processor$ according to their order in the FIFO queue.

The process at the head of the queue runs first and keeps the processor until it
executes some statement that blocks it, explicitly releases the processor,
or finishes.\\

\indent \indent (A22) $Sched_{-}Rr$: It can be seen as a 
$Sched_{-}Fifo$ policy but with a time quantum 
and some extra rules on the queue management.

When the quantum is exhausted, the preempted thread is moved 
to the tail of the queue.\\

\indent \indent (A23) $Sched_{-}Others$: The behaviour of this policy is not 
defined in the POSIX
standard. It is implementation defined. 

Sometimes, this policy provides a time sharing scheduler. 


This policy is used by Linux for all processes
with a priority level of 0. These processes are put in a $Sched_{-}Others$
queue. 


With Linux, the process in the $Sched_{-}Others$ queue that has waited
longest for the processor is dispatched first.\\

\begin{center}
Implementation
\end{center}

The figure \ref{dtd_task} gives the DTD of entity \task.


\begin{figure}{}
\begin{lstlisting}{}

<!ELEMENT tasks (generic_task | periodic_task | aperiodic_task 
  | poisson_task | sporadic_task | parametric_task 
  | scheduling_task | frame_task)+>
<!ELEMENT generic_task (object_type | name | task_type 
  | cpu_name | address_space_name | capacity | deadline 
  | start_time | priority | blocking_time | policy 
  | offsets | text_memory_size | stack_memory_size
  | parameters | criticality | context_switch_overhead
  | mils_confidentiality_level | mils_integrity_level 
  | mils_component | mils_task | mils_compliant)*>
<!ATTLIST generic_task id ID #REQUIRED>
<!ELEMENT periodic_task (object_type | name | task_type 
  | cpu_name | address_space_name | capacity | deadline 
  | start_time | priority | blocking_time | policy | offsets 
  | text_memory_size | stack_memory_size | parameters 
  | criticality | context_switch_overhead | mils_confidentiality_level 
  | mils_integrity_level | mils_component | mils_task | mils_compliant
  | period | jitter)*>
<!ATTLIST periodic_task id ID #REQUIRED>
<!ELEMENT aperiodic_task (object_type | name | task_type
  | cpu_name | address_space_name | capacity | deadline
  | start_time | priority | blocking_time | policy | offsets
  | text_memory_size | stack_memory_size | parameters 
  | criticality | context_switch_overhead
  | mils_confidentiality_level | mils_integrity_level 
  | mils_component | mils_task | mils_compliant)*>
<!ATTLIST aperiodic_task id ID #REQUIRED>
<!ELEMENT poisson_task (object_type | name | task_type 
  | cpu_name | address_space_name | capacity | deadline 
  | start_time | priority | blocking_time | policy | offsets 
  | text_memory_size | stack_memory_size | parameters 
  | criticality | context_switch_overhead | mils_confidentiality_level 
  | mils_integrity_level | mils_component | mils_task | mils_compliant
  | period | jitter | seed | predictable )*>
<!ATTLIST poisson_task id ID #REQUIRED>
<!ELEMENT sporadic_task (object_type | name | task_type 
  | cpu_name | address_space_name | capacity | deadline 
  | start_time | priority | blocking_time | policy | offsets 
  | text_memory_size | stack_memory_size | parameters 
  | criticality | context_switch_overhead |  mils_confidentiality_level 
  | mils_integrity_level | mils_component | mils_task | mils_compliant 
  | period | jitter | seed | predictable)*>
<!ATTLIST sporadic_task id ID #REQUIRED>
<!ELEMENT parametric_task (object_type | name | task_type
  | cpu_name | address_space_name | capacity | deadline
  | start_time | priority | blocking_time | policy | offsets
  | text_memory_size | stack_memory_size | parameters
  | criticality | context_switch_overhead |  mils_confidentiality_level
  | mils_integrity_level | mils_component | mils_task | mils_compliant 
  | period | jitter | seed | predictable | activation_rule)*>
<!ATTLIST parametric_task id ID #REQUIRED>
<!ELEMENT scheduling_task (object_type | name | task_type
  | cpu_name | address_space_name | capacity | deadline
  | start_time | priority | blocking_time | policy | offsets
  | text_memory_size | stack_memory_size | parameters
  | criticality | context_switch_overhead | mils_confidentiality_level 
  | mils_integrity_level | mils_component | mils_task | mils_compliant 
  | period | jitter | seed | predictable )*>
<!ATTLIST scheduling_task id ID #REQUIRED>
<!ELEMENT frame_task (object_type | name | task_type
  | cpu_name | address_space_name | capacity | deadline
  | start_time | priority | blocking_time | policy | offsets
  | text_memory_size | stack_memory_size | parameters
  | criticality | context_switch_overhead 
  | mils_confidentiality_level | mils_integrity_level 
  | mils_component | mils_task | mils_compliant | period
  | jitter | interarrival)*>
<!ATTLIST frame_task id ID #REQUIRED>

\end{lstlisting}
\caption{The DTD of entity $Task$}
\label{dtd_task}
\end{figure}


\begin{center}
Example
\end{center}

We give at figure \ref{Task_example} an example of \task described in 
Cheddar ADL.

This task is $periodic$ ($task_{-}type$ is 
$PERIODIC_{-}TYPE$), and its $period$ ($4$) is specified by attribute $period$. 
We can remark another informations, like by example the task runs on $processor1$, 
and $addr1$ is $Address_{-}space$ dedicated for its execution.


\begin{figure}{}
\begin{lstlisting}{}

<periodic_task id=" 71">
      <object_type>TASK_OBJECT_TYPE</object_type>
      <name>T1</name>
      <task_type>PERIODIC_TYPE</task_type>
      <cpu_name>processor1</cpu_name>
      <address_space_name>addr1</address_space_name>
      <capacity>2</capacity>
      <deadline>4</deadline>
      <start_time>0</start_time>
      <priority>1</priority>
      <blocking_time>10</blocking_time>
      <policy>SCHED_FIFO</policy>
      <text_memory_size>0</text_memory_size>
      <stack_memory_size>0</stack_memory_size>
      <criticality>0</criticality>
      <context_switch_overhead>0</context_switch_overhead>
      <context_switch_overhead>0</context_switch_overhead>
      <mils_confidentiality_level>Top_Secret</mils_confidentiality_level>
      <mils_integrity_level>HIGH</mils_integrity_level>
      <mils_component>SLS</mils_component>
      <mils_task>APPLICATION</mils_task>
      <mils_compliant>TRUE</mils_compliant>
      <period>4</period>
      <jitter>0</jitter>
</periodic_task>

\end{lstlisting}
\caption{An example of $Task$ description in Cheddar ADL}
\label{Task_example}
\end{figure}
