Page Replacement Algorithms

In an operating system that uses paging for memory management, page replacement algorithms come into play when a new page needs to be loaded into memory, but there are no free page frames available. These algorithms decide which existing page should be replaced to accommodate the new one. Let’s delve into some common page replacement strategies:

First In First Out (FIFO)

Principle: FIFO follows a straightforward approach by replacing the page that entered memory first.

This is the simplest algorithm. The operating system maintains a queue of all pages in memory, with the oldest page at the front.
When a page fault occurs (i.e., a requested page is not in memory), the page at the front of the queue is selected for replacement.

Imagine a queue where pages enter from one end and exit from the other. FIFO replaces the page at the front of the queue when needed.

Example: Consider a page reference string: 1, 3, 0, 3, 5, 6, 3 with 3 page frames. The resulting page faults are as follows:
  • Initially, all slots are empty, so when 1, 3, and 0 arrive, they are allocated to the empty slots (3 page faults).
  • When 3 comes again, it’s already in memory (0 page faults).
  • Then 5 arrives, not in memory, so it replaces the oldest page ie;1(1 page fault).
  • Similarly, 6 replaces the oldest page ie;3(1 page fault).
  • Finally, when 3 comes again, it replaces 0 (1 page fault).
  • Total page faults: 6.
Note: Belady’s anomaly shows that increasing the number of page frames may lead to more page faults with FIFO.

Least Recently Used (LRU)

Principle: LRU prioritizes replacing the least recently used page.
  • LRU replaces the page that hasn’t been used for the longest time.
  • It requires maintaining a stack or queue of recently accessed pages.
  • Efficient but computationally expensive due to frequent updates.
Think of a stack where the most recently accessed page is always at the top. LRU replaces the page at the bottom of the stack when needed.
Example:     Consider a page reference string: 1, 3, 0, 3, 5, 6, 3 with 3 page frames. The resulting page  faults are as follows:
  • Initially, all slots are empty, so when 1, 3, and 0 arrive, they are allocated to the empty slots (3 page faults).
  • When 3 comes again, it’s already in memory (0 page faults).
  • Then 5 arrives, not in memory, so it replaces the LRU page ie;1(1 page fault).
  • Similarly, 6 replaces the LRU page ie;0(1 page fault).
  • Finally, when 3 comes again, it's already in memory(0 page fault)
  • Total page faults: 5.
Least Frequently Used (LFU)

Principle: LFU replaces the page that is used the least within a specific time period.
In LFU, we replace the least frequently used pages in memory. If multiple pages have the same frequency, we replace the one that arrived first.
  • LFU keeps track of the frequency of page usage.
  • When a page fault occurs, the page with the lowest usage count is replaced.
  • LFU can be effective in scenarios where certain pages are accessed infrequently.
    However, it requires maintaining additional data structures to track usage counts.
Imagine a counter associated with each page. LFU replaces the page with the lowest counter value when needed.

Example :  Consider a page reference string: 1, 3, 0, 3, 5, 6, 3 with 3 page frames. The resulting page  faults are as follows:
  • Initially, all slots are empty, so when 1, 3, and 0 arrive, they are allocated to the empty slots (3 page faults).
  • When 3 comes again, it’s already in memory (0 page faults).
  • Then 5 arrives, not in memory, so it replaces the LFU page ie;1(1 page fault).
  • Similarly, 6 replaces the LFU page ie;0 or 5(1 page fault).
  • Finally, when 3 comes again, it is already there  (0 page fault).
  • Total page faults: 5
In summary:
FIFO is simple but lacks sophistication.
LRU considers recent usage patterns and performs well.
LFU focuses on usage frequency but requires additional bookkeeping.

Remember, each algorithm has its strengths and weaknesses, and the choice depends on the specific system requirements and workload characteristics.

//**********************************************************
// C program -FIFO page replacement algorithm.Simple Implementation
//***********************************************************
#include <stdio.h>
#include <stdlib.h>

#define MAX_FRAMES 3 // Maximum number of frames
#define MAX_PAGES 20 // Maximum number of pages

int frames[MAX_FRAMES]; // Array to store the frames
int rear = -1; // Pointer to the rear of the frame queue

// Function to initialize frames array
void initialize() {
    for (int i = 0; i < MAX_FRAMES; i++) {
        frames[i] = -1; // Initializing frames with -1 (empty)
    }
}

// Function to display the frames
void displayFrames() {
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (frames[i] != -1)
            printf("%d ", frames[i]);
        else
            printf("- ");
    }
    printf("\n");
}

// Function to implement FIFO page replacement algorithm
void FIFO(int pages[], int n) {
    int page_faults = 0;
    int front = 0; // Pointer to the front of the frame queue

    for (int i = 0; i < n; i++) {
        int page = pages[i];
        int found = 0;

        // Check if page already exists in frames
        for (int j = 0; j < MAX_FRAMES; j++) {
            if (frames[j] == page) {
                found = 1;
                printf("page %d already there\n",page);
                break;
            }
        }

        if (!found) {
            page_faults++;
           
            if (rear < MAX_FRAMES - 1) {
                rear++;
            } else {
                rear = 0;
            }
            frames[rear] = page;
            printf("page %d loaded in frame %d \n",page,rear);
        }

        //printf("Page %d : ", page);
        displayFrames();
    }

    printf("Total Page Faults: %d\n", page_faults);
}

