作者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