Skip to content

DA7. File Processing and External Sorting

Statement

  • Using Jeliot, execute the following algorithm which implements a buffer pool algorithm. The algorithm offers options for three different heuristics including LRU, LFU, and FIFO.
  • The algorithm will request the following information to be entered Menu: 1. FIFO, 2. LRU, 3. LFU
  • For this assignment you must run the algorithm for each menu option as specified and respond to the questions.

Solution

  • The image below shows the output of execution the algorithm for each menu option, according to the input specified in each section below.
  • The code starts by asking user to enter the number of buffers and the number of pages to be placed in the buffer pool, buffer is set to -1 by default.
  • The printed -1 means that the buffer is empty, and the buffer pool is not full yet, and the next page will be placed in the buffer pool.
  • When the buffer pool is full, and a new page is entered/requested, the algorithm will replace the page according to the selected heuristic, and the buffer pool will be updated.
  • The replaced page must be written to the disk before throwing it in, this will increase the number of I/O requests.
  • If it was the opposite, the requested page must be brought from the disk, and the number of I/O requests will be increased.

Option 1 (FIFO)

  • Use the following input:
Buffers: 2   // the size of the buffer pool
Pages: 6    // the number of items to place into the pool.
Page Values:  5, 5, 5, 10, 20, 5
  • Questions:
    1. Describe the heuristic used by the algorithm.
    2. Under what condition, the heuristic will not be efficient? Efficient means the number of I/O request is minimized assuming that value 5 is used more often than the other values.
    3. Describe a situation where the heuristic will be efficient. (suggest optimizations for this heuristic).

Option 1 (FIFO) - Solution

  1. The FIFO algorithm is the simplest of the three algorithms, it simply replaces the oldest page in the buffer pool with the new page. It is implemented as a Queue data structure, where the oldest page is at the rear of the queue, and the newest page is at the front of the queue.
  2. If a page is requested frequently every now and then, assuming the buffer pool size is less than the total of program pages and the buffer is full, these pages need to always be brought from the disk, as they are always replaced by the new pages before they are requested again. In the example above, the last 5 was requested from the disk, while the first three 5s were just in the buffer pool.
  3. Well, if the repetitive requests come as sequence, like the 5 5 5 in the example above, the FIFO algorithm will be efficient, and the pages will always be in the buffer pool, and no I/O requests will be made.

Option 2 (LRU)

  • Use the following input:
Buffers: 2   // the size of the buffer pool
Pages: 6    // the number of items to place into the pool.
Page Values:  5, 10, 5, 10, 20, 5
  • Questions:
    1. Describe the heuristic used by the algorithm.
    2. Describe a situation where the heuristic will be efficient. (suggest optimizations for this heuristic).

Option 2 (LRU) - Solution

  1. LFU stands for Least Frequently Used, it is implemented as a Priority Queue data structure, where the least frequently used page is at the rear of the queue, and the most frequently used page is at the front of the queue. Whenever a buffer page is accessed, its priority is increased, and the page is moved towards the front of the queue. New pages are always added to the rear of the queue.
  2. If the program contains a few pages that are repetitively requested, like the 5, 10 in the example above, if the entire program was made of sequence like that 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, ..., the LRU algorithm will be efficient, and the pages will always be in the buffer pool, and no I/O requests will be made.

Option 3 (LFU)

  • Use the following input:
Buffers: 2   // the size of the buffer pool
Pages: 6    // the number of items to place into the pool.
Page Values: 5, 10, 20, 25, 30, 35
  • Questions:
    1. Describe the heuristic used by the algorithm.
    2. What happens when no integer is repeated in the input page values?
    3. Describe what happens in the buffer pool when a value is repeated in the page values.

Option 3 (LFU) - Solution

  1. LFU stands for Least Frequently Used, it is implemented as a Queue data structure where timestamp of the last access is tracked along with the number of accesses. This solves problems like: if the program requested a page too many times in the past, it is highly likely done with it and will be no longer requested.
  2. If no repetitive pages are requested, the LFU algorithm will be inefficient, and the pages will always be brought from the disk, and no I/O requests will be made.
  3. If a value is repeated multiple one or more times within the max time interval, the page will be in the puffer pool and no I/O request is made; but if the page is requested after the max time interval, the page needs to be brought from the disk, and the number of I/O requests will be increased.

References