cos331-hw4/COS331-HW4-PEASE/hw4.c

// HW4
// Nicholas Pease
#include <stdio.h>
#include <stdlib.h>

// Defines
#define PAGE_SIZE 256
#define PHYSICAL_PAGE_COUNT 64
#define LOGICAL_PAGE_COUNT 256

// Structs and Enums
typedef enum
{
    false,
    true
} bool;

struct MemoryAddress
{
    unsigned short int address;
    unsigned int pageNumber;
    unsigned int offset;
    unsigned int runNumber; // Run Number
};

struct PageTableEntry
{
    int pageNumber; // Physical Page Number
    bool valid;     // Valid bit defaults to false (page not loaded)
};

// Globals
int numPageFaults = 0;
struct PageTableEntry RAMTracker[PHYSICAL_PAGE_COUNT];                                // Physical RAM Tracker
struct PageTableEntry LogicalRAMTracker[LOGICAL_PAGE_COUNT];                          // Logical RAM Tracker
unsigned char RAM[PHYSICAL_PAGE_COUNT][PAGE_SIZE] = {[0 ... 63] = {[0 ... 255] = 0}}; // RAM initialized to 0s
unsigned short int addresses[512];                                                    // Randomly generated logical addresses
int leastRecentlyUsedCalculation[PHYSICAL_PAGE_COUNT] = {[0 ... 63] = 0};             // LRU calculation array

// Methods for VirtualMemory

// Generates a MemoryAddress datatype from the current address, as well as calculates page and offset
struct MemoryAddress generateAddress(unsigned short int logicalAddress, unsigned int runNumber)
{
    unsigned short int offsetbitMask = 0b0000000011111111;
    struct MemoryAddress generatedAddress;
    // 16 bits for address ( 8 page, 8 offset)
    generatedAddress.address = logicalAddress;                // Set the logical address
    generatedAddress.pageNumber = logicalAddress >> 8;        // Moves 8 to the right (leaving page)
    generatedAddress.offset = logicalAddress & offsetbitMask; // Applies the bitmask to get the offset
    generatedAddress.runNumber = runNumber;                   // Set the run number

    return generatedAddress;
}

// Least Recently Used (LRU) Algorithm
int LRU()
{
    // Find the least recently used page

    // Start at 0 and work down
    int oldestPage = 0;                                    // Initialize the oldest page to 0
    int oldestRunNumber = leastRecentlyUsedCalculation[0]; // Initialize the oldest run number
    for (int i = 1; i < PHYSICAL_PAGE_COUNT; i++)
    {
        if (leastRecentlyUsedCalculation[i] < oldestRunNumber)
        {
            oldestPage = i;                                    // Update the oldest page
            oldestRunNumber = leastRecentlyUsedCalculation[i]; // Update the oldest run number
        }
    }
    printf("Victim Physical Page is %d\n", oldestPage);
    printf("LP %d is currently mapped to victim page frame\n", RAMTracker[oldestPage].pageNumber);
    // Update logical RAM tracker
    LogicalRAMTracker[RAMTracker[oldestPage].pageNumber].valid = false; // Set the logical page as valid
    LogicalRAMTracker[RAMTracker[oldestPage].pageNumber].pageNumber = 0;
    return oldestPage; // Return the page number of the least recently used page
}

// Loads a DiskPage into RAM via its logical page number
// If there is no free page, it will use the LRU algorithm to find a victim page
void loadIntoRAM(unsigned int logicalPageNumber)
{
    // Determine if there is a free page in RAM
    int physicalPageNumber = -1;
    for (int i = 0; i < PHYSICAL_PAGE_COUNT; i++)
    {
        if (RAMTracker[i].valid == false)
        {
            physicalPageNumber = i; // Found a free page
            printf("Found Free Frame %d in memory\n", physicalPageNumber);
            break;
        }
    }

    // If no free page, find "victim" page using LRU algorithm
    if (physicalPageNumber == -1)
    {
        printf("No Free Page Frame. Invoking LRU Page Replacement Algorithm\n");
        physicalPageNumber = LRU();
    }

    // Load from file into RAM using the free page number
    FILE *fp = fopen("Back.bin", "rb"); // Open file for reading
    unsigned char buf[PAGE_SIZE];
    fseek(fp, logicalPageNumber * PAGE_SIZE, SEEK_SET); // Move to target page
    fread(buf, PAGE_SIZE, 1, fp);                       // Pull out page from the file
    fclose(fp);                                         // Close file

    // Update RAM
    for (int i = 0; i < PAGE_SIZE; i++)
    {
        RAM[physicalPageNumber][i] = buf[i]; // Load the page into RAM
    }

    RAMTracker[physicalPageNumber].valid = true; // Set the page as valid
    RAMTracker[physicalPageNumber].pageNumber = logicalPageNumber;
    LogicalRAMTracker[logicalPageNumber].valid = true; // Set the logical page as valid
    LogicalRAMTracker[logicalPageNumber].pageNumber = physicalPageNumber;

    printf("Logical Page %d Now Mapped to Physical Page %d\n", logicalPageNumber, physicalPageNumber);
}

