OS Project 2 WIP: Virtual Memory Page Replacement Algorithms Analysis

getdata.py

#!/usr/bin/env python3.2

##################################################################
# Lim Jiew Meng (A0087884H)
# CS2106 OS Project 2 : Page Replacement Algorithms
##################################################################

import argparse
from rsgen import ReferenceStringGenerator
from vm import VirtualMemory, RandomPageReplacement, FifoPageReplacement, LruPageReplacement
import math
import sys
import json
import threading
from time import sleep

# numFrames: number of frames in virtual memory
# algo: page replacement algorithm to use
# rs: reference string (array)
# algoData: dictionary of 2D array representing resulting data
# key: name of algo
# i: index of e (for use in algoData)
# j: index of t (for use in algoData)
def QueryVM(numFrames, algo, rs, algoData, key, i, j):
    # init virtual memory with algo
    vmobj = VirtualMemory(numFrames, algo)
    # query reference strings
    for r in rs:
        vmobj.get(r)
    # store page fault data
    algoData[key][i][j] = vmobj.pageFaults

# main function that generates RS for each (e, t), 
# then starts querying VM with different page replacement algos (with threading) 
# and gets page fault statistics, which are output as JSON or CSV 
def main():

    # parses input options
    parser = argparse.ArgumentParser(description="Gets statistics for different page replacement algoriths with varing working set size (e) and stability (t)")
    parser.add_argument("--numReferences", metavar="N", type=int, default=120000, help="Number of references to generate")
    parser.add_argument("--numPages", metavar="P", type=int, default=1000, help="Number of pages in virtual memory (# pages)")
    parser.add_argument("--numFrames", metavar="F", type=int, default=100, help="Number of frames in main memory")
    parser.add_argument("--numPageReferenced", metavar="m", type=int, default=100, help="Number of times each page referenced")
    parser.add_argument("--lruFactor", metavar="lru", type=float, default=0, help="Chance of reference coming from LRU")
    parser.add_argument("--outputFormat", metavar="format", type=str, default="csv", help="json | csv")

    args = vars(parser.parse_args())
    
    # init variables 
    workingSetAxis = [] # x axis markers
    stabilityAxis = [] # y axis markers
    algoData = {} # dictionary of 2D array for pf data. In 2D array, row: working set (e), column: stability (t)
    
    for k in ["FIFO", "LRU", "Random"]:
        algoData[k] = [[None for i in range(6)] for j in range(8)]
    
    for i in range(8):
        e = 2 + i * math.floor(args["numFrames"] / 5)
        workingSetAxis.append(e)
        
    for j in range(6):
        t = j / 5
        stabilityAxis.append(t)  
        
    rsgenerator = ReferenceStringGenerator() 
    
    # for working set (e) from 2 to ~F (get 8 points)
    for i in range(8):
        e = workingSetAxis[i]
        # for stability (t) from 0 to 1 (get 6 points)
        for j in range(6):
            t = stabilityAxis[j]
            # generate a reference string (RS(e, t))
            rs = rsgenerator.generate(args["numReferences"], args["numPages"], e, args["numPageReferenced"], t, args["numFrames"], args["lruFactor"]).split(" ")
            
            # wait if there are too many threads running already
            while (threading.activeCount() > 12): 
                sleep(2)
            
            # start threads to process RS(e, t) with each algo
            threading.Thread(target = QueryVM, args = (args["numFrames"], RandomPageReplacement(), rs, algoData, "Random", i, j)).start()
            threading.Thread(target = QueryVM, args = (args["numFrames"], FifoPageReplacement(), rs, algoData, "FIFO", i, j)).start()
            threading.Thread(target = QueryVM, args = (args["numFrames"], LruPageReplacement(args["numFrames"]), rs, algoData, "LRU", i, j)).start()

    # wait for tasks to finish
    while threading.activeCount() > 1:
        sleep(2)
                
    # print json
    if args["outputFormat"] == "json":
        print(json.dumps({"data": algoData, "workingSetAxis": workingSetAxis, "stabilityAxis": stabilityAxis}, indent=4))  
    else: 
        for k in ["FIFO", "LRU", "Random"]:
            print(k)
            print("," + ",".join(map(lambda n : str(n), stabilityAxis)))
            for i in range(len(workingSetAxis)):
                line = str(workingSetAxis[i]) + "," + ",".join(map(lambda n : str(n), algoData[k][i]))
                print(line)
        # TODO: REMOVE
        print(json.dumps({"data": algoData, "workingSetAxis": workingSetAxis, "stabilityAxis": stabilityAxis}))    

if __name__ == "__main__":                       
    main()

