\subsubsection{Buffer}
\label{buffer}

A \buffer is specified by the following definitions:\\

(1) It is statically defined in an \addressspace.\\

(2) A \buffer has an unique name, size and is hosted by 
a \processor and an \addressspace.\\

(3) It allows to model queued data exchanges 
between \tasks on the same \addressspace.\\

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

$Name$ : It is the unique name of a \buffer.\\

$Cpu_{-}Name$: It corresponds to the name of \processor hosted by a \buffer.\\

$Address_{-}Space_{-}Name$: It corresponds to the name of \addressspace 
hosted by a \buffer.\\

$Queueing_{-}System_{-}Type$: It defines the types of $Queueing_{-}System$.
A $Queueing_{-}System$ model is assigned to each \buffer. This model describes the way buffer
reads and writes operations will be done at simulation time.
This information is also used to apply \buffer feasibility
tests.\\

$Buffer_-Size$: Size of a \buffer.\\

$Buffer\_Initial\_Data\_Size$: Initial data in a \buffer. \\

$Roles$: It is the type of $Buffer_{-}Roles_{-}Table$.\\

$Buffer_{-}Roles_{-}Table$ is a list of $Buffer_{-}Role$.\\



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

(L1) \buffer name must not be empty.\\

(L2) \buffer name must be a valid identifier.\\

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

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

(L5) $Buffer_-Size$ must be greater than 0.\\

(L6) $Buffer\_Initial\_Data\_Size$ must be greater than 0 and less than $Buffer_-Size$. \\

(L7) Two types of \tasks can access to a \buffer: producers and
consumers. \\

(L8) We suppose that a producer/consumer writes/reads a fixed size of 
information to a \buffer. \\

(L9) For each producer or consumer, the size of the information
produced or consumed has to be defined in the $Buffer_{-}Role$.\\

(L10) The time of the read/write operation is also given in the $Buffer_{-}Role$: 
this time is relative to the task capacity (e.g. if task $T_i$ consumes a
message at time $2$, it means that the message will be
removed from the \buffer when $T_i$ runs the $2^{nd}$ unit of
time of its $capacity$).\\


\begin{center}
Annexes
\end{center}

(A1) The types of $Queueing_{-}System$ \cite{kleinrock76}.\\

\indent \indent (A11) $Qs_{-}Pp1$: compliant with P/P/1 queueing 
model \cite{Legrand04}.
There are several producers but only one consumer \task.
Producers and the consumers are independent periodic tasks.
Producers and the consumer are not blocked when they access the \buffer.\\


\indent \indent (A12) $Qs_{-}Mm1$ : compliant with 
the classical M/M/1 queueing system model.
There are several producers but only one consumer task.
Producers are released according to a Markovian law.
The consumer is released on data arrival and its service time is exponential (markovian law too).\\

\indent \indent (A13) $Qs_{-}Md1$ : 
compliant with 
the classical M/D/1 queueing system model.
There are several producers but only one consumer \task.
Producers are released according to a Markovian law.
The consumer is released on data arrival and its service time is deterministic.\\

\indent \indent (A14) $Qs_{-}Mp1$ : compliant with 
the classical M/P/1 queueing system model. \\

\indent \indent (A15) $Qs_{-}Mg1$ : compliant with 
the classical M/G/1 queueing system model. \\

\indent \indent (A16) $Qs_{-}Mms$ : compliant with 
the classical M/M/S queueing system model. \\

\indent \indent (A17) $Qs_{-}Mds$ : compliant with 
the classical M/D/S queueing system model. \\

\indent \indent (A18) $Qs_{-}Mps$ : compliant with 
the classical M/P/S queueing system model. \\

\indent \indent (A19) $Qs_{-}Mgs$ : compliant with 
the classical M/G/S queueing system model. \\

\indent \indent (A110) $Qs_{-}Mm1n$ : compliant with 
the classical M/M/1/N queueing system model. \\

\indent \indent (A111) $Qs_{-}Md1n$ : compliant with 
the classical M/D/1/N queueing system model. \\

\indent \indent (A112) $Qs_{-}Mp1n$ : compliant with 
the classical M/P/1/N queueing system model. \\

\indent \indent (A113) $Qs_{-}Mg1n$ : compliant with 
the classical M/G/1/N queueing system model. \\

\indent \indent (A114) $Qs_{-}Mmsn$ : compliant with 
the classical M/M/S/N queueing system model. \\

\indent \indent (A115) $Qs_{-}Mdsn$ : compliant with 
the classical M/D/S/N queueing system model. \\

\indent \indent (A116) $Qs_{-}Mpsn$ : compliant with 
the classical M/P/S/N queueing system model. \\

