VMM_Simulator_program

// CSC139HW2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//Sharon Fitzpatrick
// VMM Simulator
//creates a trace file that show the programs's execution
//creates a debug file that shows all elements of swapping, allocation,and more
//reads from an input.txt file that contains the reads and write that is generated by the other program Address_Generator.cpp

#include<cstdio>  
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<stack>
#include <vector>
#include<string>
#include<iostream>
#include <fstream>
#include <sstream> 

using namespace std;

// const global variables
const int REPLACEMENT_CYCLES = 10;					    //cost of replacing a page   
const int PAGE_SIZE = 4096;
const int MAX_PAGE_ENTRIES = 1024;						//4096 / 4 
const int PAGE_DIR_ACCESS = 1;							// access through PD cost 1 cycle each
const int SWAP_COST = 5000;

//global variables
int MEM_CYCLES = 0;
int MEM_ACCESS = 0;
int NUMBER_SWAPINS = 0;
int NUMBER_SWAPOUTS = 0;
int TOTAL_PAGES_MALLOC = 0;
int TRIPLES = 0;
int NUMBER_PAGE_FRAMES = 0;
int NUM_PAGES_PAGETABLE = 0;
int LAST_WORKING_SET = 0;
int MAX_WORKING_SET = 0;
int MAX_PHYSICAL_PAGES = 0;
int MEM_CYCLES_NO_VMM = 0;

unsigned int get_page_offset(unsigned int address)
{
	int PAGE_MASK = 4095;
	return (address & PAGE_MASK); // get second set of leftmost 10 bits
}

unsigned int get_pagetable_index(unsigned int address)
{
	int PT_MASK = 4190208;
	return (address & PT_MASK) >> 12; // get second set of leftmost 10 bits
}

unsigned int get_pagedir_index(unsigned int address)
{
	return (address >> 22); //get leftmost 10 bits by geting rid of 22 rightmost bits we dont care about
}


int get_address(int pt_index, int pd_index)
{
	string string_pt = to_string(pt_index);
	string string_pd = to_string(pd_index);
	string addr_string = string_pt + string_pd;
	return(stoi(addr_string));
}

class STATS {
public:

	void write_to_output()
	{

		MEM_CYCLES_NO_VMM = MEM_ACCESS * REPLACEMENT_CYCLES;

		ofstream myfile;
		myfile.open("output.txt");
		myfile << "***Paging Activity Statistics * **.\n";
		myfile << "number of memory accesses =" << MEM_ACCESS << " .\n";
		//TRIPLES = MEM_ACCESS + 1;	
		myfile << "number of triples(1 + access) = " << TRIPLES << " .\n";
		myfile << "number of swap ins(faults) = " << NUMBER_SWAPINS << " .\n";
		myfile << "number of swap outs = " << NUMBER_SWAPOUTS << " .\n";
		TOTAL_PAGES_MALLOC += NUM_PAGES_PAGETABLE;
		myfile << "total number of pages malloced = " << TOTAL_PAGES_MALLOC << " .\n";
		myfile << "number of pages for Page Tables = " << NUM_PAGES_PAGETABLE << " .\n";
		myfile << "number of page frames for user = " << NUMBER_PAGE_FRAMES << " .\n";
		myfile << "total memory cycles = " << MEM_CYCLES << " .\n";
		MEM_CYCLES_NO_VMM = MEM_ACCESS * REPLACEMENT_CYCLES;
		myfile << "cycles w / o Vmm = " << MEM_CYCLES_NO_VMM << " .\n";
		myfile << "cycles per swap_in = 5000.\n";
		myfile << "cycles per swap_out = 5000.\n";
		myfile << "last working set size = " << LAST_WORKING_SET << " .\n";
		myfile << "max working set size ever = " << MAX_WORKING_SET << " .\n";
		myfile << "max physical pages = " << MAX_PHYSICAL_PAGES << " .\n";
		myfile << "page size = 4096.\n";
		myfile << "replacement algorithm = random.\n";
		myfile << "Address Range: 0 - 4290772992 .\n";
		myfile.close();
	}

};
//function to read input file


struct PageTable_entry {
	unsigned int address = 0;	//address of page (address given shifted by 12 bits to the right)
	bool Dirtybit = 0;		//set if page frame is modified
	bool Presentbit = 0;		//set if page frame is in memory
	bool On_Disk = 0;		//set if page frame is on disk
	int index_of_frame = -1;	//index of page frame it points to -1 means it doesnt exist or on the disk
};