rsgen.py

#!/usr/bin/env python3.2

#################################################################
# Lim Jiew Meng (A0087884H)
# CS2106 OS Proj 2 : Page Replacement Algorithms
#################################################################

import argparse
import random
from math import floor
from vm import Lru

class ReferenceStringGenerator:
    # numReferences : total number of page references to generate
    # numPages (P) : num pages in virtual memory
    # workingSet (e) : num pages in working set
    # numPageReferenced (m) : num page referenced 
    # stability: length of stable period (0 - 1)
    # lruSize: size of LRU (See lruFactor)
    # lruFactor: probability of generating a reference already in LRU (in an attempt to show benefit of LRU over FIFO)
    def generate(self, numReferences, numPages, workingSet, numPageReferenced, stability, lruSize = 10, lruFactor = 0):
        rs = ""
        p = random.randint(0, numPages - 1)
        lru = Lru(lruSize)
        lruRef = 0
        for i in range(floor(numReferences / numPageReferenced)):
            for j in range(numPageReferenced):
                if lru.size() > 0 and j > 5 and random.random() < lruFactor: # j > 5 simply ensures references can vary (ie. at least 5 distinct reference in LRU for current working set)
                    # get a random reference from LRU (within the current working set)
                    # start and end allows generation of a random index within the LRU, and current working set
                    start = max([0, lru.size() - j])
                    end = min([lru.size() - 1, lru.size() + j])
                    ref = lru.get(random.randint(start, end))
                    lruRef += 1
                else:
                    # get a random reference from working set
                    ref = (random.randint(p, p + workingSet)) % numPages
                    
                rs += str(ref) + " "
                lru.add(ref)

            if random.random() < stability: 
                p = random.randint(0, numPages - 1)
            else:
                p += 1
            
        return rs 
        
def main():
    parser = argparse.ArgumentParser(description="Generates reference strings")
    parser.add_argument("--numReferences", metavar="N", type=int, default=100000, help="Number of references to generate")
    parser.add_argument("--numPages", metavar="P", type=int, default=1000, help="Number of pages in virtual memory (# pages)")
    parser.add_argument("--numPageReferenced", metavar="m", type=int, default=100, help="Number of times each page referenced")
    parser.add_argument("--workingSet", metavar="e", type=int, default=50, help="Size of working set (# pages)")
    parser.add_argument("--stability", metavar="t", type=float, default=0.1, help="How stable should the references be. Between 0 - 1")
    parser.add_argument("--lruSize", metavar="lruSize", type=int, default=50, help="The size of LRU, typically number of frames")
    parser.add_argument("--lruFactor", metavar="lruFactor", type=float, default=0, help="Probability of references from LRU (w/in working set as much as possible)")    
    args = vars(parser.parse_args())

    # generate reference string
    rsgen = ReferenceStringGenerator()
    rs = rsgen.generate(args['numReferences'], args['numPages'], args['workingSet'], args['numPageReferenced'], args['stability'])
    print(rs)

if __name__ == "__main__":                       
    main()

vm.py

#!/usr/bin/env python3.2

##################################################################
# Lim Jiew Meng (A0087884H)
# CS2106 OS Project 2 : Page Replacement Algorithms
##################################################################

import argparse
import random

# Abstract Base Class for Page Replacement Algorithm of a Virtual Memory
# to be used with class extending VirtualMemory
class PageReplacementAlgotithm:

    # called when a page request is found in memory (no page fault)
    # frames: the frame table
    # page: the page requested
    def hit(self, frames, page):
        pass

    # called when a page fault occurs
    # see hit() for info on params
    def miss(self, frames, page):
        pass
        
    # helper to find empty slot in frames
    # returns the index of an empty slot, -1 if no empty slot
    def emptySlot(self, frames):
        try: 
            index = frames.index(None)
            return index
        except BaseException:
            return -1
	

# VirtualMemory (VM) class. Page Replacement Algorithm is implemented 
# using the Strategy Pattern
#
# Basic workings: 
#
# get(page) queries the VM. It calls hit() or miss() in the 
# Page Replacement Stragety class. If its a miss, pageFaults is incremented. 
# Subclasses of PageRepacementAlgorithm should override the hit() or miss() 
# methods as approperiate (to implement the page replacement strategy)
class VirtualMemory:
    def __init__(self, numFrames, pageReplacementAlgorithm):
        # counter for page faults
        self.pageFaults = 0

        # frame table: M[f] -> p
        self.frames = [None] * numFrames

        # strategy to use for page replacement
        self.pageReplacementAlgorithm = pageReplacementAlgorithm

    # queries the frame table for the existance of a page
    # calls replacement algo hit() or miss() as applicable
    def get(self, page):
        if self.isPageFault(page):
            # call pageReplacementAlgorithm.miss()
            self.pageReplacementAlgorithm.miss(self.frames, page)
            
            # increment counter
            self.pageFaults += 1
        else: 
            self.pageReplacementAlgorithm.hit(self.frames, page)
        
    # checks if a page is in the frame table (memory)
    def isPageFault(self, page):
        try:
            index = self.frames.index(page)
            return False
        except BaseException: # when page not found in frames (frame table)
            return True

