9,18 → 9,21 |
The First Scheduling Framework (FSF) is the result of a joint |
effort from four european research groups to propose an API for |
flexible real-time scheduling in Real Time operating systems. See |
<a href="http://130.243.76.81:8080/salsart/first/">the FIRST web |
page</a> for more details in the project. |
the FIRST web page <a |
href="http://130.243.76.81:8080/salsart/first/"> |
(http://130.243.76.81:8080/salsart/first/)</a> for more details in |
the project. |
|
\section lib Objectives |
|
Scheduling theory generally assumes that real-time systems are mostly |
composed of activities with hard real-time requirements, many systems |
are built today by composing different application or components in |
the same system, leading to a mixture of many different kinds of |
requirements with small parts of the system having hard real-time |
requirements and other larger parts with requirements for more |
flexible scheduling, taking into account quality of service. Hard |
composed of activities with hard real-time requirements. |
|
Many systems are built today by composing different application or |
components in the same system, leading to a mixture of many different |
kinds of requirements with small parts of the system having hard |
real-time requirements and other larger parts with requirements for |
more flexible scheduling, taking into account quality of service. Hard |
real-time scheduling techniques are extremely pessimistic for the |
latter part of the application, and consequently it is necessary to |
use techniques that let the system resources be fully utilized to |
41,7 → 44,7 |
different kinds of requirements: |
|
- co-operation and coexistence of standard real-time scheduling |
schemes, time-triggered and eventtriggered, dynamic and fixed |
schemes, time triggered and event triggered, dynamic and fixed |
priority based, as well as off-line based through a common |
architecture that is independent on the underlying scheduling |
mechanism |
63,7 → 66,7 |
|
The service contract is the mechanism that we have chosen for the |
application to dynamically specify its own set of complex and flexible |
execution requirements. From the application s perspective, the |
execution requirements. From the application's perspective, the |
requirements of an application or application component are written as |
a set of service contracts, which are negotiated with the underlying |
implementation. To accept a set of contracts, the system has to check |
128,6 → 131,43 |
- create and bind threads to servers |
- create/destroy a synchronization object |
- manage bounded workloads |
|
A round-robin background scheduling policy is available for those |
threads that do not have real-time requirements. Because some of |
these threads may require sharing information with other threads |
run by regular servers, special background contracts may be created |
for specifying the synchronization requirements. |
|
The way of specifying a background contract is by setting |
budget_min = period_max = 0. Negotiation may fail if the contract |
uses shared_objects. If the contract has no shared_objects the |
returned server id represents the background and may be used to |
bind more than one thread. If the contract has shared objects a |
server is created to keep track of them, but the associated threads |
are executed in the background, together with the other background |
threads. |
|
An abstract synchronization object is defined by the application. |
This object can be used by an application to wait for an event to |
arrive by invoking the fsf_schedule_triggered_job() operation. It |
can also be used to signal the event either causing a waiting |
server to wake up, or the event to be queued if no server is |
waiting for it. |
|
These objects are used to synchronize threads belonging to bounded |
workload servers. |
|
In the future we may add a broadcast operation that would signal a |
group of synchronization objects. We have not included a broadcast |
service in this version because it can be easily created by the |
user by signalling individual synchronization objects inside a |
loop. |
|
Notice that for synchronization objects there is no naming service |
like in shared objects because tasks that use synchronization are |
not developed independently, as they are closely coupled. |
|
|
*/ |
|
/** |
142,7 → 182,7 |
distributed among those applications that have expressed their ability |
to take advantage of it. |
|
This module include functions for sharing the spare capacity in the |
This module includes functions for sharing the spare capacity in the |
system between the servers. It allows to mainly to specify |
additional contract parameters to allow the sharing of the spare |
capacity. |
149,7 → 189,7 |
|
The features provided by this module are different from the |
services provided by the Dynamic reclamation module. This module |
influences the negotiation procedure (see the \ref core_negotiate |
influences the negotiation procedure (see the \ref coremodule |
module). |
|
*/ |
178,8 → 218,9 |
\defgroup shobjmodule Shared Objects module |
|
The shared objects module of FSF allows the application to specify in |
the contract attributes all the information required to do the |
schedulability analysis. |
the contract attributes all the information related to the mutually |
exclusive use of shared resources that is required to do the |
schedulability analysis. |
|
The set of shared objects present in the system together with the |
lists of critical sections specified for each contract are used for |
202,18 → 243,130 |
section, and this extra budget is taken into account in the |
schedulability analysis. |
|
Because shared objects are meant to be used by independent |
applications, there needs to be a way of identifying them through |
some global name. We use the type fsf_shared_object_id_t to |
represent these identifiers. To avoid potential name or identity |
conflicts between different independent applications we use a |
null-character-terminated string. |
|
For efficiency purposes, the contracts have smaller identifiers for |
the shared objects, that can be implemented with a pointer or an |
index to an array element. Therefore conversion functions are |
necessary to convert a long identifier of type |
fsf_shared_object_id_t into a short handle to the object, of the |
type fsf_shared_obj_handle_t. This conversion is done at the |
creation of the object (with fsf_init_shared_object), and there is |
also a function to obtain the handle after the object has been |
created (fsf_get_shared_object_handle). |
|
To make the use of shared objects in FSF independent of the |
underlying synchronization protocol, the function that initializes |
a shared object (fsf_init_shared_object) also initializes the mutex |
specified by the user with the appropriate, implementation-defined, |
attributes. Therefore, the application should not initialize the |
mutex itself, but should pass the mutex to this function call, and |
then use it with the regular POSIX interfaces to enter and leave |
critical sections. It is possible to obtain a pointer to the mutex |
from the shared object with the function |
fsf_get_shared_object_mutex. |
*/ |
|
/** |
\defgroup distjmodule Distributed module |
|
@todo Peppe complete description |
FSF is designed to support applications with requirements for |
distribution. The first step towards distribution is the ability to |
support service contracts for the network or networks used to |
interconnect the different processing nodes in the system. Similar |
to the core FSF module, the contracts on the network allow the |
application to specify its minimum utilization (bandwidth) |
requirements, so that the implementation can make guarantees or |
reservations for that minimum utilization. We use the same contract |
that is used for processing nodes, and thus the core attributes for |
distribution are the same as for the core FSF with the addition of |
the network id attribute, that identifies the contract as a network |
contract for the specified network. The default value for the |
network id is null, which means that the contract applies to the |
processing node where the contact is negotiated. |
|
For the FSF implementation to keep track of consumed network |
resources and to enforce the budget guarantees it is necessary that |
the information is sent and received through specific FSF |
services. To provide communication in this context we need to |
create objects similar to the sockets used in most operating |
systems to provide message communication services. We call these |
objects communication endpoints, and we distinguish send and |
receive endpoints. |
|
A send endpoint contains information about the network to use, the |
destination node, and the port that identifies a reception |
endpoint. It is bound to a network server that specifies the |
scheduling parameters of the messages sent through that endpoint, |
keeps track of the resources consumed, and limits the bandwidth to |
the amount reserved for it by the system. It provides message |
buffering for storing messages that need to be sent. |
|
A receive endpoint contains information about the network and port |
number to use. It provides message buffering for storing the |
received messages until they are retrieved by the application. A |
receive endpoint may get messages sent from different send |
endpoints, possibly located in different processing nodes. |
|
This module provides communication and negotiation services to |
support the negotiation of independent servers on networks, as well |
as to offer the simple communications primitives that allow for |
accounting and limiting the network bandwidth used. |
|
The concrete protocol and communications hardware and software |
interfaces to use and whether the communication strategy over the |
real-time network is connection-oriented or not, are implementation |
dependent. The creation of endpoints will set them as |
appropriate. |
|
A node may negotiate contracts to reserve bandwidth for the sending |
of messages through the networks to which it is connected. It does |
not have to reserve bandwidth for incoming messages, just for |
outgoing messages. A node cannot reserve bandwidth in networks to |
which it has no direct connection. |
|
As mentioned above, specific send and receive communication |
primitives are included to transfer messages while managing the |
bandwidth budget consumption. The send operation is non-blocking: |
it just copies the message into an internal buffer and returns |
immediately. The FSF network scheduler of the sender processor |
takes responsibility on accounting the bandwidth fraction used |
through each send endpoint, using the bandwidth reservation made by |
the network server that is bound to it. |
|
Considering that bandwidth reservations should be done in the form |
of number of bytes per time unit, that the speed of the network is |
quite variable from one platform to another, and that the regular |
FSF contract negotiation operations work with budgets expressed as |
CPU time, a function is added to convert the size of messages to |
the amount of time that is necessary to be used as the budget in |
the FSF contract. |
|
*/ |
|
/** |
\defgroup distsparemodule Distributed spare capacity module |
|
@todo Peppe complete description |
In the distributed FSF we have chosen to give a minimum support for |
spare capacity distribution inside FSF, and leave the consensus |
problem related to the negotiation of end-to-end transactions to |
some higher-level manager that would make the negotiations for the |
application. |
|
There is a new attribute in the service contract called the granted |
capacity flag which, when set, has the implication that the period |
or budget of the server can only change if a renegotiation or a |
change of quality and importance is requested for it; it may not |
change automatically, for instance because of negotiations for |
other servers. This provides a stable framework while performing |
the distributed negotiation. |
|
For a server with the granted capacity flag set, there is an |
operation to return spare capacity that cannot be used due to |
restrictions in other servers of a distributed transaction. |
*/ |