Subversion Repositories shark

Rev

Rev 995 | Blame | Compare with Previous | Last modification | View Log | RSS feed

/**
   \mainpage FSF reference

   This reference manual contains the description of the API provided
   by the FSF library.

   \section intro Introduction to FSF

   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
   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
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
achieve the highest possible quality.

The FIRST project aims at developing a framework for a scheduling
architecture that provides the ability to compose several applications
or components into the system, and to flexibly schedule the available
resources while guaranteeing hard real-time requirements. The FIRST
Scheduling Framework (FSF) is independent of the underlying
implementation, and can run on different underlying scheduling
strategies. It is based on establishing service contracts that
represent the complex and flexible requirements of the application,
and which are managed by the underlying system to provide the required
level of service.

FSF provides a generalized architecture framework that combines
different kinds of requirements:

 - co-operation and coexistence of standard real-time scheduling
   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

- integration of different timing requirements such as hard and soft,
  and more flexible notions

- temporal encapsulation of subsystems in order to support the
  composability and reusability of available components including
  legacy subsystems.

FSF has been implemented in two POSIX compliant real-time operating
systems, <a href="http://marte.unican.es">MaRTE</a> and <a
href="http://shark.sssup.it/">SHARK</a>, which are based on FP and EDF
scheduling schemes, respectively, thus illustrating the platform
independence of the presented approach.

   \section Service Contracts

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
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
as part of the negotiation if it has enough resources to guarantee all
the minimum requirements specified, while keeping guarantees on all
the previously accepted contracts negotiated by other application
components. If as a result of this negotiation the set of contracts is
accepted, the system will reserve enough capacity to guarantee the
minimum requested resources, and will adapt any spare capacity
available to share it among the different contracts that have
specified their desire or ability for using additional capacity.


As a result of the negotiation process, if a contract is accepted, a
server is created for it. The server is a software object that is the
run-time representation of the contract; it stores all the information
related to the resources currently reserved for that contract, the
resources already consumed, and the resources required to handle the
budget consumption and replenishment events in the particular
operating system being used.

Because there are various application requirements specified in the
contract, they are divided into several groups, also allowing the
underlying implementation to give different levels of support trading
them against implementation complexity. This gives way to a modular
implementation of the framework, with each module addressing specific
application requirements. The minimum resources required by the
application to be reserved by the system are specified in the core
module. The requirements for mutual exclusive synchronization among
parts of the application being scheduled by different servers or among
different applications are specified in the shared objects
module. Flexible resource usage is associated with the spare capacity
and dynamic reclamation modules. The ability to compose applications
or application components with several threads of control, thus
requiring hierarchical scheduling of several threads inside the same
server are supported by the hierarchical scheduling module. Finally,
the requirements of distributed applications are supported by the
distributed and the distributed spare capacity modules. We will now
explain these modules together with their associated application
requirements.


 */


/**
   \defgroup coremodule Core module

The core module contains the service contract information related to
the application minimum resource requirements, the operations required
to create contracts and negotiate them, and the underlying
implementation of the servers with a resource reservation mechanism
that allows the system to guarantee the resources granted to each
server.

   This module includes the basic functions and services that are
   provided by any FSF implementation. This module includes basic type
   definitions, and functions to

   - create a contract and initialize it
   - set/get the basic parameters of a contract
   - negotiate a service contract, obtaining a server id
   - 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.


*/


/**
   \defgroup sparemodule Spare capacity sharing module

Many applications have requirements for flexibility regarding the
amount of resources that can be used. The spare capacity module allows
the system to share the spare capacity that may be left over from the
negotiation of the service contracts, in a static way. During the
negotiation, the minimum requested resources are granted to each
server, if possible. Then, if there is any extra capacity left, it is
distributed among those applications that have expressed their ability
to take advantage of it.

   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.

   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 coremodule
   module).
     
 */


/**
   \defgroup hiermodule Hierarchical scheduling module

One of the application requirements that FSF addresses is the ability
to compose different applications, possibly using different scheduling
policies, into the same system. This can be addressed with support in
the system for hierarchical scheduling. The lower level is the
scheduler that takes care of the service contracts, using an
unspecified scheduling policy (for instance, a CBS on top of EDF, or a
sporadic server on top of fixed priorities). The top level is a
scheduler running inside one particular FSF server, and scheduling the
application threads with whatever scheduling policy they were
designed. In this way, it is possible to have in the same system one
application with, for example, fixed priorities, and another one
running concurrently with an EDF scheduler.

We are currently providing four top-level schedulers: fixed
priorities, EDF, round robin and table-driven.
 */


/**
   \defgroup shobjmodule Shared Objects module

The shared objects module of FSF allows the application to specify in
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
schedulability analysis purposes only. A run-time mechanism for mutual
exclusion is not provided in FSF for two important reasons. One of
them is upward compatibility of previous code using regular primitives
such as mutexes or protected objects (in Ada); this is a key issue if
we want to persuade application developers to switch their systems to
the FSF environment. The second reason is that enforcing worst case
execution time for critical sections is expensive. The number of
critical sections in real pieces of code may be very high, in the tens
or in the hundreds per task, and monitoring all of them would require
a large amount of system resources.

The FSF application does not depend on any particular synchronization
protocol, but there is a requirement that a budget expiration cannot
occur inside a critical section, because otherwise the blocking delays
could be extremely large. This implies that the application is allowed
to overrun its budget for the duration, at most, of the critical
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

   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

   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.
 */