Memory Management

Seen in CS241 - Foundations of Sequential Programs and later in SE350 - Operating Systems. Module 9: Memory Management

In C and C++ (also WLP4), memory management is explicit, meaning the programmer must request memory from the heap and indicate that the allocated memory is no longer needed.

In this module, implementation of two memory allocator will be discussed along with their implementation.

The Core Problem

A memory allocator needs some sort of data structure to keep trach how memory was parceled and allocated. BUT that data structure needs to go into memory, the very memory that it’s trying to allocate.\

Free List Algorithm: Maintain a List of Free Blocks

When the allocator is initialized, it will being with a linked list that represents the entire free memory: the heap. This linked list will be updated to keep trach of the free parts on the heap. The [free] pointer is a pointer to the start of the first free block (stored in global memory).

Since the user does not provide the size when deallocating, the allocator must store the sizes. First word in the block to store the amount of memory available in the block, second word, within the heap, is a pointer to the next free block.

Ex:

new int[4];
sizeof(Object);
malloc(16);

The memory allocator will allocate 30 bytes; 4 to store bookkeeping information (save how many bytes to free) and 16 bytes as requested by the programmer.

Responsibility of the program (the mutator), not the allocator, to remember memory that’s in use.

When user calls free on Block A as an argument, as in the example in the course notes, we gave the user back the address 0x104. Because we do not want the user to change the size of the memory allocated, therefore the first thing we need to do when called free is to substract 4 bytes back to get real address of the block to free. so 0x100 needs to be free. Then we check if the address freed is smaller than the head of the free linked list. In our case, yes, so we push it in front of it. Update the correct pointer (watch video).

Problems With the Free List Approach

Can create “holes” in the heap when we repeatetly allocate and deallocate. Not always choose the first block of RAM that is big enough to satisfy allocation request. There is no right solution.

Binary Buddy System

Binary system restricts itself to only allocating blocks of size $2^k$ for some k.

Refer to the course notes.

Binary Buddy System Bookkeeping

How is the free list maintained? I have no idea what’s going on, I don’t think Gregor went over it in class.

”The one obvious disadvantage of using the binary buddy system is that it causes internal fragmentation; by insisting to allocate blocks of certain size, extra memory is allocated/wasted.”

Implicit Memory Management: Garbage Collection

Garbage collector must take the most conservative approach (must not deem any memory to be garbage until it is absolutely certain that the progam will never refer to it again).

Reference Counting

The key to automatic garbage collection is determining which blocks of memory are no longer going to be used by the program. Keep track of the number of pointers that point to each block = algorithm called The Reference Counting algorithm. Algorithm will watch every pointer update so that the reference count to each block is accurate. Now we can deallocate memory whenever the reference count of a block reaches 0, that block can be deleted.

Look up std::shared_ptr: a template class that supports RAII; the idea being that for heap objects with joint ownership, the heap object is wrapped within a stack allocated shared_ptr object. Multiple such shared ptr objects might jointly claim ownership of the same heap object.\

Problem: “The algorithm does also suffer from one other limitation: circular references, a block of memory that refers to another block of memory which refers back to the first block (while 2 is the smallest sequence of blocks, there could be sequences bigger than 2 completing the circle). Together these two blocks might not be accessible from anywhere else in the program but, since their reference counts are not zero, they would never be deallocated. Because of this limitation, reference counting is generally not considered as a complete or workable algorithm for garbage collection.”

Mark and Sweep

”The algorithm begins with a Mark phase where it discovers parts of the heap that are reachable from the stack and global variables. The entire stack (and global variables) is scanned for pointers leading into the heap. Each such heap block is marked as reachable. If the marked heap blocks contain pointers, the algorithm repeatedly follows any such pointers to discover new parts of the heap that are also reachable. Once the entire reachable part of the heap has been marked, the algorithm conducts the sweep phase; any block that was not marked is deallocated, since it was unreachable.”

Copying Collector

”Copying Collectors involve copying live blocks. The classic and original copying collector is Cheney’s Algorithm, which splits the heap into two halves named from and to. Memory is only allocated from the from part of the heap. When this half fills up, the garbage collector runs and copies the reachable parts from from to to. Then the roles of from and to are reversed. One advantage of using this approach is that of automatic compaction; since memory is copied from one half of the heap to another, it can be laid out contiguously thereby avoiding any fragmentation. The algorithm is also a “Stop the World” algorithm and is not truly suitable for applications that expect real-time response guarantees. Additionally, the algorithm halves the amount of heap memory available to the program.”

Pros:

• copying collectors tend to work well when few objects survive collection, and mark-and-sweep works better when most objects survive collection.
• Automatic compaction; since memory is copied from one half of the heap to another, it can be laid out contiguously thereby avoiding any fragmentation.