页面置换算法学习之FIFO，Optimal，LRU

朱雀 2022-04-24 04:06 308阅读 0赞

数据定义：

typedef struct item
    {	
            int num;		//页号
    	int time;		//等待时间，LRU算法会用到这个属性
    }Pro; int pageNum;	//系统分配给作业的主存中的页面数
    int memoryNum;		//可用内存页面数

int curmemory;  //调入内存中的页面个数 
    int missNum;  //缺页次数
    float missRate;  //缺页率
    char c;    //得到用户的输入字符，来选择相应的置换算法
    Pro *page;   //作业页面集
    Pro *memory;  //内存页面集
    
    page = (Pro*)malloc(sizeof(Pro)*pageNum);
    memory = (Pro*)malloc(sizeof(Pro)*memoryNum);

A．先进先出(FIFO)页面置换算法

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO 算法并不能保证这些页面不被淘汰。

这里，我们仍用上面的例子，但采用 FIFO 算法进行页面置换(图  
4-27)。当进程第一次访问页面 2 时，将把第 7 页换出，因为它是最先被调入内存的；在第一次访问页面 3 时，又将把第 0 页换出，  
因为它在现有的 2， 0，  
1 三个页面中是最老的页。 由图 4-27 可以看出，利用 FIFO 算法时进行了  
12 次页面置换，比最佳置换算法正好多一倍。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70]

//FIFO页面置换
     void fifoPage(Pro *page, Pro *memory)
    {  
       missNum = 0;    
       printf("FIFO页面置换情况:   \n");  
        for (i = 0; i<pageNum; i++) 
        {   
             if (Search(page[i].num, memory)<0)//若在内存中没有找到该页面   
             {    
                    missNum++;     
                    memory[curmemory].num = page[i].num;
                    print(memory); 
                    curmemory = (curmemory + 1) % memoryNum;   //找出最先进入内存的页面 
              } 
         }//end for 
         missRate = (float)missNum / pageNum; 
         printf("缺页次数：%d   缺页率:  %f\n", missNum, missRate);
     }

B．最佳(Optimal)置换算法

最佳置换算法是由 Belady 于  
1966 年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。现举例说明如下。

假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

进程运行时，先将 7，0，1  
三个页面装入内存。以后，当进程要访问页面 2 时，将会产生缺页中断。  
此时 OS 根据最佳置换算法， 将选择页面 7 予以淘汰。  
这是因为页面 0 将作为第 5 个被访问的页面，页面  
1 是第 14 个被访问的页面，而页面 7 则要在第  
18 次页面访问时才需调入。 下次访问页面 0 时， 因它已在内存而不必产生缺页中断。当进程访问页面 3时，又将引起页面 1 被淘汰；因为，它在现有的  
1，2，0 三个页面中，将是以后最晚才被访问的。图 4-26 示出了采用最佳置换算法时的置换图。由图可看出，采用最佳置换算法发生了 6 次页面置换。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70 1]

void  OptimalPage(Pro *page, Pro *memory)
    {  
           missNum = 0;   
           curmemory = 0;    
           printf("Optimal页面置换情况:   \n");   
           for (i = 0; i<pageNum; i++)  
           {   
                if (Search(page[i].num, memory) < 0)//若在内存中没有找到该页面   
                {      
                  //找出未来最长时间内不再被访问的页面     
                  int tem;    
                  int opt = 0;    
                   for (int k = 0; k < memoryNum; k++)     
                   {     
                       if (memory[k].num == -1)      
                       {       
                           curmemory = k;      
                            break;
                        }      //endif
                       tem = 0;       //页面k在未来tem时间内不会出现     
                       int j;     
                       for (j = i+1; j < pageNum; j++)     
                       {       
                              if (page[j].num == memory[k].num)     
                              {        
                                    if (tem > opt) 
                                    {         
                                          opt = tem;    
                                           curmemory = k; 
                                    }        
                                     break;
                               }       
                               else
                                     tem++; 
                     } //end for
                    if (j == pageNum)
                    {       
                          opt = tem;       
                           curmemory = k; 
                    } 
              } 
              missNum++;    
              memory[curmemory].num = page[i].num;     
              print(memory);
          }   
       }//end for 
       missRate = (float)missNum / pageNum;
        printf("缺页次数：%d   缺页率:  %f\n", missNum, missRate); 
    }

C．最近最久未使用LRU(Least  
Recently Used)置换算法

FIFO 置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。

利用 LRU 算法对上例进行页面置换的结果如图 4-28 所示。当进程第一次对页面  
2 进行访问时，由于页面 7 是最近最久未被访问的，故将它置换出去。当进程第一次对页面 3进行访问时，第  
1 页成为最近最久未使用的页，将它换出。由图可以看出，前 5 个时间的图像与最佳置换算法时的相同，但这并非是必然的结果。因为，最佳置换算法是从“向后看”的观点出发的，即它是依据以后各页的使用情况；而 LRU 算法则是“向前看”的，即根据各页以前的使用情况来判断，而页面过去和未来的走向之间并无必然的联系。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70 2]

void LRUPage(Pro *page, Pro *memory)
    {   
         missNum = 0;
         curmemory = 0;    
         printf("LRU页面置换情况:   \n");   
         for (i = 0; i<pageNum; i++)   
         {    
             int rec=Search(page[i].num, memory);    
             if (rec < 0)    //若在内存中没有找到该页面    
             {    
                    missNum++;     
                    for (int j = 0; j<memoryNum; j++)     //找出最近最久未使用的页面     
                     if (memory[j].time == -1) 
                     {       
                             curmemory = j; 
                             break;    
                      }      
                      else if (memory[j].time > memory[curmemory].time)       
                              curmemory = j;      
                     memory[curmemory].num = page[i].num;     
                     memory[curmemory].time = 0;    
                     print(memory);     
               }    
               else 
                    memory[rec].time = 0;     
               for (int j = 0; j<memoryNum; j++)     //内存中的所有页面等待时间+1      
               if (memory[j].num != -1)      
                     memory[j].time++;    
             }//end for   
             missRate = (float)missNum / pageNum; 
             printf("缺页次数：%d   缺页率:  %f\n", missNum, missRate);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70]: /images/20220220/a02229dd55e841af96e7af8141a935f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70 1]: /images/20220220/eeca57ebd40b48b1866a6dbb135c5cdf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70 2]: /images/20220220/48ae7ad8188e43018929a4ddad8e4ecb.png