Theoretical Question on Buffering

[aceman817]

Hey guys! Hopefully one of you will be able to lead me in the right direction. I have come across a question in one of my CS courses that is a little puzzling to me:

Suppose that a driver is configured with 8 disk block buffers. What is the best possible read performance improvement of a program that uses this driver (compared to one that uses no buffering)? What are the conditions under which the performance is the best?


I can't seem to find any good sites on buffering to use as a reference. I don't think it would be just 8 times better. Would it go something like i, i+1, i+2, i+3, i+4, i+5, i+6, i+7? Any suggestions are greatly appreciated!

 

[kamper]

I'm no kernel expert, but I'll take a shot.

Assume there's a file on the disk and a program that's gonna read it. Nothing's started yet, so the buffer is empty. The program reads the first block of the file (or part of it). This takes the full amount of time that a non-buffered situation would take. In order to improve future performance, the driver is now going to have to guess that the program will want the next 7 blocks and will have to asynchronously read them while the program deals with the first block. If the program then proceeds to read the next 7 blocks, it will get an essentially instantaneous response (compared to the 'very long' time required to read 7 blocks from disk). In order for this to work, though, there would actually have to be a sufficient amount of time between when the program reads the first block and the next 7 to allow the driver to get that data into the buffer. If there are more than 8 blocks in the file, the driver will have to start guessing again which blocks will be needed when.

I suppose even the first block could be preloaded when the app opens the file. In reality, read prediction probably won't work nearly so cleanly. Writes, on the other hand, can be sped up very easily with buffering (because the driver doesn't need to anticipate them).

 

[itachi]

umm.. you're overcomplicating.

the best possible performance is that of the memory.. and it would occur when an application requests a block that's in the buffer.

for example, for a sequence of disk accesses (H = hit, M = miss):
0, 1, 2, 1, 2, 0, 3.. the result of the buffer check would be : M, M, M, H, H, H, M
for all misses, the program is blocked until the block is read.

 

[aceman817]

Thanks for the tips, guys. Do you happen to know of any good sites for reference where I can explore the concept further?

 

[sunase]

There are many algorithms for managing memory buffers: FIFO, LRU, OPT, NUR, and stack/working set algorithms in general, etc.. Web sites generally won't cover the details sufficiently to be worthwhile. You should be using real resources like text books, class notes/lectures, papers, and whatnot for things like this.