Subversion Repositories shark

Rev

Rev 993 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
882 trimarchi 1
/**
2
   \mainpage FSF reference
3
 
4
   This reference manual contains the description of the API provided
5
   by the FSF library.
6
 
7
   \section intro Introduction to FSF
8
 
9
   The First Scheduling Framework (FSF) is the result of a joint
10
   effort from four european research groups to propose an API for
929 lipari 11
   flexible real-time scheduling in Real Time operating systems.  See
993 lipari 12
   the FIRST web page <a
13
   href="http://130.243.76.81:8080/salsart/first/">
14
   (http://130.243.76.81:8080/salsart/first/)</a> for more details in
15
   the project.
882 trimarchi 16
 
17
   \section lib Objectives
18
 
929 lipari 19
Scheduling theory generally assumes that real-time systems are mostly
993 lipari 20
composed of activities with hard real-time requirements.
21
 
22
Many systems are built today by composing different application or
23
components in the same system, leading to a mixture of many different
24
kinds of requirements with small parts of the system having hard
25
real-time requirements and other larger parts with requirements for
26
more flexible scheduling, taking into account quality of service. Hard
929 lipari 27
real-time scheduling techniques are extremely pessimistic for the
28
latter part of the application, and consequently it is necessary to
29
use techniques that let the system resources be fully utilized to
30
achieve the highest possible quality.
882 trimarchi 31
 
929 lipari 32
The FIRST project aims at developing a framework for a scheduling
33
architecture that provides the ability to compose several applications
34
or components into the system, and to flexibly schedule the available
35
resources while guaranteeing hard real-time requirements. The FIRST
36
Scheduling Framework (FSF) is independent of the underlying
37
implementation, and can run on different underlying scheduling
38
strategies. It is based on establishing service contracts that
39
represent the complex and flexible requirements of the application,
40
and which are managed by the underlying system to provide the required
41
level of service.
882 trimarchi 42
 
929 lipari 43
FSF provides a generalized architecture framework that combines
44
different kinds of requirements:
882 trimarchi 45
 
929 lipari 46
 - co-operation and coexistence of standard real-time scheduling
993 lipari 47
   schemes, time triggered and event triggered, dynamic and fixed
929 lipari 48
   priority based, as well as off-line based through a common
49
   architecture that is independent on the underlying scheduling
50
   mechanism
882 trimarchi 51
 
929 lipari 52
- integration of different timing requirements such as hard and soft,
53
  and more flexible notions
882 trimarchi 54
 
929 lipari 55
- temporal encapsulation of subsystems in order to support the
56
  composability and reusability of available components including
57
  legacy subsystems.
58
 
59
FSF has been implemented in two POSIX compliant real-time operating
60
systems, <a href="http://marte.unican.es">MaRTE</a> and <a
61
href="http://shark.sssup.it/">SHARK</a>, which are based on FP and EDF
62
scheduling schemes, respectively, thus illustrating the platform
63
independence of the presented approach.
64
 
65
   \section Service Contracts
66
 
67
The service contract is the mechanism that we have chosen for the
68
application to dynamically specify its own set of complex and flexible
993 lipari 69
execution requirements. From the application's perspective, the
929 lipari 70
requirements of an application or application component are written as
71
a set of service contracts, which are negotiated with the underlying
72
implementation. To accept a set of contracts, the system has to check
73
as part of the negotiation if it has enough resources to guarantee all
74
the minimum requirements specified, while keeping guarantees on all
75
the previously accepted contracts negotiated by other application
76
components. If as a result of this negotiation the set of contracts is
77
accepted, the system will reserve enough capacity to guarantee the
78
minimum requested resources, and will adapt any spare capacity
79
available to share it among the different contracts that have
80
specified their desire or ability for using additional capacity.
81
 
82
 
83
As a result of the negotiation process, if a contract is accepted, a
84
server is created for it. The server is a software object that is the
85
run-time representation of the contract; it stores all the information
86
related to the resources currently reserved for that contract, the
87
resources already consumed, and the resources required to handle the
88
budget consumption and replenishment events in the particular
89
operating system being used.
90
 
91
Because there are various application requirements specified in the
92
contract, they are divided into several groups, also allowing the
93
underlying implementation to give different levels of support trading
94
them against implementation complexity. This gives way to a modular
95
implementation of the framework, with each module addressing specific
96
application requirements. The minimum resources required by the
97
application to be reserved by the system are specified in the core
98
module. The requirements for mutual exclusive synchronization among
99
parts of the application being scheduled by different servers or among
100
different applications are specified in the shared objects
101
module. Flexible resource usage is associated with the spare capacity
102
and dynamic reclamation modules. The ability to compose applications
103
or application components with several threads of control, thus
104
requiring hierarchical scheduling of several threads inside the same
105
server are supported by the hierarchical scheduling module. Finally,
106
the requirements of distributed applications are supported by the
107
distributed and the distributed spare capacity modules. We will now
108
explain these modules together with their associated application
109
requirements.
110
 
111
 
882 trimarchi 112
 */
