Clock算法

Clock算法的简介

由于LRU算法对于硬件要求很高，它的近似算法通常是更好的选择，Clock算法就是用的比较多的一种LRU近似算法。

Clock算法的理解

话不多说，直接进入正题！

简单Clock置换算法

例题：页面流 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 在3个物理块下的置换过程。
相比起其他算法，Clock算法需要一个指针，简单理解就是指针指向哪里页面就优先插入哪里。
比如在初始状态时指针指向第一个物理块，页面7便插入第一个物理块，同时指针下移，那么什么时候指针要下移呢？很简单，当插入成功后指针移到插入位置的下一位。
除了指针还需要给每个在物理块中的页面标个号（0或1），刚插入的或者已经在物理块中又被访问的页面标为1。这个标号有什么用呢，你可以理解为一个一次性的“免换金牌”，当被指针指着要被换出的时候，如果标号是1，就改为0，然后按顺序判断下一个位置，直到循环下去找到一个0，把标号0的页面换出去，同时指针移到换出位置的下一位。
例题的流程便是这样的（这里我用*表示标号为1，没有则为0）：

改进Clock置换算法

由于在实际系统使用中页面不仅会被访问还会被修改，所以改进型Clock算法就是把页面分成四种情况：
1.最近既没修改也没访问
2.最近没访问但修改了
3.最近访问了但没修改
4.最近即访问又修改了
按照类似简单Clock算法（使用两个标号）来依次判断有没有情况1的页面，如果有就换出，如果没有就判断有没有情况2的页面，注意，当判断完后还是没有并不是去判断情况3和4，而是把所有访问标号都重置为0，再依次判断1和2，这样就能找到最适合换出的页面。

总结

Clock算法相较于其他页面置换算法比较复杂，但是只要掌握原理，用例题练几遍就能很熟练啦~

王道操作系统CLOCK算法理解

最近复习到操作系统的CLOCK算法，虽然这个算法看起来简单，但在做题时却十分费解，尤其是指针的位置，本文针对王道课后相关习题做以解释说明。

21版王道操作系统3.2.9第11题

对于了解FIFO、LRU算法以及CLOCK算法的同学不难做出结果，但本人在计算CLOCK算法时，得出的结果却是虚拟页号为1的页（答案为虚拟页号为2，页帧号为0的帧），在看课后习题时亦百思不得其解，刚开始本人的理解如下：

1. 首先根据CLOCK算法，在指针摆动的过程中，所遇到第一个访问位为0的页面即换出页面；
2. 如何判断指针位置呢，由于最近访问时间最靠前的虚拟页号为2和1的页的访问位均为0，故判断指针当前位置在虚拟页号为2号的页帧上，刚将该帧的访问位置0；
3. 故接下来指针顺序摆动，将表中第三行和第四行的页帧访问位置0，随后回到虚拟页号为1的页帧处，此时结束第一轮指针搜寻；
4. 随后指针发现当前所在页帧的访问位为0，故换出；

想必此时对CLOCK算法十分了解的同学已经发现了问题所在。是的，在CLOCK算法中，指针的摆动顺序并非按照最近访问时间来排，而是按照页帧的装入时间来进行排序循环（此处容易理解：最近访问时间是实时动态变化的，而指针的摆动顺序却是在页帧装入时变更后，无页帧更换变化便不进行更新的）。所以正确的解法应如下：

