mmu.cpp

/*
    Operating Systems Fall 2013, Lab 3. 10 November 2013
    Lior Galanti lior.galanti@nyu.edu N14314920
*/

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdint.h>

#include <fstream>
#include <iostream>
#include <sstream> 
#include <string>
#include <list>

// Header 
using namespace std;

enum PageReplacementAlgorithm {
    NRU = 0,
    LRU = 1,
    RANDOM = 2,
    FIFO = 3,
    SECOND_CHANCE = 4,
    CLOCK = 5,
    AGING = 6
};
enum ReplacementTarget {
    PHYSICAL = 0,
    VIRTUAL = 1
};
class PageTableEntry {
public:
    uint32_t present:1;
    uint32_t modified:1;
    uint32_t referenced:1;
    uint32_t pagedout:1;
    uint32_t physical:6;
    uint32_t logical:6;
    
    PageTableEntry(uint32_t logical){
        present = 0;
        modified = 0;
        referenced = 0;
        pagedout = 0;
        physical = 0;
        
        // we keep the logical address here for convinence but it can be inferred from the array index
        // in our case it won't make the record bigger anyway
        this->logical = logical;
    }
    void PrintPageStatus(){
        if(!present){
            if(pagedout)
                printf("# ");
            else
                printf("* ");
        } else {
            printf("%d:%c%c%c ", logical, referenced?'R':'-', modified?'M':'-', pagedout?'S':'-');
        }
    }
};
class Options {
public:
    enum PageReplacementAlgorithm policy;
    enum ReplacementTarget target;
    bool O;
    bool P;
    bool F;
    bool S;
    bool p;
    bool f;
    char* inputFilePath;
    char* randFilePath;
    uint32_t numberOfFrames;
    uint32_t numberOfPages;
    
    Options(){
        policy = LRU;           // Default policy is LRU
        target = PHYSICAL;      // Default target is PHYSICAL
        O = false;
        P = false;
        F = false;
        S = false;
        p = false;
        f = false;
        inputFilePath = NULL;
        randFilePath = NULL;
        numberOfPages = 64;     // Virtual memory space is 64 pages
        numberOfFrames = 32;    // Default number of physical frames is 32
    }
};
class Instruction {
public:
    uint32_t index;
    uint32_t type;
    uint32_t logical;
    
    Instruction(){
        index = 0;
        type = 0;
        logical = 0;
    }
};
class SummaryStatistics{
public:
    uint64_t instruction;
    uint64_t unmap;
    uint64_t map;
    uint64_t pageIn;
    uint64_t pageOut;
    uint64_t zero;
    uint64_t totalCost;
    
    SummaryStatistics(){
        instruction = 0;
        unmap = 0;
        map = 0;
        pageIn = 0;
        pageOut = 0;
        zero = 0;
        totalCost = 0;
    }
    void UnMapOperation(){
        unmap++;
        totalCost += 400;
    }
    void MapOperation(){
        map++;
        totalCost += 400;
    }
    void PageInOperation(){
        pageIn++;
        totalCost += 3000;
    }
    void PageOutOperation(){
        pageOut++;
        totalCost += 3000;
    }
    void ZeroOperation(){
        zero++;
        totalCost += 150;
    }
    void IoOperation(){
        instruction += 1;
        totalCost += 1;
    }
    int PrintSummary(){
        printf("SUM %llu U=%llu M=%llu I=%llu O=%llu Z=%llu ===> %llu\n",
            instruction,
            unmap,
            map,
            pageIn,
            pageOut,
            zero,
            totalCost
        );
        return 1;
    }
};
class MemoryManager {
public:
    bool valid;
    SummaryStatistics statistics;
    PageTableEntry** pageTable;
    PageTableEntry** frameTable;
    uint32_t* randomSet;
    uint32_t totalRandom;
    uint32_t randomOffset;
    uint32_t instructionCount;
    uint32_t usedFrames;
    ifstream instructionFile;
    Options* options;
    
