Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2002-07-01
2004-11-02
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S134000
Reexamination Certificate
active
06813692
ABSTRACT:
The present invention relates to communications systems and, in particular, those employing multiplex signals comprising a periodically repeated plurality of modules.
Interactive digital television applications such as tele-banking, tele-shopping or electronic newspapers are typically broadcast in a carousel like fashion where the corresponding data sections are repeated periodically in the transport stream.
DSM-CC (Digital Storage Media-Command and Control) object carousels are such a type of broadcast file system used in interactive digital TV. These have been specified as the delivery system for content in several standards, including the UK Digital Terrestrial Group guidelines and the DVB Multimedia Home Platform (MHP). A DSM-CC object carousel consists of a number of ‘modules’, each of which contains part of a larger directory structure, either as several small files (in which case the maximum module size is 64 Kbytes) or a single large file (where the module can be any size). These modules are then broadcast with the digital TV signal, with some modules possibly being repeated to improve access times. Once all modules have been broadcast, the broadcaster returns to the beginning and starts broadcasting the modules again. This process bears a close resemblance to the way that teletext pages are broadcast, with DSM-CC modules replacing individual teletext pages as the basic unit.
Digital TV platforms that use DSM-CC typically cache at least some DSM-CC modules, to avoid the long delays in accessing modules encountered with systems like teletext which are caused by having to wait for the requested module's turn to be broadcast. This cache may be quite small and therefore effective management of the cache is important. On a DVB MHP platform, another level of complexity to the cache management is added since an application broadcast using DSM-CC can access the object carousel and load files from it.
The DSM-CC cache actually acts like a small part of memory, independent of all others. Objects are created in that memory (DSM-CC modules that have been loaded in this case) and must be freed at some later point when they are no longer needed. The platform must decide when a module can be freed to avoid long delays in re-loading a module if it is still being used.
Another perennial problem when managing memory is the problem of fragmentation. As objects get created and destroyed in a memory space, the available free space gets fragmented, with still-active pieces of memory existing between areas of free space. This can make it impossible to allocate large blocks of memory, and can be a significant problem given the potential size of DSM-CC modules.
The invention provides methods and apparatuses for management of DSM-CC and similar caches as defined in the appended claims to which reference should now be made and the disclosure of which is included herein by reference.
By thinking of the cache as a small, independent part of memory, it becomes possible to apply existing garbage collection algorithms to managing the cache and addressing the above problems. Garbage collection is a method for managing memory in some computer systems and programming languages (Java in particular) where the user does not have to explicitly free memory after use. Instead, the system will detect that the memory is not being used and automatically free it. There are a number of different methods of garbage collection, of which some are more applicable to certain machines and applications than others.
Due to the characteristics of the DSM-CC cache, in particular the fact that the only references to a module will be from outside the DSM-CC cache, a highly efficient reference count implementation of garbage collection can be used to manage the cache. This implementation involves keeping track of the number of references that exist to an object in the memory space that is handled by the garbage collector. The object can safely be reclaimed if the number of references is zero. Pure reference count algorithms cannot usually be used in garbage collection, because any data structure that refers to itself (either directly or indirectly) will always have a reference count of at least one, and will therefore never get reclaimed. This type of structure will never occur in a DSM-CC cache, however, since a module will never have a reference to another module and all references to a module will be from outside the cache.
Another type of garbage collector, which may use reference counting as one part of the algorithm, is a compacting garbage collector, where instead of a direct reference to an object in the cache, the application has a reference to a ‘handle’ that provides a level of indirection. This then allows the garbage collector to move the data in memory, in order to gather all the free space into one block, thus allowing more objects to be created than may otherwise be possible. This makes it particularly suitable for addressing the problem of fragmentation.
REFERENCES:
patent: 5043885 (1991-08-01), Robinson
patent: 5701432 (1997-12-01), Wong et al.
patent: 5764992 (1998-06-01), Kullick et al.
patent: 5920725 (1999-07-01), Ma et al.
patent: 6292194 (2001-09-01), Powell, III
patent: 2002/0107995 (2002-08-01), Skaringer et al.
patent: 2003/0002432 (2003-01-01), Morris et al.
patent: 0909091 (1999-04-01), None
Morris Octavius J.
Morris Steven
Koninklijke Philips Electronics , N.V.
Nguyen Hiep T.
LandOfFree
Receiver apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Receiver apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Receiver apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3319113