int main() {
    int pages[MAX_PAGES]; // Array to store pages

    // Example sequence of page references
    int n;
    printf("Enter number of pages: ");
    scanf("%d", &n);
    printf("Enter the page reference sequence: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &pages[i]);
    }

    initialize(); // Initialize frames array
    FIFO(pages, n); // Apply FIFO algorithm

    return 0;
}

Output:
Enter number of pages: 7
Enter the page reference sequence: 1 3 0 3 5 6 3
page 1 loaded in frame 0 
1 - - 
page 3 loaded in frame 1 
1 3 - 
page 0 loaded in frame 2 
1 3 0 
page 3 already there
1 3 0 
page 5 loaded in frame 0 
5 3 0 
page 6 loaded in frame 1 
5 6 0 
page 3 loaded in frame 2 
5 6 3 
Total Page Faults: 6
//**********************************************************
// C program -LRU page replacement algorithm.Simple Implementation
//***********************************************************
#include <stdio.h>
#include <stdlib.h>

#define MAX_FRAMES 3 // Maximum number of frames
#define MAX_PAGES 20 // Maximum number of pages

int frames[MAX_FRAMES]; // Array to store the frames
int counter[MAX_FRAMES]; // Array to store the counter for each frame

// Function to initialize frames and counter arrays
void initialize() {
    for (int i = 0; i < MAX_FRAMES; i++) {
        frames[i] = -1; // Initializing frames with -1 (empty)
        counter[i] = 0; // Initializing counter with 0
    }
}

// Function to display the frames
void displayFrames() {
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (frames[i] != -1)
            printf("%d ", frames[i]);
        else
            printf("- ");
    }
    printf("\n");
}

// Function to find the least recently used frame
int findLRU() {
    int max = counter[0];
    int lru_frame = 0;

    for (int i = 1; i < MAX_FRAMES; i++) {
        if (counter[i] > max) {
            max = counter[i];
            lru_frame = i;
        }
    }

    return lru_frame;
}

// Function to implement LRU page replacement algorithm
void LRU(int pages[], int n) {
    int page_faults = 0;

    for (int i = 0; i < n; i++) {
        int page = pages[i];
        int found = 0;

        // Check if page already exists in frames
        for (int j = 0; j < MAX_FRAMES; j++) {
            if (frames[j] == page) {
                found = 1;
                printf("page %d is already there \n",page);
                break;
            }
        }

        if (!found) {
            int lru_frame = findLRU();
            printf("page %d is loaded in frame %d\n",page,lru_frame);
            frames[lru_frame] = page;
            counter[lru_frame] = 0;
            page_faults++;
        }

        // Increment counter for all frames
        for (int j = 0; j < MAX_FRAMES; j++) {
            counter[j]++;
        }

        // Reset counter for the used frame
        for (int j = 0; j < MAX_FRAMES; j++) {
            if (frames[j] == page) {
                counter[j] = 0;
                break;
            }
        }

        //printf("Page %d : ", page);
        displayFrames();
    }

    printf("Total Page Faults: %d\n", page_faults);
}

int main() {
    int pages[MAX_PAGES]; // Array to store pages

    // Example sequence of page references
    int n;
    printf("Enter number of pages: ");
    scanf("%d", &n);
    printf("Enter the page reference sequence: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &pages[i]);
    }

    initialize(); // Initialize frames and counter arrays
    LRU(pages, n); // Apply LRU algorithm

    return 0;
}

Output:
Enter number of pages: 7
Enter the page reference sequence: 1 3 0 3 5 6 3
page 1 is loaded in frame 0
1 - - 
page 3 is loaded in frame 1
1 3 - 
page 0 is loaded in frame 2
1 3 0 
page is already there 3
1 3 0 
page 5 is loaded in frame 0
5 3 0 
page 6 is loaded in frame 2
5 3 6 
page is already there 3
5 3 6 
Total Page Faults: 5

//***********************************************************
// C program -LFU  page replacement algorithm.Simple Implementation
//***********************************************************
#include <stdio.h>
#include <stdlib.h>

#define MAX_FRAMES 3 // Maximum number of frames
#define MAX_PAGES 20 // Maximum number of pages

int frames[MAX_FRAMES]; // Array to store the frames
int counts[MAX_FRAMES]; // Array to store the count for each frame

// Function to initialize frames and counts arrays
void initialize() {
    for (int i = 0; i < MAX_FRAMES; i++) {
        frames[i] = -1; // Initializing frames with -1 (empty)
        counts[i] = 0; // Initializing counts with 0
    }
}

// Function to display the frames
void displayFrames() {
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (frames[i] != -1)
            printf("%d ", frames[i]);
        else
            printf("- ");
    }
    printf("\n");
}