    void Run(){
        Open();
        PageTableEntry* pte = NULL;
        Instruction* instruction = NextInstruction();
        while(instruction != NULL) {
            options->O && printf("==> inst: %d %d\n", instruction->type, instruction->logical);
            pte = pageTable[instruction->logical];
             
            // if the page is not present in physical memory we need to first page it in
            if(!pte->present){
                if(HasFreeMemory()){
                    PageIn(instruction->index, AllocateFreeMemory(), instruction->logical);
                } else {
                    ReplacePage(instruction->index, instruction->logical);
                }
            }
            Access(instruction->index, pte->physical);
            
            
            // flip the referenced bit since we accessed the page
            pte->referenced = 1;
            
            if(instruction->type == 1){
                // if the instruction wrote to the page flip the modified bit
                pte->modified = 1;
            }
            
            options->p && PrintPageTable();
            options->f && PrintFrameTable();
            
            // Deallocate the instruction
            delete instruction;
            
            // Fetch the next instruction
            instruction = NextInstruction();
        }
        
        options->P && PrintPageTable();
        options->F && PrintFrameTable();
        options->S && PrintSummaryStatistics();
        Close();
    }
    MemoryManager(Options* options) {
        valid = true;
        pageTable = NULL;
        frameTable = NULL;
        randomSet = NULL;
        totalRandom = 0;
        randomOffset = 0;
        instructionCount = 0;
        usedFrames = 0;
        this->options = options;
        
        // Initialize the Random generator
        LoadRandom();
        
        // Initialize the frame table
        frameTable = (PageTableEntry**)malloc(sizeof(PageTableEntry*) * options->numberOfFrames);
        for(int i=0;i<options->numberOfFrames;i++){
            frameTable[i] = NULL;
        }
        
        // Initialize the page table
        pageTable = (PageTableEntry**)malloc(sizeof(PageTableEntry*) * options->numberOfPages);
        for(int i=0;i<options->numberOfPages;i++){
            pageTable[i] = new PageTableEntry(i);
        }
    }
    ~MemoryManager(){
        destroyBase();
    };
protected:
    virtual void Access(uint32_t instructionIndex, uint32_t physical){
        statistics.IoOperation();
    }
    virtual void PageOut(uint32_t instructionIndex, uint32_t physical){
        // If the frame table is null at the given index it means the frame is not in use so nothing to do.
        if(frameTable[physical] != NULL){
            PageTableEntry* pte = frameTable[physical];
            
            // unmap the virtual page to avoid further access
            options->O && printf("%d: UNMAP  %2d  %2d\n", instructionIndex, pte->logical, pte->physical);
            statistics.UnMapOperation();
            
            // if the page was dirty page the page out to a swap device
            if(pte->modified){
                pte->pagedout = 1;
                pte->modified = 0;
                options->O && printf("%d: OUT    %2d  %2d\n", instructionIndex, pte->logical, pte->physical);
                statistics.PageOutOperation();
            }
            // flip the present bit to indicate the page is not in physical memory
            pte->present = 0;
            frameTable[physical] = NULL;
        } else {
            fprintf (stderr, "ERROR: attempted to page out an empty frame.\n");
        }
    }
    virtual void PageIn(uint32_t instructionIndex, uint32_t physical, uint32_t logical){
        if(frameTable[physical] == NULL){
            PageTableEntry* pte = pageTable[logical];
            
            // set the physical address
            pte->physical = physical;
            
            if(pte->pagedout){
                // if the page has been paged out, page in the virtual page into the physical frame
                options->O && printf("%d: IN     %2d  %2d\n", instructionIndex, pte->logical, pte->physical);
                statistics.PageInOperation();
            } else {
                // else zero the frame
                options->O && printf("%d: ZERO       %2d\n", instructionIndex, pte->physical);
                statistics.ZeroOperation();
            }
            
            // map the virtual page to the physical frame
            options->O && printf("%d: MAP    %2d  %2d\n", instructionIndex, pte->logical, pte->physical);
            statistics.MapOperation();
            
            // flip the present bit to indicate the page is now in physical memory
            pte->present = 1;
            
            // update the pointer on the frame table
            frameTable[physical] = pte;
        } else {
            fprintf (stderr, "ERROR: attempted to page into a used frame.\n");
        }
    }
    virtual void ReplacePage(uint32_t instructionIndex, uint32_t logical){}
    virtual int PrintPageTable(){
        for(int i=0;i<options->numberOfPages;i++){
            pageTable[i]->PrintPageStatus();
        }
        printf("\n");
        return 1;
    }
    virtual int PrintFrameTable(){
        for(int i=0;i<options->numberOfFrames;i++){
            if(frameTable[i] == NULL)
                printf("* ");
            else
                printf("%d ", frameTable[i]->logical);
        }
        printf("\n");
        return 1;
    }
    virtual int PrintSummaryStatistics(){
        return statistics.PrintSummary();
    }
    uint32_t NextRandom(uint32_t range){
        uint32_t random = randomSet[randomOffset] % range;
        randomOffset = (randomOffset + 1) % totalRandom;
        return random;
    }
    void destroyBase(){
        if (randomSet != NULL) {
            free(randomSet); 
        }
        
        if(frameTable != NULL){
            free(frameTable);
        }
        
        if(pageTable != NULL) {
            for(int i=0;i<options->numberOfPages;i++){
                if(pageTable[i] != NULL){
                    delete pageTable[i];
                }
            }
            free(pageTable);
        }
        free(options);
    }
private:
    void Open(){
        if (valid && options->inputFilePath != NULL) {
            instructionFile.open(options->inputFilePath);
            if (!instructionFile.is_open()) {
                cerr << "Error opening instruction file\n";
                valid = 0;
            }
        }
    }
    void Close(){
        if (valid && instructionFile.is_open()) {
            instructionFile.close();
        }
    }
    void LoadRandom(){
        if (options->randFilePath != NULL) {
            int length, value, index;
            string line;
            ifstream randomFile(options->randFilePath);
            if (randomFile) {
                // Get the size of the array
                getline(randomFile, line);
                istringstream iss(line);
                if (iss >> totalRandom) {
                    // allocate an array for random numbers
                    randomSet = (uint32_t*)malloc(sizeof(uint32_t) * totalRandom);
                    
                    index = 0;
                    while (getline( randomFile, line )) {
                        istringstream iss(line);
                        iss >> value;
                        randomSet[index] = value;
                        index++;
                    }
                } else {
                    cerr << "Input file format error\n";
                }
                randomFile.close();
            } else {
                cerr << "Error opening random file\n";
                valid = 0;
            }
        }
    };
    Instruction* NextInstruction(){
        Instruction* instruction = NULL;
        string line;
        while(getline(instructionFile, line)){
            if(line.at(0) != '#'){
                instruction = new Instruction();
                istringstream iss(line);
                instruction->index = instructionCount;
                iss >> instruction->type >> instruction->logical;
                instructionCount++;
                break;
            }
        }
        return instruction;
    };
    uint32_t AllocateFreeMemory(){
        return usedFrames++;
    }
    bool HasFreeMemory(){
        return usedFrames < options->numberOfFrames ? true : false;
    }
};
class NRUMemoryManager: public MemoryManager {
public:
    uint32_t pageReplacementCount;
    PageTableEntry** priorityClass[4];
    uint32_t priorityCount[4];
    
