【操作系统】页面置换算法（最佳置换算法）（C语言实现）

【操作系统】页面置换算法（最佳置换算法）（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;// 记录已经分配的作业的下标voidinput(){//初始化作业序列  , 以及内存分配给进程的物理块数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;}}voidprint(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");}intjudge(){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;}}return0;}voidchange(){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;//是的话让标志位置为1break;}}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;}}}intmain(){input();change();system("pause");}