Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-25
2004-04-20
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06725244
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer systems and, more particularly, to opening and closing files by operating systems running on computer systems.
2. Description of the Related Art
It is well known that a computer system executes an operating system to perform fundamental operations of the computer system. In this regard, an operating system opens files for use by a computer system and then assigns the open file a numeric number known as a file descriptor. For example, the command open (“/usr/bin/ls”) is an open system call for a UNIX-based operating system and “/usr/bin/ls” is the path name to a particular file to be opened. In response to the open system call, the operating system returns the smallest available file descriptor. The file descriptor is an integer that represents the file that has been opened by the open system call. Hence, once a file has been opened, the file descriptor is used in subsequent commands that access the open file. One advantage of using file descriptors over path names is that the operating system readily understands the integer value as identifying a particular file without having to parse a path name to locate the particular file. Another advantage of using file descriptors is that some system calls do not initially specify particular files (i.e., path names) to be processed so the file descriptors are needed in these situations to initially refer to files.
One problem with conventional implementations of open system calls is that in order for an operating system to identify an available file descriptor, an involved search of the available file descriptors must be made. In other words, the operating system supports a certain number of file descriptors that can be allocated to the files being opened. As a file is opened with an open system call and a file descriptor assigned, the file descriptor is thereafter unavailable until the open file is subsequently closed and the file descriptor released. It is understood that the smallest available file descriptor is the file descriptor that is normally to be assigned.
Conventionally, the file descriptors are maintained in a file descriptor table and, when an open system call is issued, a linear search of the file descriptor table would be performed to locate the smallest available entry in the file descriptor table. Unfortunately, the linear search of the file descriptor table is time consuming and not very efficient in locating the smallest available file descriptor. Typically, the file table would be searched in a linear manner starting from the beginning (i.e., file descriptor “0”) and continuing until an available file descriptor is found or the entire file descriptor table has been traversed without success.
As operating systems continue to become more complex, the number of file descriptor supported likewise continues to increase. Today, an operating system often supports millions of file descriptors. Hence, the linear search through the file descriptor table is becoming more inefficient as operating systems advance. More recently, it has been suggested that bitmaps can be used to speed up the linear search of the file descriptor table by a constant factor. See, G. Banga & J. Mogul, “Scalable kernel performance for Internet servers under realistic loads”, Western Research Laboratory, Digital Equipment Corporation, October 1998. While this bitmap technique is useful if the number of file descriptors is not too large, it is inadequate for large numbers of file descriptors. Hence, with modern operating systems supporting millions of file descriptors, the use of bitmaps to speed up the linear search provides only a minor improvement.
Thus, there is a need for improved approaches to allocate file descriptors.
SUMMARY OF THE INVENTION
Broadly speaking, the invention relates to improved techniques for allocation of file descriptors. According to one aspect of the invention, the file descriptors are stored in a tree-like data structure. The tree-like data structure is a data structure that includes a plurality of nodes arranged in the tree-like structure. The nodes have numeric values that are the file descriptors represented in a binary format. Each of the nodes also maintains an allocation count and an indication whether or not a particular node is available (i.e., unallocated). Preferably, the tree-like structure is an infix binary tree in which each node records the number of file descriptors within its right subtree (including itself) that are already allocated. Further, the tree-like data structure does not need to utilize customary left, right and parent pointers, but instead uses the features of the infix binary tree.
The invention can be implemented in numerous ways, including as a method, system, device or a computer readable medium. Several embodiments of the invention are discussed below.
As a method for allocating a file descriptor, one embodiment of the invention includes the acts of: providing a plurality of file descriptors in a tree-like data structure, searching the tree-like data structure to determine a smallest one of the file descriptors that is available, and allocating the one of the file descriptors that is determined to be the smallest.
As a data structure for use by a computer program in managing allocation of file descriptors, one embodiment of the invention includes at least a plurality of nodes, and an allocation count provided for each of the nodes. Each of the nodes represents a numeric value of one of the file descriptors, and the nodes are arranged in a tree like arrangement with subtrees. The allocation count for each node indicates the number of nodes allocated in the node and its associated subtree.
As an infix binary tree for use by a computer program in managing allocation of file descriptors, one embodiment of the invention includes at least: a plurality of nodes, each of the nodes representing a numeric value of one of the file descriptors; and an allocation count provided for each of the nodes.
As a computer readable medium including computer program code for allocating a file descriptor, one embodiment of the invention includes at least: computer program code for providing a plurality of file descriptors in a tree-like data structure; computer program code for searching the tree-like data structure to determine a smallest one of the file descriptors that is available; and computer program code for allocating the one of the file descriptors that is determined to be the smallest.
As a computer system, one embodiment of the invention includes at least a processor and an operating system executable on the processor. The operating system operates to allocate a file descriptor in response to a system call. The operating system includes at least: computer program code for providing a plurality of file descriptors in a tree-like data structure; computer program code for searching the tree-like data structure to determine a smallest one of the file descriptors that is available; and computer program code for allocating the one of the file descriptors that is determined to be the smallest.
The advantages of the invention are numerous. Different embodiments or implementations may yield one or more of the following advantages. One advantage of the invention is that appropriate file descriptors to be allocated can in general be located (i.e., via searching) much more efficiently than conventionally achieved. Another advantage of the invention is that the approach utilized is well suited for use with operating systems that support large number of file descriptors.
REFERENCES:
patent: 3916387 (1975-10-01), Woodrum
patent: 4833624 (1989-05-01), Kuwahara et al.
patent: 5077760 (1991-12-01), Lepage
patent: 5321837 (1994-06-01), Daniel et al.
patent: 5402369 (1995-03-01), Main
patent: 5544353 (1996-08-01), Forman et al.
patent: 5568487 (1996-10-01), Sitbon et al.
patent: 5600651 (1997-02-01), Molle
patent: 5717919 (1998-02-01), Kodavalla et al.
patent: 5809295 (1998-09-01), Straub et al.
patent: 5991771 (1999-11-01), F
Beyer Weaver & Thomas LLP.
Dodds, Jr. Harold E.
Robinson Greta
Sun Microsystems Inc.
LandOfFree
Method and system for allocation of file descriptors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for allocation of file descriptors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for allocation of file descriptors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3264455