    NRUMemoryManager(Options* options):MemoryManager(options){
        pageReplacementCount = 0;
        for(int i=0;i<4;i++){
            priorityClass[i] = (PageTableEntry**)malloc(sizeof(PageTableEntry*) * options->numberOfFrames);
            priorityCount[i] = 0;
        }
    };
    ~NRUMemoryManager(){
        destroyBase();
        for(int i=0;i<4;i++){ free(priorityClass[i]); }
    }
    void ReplacePage(uint32_t instructionIndex, uint32_t logical){
        // Choose the page to be replaced
        uint32_t physical = PickPageToEvict();
        ResetReferencedFlag();
        PageOut(instructionIndex, physical);
        PageIn(instructionIndex, physical, logical);
    }
    void ResetReferencedFlag(){
        pageReplacementCount++;
        if(pageReplacementCount == 10){
            for(int i=0;i<options->numberOfPages;i++){
                if(pageTable[i]->present){
                    pageTable[i]->referenced = 0;
                }
            }
            pageReplacementCount = 0;
        }
    }
    uint32_t PickPageToEvict(){
        /*
            NRU Classes
            
            idx R   M
            0   0   0
            1   0   1 
            2   1   0
            3   1   1
        */
        
        PageTableEntry** table;
        uint32_t count, i, random, result;
        
        if(options->target == PHYSICAL){
            table = frameTable;
            count = options->numberOfFrames;
        } else if(options->target == VIRTUAL){
            table = pageTable;
            count = options->numberOfPages;
        }
        for(i=0;i<4;i++){
            priorityCount[i] = 0;
        }
        for(i=0;i<count;i++){
            PageTableEntry*  pte = table[i];
            if(pte->present){
                if(pte->referenced){
                    if(pte->modified){
                        priorityClass[3][priorityCount[3]] = pte; // 11
                        priorityCount[3]++;
                    } else {
                        priorityClass[2][priorityCount[2]] = pte; // 10
                        priorityCount[2]++;
                    }
                } else {
                    if(pte->modified){
                        priorityClass[1][priorityCount[1]] = pte; // 01
                        priorityCount[1]++;
                    } else {
                        priorityClass[0][priorityCount[0]] = pte; // 00
                        priorityCount[0]++;
                    }
                }
            }
        }
        for(i=0;i<4;i++){
            if(priorityCount[i] > 0){
                random = NextRandom(priorityCount[i]);
                result = priorityClass[i][random]->physical;
                break;
            }
        }
        return result;
    }
};
class RandomMemoryManager: public MemoryManager {
public:
    PageTableEntry** present;
    
