操作系统课程设计——页面置换算法模拟实现

import time import sys import random class Page: def __init__(self, index: int): self.__index = index self.__pv = 0 self.__last_visit = float(time.time()) # 时间戳 self.__last_put = -1 # 上次装入时间 pass @property def pv(self): ''' 访问次数。 ''' return self.__pv @property def last_visit(self): ''' 访问时间。 ''' return self.__last_visit def visit(self): self.__pv += 1 time.sleep(0.001) self.__last_visit = float(time.time()) # 时间戳 @property def index(self): ''' 页号。 ''' return self.__index def set_last_put(self): self.__last_put = float(time.time()) pass @property def last_put(self): return self.__last_put class Mem: ''' 为进程申请的独立内存空间。 ''' def __init__(self, size: int, func): ''' 初始化内存。 参数 -------- size : int 以页为单位的内存容量。 func 页面置换算法，必需传入名为page、blocks的参数，并返回一个页。 ''' self.__blocks = [] self.__max_size = size self.__func = func self.__find = 0 self.__total = 0 pass @property def max(self): ''' 以页为单位的内存容量。 ''' return self.__max_size @property def size(self): ''' 已使用页数。 ''' return len(self.__blocks) def print_mem(self): ''' 打印占页情况。 ''' print('[ ', end='') first = True length = len(self.__blocks) for i in range(0, self.__max_size): if i < length: if first: print(str(self.__blocks[i].index).zfill(2), end='') first = False else: print('\t | ' + str(self.__blocks[i].index).zfill(2), end='') pass else: if first: print(' ', end='') first = False else: print('\t | '+'-', end='') pass print('\t]') pass def get(self, index): ''' 查看已经使用的页。 ''' if index > 0 and index < self.__size: return self.__blocks[index] else: return None pass def push(self, page: Page): ''' 装入页面。 参数 -------- page : Page 待装入页面。 ''' try: for i in self.__blocks: if page.index == i.index: i.visit() self.__find += 1 self.__total += 1 return index = None if self.size < self.max: self.__blocks.append(page) self.__total += 1 page.visit() page.set_last_put() return else: rem = self.__func(page=page, blocks=self.__blocks) if rem is not None: for i in self.__blocks: if i.index is rem.index: index = self.__blocks.index(i) break pass if index is not None: self.__blocks[index] = page self.__total += 1 page.visit() page.set_last_put() pass except BaseException as e: print(repr(e)) pass else: pass pass @property def pfr(self): ret = 1-self.hr # 缺页率 return ret @property def hr(self): ret = self.__find/self.__total # 命中率 return ret all_pages = [] all_indexs = [] now_index = 0 def run(func, size: int, page_count: int): try: global all_pages global now_index all_pages = [] now_index = 0 for i in range(0, page_count): all_pages.append(Page(i)) # 初始化内存 pass mem = Mem(size, func) for index in all_indexs: now_index += 1 # 为Opt服务 print('('+str(now_index).zfill(3)+')\t: ',end='') i = all_pages[index] mem.push(i) # 初始化模拟进程 print(str(i.index).zfill(2), end='\t--> ') mem.print_mem() pass print('-'*16) print('Hit rate: ' + str(mem.hr)) print('Page fault rate: '+str(mem.pfr)) print('-'*16+'\n') pass except Exception as e: e.print_exc() pass else: pass pass def LRU(page: Page, blocks: list): ''' 最久未使用。 ''' ret = None min = sys.float_info.max for i in blocks: if i != None: if i.last_visit < min: ret = i min = i.last_visit return ret def FIFO(page: Page, blocks: list): ''' 先进先出。 ''' ret = None min = sys.float_info.max for i in blocks: if i != None: if i.last_put < min: ret = i min = i.last_put return ret def LFU(page: Page, blocks: list): ''' 最少使用。 ''' ret = None min = sys.maxsize for i in blocks: if i != None: if i.pv < min: ret = i min = i.pv return ret def Opt(page: Page, blocks: list): ''' 最佳。 ''' global all_pages global now_index ret = None max = 0 for i in blocks: if i != None: d = 0 for future in range(now_index, len(all_indexs)): if all_indexs[future] == i.index: break d += 1 pass if d > max: ret = i max = d return ret def __main__(): page_count=10 global all_indexs for i in range(0, 30): # 进程所需页号 all_indexs.append(random.randint(1, page_count)-1) pass print('-'*16+'\n'+'LRU:') run(LRU, 4, page_count) print('-'*16+'\n'+'FIFO:') run(FIFO, 4, page_count) print('-'*16+'\n'+'LFU:') run(LFU, 4, page_count) print('-'*16+'\n'+'Opt:') run(Opt, 4, page_count) pass __main__()