Buffer Management

Buffer Management

1. Changes to support buffered read/write features.

• Assign a table id number per each file.
• Implement a Buffer Management Layer between the Index Management Layer and the Storage(File Space) Management Layer
• Support separate source files and the compilation in use of Makefile

2. Pinning Strategy

• Initial State: the pin_cnt for every frame is set to 0 and the dirty flags are turned off.
• When a page is requested,
• The buffer manager checks the buffer pool to see whether some frame contains the requested page.
  • 1. If so, increment the pin_cnt of that frame.
  • 2. Otherwise,
    • The buffer manager chooses a frame for replacement based on the LRU(Least Recently Used) replacement policy
    • The buffer manager increments its pin_cnt.
    • If the dirty flag for the replacement frame is on, writes the page into the storage.
    • The buffer manager reads the requested page into the replacement frame.
• Finally, return the address of the frame containing the requested page to the requestor.
• When the requestor subsequently requests another page, unpin the pin_cnt of the current frame and then provide the requested frame.

3. Data structure for implementing buffers by the LRU policy

• I use the doubly circular linked list, rather than single linked list.
• The reason for choosing doubly circular list is that in linked list it takes O(n) (where n is the number of items in the list) of searching the Least Recently Used item.
• Even worse, if you are to finding second least recently used item, the design choice of the linked list will perform worse as the size of the buffer pool gets larger.
• Therefore, I chose the doubly circular linked list.
  • It can find both the Most Recently Used item and the Least Recently Used item in O(1).
  • Furthermore, it supports backward searching as well.