Here's what Alexandre has to say about using a Queue for the extra credit part of HW3, and he's right (as usual ):

I was working on implementing Queue structure for the Homework3 and then I realized that “classic” Queue, which grants access only to the first element (and to the last element, if Queue is bidirectional), would not be efficient in some particular sequence of pin/unpin. It could happen if we want to pin the buffer which is unpinned, but it is not the first in the queue.

For example, in the test program you gave us:

      bufferManager.unpin( buffers[3] );

      bufferManager.unpin( buffers[1] );

      bufferManager.unpin( buffers[2] );

Let’s assume that these buffers got completely unpinned (pins=0). If we use Queue to store buffers, then buffers will be stored in order:

      (head) - 3 - 1 - 2 - (tail)

So what would happen if we do the following?

      bufferManager.pin( buffers[2] );

According to the LRU buffer replacement policy, buffer #3 will be used to store block #2. That means, as result we will have the following buffer pool

( in format block#(pins) ):

      0(1), 1(0), 2(0), 2(1)

So we shall have block #2 stored twice. (Will the each of blocks #2 contain the same information?)

In fact, simpledb somehow checks if the block to be pinned is already in the buffer pool. Therefore, we are not getting same blocks stored in different buffers.

The problem is that we have to access particular Buffer stored somewhere in the middle of the Queue. If we assume that Queue is implemented based on LinkedList, then accessing a stored element could be similar to the searching though buffer pool. So we gained nothing by using Queue.

PoonamPawar wrote:

cysun wrote:

Here's what Alexandre has to say about using a Queue for the extra credit part of HW3, and he's right (as usual ):

I was working on implementing Queue structure for the Homework3 and then I realized that “classic” Queue, which grants access only to the first element (and to the last element, if Queue is bidirectional), would not be efficient in some particular sequence of pin/unpin. It could happen if we want to pin the buffer which is unpinned, but it is not the first in the queue.

 

For example, in the test program you gave us:

 

      bufferManager.unpin( buffers[3] );

      bufferManager.unpin( buffers[1] );

      bufferManager.unpin( buffers[2] );

 

Let’s assume that these buffers got completely unpinned (pins=0). If we use Queue to store buffers, then buffers will be stored in order:

 

      (head) - 3 - 1 - 2 - (tail)

 

So what would happen if we do the following?

 

      bufferManager.pin( buffers[2] );

 

According to the LRU buffer replacement policy, buffer #3 will be used to store block #2. That means, as result we will have the following buffer pool

( in format block#(pins) ):

 

      0(1), 1(0), 2(0), 2(1)

 

So we shall have block #2 stored twice. (Will the each of blocks #2 contain the same information?)

In fact, simpledb somehow checks if the block to be pinned is already in the buffer pool. Therefore, we are not getting same blocks stored in different buffers.

 

The problem is that we have to access particular Buffer stored somewhere in the middle of the Queue. If we assume that Queue is implemented based on LinkedList, then accessing a stored element could be similar to the searching though buffer pool. So we gained nothing by using Queue.

So,does that mean we should not use queue,priority queue,LinkList for extra credit?

You can use anything you want, but obviously it has to be something that works correctly and more efficient than O(n) (and prefereably O(1)).