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(coun t);
if(object->page_number == request[i]){
found == 1;
remove_from_lis t(count);
add_to_last_of_ list(page_numbe r);
}else{
count++;
}
}
....
struct linked_list
*get_object(int position)
{
int count = 0;
if(*head==NULL) {
printf("linked list is null!\n");
exit(EXIT_FAILU RE);
}
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_SIZ E = 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_FAILU RE);
}
while(next(*hea d) != NULL){
printf("\n<iter atecount: %d / page_number: %d \n", count,
next(*head)->page_number) ;
*head = next(*head);
count++;
}
return count;
}
struct linked_list
*get_last_objec t(struct linked_list *object)
{
struct linked_list *o;
if(object==NULL ){
printf("linked list passed in is NULL\n");
exit(EXIT_FAILU RE);
}
if(next(object) ==NULL){
//line 79 its next should be null
return object;
}
while( next(object) != NULL){
if( next(next(objec t)) == 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_FAILU RE);
}
first_object = list;
list = list->next;
first_object->next = NULL;
/* free unused memroy */
return first_object->page_number;
}
int
find_free_mem_p osition()
{
int i;
for(i=0; i<MEMORY_SIZE; i++){
if(mem[i] == NOT_INIT){
return i;
}
}
}
void
init_request()
{
int i;
for(i=0; i<REQUEST_SIZE ; i++){
request[i] = 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_FAILU RE);
}
while(next(*hea d)!=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_FAILU RE);
}
//iterate(&list);
while( next(list)!=NUL L){
if(count == position){
return next(list);
}else{
list = next(list);
}
count++;
}
}
*/
int
is_found(struct linked_list *o, int page_number_pas sed){
if(o==NULL){
printf(" get object is null\n");
return FALSE;
}
if(o->page_number == page_number_pas sed){
return TRUE;
}else{
return FALSE;
}
}
void
remove_from_lis t(int position)
{
int count = 0;
struct linked_list *n;
if(list==NULL) {
printf(" list is NULL\n");
exit(EXIT_FAILU RE);
}
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_li st(int page_number)
{
int count = 0;
int found = FALSE;
struct linked_list *object;
if(list==NULL){
printf(" List is NULL!\n");
exit(EXIT_FAILU RE);
}
while(found == FALSE){
object = get(page_number );
if( is_found(object , page_number)){// page is found
found == TRUE;
remove_from_lis t(object->page_number) ;
add_to_last(pag e_number);
}else{//page not found in lined list
count++;
}
}
}
*/
void
page_replacemen t_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[i] = NOT_INIT;
for(i=0; i<PAGE_SIZE; i++) page_table[i] = 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[i]);
if(page_table[request[i]]!=NOT_INIT){//page is used
page_hit++;
printf(" << page hit! >");
if(policy==LRU) {
//reorg_linked_li st(request[i]);
while(found == FALSE){
object = get_object(coun t, &list);
if(object == NULL){
printf("object is null!\n");
exit(EXIT_FAILU RE);
}
printf("count:% d / page_number:%d / request[%d]:%d\n", count, object-
>page_number, i, request[i]);if( is_found(object , request[i])){// page is found
found == TRUE;
remove_from_lis t( count);
add_to_last(pag e_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_p osition();
printf(" free space at position: %d", position);
// book room
mem[position] = request[i];
page_table[request[i]] = position;
//add to the linked list
add_to_last(req uest[i]);
//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[i]] = position;
mem[position] = request[i];
add_to_last(req uest[i]);
}
}
//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((tim e_t)NULL));
list = NULL;
init_request();
page_replacemen t_policy(LRU);
//page_replacemen t_policy(FIFO);
}
========== source end
