New version page

Operating System Support for Database Management

Upgrade to remove ads

This preview shows page 1-2 out of 7 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

COMPUTING PRACTICES Operating System Support for Database Management Michael Stonebraker University of California, Berkeley 1. Introduction Database management systems (DBMS) provide higher level user support than conventional operating systems. The DBMS designer must work in the context of the OS he/she is faced with. Different operating systems are designed for different use. In this paper we examine several popular operating system services and indicate whether they are appro- priate for support of database man- agement functions. Often we will see that the wrong service is provided or that severe performance problems exist. When possible, we offer some Permission to copy without fee all or part of this material is granted provided that the cop- ies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its "date appear, and notice is given that copying is by permission of the Association for Com- puting Machinery. To copy otherwise, or to republish, requires a fee and/or specific per- mission. This research was sponsored by U.S. Air Force Office of Scientific Research Grant 78- 3596, U.S. Army Research Office Grant DAAG29-76-G-0245, Naval Electronics Sys- tems Command Contract N00039-78-G-0013, and National Science Foundation Grant MCS75-03839-A01. Key words and phrases: database manage- ment, operating systems, buffer management, file systems, scheduling, interprocess commu- nication CR Categories: 3.50, 3.70, 4.22, 4.33, 4.34, 4.35 Author's address: M. Stonebraker, Dept. of Electrical Engineering and Computer Sci- ences, University of California, Berkeley, CA 94720. © 1981 ACM 0001-0782/81/0700-0412 $00.75. 412 SUMMARY: Several operating system services are examined with a view toward their applicability to support of database management functions. These services include buffer pool management; the file system; scheduling, process manage- ment, and interprocess communication; and consistency control. suggestions concerning improve- ments. In the next several sections we look at the services provided by buffer pool management; the file sys- tem; scheduling, process manage- ment, and interprocess communica- tion; and consistency control. We then conclude with a discussion of the merits of including all files in a paged virtual memory. The examples in this paper are drawn primarily from the UNIX op- erating system [17] and the INGRES relational database system [19, 20] which was designed for use with UNIX. Most of the points made for this environment have general appli- cability to other operating systems and data managers. 2. Buffer Pool Management Many modern operating systems provide a main memory cache for the file system. Figure 1 illustrates this service. In brief, UNIX provides a buffer pool whose size is set when Communications of the ACM the operating system is compiled. Then, all file I/O is handled through this cache. A file read (e.g., read X in Figure 1) returns data directly from a block in the cache, if possible; otherwise, it causes a block to be "pushed" to disk and replaced by the desired block. In Figure 1 we show block Y being pushed to make room for block X. A file write simply moves data into the cache; at some later time the buffer manager writes the block to the disk. The UNIX buffer manager used the popular LRU [15] replacement strategy. Fi- nally, when UNIX detects sequential access to a file, it prefetches blocks before they are requested. Conceptually, this service is de- sirable because blocks for which there is so-called locality of reference [15, 18] will remain in the cache over repeated reads and writes. However, the problems enumerated in the fol- lowing subsections arise in using this service for database management. July 1981 Volume 24 Number 7read X 1 main memory [ cache ] D ® (9 I-'- "~'/ disk I 3 Fig. 1. Structure of a Cache. 2.1 Performance The overhead to fetch a block from the buffer pool manager usu- ally includes that of a system call and a core-to-core move. For UNIX on a PDP-11/70 the cost to fetch 512 bytes exceeds 5,000 instructions. To fetch 1 byte from the buffer pool requires about 1,800 instructions. It appears that these numbers are somewhat higher for UNIX than other contemporary operating sys- tems. Moreover, they can be cut somewhat for VAX 11/780 hardware [10]. It is hoped that this trend to- ward lower overhead access will con- tinue. However, many DBMSs includ- ing INGRES [20] and System R [4] choose to put a DBMS managed buffer pool in user space to reduce overhead. Hence, each of these sys- tems has gone to the trouble of con- structing its own buffer pool man- ager to enhance performance. In order for an operating system (OS) provided buffer pool manager to be attractive, the access overhead must be cut to a few hundred instruc- tions. The trend toward providing the file system as a part of shared virtual memory (e.g., Pilot [16]) may provide a solution to this problem. This topic is examined in detail in Section 6. 2.2 LRU Replacement Although the folklore indicates that LRU is a generally good tactic for buffer management, it appears to perform only marginally in a data- base environment. Database access in INGRES is a combination of: (1) sequential access to blocks which will not be rereferenced; (2) sequential access to blocks which will be cyclically rerefer- enced; (3) random access to blocks which will not be referenced again; (4) random access to blocks for which there is a nonzero prob- ability of rereference. Although LRU works well for case 4, it is a bad strategy for other situ- ations. Since a DBMS knows which blocks are in each category, it can use a composite strategy. For case 4 it should use LRU while for 1 and 3 it should use toss immediately. For blocks in class 3 the reference pattern is 1, 2, 3 ..... n, 1, 2, 3 ..... Clearly, LRU is the worst possible replace- ment algorithm for this situation. Unless all n pages can be kept in the cache, the strategy should be to toss immediately. Initial studies [9] sug- gest that the miss ratio can be cut 10-15% by a DBMS


Download Operating System Support for Database Management
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Operating System Support for Database Management and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Operating System Support for Database Management 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?