链接：https://pan.baidu.com/s/1MM1AELWeqEIQ1WPJ2xbwUA 

提取码：fxyr 

 

Introduction

This thesis presents work in the area of automatic memory management

for hard real-time and embedded systems. The motivation of the thesis is

to be able to develop hard real-time and embedded systems using mod￾ern languages. Since these languages commonly use automatic memory

management or garbage collection (GC), which traditionally has had an

unpredictable runtime behavior, we could either try to eliminate the need

for GC using manual techniques, or we could develop GC techniques for

these systems. Since GC is such a powerful tool to eliminate memory re￾lated programming errors, we decided to develop techniques to use GC in

hard real-time and embedded systems. During this work three other GC

techniques for these systems have been published. The main advantage

of our work compared to the other three is that memory utilization effi-

ciency increased by about 50 %. We have also developed an optimization

for incremental garbage collectors and a static garbage collector that aims

to eliminate the need for runtime garbage collection.

1.1 Perspective

Once upon a time, programming required a deep knowledge of how the

machines were constructed and the programmers had full control of the

execution of the system. Charles Babbage became the first programmer

when he programmed his difference machine in 1822. It was programmed

by exchanging the gears that performed the calculations. More than 100

years later in about 1945 Konrad Zuse developed Plankalk¨ul [BW72], the

first programming language. Unfortunately, most work was lost or con-

fiscated in the aftermath of World War II and the work was not published

until 1972. Plankalk¨ul was used to program the Z3, the first universal com￾puter in the world [Roj98].

2 CHAPTER 1. INTRODUCTION

Contemporary computers were more like calculators, and the calcula￾tions where input by punching holes in paper tapes (Z3 and Colossus) or

even by making physical changes to the hardware (ENIAC). In 1945 John

von Neumann published the EDVAC report [vN45] and Alan Turing pub￾lished the ACE Report [TCD86]. Both came to the conclusion that pro￾grams should be stored in memory in the same way as data was. This

was the birth of the computer architecture that is still used today. In 1949,

Short Code [Sch88] was introduced by John W. Mauchly, it was the first

programming languages for the new generation computers.

Programming languages has since evolved, adding features like recur￾sion, pointers, dynamic memory management, garbage collection, struc￾tured programming, object-orientation, etc. Many of these features have

become natural parts of programming languages, and most developers

can not write a non-trivial program without them. These features makes

programming less error-prone, and more complex systems can be imple￾mented. However, with a higher level of abstraction, the control of the

applications runtime behavior is lost. When developing real-time systems,

i.e. systems whose correctness is not only dependent of their output but

also on their timing, it is crucial that the runtime behavior can be predicted.

A conflict occurs when real-time systems become increasingly more

complex. Modern languages would certainly ease development and pro￾duce more stable systems, but the control of the runtime behavior is lost.

The features of modern languages are not the problem, it is the way they

are implemented that cause problems. Their implementations usually try

to optimize average performance, and not worst case performance as is

required in real-time systems. This thesis focuses on automatic memory

management of real-time and embedded systems, and presents techniques

to make it predictable and still efficient.

1.2 Problem Definition

To be able to maintain full control of the runtime behavior of a system,

it must be possible to predict the amount of resources (e.g. CPU time and

memory) that is required for any (virtual) machine level instruction and for

all runtime system work. Note that using such a system does not prevent

writing an unpredictable application. An example is an application that

waits for external events, e.g. input from a user. First, it is not always

possible to know when the event occurs, and second the data passed with

the event may be unknown. Thus, developers must still follow rules to

handle such cases.

Early implementations of new languages are typically designed to be

easy to implement and prove correct. Then follows optimizations for the

average case, which is commonly interactive window based applications

1.3. CONTRIBUTIONS 3

or possibly servers. Techniques that are optimized for such systems are seldom appropriate for hard real-time and embedded systems, because their

target systems need not be predictable and they have much more memory

resources available.

To be more specific, garbage collection algorithms may be designed to

interrupt the application for short time periods in the general case, but it

need not be guaranteed that it will collect all garbage memory before the

system runs out of memory. If the memory runs out, the system can be

stopped to collect the remaining garbage memory. Such stop may take

a second or two, but that does not matter to these systems. Unfortunately

many such techniques are called real-time garbage collectors, which is confusing. Another problem with garbage collectors is that they consume very

much memory. The runtime systems that use real-time garbage collectors

that guarantee memory availability need about 70 % of the system memory for internal use, which leaves about 30 % for the application. A large

contribution to the overhead comes from the memory that is needed to allocate objects while the garbage collector collects garbage memory. This

alone typically causes an overhead of about 50 %.

The garbage collector is not the only part of a runtime system that needs

to be redesigned to make it predictable. Examples of other parts that need

attention are thread support, synchronization, messaging, and some complex instructions. This is, however, out of scope for this thesis.