struct PageTable
{
	PageTable_entry pt_entries[1024];//a page table can hold 1024 total enties (4096 total bytes/4 bytes per entry)
	bool exists = 0;
};

class DiskBlock {
private:
	typedef struct Disk {
		unsigned int page_address;			//address of page
		Disk* next_disk;
	}*disk_ptr;

	disk_ptr head;
	disk_ptr temp;
	disk_ptr curr;

public:
	void Add_Disk(unsigned int addr, ofstream& debug)
	{
		disk_ptr newdisk = new Disk;
		newdisk->next_disk = NULL;
		newdisk->page_address = addr;

		if (head != NULL)
		{
			curr = head;
			while (curr->next_disk != NULL)
			{
				curr = curr->next_disk;
				if (curr->page_address == addr)
				{
					debug << "\n This address was already on the disk. Address: " << curr->page_address << "\n";
					delete  newdisk;			//delete the new disk that was created
					return;						//end the loop and exit this address is already on the disk
				}
			}

			curr->next_disk = newdisk;//new page will be  at the end of list of disks
			debug << endl << "\npage with address: " << addr << " was added to the disk";
		}
		else//means we have an empty disk
		{
			head = newdisk;
			debug << endl << "page with address: " << addr << " was added to head of the disk";
		}
	}
	bool Remove_disk(unsigned int addr)
	{
		disk_ptr delete_disk = NULL;
		temp = head;
		curr = head;
		while ((curr != NULL) && (curr->page_address != addr))
		{
			temp = curr;
			curr = curr->next_disk;
		}
		if (curr == NULL)
		{
			cout << endl << "page with address: " << addr << "was not on the disk";
			return false;
		}
		else
		{
			cout << endl << "page with address: " << addr << "was deleted from the disk";
			delete_disk = curr;
			curr = curr->next_disk;
			temp->next_disk = curr;
			delete delete_disk;
			return true;
		}
	}
	void print_disk()
	{
		curr = head;
		cout << "\n*****Printing contents of disk*****\n";
		while (curr != NULL)
		{
			cout << curr->page_address << endl;
			curr = curr->next_disk;
		}
	}
	~DiskBlock() {
		curr = head;
		temp = head;
		while (curr)
		{
			curr = curr->next_disk;//move to text spot
			free(temp);
			temp = curr;
		}
	}
};

class Main_Memory {
	int num_free_frame_left;
	//dynamically allocated page frames based on page frames given by user
	PageTable_entry** page_frames;
	DiskBlock disk;
public:
	Main_Memory(int max_frames)
	{
		page_frames = new PageTable_entry * [max_frames];
		num_free_frame_left = max_frames;
	}

	~Main_Memory()
	{
		delete[] page_frames;
		num_free_frame_left = 0;
	}

