Least recently used (LRU) memory question

[kkk]

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

The problem is when a page hit occurred (simulated process request
(contains requested page) a page, which has the same page number as
requesting process), I try to obtain the page number previously stored
in the linked list with its position. The linked list store pages that
have been used by simulated physical memory (the linked list size is
10). The code snippet looks like:
========= code beg
....
struct linked_list{
int page_number;
struct linked_list *next;
} *list;

....
struct linked_list *object;
int found = FALSE;
int count=0;
while(found==0){

object = get_object(count);
if(object->page_number == request){
found == 1;
remove_from_list(count);
add_to_last_of_list(page_number);
}else{
count++;
}
}

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

But the problem is that because I assign value to the list with next()
function, which point to the next object, then next time when trying
to traverse through the linked list, the object return by get_object()
is NULL. That cause the error of the programme.

So my question is how to avoid overwriting the pointer stored in the
linked list?

I sincerely appreciate any help.

below is the source:
========== source 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){
//line 79 its next should be 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_object(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_object(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);
}

========== source end

 

[Barry Schwarz]

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

snip 300+ lines

You posted two messages a little over 1 hour apart. The second added
50 lines. Would you care to describe what you added? You should also
recognize that Usenet is not a chat room. It may take several hours
or more for your message to propagate. Similarly for any responses.


Remove del for email

 

[kkk]

snip 300+ lines

You posted two messages a little over 1 hour apart. The second added
50 lines. Would you care to describe what you added? You should also
recognize that Usenet is not a chat room. It may take several hours
or more for your message to propagate. Similarly for any responses.

Remove del for email

I think it is because of google. My previous two messages was post
through google's usenet web interface. It told me that my first
message will be deleted and will not appeared on the usenet after
deleted. However, it seems not so. I am sorry for that problem because
I just thought my first message was too general without specifying the
code with which I am confused.

Thanks your reply indeed.

 

[santosh]

I think it is because of google. My previous two messages was post
through google's usenet web interface. It told me that my first
message will be deleted and will not appeared on the usenet after
deleted. However, it seems not so.

Google Groups *has* apparently honoured your request and deleted the
message from it's servers, since it doesn't appear on Groups. However,
it has no authority to do the same for all the other thousands of
servers that comprise Usenet. Most Usenet servers ignore CANCEL
messages, since they're prone to abuse.