Muhammad Usman Faridi
68062
Complex Computing Problem
6/7/24
Submit to: Sir Azeem
Detailed Design and Implementation
1. Resource Management
Allocation Tables/Maps: Use a data structure (e.g., hash map or array) to track
the allocation of physical memory to each VM. This structure will map each VM
to its allocated memory blocks.
Memory Allocation Strategy: Implement strategies for efficient memory
allocation, considering factors such as VM priority, current memory usage, and
available resources. The system should dynamically adjust allocations based on
demand.
Code to implement:
#include <iostream>
#include <vector>
#define TOTAL_PHYSICAL_MEMORY 1024 // Example size in MB
struct VM {
int vm_id;
size_t allocated_memory;
};
class MemoryManager {
public:
MemoryManager(size_t total_memory) : total_memory(total_memory),
used_memory(0) {}
bool allocate_memory(int vm_id, size_t size) {
if (used_memory + size > TOTAL_PHYSICAL_MEMORY) {
return false; // Not enough memory
}
VM vm = {vm_id, size};
vms.push_back(vm);
used_memory += size;
return true;
}
void deallocate_memory(int vm_id) {
for (auto it = vms.begin(); it != vms.end(); ++it) {
if (it->vm_id == vm_id) {
used_memory -= it->allocated_memory;
vms.erase(it);
break;
}
}
}
void print_memory_status() const {
std::cout << "Total Memory: " << TOTAL_PHYSICAL_MEMORY << "
MB\n";
std::cout << "Used Memory: " << used_memory << " MB\n";
std::cout << "Available Memory: " << TOTAL_PHYSICAL_MEMORY -
used_memory << " MB\n";
for (const auto &vm : vms) {
std::cout << "VM ID: " << vm.vm_id << ", Allocated Memory: " <<
vm.allocated_memory << " MB\n";
}
}
private:
std::vector<VM> vms;
size_t total_memory;
size_t used_memory;
};
int main() {
MemoryManager manager(TOTAL_PHYSICAL_MEMORY);
manager.allocate_memory(1, 200);
manager.allocate_memory(2, 300);
manager.print_memory_status();
manager.deallocate_memory(1);
manager.print_memory_status();
return 0;
}
Picture of the output:
2. Demand Paging
Page Tables: Each VM will have a page table to map virtual pages to physical
frames. The page table will store information about the location of each page (in
memory or on disk).
On-Demand Loading: Implement mechanisms to load pages into memory only
when accessed, updating the page table accordingly.
Code to implement:
#include <iostream>
#include <vector>
#include <cstdlib>
#define PAGE_SIZE 4
#define NUM_PAGES 256
struct PageTableEntry {
int page_number;
bool in_memory;
int frame_number;
};
struct VM {
int vm_id;
std::vector<PageTableEntry> page_table;
VM(int id) : vm_id(id), page_table(NUM_PAGES) {
for (int i = 0; i < NUM_PAGES; ++i) {
page_table[i].page_number = i;
page_table[i].in_memory = false;
page_table[i].frame_number = -1;
}
}
};
class MemoryManager {
public:
MemoryManager() {}
VM* create_vm(int vm_id) {
vms.emplace_back(vm_id);
return &vms.back();
}
void load_page(VM* vm, int page_number, int frame_number) {
vm->page_table[page_number].in_memory = true;
vm->page_table[page_number].frame_number = frame_number;
}
void unload_page(VM* vm, int page_number) {
vm->page_table[page_number].in_memory = false;
vm->page_table[page_number].frame_number = -1;
}
void access_page(VM* vm, int page_number) {
if (vm->page_table[page_number].in_memory) {
std::cout << "Page " << page_number << " is in memory at frame " <<
vm->page_table[page_number].frame_number << "\n";
} else {
std::cout << "Page " << page_number << " is not in memory, loading
page...\n";
// Simulate loading the page into memory
load_page(vm, page_number, rand() % NUM_PAGES);
std::cout << "Page " << page_number << " loaded into frame " << vm-
>page_table[page_number].frame_number << "\n";
}
}
private:
std::vector<VM> vms;
};
int main() {
MemoryManager manager;
VM* vm = manager.create_vm(1);
manager.access_page(vm, 10);
manager.access_page(vm, 10);
manager.unload_page(vm, 10);
manager.access_page(vm, 10);
return 0;
}
Picture of the output:
3. Page Fault Handling
Following are the steps to handle page fault
Detect page fault.
Identify the missing page.
Fetch the page from disk.
Update the page table.
Resume VM execution.
Code to Implement
#include <iostream>
#include <vector>
#include <cstdlib>
#define PAGE_SIZE 4 // Example page size in KB
#define NUM_PAGES 256 // Example number of pages per VM
struct PageTableEntry {
int page_number;
bool in_memory;
int frame_number;
};
struct VM {
int vm_id;
std::vector<PageTableEntry> page_table;
VM(int id) : vm_id(id), page_table(NUM_PAGES) {
for (int i = 0; i < NUM_PAGES; ++i) {
page_table[i].page_number = i;
page_table[i].in_memory = false;
page_table[i].frame_number = -1;
}
}
};
class MemoryManager {
public:
MemoryManager() {}
VM* create_vm(int vm_id) {
vms.emplace_back(vm_id);
return &vms.back();
}
void load_page(VM* vm, int page_number, int frame_number) {
vm->page_table[page_number].in_memory = true;
vm->page_table[page_number].frame_number = frame_number;
}
void handle_page_fault(VM* vm, int page_number) {
std::cout << "Handling page fault for page " << page_number << "\n";
// Simulate fetching the page from disk
load_page(vm, page_number, rand() % NUM_PAGES);
std::cout << "Page " << page_number << " loaded into frame " << vm-
>page_table[page_number].frame_number << "\n";
}
void access_page(VM* vm, int page_number) {
if (vm->page_table[page_number].in_memory) {
std::cout << "Page " << page_number << " is in memory at frame " <<
vm->page_table[page_number].frame_number << "\n";
} else {
std::cout << "Page " << page_number << " is not in memory, triggering
page fault...\n";
handle_page_fault(vm, page_number);
std::cout << "Page " << page_number << " is now in memory at frame "
<< vm->page_table[page_number].frame_number << "\n";
}
}
private:
std::vector<VM> vms;
};
int main() {
MemoryManager manager;
VM* vm = manager.create_vm(1);
manager.access_page(vm, 10);
manager.access_page(vm, 20);
manager.access_page(vm, 10);
return 0;
}
Picture of the output:
4. Page Replacement
Replacement Algorithms: Implement LRU (Least Recently Used), FIFO (First In,
First Out), and potentially a custom hybrid algorithm.
Selection Criteria: Use access patterns and page usage history to decide which
pages to evict.
Code to implement:
#include <iostream>
#include <vector>
#include <climits>
#include <cstdlib>
#define PAGE_SIZE 4
#define NUM_PAGES 256
#define PHYSICAL_FRAMES 64
struct PageTableEntry {
int page_number;
bool in_memory;
int frame_number;
int last_access_time;
PageTableEntry() : page_number(-1), in_memory(false), frame_number(-1),
last_access_time(-1) {}
};
class VM {
public:
int vm_id;
std::vector<PageTableEntry> page_table;
VM(int id) : vm_id(id), page_table(NUM_PAGES) {
for (int i = 0; i < NUM_PAGES; ++i) {
page_table[i].page_number = i;
};
class MemoryManager {
public:
std::vector<VM> vms;
int current_time;
MemoryManager() : current_time(0) {}
VM* create_vm(int vm_id) {
vms.emplace_back(vm_id);
return &vms.back();
int select_page_to_replace(const std::vector<PageTableEntry>& page_table) {
int lru_page = -1;
int min_access_time = INT_MAX;
for (const auto& entry : page_table) {
if (entry.in_memory && entry.last_access_time < min_access_time) {
min_access_time = entry.last_access_time;
lru_page = entry.page_number;
}
return lru_page;
void handle_page_fault(VM* vm, int page_number) {
std::cout << "Handling page fault for page " << page_number << "\n";
int frame_number = -1;
// Check if there is a free frame
for (int i = 0; i < NUM_PAGES; ++i) {
if (!vm->page_table[i].in_memory) {
frame_number = i;
break;
// If no free frame, select a page to replace
if (frame_number == -1) {
int lru_page = select_page_to_replace(vm->page_table);
frame_number = vm->page_table[lru_page].frame_number;
vm->page_table[lru_page].in_memory = false;
vm->page_table[lru_page].frame_number = -1;
// Stimulate fetching the page from disk
vm->page_table [page_number].in_memory = true;
vm->page_table[page_number].frame_number = frame_number;
vm->page_table[page_number].last_access_time = current_time;
std::cout << "Page " << page_number << " loaded into frame " << frame_number
<< "\n";
}
void access_page(VM* vm, int page_number) {
current_time++;
if (vm->page_table[page_number].in_memory) {
std::cout << "Page " << page_number << " is in memory at frame " << vm-
>page_table[page_number].frame_number << "\n";
vm->page_table[page_number].last_access_time = current_time;
} else {
std::cout << "Page " << page_number << " is not in memory, triggering page
fault...\n";
handle_page_fault(vm, page_number);
std::cout << "Page " << page_number << " is now in memory at frame " << vm-
>page_table[page_number].frame_number << "\n";
};
int main() {
MemoryManager manager;
VM* vm = manager.create_vm(1);
manager.access_page(vm, 10);
manager.access_page(vm, 20);
manager.access_page(vm, 10);
return 0;
}
Output of the Code:
5. Performance Monitoring
Metrics Collection: Track metrics such as page fault rate, memory utilization,
and response time.
Analysis Tools: Develop tools to analyze collected metrics and identify
performance bottlenecks.
Code to Implement:
#include <iostream>
#include <vector>
#include <climits>
#define PAGE_SIZE 4
#define NUM_PAGES 256
#define PHYSICAL_FRAMES 64
struct PageTableEntry {
int page_number;
bool in_memory;
int frame_number;
int last_access_time;
PageTableEntry() : page_number(-1), in_memory(false), frame_number(-1),
last_access_time(-1) {}
};
class VM {
public:
int vm_id;
std::vector<PageTableEntry> page_table;
VM(int id) : vm_id(id), page_table(NUM_PAGES) {
for (int i = 0; i < NUM_PAGES; ++i) {
page_table[i].page_number = i;
}
}
};
class MemoryManager {
public:
std::vector<VM> vms;
int current_time;
int page_faults;
MemoryManager() : current_time(0), page_faults(0) {}
VM* create_vm(int vm_id) {
vms.emplace_back(vm_id);
return &vms.back();
}
int select_page_to_replace(const std::vector<PageTableEntry>& page_table) {
int lru_page = -1;
int min_access_time = INT_MAX;
for (const auto& entry : page_table) {
if (entry.in_memory && entry.last_access_time < min_access_time) {
min_access_time = entry.last_access_time;
lru_page = entry.page_number;
}
}
return lru_page;
}
void handle_page_fault(VM* vm, int page_number) {
std::cout << "Handling page fault for page " << page_number << "\n";
page_faults++;
int frame_number = -1;
for (int i = 0; i < NUM_PAGES; ++i) {
if (!vm->page_table[i].in_memory) {
frame_number = i;
break;
}
}
if (frame_number == -1) {
int lru_page = select_page_to_replace(vm->page_table);
frame_number = vm->page_table[lru_page].frame_number;
vm->page_table[lru_page].in_memory = false;
vm->page_table[lru_page].frame_number = -1;
}
// Simulate fetching the page from disk
vm->page_table[page_number].in_memory = true;
vm->page_table[page_number].frame_number = frame_number;
vm->page_table[page_number].last_access_time = current_time;
std::cout << "Page " << page_number << " loaded into frame " <<
frame_number << "\n";
}
void access_page(VM* vm, int page_number) {
current_time++;
if (vm->page_table[page_number].in_memory) {
std::cout << "Page " << page_number << " is in memory at frame " <<
vm->page_table[page_number].frame_number << "\n";
vm->page_table[page_number].last_access_time = current_time;
} else {
std::cout << "Page " << page_number << " is not in memory, triggering
page fault...\n";
handle_page_fault(vm, page_number);
std::cout << "Page " << page_number << " is now in memory at frame "
<< vm->page_table[page_number].frame_number << "\n";
}
}
void print_performance_metrics() const {
std::cout << "Current Time: " << current_time << "\n";
std::cout << "Page Faults: " << page_faults << "\n";
}
};
int main() {
MemoryManager manager;
VM* vm = manager.create_vm(1);
manager.access_page(vm, 10);
manager.access_page(vm, 20);
manager.access_page(vm, 10);
manager.print_performance_metrics();
return 0;
}
Output of the Code:
