source: rtems-docs/c-user/key_concepts.rst @ c65aeed

5
Last change on this file since c65aeed was 464d541, checked in by Sebastian Huber <sebastian.huber@…>, on 03/07/18 at 13:18:10

c-user: Use uniprocessor throughout

  • Property mode set to 100644
File size: 24.4 KB
Line 
1.. comment SPDX-License-Identifier: CC-BY-SA-4.0
2
3.. COMMENT: COPYRIGHT (c) 1988-2008.
4.. COMMENT: On-Line Applications Research Corporation (OAR).
5.. COMMENT: All rights reserved.
6
7Key Concepts
8************
9
10Introduction
11============
12
13The facilities provided by RTEMS are built upon a foundation of very powerful
14concepts.  These concepts must be understood before the application developer
15can efficiently utilize RTEMS.  The purpose of this chapter is to familiarize
16one with these concepts.
17
18.. _objects:
19
20.. index:: objects
21
22Objects
23=======
24
25RTEMS provides directives which can be used to dynamically create, delete, and
26manipulate a set of predefined object types.  These types include tasks,
27message queues, semaphores, memory regions, memory partitions, timers, ports,
28and rate monotonic periods.  The object-oriented nature of RTEMS encourages the
29creation of modular applications built upon re-usable "building block"
30routines.
31
32All objects are created on the local node as required by the application and
33have an RTEMS assigned ID.  All objects have a user-assigned name.  Although a
34relationship exists between an object's name and its RTEMS assigned ID, the
35name and ID are not identical.  Object names are completely arbitrary and
36selected by the user as a meaningful "tag" which may commonly reflect the
37object's use in the application.  Conversely, object IDs are designed to
38facilitate efficient object manipulation by the executive.
39
40.. index:: object name
41.. index:: rtems_name
42
43Object Names
44------------
45
46An object name is an unsigned thirty-two bit entity associated with the object
47by the user.  The data type ``rtems_name`` is used to store object
48names.
49
50.. index:: rtems_build_name
51
52Although not required by RTEMS, object names are often composed of four ASCII
53characters which help identify that object.  For example, a task which causes a
54light to blink might be called "LITE".  The ``rtems_build_name`` routine is
55provided to build an object name from four ASCII characters.  The following
56example illustrates this:
57
58.. code-block:: c
59
60    rtems_name my_name;
61    my_name = rtems_build_name( 'L', 'I', 'T', 'E' );
62
63However, it is not required that the application use ASCII characters to build
64object names.  For example, if an application requires one-hundred tasks, it
65would be difficult to assign meaningful ASCII names to each task.  A more
66convenient approach would be to name them the binary values one through
67one-hundred, respectively.
68
69.. index:: rtems_object_get_name
70
71RTEMS provides a helper routine, ``rtems_object_get_name``, which can be used
72to obtain the name of any RTEMS object using just its ID.  This routine
73attempts to convert the name into a printable string.
74
75The following example illustrates the use of this method to print an object
76name:
77
78.. code-block:: c
79
80    #include <rtems.h>
81    #include <rtems/bspIo.h>
82    void print_name(rtems_id id)
83    {
84        char  buffer[10];   /* name assumed to be 10 characters or less */
85        char *result;
86        result = rtems_object_get_name( id, sizeof(buffer), buffer );
87        printk( "ID=0x%08x name=%s\n", id, ((result) ? result : "no name") );
88    }
89
90.. index:: object ID
91.. index:: object ID composition
92.. index:: rtems_id
93
94Object IDs
95----------
96
97An object ID is a unique unsigned integer value which uniquely identifies an
98object instance.  Object IDs are passed as arguments to many directives in
99RTEMS and RTEMS translates the ID to an internal object pointer. The efficient
100manipulation of object IDs is critical to the performance of RTEMS services.
101Because of this, there are two object Id formats defined.  Each target
102architecture specifies which format it will use.  There is a thirty-two bit
103format which is used for most of the supported architectures and supports
104multiprocessor configurations.  There is also a simpler sixteen bit format
105which is appropriate for smaller target architectures and does not support
106multiprocessor configurations.
107
108Thirty-Two Object ID Format
109~~~~~~~~~~~~~~~~~~~~~~~~~~~
110
111The thirty-two bit format for an object ID is composed of four parts: API,
112object class, node, and index.  The data type ``rtems_id`` is used to store
113object IDs.
114
115.. code-block:: c
116
117    31      27 26   24 23          16 15                             0
118    +---------+-------+--------------+-------------------------------+
119    |         |       |              |                               |
120    |  Class  |  API  |     Node     |             Index             |
121    |         |       |              |                               |
122    +---------+-------+--------------+-------------------------------+
123
124The most significant five bits are the object class.  The next three bits
125indicate the API to which the object class belongs.  The next eight bits
126(16-23) are the number of the node on which this object was created.  The node
127number is always one (1) in a single processor system.  The least significant
128sixteen bits form an identifier within a particular object type.  This
129identifier, called the object index, ranges in value from 1 to the maximum
130number of objects configured for this object type.
131
132Sixteen Bit Object ID Format
133~~~~~~~~~~~~~~~~~~~~~~~~~~~~
134
135The sixteen bit format for an object ID is composed of three parts: API, object
136class, and index.  The data type ``rtems_id`` is used to store object IDs.
137
138.. code-block:: c
139
140    15      11 10    8 7            0
141    +---------+-------+--------------+
142    |         |       |              |
143    |  Class  |  API  |    Index     |
144    |         |       |              |
145    +---------+-------+--------------+
146
147The sixteen-bit format is designed to be as similar as possible to the
148thrity-two bit format.  The differences are limited to the eliminatation of the
149node field and reduction of the index field from sixteen-bits to 8-bits.  Thus
150the sixteen bit format only supports up to 255 object instances per API/Class
151combination and single processor systems.  As this format is typically utilized
152by sixteen-bit processors with limited address space, this is more than enough
153object instances.
154
155Object ID Description
156---------------------
157
158The components of an object ID make it possible to quickly locate any object in
159even the most complicated multiprocessor system.  Object ID's are associated
160with an object by RTEMS when the object is created and the corresponding ID is
161returned by the appropriate object create directive.  The object ID is required
162as input to all directives involving objects, except those which create an
163object or obtain the ID of an object.
164
165The object identification directives can be used to dynamically obtain a
166particular object's ID given its name.  This mapping is accomplished by
167searching the name table associated with this object type.  If the name is
168non-unique, then the ID associated with the first occurrence of the name will
169be returned to the application.  Since object IDs are returned when the object
170is created, the object identification directives are not necessary in a
171properly designed single processor application.
172
173In addition, services are provided to portably examine the subcomponents of an
174RTEMS ID.  These services are described in detail later in this manual but are
175prototyped as follows:
176
177.. index:: obtaining class from object ID
178.. index:: obtaining node from object ID
179.. index:: obtaining index from object ID
180.. index:: get class from object ID
181.. index:: get node from object ID
182.. index:: get index from object ID
183.. index:: rtems_object_id_get_api
184.. index:: rtems_object_id_get_class
185.. index:: rtems_object_id_get_node
186.. index:: rtems_object_id_get_index
187
188.. code-block:: c
189
190    uint32_t rtems_object_id_get_api( rtems_id );
191    uint32_t rtems_object_id_get_class( rtems_id );
192    uint32_t rtems_object_id_get_node( rtems_id );
193    uint32_t rtems_object_id_get_index( rtems_id );
194
195An object control block is a data structure defined by RTEMS which contains the
196information necessary to manage a particular object type.  For efficiency
197reasons, the format of each object type's control block is different.  However,
198many of the fields are similar in function.  The number of each type of control
199block is application dependent and determined by the values specified in the
200user's Configuration Table.  An object control block is allocated at object
201create time and freed when the object is deleted.  With the exception of user
202extension routines, object control blocks are not directly manipulated by user
203applications.
204
205.. index:: communication and synchronization
206
207Communication and Synchronization
208=================================
209
210In real-time multitasking applications, the ability for cooperating execution
211threads to communicate and synchronize with each other is imperative.  A
212real-time executive should provide an application with the following
213capabilities:
214
215- Data transfer between cooperating tasks
216
217- Data transfer between tasks and ISRs
218
219- Synchronization of cooperating tasks
220
221- Synchronization of tasks and ISRs
222
223Most RTEMS managers can be used to provide some form of communication and/or
224synchronization.  However, managers dedicated specifically to communication and
225synchronization provide well established mechanisms which directly map to the
226application's varying needs.  This level of flexibility allows the application
227designer to match the features of a particular manager with the complexity of
228communication and synchronization required.  The following managers were
229specifically designed for communication and synchronization:
230
231- Semaphore
232
233- Message Queue
234
235- Event
236
237- Signal
238
239The semaphore manager supports mutual exclusion involving the synchronization
240of access to one or more shared user resources.  Binary semaphores may utilize
241the optional priority inheritance algorithm to avoid the problem of priority
242inversion.  The message manager supports both communication and
243synchronization, while the event manager primarily provides a high performance
244synchronization mechanism.  The signal manager supports only asynchronous
245communication and is typically used for exception handling.
246
247.. index:: locking protocols
248
249Locking Protocols
250=================
251
252RTEMS supports the four locking protocols
253
254* :ref:`PriorityCeiling`,
255
256* :ref:`PriorityInheritance`,
257
258* :ref:`MrsP`, and
259
260* :ref:`OMIP`
261
262for synchronization objects providing mutual-exclusion (mutex).  The OMIP is
263only available in SMP configurations and replaces the priority inheritance
264protocol in this case.  One aim of the locking protocols is to avoid priority
265inversion.
266
267Since RTEMS 5.1, priority updates due to the locking protocols take place
268immediately and are propagated recursively.  The mutex owner and wait for mutex
269relationships define a directed acyclic graph (DAG).  The run-time of the mutex
270obtain, release and timeout operations depend on the complexity of this
271resource dependency graph.
272
273.. index:: priority inversion
274
275.. _PriorityInversion:
276
277Priority Inversion
278------------------
279
280Priority inversion is a form of indefinite postponement which is common in
281multitasking, preemptive executives with shared resources.  Priority inversion
282occurs when a high priority tasks requests access to shared resource which is
283currently allocated to a low priority task.  The high priority task must block
284until the low priority task releases the resource.  This problem is exacerbated
285when the low priority task is prevented from executing by one or more medium
286priority tasks.  Because the low priority task is not executing, it cannot
287complete its interaction with the resource and release that resource.  The high
288priority task is effectively prevented from executing by lower priority tasks.
289
290.. index:: priority ceiling protocol
291.. index:: immediate ceiling priority protocol
292
293.. _PriorityCeiling:
294
295Immediate Ceiling Priority Protocol (ICPP)
296------------------------------------------
297
298Each mutex using the Immediate Ceiling Priority Protocol (ICPP) has a ceiling
299priority.  The priority of the mutex owner is immediately raised to the ceiling
300priority of the mutex.  In case the thread owning the mutex releases the mutex,
301then the normal priority of the thread is restored.  This locking protocol is
302beneficial for schedulability analysis, see also
303:cite:`Burns:2001:RealTimeSystems`.
304
305This protocol avoids the possibility of changing the priority of the mutex
306owner multiple times since the ceiling priority must be set to the one of
307highest priority thread which will ever attempt to acquire that mutex.  This
308requires an overall knowledge of the application as a whole.  The need to
309identify the highest priority thread which will attempt to obtain a particular
310mutex can be a difficult task in a large, complicated system.  Although the
311priority ceiling protocol is more efficient than the priority inheritance
312protocol with respect to the maximum number of thread priority changes which
313may occur while a thread owns a particular mutex, the priority inheritance
314protocol is more forgiving in that it does not require this apriori
315information.
316
317.. index:: priority inheritance protocol
318
319.. _PriorityInheritance:
320
321Priority Inheritance Protocol
322-----------------------------
323
324The priority of the mutex owner is raised to the highest priority of all
325threads that currently wait for ownership of this mutex :cite:`Sha:1990:PI`.
326Since RTEMS 5.1, priority updates due to the priority inheritance protocol
327take place immediately and are propagated recursively.
328
329.. index:: Multiprocessor Resource Sharing Protocol (MrsP)
330
331.. _MrsP:
332
333Multiprocessor Resource Sharing Protocol (MrsP)
334-----------------------------------------------
335
336The Multiprocessor Resource Sharing Protocol (MrsP) is a generalization of the
337priority ceiling protocol to clustered scheduling :cite:`Burns:2013:MrsP`.  One
338of the design goals of MrsP is to enable an effective schedulability analysis
339using the sporadic task model.  Each mutex using the MrsP has a ceiling
340priority for each scheduler instance.  The priority of the mutex owner is
341immediately raised to the ceiling priority of the mutex defined for its home
342scheduler instance.  In case the thread owning the mutex releases the mutex,
343then the normal priority of the thread is restored.  Threads that wait for
344mutex ownership are not blocked with respect to the scheduler and instead
345perform a busy wait.  The MrsP uses temporary thread migrations to foreign
346scheduler instances in case of a preemption of the mutex owner.  This locking
347protocol is available since RTEMS 4.11. It was re-implemented in RTEMS 5.1 to
348overcome some shortcomings of the original implementation
349:cite:`Catellani:2015:MrsP`.
350
351.. index:: O(m) Independence-Preserving Protocol (OMIP)
352
353.. _OMIP:
354
355O(m) Independence-Preserving Protocol (OMIP)
356----------------------------------------------------
357
358The :math:`O(m)` Independence-Preserving Protocol (OMIP) is a generalization of
359the priority inheritance protocol to clustered scheduling which avoids the
360non-preemptive sections present with priority boosting
361:cite:`Brandenburg:2013:OMIP`.  The :math:`m` denotes the number of processors
362in the system.  Similar to the uniprocessor priority inheritance protocol, the
363OMIP mutexes do not need any external configuration data, e.g. a ceiling
364priority.  This makes them a good choice for general purpose libraries that
365need internal locking.  The complex part of the implementation is contained in
366the thread queues and shared with the MrsP support.  This locking protocol is
367available since RTEMS 5.1.
368
369.. index:: thread queues
370
371Thread Queues
372=============
373
374In case more than one :term:`thread` may wait on a synchronization object, e.g.
375a semaphore or a message queue, then the waiting threads are added to a data
376structure called the thread queue.  Thread queues are named task wait queues in
377the Classic API.  There are two thread queuing disciplines available which
378define the order of the threads on a particular thread queue.  Threads can wait
379in FIFO or priority order.
380
381In uniprocessor configurations, the priority queuing discipline just orders
382the threads according to their current priority and in FIFO order in case of
383equal priorities.  However, in SMP configurations, the situation is a bit more
384difficult due to the support for clustered scheduling.  It makes no sense to
385compare the priority values of two different scheduler instances.  Thus, it is
386impossible to simply use one plain priority queue for threads of different
387clusters.  Two levels of queues can be used as one way to solve the problem.
388The top-level queue provides FIFO ordering and contains priority queues.  Each
389priority queue is associated with a scheduler instance and contains only
390threads of this scheduler instance.  Threads are enqueued in the priority
391queues corresponding to their scheduler instances.  To dequeue a thread, the
392highest priority thread of the first priority queue is selected.  Once this is
393done, the first priority queue is appended to the top-level FIFO queue.  This
394guarantees fairness with respect to the scheduler instances.
395
396Such a two-level queue needs a considerable amount of memory if fast enqueue
397and dequeue operations are desired.  Providing this storage per thread queue
398would waste a lot of memory in typical applications.  Instead, each thread has
399a queue attached which resides in a dedicated memory space independent of other
400memory used for the thread (this approach was borrowed from FreeBSD).  In case
401a thread needs to block, there are two options
402
403* the object already has a queue, then the thread enqueues itself to this
404  already present queue and the queue of the thread is added to a list of free
405  queues for this object, or
406
407* otherwise, the queue of the thread is given to the object and the thread
408  enqueues itself to this queue.
409
410In case the thread is dequeued, there are two options
411
412* the thread is the last thread in the queue, then it removes this queue
413  from the object and reclaims it for its own purpose, or
414
415* otherwise, the thread removes one queue from the free list of the object
416  and reclaims it for its own purpose.
417
418Since there are usually more objects than threads, this actually reduces the
419memory demands.  In addition the objects only contain a pointer to the queue
420structure.  This helps to hide implementation details.  Inter-cluster priority
421queues are available since RTEMS 5.1.
422
423A doubly-linked list (chain) is used to implement the FIFO queues yielding a
424:math:`O(1)` worst-case time complexity for enqueue and dequeue operations.
425
426A red-black tree is used to implement the priority queues yielding a
427:math:`O(log(n))` worst-case time complexity for enqueue and dequeue operations
428with :math:`n` being the count of threads already on the queue.
429
430.. index:: time
431
432Time
433====
434
435The development of responsive real-time applications requires an understanding
436of how RTEMS maintains and supports time-related operations.  The basic unit of
437time in RTEMS is known as a `clock tick` or simply `tick`.  The tick interval
438is defined by the application configuration option
439:ref:`CONFIGURE_MICROSECONDS_PER_TICK <CONFIGURE_MICROSECONDS_PER_TICK>`.  The
440tick interval defines the basic resolution of all interval and calendar time
441operations.  Obviously, the directives which use intervals or wall time cannot
442operate without some external mechanism which provides a periodic clock tick.
443This clock tick is provided by the clock driver.  The tick precision and
444stability depends on the clock driver and interrupt latency.  Most clock
445drivers provide a timecounter to measure the time with a higher resolution than
446the tick.
447
448.. index:: rtems_interval
449
450By tracking time in units of ticks, RTEMS is capable of supporting interval
451timing functions such as task delays, timeouts, timeslicing, the delayed
452execution of timer service routines, and the rate monotonic scheduling of
453tasks.  An interval is defined as a number of ticks relative to the current
454time.  For example, when a task delays for an interval of ten ticks, it is
455implied that the task will not execute until ten clock ticks have occurred.
456All intervals are specified using data type :c:type:`rtems_interval`.
457
458A characteristic of interval timing is that the actual interval period may be a
459fraction of a tick less than the interval requested.  This occurs because the
460time at which the delay timer is set up occurs at some time between two clock
461ticks.  Therefore, the first countdown tick occurs in less than the complete
462time interval for a tick.  This can be a problem if the tick resolution is
463large.
464
465The rate monotonic scheduling algorithm is a hard real-time scheduling
466methodology.  This methodology provides rules which allows one to guarantee
467that a set of independent periodic tasks will always meet their deadlines even
468under transient overload conditions.  The rate monotonic manager provides
469directives built upon the Clock Manager's interval timer support routines.
470
471Interval timing is not sufficient for the many applications which require that
472time be kept in wall time or true calendar form.  Consequently, RTEMS maintains
473the current date and time.  This allows selected time operations to be
474scheduled at an actual calendar date and time.  For example, a task could
475request to delay until midnight on New Year's Eve before lowering the ball at
476Times Square.  The data type :c:type:`rtems_time_of_day` is used to specify calendar
477time in RTEMS services.  See :ref:`Time and Date Data Structures`.
478
479.. index:: rtems_time_of_day
480
481Timer and Timeouts
482==================
483
484Timer and timeout services are a standard component of an operating system.
485The use cases fall roughly into two categories:
486
487* Timeouts -- used to detect if some operations need more time than expected.
488  Since the unexpected happens hopefully rarely, timeout timers are usually
489  removed before they expire. The critical operations are insert and removal.
490  For example, they are important for the performance of a network stack.
491
492* Timers -- used to carry out some work in the future. They usually expire
493  and need a high resolution. An example use case is a time driven scheduler,
494  e.g.  rate-monotonic or EDF.
495
496In RTEMS versions prior to 5.1 the timer and timeout support was implemented
497by means of delta chains.  This implementation was unfit for SMP systems due to
498several reasons.  The new implementation present since RTEMS 5.1 uses a
499red-black tree with the expiration time as the key.  This leads to
500:math:`O(log(n))` worst-case insert and removal operations for :math:`n` active
501timer or timeouts.  Each processor provides its own timer and timeout service
502point so that it scales well with the processor count of the system.  For each
503operation it is sufficient to acquire and release a dedicated SMP lock only
504once. The drawback is that a 64-bit integer type is required internally for the
505intervals to avoid a potential overflow of the key values.
506
507An alternative to the red-black tree based implementation would be the use of a
508timer wheel based algorithm :cite:`Varghese:1987:TimerWheel` which is used in
509Linux and FreeBSD :cite:`Varghese:1995:BSDCallout` for example.  A timer wheel
510based algorithm offers :math:`O(1)` worst-case time complexity for insert and
511removal operations.  The drawback is that the run-time of the clock tick
512procedure is unpredictable due to the use of a hash table or cascading.
513
514The red-black tree approach was selected for RTEMS, since it offers a more
515predictable run-time behaviour.  However, this sacrifices the constant insert
516and removal operations offered by the timer wheel algorithms.  See also
517:cite:`Gleixner:2006:Hrtimers`.  The implementation can re-use the red-black
518tree support already used in other areas, e.g. for the thread priority queues.
519Less code is a good thing for size, testing and verification.
520
521.. index:: memory management
522
523Memory Management
524=================
525
526RTEMS memory management facilities can be grouped into two classes: dynamic
527memory allocation and address translation.  Dynamic memory allocation is
528required by applications whose memory requirements vary through the
529application's course of execution.  Address translation is needed by
530applications which share memory with another CPU or an intelligent Input/Output
531processor.  The following RTEMS managers provide facilities to manage memory:
532
533- Region
534
535- Partition
536
537- Dual Ported Memory
538
539RTEMS memory management features allow an application to create simple memory
540pools of fixed size buffers and/or more complex memory pools of variable size
541segments.  The partition manager provides directives to manage and maintain
542pools of fixed size entities such as resource control blocks.  Alternatively,
543the region manager provides a more general purpose memory allocation scheme
544that supports variable size blocks of memory which are dynamically obtained and
545freed by the application.  The dual-ported memory manager provides executive
546support for address translation between internal and external dual-ported RAM
547address space.
Note: See TracBrowser for help on using the repository browser.