Game Engine Architecture

217

Memory fragmentation is not as much of a problem on operating sys-
tems that support virtual memory. A virtual memory system maps discontigu-
ous blocks of physical memory known as pages into a virtual address space, in
which the pages appear to the application to be contiguous. Stale pages can
be swapped to the hard disk when physical memory is in short supply and
reloaded from disk when they are needed. For a detailed discussion of how
virtual memory works, see htt p://lyle.smu.edu/~kocan/7343/fall05/slides/
chapter08.ppt. Most embedded systems cannot aff ord to implement a virtual
memory system. While some modern consoles do technically support it, most
console game engines still do not make use of virtual memory due to the in-
herent performance overhead.

5.2.2.1. Avoiding Fragmentation with Stack and Pool Allocators

The detrimental eff ects of memory fragmentation can be avoided by using
stack and/or pool allocators.

• A stack allocator is impervious to fragmentation because allocations are
  always contiguous, and blocks must be freed in an order opposite to
  that in which they were allocated. This is illustrated in Figure 5.4.


• A pool allocator is also free from fragmentation problems. Pools do be-
  come fragmented, but the fragmentation never causes premature out-
  of-memory conditions as it does in a general-purpose heap. Pool alloca-
  tion requests can never fail due to a lack of a large enough contiguous
  free block, because all of the blocks are exactly the same size. This is
  shown in Figure 5.5.

5.2. Memory Management

Figure 5.4. A stack allocator is free from fragmentation problems.

Allocated blocks, always contiguous Single free block, always contiguous

deallocation

allocation

Allocated and free blocks all the same size

Figure 5.5. A pool allocator is not degraded by fragmentation.