113
 
114
/**
115
   \defgroup coremodule Core module
116
 
929 lipari 117
The core module contains the service contract information related to
118
the application minimum resource requirements, the operations required
119
to create contracts and negotiate them, and the underlying
120
implementation of the servers with a resource reservation mechanism
121
that allows the system to guarantee the resources granted to each
122
server.
123
 
882 trimarchi 124
   This module includes the basic functions and services that are
125
   provided by any FSF implementation. This module includes basic type
126
   definitions, and functions to
127
 
128
   - create a contract and initialize it
129
   - set/get the basic parameters of a contract
130
   - negotiate a service contract, obtaining a server id
131
   - create and bind threads to servers
132
   - create/destroy a synchronization object
133
   - manage bounded workloads
993 lipari 134
 
135
   A round-robin background scheduling policy is available for those
136
   threads that do not have real-time requirements. Because some of
137
   these threads may require sharing information with other threads
138
   run by regular servers, special background contracts may be created
139
   for specifying the synchronization requirements.
140
 
141
   The way of specifying a background contract is by setting
142
   budget_min = period_max = 0. Negotiation may fail if the contract
143
   uses shared_objects. If the contract has no shared_objects the
144
   returned server id represents the background and may be used to
145
   bind more than one thread. If the contract has shared objects a
146
   server is created to keep track of them, but the associated threads
147
   are executed in the background, together with the other background
148
   threads.
149
 
150
   An abstract synchronization object is defined by the application.
151
   This object can be used by an application to wait for an event to
152
   arrive by invoking the fsf_schedule_triggered_job() operation.  It
153
   can also be used to signal the event either causing a waiting
154
   server to wake up, or the event to be queued if no server is
155
   waiting for it.
156
 
157
   These objects are used to synchronize threads belonging to bounded
158
   workload servers.
159
 
160
   In the future we may add a broadcast operation that would signal a
161
   group of synchronization objects. We have not included a broadcast
162
   service in this version because it can be easily created by the
163
   user by signalling individual synchronization objects inside a
164
   loop.
165
 
166
   Notice that for synchronization objects there is no naming service
167
   like in shared objects because tasks that use synchronization are
168
   not developed independently, as they are closely coupled.
169
 
170
 
882 trimarchi 171
*/
172
 
173
/**
174
   \defgroup sparemodule Spare capacity sharing module
175
 
929 lipari 176
Many applications have requirements for flexibility regarding the
177
amount of resources that can be used. The spare capacity module allows
178
the system to share the spare capacity that may be left over from the
179
negotiation of the service contracts, in a static way. During the
180
negotiation, the minimum requested resources are granted to each
181
server, if possible. Then, if there is any extra capacity left, it is
182
distributed among those applications that have expressed their ability
183
to take advantage of it.
184
 
993 lipari 185
   This module includes functions for sharing the spare capacity in the
929 lipari 186
   system between the servers. It allows to mainly to specify
882 trimarchi 187
   additional contract parameters to allow the sharing of the spare
929 lipari 188
   capacity.
882 trimarchi 189
 
190
   The features provided by this module are different from the
191
   services provided by the Dynamic reclamation module. This module
993 lipari 192
   influences the negotiation procedure (see the \ref coremodule
929 lipari 193
   module).
882 trimarchi 194
 
195
 */
