import random
from optparse import OptionParser 
import sys

# global constants that may be set with options 
# see parseArgs for more information and default values 

debugLevel = 0
systemPageCount = 0 
clockLimit = 0 
processCount = 0 
outputFile = sys.stdout 
averageInstructions = 0
memoryLimit = 0 
loadTime = 0 

# this is to make it possible to test with consecutive
# memory locations instead of random(ish) ones
# may be useful in testing and debugging 
usingConsecutive = False

# pages currently loaded into memory 
systemPages  = []
# pages in the process of being loaded into memory 
pendingPages = [] 

# runnable process list 
runnableProcesses = []
# processes blocked on page loads 
stoppedProcesses = [] 

# this is used to get new process ids, and is not a
# count of processes in the system 
processNumber = 100 

# current time in "ticks" 
clock = 0   

def randStream(start,averageDiff, sigmaDiff, limit) :
    """
    Generates a stream of numbers starting with "start"
    The difference between consecutive numbers in the sequence
    has mean "averageDiff" and standard deviation "sigmaDiff".
    The numbers will never be less than zero or greater than "limit".
    """
    current = start
    while True :
        diff = random.gauss(averageDiff,sigmaDiff)

        start = start + int(diff) 
        
        if start < 0 :
            start = 0
        if start > limit :
            start = limit 
        yield start

# for testing this may be convenient 
def consecutiveStream(limit) :  
    """
    Generate a stream of numbers that runs from 0 to limit and then repeats 
    """
    current = 0
    while True :
        yield current
        current +=1
        if current > limit : current = 0 

def instructionStream(count, istream, dstream) :
    """
    Generate a stream of pairs of numbers that correspond (kind of)
    to instructions and memory locations used by those instructions 
    """

    for i in range(count) : 
        yield (istream.next(), dstream.next()) 

class Page :
    """
    Class Page represents a page in memory.
    Each page has
       process - the process the page belongs to
       address - the address of the page
       inMemory - is the page currently in memory or not
       loading - is the page currently being loaded
       loadEnd - the clock time at which the page will finish loading


    """ 
    def __init__(self, process, addr):
        """
        Initialize a page with its owning process and address 
        """
        self.process = process
        self.address = addr 
        self.inMemory = False
        self.loading = False 
        self.loadEnd = 0

    def __str__(self) :
        return "Page(pid=%d addr=%d inMem?=%s load?=%s)" % (self.process.processID, self.address, self.inMemory, self.loading)

    def __repr__(self) :
        return self.__str__() 

    def update(self) :
        pass

    def fetch(self) :
        """
        initiate a fetch of a page not in memory 
        """
        makeUnRunnable(self.process) 
        self.process.faults += 1 
        self.loading = True 
        self.loadEnd = clock + loadTime 
        if debugLevel > 3 : 
            print "Fetch page :", self 
        systemFetch(self) 

    def endFetch(self) :
        """
        indicate that the fetch of this page has completed
        """ 
        self.loading = False
        self.inMemory = True 
        if debugLevel > 3 : 
            print "End Fetch page :", self 
        makeRunnable(self.process)             

    def unload(self) :
        """
        mark a page as not being in memory 
        """
        if debugLevel > 8 :
            print "unloading ", self 
        self.inMemory = False 

