Analysis of various page replacement algo

page_replacements_algo.py

import random

DEBUG_MODE = 0


def _debug_printer(*args):
    if DEBUG_MODE:
        for s in args:
            print(s, end="")
        print()


def fifo(data, page_size):
    # print("Doing for FIFO")
    table = []
    miss = 0
    hit = 0
    for i in data:
        if i in table:
            hit += 1
            _debug_printer(i, " ==>", " HIT", f"   [Size:{len(table)}, {table} ]")
        else:
            miss += 1
            _debug_printer(i, " ==>", " MISS", f"  [Size:{len(table)}, {table} ]")
            if len(table) >= page_size:
                victim = table.pop()
                _debug_printer(" " * 6, "Victim ==>", victim)

            table.insert(0, i)

    return miss, hit


def lru(data, page_size):
    # print("Doing for LRU")
    table = []
    miss = 0
    hit = 0
    for i in data:
        if i in table:
            hit += 1
            table.remove(i)
        else:
            miss += 1
            _debug_printer(i, " ==>", " MISS", f"  [Size:{len(table)}, {table} ]")
            if len(table) >= page_size:
                victim = table.pop()
                _debug_printer(" " * 6, "Victim ==>", victim)
        table.insert(0, i)

    return miss, hit


def random_replacement(data, page_size):
    # print("Doing for Random")
    table = []
    miss = 0
    hit = 0
    for i in data:
        if i in table:
            hit += 1
            _debug_printer(i, " ==>", " HIT", f"   [Size:{len(table)}, {table} ]")
        else:
            miss += 1
            _debug_printer(i, " ==>", " MISS", f"  [Size:{len(table)}, {table} ]")
            if len(table) >= page_size:
                victim = random.choice(table)
                _debug_printer(" " * 6, "Victim ==>", victim)
                table.remove(victim)
            table.append(i)
    return miss, hit


def lifo(data, page_size):
    # print("Doing for LIFO")
    table = []
    miss = 0
    hit = 0
    for i in data:
        if i in table:
            hit += 1
            _debug_printer(i, " ==>", " HIT", f"   [Size:{len(table)}, {table} ]")
        else:
            miss += 1
            _debug_printer(i, " ==>", " MISS", f"  [Size:{len(table)}, {table} ]")
            if len(table) >= page_size:
                victim = table.pop()
                _debug_printer(" " * 6, "Victim ==>", victim)
            table.append(i)
    return miss, hit


def optimal(data, page_size):
    table = []
    miss = 0
    hit = 0
    for i in data:
        if i in table:
            hit += 1
        else:
            miss += 1
            if len(table) >= page_size:
                future_indices = [data.index(x) if x in data[data.index(i):] else float('inf') for x in table]
                victim = table[future_indices.index(max(future_indices))]
                table.remove(victim)
            table.append(i)

    return miss, hit


def main():
    # pagesize, inputsize, inputchoices
    iterations = [
        [5, 100, 10],
        [5, 1000, 10],
        [5, 1000, 100],
        [50, 20, 10],
        [100, 100, 100],
        [50, 100, 1000],
        [100, 1000, 1000],
        [100, 10000, 1000],
    ]
    for page_size, \
            total_size_of_input_array_size, \
            valid_individual_input_choices_1_to_what in iterations:
        data = []
        _valid_inputs_choices = [i for i in range(1, valid_individual_input_choices_1_to_what + 1)]
        for i in range(total_size_of_input_array_size):
            c = random.choice(_valid_inputs_choices)
            data.append(c)

        print("Page size:", page_size)
        print("Input Size:", total_size_of_input_array_size)
        print("Random Data from 0 -", valid_individual_input_choices_1_to_what)
        # print("Data:", data)
        m, h = fifo(data, page_size)
        print("FIFO", "Misses:", m, "Hits:", h)
        m, h = lru(data, page_size)
        print("LRU", "Misses:", m, "Hits:", h)
        m, h = random_replacement(data, page_size)
        print("Random", "Misses:", m, "Hits:", h)
        m, h = lifo(data, page_size)
        print("LIFO", "Misses:", m, "Hits:", h)
        m, h = optimal(data, page_size)
        print("Optimal", "Misses:", m, "Hits:", h)
        print("-" * 50)


if __name__ == '__main__':
    main()

Result:

Page size: 5
Input Size: 100
Random Data from 0 - 10
FIFO Misses: 62 Hits: 38
LRU Misses: 68 Hits: 32
Random Misses: 63 Hits: 37
LIFO Misses: 54 Hits: 46
Optimal Misses: 54 Hits: 46

Page size: 5
Input Size: 1000
Random Data from 0 - 10
FIFO Misses: 496 Hits: 504
LRU Misses: 504 Hits: 496
Random Misses: 481 Hits: 519
LIFO Misses: 523 Hits: 477
Optimal Misses: 523 Hits: 477

Page size: 5
Input Size: 1000
Random Data from 0 - 100
FIFO Misses: 955 Hits: 45
LRU Misses: 956 Hits: 44
Random Misses: 949 Hits: 51
LIFO Misses: 956 Hits: 44
Optimal Misses: 956 Hits: 44

Page size: 50
Input Size: 20
Random Data from 0 - 10
FIFO Misses: 8 Hits: 12
LRU Misses: 8 Hits: 12
Random Misses: 8 Hits: 12
LIFO Misses: 8 Hits: 12
Optimal Misses: 8 Hits: 12

Page size: 100
Input Size: 100
Random Data from 0 - 100
FIFO Misses: 69 Hits: 31
LRU Misses: 69 Hits: 31
Random Misses: 69 Hits: 31
LIFO Misses: 69 Hits: 31
Optimal Misses: 69 Hits: 31

Page size: 50
Input Size: 100
Random Data from 0 - 1000
FIFO Misses: 92 Hits: 8
LRU Misses: 92 Hits: 8
Random Misses: 95 Hits: 5
LIFO Misses: 94 Hits: 6
Optimal Misses: 91 Hits: 9

Page size: 100
Input Size: 1000
Random Data from 0 - 1000
FIFO Misses: 903 Hits: 97
LRU Misses: 906 Hits: 94
Random Misses: 910 Hits: 90
LIFO Misses: 909 Hits: 91
Optimal Misses: 743 Hits: 257

Page size: 100
Input Size: 10000
Random Data from 0 - 1000
FIFO Misses: 9006 Hits: 994
LRU Misses: 9005 Hits: 995
Random Misses: 9023 Hits: 977
LIFO Misses: 8973 Hits: 1027
Optimal Misses: 8957 Hits: 1043