实现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]的尺寸设为restpage，但mem_size似乎是可自由配置的，这是意图吗？

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

编辑：

我看到一个错误在你的新代码，在你的find_victim你不初始化局部变量 '框架'

EDITx2：

当您从阅读你可能只想在每行 上放置一个十六进制地址的文件，而不是使用fgets（）逐行读取文件（或者加载整个文件并且逐行读取文件，即 ）。

Answer 2

最明显的问题在于您的算法输入。 restpage数组是一个全局数组，因此将被初始化为仅包含值0.然后，您将这些数组元素用作请求的页码，这意味着如果mem_size < 100的算法只处理页0的请求，

如果mem_size >= 100，你超出了数组界限，并在未定义的行为的土地上正常登陆。

有两个补丁，你需要做：

1. 就像你正在检查在命令行参数一个有效的文件，你还必须检查mem_size不是太大
2. 写的附加循环为restpage中的每个元素提供一个随机值，以确保并非所有页面请求都是针对同一页面的。