//Program 5
//Michael Donze
//CS 452
//Program simulates memory management using the LRU page replacement algorithm.




//INCLUDE FILES----------------------------------------------------------------------------------------------
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

//DEFINITIONS------------------------------------------------------------------------------------------------
#define MAX_ARRAY 6000		//Max number for lines from the input file.
#define LINE_MAX 14		//Max for number of characters per line in input file.
#define PTI_MAX 64		//Max number of pages per process.
#define MAX_PROCESSES 10	//Changeable number for max processes.
#define PHY_MEM_MAX 16		//Max number of pages physical memory can hold.
#define VALID 1			//Reference bit: means page in simulated memory.
#define INVALID 0		//Reference bit: means page not in simulated memory.

//FUNCTION DECLARATIONS--------------------------------------------------------------------------------------
int readfile(char *file);
void replace(char proc, int page);
int convert_decimal(char t[]);
int checkmem();
int checkpagetable(char proc, int index);
void put_in_frame(char proc, int page, int freeframe);
void update_clock(int frameindex);
void update_page_table(int proc, int page);



struct page_table	//Page table structure.
{
	int tbl[PTI_MAX][2];	//Integer array w/ Max elements of the number of pages
				//possible in logical memory. Element [page][1] will
};				//hole the INVALID bit telling the process that that page 
				//isn't in simulated memory. Otherwise [page][1] will
				//hold the VALID bit, meaning page is in memory. [page][0]
				//will hold the index # of where it is located in memory.

struct PCB	//Simulated process control block.
{

	struct page_table list[MAX_PROCESSES];	//Page table per process.  

}pcblist[MAX_PROCESSES]; 	//Array of PCB's with a PCB per process, there are
				//MAX_PROCESSES of these.  MAX_PROCESSES can be set to 
				//any value.  The index into this array of structures
				//represents the process using it.


//GLOBAL VARIABLES-------------------------------------------------------------------------------------------
char pagereferences[1][LINE_MAX];//Array to take in lines from file.
int freeframes[PHY_MEM_MAX][3];	//Simulated physical memory element 0: process#, 1: page#, 2: clock value.
int page_faults;		//Keeps track of total page faults that occur.
int clock;			//Simulated clock.
int pg_faults[MAX_PROCESSES];	//Array that holds page faults by process. Element determines process.
int page_ref = 0;		//Keeps track of the total page references.
int pg_ref[MAX_PROCESSES];	//Array that holds page references by process. Element determines process.





//MAIN FUNCTION----------------------------------------------------------------------------------------------
int main(int argc, char *argv[])
{

int error,l,g;
clock = 0;		//Initialize clock.
page_faults = 0;	//Initialize variable to keep track of total page faults.

for(l = 0; l < PHY_MEM_MAX; l ++)
{
	freeframes[l][0] = MAX_PROCESSES;	//Initialize memory to MAX_PROCESSES to mark unused frame
}

for(l = 0; l < MAX_PROCESSES; l ++)
{

	
	pg_faults[l] = 0;			//Initialize page faults array to 0. 
	pg_ref[l] = 0;				//Initialize page refernces array to 0.

	for(g = 0; g < PTI_MAX; g ++)
	{
		pcblist[l].list[l].tbl[g][1] = INVALID;	//Initialize each page table entry
							//[page][1] with INVALID. This bit
	}						//tells each process that none of 
							//its pages are in memory.
}

if(argc < 2)
{
	printf("usage: Progfile: Inputfile:\n");	//Check to see if there is 2 arguments on the 
	exit(1);					//command line. 1st is executable, 2nd is 
							//the input file.
}

error = readfile(argv[1]);				//Call the function to read file and perform
							//actions on each memory reference generated
							//by the file.
if(error < 0)						
{
	printf("Error opening file!\n");		//Check return value of the readfile function.
	exit(1);					//A -1 indicates an error, no such file, or
}							//an opening error.


for(l = 0; l < MAX_PROCESSES; l ++)
{
	if(pg_faults[l] != 0)	//Search fault array and determine which process was used and how
	{			//many faults occured associated with that process. Demand paging
				//requires a page fault to occur for the process to even be in
				//memory; that is why 0 is used to determine if the process was
				//used or not. The number stored in the element representing the 
				//process is the total number of page faults for that process
		printf("Process %d total page faults: %d\n",l,pg_faults[l]);

	}
	if(pg_ref[l] != 0)	//Similar to the page fault array, but this array holds the
	{			//total number of page references by process.
		printf("Process %d total page references: %d\n",l,pg_ref[l]);
	}
	
}

printf("Total page references : %d\n",page_ref);
printf("Total Page faults : %d\n",page_faults);



return 0;
}



