Skip to content

Instantly share code, notes, and snippets.

@ratmcu
Last active May 3, 2024 17:31
Show Gist options
  • Save ratmcu/9595272028b996a71b91f6d92221fccf to your computer and use it in GitHub Desktop.
Save ratmcu/9595272028b996a71b91f6d92221fccf to your computer and use it in GitHub Desktop.
virtual memory manager with paging in c++

compiling

$g++ --std=c++11 main.cpp -lpthread -o sim

running (make sure the simulation input file "input.txt" is places at the location with the current name)

./sim

8 // total No. of page frames in main memory
16 // page size (in bytes)
4 // No. of page frames per process for FIFO, LIFO, LRU-X, LDF...
4 // used by LRU-X, OPT-X for lookaheads
4 // min pool size
8 // max pool size
3 // total number of processes
100 16 // pid1 size1
101 16 // pid2 size2
102 16 // pid3 size3
101 0x0F // processid and address pairs..
100 0x1A
102 0x10
102 0xFF
100 0x20
100 0x6F
102 0x31
101 0x11
101 0x2A
101 0x30
100 0x71
100 0x6A
100 0x50
101 0x4A
101 0x50
100 0x7A
100 0x70
101 0x0A
100 0xFA
101 0x10
101 0x2A
102 0xA0
102 0x3A
101 0x30
100 0x70
100 0x5A
100 0x70
100 0xDA
100 0x6A
100 0x10
101 0x4A
101 0x5A
102 0xAA
101 0x00
101 0x1A
100 0x2A
100 0xA0
100 0x2A
100 0xDA
102 0x10
100 0x3A
100 0x30
101 0x20
101 0x3A
101 0x4A
101 0x5A
100 0x1A
102 0x3A
102 0xF0
100 0x20
100 -1 // process 100 ends
101 -1 // process 101 ends
102 0x3A
102 0xF0
102 0xFA
102 -1 // process 102 ends
#include <stdio.h>
#include <string>
#include <vector>
#include <limits.h> // for INT_MAX
#include <iostream>
#include <fstream>
#include <pthread.h>
pthread_mutex_t memory_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t disk_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t fault_condition_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t fault_condition_cond = PTHREAD_COND_INITIALIZER;
pthread_mutex_t disk_condition_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t disk_condition_cond = PTHREAD_COND_INITIALIZER;
std::vector<std::string> getStringParts(std::string line)
{
// std::cout << line << '\n';
std::vector<std::string> list;
if(line.size()==0) return list;
int end = line.find(' ');
if(end != std::string::npos)
{
list.push_back(line.substr(0, end));
std::vector<std::string> sub_list = getStringParts(line.substr(end+1, line.size()));
if(sub_list.size()!=0)
list.insert(list.end(), sub_list.begin(), sub_list.end());
}
else
{
end = line.size();
// if(line.substr(0, end).size())
list.push_back(line.substr(0, end));
}
return list;
}
struct Process
{
std::vector<int> frames;
std::string name;
unsigned int page_size;
unsigned int faults;
};
Process getProcess(std::string name, std::vector<Process> &processes)
{
for(int i= 0; i < processes.size(); i++)
{
if(name == processes[i].name)
{
return processes[i];
}
}
}
struct Frame
{
std::string process;
int number;
};
struct Memory
{
std::vector<Frame> *frames;
std::vector<int> *counts;
};
unsigned int countBits(unsigned int n)
{
unsigned int count = 0;
while (n)
{
count++;
n >>= 1;
}
return count;
}
struct DiskCommand
{
int rw; // 1 for write 0 for read;
Frame *frame;
int slot;
Memory *memory;
};
struct DiskArgs
{
DiskCommand *command;
};
struct HandlerArg
{
Memory *memory;
Frame *frame;
DiskCommand *disk_command;
};
struct ReplacerArgs
{
Memory *memory;
DiskCommand *disk_command;
};
int getFreeFrame(const Memory *memory)
{
for(int i= 0; i < memory->frames->size(); i++)
{
if(memory->frames->operator[](i).process.length()==0)
{
return i;
}
}
return -1;
}
void* handlerThread(void *vargp)
{
HandlerArg *arg = (HandlerArg *)vargp;
Memory *memory = arg->memory;
Frame *frame = arg->frame;
DiskCommand *disk_command = arg->disk_command;
while (1)
{
pthread_mutex_lock( &fault_condition_mutex );
pthread_cond_wait( &fault_condition_cond, &fault_condition_mutex );
pthread_mutex_unlock( &fault_condition_mutex );
//wait for a free frame in memory
//call the disk process with frame number and memory location and mamory slot
std::cout << "handling fault of process: " << frame->process << " for frame: " << frame->number << '\n';
int free_frame = getFreeFrame(memory);
while(free_frame == -1)
{
free_frame = getFreeFrame(memory);
std::cout << "no free frames!!\n";
}
//command and wait for the disk process
pthread_mutex_lock( &disk_mutex );
disk_command->frame = frame;
disk_command->rw = 0;
disk_command->slot = free_frame;
disk_command->memory = memory;
pthread_mutex_lock( &disk_condition_mutex );
pthread_cond_signal( &disk_condition_cond );
pthread_mutex_unlock( &disk_condition_mutex );
// std::cout << "waiting for disk to bring the frame \n";
pthread_mutex_lock( &disk_condition_mutex );
pthread_cond_wait( &disk_condition_cond, &disk_condition_mutex );
pthread_mutex_unlock( &disk_condition_mutex );
// std::cout << "disk brought the frame to memeory\n";
//signal back
pthread_mutex_lock( &fault_condition_mutex );
pthread_cond_signal( &fault_condition_cond );
pthread_mutex_unlock( &fault_condition_mutex );
pthread_mutex_unlock( &disk_mutex );
// std::cout << "signalled back to the simulator\n";
}
}
int maxCountSlot(Memory *memory)
{
int max = 0;
int slot = 0;
for(int i= 0; i < memory->counts->size(); i++)
{
if(memory->counts->operator[](i) > max)
{
max = memory->counts->operator[](i);
slot = i;
}
}
return slot;
}
int freeSolts(Memory *memory)
{
int count = 0;
for(int i= 0; i < memory->frames->size(); i++)
{
if(memory->frames->operator[](i).process.length()==0)
{
count++;
}
}
return count;
}
void* replacementThread(void *vargp)
{
ReplacerArgs *arg = (ReplacerArgs *)vargp;
Memory *memory = arg->memory;
DiskCommand *disk_command = arg->disk_command;
int min = 4;
int max = 8;
int free_slots = 0;
Frame frame;
while (1)
{
free_slots = freeSolts(memory);
while(free_slots > 4 )
{
free_slots = freeSolts(memory);
}
disk_command->frame = &frame;
disk_command->rw = 1;
disk_command->slot = maxCountSlot(memory);
disk_command->memory = memory;
pthread_mutex_lock( &disk_mutex );
pthread_mutex_lock( &disk_condition_mutex );
pthread_cond_signal( &disk_condition_cond );
pthread_mutex_unlock( &disk_condition_mutex );
// std::cout << "waiting for frame be written to the disk\n";
pthread_mutex_lock( &disk_condition_mutex );
pthread_cond_wait( &disk_condition_cond, &disk_condition_mutex );
pthread_mutex_unlock( &disk_condition_mutex );
pthread_mutex_unlock( &disk_mutex );
// std::cout << "disk saved the frame in disk\n";
}
}
void modifyMemory(Frame *frame, Memory *memory, int slot, int rw)
{
if(rw==0)
{
memory->frames->operator[](slot) = *frame;
}
else
{
memory->frames->operator[](slot).number = -1;
memory->frames->operator[](slot).process = "";
}
}
void* diskThread(void *vargp)
{
DiskArgs *arg = (DiskArgs *)vargp;
DiskCommand *command = arg->command;
while (1)
{
pthread_mutex_lock( &disk_condition_mutex );
pthread_cond_wait( &disk_condition_cond, &disk_condition_mutex );
pthread_mutex_unlock( &disk_condition_mutex );
// std::cout << "disk started \n";
modifyMemory(command->frame, command->memory, command->slot, command->rw);
pthread_mutex_lock( &disk_condition_mutex );
pthread_cond_signal( &disk_condition_cond );
pthread_mutex_unlock( &disk_condition_mutex );
}
}
void updateProcesses(Process process, std::vector<Process> &processes)
{
for(int i= 0; i < processes.size(); i++)
{
if(process.name == processes[i].name)
{
processes[i] = process;
return;
}
}
}
int pageInMemory(std::string name, int page, const Memory *memory)
{
for(int i= 0; i < memory->frames->size(); i++)
{
if(name == memory->frames->operator[](i).process && page == memory->frames->operator[](i).number )
{
return 1;
}
}
return -1;
}
void memorySweepFIFO(Memory *memory)
{
for(int i= 0; i < memory->counts->size(); i++)
{
memory->counts->operator[](i)++;
}
}
int main()
{
std::ifstream file("input.txt");
std::string line;
std::vector<std::vector<std::string>> sim_data;
while(std::getline(file, line))
{
std::vector<std::string> list = getStringParts(line);
sim_data.push_back(list);
}
//create the simulator
//initialize memory
int memory_size = std::stoi(sim_data[0][0]);
std::vector<Frame> *frames = new std::vector<Frame>(memory_size);
std::vector<int> *counts = new std::vector<int>(memory_size);
std::cout << "total frames in memeory: " << memory_size << '\n';
for( int i = 0; i++ ;i<memory_size)
{
Frame frame;
frame.process = "";
frame.number = -1;
frames->operator[](i)= frame;
counts->operator[](i)= 0;
}
Memory *memory = new Memory;
memory->frames = frames;
memory->counts = counts;
//create the processes
int process_number = std::stoi(sim_data[6][0]);
std::cout << "number of processes: " << process_number << '\n';
std::vector<Process> processes;
for( int i = 0; i<process_number; i++)
{
Process process;
process.faults = 0;
process.page_size = std::stoi(sim_data[6+1+i][1]);
process.name = sim_data[6+1+i][0];
processes.push_back(process);
}
//create the disk process
pthread_t driver_id;
DiskArgs *dkarg = new DiskArgs;
DiskCommand *dcmd = new DiskCommand;
dkarg->command = dcmd;
pthread_create(&driver_id, NULL, diskThread, (void*)dkarg);
//create the fault handler process
pthread_t handler_id;
HandlerArg *hndlr = new HandlerArg;
Frame *missing_frame = new Frame;
hndlr->memory = memory;
hndlr->frame = missing_frame;
hndlr->disk_command = dkarg->command;
pthread_create(&handler_id, NULL, handlerThread, (void*)hndlr);
//create the page replacement process
pthread_t rplcmnt_id;
ReplacerArgs *rparg = new ReplacerArgs;
rparg->memory = memory;
rparg->disk_command = dkarg->command;
pthread_create(&rplcmnt_id, NULL, replacementThread, (void*)rparg);
//run simulation
int page_size = std::stoi(sim_data[1][0]);
std::cout << "page size: " << page_size << '\n';
for( int i = 6+process_number+1; i < sim_data.size(); i++)
{
Process process = getProcess(sim_data[i][0], processes);
if (std::stoi(sim_data[i][1], 0, 16 )==-1)
{
continue;
std::cout << "process died \n";
}
int page = std::stoi(sim_data[i][1], 0, 16 ) >> (countBits(page_size)-1);
// std::cout << sim_data[i][0] << " " << std::stoi(sim_data[i][1], 0, 16 ) << '\n';
// std::cout << page << " \n";
if(-1==pageInMemory(process.name, page, memory))
{
// signal handler and wait
// std::cout << "fault occured" << "\n";
missing_frame->number = page;
missing_frame->process = process.name;
pthread_mutex_lock( &fault_condition_mutex );
pthread_cond_signal( &fault_condition_cond );
pthread_mutex_unlock( &fault_condition_mutex );
pthread_mutex_lock( &fault_condition_mutex );
pthread_cond_wait( &fault_condition_cond, &fault_condition_mutex );
pthread_mutex_unlock( &fault_condition_mutex );
process.faults++;
updateProcesses(process, processes);
memorySweepFIFO(memory);
}
}//end of simulation loop
int total = 0;
for(auto process: processes)
{
std::cout << "faults from process " << process.name << " :" << process.faults << " \n";
total += process.faults;
}
std::cout << "total faults: " << total << " \n";
return 0;
}
@Tahashayan
Copy link

please I want that

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment