1

HEAP MEMORY MANAGEMENT

Memory areas

In languages like C or Java,the memory used by a program can be allocatedfrom three different areas:

• Astatic area, which is laid out at compilationtime, and allocated when the program starts,

• Astack, from which memory is allocated andfreed dynamically, in LIFO order,

• Aheap, from which memory is allocated andfreed dynamically, in any order.

Location of data

Each of the areas presented before is useful tostore different kinds of data:

• Global variables and constants go into thestatic area,

• Local variables and method parameters go intothe stack,

• All data outliving the method which createdthem go into the heap. In Java, objects are stored in the

heap.

The memory management techniques we discuss in this lecture apply exclusivelyto the management of the heap.

Management of freememory

  • The memory manager is part of the Operating System. It must keep trackof which parts of the heap are free, and which areallocated.To keep track of free memory a memory manager uses a data structure called free list.

A free list is a data structure that keeps track of free memory blocks in a scheme for dynamic memory allocation.

  • Memory manager:
  • allocates memory needed by programs.
  • releases (deallocates) memory no longer needed by programs.
  • defragments memory.

A memory manager supports the following two allocation and deallocationoperations:

  • acquire(size) : searches for a contiguous block of size bytes from the heap and returns a reference to that block. It throws an exception if such a block does not exist.
  • release(address, size) : returns the indicated block to the heap for reuse

The aim of allocation is to find a free block big enough to satisfy the request, and possibly split it

in two if it is too big: one part is then returned as the result of the allocation, while the other is put

back in the free list.

On deallocation, adjacent free blocks can becoalesced (ie., combined) to form bigger free blocks.

Problems faced in memory allocation:

  • Memory fragmentation:
  • External fragmentation

Memory wasted outside allocated blocks

  • Internal fragmentation

Memory wasted inside allocated block(s). Results when memory allocated is larger than memory requested.

  • Overhead: Additional memory that must be allocated, above and beyond that requested by programs, in order tp provide for the management of the heap. For example, it may require a few words of memory to describe the location of each allocated memory block.

Allocation policies

Whenever a block of memory is requested, therewill in general be several free blocks big enough

to satisfy the request.A policy must therefore be used to decide whichof those candidates to choose.

There are several such policies: first fit, next fit, best fit, worst fit, etc.

First fit chooses the first block in the free list bigenough to satisfy the request, and split it.

Next fit is like first fit, except that the search for afitting block will start where the last one stopped,

instead of at the beginning of the free list.

Best fit chooses the smallest block bigger thanthe requested one.

Worst fit chooses the biggest, with the aim ofavoiding the creation of too many smallfragments – but doesn’t work well in practice.

Free list implementations

  • Free list common implementations:
  • singly-linked list
  • doubly-linked list
  • buddy systems: an array of doubly-linked lists
  • Singly-linked list implementation of free-list:
  • nodes must be sorted according to start addresses of free blocks so that adjacent free memory blocks can be combined.
  • acquire( ) operation is O(n); release( ) operation is O(n); where n is the number of blocks in the heap.
  • In order to free a block, a node must be inserted or modified at the appropriate place in the free list. Searching for the node has complexity O(n).

Example: Assume that the node structure of singly-linked free-list is:

Suppose the initial state of the heap is:

where the shaded areas are allocated blocks. The corresponding free-list is:

The operation acquire(700) using the first-fit allocation policy will result in:

The corresponding free-list is:

The operation release(400, 1100) , i.e., release 400 bytes starting at address 1100, will result in:

The corresponding free-list is:

The operation release(900, 2300) will result in:

The corresponding free-list is:

  • Doubly-linked list implementation of free-list:
  • nodes are not sorted according to start addresses of free blocks.
  • acquire( ) operation is O(n); release( ) operation is O(1)

The release operation does not combine adjacent free blocks. It simply prepends a node corresponding to a freed block at the front of the free list. This operation is thus O(1). Adjacent free blocks are combined by acquire().

The acquire operation traverses the free list in order to find a free area of a suitable size. As it does so it also combines adjacent free blocks.

Boundary Tags

Boundary tags are data structures on the boundary between blocks in the heap from which storage is allocated. The use of such tags allows blocks of arbitrary size to be used, they also make it easier to coalesce (i.e., combine) adjacent free blocks. The tag describes for each block, how big it is, its status (allocated or free), and the addresses of its neighbours.

Example: Assume the node structure of a doubly-linked free-list is:

Note: We may also include the status (allocated or free) of each of the three blocks in the node.

Suppose the initial state of the heap is:

where the shaded areas are allocated blocks and the grayed areas are boundary tags. The corresponding free-list is:

The operation release(400, 4000) will result in:

Notice that the adjacent free blocks starting from address 3200 to 4700 are not combined at this stage. The node corresponding to the freed block is appended at the front of the free-list:

The nodes x, y, and z correspond to the three free blocks that have not yet been combined.

The operation acquire(600) using the first-fit allocation policy will first result in the combination of the three adjacent free blocks:

At this point the corresponding free list is:

The required 600 bytes are then allocated, resulting in:

The corresponding free list is:

  • Buddy Systems implementation of free-list:

Instead of having a single free list, it is possible to have an array of free lists; each element of the array holding blocks of (approximately) the same size. One type of buddy systems is the binary buddy system.

  • For a memory of size m, there are free-lists of size 20, 21, 22, . . . , 2k, where m 2k

Example:

  • The heap is viewed as one large block which can be split into two equal smaller blocks, called buddies. Each of these smaller blocks can again be split into two equal smaller buddies, and so on. Each memory block has its “buddy”. The “buddy” of a block of size 2k that starts at address x is the block of size 2k that start at address y = complementBit_k(x), where the address bits are numbered from right to left starting with 0.

Example: If each block is of size 8 bytes (i.e., 23 bytes); then the buddy of a block is obtained by complementing bit 3 of its starting address. If each block is of size 4 bytes (i.e., 22 bytes); then the buddy of a block is obtained by complementing bit 2 of its starting address.

Example: What is the starting address of the buddy of a block that starts at address 1100101010101101 if each block is 16 bytes?

Solution: 16 = 24; the starting address of the buddy is obtained by complementing bit 4:

1100101010111101

  • Disadvantages of Binary Buddy Systems:
  • Only memory of size that is a power of 2 can be allocated  internal fragmentation if memory request is not a power of 2.
  • A freed block can only be returned to the free-list if its buddy is also free  external fragmentation.
  • Advantages of Binary Buddy Systems:
  • Both acquire( ) and release( ) operations are fast.

Binary Buddy System Algorithms

When a request is made for a block of size x <= 2k,a search is made in the corresponding free list. If there is a block in this list, it is allocated; otherwise if there are no free blocks of size 2k, we can obtain one by splitting a block of size 2k+1 in two. And if there are no blocks of size 2k+1, we can obtain one of those by splitting a block of size 2k+2 in two, and so on. If we reach the heap size without obtaining an appropriate free block; the request cannot be satisfied; an exception is thrown. When a block is split into two buddies, it is taken off the free list of its size. One buddy is placed on the free list for the next lower size, and the other is used, splitting it again if needed.

When a block of memory is of size 2k is released, it is placed back in the free list of its size, and if its buddy is also free they are combined to form a free block of size2k+1. This block is then moved to the corresponding free list. If its buddy is free they are combined to form a free block of size 2k+2, which is then moved to the appropriate free list and so on.

Example: Assume the size of an initially empty heap is 256K. The corresponding free-list is:

The corresponding heap memory layout is:

Suppose the memory manager issues the following requests in Kilobytes: acquire(9), acquire(32), acquire(30), release(30), release(9), release(32) in the given order:

  1. acquire(9)

There are no free blocks of size 16, 32, 64, and 128. The block of size 256 is split into two; these two blocks are attached to the free-list of blocks of size 128:

One of the blocks of size 128 is split into two; the resulting two blocks of size 64 are attached to the free-list of blocks of size 64:

One of the blocks of size 64 is split into two; the resulting two blocks of size 32 are attached to the free-list of blocks of size 32:

One of the blocks of size 32 is split into two; the resulting two blocks of size 16 are attached to the free-list of blocks of size 16:

One block of size 16 is allocated; since the request was for 9KB; 7KB are wasted in internal fragmentation:

The corresponding heap memory layout is:

  1. acquire(32)

There is a free block of size 32; this is allocated:

The corresponding heap memory layout is:

  1. acquire(30)

There is no free block of size 32. The free block of size 64 at the free-list of blocks of size 64 is

split into two; the resulting blocks of size 32 are moved to the free-list of blocks of size 32:

One of the 32KB blocks is allocated; since the request was for 30KB, 2KB are wasted in internal fragmentation:

The corresponding heap memory layout is:

  1. release(30)

The buddy of the released 32KB block is free. The two blocks are combined to form a block of

size 64:

This 64KB block is then moved to its free-list:

The corresponding heap memory layout is:

  1. release(9)

The buddy of the released 16KB block is free. The two blocks are combined to form a block of

size 32:

This 32KB block is then moved to its free-list:

The corresponding heap memory layout is:

  1. release(32)

The buddy of the released 32KB block is free. The two blocks are combined to form a block of

size 64:

This 64KB block is then moved to its free-list:

The buddy of the 64KB block is free. The two blocks are combined to form a block of

size 128; this is then attached to its free-list:

The buddy of the 128KB block is free. The two blocks are combined to form a block of

size 256; this is then attached to its free-list:

The corresponding heap memory layout is: