Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _GNU_SOURCE
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <assert.h>
- #define TRUE 1
- #define FALSE 0
- typedef struct ListNode {
- int val, referenceBit;
- struct ListNode *next;
- } *List;
- void printList(List l){
- while(l != NULL){
- printf("%d(%d) ", l->val, l->referenceBit);
- l = l->next;
- }
- }
- void freeList(List l){
- if(l == NULL) return;
- freeList(l->next);
- free(l);
- }
- int *readReferences(int *numReferences){
- // read line from stdin
- char *input= NULL;
- size_t inputLength;
- getline(&input, &inputLength, stdin);
- // allocate memory to story reference integers
- int currentSize = 1;
- int *references = malloc(currentSize*sizeof(int));
- // parse input string
- int index = 0;
- char *token = strtok(input, " ");
- while(token != NULL){
- // allocate memory for new reference
- if(index == currentSize){
- currentSize = currentSize + 1;
- references = (int *)realloc(references, currentSize*sizeof(int));
- }
- // store reference
- references[index] = atoi(token);
- // get new reference
- token = strtok(NULL, " ");
- index++;
- }
- (*numReferences) = index;
- free(input);
- return references;
- }
- int isNotInMemory(List frames, int reference){
- if(frames == NULL) return TRUE;
- return (frames->val != reference) && isNotInMemory(frames->next, reference);
- }
- int pageReplacement(int *numFrames, int *numReferences, int **references){
- int curReference, pageFaults = 0, curFrameSize = 0;
- List list = NULL, tmp;
- // second-page algorithm
- for(int i=0; i<*numReferences; i++){
- curReference = (*references)[i];
- printf("%d\t\t", curReference); // DEBUG
- if( isNotInMemory(list, curReference) ){
- printf("Y\t\t"); // DEBUG
- pageFaults++;
- // queue is full
- if( curFrameSize == (*numFrames) ){
- while(list->referenceBit != 0){
- // set reference bit to 0
- list->referenceBit = 0;
- // move to end of queue
- tmp = list;
- while(tmp->next != NULL){
- tmp = tmp->next;
- }
- tmp->next = list;
- list = list->next;
- }
- printf("[%d] ", list->val);
- // take the head out
- tmp = list;
- list = list->next;
- free(tmp);
- curFrameSize--;
- }
- // allocate memory for new element
- List newElem = malloc(sizeof(struct ListNode));
- assert( newElem != NULL);
- newElem->val = curReference;
- newElem->referenceBit = 0;
- newElem->next = NULL;
- // insert new element at the end
- tmp = list;
- if(i>0){
- while(tmp->next != NULL){
- tmp = tmp->next;
- }
- tmp->next = newElem;
- } else {
- list = newElem;
- }
- curFrameSize++;
- } else {
- printf("N\t\t"); // DEBUG
- // page is in memory
- // set reference bit to 1
- List referenceToPage = list;
- while(referenceToPage->val != curReference){
- assert(referenceToPage != NULL);
- referenceToPage = referenceToPage->next;
- }
- referenceToPage->referenceBit = 1;
- }
- printList(list); // DEBUG
- printf("\n");
- }
- freeList(list);
- return pageFaults;
- }
- int main(int argc, char *argv[]) {
- int numFrames;
- scanf("%d\n", &numFrames);
- int numReferences;
- int *references = readReferences(&numReferences);
- printf("REFERENCE\tPAGE FAULT\tQUEUE\n"); // DEBUG
- printf("Number of page faults: %d\n", pageReplacement(&numFrames, &numReferences, &references) );
- free(references);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement