Block Pattern Based Buffer Cache Management Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract- Efficient caching of the data block in the buffer cache can short circuit the costly delays associated with access to secondary storage. Pattern based buffer cache management technique is being discussed for enhancing the system performance. The technique determines the victim block to be replaced by identifying the I/O access patterns. The blocks are stored in separate, pattern based partitions of the cache, which supports multiple replacement policies to best utilize the cache under that reference pattern. As the suggested technique aims at improving the buffer cache hit ratio it could be used for enhancing the performance of multimedia application and can be useful for power saving in database server as increased cache hit ratio reduces the memory traffic and thus saves the energy.

Keywords- buffer cache, replacemt policies, access patterns, program counter, cache partition


Modern operating systems employ buffer cache for enhancing the system performance affected by the slower secondary storage access. Effectiveness of the block replacement algorithm play a key role in determining the system performance. Design of effective replacement algorithm is an active research area in the field of operating system. Oldest and widely used replacement algorithm in real time system is the LRU (Least Recently Used) [1, 2] due to its effective use of principle of locality.

Due to minimal management overhead and reduced complexity and simple implementation current GNU/Linux kernel still implements LRU replacement policy. But these policies are dependent on the application working set and suffer from degraded performance when weak locality of reference is exhibited by the application working set having a large size compared to the cache size [3].

In today's world where everything is available on one click either through internet or hand held devices information is buffered in memory everywhere. Yang and Zhang showed that through correct prefetching and caching of the requested data the network traffic and bandwidth could be saved to a larger extent [4].

For better performance gain and improved cache hit ration the information in accesses made to the data blocks by the I/O request are reduced by recent replacement algorithm [5-8]. These techniques exploit the patterns exhibited in the I/O workload such as mixed, thrashing, periodic and apply specific replacement policies to best utilize the cache under that reference pattern.

The paper is organized as follows. Initially the concept of buffer cache is explained in section 1. In Section 2 some of the techniques for buffer cache management are discussed. Section 3 describes methods used for handling the cache partition. The paper concludes by suggesting a efficient pattern based technique for buffer cache management in Section 4. Section 5 and Section 6 deals with the expected result and conclusion.

Buffer Cache organization

Inside the computer system the storage devices such as the registers, cache, main memory are ordered at various levels as depicted in "Fig.1". At the top level are the registers were data is accessed at the speed of processor usually in one clock cycle. At next higher level exists programmer transparent cache memory implementable at one or more levels and handled by memory management unit. Primary memory is present next one level up managed by the operating system.

Storage Hirerachies

A noticeable fact is at higher levels the space available for storing the data increases but the access time, and the transfer bandwidth, i.e. the rate at which the information is transferred between the adjacent levels is decreased. Buffer cache is introduced as an interface in user area between the main memory and disk drives. Thus buffer cache aims to reduce the frequency of physical disc access and enhance the system throughput.

Direct access to even a single byte or character from the secondary storage is prohibited. Whenever the request for the data or instruction arise the operating system kernel initially searches for the block, containing the requested byte, in the buffer cache. If the request is not satisfied, the block containing the requested byte is searched from the secondary disk, brought into the buffer cache and finally passed to main memory and then to the cache. And as the buffer resides in main memory the access time between main memory and buffer cache is negligible.

For efficient management the buffer cache is divided into header and data area as depicted in "Fig 2".

Fields Inside Buffer Cache

The fields of the buffer cache are discussed:-

Device Number It comprise of the devices in the system. For e.g.: during installation we may have one or more file systems or logical partitions of single disk are assigned unique device no.

Block Number It points to the unique block of a particular device.

Status Field It determines the state of the buffer cache when used by the processes under execution.

Data Area The data blocks fetched from the disk are placed into the data area of the buffer cache. The size of the data area is same as the block of secondary storage.

Pointers The remaining space is utilized by the data structure or management techniques used for efficient buffer cache utilization.

Whenever process executes it makes use of one buffer cache at a time. Firstly the status of the block is locked, then the contents of the data area are used and at the end the block is released.

Whenever the page fault occurs kernel searches that whether the requested block is present in the buffer cache or not. If found the block is transferred to the user area, and as it is main memory to main memory transaction transfer bandwidth is negligible. If the block is not found it is fetched from the secondary storage and placed into buffer cache. I

