Memory Allocation - Worst Fit

 

Memory Allocation Strategy: Worst Fit

When a program requests memory, another strategy is the Worst Fit.

What is Worst Fit?

Definition:
In the Worst Fit strategy, the OS searches the entire list of free memory blocks and allocates memory from the largest available block.

  • The idea is to leave behind a reasonably large free block after allocation.

  • It aims to avoid creating many small useless memory fragments.

Example:

Suppose free blocks are: 200KB, 500KB, 300KB, 600KB.

A process requests 250KB:

  • 200KB → too small

  • 500KB → enough

  • 300KB → enough

  • 600KB → enough → largest block

Worst Fit will choose 600KB block.

After allocating 250KB:

  • 600 - 250 = 350KB left.

Advantages of Worst Fit

  • Reduces Very Small Fragments:
    By allocating from the largest block, it leaves larger remaining parts.

  • Better for Large Future Requests:
    Big processes later can still find large blocks.

Disadvantages of Worst Fit

  • Slow Allocation:
    Must search the entire list to find the largest block.

  • Not Always Space Efficient:
    Sometimes leaves big holes in memory that are still wasted.

  • Higher Overhead:
    Searching and managing free memory takes more processing.

Implementing Worst Fit using Linked List

Linked List Structure (same):

  • Start address

  • Size of free block

  • Pointer to next block

Worst Fit Algorithm Steps:

  1. Traverse entire free list.

  2. Find the block with the largest size that is still large enough.

  3. Allocate memory:

    • If exact size → remove the block.

    • If larger → split the block.

Example

Initial Free Memory:


+---------+    +---------+    +---------+    +---------+
| 200 KB  | -> | 500 KB  | -> | 300 KB  | -> | 600 KB  |
+---------+    +---------+    +---------+    +---------+

Process requests 250KB.

Check:

  • 200 → too small

  • 500 → enough

  • 300 → enough

  • 600 → enough → largest block

Allocate from 600 KB block.

Result:


+---------+    +---------+    +---------+    +---------+
| 200 KB  | -> | 500 KB  | -> | 300 KB  | -> | 350 KB  |
+---------+    +---------+    +---------+    +---------+

C Program: Worst Fit Memory Allocation using Linked List

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

// Define structure for memory block
struct Block {
    int start_address;
    int size;
    struct Block* next;
};

struct Block* head = NULL;

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

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

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

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

// Function to display free memory blocks
void display_free_blocks() {
    struct Block* temp = head;
    printf("\nFree Memory Blocks:\n");
    printf("----------------------\n");
    while (temp != NULL) {
        printf("Start: %d, Size: %d KB\n", temp->start_address, temp->size);
        temp = temp->next;
    }
    printf("----------------------\n");
}

// Worst Fit Allocation Function
void worst_fit_allocate(int request_size) {
    struct Block* temp = head;
    struct Block* worst_block = NULL;
    struct Block* worst_prev = NULL;
    struct Block* prev = NULL;

    // Find the worst (largest) block
    while (temp != NULL) {
        if (temp->size >= request_size) {
            if (worst_block == NULL || temp->size > worst_block->size) {
                worst_block = temp;
                worst_prev = prev;
            }
        }
        prev = temp;
        temp = temp->next;
    }

    if (worst_block == NULL) {
        printf("\nAllocation failed: No sufficient memory block available.\n");
        return;
    }

    printf("\nMemory allocated at address: %d\n", worst_block->start_address);

    // Allocate memory
    if (worst_block->size == request_size) {
        // Perfect fit
        if (worst_prev == NULL) {
            head = worst_block->next;
        } else {
            worst_prev->next = worst_block->next;
        }
        free(worst_block);
    } else {
        // Split the block
        worst_block->start_address += request_size;
        worst_block->size -= request_size;
    }
}

