Improving Performance of a Tape System:Programs and Graphs
Previous Programs and Graphs
Final Program
- This program runs LRU and Belady algorithm and computes their miss ratio simultaneously.
# comparison.py
# Nancy Xiao
# this program uses traces of tape requests at the European Centre for Medium-Range Weather Forecasts
# (data can be found in the paper "Analysis of the ECMWF Storage Landscape" by Grawinkel et al)
# the program simulates the tape system by implementing both LRU and Belady algorithm
# that is to say, whenever the tape drive is full and the system needs to insert a new tape
# 1. one system which implements LRU will replace the least recently used tape with the new tape
# 2. the other system which implements Belady will look for tape that will
# never be used in the future or will not be used in the near future
# the line below shows a typical tape request
# hdre01#VLAD#20140501:005936# MOUNT RC1021 Home 1,14,5,6,1 Drive 1,14,1,15 Client Host Id 328.681.634.674
# time of the request: hdre01#VLAD#20140501:005936#
# to mount or dismount a tape: MOUNT
# tape ID: RC1021
# where the tape is fetched: Home 1,14,5,6,1
# insert to which drive: Drive 1,14,1,15
# IP address of the requester: Client Host Id 328.681.634.674
# version: 4/9/2017
from __future__ import print_function
from __future__ import division
import math
import sys
import datetime
# drive of Belady
drive = []
# drive of LRU
LRUdrive = []
# miss & hit of Belady
miss = 0
hit = 0
# miss & hit of LRU
LRUmiss = 0
LRUhit = 0
DEBUG = False
def displayDict( tapesD ):
keys = list( tapesD.keys() )
keys.sort()
if DEBUG:
print( "Dictionary" )
print( "--------------------------------------------" )
for key in keys:
print( "%2s: %s" % (key, ", ".join( [str(k) for k in tapesD[key]] ) ) )
print( "--------------------------------------------" )
def main():
global drive, tapes, miss, hit, LRUmiss, LRUhit,LRUdrive
global DEBUG
if len( sys.argv ) != 3:
print( "Syntax: python testCommandLineArgs.py noDrives traceFileName" )
return
# get command line parameters
noDrives = int( sys.argv[1] )
fileName = sys.argv[2]
print( "No drives: ", noDrives )
print( "trace file: ", fileName )
# initialize the drives
drive = [-1]*noDrives
LRUdrive = [-1]*noDrives
# take in tape requests and clean up the requests
file = open( fileName, 'r' )
lines = file.readlines()
file.close()
# to record tape index in LRUdrive
LRUindex = 0
# to record tapes' index in dictionary keys
tapeIndex = 0
# to remove the tapes' index that has been inserted/removed
currentIndex = 0
# to find out which tape will not be called in near future
farthestIndex = 0
# to record the index of this tape
farthestTapeIndex = 0
# to initialize the dictionary
tapesD = {}
# to initialize a boolean to decided if Belady is needed
isFound = False
# to initialize a list of all "MOUNT" tape requests
requestList = []
for line in lines:
# clean up the file
line = line.replace( " ", " " )
line = line.replace( " ", " " )
line = line.replace( " ", " " )
fields = line.split(" ")
md = fields[1]
tape = fields[2]
if md != "DISMOUNT":
# record all tapes'index in dictionary
if tape not in tapesD.keys():
tapesD[ tape ] = [tapeIndex]
else:
tapesD[ tape ].append(tapeIndex)
tapeIndex += 1
# to append all eligible tape requests into list
requestList.append((md,tape))
#displayDict(tapesD)
for md, tape in requestList :
if md != "DISMOUNT":
# the first system simulates LRU
if tape not in LRUdrive:
LRUdrive = [tape] + LRUdrive[0:-1]
LRUmiss += 1
else:
# implements LRU
LRUindex = LRUdrive.index(tape)
LRUdrive = [tape] + LRUdrive[0:LRUindex]+LRUdrive[LRUindex+1:]
LRUhit += 1
# the second system simulates Belady
# if tape requested is in drive
if tape in drive:
hit += 1
if DEBUG: print( " %s --> Hit" % str(drive) )
# if tape is not in drive and drive has empty space
elif tape not in drive and drive[noDrives-1]== -1:
miss += 1
drive = [tape] + drive[0:-1]
if DEBUG: print( " %s --> Miss" % str( drive ) )
# if tape is not in drive and drive is full
else:
miss += 1
# check if any tape will never be needed again
# if found, replace it with the new tape
for k in range(0,len(drive)):
if len(tapesD[drive[k]])==0:
drive[k] = tape
isFound = True
if DEBUG: print( " %s --> Miss (isFound:T)" % str( drive ) )
break
# if all tapes will be needed again
# find out which tape will be called relatively late
if isFound == False:
for k in range(0,len(drive)):
if farthestIndex < tapesD[drive[k]][0]:
farthestIndex = tapesD[drive[k]][0]
# record the index of the tape in drive,helping the future replacement
farthestTapeIndex = k
if DEBUG: print( " farthestTapeIndex =", k )
# reset the index recorders
farthestIndex = 0
# move the newly added tape to the first place
record = tapesD[drive[k]]
drive[farthestTapeIndex] = tape
if DEBUG: print( " Updated drive =", str( drive ) )
if DEBUG: print( "===> current index %d: current tape: %2s " % (currentIndex, tape) )
# move the newly inserted tape to the first place
index = drive.index(tape)
drive = [tape] +drive[0:index]+drive[index+1:]
# remove the tape index that has already been inserted
tapesD[ tape ].remove(currentIndex)
if DEBUG: displayDict( tapesD )
# update which tape is currently dealt with
currentIndex +=1
# set the boolean to its original state
isFound = False
# if Belady perform worse than LRU (which should never happen）
# print out the two systems' situations
if miss > LRUmiss:
print("currentIndex",currentIndex,"request",line)
print("LRU miss & hit",LRUmiss, LRUhit)
print("LRU drive", LRUdrive)
print("tape",tape,"isFound",isFound)
print("tape removal",record)
print("miss & hit", miss, hit)
print("Belady drive", drive)
#calculate the miss ratio of both Belady and LRU
total_request = hit + miss
raw_percent = 100*(miss/total_request)
LRUtotal_request = LRUhit + LRUmiss
LRUraw_percent = 100*(LRUmiss/LRUtotal_request)
# miss ratio，precision to 2 decimal places
percent = round(raw_percent,2)
LRUpercent = round(LRUraw_percent,2)
# current date time
date = datetime.datetime.now().strftime("%Y%m%d %H:%M")
f = open("results.txt",'a')
f.write('\n')
#append result
LRUresult = (', '.join((date,fileName,str(noDrives),str(LRUtotal_request),str(LRUhit),str(LRUmiss),str(LRUpercent))))
result = (', '.join((date,fileName,str(noDrives),str(total_request),str(hit),str(miss),str(percent))))
LRUresult = "LRU " + LRUresult
result = "Belady " + result
f.write(LRUresult)
f.write('\n')
f.write(result)
f.close()
print(LRUresult)
print(" ")
print(result)
main()
Final Graphs
