[問題] LRU機制的實作

看板LinuxDev作者 (Katastrophy)時間14年前 (2012/01/24 18:22), 編輯推噓4(4推 0噓 40→)
留言44則, 4人參與, 最新討論串1/1
請問一下如果想要實作Cache的LRU機制 操作是以檔案為基礎操作單位 這樣的話 寫一個recursive list dir一次掃一整個目標目錄下面所有檔案 找到least rescently used 的檔案(或是找到最少用的若干個) 這樣的作法會不會不太切實際 我的快取系統快取的檔案不會太多 (cache大小大概16GB左右) 所以一次應該不會跑太久 @@ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.126.125.176
→
01/24 22:53, , 1F
標題打錯了..
01/24 22:53, 1F
→
01/25 00:07, , 2F
orz
01/25 00:07, 2F
→
01/25 00:34, , 3F
感覺一般來說在第一次 compulsory miss 後檔案進了
01/25 00:34, 3F
→
01/25 00:35, , 4F
cache 之後才開始記錄吧? (有錯請指證:P
01/25 00:35, 4F
→
01/25 00:35, , 5F
檔案多的話這個掃描豈不是太慢 :P
01/25 00:35, 5F
→
01/25 01:01, , 6F
可是我看到建議的做法 好像是approximate LRU
01/25 01:01, 6F
→
01/25 01:02, , 7F
用記錄的 他記的量會很大吧 書架演算法之類的
01/25 01:02, 7F
→
01/25 01:03, , 8F
每當一個檔案被用到 就排到queue的最後面這樣
01/25 01:03, 8F
→
01/25 01:03, , 9F
如果都是用絕對路徑做紀錄 這個queue會相當佔容量...
01/25 01:03, 9F
→
01/25 01:04, , 10F
還是要回歸到approximate LRU @@ ? 用一個byte定時shift
01/25 01:04, 10F
→
01/25 01:23, , 11F
我看一些討論 linux kernel做LRU的時候 也是要做scan說@@
01/25 01:23, 11F
→
01/25 01:24, , 12F
他以page為單位去scan 雖然說是在memory不過應該也不快吧
01/25 01:24, 12F
→
01/25 01:25, , 13F
對了 我的cache的儲存媒體是SDcard 他random access算快
01/25 01:25, 13F
※ 編輯: EntHeEnd 來自: 59.126.125.176 (01/25 18:13)
推
01/28 10:37, , 14F
linux做的時候應該沒有scan
01/28 10:37, 14F
→
01/28 10:38, , 15F
他用一個linked list用到就抓到head
01/28 10:38, 15F
→
01/28 14:17, , 16F
喔喔 @@... 可是那樣做的話 如果是要記檔案的資訊
01/28 14:17, 16F
→
01/28 14:18, , 17F
每個檔案不說路徑至少都要記檔名 這樣這個list會相當佔
01/28 14:18, 17F
→
01/28 14:18, , 18F
容量吧
01/28 14:18, 18F
→
01/28 14:22, , 19F
用list的作法應該就是書架演算法 用到的就放到list最後吧
01/28 14:22, 19F
→
01/28 14:23, , 20F
這樣這樣應該會發生讓面提到的list佔很大的儲存空間的問
01/28 14:23, 20F
→
01/28 14:23, , 21F
題吧 @@
01/28 14:23, 21F
→
01/28 14:24, , 22F
就我目前粗淺google到的資訊 大部分都有提到time stamp
01/28 14:24, 22F
→
01/28 14:25, , 23F
如果有用到time stamp的話 應該就是用scan的做法吧 @@
01/28 14:25, 23F
→
01/28 14:34, , 24F
我加上file字眼去找 有找到說用list做的了 謝謝樓上板友
01/28 14:34, 24F
→
01/28 14:34, , 25F
回答 我先研究看看 ^^
01/28 14:34, 25F
→
01/28 14:36, , 26F
不過用list的作法 再找LRU的目標很快 更新list的動作還是
01/28 14:36, 26F
→
01/28 14:37, , 27F
免不掉scan...
01/28 14:37, 27F
推
01/28 18:34, , 28F
更新應該也可以不用scan,以kernel的replacement policy
01/28 18:34, 28F
推
01/28 18:36, , 29F
來說他會知道自己要更新的page是哪個,用array加上offset
01/28 18:36, 29F
推
01/28 18:39, , 30F
可以存取到那個struct,之後再存取struct裡面的lru membe
01/28 18:39, 30F
→
01/28 18:40, , 31F
這個list node就可以把他取出放到head
01/28 18:40, 31F
→
01/28 19:41, , 32F
喔喔... 對齁 可是用list有一個問題就是要存的資訊量用在
01/28 19:41, 32F
→
01/28 19:42, , 33F
檔案的時候 我都是用路徑和檔名來操作的話 這樣要記的東
01/28 19:42, 33F
→
01/28 19:43, , 34F
西(路徑)可能很長 檔案多起來這個list佔的空間會很大 @@
01/28 19:43, 34F
→
01/28 19:44, , 35F
等等... 其實我還沒搞懂上面的說法 orz...
01/28 19:44, 35F
→
01/28 19:45, , 36F
我看過可以在O(1)找到 list node的做法是另外用hash map
01/28 19:45, 36F
→
01/28 19:45, , 37F
過去該 list node 用以直接操作目標list node
01/28 19:45, 37F
→
01/28 19:46, , 38F
用array的話 應該是把access的page的address當成array
01/28 19:46, 38F
→
01/28 19:47, , 39F
index來用 然後array裡面存的是該page對應的list node
01/28 19:47, 39F
→
01/28 19:47, , 40F
的address這樣吧 (概念上 @@)
01/28 19:47, 40F
→
01/28 19:48, , 41F
不過要這樣操作 應該是在他page都是用編號(address)來代
01/28 19:48, 41F
→
01/28 19:48, , 42F
表 可以避免掉要記路徑檔名的話 要使用太多空間的問題
01/28 19:48, 42F
→
01/28 19:49, , 43F
如果對檔案的操作 都是用路徑檔名來操作 list... 好像不
01/28 19:49, 43F
→
01/28 19:49, , 44F
太合用 @@？
01/28 19:49, 44F
‣ 更多 EntHeEnd 的文章
文章代碼(AID): #1F7ePfOK (LinuxDev)