1 Prefetching for Energy Efficiency
fetch on demand 策略，需要66个单位时间，此方案下磁盘的idle时间是60个单位时间，6 misses
总共预取需要61个时间段，磁盘idle时间有5个间歇期，每个间歇期有9个时间段，其中有一个是8个时间段,1 miss
预取时间段为61个时间段，其中idle时间间歇为两个，一个是27包含27个时间段，一个包含28个时间段,1 miss
2 Rules for Optimal Prefetching Revisited
- 什么时候在disk上面预取
- 预取哪个块
- 哪个块将被替换
4个基本规则：
- 对于cache中没有的block，预取reference stream 中的下一个块
- 哪个块被丢弃：下次将最长时间被引用的块
- 当在B之前需要访问A时，不能丢弃A去预取B
- 预取与替换操作不要对于同一个块执行，这样效率会很低，该规则回答了什么时候预取将停止！
2.2 预取策略带来的节能
传统的预取方案是根据应用程序的需要事先将block从磁盘中取出
这样会出现两个问题：
- true positives:预取的块是有用的
- false positive：有用的块没有被取出
节能的预取：取得足够的块保证较长的磁盘idle间歇，这个目标与上述目标不同，需要更多的数据，具有更强烈的预测性
本文中采用ratio=true/false的比值引入到节能效果的判断
3 具体的设计
设计的预取算法需要考虑三个问题：
- 什么时候开始进行预取
- 取哪个块
- 内存中哪个块将被替换
两个新的规则：
(1)最大化磁盘的利用率，在一个预取操作完成后紧接着下一个预取操作
(2)idle时间的保证：不要随意打断磁盘的idle的时间，除非马上要进行新的预取操作以保证性能
什么时候开始预取：
磁盘在active时：预取尽可能多的数据
磁盘在idle时：尽量让磁盘多休眠，推迟预取时间一直到最后无法推迟为止
Epoch-based algorithm :
每一个Epoch分为两个阶段：
active phase 以及 idle phase
预取操作在active 阶段进行，OS必须要：
- 预测需要访问的数据
- 计算内存的总容量
- 将内存中无效的映射数据以及dirty页数据
- Prefetch or reserve buffers for writing new data proportional to each executing
application’s memory resource requirements
预取启动时间：要cover住自身的预取延迟以及磁盘powe-up的时间
上述的Epoch的两个阶段，任何一个阶段将会被一下的任意事件触发：
- 性能存在问题
- miss产生，没有预取所有需要的数据以及将有用页进行剔除，导致延迟急剧增加
- 内存资源已经不够用了
预取哪个块：
为了控制预取的精确性，采用hints的方法进行预取策略的指定.hints方法最早由Patterson提出的.
hint定义了一个文件区分的接口，该描述符可以是一个文件描述符，也可以就是一个文件名,该描述符的作用是：
操作文件的方式：顺序，环，随机
第一次与最后一次访问文件的时间：该时间信息是程序执行开始时间的一个偏移或者hint创建的时间
对于随机的访问：hint也需要了解文件中的"hot"集，对于每个集合访问的概率，还定义一个指针，该指针指向一个文件，
该文件需要具有以下属性：在特定时间内对于某个特定page最有可能访问的
hint的接口
本文中实现的monitor daemon是追踪文件的活跃状态，通过跟踪open，close，read，write execve,exit以及setpgid
等系统调用.
两层目的：
- 依据上述的信息建立文件操作行为的数据库
- 根据该数据库生成hints
monitor 的行为
替换哪个块：
power-aware 预取方式的特点：
- 提前做预取，不像以前传统的方法可以一直进行出页操作
- 在替换过程中，需要知道哪些页将在一段时间内不会被访问，以便进行替换
两个重要的替换参数：
- 留下来的内存空间要足够大，大到可以容下任何一段时间内的需要预取的数据量
- 被替换掉的page不会马上访问，起码要比预取来的数据优先级要低
这样做的目的是：
使得磁盘idle的时间最大化
接下来对于page miss的问题进行分类：
- 剔除导致的缺失：将常驻在buffer里面的page剔除
- 预取导致的缺失：预取的数据没有被访问，访问缺失产生，说明预取的cache较小，应该更大点
- 强制缺失：
eviction miss在idle状态下说明预取的量需要减少了，而prefetch miss说明预取的page量要增加
预取的page量最终还是由hints决定的
4实验：
Hinted files
hints设计：
- hints由内核自动的监测和产生的
- 双向链表
- 根据第一次访问时间来进行排序
内核需要跟踪系统内部的行为：
找到文件的caching state，是完全没有被cache,完全被cache，还是部分cache，或者只是元数据被cache
内核中通常都是认为文件没有被cache的，所以内核会主动的去对元数据以及数据进行cache操作
- 访问的速率：一秒时间内访问pages的数量
- 预取的数量：在当前的状态下，根据hints的记录需要预取的pages的数量
Prefetch Thread
idle的时间是有限的，由于不同应用程序之间缺乏协调
即使磁盘出现很长时间idle的状态时，仍然不能将磁盘进行关闭操作
写请求可以被集合起来由于大部分的写操作都是由update daemon产生的，page-out由swap daemon产生的
本文中设计一个Prefetch daemon操作
The prefetching algorithm sets an
initial target idle period and for each hinted file that is predicted to be accessed within the target period it aggressively prefetches
metadata and data proportional to the average access rate.
The target idle time is then increased gradually until all hinted files are fully
prefetched or the amount of memory available for prefetching is depleted
目标idle时间(breakeven)设定的标准是：the times over which the energy savings of lowpower states
exactly equal the energy cost of returning to the Active state
Prefetch cache
构造一个新的Prefetch cache，每一个page在PC中都有一个时间戳，该时间戳显示page将被访问的时间
当一个page被用完时，那么将该page放入到linux自身的LRUlist中，采用内核的页回收机制进行处理
Eviction Cache
根据预取的机制去决定剔除的page的数量
建立一个新的eviction cache：该cache保存了被剔除的page的元数据，由一个序列号表示
During the idle phase, if an eviction miss takes place, the difference between
the page’s eviction number and the current epoch’s starting eviction number indicates the number
of pages that were evicted in favor of prefetching without causing
an eviction miss.
由上述序列号去调整预取的深度(cache size)，cache size的大小与强制缺失没有关系，其大小的调整在没有缺失时以及只有一次预取缺失时，在初始化阶段时，将该序列号定义为idle的page数量
linux自身具有update的操作，但是存在一定的弊端，update操作没5秒一次，刷新所有脏buffer的时间为30s
该策略不利于节能：
即使在轻载的条件下idle时间跨度都在5s或者更少
本文中采用刷新脏buffer的时间在1分钟一次，在open操作上面加入write behind操作
在写的过程中应注意的：
系统会出现内存不够以及page daemon会出现换页的现象，为了解决这个问题，预取的线程会提前为将来可能出现的写操作事先预留一部分空间
这个部分预留的内存与写的速率成正比例关系，在预取阶段的后期，预取线程清除所有的保留页数
Power Management Policy
- 若预测的时间长度比硬盘standby breakeven 时间，在一秒之内进入standby状态
- 如果预取系统重复的错误预测idle时间的长度，采用动态调整threshold的策略
- 对于rate-based的应用程序，使得spin-down的磁盘能够准确的完成spin-up操作，及时的满足服务需求
阅读(1553) | 评论(0) | 转发(0) |