// Function to find the least frequently used frame
int findLFU() {
    int min = counts[0];
    int lfu_frame = 0;

    for (int i = 1; i < MAX_FRAMES; i++) {
        if (counts[i] < min) {
            min = counts[i];
            lfu_frame = i;
        }
    }

    return lfu_frame;
}

// Function to implement LFU page replacement algorithm
void LFU(int pages[], int n) {
    int page_faults = 0;

    for (int i = 0; i < n; i++) {
        int page = pages[i];
        int found = 0;

        // Check if page already exists in frames
        for (int j = 0; j < MAX_FRAMES; j++) {
            if (frames[j] == page) {
                found = 1;
                counts[j]++;
                printf("page %d is already in memory\n",page);
                break;
            }
        }

        if (!found) {
            int lfu_frame = findLFU();
            frames[lfu_frame] = page;
            counts[lfu_frame] = 1;
            page_faults++;
            printf("page %d is loaded in frame %d\n",page,lfu_frame);
        }

        //printf("Page %d : ", page);
        displayFrames();
    }

    printf("Total Page Faults: %d\n", page_faults);
}

int main() {
    int pages[MAX_PAGES]; // Array to store pages

    // Example sequence of page references
    int n;
    printf("Enter number of pages: ");
    scanf("%d", &n);
    printf("Enter the page reference sequence: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &pages[i]);
    }

    initialize(); // Initialize frames and counts arrays
    LFU(pages, n); // Apply LFU algorithm

    return 0;
}

output:

Enter number of pages: 7
Enter the page reference sequence: 1 3 0 3 5 6 3
page 1 is loaded in frame 0
1 - - 
page 3 is loaded in frame 1
1 3 - 
page 0 is loaded in frame 2
1 3 0 
page 3 is already in memory
1 3 0 
page 5 is loaded in frame 0
5 3 0 
page 6 is loaded in frame 0
6 3 0 
page 3 is already in memory
6 3 0 
Total Page Faults: 5

To implement the LFU page replacement algorithm with the criteria of replacing the page that came first when two pages have the same frequency count, you need to maintain the order of arrival of pages. This can be achieved by keeping track of the order of arrival of pages in addition to their counts. 


Comments

Post a Comment

Popular posts from this blog

CSL 204 OPERATING SYSTEM LAB KTU IV SEM CSE

About Me Syllabus Scheme Program List Linux Basics 1. Linux History and GNU 2. Linux Basic Features and Architecture 3. How to Install Linux 4. Install Linux Inside Windows using WSL 5. Free software 6. Linux Chronology 7 .Package Management 8 .Compile and install from source 9 .Important Directories 10. File Permissions 11. Special Permissions 12 .Shell 13. Bash shell in windows 10 14 .Basic Linux command for beginners 15. Input Output Redirection  16. Directory Commands 17. File Commands 18 .Communication Commands 19. Information Commands  20 .IO Commands   21 .Process Management Commands 22. Account Administration Commands 23. Pipes and Filters  24. Top 100 commands to learn. Shell Programming 1. Shell Script 2. Arithmetic Expressions 3. Special Shell Variables 4. Shell Script for getting important info 5. if and case statement 6. looping statements while,until,for 7. Menu driven Programs 8. GUI Menus 9. Functions in scripts 10. String Handling 11. Command line arguments in scripts
Read more

FCFS and SJF

Image
CPU Scheduling in Operating Systems: In the context of operating systems, CPU scheduling involves determining which process (or task) should be executed next by the central processing unit (CPU). The goal is to maximize CPU utilization, minimize waiting time, and ensure fair allocation of resources. Various scheduling algorithms are used to achieve these objectives. First-Come-First-Serve (FCFS) Scheduling: Definition: FCFS is the simplest CPU scheduling algorithm. It is non-preemptive, meaning once a process starts executing, it cannot be interrupted until completion. Processes are placed in a queue based on their arrival time. The process that arrives first gets executed first. Execution Order : Processes are executed in the order they arrive. The process at the front of the queue is selected for execution. Advantages: Easy to implement. Minimal overhead. Disadvantages: Often results in long waiting times. Leads to the convoy effect (where a long process holds up other processes). Sh
Read more

Shared Memory Inter-Process Communication ( IPC)

Shared memory Inter-Process Communication (IPC) in Linux allows processes to communicate by sharing a region of memory. This method is efficient because it avoids the overhead of copying data between processes. Here's how shared memory IPC is typically done in Linux: Create a Shared Memory Segment: To use shared memory IPC, you need to create a shared memory segment. This is done using the shmget() system call, which allocates a new shared memory segment or obtains the identifier of an existing one. You specify the size of the shared memory segment and some permissions. Attach the Shared Memory Segment: Once you have obtained the identifier for the shared memory segment, you need to attach it to the address space of your process. This is done using the shmat() system call. This call returns the address of the shared memory segment in your process's address space. Accessing the Shared Memory: After attaching the shared memory segment to your process's address space, you c
Read more