Внедрение алгоритма замены страницы LRU

Question

Отредактировано, чтобы включить краткое описание того, что ожидается от кода.

#include <sys/file.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <time.h> 

#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<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->next = res_set_head; 
res_set_head->prev = res_set_head; 

/* initialise free list - all 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 - 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 >> 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->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 a list entry at the 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: 
    ** 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<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 the page table entry for the 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: 
** 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->prev; 
current = head; 
while (current->prev != tail) 
{ 
    current = current->next; 
    free(current->prev); 
} 
    } 

Answer 1

У вас есть размерная настройка для [100], но mem_size кажется свободно настраиваемой, это намерение?

mem_size = atoi(argv[2]); 
fclose(stream); 
.. 
for(i=0;i<mem_size;i++) 
{ 
totalabsence+=find_victim(&pt,restpage[i]); 
} 

EDIT:

Я вижу одну ошибку в новом коде, в вашем find_victim вы не инициализировать локальную переменную 'кадр'

EDITx2:

Когда вы читаете из файл, вы можете просто поместить один гексаговый адрес в каждой строке и использовать вместо этого fgets() для чтения файла по строкам (или загрузить весь файл и пройти его по строкам).

Answer 2

Наиболее очевидная проблема заключается в вводе вашего алгоритма. массив restpage является глобальным массивом и поэтому будет инициализирован содержать только значение 0. Затем вы используете эти элементы массива в качестве номеров страниц, которые вы запрашиваете, а это означает, что ваш алгоритм обрабатывает только запросы на страницу 0, если mem_size < 100.

И если mem_size >= 100, вы преодолеваете границы массива и приземлитесь прямо в земле undefined поведение.

Есть два исправления вам нужно сделать:

1. Подобно тому, как вы проверяете для действительного файла аргументов командной строки, вы должны также проверить, что mem_size не слишком большой
2. написать дополнительный цикл, чтобы дать каждому элементу в restpage случайное значение, чтобы гарантировать, что не все запросы страниц относятся к одной странице.