//FUNCTION TO UPDATE PAGE TABLE------------------------------------------------------------------------------


void update_page_table(int proc, int page)   //Tell process's page table that the page is 
{					     //no longer in memory by setting INVALID bit.

	pcblist[proc].list[proc].tbl[page][1] = INVALID;
}

//-----------------------------------------------------------------------------------------------------------


//FUNCTION TO UPDATE CLOCK-----------------------------------------------------------------------------------

void update_clock(int frameindex)	//Increment clock if process's page is referenced again.
{

	freeframes[frameindex][2] = clock;
}

//-----------------------------------------------------------------------------------------------------------


//FUNCTION TO READ FILE AND PERFORM ACTIONS FROM MEMORY REFERENCES-------------------------------------------

int readfile(char *file)
{
FILE *fp;
int i,z,pid,pageindex,check;
char arg[6];	//Holds high order logical address.
char process;	//Holds process number.

pid = 0;



if((fp = fopen(file,"r")) == NULL)
{
	return -1;
}
else
{
	while(!feof(fp))
	{

	
	fgets(pagereferences[0],LINE_MAX,fp);		//Read line by line from file.
		
		page_ref ++;	//Increment page references variable.
		clock ++;	//Increment simulated clock.
		
		for(i = 0; i < 6; i ++)//Clear out arg array.
		{
			arg[i] = '\0';

		}

		if(pagereferences[0] != NULL)	//Make sure line is read into array.
		{
			arg[0] = pagereferences[0][4]; 	//Set arg value from input,
			arg[1] = pagereferences[0][5];	//element by element, to represent
			arg[2] = pagereferences[0][6];	//high order binary logical
			arg[3] = pagereferences[0][7];	//address.
			arg[4] = pagereferences[0][8];	//
			arg[5] = pagereferences[0][9];	//
			process = pagereferences[0][1];	//Set process # from input line.

			pageindex = convert_decimal(arg);//Convert address to decimal #.

			z = checkpagetable(process,pageindex);//Using decimal conversion
			//representing index into the page table and process #, check the
			//corresponding page table entry to see if it's in memory. If
			//not, return -1, otherwise return 1.
			
			if(z < 0)	//Checked page table; not in memory.
			{
				check = checkmem();//Check memory to see if there are
				//open frames. If so, return the open frame index. If
				//not return -1.

				if(check < 0)//No free frames in simulated memory.
				{
					printf("No free frames!\n");
					replace(process,pageindex);//This function searches
					//through memory frame clock values to determine
					//which process and page will be booted out. The
					//parameters taken are the process and page that 
					//want to come into memory.

				}
				else	//Free frames in simulated memory.
				{
					printf("Page put in free frame %d\n\n",check);
					
					put_in_frame(process,pageindex,check);//This 
					//function takes the process,page,and free 
					//memory frame as parameters and puts them in the
					//memory frame specified.
				}


			}

		}

		process = ' ';	      //Clear process variable.
		pageindex = 0;	      //Clear page variable
	}

}
fclose(fp);		//Close input file.
return 1;		//Return true for success of reading and manipulating file.
}


//-----------------------------------------------------------------------------------------------------------


//FUNCTION TO REPLACE FRAME THAT IS IN MEMORY----------------------------------------------------------------