int main() {
    // Example initial blocks
    add_block(1000, 200);
    add_block(1200, 500);
    add_block(1700, 300);
    add_block(2000, 600);

    display_free_blocks();

    // Example allocations
    printf("Allocate Process of size 250\n");
    worst_fit_allocate(250);
    display_free_blocks();

    printf("Allocate Process of size 100\n");
    worst_fit_allocate(100);
    display_free_blocks();

    printf("Allocate Process of size 700\n");
    worst_fit_allocate(700); // Should fail
    display_free_blocks();

    return 0;
}

Output

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1200, Size: 500 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
----------------------
Allocate Process of size 250

Memory allocated at address: 2000

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1200, Size: 500 KB
Start: 1700, Size: 300 KB
Start: 2250, Size: 350 KB
----------------------
Allocate Process of size 100

Memory allocated at address: 1200

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1300, Size: 400 KB
Start: 1700, Size: 300 KB
Start: 2250, Size: 350 KB
----------------------
Allocate Process of size 700

Allocation failed: No sufficient memory block available.

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1300, Size: 400 KB
Start: 1700, Size: 300 KB
Start: 2250, Size: 350 KB
----------------------

C Program: Worst Fit Memory Allocation using Doubly Linked List

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

// Define structure for a doubly linked memory block
struct Block {
    int start_address;
    int size;
    struct Block* next;
    struct Block* prev;
};

struct Block* head = NULL;

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

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

    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 all free blocks
void display_free_blocks() {
    struct Block* temp = head;
    printf("\nFree Memory Blocks:\n");
    printf("----------------------\n");
    while (temp != NULL) {
        printf("Start: %d, Size: %d KB\n", temp->start_address, temp->size);
        temp = temp->next;
    }
    printf("----------------------\n");
}

// Worst Fit Allocation using Doubly Linked List
void worst_fit_allocate(int request_size) {
    struct Block* temp = head;
    struct Block* worst_block = NULL;

    // Find the worst (largest) block
    while (temp != NULL) {
        if (temp->size >= request_size) {
            if (worst_block == NULL || temp->size > worst_block->size) {
                worst_block = temp;
            }
        }
        temp = temp->next;
    }

    if (worst_block == NULL) {
        printf("\nAllocation failed: No sufficient memory block available.\n");
        return;
    }

    printf("\nMemory allocated at address: %d\n", worst_block->start_address);

    // Allocate memory
    if (worst_block->size == request_size) {
        // Perfect fit — remove the block from the list
        if (worst_block->prev == NULL)
                   head = worst_block->next; // head node is being removed

        else if (worst_block->next != NULL){
            worst_block->next->prev = worst_block->prev;
            worst_block->prev->next = worst_block->next;
        }
        else //last block
            worst_block->prev->next=NULL;
        free(worst_block);
    } else {
        // Split the block
        worst_block->start_address += request_size;
        worst_block->size -= request_size;
    }
}

// Main function
int main() {
    // Add initial memory blocks
    add_block(1000, 200);
    add_block(1200, 500);
    add_block(1700, 300);
    add_block(2000, 600);

    display_free_blocks();

    printf("Allocate Process of size 250\n");
    worst_fit_allocate(250);
    display_free_blocks();

    printf("Allocate Process of size 100\n");
    worst_fit_allocate(100);
    display_free_blocks();

    printf("Allocate Process of size 700\n");
    worst_fit_allocate(700); // Should fail
    display_free_blocks();

    return 0;
}

Output

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1200, Size: 500 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
----------------------
Allocate Process of size 250

Memory allocated at address: 2000

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1200, Size: 500 KB
Start: 1700, Size: 300 KB
Start: 2250, Size: 350 KB
----------------------
Allocate Process of size 100

Memory allocated at address: 1200

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1300, Size: 400 KB
Start: 1700, Size: 300 KB
Start: 2250, Size: 350 KB
----------------------
Allocate Process of size 700

Allocation failed: No sufficient memory block available.

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1300, Size: 400 KB
Start: 1700, Size: 300 KB
Start: 2250, Size: 350 KB
----------------------

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