Least recently used (LRU) memory question

[kkk]

I am practicing LRU by writing a simulating programme in c, but
encounter a problem.

When obtaining data from a linked list (which stores the requested
page number), seemingly the programme falls into an infinite loop. I
guess that is because the object obtained through function get()
always remains the same. However, I have no idea how to solve it.
Would anyone is able to give me an hint?

I sincerely appreciate it.

code is as below:
=============== code beg
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MEMORY_SIZE 10
#define PAGE_SIZE 500
#define REQUEST_SIZE 1000
#define NOT_INIT -1
#define FIFO 99
#define LRU 98
#define FIFO_STR "FIFO"
#define LRU_STR "LRU"
#define TRUE 1
#define FALSE 0

struct linked_list{
int page_number;
struct linked_list *next;
} *list;

static int mem[MEMORY_SIZE]; //physical memory
static int page_table[PAGE_SIZE]; //page table capacity
static int request[REQUEST_SIZE];//preocess request number
int LINKED_LIST_SIZE = 0;

struct linked_list
*next(struct linked_list *object)
{
return object->next;
}

int
iterate(struct linked_list **head)
{
int count=0;
if(*head==NULL){
printf("linked list is null!");
exit(EXIT_FAILURE);
}
while(next(*head) != NULL){
printf("\n<iterate> count: %d / page_number: %d \n", count,
next(*head)->page_number);
*head = next(*head);
count++;
}
return count;
}

struct linked_list
*get_last_object(struct linked_list *object)
{
struct linked_list *o;
if(object==NULL){
printf("linked list passed in is NULL\n");
exit(EXIT_FAILURE);
}
if(next(object)==NULL){
return object;
}
while( next(object) != NULL){
if( next(next(object)) == NULL){// the last object in the linked
list
return next(object);
}else{
object = next(object);
}
}
}

void
add_to_last(int requested_page)
{
struct linked_list *object;
struct linked_list *last_object;
if(list == NULL){// not yet init
list = (struct linked_list *)malloc(sizeof(struct linked_list));
list->page_number = requested_page;
list->next = NULL;
}else{// new request page
object = (struct linked_list *)malloc(sizeof(struct linked_list));
object->next = NULL;
object->page_number = requested_page;
last_object = get_last_object(list);
last_object->next = object;
}
}

int
remove_first()
{
struct linked_list *first_object;
if(list==NULL){
printf(" First object in linked list is NULL!\n");
exit(EXIT_FAILURE);
}
first_object = list;
list = list->next;
first_object->next = NULL;
/* free unused memroy */
return first_object->page_number;
}

int
find_free_mem_position()
{
int i;
for(i=0; i<MEMORY_SIZE; i++){
if(mem == NOT_INIT){
return i;
}
}
}


void
init_request()
{
int i;
for(i=0; i<REQUEST_SIZE; i++){
request = nrand(0, PAGE_SIZE);
}
}

struct linked_list
*get(int position, struct linked_list **head)
{
int count = 0;
if(*head==NULL){
printf("linked list is null!\n");
exit(EXIT_FAILURE);
}
while(next(*head)!=NULL){
if(count == position){
return *head;
}else{
*head = next(*head);
}
count++;
}
}

/*
struct linked_list
*get(int position)
{
int count = 0;
if(list==NULL){
printf("linked list is null!\n");
exit(EXIT_FAILURE);
}
//iterate(&list);
while( next(list)!=NULL){
if(count == position){
return next(list);
}else{
list = next(list);
}
count++;
}
}
*/

int
is_found(struct linked_list *o, int page_number_passed){
if(o==NULL){
printf(" get object is null\n");
return FALSE;
}
if(o->page_number == page_number_passed){
return TRUE;
}else{
return FALSE;
}
}

void
remove_from_list(int position)
{
int count = 0;
struct linked_list *n;
if(list==NULL) {
printf(" list is NULL\n");
exit(EXIT_FAILURE);
}
while(next(list)!=NULL){
count++;
if(count == position){
list->next = next(list);
list->page_number = next(list)->page_number;
free(next(list));
}else{
list = next(list);
}
}
}

/*
void
reorg_linked_list(int page_number)
{
int count = 0;
int found = FALSE;
struct linked_list *object;
if(list==NULL){
printf(" List is NULL!\n");
exit(EXIT_FAILURE);
}
while(found == FALSE){
object = get(page_number);
if( is_found(object , page_number)){// page is found
found == TRUE;
remove_from_list(object->page_number);
add_to_last(page_number);
}else{//page not found in lined list
count++;
}
}
}
*/
void
page_replacement_policy(int policy)
{
int i, position, page_number;
int page_hit = 0, page_miss = 0, page_swap = 0;
int free_mem = MEMORY_SIZE;
char banner[10];

int found = FALSE;
struct linked_list *object;
int count = 0;

for(i=0; i<MEMORY_SIZE; i++) mem = NOT_INIT;
for(i=0; i<PAGE_SIZE; i++) page_table = NOT_INIT;

memset(banner, 0, sizeof(banner));
if(policy == FIFO)
strncpy(banner, FIFO_STR, strlen(FIFO_STR));
else if(policy == LRU)
strncpy(banner, LRU_STR, strlen(LRU_STR));

printf("========== %s BEG ==========\n", banner);

for(i=0; i<REQUEST_SIZE; i++){ // loop through each process
printf(" request[%d]: %d", i, request);
if(page_table[request]!=NOT_INIT){//page is used
page_hit++;
printf(" << page hit! >> ");
if(policy==LRU){
//reorg_linked_list(request);
while(found == FALSE){
object = get(count, &list);
if(object == NULL){
printf("object is null!\n");
exit(EXIT_FAILURE);
}
printf("count:%d / page_number:%d / request[%d]:%d\n", count, object-

page_number, i, request);

if( is_found(object , request)){// page is found
found == TRUE;
remove_from_list( count);
add_to_last(page_number);
}else{//page not found in linked list
count++;
}
}//while
}
}else{// page is not used // mem is not yet init
page_miss++;
printf(" << page miss! >> ");
if(free_mem > 0){// has free memory
position = find_free_mem_position();
printf(" free space at position: %d", position);
// book room
mem[position] = request;
page_table[request] = position;
//add to the linked list
add_to_last(request);
//decrement free memory space by 1
free_mem--;
}else{// need to swap mem
//remove page from mem
page_number = remove_first();
position = page_table[page_number];
page_table[page_number] = NOT_INIT;
page_swap++;
printf(" old page (%d) at position (%d) swapped out!",
page_number, position);
//associate new page with physical mem
// and page_table
page_table[request] = position;
mem[position] = request;
add_to_last(request);
}
}
//iterate(list);
printf("\n");
}
printf("========== %s END ==========\n", banner);

}

int
nrand(int min, int max)
{
int n;
n = (min + rand() % max);
return n;
}

int
main(int *argc, char **argv)
{
srand(time((time_t)NULL));
list = NULL;
init_request();
page_replacement_policy(LRU);
//page_replacement_policy(FIFO);
}

=============== code end