void replace(char proc, int page)
{
int loop;
int loop2;
int temp;
int frm;
int pg;


int arr[PHY_MEM_MAX];	//Integer array to take in clock values of pages in memory.

temp = 0;


for(loop = 0; loop < PHY_MEM_MAX; loop ++)//Put clock values of processes in memory in arr.
{
	arr[loop] = freeframes[loop][2];
}

for(loop = 0; loop < PHY_MEM_MAX - 1; ++loop)//Sort clock values in arr in ascending order.
{

	for(loop2 = loop + 1; loop2 < PHY_MEM_MAX; ++ loop2)
	{

		if(arr[loop] > arr[loop2])
		{
			temp = arr[loop];
			arr[loop] = arr[loop2];
			arr[loop2] = temp;

		}

	}

}

temp = arr[0];//Since arr is sorted, first element is smallest clock value.

for(loop = 0; loop < PHY_MEM_MAX; loop ++)
{

if(freeframes[loop][2] == temp)//Search in memory for small clock value obtained in previous.
{
frm = loop;//Frame found, set to frm variable.
pg = freeframes[frm][1];//Set page # to be replaced to pg variable.
printf("Replace frame %d victim: process %d page %d\n\n",loop,freeframes[loop][0],freeframes[loop][1]);
break;

}



}


update_page_table(freeframes[frm][0],pg);	//Update page table of victim process and page.
put_in_frame(proc,page,frm);			//Put current page in victim's frame in physical memory.



}

//-----------------------------------------------------------------------------------------------------------


//FUNCTION TO CONVERT ARRAY TO DECIMAL-----------------------------------------------------------------------

int convert_decimal(char t[])//Convert array into decimal equivalent.
{
int x;
x = 0;


if(t[5] == '1')//2 to the 0
	x = x + 1;
if(t[4] == '1')//2 to the 1st
	x = x + 2;
if(t[3] == '1')//2 to the 2nd
	x = x + 4;
if(t[2] == '1')//2 to the 3th
	x = x + 8;
if(t[1] == '1')//2 to the 4th
	x = x + 16;
if(t[0] == '1')//2 to the 5th
	x = x + 32;


return x;
}

//-----------------------------------------------------------------------------------------------------------


//FUNCTION TO CHECK MEMORY FRAMES TO SEE IF OCCUPIED---------------------------------------------------------

int checkmem()//Check memory frames to see if frame is occupied or not.
{
int a;

	for(a = 0; a < PHY_MEM_MAX; a ++)//Search through frames.
	{

		if(freeframes[a][0] == MAX_PROCESSES)//Frame is empty;MAX_PROCESSES means empty.
		{
			return a;//Return empty frame.
		}
	}
a = -1;

return a;					//Frame isn't empty.
}


//-----------------------------------------------------------------------------------------------------------



//FUNCTION TO CHECK PROCESS'S PAGE TABLE---------------------------------------------------------------------

int checkpagetable(char proc, int index)//Check page table of process to determine if INVALID or
{					//if VALID get frame index # and update clock, since page
int b;					//was referenced again.
int pro;
int ind;

pro = atoi(&proc);

pg_ref[pro]++;		//Update # of references of process by element, which represents process.

	if(pcblist[pro].list[pro].tbl[index][1] == INVALID)	//If bit = INVALID, page fault.
	{							//Return -1.
		b = -1;
		printf("PAGE FAULT on process %d page # %d\n",pro,index);
		pg_faults[pro] ++;
		page_faults = page_faults + 1;
		return b;
	}
	else							//Else get frame where page is located.
	{							//Update clock in the memory frame.
		ind = pcblist[pro].list[pro].tbl[index][0];	//Return 1.
		b = 1;
		update_clock(ind);
		return b;
	}

}

//-----------------------------------------------------------------------------------------------------------



//FUNCTION TO PUT PROCESS IN MEMORY--------------------------------------------------------------------------

void put_in_frame(char proc, int page, int freeframe)
{			//Put page in frame, paramaters process, page, and free frame index.
int a;
a = atoi(&proc);

freeframes[freeframe][0] = a;		//Put process # in simulated memory frame.
freeframes[freeframe][1] = page; 	//Put page # associated w/ process in frame.
freeframes[freeframe][2] = clock;	//Put clock flag in frame associated w/ process and page.
pcblist[a].list[a].tbl[page][0] = freeframe;	//Tell page table that process and page is in memory.
pcblist[a].list[a].tbl[page][1] = VALID;

}

//-----------------------------------------------------------------------------------------------------------