Segmented LRU替换算法

在LRU(Least Recently Used)算法中,我们将缓存行按照最近使用时间进行排序。每次替换其中最长时间没有访问过的缓存行。

在实际的cache替换场景中,有一个很重要的现象,即如果一个缓存行被短时间访问了超过两次,那么他极有可能在近期再次被访问。LRU算法并没有基于该现象进行优化,而常常由于某一个常用缓存行在短时间内恰好没有使用而被替换出去。

Segmented LRU算法就是用来解决上述问题的,他通过在缓存行上面新加一个位,将缓存分为两个段(segment),分别称作试用段(probationary segment)和保护段(protected segment)。保护段里面存放了那些近期被多次访问,极有可能再次被访问的缓存行。而试用段则存放最近被导入缓存,但是并没有被多次访问的段。

上图非常清楚的解释了两个段的关系——

  • 任何段的访问都会导致该行被移到保护段的顶端
  • 保护段中最近未被使用的行会被退回到试用段的顶端,在替换他之前,为它提供额外的机会

当然,如果我们仔细对比了LRU和SLRU的代码,可以发现区别并不像之前我们说的这么多。如果我们将保护段和试用段连到一起,你就会发现,SLRU和LRU唯一的区别就是当一个不在缓存中的行进入缓存时,LRU算法将它放在了第0号位置,即Most Recently Used的位置,而SLRU算法将它放在了不那么高的一个位置,即保护段和试用段连接处的位置。这样SLRU算法就不会担心某一些特定代码段(比如短时间塞入了大量无用缓存行)会完全破坏缓存的有效性了。

参考文献:R. Karedla et al, “Caching Strategies to Improve Disk System Performance”, Computer, vol. 27, no. 3, pp. 38-46, Mar. 1994.

使用mac对含FDisk_partition_scheme的U盘重新分区

我有一个4G的U盘,由于用来装机后,U盘被分成了两个区。使用mac系统自带的Disk Utility只能够对于两个分区分别格式化,却不能够进行“分区”以及“删除分区”操作。

使用百度上建议的diskutil mergePartitions命令报如下错误——

Merging partitions encountered error "MediaKit reports partition (map) too small; if you recently grew your whole-disk, you should run whole-disk repair (-5341)".

使用终端命令diskutil list,可以看出U盘有如下结构——

/dev/disk5 (external, physical):
#: TYPE NAME SIZE IDENTIFIER
0: FDisk_partition_scheme *4.0 GB disk5
1: Apple_HFS 2.9 GB disk5s1
2: Apple_HFS 314.6 MB disk5s2

第0项指示了U盘总空间大小,我猜测是类似于分区表的根目录,指示了整个树形结构的大小总和,而表中1号2号项则加起来大约4G,是我们需要合并的两个分区。

我的其他U盘的第0项的TYPE是“GUID_partition_scheme”。猜测可能我们的MAC系统不支持“FDisk_partition_scheme”的磁盘分区操作。而接下来,我们这试图将磁盘抹掉,重置为“GUID_partition_scheme”。

diskutil list
diskutil unmountDisk force disk5
sudo dd if=/dev/zero of=/dev/disk5 bs=1024 count=1024
diskutil list

此时,输出为

/dev/disk5 (external, physical):
#: TYPE NAME SIZE IDENTIFIER
0: *4.0 GB disk5

接着,我们使用diskutil重新对这个空白磁盘格式化

diskutil partitionDisk disk5 GPT JHFS+ "My External HD" 0g

现在,我们的磁盘就和普通u盘一样了,有3.7G的可用空间。

/dev/disk5 (external, physical):
#: TYPE NAME SIZE IDENTIFIER
0: GUID_partition_scheme *4.0 GB disk5
1: EFI EFI 209.7 MB disk5s1
2: Apple_HFS My External HD 3.7 GB disk5s2

参考链接:https://superuser.com/questions/233531/how-can-i-resolve-the-error-mediakit-reports-partition-map-too-small