* ZZZZ HeapGuard Naecon paper (16,047 Bytes)
@ 1991-07-20 18:45 SAHARBAUGH
0 siblings, 0 replies; only message in thread
From: SAHARBAUGH @ 1991-07-20 18:45 UTC (permalink / raw)
On 20 July Norm Cohen writes about task access type variables (very well I
might add) and says in passing:
"Of course no Ada compiler yet provides garbage collection for ANY types,
let alone task types."
Thanks Norm for reminding me to post our HeapGuard paper.
----
<This paper(with figures) was published in NAECON 91, IEEE
catalog# 91CH3007-2, ISSN# 0547-3578, pp 704-708>
HeapGuard TM,
Eliminating Garbage Collection in Real-Time Ada Systems
Sam Harbaugh and Bill Wavering
Integrated Software, Inc., Palm Bay, Florida
<HeapGuard is a trademark of Integrated Software, Inc.,
all rights reserved>
Abstract
In any kind of real-time system, garbage collection must
be avoided. Garbage collection requires a great deal of time
to move data and occurs at unpredictable times. This paper
introduces HeapGuard, a heap management system which
eliminates the problem of garbage collection in real-time
systems. The sources of garbage and traditional garbage
collection are reviewed. The HeapGuard scheme and optional
supporting hardware are presented.
The Cause of Garbage
Programming languages, such as Ada [LRM], Lisp,
Smalltalk, C++, make extensive use of dynamic memory and heap
management techniques. For example, heap memory is used
explicitly when the Ada programmer uses the keyword "new" to
dynamically allocate an object such as a node in a linked
list or when declaring an access type [Booch]. The Ada
program makes implicit calls to the Ada Runtime Environment
(ARTE) to allocate heap memory for task stack space, I/O data
buffers and for various size program objects. The ARTE calls
the Heap Manager to get the heap space. See Figure 1.
When the program is done with an object it calls the
ARTE to deallocate the object's heap space. This happens
implicitly when the object goes out of scope, for example, a
subprogram's local storage is deallocated when the
subprogram is exited. Deallocation occurs explicitly when
the program calls an instantiation of the Ada generic
procedure "unchecked_deallocation" [Booch]. The programmer
depends on the ARTE calls to the Heap Manager to release and
reclaim the heap space.
<figure shows relationship of Ada program, ARTE, Heap
Manager, Heap management information and Heap memory>
Figure 1. Run-Time Software Architecture
Some heap managers return the released space for
reallocation while others do nothing at all to make the space
reusable. The heap managers that do nothing to reclaim heap
space will surely cause a "STORAGE_ERROR" exception when a
program's allocation request cannot be satisfied. The heap
managers which reuse heap space can create garbage (unused
heap fragments) as explained next.
As the Ada program allocates and deallocates various
size objects, the heap becomes fragmented when newly
allocated objects don't fit exactly into holes left by
deallocations. See Figure 2. Eventually an allocation
request will be denied even though the total amount of unused
memory exceeds the request. The heap manager must then
garbage collect or the program must quit.
Garbage collection is the process of moving the
program's data in the heap to a heap space where it can be
stored contiguously [Aho]. See Figure 2. Garbage collection
takes an unpredictable amount of time and occurs at
unpredictable times, thus rendering any real-time use of
garbage collection as unreliable. The processing time is
significant because the program's data must be moved. After
compaction, addresses of heap objects must be changed in the
Ada program to point to the objects' new location. Changing
these program addresses is a complex
<Figure shows empty heap, fragmented heap and compacted heap>
Figure 2. A Traditional Heap
management problem not even attempted by today's Ada vendors
or run-time systems. Also, changing addresses is impossible
in an Ada program implemented in read-only memory, such as in
an embedded computer system. In all, garbage collection must
be avoided in real-time Ada programs.
General Discussion of Garbage Collection
How can garbage collection be avoided? Garbage
collection is typically avoided by making all objects the
same size or by making the heap requests all the size of the
largest object. This is difficult in programs such as expert
systems, object oriented systems and data base applications.
This technique, also, wastes space and restricts
implementation techniques.
How is garbage collection dealt with? A common method
of garbage collection is to always perform some form of
incremental garbage collection according to some method of
allocating processor resources in the "background." Another
method of performing garbage collection is to size the heap
for the worst case storage scenario. And the easiest method
is to perform no garbage collection at all, at the expense
of, eventually, receiving a "STORAGE ERROR" exception.
How much memory does garbage collection use?
Incremental garbage collection can waste 50% of the heap
space. During incremental garbage collection the users' data
is marked and copied from the fragmented heap space to a
"clean" contiguous heap space. The clean heap space has to
be "large enough" to hold all the data from the fragmented
heap space. Large enough is roughly the same size as the
fragmented heap space being copied from. Thus, the space set
aside to manage and accommodate the heap is roughly twice the
needed space. The other methods of dealing with fragmented
heap space all operate by using some amount of extra memory.
Project Background
In 1985 the Air Force awarded a contract, to Integrated
Software, Inc., to identify a set of primitive functions that
could be implemented in hardware to support the functions of
the Ada Runtime Environment (ARTE) in real-time systems, such
as avionics. The work focused strongly on the support of
heap management to avoid garbage collection and allow Ada to
be safely used in real-time avionics systems. Research
performed on that contract validated the HeapGuard heap
management scheme. Further, the HeapGuard scheme is being
used on another contract to improve real-time performance of
expert systems and Artificial Intelligence. On this second
contract, HeapGuard has been integrated into the ARTE on a
UNIX platform. The HeapGuard scheme has been implemented in
both hardware and software.
The HeapGuard Scheme
The HeapGuard scheme can be stated as follows.
Assuming random allocations and deallocations, for a heap
< note to Ada BB readers: note the word "Assuming">
size of N storage units, reserve a heap area of 2N-2 units
and allocate objects on the heap using first-fit allocation*.
The first fit allocation must always start the allocation
attempt from the same end of the heap. For example, see
Figure 3, to allocate a new object of size four words on the
heap, the first fit allocator would begin searching for
unallocated heap storage at location zero. The new object
would, finally, be stored beginning at location twenty.
<figure shows program address range, 0-37, for a 20 word
HeapGuard heap using 2N-2 derating>
Figure 3. A 20 word HeapGuardHeap
HeapGuard Feasibility Tests
In order to determine the feasibility of using
HeapGuard , tests were run to try and "bust the heap."
HeapGuard feasibility tests were performed using a prototype
of HeapGuard. The tests were run, one at a time, for varying
values of reserved heap size, M, and for varying values of
the amount of the heap, N, used by the program at any one
time. The size of the stored objects varied randomly from 1
to N and the time at which they were deallocated varied
randomly. For each value of N, tests were run for M < 2*N-2
and then tests were run for M >= 2*N-2. In all cases the
tests failed for M < 2*N-2 and never failed for M >= 2*N-2.
*For non-random allocations and deallocations there is a
heap usage pattern which, according to Robson [ROB], requires
more than 2*N-2 for heaps of 512 or greater storage units.
<note to Ada BB readers: pay attention to this footnote. The
consequence is that a software-only HeapGuard scheme for over
512 heap objects will become more costly (in terms of wasted
heap RAM) and therefore to absolutely guarentee no need to
garbage collect for a worst-case usage pattern one should use
the hardware pointer scheme which "wastes" only address space
and not RAM.>
Hardware Supported HeapGuard
There are two reasons to provide hardware support for
HeapGuard. The first reason is that the additional hardware
can perform heap management concurrent with execution of the
Ada program and therefore obtain higher throughput. The
second, and more interesting, reason is that by using address
pointers to a heap which stores large objects, fewer total
memory elements are needed. The remainder of this section
describes the benefits of using address pointers.
When using hardware support for HeapGuard, address
pointers point to the allocated blocks in the heap. See
Figures 4 and 5. All memory accesses by the Ada program to
the heap are made indirectly through the pointers. This
indirect addressing is done by address bus interface level
hardware, transparently to the Ada program. Pointer
management is done by the heap pointer manager. The heap
pointer manager can be in the support hardware.
Alternatively, the heap pointer manager can be in a separate
program in the Ada program address space if the support
hardware provides a data path from the heap pointer manager
program to the pointer storage.
<figure shows pointers from program address space to heap
memory locations>
Figure 4.
The decision to use address pointers depends on the
range of heap object sizes and the cost of memory. In the
case of large objects (as in AI applications) and/or
expensive memory (as in avionics applications), the address
pointers may be the most economical implementation. In the
case of small objects and/or inexpensive memory (as in an
office workstation), the software-only implementation of
HeapGuard may be the most economical implementation.
The size of heap memory required for software or
hardware implementation of pointers can be calculated. For
purposes of explanation assume that the heap memory is
organized as 32 bit words (4 bytes) and that each address
pointer is 16 bits (2 bytes). Further assume that the Ada
program wishes to use a heap of size N words. In order to
simplify the explanation, assume that the heap usage is
derated by exactly 50%. For random usage patterns, the
address pointers will occupy a memory space of 2*N and each
pointer will be capable of pointing to any word in the actual
heap. For non-random usage patterns refer for examples to
Robson [ROB]. If the Ada program wishes to be able to
allocate one word (and larger) objects then 2*N pointers must
be provided. The total storage used for actual heap (4
bytes/word * N words) and pointers (2 bytes/pointer * 2N
pointers) is 4*N + 2*2N = 8N bytes. In this case of one word
objects (see Figure 4) it would be simpler to provide the
actual heap space of 2N words (8N bytes) and implement
HeapGuard in software only.
<figure shows one pointer per heap block>
Figure 5.
By instrumenting an application, the sizes of objects
the application allocates can be determined. Now assume that
the Ada program's heap object's sizes are always some
multiple of 4 words, (see figure 5) termed a 4 word block.
The address pointer memory space, as seen by the Ada program,
will still be 2N but only 2N/4 address pointers need to be
provided, one to each block. This is simply implemented by
not decoding the 2 least significant bits of the heap memory
address. In this case of 4 word blocks the memory required
for actual heap (4 bytes/word * N words) and pointers (2
bytes/pointer * 2N/4 pointers) is 4*N + 2*2N/4 = 4*N + N
bytes.
Conclusions
In real-time computer systems, heap memory could be
managed using HeapGuard in order to provide predictable
timing and eliminate storage errors due to fragmentation. If
feasible, a coprocessor could be provided to manage the
dynamic memory and increase system throughput. If the
application program is known to store only small objects,
then a software-only implementation could be effective. If
the application program is known to store many large objects
in dynamic memory then the coprocessor could provide and
manage a set of pointers to these large objects. If the
program stores many small and many large objects, then a
software-only heap for the small objects and an address
pointer based heap for large objects could be provided.
Disclaimer
Neither the author, Integrated Software, Inc., nor the U. S.
Government in any way warrant HeapGuard for any usage and
are not responsible for any consequences of its usage.
Integrated Software, Inc., retains all rights to the
HeapGuard technique and a patent is pending. As such, the
HeapGuard technique and the HeapGuard name are subject to
use only with permission from ISI.
Acknowledgements
This research and development was sponsored by:
Wright Research and Development Center
Avionics Laboratory
Wright-Patterson AFB, Ohio 45433-6543
In particular we wish to acknowledge Sharon Barklay, Captain
Rick A. Long, Lt. Rick Ricart, Terry Rogers, James Williamson
and Lt. Jon Wood for their support.
And we wish to thank Larry Koos, of Koos Technical Services,
Orlando FL, for his support.
A special thanks is due to Professor John McHugh at the
University of North Carolina, Chapel Hill, NC.
<note to Ada BB readers: John computed worst-case upper
bounds values from Robsen's paper>
References
[Aho] "Data Structures and Algorithms",
A. V. Aho et al, Addison-Wesley, 1983, ISBN 0-201-00023-7
[Booch] Software Engineering with Ada, 2nd edition (1986),
Grady Booch, Benjamin-Cummings, ISBN 0-8053-0604-8
[LRM] ANSI/MIL-STD-1815A The Ada Programming Language
[McEntee] "Garbage Collection Enhances AI, Symbolic
Processing Functions", Timothy J. McEntee, Computer
Technology Review, Summer 1986
[ROB] "An Estimate of the Store Size Necessary for Dynamic
Storage Allocation", J. M. Robson, JACM, Vol 18, No 3, July
71, pp 416-423.
About the Authors
Sam Harbaugh received his BSEE, MSEE and PhD EE (1964) from
Carnegie Institute of Technology (now Carnegie-Mellon
University). He has 25 years experience in real-time
computer systems, 7 years using Ada. He is President of
Integrated Software, Inc., which specializes in real-time Ada
for applications such as Avionics, Expert Systems and Aircrew
Training Simulators.
Bill Wavering received his BSCS from the University of
Illinois (1977), and MSCS (1982) from Florida Institute of
Technology. He has 13 years experience in real-time computer
systems, the past 2 years using Ada, and the past 5 years
using Artificial Intelligence techniques. He is currently
concluding a research project during which hardware support
for the Ada Fuzzy Expert System (AFES, available from ISI),
and for HeapGuard, was developed. He is, also, Principal
Investigator on a NASA contract to research techniques for
inference in a real-time expert system. He is a Member of
the Technical Staff of Integrated Software, Inc.
The authors may be reached at: Integrated Software, Inc.,
1945 Palm Bay Rd. N.E. #7, Palm Bay, FL 32905, 407-984-1986
---
* HeapGuard is a trademark of Integrated Software, Inc.
* For an explanation of first-fit allocation see [Aho].
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~1991-07-20 18:45 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1991-07-20 18:45 ZZZZ HeapGuard Naecon paper (16,047 Bytes) SAHARBAUGH
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox