Method and system for allocation of file descriptors
AssigneeSun Microsystems, Inc.
InventorJeffrey S. Bonwick
Life of this patent
Estimating the term…
Abstract
Improved techniques for allocating file descriptors are disclosed. According to one aspect, 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. The improved techniques allow file descriptors to be allocated much more efficiently than conventionally achieved.
Claims22
A method for allocating a file descriptor for a computer system, comprising:
- (a) providing a plurality of file descriptors in a tree like data structure with subtrees, the tree like data structure having a plurality of nodes associated with the plurality of file descriptors representing files that are available to be allocated by the computer system, each of the nodes in the tree like data structure representing a numeric value of one of the file descriptors, wherein an allocation count for each node indicates the number of nodes allocated considering the node and those of said nodes in an associated subtree of said node;
- (b) searching the tree like data structure to determine a smallest one of the file descriptors that is available for allocation;
- wherein the searching is performed by ascending or descending the tree like data structure at least partially based on one or more of the allocation counts;
- and
- (c) allocating the one of the file descriptors in the tree like data structure that is determined to be the smallest.
A data structure for use by a computer program in managing allocation of file descriptors which represent files that are available for use by the computer program, said data structure comprising:
- a plurality of nodes, each of said nodes representing a numeric value of one of the file descriptors, the file descriptors representing files that are available for allocation by the computer program, said nodes being arranged in a tree like arrangement with subtrees;
- and
- an allocation count provided for each of said nodes, said allocation count for each node indicates the number of nodes allocated in said node and its associated subtree.
An infix binary tree for use by a computer program in managing allocation of file descriptors which represent files that are available on the computer system, said infix binary tree comprising:
- a plurality of nodes arranged in a tree like arrangement with subtrees, each of said nodes representing a numeric value of one of the file descriptors, the file descriptors representing files that are available for allocation on the computer system;
- and
- an allocation count provided for each of said nodes, wherein said allocation count for each node indicates the number of nodes allocated considering the node and those of said nodes in an associated subtree of said node.
A computer readable medium including computer program code for allocating a file descriptor representing a file that is available for allocation in a computer system, comprising:
- computer program code for providing a plurality of file descriptors in a tree like data structure with subtrees, the tree like data structure having a plurality of nodes associated with the plurality of file descriptors representing files that are available for allocation of the computer system, each of the nodes representing a numeric value of one of the file descriptors, wherein an allocation count for each node indicates the number of nodes allocated considering the node and those of said nodes in an associated subtree of said node;
- computer program code for searching the tree like data structure to determine a smallest one of the file descriptors that is available, wherein the searching is performed at least partially based on one or more of the allocation counts;
- and computer program code for allocating the one of the file descriptors represented in the tree like data structure that is determined to be the smallest.
A computer system, comprising:
- a processor;
- and an operating system executable on said processor, said operating system operating to allocate a file descriptor in response to a system call, said operating system including at least:
- computer program code for providing a plurality of file descriptors in a tree like data structure, the tree like data structure having a plurality of nodes associated with the plurality of file descriptors representing files that are available for allocation of the computer system;
- 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.
Dependencies are inferred from the claim text.