Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Least Recently Used Algorithm

    Uploaded by

    Navya
    The document discusses the Least Recently Used (LRU) page replacement algorithm. LRU replaces the least recently used page based on the idea that pages accessed recently will likely be accessed again soon. Whenever a page fault occurs, the page that was accessed furthest in the past is removed from memory frames to make space for the new page. Pseudocode and an example are provided to demonstrate how LRU tracks page access times and replaces the least recently used page.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Least Recently Used Algorithm

    Uploaded by

    Navya
    15 views5 pages
    The document discusses the Least Recently Used (LRU) page replacement algorithm. LRU replaces the least recently used page based on the idea that pages accessed recently will likely be accessed again soon. Whenever a page fault occurs, the page that was accessed furthest in the past is removed from memory frames to make space for the new page. Pseudocode and an example are provided to demonstrate how LRU tracks page access times and replaces the least recently used page.

    Original Title

    lru

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses the Least Recently Used (LRU) page replacement algorithm. LRU replaces the least recently used page based on the idea that pages accessed recently will likely be accessed again soon. Whenever a page fault occurs, the page that was accessed furthest in the past is removed from memory frames to make space for the new page. Pseudocode and an example are provided to demonstrate how LRU tracks page access times and replaces the least recently used page.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    15 views5 pages

    Least Recently Used Algorithm

    Uploaded by

    Navya
    The document discusses the Least Recently Used (LRU) page replacement algorithm. LRU replaces the least recently used page based on the idea that pages accessed recently will likely be accessed again soon. Whenever a page fault occurs, the page that was accessed furthest in the past is removed from memory frames to make space for the new page. Pseudocode and an example are provided to demonstrate how LRU tracks page access times and replaces the least recently used page.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    Page replacement is a widely used approach in memory management.

    The idea is simple: the


    main memory cannot hold all the referred pages in memory. So whenever a new page is
    referenced, an existing page is replaced by the page that was newly called. The goal of any
    page replacement mechanism is to minimize the number of page faults.

    Least Recently Used Algorithm


    Algorithm is a page replacement technique used for memory management. According to this
    method, the page which is least recently used is replaced. Therefore, in memory, any page
    that has been unused for a longer period of time than the others is replaced.

    Least Recently Used (LRU) page replacement algorithm works on the concept that the pages
    that are heavily used in previous instructions are likely to be used heavily in next instructions.
    And the page that are used very less are likely to be used less in future. Whenever a page
    fault occurs, the page that is least recently used is removed from the memory frames. Page
    fault occurs when a referenced page in not found in the memory frames.

    This idea is somewhat based on locality of reference, that any page that has been unused for a
    great amount of time is more likely to remain unused. Therefore, it is better to replace that
    page.

    Code

    In this algorithm, we replace the element which is the current least recently used element in
    the current stack.That is, when we look to the left of the table, that we have created we
    choose the further most page to get replaced.

    #include<stdio.h>

    #include<limits.h>

    int checkHit(int incomingPage, int queue[], int occupied){

    for(int i = 0; i < occupied; i++){

    if(incomingPage == queue[i])

    return 1;

    return 0;
    }

    void printFrame(int queue[], int occupied)

    for(int i = 0; i < occupied; i++)

    printf("%d\t\t\t",queue[i]);

    int main()

    // int incomingStream[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1};

    // int incomingStream[] = {1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3, 6, 1, 2, 4, 3};

    int incomingStream[] = {1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3};

    int n = sizeof(incomingStream)/sizeof(incomingStream[0]);

    int frames = 3;

    int queue[n];

    int distance[n];

    int occupied = 0;

    int pagefault = 0;

    printf("Page\t Frame1 \t Frame2 \t Frame3\n");

    for(int i = 0;i < n; i++)

    printf("%d: \t\t",incomingStream[i]);

    // what if currently in frame 7

    // next item that appears also 7

    // didnt write condition for HIT

    if(checkHit(incomingStream[i], queue, occupied)){


    printFrame(queue, occupied);

    // filling when frame(s) is/are empty

    else if(occupied < frames){

    queue[occupied] = incomingStream[i];

    pagefault++;

    occupied++;

    printFrame(queue, occupied);

    else{

    int max = INT_MIN;

    int index;

    // get LRU distance for each item in frame

    for (int j = 0; j < frames; j++)

    distance[j] = 0;

    // traverse in reverse direction to find

    // at what distance frame item occurred last

    for(int k = i - 1; k >= 0; k--)

    ++distance[j];

    if(queue[j] == incomingStream[k])

    break;

    // find frame item with max distance for LRU


    // also notes the index of frame item in queue

    // which appears furthest(max distance)

    if(distance[j] > max){

    max = distance[j];

    index = j;

    queue[index] = incomingStream[i];

    printFrame(queue, occupied);

    pagefault++;

    printf("\n");

    printf("Page Fault: %d",pagefault);

    return 0;

    Example :
    1. Time reference string : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1
    Allocation frame = 3

    7 0 1 2 0 3 0 4 2 3 0 3 2 1

    7 7 7 2 2 2 2 4 4 4 0 0 0 1

    0 0 0 0 0 0 0 0 3 3 3 3 3

    1 1 1 3 3 3 2 2 2 2 2 2

    1* 2* 3* 4* 5 6* 7 8* 9* 10* 11* 12 13 14*


    ‘ * ‘ indicates page fault
    Total Page fault = 10
    Total Page hit = 4

    Output :
    Page Frame1 Frame2 Frame3
    7: 7

    0: 7 0

    1: 7 0 1
    2: 2 0 1
    0: 2 0 1
    3: 2 0 3
    0: 2 0 3
    4: 4 0 3
    2: 4 0 2
    3: 4 3 2
    0: 0 3 2
    3: 0 3 2
    2: 0 3 2
    1: 1 3 2
    Page Fault: 10

    You might also like