Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-07-01
2001-07-03
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06256645
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems and in particular, storage managers for controlling the assignment of storage locations to users in a situation where a common block of storage is to be shared by a plurality of users in an efficient manner.
BACKGROUND
In modern computer systems, many users often share a common block (i.e., section) of memory so that a highly efficient use of the memory is achieved. That is, oftentimes, users only need access to the memory for a short period of time, so it would be highly inefficient to totally dedicate portions of the memory block to particular users even during times when such users are not requesting access to the memory. Instead, when a user wishes to use a part of the memory block, the user makes a request to a storage manager which temporarily allocates a portion of the memory block to the requesting user. When the requesting user is finished with the allocated portion, the storage manager releases the allocated portion so that a future request (possibly from a different user) can now use this portion of the memory block.
An example of a conventional system will now be described with reference to
FIGS. 1
,
2
and
3
. In
FIG. 1
, a plurality of requesting applications (
11
a
,
11
b
,
11
c
), are simultaneously requesting access to a block of memory within memory
13
, which could be semiconductor memory, a hard disk, or any other type of memory. The requesting applications must first contact a storage manager
12
which performs the function of temporarily allocating portions of the memory block to each requesting application. For example, as shown in
FIG. 2
, the storage manager temporarily assigns area
21
of memory block
131
to requesting application
11
a
, area
22
to application
11
b
and area
23
to application
11
c
. If application
11
a
uses up its allocated area
21
and needs more space, the storage manager assigns a new area
31
(see
FIG. 3
) to application
11
a
. Similarly, if applications
11
b
and
11
c
request more space, areas
32
and
33
, respectively, are assigned thereto by the storage manager
12
.
As can be seen in
FIG. 3
, the memory block
131
soon becomes cluttered with assigned areas. As more and more areas become assigned to requesting applications, the memory is said to become “fragmented” since the available space has been split up so many times between the same few applications. A major problem with this system is that a new requesting application may not be able to have space allocated to it, since the previous applications have been allocated space that extends throughout the block
131
. Although there is space in between the allocated areas (e.g., between areas
31
and
32
) this space soon closes in as more areas are allocated and soon such spaces become very small. This inefficiency is known as external fragmentation.
One solution to this fragmentation problem is to provide an initial free area (
41
,
42
,
43
in
FIG. 4
) to each requesting application (
11
a
,
11
b
,
11
c
, respectively). When a requesting application makes a first request to the storage manager
12
for a memory area, the requesting application informs the storage manager of the amount of memory that it will require for the lifetime of the particular session in which the application needs the use of the memory. The storage manager then allocates an area of this size to the application. As the application makes requests for storage, all of the requests are satisfied from the initial free area assigned to that requesting application. This greatly reduces the fragmentation problem since all of an application's assigned memory areas are confined to the initial free area, thus preventing the storage manager from assigning a particular application memory areas interspersed throughout the block.
However, this technique is disadvantageous in that the requesting application must provide the storage manager with the amount of memory space that will be needed by that application, thus imposing a burden on the requesting application. For example, this may entail the requesting application keeping statistics from previous runs. This presents a drain on the requesting application's processing power, and the application is thus diverted from focusing on its core functions.
Further, if the requesting application requests too much space, then an inefficiency known as internal fragmentation results wherein allocated space in the initial free area goes unused by the requesting application and is thus also unusable by other applications. If the requesting application requests not enough space, the storage manager will begin to assign areas outside of the initial free area to the application, resulting in the external fragmentation described above.
SUMMARY OF THE INVENTION
According to one aspect, the present invention provides a storage manager apparatus located between a plurality of requesting applications and a memory shared between the applications, comprising: a means for receiving a present memory access request from a first of the plurality of requesting applications; a means for accessing statistical data, the data based on collected values of sizes of initial free areas from prior memory access requests from the first requesting application; and a means for setting a value of an initial free area for use by the present memory access request based on the accessed statistical data.
Preferably, the statistical data is a weighted average of sizes of initial free areas from prior memory access requests.
Further preferably, the apparatus further includes:a means for monitoring a total amount of memory used by the present memory access request until the initial free area is returned to the storage manager for assignment to another requesting application; and a means for re-calculating the statistical data for the first requesting application based on the monitored total amount.
According to a second aspect, the invention provides a method for carrying out the functional steps described above in conjunction with the first aspect of the invention.
According to a third aspect, the present invention provides a computer program product for, when run on a computer, carrying out the functional aspects described above in conjunction with the first aspect of the invention.
Thus, with the present invention, the requesting application is relieved from the task of determining the amount of memory it will need and providing this amount to the storage manager. Further, as the storage manager selects a size of the initial free area that is based on the prior history of use for this particular requesting application, there is a good chance that the size will be selected in such a way that it provides a satisfactory compromise between the problems associated with setting the size too big and those associated with setting the size too small.
REFERENCES:
patent: 5367637 (1994-11-01), Wei
patent: 5568635 (1996-10-01), Yamaguchi
patent: 5784699 (1998-07-01), McMahon et al.
patent: 5797689 (1998-08-01), Oyama et al.
patent: 1508731 (1978-04-01), None
IEEE Publication, “Improving File System Performance by Dynamically Restructuring Disk Space”, by Shane McDonald et al., Department of Computational Science, University of Saskatchewan, Canada, pp. 264-269, Jan. 1989.*
IEEE Publication, “A High Performance Memory Allocator for Object-Oriented Systems”, by J. Morris Chang et al., pp. 357-366, Jan. 1989.*
IBM Technical Disclosure Bulletin, “Method for Improved Allocation of Computer Disk File Space Based on File Size Distribution Experience” by Bryant et al., pp. 1-5, Mar. 1985.*
IBM Technical Disclosure Bulletin vol. 27 No. 10B, Mar. 1985, “Method for Controlling Fragmentation Loss of Computer Disk File Space”, by R M Bryant and P A Franaszek p. 6073-6074.
IBM Technical Disclosure Bulletin vol. 27 No. 10B, Mar. 1985, “Method for Improving Allocation of Computer Disk File Space Based on File Size Distribution Experience”, by R M Bryant and P A Franaszek p. 6075-6079.
IBM document No. ZW84-5434-00, F
Black Thomas
International Business Machines - Corporation
Johnson Prentiss W.
Mizrahi Diane D.
LandOfFree
Storage manager which sets the size of an initial-free area... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Storage manager which sets the size of an initial-free area..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Storage manager which sets the size of an initial-free area... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2448850