Memory Management in Stage 2 (Protected Mode)

First let us get familiar with the term Memory.

Memory: Memory in computing refers to the component of a computer system responsible for storing data and instructions that the processor needs to access quickly. It plays a crucial role in the performance and functionality of a computer, as it temporarily holds information that the CPU (Central Processing Unit) actively uses to perform tasks.

Types of Memory in Computing

1. Primary Memory (Main Memory):
   • Random Access Memory (RAM): This is the most common type of primary memory. RAM is volatile, meaning it loses its contents when the power is turned off. It temporarily holds data and instructions that the CPU needs while executing programs. RAM is fast and directly accessible by the CPU, making it essential for running applications and the operating system.
   • Cache Memory: A small, high-speed memory located inside or very close to the CPU. It stores frequently accessed data and instructions to speed up processing. Cache memory is faster than RAM and is used to reduce the time it takes for the CPU to access data from the main memory.
   • Read-Only Memory (ROM): Non-volatile memory that stores critical information needed for the computer to boot up, such as the BIOS (Basic Input/Output System). Data in ROM cannot be modified or can only be modified slowly or with difficulty, so it's mainly used for firmware.
2. Secondary Memory (Storage):
   • Hard Disk Drives (HDD) and Solid State Drives (SSD): These are non-volatile storage devices that hold data permanently until it is deleted or modified. Secondary memory is used to store the operating system, applications, and user data. SSDs are faster than HDDs because they use flash memory to store data, whereas HDDs use spinning disks.
   • Optical Discs (CDs, DVDs, Blu-rays): Use laser technology to read and write data. They are often used for storing large amounts of data, such as software, movies, and games.
   • USB Flash Drives and External Storage Devices: Portable storage devices that use flash memory. They are often used for transferring data between computers or for backup purposes.

Memory Management

Memory management is the process of controlling and coordinating computer memory, assigning portions of memory to various running programs to optimize overall system performance. It involves multiple tasks, such as allocating memory space for processes, managing virtual memory, and handling memory deallocation when processes no longer need certain memory regions.

Memory Management is one of the fundamental function of a operating system (OS), responsible for managing the computer's primary memory.

Memory Management involves several key responsibilities:

1. Memory Allocation: Memory Allocation refers to the process of reserving a portion of the computer's memory for use by programs and processes. In the context of computing, memory allocation can be broadly divided into two categories:
   • Static Memory Allocation: In this memory is allocated at compile time, and the size and location of the memory do not change during runtime. This is typically used for global variables and static arrays.
   • Dynamic Memory Allocation: In this memory is allocated at runtime based on the program's needs. This allows for more flexible and efficient use of memory, as the exact memory requirements of a program might not known until it runs. It is achieved using the function like malloc, free, calloc, and realloc in C. Memory allocation works on heap memory.
2. Memory Deallocation: After a program has finished using a block of memory, the OS deallocates it, freeing it up for other programs to use. Proper deallocation is crucial to prevent memory leaks, which can lead to inefficient memory usage or system crashes.
3. Memory Mapping: The OS maps the logical addresses used by a program to physical addresses in the computer's memory. This mapping allows programs to be executed efficiently, regardless of where in physical memory they are loaded.
4. Memory Protection: To ensure that one process does not interfere with another, the OS implements memory protection mechanisms. This prevents unauthorized access to memory regions, ensuring system stability and security.

Memory Pool vs. Heap

Both memory pools and the heap are used for dynamic memory allocation, but they serve different purposes and have distinct characteristics.

Heap

• General-Purpose: The heap is a general-purpose memory area used for dynamic memory allocation. When you use functions like malloc, calloc, realloc, or new (in C++), the memory is allocated from the heap.
• Flexible Size: The heap can dynamically grow and shrink as needed, and it can allocate memory blocks of various sizes.
• Fragmentation: Since the heap can allocate and free memory blocks of arbitrary sizes, it is prone to fragmentation. Fragmentation occurs when there are many small gaps of unused memory between allocated blocks, making it difficult to allocate large contiguous memory blocks even if enough total memory is available.
• Speed: Allocating and deallocating memory from the heap can be relatively slow, especially if the system has to search for a suitably sized block or handle fragmentation.
• Example Usage: General-purpose dynamic memory allocation for data structures like arrays, linked lists, trees, etc.

Memory Pool

