计算机操作系统实验之页面置换算法（C语言）

àì夳堔傛蜴生んèń 2023-06-20 06:19 32阅读 0赞

### 计算机操作系统实验之页面置换算法（C语言） ###

*   *   *  实验目的
         *  实验内容与基本要求
         *  页面置换算法的基本内容
         *   *  最佳置换算法
             *  先进先出置换算法
             *  最近最久未使用算法
         *  实现思路
         *  流程图
         *   *  程序总流程图
             *  OPT算法流程图
             *  FIFO算法流程图
             *  LRU算法流程图
         *  全部代码
         *   *  代码
             *  实验截图

### 实验目的 ###

1、了解内存分页管理策略

2、掌握一些基本的页面置换算法

### 实验内容与基本要求 ###

用C，C++等语言编写程序，实现OPT、FIFO、LRU置换算法

### 页面置换算法的基本内容 ###

页面置换算法是在当进程运行过程中，若其要访问的页面不在内存且内存已满时，要决定将哪个页面换出的算法。常见的页面置换算法包括最佳置换、先进先出置换、最近最久未使用置换和Clock置换等。本次的实验实现的算法包括最佳置换算法（OPT）、先进先出置换算法（FIFO）和最近最久未使用算法（LRU）。

页面置换算法涉及到一些概念如下：

*  缺页率：当需要访问的页面不在内存时称为缺页，此时需要将页面调入内存。缺页率就是要访问的页面不在内存中的概率。因此缺页率=缺页次数/要访问的页面总数。需要注意的是，缺页的时候不一定需要进行页面置换（如果内存还没满，直接将页面调入内存即可）。
 *  置换率：置换就是将旧页面调出内存，新页面调进内存，即新页面代替旧页面的过程。置换率就是需要进行页面置换的概率。所以置换率=置换次数/要访问的页面总数。
 *  命中率：就是要访问的页面恰好在内存中的概率。可以发现（缺页率+命中率=1）。

#### 最佳置换算法 ####

最佳置换算法，就是所选择内存中以后永远不再使用，或者是在未来最长的一段时间内不再被访问的页面来换出。

![img\_1][img_1]  
用这种算法可以保证获得最低的缺页率，最低的置换次数，因此效率最高。然而在实际情况中，我们是无法知道哪个页面是未来最长时间内不再被访问的，所以实际上它是无法实现的。

#### 先进先出置换算法 ####

先进先出置换算法，就是选择内存中最先进入内存，在内存中呆的最久的页面来换出。它实现简单，但是效率不高。  
![img\_2][img_2]  
![img\_3][img_3]

#### 最近最久未使用算法 ####

最近最久未使用算法，是选择当前内存中，最久没有被访问的页面来换出。它是希望通过过去页面访问的情况，来预测未来页面的访问情况，但是页面过去与未来的走向之间并没有必然的联系，因此它的效率也不是十分高。  
![img\_4][img_4]  
![img\_5][img_5]

### 实现思路 ###

无论采用哪个算法，当进程需要访问一个页面时，存在三种情况：

1.页面已经在内存中

2.页面不在内存中，但是此时内存还未满

3.页面不在内存中，且此时内存已满，需要把页面换出

不同算法的区别主要是决定换出哪个页面

![img\_6][img_6]

最佳置换算法中，被换出的算法是在最长未来时间内不再被访问的页面。也就是说，需要计算出当前内存中页面的下一次访问位置，哪个页面的下一次访问位置最远，就将它换出。因此需要一个数组额外记录下次访问位置，每当访问完一个页面（不管这个页面是新换入的，还是早就在内存中的），都需要遍历剩下的页面号引用串，更新这个数组。

先进先出置换算法比较简单，用一个变量记录当前内存中最先进入页面的下标。由于页面都是按数组下标顺序保存的，因此每访问一个页面，该变量就加一。等变量等于数组长度时，再重新归零即可。

最近最久未使用算法有两种思路：1.与最佳置换算法类似，设置一个时间数组，记录从内存中页面上次访问至今的时间，哪个页面的时间最长则将它换出。如果要访问的页面已在内存中，则时间归零。当每次发起一个访问请求，则所有页面访问时间加一，更新该数组。2.用数组模拟队列的结构，队列头出队列尾入，每当需要访问新的页面时，就将数组内的数据前移一位，新页面加入数组最后。如果要访问的页面已在内存中，则用一个临时变量记录该页面，然后从该页面起的数据前移一位，把该页面加入数组最后（课本上说是用栈的结构，但是严格上来说，栈只允许一端出入。因此按照课本上的功能描述，实际应该采用的结构仍是队列）