1. 首先根据CLOCK算法，在指针摆动的过程中，所遇到第一个访问位为0的页面即换出页面；
2. 其次判断指针位置。根据装入时间可知，指针的摆动顺序为（3021–虚拟页号顺序）而此时3号和0号均为1，可知此时指针位置有两种可能性，第一种为在指向2号页时产生缺页中断，故循环寻找访问位为0的页帧，未找到后再次循环判断，并将跳过的页面访问位置0，所以此时指针在0号页（刚刚将1号页的访问位置0，顺延指向0号页）；第二种可能为，系统刚过163的时间，即指针刚刚将3号页帧的访问位置1，随后指向后面一个页，即2号页，并发生缺页中断；
3. 现在对以上两种可能性进行分别分析。第一种可能性下，由于指针置0的起始位置在2号帧，故循环置零后再次进行访问位判断，此时2号页为第一个访问位为0的页，故被换出（此处区别CLOCK算法和改进的CLOCK算法）；第二种可能性下，由于此时指针开始循环寻找访问位为0的页面换出，此时2号页为第一个判断项，且访问位为0，故被换出；
4. 综上，使用NRU算法时被换出的虚拟页号为2。

在解题过程中，同学们应特别注意题中要求使用的是CLOCK算法（即NRU算法）还是改进的CLOCK算法，其次，对于指针的摆动顺序是根据装入时间来确定的这一隐藏规则要牢记。

页面置换算法之FIFO、LRU、OPT和Clock算法及其实现

页面置换

页面置换：页面置换是请求调页的基础，它完成了逻辑内存和物理内存之间的分离，采用这种机制，较小的物理内存能为程序员提供巨大的虚拟内存。

在页码被调入的时候，会有三种情况发生：
a. 类似初始化状态，内存未满，但是没有该页码，需要从磁盘中直接引入。
b. 内存已满，产生缺页错误，需要请求调页。
c. 内存已满，但是存在改页码，可以直接使用，不需要调页，也不会产生缺页错误。

所以针对这三种情况，设计如下四种页面置换算法：

FIFO页面置换

FIFO 是最简单的页面置换算法，它为每一个页面记录了调到内存的时间，当必须置换页面时，将选择最旧的页面。具体实现的话，我们并不需要记录调入页面的具体时间，只需要创建一个FIFO队列，来管理所有的内存页面，置换的是队列的首个页面，当需要调入页面到内存时，就将它加入到队列的尾部。

OPT页面置换

这个算法具有所有算法的最低的缺页错误率。并且不会遭受Belady异常，被称为OPT或者MIN。
OPT为置换最长时间不使用的页面，他与LRU算法不同的是需要向后看，寻找最不经常使用的页码，所以我们只需要向后看，有两种情况则可以结束前进：

1. 找到了（最大帧数-1）个页码号，则剩下的那一个页码即为我们要替换的页码
2. 找到了最后，都没有找到（最大帧数-1）个页码，这就按FIFO算法将没有找到的页码踢掉。

LRU页面置换

同为采用队列实现，LRU与FIFO不同的地方，需要更新不断出现的元素，将它重新插入一遍，所以对应于上面的三种情况中的c，这时所需要的页码在内存中已经存在，不能只是简单的直接调用进程，还需要将该页码更新一下，以证明最近使用过（找到页码所对应的位置，将它在队列中删掉，重新插入一遍）。

Clock算法

Clock又叫第二次机会算法，通过一个visit数组来实现第二次访问，利用循环队列相应的知识，在FIFO的基础上，在开辟一个与之对应的数组，其索引必须相呼应，两者具体关系如下：
a. 页码刚被调入，设置其页码对应的visit为1；
b. 访问过一次，则将其visit设置为0；
c. 页码被替换，对应的visit也要更新为1。
总之，将visit与队列实现同步操作即可。

具体代码如下：

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<time.h>

using namespace std;

#define N 20    //Page_Name
#define M 3     //Frame_Max_name

int in(vector<int> map,int num){             //判断新进来的元素是否已经存在与内存里面
    int flag = 0; 
    vector<int>::iterator v = map.begin();
    while( v != map.end()) {
        if(num == *v){
            flag = 1;
            break;
        }
        v++;
    }
    return flag;
}

