public
Created

OS Project 2 WIP: Virtual Memory Page Replacement Algorithms Analysis

  • Download Gist
getdata.py
Python
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 91 92 93 94 95 96 97 98 99 100 101 102 103
#!/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
Python
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
#!/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
Python
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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
#!/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 :)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.