Designing a Virtual Memory Manager Using C programming

Designing a Virtual Memory Manager
This project consists of writing a program that translates logical to physical
addresses for a virtual address space of size 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.
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) 8-bit page offset.
Hence, the addresses are structured as shown in the Figure below.
Other specifics include the following:
• 28 entries in the page table
• Page size of 28 bytes
• 16 entries in the TLB
• Frame size of 28 bytes
• 256 frames
• Physical memory of 65,536 bytes (256 frames × 256-byte frame size)
Additionally, your program need only be concerned with reading logical
addresses and translating them to their corresponding physical addresses. You
do not need to support writing to the logical address space.
Address Translation
Your program will translate logical to physical addresses using a TLB and page
table . First, the page number is extracted from the
logical address, and the TLB is consulted. In the case of a TLB-hit, the frame
number is obtained from the TLB. In the case of a TLB-miss, the page table
must be consulted. In the latter case, either the frame number is obtained

from the page table or a page fault occurs. A visual representation of the
address-translation process appears in the Figure above.
Handling Page Faults
Your program will implement demand paging. The
backing store is represented by the file BACKING STORE.bin, abinaryfileof size
65,536 bytes.Whena page fault occurs, you will read in a 256-byte page fromthe
file BACKING STORE and store it in an available page frame in physical memory.
For example, if a logical address with page number 15 resulted in a page fault,
your program would read in page 15 from BACKING STORE (remember that
pages begin at 0 and are 256 bytes in size) and store it in a page frame in
physical memory. Once this frame is stored (and the page table and TLB are
updated), subsequent accesses to page 15 will be resolved by either the TLB or
the page table.
You will need to treat BACKING STORE.bin as a random-access file so that
you can randomly seek to certain positions of the file for reading. We suggest
using the standard C library functions for performing I/O, including fopen(),
fread(), fseek(), and fclose().
The size of physical memory is the same as the size of the virtual
address space—65,536 bytes—so you do not need to be concerned about
page replacements during a page fault. Later, we describe a modification to this project using a smaller amount of physical memory; at that point, a page-replacement strategy will be required.

Test File
We provide the file addresses.txt, which contains integer values representing
logical addresses ranging from 0 − 65535 (the size of the virtual address
space). Your program will open this file, read each logical address and translate
it to its corresponding physical address, and output the value of the signed byte
at the physical address.
How to Begin
First, write a simple program that extracts the page number and offset (based
on Figure 9.33) from the following integer numbers:
1, 256, 32768, 32769, 128, 65534, 33153
Perhaps the easiest way to do this is by using the operators for bit-masking
and bit-shifting. Once you can correctly establish the page number and offset
from an integer number, you are ready to begin.
Initially,we suggest that you bypass the TLB and use only a page table. You
can integrate the TLB once your page table is working properly. Remember, address translation can work without a TLB; the TLB just makes it faster. When
you are ready to implement the TLB, recall that it has only 16 entries, so you
will need to use a replacement strategy when you update a full TLB. Youmay
use either a FIFO or an LRU policy for updating your TLB.
How to Run Your Program
Your program should run as follows:
./a.out addresses.txt
Your programwill read in the file addresses.txt,which contains 1,000 logical
addresses ranging from 0 to 65535. Your program is to translate each logical
address to a physical address and determine the contents of the signed byte
stored at the correct physical address. (Recall that in the C language, the char
data type occupies a byte of storage, so we suggest using char values.)
Your program is to output the following values:
1. The logical address being translated (the integer value being read from
addresses.txt).
2. The corresponding physical address (what your program translates the
logical address to).
3. The signed byte value stored at the translated physical address.
We also provide the file correct.txt, which contains the correct output
values for the file addresses.txt. You should use thisfile todetermine if your
program is correctly translating logical to physical addresses.
Statistics
After completion, your program is to report the following statistics:
Bibliographical Notes 461
1. Page-fault rate—The percentage of address references that resulted in
page faults.
2. TLB hit rate—The percentage of address references that were resolved in
the TLB.
Since the logical addresses in addresses.txt were generated randomly
and do not reflect any memory access locality, do not expect to have a high TLB
hit rate.
Modifications
This project assumes that physical memory is the same size as the virtual
address space. In practice, physical memory is typically much smaller than a
virtual address space. A suggested modification is to use a smaller physical
address space. We recommend using 128 page frames rather than 256. This
change will require modifying your program so that it keeps track of free page
frames as well as implementing a page-replacement policy using either FIFO
or LRU .

Download  all files required to run this program

virtmem.c

1 file(s)   4.25 KB

addresses.txt

1 file(s)   5.69 KB

BACKING_STORE.bin

1 file(s)   64.00 KB

correct.txt

1 file(s)   55.02 KB

DS_Store

1 file(s)   6.00 KB

Not a member!
Create a FREE account here to get access and download these files

Answer:

#include <stdio.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <string.h>

#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 < tlbindex; i++) { struct tlbentry *entry = &tlb[i % TLB_SIZE];
        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\n");
        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 < PAGES; i++)
        { pagetable[i] = -1; } 
   // 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;
   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 << OFFSET_BITS) | offset;
        signed char value = main_memory[physical_page * PAGE_SIZE + offset];
        
        printf("Virtual address: %d Physical address: %d Value: %d\n", logical_address, physical_address, value);
    }
    
    printf("Number of Translated Addresses = %d\n", total_addresses);
    printf("Page Faults = %d\n", page_faults);
    printf("Page Fault Rate = %.3f\n", page_faults / (1. * total_addresses));
    printf("TLB Hits = %d\n", tlb_hits);
    printf("TLB Hit Rate = %.3f\n", tlb_hits / (1. * total_addresses));
    
    return 0;
}