196
 
197
/**
198
   \defgroup hiermodule Hierarchical scheduling module
199
 
929 lipari 200
One of the application requirements that FSF addresses is the ability
201
to compose different applications, possibly using different scheduling
202
policies, into the same system. This can be addressed with support in
203
the system for hierarchical scheduling. The lower level is the
204
scheduler that takes care of the service contracts, using an
205
unspecified scheduling policy (for instance, a CBS on top of EDF, or a
206
sporadic server on top of fixed priorities). The top level is a
207
scheduler running inside one particular FSF server, and scheduling the
208
application threads with whatever scheduling policy they were
209
designed. In this way, it is possible to have in the same system one
210
application with, for example, fixed priorities, and another one
211
running concurrently with an EDF scheduler.
882 trimarchi 212
 
995 trimarchi 213
We are currently providing four top-level schedulers: fixed
214
priorities, EDF, round robin and table-driven.
882 trimarchi 215
 */
216
 
217
/**
218
   \defgroup shobjmodule Shared Objects module
219
 
929 lipari 220
The shared objects module of FSF allows the application to specify in
993 lipari 221
the contract attributes all the information related to the mutually
222
exclusive use of shared resources that is required to do the
223
schedulability analysis.
882 trimarchi 224
 
929 lipari 225
The set of shared objects present in the system together with the
226
lists of critical sections specified for each contract are used for
227
schedulability analysis purposes only. A run-time mechanism for mutual
228
exclusion is not provided in FSF for two important reasons. One of
229
them is upward compatibility of previous code using regular primitives
230
such as mutexes or protected objects (in Ada); this is a key issue if
231
we want to persuade application developers to switch their systems to
232
the FSF environment. The second reason is that enforcing worst case
233
execution time for critical sections is expensive. The number of
234
critical sections in real pieces of code may be very high, in the tens
235
or in the hundreds per task, and monitoring all of them would require
236
a large amount of system resources.
882 trimarchi 237
 
929 lipari 238
The FSF application does not depend on any particular synchronization
239
protocol, but there is a requirement that a budget expiration cannot
240
occur inside a critical section, because otherwise the blocking delays
241
could be extremely large. This implies that the application is allowed
242
to overrun its budget for the duration, at most, of the critical
243
section, and this extra budget is taken into account in the
244
schedulability analysis.
245
 
993 lipari 246
   Because shared objects are meant to be used by independent
247
   applications, there needs to be a way of identifying them through
248
   some global name. We use the type fsf_shared_object_id_t to
249
   represent these identifiers. To avoid potential name or identity
250
   conflicts between different independent applications we use a
251
   null-character-terminated string.
252
 
253
   For efficiency purposes, the contracts have smaller identifiers for
254
   the shared objects, that can be implemented with a pointer or an
255
   index to an array element.  Therefore conversion functions are
256
   necessary to convert a long identifier of type
257
   fsf_shared_object_id_t into a short handle to the object, of the
258
   type fsf_shared_obj_handle_t.  This conversion is done at the
259
   creation of the object (with fsf_init_shared_object), and there is
260
   also a function to obtain the handle after the object has been
261
   created (fsf_get_shared_object_handle).
262
 
263
   To make the use of shared objects in FSF independent of the
264
   underlying synchronization protocol, the function that initializes
265
   a shared object (fsf_init_shared_object) also initializes the mutex
266
   specified by the user with the appropriate, implementation-defined,
267
   attributes. Therefore, the application should not initialize the
268
   mutex itself, but should pass the mutex to this function call, and
269
   then use it with the regular POSIX interfaces to enter and leave
270
   critical sections. It is possible to obtain a pointer to the mutex
271
   from the shared object with the function
272
   fsf_get_shared_object_mutex.
882 trimarchi 273
 */
929 lipari 274
 
