Skip to content

@jiewmeng /getdata.py
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
OS Project 2 WIP: Virtual Memory Page Replacement Algorithms Analysis
#!/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()
#!/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()
#!/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()
@jiewmeng
Owner

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.