Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.17 KB | None | 0 0
  1. #define _GNU_SOURCE
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <assert.h>
  6.  
  7. #define TRUE 1
  8. #define FALSE 0
  9.  
  10. typedef struct ListNode {
  11.     int val, referenceBit;
  12.     struct ListNode *next;
  13. } *List;
  14.  
  15. void printList(List l){
  16.     while(l != NULL){
  17.         printf("%d(%d) ", l->val, l->referenceBit);
  18.         l = l->next;
  19.     }
  20. }
  21.  
  22. void freeList(List l){
  23.     if(l == NULL) return;
  24.     freeList(l->next);
  25.     free(l);
  26. }
  27.  
  28. int *readReferences(int *numReferences){
  29.     // read line from stdin
  30.     char *input= NULL;
  31.     size_t inputLength;
  32.     getline(&input, &inputLength, stdin);
  33.  
  34.     // allocate memory to story reference integers
  35.     int currentSize = 1;
  36.     int *references = malloc(currentSize*sizeof(int));
  37.  
  38.     // parse input string
  39.     int index = 0;
  40.     char *token = strtok(input, " ");
  41.     while(token != NULL){        
  42.         // allocate memory for new reference
  43.         if(index == currentSize){
  44.             currentSize = currentSize + 1;
  45.             references = (int *)realloc(references, currentSize*sizeof(int));
  46.         }
  47.  
  48.         // store reference
  49.         references[index] = atoi(token);
  50.  
  51.         // get new reference
  52.         token = strtok(NULL, " ");
  53.         index++;
  54.     }
  55.  
  56.     (*numReferences) = index;
  57.     free(input);
  58.     return references;
  59. }
  60.  
  61. int isNotInMemory(List frames, int reference){
  62.     if(frames == NULL) return TRUE;
  63.     return (frames->val != reference) &&  isNotInMemory(frames->next, reference);
  64. }
  65.  
  66. int pageReplacement(int *numFrames, int *numReferences, int **references){
  67.     int curReference, pageFaults = 0, curFrameSize = 0;
  68.     List list = NULL, tmp;
  69.  
  70.     // second-page algorithm
  71.     for(int i=0; i<*numReferences; i++){
  72.         curReference = (*references)[i];
  73.  
  74.         printf("%d\t\t", curReference); // DEBUG
  75.    
  76.         if( isNotInMemory(list, curReference) ){
  77.             printf("Y\t\t"); // DEBUG
  78.             pageFaults++;
  79.  
  80.             // queue is full
  81.             if( curFrameSize == (*numFrames) ){
  82.                
  83.                 while(list->referenceBit != 0){
  84.                     // set reference bit to 0
  85.                     list->referenceBit = 0;
  86.  
  87.                     // move to end of queue
  88.                     tmp = list;
  89.                     while(tmp->next != NULL){
  90.                         tmp = tmp->next;
  91.                     }
  92.                     tmp->next = list;
  93.                     list = list->next;    
  94.                 }
  95.  
  96.                 printf("[%d]  ", list->val);
  97.                 // take the head out
  98.                 tmp = list;
  99.                 list = list->next;
  100.                 free(tmp);
  101.            
  102.                 curFrameSize--;
  103.             }
  104.  
  105.             // allocate memory for new element
  106.             List newElem = malloc(sizeof(struct ListNode));
  107.             assert( newElem != NULL);
  108.             newElem->val = curReference;
  109.             newElem->referenceBit = 0;
  110.             newElem->next = NULL;
  111.  
  112.             // insert new element at the end
  113.             tmp = list;
  114.             if(i>0){
  115.                 while(tmp->next != NULL){
  116.                     tmp = tmp->next;
  117.                 }
  118.                 tmp->next = newElem;
  119.             } else {
  120.                 list = newElem;
  121.             }
  122.          
  123.             curFrameSize++;
  124.         } else {
  125.             printf("N\t\t"); // DEBUG
  126.  
  127.             // page is in memory
  128.  
  129.             // set reference bit to 1
  130.             List referenceToPage = list;
  131.             while(referenceToPage->val != curReference){
  132.                 assert(referenceToPage != NULL);
  133.                 referenceToPage = referenceToPage->next;
  134.             }
  135.             referenceToPage->referenceBit = 1;
  136.  
  137.         }
  138.        
  139.         printList(list); // DEBUG
  140.         printf("\n");
  141.     }
  142.    
  143.     freeList(list);
  144.     return pageFaults;
  145. }
  146.  
  147. int main(int argc, char *argv[]) {
  148.     int numFrames;
  149.     scanf("%d\n", &numFrames);
  150.  
  151.     int numReferences;
  152.     int *references = readReferences(&numReferences);
  153.  
  154.     printf("REFERENCE\tPAGE FAULT\tQUEUE\n"); // DEBUG
  155.  
  156.     printf("Number of page faults: %d\n", pageReplacement(&numFrames, &numReferences, &references) );
  157.  
  158.     free(references);
  159.     return 0;
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement