# ************************************************************ # * Author: D. Parson # * PageReplaceOptimal.stm per csc343 spring 2024 assignment 4 with # * assorted locality-of-reference distributions and frameCounts, # * using processor.contextCount to select the former and len(processor.fastio) # * to multiply the latter. This is a single-threaded, single-process # * simulation that does not otherwise use those processor fields. # ************************************************************ machine processor { # Assignment 4 is similated using 1 single-threaded process. tid = -1, pid = -1 ; start init, accept processorDone ; init -> processorDone init()[]/@ msg("contextCount " + str(processor.contextCount)); msg("iocount " + str(len(processor.fastio))); fork()@ } # All simulation takes place in this one thread, so no need for # processor.prefixed or pcb.prefixed state variables. machine thread { machineid = -1, pid = -1, tid = -1, # Optimal replacement does not use referenceQueues. It uses # referencePageList to "look into the future". referenceQueues # "looks into the past". referenceQueues = @[[], []]@, referencePageCount = 100000, # ^^^^^ How many times to reference a page before quitting simulation. pageCount = 500, frameCount = 100, currentPage = 0, victimPage = 0, # ^ Logical pages, physical frames, page being referenced, victimized. # NOTE in FinalPagingCSC343Spring2024, frameCount gets boosted in # the init -> readyToCompute by the number of fastio units, which # are not used for io() in this model, but just used as a # command-line parameter. future = @[]@, respage = -1, isModified = 0, wasModified = 0, # ^ future is used for Optimal # respage is a temp variable for resident page if you need it referencePageList = @[]@, # ^ referencePageList is the Reference String per Chapter 9 slide 30 # Gaussian sample below should give fairly good locality of reference. allPageSet = @None@, residentPageMap = @None@; start init, state readyToCompute, state compute, state findVictim, accept terminated ; init -> readyToCompute init()[]/@machineid, pid, tid = getid(); frameCount = frameCount * len(processor.fastio); locality = 'gaussian' if (processor.contextCount == 1) else ('exponential' if (processor.contextCount == 2) else ('revexponential' if (processor.contextCount == 3) else 'uniform')); msg("TRACE Optimal pageCount=" + str(pageCount) + ", frameCount=" + str(frameCount) + ", locality=" + locality); print("TRACE Optimal pageCount=" + str(pageCount) + ", frameCount=" + str(frameCount) + ", locality=" + locality); # For the normal distribution, the values less than one standard # deviation away from the mean account for 68.27% of the set; # while two standard deviations from the mean account for 95.45%; # and three standard deviations account for 99.73% # https://en.wikipedia.org/wiki/Normal_distribution # In FinalPagingCSC343Spring2024/ I am tightening one standard # deviation from pageCount//10 of Assignment 4 to pageCount//20 # so that 68.27% of them fit into 1/10th of the pageCount range, # approximating the locality of exponential & revexponential. for i in range(0,referencePageCount): referencePageList.append( sample(0,pageCount-1, 'gaussian', pageCount//2, pageCount//20) if (locality == 'gaussian') else (sample(0,pageCount-1,'uniform') if (locality == 'uniform') else (sample(0,pageCount-1,'exponential',pageCount//10) if (locality == 'exponential') else sample(0,pageCount-1,'revexponential',(pageCount//10)*9)))); # print("DEBUG PAGEREF",referencePageList); # ^^^ Used to plot histogram. allPageSet = set(referencePageList); residentPageMap = {}; # ^^^ residentPageMap maps resident page to the isModified bit, # and its keys serve as residentPageSet. currentPage = referencePageList.pop(0); # One in 10 pages starts life as modified, but if it stays # resident in memory before paging out, 10 accesses on average # with make it a modified page. isModified = 1 if ((sample(0,1024,'uniform') % 10) == 0) else 0; # ^^^ isModified when 1 means the page is "Dirty" and needs to be # written when paged out. 10% of of resident pages have been modified. # STUDENT B 5% per file: # Enqueue (using .append()) currentPage in the correct # referenceQueues for FIFO, LRU, or LRUDirty per instructions at # the start of this "machine thread". Note that LRU & LRUDirty require # conditional removal of currentPage *BEFORE* enqueuing, and LRUDirty # requires enqueuing into the appropriate referenceQueues[???]. # Also, for LRUDirty, conditionally remove currentPage from # both queues, one at a time. Use a "while" loop for conditional # removal() per the queue.remove(???) instructions at the top of # this thread STM. cpu(0)@ # No paging time required when currentPage is resident in a frame. # It may be resident but clean; mark it dirty if isModified. readyToCompute -> compute cpu()[@currentPage in residentPageMap@]/@ residentPageMap[currentPage] = residentPageMap[currentPage] | isModified; cpu(0)@ # No paging time required when currentPage is not resident in a frame, # but a free frame is available. readyToCompute -> compute cpu()[@(not (currentPage in residentPageMap)) and (len(residentPageMap) < frameCount)@]/@ residentPageMap[currentPage] = isModified ; cpu(0)@ # Page is not resident and there is no free frame, use specific # page replacement algorithm (Optimal is done, FIFO, LRU, LRUDirty) # to locate the victim page. readyToCompute -> findVictim cpu()[@not ((currentPage in residentPageMap) or (len(residentPageMap) < frameCount))@]/@ victimPage = -1 ; # For the currently resident pages, one of which must be victimized, # START OF OPTIMAL PAGE REPLACEMENT TO SET VARIABLE victimPage. # Optimal page replacement finds the one furthest in the # referencePageList -- the page to be referenced furthest in the # future -- and selects that as the victim. However, if there is a # page in residentPageMap that will never be referenced again, # it becomes the victim; the multiplication of # (respage * referencePageCount * 10) guarantees that this no-future # respage sorts ahead by max(). future = []; for respage in residentPageMap: future.append(referencePageList.index(respage) if (respage in referencePageList) else (respage * referencePageCount * 10)); victimPage = max(future); victimPage = referencePageList[victimPage] if (victimPage < len(referencePageList)) else int(victimPage / (referencePageCount * 10)); # END OF OPTIMAL PAGE REPLACEMENT TO SET VARIABLE victimPage. # START OF FIFO PAGE REPLACEMENT TO SET VARIABLE victimPage. # STUDENT C 15%: For PageReplaceFIFO.stm, after copying # PageReplaceOptimal.stm to PageReplaceFIFO.stm and updating # header comments at the top of the file: # 1. Remove the above lines of code from "START OF OPTIMAL" through # "END OF OPTIMAL". We are not using Optimal page replacement. # 2. Dequeue victimPage from the front of referenceQueues[0]. # See comments at start of this machine thread for queue operations. # END OF FIFO PAGE REPLACEMENT TO SET VARIABLE victimPage. # START OF LRU PAGE REPLACEMENT TO SET VARIABLE victimPage. # STUDENT D 10%: For PageReplaceLRU.stm, after copying your working # PageReplaceFIFO.stm (make testFIFO has passed) to # PageReplaceLRU.stm and updating header comments at the # top of the file: # 1. Replace the "START OF FIFO" comment line above with this # "START OF LRU" line and do the same for "END OF FIFO". # 2. Dequeue victimPage from the front of referenceQueues[0]. # This is the same as step 2 for FIFO above. # END OF LRU PAGE REPLACEMENT TO SET VARIABLE victimPage. # START OF LRUDirty PAGE REPLACEMENT TO SET VARIABLE victimPage. # STUDENT E 15%: For PageReplaceLRUDirty.stm, after copying your # working PageReplaceLRU.stm (make testLRU has passed) to # PageReplaceLRUDirty.stm and updating header comments at the # top of the file: # 1. Replace the "START OF LRU" comment line above with this # "START OF LRUDirty" line and do the same for "END OF LRU". # 2. Dequeue victimPage from the front of referenceQueues[0] if # its length is > 0, else from referenceQueues[1]. LRUDirty # prefers to select victimPage from the set of pages that # have not been modified since paging in, to avoid paging-out # overhead. See instructions for "For LRUDirty replacement" # near the top of this thread state machine. # 3. After "make testLRUDirty" passes, complete README.txt. # END OF LRUDirty PAGE REPLACEMENT TO SET VARIABLE victimPage. # STUDENT DO NOT!!! MODIFY THE LINES BELOW IN THIS TRANSITION!!! while victimPage in referenceQueues[0]: referenceQueues[0].remove(victimPage); while victimPage in referenceQueues[1]: referenceQueues[1].remove(victimPage); wasModified = residentPageMap[victimPage]; residentPageMap.pop(victimPage); residentPageMap[currentPage] = isModified ; cpu(2 if (wasModified) else 1)@ findVictim -> compute cpu()[]/@ cpu(0)@ compute -> terminated cpu()[@len(referencePageList) == 0@]/ compute -> readyToCompute cpu()[@len(referencePageList) > 0@]/@ currentPage = referencePageList.pop(0); # One in 10 pages starts life as modified, but if it stays # resident in memory before paging out, 10 accesses on average # with make it a modified page. isModified = 1 if ((sample(0,1024,'uniform') % 10) == 0) else 0; # STUDENT F 5% per file: Enqueue currentPage in the correct # referenceQueues for FIFO, LRU, or LRUDirty per instructions at # the start of this "machine thread". Note the LRU & LRUDirty require # conditional removal of currentPage *BEFORE* enqueuing, and LRUDirty # requires enqueuing into the appropriate referenceQueues[???]. # Also, for LRUDirty, conditionally remove currentPage from # both queues, one at a time. Use a "while" loop for conditional # removal() per the queue.remove(???) instructions at the top of # this thread STM. cpu(0)@ } processor