Memory Allocator / Garbage Collector

 

What is a Memory Allocator?

  • A memory allocator is a system that allocates and manages memory blocks for programs during execution.

  • It keeps track of free and used memory.

  • Example: malloc(), calloc() in C are memory allocators.

📚 What is a Garbage Collector?

  • A garbage collector automatically frees memory that a program no longer uses.

  • It reclaims unused memory and prevents memory leaks.

  • Languages like Java, Python have automatic garbage collectors.

  • C/C++ do NOT have built-in garbage collectors — programmers manually free() memory.

 Simulation Idea using Doubly Linked List:

We can simulate memory allocation and garbage collection using a doubly linked list:

  • Each node represents a memory block.

  • Each node has:

    • block_id → unique ID for the block.

    • size → size of the memory block.

    • allocated → 1 if allocated, 0 if free.

    • prev and next → for doubly linked list links.

➡️ When we allocate:

  • Find a free block (allocated = 0).

  • Mark it as allocated.

➡️ When we deallocate (simulate garbage collection):

  • Mark the block as free (allocated = 0).

Algorithms:

1. Create a Node

  • Create a block with id, size, and mark it as free (allocated = 0).

2. Memory Allocation

  • Search for a free block.

  • If found, mark as allocated.

3. Garbage Collection

  • Free the memory (allocated = 0) based on block id.

4. Display Memory Status

  • Show all blocks with their ID, size, and status (allocated or free).


C program - Memory Allocator/ Garbage Collector
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Block {
    int block_id;
    int size;
    int allocated; // 0 = free, 1 = allocated
    struct Block* prev;
    struct Block* next;
};

struct Block* head = NULL;

// Create a new memory block
struct Block* createBlock(int id, int size) {
    struct Block* newBlock = (struct Block*)malloc(sizeof(struct Block));
    newBlock->block_id = id;
    newBlock->size = size;
    newBlock->allocated = 0; // initially free
    newBlock->prev = NULL;
    newBlock->next = NULL;
    return newBlock;
}

// Add block to the list
void addBlock(int id, int size) {
    struct Block* newBlock = createBlock(id, size);

    if (head == NULL) {
        head = newBlock;
    } else {
        struct Block* temp = head;
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = newBlock;
        newBlock->prev = temp;
    }
}

// Allocate a block
void allocateBlock(int id) {
    struct Block* temp = head;
    while (temp != NULL) {
        if (temp->block_id == id) {
            if (temp->allocated == 0) {
                temp->allocated = 1;
                printf("Block %d allocated successfully.\n", id);
            } else {
                printf("Block %d is already allocated.\n", id);
            }
            return;
        }
        temp = temp->next;
    }
    printf("Block %d not found.\n", id);
}

// Garbage collection (deallocate block)
void garbageCollect(int id) {
    struct Block* temp = head;
    while (temp != NULL) {
        if (temp->block_id == id) {
            if (temp->allocated == 1) {
                temp->allocated = 0;
                printf("Block %d deallocated successfully (garbage collected).\n", id);
            } else {
                printf("Block %d is already free.\n", id);
            }
            return;
        }
        temp = temp->next;
    }
    printf("Block %d not found.\n", id);
}

// Display memory status
void displayMemory() {
    struct Block* temp = head;
    printf("\nMemory Status:\n");
    printf("ID\tSize\tStatus\n");
    while (temp != NULL) {
        printf("%d\t%d\t%s\n", temp->block_id, temp->size, (temp->allocated ? "Allocated" : "Free"));
        temp = temp->next;
    }
}

int main() {
    int choice, id, size;

    do {
        printf("\nMenu:\n");
        printf("1. Add Memory Block\n2. Allocate Block\n3. Garbage Collect (Free Block)\n4. Display Memory\n5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter block ID and size: ");
                scanf("%d %d", &id, &size);
                addBlock(id, size);
                break;
            case 2:
                printf("Enter block ID to allocate: ");
                scanf("%d", &id);
                allocateBlock(id);
                break;
            case 3:
                printf("Enter block ID to free: ");
                scanf("%d", &id);
                garbageCollect(id);
                break;
            case 4:
                displayMemory();
                break;
            case 5:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice!\n");
        }

    } while (choice != 5);

    return 0;
}

Memory Status:
ID      Size    Status
1       100     Free
2       200     Free
3       250     Free

After allocating block-2
Memory Status:
ID      Size    Status
1       100     Free
2       200     Allocated
3       250     Free

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more