Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-10-08
2004-05-18
Follansbee, John (Department: 2126)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C711S100000
Reexamination Certificate
active
06738796
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to computer architecture, and more specifically, to optimizing memory requirements for multi-threaded operating systems.
2. Description of the Background Art
Multi-threaded operating systems optimize processing time by allowing parallel operations to be executed by different threads. For example, in operations with storage media, read and write threads are used to provide simultaneous access to the storage media for both the read and write operations. However, to ensure accurate presentation of the data in the correct order, and to ensure that conflicts do not arise between the threads in attempting to access of the storage media, memory management mechanisms must be implemented to synchronize the access of the storage media and to provide identification information for the data stored in the storage media. In conventional systems, the memory management mechanisms require significant amounts of memory to maintain, for example, in systems that use synchronization objects to synchronize access to a data segment of the storage media, a synchronization object must be maintained for each data segment of the storage media. To ensure that the data segments are read in the proper order, a link list of synchronization nodes or other tracking structure is used to guide the read thread to the next data segment to be read. Thus, a read thread in operation examines the link list to determine a next synchronization node to read, and then examines the indicated synchronization object to determine whether the segment is currently being accessed by the write thread. If the synchronization object indicates the write thread is accessing the segment, the read thread is placed into a low-CPU intensive state until the segment becomes available. These structures serve a critical function in memory management, but they require a large amount of memory to maintain. Therefore, in many systems, as high-speed, processor-mapped memory is limited in size, memory quickly runs out and the systems are forced to store the memory management mechanisms in slow virtual memory. However, slow virtual memory is ineffective in systems having high data rates, for example over 10 megabits per second. Therefore, a system, method, and apparatus are needed that provides for simultaneous read and write access of memory, provides a memory management structure that identifies the location of data stored in storage media and synchronizes the accesses of the read and write threads, still provides a low-CPU usage state when conflicts arise, but does not require large amounts of memory to maintain.
SUMMARY OF THE INVENTION
In accordance with the present invention, a system, method, and apparatus are disclosed for minimizing the memory required by memory management structures in a multi-threaded operating environment. More specifically, the present invention dynamically determines the shortest necessary lifetime of a memory management structure to allow the memory required to maintain the memory management structure to be reallocated for other uses when the memory management structure is no longer required. Additionally, the present invention provides for a structure that shortens the necessary lifetime of a memory management structure.
In one embodiment, a memory management structure comprises a conventional synchronization object for each data segment. The synchronization object synchronizes the access to a data segment between write and read threads and provides a low-processor intensive state for a read thread if the read thread attempts to access a data segment to which the write thread already has access. A link list of synchronization nodes is also maintained to identify to the read thread a next data segment to be read. However, in accordance with the present invention, the synchronization node comprises a segment ready indicator that also indicates whether a data segment is available for access. If the segment ready indicator indicates to the read thread that the data segment is available for access, the read thread proceeds directly to reading the data segment without accessing the synchronization object. Accordingly, when the write thread has completed writing to a data segment, it can set the segment ready indicator of the synchronization node to indicate the data segment is available for the read thread and then destroy the synchronization object, freeing its memory for other uses. The segment ready indicator is a simple data structure that requires much less memory to maintain than the synchronization object because it is not required to provide, among other functions, a low CPU-intensive state. After reading the data segment, the read thread can then destroy the synchronization node, thus freeing the memory required to maintain this structure as well. Thus, in accordance with the present invention, a system, method, and apparatus are disclosed that minimize the memory requirements of memory management structures of a multi-threaded operating systems.
REFERENCES:
patent: 5263161 (1993-11-01), Barth et al.
patent: 6108754 (2000-08-01), Lindholm
patent: 6237043 (2001-05-01), Brown et al.
patent: 6247025 (2001-06-01), Bacon
patent: 6438586 (2002-08-01), Hass et al.
Follansbee John
Globespanvirata, Inc.
Opie G. L.
Thomas Kayden Horstemeyer & Risley
LandOfFree
Optimization of memory requirements for multi-threaded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization of memory requirements for multi-threaded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of memory requirements for multi-threaded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3249332