    RandomMemoryManager(Options* options):MemoryManager(options){
        present = (PageTableEntry**)malloc(sizeof(PageTableEntry*) * options->numberOfFrames);
    };
    ~RandomMemoryManager(){
        destroyBase();
        free(present);
    }
    void ReplacePage(uint32_t instructionIndex, uint32_t logical){
        uint32_t physical = PickPageToEvict();
        PageOut(instructionIndex, physical);
        PageIn(instructionIndex, physical, logical);
    }
    uint32_t PickPageToEvict(){
        uint32_t count, i, random, result;
        count = 0;
        
        for(i=0;i<options->numberOfFrames;i++){
            if(frameTable[i]->present){
                present[count] = frameTable[i];
                count++;
            }
        }
        random = NextRandom(count);
        return present[random]->physical;
    }
};
class FIFOMemoryManager: public MemoryManager {
public:
    list<PageTableEntry*> queue;
    
    FIFOMemoryManager(Options* options):MemoryManager(options){};
    void PageOut(uint32_t instructionIndex, uint32_t physical){
        MemoryManager::PageOut(instructionIndex, physical);
        queue.pop_front();
    }
    void PageIn(uint32_t instructionIndex, uint32_t physical, uint32_t logical){
        MemoryManager::PageIn(instructionIndex, physical, logical);
        queue.push_back(pageTable[logical]);
    }
    void ReplacePage(uint32_t instructionIndex, uint32_t logical){
        PageTableEntry* evict = queue.front();
        PageOut(instructionIndex, evict->physical);
        PageIn(instructionIndex, evict->physical, logical);
    }
};
class SecondChanceMemoryManager: public FIFOMemoryManager {
public:
    SecondChanceMemoryManager(Options* options):FIFOMemoryManager(options){};
    void ReplacePage(uint32_t instructionIndex, uint32_t logical){
        PageTableEntry* evict;
        while(true){
            evict = queue.front();
            if(evict->referenced){
                evict->referenced = 0;
                queue.pop_front();
                queue.push_back(evict);
            } else {
                break;
            }
        }
        PageOut(instructionIndex, evict->physical);
        PageIn(instructionIndex, evict->physical, logical);
    }
};
class LRUMemoryManager: public MemoryManager {
public:
    list<PageTableEntry*> order;
    