### 流程图 ###

#### 程序总流程图 ####

![总流程图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70]

#### OPT算法流程图 ####

![OPT][]

#### FIFO算法流程图 ####

![FIFO][]

#### LRU算法流程图 ####

![LRU][]

### 全部代码 ###

#### 代码 ####

//
    // main.c
    // pageReplacement
    //
    // Created by Apple on 2019/11/12.
    // Copyright © 2019 Yao YongXin. All rights reserved.
    //
    
    #include <stdio.h>
    
    //初始化队列
    void initializeList(int list[],int number){ 
        for (int i = 0; i < number; i ++) { 
            list[i] = -1;
        }
    }
    //展示队列状态
    void showList(int list[], int number){ 
        for (int i = 0; i < number; i ++) { 
            printf("%2d",list[i]);
        }
        printf("\n");
    }
    
    //展示当前内存状态
    void showMemoryList(int list[],int phyBlockNum){ 
        for (int i = 0; i < phyBlockNum; i ++) { 
            if (list[i] == -1) { 
                break;
            }
            printf(" |%d|",list[i]);
        }
        printf("\n");
    }
    
    void informationCount(int missingCount,int replaceCount,int pageNum){ 
        printf("缺页次数:%d 缺页率:%d/%d\n",missingCount,missingCount,pageNum);
        double result = (double)(pageNum - missingCount)/(double)pageNum;
        printf("置换次数:%d 命中率:%.2f\n",replaceCount,result);
    }
    
    //找到该页面下次要访问的位置
    int getNextPosition(int currentPage,int currentPosition,int strList[],int pageNum){ 
        
        for (int i = currentPosition+1; i < pageNum; i ++) { 
            if (strList[i] == currentPage) { 
                return i;
            }
        }
        
        return 100;
    }
    
    //最佳置换算法
    void replacePageByOPT(int memoryList[],int phyNum,int strList[],int pageNum){ 
        
        //置换次数
        int replaceCount = 0;
        //缺页次数
        int missingCount = 0;
        
        //记录在内存的物理块的下一次访问位置
        int nextPosition[phyNum];
        //初始化
        initializeList(nextPosition, phyNum);
        
        //记录当前页面的访问情况: 0 未访问
        int isVisited;
        
        for (int i = 0; i < pageNum; i ++) { 
            isVisited = 0;
            //判断是否需要置换->内存已满且需要访问的页面不在内存中
            for (int j = 0; j < phyNum; j ++) { 
                if (memoryList[j] == strList[i]) { 
                    //该页面已经存在内存中
                    //记录下一次访问它的位置
                    nextPosition[j] = getNextPosition(memoryList[j], i, strList, pageNum);
                    
                    //修改访问情况
                    isVisited = 1;
                    
                    //展示
                    printf("%d\n",strList[i]);
                    break;
                }
                if (memoryList[j] == -1) { 
                    //页面不在内存中且内存未满->直接存入
                    memoryList[j] = strList[i];
                    nextPosition[j] = getNextPosition(memoryList[j], i, strList, pageNum);
                    
                    missingCount ++;
                    
                    //修改访问情况
                    isVisited = 1;
                    
                    //展示
                    printf("%d\n",strList[i]);
                    showMemoryList(memoryList, phyNum);
                    break;
                }
            }
            
            if (!isVisited) { 
                
                //当前页面还没访问过
                //内存已满且当前访问不在内存中->进行置换
                //1.寻找到最晚才被访问到的页面
                int max = 0;
                for (int k = 1; k < phyNum; k ++) { 
                    if (nextPosition[max] < nextPosition[k]) { 
                        max = k;
                    }
                }
                
                
                //2.将该位置的页面换出
                memoryList[max] = strList[i];
                nextPosition[max] = getNextPosition(memoryList[max], i, strList, pageNum);
                
                missingCount ++;
                replaceCount ++;
                
                //展示
                printf("%d\n",strList[i]);
                showMemoryList(memoryList, phyNum);
            }
        }
        informationCount(missingCount, replaceCount,pageNum);
    }
    //先进先出置换算法
    void replacePageByFIFO(int memoryList[],int phyNum,int strList[],int pageNum){ 
        
        //置换次数
        int replaceCount = 0;
        //缺页次数
        int missingCount = 0;
        
        //记录当前最早进入内存的下标
        int pointer = 0;
        
        //记录当前页面的访问情况: 0 未访问
        int isVisited = 0;
        for (int i = 0; i < pageNum; i ++) { 
            isVisited = 0;
            
            //判断是否需要置换->内存已满且需要访问的页面不在内存中
            for (int j = 0; j < phyNum; j ++) { 
                if (memoryList[j] == strList[i]) { 
                    //该页面已经存在内存中
                    //修改访问情况
                    isVisited = 1;
                    //修改访问时间
                    //展示
                    printf("%d\n",strList[i]);
                    break;
                }
                if (memoryList[j] == -1) { 
                    //页面不在内存中且内存未满->直接存入
                    memoryList[j] = strList[i];
                    //修改访问情况
                    isVisited = 1;
                    missingCount ++;
                    //展示
                    printf("%d\n",strList[i]);
                    showMemoryList(memoryList, phyNum);
                    break;
                }
            }
            
            if (!isVisited) { 
                //当前页面还未被访问过->需要进行页面置换
                //直接把这个页面存到所记录的下标中
                memoryList[pointer] = strList[i];
                
                //下标指向下一个
                pointer ++;
                
                //如果到了最后一个，将下标归零
                if (pointer > phyNum-1) { 
                    pointer = 0;
                }
                
                
                missingCount ++;
                replaceCount ++;
                
                //展示
                printf("%d\n",strList[i]);
                showMemoryList(memoryList, phyNum);
            }
        }
        informationCount(missingCount, replaceCount, pageNum);
    }
    
    //最近最久未使用置换算法
    void replacePageByLRU(int memoryList[],int phyNum,int strList[],int pageNum){ 
        
        //置换次数
        int replaceCount = 0;
        //缺页次数
        int missingCount = 0;
    
        //记录内存中最近一次访问至今的时间
        int timeRecord[phyNum];
        //初始化
        initializeList(timeRecord, phyNum);
    
        //记录当前页面的访问情况: 0 未访问
        int isVisited = 0;
        
        //记录已经在内存中的页面数量
        int pageCount = 0;
        for (int i = 0; i < pageNum; i ++) { 
            isVisited = 0;
            
            //时间加一
            for (int p = 0; p < pageCount; p ++) { 
                if (memoryList[p] != -1) { 
                    timeRecord[p] ++;
                }
            }
            
            //是否需要置换
            for (int j = 0; j < phyNum; j ++) { 
                if (memoryList[j] == strList[i]) { 
                    //该页面已经存在内存中
                    //修改访问情况
                    isVisited = 1;
                    //重置访问时间
                    timeRecord[j] = -1;
                    //展示
                    printf("%d\n",strList[i]);
                    break;
                }
                if (memoryList[j] == -1) { 
                    //页面不在内存中且内存未满->直接存入
                    memoryList[j] = strList[i];
                    pageCount ++;
                    //修改访问情况
                    isVisited = 1;
                    //修改访问时间
                    timeRecord[j] ++;
                    
                    missingCount ++;
                    //展示
                    printf("%d\n",strList[i]);
                    showMemoryList(memoryList, phyNum);
                    break;
                }
            }
    
            if (!isVisited) { 
                //需要置换
                //1.遍历时间记录表，寻找最久未访问的页面所在的内存下标
                int max = 0;
                for (int k = 0; k < phyNum; k ++) { 
                    if (timeRecord[max] < timeRecord[k]) { 
                        max = k;
                    }
                }
    
                //2.将该位置的页面换出
                memoryList[max] = strList[i];
                timeRecord[max] = -1;
                
                missingCount ++;
                replaceCount ++;
    
                //展示
                printf("%d\n",strList[i]);
                showMemoryList(memoryList, phyNum);
                
            }
        }
        informationCount(missingCount, replaceCount, pageNum);
    }
    
    //最近最久未使用置换算法-2
    //void replacePageByLRU(int memoryList[],int phyNum,int strList[],int pageNum){ 
    //
    // int isVisited = 0;
    //
    // //记录已经在内存中的页面数量
    // int pageCount = 0;
    // for (int i = 0; i < pageNum; i ++) { 
    // isVisited = 0;
    // //判断内存是否需要换页
    // for (int j = 0; j < phyNum; j ++) { 
    // if (memoryList[j] == strList[i]) { 
    // //已经存在于内存中，把它换到队列尾部
    // int temp = memoryList[j];
    // for (int k = j; k < pageCount-1; k ++) { 
    // memoryList[k] = memoryList[k+1];
    // }
    // memoryList[pageCount-1] = temp;
    //
    // //修改访问情况
    // isVisited = 1;
    // //修改访问时间
    // //展示
    // printf("%d\n",strList[i]);
    // break;
    // }
    //
    // if (memoryList[j] == -1) { 
    // //页面不在内存中且内存未满->直接存入
    // memoryList[j] = strList[i];
    // //修改访问情况
    // isVisited = 1;
    //
    // pageCount ++;
    //
    // //展示
    // printf("%d\n",strList[i]);
    // showMemoryList(memoryList, phyNum);
    // break;
    // }
    // }
    //
    // if (!isVisited) { 
    // //需要换页
    // //1.直接将数组整体往前移一位
    // for (int k = 0; k < phyNum; k ++) { 
    // memoryList[k] = memoryList[k+1];
    // }
    // //2.将当前页面加到队尾
    // memoryList[phyNum-1] = strList[i];
    // //展示
    // printf("%d\n",strList[i]);
    // showMemoryList(memoryList, phyNum);
    // }
    //
    //
    // }
    //}
    int main(int argc, const char * argv[]) { 
        
        //物理块的数量
        int phyBlockNum;
        printf("请输入物理块数量:\n");
        scanf("%d",&phyBlockNum);
        
        //生成内存队列
        int memoryList[phyBlockNum];
        //初始化内存状态
        initializeList(memoryList, phyBlockNum);
        //showMemoryList(memoryList,phyBlockNum);
        
        //页面数量
        int pageNum;
        printf("请输入要访问的页面总数:\n");
        scanf("%d",&pageNum);
        
        //保存页面号引用串
        int pageNumStrList[pageNum];
        printf("请输入要访问的页面号:\n");
        for (int i = 0; i < pageNum; i ++) { 
            scanf("%d",&pageNumStrList[i]);
        }
        showList(pageNumStrList, pageNum);
        
        int chose;
        while (1) { 
            printf("请选择所需的置换算法:\n");
            printf("1.OPT 2.FIFO 3.LRU 4.退出\n");
            scanf("%d",&chose);
            
            switch (chose) { 
                case 1:
                    showList(pageNumStrList, pageNum);
                    replacePageByOPT(memoryList, phyBlockNum, pageNumStrList, pageNum);
                    //重新初始化内存
                    initializeList(memoryList, phyBlockNum);
                    break;
                case 2:
                    showList(pageNumStrList, pageNum);
                    replacePageByFIFO(memoryList, phyBlockNum, pageNumStrList, pageNum);
                    //重新初始化内存
                    initializeList(memoryList , phyBlockNum);
                    break;
                case 3:
                    showList(pageNumStrList, pageNum);
                    replacePageByLRU(memoryList, phyBlockNum, pageNumStrList, pageNum);
                    //重新初始化内存
                    initializeList(memoryList, phyBlockNum);
                    break;
                default:
                    return 0;
                    break;
            }
        }
        
        return 0;
    }

#### 实验截图 ####

![img\_7][img_7]  
![img\_8][img_8]  
![img\_9][img_9]

[img_1]: https://img-blog.csdnimg.cn/20191208170110630.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_2]: https://img-blog.csdnimg.cn/20191208170138868.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_3]: https://img-blog.csdnimg.cn/20191208170203619.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_4]: https://img-blog.csdnimg.cn/20191208170225985.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_5]: https://img-blog.csdnimg.cn/20191208170241751.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_6]: https://img-blog.csdnimg.cn/20191208170316592.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191208170343855.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[OPT]: https://img-blog.csdnimg.cn/20191208170430272.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[FIFO]: https://img-blog.csdnimg.cn/20191208170505809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[LRU]: https://img-blog.csdnimg.cn/2019120817052139.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_7]: https://img-blog.csdnimg.cn/20191208171250619.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_8]: https://img-blog.csdnimg.cn/20191208171313346.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_9]: https://img-blog.csdnimg.cn/20191208171323547.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70