1
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • 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
  • 1
    $\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
  • $\begingroup$ @Terence nobody cares one bit how long it takes to modify data structures in memory. The only thing that counts is reading from disk / writing to disk. Nanoseconds vs milliseconds. $\endgroup$ – gnasher729 Apr 27 at 11:23
1
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

As you said, For LRU, if implemented using Heap data-structure:

Cost of a Read operation: O(log n)
Cost of a Write operation: O(log n)

For Clock:

Cost of a Read operation: O(1)
Cost of a Write operation: O(n)

A buffer management system uses a replacement policy to replace the pages in the buffer with the new page that is to be allocated some space in the buffer.

A buffer manager is more or like a cache mechanism.

As per your deduction, it is true that the cost of a write operation is cheaper in the Clock algorithm than compared to LRU.

But! Do you think there are going to be more writes than reads? If there are more number of writes, then the use of a buffer manager(or caching mechanism) comes into question. When there are more writes, one can directly fetch a data page from the disc and serve to the user rather than incurring the extra cost of replacing pages in the buffer.

So a caching mechanism, such as buffer manager, is preferable when there are more reads than writes. Since there are more reads, the Clock algorithm performs better than the LRU.

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

I'm unclear if you're asking about databases or operating systems here.

Databases have different tradeoffs, because "accessing" a page is a coarse-grained operation that typically includes locking it as part of a transaction, so you have the scope to do more work every time a page is "accessed". Operating systems don't have that luxury.

For example, imagine that you put all pages in a doubly-linked list. Every time you access a page, you move it to the head of the list. The least recently-used page is then always at the tail of the list. The time taken is $O(1)$ per access, with no heap needed.

This used to be practical for databases, but as the number of CPUs increased, the page list experienced high contention, and this limits concurrency. But there are modern variants that aren't as expensive and still require only $O(1)$ work per access.

| cite | improve this answer | | | | |
$\endgroup$

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.