Disk block cache management for a distributed shared memory...

Details Disk block cache management for a distributed shared memory... Disk block cache management for a distributed shared memory...

1998-05-13

2002-05-14

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S121000, C711S147000, C711S148000, C710S104000, C709S200000, C709S201000, C709S241000, C707S793000, C712S028000, C712S029000, C712S030000, C712S031000, C712S034000

Reexamination Certificate

active

06389513

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to cache management for computer systems. More particularly, this invention relates to management of disk blocks cached in the memory of a distributed shared memory computer system. An example of such a computer system is a NUMA (non-uniform memory access) machine.
BACKGROUND OF THE INVENTION
In a computer system, one of the tasks of the operating system kernel is to maintain files such as data on mass storage devices (such as disks) so that processes executing in the computer can properly access these files. For example, when a process,wants to read data from a file stored on disk, the kernel brings the data into the main memory of the computer where the process+an access it. Similarly, the kernel often writes data in main memory back to disk to save the data.
The kernel could read and write directly to and from the disk for all file system accesses, but system response time and throughput would be poor because disk access times are quite slow. The kernel therefore attempts to minimize the frequency of disk access by keeping a pool of internal data buffers in main memory, called the buffer cache. A typical buffer cache and its management are described in
The Design of the UNIX Operating System
, by Maurice J. Bach (Prentice-Hall 1986), which is incorporated by reference herein and summarized below. Traditional UNIX systems, for example, use a dedicated area in memory called the block buffer cache to cache blocks accessed through the file system; the virtual memory system caches process text and data pages separately. Modern UNIX systems integrate the buffer cache within the virtual memory system.
When reading blocks of data from disk, the kernel attempts to read first from the buffer cache. If the data is already in the cache, the kernel does not have to read from disk. If the data is not in the cache, however, the kernel reads the data from disk and caches it, using an algorithm that tries to save as much good data in the cache as possible. Similarly, the kernel caches data that it writes to disk so that the data is available in memory if the kernel later tries to read it.
During system initialization, the kernel allocates space for a number of buffers, configurable according to memory size and system performance constraints. A buffer consists of two parts: a data array of memory that contains data blocks from disk and a buffer header that identifies a particular data array. Because there is a one-to-one mapping of buffer headers to data arrays, both parts are often referred to in the art as a “buffer.” The context of a particular reference should make clear which part is being discussed. The data in a buffer corresponds to the data in a logical disk block in a file, and the kernel identifies a buffer's contents by examining fields in the buffer header. The buffer is the in memory copy of the disk block; the contents of the disk block map into the buffer, but the mapping is temporary and exists only until the kernel decides to map another disk block into that particular buffer.
The buffer header contains a number of fields and pointers that provide information about the buffer and its contents. Several fields uniquely identify the buffer such as by the file system and block number of the data on disk. Another field gives the status of the buffer such as locked, valid, etc. A pointer points to the associated memory array that stores the data. The buffer header also contains two sets of pointers used by buffer allocation algorithms to maintain the overall structure of the buffer pool.
One of these sets of pointers relates to a free list of buffers maintained by the kernel. Data is cached in the buffer pool according to a least recently used algorithm. After the kernel allocates a buffer to a disk block, it cannot use the buffer for another block until all other buffers have been used more recently. The free list preserves the least recently used order. The free list is typically implemented as a circular, doubly linked list of buffer headers with a dummy buffer header that marks its beginning and end; the forward and backward pointers in the header link the buffer to the list. Every buffer is put on the free list when the system is booted. The kernel normally removes a buffer from the head of the free list when it needs to allocate a buffer for a disk block and places a buffer at the tail of the free list when the buffer is available for allocation. Hence, the buffers that are closer to the head of the free list have not been used as recently as those that are further from the head.
The other set of pointers is used for efficient searching of the buffer pool for a particular buffer. Rather than simply group all of the buffers into the buffer pool, the kernel organizes the buffers into separate queues, hashed as a function of a disk block attribute such as its address (e.g., file and block offset). The kernel links the buffers on a hash queue into a circular, doubly linked list using the forward and backward pointers in the set. A hashing function is chosen that uniformly distributes the buffers across the set of hash queues, such as a modulo function.
FIG. 1
shows a cache management data structure (also known as buffer cache metadata) that includes headers of the hash queues on the left side and associated rows of buffer headers for each hash queue on the right side. The queue headers are also known as “buckets” and the queues as “chains” or “lists” of buffer header elements. With a hashing function of modulo
4
, all buffers whose disk block numbers are multiple of 4 are elements of the first hash queue, buffers whose disk block numbers have a remainder of 1 are elements of the second hash queue, etc.
FIG. 1
also shows how the free list is implemented through the doubly linked list. Buffer
3
is at the head of the free list and buffer
10
is at the tail.
In a traditional implementation each buffer in the buffer cache exists on a hash queue. A buffer may also be on the free list if its status is free. Because a buffer may be simultaneously on a hash queue and on the free list, the kernel has two ways to find it. It searches the hash queue if it is looking for a particular buffer, and it removes a buffer from the free list if it needs a buffer for storing a disk block.
Although buffer caches were initially used in operating systems, they are not limited to such. They also find use in application programs including database management systems (DBMS) or database servers. These servers manage large databases of information (data) such as product information, employee information, or airline reservations. DBMSs are often configured as a client/server model with a database of information and a database server as the back end and inexpensive desktop computers as front ends, or clients. The client runs user-friendly applications that enable a user to communicate with the database server. User requests to a database server are called queries.
In a database the information is physically stored in several files but is logically organized into tables of related data such as employees, products, etc. A table consists of a set of rows and columns. A column represents a category of data, such as Employee Name, while a row represents specific instances of those categories—for example, all of the data for one employee. A table is a logical area of storage made up of data segments that are allocated by the database server for storing table data. For example, in an employee table, the data segment stores such information as the names of the employees, their hire dates, and so forth. A data segment, in turn, is made up of data blocks. A data block is the smallest logical unit of storage. A data block consists of row data (the actual data contained in rows or parts of rows of a table), free space (space that can be used for adding new rows), and block information (block attribute, applicable table, and other header information). Though a data block is a logical structure, it corresponds to a certain number of bytes of physica

Affiliated with

Also associated with

Rating

Disk block cache management for a distributed shared memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Disk block cache management for a distributed shared memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Disk block cache management for a distributed shared memory... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2873474