Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-05-09
2004-03-23
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06711595
ABSTRACT:
COPYRIGHT NOTICE
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. The copyright owner does not hereby waive any of its rights to have this patent document maintained in secrecy, including without limitation its rights pursuant to 37 C.F.R. §1.14.
TECHNICAL FIELD
This invention relates to memory management in a computer system, and more particularly to sharing of lookup data by loading lookup data into standard template library objects (STL objects) in a shared memory.
BACKGROUND
Modern data processing systems that support several processes simultaneously are defined as multiprocessing systems. More specifically, a process can be defined as an address space, a thread of control operating within that address space, and a set of required system resources for supporting the execution of a program. Before execution, the data needed for program execution and on which the program operates is loaded into the address space. In a multiprocessing system, several processes may execute and share data; some of the data used in different processes are the same for subsequent processes, and are termed “shared data.”
In multiprocessing systems, a plurality of processes may execute simultaneously for higher performance. The processes may be interconnected by a system bus through which they communicate among themselves and with commonly shared resources, such as input/output units and working memories. Shared memory is a reserved memory area to which all of the sharing processes have access; different access methods allow the processes to use the shared memory with different performance characteristics.
Sharing of data structures between processes, specially the sharing of Standard Template Library object (STL objects), has always been a desirable functionality. The Standard Template Library (STL) comprises a set of C++ generic data structures and algorithms, and the STL provides reusable, interchangeable components adaptable to many different uses in software development environment, some of which are described by G. Bowden Wise in
An Overview of the Standard Template Library
, available at www.cs.rpi.edu/~wiseb/xrds/ovp2-3b.html. This article is hereby incorporated by reference in its entirety.
Conventional operating systems such as Windows NT and other operating systems such as UNIX provide shared memory. NT provides shared memory in the form of memory-mapped files. However, the shared memory segment is not necessarily loaded in at the same address by default in different processes or in the same program. Specifically, the MapMemoryFileEx Application Program Interface (API) function is used to request NT to load the shared memory segment at a particular address. It is of very little relevance whether the memory segment is loaded in the same address for offset-based data structures like an array, because, even if the same data structure is loaded at different addresses in different processes, the computations are done based on the offsets. It is of great importance, however, whether the memory segment is loaded in the same address for pointer-based data structures, where an address in one process is not correlated to an address in another process.
SUMMARY
STL objects are pointer-based data structures. Addressing the deficiency in the traditional file-based approach, this invention provides a technique to load STL objects to allow sharing of the STL objects by a plurality of processes. In one embodiment, this invention implements sharing of any number of STL objects between processes and threads using New Technology's (NT's) Section Objects (or shared memory) and special STL allocator function. Data which are needed by more than one process are stored in user STL objects, and the user STL objects are placed in the same memory segment. By attaching the shared memory segment, multiple processes may have access to the stored data.
In one aspect, the invention features a computer-implemented method or an apparatus comprising a computer-readable medium having a plurality of sequences of instructions stored thereon for sharing data structures among processes by using a shared memory segment. The method includes creating the shared memory segment, anchoring a system STL (Standard Template Library) map in the shared memory segment, receiving a user STL object, obtaining an address for the user STL object, and inserting the user STL object into the system map.
In another aspect, the invention is directed to a method or an apparatus comprising a computer-readable medium having a plurality of sequences of instructions stored thereon for conducting garbage collection by an allocator, the allocator capable of allocating storage for a user STL object in a shared memory segment common to a plurality of processes. The method includes creating a first map containing a plurality of nodes representing a plurality of free blocks, each block represented in the first map by a node denoting a size and an address of the free block, responding to an allocation request, and responding to a deletion request by entering a size and an address of a deleted block into the first map.
In yet another aspect, the invention is directed to a computer system implementing a data-sharing scheme capable of supporting a shared memory segment common to a plurality of processes, the computer having a processor for executing instructions, a memory for storing instructions, the computer system. The computer system includes the shared memory segment, a system STL map anchored in the shared memory segment, and a plurality of user STL objects, wherein each object is named and is seated in the STL map by inserting a name and an address of the object into the system STL map.
Various implementations of the invention may include one or more of the following features. The user STL object may have a name. The shared memory segment may be named and may comprise approximately 10 MB of memory. The user STL object may comprise created or existing user STL object. The obtaining step may consist of returning the address of the user STL object if the name of the user STL object is in the system. STL map. The obtaining step may consist of returning a next allocation address from the shared memory segment if the name of the user STL object is not in the system STL map.
The method may consist of updating the next allocation address by increasing the next allocation address by an allocated size of the user STL object. The inserting step may consist of entering the name and the address of the user STL object into the system STL map.
Further the method may consist of requesting storage from an allocator, wherein the allocator allocates memory from the shared memory segment to store at least one node of the user STL object and data added to the user STL object. The data may comprise an entity capable of supporting a single writer and a plurality of readers. An access to the address of the next allocation may be synchronized. The allocator may performs garbage collection. The processes may be threaded.
Implementation of the invention may include one or more of the following features. The responding to an allocation request step may return an address of a free block in the plurality of free blocks if the allocation request is for a storage size equal to or smaller than the free block. The responding to an allocation request step may allocate memory from the shared memory segment. It may provide a snapshot of the shared memory segment. The snapshot may include a total size of the shared memory segment. The first map may be available to only one process of the plurality of processes and the one process may be a writer process. The shared memory segment may be named and may consist of about 10 MB of memory. Addresses of the plurality
Fish & Richardson P.C.
Openwave Systems Inc.
Rayyan Susan
Robinson Greta
LandOfFree
Method and apparatus for sharing standard template library... 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 sharing standard template library..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for sharing standard template library... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3242796