FIFO页面置换算法

FIFO页面置换算法 1 假设每个页面中可存放10条指令 分配给作业的内存块数为4 2 用C语言模拟一个作业的执行过程 该作业共有320条指令 即它的地址空间为3 2页 目前它的所有页都还未调入内存 在模拟过程中 如果所访问的指令已在内存 则显示其物理地址 并转下一条指令 如果所访问的指令还未装入内存 则发生缺 页 此时需记录缺页的次数 并将相应页调入内存 如果4个内存块均已装入该作业 则需进行页面置换 最后显示其物理地址 并转下一条指令 在所有320指令执行完毕后 请计算并显示作业运行过程中发生的缺页率 3 置换算法 先进先出FIFO算法 include include include define N 4 define size 320 typedef struct Block int block num 块号 int page num 页号 struct Block next BLOCK BLOCKLIST typedef struct instruct 指令数据结构 int address 指令地址 int page num 指令所存的页号 INSTRUCTION INSTRUCTIONLIST INSTRUCTION instructions size 定义320条指令 BLOCKLIST block head front in block head指向块链表的头 front in指向最老的页面 即被淘汰的页面 int diseffect 0 缺页次数 int blockSize 0 标记块是否满 初始化指令 void Init Instructions for int i 0 i 320 i instructions i address rand 320 for int k 0 k 320 k instructions k page num int instructions k address 10 初始化块 循环链表 BLOCKLIST Init block BLOCKLIST head BLOCKLIST malloc sizeof BLOCK BLOCKLIST p for int i 1 inext BLOCKLIST malloc sizeof BLOCK p p next p block num i p page num 1 p next head return head 显示块内的数据 void display INSTRUCTION instructions BLOCKLIST p block head printf The new page page num d address d n instructions page num instructions address printf block num page num n do printf 2d 10d n p block num p page num p p next while p block head 显示页面对应的物理地址 void show physical address BLOCKLIST printf physical address address p block num 1024 instructions address 10 printf d n n address 查找该页是否存在 存在不要置换 否则置换 int Find page in block INSTRUCTION instructions BLOCKLIST do if p page num instructions page num return 1 p p next while p block head return 0 用于将四个块填满 void loadpage INSTRUCTION instructions BLOCKLIST p p block head while p page num 1 p p next p page num instructions page num blockSize 按FIFO置换页面 void replace page INSTRUCTION instructions BLOCKLIST p front in front in front in next void main BLOCKLIST p Init Instructions block head Init block front in block head for int i 0 i size i if Find page in block instructions i p display instructions i show physical address p instructions i getchar continue else if blockSize N diseffect loadpage instructions i display instructions i else diseffect replace page instructions i p display instruc