class Process :
    """
    Process variables :
      processID - the (essentially) random number used to identify the process 
      instructionStream - the instruction stream for the process 
      memory - a dictionary (address -> page) of the pages in the process 
      currentInstruction - the address of the current instruction
                          (produced by the instructionStream)
      currentDatum - the address of the current memory location 
                          (produced by the instructionStream)
      instructionsDone - the number of instructions completed 
      canRun  - is the process runnable - that is, is it not waiting for a page to load
      faults - a count of pageFaults 
    """ 
    def __init__(self, istream) :
        """
        Initialize a Process with its associated stream of instructions/data 
        """ 
        global processNumber 
        processNumber += 1 

        self.instructionStream = istream
        self.memory = {} 
        self.currentInstruction = None
        self.currentDatum  = None 
        self.processID = processNumber
        self.instructionsDone = 0 
        self.canRun = True 
        self.faults = 0 
        if debugLevel > 2 : 
            print "new process:", self

    def __str__(self) :
        return "Process(pid=%(processID)s, inst=%(currentInstruction)s, run?=%(canRun)s)" % self.__dict__
    
    def __repr__(self) :
        return self.__str__()
    
    def tryToRun(self, instructionCount) : 
        """
        tries to run this process for instructionCount instructions 
        """
        if self.currentInstruction : # an incomplete instruction? 
            ok = self.doInstruction(self.currentInstruction) # yup 
            if not ok : return 
        i = 0
        while i < instructionCount and not self.currentInstruction :
            try : 
                nextID = self.instructionStream.next()
                if debugLevel > 3 : 
                    print nextID
                ok = self.doInstruction(nextID)
                if not ok : return 
                i += 1 
            except StopIteration :
                self.quit() 
                return 

    def doInstruction(self, nextID)  :
        """
        Attempt to do the next "instruction" which consists of an instruction
        address and a data address

        Since first the instruction and then the datum are fetched
        it is quite possible that pressure on the memory will have forced
        the instruction part to be discarded, in which case it will have
        to be restarted.  
        """ 
        global clock
        clock += 1  
        (instruction, datum) = nextID 
        ok = self.doMemoryReference(instruction)  # might have to try from beginning 
        if not ok :
            self.currentInstruction = nextID
            return ok
        ok = self.doMemoryReference(datum)
        if ok :
            self.currentInstruction = False
        else :
            return False 
        self.instructionsDone += 1 
        return ok 

    def doMemoryReference(self,addr) :
        """
        Handles referencing an address.   if the page is in memory, good
        otherwise, initiate a fetch on the page
        """ 
        if addr in self.memory :  # does the page exist 
            if self.memory[addr].inMemory : # and is it in memory
                self.memory[addr].update()  # yes, maybe do bookkeeping 
                return True
            else :
                self.memory[addr].fetch()   # nope fetch 
                return False

        self.memory[addr] = Page(self, addr) # doesn't exist and needs fetching 
        self.memory[addr].fetch() 
        return False 

    quitFmt = "Process %d quitting at time %d with %d faults over %d instructions "
    ratioFmt = "ratio = %f\n" 

    def finish(self) : 
        """
        End a process and print some bookkeeping information. 
        """ 
        runnableProcesses.remove(self) 
        outputFile.write(self.quitFmt % (self.processID,
                                         clock, 
                                         self.faults,
                                         self.instructionsDone))
        if self.instructionsDone != 0 : 
            faultProportion = float(self.faults)/float(self.instructionsDone)
            outputFile.write(self.ratioFmt % faultProportion) 
        else :
            outputFile.write("\n") 

    def quit(self) :
        """
        quit ends a process but starts a new one
        """ 
        self.finish()
        makeNewProcess()

    def kill(self) :
        """
        kill just ends the process and doesn't start a new one
        should be used at the end of the simulation
        """ 
        self.finish()
        
def systemFetch(page) :
    """
    Adds a page to the list of pages being read in to memory. 
    """ 
    pendingPages.append(page)
    if debugLevel > 5 :
        print "Fetch ", pendingPages 

def makeRunnable(process) : 
    """
    Marks a process as being runnable at the system level 
    """ 
    if debugLevel > 5 :
        print "makeRunnable :", process 
    process.canRun = True 
    runnableProcesses.append(process)
    stoppedProcesses.remove(process) 

def makeUnRunnable(process) : 
    """
    Marks a process as not being runnable at the system level 
    """ 

    if debugLevel > 5 :
        print "makeUnRunnable :", process 
    process.canRun = False 
    runnableProcesses.remove(process)
    stoppedProcesses.append(process)
    
def systemDoPage() :
    """
    Check pending pages for pages that we can now load in and mark them
    as now being in memory.   potentially this unblocks processes. 
    """ 
    global systemPages
    global pendingPages 
    if debugLevel > 4 : 
        print "system Pages (len=%d) " % len(systemPages) 
        print systemPages 
        print "pending pages :"
        print pendingPages 
    if pendingPages : 
        for p in pendingPages : 
            if p.loadEnd <= clock :
                pendingPages.remove(p) 
                p.endFetch() 
                systemPages.append(p) 

                if len(systemPages) > systemPageCount :
                   # this is where you should change the way pages are
                   # picked for removal 
                   p1 = random.choice(systemPages)  
                   p1.unload()
                   systemPages.remove(p1) 


def makeNewProcess() :
    if usingConsecutive :
        runnableProcesses.append(Process(consecutiveIStream())) 
    else : 
        runnableProcesses.append(Process(randomIStream()))
    
def randomIStream() :
    """
    Generate a random(ish) stream of instruction/datum "addresses" 
    """ 
    istream = randStream(random.randint(0,memoryLimit), 0,  4, memoryLimit)
    dstream = randStream(random.randint(0,memoryLimit), 0, 20, memoryLimit) 
    return instructionStream(random.randint(1,2*averageInstructions), istream, dstream)

