Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-04-07
2002-10-22
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S202000, C710S015000
Reexamination Certificate
active
06470398
ABSTRACT:
MICROFICHE APPENDIX AND COPYRIGHT NOTICE
This application is being filed with a microfiche appendix consisting of 111 frames on 2 sheets containing source code listings for software components related to the invention. Appendix sections are labeled A, B, D, and E.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The present invention is related to the field of digital circuits and to the field of instructions and program code for the operation thereof. More particularly, the present invention is related to data communication between digital circuits or between processes running on the same circuit. The invention is further related to fault-tolerant and scalable distributed processor and distributed memory digital processing systems.
This discussion of the present invention presupposes some familiarity with computer programming and software, particularly data input and output (I/O), network communications, and interprocess communications. The present invention also presupposes some familiarity with multiprocessor and nonshared memory computer systems, as discussed in co-assigned U.S. Pat. No. 4,228,496, which is incorporated herein by reference to the extent necessary to understand and enable the invention. This discussion of the present invention also presupposes some familiarity with the UNIX and related operating systems and with the well-known sockets protocol for enabling interprocess and network communication.
In all cases, the glossary and specific examples given herein are intended to be illustrative of the invention but not limiting. It will be apparent to anyone of skill in the art that the present invention may be implemented in an unlimited variety of operating system environments. Therefore, the invention should not be limited except as provided in the attached claims.
Background of Select( ) and Sockets( )
In UNIX and other operating systems (OS's), processes use a select( ) (or a similar) system call to inform the OS kernel that they are interested in a particular resource for interprocess communication. A simple example would be a process that needs to wait for a particular resource to have data to read or to be available for a write. Rather than the process using CPU time to repeatedly query the connection to determine if the connection is ready, the process may call select( ) and then become dormant if the connection is not immediately ready. The call to select( ) registers with the OS kernel that the calling process needs to be awakened when the interprocess communication resource becomes ready.
The select( ) OS call may be used by a process having open connections to one or more sockets. A socket is a resource for interprocess communication that is generally used between a user process and a special I/O process handling a network I/O protocol such as the common internet protocols TCP or IP. Sockets are generally implemented as a data structure within the OS memory space, and this memory space is accessible to the OS, the I/O process responsible for delivering data to the socket, and the user process that is communicating via the socket. A socket data structure has associated with it all state information necessary to handle the interprocess communication and generally includes a pointer to a memory location for temporarily storing the actual data packets flowing between the user process and the I/O connection.
Select( ) also may be used on other OS data structures used for interprocess communication such as pipes or FIFOs and for other opened I/O such as ttys, disk opens, and directory opens. While select( ) performs a similar function no matter what type of data structure it is called on, the details of the select( ) implementation for different data structures may vary in different operating systems as described more fully below.
A good description of the select( ) system call and sockets can be found in the reference book
UNIX Network Programming
, by Richard Stevens, (section 6.13), Prentice Hall, 1990.
Background of Distributed Memory Environments
In operating systems that have a single central processing unit (CPU) or multiple CPUs with shared memory, select( ) can be easily implemented because the data structures representing sockets, pipes, or FIFOs in the system are contained in a single memory space, as shown in
FIG. 1
, and therefore can be directly accessible to every process running in that memory space, including the OS.
However, in non-shared memory distributed systems, such as that discussed in U.S. Pat. No. 4,228,496, select( ) is more difficult to implement because the information regarding the occurrence of different events on different data structures may be contained in a memory different from that which holds the user process calling select and may not be directly accessible even to the OS local to the process that called select.
What is needed is a method for performing a select( ) function effectively in a distributed memory environment.
SUMMARY OF THE INVENTION
Glossary
The following terms are used in this application in accordance with the explanations below and also in accordance with their broad meanings as understood in the art.
Connection—a means for communicating data between processes or between a process and an I/O device, such as a socket, a RAM file, a disk file, a directory, a pipe, a FIFO, a TTY, etc.
Event—an occurrence on a connection, such as a ready-to-read, ready-to-write, or exceptional condition.
File descriptor (FD)—An identifier local to a user process and shared by only that process and related (child) processes for identifying a particular connection opened or created by that process.
I/O process—An input/output process for managing data input and output on some physical resources such as a network. Also called a server process.
Kernel—The executing operating system executable code that manages the activity of all other processes.
Message—In a distributed CPU environment, data communicated between two or more different CPUs or memory spaces over a communications channel.
Operating System (OS)—The kernel and other callable functions and resources available to processes.
Process—a collection (generally a sequence) of executable program code and associated state information that can independently execute and may at any given time be either executing or dormant.
Socket—A data construct residing in a memory that allows one process to communicate data with another process via a standard interface.
User process—A process created to perform a user function. Also called an application.
REFERENCES:
patent: 5142622 (1992-08-01), Owens
patent: 5524211 (1996-06-01), Woods et al.
patent: 5606705 (1997-02-01), Randall et al.
patent: 5706516 (1998-01-01), Chang et al.
patent: 5721825 (1998-02-01), Lawson et al.
patent: 5799156 (1998-08-01), Hogan et al.
patent: 5905890 (1999-05-01), Seamon et al.
patent: 6237035 (2001-05-01), Himmel et al.
patent: 0 360 768 (1990-03-01), None
patent: 0 509 946 (1992-10-01), None
patent: 0 723 236 (1996-07-01), None
Dannenberg, Roger B. “A Butler Process for Resource Sharing on Spice Machines”, Jul. 1985.*
Hall, Martin. “Windows Sockets”, Jan. 1993.*
Sidhu, Gursharan S. “Inside Applet Talk”, 1990.*
Kaashoek, M. F. “Group Communication in Amoeba and its Applications”, Jul. 1993.*
(Stevens). Stevens, Richard W. “UNIX Network Programming”, Jan. 1990.*
Handley, M. et al. “SIP: Session Initiation Protocol” Dec. 2, 1996.*
Nielsen, Kjell, et al.,Inter-processor Communication and Ada in Distributed Real-Time Systems, vol. 13, No. 8, Oct. 1, 1990, pp. 451-459.
Chan Sylvia
Gupta Minoo
Plum Lars
Shaw Robert
Uren Jim
Bullock, Jr. Lewis A.
Compaq Computer Corporation
Courtenay III St. John
Oppenheimer Wolff & Donnelly
Sherry Leah
LandOfFree
Method and apparatus for supporting a select () system call... 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 apparatus for supporting a select () system call..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for supporting a select () system call... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2963238