\indent \indent (A117) $Qs_{-}Mgsn$ : compliant with 
the classical M/G/S/N queueing system model. \\

(A2) The $Buffer_{-}Roles_{-}Table$ is a list of $Buffer_{-}Role$. 
Each $Buffer_{-}Role$ is characterized by:\\

\indent \indent (A21) $The_{-}Role$ which is the type of $Buffer_{-}Role_{-}Type$.

It describes the behaviour of \task on the \buffer.\\

\indent \indent \indent \indent (A211) $No_{-}Role$: When any role is defined.\\

\indent \indent \indent \indent (A212) $Queuing_{-}Producer$: name of the producer \task.\\

\indent \indent \indent \indent (A213) $Queuing_{-}Consumer$: name of the consumer \task.\\

\indent \indent \indent \indent (A214) $Sampling_{-}Writer$: name of the producer \task.\\

\indent \indent \indent \indent (A215) $Sampling_{-}Reader$: name of the consumer \task.\\

\indent \indent \indent \indent (A216) $UCSDF_{-}Producer$: name of the producer \task whom the production rate is described by an amplitude function (A25)\\

\indent \indent \indent \indent (A217) $UCSDF_{-}Consumer$: name of the consumer \task whom the consumption rate is described by an amplitude function (A25)\\

\indent \indent (A22) $Size$ : size of the data to read/write from/to the \buffer.\\

\indent \indent (A23) $Time$ : time at which the data must be read or write on the \buffer.
This time is relative to the \task capacity\\

\indent \indent (A24) $Timeout$ : specify the maximum blocking time allowed when a read/write is 
proceeded on a \buffer.\\

\indent \indent (A25) $amplitude_{-}function$ : the number of token produced/consumed by a producer/consumer is an ultimately cyclo-static sequence $s=u(v)$ in which $u$ denotes the initialization part and $(v)$ denotes the cyclic part.
The number of produced tokens is depending on the release number of a producer/consumer. 
For an $i^{th}$ release, the number of token produced/consumed is computed as follows:
\begin{equation}
	nb\_token =
	    \begin{cases}
	      u[i] & \mbox{if } i \leq u\\
	      v[(j-|u|) \mod |v|] & \mbox{otherwise}
	    \end{cases} 
\end{equation} 

This property can only be applied to the producers/consumers with the roles UCSDF\_Producer and UCSDF\_Consumer \\

\indent \indent (A26) Buffer Underflow : Underflow event occurs when a task reads from a buffer 
and the read data size is greater than the current data size in the buffer. 
When it happens, a task does not read the buffer and
current data in a buffer is not consumed.\\

\indent \indent (A25) Buffer Overflow : Overflow event occurs when a task writes to a buffer 
and the write data size plus the current data size in the buffer is greater than $Buffer_-Size$.
When it happens, a task does not write any data to the buffer.\\

\begin{center}
Implementation
\end{center}

The figure \ref{dtd_buffer} gives the DTD of entity \buffer.


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

<!ELEMENT buffers (buffer | buffer_role)+>
<!ELEMENT buffer (object_type | name | cpu_name 
  | address_space_name | queueing_system_type | size 
  | roles)*>
<!ATTLIST buffer id ID #REQUIRED>
<!ELEMENT buffer_role (the_role | size | time | timeout 
   | amplitude_function)*>
<!ATTLIST address_space id ID #REQUIRED>

\end{lstlisting}
	\caption{The DTD of entity \buffer}
	\label{dtd_buffer}
\end{figure}




\begin{center}
Example
\end{center}

The figure \ref{example_buffer} gives an example of entity \buffer, 
described using Cheddar ADL.

The considered \buffer, named $B1$ is hosted by the \processor 
$processor1$ and \addressspace $addr1$.


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

<buffers>
<buffer id=" 37" >
 <object_type>BUFFER_OBJECT_TYPE</object_type>
 <name>B1</name>
 <cpu_name>processor1</cpu_name>
 <address_space_name>addr1</address_space_name>
 <queueing_system_type>QS_MM1</queueing_system_type>
 <size>1</size>
 <roles>
 <task_name> T1 </task_name> 
 <buffer_role>
  <the_role>QUEUING_PRODUCER</the_role>
  <size>1</size>
  <time>1</time>
  <timeout>1</timeout>
 </buffer_role>
 <task_name> T2 </task_name> 
 <buffer_role>
  <the_role>QUEUING_CONSUMER</the_role>
  <size>2</size>
  <time>2</time>
  <timeout>2</timeout>
  <amplitude_functio TO BE COMPLETED
 </buffer_role>
 </roles>
</buffer>
</buffers>

\end{lstlisting}
\caption{An example of entity \buffer}
\label{example_buffer}
\end{figure}
