AlgoVerse

سیاست‌های حافظه‌ی نهان (LRU، FIFO، دورترین در آینده)

سه حافظه‌ی نهان با یک اندازه به یک دنباله‌ی درخواست جواب می‌دهند و تعداد خطاها مقایسه می‌شود؛ «دورترین در آینده» بهینه است ولی باید آینده را بداند.

حافظه‌ی نهان (cache) کوچک و سریع است و فقط k عضو جا می‌گیرد. درخواستی که در آن نباشد یک خطا (miss) است: عضو باید آورده شود و اگر حافظه پر است، یکی بیرون برود. کدام؟

ادامه‌ی توضیح ↓
ورودی:
R 1×12 · k=3خروجی PDF

حافظه‌ی ۳ خانه‌ای و ۱۲ درخواست؛ خطاها: LRU ۱۰، FIFO ۹ و بهینه ۷.

  1. def caching(R, k):
  2. # Three caches of size k serve the same requests: LRU, FIFO and furthest-in-future (the offline optimum).
  3. reqs = R[0]
  4. lru = [] # least recently used first
  5. fifo = [] # oldest first
  6. opt = []
  7. hits = [0, 0, 0]
  8. misses = [0, 0, 0]
  9. rows = [] # for the picture: each request and the three caches after it
  10. for t in range(len(reqs)):
  11. x = reqs[t]
  12. if x in lru:
  13. hits[0] = hits[0] + 1
  14. lru.remove(x)
  15. lru.append(x)
  16. else:
  17. misses[0] = misses[0] + 1
  18. if len(lru) == k:
  19. y = lru.pop(0)
  20. lru.append(x)
  21. if x in fifo:
  22. hits[1] = hits[1] + 1
  23. else:
  24. misses[1] = misses[1] + 1
  25. if len(fifo) == k:
  26. y = fifo.pop(0)
  27. fifo.append(x)
  28. if x in opt:
  29. hits[2] = hits[2] + 1
  30. else:
  31. misses[2] = misses[2] + 1
  32. if len(opt) == k:
  33. y = furthest(reqs, t, opt)
  34. opt.remove(y)
  35. opt.append(x)
  36. rows.append([x, list(lru), list(fifo), list(opt)])
  37. return misses
  40. def furthest(reqs, t, cache):
  41. # The cached item whose next request is furthest away (or never comes).
  42. best = cache[0]
  43. best_next = -1
  44. for y in cache:
  45. nxt = len(reqs)
  46. for s in range(len(reqs) - 1, t, -1):
  47. if reqs[s] == y:
  48. nxt = s
  49. if nxt > best_next:
  50. best = y
  51. best_next = nxt
  52. return best

ناوردا: تا هر لحظه، تعداد خطاهای «دورترین در آینده» از هر سیاست دیگری بیشتر نیست.

شروع اجرا

x—
hits—
misses—

جدول هنوز خالی است.

متغیرهای محلی

k3

نارنجی = در همین گام عوض شد

R list

[1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]

Call stack

  1. caching()خط 1
گام ۱ از ۳۸۵
خط سیاه = served · خط نارنجی = گام کلیدیlru_miss: 0/10 · fifo_miss: 0/9 · opt_miss: 0/7 · served: 0/12 · lru_evict: 0/7 · fifo_evict: 0/6 · opt_evict: 0/4 · opt_hit: 0/5 · lru_hit: 0/2 · fifo_hit: 0/3
    توضیح

    مسئله

    حافظه‌ی نهان (cache) کوچک و سریع است و فقط k عضو جا می‌گیرد. درخواستی که در آن نباشد یک خطا (miss) است: عضو باید آورده شود و اگر حافظه پر است، یکی بیرون برود. کدام؟

    • LRU: عضوی که مدت بیشتری از آخرین استفاده‌اش گذشته.
    • FIFO: عضوی که زودتر از همه وارد شده.
    • دورترین در آینده (Belady): عضوی که درخواست بعدی‌اش از همه دیرتر است.

    چرا «دورترین در آینده» بهینه است

    با یک استدلال جابه‌جایی (فصل الگوریتم‌های حریصانه در CLRS) می‌شود نشان داد هر برنامه‌ی بهینه را می‌توان قدم به قدم به همین انتخاب حریصانه تبدیل کرد بی آنکه خطاها بیشتر شوند. ولی این سیاست آفلاین است: باید آینده را بداند.

    سیاست‌های آنلاین

    LRU و FIFO آینده را نمی‌دانند. هر دو k-رقابتی‌اند: خطاهایشان حداکثر حدود k برابر بهینه است، و هیچ الگوریتم قطعی آنلاینی بهتر از این نمی‌تواند (CLRS فصل ۲۷).

    ورودی

    R درخواست‌ها و k اندازه‌ی حافظه است.