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

5
Last change on this file since aaff696 was aaff696, checked in by Sebastian Huber <sebastian.huber@…>, on 01/31/17 at 10:15:56

c-user: Add key concept thread queues

Update #2556.

  • Property mode set to 100644
File size: 19.1 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
20Objects
21=======
22
23.. index:: objects
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
40Object Names
41------------
42.. index:: object name
43.. index:: rtems_name
44
45An object name is an unsigned thirty-two bit entity associated with the object
46by the user.  The data type ``rtems_name`` is used to store object
47names... index:: rtems_build_name
48
49Although not required by RTEMS, object names are often composed of four ASCII
50characters which help identify that object.  For example, a task which causes a
51light to blink might be called "LITE".  The ``rtems_build_name`` routine is
52provided to build an object name from four ASCII characters.  The following
53example illustrates this:
54
55.. code-block:: c
56
57    rtems_name my_name;
58    my_name = rtems_build_name( 'L', 'I', 'T', 'E' );
59
60However, it is not required that the application use ASCII characters to build
61object names.  For example, if an application requires one-hundred tasks, it
62would be difficult to assign meaningful ASCII names to each task.  A more
63convenient approach would be to name them the binary values one through
64one-hundred, respectively.
65
66.. index:: rtems_object_get_name
67
68RTEMS provides a helper routine, ``rtems_object_get_name``, which can be used
69to obtain the name of any RTEMS object using just its ID.  This routine
70attempts to convert the name into a printable string.
71
72The following example illustrates the use of this method to print an object
73name:
74
75.. code-block:: c
76
77    #include <rtems.h>
78    #include <rtems/bspIo.h>
79    void print_name(rtems_id id)
80    {
81        char  buffer[10];   /* name assumed to be 10 characters or less */
82        char *result;
83        result = rtems_object_get_name( id, sizeof(buffer), buffer );
84        printk( "ID=0x%08x name=%s\n", id, ((result) ? result : "no name") );
85    }
86
87Object IDs
88----------
89.. index:: object ID
90.. index:: object ID composition
91.. index:: rtems_id
92
93An object ID is a unique unsigned integer value which uniquely identifies an
94object instance.  Object IDs are passed as arguments to many directives in
95RTEMS and RTEMS translates the ID to an internal object pointer. The efficient
96manipulation of object IDs is critical to the performance of RTEMS services.
97Because of this, there are two object Id formats defined.  Each target
98architecture specifies which format it will use.  There is a thirty-two bit
99format which is used for most of the supported architectures and supports
100multiprocessor configurations.  There is also a simpler sixteen bit format
101which is appropriate for smaller target architectures and does not support
102multiprocessor configurations.
103
104Thirty-Two Object ID Format
105~~~~~~~~~~~~~~~~~~~~~~~~~~~
106
107The thirty-two bit format for an object ID is composed of four parts: API,
108object class, node, and index.  The data type ``rtems_id`` is used to store
109object IDs.
110
111.. code-block:: c
112
113    31      27 26   24 23          16 15                             0
114    +---------+-------+--------------+-------------------------------+
115    |         |       |              |                               |
116    |  Class  |  API  |     Node     |             Index             |
117    |         |       |              |                               |
118    +---------+-------+--------------+-------------------------------+
119
120The most significant five bits are the object class.  The next three bits
121indicate the API to which the object class belongs.  The next eight bits
122(16-23) are the number of the node on which this object was created.  The node
123number is always one (1) in a single processor system.  The least significant
124sixteen bits form an identifier within a particular object type.  This
125identifier, called the object index, ranges in value from 1 to the maximum
126number of objects configured for this object type.
127
128Sixteen Bit Object ID Format
129~~~~~~~~~~~~~~~~~~~~~~~~~~~~
130
131The sixteen bit format for an object ID is composed of three parts: API, object
132class, and index.  The data type ``rtems_id`` is used to store object IDs.
133
134.. code-block:: c
135
136    15      11 10    8 7            0
137    +---------+-------+--------------+
138    |         |       |              |
139    |  Class  |  API  |    Index     |
140    |         |       |              |
141    +---------+-------+--------------+
142
143The sixteen-bit format is designed to be as similar as possible to the
144thrity-two bit format.  The differences are limited to the eliminatation of the
145node field and reduction of the index field from sixteen-bits to 8-bits.  Thus
146the sixteen bit format only supports up to 255 object instances per API/Class
147combination and single processor systems.  As this format is typically utilized
148by sixteen-bit processors with limited address space, this is more than enough
149object instances.
150
151Object ID Description
152---------------------
153
154The components of an object ID make it possible to quickly locate any object in
155even the most complicated multiprocessor system.  Object ID's are associated
156with an object by RTEMS when the object is created and the corresponding ID is
157returned by the appropriate object create directive.  The object ID is required
158as input to all directives involving objects, except those which create an
159object or obtain the ID of an object.
160
161The object identification directives can be used to dynamically obtain a
162particular object's ID given its name.  This mapping is accomplished by
163searching the name table associated with this object type.  If the name is
164non-unique, then the ID associated with the first occurrence of the name will
165be returned to the application.  Since object IDs are returned when the object
166is created, the object identification directives are not necessary in a
167properly designed single processor application.
168
169In addition, services are provided to portably examine the subcomponents of an
170RTEMS ID.  These services are described in detail later in this manual but are
171prototyped as follows:
172
173.. index:: obtaining class from object ID
174.. index:: obtaining node from object ID
175.. index:: obtaining index from object ID
176.. index:: get class from object ID
177.. index:: get node from object ID
178.. index:: get index from object ID
179.. index:: rtems_object_id_get_api
180.. index:: rtems_object_id_get_class
181.. index:: rtems_object_id_get_node
182.. index:: rtems_object_id_get_index
183
184.. code-block:: c
185
186    uint32_t rtems_object_id_get_api( rtems_id );
187    uint32_t rtems_object_id_get_class( rtems_id );
188    uint32_t rtems_object_id_get_node( rtems_id );
189    uint32_t rtems_object_id_get_index( rtems_id );
190
191An object control block is a data structure defined by RTEMS which contains the
192information necessary to manage a particular object type.  For efficiency
193reasons, the format of each object type's control block is different.  However,
194many of the fields are similar in function.  The number of each type of control
195block is application dependent and determined by the values specified in the
196user's Configuration Table.  An object control block is allocated at object
197create time and freed when the object is deleted.  With the exception of user
198extension routines, object control blocks are not directly manipulated by user
199applications.
200
201Communication and Synchronization
202=================================
203.. index:: communication and synchronization
204
205In real-time multitasking applications, the ability for cooperating execution
206threads to communicate and synchronize with each other is imperative.  A
207real-time executive should provide an application with the following
208capabilities:
209
210- Data transfer between cooperating tasks
211
212- Data transfer between tasks and ISRs
213
214- Synchronization of cooperating tasks
215
216- Synchronization of tasks and ISRs
217
218Most RTEMS managers can be used to provide some form of communication and/or
219synchronization.  However, managers dedicated specifically to communication and
220synchronization provide well established mechanisms which directly map to the
221application's varying needs.  This level of flexibility allows the application
222designer to match the features of a particular manager with the complexity of
223communication and synchronization required.  The following managers were
224specifically designed for communication and synchronization:
225
226- Semaphore
227
228- Message Queue
229
230- Event
231
232- Signal
233
234The semaphore manager supports mutual exclusion involving the synchronization
235of access to one or more shared user resources.  Binary semaphores may utilize
236the optional priority inheritance algorithm to avoid the problem of priority
237inversion.  The message manager supports both communication and
238synchronization, while the event manager primarily provides a high performance
239synchronization mechanism.  The signal manager supports only asynchronous
240communication and is typically used for exception handling.
241
242Thread Queues
243=============
244.. index:: thread queues
245
246In case more than one :ref:`thread <task>` may wait on a synchronization
247object, e.g. a semaphore or a message queue, then the waiting threads are added
248to a data structure called the thread queue.  Thread queues are named task wait
249queues in the Classic API.  There are two thread queuing disciplines available
250which define the order of the threads on a particular thread queue.  Threads
251can wait in FIFO or priority order.
252
253In uni-processor configurations, the priority queuing discipline just orders
254the threads according to their current priority and in FIFO order in case of
255equal priorities.  However, in SMP configurations, the situation is a bit more
256difficult due to the support for clustered scheduling.  It makes no sense to
257compare the priority values of two different scheduler instances.  Thus, it is
258impossible to simply use one plain priority queue for threads of different
259clusters.  Two levels of queues can be used as one way to solve the problem.
260The top-level queue provides FIFO ordering and contains priority queues.  Each
261priority queue is associated with a scheduler instance and contains only
262threads of this scheduler instance.  Threads are enqueued in the priority
263queues corresponding to their scheduler instances.  To dequeue a thread, the
264highest priority thread of the first priority queue is selected.  Once this is
265done, the first priority queue is appended to the top-level FIFO queue.  This
266guarantees fairness with respect to the scheduler instances.
267
268Such a two-level queue needs a considerable amount of memory if fast enqueue
269and dequeue operations are desired.  Providing this storage per thread queue
270would waste a lot of memory in typical applications.  Instead, each thread has
271a queue attached which resides in a dedicated memory space independent of other
272memory used for the thread (this approach was borrowed from FreeBSD).  In case
273a thread needs to block, there are two options
274
275* the object already has a queue, then the thread enqueues itself to this
276  already present queue and the queue of the thread is added to a list of free
277  queues for this object, or
278
279* otherwise, the queue of the thread is given to the object and the thread
280  enqueues itself to this queue.
281
282In case the thread is dequeued, there are two options
283
284* the thread is the last thread in the queue, then it removes this queue
285  from the object and reclaims it for its own purpose, or
286
287* otherwise, the thread removes one queue from the free list of the object
288  and reclaims it for its own purpose.
289
290Since there are usually more objects than threads, this actually reduces the
291memory demands.  In addition the objects only contain a pointer to the queue
292structure.  This helps to hide implementation details.  Inter-cluster priority
293queues are available since RTEMS 4.12.
294
295A doubly-linked list (chain) is used to implement the FIFO queues yielding a
296:math:`O(1)` worst-case time complexity for enqueue and dequeue operations.
297
298A red-black tree is used to implement the priority queues yielding a
299:math:`O(log(n))` worst-case time complexity for enqueue and dequeue operations
300with :math:`n` being the count of threads already on the queue.
301
302Time
303====
304.. index:: time
305
306The development of responsive real-time applications requires an understanding
307of how RTEMS maintains and supports time-related operations.  The basic unit of
308time in RTEMS is known as a `clock tick` or simply `tick`.  The tick interval
309is defined by the application configuration option
310:ref:`CONFIGURE_MICROSECONDS_PER_TICK <CONFIGURE_MICROSECONDS_PER_TICK>`.  The
311tick interval defines the basic resolution of all interval and calendar time
312operations.  Obviously, the directives which use intervals or wall time cannot
313operate without some external mechanism which provides a periodic clock tick.
314This clock tick is provided by the clock driver.  The tick precision and
315stability depends on the clock driver and interrupt latency.  Most clock
316drivers provide a timecounter to measure the time with a higher resolution than
317the tick.
318
319.. index:: rtems_interval
320
321By tracking time in units of ticks, RTEMS is capable of supporting interval
322timing functions such as task delays, timeouts, timeslicing, the delayed
323execution of timer service routines, and the rate monotonic scheduling of
324tasks.  An interval is defined as a number of ticks relative to the current
325time.  For example, when a task delays for an interval of ten ticks, it is
326implied that the task will not execute until ten clock ticks have occurred.
327All intervals are specified using data type :c:type:`rtems_interval`.
328
329A characteristic of interval timing is that the actual interval period may be a
330fraction of a tick less than the interval requested.  This occurs because the
331time at which the delay timer is set up occurs at some time between two clock
332ticks.  Therefore, the first countdown tick occurs in less than the complete
333time interval for a tick.  This can be a problem if the tick resolution is
334large.
335
336The rate monotonic scheduling algorithm is a hard real-time scheduling
337methodology.  This methodology provides rules which allows one to guarantee
338that a set of independent periodic tasks will always meet their deadlines even
339under transient overload conditions.  The rate monotonic manager provides
340directives built upon the Clock Manager's interval timer support routines.
341
342Interval timing is not sufficient for the many applications which require that
343time be kept in wall time or true calendar form.  Consequently, RTEMS maintains
344the current date and time.  This allows selected time operations to be
345scheduled at an actual calendar date and time.  For example, a task could
346request to delay until midnight on New Year's Eve before lowering the ball at
347Times Square.  The data type :c:type:`rtems_time_of_day` is used to specify calendar
348time in RTEMS services.  See :ref:`Time and Date Data Structures`.
349
350.. index:: rtems_time_of_day
351
352Timer and Timeouts
353==================
354
355Timer and timeout services are a standard component of an operating system.
356The use cases fall roughly into two categories:
357
358* Timeouts -- used to detect if some operations need more time than expected.
359  Since the unexpected happens hopefully rarely, timeout timers are usually
360  removed before they expire. The critical operations are insert and removal.
361  For example, they are important for the performance of a network stack.
362
363* Timers -- used to carry out some work in the future. They usually expire
364  and need a high resolution. An example use case is a time driven scheduler,
365  e.g.  rate-monotonic or EDF.
366
367In RTEMS versions prior to 4.12 the timer and timeout support was implemented
368by means of delta chains.  This implementation was unfit for SMP systems due to
369several reasons.  The new implementation present since RTEMS 4.12 uses a
370red-black tree with the expiration time as the key.  This leads to
371:math:`O(log(n))` worst-case insert and removal operations for :math:`n` active
372timer or timeouts.  Each processor provides its own timer and timeout service
373point so that it scales well with the processor count of the system.  For each
374operation it is sufficient to acquire and release a dedicated SMP lock only
375once. The drawback is that a 64-bit integer type is required internally for the
376intervals to avoid a potential overflow of the key values.
377
378An alternative to the red-black tree based implementation would be the use of a
379timer wheel based algorithm :cite:`Varghese:1987:TimerWheel` which is used in
380Linux and FreeBSD :cite:`Varghese:1995:BSDCallout` for example.  A timer wheel
381based algorithm offers :math:`O(1)` worst-case time complexity for insert and
382removal operations.  The drawback is that the run-time of the clock tick
383procedure is unpredictable due to the use of a hash table or cascading.
384
385The red-black tree approach was selected for RTEMS, since it offers a more
386predictable run-time behaviour.  However, this sacrifices the constant insert
387and removal operations offered by the timer wheel algorithms.  See also
388:cite:`Gleixner:2006:Hrtimers`.  The implementation can re-use the red-black
389tree support already used in other areas, e.g. for the thread priority queues.
390Less code is a good thing for size, testing and verification.
391
392Memory Management
393=================
394.. index:: memory management
395
396RTEMS memory management facilities can be grouped into two classes: dynamic
397memory allocation and address translation.  Dynamic memory allocation is
398required by applications whose memory requirements vary through the
399application's course of execution.  Address translation is needed by
400applications which share memory with another CPU or an intelligent Input/Output
401processor.  The following RTEMS managers provide facilities to manage memory:
402
403- Region
404
405- Partition
406
407- Dual Ported Memory
408
409RTEMS memory management features allow an application to create simple memory
410pools of fixed size buffers and/or more complex memory pools of variable size
411segments.  The partition manager provides directives to manage and maintain
412pools of fixed size entities such as resource control blocks.  Alternatively,
413the region manager provides a more general purpose memory allocation scheme
414that supports variable size blocks of memory which are dynamically obtained and
415freed by the application.  The dual-ported memory manager provides executive
416support for address translation between internal and external dual-ported RAM
417address space.
Note: See TracBrowser for help on using the repository browser.