Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-07-02
2003-09-30
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S165000
Reexamination Certificate
active
06629221
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a buffer memory management system including a set of memory locations, each location temporarily storing a data block (BD) at a respective location address, said system avoiding rearrangement in the event of premature elimination of a data block stored in the memory. The problem of rearrangement following premature elimination of a data block relates to the consequences of that elimination, namely the need to modify the arrangement of the sequential relations between BDs in the management system. This problem is addressed in a previous patent application of the applicant, published under the number FR 2 752 632. The entirety of that application is considered to be incorporated into the present application by reference.
The present invention addresses more particularly the more specific problem of managing locations of a buffer memory when the stored data blocks are managed in accordance with n priority categories (where n is greater than 1), for example hierarchically in categories that reflect the respective priority levels of the various data blocks, and when a data block loss control discipline is used that implies an operation of writing a new data block into a location already occupied by another data block. If the memory is saturated, or filled to a level close to saturation (whether globally or for a given category), that operation typically consists of writing a new data block which has a high priority into a buffer memory location made available by eliminating from it the data block stored in that location, which is generally of lower priority.
This combined operation of eliminating a stored data block and simultaneously writing another data block in the same buffer memory location is referred to hereinafter as “substitution”; it is also known in the art as “push-out”. Data blocks that can be eliminated are referred to hereinafter as “data blocks cleared for elimination” (BDCE). They are typically data blocks of n−1 lower priority categories (data blocks of the highest category cannot be eliminated).
Apart from the situation of eliminating a data block during a substitution operation, the invention also encompasses two other possible situations of premature elimination (without substitution) of a data block (referred to hereinafter as “BD”):
1.) eliminating a cleared for elimination BD in a given category i, typically the BD that is the first in a list used to manage the subset of BDs cleared for elimination (BDCE) of that category i; and
2.) eliminating a particular BD stored in a buffer memory location.
According to the solution proposed in the aforementioned patent application, each BD stored in the buffer memory is associated with a BD identifier (IBD), which can be different from the address (EMT) of its location in the buffer memory, and a BD is eliminated from a location of the buffer memory (EMT) without it being necessary to rearrange the sequential relations between BDs, which are managed by means of their respective BD identifiers (IBD). This is because eliminating a BD immediately frees the buffer memory location (EMT) that it was previously occupying but retains its original data block identifier (IBD). A BD that has been eliminated therefore continues to exist in the management system through its identifier IBD, for example in a chained list, but that identifier IBD is associated with an eliminated BD flag that is detected subsequently when the BD is serviced.
Accordingly, the situation envisaged in the aforementioned patent application is that of premature elimination of a given BD stored in a buffer memory effected as an isolated operation. There may be various causes for isolated elimination of a BD: creation ahead of time of new free locations for possible high-priority BD (typically in the event of imminent saturation of the buffer memory), elimination of an incorrect BD, etc.
Generally speaking, in the buffer memory management system described in the aforementioned patent application, when a BD is eliminated, the memory location (EMT) that it occupies is immediately released so that it become available, but the identifier IBD associated with the BD eliminated in this way is retained, so that the arrangement of the sequential relations between BDs (referenced by their identifier IBD) is not prematurely modified in the management system.
To achieve this technical effect, the management system according to the patent application previously cited includes:
a) free buffer memory location address management means for finding a free location on receiving a new data block to be stored in the buffer memory and for freeing the address of a location when it is no longer occupied by a data block;
b.) write control means for writing a new data block into a location of the buffer memory;
c.) free block identifier management means for assigning a free block identifier to each new data block stored in the buffer memory;
d.) location/block identifier association management means for storing, for each identifier associated with a data block, the address of the location that it occupies in the buffer memory; and
e.) time management means in respect of data blocks stored in the buffer memory, for:
commanding the reception of a new data block to be stored in the buffer memory;
using a given service discipline, arranging the identifiers of the data blocks stored in the buffer memory by managing, as a function of time parameters associated with the identifiers of the blocks, their respective waiting times in the buffer memory and thereby determining respective read times for their service, each data block having normally to be read a predetermined number of times before freeing its location in the buffer memory and its associated block identifier;
commanding service of a data block to be read in the buffer memory; and
possibly commanding premature elimination of a predetermined stored data block, freeing of its location in the buffer memory and temporary preservation of its associated block identifier to prevent rearrangement of time relations between blocks.
To enable premature elimination of a data block stored in a buffer memory location and the immediate release of that location without having to rearrange the block identifiers managed by the time management means, the management system further includes:
a.) elimination flag management means for storing, for each data block identifier, an elimination flag indicating whether the corresponding block has been prematurely eliminated or not;
b.) means for commanding the free location address management means to free the address of the location storing a block to be eliminated;
c.) means for writing into the elimination flag management memory, each time that a block has been eliminated, a flag value storing the elimination of the block;
d.) means for reading the elimination flag management memory in the event of each selection of a block identifier, in order to read that block in the buffer memory, and for authorizing reading the buffer memory location corresponding to the selected block identifier only if the elimination flag that has been read indicates that the block having that block identifier has not already been eliminated; and
e.) means for authorizing the free location address management means to free the address of the location corresponding to a block that has been read after that block has been read a predetermined number of times and for as long as reading is authorized, if that block has not already been eliminated.
With the above management system, it is possible to release a buffer memory location at the earliest possible time because the time management means include means for commanding the free location address management means to free prematurely the address of the location storing the block to be eliminated, as soon as the decision is taken to eliminate that block. The time management means do not rearrange the time parameters when a data block is eliminated, however. They therefore normally select the identifiers of the blocks elimina
Alcatel
Elmore Reba I.
Sughrue & Mion, PLLC
LandOfFree
Memory management system for enabling writing of data blocks... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory management system for enabling writing of data blocks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management system for enabling writing of data blocks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3009561