	void allocate_free_frames(PageTable_entry* pt_entry, int& cost, ofstream& debug, ofstream& trace, char mode) {
		int index_frame;

		if (pt_entry->Presentbit == 1)//page currently resides in memory.
		{
			//if write set the dirty bit
			if (mode == 'w')
			{
				pt_entry->Dirtybit = 1;
				debug << "\n Page was already in memory at Page Frame Index: " << pt_entry->Presentbit << " and was written to.";
			}
			else
			{
				debug << "\n Page was already in memory at Page Frame Index: " << pt_entry->Presentbit;
			}

			return;//exit there is nothing left to do
		}

		if (!any_free_frame())//means no free frames 
		{
			index_frame = 0;
			if (pt_entry->On_Disk == 0)		//means this page has never existed before and we need to create a 
				++TOTAL_PAGES_MALLOC;

			if ((page_frames[index_frame]->Dirtybit == 1) && (page_frames[index_frame]->On_Disk == 1))
			{
				//Swap Out to update the disk entry
				debug << "\n Swap out for dirty bit=1 with page address " << pt_entry->address << " and on disk for victim page " << page_frames[index_frame]->address;
				Swap_Out(page_frames, index_frame, disk, debug, trace);			//swap out will update the page's information, set present bit false, on disk = true
				cost += SWAP_COST;									// add swap out cost
				debug << "\n total cost: " << cost;
				page_frames[index_frame]->On_Disk = 1;

			}
			else if ((page_frames[index_frame]->Dirtybit == 1) && (page_frames[index_frame]->On_Disk == 0))
			{
				//the page is dirty and not on disk so it must be swapped out
				debug << "\n Swap out for dirty bit=1 with page address " << pt_entry->address << " and not on disk for victim page " << page_frames[index_frame]->address;
				Swap_Out(page_frames, index_frame, disk, debug, trace);			//swap out will update the page's information, set present bit false, on disk = true
				cost += SWAP_COST;									// add swap out cost
				debug << "\n total cost: " << cost;
				page_frames[index_frame]->On_Disk = 1;
			}
			else
			{
				//Dirtybit = 0 and On_Disk = 0 meaning the page was not modified and not on disk so it must be swapped out
				debug << "\n Swap out for dirty bit=0 with page address " << pt_entry->address << " and not on disk for victim page " << page_frames[index_frame]->address;
				Swap_Out(page_frames, index_frame, disk, debug, trace);			//swap out will update the page's information, set present bit false, on disk = true
				cost += SWAP_COST;									// add swap out cost
				debug << "\n total cost: " << cost;
				page_frames[index_frame]->On_Disk = 1;
			}
			//If its not one of these options: the victim page was not dirty and the most update to date version is already on disk just overwrite it
			if (((*pt_entry).On_Disk == true) && ((*pt_entry).Presentbit == false))						//if new entry already has a copy on the disk and is not present
			{
				debug << "\n Swap in for new entry that was on disk addr  " << (*pt_entry).address;
				Swap_In(pt_entry, disk, debug, trace);							// swap in removes the page from the disk
				cost += SWAP_COST;									//add swap in cost

			}
			page_frames[index_frame] = pt_entry;				//replace the first page frame with the page
			pt_entry->index_of_frame = 0;							//indicate which index the page reside on
			pt_entry->Presentbit = 1;							//indicate which index the page reside on

		}
		else//means there are free frames available
		{
			++TOTAL_PAGES_MALLOC;
			index_frame = num_free_frame_left - 1;		//fill in pages from last spot to first spot
			++LAST_WORKING_SET;
			if (MAX_PHYSICAL_PAGES < NUMBER_PAGE_FRAMES) ++MAX_PHYSICAL_PAGES;
			if (MAX_WORKING_SET < MAX_PHYSICAL_PAGES)  ++MAX_WORKING_SET;

			debug << "\n There were free frames available. Index: " << index_frame << "is free";
			take_free_frame();							//remove a free frame
			debug << "\n After take_free_frame() page frames left: " << num_free_frame_left;

			pt_entry->index_of_frame = index_frame;						//indicate which frame is associated with the page
			debug << "\n Addresses stored at frame " << index_frame << " is page addr: " << pt_entry->address;

			page_frames[index_frame] = pt_entry;
			debug << "\nPage_frames[index_frame]->address" << page_frames[index_frame]->address;
			pt_entry->Presentbit = true;				//set present bit to true to indicate its in memory
			pt_entry->index_of_frame = index_frame;

		}

	}

	void delete_freeframes()
	{
		delete[] page_frames;
	}
	void take_free_frame() { --num_free_frame_left; }
	bool any_free_frame() { return ((num_free_frame_left <= 0) ? false : true); }


	//take a page away from the page_frames 
	void Swap_Out(PageTable_entry** pt, int pageframeindex, DiskBlock out_disk, ofstream& debug, ofstream& trace)
	{
		//take the first page out of the page frame array for random replacement
		MEM_CYCLES += SWAP_COST;
		(*(pt + pageframeindex))->Presentbit = 0;							//indicates no longer on a frame
		(*(pt + pageframeindex))->Dirtybit = 0;								// page to be stored on disk so the modify bit is cleared
		(*(pt + pageframeindex))->index_of_frame = -1;						// page to be stored on disk so the page frame index is cleared
		out_disk.Add_Disk((*pt + pageframeindex)->address, debug);					//add the page to disk block
		//remove the page from the page frame index =0
		debug << "\nSWAP OUT COMPLETE FOR page frame address " << (*(pt + pageframeindex))->address;
		trace << "\nSwapped out page frame[0]: old page address  " << (*(pt + pageframeindex))->address << " is now on disk, 5000 cycles";
		++NUMBER_SWAPOUTS;
	}
	void Swap_In(PageTable_entry* pt, DiskBlock in_disk, ofstream& debug, ofstream& trace)
	{
		//move a page from disk into first spot page frame array for random replacement
		++NUMBER_SWAPINS;
		MEM_CYCLES += SWAP_COST;
		pt->Presentbit = 1;					//set pagetable present bit to true
		pt->Dirtybit = 0;					//set modify bit to false;
		debug << "\nSWAP IN COMPLETE FOR page address, which is now at page frame 0 " << (pt)->address;
		trace << "\nSwapped in  page address " << (pt)->address << ", 5000 cycles";
	}
};