    LRUMemoryManager(Options* options):MemoryManager(options){};
    void Access(uint32_t instructionIndex, uint32_t physical){
        MemoryManager::Access(instructionIndex, physical);
        // move to the top of the order list
        PageTableEntry* accessed = NULL;
        for(list<PageTableEntry*>::iterator pte = order.begin();pte != order.end(); pte++) {
            if ((*pte)->physical == physical) {
                accessed = *pte;
                order.erase(pte);
                break;
            }
        }
        
        if (accessed != NULL){
            order.push_front(accessed);
        }
    }
    void PageOut(uint32_t instructionIndex, uint32_t physical){
        MemoryManager::PageOut(instructionIndex, physical);
        // remove from the order list
        order.pop_back();
    }
    void PageIn(uint32_t instructionIndex, uint32_t physical, uint32_t logical){
        MemoryManager::PageIn(instructionIndex, physical, logical);
        // add to the order list at the top
        order.push_front(pageTable[logical]);
    }
    void ReplacePage(uint32_t instructionIndex, uint32_t logical){
        // evict the one on the bottom of the list
        PageTableEntry* evict = order.back();
        PageOut(instructionIndex, evict->physical);
        PageIn(instructionIndex, evict->physical, logical);
    }
};
class AgingMemoryManager: public MemoryManager {
public:
    uint32_t* age;
    
    AgingMemoryManager(Options* options):MemoryManager(options){
        int count;
        if(options->target == PHYSICAL){
            count = options->numberOfFrames;
        } else if(options->target == VIRTUAL){
            count = options->numberOfPages;
        }
        age = (uint32_t*)malloc(sizeof(uint32_t) * count);
        for(int i=0;i<count;i++){
            age[i] = 0;
        }
    };
    ~AgingMemoryManager(){
        destroyBase();
        free(age);
    }
    void PageOut(uint32_t instructionIndex, uint32_t physical){
        // When we page out we reset the age
        if(options->target == PHYSICAL){
            age[physical] = 0;
        } else if(options->target == VIRTUAL){
            PageTableEntry* pte = frameTable[physical];
            age[pte->logical] = 0;
        }
        MemoryManager::PageOut(instructionIndex, physical);
    }
    void ReplacePage(uint32_t instructionIndex, uint32_t logical){
        uint32_t smallest = 0xffffffff;
        PageTableEntry* evict = NULL;
        PageTableEntry** table = NULL;
        int i, count;
        
        if(options->target == PHYSICAL){
            count = options->numberOfFrames;
            table = frameTable;
        } else if(options->target == VIRTUAL){
            count = options->numberOfPages;
            table = pageTable;
        }
        for(i=0;i<count;i++){
            if(table[i] != NULL && table[i]->present) {
                age[i] = age[i] >> 1;
                if(table[i]->referenced){
                    age[i] = age[i] + 0x80000000;
                    table[i]->referenced = 0;
                }
            }
        }
        for(i=0;i<count;i++){
            if(table[i] != NULL && table[i]->present) {
                if(age[i] < smallest){
                    smallest = age[i];
                    evict = table[i];
                }
            }
        }
        PageOut(instructionIndex, evict->physical);
        PageIn(instructionIndex, evict->physical, logical);
    }
};
class ClockMemoryManager: public MemoryManager {
public:
    uint32_t hand;
    
