python program that implements the FIFO LRU and optimal page replacement algorithms
Write a Python program that implements the FIFO, LRU, and optimal page replacement
algorithms. First, generate a
random page-reference string where page numbers range from 0 to 9.
Apply the random page-reference string to each algorithm, and record
the number of page faults incurred by each algorithm. Implement the
replacement algorithms so that the number of page frames can vary from
1 to 7. Assume that demand paging is used.
Download all files
python program that implements the FIFO LRU and optimal page replacement algorithms
1 file(s) 121.00 KB
DS_Store File
1 file(s) 6.00 KB
Not a member!
Create a FREE account here to get access and download these files
Answer:
''' Demonstration of simple page replacement algorithms FIFO LRU Optimal Usage python paging.py [number of page frames] ''' #for obtaining command line parameters import sys ''' Simple FIFO page replacement algorithm ''' def FIFO(size, pages): SIZE = size count = 0 memory = [] faults = 0 fifoIndex = 0 for page in pages: if memory.count(page) == 0 and count < SIZE: # not present, but no replacement is necessary - page fault memory.append(page) count += 1 faults += 1 elif memory.count(page) == 0 and count == SIZE: # memory is full - replace FIFO page - page fault memory[fifoIndex] = page fifoIndex = (fifoIndex + 1) % SIZE faults += 1 elif memory.count(page) > 0: # present - do nothing pass #print ' faults =',faults,'inserting',page,'memory = ',memory return faults ''' LRU algorithm ''' def LRU(size, pages): SIZE = size count = 0 memory = [] faults = 0 for page in pages: if memory.count(page) == 0 and count < SIZE: # not present, but no replacement is necessary - page fault memory.append(page) count += 1 faults += 1 elif memory.count(page) == 0 and count == SIZE: # memory is full - replace LRU page - page fault # page at index 0 is LRU page memory.pop(0) memory.append(page) faults += 1 elif memory.count(page) > 0: # page is present - reorder stack memory.remove(page) memory.append(page) return faults ''' Optimal algorithm This algorithm works by replacing the page that will not be used for the longest period of time. ''' def OPT(size,pages): SIZE = size count = 0 memory = [] faults = 0 x = 0 for page in pages: if memory.count(page) == 0 and count < SIZE: # not present, but no replacement is necessary - page fault memory.append(page) count += 1 faults += 1 elif memory.count(page) == 0 and count == SIZE: # memory is full - replace the page using optimal algorithm # iterate through the existing pages and determine where # they will be used again in the future. # Evict the page that will not be used for the longest period of time. future = -1 for i in memory: # if this page won't be used again, evict it if pages[x:].count(i) == 0: evictedPage = i break else: index = pages[x:].index(i) if index > future: future = index evictedPage = i # evictedPage is the page to evict p = memory.index(evictedPage) memory.remove(evictedPage) memory.insert(p,page) faults += 1 elif memory.count(page) > 0: # page is present - do nothing pass # adjust the index so it now indicates the next page in the string x += 1 return faults def main(): pages = (7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1) size = int(sys.argv[1]) print 'FIFO', FIFO(size,pages), 'page faults.' print 'LRU', LRU(size,pages), 'page faults.' print 'OPT', OPT(size,pages), 'page faults.' if __name__ == "__main__": if len(sys.argv) != 2: print 'Usage: python paging.py [number of pages]' else: main()
Leave a reply