title: Implementing LRU page replacement algorithm
body: <p>Edited to include short description of what is expected from the code.</p>
  
  <pre><code>#include &lt;sys/file.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;time.h&gt;
  
  #define MAX_PAGE 0xFF+1
  
  /* page table entry  you may need to add your own fields to it*/
  typedef struct
    {
  unsigned short frame;/*location*/
  unsigned int valid:1;
  unsigned int in_mem:1;
  unsigned int dirty:1;
  unsigned int last_frame;
     } pt_entry;
  
  /* list entry for physical frames*/
  
  struct list_item
   {
  unsigned short frame;
  struct list_item *next;
  struct list_item *prev;
  int page_num; 
   };
  
  typedef struct list_item *list;
  
  void start_simulation(FILE *);
  void resolve(int);
  unsigned short find_frame(void);
  unsigned short find_victim(void);
  void display_stats(void);
  void to_resident_set(list);
  void free_mem(list);
  void invalidate(unsigned short);
  
  
  /*============================ header ends here ============================== *
  
  /*#include "lru.h"*/
  
  pt_entry pte[MAX_PAGE];     /* page table */
  int mem_size;               /* physical memory size in page frames */
  list free_list_head;            /* free list */ 
  list res_set_head;          /* resident set */
  int total_fault = 0;            /* total number of page faults */
  int total_ref = 0;          /* total number of memory references */
  
  /* main program:
  ** read in paramters, and open the input file start the simulation */
  
  int main(int argc, char *argv[])
      {
  FILE *stream;
  
  if (argc != 3)
      {
      printf("The format is: pager file_name memory_size.\n");
      exit(1);
       }
  printf("File used %s, resident set size %d\n", argv[1], atoi(argv[2]));
  if ((stream = fopen(argv[1], "r")) == NULL)
      {
      perror("File open failed");
      exit(1);
       }
  
  mem_size = atoi(argv[2]);
  start_simulation(stream);
  fclose(stream);
   }
  
  /*initialise the page table
   ** initialise the resident set, and the free list
   ** in the simulation loop
   **16-bit memory addresses representing the program trace are read from the input 
   **file one by one the virtual address is resolved ie. physical frame for the  
   **virtual page identified
   **the loop exits when it encounters the end of file
   ** free memory allocated for lists
   ** display statistics
    */
  
  void start_simulation(FILE * stream)
    { 
  char *addr_buf;
  int address;
  int i, n;
  list new_entry, current;
  
  /* initialise the page table */
    for(i=0; i&lt;MAX_PAGE;i++)
  {
      pte[i].frame = -1;
      pte[i].valid = 0;
      pte[i].dirty = 0;
      pte[i].in_mem = 0;
  }
  
   /* initialise the resident set - empty*/
  res_set_head = (list)malloc(sizeof(struct list_item));
  res_set_head-&gt;next = res_set_head;
  res_set_head-&gt;prev = res_set_head;
  
  /* initialise free list - all physical pages*/
  free_list_head = (list)malloc(sizeof(struct list_item));
  free_list_head-&gt;next = free_list_head;
  free_list_head-&gt;prev = free_list_head;
  current = free_list_head;
  
  for(i=0; i&lt;mem_size;i++)
  {
      new_entry = (list)malloc(sizeof(struct list_item));
      current-&gt;next = new_entry;
      new_entry-&gt;prev = current;
      new_entry-&gt;next = free_list_head;
      new_entry-&gt;frame = i;
      current = new_entry;
      free_list_head-&gt;prev = current;
  }
  
   /* main simulation loop */
  while( (n = fscanf(stream, "%x", &amp;address)) != -1)
  {
      resolve(address);
      total_ref++; 
  }
  
  free_mem(free_list_head);
  free_mem(res_set_head);
  display_stats();
  return; 
  }
  
  /* resolve address reference
   ** if page table entry valid - do nothing
   ** if page table entry invalid - find a physical frame for this page
   **and update pte for the page
  */
  
  void resolve(int address)   
   {   
   unsigned short frame_alloc;   
   int virt_page;   
   static int disp_counter = 0;   
   virt_page = address &gt;&gt; 8;   
   if (pte[virt_page].valid == 1)   
    { 
     /*Was trying to implement */  
     //pte[virt_page].frame = pte[0];   
    }   
  else  
    {   
     frame_alloc = find_frame();   
     pte[virt_page].valid = 1;   
     pte[virt_page].frame = frame_alloc;   
     total_fault++;   
   }   
   } 
  
   /* find_frame:
   ** if free list is empty find a victim frame
   **     else detach the last frame of the free list and attach it 
   **     to the resident set
   **     return frame number
   */
   unsigned short find_frame()
     {
  unsigned short frame;
  list current, new_tail;
  if (free_list_head == free_list_head-&gt;prev)   /* free list empty */
      frame = find_victim();
  else
  {
      new_tail = free_list_head-&gt;prev-&gt;prev;
      new_tail-&gt;next = free_list_head;
      current = free_list_head-&gt;prev;
      free_list_head-&gt;prev = new_tail;
  
      to_resident_set(current);
      frame = current-&gt;frame;
  }
  return frame;
   }
  
  /* to_resident_set:
   **         attach a list entry at the end of resident set
   */
  void to_resident_set(list current)
    {
  list tail;
  tail = res_set_head-&gt;prev;
  tail-&gt;next = current;
  current-&gt;next = res_set_head;
  current-&gt;prev = tail;
  res_set_head-&gt;prev = current;
    }
    /* find_victim:
     ** As you can see I simply take the first page frame from the resident set list. 
     ** This implements the FIFO replacement strategy. Your task is to replace it with
     ** a more efficient strategy.
     */
  
    unsigned short find_victim()
     {
  int i;
       unsigned short frame=0;
  list current;
  
  for(i=0;i&lt;MAX_PAGE;i++)
  {
    if (pte[i].frame == frame &amp;&amp; pte[i].valid == 1)
      {
          frame = res_set_head-&gt;next-&gt;frame;  
          invalidate(frame);
          current = res_set_head-&gt;next;
          res_set_head-&gt;next = current-&gt;next;
          res_set_head-&gt;next-&gt;prev = res_set_head;
          to_resident_set(current);
          break;
      }   
  }
  return frame;
     }
  
   /* invalidate:
   ** invalidate the page table entry for the victim page */
  
  void invalidate(unsigned short frame)
    {
  int i;
  
  for(i=0;i&lt;MAX_PAGE;i++)
  {
      if (pte[i].frame == frame &amp;&amp; pte[i].valid == 1)
      {
          pte[i].valid = 0;
          pte[i].frame = -1;
          break;
      }
  
      }
     }
   /* display_stats:
   ** This is very basic, you may want to make it more sophisticated,
   ** for example save the data from multiple runs into a file for 
   ** comparison etc
   */
   void display_stats()
    {
  printf("\nProcess issued %d memory references\n", total_ref);
  printf("Process triggered %d page faults\n", total_fault);
  printf("Pafe fault rate is %d percent\n",((total_fault*100)/total_ref));
    }
  
  /* free memory allocated to the list */
  
  void free_mem(list head)
   {
  list current,tail;
  tail = head-&gt;prev;
  current = head;
  while (current-&gt;prev != tail)
  {
      current = current-&gt;next;
      free(current-&gt;prev);
  }
    }
  </code></pre>