page-replacement/pageReplacementAlgorithm.cpp at main · WilliamSilveiraF/page-replacement · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "pageReplacementAlgorithm.h"

PageReplacementAlgorithm::PageReplacementAlgorithm(size_t cap) : physicalMemory(cap) {}

FIFO::FIFO(size_t cap) : PageReplacementAlgorithm(cap) {}

int FIFO::getPageFaults(int pages[], int totalPages) {
    int page_faults = 0;
    for (int i = 0; i < totalPages; i++) {
        if (!physicalMemory.contains(pages[i])) {
            if (physicalMemory.isFull()) {
                int oldestPage = pagesQueue.dequeue();
                physicalMemory.removePage(oldestPage);
            }
            physicalMemory.addPage(pages[i]);
            pagesQueue.enqueue(pages[i]);
            page_faults++;
        }
    }
    return page_faults;
}

OPT::OPT(size_t cap) : PageReplacementAlgorithm(cap) {}

int OPT::predict(int pages[], int totalPages, int currentIndex) {
    int frameToReplace = -1;
    int latestUsageIndex = currentIndex;

    for (int page : physicalMemory.getPages()) {
        int j;
        for (j = currentIndex; j < totalPages; j++) {
            if (page == pages[j]) {
                if (j > latestUsageIndex) {
                    latestUsageIndex = j;
                    frameToReplace = page;
                }
                break;
            }
        }

        if (j == totalPages) return page;
    }

    return (frameToReplace == -1) ? *physicalMemory.getPages().begin() : frameToReplace;
}

int OPT::getPageFaults(int pages[], int totalPages) {
    int page_faults = 0;

    for (int i = 0; i < totalPages; i++) {
        if(physicalMemory.contains(pages[i])) {
            continue;
        }
        if (!physicalMemory.isFull()) {
            physicalMemory.addPage(pages[i]);
        } else {
            int pageToRemove = predict(pages, totalPages, i + 1);
            physicalMemory.removePage(pageToRemove);
            physicalMemory.addPage(pages[i]);
        }
        page_faults++;
    }
    return page_faults;
}

LRU::LRU(int cap) : PageReplacementAlgorithm(cap), time(0) {}

int LRU::getPageFaults(int pages[], int totalPages) {
    int page_faults = 0;
    for (int i = 0; i < totalPages; i++) {
        time++;
        if (!physicalMemory.contains(pages[i])) {
            if (physicalMemory.isFull()) {
                int lru_page = INT_MAX, oldest_time = INT_MAX;
                for (const auto& pair : timestamps) {
                    if (pair.second < oldest_time) {
                        oldest_time = pair.second;
                        lru_page = pair.first;
                    }
                }
                physicalMemory.removePage(lru_page);
                timestamps.erase(lru_page);
            }
            physicalMemory.addPage(pages[i]);
            page_faults++;
        }
        timestamps[pages[i]] = time;
    }
    return page_faults;
}