Implementation of the DEAR Scheme in FreeBSD

Figure 3 shows the overall structure of the buffer cache manager for the DEAR scheme as implemented in FreeBSD 2.2.5. The DEAR scheme applies different replacement policies for different applications. This requires a split of the buffer cache management module into two parts, one for block allocation and the other for block replacement. The module responsible for block allocation is the System Cache Manager (SCM). There is one SCM in the system. The module responsible for block replacement is the Application Cache Manager (ACM). There is one ACM for each application. This organization is similar to that proposed for application-controlled file caching [12]. Both of the modules are located in the VFS (Virtual File System) layer and collaborate with each other for buffer allocation and block replacement.

 

Figure 3: Overall structure of the DEAR scheme in FreeBSD 2.2.5.

An ACM is allocated to each process when the process is forked. When a block is referenced from the process, the associated ACM is called by the bread() or bwrite() procedure in the SCM (1) to locate the information about the referenced block using a hash table, (2) to update the block attribute that is changed by the current reference, (3) to place the block into a linked list that maintains the blocks referenced in the current detection period, and (4) to adjust the replacement order according to the application-specific replacement policy. To maintain the replacement order, the current implementation uses the linked list data structure for the LRU and MRU replacement policies and the heap data structure for the LFU replacement policy.

After the steps (1)-(4) are performed, a check is made to see whether the current detection period is over (i.e., checks whether the number of references from the process is equal to the length of the detection period). If so, the monitoring process explained in the previous section is invoked to detect the application's reference pattern. The detected reference pattern dictates the replacement policy of the ACM. If none of the detection conditions previously explained is satisfied, the default LRU replacement policy is used.

The structure of information maintained for each block by the ACM is <vnode #, block #, backward distance, frequency, forward distance, hp, bp, fp, cp>. The pointer hp is used to place the block into the hash table that is used to locate the information about the currently referenced block. The pointers bp and fp are used to place the block into the ordered lists for the backward distance and frequency block attribute types, respectively, which are constructed when the monitoring process is invoked. Finally, the pointer cp is used to place the block into the list of blocks referenced in the current detection period. This data structure is the main space overhead of the DEAR scheme.

The main time overhead of the DEAR scheme is that needed to order the blocks according to each block attribute value, which has an $O(n\log n)$ time complexity where n is the number of distinct blocks referenced in the detection period. This operation is invoked once at the end of each detection period for each block attribute type. Other time overheads include those needed to calculate the forward distance, backward distance, and frequency of blocks at the end of each detection period, which has a time complexity of O(n) where n is the number of distinct blocks referenced in the detection period.

Figure 4: Interaction between ACM and SCM.

The ACM and SCM interact with each other as depicted in Figure 4. When an application misses in the buffer cache, the ACM for the application makes a request to the SCM for additional buffer space (step (1) in Figure 4). If the SCM does not have any free buffer space, it sends a replacement request to one of the ACMs (step (2)). This operation is performed in the getnewbuf() procedure in the SCM, and the selected ACM is the one associated with an application whose current reference pattern is sequential. If there is no such application, the SCM simply chooses the ACM of the application with the global LRU block. The selected ACM decides the victim block to be replaced using its current replacement policy (step (3)) and deallocates its space to the SCM (step (4)). The SCM allocates this space to the ACM that requested the space (step (5)).