Garbage Collection and Compaction

 

🧹 Garbage Collection and Compaction

1. What is Garbage Collection?

Garbage Collection is the process of identifying and reclaiming memory that is no longer in use by any program.

  • After a process releases memory (explicitly or automatically), that memory becomes "garbage" if not reclaimed.

  • Garbage collection frees up this memory so that it can be used for new allocations.

Key idea: Automatically clean unused memory blocks.

✨ Example:

Suppose memory blocks are:

Block Address        Size        Used/Free
1000        200        Used
1200        150        Free
1350        300        Used
1650        100        Free
1750        200        Free
Garbage collection will identify blocks at 1200, 1650, and 1750 as free memory.

2. What is Compaction?

Compaction is the process of rearranging memory contents so that all free memory is combined together into one large block.

  • After garbage collection, free blocks may be scattered.

  • Compaction moves used memory blocks together and pushes free space to one side.

Key idea: Minimize fragmentation and maximize continuous free memory.

✨ Example (after compaction):

Initially:


[Used 200][Free 150][Used 300][Free 100][Free 200]

After Compaction:


[Used 200][Used 300][Free 450]

  • All free space becomes one large block of 450 KB.

🎯 Why are Garbage Collection and Compaction Important?

  • Avoids memory leaks.

  • Ensures large memory blocks are available.

  • Improves system performance.

  • Essential in systems like Java Virtual Machine (JVM) and Operating Systems.

🧠 Linked List Representation

  • Each memory block = one node.

  • Fields:

    • Start Address

    • Size

    • Status (Used or Free)

    • Pointer to next block

    • Pointer to previous block

🔵 C Program: Garbage Collection and Compaction using doubly Linked List

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Define structure for memory block (Doubly Linked List)
struct Block {
    int start_address;
    int size;
    int is_free; // 1 if free, 0 if used
    struct Block* prev;
    struct Block* next;
};

struct Block* head = NULL;

// Create a new block
struct Block* create_block(int start, int size, int is_free) {
    struct Block* new_block = (struct Block*)malloc(sizeof(struct Block));
    new_block->start_address = start;
    new_block->size = size;
    new_block->is_free = is_free;
    new_block->next = NULL;
    new_block->prev = NULL;
    return new_block;
}

// Add block to the end
void add_block(int start, int size, int is_free) {
    struct Block* new_block = create_block(start, size, is_free);

    if (head == NULL) {
        head = new_block;
        return;
    }

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

    temp->next = new_block;
    new_block->prev = temp;
}

// Display memory blocks
void display_memory() {
    struct Block* temp = head;
    printf("\nMemory Blocks:\n");
    printf("----------------------------\n");
    while (temp != NULL) {
        printf("Start: %d, Size: %d, Status: %s\n",
               temp->start_address,
               temp->size,
               temp->is_free ? "Free" : "Used");
        temp = temp->next;
    }
    printf("----------------------------\n");
}

// Garbage collection: merge adjacent free blocks
void garbage_collection() {
    struct Block* temp = head;

    while (temp != NULL && temp->next != NULL) {
        if (temp->is_free && temp->next->is_free) {
            // Merge with next
            temp->size += temp->next->size;
            struct Block* to_delete = temp->next;
            temp->next = to_delete->next;

            if (to_delete->next != NULL) {
                to_delete->next->prev = temp;
            }

            free(to_delete);
        } else {
            temp = temp->next;
        }
    }
}

// Compaction: move used blocks to front, merge all free blocks
void compaction() {
    struct Block* new_head = NULL;
    struct Block* last_used = NULL;
    int current_address = 1000;

    // Move used blocks
    struct Block* temp = head;
    while (temp != NULL) {
        if (!temp->is_free) {
            struct Block* new_block = create_block(current_address, temp->size, 0);
            current_address += temp->size;

            if (new_head == NULL) {
                new_head = new_block;
                last_used = new_head;
            } else {
                last_used->next = new_block;
                new_block->prev = last_used;
                last_used = new_block;
            }
        }
        temp = temp->next;
    }

    // Calculate total free space
    int free_size = 0;
    temp = head;
    while (temp != NULL) {
        if (temp->is_free) {
            free_size += temp->size;
        }
        temp = temp->next;
    }

    if (free_size > 0) {
        struct Block* free_block = create_block(current_address, free_size, 1);
        if (new_head == NULL) {
            new_head = free_block;
        } else {
            last_used->next = free_block;
            free_block->prev = last_used;
        }
    }

    // Free old memory list
    temp = head;
    while (temp != NULL) {
        struct Block* next = temp->next;
        free(temp);
        temp = next;
    }

    head = new_head;
}

int main() {
    // Initial memory setup
    add_block(1000, 200, 0); // Used
    add_block(1200, 150, 1); // Free
    add_block(1350, 300, 0); // Used
    add_block(1650, 100, 1); // Free
    add_block(1750, 200, 1); // Free

    printf("\nBefore Garbage Collection and Compaction:");
    display_memory();

    garbage_collection();
    printf("\nAfter Garbage Collection:");
    display_memory();

    compaction();
    printf("\nAfter Compaction:");
    display_memory();

    return 0;
}

Output
Before Garbage Collection and Compaction:
Memory Blocks:
--------------------------------------------
Start: 1000, Size: 200, Status: Used
Start: 1200, Size: 150, Status: Free
Start: 1350, Size: 300, Status: Used
Start: 1650, Size: 100, Status: Free
Start: 1750, Size: 200, Status: Free
---------------------------------------------

After Garbage Collection:
Memory Blocks:
--------------------------------------------
Start: 1000, Size: 200, Status: Used
Start: 1200, Size: 150, Status: Free
Start: 1350, Size: 300, Status: Used
Start: 1650, Size: 300, Status: Free
----------------------------------------------

After Compaction:
Memory Blocks:
--------------------------------------------
Start: 1000, Size: 200, Status: Used
Start: 1200, Size: 300, Status: Used
Start: 1500, Size: 450, Status: Free
--------------------------------------------

Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and evaluation scheme  1.Basic Concepts of Data Structures     Data structures and data abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to prefix and prefix evaluation    2.Linked List and Memory Management          Self Referential Data Structures     Dynamic Memory Allocation in C     Singly Linked...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more

Data Structures and Data Abstraction

  What is a Data Structure? A data structure is a way to organize, manage, and store data so that it can be used efficiently . It defines how data is arranged in memory and how operations like insertion , deletion , searching , and updating can be performed. In simple words: Data structures are like containers that hold data together in a certain format so that computers can easily access and modify them.   More formally   "A data structure is a mathematical and logical model of a particular organization of data. It describes the relationship among the data elements, and the operations that can be performed on them." ➔ Key points: Organization of data. Logical relationship between data elements. Set of operations that can be applied (like insert, delete, search, etc.). Key Points about Data Structures: They help in organizing large amounts of data easily. They improve the efficiency of algorithms. They decide how fast and efficient prog...
Read more