// Outermost method to initiate reading from a specific logical address
// Takes a MemoryAddress struct as input
void readFromAddress(struct MemoryAddress logicalAddress)
{
    // Check if page is already loaded into RAM
    if (LogicalRAMTracker[logicalAddress.pageNumber].valid != true)
    {
        // Page is not loaded into RAM, so we need to calculate and load it
        numPageFaults++;
        printf("Page Not Mapped. Page Fault Number %d.\n", numPageFaults);
        loadIntoRAM(logicalAddress.pageNumber); // Load the page into RAM
    }
    else
    {
        printf("Logical Page %d is in memory and mapped to Physical Page %d\n", logicalAddress.pageNumber, LogicalRAMTracker[logicalAddress.pageNumber].pageNumber);
    }

    int physicalPageNumber = LogicalRAMTracker[logicalAddress.pageNumber].pageNumber; // Get the physical page number

    // Add to LRU list
    leastRecentlyUsedCalculation[physicalPageNumber] = logicalAddress.runNumber; // Update the LRU calculation with the current run number

    // Page confirmed to be in RAM, so we can read from it
    printf("Final address is Physical Page: %d Offset: %d\n", physicalPageNumber, logicalAddress.offset); // Print the final address
    unsigned char data = RAM[physicalPageNumber][logicalAddress.offset];                                  // Read the data from RAM
    printf("The value at that address: %d\n", data);                                                      // Print the data
}

// Final outputs as per homework guidelines
// Also outputs as table
void finalOutput()
{
    printf("Final Output:\n\n");
    printf("%d Total Page Faults\n\n", numPageFaults);

    for (int i = 0; i < LOGICAL_PAGE_COUNT; i++)
    {
        if (LogicalRAMTracker[i].valid)
        {
            printf("Logical Page %d Mapped to Physical Page %d\n", i, LogicalRAMTracker[i].pageNumber);
        }
        else
        {
            printf("Logical Page %d Not Mapped\n", i);
        }
    }

    printf("\n\n");
    printf("Logical Page Mappings:\n");
    printf("Address = Row * 16 + Column (in Hex)\n");
    printf("I.E: F (15) * 16 + F (15) = 255\n\n");
    for (int col = 0; col < 16; col++)
        printf("\t%X", col);
    printf("\n");
    for (int row = 0; row < 16; row++)
    {
        printf("%X \t", row);
        for (int col = 0; col < 16; col++)
        {
            int index = row * 16 + col;
            if (LogicalRAMTracker[index].valid)
            {
                printf("%d \t", LogicalRAMTracker[index].pageNumber);
            }
            else
            {
                printf("   \t"); // blank for not mapped
            }
        }
        printf("\n");
    }
}

main(int argc, char *argv[])
{
    srand(9); // all get same addresses
    for (int i = 0; i < 512; i++)
        addresses[i] = rand() % 65535; // Logical Address Generation

    // Generate File Contents
    unsigned char buf[PAGE_SIZE];       // Contents of a page
    FILE *fp = fopen("Back.bin", "wb"); // Open file for writing
    for (int i = 0; i < 256; i++)
        buf[i] = (unsigned char)i; // Fill with 0-255
    for (int i = 0; i < PAGE_SIZE; i++)
        fwrite(buf, PAGE_SIZE, 1, fp); // Write 255 pages
    fclose(fp);                        // Close file

    for (int i = 0; i < 512; i++)
    {
        struct MemoryAddress logicalAddress = generateAddress(addresses[i], i);                   // Generate the address via the struct
        printf("Reference %d. Logical Address %d\n", i, logicalAddress.address);                  // Print the logical address
        printf("Logical Page %d, Offset %d\n", logicalAddress.pageNumber, logicalAddress.offset); // Print the page number and offset
        readFromAddress(logicalAddress);                                                          // Read from the address (and perform memory operations if required))
        printf("\n");
    }

    finalOutput();

    return 0;
}