    ClockMemoryManager(Options* options):MemoryManager(options){
        hand = 0;
    };
    void ReplacePage(uint32_t instructionIndex, uint32_t logical){
        PageTableEntry* evict;
        PageTableEntry** table;
        int count;
        if(options->target == PHYSICAL){
            table = frameTable;
            count = options->numberOfFrames;
        } else if(options->target == VIRTUAL){
            table = pageTable;
            count = options->numberOfPages;
        }
        
        while(true){
            evict = table[hand];
            if(!evict->present){
                hand = (hand + 1) % count;
            } else if(evict->referenced){
                evict->referenced = 0;
                hand = (hand + 1) % count;
            } else {
                hand = (hand + 1) % count;
                break;
            }
        }
        PageOut(instructionIndex, evict->physical);
        PageIn(instructionIndex, evict->physical, logical);
    }
};

// Command Line
Options* ParseCommandLine(int argc, char **argv) {
    opterr = 0;
    int index, c;
    Options* options = new Options();
    while ((c = getopt (argc, argv, "a:o:f:")) != -1) {
        switch (c) {
            case 'a':
                if (strcmp(optarg, "N") == 0) {
                    options->policy = NRU;
                    options->target = VIRTUAL;
                } else if (strcmp(optarg, "C") == 0) {
                    options->policy = CLOCK;
                    options->target = VIRTUAL;
                } else if (strcmp(optarg, "A") == 0) {
                    options->policy = AGING;
                    options->target = VIRTUAL;
                } else if (strcmp(optarg, "l") == 0) {
                    options->policy = LRU;
                    options->target = PHYSICAL;
                } else if (strcmp(optarg, "r") == 0) {
                    options->policy = RANDOM;
                    options->target = PHYSICAL;
                } else if (strcmp(optarg, "f") == 0) {
                    options->policy = FIFO;
                    options->target = PHYSICAL;
                } else if (strcmp(optarg, "s") == 0) {
                    options->policy = SECOND_CHANCE;
                    options->target = PHYSICAL;
                } else if (strcmp(optarg, "c") == 0) {
                    options->policy = CLOCK;
                    options->target = PHYSICAL;
                } else if (strcmp(optarg, "a") == 0) {
                    options->policy = AGING;
                    options->target = PHYSICAL;
                }
                break;
                
            case 'o':
                for(char* i = optarg; *i; ++i) {
                    if(*i == 'O') {
                        options->O = true;
                    } else if (*i == 'P') {
                        options->P = true;
                    } else if (*i == 'F') {
                        options->F = true;
                    } else if (*i == 'S') {
                        options->S = true;
                    } else if (*i == 'p') {
                        options->p = true;
                    } else if (*i == 'f') {
                        options->f = true;
                    }
                }
                break;
                
            case 'f':
                options->numberOfFrames = atoi(optarg);
                break;
                
            case '?':
                if (optopt == 'a' || optopt == 'o' || optopt == 'f')
                    fprintf (stderr, "Option -%c requires an argument.\n", optopt);
                else if (isprint (optopt))
                    fprintf (stderr, "Unknown option `-%c'.\n", optopt);
                else
                    fprintf (stderr, "Unknown option character `\\x%x'.\n", optopt);
            default: abort ();
        }
    }
    
    if ((argc - optind) == 2) {
        options->inputFilePath = argv[optind];
        options->randFilePath = argv[optind+1];
    } else {
        fprintf (stderr, "mmu expects 2 positional arguments.\n");
    }
    return options;
}

// Main
int main (int argc, char **argv) {
    Options* options = ParseCommandLine(argc, argv);
    //options->PrintSummary();
    MemoryManager* mmu;
    if(options->policy == NRU){
        mmu = new NRUMemoryManager(options);
        
    } else if(options->policy == RANDOM){
        mmu = new RandomMemoryManager(options);
        
    } else if(options->policy == FIFO){
        mmu = new FIFOMemoryManager(options);
        
    } else if(options->policy == SECOND_CHANCE){
        mmu = new SecondChanceMemoryManager(options);
        
    } else if(options->policy == CLOCK){
        mmu = new ClockMemoryManager(options);
        
    } else if(options->policy == LRU){
        mmu = new LRUMemoryManager(options);
        
    } else if(options->policy == AGING){
        mmu = new AgingMemoryManager(options);
    }
    
    mmu->Run();
    
    delete mmu;
}