作者EntHeEnd (Katastrophy)
看板LinuxDev
标题[问题] LUR机制的实作
时间Tue Jan 24 18:22:31 2012
请问一下如果想要实作Cache的LRU机制
操作是以档案为基础操作单位
这样的话
写一个recursive list dir一次扫一整个目标目录下面所有档案
找到least rescently used 的档案(或是找到最少用的若干个)
这样的作法会不会不太切实际
我的快取系统快取的档案不会太多
(cache大小大概16GB左右)
所以一次应该不会跑太久 @@
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.126.125.176
1F：→ lctwolf:标题打错了.. 01/24 22:53
2F：→ EntHeEnd:orz 01/25 00:07
3F：→ danielsig727:感觉一般来说在第一次 compulsory miss 後档案进了 01/25 00:34
4F：→ danielsig727:cache 之後才开始记录吧? (有错请指证:P 01/25 00:35
5F：→ danielsig727:档案多的话这个扫描岂不是太慢 :P 01/25 00:35
6F：→ EntHeEnd:可是我看到建议的做法 好像是approximate LRU 01/25 01:01
7F：→ EntHeEnd:用记录的 他记的量会很大吧 书架演算法之类的 01/25 01:02
8F：→ EntHeEnd:每当一个档案被用到 就排到queue的最後面这样 01/25 01:03
9F：→ EntHeEnd:如果都是用绝对路径做纪录 这个queue会相当占容量... 01/25 01:03
10F：→ EntHeEnd:还是要回归到approximate LRU @@ ? 用一个byte定时shift 01/25 01:04
11F：→ EntHeEnd:我看一些讨论 linux kernel做LRU的时候 也是要做scan说@@ 01/25 01:23
12F：→ EntHeEnd:他以page为单位去scan 虽然说是在memory不过应该也不快吧 01/25 01:24
13F：→ EntHeEnd:对了 我的cache的储存媒体是SDcard 他random access算快 01/25 01:25
※ 编辑: EntHeEnd 来自: 59.126.125.176 (01/25 18:13)
14F：推 mimi0213:linux做的时候应该没有scan 01/28 10:37
15F：→ mimi0213:他用一个linked list用到就抓到head 01/28 10:38
16F：→ EntHeEnd:喔喔 @@... 可是那样做的话 如果是要记档案的资讯 01/28 14:17
17F：→ EntHeEnd:每个档案不说路径至少都要记档名 这样这个list会相当占 01/28 14:18
18F：→ EntHeEnd:容量吧 01/28 14:18
19F：→ EntHeEnd:用list的作法应该就是书架演算法 用到的就放到list最後吧 01/28 14:22
20F：→ EntHeEnd:这样这样应该会发生让面提到的list占很大的储存空间的问 01/28 14:23
21F：→ EntHeEnd:题吧 @@ 01/28 14:23
22F：→ EntHeEnd:就我目前粗浅google到的资讯 大部分都有提到time stamp 01/28 14:24
23F：→ EntHeEnd:如果有用到time stamp的话 应该就是用scan的做法吧 @@ 01/28 14:25
24F：→ EntHeEnd:我加上file字眼去找 有找到说用list做的了 谢谢楼上板友 01/28 14:34
25F：→ EntHeEnd:回答 我先研究看看 ^^ 01/28 14:34
26F：→ EntHeEnd:不过用list的作法 再找LRU的目标很快 更新list的动作还是 01/28 14:36
27F：→ EntHeEnd:免不掉scan... 01/28 14:37
28F：推 mimi0213:更新应该也可以不用scan,以kernel的replacement policy 01/28 18:34
29F：推 mimi0213:来说他会知道自己要更新的page是哪个,用array加上offset 01/28 18:36
30F：推 mimi0213: 可以存取到那个struct,之後再存取struct里面的lru membe 01/28 18:39
31F：→ mimi0213: 这个list node就可以把他取出放到head 01/28 18:40
32F：→ EntHeEnd:喔喔... 对齁 可是用list有一个问题就是要存的资讯量用在 01/28 19:41
33F：→ EntHeEnd:档案的时候 我都是用路径和档名来操作的话 这样要记的东 01/28 19:42
34F：→ EntHeEnd:西(路径)可能很长 档案多起来这个list占的空间会很大 @@ 01/28 19:43
35F：→ EntHeEnd:等等... 其实我还没搞懂上面的说法 orz... 01/28 19:44
36F：→ EntHeEnd:我看过可以在O(1)找到 list node的做法是另外用hash map 01/28 19:45
37F：→ EntHeEnd:过去该 list node 用以直接操作目标list node 01/28 19:45
38F：→ EntHeEnd:用array的话 应该是把access的page的address当成array 01/28 19:46
39F：→ EntHeEnd:index来用 然後array里面存的是该page对应的list node 01/28 19:47
40F：→ EntHeEnd:的address这样吧 (概念上 @@) 01/28 19:47
41F：→ EntHeEnd:不过要这样操作 应该是在他page都是用编号(address)来代 01/28 19:48
42F：→ EntHeEnd:表 可以避免掉要记路径档名的话 要使用太多空间的问题 01/28 19:48
43F：→ EntHeEnd:如果对档案的操作 都是用路径档名来操作 list... 好像不 01/28 19:49
44F：→ EntHeEnd:太合用 @@？ 01/28 19:49