• Special-Purpose: A memory pool, also known as a fixed-size block allocator or slab allocator, is a pre-allocated block of memory that is divided into smaller, fixed-size blocks. These blocks are then allocated and deallocated very quickly.
• Fixed Block Size: Memory pools typically allocate blocks of a fixed size, which can make memory allocation and deallocation much faster than in the heap. This is because the pool knows the size of the blocks in advance and doesn't need to search for a suitable-sized block.
• Reduced Fragmentation: Memory pools are designed to reduce fragmentation by allocating memory in fixed-size chunks. This is especially useful in systems where many objects of the same size are frequently allocated and deallocated.
• Predictability and Efficiency: Because memory pools pre-allocate memory and use fixed-size blocks, they can be more predictable and efficient in terms of both speed and memory usage.
• Example Usage: Situations where the program frequently allocates and deallocates many objects of the same size, such as in real-time systems, networking, or game development.

Different Heap Implementation Strategies

A heap is a region of memory used for dynamic memory allocation, where blocks of memory are allocated and deallocated in arbitrary order. Implementing a heap involves managing free memory blocks and ensuring that memory can be allocated and freed efficiently.

Here are several common heap implementation strategies, each with its advantages and trade-offs:

1. Bump Pointer Allocation

Overview

• Bump Pointer Allocation is one of the simplest heap allocation strategies. It uses a single pointer to keep track of the end of the allocated memory area (the bump pointer).
• Memory is allocated by moving this pointer forward by the requested size.

How It Works

• Initialize a heap region with a bump pointer set to the start of the heap.
• When allocating memory, return the current position of the bump pointer and then advance the pointer by the size of the allocation.
• Memory is deallocated all at once by resetting the bump pointer to the start of the heap.

Pros

• Very simple to implement.
• Fast allocation since no searching or bookkeeping is required.

Cons

• Does not support deallocating individual allocations; all memory must be freed at once.
• Leads to memory fragmentation over time if not managed properly.

Example:

#define HEAP_SIZE 4096
char heap[HEAP_SIZE];
size_t heap_ptr = 0;

void* bump_alloc(size_t size) {
    if (heap_ptr + size > HEAP_SIZE) {
        return NULL;  // Out of memory, return
        				// NULL, or (void*)0
    }
    void* ptr = &heap[heap_ptr];
    heap_ptr += size;
    return ptr;
}

void bump_reset() {
    heap_ptr = 0;  // Reset to free all memory
}

2. Free List Allocation

Overview

• Free List Allocation involves maintaining a list of free memory blocks, allowing for flexible allocation and deallocation.
• Memory blocks are managed in a linked list where each block points to the next free block.

How It Works

• Start with a list of free blocks. Each block contains a pointer to the next free block.
• When memory is allocated, find a suitable block from the free list, remove it from the list, and return it.
• When memory is deallocated, add the block back to the free list.

Pros

• Supports dynamic allocation and deallocation.
• Can reduce fragmentation by reusing free blocks.

Cons

• Requires additional memory to store free list pointers.
• Allocation can be slower due to list traversal.

3. Bitmap Allocation

Overview

• Bitmap Allocation uses a bitmap to keep track of which memory blocks are free or allocated. Each bit in the bitmap corresponds to a fixed-size block in the heap.

How It Works

• Divide the heap into fixed-size blocks.
• Use a bitmap (an array of bits) where each bit represents the status of a block (0 for free, 1 for allocated).
• To allocate memory, find a 0 bit in the bitmap, mark it as 1, and return the corresponding block.
• To deallocate memory, set the corresponding bit back to 0.

Pros

• Fast allocation and deallocation.
• Simple to implement for fixed-size blocks.

Cons

• Not suitable for variable-size allocations.
• May lead to internal fragmentation if blocks are not fully utilized.

#define HEAP_SIZE 4096
#define BLOCK_SIZE 64
#define BITMAP_SIZE (HEAP_SIZE / BLOCK_SIZE)

char heap[HEAP_SIZE];
unsigned char bitmap[BITMAP_SIZE] = {0};

void* bitmap_alloc() {
    for (int i = 0; i < BITMAP_SIZE; ++i) {
        if (bitmap[i] == 0) {
            bitmap[i] = 1;  // Mark block as allocated
            return &heap[i * BLOCK_SIZE];
        }
    }
    return NULL;  // No free block found
    				// return NULL or (void*)0
}

void bitmap_free(void* ptr) {
    size_t offset = (char*)ptr - heap;
    size_t index = offset / BLOCK_SIZE;
    bitmap[index] = 0;  // Mark block as free
}