void read(ofstream& trace, ofstream& debug, PageTable* pd, unsigned int address, Main_Memory& memory, int total_cost, char mode)
{
	int page_offset = get_page_offset(address);
	int page_table_index = get_pagetable_index(address);
	int page_dir_index = get_pagedir_index(address);
	debug << "\npage_offset " << page_offset;
	debug << "\npage_table_index " << page_table_index;
	debug << "\npage_dir_index " << page_dir_index;

	string mode_type;
	mode_type = (mode == 'r') ? "read" : "write";

	if (pd[page_dir_index].pt_entries[page_table_index].Presentbit == 0)	//if there is no page on the page table index
	{
		total_cost += REPLACEMENT_CYCLES;
		MEM_CYCLES += REPLACEMENT_CYCLES;
		trace << "\nPT[" << page_table_index << "] is NULL: 10 cycles";
		total_cost += SWAP_COST;
		MEM_CYCLES += SWAP_COST;
		trace << "\nPT[" << page_table_index << "] allocates new page : 5000 cycles";
		pd[page_dir_index].pt_entries[page_table_index].address = get_address(page_table_index, page_dir_index);

		total_cost += REPLACEMENT_CYCLES;
		MEM_CYCLES += REPLACEMENT_CYCLES;
		trace << "\nPT[" << page_table_index << "] is address " << pd[page_dir_index].pt_entries[page_table_index].address << ", 10 cycles";

		PageTable_entry* temp_ptr = &(pd[page_dir_index].pt_entries[page_table_index]);

		memory.allocate_free_frames(temp_ptr, total_cost, debug, trace, mode);

		total_cost += REPLACEMENT_CYCLES;
		MEM_CYCLES += REPLACEMENT_CYCLES;
		trace << "\n" << mode_type << " address + " << page_offset << " ,10 cycles";

		trace << "\nTotal cost: " << total_cost << " cycles -- end output for 1 " << mode_type << " \n";
		debug << "\n Page address " << pd[page_dir_index].pt_entries[page_table_index].address << " stored at page frame index " << pd[page_dir_index].pt_entries[page_table_index].index_of_frame;
	}
	else  //page is currently in memory and has page frame
	{
		total_cost += REPLACEMENT_CYCLES;
		MEM_CYCLES += REPLACEMENT_CYCLES;
		pd[page_dir_index].pt_entries[page_table_index].address = get_address(page_table_index, page_dir_index);
		trace << "\nPT[" << page_table_index << "] is address " << pd[page_dir_index].pt_entries[page_table_index].address << ", 10 cycles";

		total_cost += REPLACEMENT_CYCLES;
		MEM_CYCLES += REPLACEMENT_CYCLES;
		trace << "\n" << mode_type << " address + " << page_offset << " ,10 cycles";
		PageTable_entry* temp_ptr = &(pd[page_dir_index].pt_entries[page_table_index]);
		memory.allocate_free_frames(temp_ptr, total_cost, debug, trace, mode);
		trace << "\nTotal cost: " << total_cost << " cycles -- end output for 1 " << mode_type << " \n";
	}

}

