要求：
在第1部分实验基础上实现进程的分页式内存分配和地址转换过程，并进一步实现请求分页式存储分配和地址转换过程。页面置换算法至少应实现先进先出（FIFO）、最近最久未使用（LRU）等算法。
建立1个位示图，用来模拟内存的分配情况，位示图的位数与设定的物理块个数相同。程序启动时可利用一组随机0和1填充位示图，表示内存已被占用情况。
1、创建进程时输入进程大小，并根据程序中设定的物理块大小为进程分配物理块，同时建立页表。例如，在上图基础上，若要建立一个大小为5000字节的进程，则：
- 计算出该进程共有“向上取整（5000/1024）=5”个页，需要占用5个内存块；
- 建立空的页表，即长度为5的一维整数数组；
- 从位示图中找出前5个“0”位在整个位示图中的位置号（即i字节j位为0，则该位的位置为8*i+j），并将这些号依次填入页表中，同时把前5个“0”改为“1”，以示对应内存块已经分配。
输入当前执行进程所要访问的逻辑地址，并将其转换成相应的物理地址。
进程退出时，根据其页表内容向位示图反向回填“0”。
扩充页表，将其变成支持请求和置换功能的二维页表（增加存在位等）。创建进程时可装入固定的前三页（或键盘输入初始装入页数，不同进程的装入个数可以不同），其余页装入到置换空间内（置换空间大小应为内存空间大小的1.5-2倍，对其还需建立独立的置换空间位示图）。
分别采用FIFO或LRU置换算法对地址转换过程中遇到的缺页现象进行页面置换，可将多次地址转换过程中所涉及到的页号视为进程的页面访问序列，从而计算置换次数和缺页率。
在完成第六步的基础上实现OPT的页面置换算法，并加以比较。
代码
import numpy as np
import math
class PCB(object):
def __init__(self, name, length):
self.name = name
self.length = length
self.start = 0
self.page = 0
self.pages_in_ram = 0
self.page_list_FIFO = [[], []] # 页表
self.page_list_LRU = [[], []]
self.ram_list_FIFO = [] # 在内存的进程的页表
self.ram_list_LRU = []
self.ram_FIFO = []
self.ram_LRU = []
self.visit = [] # 访问过的页
self.total = 0
self.missing_FIFO = 0
self.missing_LRU = 0
self.swap = []
def show(self):
print(self.ram_list_FIFO)
def create(p, ready, run):
global name_list
l = len(name_list)
name_list[p.name] = 1
if l == len(name_list):
print('不能创建同名进程！')
return
p.page = math.ceil(p.length / (block_size * 1024)) # 向上取整得页数
p.page_list_FIFO[0] = [0] * p.page
p.page_list_FIFO[1] = [0] * p.page
p.page_list_LRU[0] = [0] * p.page
p.page_list_LRU[1] = [0] * p.page
# print(p.page, p.page_list)
pages = int(input('进程共有'+str(p.page)+'页, '+'输入装入内存的页数：'))
p.pages_in_ram = pages
global ram
global switch
c = 0
if ram.shape[0] * ram.shape[1] - np.count_nonzero(ram) >= pages: # 空闲空间比用户要求的页表大
for i in range(ram.shape[0]):
for j in range(ram.shape[1]):
if ram[i][j] == 0:
ram[i][j] = 1
p.ram_FIFO.append(8 * i + j)
p.ram_LRU.append(8 * i + j)
c += 1 # 空出pages页给进程
if c >= pages:
break
if c >= pages:
break
c = 0
for i in range(switch.shape[0]):
for j in range(switch.shape[1]):
if switch[i][j] == 0:
p.page_list_LRU[0][c] = 8 * i + j # 将进程存入置换空间
p.page_list_FIFO[0][c] = 8 * i + j
p.swap.append(8 * i + j)
switch[i][j] = 1
c += 1
if c >= p.page:
break
if c >= p.page:
break
ready_to_run(ready, run)
print(p.page_list_FIFO)
else:
print('剩余内容不足!剩余块数为:' + str(ram.shape[0] * ram.shape[1] - np.count_nonzero(ram)))
print('...正在将剩余内存分配给该进程...')
def ready_to_run(ready, run):
# print(type(run))
if not run and ready:
p = ready.pop(0)
# print(type(p))
run.append(p)
# print(ready, run)
def block(ready, blo, run):
if run:
pro = run.pop()
blo.append(pro)
ready_to_run(ready, run)
else:
print('没有可以阻塞的进程！')
def times_over(run, ready):
if run:
pro = run.pop()
ready.append(pro)
ready_to_run(ready, run)
else:
print('没有正在运行的进程！')
def wake_up(blo, ready, run): # block[0]->ready
if blo:
pro = blo.pop(0)
ready.append(pro)
ready_to_run(ready, run)
else:
print('没有可唤醒的进程！')
def address_switch(log, p):
global block_size
page_num = log // (block_size * 1024) # 访问的页号
if page_num < len(p.page_list_FIFO[0]): # log // (block_size * 1024)为页号
p.total += 1
# if p.page_list[1][page_num]: # 如果在内存就转换地址
if len(p.ram_list_FIFO) < p.pages_in_ram: # 如果内存没满，ram列表不为空
if page_num not in p.ram_list_FIFO: # 不在内存
p.missing_FIFO += 1
p.ram_list_FIFO.append(page_num)
p.page_list_FIFO[0][page_num] = p.ram_FIFO.pop() # 将属于进程的内存分一块给访问的页
p.page_list_FIFO[1][page_num] = 1
if page_num in p.ram_list_LRU: # 如果在内存，更新位置
# print('!!!!')
i = p.ram_list_LRU.index(page_num)
p.ram_list_LRU.pop(i)
p.ram_list_LRU.append(page_num)
if page_num not in p.ram_list_LRU:
p.missing_LRU += 1
p.ram_list_LRU.append(page_num)
p.page_list_LRU[0][page_num] = p.ram_LRU.pop()
p.page_list_LRU[1][page_num] = 1
else:
if page_num not in p.ram_list_FIFO:
p.missing_FIFO += 1
first = p.ram_list_FIFO.pop(0) # 先进的页号
p.ram_list_FIFO.append(page_num)
# 交换出去的和进来的页数在内存和置换空间的位置
p.page_list_FIFO[0][page_num], p.page_list_FIFO[0][first] = p.page_list_FIFO[0][first], \
p.page_list_FIFO[0][page_num]
p.page_list_FIFO[1][page_num] = 1
p.page_list_FIFO[1][first] = 0
if page_num in p.ram_list_LRU: # 如果当前页数在内存里
i = p.ram_list_LRU.index(page_num)
p.ram_list_LRU.pop(i)
p.ram_list_LRU.append(page_num)
else:
p.missing_LRU += 1
before = p.ram_list_LRU.pop(0)
# print('before:', before)
p.ram_list_LRU.append(page_num)
# 交换出去的和进来的页数在内存和置换空间的位置
p.page_list_LRU[0][page_num], p.page_list_LRU[0][before] = p.page_list_LRU[0][before], \
p.page_list_LRU[0][page_num]
p.page_list_LRU[1][page_num] = 1
p.page_list_LRU[1][before] = 0
p.visit.append(page_num)
page_FIFO = p.page_list_FIFO[0][page_num]
page_add_FIFO = log % (block_size * 1024)
page_LRU = p.page_list_LRU[0][page_num]
page_add_LRU = log % (block_size * 1024)
# print(page_FIFO, page_add_FIFO)
print('FIFO:', p.page_list_FIFO)
print('FIFO:', p.ram_list_FIFO)
print('FIFO下的物理地址:' + str(hex(page_FIFO * block_size * 1024 + page_add_FIFO)))
print('FIFO缺页率:' + str(p.missing_FIFO/p.total))
print('LRU:', p.page_list_LRU)
print('LRU:', p.ram_list_LRU)
print('LRU下的物理地址:' + str(hex(page_LRU * block_size * 1024 + page_add_LRU)))
print('LRU缺页率:' + str(p.missing_LRU / p.total))
print('访问列表:', p.visit)
# print('OPT缺页率:', opt(p))
else:
print('地址越界！')
def opt(p):
farthest = {}
for i in range(p.page):
farthest[i] = 0
ram_list = p.visit[:p.pages_in_ram]
missing = p.pages_in_ram
for i in range(p.pages_in_ram, len(p.visit)):
# print(ram_list)
for k in range(p.page):
try:
farthest[k] = p.visit.index(k, i+1, len(p.visit)-1)
except ValueError:
farthest[k] = 1000
now = p.visit[i]
# print(now)
# print(farthest)
if now not in ram_list:
# print('缺页！')
missing += 1
far = max(ram_list, key=lambda x: farthest[x]) # 找到最远的页数
ind = ram_list.index(far)
ram_list[ind] = now # 将最远的页数替换成现在访问的页数
return missing / p.total
def quit(ready, run):
p = run.pop()
global name_list
del name_list[p.name]
for k in range(len(p.page_list_FIFO[0])):
i = p.page_list_FIFO[0][k] // 8
j = p.page_list_FIFO[0][k] % 8
if p.page_list_FIFO[1][k] == 1:
global ram
ram[i][j] = 0 # 退出时将在内存的页在位示图置零
else:
global switch
switch[i][j] = 0 # 不再内存的页在置换空间中置零
i = p.page_list_LRU[0][k] // 8
j = p.page_list_LRU[0][k] % 8
if p.page_list_LRU[1][k] == 1:
ram[i][j] = 0 # 退出时将在内存的页在位示图置零
else:
switch[i][j] = 0 # 不再内存的页在置换空间中置零
for k in range(len(p.swap)): # 统一归还置换空间的位置
i = p.swap[k] // 8
j = p.swap[k] % 8
switch[i][j] = 0
ready_to_run(ready, run)
if __name__ == '__main__':
run = []
ready = []
blocked = []
while True:
try:
ram_size = int(input("输入内存(K):"))
block_size = int(input("块的大小(K):"))
break
except ValueError:
print('输入错误！请重新输入！')
continue
ram = np.random.randint(0, 2, (ram_size // (block_size * 8), 8), dtype=np.int8) # 位示图
switch = np.random.randint(0, 2, size=[(ram_size * 2) // (block_size * 8), 8], dtype=np.int8)
name_list = {}
print("0.输出进程")
print("1.创建进程")
print("2.进入阻塞状态")
print("3.时间片完")
print("4.唤醒")
print("5.结束进程")
print("6.显示位示图")
print("7.地址转换")
print('8.OPT缺页率')
print("9.帮助")
print("10.退出")
while True:
try:
a = int(input())
except ValueError:
print('输入错误！请重新输入！')
continue
if a == 0:
pass
if a == 1:
pcb_name, pcb_size = input("输入进程的名字及内存(字节):").strip().split()
pcb_size = int(pcb_size)
# print(ram)
pcb = PCB(pcb_name, pcb_size)
ready.append(pcb)
create(pcb, ready, run)
if a == 2:
block(ready, blocked, run)
if a == 3:
times_over(run, ready)
if a == 4:
wake_up(blocked, ready, run)
if a == 5:
quit(ready, run)
if a == 6:
print('内存位示图:\n', ram)
print('置换空间位示图:\n', switch)
if a == 7:
pcb = run[0]
log = int('0x' + input("输入逻辑地址:"), 16)
address_switch(log, pcb)
if a == 8:
pcb = run[0]
print(opt(pcb))
if a == 9:
print("0.输出进程")
print("1.创建进程")
print("2.进入阻塞状态")
print("3.时间片完")
print("4.唤醒")
print("5.结束进程")
print("6.显示位示图")
print("7.地址转换")
print('8.OPT缺页率')
print("9.帮助")
print("10.退出")
if a == 10:
exit(0)
