【操作系统】页面置换算法（最佳置换算法）（C语言实现）
（编码水平较菜，写博客也只是为了个人知识的总结和督促自己学习，如果有错误，希望可以指出）
1.页面置换算法：
2.具体的页面置换算法：
2.1 最佳置换算法：一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，那么如果发生缺页中断时，就将该页面换出，以便存放后面调入内存中的页面。
1.这是计算机操作系统（第四版）中的一个例子。系统首先为进程分配了三个物理块。上面一排数字是作业号。在转满三个物理块后，要访问2号作业，2号作业不在内存，所以会发生缺页中断，然后系统需要将2号作业调入内存，但是此时物理块已经装满。
2.依据最佳置换算法，会将7号页换出（0号页在2号页后第1个就会被访问，1号页在2号页后第10个会被访问，7号页在2号页后第14个会被访问，7号页在已经装入内存的作业中是未来最长时间不会被访问的，所以换出7号页）。
3.后面依次类推。
2.2 先进先出算法：如果发生缺页中断，需要换出一个页面的时候，总是选择最早进入内存的页面，即选择在内存中驻留时间最久的页面进行换出。
有点不清楚。。。。。就是每次发生缺页就将最早进入内存的页面换出，然后将刚调入的页面换入该物理块。
2.3 最近最久未使用（LRU）置换算法：LRU算法是缺页中断发生时选择最久未使用的页面进行换出。
这个算法其实也很好判断。分享一个小技巧。内存分配了k个物理块，发生缺页中断将要往内存调入某个页面的时候，在该页面往前面数K个物理块最前面的那个就会是要换出的，因为该页面最长时间未被使用过。（可能前面会有重复的页面，有几个重复的页面就再往前面多数几个）
例如：装入7，0，1，之后访问2号页面的时候会发生缺页中断。此时物理块有三个，2号页面前面有三个页面，最前面的是7号页面所以将7号页面换出。
2.4Clock置换算法（没有动图，不太形象，就不举例子了，如果不太清楚，可以私信我。）
2.4.1简单的Clock置换算法:将所有页面通过链接指针连接成一个循环队列。然后需要为每一个页面设置一个访问位。当某页被访问的时候，将访问位置为1。选择页面换出的时候，需要检查页面的访问位。如果是0，就将页面换出，如果是1，那么就将访问位置为0。
简单的Clock算法最多访问两轮：
最坏情况就是所有的页面访问位都是1，访问1轮之后，全部访问位都会被置为0，那么肯定会找到一个页面换出。
2.42改进型Clock算法:将所有页面通过链接指针连接成一个循环队列。然后需要为每一个页面设置一个访问位和一个修改位。访问位为0表示未访问过，为1表示访问过。修改位为0表示未修改过，为1表示修改过。
此时页面会有四种情况：
1.未被访问，未被修改，最佳淘汰。
2.未被访问，被修改过。
3.被访问过，未被修改。
4.被访问过，被修改过。
换出页面的时候：
1.寻找未被访问，未被修改的页面，不修改访问位。找到则换出，找不到进行第二步。
2.寻找未被访问，但是被修改过的页面。此时，每次扫描页面的时候，将所有访问位置为0。找到就返回，找不到就进行第三步。
3.重复第一次步骤，寻找未被访问，未被修改的页面，不修改访问位。找到则换出，找不到进行第四步。
4.重复第二步。寻找未被访问，但是被修改过的页面。此时一定可以找到。
也就是说，改进型Clock算法，最多扫描四轮队列。因为最坏的情况就是全部页面的访问位和修改位都是1的情况。在经过第二轮扫描之后页面的访问位已经都是0。所以第四轮一定可以找到一个页面换出。
3.最佳置换算法运行截图：
首先是前面三个装入，就省略掉了直接从第四次之后开始打印的。
4.代码
#include<stdio.h>
#include<stdlib.h>
#define MAX 20 // 定义作业序列的最大长度
#define num_alloacte 3 //内存分配给进程的物理块数 ， 也就是同一时刻最多有几个页面可以在内存中
int work_list [MAX]; //存储作业序列
int num; //存储要输入的序列的长度
int memory_alloacte [num_alloacte]; // 现在在进程中的页面序列
int current; // 记录已经分配的作业的下标
void input(){ //初始化作业序列 , 以及内存分配给进程的物理块数
printf("请输入作业的个数:");
scanf("%d",&num);
if (num > MAX) {
printf("序列过长");
return;
}
printf("请输入作业序列：\n");
for(int i = 0;i < num; i ++){
scanf("%d",&work_list[i]);
}
for(int i = 0;i < MAX ; i ++){
memory_alloacte[i] = -1;
}
for(int i = 0;i < num_alloacte;i ++){
memory_alloacte[i] = work_list[i];
current = i;
}
}
void print(int* work_list,int* memory_alloacte ){
printf("\t现在进程中的页面序列：");
for(int i = 0; i < num_alloacte; i ++){
printf("%3d\t",*(memory_alloacte+i));
}
printf("\t\t当前剩余的作业序列:");
for(int i = current+1; i < num;i ++){
printf("%3d",*(work_list+i));
}
printf("\n");
}
int judge(){
int temp [num_alloacte]; //赋值一个临时变量 记录此时物理框中的作业号
int count = num_alloacte; //记录临时变量物理框中还剩下的个数
for(int i = 0;i < num_alloacte; i ++){
temp[i] = memory_alloacte[i];
}
int cur = current + 1;
while (cur < num)
{
for (int i = 0; i < num_alloacte; i++)
{
if(work_list[cur] == temp[i]){ //如果剩下的工作序列中 现有内存中的作业还会调用的话， 就将其的值置为 -1
if(count == 1){ //此时内存中剩下的那个作业号肯定是最长时间没有调用过的，后者是以后再也不会调用
return i;
}
temp[i] = -1;
count --;
break;
}
}
cur ++;
}
//此时再来遍历这个 临时的物理块中作业号的 数组 ， 如果他的值不是 -1，就说明后面需要调用的作业中再也没有这个作业了，所以 就可以直接返回。
for(int i = 0;i < num_alloacte;i ++){
if(temp[i] != -1){
return i;
}
else
{
continue;
}
}
return 0;
}
void change(){
int index;
int flag = 0;
for (int i = current + 1; i < num; i++)
{
for (int j = 0; j < num_alloacte; j++) //来判断下一个作业是否已经在内存中
{
if(work_list[i] == memory_alloacte[j]){
flag = 1; //是的话让标志位置为1
break;
}
}
if(flag == 0){ //说明不在内存中，会出现页面中断。需要进行换页。
index = judge();
if(memory_alloacte[index] != work_list[i]){
memory_alloacte[index] = work_list[i];
}
current ++;
print(work_list,memory_alloacte);
}
else
{
flag = 0;
current ++;
print(work_list,memory_alloacte);
continue;
}
}
}
int main(){
input();
change();
system("pause");
}