Dynamic storage allocation for real-time embedded systems
∗
M. Masmano, I. Ripoll, and A. Crespo
Universidad Polit´ecnica de Valencia, Spain.
{mmasmano,iripoll,alfons}@disca.upv.es
Abstract
Dynamic memory allocation DSA algorithms have
played in important role in the modern software engi-
neering paradigms and techniques (as object oriented
paradigm). Additionally, its utilization allows to in-
crease t he flexibility and functionalities of the applica-
tions. There exists in the literature a large number of
works and references to this particular issue. However,
in the real-time community the use of dynamic memory
techniques has been not considered as an important issue
because spatial and temporal worst case for allocation
and deallocation operations were insufficiently bounded.
It is significant the reduced number of papers about this
topic in the more relevant real-time events.
Considering these reasons new dynamic storage allo-
cator DSA algorithms with a bounded and acceptable
temporary behavior must be developed to be used by
RTOS. On this paper a new DSA algorithms called Two
Level Segregated Fit (TLSF), developed specifically to be
used by RTOS, is introduced and compared with other
previously propo sals.
1 Introduction
The study of dynamic storage allocation (DSA) algo-
rithms has been an important topic in the operating sys-
tems research and implementation and has been widely
analysed. Wilson et al. [7] wrote an excellent sur-
vey/tutorial of the research about storage allocation
done between 1961 and 1995. Due to the large amount
of existing DSA algorithms and studies, the reader can
get to think that the problem of dynamic memory al-
location has b ee n already solved. This can be true in
most applications types, however the situation for the
real time applications is quiet different.
In real-time systems it is needed to know in advance
the operation bounds in order to analyse the system.
The dynamic memory allocation operations lack of a
sufficient bounds to provide efficient support to the ap-
plications which means that the time required to allo-
cate and deallocate memory are both unpredictable .
Additionally, the dynamic memory management can in-
troduce an important memory fragmentation that can
generate unreliable service when the application runs
for large period of time. It is imp ortant to point out
that a fast response and high thoughtput are important
characteristics that has to be taken into account in any
systems, and in particular in a RTS. But the main char-
acteristic that defines a RTS is to guarantee the timing
constrains.
Most of the DSA algorithms were designed to provide
fast response time for the most probable case achieving
a good overall performance, although the worst case can
be high. For these reasons, most RTOS developers and
researchers avoid the use of dynamic memory at all, or
use it in a restricted way, for example, only during the
system startup [6].
This paper prese nts a new algorithm for dynamic
memory alocation that tries to solve the problem of the
worst case bound maintaining the efficiency of the allo-
cation and deallocation operations. Also, the fragmen-
tation problem is improved enougth to be used in real-
time systems running for long time. Section 2 presents a
review of the requirements that should be fulfilled by the
dynamic memory allocation algorithms for real-time ap-
plications. Section 3 analyses some of the most relevant
DSA implementations used in real-time and non-real-
time environments. In section 4, the design guidelines
of the proposed DSA are presented. The propossed al-
gorithm is outlined in section 5.
2 Real-Time requirements
One of the key issues in re al-time systems is the schedu-
lability analysis to determine w hether the timing con-
straints will be satisfied at run-time or not. Regardless
of which analysis and scheduling techniques are used, it
is essential that the real-time designer be able to deter-
mine the worst-case execution time of all the activities
involved in the application. Moreover, real-time applica-
tions run for large periods of time. During its operation,
memory can be allocated and deallocated many times
which aggravates the m emory fragmentation problem.
Considering these aspects, the requirements of real-
time applications regarding dynamic memory can be
stated as follows:
Bounded response time. The WCRT has to be
known a priority and, if possible, be independent of ap-
plication data. This is the main requirement the must
be meet.
∗
This work has been supported by the Euro pean C omm ision project: IST-2001-35102(OCERA) http://www.ocera.org.
1
