The author while talking about buffer cache in the book - The design of the UNIX operating system, says that

a buffer is always on a hash queue, but it may or may not be on the free list.

What about the buffers in the free list that might not have been used at all? Wouldn't they be just part of the free list?

The data structures presented in the book are similar to the ones discussed here

The book talks about UNIX System V.


"What about the buffers in the free list that might not have been used at all? Wouldn't they just be part of the free list?"

I believe you answered your own question! From the same text:

"Every buffer is put on the free list when the system is booted."

"...it may or may not be on the free list."

It's on the free list at initialization of the system because it's, well, free! But maybe it is not when the system consumes a buffer and throws it into a hash queue for use, afterwards tossing it back into the free list.

Hash queue sort of says "Yes, I have seen this and used it in some capacity." It doesn't necessarily mean it has processed from the buffer queue yet.

The wording is a little confusing, and I had to dig up the text you referenced. I'm looking at pages 40/41 for clarity.

  • Thank you for the answer. Also, when the system is booted, wouldn't the hash queue be empty? If so, why does the author say that - "a buffer is always on the has queue"? – gaganso Jun 15 '17 at 13:49

The free list is an algorithm that is used for searching the unlocked and free buffer in the buffer cache. This data structure is used mainly for writing the buffer. Because for writing you can select any buffer where as for reading it requires a specific buffer.

Now, All the buffers present in the Free list may not be empty but are definitely unlocked. Also, all the buffers are present in the hash queue but not on the free list.

Because at the time of installation, admin is being asked about the number of queues and then it is decided to put all the buffers in those queues. Hence all buffers have to be listed in the hash queue by the system.

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.