【操作系统】页面置换算法（最佳置换算法）（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.最佳置换算法运行截图：

首先是前面三个装入，就省略掉了直接从第四次之后开始打印的。

#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");
}