Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-09-17
2003-07-22
Shah, Sanjiv (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06598049
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data structure identifying method for use in an object-oriented operating system. The invention is also concerned with a recording medium in which a program implementing the above data structure identifying method is recorded. Details of certain features of the present invention are described in European Patent Application No. 0,753,811 A1 entitled in “Data processing method and device” and filed by the same assignee on Jul. 12, 1996 claiming a Convention Priority on JP 178625/95, filed Jul. 7, 1997, the complete disclosure of which is hereby incorporated herein by reference.
2. Description of the Related Art
For controlling various types of apparatuses and performing data communications between the apparatuses, software is becoming essential and the role of software is increasingly important. In all the software programs, and in particular, in most of the software programs to implement a complicated system, processing is simply described by handling a plurality of data items as a unit. Such a unit of data items is generally referred to as “an object” or “a data structure”.
In a software program, an object or a data structure is provided with a name and is identified by the name. In programming languages, such as C and C++, the name provided for an object or a data structure represents a function, a type, a class, or a variable.
However, the name defined by a programming language is used only in a region of the program text, which is referred to as “scope”, and is insufficient for representing an object or a data structure in a larger scale software program. Accordingly, most software programs cannot be implemented by a single program text and require a plurality of program texts.
There are increasingly a number of software programs which have been separately developed by a plurality of engineers and achieve a system by communicating and operating in cooperation with the programs.
Generally, a software module providing a certain service is referred to as “a server”, while a software module using the service is referred to as “a client”. In this case, the client can be considered as an identifier user, while the server can be regarded to include an identifier manager.
The definitions of the data structure and the data identifier are as follows.
The data structure specified in the following description cannot be directly accessed by the clients. In the relationship between an operating system (OS) and an application, for example, the data structure for which the OS manages calculation resources is not directly accessed by the application. This is because if the application is allowed to access the data structure within the OS, there is a possibility of destroying the OS.
Similarly, in regard to the application, in the relationship between the client and the server, the client is prohibited to directly access the data structure of the server, particularly when an object-oriented technique is applied to the application. The reason is as follows. According to the object-oriented technique, data managed by an object is accessed only by a method for processing the data or an application program interface (API), thereby offering advantages such as ease of programming and ensuring maintainability and safety.
Under the aforementioned condition, the basic functions, such as communications and cooperative operations between software programs, are supported by the OS. In an application program run on the OS, instead of using a name provided by a programming language, the use of an identifier (ID) is becoming popular for identifying an object or a data structure.
The identifier is generally treated in program as a value of an integer type or a value of specific type defined for an identifier. The value of the identifier is determined by the OS. The identifiers are required to distinguish between the objects or the data structures, and thus, each identifier has a unique value as viewed from the overall system. Accordingly, the number of bits and the content expressing the identifier, which are referred to as “a format”, determine the performance of the system or the required memory size.
FIG. 25A
illustrates an example of the format of an identifier that uses a memory address. For example, in a memory, such as a Transfer Look aside Buffer (TLB), for use in a microprocessor which is not provided with a memory management mechanism, all the possible address values within the system are unique. Accordingly, when a data structure is created, as shown in
FIG. 26A
, the memory address at which the data structure is arranged is used, as illustrated in
FIG. 26B
, as an identifier corresponding to the data structure.
The format of the above-mentioned identifier requires a sufficient number of bits needed for representing the address corresponding to the data structure. In this format, the address of the data structure can be readily recognized by the value of the identifier. This is very effective for a system which immediately needs to recognize the content of the data structure.
However, if there is a possibility of dynamically generating or erasing the data structure, the value of the identifier is likely to change and is not fixed over time. Accordingly, if it is possible that the data structure be dynamically created or destroyed while the system is operating and that the same address be reused, the address value cannot be used for the identifier.
Another example of the format of an identifier using a time stamp is shown in FIG.
25
B.
The number of bits required for this format is determined by the time needed for generating or erasing the data structure and the time during which the identifier is valid. For example, if it is assumed that the time needed for creating a certain structure is 10 microseconds and the system should continue to run for approximately 20 years, 46 bits are required. Namely, since 2
46
=7.04×10
13
, the system can be operated for 195,465.73 hours or 22.31 years.
According to the above type of format, the value of the identifier is unique on a time axis merely by issuing time stamps in sufficiently small units, thereby making it possible to distinguish between data structures by the identifier.
However, in order to check the data structure, the address value should be searched, which further requires additional processing, such as the use of a Hash table, thereby failing to exhibit the performance of this type of format. Additionally, if a sufficient number of bits are not used, a time stamp for the required number of years cannot be expressed.
As still another example of the format of an identifier which provides a unique value on a time axis, a counter may be used.
In this method, every time a data structure defined by an identifier is created or destroyed, the counter value may be incremented. In this method, as well as in the previous method, however, additional processing is required for searching the address value in order to check the data structure from the value of the identifier.
According to the above known formats of the identifier, i.e., the format in which an address value is combined with a time stamp or a counter, a great number of bits are required. In a 32-bit addressing processor, for example, which is currently used as a standard processor, 32 bits are required for an address value, and 32 bits (or 64 bits) are needed for a time stamp, thus resulting in a total of 64 bits (or 96 bits).
A sufficient memory area is not always ensured for software programs which are used by being integrated into various apparatuses. It is thus desirable that memory be used as little as possible by the above types of software programs, and the format of an identifier requiring a smaller number of bits is thus demanded. With a smaller number of bits, it is possible to decrease the cost required for performing comparison operations on identifiers or for copying the values of identifiers, thereby improving the performance of the entire system.
However, the perfo
Frommer William S.
Frommer & Lawrence & Haug LLP
Savit Glenn F.
Shah Sanjiv
Sony Corporation
LandOfFree
Data structure identifying method and recording medium does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data structure identifying method and recording medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure identifying method and recording medium will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3109389