It may happen that the buffer cache is full and no free buffer is available for storing the data. Then one of the blocks needs to be replaced. Thus an efficient replacement policy is need that can determine the block to be replaced that can lead to improved system performance.

Also as there would be many buffers in the system linear searching of the available buffer, either free or contacting data, would increase the application execution time and cause management overhead. Hence data structures like hash tables, doubly link list are used for managing the buffer cache.


Static Partioning

A static cache partitioning [9] technique divided the cache memory into prefetch buffer and cache buffer. The technique was not able to cope with reduces cache hit rates due to reasons as limited size of the buffer and prefetch cache, non redundant pattern of file access, large working sets.

Marginal Gain Functions

To address the problem of allocating the data blocks among the various cache partition, a widely known concept of resource allocation strategies, marginal gain [10] is used. It is defined by the following equation

MG(n) ≈ Hit(n) - Hit(n-1)


MG(n): Determines the expected number of extra buffer hit per unit time that would be obtained by increasing the buffer size from (n-1) to (n)

Hit(n) : With n available buffers it is the expected number of buffer hit per unit time.

Dynamic Partioning

Cost-benefit analysis [11] partitioned the aggregate cache by using the probabilities of blocks future access for weighing the cost of ejecting or allocation a block to cache partition.

To take maximum benefit of the available cache memory dynamic cache management techniques were suggested. One of such technique is SA-W2R [12]. SA-W2R integrated buffer management and constant prefetching and allowed the integration of other replacement policies in the modular approach.

APACS (An Automatic Prefetching and Caching System) [13] used the hit ratio of the cache buffer and prefetch buffer partitions of the main memory as an indicator for managing the cache partition by taking into account the full context information about the I/O access patterns.


The patterns are precisely identified at the block level, application level, file level and program context level by the pattern based replacement algorithms. Several algorithms have been proposed in the past the identified the patterns at each of this level.

Level Based Replacement Algorithm

SEQ [19] technique worked at the block level and handled long sequence page cache misses by applying Most Recently Used policy.

At application level DEAR [6] accurately classified the I/O access patterns of each of individual running application into categories as sequential, temporal etc.

Unified Buffer Management [5] worked at file level and classified the references made to individual files. The buffer cache wad divided based on the patterns being detected and marginal gain function was used for managing the block among various partitions.

At program context level Program Counter Based Classification (PCC) [7] and Adaptive Multi Policy caching (AMP) [8] exploited the program counter exhibited in the application binary code for accurately identifying the access pattern and enhancing the cache performance.


To avoid the delays associated with disk access, data blocks are read in advance and kept in main memory in prefetching mechanism. Predictive and Instructive/Informed are the two categories of prefetching. The past behaviors of I/O request, explored from the traces of the system call, are used in predictive caching implemented at the file level. Informed prefetching is based on hints inserted by the complier or the programmer.

APACS [13] was the extension of [12]. The technique implemented at file level, mitigated the shortcoming of prefetching by employing dynamic cache partition, prefetching pipelining and prefetch buffer management.

LPU (Least Popularly Used) [14] replacement algorithm managed the buffer cache by taking into account temporal locality and content locality of I/O request. It not only considered the frequency of data blocks but also the similarity in the content of the block being accessed.

Reuse Distance Prediction

The concept of reused distance was used by some of the replacement strategies for better utilization of the cache. Reused distance of a block or address is time difference between two consecutive references to this block address [15]. The reused distances were obtained by making use of instruction program counter for optimizing the performance of Level 2 cache.

Reuse distance of cache blocks were related to memory access instructions in [16]. Re-Reference Interval Prediction (RRIP) [17] technique suggested Static RRIP (SRRIP) that was scan resistant and Dynamic RRIP (DRRIP) that was both scanresistant and thrash resistant to overcome the drawbacks of the widely used LRU.

SHiP: Signature Based Hit Predictor [18] technique enhanced the cache performance by correlating the re-reference behavior of each cache line with the signatures associated with the memory region, program counter and instruction sequence history.


System Modules

The system consists of three modules as depicted in architectural design in "Fig.3".

Detection Module:

