home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1989 / 04 / lru.c < prev    next >
Text File  |  1989-03-24  |  5KB  |  161 lines
  1. _LRU Technique_
  2. by Tom Gettys
  3.  
  4. [FULL LISTING FOR SIDEBAR TO _VIRTUAL DEMAND PAGED MEMORY_ BY
  5. KENT DAHLGREN IN THE APRIL, 1989, ISSUE OF DDJ]
  6.  
  7.  
  8. #include <stdio.h>
  9. #include <ctype.h>
  10.  
  11. #define BYTE unsigned char
  12. #define WORD unsigned int
  13.  
  14. #define TRUE 1
  15. #define FALSE 0
  16.  
  17. #define READ 0
  18. #define WRITE 1
  19.  
  20. #define BAD_PAGE 0xFFFF                /* set to invalid page ID            */
  21. #define BFRS 0x8                       /* number of page buffers            */
  22. #define LIST_HEAD BFRS                 /* index of FIFO list head           */
  23.  
  24. /*
  25. ** lru_fifo[] is a queue that is the mechanism by which the LRU algorithm
  26. ** is realized.  It is implemented as a doublely-linked list to facilitate
  27. ** node deletion as well as the queuing and de-queuing of nodes.  The last
  28. ** element is the list head node.
  29. */
  30.  
  31. struct
  32. {
  33.    WORD succ;                          /* index of next younger node        */
  34.    WORD pred;                          /* index of next older node          */
  35.    BYTE dirty_bit;                     /* TRUE if page has been written to  */
  36.    WORD page_id;                       /* ID of page associated w/this node */
  37. } lru_fifo[BFRS + 1];
  38.  
  39. /*
  40. ** The nodes of LRU_FIFO[] are linked together into a circular doublely-linked
  41. ** list with a list head (last element).  In this particular implementation the
  42. ** ID of the buffer associated with each node is the same as the node index.
  43. ** Note that the page_id is set to a value that is guarenteed to not match
  44. ** any valid page request, and the dirty-bit is set to FALSE.  By priming the
  45. ** system with bogus pages the startup special cases are avoided and the code
  46. ** is more efficient (is the LRU FIFO full/empty?).
  47. */
  48.  
  49. void init_fifo(void)
  50. {
  51.    WORD i;
  52.  
  53.    for (i = 0; i <= BFRS; i++)
  54.    {
  55.       lru_fifo[i].succ = i + 1;
  56.       lru_fifo[i].pred = i - 1;
  57.       lru_fifo[i].page_id = BAD_PAGE;
  58.       lru_fifo[i].dirty_bit = FALSE;
  59.    }
  60.    lru_fifo[0].pred = BFRS;
  61.    lru_fifo[BFRS].succ = 0;
  62. }
  63.  
  64. /*
  65. ** The specified page ID is compared to the IDs of the resident pages.  If a
  66. ** match is found the ID of the buffer containing that page is placed in the
  67. ** second parameter and a value of TRUE is returned.  If no match is found
  68. ** the ID of the LRU page is placed in the second parameter and a value of
  69. ** FALSE is returned.
  70. */
  71.  
  72. int search(WORD page_id, WORD *buffer)
  73. {
  74.    WORD i;
  75.  
  76.    for (i = 0; i < BFRS; i++)
  77.    {
  78.       if (lru_fifo[i].page_id == page_id)
  79.       {
  80.          *buffer = i;
  81.          return(TRUE);
  82.       }
  83.    }
  84.    *buffer = lru_fifo[LIST_HEAD].succ;
  85.    return(FALSE);
  86. }
  87.  
  88. /*
  89. ** The specified FIFO node is requeued - that is, it is deleted from its
  90. ** current position and inserted at the back of the queue.
  91. */
  92.  
  93. void requeue(WORD node)
  94. {
  95.    lru_fifo[lru_fifo[node].pred].succ = lru_fifo[node].succ; /* delete node */
  96.    lru_fifo[lru_fifo[node].succ].pred = lru_fifo[node].pred; /* from FIFO   */
  97.  
  98.    lru_fifo[lru_fifo[LIST_HEAD].pred].succ = node;    /* link node to the   */
  99.    lru_fifo[node].pred = lru_fifo[LIST_HEAD].pred;    /* rear of the FIFO   */
  100.  
  101.    lru_fifo[LIST_HEAD].pred = node;                   /* link node to the   */
  102.    lru_fifo[node].succ = LIST_HEAD;                   /* list head          */
  103. }
  104.  
  105. /*
  106. ** This function serves as a bare-bones memory manager.  Print statements
  107. ** are used to specify the state of the MMS and indicate the operations
  108. ** to be performed in each case.
  109. */
  110.  
  111. void manager(WORD page, int rw)
  112. {
  113.    int found;
  114.    WORD bid;
  115.  
  116.    found = search(page, &bid);
  117.    if (!found)
  118.    {
  119.       printf("page fault on page %X - ", page);
  120.       printf("the LRU buffer is %X\n", bid);
  121.       if (lru_fifo[bid].dirty_bit)
  122.       {
  123.          printf("buffer %X has been modified - ", bid);
  124.          printf("writing page %X\n", lru_fifo[bid].page_id);
  125.       }
  126.       lru_fifo[bid].page_id = page;
  127.  
  128.       if (rw == WRITE)
  129.          printf("writing page %X to buffer %X\n", page, bid);
  130.       else
  131.          printf("reading page %X into buffer %X\n", page, bid);
  132.    }
  133.    else if (rw == WRITE)
  134.       printf("writing page %X to buffer %X\n", page, bid);
  135.  
  136.    if (rw == WRITE) lru_fifo[bid].dirty_bit = TRUE;
  137.    requeue(bid);
  138. }
  139.  
  140.  
  141. void main(void)
  142. {
  143.    char rw;
  144.    int found, done;
  145.    WORD page, bid, buffer;
  146.  
  147.    init_fifo();
  148.    done = FALSE;
  149.  
  150.    while (!done)
  151.    {
  152.       printf("\nTo end enter %X for the page number\n", BAD_PAGE);
  153.       printf("enter a page number and either R or W: ");
  154.       scanf("%x %c", &page, &rw);
  155.       if (rw == 'w') rw = 'W';
  156.  
  157.       if (page == BAD_PAGE) done = TRUE;
  158.       else manager(page, rw == 'W' ? WRITE : READ);
  159.    }
  160. }
  161.