275
/**
276
   \defgroup distjmodule Distributed module
277
 
993 lipari 278
   FSF is designed to support applications with requirements for
279
   distribution. The first step towards distribution is the ability to
280
   support service contracts for the network or networks used to
281
   interconnect the different processing nodes in the system. Similar
282
   to the core FSF module, the contracts on the network allow the
283
   application to specify its minimum utilization (bandwidth)
284
   requirements, so that the implementation can make guarantees or
285
   reservations for that minimum utilization. We use the same contract
286
   that is used for processing nodes, and thus the core attributes for
287
   distribution are the same as for the core FSF with the addition of
288
   the network id attribute, that identifies the contract as a network
289
   contract for the specified network. The default value for the
290
   network id is null, which means that the contract applies to the
291
   processing node where the contact is negotiated.
929 lipari 292
 
993 lipari 293
   For the FSF implementation to keep track of consumed network
294
   resources and to enforce the budget guarantees it is necessary that
295
   the information is sent and received through specific FSF
296
   services. To provide communication in this context we need to
297
   create objects similar to the sockets used in most operating
298
   systems to provide message communication services. We call these
299
   objects communication endpoints, and we distinguish send and
300
   receive endpoints.
301
 
302
   A send endpoint contains information about the network to use, the
303
   destination node, and the port that identifies a reception
304
   endpoint. It is bound to a network server that specifies the
305
   scheduling parameters of the messages sent through that endpoint,
306
   keeps track of the resources consumed, and limits the bandwidth to
307
   the amount reserved for it by the system. It provides message
308
   buffering for storing messages that need to be sent.
309
 
310
   A receive endpoint contains information about the network and port
311
   number to use. It provides message buffering for storing the
312
   received messages until they are retrieved by the application. A
313
   receive endpoint may get messages sent from different send
314
   endpoints, possibly located in different processing nodes.
315
 
316
   This module provides communication and negotiation services to
317
   support the negotiation of independent servers on networks, as well
318
   as to offer the simple communications primitives that allow for
319
   accounting and limiting the network bandwidth used.
320
 
321
   The concrete protocol and communications hardware and software
322
   interfaces to use and whether the communication strategy over the
323
   real-time network is connection-oriented or not, are implementation
324
   dependent. The creation of endpoints will set them as
325
   appropriate.
326
 
327
   A node may negotiate contracts to reserve bandwidth for the sending
328
   of messages through the networks to which it is connected. It does
329
   not have to reserve bandwidth for incoming messages, just for
330
   outgoing messages.  A node cannot reserve bandwidth in networks to
331
   which it has no direct connection.
332
 
333
   As mentioned above, specific send and receive communication
334
   primitives are included to transfer messages while managing the
335
   bandwidth budget consumption. The send operation is non-blocking:
336
   it just copies the message into an internal buffer and returns
337
   immediately. The FSF network scheduler of the sender processor
338
   takes responsibility on accounting the bandwidth fraction used
339
   through each send endpoint, using the bandwidth reservation made by
340
   the network server that is bound to it.
341
 
342
   Considering that bandwidth reservations should be done in the form
343
   of number of bytes per time unit, that the speed of the network is
344
   quite variable from one platform to another, and that the regular
345
   FSF contract negotiation operations work with budgets expressed as
346
   CPU time, a function is added to convert the size of messages to
347
   the amount of time that is necessary to be used as the budget in
348
   the FSF contract.
349
 
929 lipari 350
 */
351
 
352
/**
353
   \defgroup distsparemodule Distributed spare capacity module
354
 
993 lipari 355
   In the distributed FSF we have chosen to give a minimum support for
356
   spare capacity distribution inside FSF, and leave the consensus
357
   problem related to the negotiation of end-to-end transactions to
358
   some higher-level manager that would make the negotiations for the
359
   application.
929 lipari 360
 
993 lipari 361
   There is a new attribute in the service contract called the granted
362
   capacity flag which, when set, has the implication that the period
363
   or budget of the server can only change if a renegotiation or a
364
   change of quality and importance is requested for it; it may not
365
   change automatically, for instance because of negotiations for
366
   other servers. This provides a stable framework while performing
367
   the distributed negotiation.
368
 
369
   For a server with the granted capacity flag set, there is an
370
   operation to return spare capacity that cannot be used due to
371
   restrictions in other servers of a distributed transaction.
929 lipari 372
 */