Access pattern of the data blocks from the I/O request are determined by this module. The suggested technique verifies the temporal locality, decisive in determining the block to be replaced, by predicting the reuse distance using the program counters that determine the memory location of the instructions.

Architectural Design of the Pattern Based System

Allocation Module:

The buffer cache partitions are managed by the allocation module. The following steps are taken:

The number of buffer cache partition depends upon the types of patterns detected by the detection module.

Once the data blocks are fetched they are placed in the free space allocated to their respective partition. For e.g. block accessed are placed in sequential partition and block accessed at regular interval are placed in looping partition.

As the block migrates between different partitions an efficient scheme is needed for managing the block movement. Traditionally marginal gain functions discussed above were used for managing the buffer cache partition.

Replacement Module

When the blocks need to be replaced from their respective partition use of efficient replacement policies significantly enhance the system performance. By using different replacement policies best suited for particular pattern the buffer cache under that pattern can be efficiently utilized. For sequential pattern MRU works well and for looping both MRU and LRU are suited.

Examples of I/O Access Patterns

Access patterns would be classified into following categories:

Sequential Reference: Blocks referenced only once and never revisited would be considered to exhibit sequential references.

Looping Reference: Blocks referenced at the regular interval are classified as looping.

Mixed Pattern: Blocks accessed on frequent bases are said to have mixed pattern.

Others: If none of the others patterns are found.

Data Structures

For predicting the patterns accurately and managing the buffer cache hash tables are used. File Table is used for maintain the updated information for consecutive referenced blocks. The attributes of files such as inode, starting block, ending block, reference period represented as function of time, are used for identifying the sequence. Program Counter (PC) table is used to identify accesses pattern of the instructions. Instructions are identified by the use of the program counter. Information about unique blocks and the references issued to them are managed in PC table.

Pattern identification Process

The suggested technique attempts to precisely identify the I/O access pattern through the following steps

When a block is referenced it is correspondingly checked in the file hash table. If found belonging to any file sequence, the fields associated with the block entry are updated. If not found belonging to any sequence a new block entry is made in the file hash table.

Simultaneously the information obtained from the program context of the instruction that issued the I/O request are updated in the PC table.

A threshold is set for distinguishing among the patterns. Based on the condition associated with the threshold value the pattern is identified.

Data block pattern is decided based on the results retrieved from the File table and PC table.


The suggested technique identifies the pattern by exploiting the pattern at the file or program context level. The threshold is said to 3. The concept is initially the blocks are classified as others. If threshold is crossed they are grouped as sequential and if referenced again then categorized as looping. "Fig 4" depicts the scenario of the block request.

Example of Pattern Classification

Comparison of suggested pattern based technique with UBM and PCC are shown.

Proposed Pattern Based Technique: File A is initially classified as other. After it is visited the program counters are updated and the access pattern of PC1 is changed to sequential as the threshold is crossed. When the file A and file B are accessed again their information is updated in the file table and then they are classified as looping. Noticeable fact is though the file C is visited for the first time it is correctly classified by the proposed technique as looping compared to PCC and UBM.

UBM: As the threshold is considered three UBM always classifies the File A incorrectly as others. Similarly first three blocks of File B were initially classified as others and fourth block as sequential. After File B was visited again the block references were classified as looping.

PCC: Though sequential references in UBM were considered to be contiguous block within one file, PCC considered sequential block to belong to discrete files. PC1 was classified as others when accessing the first three blocks and as sequential when it is encountered again. Thus it can be seen that proposed technique can identify the access pattern more precisely compared to PCC and UBM pattern based classification technique.


Pattern based buffer cache management technique would endeavor to precisely identify the I/O access pattern and enhance the system performance by reducing the execution time through increased buffer cache hit ratios. An efficient technique would be employed for managing movement of the block among the various partitions of the buffer cache. The performance of replacement schemes implemented for utilizing the cache partitions to the best of their abilities would be enhanced up to 10 to 15 % compared to LRU by the proposed technique.


The proposed technique would lead to efficient utilization of the partition based buffer cache by taking into account the patterns of the block being accessed by the I/O request, and would enhance the system performance by improving the cache hit ratio, and reducing the number of I/O request issued to secondary storage and the application response time.