USO054045l1A
`
`
`
`[11] Patent Number:
`
`
`
`[45] Date of Patent:
`
`
`
`
`5,404,511
`
`
`Apr. 4, 1995
`
`
`
`
`
`Guide to OS—9/68000”, Chapters 3 & 4, published by
`
`
`
`
`
`Microwave Systems Corporation,
`ISBN 0-9180-
`35-0105 1991.
`
`
`
`
`
`
`Primary Examiner—Thomas G. Black
`Assistant Examiner—--Jennifer M. Orzech
`
`
`
`Attorney, Agent, or Fz'rm—Anne E. Barschall
`
`
`
`
`
`
`[57]
`
`ABSTRACT
`
`
`
`
`
`
`
`
`
`An application module of a data processing apparatus
`
`
`
`
`
`
`
`
`requires various quantities of memory space for the
`
`
`
`
`
`
`buffering of data to be processed. In particular, image
`and audio files are to be read from a CD-ROM disc and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`decoded in real-time. The operating system provides a
`
`
`
`
`
`
`
`‘memory manager to allocate buffer space from the
`
`
`
`
`
`
`available memory. To alleviate the problem of fragmen-
`tation, a fragmented memory manager module secures
`
`
`
`
`
`
`at the outset an allocation of buffer space sufficient for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`all requirements of the application module, and parti-
`
`
`
`
`
`
`
`
`
`tions the allocation into small units of buffer space (frag-
`ments), which are linked into a list by respective list
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`pointers. Any subsequent requirement for buffer space
`
`
`
`
`
`
`is met by the fragmented memory manager, by un-link-
`
`
`
`
`
`
`
`
`
`ing the requisite number of fragments from the list of
`
`
`
`
`
`unallocated fragments. The application module is
`
`
`
`
`
`
`
`adapted to use fragmented buffer space where possible,
`
`
`
`
`
`
`
`while the allocation of buffer space in contiguous blocks
`is not excluded when necessary.
`
`
`
`
`
`
`3 Claims, 7 Drawing Sheets
`
`
`
`
`
`
`
`
`
`United States Patent [191
`
`
`Notarianni
`
`
`[75]
`
`
`
`
`
`
`[54] COMPACI‘ DISC PLAYER WITH
`FRAGMENT MEMORY MANAGEMENT
`
`
`
`
`
`
`
`Inventor: Benedetto A. Notarianni, Reigate,
`
`England
`
`
`
`
`
`
`[73] Assignee: U.S. Philips Corporation, New York,
`N.Y.
`
`
`
`
`[21] Appl. No.: 904,771
`[22] Filed:
`Jun. 26, 1992
`
`
`
`
`[51]
`Int. Cl.5 .............................................. G06F 15/20
`
`
`
`
`
`[52] U.S. Cl. .................................... .. 395/600; 369/32;
`
`
`
`369/47
`[58] Field of Search ............... 395/425, 600, 325, 164;
`
`
`
`
`
`
`
`369/32, 47, 33, 30, 25, 14
`
`
`
`
`
`
`
`
`
`
`
`[56]
`
`References Cited
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`4,912,629 3/1990 Shuler ................................. 395/600
`
`
`
`
`
`5,109,336 4/1992 Guenther ..
`395/425
`
`
`
`
`
`5,148,527 9/I992 Basso ................................... 395/425
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`Wilson, “Uniprocessor Garbage Collection Tech-
`
`
`
`
`
`niques”, Proceedings: Memory Management. Interna-
`
`
`
`
`
`
`
`tional Workshop IWMM 92, pp. 1-42 (Springer Verlag
`
`
`
`Sep. 23, 1992).
`
`
`
`
`
`Edited by Philips International & published by Kluwer
`Technical Books, ISBN 90 201-21103, entitled: “CD—I:
`
`
`
`
`
`
`
`
`
`
`
`A Designer’s Overview”, Chapter 7 1987.
`
`
`
`
`
`
`P. Dibble, “OS-9 Insights: An Advanced Programmers
`
`
`
`co ms
`
`
`
`
`
`
`
`
` APPLICATION
`
`
`
`
`
`
`
`MODULE
`
`
`
`
`
`
`FRAG LISTS
`
`
`
`
`
`
`
`
`
`
`
`
`210
`
`
`
`MEMORY
`MANAGER
`
`
`
`
`
`
`
`Page 1 of 14
`
`Samsung Exhibit 1031
`
`Page 1 of 14
`
`Samsung Exhibit 1031
`
`

`
`U.S. Patent
`
`
`
`
`Apr. 4, 1995
`
`
`
`
`Sheet 1 of 7
`
`
`5,404,511
`
`
`
`M n II V»
`
`_
`
`W - Ar
`— 200
`
`- —
`
`SB
`
`
`
`
`
`(PRIOR ART)
`FlG.1
`
`Page 2 of 14
`
`Page 2 of 14
`
`

`
`
`
`U.S. Patent
`
`
`Apr. 4, 1995
`
`
`
`
`Sheet 2 of 7
`
`5,404,511
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MANAGER
`
`
`
` MEMORY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`?.IlII'4IEF"/2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 3 of 14
`
`Page 3 of 14
`
`

`
`U.S. Patent
`
`
`
`
`Apr. 4, 1995
`
`
`
`Sheet 3 of 7
`
`
`5,404,511
`
`
`
`
`
`PEL+
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FRAG
`AC.
`
`
`
`
`
`
`300
`
`- ..
`BUFFER
`
`
`
`
`
`
`aurrm
`2321. was
`
`
`
`
`
`_
`
`
`/ /'
`/ ,
`
`
`
`/
`
`
`
`IIIIZ
`
`
`
`
`
`
`
`
`
`
`
`/'
`
`.
`
`/
`
`
`
`/
`
`
`
`
`
`
`
`%.
`
`
`
`
`
`
`
`
`
`Pu
`
`
`PE“
`
`
`
`
`
`
`
`
`
`
`
`Page 4 of 14
`
`
`
`
`
`FI 6.4
`
`
`
`
`FRAGM Z12
`
`
`
`
`
`
`
`
`
`
`%
`
`
`
`
`
`
`
`
`-
`
`
`
`
`
`
`
`E§'Afi§§AE§fgff:'lL-4LJ1:E-Egg-:E’fl-.:J]
`
`
`
`
`Page 4 of 14
`
`

`
`U.S. Patent
`
`
`
`
`Apr. 4, 1995
`
`
`
`Sheet 4 of 7
`
`
`5,404,511
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`"PLAY (FILE, PCB)
`
`
`
`I I
`
`712
`
`
`
`
`
`FRAG_FREE (IMZ)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FRAG _ SHUTDDWN
`
`
`5%
`
`RETURN
`
`714
`
`Page 5 of 14
`
`Page 5 of 14
`
`

`
`
`U.S. Patent
`
`
`
`
`
`Apr. 4, 1995
`
`Sheet 5 of 7
`
`
`5,404,511
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RETURN
`
` \
`
`
`
`
`FRAG.. [NIT
`
`800
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`846
`
`31.3
`
`850
`
`.
`
`
`
`R RELEASE
`
`
`
`951.
`
`Page 6 of 14
`
`
`
`
`
`
`
`ALLUC.
`
`I
`
`Page 6 of 14
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 6 of 7
`
`5,404,511
`
`E
`
`._.u..l|.|
`
`§_§_H-_§_§_E
`
`.I....ll: |l.a1'“.._nu.I|J_.....I»I'3°.
`_a_H_-_E_HE_l...u9III....
`
`Il ll
`_:_.Im-E.EH:5.9.5@
`
`Page 7 of 14
`
`Page 7 of 14
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 7 of 7
`
`5,404,511
`
`?E__m-§
`
`b.a.=_._-$E
`
`Page 8 of 14
`
`Page 8 of 14
`
`

`
`1
`
`
`
`
`5,404,5l 1
`
`COMPACI‘ DISC PLAYER VVITH FRAGMENT
`
`
`
`
`
`MEMORY MANAGEMENT
`
`
`
`
`
`5
`
`10
`
`15
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`taining by means of said list pointers a linked list of
`
`
`
`
`
`unallocated fragments (the “free list”);
`
`
`
`
`
`
`
`(b) in response to each subsequent request for alloca-
`
`
`
`
`
`
`
`
`tion of a quantity buffer space, un-linking from the free
`
`
`
`
`
`
`
`
`list a list (the “allocated list”) of fragments sufficient in
`
`
`
`
`
`
`
`number to contain the requested quantity of buffer
`space; and
`
`
`
`
`
`
`
`
`(c) in response to a subsequent request for release of
`
`
`
`
`
`
`
`
`the allocated list of fragments re-linking the allocated
`
`
`
`
`
`
`
`
`list of buffer fragments into the free list.
`By managing the memory from the outset as a set of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`many small fragments, any small fragment can be uti-
`
`
`
`
`
`
`
`
`
`lised to contribute to any allocation of buffer space,
`
`
`
`
`
`
`
`large or small (minimum size: one fragment). Of course
`
`
`
`
`
`
`
`
`the allocated buffer may be the sum of many fragments
`
`
`
`
`
`
`dispersed randomly throughout the physical memory
`
`
`
`
`
`
`space. This need not be a problem, however,,because
`
`
`
`
`
`
`
`
`the list pointers can be used by the apparatus in access-
`
`
`
`
`
`
`
`
`ing the allocated buffer space. It will be appreciated that
`fragmentation no longer prevents allocation of a re-
`
`
`
`
`
`
`
`
`
`
`quested quantity of buffer space.
`
`
`
`
`
`
`
`
`In the CD-I apparatus, the CDRTOS play control
`
`
`
`
`
`
`function is already capable of using fragmented memory
`as buffer space by means of its play control structure.
`
`
`
`
`
`
`
`The invention is particularly valuable in such a case.
`
`
`
`
`
`
`
`
`
`
`
`Accordingly, a particular embodiment of the inven-
`
`
`
`
`
`
`tion provides a real-time data processing apparatus
`
`comprising:
`a database access means (“reader”) for receiving from
`
`
`
`
`
`
`
`
`
`
`
`
`
`a database data for processing in real-time;
`
`
`
`
`
`
`
`real-time data processing means (“decoder”) for pro-
`
`
`
`
`
`
`
`cessing the data received from the database;
`
`
`
`
`
`
`
`
`memory means coupled between the reader and the
`
`
`
`
`
`
`
`
`decoder for providing buffer space for storing the
`
`
`
`
`
`
`received data prior to processing by the decoder;
`
`
`
`
`
`
`an application module for generating play commands
`to control the reader and decoder to process data in
`
`
`
`
`
`
`
`
`a desired sequence; and
`
`
`
`
`' a play control module for receiving said commands
`
`
`
`
`
`
`
`
`
`and for controlling the reader and decoder in real
`
`
`
`
`
`
`
`
`time so as to receive data from the database and
`
`
`
`
`
`
`
`
`cause processing of said data in a real-time se-
`
`
`
`
`
`
`
`quence defined by said commands,
`
`
`
`
`
`
`
`
`
`
`
`
`wherein each play command supplied to the play con-
`
`
`
`
`
`
`
`
`trol module includes (i) file information defining the
`location in the database of the data to be processed and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(ii) buffer information specifying the location in the
`memory of buffer space for storing said data, wherein
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the buffer information comprises at least one play con-
`
`
`
`
`
`
`
`
`trol item containing fields for indicating the location of
`a first quantity of buffer space and a list pointer to an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`optional further play control item, wherein the play
`control module is responsive to said play command to
`
`
`
`
`
`
`cause the data defined by the file information to be
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`received from the database and stored in said first quan-
`
`
`
`
`
`
`
`
`
`
`tity of buffer space and in the event that said first quan-
`
`
`
`
`
`
`
`
`
`tity of buffer space becomes full to use the list pointer in
`the at least one play control item to identify a further
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`play control item indicating a further quantity of buffer
`
`
`
`
`
`
`
`
`
`space for storage of the required data, and wherein the
`total of available buffer space in the memory is divided
`
`
`
`
`
`
`
`
`
`
`
`
`
`into a plurality of fragments, each fragment containing
`
`
`
`
`
`
`a relatively small predetermined quantity of available
`
`
`
`
`
`
`
`
`buffer space and having an associated play control item
`
`
`
`
`
`
`
`with a list pointer identifying a further fragment con-
`
`
`
`
`
`
`
`
`taining available buffer space, the apparatus yet further
`
`
`
`
`
`
`comprising a fragmented memory manager module for
`
`
`
`
`
`
`
`
`maintaining by means of the play control item list point-
`
`The invention relates to dynamic allocation of bufi'er
`
`
`
`
`
`
`
`
`
`
`
`
`space in the memory of a data processing apparatus.
`
`
`
`
`
`
`
`The invention has particular utility in so-called interac-
`tive systems, where audio, video and other data items
`
`
`
`
`
`
`
`
`
`are to be decoded and presented to a user in real-time.
`
`
`
`
`
`
`
`
`
`
`
`
`
`In many data processing apparatuses, data is read
`from a database stored in some form of mass memory
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(for example a magnetic disc or Compact Disc read-
`
`
`
`
`
`
`only memory (CD-ROM) and transferred to local mem-
`
`
`
`
`
`
`ory (RAM) for processing. Local memory is limited,
`
`
`
`
`
`
`however, and it is generally unpredictable what items of
`
`
`
`
`
`
`
`
`
`
`data need to-be loaded at any given time, and what is the
`
`
`
`
`
`
`
`size of each. Therefore it is necessary to provide some
`
`
`
`
`
`
`
`memory management function, which keeps track of
`the available memory and allocates buffer space in re-
`
`
`
`
`
`
`
`20
`
`
`
`
`
`sponse to requests from application processes.
`
`
`
`
`
`
`The Compact Disc-Interactive (CD-I) player, avail-
`
`
`
`
`
`
`
`able from Philips, is an example of a data processing
`apparatus in which memory management functions are
`
`
`
`
`
`
`
`
`
`
`
`provided by a real-time operating system CDRTOS.
`25
`
`
`
`
`
`
`CDRTOS is based on another real-time operating sys-
`
`
`
`
`
`
`
`
`tem OS-9/68000. The CD-I player operates under the
`
`
`
`
`
`
`control of an application program which is loaded from
`a CD-ROM. Through some play control functions of
`
`
`
`
`
`
`
`CDRTOS, the application program can control access
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to a large database of images, sounds and other informa-
`tion stored on the CD-ROM, under the interactive con-
`
`
`
`
`
`
`
`trol of the user.
`
`
`
`
`
`
`
`
`
`
`A description of the CD-I player is provided in
`
`
`
`
`
`“CD-I: A Designer’s Overview”, edited by Philips In-
`
`
`
`
`
`
`ternational and published by Kluwer Technical Books,
`
`
`
`
`
`
`ISBN 90-201-21103. This book is incorporated herein
`
`
`
`
`
`
`by reference. The problems of memory management in
`
`
`
`
`
`
`
`such systems are described for example in Chapter 3
`and 4 of the book “OS-9 INSIGHTS: An Advanced
`
`
`
`
`
`
`
`
`
`
`
`Programmers Guide to OS-9/68000” by Peter Dibble,
`
`
`
`
`
`published by Microware Systems Corporation, ISBN
`0-918035-0105.
`
`
`
`
`
`
`
`
`One particular problem highlighted in the Dibble
`book is that of memory fragmentation. This occurs
`
`
`
`
`
`
`
`45
`
`
`
`
`
`
`
`when, after a period of operation during which various
`parts of the memory have been allocated and de-
`
`
`
`
`
`
`
`
`
`allocated, the available (unallocated) memory at a given
`
`
`
`
`
`
`
`
`
`
`
`
`time is made up of small areas dispersed efiectively at
`
`
`
`
`
`
`
`random throughout the memory space. This fragmenta-
`
`
`
`
`
`
`
`
`
`tion might mean, for example, that a request for the
`
`
`
`
`
`
`
`
`allocation of 60 kilobytes of buffer space cannot be
`satisfied because there is no single unallocated block
`
`
`
`
`
`
`
`
`
`
`
`
`
`larger than 50 kilobytes. At the same time, adding up all
`the small fragments, there may in fact be hundreds of
`
`
`
`
`
`
`
`55
`
`
`
`kilobytes of unallocated memory.
`
`
`
`
`
`
`The invention addresses the problem of providing
`
`
`
`
`
`memory management in a data processing apparatus,
`
`
`
`
`
`
`for example to reduce the problem of fragmentation
`described above.
`
`
`
`
`
`
`
`The invention provides a method of dynamically
`
`
`
`
`
`
`
`allocating and releasing variable quantities of buffer
`space in a memory of a data processing apparatus hav-
`
`
`
`
`
`
`ing a finite total amount of buffer space, the method
`
`
`
`
`
`
`
`
`
`comprising:
`
`
`
`
`
`
`
`
`
`(a) in an initialization step (i) partitioning the total
`unallocated buffer space into a set of small buffer frag-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ments, maintaining for each unallocated fragment a
`
`
`
`
`
`
`
`
`respective list pointer; and (ii) constructing and main-
`
`
`
`
`
`
`
`30
`
`35
`
`
`
`
`
`50
`
`
`
`60
`
`
`
`65
`
`
`
`Page 9 of 14
`
`Page 9 of 14
`
`

`
`5,404,511
`
`l0
`
`15
`
`20
`
`
`
`.
`3
`
`
`
`
`
`
`
`
`
`
`
`ers a list of those of said fragments whose buffer space
`
`
`
`
`
`
`
`
`
`is not currently in use by the play control module (the
`
`
`
`
`
`
`
`
`
`“free list”) and for responding to each request for allo-
`
`
`
`
`
`
`
`
`cation of buffer space by un-linking from the free list a
`
`
`
`
`
`
`
`
`list of fragments (the “allocated list”) and supplying to 5
`the application module a pointer to the allocated list for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`use by the play control module in identifying buffer
`
`
`
`
`fragments for received data.
`
`
`
`
`
`
`
`
`In the case of CD-I, each fragment may conveniently
`contain enough buffer space for one sector of data from
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the CD-ROM, that is 2324 bytes. The memory con-
`
`
`
`
`
`
`
`sumed by storing so many list pointers will be only one
`percent or so of the total memory space, which is trivial
`
`
`
`
`
`
`
`compared to the amount of memory that can be wasted
`
`
`
`
`
`
`
`
`
`
`
`
`by fragmentation in a conventional memory manage-
`ment system.
`
`
`To illustrate the above and further features and ad-
`
`
`
`
`
`
`
`
`vantages of the invention, embodiments of the invention
`
`
`
`
`
`
`
`
`
`
`
`
`will now be described, by way of example, with refer-
`
`
`
`
`
`ence to the accompanying drawings, in which:
`FIG. 1 shows the hardware structure of the data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`processing apparatus suitable for implementing the in-
`
`
`
`
`
`
`vention, in the particular form of a CD-I player;
`
`
`
`
`
`
`
`FIG. 2 shows the logical structure of the apparatus of
`25
`
`
`
`
`
`
`FIG. 1, operating in accordance with the invention;
`
`
`
`
`
`
`FIG. 3 illustrates the problem of memory fragmenta-
`tion as it arises in the real-time control of the CD-I
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`player with conventional memory management;
`
`
`
`
`
`
`
`FIG. 4 illustrates the partitioning of the memory into
`
`
`
`
`
`
`
`small fragments in the apparatus of FIGS. 1 and 2, and 30
`
`
`
`
`
`
`shows the structure of one representative fragment;
`
`
`
`
`
`
`FIG. 5 shows the logical structure of a fragmented
`memory manager module in the apparatus;
`
`
`
`
`
`
`
`
`
`
`
`FIG. 6 is a flow chart representing the operation of
`35
`an application module of the apparatus;
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 7 comprises four flow charts representing the
`
`
`
`
`
`
`operation of elements of the fragmented memory man-
`ager of FIG. 6;
`
`
`
`
`
`
`
`
`FIG. 8 illustrates the allocation of memory fragments
`40
`at points (A), (B), (C) and (D) in the flow chart of FIG.
`
`
`
`
`
`
`
`
`
`
`
`7; and
`
`
`
`
`
`
`
`
`FIG. 9 illustrates the allocation of contiguous blocks
`
`
`
`
`
`
`
`
`of memory within the fragmented memory of the appa-
`ratus.
`
`
`
`
`
`
`
`FIG. 1 is a block schematic diagram of the Compact 45
`
`
`
`
`
`Disc-Interactive (CD-I) player. It comprises a compact
`
`
`
`
`
`
`
`disc player CDP to which is connected a compact disc
`
`
`
`
`
`
`digital audio controller decoder CDDA and a compact
`disc control unit CDCU. The CDDA is connected to an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`audio processing unit APU which feeds two loudspeak-
`ers LSL and LSR. The CD control unit CDCU is con-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`nected to a system bus SB along which various digital
`signals are passed. Also connected to the system bus SB
`
`
`
`
`
`
`
`
`are a microprocessor unit MPU, a DMA controller
`
`
`
`
`
`
`55
`DMA, a non—volatile random access memory NVRAM,
`
`
`
`
`
`
`a clock calendar unit C/C, a read-only memory contain-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`‘ing the real-time operating system CD RTOS, a key-
`board KB, a pointing device INP, and an access con-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`troller AC. The access controller controls the reading
`from and writing to a random access memory RAM
`
`
`
`
`
`
`
`which is split into two banks A and B. The access con-
`
`
`
`
`
`
`
`
`troller is also connected to a video decoder VD which
`
`
`
`
`
`
`
`
`
`
`
`
`
`in turn feeds a video generator VRGB, the output of
`
`
`
`
`
`
`
`which is connected to a video display unit VDU. Also
`
`
`
`
`
`
`
`
`connected to the system bus SB is an adaptive pulse 65
`code modulation decoder ADPCM which feeds the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`audio processing unit APU. A description of the CD-I
`base case decoder as shown in FIG. 1 is given in the
`
`
`
`
`
`
`
`
`50
`
`
`4
`
`
`
`
`
`
`book “Compact Disc-Interactive, A Designer’s Over-
`view” mentioned above.
`
`
`
`
`
`
`
`
`
`
`
`In the CD-I player, the operating system CDRTOS
`
`
`
`
`
`
`
`controls the operation of the various hardware elements
`in real-time, under the control of application programs
`
`
`
`
`
`
`
`loaded from the disc. The processing power of micro-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`processor MPU is thus shared by application software
`modules and modules of CDRTOS, but in an asynchro-
`
`
`
`
`
`nous manner such that each module can be regarded as
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`an independent functional module of the player.
`FIG. 2 illustrates the interaction of various modules
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in the CD-I player when implementing the present
`invention. Central to these functions is the memory
`
`
`
`
`
`
`
`
`
`
`
`
`200.
`This
`comprises
`one megabyte
`(RAM)
`(1024X1024X 8 bits) of read-write memory, divided
`
`
`
`
`
`
`
`
`
`
`
`
`
`into two planes A and B. A third plane FMV is shown
`
`
`
`
`
`
`
`
`dotted, which in future CD-I players will provide stor-
`age for full motion video data.
`
`
`
`
`
`
`
`
`
`
`
`
`
`An application module 202, defined by program data
`
`
`
`
`
`
`
`
`
`read from the disc player 204 (CDP), operates with
`assistance from CDRTOS to read audio, video and
`
`
`
`
`
`
`
`program data from the disc into memory, and to cause
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the decoders 206 to read this data for the generation of
`
`
`
`
`
`
`desired audio and video presentations. Specifically,
`video decoders VDA and VDB receive data from re-
`
`
`
`
`
`
`
`
`
`
`
`
`
`spective planes A and B of the memory, while the audio
`
`
`
`
`
`
`
`decoder ADPCM can receive data from either plane.
`A primary function of CDRTOS is the so-called
`
`
`
`
`
`
`
`playing of “real time fles”. Such files can contain audio
`
`
`
`
`
`
`
`
`
`data, video data or an interleaved mixture of the two, as
`
`
`
`
`
`
`
`
`
`
`
`described in the Philips/Kluwer textbook. A play con-
`trol module 208 of CDRTOS receives instructions in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the form of a file reference and play control information
`
`
`
`
`
`
`
`
`an proceeds to cause the reading, storing and decoding
`
`
`
`
`
`
`
`
`
`
`
`of the data without further effort on the part of the
`
`
`
`
`
`
`application module 202. A memory manager module
`210 of CDRTOS allows the application module 202 to
`
`
`
`
`
`
`
`reserve blocks of memory in a desired plane of the
`
`
`
`
`
`
`
`
`memory 200, which can be used as buffers storing the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`video/audio data for a given play operation.
`The elements of FIG. 2 as described so far are con-
`
`
`
`
`
`
`
`
`
`
`
`
`ventional. In a conventional arrangement, as the appli-
`
`
`
`
`
`
`cation module progresses in its operation, controlled by
`
`
`
`
`
`
`
`
`
`interaction with the user of the CD-I player, the prob-
`
`
`
`
`lem of “memory fragmentation” arises.
`
`
`
`
`
`
`FIG. 3 illustrates the problem of fragmentation in the
`
`
`
`
`
`
`playing of real-time files in a CD-I player, according to
`conventional practice. Sections of one plane of RAM
`
`
`
`
`
`
`are shown, with an arrow 300 indicating the direction of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`increasing memory address. Farts of the address space
`which are free (not allocated by CDRTOS memory
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`manager) are indicated by cross-hatching (302 etc.).
`
`
`
`
`
`
`
`Parts presently allocated for unspecified purposes are
`
`
`
`
`
`
`
`shown by simple hatching (304). Other blocks contain-
`ing bufier spaces IM.1, IM.2, IM.3, AUD.1 and AUD.2
`
`
`
`
`
`
`
`
`have been allocated as buffer areas for the purpose of
`
`
`
`
`
`
`
`
`storing video and audio data read from the disc.
`
`
`
`
`
`
`
`
`
`A play control structure is also constructed in mem-
`
`
`
`
`
`
`
`
`
`
`
`
`
`ory by the application module 202. This comprises a
`
`
`
`
`
`
`
`
`Play Control Block (PCB), a Channel Index List (CIL)
`for video, a CIL for audio and a set of Play Control List
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`items (PCLs). The application module 202 supplies the
`play control module 208 of CDRTOS with one or more
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`file references (pointers to data locations on the disc 24),
`and a pointer to the PCB. From then on the reading,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`storage and decoding of the files is automatic, barring
`
`
`
`
`intervention by the application module.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page10of14
`
`Page 10 of 14
`
`

`
`5,404,511
`
`5
`
`10
`
`
`
`15
`
`
`
`5
`
`The PCB area contains various control and status
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`fields, including channel identifiers and pointers to the
`
`
`
`
`
`
`
`
`two CILs. By changing the channel number, the partic-
`ular audio and/or video data read from the disc can be
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`selected to account for the language preference of the
`
`
`
`
`
`
`user, as described in the Philips/Kluwer textbook. For
`a given channel, each CIL has a pointer to a PCL item,
`
`
`
`
`
`
`
`
`as shown. The PCL structure in particular is relevant to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`an understanding of the present embodiment, and will
`now be described.
`
`
`Each PCL item points to an area of memory which is
`
`
`
`
`
`
`
`to be used as a buffer, and contains the following fields:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PCL_CTRL: This-field is initialized to zero by the
`
`
`
`
`
`
`
`application module before the play command is issued.
`
`
`
`
`
`
`
`
`It contains status flags for use by CDRTOS, in particu-
`lar to note when an error occurs in reading data into the
`
`
`
`
`
`
`
`
`
`corresponding buffer, or when the buffer is full.
`
`
`
`
`
`
`
`
`
`
`PCL_SMODE: This field is updated by CDRTOS
`
`
`
`
`
`
`
`
`with the value contained in the submode byte of the
`20
`subheader of the last sector read into this PCL.
`
`
`
`
`
`
`
`
`PCL__TYPE: This field is set by the CDRTOS and
`
`
`
`
`
`
`
`
`
`
`
`
`
`contains the coding information byte of the subheader
`of the last sector read into the buffer of this PCL. This
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`field can be used by the application module for refer-
`ence only.
`
`
`
`
`
`
`
`
`PCL_SIG: This field is initialised by the application
`module and contains a signal number to be returned to
`
`
`
`
`
`
`the application module when the buffer of the PCL is
`
`
`
`
`
`
`
`full or an error has been detected in the data transferred
`
`
`
`
`
`
`
`
`to the buffer.
`
`
`
`PCL__NXT: This is a pointer to a further PCL item.
`
`
`
`
`
`
`
`
`
`
`
`
`
`A linked list of PCLs can be built by the application, but
`
`
`
`
`
`
`
`
`need only contain one item. The list may be circular or
`
`
`
`
`
`
`
`may be terminated by the entry of a null pointer in this
`35
`
`
`
`
`
`
`
`
`
`field. The list of PCL’s may be manipulated by the
`application module at any time during the execution of
`
`
`
`
`
`
`
`
`
`the Play.
`
`
`
`
`
`
`PCL_BUF: This is a pointer to the buffer space in
`which the data from the disc is to be stored. It is the
`
`
`
`
`
`
`
`
`
`responsibility of the application module to make sure
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`that this points to an allocated data area large enough to
`
`
`
`
`
`
`
`
`
`hold all the data requested for this PCL. If this pointer
`is zero, the data is not transferred into memory and
`
`
`
`
`
`
`
`
`
`PCL._CNT (see below) is not incremented.
`
`
`
`
`PCL_BUFSZ: This field specifies the size, in sectors,
`
`
`
`
`
`
`
`of the buffer pointed to by PCL__BUF. This field is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`initialized by the application, and may be changedby
`the application at any time during the execution of the
`
`
`
`
`
`
`
`
`play command. A sector, as read from the disc, contains
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`up to 2324 bytes of data (CD-ROM Mode 2, Form 2).
`PCL_ERR: This field points to an error information
`
`
`
`
`
`
`structure. If this field contains a zero (No error informa-
`
`
`
`
`
`
`
`
`tion structure available) a “Data error” bit is set in
`
`
`
`
`
`
`
`
`PCL-CTRL, otherwise information about the data in
`
`
`
`
`
`
`error is also returned in the given buffers. These data
`
`
`
`
`
`
`
`
`can be used to conceal error in video sectors for in-
`
`
`
`
`
`
`
`stance.
`
`PCL_CNT: This field contains the ofiset in bytes
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`into the buffer of the next position to copy data. It
`
`
`
`
`
`
`
`should be initialized to zero by the application before
`
`
`
`
`
`
`
`the start of a play command. This field is updated by the
`
`
`
`
`
`
`system, but it may be changed by the application at any
`
`
`
`
`
`
`
`time during the execution of the play command.
`
`
`
`
`
`
`
`Returning to the example of FIG. 3, then, the CIL(V-
`IDEO) 306 points to a first PCL item 308 which in turn
`
`
`
`
`
`
`
`points to a bufferreserved for video data IM.l. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`buffer conventionally will contain enough space for
`serveral tens of disc sectors; enough for one complete
`
`
`
`
`
`
`
`
`
`40
`
`
`
`6
`
`
`
`
`
`
`
`
`
`
`image, for example. This first PCL item in turn points
`(by field PCL_NXT) to a second PCL item, which
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`describes the buffer area for data IM.2, perhaps a sec-
`ond image. The second PCL points to a third PCL
`
`
`
`
`
`
`
`
`
`describing the buffer for data IM.3. The third PCL
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`points back to the first PCL 308, thereby defining a
`
`
`
`
`
`continuously repeating series of three images.
`The CIL(AUDIO) 310 points to a list of two PCLs,
`
`
`
`
`
`
`
`describing the buffers for data AUD.1 an AUD.2 re-
`
`
`
`
`
`
`
`spectively. The second of these audio PCLs contains a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`null pointer ‘0’ in the field PCL_NXT, indicating no
`further sound data to be played. As mentioned above,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the application module can halt or modify the playback
`
`
`
`
`
`
`
`
`by altering various fields in the play control structure.
`
`
`
`
`
`
`
`Now, in the course of the interactive operation of the
`
`
`
`
`
`
`
`
`player under control of the application module and the
`user, buffers of different sizes are allocated and released
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`many times. This leads to the problem of memory frag-
`mentation which can be seen in the status of the mem-
`
`
`
`
`
`
`
`
`ory as illustrated in FIG. 3. The unallocated areas
`
`
`
`
`
`
`
`(cross-hatched) are small and scattered between the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`allocated blocks. This means that a request
`to the
`CDRTOS memory manager 200 for a new allocation of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a large buffer space cannot be satisfied, even though the
`total amount of unallocated memory may be sufficient.
`
`
`
`
`
`
`
`
`
`
`
`
`The memory fragmentation problem can now be
`
`
`
`
`
`addressed by operation of a Fragmented Memory Man-
`ager module 212 (FRAGM),
`shown in FIG. 2.
`
`
`
`
`
`
`
`
`
`
`
`
`
`FRAGM 212 actually partitions the memory into uni-
`
`
`
`
`
`
`
`form and small buffers (“fragments”) and maintains a
`
`
`
`
`
`linked listing of all unallocated fragments to allow dy-
`
`
`
`
`
`
`
`namic allocation of any total buffer size, regardless of
`
`
`
`
`
`
`
`the physical addresses of the individual fragments in the
`memory 200. By making the links via PCL-like struc-
`
`
`
`
`
`
`
`
`
`tures, in this CD-I embodiment, the fragmentation be-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`comes effectively transparent to the play control mod-
`ule 208 of CDRTOS.
`
`
`
`As shown in FIG. 4, a large area of memory is di-
`
`
`
`
`
`
`
`vided into data structures “FRAG”. Each FRAG com-
`
`
`
`
`
`
`
`prises a buffer large enough for one disc data sector
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(2324 bytes), followed by an augmented PCL structure
`(PCL+). The various fields of the PCL structure are
`
`
`
`
`
`
`
`
`provided, with the meanings as described above. This is
`
`
`
`
`
`
`
`
`
`
`
`
`
`augmented however by an additional pointer field
`FRAG_PREV.
`
`
`
`
`
`
`
`
`FIG. 5 shows the logical structure of the fragmented
`
`
`
`
`
`
`memory manager module 212 (FRAGM) which in-
`functions
`FRAG_INT,
`FRAG-GRAB,
`cludes
`
`
`
`
`FRAG_FREE and FRAG_SHUTDOWN. These are
`
`
`
`
`
`
`
`
`
`
`activated by the application module 202, for example by
`
`
`
`
`
`
`
`
`respective software function calls. For each plane of
`
`
`
`
`
`
`memory (A,B, FMV, etc) FRAGM maintains a pointer
`variable FREE-A, FREE-B, etc. For the purpose of
`
`
`
`
`
`
`
`
`
`
`
`
`
`simplicity, the following description makes no distinc-
`
`
`
`
`
`
`tion between planes, except as explicitly mentioned.
`The operation of the various modules 202-212 in
`
`
`
`
`
`
`
`accordance with the invention will now be described
`
`
`
`
`
`
`
`with reference to the flow charts of FIGS. 6 and 7. To
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`assist in an understanding of their operation, FIG. 8
`
`
`
`
`
`
`
`
`shows the status of memory allocation at four points
`(A),(B),(C) and (D) in the operation, as marked with
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`circled letters in FIG. 6. It should be appreciated that
`
`
`
`
`
`
`
`
`while there are only shown twelve memory fragments,
`in practice hundreds of fragments can be allocated in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the memory, each fragment giving 2324 bytes of buffer
`storage.
`
`
`
`
`
`
`
`
`In FIG‘. 6, the application module begins operation at
`700 when, for example, the user inserts a disc and a
`
`
`
`
`
`
`
`
`
`
`25
`
`
`
`30
`
`
`
`
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`65
`
`
`
`Page11of14
`
`Page 11 of 14
`
`

`
`
`
`
`
`7
`. CD-I application program is automatically read from
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the disc and executed. The application program resides
`in one or other of the planes of the memory 200, but the
`
`
`
`
`
`
`
`
`
`
`bulk of memory remains unallocated, to be used for
`
`
`
`
`
`
`
`
`
`‘
`video and audio data.
`
`
`
`
`
`
`
`
`
`
`
`
`Rather than request allocation of buffer memory
`from the CDRTIS memory manager 210 in the conven-
`
`
`
`
`
`
`
`
`tional manner, as and when buffers are required, the
`
`
`
`
`
`
`
`
`applicati