This is a working project but we made it with the Specifics 2^8 entries in the page table Page size of 2^8 bytes 16 entries in the TLB Frame size of 2^8 bytes 256 frames Physical memory of 65,536 bytes (256 frames x 256-byte frame size), when we need it to be (as said in the pictures/question), 2^7 = 128 entries in the page table Page size of 2^8 bytes 16 entries in the TLB Frame size of 2^8 bytes 128 frames Physical memory of 32,768 bytes (128 frames x 256-byte frame size) Virtual memory of 65,536 bytes = twice the size of physical memory, and we didnt know how to (Specific for the Three-Students-Project: The size of the physical memory is smaller than the size of the virtual address space ---65,536 bytes--- so you need to be concerned about page replacements during a page fault. Since there are only 128 page frames rather than 256, you are therefore required to keep track of free page frames as well as implementing a page-replacement policy using either FIFO or LRU)

#include #include #include #include #include #include #include

#define TLB_SIZE 16 #define PAGES 256 #define PAGE_MASK 255

#define PAGE_SIZE 256 #define OFFSET_BITS 8 #define OFFSET_MASK 255

#define MEMORY_SIZE PAGES * PAGE_SIZE

// Max number of characters per line of input file to read. #define BUFFER_SIZE 10

struct tlbentry { unsigned char logical; unsigned char physical; };

// TLB is kept track of as a circular array, with the oldest element being overwritten once the TLB is full. struct tlbentry tlb[TLB_SIZE]; // number of inserts into TLB that have been completed. Use as tlbindex % TLB_SIZE for the index of the next TLB line to use. int tlbindex = 0;

// pagetable[logical_page] is the physical page number for logical page. Value is -1 if that logical page isn't yet in the table. int pagetable[PAGES];

signed char main_memory[MEMORY_SIZE];

// Pointer to memory mapped backing file signed char *backing;

int max(int a, int b) { if (a > b) return a; return b; }

/* Returns the physical address from TLB or -1 if not present. */ int search_tlb(unsigned char logical_page) { int i; for(i=max((tlbindex - TLB_SIZE),0); i

if (entry -> logical == logical_page){ return entry -> physical; } } return -1; }

/* Adds the specified mapping to the TLB, replacing the oldest mapping (FIFO replacement). */ void add_to_tlb(unsigned char logical, unsigned char physical) { struct tlbentry *entry = &tlb[tlbindex % TLB_SIZE];

tlbindex++; entry->logical = logical; entry->physical = physical; }

int main(int argc, const char *argv[]) { if (argc != 3) { fprintf(stderr, "Usage ./virtmem backingstore input "); exit(1); }

const char *backing_filename = argv[1]; int backing_fd = open(backing_filename, O_RDONLY); backing = mmap(0, MEMORY_SIZE, PROT_READ, MAP_PRIVATE, backing_fd, 0);

const char *input_filename = argv[2]; FILE *input_fp = fopen(input_filename, "r");

// Fill page table entries with -1 for initially empty table. int i; for (i = 0; i

// Character buffer for reading lines of input file. char buffer[BUFFER_SIZE];

// Data we need to keep track of to compute stats at end. int total_addresses = 0; int tlb_hits = 0; int page_faults = 0;

// Number of the next unallocated physical page in main memory unsigned char free_page = 0;

//Now, read virtual addess one by one, find its page number and offset //Then, check with TLB, if it is a miss, check with page table. If page table entry is -1, it is a page fault, then copy page from backing file into physical memory //Note you need to update page table and tlb correspondingly. while (fgets(buffer, BUFFER_SIZE, input_fp) != NULL) {

total_addresses++; int logical_address = atoi(buffer); int offset = logical_address & OFFSET_MASK; int logical_page = (logical_address >> OFFSET_BITS) & PAGE_MASK; int physical_page = search_tlb(logical_page); //TLB hit

if(physical_page != -1){ tlb_hits++; //TLB miss }else { physical_page = pagetable[logical_page]; // Page fault if(physical_page == -1){ page_faults++; physical_page = free_page; free_page++;

// Copy page from backing file into physical memory memcpy(main_memory + physical_page * PAGE_SIZE, backing + logical_page * PAGE_SIZE, PAGE_SIZE);

pagetable[logical_page] = physical_page; } add_to_tlb(logical_page, physical_page); }

int physical_address = (physical_page

printf("Number of Translated Addresses = %d ", total_addresses); printf("Page Faults = %d ", page_faults); printf("Page Fault Rate = %.3f ", page_faults / (1. * total_addresses)); printf("TLB Hits = %d ", tlb_hits); printf("TLB Hit Rate = %.3f ", tlb_hits / (1. * total_addresses));

return 0; }

Designing a Virtual Memory Manager This project consists of writing a program that translates logical to physical addresses for a virtual address space of 216 65,536 bytes. Your program will read from a file containing logical addresses and, using a TLB as well as a page table, will translate each logical address to its corresponding physical address and output the value of the byte stored at the translated physical address. The goal behind this project is to simulate the steps involved in translating logical to physical addresses. Make sure your program uses fast operations like left/right shift operators. Specifics Your program will read a file containing several 32-bit integer numbers that represent logical addresses. However, you need only be concerned with 16-bit addresses, so you must mask the rightmost 16 bits of each logical address. These 16 bits are divided into (1) an 8-bit page number, and (2) an 8-bit page offset. Hence, the addresses are structured as shown in the figure below offset 31 16 15 8 7 0 Other specifics include the following 27-128 entries in the page table Page size of 2 bytes 16 entries in the TLB Frame size of 28 bytes Physical memory of 32,768 bytes (128 frames x 256-byte frame size) . 128 frames Virtual memory of 65,536 bytes twice the size of physical memory