Abstract:
A method for compaction of objects within a computer memory, the method including dividing a memory space into a plurality of non-overlapping sections, selecting a plurality of source sections from among the sections, each containing at least one object, selecting a plurality of target sections from among the sections, and moving any of the objects from the source section to the target section, where each of a plurality of pairs of the source and target sections is exclusively available to a different process from among a plurality of processes operative to perform any of the steps with a predefined degree of concurrency.

Description:
FIELD OF THE INVENTION 
   The present invention relates to computer memory management in general, and more particularly to a compaction of memory objects. 
   BACKGROUND OF THE INVENTION 
   Computer operating systems (OS) typically provide a mechanism for storing “objects” of data. Often, the OS dynamically allocates a sub-section of memory for utilization by an application into which the application places its objects. When the application finishes its utilization of a sub-section of memory, the OS may reclaim the memory. This process of reclamation is popularly known as garbage collection (GC). 
   Garbage collectors from the mark-sweep family suffer from memory fragmentation, which is the creation of holes of unused space between objects, the space being previously populated by objects that are no longer required by an application. To reduce fragmentation, a garbage collector may compact memory by moving utilized objects to reduce the unutilized space between them. This has the effect of combining small areas of unutilized memory into larger chunks of free space, making memory allocation more efficient, and reducing the memory footprint of the application. A goal of compaction algorithms is to create the largest chunks of free space possible within memory, thus enabling easy re-allocation by the OS. 
   Typically, a compaction algorithm run as part of a single process will aggregate objects to one “side” of the memory space, thus freeing up the rest of the memory space. While multi-process compaction algorithms take advantage of multiple processors and/or multiple threads to speed up memory compaction, each process typically works independently. These multiple, independent compactions typically create a number of sub-sections within the memory where the allocated objects are relocated to one side of each sub-section. This leaves memory organized locally into relatively large chunks, while still leaving memory relatively fragmented at the global level. 
   SUMMARY OF THE INVENTION 
   The present invention discloses an improved system and method for global compaction of memory by multiple processes working in a local fashion. 
   In one aspect of the invention a method is provided for compaction of objects within a computer memory, the method including dividing a memory space into a plurality of non-overlapping sections, selecting a plurality of source sections from among the sections, each containing at least one object, selecting a plurality of target sections from among the sections, and moving any of the objects from the source section to the target section, where each of a plurality of pairs of the source and target sections is exclusively available to a different process from among a plurality of processes operative to perform any of the steps with a predefined degree of concurrency. 
   In another aspect of the present invention where the dividing step includes dividing into a number of sections that is a multiple of the number of the processes. 
   In another aspect of the present invention the dividing step includes dividing such that each of the sections m approximately equal in size. 
   In another aspect of the present invention the dividing step includes dividing such that boundaries of any of the sections fall within an empty region of the memory. 
   In another aspect of the present invention the dividing step includes dividing such that boundaries of any of the sections fall at the start or end of an object. 
   In another aspect of the present invention the moving step includes moving the objects from the source section to the target section such that the moved objects appear in the target section in the same order in which they appeared in the source section. 
   In another aspect of the present invention the moving step includes moving the objects from the source section to the target section such that the moved objects appear with less space between them in the target section as compared with the source section. 
   In another aspect of the present invention any of the steps are performed concurrently by each of the processes. 
   In another aspect of the present invention the target section selection step includes selecting any of the source sections as any of the target sections subsequent to any of the objects having been moved within or out of the source section. 
   In another aspect of the present invention the moving step includes moving at least one of the objects out of the source section and at least one of the objects within the source section. 
   In another aspect of the present invention the moving step includes moving any of the objects from the source section to a second one of the target sections subsequent to moving any of the objects from the source section to a second one of the target sections. 
   In another aspect of the present invention a system is provided for compaction of objects within a computer memory, the system including means for dividing a memory space into a plurality of non-overlapping sections, means for selecting a plurality of source sections from among the sections, each containing at least one object, means for selecting a plurality of target sections from among the sections, and means for moving any of the objects from the source section to the target section, where each of a plurality of pairs of the source and target sections is exclusively available to a different process from among a plurality of processes operative to control any of the means with a predefined degree of concurrency. 
   In another aspect of the present invention the means for dividing is operative to divide into a number of sections that is a multiple of the number of the processes. 
   In another aspect of the present invention the means for dividing is operative to divide such that each of the sections m approximately equal in size. 
   In another aspect of the present invention the means for dividing is operative to divide such that boundaries of any of the sections fall within an empty region of the memory. 
   In another aspect of the present invention the means for dividing is operative to divide such that boundaries of any of the sections fall at the start or end of an object. 
   In another aspect of the present invention the means for moving is operative to move the objects from the source section to the target section such that the moved objects appear in the target section in the same order in which they appeared in the source section. 
   In another aspect of the present invention the means for moving is operative to move the objects from the source section to the target section such that the moved objects appear with less space between them in the target section as compared with the source section. 
   In another aspect of the present invention any of the processes are concurrently operational. 
   In another aspect of the present invention the target section selection means is operative to select any of the source sections as any of the target sections subsequent to any of the objects having been moved within or out of the source section. 
   In another aspect of the present invention the means for moving is operative to move at least one of the objects out of the source section and at least one of the objects within the source section. 
   In another aspect of the present invention the means for moving is operative to move any of the objects from the source section to a second one of the target sections subsequent to moving any of the objects from the source section to a second one of the target sections. 
   In another aspect of the present invention a computer program is provided embodied on a computer-readable medium, the computer program including a first code segment operative to divide a memory space into a plurality of non-overlapping sections, a second code segment operative to select a plurality of source sections from among the sections, each containing at least one object, a third code segment operative to select a plurality of target sections from among the sections, and a fourth code segment operative to move any of the objects from the source section to the target section, where each of a plurality of pairs of the source and target sections is exclusively available to a different process from among a plurality of processes operative to perform any of the code segments with a predefined degree of concurrency. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention will be understood and appreciated more fully from the following detailed description taken in conjunction with the appended drawings in which: 
       FIG. 1A  is a simplified block diagram of a computer system, useful in understanding the present invention; 
       FIG. 1B  is a pictorial representation of memory storage, useful in understanding the present invention; 
       FIG. 2  is a simplified flowchart illustration of a method for global compaction of memory, operative in accordance with a preferred embodiment of the present invention; and 
       FIGS. 3A–3E , are simplified, time-sequential pictorial illustrations of an exemplary implementation of the method of  FIG. 2 . 
   

   DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
   Reference is now made to  FIG. 1A , which is a simplified block diagram of a computer system, and additionally to  FIG. 1B , which is a simplified pictorial representation of memory storage, both useful in understanding the present invention. A typical Computer System  100  employs an operating system, and may also provide an execution environment that mediates between an Application  110  and the operating system, such as a Java Virtual Machine (JVM). The execution environment also typically provides a Garbage Collector  130  to compact a Memory  140 . Garbage Collector  130  preferably includes one or more Processes  150 , where each Process  150  is capable of compacting some or all of a Memory  140  independently. During the course of execution, Application  110  may store one or more Objects  160  in Memory  140 . For example,  FIG. 1B  depicts a series of Objects  160 , labeled Object 1  through Object 5 , stored in Memory  140 . Empty spaces, particularly those that are too small to be utilized for storing new objects, may accumulate within Memory  140  in areas not allocated to stored Objects  160 , such as the space denoted Empty and the spaces between Object 1  and Object 2 , Object 3  and Object 4 , and Object 4  and Object 5 . Garbage Collector  130  may then compact Memory  140 , aggregating Objects  160  to one side of the memory space. For example, Object 1  through Object 5  may move to the far right side of Memory  140 , increasing the largest contiguous Empty block of memory. During the compaction of Memory  140 , Garbage Collector  130  preferably preserves the locality of reference, i.e. the local composition of the Memory  140 . Objects  160  that were near in memory to each other remain so after Garbage Collector  130  compacts Memory  140 . 
   Reference is now additionally made to  FIG. 2 , which is a simplified flowchart illustration of a method for global compaction of memory, operative in accordance with a preferred embodiment of the present invention. In the method of  FIG. 2 , Memory  140  is divided into a series of m non-overlapping Sections  200 , where m is typically chosen to be a multiple K of the number of independent processes P that will be used to compact Memory  140 . Processes P may be implemented within the context of one or more processors and/or one or more threads, and may be implemented using any predefined degree of concurrency. For example, if the garbage collector uses 2 processes, and if K is equal to 4, Memory  140  may be divided into 8 Sections  200 . K is preferably chosen such that each Section  200  is larger than a predefined minimum size to ensure that locality of reference is preserved in relatively large groups of Objects  160 , where most of the objects of the section are copied together. Given a predefined time limit for processing a section as described hereinbelow and an estimated speed at which a section is processed, a maximum section size may be predefined, where the sections are preferably set to be smaller than the predefined maximum size to insure good load balancing between the different processes. Each section m is preferably approximately equal in size, while allowing for section boundaries to be set to either fall within an empty region of memory or at the start or end of an object. 
   An array of pointers, denoted pToFreeSpace, is preferably allocated and initially set to NULL. Each pointer, denoted pToFreeSpace[i], preferably points to a free space in a particular Section  200   i  of Memory  140 . Furthermore, a global variable numOfSectionsTaken is also preferably allocated and initialized to zero. Each Process  150  may access these global variables and may employ any known thread-protection methodology. 
   An iterative process commences where Sections  200  of Memory  140  are reorganized by multiple Garbage Collector processes, where each Garbage Collector process typically has exclusive access to a unique Section  200 . Each Garbage Collector processes is also preferably capable of performing an atomic operation (i.e., uninterrupted by other processes) of checking a predicate and setting a value using conventional parallel programming techniques such as test-and-set or compare-and-swap. This operation may be denoted as: start-atomic-block, if (predicate) then operation, end-atomic-block. During the iterative process, each of the P Processes  150  preferably performs the following using any predefined degree of concurrency, and preferably fully concurrently:
         1. Find a source Section  200 , denoted S
           a. Set S to numOfSectionsTaken and increment numOfSectionsTaken.   b. If S&gt;m exit.   c. Set a local variable pFirstToMove to point to the first object in S.   
           2. Find a target Section  200 , denoted T, as follows:
           Set T=0, and iterate as described hereinbelow:
               a. If pToFreeSpace[T]=NULL;
                   i. T++;   ii. If T&gt;=numOfSectionsTaken, goto step 4   
                   b. Else
                   i. Start-atomic-block   ii. If pToFreeSpace[T]!=NULL Set pToFreeSpace[T]=NULL   iii. End-atomic-block   iv. Break, i.e. stop iterations. (goto step 3)   
                   
               
           3. Move Objects  160  from Section S starting at pFirstToMove to the free space in Section T pointed to by pToFreeSpace[T] as long as there is still free spaces in Section T and S is not emptied. During the move, advance pFirstToMove to point to the next object to be moved.
           a. If the portion of Memory  140  pointed to by pToFreeSpace[T] in Section T is not large enough to contain all the Objects  160  in Section  200  S, leave pToFreeSpace[T] as NULL   b. If free space remains in the target Section  200  T, set pToFreeSpace[T]=[start of free space in T].   c. If there are still objects  160  left in Section S (pFirstToMove still points to an object) Goto step 2.   d. Set pToFreeSpace[S] to point to the start of the free space in the source Section  160  S (which in this case is the start of the section).   e. Goto step 1   
           4. If a target Section  200  T was previously not found:
           a. Compact the Objects  160  within Section S.   b. Set pToFreeSpace[S] to point to the start of the newly created free space in the source Section  160  S.   c. Goto step 1.   
               

   Thus, objects are preferably moved from Section S to Section T such that the moved objects appear in Section T in the same order in which they appeared in Section S, but with less space between the objects in Section T as compared with Section S, and preferably little or no space between them. 
   Reference is now made to  FIGS. 3A–3E  which are simplified, time-sequential pictorial illustrations of an exemplary memory space during various stages of compaction in accordance with the method of  FIG. 2 . In  FIGS. 3A–3E  two concurrent Processes  150  are employed to compact Memory  140 , which is divided into four Sections  200  of equal size, designated Section 0  through Section 3  as shown in  FIG. 3A . In  FIG. 3B , Sections  200  are shown adjusted such that section boundaries do not fall within an object. In  FIG. 3C , each of the two Processes  150  are assigned a different Section  200 , Section 0  and Section 1  respectively, and Memory  140  is compacted according to the method of  FIG. 2  described hereinabove. Section 0  and Section 1  are concurrently compacted within themselves as no target section is exclusively available to receive objects from them. In  FIG. 3D , the two Processes  150  are each assigned a different Section  200 , namely Section 2  and Section 3 , as source sections. The Process which is assigned Section 2  uses Section 0  as a target section, with Object 4  and Object 5  being moved from Section 2  into the empty space created in Section 0 . At the same time, the other process which is assigned Section 3  uses Section 1  as a target section, with Object 6  being moved from Section 3  into the empty space created in Section 1 . As target Section 1  is not left with enough space to accommodate Object 7 , a new target section, Section 2 , is selected, into which Object 7  is moved as shown in  FIG. 3E . 
   It is appreciated that one or more of the steps of any of the methods described herein may be omitted or carried out in a different order than that shown, without departing from the true spirit and scope of the invention. 
   While the methods and apparatus disclosed herein may or may not have been described with reference to specific computer hardware or software, it is appreciated that the methods and apparatus described herein may be readily implemented in computer hardware or software using conventional techniques. 
   While the present invention has been described with reference to one or more specific embodiments, the description is intended to be illustrative of the invention as a whole and is not to be construed as limiting the invention to the embodiments shown. It is appreciated that various modifications may occur to those skilled in the art that, while not specifically shown herein, are nevertheless within the true spirit and scope of the invention.