def consecutiveIStream() :
    """
    Generate a stream of consecutive instruction/datum "addresses" 
    """ 
    istream = consecutiveStream(200)
    dstream = consecutiveStream(2000) 
    return instructionStream(200, istream, dstream)

def idleIStream() :
    """
    Generates a stream of instruction at 0, datum at 0 to (kind of) simulate the
    idle process.   Once these are read in once, they should stay there.
    It will run for at clockLimit cycles, which is as much as the simulation will
    run. 
    """ 
    istream = consecutiveStream(0)
    dstream = consecutiveStream(0) 
    return instructionStream(clockLimit, istream, dstream)
    
def runProcesses() :
    """
    Run processes on the process list until done (when there are no runnable
    or blocked processes left). 
    """ 
    global runnableProcesses
    global stoppedProcesses 
    global clock 

    runnableProcesses = [Process(idleIStream())]  # idle process, runs forever 

    for i in range(processCount) :
        makeNewProcess() 

    stoppedProcesses = [] 

    while clock < clockLimit :
        systemDoPage() 
        if runnableProcesses : 
            if debugLevel > 4 : 
                print "runnable:"
                print runnableProcesses
            # pick a process to run randomly
            p = random.choice(runnableProcesses)
            p.tryToRun(100)                # try to run it

        if stoppedProcesses :   
            if debugLevel > 4 : 
                print "stopped:"
                print stoppedProcesses

    for i in runnableProcesses : # out of time, stop all procs 
        i.kill() 

usestr= """Usage: %s [--clock-limit count] 
                     [--process-count count] 
                     [--pages count]
                     [--average-instruction-count count]
                     [--load-time time] 
                     [--memory-limit size] 
                     [--debug-level debug level]
                     [--output-file filename]"""

def parseArgs() :
    
    global systemPageCount
    global clockLimit  
    global processCount 
    global outputFile 
    global averageInstructions
    global memoryLimit 
    global debugLevel
    global loadTime 
    parser = OptionParser()

    parser.add_option("--clock-limit",
                      action="store", type="int",
                      dest="clockLimit", default=100000,
                      help="set total number time ticks to run")

    parser.add_option("--pages",
                      action="store", type="int",
                      dest="systemPageCount", default=10,
                      help="total number of pages") 

    parser.add_option("--average-instruction-count",
                      action="store", type="int",
                      dest="averageInstructions", default=20,
                      help="average number of instructions to be run by each process") 

    parser.add_option("--memory-limit",
                      action="store", type="int",
                      dest="memoryLimit", default=5, 
                      help="total memory for each process") 

    parser.add_option("--load-time",
                      action="store", type="int",
                      dest="loadTime", default=10, 
                      help="time to load a page in ticks")

    parser.add_option("--process-count",
                      action="store", type="int",
                      dest="processCount", default=10, 
                      help="number of processes to run (excluding idle)")

    parser.add_option("--debug-level",
                      action="store", type="int",
                      dest="debugLevel", default=0, 
                      help="Debugging level: 0 -> none, 10 -> all") 

    parser.add_option("--output-file",
                      action="store", type="string",
                      dest="outputFile" , default=None, 
                      help="file for output") 

    (options, args) = parser.parse_args() 
    systemPageCount = options.systemPageCount 
    clockLimit = options.clockLimit 
    if options.outputFile  : 
        outputFile = open(options.outputFile, "w")
    memoryLimit = options.memoryLimit
    averageInstructions = options.averageInstructions 
    loadTime = options.loadTime 
    debugLevel = options.debugLevel 
    processCount = options.processCount 

    # echo arguments as a single line prefaced with a #
    # so the program can be rerun
    # with the same arguments if needed, and so the information
    # about the arguments is saved in the output file for reference

    outputFile.write("# ")
    outputFile.write("--clock-limit=%d " % clockLimit)
    outputFile.write("--process-count=%d " % processCount)
    outputFile.write("--pages=%d " % systemPageCount) 
    outputFile.write("--average-instruction-count=%d " % averageInstructions)
    outputFile.write("--memory-limit=%d " % memoryLimit) 
    outputFile.write("--load-time=%d" % loadTime)  
    outputFile.write("\n") 

def main() :
    parseArgs() 
    runProcesses()

def simpleTest() : 
    runProcesses()

def showRandomStream() : 
    rgen = randStream(100,0, 10, 500)
    for i in range(5000) :
        print rgen.next()

if __name__ == "__main__" :
    main()