计算机操作系统实验之页⾯置换算法（C语⾔）
计算机操作系统实验之页⾯置换算法（C语⾔）
实验⽬的
1、了解内存分页管理策略
只要你说你爱我22、掌握⼀些基本的页⾯置换算法
实验内容与基本要求
⽤C，C++等语⾔编写程序，实现OPT、FIFO、LRU置换算法
页⾯置换算法的基本内容
页⾯置换算法是在当进程运⾏过程中，若其要访问的页⾯不在内存且内存已满时，要决定将哪个页⾯换出的算法。常见的页⾯置换算法包括最佳置换、先进先出置换、最近最久未使⽤置换和Clock置换等。本次的实验实现的算法包括最佳置换算法（OPT）、先进先出置换算法（FIFO）和最近最久未使⽤算法（LRU）。
ritual
页⾯置换算法涉及到⼀些概念如下：
百衲衣缺页率：当需要访问的页⾯不在内存时称为缺页，此时需要将页⾯调⼊内存。缺页率就是要访问的页⾯不在内存中的概率。因此缺页率=缺页次数/要访问的页⾯总数。需要注意的是，缺页的时候不⼀定需要进⾏页⾯置换（如果内存还没满，直接将页⾯调⼊内存即可）。
置换率：置换就是将旧页⾯调出内存，新页⾯调进内存，即新页⾯代替旧页⾯的过程。置换率就是需要进⾏页⾯置换的概率。所以置换率=置换次数/要访问的页⾯总数。
四级英语作文预测>快速去痘的方法命中率：就是要访问的页⾯恰好在内存中的概率。可以发现（缺页率+命中率=1）。
最佳置换算法
最佳置换算法，就是所选择内存中以后永远不再使⽤，或者是在未来最长的⼀段时间内不再被访问的页⾯来换出。
⽤这种算法可以保证获得最低的缺页率，最低的置换次数，因此效率最⾼。然⽽在实际情况中，我们是⽆法知道哪个页⾯是未来最长时间内不再被访问的，所以实际上它是⽆法实现的。
先进先出置换算法
先进先出置换算法，就是选择内存中最先进⼊内存，在内存中呆的最久的页⾯来换出。它实现简单，但是效率不⾼。天津培训网
atu
最近最久未使⽤算法
最近最久未使⽤算法，是选择当前内存中，最久没有被访问的页⾯来换出。它是希望通过过去页⾯访问的情况，来预测未来页⾯的访问情况，但是页⾯过去与未来的⾛向之间并没有必然的联系，因此它的效率也不是⼗分⾼。
实现思路
⽆论采⽤哪个算法，当进程需要访问⼀个页⾯时，存在三种情况：
1.页⾯已经在内存中
2.页⾯不在内存中，但是此时内存还未满ruby
3.页⾯不在内存中，且此时内存已满，需要把页⾯换出
不同算法的区别主要是决定换出哪个页⾯
最佳置换算法中，被换出的算法是在最长未来时间内不再被访问的页⾯。也就是说，需要计算出当前内存中页⾯的下⼀次访问位置，哪个页⾯的下⼀次访问位置最远，就将它换出。因此需要⼀个数组额外记录下次访问位置，每当访问完⼀个页⾯（不管这个页⾯是新换⼊的，还是早就在内存中的），都需要遍历剩下的页⾯号引⽤串，更新这个数组。
先进先出置换算法⽐较简单，⽤⼀个变量记录当前内存中最先进⼊页⾯的下标。由于页⾯都是按数组下标顺序保存的，因此每访问⼀个页⾯，该变量就加⼀。等变量等于数组长度时，再重新归零即可。
最近最久未使⽤算法有两种思路：1.与最佳置换算法类似，设置⼀个时间数组，记录从内存中页⾯上次访问⾄今的时间，哪个页⾯的时间最长则将它换出。如果要访问的页⾯已在内存中，则时间归零。当每次发起⼀个访问请求，则所有页⾯访问时间加⼀，更新该数组。2.⽤数组模拟队列的结构，队列头出队列尾⼊，每当需要访问新的页⾯时，就将数组内的数据前移⼀位，新页⾯加⼊数组最后。如果要访问的页⾯已在内存中，则⽤⼀个临时变量记录该页⾯，然后从该页⾯起的数据前移⼀位，把该页⾯加⼊数组最后（课本上说是⽤栈的结构，但是严格上来说，栈只允许⼀端出⼊。因此按照课本上的功能描述，实际应该采⽤的结构仍是队列）
流程图
程序总流程图
OPT算法流程图
FIFO算法流程图
LRU算法流程图
全部代码
达利通代码
//
// main.c
member
// pageReplacement
//
// Created by Apple on 2019/11/12.
// Copyright © 2019 Yao YongXin. All rights rerved. //
#include<stdio.h>
//初始化队列
void initializeList(int list[],int number){
