WebSVN - shark - Blame - Rev 1677 - /sharkdoc/trunk/vol3/vol3.tex

Rev	Author	Line No.	Line
1676	tullio	1	\documentclass[english]{report}
		2	\usepackage[T1]{fontenc}
		3	\usepackage[latin1]{inputenc}
		4	\usepackage{geometry}
		5	\geometry{verbose,a4paper}
		6	\usepackage{array}
		7	\usepackage{makeidx}
		8	\makeindex
		9	\usepackage{graphicx}
		10
		11	\makeatletter
		12
		13	\usepackage{babel}
		14
		15	\newenvironment{intest}{\noindent\large\bf\hspace*{1pt}}
		16	{\vspace*{-5pt}\\\line(1,0){433}}
		17
		18	\makeatother
		19
		20	\begin{document}
		21
		22	\thispagestyle{empty}
		23
		24	\begin{center}{\LARGE S.Ha.R.K. User Manual}\end{center}{\LARGE \par} \vfill{}
		25
		26	\begin{center}{\large Volume III}\end{center}
		27
		28	\begin{center}
		29	S.Ha.R.K. Modules
		30	\end{center}
		31	\vfill{}
		32
		33	\begin{center}Written by\end{center}
		34
		35	\begin{center}Giorgio Buttazzo (giorgio at sssup.it)\end{center}
		36	\begin{center}Paolo Gai (pj at sssup.it)\end{center}
		37	\begin{center}Luigi Palopoli (luigi at hartik.sssup.it)\end{center}
		38	\begin{center}Marco Caccamo (caccamo at sssup.it)\end{center}
		39	\begin{center}Giuseppe Lipari (lipari at sssup.it) \end{center}
		40	\begin{center}Tullio Facchinetti (tullio.facchinetti at unipv.it) \end{center}
		41	\vfill{}
		42
		43	\begin{center}\includegraphics[width=2cm]{../common/sssup.ps}\end{center}
		44
		45	\begin{center}
		46	Scuola Superiore di Studi e Perfezionamento S. Anna
		47	\end{center}
		48
		49	\begin{center}RETIS Lab\end{center}
		50	\begin{center}Via Carducci, 40 - 56100 Pisa\end{center}
		51	\pagebreak
		52
		53	\tableofcontents{}
		54
		55	\begin{abstract}
		56	The S.Ha.R.K. kernel provides a way to implement in a simple
		57	way a lot of scheduling algorithms that have been proposed by the
		58	Real-Time literature. This Volume simply contains a simple
		59	description on which modules are available and how these modules
		60	can be used. Moreover, to help the implementation of new modules,
		61	a small description of the tricks used in the implementation is
		62	also given.
		63	\end{abstract}
		64
		65	%----------------------------------------------------------------------------
		66	\chapter{Models}
		67	%----------------------------------------------------------------------------
		68
		69	Task Models and Resource Models are the structures used by the
		70	S.Ha.R.K. Kernel to isolate the scheduling parameter needed by the
		71	various Scheduling Modules and Resource Modules.
		72
		73	To simplify the use of the Models, the Kernel provides a set of
		74	macros that can be used to fill their various fields. In the
		75	following paragraphs, the various models are described in detail.
		76	All the Model definitions of this chapter can be found in the file
		77	\texttt{include/kernel/model.h}.
		78
		79	Examples of Models initializations can be found in various
		80	examples through this Volume.
		81
		82	%----------------------------------------------------------------------------
		83	\section{HARD\_TASK\_MODEL}
		84	%----------------------------------------------------------------------------
		85
		86	\begin{tt}
		87	\begin{verbatim}
		88	typedef struct {
		89	TASK_MODEL t;
		90	TIME mit;
		91	TIME drel;
		92	TIME wcet;
		93	int periodicity;
		94	} HARD_TASK_MODEL;
		95	\end{verbatim}
		96	\end{tt}
		97
		98	A Hard Task model can be used to model periodic and sporadic
		99	tasks. These tasks are usually guaranteed basing on their minimum
		100	interarrival time (mit) and wcet, and may have a relative
		101	deadline.
		102
		103	Table \ref{tab:HARD_TASK_MODEL_Macros} shows the macros that
		104	applies to a \texttt{HARD\_TASK\_MODEL}.
		105
		106	\begin{table}
		107	\begin{tabular}{\|l\|p{8cm}\|}
		108	\hline Macro name & Behaviour \\ \hline
		109
		110	hard\_task\_default\_model(m) & Default values for the Model
		111	(periodic task, others = 0) \\ \hline
		112
		113	hard\_task\_def\_level(m,l) & Set the Model level to l. A Module
		114	registered at level x can accept a Model only if it has level 0 or
		115	x. The default value is 0. \\ \hline
		116
		117	hard\_task\_def\_arg(m,a) & Set the void * argument passed to
		118	the task the first time it is activated. The default value is
		119	NULL.\\ \hline
		120
		121	hard\_task\_def\_stack(m,s) & Set the task stack size. The default
		122	value is 4096.\\ \hline
		123
		124	hard\_task\_def\_stackaddr(m,s) & If the stack is statically
		125	allocated you can tell its address here. The default is NULL (no
		126	pre-allocated stack).\\ \hline
		127
		128	hard\_task\_def\_group(m,g) & Set the task group to g. Task
		129	grouping influences primitives like group\_activate() or
		130	group\_kill()\\ \hline
		131
		132	hard\_task\_def\_usemath(m) & Declare that the task uses floating
		133	point arithmetic.\\ \hline
		134
		135	hard\_task\_def\_system(m) & Declare that the task is a system
		136	task. System tasks behaves differently at shutdown. See the
		137	Architecture manual for details.\\ \hline
		138
		139	hard\_task\_def\_nokill(m) & Declare that the task can not be
		140	killed. These tasks behaves differently at shutdown. See the
		141	Architecture manual for details.\\ \hline
		142
		143	hard\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
		144	JET informations for the task.\\ \hline
		145
		146	hard\_task\_def\_mit(m,p) & Set the Minimum Interarrival Time
		147	(MIT) of the Model to p.\\ \hline
		148
		149	hard\_task\_def\_drel(m,d) & Set the relative deadline to
		150	d.\\ \hline
		151
		152	hard\_task\_def\_wcet(m,w) & Set the Worst Case Execution Time to
		153	w.\\ \hline
		154
		155	hard\_task\_def\_periodic(m) & Declare that the task is
		156	Periodic.\\ \hline
		157
		158	hard\_task\_def\_aperiodic(m) & Declare that the task is Sporadic
		159	(Aperiodic).\\ \hline
		160
		161	hard\_task\_def\_joinable(m) & Declare that the task is joinable
		162	with task\_join()/pthread\_join().\\ \hline
		163
		164	hard\_task\_def\_unjoinable(m) & Declare that the task is not
		165	joinable (is detached) with
		166	task\_join()/pthread\_join().\\ \hline
		167
		168	hard\_task\_def\_trace(m) & Declare that the task has to be traced
		169	by the Tracer.\\ \hline
		170
		171	hard\_task\_def\_notrace(m) & Declare that the task has not to be
		172	traced by the Tracer.\\ \hline
		173	\end{tabular}
		174	\caption{HARD\_TASK\_MODEL Macros}
		175	\label{tab:HARD_TASK_MODEL_Macros}
		176	\end{table}
		177
		178	%----------------------------------------------------------------------------
		179	\section{SOFT\_TASK\_MODEL}
		180	%----------------------------------------------------------------------------
		181
		182	\begin{tt}
		183	\begin{verbatim}
		184	typedef struct {
		185	TASK_MODEL t;
		186	TIME period;
		187	TIME met;
		188	TIME wcet;
		189	int periodicity;
		190	int arrivals;
		191	} SOFT_TASK_MODEL;
		192	\end{verbatim}
		193	\end{tt}
		194
		195	A Soft Task model can be used to model periodic and aperiodic
		196	tasks usually not guaranteed or guaranteed basing on their period
		197	and mean execution time (met). A Soft task can also record pending
		198	activations if the arrivals are set to SAVE\_ACTIVATIONS. A wcet
		199	field is also present for those servers that need it (i.e., TBS).
		200
		201	Table \ref{tab:SOFT_TASK_MODEL_Macros} shows the macros that
		202	applies to a \texttt{SOFT\_TASK\_MODEL}.
		203
		204	\begin{table}
		205	\begin{tabular}{\|l\|p{8cm}\|}
		206	\hline Macro name & Behaviour\\ \hline
		207
		208	soft\_task\_default\_model(m) & Default values for the Model
		209	(periodic task, save arrivals, others = 0).\\ \hline
		210
		211	soft\_task\_def\_level(m,l) & Set the Model level to l. A Module
		212	registered at level x can accept a Model only if it has level 0 or
		213	x. The default value is 0.\\ \hline
		214
		215	soft\_task\_def\_arg(m,a) & Set the void * argument passed to
		216	the task the first time it is activated. The default value is
		217	NULL.\\ \hline
		218
		219	soft\_task\_def\_stack(m,s) & Set the task stack size. The default
		220	value is 4096.\\ \hline
		221
		222	soft\_task\_def\_stackaddr(m,s) & If the stack is statically
		223	allocated you can tell its address here. The default is NULL (no
		224	pre-allocated stack).\\ \hline
		225
		226	soft\_task\_def\_group(m,g) & Set the task group to g. Task
		227	grouping influences primitives like group\_activate() or
		228	group\_kill()\\ \hline
		229
		230	soft\_task\_def\_usemath(m) & Declare that the task uses floating
		231	point arithmetic.\\ \hline
		232
		233	soft\_task\_def\_system(m) & Declare that the task is a system
		234	task. System tasks behaves differently at shutdown. See the
		235	Architecture manual for details.\\ \hline
		236
		237	soft\_task\_def\_nokill(m) & Declare that the task can not be
		238	killed. These tasks behaves differently at shutdown. See the
		239	Architecture manual for details.\\ \hline
		240
		241	soft\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
		242	JET informations for the task.\\ \hline
		243
		244	soft\_task\_def\_period(m,p) & Set the task period to
		245	p.\\ \hline
		246
		247	soft\_task\_def\_met(m,d) & Set the task Mean Execution Time (MET)
		248	to d.\\ \hline
		249
		250	soft\_task\_def\_wcet(m,w) & Set the Worst Case Execution Time to
		251	w.\\ \hline
		252
		253	soft\_task\_def\_periodic(m) & Declare that the task is
		254	Periodic.\\ \hline
		255
		256	soft\_task\_def\_aperiodic(m) & Declare that the task is Sporadic
		257	(Aperiodic).\\ \hline
		258
		259	soft\_task\_def\_joinable(m) & Declare that the task is joinable
		260	with task\_join()/pthread\_join().\\ \hline
		261
		262	soft\_task\_def\_unjoinable(m) & Declare that the task is not
		263	joinable (is detached) with
		264	task\_join()/pthread\_join().\\ \hline
		265
		266	soft\_task\_def\_trace(m) & Declare that the task has to be traced
		267	by the Tracer.\\ \hline
		268
		269	soft\_task\_def\_notrace(m) & Declare that the task has not to be
		270	traced by the Tracer.\\ \hline
		271
		272	soft\_task\_def\_save\_arrivals(m) & The task will save a pending
		273	activation if it arrives when the task is already
		274	active.\\ \hline
		275
		276	soft\_task\_def\_skip\_arrivals(m) & The task will ignore a
		277	pending activation if it arrives when the task is already
		278	active.\\ \hline
		279	\end{tabular}
		280	\caption{SOFT\_TASK\_MODEL Macros}
		281	\label{tab:SOFT_TASK_MODEL_Macros}
		282	\end{table}
		283
		284	\pagebreak
		285
		286	%----------------------------------------------------------------------------
		287	\section{NRT\_TASK\_MODEL}
		288	%----------------------------------------------------------------------------
		289
		290	\begin{tt}
		291	\begin{verbatim}
		292	typedef struct {
		293	TASK_MODEL t;
		294	int weight;
		295	TIME slice;
		296	int arrivals;
		297	int policy;
		298	int inherit;
		299	} NRT_TASK_MODEL;
		300	\end{verbatim}
		301	\end{tt}
		302
		303	A NRT task has a weight and a time slice, plus a policy attribute.
		304	It can be used to model Round Robin, Proportional Share, POSIX,
		305	and Priority tasks.
		306
		307	Note that policy and inherit are inserted in the model to support
		308	POSIX compliant scheduling without adding another Task Model;
		309	weight can be used to contain the fixed priority of a task; slice
		310	can be used to contain the RR slice of the task.
		311
		312	Table \ref{tab:NRT_TASK_MODEL_Macros} shows the macros that
		313	applies to a \texttt{NRT\_TASK\_MODEL}.
		314
		315	\begin{table}
		316	\begin{tabular}{\|c\|p{8cm}\|}
		317	\hline Macro name & Behaviour\\ \hline
		318
		319	nrt\_task\_default\_model(m) & Default values for the Model (save
		320	arrivals, NRT\_RR\_POLICY, NRT\_EXPLICIT\_SCHED, others =
		321	0).\\ \hline
		322
		323	nrt\_task\_def\_level(m,l) & Set the Model level to l. A Module
		324	registered at level x can accept a Model only if it has level 0 or
		325	x. The default value is 0.\\ \hline
		326
		327	nrt\_task\_def\_arg(m,a) & Set the void * argument passed to the
		328	task the first time it is activated. The default value is
		329	NULL.\\ \hline
		330
		331	nrt\_task\_def\_stack(m,s) & Set the task stack size. The default
		332	value is 4096.\\ \hline
		333
		334	nrt\_task\_def\_stackaddr(m,s) & If the stack is statically
		335	allocated you can tell its address here. The default is NULL (no
		336	pre-allocated stack).\\ \hline
		337
		338	nrt\_task\_def\_group(m,g) & Set the task group to g. Task
		339	grouping influences primitives like group\_activate() or
		340	group\_kill()\\ \hline
		341
		342	nrt\_task\_def\_usemath(m) & Declare that the task uses floating
		343	point arithmetic.\\ \hline
		344
		345	nrt\_task\_def\_system(m) & Declare that the task is a system
		346	task. System tasks behaves differently at shutdown. See the
		347	Architecture manual for details.\\ \hline
		348
		349	nrt\_task\_def\_nokill(m) & Declare that the task can not be
		350	killed. These tasks behaves differently at shutdown. See the
		351	Architecture manual for details.\\ \hline
		352
		353	nrt\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
		354	JET informations for the task.\\ \hline
		355
		356	nrt\_task\_def\_weight(m,w) & Set the task weight to
		357	w.\\ \hline
		358
		359	nrt\_task\_def\_slice(m,d) & Set the timeslice to
		360	d.\\ \hline
		361
		362	nrt\_task\_def\_policy(m,p) & Set the policy of the task. p can be
		363	NRT\_RR\_POLICY or NRT\_FIFO\_POLICY. (used for POSIX
		364	scheduling)\\ \hline
		365
		366	nrt\_task\_def\_inherit(m,i) & Tell if the task should inherit the
		367	same properties of the father. i can be NRT\_INHERIT\_SCHED or
		368	NRT\_EXPLICIT\_SCHED. (used for POSIX scheduling)\\
		369	\hline
		370
		371	nrt\_task\_def\_joinable(m) & Declare that the task is joinable
		372	with task\_join()/pthread\_join().\\ \hline
		373
		374	nrt\_task\_def\_unjoinable(m) & Declare that the task is not
		375	joinable (is detached) with
		376	task\_join()/pthread\_join().\\ \hline
		377
		378	nrt\_task\_def\_trace(m) & Declare that the task has to be traced
		379	by the Tracer.\\ \hline
		380
		381	nrt\_task\_def\_notrace(m) & Declare that the task has not to be
		382	traced by the Tracer.\\ \hline
		383
		384	nrt\_task\_def\_save\_arrivals(m) & The task will save a pending
		385	activation if it arrives when the task is already
		386	active.\\ \hline
		387
		388	nrt\_task\_def\_skip\_arrivals(m) & The task will ignore a pending
		389	activation if it arrives when the task is already
		390	active.\\ \hline
		391	\end{tabular}
		392	\caption{NRT\_TASK\_MODEL Macros}
		393	\label{tab:NRT_TASK_MODEL_Macros}
		394	\end{table}
		395
		396	%----------------------------------------------------------------------------
		397	\section{JOB\_TASK\_MODEL}
		398	%----------------------------------------------------------------------------
		399
		400	\begin{tt}
		401	\begin{verbatim}
		402	typedef struct {
		403	TASK_MODEL t;
		404	TIME period;
		405	struct timespec deadline;
		406	int noraiseexc;
		407	} JOB_TASK_MODEL;
		408	\end{verbatim}
		409	\end{tt}
		410
		411	This model implements a Job with an optional period and a starting
		412	deadline (for the first activation). A Job task can raise a
		413	XDEADLINE\_MISS exception; if the flag noraiseexc is != 0, the
		414	exception is not raised.
		415
		416	This model is normally used with aperiodic servers: the aperiodic
		417	server insert a guest task in another level with that model
		418	calling \texttt{guest\_create} and \texttt{guest\_activate}. When
		419	the task has to be removed, \texttt{guest\_end} is called.
		420
		421	Note that there is no capacity control on this model. Note that
		422	the task that accept this task DOESN'T reactivate the task after a
		423	period... There is NOT a guest\_endcycle defined for this model...
		424
		425	Table \ref{tab:JOB_TASK_MODEL_Macros} shows the macros that
		426	applies to a \texttt{JOB\_TASK\_MODEL}.
		427
		428	\begin{table}
		429	\begin{tabular}{\|l\|p{8cm}\|}
		430	\hline Macro name& Behaviour\\ \hline
		431
		432	job\_task\_default\_model(m,dl) & Default values for the Model
		433	(period = 0, deadline = dl, noraiseexc = 0)\\ \hline
		434
		435	job\_task\_def\_level(m,l) & Set the Model level to l. A Module
		436	registered at level x can accept a Model only if it has level 0 or
		437	x. The default value is 0.\\ \hline
		438
		439	job\_task\_def\_arg(m,a) & Set the void * argument passed to the
		440	task the first time it is activated. The default value is
		441	NULL.\\ \hline
		442
		443	job\_task\_def\_stack(m,s) & Set the task stack size. The default
		444	value is 4096.\\ \hline
		445
		446	job\_task\_def\_stackaddr(m,s) & If the stack is statically
		447	allocated you can tell its address here. The default is NULL (no
		448	pre-allocated stack).\\ \hline
		449
		450	job\_task\_def\_group(m,g) & Set the task group to g. Task
		451	grouping influences primitives like group\_activate() or
		452	group\_kill()\\ \hline
		453
		454	job\_task\_def\_usemath(m) & Declare that the task uses floating
		455	point arithmetic.\\ \hline
		456
		457	job\_task\_def\_system(m) & Declare that the task is a system
		458	task. System tasks behaves differently at shutdown. See the
		459	Architecture manual for details.\\ \hline
		460
		461	job\_task\_def\_nokill(m) & Declare that the task can not be
		462	killed. These tasks behaves differently at shutdown. See the
		463	Architecture manual for details.\\ \hline
		464
		465	job\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
		466	JET informations for the task.\\ \hline
		467
		468	job\_task\_def\_period(m,p) & Set the period to p.\\ \hline
		469
		470	job\_task\_def\_deadline(m,dl) & Set the deadline to
		471	dl.\\ \hline
		472
		473	job\_task\_def\_noexc(m) & Set noraiseexc = 1.\\ \hline
		474
		475	job\_task\_def\_yesexc(m) & Set noraiseexc = 1.\\ \hline
		476
		477	job\_task\_def\_joinable(m) & Declare that the task is joinable
		478	with task\_join()/pthread\_join().\\ \hline
		479
		480	job\_task\_def\_unjoinable(m) & Declare that the task is not joinable (is
		481	detached) with task\_join()/pthread\_join().\\ \hline
		482
		483	job\_task\_def\_trace(m) & Declare that the task has to be traced
		484	by the Tracer.\\ \hline
		485
		486	job\_task\_def\_notrace(m) & Declare that the task has not to be
		487	traced by the Tracer.\\ \hline
		488	\end{tabular}
		489	\caption{HARD\_TASK\_MODEL Macros}
		490	\label{tab:JOB_TASK_MODEL_Macros}
		491	\end{table}
		492
		493	%----------------------------------------------------------------------------
		494	\section{BDEDF\_RES\_MODEL (BlockDevice EDF resource model)}
		495	%----------------------------------------------------------------------------
		496
		497	TBD
		498
		499	%----------------------------------------------------------------------------
		500	\section{BDPSCAN\_RES\_MODEL (Block Device PSCAN resource model)}
		501	%----------------------------------------------------------------------------
		502
		503	TBD
		504
		505	%----------------------------------------------------------------------------
		506	\section{PC\_RES\_MODEL (Priority Ceiling Resource Model)}
		507	%----------------------------------------------------------------------------
		508
		509	\begin{tt}
		510	\begin{verbatim}
		511	typedef struct {
		512	RES_MODEL r;
		513	DWORD priority;
		514	} PC_RES_MODEL;
		515	\end{verbatim}
		516	\end{tt}
		517
		518	This Resource Model signal to the Priority Ceiling (PC) Module
		519	that the task may use the PC protocol for some mutexes.
		520
		521	Note that the PC Module consider the tasks created without using
		522	this resource models to have priority = MAX\_DWORD (the lowest).
		523
		524	The macro that can be used to setup the Resource Model are the
		525	following:
		526
		527	\texttt{PC\_res\_default\_model(res, prio) }
		528
		529	Initializes a PC\_RES\_MODEL with a priority equal to prio.
		530
		531	\texttt{PC\_res\_def\_level(res,l)}
		532
		533	Set the Model level to l (in a way similar to what happens to task
		534	models).
		535
		536	%----------------------------------------------------------------------------
		537	\section{SRP\_RES\_MODEL (Stack Resource Policy resource model)}
		538	%----------------------------------------------------------------------------
		539
		540	\begin{tt}
		541	\begin{verbatim}
		542	typedef struct {
		543	RES_MODEL r;
		544	DWORD preempt;
		545	} SRP_RES_MODEL;
		546	\end{verbatim}
		547	\end{tt}
		548
		549	This Resource Model signal to the Stack Resource Policy (PC)
		550	Module that the task will use the SRP protocol.
		551
		552	Note that the SRP Module does not influence the schedule of any
		553	task that did not pass a SRP\_RES\_MODEL at its creation. The SRP
		554	Module uses another resource model that is embedded into the mutex
		555	structure. See \texttt{modules/srp/srp.c} for details.
		556
		557	The macro that can be used to setup the Resource Model are the
		558	following:
		559
		560	\texttt{SRP\_res\_default\_model(res, pre) }
		561
		562	Initializes a SRP\_RES\_MODEL with a preemption level equal to
		563	prio.
		564
		565	\texttt{SRP\_res\_def\_level(res,l)}
		566
		567	Set the Model level to l (in a way similar to what happens to task
		568	models).
		569
		570	%----------------------------------------------------------------------------
		571	\chapter{Mutex attributes}
		572	%----------------------------------------------------------------------------
		573
		574	Every mutex attribute encode a particular mutex protocol, and one
		575	of them must be passed to the mutex\_init() primitive to specify
		576	the protocol used by a particular mutex. The following paragraphs
		577	describe in detail the mutex attributes. Their definitions can be
		578	found in \texttt{include/kernel/model.h}. Examples of use of mutex
		579	attributes can be found later in this document.
		580
		581	%----------------------------------------------------------------------------
		582	\section{PI\_mutexattr\_t (Priority Inheritance Mutex Attribute)}
		583	%----------------------------------------------------------------------------
		584
		585	\texttt{typedef mutexattr\_t PI\_mutexattr\_t;}
		586
		587	The Priority Ceiling Mutex Attribute.
		588
		589	You can initialize that attribute using the static initializer
		590	\texttt{PI\_MUTEXATTR\_INITIALIZER} or calling the macro
		591
		592	\texttt{PI\_mutexattr\_default(a)}
		593
		594	where a is the mutex attribute.
		595
		596	%----------------------------------------------------------------------------
		597	\section{NPP\_mutexattr\_t (Non Preemptive Protocol Mutex Attribute)}
		598	%----------------------------------------------------------------------------
		599
		600	\texttt{typedef mutexattr\_t NPP\_mutexattr\_t;}
		601
		602	The Non Preemptive Protocol Mutex Attribute. You can initialize
		603	that attribute using the static initializer
		604	\texttt{NPP\_MUTEXATTR\_INITIALIZER} or calling the macro
		605
		606	\texttt{NPP\_mutexattr\_default(a)}
		607
		608	where a is the mutex attribute.
		609
		610	%----------------------------------------------------------------------------
		611	\section{PC\_mutexattr\_t (Priority Ceiling Mutex Attribute)}
		612	%----------------------------------------------------------------------------
		613
		614	\texttt{typedef struct \{ mutexattr\_t a; DWORD ceiling; \}
		615	PC\_mutexattr\_t;}
		616
		617	The Priority Ceiling Mutex Attribute.
		618
		619	You can initialize that attribute using the static initializer
		620	\texttt{PC\_MUTEXATTR\_INITIALIZER} or calling the macro
		621
		622	\texttt{PC\_mutexattr\_default(at,c) }
		623
		624	where at is the mutex attribute, and c is the ceiling of the
		625	mutex.
		626
		627	%----------------------------------------------------------------------------
		628	\section{SRP\_mutexattr\_t (Stack Resource Policy Mutex Attribute)}
		629	%----------------------------------------------------------------------------
		630
		631	\texttt{typedef mutexattr\_t SRP\_mutexattr\_t;}
		632
		633	The Stack Resource Policy Mutex Attribute. You can initialize that
		634	attribute using the static initializer
		635	\texttt{SRP\_MUTEXATTR\_INITIALIZER} or calling the macro
		636
		637	\texttt{SRP\_mutexattr\_default(a) }
		638
		639	where at is the mutex attribute.
		640
		641	%----------------------------------------------------------------------------
		642	\section{NOP\_mutexattr\_t (No Protocol Mutex Attribute)}
		643	%----------------------------------------------------------------------------
		644
		645	\texttt{typedef mutexattr\_t NOP\_mutexattr\_t;}
		646
		647	The No Protocol Mutex Attribute.
		648
		649	You can initialize that attribute using the static initializer
		650	\texttt{NOP\_MUTEXATTR\_INITIALIZER} or calling the macro
		651
		652	\texttt{NOP\_mutexattr\_default(a) }
		653
		654	where at is the mutex attribute.
		655
		656	%----------------------------------------------------------------------------
		657	\section{NOPM\_mutexattr\_t (No Protocol Multiple lock Mutex Attribute)}
		658	%----------------------------------------------------------------------------
		659
		660	typedef mutexattr\_t NOPM\_mutexattr\_t;
		661
		662	The No Protocol Multiple lock Mutex Attribute. You can initialize
		663	that attribute using the static initializer
		664	\texttt{NOPM\_MUTEXATTR\_INITIALIZER} or calling the macro
		665
		666	\texttt{NOPM\_mutexattr\_default(a) }
		667
		668	where at is the mutex attribute.
		669
		670	%----------------------------------------------------------------------------
		671	\chapter{Scheduling algorithms}
		672	%----------------------------------------------------------------------------
		673
		674	%----------------------------------------------------------------------------
		675	\section{DUMMY}
		676	%----------------------------------------------------------------------------
		677
		678	\paragraph{Task Models Accepted:}
		679
		680	\begin{description}
		681	\item [DUMMY\_TASK\_MODEL]- This Model is used only at system
		682	startup to register the dummy task. It cannot be used by the other
		683	modules.
		684	\end{description}
		685
		686	\paragraph{Description:}
		687
		688	This Module implements a \texttt{dummy} task. A dummy task is a
		689	task like all the other task that simply does an infinite loop,
		690	does nothing inside.
		691
		692	Why we need such a Module? Look at the Scheduling Module
		693	Architecture: when the Kernel needs to schedule a task, it asks to
		694	all the registered modules if they have a task to schedule. The
		695	hyphotesis is that there must be ALWAYS a task to schedule. The
		696	dummy Scheduling Modules is used to register a module that have
		697	always a task to schedule (the dummy task).
		698
		699	The dummy Module is not needed if you can ensure that there will
		700	always be a task to schedule.
		701
		702	\paragraph{Exceptions Raised:}
		703
		704	\begin{description}
		705	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		706	guest operation is called, the exception is raised. \item
		707	[XUNVALID\_DUMMY\_OP]The dummy task can't be created, or
		708	activated, or another (strange) problem occurred.
		709	\end{description}
		710
		711	\paragraph{Usage:}
		712
		713	Usually the Dummy Module is the LAST scheduling module registered
		714	in the function
		715
		716	\texttt{\_\_kernel\_register\_levels\_\_}.
		717
		718	Just insert the following line into
		719	\texttt{\_\_kernel\_register\_levels\_\_} to register the Module:
		720
		721	\texttt{dummy\_register\_level();}
		722
		723	If you have a CPU where the HLT instruction works, you can use the
		724	define \texttt{\_\_HLT\_WORKS\_\_}. If that \texttt{\#define} is
		725	defined, the idle loop of the \texttt{dummy} task will use
		726	\texttt{HLT}, maybe saving power.
		727
		728	\paragraph{Files:}
		729
		730	\texttt{modules/dummy/*}
		731
		732	\paragraph{Implementation hints:}
		733
		734	You can look at the code to learn how to create a new task at
		735	startup using a \texttt{RUNLEVEL\_INIT} function.
		736
		737	%----------------------------------------------------------------------------
		738	\section{IntDrive Interrupt Server}
		739	%----------------------------------------------------------------------------
		740
		741	\input{intserver.tex}
		742
		743	\paragraph{Files:}
		744
		745	\texttt{modules/intdrive/*}
		746
		747	%----------------------------------------------------------------------------
		748	\subsection{Implementation}
		749	%----------------------------------------------------------------------------
		750
		751	\begin{intest}
		752	INTDRIVE\_register\_level \index{INTDRIVE\_register\_level}
		753	\end{intest}
		754
		755	\begin{description}
		756	\item [\textbf{LEVEL INTDRIVE\_register\_level(TIME capacity, TIME q\_theta, int
		757	U, int flags);}]
		758	\item [\textbf{Description:}]This function registers the IntDrive module at
		759	initialization time. This model should be usually registered as the first module
		760	in the \texttt{\_\_kernel\_register\_levels\_\_} function.
		761	\item [\textbf{Parameters:}]~
		762
		763	\begin{itemize}
		764	\item \textbf{capacity}: the server capacity;
		765	\item \textbf{q\_theta}: the server threshold;
		766	\item \textbf{U}: the maximum bandwidth consumed by the server;
		767	\item \textbf{flags}: a set of configuration options. Supported values are:
		768
		769	\begin{itemize}
		770	\item \textbf{INTDRIVE\_CHECK\_WCET}: when a WCET overrun occurs, an exception
		771	is raised.
		772	\end{itemize}
		773
		774	\end{itemize}
		775
		776	\end{description}
		777
		778	\begin{intest}
		779	INTDRIVE\_usedbandwidth \index{INTDRIVE\_usedbandwidth}
		780	\end{intest}
		781
		782	\begin{description}
		783	\item [\textbf{bandwidth\_t INTDRIVE\_usedbandwidth(LEVEL l);}]
		784	\item [\textbf{Description:}]returns the bandwidth used by the IntDrive.
		785	\end{description}
		786
		787	\begin{intest}
		788	INTDRIVE\_set\_q\_theta \index{INTDRIVE\_set\_q\_theta}
		789	\end{intest}
		790
		791	\begin{description}
		792	\item [\textbf{TIME INTDRIVE\_set\_q\_theta(LEVEL l, TIME new\_q\_theta);}]
		793	\item [\textbf{Description:}]changes the \texttt{q\_theta} value. Notice that
		794	changing \texttt{q\_theta} does not affect the bandwidth used by the server, nor
		795	the schedulability conditions for the application tasks.
		796	\end{description}
		797
		798	\textbf{ATTENTION:} notice that IntDrive is based on the Lipari-Bini
		799	hierarchical framework proposed in \cite{Lip03}. Therefore, the schedulability
		800	tests used by the current scheduling modules are no more sufficient to guarantee
		801	the schedulability. See \cite{Lip03} and \cite{Fac05} for more details.
		802
		803	%----------------------------------------------------------------------------
		804	\section{EDF (Earliest Deadline First) }
		805	%----------------------------------------------------------------------------
		806
		807	\paragraph{Task Models Accepted:}
		808
		809	\begin{description}
		810	\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic). The
		811	\texttt{wcet} and \texttt{mit} must be != 0. These parameters will
		812	be used to set the Worst Case Execution Time (WCET) and Period of
		813	the tasks. The \texttt{periodicity} can be either
		814	\texttt{PERIODIC} or \texttt{APERIODIC}. drel field must be <=
		815	mit.
		816
		817	\begin{description}
		818	\item [NOTE:]A Relative Deadline of 0 is interpreted as MIT. \item
		819	[NOTE:]The utilization of the task is computed as wcet/drel. \item
		820	[NOTE:]\textbf{offset} field specifies a release offset relative
		821	to task\_activate or group\_activate.
		822	\end{description}
		823
		824	\end{description}
		825
		826	\paragraph{Guest Models Accepted:}
		827
		828	\begin{description}
		829	\item [JOB\_TASK\_MODEL]- A single guest task activation. It must
		830	be identified by an absolute deadline and a period. The
		831	\texttt{period} field is ignored. \item [Description:]This module
		832	schedules periodic and sporadic tasks based on their absolute
		833	deadlines. The task guarantee is based on a simple utilization
		834	approach. The utilization factor of a task is computed as
		835	wcet/drel. (By default, drel = mit.) A periodic task must only be
		836	activated once; subsequent activations are triggered by an
		837	internal timer. By contrast, an sporadic task must be explicitely
		838	activated for each instance. NO GUARANTEE is performed on guest
		839	tasks. The guarantee must be performed by the level that inserts
		840	guest tasks in the EDF level.
		841	\end{description}
		842
		843	\paragraph{Exceptions raised:}
		844
		845	\begin{description}
		846	\item [XDEADLINE\_MISS]If a task misses its deadline and the
		847	\texttt{EDF\_ENABLE\_DL\_EXCEPTION} flag is set, this exception is
		848	raised. Note that after raising that exception, the task can't be
		849	put in execution again. The safest thing to do is to Shut Down the
		850	system! This exception is also raised if a guest task miss its
		851	deadline. \item [XWCET\_VIOLATION]If a task executes longer than
		852	its declared wcet and the \texttt{EDF\_ENABLE\_WCET\_EXCEPTION}
		853	flag is set, this exception is raised and the task is put in the
		854	\texttt{EDF\_WCET\_VIOLATED} state. To reactivate it, use
		855	\texttt{EDF\_task\_activate} via task\_activate or manage directly
		856	the EDF data structure. Note that the exception is not handled
		857	properly, an \texttt{XDEADLINE\_MISS} exception will also be
		858	raised at the period end. \item [XACTIVATION]If a sporadic task is
		859	activated with a rate that is greather than the rate declared in
		860	the model, this exception is raised and the task is NOT activated.
		861	This exception is also raised if we are trying to activate a
		862	periodic task stopped with \texttt{task\_delay}. \item
		863	[XUNVALID\_GUEST]This exception is raised if a
		864	\texttt{guest\_endcycle} or \texttt{guest\_sleep} guest calls are
		865	called.
		866	\end{description}
		867
		868	\paragraph{Usage:}
		869
		870	Usually this model is registered as one of the first Modules in
		871	the \texttt{\_\_kernel\_register\_levels\_\_} function. To
		872	register this module, just put this line into the
		873	\texttt{\_\_kernel\_register\_levels\_\_} function:
		874
		875	\texttt{EDF\_register\_level(flag);}
		876
		877	where \texttt{flag} can be:
		878
		879	\begin{description}
		880	\item [(No\_flags\_enabled)]- Deadline and wcet overruns are
		881	ignored. Pending periodic jobs are queued and are eventually
		882	scheduled with correct deadlines according to their original
		883	arrival times. Sporadic tasks that arrive to often aresimply
		884	dropped. \item [EDF\_ENABLE\_DL\_CHECK]- When a deadline overrun
		885	occurs, the dl\_miss counter of the task is increased. Same
		886	behavior for pending jobs as above. \item
		887	[EDF\_ENABLE\_WCET\_CHECK]- When a wcet overrun occurs, the
		888	wcet\_miss counter of the task is increased. Same behavior for
		889	pending jobs as above. \item [EDF\_ENABLE\_DL\_EXCEPTION]- When a
		890	deadline overrun occurs, an exception is raised. \item
		891	[EDF\_ENABLE\_WCET\_EXCEPTION]- When a wcet overrun occurs, an
		892	exception is raised. \item [EDF\_ENABLE\_ACT\_EXCEPTION]When a
		893	periodic or sporadic task is activated too often, an exception is
		894	raised.
		895	\end{description}
		896
		897	The functions \texttt{EDF\_get\_dl\_miss},
		898	\texttt{EDF\_get\_wcet\_miss}, \texttt{EDF\_get\_act\_miss}, and
		899	EDF\_get\_nact can be used to find out the number of missed
		900	deadlines, the number of wcet overruns, the number of skipped
		901	activations, and the number of currently queued periodic
		902	activations.
		903
		904	\begin{description}
		905	\item [EDF\_DISABLE\_ALL]- All checks disabled \item
		906	[EDF\_ENABLE\_GUARANTEE]- Guarantee test enabled.
		907
		908	When enabled, an acceptance test
		909	($\sum\frac{WCET_{i}}{Period_{i}}<1$) is performed; Deadline miss
		910	exceptions are raised in any case.
		911
		912	\item [EDF\_ENABLE\_ALL]- All checks enabled
		913	\end{description}
		914
		915	The EDF Module provides also addictional functions:
		916
		917	\begin{description}
		918	\item [\textbf{bandwidth\_t EDF\_usedbandwidth(LEVEL l);}]
		919	It returns the used bandwidth, where l is the level at which the
		920	EDF Module is registered.
		921	\item [\textbf{int EDF\_get\_dl\_miss(PID p);}]
		922	It returns the deadline miss counter.
		923	\item [\textbf{int EDF\_get\_wcet\_miss(PID p);}]
		924	It returns the wcet miss counter.
		925	\item [\textbf{int EDF\_get\_act\_miss(PID p);}]
		926	It returns the activation miss counter.
		927	\end{description}
		928
		929	\paragraph{Files:}
		930
		931	\texttt{modules/edf/*}
		932
		933	\paragraph{Implementation hints:}
		934
		935	It uses the CONTROL\_CAP field to keep track of the task execution
		936	time. It implements a ZOMBIE state for ended tasks. It post a
		937	single OSLib event for each task for deadline/reactivation/zombie
		938	detection. The \texttt{guest\_endcycle} and \texttt{guest\_sleep}
		939	guest calls are not implemented.
		940
		941	\begin{description}
		942	\item [NOTES:]~
		943	\end{description}
		944
		945	\begin{enumerate}
		946	\item Relative deadlines \textbf{drel <= mit} may be specified.
		947	\item An offset
		948	>
		949
		950	time. To synchronize a group of tasks, assign suitable offsets and
		951	then use the group\_activate function. \item This level doesn't
		952	manage the main task. \item The level uses the priority and
		953	timespec\_priority fields. \item The guest tasks don't provide the
		954	guest\_endcycle function.
		955	\end{enumerate}
		956
		957	%----------------------------------------------------------------------------
		958	\section{POSIX (fixed priority FIFO/RR scheduler)}
		959	%----------------------------------------------------------------------------
		960
		961	\paragraph{Task Models Accepted:}
		962
		963	\begin{description}
		964	\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. If the
		965	\texttt{inherit} field is set to \texttt{NRT\_INHERIT\_SCHED}, the
		966	scheduling properties of the running task are inherited (as
		967	required by the POSIX standard). Else, the \texttt{slice} field is
		968	used to set the time slice of the task (if \texttt{slice} is set
		969	to 0, the default value is used); the \texttt{weight} field is
		970	used to set the task priority; the \texttt{policy} field is used
		971	to set the policy of the task (\texttt{NRT\_RR\_POLICY} for
		972	Round-Robin or \texttt{NRT\_FIFO\_POLICY} for FIFO); the
		973	\texttt{arrivals} field can be set to \texttt{SAVE\_ARRIVALS} or
		974	\texttt{SKIP\_ARRIVALS}.
		975	\end{description}
		976
		977	\paragraph{Description:}
		978
		979	This module schedule his tasks following the POSIX scheduler as
		980	described by the standard IEEE 1003.1c. This Module is typically
		981	used by the POSIX primitives for their scheduling pourposes. For
		982	example, the pthread\_create function calls the task\_createn
		983	function passing a NRT\_TASK\_MODEL filled with the correct
		984	parameters.
		985
		986	The Module can create the \texttt{\_\_init\_\_} task, that is
		987	typically used to call the Standard C \texttt{main()} function.
		988
		989	\paragraph{Exceptions Raised:}
		990
		991	\begin{description}
		992	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		993	guest operation is called, the exception is raised.
		994	\end{description}
		995
		996	\paragraph{Usage:}
		997
		998	To register this module, just put this line into the
		999	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1000
		1001	\texttt{POSIX\_register\_level(slice, createmain, mb,
		1002	prioritylevels);}
		1003
		1004	where \texttt{slice} is the default timeslice for the POSIX tasks scheduled
		1005	using the Round-Robin policy, \texttt{createmain} is \texttt{POSIX\_MAIN\_YES}
		1006	or \texttt{POSIX\_MAIN\_NO} if you want that the POSIX Module creates or not the
		1007	\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct multiboot\_info
		1008	*} the Kernel passed to the \texttt{\_\_kernel\_register\_levels\_\_}
		1009	function, and prioritylevels are the number of different priority levels
		1010	supported by the Module \footnote{The POSIX standard requires a minimum of 32
		1011	priority levels}.
		1012
		1013	The POSIX Module provides also some addictional function, that are
		1014	used to implement the behaviour of various POSIX primitives:
		1015
		1016	\texttt{int POSIX\_sched\_yield(LEVEL l);}
		1017
		1018	This function forces the running task to go to his queue tail,
		1019	then calls the scheduler and changes the context. It is used by
		1020	the \texttt{sched\_yield()} primitive.
		1021
		1022	\texttt{int POSIX\_get\_priority\_max(LEVEL l);}
		1023
		1024	This function returns the maximum level allowed for the POSIX
		1025	level. It is used by the \texttt{sched\_get\_priority()}
		1026	primitive.
		1027
		1028	\texttt{int POSIX\_rr\_get\_interval(LEVEL l);}
		1029
		1030	This function returns the default timeslice for the POSIX level.
		1031	It is used by the \texttt{sched\_rr\_get\_interval()} primitive.
		1032
		1033	\texttt{int POSIX\_getschedparam(LEVEL l, PID p, int *policy,
		1034	int *priority);}
		1035
		1036	This functions returns some paramaters of a task; \texttt{policy}
		1037	is set to \texttt{NRT\_RR\_POLICY} or \texttt{NRT\_FIFO\_POLICY};
		1038	priority is set in the range \texttt{{[}0..prioritylevels{]}}. The
		1039	function returns \texttt{ENOSYS} or \texttt{ESRCH} if there are
		1040	problems. The function must be called with interrupts disabled and
		1041	is used by the \texttt{pthread\_getschedparam()} primitive.
		1042
		1043	\texttt{int POSIX\_setschedparam(LEVEL l, PID p, int policy, int
		1044	priority);}
		1045
		1046	This functions sets some paramaters of a task; \texttt{policy}
		1047	must be set to \texttt{NRT\_RR\_POLICY} or
		1048	\texttt{NRT\_FIFO\_POLICY}; priority must be set in the range
		1049	\texttt{{[}0..prioritylevels{]}}. The function returns
		1050	\texttt{ENOSYS}, \texttt{EINVAL} or \texttt{ESRCH} if there are
		1051	problems. The function must be called with interrupts disabled and
		1052	is used by the \texttt{pthread\_setschedparam() primitive}.
		1053
		1054	\paragraph{Files:}
		1055
		1056	\texttt{modules/posix/*}
		1057
		1058	\paragraph{Implementation hints:}
		1059
		1060	The implementation of this module is directly derived from the RR
		1061	scheme.
		1062
		1063	%----------------------------------------------------------------------------
		1064	\section{RM (Rate Monotonic)}
		1065	%----------------------------------------------------------------------------
		1066
		1067	\paragraph{Task
		1068	Models Accepted:}
		1069
		1070	\begin{description}
		1071	\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic). The
		1072	\texttt{wcet} and \texttt{mit} must be != 0. These parameters will
		1073	be used to set the Worst Case Execution Time (WCET) and Period of
		1074	the tasks. The \texttt{periodicity} can be either
		1075	\texttt{PERIODIC} or \texttt{APERIODIC}. The Relative Deadline is
		1076	ignored (deadlines are equal to periods).
		1077	\end{description}
		1078
		1079	\paragraph{Guest Models Accepted:}
		1080
		1081	\begin{description}
		1082	\item [JOB\_TASK\_MODEL]- A single guest task activation. It must
		1083	be identified by an absolute deadline and a period.
		1084	\end{description}
		1085
		1086	\paragraph{Description:}
		1087
		1088	This module schedule his tasks following the classic RM scheme as
		1089	described by Liu and Layland. The task guarantee is based on the
		1090	factor utilization approach. The tasks scheduled are periodic and
		1091	sporadic. The sporadic tasks are like hard task with periodicity
		1092	set to \texttt{APERIODIC}; they are guaranteed as a periodic task
		1093	with period equal to the minimum interarrival time. All the task
		1094	are put in a queue and the scheduling is based on the period
		1095	value.
		1096
		1097	No Guarantee is performed on guest tasks. The guarantee must be
		1098	performed by the level that inserts guest tasks in the RM level.
		1099
		1100	If a RM task does not respect its WCET and deadline constraints,
		1101	then the Module will raise an exception. Note that the deadline
		1102	exception is not recoverable, so the Module will be in an
		1103	inconsistent state after a Deadline Miss. Deadline Miss in this
		1104	Module are treated as unrecoverable errors.
		1105
		1106	If you try to activate a Periodic task that is not sleeping,
		1107	nothing happens.
		1108
		1109	\paragraph{Exceptions Raised:}
		1110
		1111	\begin{description}
		1112	\item [XDEADLINE\_MISS]If a task miss his deadline, the exception
		1113	is raised. Note that after raising that exception, the task can't
		1114	be put in execution again. The safest thing to do is to Shut Down
		1115	the system! This exception is also raised if a guest task miss its
		1116	deadline. \item [XWCET\_VIOLATION]If a task doesn't end the
		1117	current cycle before if consume the \texttt{wcet}, an exception is
		1118	raised, and the task is put in the \texttt{RM\_WCET\_VIOLATED}
		1119	state. To reactivate it, use \texttt{RM\_task\_activate} via
		1120	task\_activate or manage directly the RM data structure. Note that
		1121	the exception is not handled properly, an \texttt{XDEADLINE\_MISS}
		1122	exception will also be raised at the period end. \item
		1123	[XACTIVATION]If a sporadic task is activated with a rate that is
		1124	greather than the rate declared in the model, this exception is
		1125	raised and the task is NOT activated. This exception is also
		1126	raised if we are trying to activate a periodic task stopped with
		1127	\texttt{task\_sleep} before the deadline in which the
		1128	\texttt{task\_sleep} is called. \item [XUNVALID\_GUEST]This
		1129	exception is raised if a \texttt{guest\_endcycle} or
		1130	\texttt{guest\_sleep} guest calls are called.
		1131	\end{description}
		1132
		1133	\paragraph{Usage:}
		1134
		1135	Usually this model is registered as one of the first Modules in
		1136	the \texttt{\_\_kernel\_register\_levels\_\_} function. To
		1137	register this module, just put this line into the
		1138	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1139
		1140	\texttt{RM\_register\_level(flag);}
		1141
		1142	where \texttt{flag} can be:
		1143
		1144	Restrictions and special features:
		1145
		1146	\begin{description}
		1147	\item [(No\_flags\_enabled)]- Deadline and wcet overruns are
		1148	ignored. Pending periodic jobs are queued and are eventually
		1149	scheduled with correct deadlines according to their original
		1150	arrival times. Sporadic tasks that arrive to often are simply
		1151	dropped. \item [RM\_ENABLE\_DL\_CHECK]- When a deadline overrun
		1152	occurs, the dl\_miss counter of the task is increased. Same
		1153	behavior for pending jobs as above. \item
		1154	[RM\_ENABLE\_WCET\_CHECK]- When a wcet overrun occurs, the
		1155	wcet\_miss counter of the task is increased. Same behavior for
		1156	pending jobs as above. \item [RM\_ENABLE\_DL\_EXCEPTION]- When a
		1157	deadline overrun occurs, an exception is raised. \item
		1158	[RM\_ENABLE\_WCET\_EXCEPTION]- When a wcet overrun occurs, an
		1159	exception is raised. \item [RM\_ENABLE\_ACT\_EXCEPTION]When a
		1160	periodic or sporadic task is activated too often, an exception is
		1161	raised. \item [RM\_DISABLE\_ALL]- Wcet and Guarantee test disabled
		1162	\item [RM\_ENABLE\_GUARANTEE]- Guarantee test enabled (when
		1163	enabled, an acceptance test ($\sum\frac{WCET_{i}}{Period_{i}}<1$)
		1164	is performed; Deadline miss exceptions are raised in any case.
		1165	Note that, for reasons of semplicity, the test that has been
		1166	implemented IS NOT the test for RM, but only a simple acceptance
		1167	test. \item [RM\_ENABLE\_ALL]- Wcet and Guarantee test enabled
		1168	\end{description}
		1169	The RM Module provides also addictional functions:
		1170
		1171	\begin{description}
		1172	\item [\textbf{bandwidth\_t RM\_usedbandwidth(LEVEL l);}]
		1173	It returns the used bandwidth, where l is the level at which the
		1174	RM Module is registered.
		1175	\item [\textbf{int RM\_get\_dl\_miss(PID p);}]
		1176	It returns the deadline miss counter.
		1177	\item [\textbf{int RM\_get\_wcet\_miss(PID p);}]
		1178	It returns the wcet miss counter.
		1179	\item [\textbf{int RM\_get\_act\_miss(PID p);}]
		1180	It returns the activation miss counter.
		1181	\end{description}
		1182
		1183	\paragraph{Files:}
		1184
		1185	\texttt{modules/rm/*}
		1186
		1187	\paragraph{Implementation hints:}
		1188
		1189	The implementation of this module is very similar to the
		1190	implementation of the EDF Module.
		1191
		1192	\paragraph{NOTE}
		1193
		1194	\begin{enumerate}
		1195	\item Relative deadlines drel <= mit may be specified. \item An offset > 0 will
		1196	delay the activation of the task by the same amount of time. To synchronize a
		1197	group of tasks, assign suitable \item offsets and then use the group\_activate
		1198	function. \item This level doesn't manage the main task. \item The level uses
		1199	the priority and timespec\_priority fields. \item The guest tasks don't provide
		1200	the guest\_endcycle function. \item At init time, the user can specify the
		1201	behavior in case ofdeadline and wcet overruns. The following flags are
		1202	available:
		1203	\end{enumerate}
		1204
		1205	%----------------------------------------------------------------------------
		1206	\section{RR (Round Robin)}
		1207	%----------------------------------------------------------------------------
		1208
		1209	\paragraph{Task Models Accepted:}
		1210
		1211	\begin{description}
		1212	\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. The \texttt{slice}
		1213	field is used to set the time slice of the task. If \texttt{slice}
		1214	is set to 0, the default value is used. The \texttt{weight},
		1215	\texttt{arrivals}, \texttt{policy} and \texttt{inherit} fields are
		1216	ignored.
		1217	\end{description}
		1218
		1219	\paragraph{Description:}
		1220
		1221	This module schedule his tasks following the classic round-robin
		1222	scheme. The default timeslice is given at registration time and is
		1223	a a per-task specification. The default timeslice is used if the
		1224	\texttt{slice} field in the \texttt{NRT\_TASK\_MODEL} is 0.
		1225
		1226	If a task is activated when it is already active (its instance is
		1227	not yet finished on a \texttt{task\_endcycle} or
		1228	\texttt{task\_sleep}), nothing happens.
		1229
		1230	If you need to remember the pending activations you can use the
		1231	\texttt{RR2} scheduling module.
		1232
		1233	The Module can create the \texttt{\_\_init\_\_} task, that is
		1234	typically used to call the Standard C \texttt{main()} function.
		1235
		1236	\paragraph{Exceptions Raised:}
		1237
		1238	\begin{description}
		1239	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		1240	guest operation is called, the exception is raised.
		1241	\end{description}
		1242
		1243	\paragraph{Usage:}
		1244
		1245	To register this module, just put this line into the
		1246	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1247
		1248	\texttt{RR\_register\_level(slice, createmain, mb);}
		1249
		1250	where \texttt{slice} is the default timeslice for the RR tasks,
		1251	\texttt{createmain} is \texttt{RR\_MAIN\_YES} or
		1252	\texttt{RR\_MAIN\_NO} if you want that RR creates or not the
		1253	\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct
		1254	multiboot\_info *} the Kernel passed to the
		1255	\texttt{\_\_kernel\_register\_levels\_\_} function.
		1256
		1257	You can use more than one RR Scheduling Module to simulate a
		1258	Multilevel scheduling policy. The RR Module does not add any
		1259	addictional function.
		1260
		1261	\paragraph{Files:}
		1262
		1263	\texttt{modules/rr/*}
		1264
		1265	\paragraph{Implementation hints:}
		1266
		1267	This is one of the simplest scheduling module. It can be useful to
		1268	learn how to create the \_\_init\_\_ task at startup time. It uses
		1269	the CONTROL\_CAP field. It supports negative task capacities (that
		1270	can happen when using shadows; for that reason, the scheduler has
		1271	a while inside, and the timeslices ar added and not assigned). No
		1272	Guarantee is performed at task creation.
		1273
		1274	%----------------------------------------------------------------------------
		1275	\section{RR2 (Round Robin with pending activations)}
		1276	%----------------------------------------------------------------------------
		1277
		1278	\paragraph{Task Models Accepted:}
		1279
		1280	\begin{description}
		1281	\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. The \texttt{slice}
		1282	field is used to set the time slice of the task. If \texttt{slice}
		1283	is set to 0, the default value is used. The \texttt{arrivals}
		1284	field is used to say if the activations have to be saved
		1285	(\texttt{SAVE\_ARRIVALS}) or skipped (\texttt{SKIP\_ARRIVALS}).
		1286	The \texttt{weight}, \texttt{policy} and \texttt{inherit} fields
		1287	are ignored.
		1288	\end{description}
		1289
		1290	\paragraph{Description:}
		1291
		1292	The Module is identical to the RR Scheduling Module, except that
		1293	task activations can be saved if a task was created with the
		1294	arrivals field equal to SAVE\_ARRIVALS.
		1295
		1296	\paragraph{Exceptions Raised:}
		1297
		1298	See the RR Scheduling Module.
		1299
		1300	\paragraph{Usage:}
		1301
		1302	See the RR Scheduling Module, changing every occurrence of RR with
		1303	RR2.
		1304
		1305	\paragraph{Files:}
		1306
		1307	\texttt{modules/rr2/*}
		1308
		1309	\paragraph{Implementation hints:}
		1310
		1311	With respect to the RR Scheduling Module, it adds a pending
		1312	activation counter (nact) for each task.
		1313
		1314	%----------------------------------------------------------------------------
		1315	\section{RRSOFT (hard/SOFT Round Robin)}
		1316	%----------------------------------------------------------------------------
		1317
		1318	\paragraph{Task Models Accepted:}
		1319
		1320	\begin{description}
		1321	\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic).
		1322	Only the periodicity and the mit parameters are used to know if
		1323	the task is periodic/sporadic and to set the task period. The task
		1324	timeslice is set to the default value. \item [SOFT\_TASK\_MODEL]-
		1325	Soft Tasks (Periodic and Sporadic). Only the periodicity, arrivals
		1326	and period parameters are used to know if the task is
		1327	periodic/sporadic, to set the task period and to know if the
		1328	pending activations should be saved. The task timeslice is set to
		1329	the default value. \item [NRT\_TASK\_MODEL]- Non-Realtime Tasks.
		1330	The \texttt{slice} field is used to set the time slice of the
		1331	task. If \texttt{slice} is set to 0, the default value is used.
		1332	The \texttt{arrivals} field is used to say if the activations have
		1333	to be saved (\texttt{SAVE\_ARRIVALS}) or skipped
		1334	(\texttt{SKIP\_ARRIVALS}). The \texttt{weight}, \texttt{policy}
		1335	and \texttt{inherit} fields are ignored.
		1336	\end{description}
		1337
		1338	\paragraph{Description:}
		1339
		1340	This module can be used as a polymorphic module that can accept
		1341	Hard, Soft or NRT Task Models. The policy used to schedule the
		1342	tasks is the same of RR2, plus the fact that SOFT and HARD tasks
		1343	can be periodic, so they can be automatically activated at each
		1344	instance.
		1345
		1346	This Module is very useful if you want to replace another Module
		1347	that accept Hard of Soft tasks with a round-robin scheduler, for
		1348	example to compare a scheduling algorithm with the plain round
		1349	robin.
		1350
		1351	\paragraph{Exceptions Raised:}
		1352
		1353	\begin{description}
		1354	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		1355	guest operation is called, the exception is raised.
		1356	\end{description}
		1357
		1358	\paragraph{Usage:}
		1359
		1360	To register this module, just put this line into the
		1361	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1362
		1363	\texttt{RRSOFT\_register\_level(slice, createmain, mb, models);}
		1364
		1365	where \texttt{slice} is the default timeslice for the RR tasks,
		1366	\texttt{createmain} is \texttt{RR\_MAIN\_YES} or
		1367	\texttt{RR\_MAIN\_NO} if you want that RR creates or not the
		1368	\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct
		1369	multiboot\_info *} the Kernel passed to the
		1370	\texttt{\_\_kernel\_register\_levels\_\_} function, and
		1371	\texttt{models} specifies the kind of Models accepted by the
		1372	Module. The \texttt{models} value can be an or of the values of
		1373	the following constants: \texttt{RRSOFT\_ONLY\_HARD},
		1374	\texttt{RRSOFT\_ONLY\_HARD}, \texttt{RRSOFT\_ONLY\_HARD}.
		1375
		1376	You can use more than one RR Scheduling Module to simulate a
		1377	Multilevel scheduling policy. The RR Module does not add any
		1378	addictional function.
		1379
		1380	\paragraph{Files:}
		1381
		1382	\texttt{modules/rrsoft/*}
		1383
		1384	\paragraph{Implementation hints:}
		1385
		1386	The implementation of the Module is similar to RR2 plus the
		1387	implementation of the reactivation for periodic tasks.
		1388
		1389	%----------------------------------------------------------------------------
		1390	\chapter{Aperiodic servers}
		1391	%----------------------------------------------------------------------------
		1392
		1393	%----------------------------------------------------------------------------
		1394	\section{CBS (Constant Bandwidth Server)}
		1395	%----------------------------------------------------------------------------
		1396
		1397	\paragraph{Task Models Accepted:}
		1398
		1399	\begin{description}
		1400	\item [SOFT\_TASK\_MODEL]- Soft Tasks (Periodic and Sporadic). The
		1401	\texttt{met} and \texttt{period} must be != 0. These parameters
		1402	will be used to set the Mean Execution Time (MET) and the Period
		1403	of the tasks. The \texttt{periodicity} can be either
		1404	\texttt{PERIODIC} or \texttt{APERIODIC}. The \texttt{arrivals}
		1405	field can be either \texttt{SAVE\_ARRIVALS} or
		1406	\texttt{SKIP\_ARRIVALS}. The \texttt{wcet} field is ignored (Worst
		1407	case execution times are not used by CBS).
		1408	\end{description}
		1409
		1410	\paragraph{Description:}
		1411
		1412	This module schedule his tasks following the CBS algorithm. The
		1413	task guarantee is based on the factor utilization approach. The
		1414	tasks scheduled are periodic and sporadic. The sporadic tasks are
		1415	like hard task with periodicity set to \texttt{APERIODIC}. All the
		1416	task are put as guest task in the scheduling queue of another
		1417	Module (typically that Module is an EDF Module).
		1418
		1419	A CBS server is attached to each task, with the parameters passed
		1420	in the \texttt{SOFT\_TASK\_MODEL}.
		1421
		1422	If you try to activate a Periodic task that is not sleeping, a pending
		1423	activation is recorded \footnote{If the task was created with the
		1424	\texttt{SAVE\_ARRIVALS} option... }.
		1425
		1426	\paragraph{Exceptions Raised:}
		1427
		1428	\begin{description}
		1429	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		1430	guest operation is called, the exception is raised.
		1431	\end{description}
		1432
		1433	\paragraph{Usage:}
		1434
		1435	To register this module, just put this line into the
		1436	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1437
		1438	\texttt{CBS\_register\_level(flag, master);}
		1439
		1440	where \texttt{flag} can be:
		1441
		1442	\begin{description}
		1443	\item [CBS\_DISABLE\_ALL]- Guarantee test disabled. \item
		1444	[CBS\_ENABLE\_GUARANTEE]- Guarantee test enabled (when enabled, an
		1445	acceptance test ($\sum\frac{met_{i}}{period_{i}}<1$) is performed;
		1446	Deadline miss exceptions are raised in any case. \item
		1447	[CBS\_ENABLE\_ALL]- Guarantee test enabled.
		1448	\end{description}
		1449	and \texttt{master} is the level to that the CBS is attached. At
		1450	the moment, you can attach a CBS Module either to an \texttt{EDF}
		1451	or an \texttt{EDFACT} Module. The CBS Module can be registered as
		1452	the last scheduling Module after the \texttt{DUMMY} Module (this
		1453	because the CBS Module does not use background time, and because
		1454	when a CBS task is ready it is inserted in another queue!).
		1455
		1456	The CBS Module provides also an addictional function, that can be
		1457	used to get the used bandwidth by the Module and the pending
		1458	activations of a task. The prototypes of these function are:
		1459
		1460	\texttt{bandwidth\_t CBS\_usedbandwidth(LEVEL l);}
		1461
		1462	where l is the level at which the CBS Module is registered.
		1463
		1464	\texttt{int CBS\_get\_nact(LEVEL l, PID p);}
		1465
		1466	Returns the number of pending activations of a task. No control is
		1467	done if the task is not a CBS task! (l is the level at which the
		1468	CBS Module is registered, p is the PID of the task).
		1469
		1470	\paragraph{Files:}
		1471
		1472	\texttt{modules/cbs/*}
		1473
		1474	\paragraph{Implementation hints:}
		1475
		1476	CBS implementation is similar to the EDF implementation except
		1477	that a capacity exaustion postpones a deadline, and that the
		1478	deadline event is simply a reactivation. This is one of the only
		1479	Modules where the \texttt{task\_eligible} task calls is defined
		1480	non-void.
		1481
		1482	%----------------------------------------------------------------------------
		1483	\section{HARD\_CBS}
		1484	%----------------------------------------------------------------------------
		1485
		1486	This Module is very similar to the standard CBS, but it implements
		1487	the Hard Reservation algorithm.
		1488
		1489	\begin{description}
		1490	\item [Files:]\texttt{modules/hardcbs/*}
		1491	\end{description}
		1492
		1493	%----------------------------------------------------------------------------
		1494	\section{DS (Deferrable Server)}
		1495	%----------------------------------------------------------------------------
		1496
		1497	\paragraph{Task Models Accepted:}
		1498
		1499	\begin{description}
		1500	\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
		1501	\texttt{periodicity} can be only \texttt{APERIODIC}. The
		1502	\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
		1503	\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
		1504	\end{description}
		1505
		1506	\paragraph{Description:}
		1507
		1508	This module schedule its tasks following the Deferrable Server
		1509	Algorithm. All the aperiodic requests are served on a FCFS basis.
		1510	The Module can be configured to use only its budget or to also use
		1511	the idle time left by the higher level Modules. The Module can be
		1512	configured to save or skip task activations. The Module can be
		1513	attached to either a RM or an EDF Module.
		1514
		1515	\paragraph{Exceptions Raised:}
		1516
		1517	\begin{description}
		1518	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		1519	guest operation is called, the exception is raised.
		1520	\end{description}
		1521
		1522	\paragraph{Usage:}
		1523
		1524	To register this module, just put this line into the
		1525	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1526
		1527	\texttt{DS\_register\_level(flag, master, Cs, per);}
		1528
		1529	where \texttt{flag} can be:
		1530
		1531	\begin{description}
		1532	\item [DS\_DISABLE\_ALL]- Guarantee test disabled; Background
		1533	scheduling disabled. \item [DS\_ENABLE\_BACKGROUND]- Background
		1534	scheduling enabled. \item [DS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
		1535	test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
		1536	is performed. This flag have to be used if the Module is attached
		1537	to an EDF Module. \item [DS\_ENABLE\_ALL\_EDF]- EDF guarantee test
		1538	enabled, Background scheduling disabled. \item
		1539	[DS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
		1540	an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
		1541	have to be used if the Module is attached to a RM Module. \item
		1542	[DS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
		1543	scheduling disabled.
		1544	\end{description}
		1545	\texttt{master} is the level to that the DS Module is attached. At
		1546	the moment, you can attach a DS Module either to an \texttt{EDF},
		1547	\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
		1548	\texttt{per} are the budget and the period of the deferrable
		1549	server. If it is configured to do not use background time, the DS
		1550	Module can be registered as the last scheduling Module after the
		1551	\texttt{DUMMY} Module. Otherwise, it should be put in the middle
		1552	of the list to catck the idle time left by higher level Modules.
		1553
		1554	The DS Module provides also an addictional function, that can be
		1555	used to get the used bandwidth by the Module. The prototype of the
		1556	function is:
		1557
		1558	\texttt{bandwidth\_t DS\_usedbandwidth(LEVEL l);}
		1559
		1560	where l is the level at which the DS Module is registered.
		1561
		1562	\paragraph{Files:}
		1563
		1564	\texttt{modules/ds/*}
		1565
		1566	\paragraph{Implementation hints:}
		1567
		1568	The DS Module uses a FIFO queue to enqueue the ready tasks. Only
		1569	the first task is inserted into the queue of the Master Level. The
		1570	Module does not use the CONTROL\_CAP field, but it handles its
		1571	capacity event by itself. The budget of the module is recharged
		1572	every DS period, and is kept into an internal data structure of
		1573	the module, and not in the wcet and avail\_time fields of every
		1574	task. Note that the idle time is recognized when the DS scheduler
		1575	is called. In that case, no capacity event is posted. The
		1576	implementation is very similar to the PS Module implementation.
		1577
		1578	%----------------------------------------------------------------------------
		1579	\section{PS (Polling Server)}
		1580	%----------------------------------------------------------------------------
		1581
		1582	\paragraph{Task Models Accepted:}
		1583
		1584	\begin{description}
		1585	\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
		1586	\texttt{periodicity} can be only \texttt{APERIODIC}. The
		1587	\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
		1588	\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
		1589	\end{description}
		1590
		1591	\paragraph{Description:}
		1592
		1593	This module schedule its tasks following the Polling Server
		1594	Algorithm. All the aperiodic requests are served on a FCFS basis.
		1595	The Module can be configured to use only its budget or to also use
		1596	the idle time left by the higher level Modules. The Module can be
		1597	configured to save or skip task activations. The Module can be
		1598	attached to either a RM or an EDF Module.
		1599
		1600	\paragraph{Exceptions Raised:}
		1601
		1602	\begin{description}
		1603	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		1604	guest operation is called, the exception is raised.
		1605	\end{description}
		1606
		1607	\paragraph{Usage:}
		1608
		1609	To register this module, just put this line into the
		1610	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1611
		1612	\texttt{PS\_register\_level(flag, master, Cs, per);}
		1613
		1614	where \texttt{flag} can be:
		1615
		1616	\begin{description}
		1617	\item [PS\_DISABLE\_ALL]- Guarantee test disabled; Background
		1618	scheduling disabled. \item [PS\_ENABLE\_BACKGROUND]- Background
		1619	scheduling enabled. \item [PS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
		1620	test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
		1621	is performed. This flag have to be used if the Module is attached
		1622	to an EDF Module. \item [PS\_ENABLE\_ALL\_EDF]- EDF guarantee test
		1623	enabled, Background scheduling disabled. \item
		1624	[PS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
		1625	an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
		1626	have to be used if the Module is attached to a RM Module. \item
		1627	[PS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
		1628	scheduling disabled.
		1629	\end{description}
		1630	\texttt{master} is the level to that the DS Module is attached. At
		1631	the moment, you can attach a PS Module either to an \texttt{EDF},
		1632	\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
		1633	\texttt{per} are the budget and the period of the deferrable
		1634	server. If it is configured to do not use background time, the PS
		1635	Module can be registered as the last scheduling Module after the
		1636	\texttt{DUMMY} Module. Otherwise, it should be put in the middle
		1637	of the list to catck the idle time left by higher level Modules.
		1638
		1639	The PS Module provides also an addictional function, that can be
		1640	used to get the used bandwidth by the Module. The prototype of the
		1641	function is:
		1642
		1643	\texttt{bandwidth\_t PS\_usedbandwidth(LEVEL l);}
		1644
		1645	where l is the level at which the PS Module is registered.
		1646
		1647	\paragraph{Files:}
		1648
		1649	\texttt{modules/ps/*}
		1650
		1651	\paragraph{Implementation hints:}
		1652
		1653	The PS Module uses a FIFO queue to enqueue the ready tasks. Only
		1654	the first task is inserted into the queue of the Master Level. The
		1655	Module does not use the CONTROL\_CAP field, but it handles its
		1656	capacity event by itself. The budget of the module is recharged
		1657	every PS period, and is kept into an internal data structure of
		1658	the module, and not in the wcet and avail\_time fields of every
		1659	task. Note that the idle time is recognized when the PS scheduler
		1660	is called. In that case, no capacity event is posted. The
		1661	implementation is very similar to the DS Module implementation.
		1662
		1663	%----------------------------------------------------------------------------
		1664	\section{SS (Sporadic Server)}
		1665	%----------------------------------------------------------------------------
		1666
		1667	\paragraph{Task Models Accepted:}
		1668
		1669	\begin{description}
		1670	\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
		1671	\texttt{periodicity} can be only \texttt{APERIODIC}. The
		1672	\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
		1673	\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
		1674	\end{description}
		1675
		1676	\paragraph{Description:}
		1677
		1678	This module schedule its tasks following the Sporadic Server
		1679	Algorithm. The Module can be configured to save or skip task
		1680	activations. The Module can be attached to either a RM or an EDF
		1681	Module. The module has been written by Marco Gigante. Please
		1682	contact the author for more informations.
		1683
		1684	\paragraph{Exceptions Raised:}
		1685
		1686	\begin{description}
		1687	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		1688	guest operation is called, the exception is raised.
		1689	\end{description}
		1690
		1691	\paragraph{Usage:}
		1692
		1693	To register this module, just put this line into the
		1694	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1695
		1696	\texttt{SS\_register\_level(flag, master, Cs, per);}
		1697
		1698	where \texttt{flag} can be:
		1699
		1700	\begin{description}
		1701	\item [SS\_DISABLE\_ALL]- Guarantee test disabled; Background
		1702	scheduling disabled. \item [SS\_ENABLE\_BACKGROUND]- Background
		1703	scheduling enabled. \item [SS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
		1704	test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
		1705	is performed. This flag have to be used if the Module is attached
		1706	to an EDF Module. \item [SS\_ENABLE\_ALL\_EDF]- EDF guarantee test
		1707	enabled, Background scheduling disabled. \item
		1708	[SS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
		1709	an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
		1710	have to be used if the Module is attached to a RM Module. \item
		1711	[SS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
		1712	scheduling disabled.
		1713	\end{description}
		1714
		1715	\texttt{master} is the level to that the SS Module is attached. At
		1716	the moment, you can attach a SS Module either to an \texttt{EDF},
		1717	\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
		1718	\texttt{per} are the budget and the period of the deferrable
		1719	server. If it is configured to do not use background time, the SS
		1720	Module can be registered as the last scheduling Module after the
		1721	\texttt{DUMMY} Module. Otherwise, it should be put in the middle
		1722	of the list to catck the idle time left by higher level Modules.
		1723
		1724	The SS Module provides also some addictional function, that can be
		1725	used to get the used bandwidth by the Module and its available
		1726	capacity. The prototypes of the functions are:
		1727
		1728	\texttt{bandwidth\_t SS\_usedbandwidth(LEVEL l);}
		1729
		1730	where l is the level at which the SS Module is registered.
		1731
		1732	\texttt{int SS\_availCs(LEVEL l);}
		1733
		1734	Returns tha available capacity of the Module
		1735
		1736	\paragraph{Files:}
		1737
		1738	\texttt{modules/ss/*}
		1739
		1740	\paragraph{Implementation hints:}
		1741
		1742	The implementation of the Module is quite complex. Please refer to
		1743	the comments in the source code.
		1744
		1745	%----------------------------------------------------------------------------
		1746	\section{TBS (Total Bandwidth Server)}
		1747	%----------------------------------------------------------------------------
		1748
		1749	\paragraph{Task Models Accepted:}
		1750
		1751	\begin{description}
		1752	\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
		1753	\texttt{wcet} must be != 0. The \texttt{periodicity} can be either
		1754	\texttt{PERIODIC} or \texttt{APERIODIC}. The \texttt{arrivals}
		1755	field can be either \texttt{SAVE\_ARRIVALS} or
		1756	\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
		1757	\end{description}
		1758
		1759	\paragraph{Description:}
		1760
		1761	This module schedule his tasks following the TBS algorithm. The
		1762	task guarantee is based on the factor utilization approach. The
		1763	tasks scheduled are only sporadic. Each task has a deadline
		1764	assigned with the TBS scheme,
		1765	$d_{k}=\max(r_{k},d_{k-1})+\frac{wcet}{U_{s}}$
		1766
		1767	The tasks are inserted in an EDF level (or similar), and the TBS
		1768	level expects that the task is scheduled with the absolute
		1769	deadline passed in the guest model.
		1770
		1771	The acceptance test is based on the factor utilization approach.
		1772	The theory guarantees that the task set is schedulable if
		1773	$U_{p}+U_{s}\leq1$ so it is sufficient to add the Us to the
		1774	bandwidth used by the upper levels.
		1775
		1776	\paragraph{Exceptions Raised:}
		1777
		1778	\begin{description}
		1779	\item [XUNVALID\_GUEST]This level doesn't support guests. When a
		1780	guest operation is called, the exception is raised. \item
		1781	[XDEADLINE\_MISS]If a task miss his deadline, the exception is
		1782	raised. Normally, a TBS task can't cause the raise of such
		1783	exception because if it really use more time than declared a
		1784	\texttt{XWCET\_VIOLATION} is raised instead. \item
		1785	[XWCET\_VIOLATION]If a task doesn't end the current cycle before
		1786	if consume the wcet, an exception is raised, and the task is put
		1787	in the \texttt{TBS\_WCET\_VIOLATED} state. To reactivate it, call
		1788	\texttt{TBS\_task\_activate} using \texttt{task\_activate} or
		1789	manage directly the TBS data structure. Note that if the exception
		1790	is not handled properly, an \texttt{XDEADLINE\_MISS} exception
		1791	will also be raised at the absolute deadline...
		1792	\end{description}
		1793
		1794	\paragraph{Usage:}
		1795
		1796	To register this module, just put this line into the
		1797	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1798
		1799	\texttt{TBS\_register\_level(flag, master, num, den);}
		1800
		1801	where \texttt{flag} can be:
		1802
		1803	\begin{description}
		1804	\item [TBS\_DISABLE\_ALL]- Guarantee test disabled. \item
		1805	[TBS\_ENABLE\_GUARANTEE]- Guarantee test enabled (when enabled,
		1806	the acceptance test is performed); Deadline miss exceptions are
		1807	raised in any case. \item [TBS\_ENABLE\_WCET\_CHECK]- WCET check
		1808	enabled. \item [TBS\_ENABLE\_ALL]- Guarantee test and WCET check
		1809	enabled.
		1810	\end{description}
		1811	and \texttt{master} is the level to that the TBS is attached. num
		1812	and den are the reserved bandwidth ($U_{s}=\frac{num}{den}$) for
		1813	the TBS server. At the moment, you can attach a TBS Module either
		1814	to an \texttt{EDF} or an \texttt{EDFACT} Module. The TBS Module
		1815	can be registered as the last scheduling Module after the
		1816	\texttt{DUMMY} Module (this because the TBS Module does not use
		1817	background time, and because when a TBS task is ready it is
		1818	inserted in another queue!).
		1819
		1820	The TBS Module provides also some addictional functions, that can
		1821	be used to get the used bandwidth by the Module and the pending
		1822	activations of a task. The prototypes of these function are:
		1823
		1824	\texttt{bandwidth\_t TBS\_usedbandwidth(LEVEL l);}
		1825
		1826	where l is the level at which the TBS Module is registered.
		1827
		1828	\texttt{int TBS\_get\_nact(LEVEL l, PID p);}
		1829
		1830	Returns the number of pending activations of a task. No control is
		1831	done if the task is not a TBS task! (l is the level at which the
		1832	TBS Module is registered, p is the PID of the task).
		1833
		1834	\paragraph{Files:}
		1835
		1836	\texttt{modules/tbs/*}
		1837
		1838	\paragraph{Implementation hints:}
		1839
		1840	The TBS implementation uses a FIFO queue for serving the aperiodic
		1841	requests of the Module's tasks. Only the first task is put in the
		1842	ready queue of the master module.
		1843
		1844	%----------------------------------------------------------------------------
		1845	\chapter{Sharing resource access protocols}
		1846	%----------------------------------------------------------------------------
		1847
		1848	%----------------------------------------------------------------------------
		1849	\section{CABS}
		1850	%----------------------------------------------------------------------------
		1851
		1852	\paragraph{Description:}
		1853
		1854	This module implements the Cyclical Asynchronous Buffers as
		1855	described in the Volume I of the User Manual.
		1856
		1857	Note that the Maximum number of CABs that can be created is
		1858	MAX\_CAB (defined in include/modules/cabs.h).
		1859
		1860	\paragraph{Usage:}
		1861
		1862	To register this module, just put this line into the
		1863	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1864
		1865	\texttt{CABS\_register\_module();}
		1866
		1867	\paragraph{Files:}
		1868
		1869	\texttt{modules/cabs/*}
		1870
		1871	%----------------------------------------------------------------------------
		1872	\section{HARTPORT}
		1873	%----------------------------------------------------------------------------
		1874
		1875	\paragraph{Description:}
		1876
		1877	This module implements the Communication Ports as described in the
		1878	Volume I of the User Manual.
		1879
		1880	\paragraph{Usage:}
		1881
		1882	To register this module, just put this line into the \texttt{\_\_init\_\_} task
		1883	\footnote{or in any other task; in any case this function has to be called
		1884	before using the port primitives}:
		1885
		1886	\texttt{HARTPORT\_init();}
		1887
		1888	\paragraph{IMPORTANT: }
		1889
		1890	Remember that to get the ports running, you need to register also
		1891	the SEM module!
		1892
		1893	\paragraph{Files:}
		1894
		1895	\texttt{modules/hartport/*}
		1896
		1897	%----------------------------------------------------------------------------
		1898	\section{NOP (NO Protocol)}
		1899	%----------------------------------------------------------------------------
		1900
		1901	\paragraph{Resource Models Accepted:}
		1902
		1903	None.
		1904
		1905	\paragraph{Description:}
		1906
		1907	The NOP Module implements a binary semaphore using the mutex
		1908	interface. If a task owns a mutex, it can not lock that mutex
		1909	again until it has unlocked it. This protocol can produce priority
		1910	inversions and chained blocking.
		1911
		1912	\paragraph{Exceptions Raised:}
		1913
		1914	None
		1915
		1916	\paragraph{Usage:}
		1917
		1918	To register this module, just put this line into the
		1919	\texttt{\_\_kernel\_register\_levels\_\_} function:
		1920
		1921	\texttt{NOP\_register\_module();}
		1922
		1923	The NOP protocol uses the default mutex mechanism provided by the
		1924	Kernel. In that way, the NOP behaviour for a mutex can be set at
		1925	run-time, and the applications can choose the protocol of their
		1926	mutexes without changing the task source code.
		1927
		1928	To initialize a NOP mutex, you need to call \texttt{mutex\_init()}
		1929	passing a previously initialized \texttt{NOP\_mutexattr\_t}.
		1930
		1931	In the following example, the demo task uses two resources,
		1932	labeled with \texttt{m1} and \texttt{m2}, and accesses three
		1933	different critical sections:
		1934
		1935	\begin{tt}
		1936	\begin{verbatim}
		1937	#include <modules/nop.h>
		1938	...
		1939
		1940	mutex_t m1,m2;
		1941	...
		1942
		1943	void demo(void arg) {
		1944	...
		1945
		1946	mutex_lock(&m1);
		1947
		1948	/* critical section of m1 */
		1949	...
		1950
		1951	mutex_unlock(&m1);
		1952	...
		1953
		1954	mutex_lock(&m1);
		1955
		1956	/* only m1 locked */
		1957	...
		1958
		1959	mutex_lock(&m2);
		1960
		1961	/* m1 and m2 locked */
		1962	...
		1963
		1964	mutex_unlock(&m2); /* NOTE: first m2, then m1! */
		1965	mutex_unlock(&m1);
		1966	...
		1967
		1968	return 0;
		1969	}
		1970
		1971	...
		1972
		1973	int main(int argc, char **argv) {
		1974	HARD_TASK_MODEL m;
		1975	PID p0, p1, p2;
		1976
		1977	NOP_mutexattr_t a;
		1978
		1979	/* Initialize the NOP mutexes */
		1980	NOP_mutexattr_default(a);
		1981	mutex_init(&m1, &a);
		1982	mutex_init(&m2, &a);
		1983	...
		1984
		1985	/* Create the task */
		1986	hard_task_default_model(m);
		1987	hard_task_def_mit(m, 1000000);
		1988	hard_task_def_wcet(m, 80000);
		1989	p0 = task_create("DEMO", demo, &m, NULL);
		1990	...
		1991	}
		1992	\end{verbatim}
		1993	\end{tt}
		1994
		1995	Critical sections must be properly nested (like Chinese boxes):
		1996	hence the order of the \texttt{mutex\_unlock(m1)} and
		1997	\texttt{mutex\_unlock(m2)} primitives cannot be changed without
		1998	modifying the corresponding \texttt{mutex\_lock()}.
		1999
		2000	\paragraph{Note:}
		2001
		2002	NOP Mutexes can be statically allocated. See
		2003	\texttt{include/modules/nop.h} for details.
		2004
		2005	\paragraph{Note:}
		2006
		2007	A task can use NOP mutexes with other mutexes with different
		2008	protocol (for example, PI, PC, SRP mutexes). We don't know the
		2009	behaviour of that choice, but, if you want to try, it works!
		2010
		2011	\paragraph{Files:}
		2012
		2013	\texttt{modules/nop/*}
		2014
		2015	\paragraph{Implementation hints:}
		2016
		2017	The implementation of the NOP mutexes is similar to the internal
		2018	semaphores.
		2019
		2020	%----------------------------------------------------------------------------
		2021	\section{NOPM (NO Protocol Multiple lock)}
		2022	%----------------------------------------------------------------------------
		2023
		2024	\paragraph{Resource Models Accepted:}
		2025
		2026	None.
		2027
		2028	\paragraph{Description:}
		2029
		2030	The NOP Module implements a binary semaphore using the mutex
		2031	interface. If a task owns a mutex, it can lock that mutex again.
		2032	It is like the NOP Module, but the owner of the mutex can issue
		2033	multiple lock/unlock on mutex. This protocol can produce priority
		2034	inversions and chained blocking.
		2035
		2036	\paragraph{Exceptions Raised:}
		2037
		2038	None
		2039
		2040	\paragraph{Usage:}
		2041
		2042	To register this module, just put this line into the
		2043	\texttt{\_\_kernel\_register\_levels\_\_} function:
		2044
		2045	\texttt{NOPM\_register\_module();}
		2046
		2047	The NOPM protocol uses the default mutex mechanism provided by the
		2048	Kernel. In that way, the NOPM behaviour for a mutex can be set at
		2049	run-time, and the applications can choose the protocol of their
		2050	mutexes without changing the task source code.
		2051
		2052	To initialize a NOPM mutex, you need to call
		2053	\texttt{mutex\_init()} passing a previously initialized
		2054	\texttt{NOPM\_mutexattr\_t}.
		2055
		2056	In the following example, the demo task uses two resources,
		2057	labeled with \texttt{m1} and \texttt{m2}, and accesses three
		2058	different critical sections:
		2059
		2060	\begin{tt}
		2061	\begin{verbatim}
		2062	#include <modules/nopm.h>
		2063	...
		2064
		2065	mutex_t m1, m2;
		2066	...
		2067
		2068	void demo(void arg) {
		2069	...
		2070
		2071	mutex_lock(&m1);
		2072
		2073	/* critical section of m1 */
		2074	...
		2075
		2076	mutex_unlock(&m1);
		2077	...
		2078
		2079	mutex_lock(&m1);
		2080
		2081	/* only m1 locked */
		2082	...
		2083
		2084	mutex_lock(&m2);
		2085
		2086	/* m1 and m2 locked */
		2087	...
		2088
		2089	mutex_unlock(&m2); /* NOTE: first m2, then m1! */
		2090	mutex_unlock(&m1);
		2091	...
		2092
		2093	return 0;
		2094	}
		2095
		2096	...
		2097
		2098	int main(int argc, char **argv) {
		2099	HARD_TASK_MODEL m;
		2100	PID p0, p1, p2;
		2101
		2102	NOPM_mutexattr_t a;
		2103
		2104	/* Initialize the NOP mutexes */
		2105	NOPM_mutexattr_default(a);
		2106	mutex_init(&m1, &a);
		2107	mutex_init(&m2, &a);
		2108	...
		2109
		2110	/* Create the task */
		2111	hard_task_default_model(m);
		2112	hard_task_def_mit(m, 1000000);
		2113	hard_task_def_wcet(m, 80000);
		2114	p0 = task_create("DEMO", demo, &m, NULL);
		2115	...
		2116	}
		2117	\end{verbatim}
		2118	\end{tt}
		2119
		2120	Critical sections must be properly nested (like Chinese boxes):
		2121	hence the order of the \texttt{mutex\_unlock(m1)} and
		2122	\texttt{mutex\_unlock(m2)} primitives cannot be changed without
		2123	modifying the corresponding \texttt{mutex\_lock()}.
		2124
		2125	\paragraph{Note:}
		2126
		2127	A task can use NOPM mutexes with other mutexes with different
		2128	protocol (for example, PI, PC, SRP mutexes). We don't know the
		2129	behaviour of that choice, but, if you want to try, it works!
		2130
		2131	\paragraph{Files:}
		2132
		2133	\texttt{modules/nopm/*}
		2134
		2135	\paragraph{Implementation hints:}
		2136
		2137	The implementation of the NOPM mutexes is similar to the NOP
		2138	implementation, except that it counts the numer of times a task
		2139	locked a mutex.
		2140
		2141	%----------------------------------------------------------------------------
		2142	\section{NPP (Non Preemptive Protocol)}
		2143	%----------------------------------------------------------------------------
		2144
		2145	\paragraph{Resource Models Accepted:}
		2146
		2147	None.
		2148
		2149	\paragraph{Description:}
		2150
		2151	The NPP Module implements a binary semaphore using the mutex
		2152	interface. The difference with the NOP Module is that when a task
		2153	lock a NPP mutex, it became non-preemptive as it called the
		2154	\texttt{task\_nopreempt()} primitive. Critical section can be
		2155	nested.
		2156
		2157	\paragraph{Exceptions Raised:}
		2158
		2159	\begin{description}
		2160	\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
		2161	ends and it owns one or more mutexes.
		2162	\end{description}
		2163
		2164	\paragraph{Usage:}
		2165
		2166	To register this module, just put this line into the
		2167	\texttt{\_\_kernel\_register\_levels\_\_} function:
		2168
		2169	\texttt{NPP\_register\_module();}
		2170
		2171	The NPP protocol uses the default mutex mechanism provided by the
		2172	Kernel. In that way, the NPP behaviour for a mutex can be set at
		2173	run-time, and the applications can choose the protocol of their
		2174	mutexes without changing the task source code.
		2175
		2176	To initialize a NPP mutex, you need to call \texttt{mutex\_init()}
		2177	passing a previously initialized \texttt{NPP\_mutexattr\_t}.
		2178
		2179	In the following example, the demo task uses two resources,
		2180	labeled with \texttt{m1} and \texttt{m2}, and accesses three
		2181	different critical sections:
		2182
		2183	\begin{tt}
		2184	\begin{verbatim}
		2185	#include <modules/npp.h>
		2186	...
		2187
		2188	mutex_t m1,m2;
		2189	...
		2190
		2191	void demo(void arg) {
		2192	...
		2193
		2194	mutex_lock(&m1);
		2195
		2196	/* critical section of m1 */
		2197	...
		2198
		2199	mutex_unlock(&m1);
		2200	...
		2201
		2202	mutex_lock(&m1);
		2203
		2204	/* only m1 locked */
		2205	...
		2206
		2207	mutex_lock(&m2);
		2208
		2209	/* m1 and m2 locked */
		2210	...
		2211
		2212	mutex_unlock(&m2); /* NOTE: first m2, then m1! */
		2213	mutex_unlock(&m1);
		2214	...
		2215
		2216	return 0;
		2217	}
		2218
		2219	...
		2220
		2221	int main(int argc, char **argv) {
		2222	HARD_TASK_MODEL m;
		2223	PID p0, p1, p2;
		2224	NPP_mutexattr_t a;
		2225
		2226	/* Initialize the NOP mutexes */
		2227	NPP_mutexattr_default(a);
		2228	mutex_init(&m1,&a);
		2229	mutex_init(&m2,&a);
		2230	...
		2231
		2232	/* Create the task */
		2233	hard_task_default_model(m);
		2234	hard_task_def_mit(m, 1000000);
		2235	hard_task_def_wcet(m, 80000);
		2236	p0 = task_create("DEMO", demo, &m, NULL);
		2237	...
		2238	}
		2239	\end{verbatim}
		2240	\end{tt}
		2241
		2242	Critical sections must be properly nested (like Chinese boxes):
		2243	hence the order of the \texttt{mutex\_unlock(m1)} and
		2244	\texttt{mutex\_unlock(m2)} primitives cannot be changed without
		2245	modifying the corresponding \texttt{mutex\_lock()}.
		2246
		2247	\paragraph{Note:}
		2248
		2249	A task can use NPP mutexes with other mutexes with different
		2250	protocol (for example, PI, PC, SRP mutexes; except for nested
		2251	critical sections). We don't know the behaviour of that choice,
		2252	but, if you want to try, it works!
		2253
		2254	\paragraph{Files:}
		2255
		2256	\texttt{modules/npp/*}
		2257
		2258	\paragraph{Implementation hints:}
		2259
		2260	The implementation of the NPP Module counts the number of locks a
		2261	task issued and uses
		2262	\texttt{task\_preempt()}/\texttt{task\_nopreempt()} to implement
		2263	the protocol.
		2264
		2265	%----------------------------------------------------------------------------
		2266	\section{PC (Priority Ceiling)}
		2267	%----------------------------------------------------------------------------
		2268
		2269	\paragraph{Resource Models Accepted:}
		2270
		2271	\begin{description}
		2272	\item [PC\_RES\_MODEL]- Task priority. This model have to be used
		2273	to tell to the PC Module that a task have to be scheduled
		2274	following the PC rules. The model can be passed at creation time
		2275	to more than one task, and it only contains the priority
		2276	information.
		2277	\end{description}
		2278
		2279	\paragraph{Description:}
		2280
		2281	This Module implements the Priority Ceiling (PC) Protocol. This
		2282	mechanism can be easily applied to Fixed Priority Scheduling to
		2283	bound blocking times and to eliminate chained blocking and
		2284	deadlocks.
		2285
		2286	\paragraph{Exceptions Raised:}
		2287
		2288	\begin{description}
		2289	\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
		2290	ends and it owns one or more PC mutexes.
		2291	\end{description}
		2292
		2293	\paragraph{Usage:}
		2294
		2295	To register this module, just put this line into the
		2296	\texttt{\_\_kernel\_register\_levels\_\_} function:
		2297
		2298	\texttt{PC\_register\_module();}
		2299
		2300	The PC protocol uses the default mutex mechanism provided by the
		2301	Kernel. In that way, the PC behaviour for a mutex can be set at
		2302	run-time, and the applications can choose the protocol of their
		2303	mutexes without changing the task source code.
		2304
		2305	To initialize a PC mutex, you need to call \texttt{mutex\_init()}
		2306	passing a previously initialized \texttt{PC\_mutexattr\_t}, that
		2307	contains the ceiling of the mutex.
		2308
		2309	To apply the Priority Ceiling protocol to a task, you need to tell the Module
		2310	what is the priority of that task \footnote{Also a task that have to be
		2311	scheduled using the PC rules but without using any PC mutex must declare its
		2312	priority!}. That information is given ti the Module using a Resource Model of
		2313	type \texttt{PC\_RES\_MODEL} at task creation time (in other words, to the
		2314	\texttt{task\_createn} primitive). That model have to be previously initialized
		2315	with the priority of the task.
		2316
		2317	Note that the priority value used by the PC Module may differ from
		2318	the priority of the scheduling algorithm that really schedule the
		2319	tasks. Typically, priorities are set to the same (or equipollent)
		2320	values.
		2321
		2322	In the following example, the demo task uses two resources,
		2323	labeled with \texttt{m1} and \texttt{m2}, and accesses three
		2324	different critical sections:
		2325
		2326	\begin{tt}
		2327	\begin{verbatim}
		2328	#include <modules/pc.h>
		2329	...
		2330
		2331	mutex_t m1,m2;
		2332	...
		2333
		2334	void demo(void arg) {
		2335	...
		2336
		2337	mutex_lock(&m1);
		2338
		2339	/* critical section of m1 */
		2340	...
		2341
		2342	mutex_unlock(&m1);
		2343	...
		2344
		2345	mutex_lock(&m1);
		2346
		2347	/* only m1 locked */
		2348	...
		2349
		2350	mutex_lock(&m2);
		2351
		2352	/* m1 and m2 locked */
		2353	...
		2354
		2355	mutex_unlock(&m2); /* NOTE: first m2, then m1! */
		2356	mutex_unlock(&m1);
		2357	...
		2358
		2359	return 0;
		2360	}
		2361	...
		2362
		2363	int main(int argc, char **argv) {
		2364	HARD_TASK_MODEL m;
		2365	PID p0, p1, p2;
		2366
		2367	PC_mutexattr_t a;
		2368	PC_RES_MODEL r;
		2369
		2370	/* Initialize the SRP mutexes */
		2371	PC_mutexattr_default(a,1); /* 1 is the pr. level */
		2372	mutex_init(&m1,&a);
		2373	mutex_init(&m2,&a);
		2374	...
		2375
		2376	/* Create the task */
		2377	hard_task_default_model(m);
		2378	hard_task_def_mit(m, 1000000);
		2379	hard_task_def_wcet(m, 80000);
		2380	PC_res_default_model(r, 1); /* set the task Priority */
		2381
		2382	p0 = task_create("DEMO", demo, &m, &r);
		2383	...
		2384	}
		2385	\end{verbatim}
		2386	\end{tt}
		2387
		2388	Critical sections must be properly nested (like Chinese boxes):
		2389	hence the order of the \texttt{mutex\_unlock(m1)} and
		2390	\texttt{mutex\_unlock(m2)} primitives cannot be changed without
		2391	modifying the corresponding \texttt{mutex\_lock()}.
		2392
		2393	The Module also provides three functions that are used to
		2394	implement similar POSIX functions. Typically the user does not
		2395	need to call them.
		2396
		2397	\texttt{int PC\_get\_mutex\_ceiling(const mutex\_t *mutex, DWORD
		2398	*ceiling);}
		2399
		2400	This function gets the ceiling of a PC mutex, and it have to be
		2401	called only by a task that owns the mutex. Returns -1 if the mutex
		2402	is not a PC mutex, 0 otherwise.
		2403
		2404	\texttt{int PC\_set\_mutex\_ceiling(mutex\_t *mutex, DWORD
		2405	ceiling, DWORD *old\_ceiling);}
		2406
		2407	This function sets the ceiling of a PC mutex, and it have to be
		2408	called only by a task that owns the mutex. Returns -1 if the mutex
		2409	is not a PC mutex, 0 otherwise.
		2410
		2411	\texttt{void PC\_set\_task\_ceiling(RLEVEL r, PID p, DWORD
		2412	priority);}
		2413
		2414	This function sets the priority of a task.
		2415
		2416	\paragraph{Note:}
		2417
		2418	The Real-Time Literature typically found a feasibility test for
		2419	the scheduling only in the case that all hard tasks use the PC
		2420	protocol. Note that the Module is written in a way that only the
		2421	tasks that declared their Priority will use the PC protocol. If a
		2422	task that does not have a Priority, it is not scheduled using the
		2423	PC protocol, also if it is inserted in the same scheduling queue
		2424	of PC tasks.
		2425
		2426	\paragraph{Note:}
		2427
		2428	A task can use PC mutexes with other mutexes with different
		2429	protocol (for example, PI, SRP, NOP mutexes). We don't know the
		2430	behaviour of that choice, but, if you want to try, it works!
		2431
		2432	\paragraph{Files:}
		2433
		2434	\texttt{modules/pc/*}
		2435
		2436	\paragraph{Implementation hints:}
		2437
		2438	The PC Module uses the shadow mechanism to implement its
		2439	behaviour. It keeps track of all the locked mutexes to block
		2440	(setting the shadow field to the mutex owner) a task that requires
		2441	a lock on a mutex with ceiling less than the system ceiling. When
		2442	unlocking, all the shadows are reset. At that point they will try
		2443	again to reaquire the mutex, that time starting from the highest
		2444	priority task in the scheduling queue.
		2445
		2446	%----------------------------------------------------------------------------
		2447	\section{PI (Priority Inheritance)}
		2448	%----------------------------------------------------------------------------
		2449
		2450	\paragraph{Resource Models Accepted:}
		2451
		2452	None.
		2453
		2454	\paragraph{Description:}
		2455
		2456	This Module implements the Priority Inheritance mechanism. This
		2457	mechanism can be easily applied to Fixed Priority Scheduling to
		2458	bound blocking times.
		2459
		2460	\paragraph{Exceptions Raised:}
		2461
		2462	\begin{description}
		2463	\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
		2464	ends and it owns one or more PI mutexes.
		2465	\end{description}
		2466
		2467	\paragraph{Usage:}
		2468
		2469	To register this module, just put this line into the
		2470	\texttt{\_\_kernel\_register\_levels\_\_} function:
		2471
		2472	\texttt{PI\_register\_module();}
		2473
		2474	The PI protocol uses the default mutex mechanism provided by the
		2475	Kernel. In that way, the PI behaviour for a mutex can be set at
		2476	run-time, and the applications can choose the protocol of their
		2477	mutexes without changing the task source code.
		2478
		2479	To initialize a PI mutex, you need to call \texttt{mutex\_init()}
		2480	passing a previously initialized \texttt{PI\_mutexattr\_t}.
		2481
		2482	In the following example, the demo task uses two resources,
		2483	labeled with \texttt{m1} and \texttt{m2}, and accesses three
		2484	different critical sections:
		2485
		2486	\begin{tt}
		2487	\begin{verbatim}
		2488	#include <modules/pi.h>
		2489	...
		2490
		2491	mutex_t m1,m2;
		2492	...
		2493
		2494	void demo(void arg) {
		2495	...
		2496
		2497	mutex_lock(&m1);
		2498
		2499	/* critical section of m1 */
		2500	...
		2501
		2502	mutex_unlock(&m1);
		2503	...
		2504
		2505	mutex_lock(&m1);
		2506
		2507	/* only m1 locked */
		2508	...
		2509
		2510	mutex_lock(&m2);
		2511
		2512	/* m1 and m2 locked */
		2513	...
		2514
		2515	mutex_unlock(&m2); /* NOTE: first m2, then m1! */
		2516	mutex_unlock(&m1);
		2517	...
		2518
		2519	return 0;
		2520	}
		2521	...
		2522
		2523	int main(int argc, char **argv) {
		2524	HARD_TASK_MODEL m;
		2525	PID p0, p1, p2;
		2526
		2527	PI_mutexattr_t a;
		2528
		2529	/* Initialize the SRP mutexes */
		2530	PI_mutexattr_default(a);
		2531	mutex_init(&m1,&a);
		2532	mutex_init(&m2,&a);
		2533	...
		2534
		2535	/* Create the task */
		2536	hard_task_default_model(m);
		2537	hard_task_def_mit(m, 1000000);
		2538	hard_task_def_wcet(m, 80000);
		2539	p0 = task_createn("DEMO", demo, &m, NULL);
		2540	...
		2541	}
		2542	\end{verbatim}
		2543	\end{tt}
		2544
		2545	Critical sections must be properly nested (like Chinese boxes):
		2546	hence the order of the \texttt{mutex\_unlock(m1)} and
		2547	\texttt{mutex\_unlock(m2)} primitives cannot be changed without
		2548	modifying the corresponding \texttt{mutex\_lock()}.
		2549
		2550	\paragraph{Note:}
		2551
		2552	A task can use PI mutexes with other mutexes with different
		2553	protocol (for example, SRP, PC, NOP mutexes). We don't know the
		2554	behaviour of that choice, but, if you want to try, it works!
		2555
		2556	\paragraph{Files:}
		2557
		2558	\texttt{modules/pi/*}
		2559
		2560	\paragraph{Implementation hints:}
		2561
		2562	This is the simplest protocol that can be implemented using the
		2563	shadows mechanism. The implementation set the shadow field when a
		2564	task blocks, and reset it when the mutex is unlocked. At that
		2565	point, the highest priority free task will lock the mutex.
		2566
		2567	%----------------------------------------------------------------------------
		2568	\section{SEM (POSIX Semaphores)}
		2569	%----------------------------------------------------------------------------
		2570
		2571	\paragraph{Description:}
		2572
		2573	This module implements the POSIX Semaphores as described in the
		2574	Volume I of the User Manual.
		2575
		2576	\paragraph{Usage:}
		2577
		2578	To register this module, just put this line into the
		2579	\texttt{\_\_kernel\_register\_levels\_\_} function:
		2580
		2581	\texttt{SEM\_register\_module();}
		2582
		2583	\paragraph{Files:}
		2584
		2585	\texttt{modules/sem/*}
		2586
		2587	\paragraph{Implementation hints:}
		2588
		2589	The implementation uses a fixed number of semaphores (note that
		2590	Internal Semaphores does not!). Note the use of
		2591	\texttt{task\_testcancel()} to implement the cancellation points.
		2592
		2593	%----------------------------------------------------------------------------
		2594	\section{SRP (Stack Resource Policy)}
		2595	%----------------------------------------------------------------------------
		2596
		2597	\paragraph{Resource Models Accepted:}
		2598
		2599	\begin{description}
		2600	\item [SRP\_RES\_MODEL]- Preemption levels. This model have to be
		2601	used to tell to the SRP Module that a task have to be scheduled
		2602	following the SRP rules. The model can be passed at creation time
		2603	to more than one task, and it only contains the preemption level
		2604	information.
		2605	\end{description}
		2606
		2607	\paragraph{Description:}
		2608
		2609	\emph{Stack Resource Policy} (SRP) is a mutual exclusion mechanism
		2610	suitable for hard real-time tasks, that can be used with static or
		2611	dynamic scheduling algorithms. Its main feature is the property
		2612	that a task is blocked not when it tries to use the resource, but
		2613	when it tries to preempt another task owning the shared resource.
		2614	This early blocking simplifies the protocol implementation and
		2615	reduces the number of context switches, increasing the system
		2616	efficiency.
		2617
		2618	This SRP implementation provides a simplified version of the protocol, suitable
		2619	only for single-unit resources, that defines a particular behaviour for the
		2620	\texttt{mutex\_XXX} primitives. Moreover, it is implemented using the shadows
		2621	mechanism (described in the S.Ha.R.K. architecture manual), so there is no
		2622	restriction on the Task Models of the tasks that will use SRP \footnote{However,
		2623	note that a schedulability test is only available for EDF and RM schedulers.}.
		2624
		2625	SRP is implemented associating a dynamic priority $p(\tau)$ and a
		2626	preemption level $\pi(\tau)$ to each task $\tau$. If an EDF
		2627	scheduler is used to schedule the tasks that use SRP, we can say
		2628	that the priority $p(\tau)$ of task $\tau$ is proportional to
		2629	$1/d$, where $d$ is the task's absolute deadline, while the
		2630	preemption level $\pi(\tau)$ is proportional to $1/D$, where $D$
		2631	is the tasks's relative deadline.
		2632
		2633	Each resource is assigned a dynamic \emph{priority ceiling}
		2634	$C_{R}$, defined as:
		2635	\[
		2636	C_{R}=max\{0\},\;\{\pi(\tau):R\in R(\tau)\, and\, Rsbusy\}
		2637	\]
		2638
		2639	\noindent where $R(\tau)$ is the set of all resources used by task
		2640	$\tau$. According to this definition, if a resource is free, its
		2641	ceiling is 0; if a resource is busy, its ceiling is the maximum
		2642	among the preemption levels of tasks using it. A \emph{System
		2643	Ceiling} $\Pi_{S}$ is also defined as the maximum ceiling among
		2644	all the resources:
		2645	\[
		2646	\Pi_{S}\;=\; max_{r}\{ C_{r}\;:\; r=1,\ldots,m\}.
		2647	\]
		2648
		2649	Starting from these definitions, the SRP works according to the
		2650	following rule:
		2651
		2652	\begin{quote}
		2653	\emph{The execution of a task is delayed until it becomes the task
		2654	having the highest priority and its preemption level is strictly
		2655	greater than the system ceiling.}
		2656	\end{quote}
		2657
		2658	Two tests are needed to allow a task to execute: a test on its
		2659	priority (i.e., the deadline, which is dynamically assigned) and a
		2660	test on the preemption level (which is statically determined).
		2661
		2662	The SRP protocol ensures that a task $\tau$, once started, cannot
		2663	be blocked on any resource until it terminates. Consequently, SRP
		2664	avoids unbounded priority inversion, blocking chains, and
		2665	deadlocks. It also reduces the number of context switches and
		2666	simplifies the implementation of the mechanism.
		2667
		2668	Since the SRP may be applied on various Scheduling Modules with
		2669	different scheduling policies, no guarantee or blocking time
		2670	calculations are performed by the Kernel.
		2671
		2672	The tasks that use SRP mutexes must declare the use of a shared
		2673	resource, using the provided resource modules.
		2674
		2675	Finally, note that this implementation of SRP is NOT compatible
		2676	with the join primitive. If a task that uses SRP mutexes calls
		2677	\texttt{task\_join} or \texttt{pthread\_join}, the result is
		2678	undefined.
		2679
		2680	\paragraph{Exceptions Raised:}
		2681
		2682	\begin{description}
		2683	\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
		2684	ends and it owns one or more SRP mutexes. \item
		2685	[XSRP\_UNVALID\_LOCK]This exception is raised when a task try to
		2686	lock a srp mutex but it don't have the privilege.
		2687	\end{description}
		2688
		2689	\paragraph{Usage:}
		2690
		2691	To register this module, just put this line into the
		2692	\texttt{\_\_kernel\_register\_levels\_\_} function:
		2693
		2694	\texttt{SRP\_register\_module();}
		2695
		2696	The SRP protocol uses the default mutex mechanism provided by the
		2697	Kernel. In that way, the SRP behaviour for a mutex can be set at
		2698	run-time, and the applications can choose the protocol of their
		2699	mutexes without changing the task source code.
		2700
		2701	To initialize a SRP mutex, you need to call \texttt{mutex\_init()}
		2702	passing a previously initialized \texttt{SRP\_mutexattr\_t}.
		2703
		2704	To use a SRP mutex, you need to tell the Module two kind of
		2705	informations:
		2706
		2707	\begin{itemize}
		2708	\item First, every task that have to be scheduled following the SRP rules must
		2709	have a (fixed) preemption level \footnote{Also a task that have to be scheduled
		2710	using the SRP rules but without using any SRP mutex must declare its preemption
		2711	level!}.
		2712	\item Second, every task must declare the mutexes that it will use during its
		2713	life.
		2714	\end{itemize}
		2715
		2716	All the two informations have to be given to the Module using
		2717	Resource Models.
		2718
		2719	To set a task preemption level you need to pass an
		2720	\texttt{SRP\_RES\_MODEL} at task creation time (in other words, to
		2721	the \texttt{task\_createn} primitive). That model have to be
		2722	previously initialized with the preemption level of the task.
		2723
		2724	To declare that a task will use a particular mutex, you have to
		2725	pass another Resource Model at task creation time. The Model you
		2726	need to pass is returned by the following function:
		2727
		2728	\texttt{RES\_MODEL SRP\_usemutex(mutex\_t m);}
		2729
		2730	where \texttt{m} is the SRP mutex the task will use.
		2731
		2732	In the following example, the demo task uses two resources,
		2733	labeled with \texttt{m1} and \texttt{m2}, and accesses three
		2734	different critical sections:
		2735
		2736	\begin{tt}
		2737
		2738	\begin{verbatim}
		2739	#include <modules/srp.h>
		2740	...
		2741
		2742	mutex_t m1,m2;
		2743	...
		2744
		2745	void demo(void arg) {
		2746	...
		2747
		2748	mutex_lock(&m1);
		2749
		2750	/* critical section of m1 */
		2751	...
		2752
		2753	mutex_unlock(&m1);
		2754	...
		2755
		2756	mutex_lock(&m1);
		2757	/* only m1 locked */
		2758	...
		2759
		2760	mutex_lock(&m2);
		2761
		2762	/* m1 and m2 locked */
		2763	...
		2764
		2765	mutex_unlock(&m2); /* NOTE: first m2, then m1! */
		2766	mutex_unlock(&m1);
		2767	...
		2768
		2769	return 0;
		2770	}
		2771	...
		2772
		2773	int main(int argc, char **argv) {
		2774	HARD_TASK_MODEL m;
		2775	PID p0, p1, p2;
		2776
		2777	SRP_mutexattr_t a;
		2778	SRP_RES_MODEL r;
		2779
		2780	/* Initialize the SRP mutexes */
		2781
		2782	SRP_mutexattr_default(a);
		2783	mutex_init(&m1,&a);
		2784	mutex_init(&m2,&a);
		2785	...
		2786
		2787	/* Create the task */
		2788	hard_task_default_model(m);
		2789	hard_task_def_mit(m, 1000000);
		2790	hard_task_def_wcet(m, 80000);
		2791	SRP_res_default_model(r, 3); /* set the task Preemption level */
		2792	p0 = task_createn("DEMO", demo, &m, &r, SRP_usemutex(&m1),
		2793	SRP_usemutex(&m2), NULL);
		2794	...
		2795	}
		2796	\end{verbatim}
		2797	\end{tt}
		2798
		2799	Critical sections must be properly nested (like Chinese boxes):
		2800	hence the order of the \texttt{mutex\_unlock(m1)} and
		2801	\texttt{mutex\_unlock(m2)} primitives cannot be changed without
		2802	modifying the corresponding \texttt{mutex\_lock()}.
		2803
		2804	\paragraph{Note:}
		2805
		2806	The Real-Time Literature typically found a feasibility test for the scheduling
		2807	only in the case that all hard tasks use the SRP protocol. Note that the Module
		2808	is written in a way that only the tasks that declared their Preemption Level
		2809	will use the SRP protocol. If a task that does not have a Preemption Level
		2810	\footnote{i.e., it was created without passing a \texttt{SRP\_RES\_MODEL} to the
		2811	\texttt{task\_createn} primitive.}, it is not scheduled using the SRP protocol,
		2812	also if it is inserted in the same scheduling queue of SRP tasks.
		2813
		2814	\paragraph{Note:}
		2815
		2816	A task can use SRP mutexes with other mutexes with different
		2817	protocol (for example, PI, PC, NOP mutexes). We don't know the
		2818	behaviour of that choice, but, if you want to try, it works!
		2819
		2820	\paragraph{Files:}
		2821
		2822	\texttt{modules/srp/*}
		2823
		2824	\paragraph{Implementation hints:}
		2825
		2826	Notes about the implementation of SRP are inserted in the heading
		2827	the source file \texttt{modules/srp/srp.c}.
		2828
		2829	%----------------------------------------------------------------------------
		2830	\chapter{File system Modules}
		2831	%----------------------------------------------------------------------------
		2832
		2833	%----------------------------------------------------------------------------
		2834	\section{BD\_EDF}
		2835	%----------------------------------------------------------------------------
		2836
		2837	TBD
		2838
		2839	%----------------------------------------------------------------------------
		2840	\section{BD\_PSCAN}
		2841	%----------------------------------------------------------------------------
		2842
		2843	TBD
		2844
		2845	\printindex{}
		2846
		2847	\bibliographystyle{alpha}
		2848	\bibliography{../common/biblio}
		2849
		2850	\end{document}

Subversion Repositories shark

(root)/sharkdoc/trunk/vol3/vol3.tex - Rev 1677