performance - Implementing LRU with timestamp: How expensive is memory store and load? -

i'm talking lru memory page replacement algorithm implement in c, not in java or c++.

according os course notes:

ok, how implement lru? idea 1): mark touch timestamp. whenever need evict page, select oldest page (=least-recently used). turns out simple idea not good. why? because every memory load, have read contents of clock , perform memory store! clear keeping timestamps make computer @ least twice slow. i

memory load , store operation should fast. is necessary rid of these little tiny operations?

in case of memory replacement, the overhead of loading page disk should lot more significant memory operations. why care memory store , load?

if notes said isn't correct, real problem implementing lru timestamp?

edit:

as dig deeper, reason can think of following. these memory store , load operations happen when there page hit. in case, not loading page disks, comparison not valid.

since hit rate expected high, updating data structure associated lru should frequent. that's why care operations repeated in udpate process, e.g., memory load , store.

but still, i'm not convincing how significant overhead memory load , store. there should measurements around. can point me them? thanks!

memory load , store operations can quite fast, in real life cases memory subsystem slower - slower - cpu's execution engine.

rough numbers memory access times:

• l1 cache hit: 2-4 cpu cycles
• l2 cache hit: 10-20 cpu cycles
• l3 cache hit: 50 cpu cycles
• main memory access: 100-200 cpu cycles

so costs real time loads , stores. lru, every regular memory access incur cost of memory store operation. alone doubles number of memory accesses cpu does. in situations slow program execution. in addition, on page eviction timestamps need read. quite slow.

in addition, reading , storing timestamps means taking space in l1 or l2 caches. space in these caches limited, cache miss rate other accesses higher, cost more time.

in short - lru quite expensive.