Mechanism for performing polling in a system

Details Mechanism for performing polling in a system Mechanism for performing polling in a system

2000-05-15

2003-06-10

Breene, John (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C710S018000, C709S224000

Reexamination Certificate

active

06578036

ABSTRACT:

BACKGROUND
This invention relates generally to computer systems, and more particularly to an improved mechanism for performing polling in a computer system.
Many operating systems (e.g. UNIX) use the notion of a “file” to access system resources. Used in this context, the term “file” refers broadly to anything that can be accessed via a path name, an IP address, or some other designator. Under this definition, a file may be, but is not limited to, a device (e.g. an I/O device), a collection of records, or a network node. To facilitate access to a file, the operating system generates a file descriptor (Fd) whenever a file is opened. This file descriptor is associated with the file, and is thereafter used as a handle to access the file. In some implementations, the file descriptor takes the form of an integer. This integer serves as an index into an entry of a file descriptor table. This entry contains a pointer to a structure within a group of one or more structures that contain pointers that eventually point to the file. By starting with the file descriptor and then following the various pointers, the file is eventually accessed.
A typical setup used to access files is shown in
FIG. 1
, wherein the setup comprises a file descriptor table
102
containing a plurality of entries
104
. Each entry
104
is referenced using an index, and each entry
104
contains a pointer to a structure within a group of one or more structures
106
. These structures
106
contain pointers that eventually point to the files
108
themselves. As noted above, the Fd is an integer, and it serves as an index into a particular entry of the file descriptor table
102
. If the value of the Fd is “0”, for example, then it references the first entry
104
(
0
) in the file descriptor table
102
. Likewise, if the value of the Fd is “1”, then it references the second entry
104
(
1
), and so on. Given that the Fd acts as an index into a particular entry
104
of the file descriptor table
102
, and that the particular entry
104
contains a pointer which eventually leads to a particular file
108
, it follows that the Fd acts as a handle to a particular file. In the example shown in
FIG. 1
, Fd “0” is the handle to file A
108
(
a
), Fd “1” is the handle to File B
108
(
b
), and Fd “2” is the handle to file C
108
(
c
).
During program execution, it is often necessary to poll various file descriptors to determine whether the files
108
associated with those file descriptors have any events that need to be serviced. This process of polling file descriptors is currently carried out by systematically polling each and every Fd for which polling is desired. More specifically, for each desired Fd, an associated entry
104
in the file descriptor table
102
is referenced. The pointer in the entry
104
is then followed to the structure(s)
106
, and the pointers in the structure(s)
106
are followed to the file
108
. Once the file
108
is accessed, it is polled for events. This process is repeated for each and every Fd for which polling is desired. At the end of the polling process, a list of Fd's and associated events is derived.
With relatively few Fd's in a system, this polling approach achieves satisfactory results. This is because the time required to poll a small number of file descriptors is fairly negligible. However, when the number of file descriptors becomes large, as is the case in complex computing systems, the polling of Fd's can require a significant amount of time and resources. In fact, if polling is performed on a repeated basis (as is the case in many programs), the polling operation alone can significantly degrade system performance. Because the current approach has a tendency to require a large number of Fd's to be indiscriminately polled whenever a polling operation is performed, it cannot be applied to large scale systems (i.e. it is not scalable). As a result, an improved mechanism is needed to perform polling in a large scale system.
SUMMARY OF THE INVENTION
In light of the shortcomings of the prior art, the present invention provides an improved mechanism for performing polling efficiently in a large scale computer system. The present invention is based, at least partially, upon the observation that when a polling operation is performed, it is not necessary to poll each and every Fd for which polling is desired. Rather, only those Fd's (referred to herein as eligible Fd's) that are associated with files for which there might be an event pending need to be polled. It has been found that the number of eligible Fd's in a system remains relatively small even when the total number of Fd's is quite large. Thus, by polling only eligible Fd's, the present invention keeps the overhead associated with a polling operation to a minimum. As a result, even in a large scale system with a large number of Fd's, polling can still be performed efficiently.
To enable only eligible Fd's to be polled, there is maintained a set of indication information. This indication information specifies for each Fd whether the file associated with that Fd might have an event pending. In one embodiment, the set of indication information takes the form of a bitmap. Each bit of the bitmap is associated with a particular Fd, and each bit indicates one of two possibilities: (1) that the file associated with the Fd has no event pending; or (2) that the file associated with the Fd might (but does not necessarily) have an event pending. Based upon the bitmap, it can be quickly and easily determined which Fd's do not need to be polled and which Fd's are eligible for polling, so that when it comes time to perform the polling operation, only the eligible Fd's are polled. This eliminates the unnecessary polling of many Fd's, which in turn significantly improves the overall efficiency of the polling process. Thus, the present invention makes it possible to efficiently implement polling even in a large scale system.


REFERENCES:
patent: 5490271 (1996-02-01), Elliott et al.
patent: 5937205 (1999-08-01), Mattson et al.
patent: 5978857 (1999-11-01), Graham
patent: 6047338 (2000-04-01), Grolemund
patent: 6088816 (2000-07-01), Nouri et al.
patent: 6115741 (2000-09-01), Domenikos et al.
patent: 6189109 (2001-02-01), Sheikh et al.
patent: 6243838 (2001-06-01), Liu et al.
patent: 6279046 (2001-08-01), Armstrong et al.
patent: 6341322 (2002-01-01), Liu et al.
patent: 6353869 (2002-03-01), Ofer et al.

Affiliated with

Also associated with

Rating

Mechanism for performing polling in a system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mechanism for performing polling in a system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for performing polling in a system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3160784