Improving Performance of a Tape System:Programs and Graphs

From CSclasswiki
Jump to: navigation, search


( Back to Main Page )


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


LRUMissRatioGraphFor5Traces.png
BeladyMissRatioGraphFor5Traces.png
BeladyAndLRUMissRatioGraphFor5Traces.png
BeladyAndLRUMissRatioGraphFor1Trace.png