This chapter is from the book
This chapter is from the book
This chapter is from the book
6.2 Static Allocation Pattern
The Static Allocation Pattern applies only to simple systems with highly predictable and consistent loads. However, where it does apply, the application of this pattern results in systems that are easy to design and maintain.
6.2.1 Abstract
Dynamic memory allocation has two primary problems that are particularly poignant for real-time and embedded systems: nondeterministic timing of memory allocation and deallocation and memory fragmentation. This pattern takes a very simple approach to solving both these problems: disallow dynamic memory allocation. The application of this pattern means that all objects are allocated during system initialization. Provided that the memory loading can be known at design time and the worst-case loading can be allocated entirely in memory, the system will take a bit longer to initialize, but it will operate well during execution.
6.2.2 Problem
Dynamic memory allocation is very common in both structured and object design implementations. C++, for example, uses new and delete, whereas C uses malloc and free to allocate and deallocate memory, respectively. In both these languages, the programmer must explicitly perform these operations, but it is difficult to imagine any sizable program in either of these languages that doesn't use pointers to allocated memory. The Java language is even worse: All objects are allocated in dynamic memory, so all object creation implicitly uses dynamic memory allocation. Further, Java invisibly deallocates memory once it is no longer used, but when and where that occurs is not under programmer control.1 As common as it is, dynamic memory allocation is somewhat of an anathema to real-time systems because it has two primary diffi-culties. First, allocation and deallocation are nondeterministic with respect to time because generally they require searching data structures to find free memory to allocate. Second, deallocation is not without problems either. There are two strategies for deallocation: explicit and implicit. Explicit deallocation can be deterministic in terms of time (since the system has a pointer to its exact location), and the programmer must keep track of all conditions under which the memory must be released and explicitly release it. Failure to do so correctly is called a memory leak, since not all memory allocated is ultimately reclaimed, so the amount of allocable storage decreases over time until system failure. Implicit deallocation is done by means of a Garbage Collector—an object that either continuously or periodically scans memory looking for lost memory and reclaiming it. Garbage collectors can be used, but they are more nondeterministic than allocation strategies, require a fair amount of processing in and of themselves, and may require more memory in some cases (for example, if memory is to be compacted). Garbage collectors do, on the other hand, solve the most common severe defects in software systems.
The third issue around dynamic memory is fragmentation. As memory is allocated in blocks of various sizes, the deallocation order is usually unrelated to the allocation order. This means that what was once a contiguous block of free memory ends up as a hodgepodge of free and used blocks of memory. The fragmentation increases the longer the system runs until eventually a request for a block of memory cannot be fulfilled because there is no single block large enough to fulfill the request, even though there may be more than enough total memory free. This is a serious problem for all real-time and embedded systems that use dynamic memory allocation—not just for those that must run for longer periods of time between reboots.
6.2.3 Pattern Structure
Figure 6-1 shows the basic structure for this pattern. It is structurally very simple but can handle systems of arbitrary size via nesting levels of abstraction. The System Object starts the initialization process and creates the highest-level Composite Objects. They have composition relations to other Composite Objects or to Primitive Objects. The latter are defined to be objects that do not create other objects dynamically. Composition relations are used because they clearly identify the creation/deletion responsibilities.
)
Figure 6-1: Static Allocation Pattern
6.2.4 Collaboration Roles
Allocation Plan
The Allocation Plan, if present, identifies the order in which the largest system composite objects should be allocated. If not present, then the system can allocate objects in any order desired.
Composite Object
A Composite Object, by definition within this pattern, is an object that has composition relations to other objects. These other objects may either be composites or primitive objects. A Composite Object is responsible for the creation of all objects that it owns via composition. There is a constraint on this object (and the System Object as well) that memory cannot be deallocated. Composites may be composed of other composites, but, as stated in the UML specification, each object owned via a composition relation may only belong to one such relation. This means that the creation responsibility for every object in the system is clearly identified in the pattern.
Part Object
This is a superclass of Composite Object and Primitive Object. This allows both System Object and Composite Object to contain, via composition, both Composite Objects and Primitive Objects.
Primitive Object
A Primitive Object is one that does not allocate any other objects. All Primitive Objects are created by composites.
System Object
The System Object is structurally the same as a Composite Object, except that it may own an Allocation Plan and is the highest abstraction possible in the system. Its responsibility is to "kick-start" the system by creating and initializing the primary pieces of the system (the highest level Composite Objects), which in turn create their pieces, and so on. Once the objects all are created, the System Object then begins system execution by running the begin operation.
6.2.5 Consequences
The Static Allocation Pattern is useful when the memory map can be allocated for worst case at run-time. This means that (1) the worst case is known and well understood, and (2) there is enough system memory to handle the worst case. Systems that work well with this pattern typically don't have much difference between worst and average case; that is, they have a consistent memory load for all execution profiles. System behavior is likewise relatively simple and straightforward. This means that the systems using this pattern will usually be small. The need to allocate the memory for all possible objects means that it can easily happen that more memory will be required than if dynamic allocation was used. Therefore, the system must be relatively immune to the cost of memory. When the cost of memory is very small with respect to overall cost, this pattern may be applicable.
There are a number of consequences of the Static Allocation Pattern. First of all, because creation of all objects takes place at startup, the execution of the system after initialization is generally faster than when dynamic allocation is used, sometimes much faster. Run-time execution is usually more predictable as well because of the removal of one of the primary sources for system nondeterminism. Further, since no deallocation is done, there is no memory fragmentation whatsoever.
Since all allocation is done at start time, there may be a noticeable delay from the initiation of startup until the system becomes available for use. In some systems that must have a very short startup time, this may not be acceptable. An ideal system run-time profile is that the system can handle a long start time but must provide minimum response time once operation has begun.
6.2.6 Implementation Strategies
This pattern is very easy to implement. In many cases, a separate initialize method may not be required—and the constructor of each of the composites may be used.
6.2.7 Related Patterns
Other patterns in this chapter address these same issues but provide somewhat different benefits and consequences. See, for example, Pool Allocation, Fixed Sized Buffer, Garbage Collector, and Garbage Compactor Patterns.
6.2.8 Sample Model
Figure 6-2 shows a simple example using instances of a fully constructed system. Figure 6-2a shows the instance structure with an object diagram, and Figure 6-2b shows how the Static Allocation Pattern works on startup. You can see how the creation process is delegated to the composite objects of decreasing abstraction until the primitive objects are constructed.
)
Figure 6-2: Static Allocation Pattern Example