int return_index(vector<int> map,int num){     //因为栈、队列等数据结构没有遍历的功能，所以写这个函数来直接定位某个元素的索引
    int index = 0;
    vector<int>::iterator v = map.begin();
    while( v != map.end()) {
        if(num == *v){
            break;
        }
        v++;
        index++;
    }
    return index;
}
int main(){
    int arr[N];//= {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
    vector<int> map;   //判断是否在stack or queue中
    int num = 0;       //缺页数
    int num1,num2,num3,num4,num5;
    srand((unsigned int)(time(NULL)));
    for(int i=0;i<N;i++){ //随机生成arr数组 表示接下来要应用的页码
        
        arr[i] = rand()%10;
        //cout << arr[i] << " ";
    }
    cout << endl;
    queue<int> FIFO;
    stack<int> LRU;

    //FIFO alforithm :
    cout << "FIFO序列如下: " << endl;
    map.clear();
    for(int i=0;i<N;i++){
        if(in(map,arr[i])){          //如果页码在内存中已经存在，输出true
            cout << "true" << endl;
            continue;
        }
            
        else{
            if(map.size()>=M){       //如果页码在内存中不存在，并且不是刚开始帧什么都没有的情况
                //int index = return_index(map,arr[i]);
                //cout << "index : " << index << endl;
                //FIFO.pop();
                //FIFO.push(arr[i]);
                map.erase(map.begin());   //头部出队列
                map.push_back(arr[i]);    //尾插
            }
            else{                    //初始状态，帧里面什么都没有，直接入队即可
                //FIFO.push(arr[i]);
                map.push_back(arr[i]);
            }
            num++;
            vector<int>::iterator v = map.begin();
            while( v != map.end()) {
                cout << *v << " ";
                v++;
            }
            cout << endl;
        }
    }
    num1 = num;
    cout << "总页数为: " << N << endl << "FIFO算法缺页数: " << num << endl;


    //LRU alaorithm :
    cout << endl << "LRU序列如下: " << endl;
    map.clear();
    num = 0;
    for(int i=0;i<N;i++){
        if(in(map,arr[i])){
            int index = return_index(map,arr[i]);   //与FIFO不同的地方，需要更新不断出现的元素，将它重新插入一遍
            map.erase(map.begin()+index);
            map.push_back(arr[i]);
            cout << "true" << endl;
            continue;
        }
        else{
            if(map.size()>=M){
                map.erase(map.begin());
                map.push_back(arr[i]);
            }
            else{
                map.push_back(arr[i]);
            }
            num++;
            vector<int>::iterator v = map.begin();
            while( v != map.end()) {
                cout << *v << " ";
                v++;
            }
            cout << endl;
        }
    }
    num2 = num;
    cout << "总页数为: " << N << endl << "LRU算法缺页数: "  << num << endl;



    //OPT alaorithm :
    cout << endl << "OPT序列如下: " << endl;
    map.clear();
    num = 0;
    
    for(int i=0;i<N;i++){
        if(in(map,arr[i])){
            // int index = return_index(map,arr[i]);
            // map.erase(map.begin()+index);
            // map.push_back(arr[i]);
            cout << "true" << endl;
            continue;
        }
        else{
            if(map.size()>=M){
                int pass = 0;
                int vis[M];
                for(int x=0;x<M;x++){
                    vis[x] = 0;
                }
                for(int j=i+1;j<N;j++){
                    for(int k=0;k<M;k++){
                        if(arr[j] == map[k]){
                            //cout << "i am " << arr[j] << endl;
                            int ind = return_index(map,arr[j]);
                            //cout << "index : " << ind << endl;
                            //cout << "arr : " << arr[j]  << endl;
                            if(vis[ind] == 1){
                                break;
                            }
                            else{
                                vis[ind] = 1;
                            }
                            pass++;
                            if(pass==M-1){
                                //cout << "pass = " << pass << "  goto !" << endl; 
                                goto This;
                            }
                            continue;
                        }
                    }
                }
This:           for(int j=0;j<M;j++){
                    if(vis[j] == 0){
                        //cout << "j == : " << j << endl;
                        map.erase(map.begin()+j);
                        map.push_back(arr[i]);
                        break;
                    }
                }
                
            }
            else{
                map.push_back(arr[i]);
            }
            num++;
            vector<int>::iterator v = map.begin();
            while( v != map.end()) {
                cout << *v << " ";
                v++;
            }
            cout << endl;
        }
    }
    num3 = num;
    cout << "总页数为: " << N << endl << "OPT算法缺页数: "  << num << endl;



    

    //Clock alaorithm 2.0 版本（循环队列） :
    cout << endl << "Clock序列如下: " << endl;
    map.clear();
    num = 0;
    vector<int> visit;
    
    int index = 0;
    for(int i=0;i<N;i++){
        if(in(map,arr[i])){
            int ind = return_index(map,arr[i]);
            //map.erase(map.begin()+index);
            visit[ind] = 1;
            //map.push_back(arr[i]);
            cout << "true" << endl;
            continue;
        }
        else{
            if(map.size()>=M){
                //int x = 0;
                while(1){
                    if(visit[index] == 0){
                        map[index] = arr[i];
                        visit[index] = 1;
                        index = (index+1) % M;
                        // map.erase(map.begin()+x);
                        // map.push_back(arr[i]);
                        // visit.erase(visit.begin()+x);
                        // visit.push_back(1);
                        break;
                    }
                    else{
                        visit[index] = 0;
                        index = (index+1) % M;
                    }
                }
            }
            else{
                map.push_back(arr[i]);
                visit.push_back(1);
            }
            num++;
            //cout << "元素 ： ";
            vector<int>::iterator v = map.begin();
            while( v != map.end()) {
                cout << *v << " ";
                v++;
            }
            //cout << endl;
            //cout << "visit : "; 
            // vector<int>::iterator y = visit.begin();
            // while( y != visit.end()) {
            //     cout << *y << " ";
            //     y++;
            // }
            
            cout << endl;
        }
    }
    num4 = num;
    cout << "总页数为: " << N << endl << "Clock算法缺页数: "  << num << endl << endl;



    //Clock alaorithm 2.0 （FIFO为基础）:
    cout << endl << "自创Clock序列如下: " << endl;
    map.clear();
    num = 0;
    visit.clear();
    for(int i=0;i<N;i++){
        if(in(map,arr[i])){
            int index = return_index(map,arr[i]);
            //map.erase(map.begin()+index);
            visit[index] = 1;
            //map.push_back(arr[i]);
            cout << "true" << endl;
            continue;
        }
        else{
            if(map.size()>=M){
                int x = 0;
                while(1){
                    if(visit[x] == 0){
                        map.erase(map.begin()+x);
                        map.push_back(arr[i]);
                        visit.erase(visit.begin()+x);
                        visit.push_back(1);
                        break;
                    }
                    else{
                        visit[x] = 0;
                        x = (x+1) % M;
                    }
                }
            }
            else{
                map.push_back(arr[i]);
                visit.push_back(1);
            }
            num++;
            //cout << "元素 ： ";
            vector<int>::iterator v = map.begin();
            while( v != map.end()) {
                cout << *v << " ";
                v++;
            }
            //cout << endl;
            //cout << "visit : "; 
            // vector<int>::iterator y = visit.begin();
            // while( y != visit.end()) {
            //     cout << *y << " ";
            //     y++;
            // }
            
            cout << endl;
        }
    }
    num5 = num;
    cout << "总页数为: " << N << endl << "自创Clock算法缺页数: "  << num << endl << endl;



    cout << "综上所述 ：" << endl;
    cout << "页码进入顺序为：" <<endl;
    for(int i=0;i<N;i++){ 
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "总页数为：" << N << endl;
    cout << "FIFO算法缺页数: "  << num1 << endl;
    cout << "LRU算法缺页数: "  << num2 << endl;
    cout << "OPT算法缺页数: "  << num3 << endl;
    cout << "Clock算法缺页数: "  << num4 << endl;
    cout << "自创Clock算法缺页数: "  << num5 << endl;

    return 0;
}