void Read_Input_file(string filename) {
	string myText;						// myText is used to read lines from the file with stringstream
	string first_line;
	string character;
	unsigned int address1;
	unsigned int address2;
	int page_frames;
	bool fail = 0;

	PageTable* PD_array;
	PD_array = new PageTable[1024];


	ofstream debugfile, tracefile;
	debugfile.open("debug.txt");
	debugfile << "*****Debug file*******";
	tracefile.open("trace.txt");
	tracefile << "*****Trace file*******";

	// Read from the text file
	ifstream MyReadFile(filename.c_str());

	getline(MyReadFile, first_line);
	istringstream istr1(first_line);
	//read the first line containg number of page fraems : ex)p 9
	istr1 >> character;
	if (character[0] == 'p' || character[0] == 'P')
	{
		istr1 >> page_frames;
		debugfile << "\nRead in the number of max number of user page frames: " << character[0] << " " << page_frames;
		tracefile << "\nRead in the number of max number of user page frames: " << character[0] << " " << page_frames;
		NUMBER_PAGE_FRAMES = (page_frames > 0) ? page_frames : 1; //if number of page frames is less than 0 use 1 page frame
		cout << "\n NUMBER_PAGE_FRAMES read in: " << NUMBER_PAGE_FRAMES;
		++TRIPLES;

	}
	Main_Memory mem(NUMBER_PAGE_FRAMES);
	// Use a while loop together with the getline() function to read the file line by line
	while (getline(MyReadFile, myText)) {
		// Output the text from the file
		debugfile << "\n Read from file: " << myText << " End of line \n";
		istringstream istr1(myText);

		for (int i = 0; i < 5; ++i)
		{
			istr1 >> character;
			int total = 0;									// total cost for a memory operation

			if (character[0] == 'w' || character[0] == 'W')	//check for write 
			{
				character[0] = 'w';
				++TRIPLES;
				++MEM_ACCESS;
				debugfile << "\n\nWrite operation: " << character[0];
				istr1 >> address1 >> address2;
				debugfile << "\naddress1 " << address1 << "\naddress2 " << address2;

				int page_dir_index = get_pagedir_index(address1);
				debugfile << "\npage_dir_index " << page_dir_index;

				if ((PD_array[page_dir_index]).exists == 0)				//no page directory entry exists for this index
				{
					++NUM_PAGES_PAGETABLE;								//A new page table must be allocated for this page directory entry
					debugfile << "\npage Fault occured at pd[" << page_dir_index << "]";
					tracefile << "\n\nPD[" << page_dir_index << "] is NULL: 1 cycle";
					++MEM_CYCLES;
					++total;

					PD_array[page_dir_index].exists = 1;		//make a page table entry associated with this page directory index
					MEM_CYCLES += SWAP_COST;
					total += SWAP_COST;
					tracefile << "\nPD[" << page_dir_index << "] allocates new page table: 5000 cycles -- start output 1 write";

					++MEM_CYCLES;
					++total;
					tracefile << "\nPD[" << page_dir_index << "] = address of page table[" << page_dir_index << "], 1 cycle ";

					++NUM_PAGES_PAGETABLE;						//each page dir points to a different page table, so increase the number of pages for the page table
					tracefile << "\nNew page table allocated Pagetable[" << page_dir_index << "]";

					read(tracefile, debugfile, PD_array, address1, mem, total, character[0]);

				}
				else   //a page directory exists for this index
				{
					tracefile << "\n\nPD[" << page_dir_index << "] is address , 1 cycle  -- -- start output 1 write";
					++MEM_CYCLES;
					++total;
					read(tracefile, debugfile, PD_array, address1, mem, total, character[0]);
				}
			}
			else if (character[0] == 'r' || character[0] == 'R')
			{
				character[0] = 'r';
				++TRIPLES;			//read in a triple
				++MEM_ACCESS;		//read is a memory access
				debugfile << "\n\nRead operation: " << character[0];
				istr1 >> address1;
				debugfile << "\naddress1 " << address1;
				int page_offset = get_page_offset(address1);
				int page_table_index = get_pagetable_index(address1);
				int page_dir_index = get_pagedir_index(address1);

				if ((PD_array[page_dir_index]).exists == 0)				//no page directory entry exists for this index
				{
					++NUM_PAGES_PAGETABLE;								//A new page table must be allocated for this page directory entry
					debugfile << "\n\npage Fault occured at pd[" << page_dir_index << "]";
					tracefile << "\n\nPD[" << page_dir_index << "] is NULL: 1 cycle";

					++MEM_CYCLES;
					++total;
					PD_array[page_dir_index].exists = 1;		//make a page table entry associated with this page directory index
					MEM_CYCLES += SWAP_COST;
					total += SWAP_COST;

					tracefile << "\nPD[" << page_dir_index << "] allocates new page table: 5000 cycles -- start output 1 read";
					++MEM_CYCLES;
					++total;

					tracefile << "\nPD[" << page_dir_index << "] = address of page table[" << page_dir_index << "], 1 cycle ";
					++NUM_PAGES_PAGETABLE;

					read(tracefile, debugfile, PD_array, address1, mem, total, character[0]);
				}
				else   //a page directory exists for this index
				{
					tracefile << "\n\nPD[" << page_dir_index << "] is address , 1 cycle  -- start output 1 read";
					++MEM_CYCLES;
					++total;
					read(tracefile, debugfile, PD_array, address1, mem, total, character[0]);
				}

			}
			else {
				debugfile << "\nUnknown variable read!Exiting file";
				cout << "\nUnknown variable read!Exiting file";
				fail = 1;
				break;
			}
		}
	}

	// Close the file
	delete[] PD_array;				//free allocated memory
	MyReadFile.close();
	debugfile.close();
	tracefile.close();
	if (!fail)
		cout << "\nFinished Successfully\n";
}

int main()
{
	Read_Input_file("input.txt");
	STATS stat_file;
	stat_file.write_to_output();

}