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