class RandomPageReplacement(PageReplacementAlgotithm):

    # tries to fill an empty slot, otherwise pick a random slot to fill
    def miss(self, frames, page):
        index = self.emptySlot(frames)
        if index > -1:
            # fill empty slot
            frames[index] = page
        else: 
            # pick a random index (in frame table) to replace
            index = random.randint(0, len(frames) - 1)
            frames[index]
        
class FifoPageReplacement(PageReplacementAlgotithm):
    
    def __init__(self):
        self.first = 0;

    def miss(self, frames, page):
        index = self.emptySlot(frames)
        if index > -1:
            # fill empty slot
            frames[index] = page
        else: 
            # fill oldest frame
            frames[self.first] = page
            self.first = (self.first + 1) % len(frames)

# Python Lists doesn't appear to support max size. collections.deque doesn't appear to support indexed accessed
# So this allows indexed access and max size :)
class Lru:
    def __init__(self, maxlen):
        self.lru = []
        self.maxlen = maxlen
    
    # adds an elem into the LRU
    def add(self, elem):
        try: 
            # check if elem is in LRU
            i = self.lru.index(elem)
            # elem already in lru. Pop first
            self.lru.pop(i)
        except Exception:
            # elem is not in LRU
            # if LRU is full, pop oldest
            if len(self.lru) == self.maxlen:
                self.lru.pop()
        
        # add element at start
        self.lru.insert(0, elem)
        
    def get(self, index):
        return self.lru[index]
        
    def size(self):
        return len(self.lru)
    
    # Finds the index of elem in LRU. If not found return -1    
    def index(self, elem):
        try:
            i = self.lru.index(elem)
        except Exception:
            i = -1
        return i
        
class LruPageReplacement(PageReplacementAlgotithm):

    def __init__(self, numFrames):
        self.numFrames = numFrames
        self.lru = Lru(numFrames)
    
    # moves page in lru to top
    def hit(self, frames, page):
        # trigger refresh of LRU (mope page to top)
        self.lru.add(page)

    # tries to fill an empty slot first, else do page replacement.
    # in any case, updates the LRU
    def miss(self, frames, page):
        index = self.emptySlot(frames)
        if index > -1:
            # fill empty slot
            frames[index] = page
        else: 
            # no empty slot: do page replacement
            # Get the index of lru page in frame table
            leastRecentlyUsedPage = self.lru.get(self.numFrames - 1)
            leastRecentlyUsedPageIndex = frames.index(leastRecentlyUsedPage)
            
            # update frame table with new page
            frames[leastRecentlyUsedPageIndex] = page
        
        # update lru
        self.lru.add(page)
    
    # helper to find the index of page in frames. -1 if not found
    def indexOf(self, frames, page):
        try:
            index = frames.index(page)
        except BaseException: 
            index = -1
        return index
        

def main():

    # parse arguments
    parser = argparse.ArgumentParser(description="Page Replacement Algorithm Simulator")
    parser.add_argument("rs", metavar="RS", type=argparse.FileType(), help="File containing reference strings")
    parser.add_argument("--numFrames", metavar="F", type=int, default=1000, help="Number of frames in main memory")
    parser.add_argument("--numPages", metavar="P", type=int, default=100, help="Number of pages in virtual memory")

    args = vars(parser.parse_args())
    rsAll = args["rs"].read()
    rs = rsAll.split(" ")
    
    # Page Replacement Algorithms
    algos = { 
        "Random" : RandomPageReplacement(),
        "FIFO": FifoPageReplacement(),
        "LRU": LruPageReplacement(args["numFrames"])
    }
    
    for key, algo in algos.items():
        # do simulation (for each algo)
        vmobj = VirtualMemory(args['numFrames'], algo)
        for r in rs:
            vmobj.get(r)
            
        # output results
        print(key + " : " + str(vmobj.pageFaults))

if __name__ == "__main__":                       
    main()

Updated rsgen with lruFactor in an attempt to generate more references from pages already in LRU, thus showing benefit of LRU over FIFO :)