$命中率=1-\frac{页面失效次数}{页地址流长度}$

页面调度算法

• LRU：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。
• FIFO：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。
• LFU：总是淘汰最近一段时间内使用次数很少的页面。
• Opt：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。

代码

总共10页。四个块，程序要30次调用页，的页号序列随机在指定。

# -*- coding: utf-8 -*-

# 运行python3.7.8
import time
import sys
import random
from multiprocessing import *

class Page:
    '''
    页面。
    '''

    def __init__(self, index: int):
        '''
        初始化页面。

        参数
        --------
        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__()

运行结果

----------------
LRU:
(001)	: 07	--> [ 07	 | -	 | -	 | -	]
(002)	: 05	--> [ 07	 | 05	 | -	 | -	]
(003)	: 03	--> [ 07	 | 05	 | 03	 | -	]
(004)	: 00	--> [ 07	 | 05	 | 03	 | 00	]
(005)	: 06	--> [ 06	 | 05	 | 03	 | 00	]
(006)	: 08	--> [ 06	 | 08	 | 03	 | 00	]
(007)	: 09	--> [ 06	 | 08	 | 09	 | 00	]
(008)	: 01	--> [ 06	 | 08	 | 09	 | 01	]
(009)	: 05	--> [ 05	 | 08	 | 09	 | 01	]
(010)	: 01	--> [ 05	 | 08	 | 09	 | 01	]
(011)	: 00	--> [ 05	 | 00	 | 09	 | 01	]
(012)	: 03	--> [ 05	 | 00	 | 03	 | 01	]
(013)	: 05	--> [ 05	 | 00	 | 03	 | 01	]
(014)	: 09	--> [ 05	 | 00	 | 03	 | 09	]
(015)	: 08	--> [ 05	 | 08	 | 03	 | 09	]
(016)	: 04	--> [ 05	 | 08	 | 04	 | 09	]
(017)	: 09	--> [ 05	 | 08	 | 04	 | 09	]
(018)	: 01	--> [ 01	 | 08	 | 04	 | 09	]
(019)	: 06	--> [ 01	 | 06	 | 04	 | 09	]
(020)	: 02	--> [ 01	 | 06	 | 02	 | 09	]
(021)	: 06	--> [ 01	 | 06	 | 02	 | 09	]
(022)	: 03	--> [ 01	 | 06	 | 02	 | 03	]
(023)	: 00	--> [ 00	 | 06	 | 02	 | 03	]
(024)	: 09	--> [ 00	 | 06	 | 09	 | 03	]
(025)	: 05	--> [ 00	 | 05	 | 09	 | 03	]
(026)	: 03	--> [ 00	 | 05	 | 09	 | 03	]
(027)	: 05	--> [ 00	 | 05	 | 09	 | 03	]
(028)	: 08	--> [ 08	 | 05	 | 09	 | 03	]
(029)	: 02	--> [ 08	 | 05	 | 02	 | 03	]
(030)	: 06	--> [ 08	 | 05	 | 02	 | 06	]
----------------
Hit rate: 0.2
Page fault rate: 0.8
----------------

----------------
FIFO:
(001)	: 07	--> [ 07	 | -	 | -	 | -	]
(002)	: 05	--> [ 07	 | 05	 | -	 | -	]
(003)	: 03	--> [ 07	 | 05	 | 03	 | -	]
(004)	: 00	--> [ 07	 | 05	 | 03	 | 00	]
(005)	: 06	--> [ 06	 | 05	 | 03	 | 00	]
(006)	: 08	--> [ 06	 | 08	 | 03	 | 00	]
(007)	: 09	--> [ 06	 | 08	 | 09	 | 00	]
(008)	: 01	--> [ 06	 | 08	 | 09	 | 01	]
(009)	: 05	--> [ 05	 | 08	 | 09	 | 01	]
(010)	: 01	--> [ 05	 | 08	 | 09	 | 01	]
(011)	: 00	--> [ 05	 | 00	 | 09	 | 01	]
(012)	: 03	--> [ 05	 | 00	 | 03	 | 01	]
(013)	: 05	--> [ 05	 | 00	 | 03	 | 01	]
(014)	: 09	--> [ 05	 | 00	 | 03	 | 09	]
(015)	: 08	--> [ 08	 | 00	 | 03	 | 09	]
(016)	: 04	--> [ 08	 | 04	 | 03	 | 09	]
(017)	: 09	--> [ 08	 | 04	 | 03	 | 09	]
(018)	: 01	--> [ 08	 | 04	 | 01	 | 09	]
(019)	: 06	--> [ 08	 | 04	 | 01	 | 06	]
(020)	: 02	--> [ 02	 | 04	 | 01	 | 06	]
(021)	: 06	--> [ 02	 | 04	 | 01	 | 06	]
(022)	: 03	--> [ 02	 | 03	 | 01	 | 06	]
(023)	: 00	--> [ 02	 | 03	 | 00	 | 06	]
(024)	: 09	--> [ 02	 | 03	 | 00	 | 09	]
(025)	: 05	--> [ 05	 | 03	 | 00	 | 09	]
(026)	: 03	--> [ 05	 | 03	 | 00	 | 09	]
(027)	: 05	--> [ 05	 | 03	 | 00	 | 09	]
(028)	: 08	--> [ 05	 | 08	 | 00	 | 09	]
(029)	: 02	--> [ 05	 | 08	 | 02	 | 09	]
(030)	: 06	--> [ 05	 | 08	 | 02	 | 06	]
----------------
Hit rate: 0.2
Page fault rate: 0.8
----------------

----------------
LFU:
(001)	: 07	--> [ 07	 | -	 | -	 | -	]
(002)	: 05	--> [ 07	 | 05	 | -	 | -	]
(003)	: 03	--> [ 07	 | 05	 | 03	 | -	]
(004)	: 00	--> [ 07	 | 05	 | 03	 | 00	]
(005)	: 06	--> [ 06	 | 05	 | 03	 | 00	]
(006)	: 08	--> [ 08	 | 05	 | 03	 | 00	]
(007)	: 09	--> [ 09	 | 05	 | 03	 | 00	]
(008)	: 01	--> [ 01	 | 05	 | 03	 | 00	]
(009)	: 05	--> [ 01	 | 05	 | 03	 | 00	]
(010)	: 01	--> [ 01	 | 05	 | 03	 | 00	]
(011)	: 00	--> [ 01	 | 05	 | 03	 | 00	]
(012)	: 03	--> [ 01	 | 05	 | 03	 | 00	]
(013)	: 05	--> [ 01	 | 05	 | 03	 | 00	]
(014)	: 09	--> [ 09	 | 05	 | 03	 | 00	]
(015)	: 08	--> [ 08	 | 05	 | 03	 | 00	]
(016)	: 04	--> [ 04	 | 05	 | 03	 | 00	]
(017)	: 09	--> [ 09	 | 05	 | 03	 | 00	]
(018)	: 01	--> [ 09	 | 05	 | 01	 | 00	]
(019)	: 06	--> [ 09	 | 05	 | 01	 | 06	]
(020)	: 02	--> [ 09	 | 05	 | 01	 | 02	]
(021)	: 06	--> [ 09	 | 05	 | 01	 | 06	]
(022)	: 03	--> [ 03	 | 05	 | 01	 | 06	]
(023)	: 00	--> [ 00	 | 05	 | 01	 | 06	]
(024)	: 09	--> [ 09	 | 05	 | 01	 | 06	]
(025)	: 05	--> [ 09	 | 05	 | 01	 | 06	]
(026)	: 03	--> [ 09	 | 05	 | 03	 | 06	]
(027)	: 05	--> [ 09	 | 05	 | 03	 | 06	]
(028)	: 08	--> [ 09	 | 05	 | 03	 | 08	]
(029)	: 02	--> [ 09	 | 05	 | 03	 | 02	]
(030)	: 06	--> [ 09	 | 05	 | 03	 | 06	]
----------------
Hit rate: 0.23333333333333334
Page fault rate: 0.7666666666666666
----------------

----------------
Opt:
(001)	: 07	--> [ 07	 | -	 | -	 | -	]
(002)	: 05	--> [ 07	 | 05	 | -	 | -	]
(003)	: 03	--> [ 07	 | 05	 | 03	 | -	]
(004)	: 00	--> [ 07	 | 05	 | 03	 | 00	]
(005)	: 06	--> [ 06	 | 05	 | 03	 | 00	]
(006)	: 08	--> [ 08	 | 05	 | 03	 | 00	]
(007)	: 09	--> [ 09	 | 05	 | 03	 | 00	]
(008)	: 01	--> [ 01	 | 05	 | 03	 | 00	]
(009)	: 05	--> [ 01	 | 05	 | 03	 | 00	]
(010)	: 01	--> [ 01	 | 05	 | 03	 | 00	]
(011)	: 00	--> [ 01	 | 05	 | 03	 | 00	]
(012)	: 03	--> [ 01	 | 05	 | 03	 | 00	]
(013)	: 05	--> [ 01	 | 05	 | 03	 | 00	]
(014)	: 09	--> [ 01	 | 09	 | 03	 | 00	]
(015)	: 08	--> [ 01	 | 09	 | 03	 | 08	]
(016)	: 04	--> [ 01	 | 09	 | 03	 | 04	]
(017)	: 09	--> [ 01	 | 09	 | 03	 | 04	]
(018)	: 01	--> [ 01	 | 09	 | 03	 | 04	]
(019)	: 06	--> [ 06	 | 09	 | 03	 | 04	]
(020)	: 02	--> [ 06	 | 09	 | 03	 | 02	]
(021)	: 06	--> [ 06	 | 09	 | 03	 | 02	]
(022)	: 03	--> [ 06	 | 09	 | 03	 | 02	]
(023)	: 00	--> [ 00	 | 09	 | 03	 | 02	]
(024)	: 09	--> [ 00	 | 09	 | 03	 | 02	]
(025)	: 05	--> [ 05	 | 09	 | 03	 | 02	]
(026)	: 03	--> [ 05	 | 09	 | 03	 | 02	]
(027)	: 05	--> [ 05	 | 09	 | 03	 | 02	]
(028)	: 08	--> [ 08	 | 09	 | 03	 | 02	]
(029)	: 02	--> [ 08	 | 09	 | 03	 | 02	]
(030)	: 06	--> [ 08	 | 09	 | 03	 | 02	]
----------------
Hit rate: 0.4482758620689655
Page fault rate: 0.5517241379310345
----------------