ALG 4-3: Optimal Caching

 

    可存储k个项目的缓存

    m个项目请求序列d1, d2,…,dm

    缓存命中:项目在请求时已在缓存中的

              缓存缺失:当请求时,项目还没有在缓存中 ---> 必须将请求的项目带入缓存,如果已满,则驱逐一些现有的项目。

     目标: 将缓存缺失的次数降至最小

 

     

      // 简化调度是指只在请求该项的步骤中将项插入到缓存中的调度

                                  // 可以将一个未删减的调度转换为一个删减的调度,并且没有更多的缓存缺失。

 

   // 定理 : 给定任何一个未减少的调度,可以将它转换成一个减少的调度,并且没有更多的缓存丢失。

 

 

 

 

原文地址:https://www.cnblogs.com/JasperZhao/p/13992182.html