[問題] LUR機制的實作

[EntHeEnd (Katastrophy)]

請問一下如果想要實作Cache的LRU機制

操作是以檔案為基礎操作單位

這樣的話

寫一個recursive list dir一次掃一整個目標目錄下面所有檔案

找到least rescently used 的檔案(或是找到最少用的若干個)

這樣的作法會不會不太切實際

我的快取系統快取的檔案不會太多

(cache大小大概16GB左右)

所以一次應該不會跑太久 @@

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.125.176
→ lctwolf:標題打錯了..
→ EntHeEnd:orz
→ danielsig727:感覺一般來說在第一次 compulsory miss 後檔案進了
→ danielsig727:cache 之後才開始記錄吧? (有錯請指證:P
→ danielsig727:檔案多的話這個掃描豈不是太慢 :P
→ EntHeEnd:可是我看到建議的做法 好像是approximate LRU
→ EntHeEnd:用記錄的 他記的量會很大吧 書架演算法之類的
→ EntHeEnd:每當一個檔案被用到 就排到queue的最後面這樣
→ EntHeEnd:如果都是用絕對路徑做紀錄 這個queue會相當佔容量...
→ EntHeEnd:還是要回歸到approximate LRU @@ ? 用一個byte定時shift
→ EntHeEnd:我看一些討論 linux kernel做LRU的時候 也是要做scan說@@
→ EntHeEnd:他以page為單位去scan 雖然說是在memory不過應該也不快吧
→ EntHeEnd:對了 我的cache的儲存媒體是SDcard 他random access算快
※ 編輯: EntHeEnd        來自: 59.126.125.176       (01/25 18:13)
推 mimi0213:linux做的時候應該沒有scan
→ mimi0213:他用一個linked list用到就抓到head
→ EntHeEnd:喔喔 @@... 可是那樣做的話 如果是要記檔案的資訊
→ EntHeEnd:每個檔案不說路徑至少都要記檔名 這樣這個list會相當佔
→ EntHeEnd:容量吧
→ EntHeEnd:用list的作法應該就是書架演算法 用到的就放到list最後吧
→ EntHeEnd:這樣這樣應該會發生讓面提到的list佔很大的儲存空間的問
→ EntHeEnd:題吧 @@
→ EntHeEnd:就我目前粗淺google到的資訊 大部分都有提到time stamp
→ EntHeEnd:如果有用到time stamp的話 應該就是用scan的做法吧 @@
→ EntHeEnd:我加上file字眼去找 有找到說用list做的了 謝謝樓上板友
→ EntHeEnd:回答 我先研究看看 ^^
→ EntHeEnd:不過用list的作法 再找LRU的目標很快 更新list的動作還是
→ EntHeEnd:免不掉scan...
推 mimi0213:更新應該也可以不用scan,以kernel的replacement policy
推 mimi0213:來說他會知道自己要更新的page是哪個,用array加上offset
推 mimi0213: 可以存取到那個struct,之後再存取struct裡面的lru membe
→ mimi0213: 這個list node就可以把他取出放到head
→ EntHeEnd:喔喔... 對齁 可是用list有一個問題就是要存的資訊量用在
→ EntHeEnd:檔案的時候 我都是用路徑和檔名來操作的話 這樣要記的東
→ EntHeEnd:西(路徑)可能很長 檔案多起來這個list佔的空間會很大 @@
→ EntHeEnd:等等... 其實我還沒搞懂上面的說法 orz...
→ EntHeEnd:我看過可以在O(1)找到 list node的做法是另外用hash map
→ EntHeEnd:過去該 list node 用以直接操作目標list node
→ EntHeEnd:用array的話 應該是把access的page的address當成array
→ EntHeEnd:index來用 然後array裡面存的是該page對應的list node
→ EntHeEnd:的address這樣吧 (概念上 @@)
→ EntHeEnd:不過要這樣操作 應該是在他page都是用編號(address)來代
→ EntHeEnd:表 可以避免掉要記路徑檔名的話 要使用太多空間的問題
→ EntHeEnd:如果對檔案的操作 都是用路徑檔名來操作 list... 好像不
→ EntHeEnd:太合用  @@？