c - Implementing LRU page replacement algorithm -
edited include short description of expected code.
#include <sys/file.h> #include <stdlib.h> #include <stdio.h> #include <time.h> #define max_page 0xff+1 /* page table entry may need add own fields 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 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, , open input file start 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 page table ** initialise resident set, , free list ** in simulation loop **16-bit memory addresses representing program trace read input **file 1 one virtual address resolved ie. physical frame **virtual page identified **the loop exits when encounters end of file ** free memory allocated lists ** display statistics */ void start_simulation(file * stream) { char *addr_buf; int address; int i, n; list new_entry, current; /* initialise page table */ for(i=0; i<max_page;i++) { pte[i].frame = -1; pte[i].valid = 0; pte[i].dirty = 0; pte[i].in_mem = 0; } /* initialise resident set - empty*/ res_set_head = (list)malloc(sizeof(struct list_item)); res_set_head->next = res_set_head; res_set_head->prev = res_set_head; /* initialise free list - physical pages*/ free_list_head = (list)malloc(sizeof(struct list_item)); free_list_head->next = free_list_head; free_list_head->prev = free_list_head; current = free_list_head; for(i=0; i<mem_size;i++) { new_entry = (list)malloc(sizeof(struct list_item)); current->next = new_entry; new_entry->prev = current; new_entry->next = free_list_head; new_entry->frame = i; current = new_entry; free_list_head->prev = current; } /* main simulation loop */ while( (n = fscanf(stream, "%x", &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 - nothing ** if page table entry invalid - find physical frame page **and update pte page */ void resolve(int address) { unsigned short frame_alloc; int virt_page; static int disp_counter = 0; virt_page = address >> 8; if (pte[virt_page].valid == 1) { /*was trying 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 empty find victim frame ** else detach last frame of free list , attach ** resident set ** return frame number */ unsigned short find_frame() { unsigned short frame; list current, new_tail; if (free_list_head == free_list_head->prev) /* free list empty */ frame = find_victim(); else { new_tail = free_list_head->prev->prev; new_tail->next = free_list_head; current = free_list_head->prev; free_list_head->prev = new_tail; to_resident_set(current); frame = current->frame; } return frame; } /* to_resident_set: ** attach list entry @ end of resident set */ void to_resident_set(list current) { list tail; tail = res_set_head->prev; tail->next = current; current->next = res_set_head; current->prev = tail; res_set_head->prev = current; } /* find_victim: ** can see take first page frame resident set list. ** implements fifo replacement strategy. task replace ** more efficient strategy. */ unsigned short find_victim() { int i; unsigned short frame=0; list current; for(i=0;i<max_page;i++) { if (pte[i].frame == frame && pte[i].valid == 1) { frame = res_set_head->next->frame; invalidate(frame); current = res_set_head->next; res_set_head->next = current->next; res_set_head->next->prev = res_set_head; to_resident_set(current); break; } } return frame; } /* invalidate: ** invalidate page table entry victim page */ void invalidate(unsigned short frame) { int i; for(i=0;i<max_page;i++) { if (pte[i].frame == frame && pte[i].valid == 1) { pte[i].valid = 0; pte[i].frame = -1; break; } } } /* display_stats: ** basic, may want make more sophisticated, ** example save data multiple runs file ** 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 %d percent\n",((total_fault*100)/total_ref)); } /* free memory allocated list */ void free_mem(list head) { list current,tail; tail = head->prev; current = head; while (current->prev != tail) { current = current->next; free(current->prev); } }
the obvious problem lies in input algorithm. restpage array global array , initialised contain value 0. use these array elements page-numbers requesting, means algorithm processes requests page 0 if mem_size < 100.
and if mem_size >= 100, overrunning array bounds , land squarely in land of undefined behaviour.
there 2 fixes need make:
- just checking valid file in command-line arguments, must check
mem_sizenot large - write additional loop give each element in
restpagerandom value, ensure not page requests same page.
Comments
Post a Comment