I'm currently learning about database systems and they mention a buffer management system which brings in pages from disk to memory. This buffer manager allows higher layers to operate as if the entire database on disk is actually in memory.

The video I am watching talks about LRU and Clock as the page replacement policies when a page doesn't exist in the buffer pool.

However what I am confused about is that this video mentioned that LRU was log n in efficiency, but Clock is a better algorithm.

Specifically, imagine the buffer pool being a hash table with page id as the key. The value is dependent on if we are doing LRU or Clock.

If LRU was implemented with a heap data structure, maintaining this structure would be O(log n). ie A read of a page is constant to see if it's in the hash table. If it is, the value points to somewhere on the LRU data structure, which needs an update since the 'last used' time has changed. This means every read, updates the LRU so this is O (log n).

For a clock page replacement policy, modifying a page's last used bit to 0 is constant time, because the page id is a key in the hash table and modifying it's value is O(1).

However for a clock replacement policy, finding a page with a last used bit = 0 requires scanning the buffer pool. That is o(n). For LRU, we just grab the root node which is O(1) and delete it which is log(n) and insert a new node which is log(n). So LRU should be O(log n) to replace a page.

So I'm confused why people would use a Clock page replacement policy and believe it is better than a LRU page replacement policy? Did the educational video I watch make an error in stating Clock is more efficient?

Or am I missing something?

  • 1
    $\begingroup$ I would just like to comment how idiotic it is to analyze cache replacement algorithms asymptotically. The constant factor is so incredibly important here. $\endgroup$ – orlp Oct 9 '18 at 16:46
  • $\begingroup$ What are the constant factors I'm missing? $\endgroup$ – Terence Chow Oct 9 '18 at 18:12
  • $\begingroup$ Compare functions $T(n) = 5000$ and $T(n) = \log_2(n)$. The latter outperforms the former for any realistic $n$ yet the former is "$O(1)$" and thus "better". $\endgroup$ – orlp Oct 9 '18 at 18:42
  • $\begingroup$ Yes, but I'm talking about accessing a hash value and setting it in my example of O(1). That's just changing a value in memory. I don't see any constants that are make the O(1) vs O(log n) comparison invalid. $\endgroup$ – Terence Chow Oct 11 '18 at 0:44

If I understand correctly I think you are confusing the cache and the cache hit data structure. The structure isn't used to access the page, its used to store the hit count. For LRU, the OS needs to examine the hit count for every page in the cache memory to find the least recently used. When a page is hit, it is moved up in the list to prevent it from being evicted. I don't see how this would translate to a hash map.

The clock algorithm, only keeps track of a set of the most recently used pages (typically since the time since a new page was requested). The clock algorithm acts as an approximation of LRU without the maintenance of the linked list.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.