JPH06511582A - Computer method and system for allocating and freeing memory - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention] 9 amazing computer methods and systems to allocate and free memory The present invention generally relates to computer methods and systems for managing memory. More specifically, allocating, freeing, and compiling memory using heap structures. This invention relates to a method and system for compacting.

Preliminary aid Computer systems can dynamically manage computer memory.

Dynamic memory management refers to the temporary allocation of blocks of memory for specific purposes. and deallocation or release when it is no longer needed for that purpose. refers to the process of Empty blocks can be used for reallocation for other purposes. can be done. The process that dynamically manages memory is called a memory manager. Ru. The memory managed by the memory manager is called a "heap." What is a heap? a data structure whose existence or size cannot be determined until the program is executed A portion of memory designated to a program for use in temporary storage.

A program requests a block of free memory of a certain size and uses it. You can then request that the block be released later. memory money The jars are made of different sizes from the heap depending on the needs of the program making the request. allocate a block of memory.

When a program needs a block of memory, it makes a request to the memory manager. send. The memory manager extracts memory from the heap to satisfy its requests. Allocate a block and obtain a handle or pointer to that memory block is sent back to the program making the request. then issuing the request A program accesses a block of memory through its handle, or pointer. can do. The program making the request must finish using the memory block. When a block is deleted, it notifies the memory manager that the block is no longer needed.

The memory manager then frees that memory block and uses it for allocation. It can be so. The memory manager sends notes to the program making the request. Unable to allocate a reblock (because the heap does not contain a large enough block) Sometimes the heap is usually compacted to consolidate all free blocks. to become

Afraid of thirst An object of the present invention is to provide an improved memory management process for computer memory. It is to provide.

Another object of the invention is to allocate blocks of memory to programs making requests. The objective is to provide an improved method for

Another object of the invention is that the program making the request no longer requires memory. By providing an improved way to free blocks of memory when they are no longer available. Ru.

Yet another object of the invention is to provide an improved method of compacting memory. That's true.

These and other objects will become apparent from the following detailed description of the invention. This is accomplished by an improved method and system for managing memory in a consistent manner. preferred In a preferred embodiment, a computer system that issues a request to be executed on a computer system; Ruflogramka, contiguous blocks of memory ( heap). The heap manager provided by the present invention manage the heap in response to instructions from programs that issue heap manager The heap manager divides the heap into uniformly sized 2″ segments. The programmer allocates a block of memory to the program making the request. request When the issuing program or memory block is finished using it, the heap manager frees a memory block and makes it available for allocation.

In the preferred embodiment, the heap manager maintains a free list for each segment. This creates a linked list of free blocks starting with that segment. It is. Each free list is routed through the largest free block array and size tree. Can be accessed. This largest free block array has multiple entries, with each An entry corresponds to one segment and the free list is opened for that segment. Points to the beginning. A size tree is one in which the value of each node is equal to the maximum value of its child nodes. This is a complete binary tree constructed as follows. Each leaf node of the size tree is Corresponds to two entries in the large free block array. included in each leaf node The values in the segment corresponding to the two entries in the free block array are Indicates the size of the largest free block.

The heap manager removes free blocks of memory of the requested size from the heap. Allocate a block of memory to the requesting program by selecting Ru. The heap manager searches the size tree and free block array to , select a segment containing a free block that satisfies the request, and then Search the free list corresponding to the requested segment and find the smallest free list that satisfies the request. An empty block is selected by positioning the empty block. heap money frees blocks of memory at the request of the requesting program. and place the freed block directly above or below it. merge with free blocks.

When the heap manager cannot satisfy an allocation request, it the program making the request. compact the heap or split the heap into larger or smaller sizes. give you the option of choosing which one to guess. The heap manager manages allocated blocks. blocks to higher addresses in the heap to free up free blocks at lower addresses. Compact the heap by consolidating. The heap manager Allocated blocks can be tracked to track where they are moved. Optionally maintains a handle to the block that was created. The program making the request When a program has a callback routine, the heap manager callback return and the allocated block is about to be moved. to notify the program making the request when the request is made, and A program cannot update the pointer it has to its allocated block. so that

Brief description of the drawing Figure 1 shows the relationship between the requesting program, the heap manager, and the heap. FIG.

FIG. 2A shows an exemplary segment layout of the block area shown in FIG. This is a diagram.

FIG. 2B shows an example segment layout of the block area shown in FIG. 2A. FIG.

FIG. 3 is a schematic diagram showing the relationship between a control area and a portion of a block area.

Figure 4 shows how the main program can allocate data blocks to the program making the request. 1 is a detailed flow diagram of the method used by Akira.

Figures 5A and 5B show data blocks in the requests of the requesting program. 1 is a detailed flow diagram of the method used by the present invention to release .

6A and 6B are used by the present invention to compact the heap. 1 is a detailed flow diagram of the method;

Figure 7A shows the size tree, largest free block array, data block array, and FIG. 2 is a schematic diagram showing the handle block and handle block in a state before compaction.

Figure 7B shows the size tree, largest free block array, data block array, and FIG. 4 is a schematic diagram showing the handle block and handle block in a state after compaction.

Detailed example of how to get rid of B The present invention provides a method and system for dynamic memory management of a heap.

A heap is a program that makes requests to temporarily store data structures. are logically contiguous areas of memory used by heap manager A program called respond to service requests made by programs running For service requests, It includes allocating, freeing, and compacting memory space within the heap. Figure 1 The program 100 issuing the request, the heap manager 101, and the heap FIG.

In the preferred embodiment, the memory manager maintains various data structures within the heap. hold Referring to FIG. 1, in a preferred embodiment of the invention, heap 105 is , divided into three main areas. That is, header area 1 that holds control information 02 and blocks of memory that are allocated and freed on demand. They are a block area 103 and a control area 104 containing control information. header area The area 102 is physically located below the block area 103 and The rear is physically located below the control area 104. Referencing a location in the heap When ``lower'' refers to the lower memory address, and ``upper'' refers to the upper memory address. means mori address. Alternatively, header area 102 and control area 104 may It does not have to be placed physically adjacent to the block area 103.

The header area 102 contains information such as the heap size, the structure of the control area 104, and blocks. Contains control information such as a pointer pointing to a specific block within the querier 103. Bro The storage area 103 is divided into segments. A segment is a free block. Logically of the memory used by the heap manager in maintaining the list It is an adjacent area. Dividing the block area 103 into segments is as follows. This will be explained in detail below. The block area 103 is also divided into blocks.

A block is a heap manager are logically contiguous areas of memory that are allocated and freed by

Each block in the block area 103 has a size field that indicates the size of the block. It starts with a cold. Preferably, the size of the blocks is an even number. This is because The lower bits of the size field are used to indicate whether the lock is free. This is because it is used. Free blocks have the lower bit of the size field set. and the allocated block, on the other hand, has this bit cleared. . All free blocks within a segment are linked together to Form a free list. Each free block preferably follows the size field a placed pointer to the next smallest free space starting in the same segment Contains a pointer to a block. Therefore, each segment the corresponding free block, which is a linked list (by size) of free blocks in the I have a list. The last field of each block is a free implied field. used. This free implicit field is unique if the block is free. Set to a special intelligence value. This free implicit field is determine whether the freed block is adjacent to a free block. used as an aid. If so, that freed block is next to It is combined with adjacent free blocks to form one free block.

Control area 104 includes a maximum free block array and a size tree.

The largest free blocks array is a list containing one entry for each segment. It is. Each entry in the largest free block array corresponds to Points to the start of the segment's free list. As mentioned above, each segment's free resources are A list is a linked list of free blocks within a segment based on size. The largest free block in the segment is now the start of the free list. There is.

A size tree is a data structure containing nodes linked together in a hierarchical form. It is a structure. A node carries a value representing the size of the largest free block within each subtree. Contains. The topmost node is called the root node. This root node is 2 has one child node, and the root node is the parent node for its child nodes. be. Each child node in the size tree has its own two child nodes . Each node in the size tree has exactly 1, except for the root node, which has nothing. It has one parent node. A node that has no child nodes is called a leaf node. Ru. A size tree means that any value contained in any node will be added to one of its child nodes. It is a complete binary tree with the property that it is equal to the greater of the included values.

The size tree is such that each child node is placed at position 2N and 2N+1 with respect to the parent node N. It is preferable that the The size tree is the largest size in each segment. Organize segments based on the size of large free blocks. The size tree is If the number of segments in a block area is N, it contains N-1 nodes. I'm here. Each node in the size tree has the largest size available in its subtree. Contains the size of free blocks, so the root node is the largest free block in the heap. Contains the size of the block. Each leaf node of the size tree has a maximum free block. corresponds to two entries in the quad array and the largest free block in the array. Set the size of the largest free block indicated by the corresponding entry to the leaf node. It is now included.

The block area is divided into 2″ sections to correspond to the size tree, which is a complete binary tree. segment. In the preferred embodiment, during heap initialization, The program manager sets the size of block area 103 to the minimum segment size. the number of segments by dividing and rounding the result to the next lowest power of 2 Determine. Minimum segment size (specified by the program making the request) (specified) is typically 100% based on the needs of the program making the request. It can be any value between 0 and 2000 bytes. The final segment size is The size of the storage area 103 is determined by dividing the size of the storage area 103 by the number of segments.

For example, if block area 103 contains 900 bytes and “C minimum segment size If the size is 100 bytes, the heap manager uses the final segment size. Determine the size as follows. First, the heap manager has a block area of 1° Divide the size of 3 by the minimum segment size to get 9 (900/100). No. 2, the heap manager rounds the result to the next lowest power of 2 and divides the result into segments. Determine the number of points. Rounding 9 to the next lowest power of 2 results in 8 segments. most Later, the heap manager segments the size (900) of block area 103. The final segment size is 113 bytes (900/ 8) Determine. The last segment is only 109. Because in this example This is because the number of segments in the block area is not evenly divided into the size of the block area. be. FIG. 2A shows a block area with eight segments 200 to 207. 103 is an exemplary segment layout.

FIG. 2B is an exemplary block layout of block area 103, with segment Component boundaries are shown with dashed lines, and block boundaries are shown with solid lines. . The block area 103 includes a handle block 210 and a master block 21. 1 and a data block 212 payout end block 213. issue a request The program using the block identifier, which is a handle or pointer, access the data block. A handle is an allocated block of memory. It can be thought of as a pointer to a pointer. make a request When a program running requests a block of memory, the heap manager allocates a block of memory, and then Sends the block identifier back to the program making the request. The program is in control When requesting a logical response (e.g., freeing a block), the program Block identifiers are used to identify blocks. The handle block 210 is described below. data block to prevent the block from being moved during heap compaction. Preferably, it is located below the rack 212.

The master block 211 has a handle block 210 and a data block 212. Preferably, it is placed between. The master block 211 is a handle block 210 or the bottom of data block 212. Contains a large amount of memory space. When the heap is initialized, the master block The block contains all available free space. The heap manager -by transferring free space in the form of data blocks from the top of the block. allocates the data block to the program making the request. master bro Blocks can be used to provide additional space for the blocks above and below them. , so the master block does not always contain extra space. data blog Is block 212 a block allocated to the program making the request? , or a block that is free and available for allocation. Block allocation and release are shown in FIGS. 4 and 5, respectively, and are discussed below. en Block 213 contains the free space to be used during the heap shake. This will be explained in detail in the "Debugging" section. master block 21 1 and end block 213 are not allocated to the requesting program. The block is marked as allocated, as if it were an allocated block. Also, end block 2 13 is also used while freeing data blocks.

FIG. 3 is a schematic diagram showing the relationship between a control area and a portion of a block area. . In this example, the block area is divided into eight segments (segment (mention boundaries 340-342 are shown in dashed lines). The control area is the size It includes a tree 300 and a largest free block array 310. maximum free block Quaray entries 320 to 327 each represent a block area segment. Corresponds to numbers O to 7. In Figure 3, only the data blocks of segments 5 and 6 are shown. Not shown. Entries 326 in largest free block array 320 are segment Points to the beginning of the free list for point 6. Block 331 is the start of the free list. Department. Block 331 then points to the next smaller free block 332. contains an inter, and block 332 points to the next smaller free block 333 Contains pointers. Even if free block 334 crosses segment boundary 341 Even though it is extended, free block 334 is not included in the free list of segment 6. Please note that. Entry 325 in largest free block array 310 is a pointer pointing to free block 334, which is the beginning of the free list for segment 5. Contains ta. The free list for segment 5 includes blocks 334-336. nothing.

The example used in Figure 3 shows the entry of the largest free block array 310 containing the null pointer trees 320 to 324 and 327 (segments 0 to 4 and segments 0 to 4, respectively) (corresponding to point 7). Null pointer is used for the corresponding segment Indicates that there are no free blocks available. Leaf node 304.305 (ent correspond to segments 320 to 323, which in turn correspond to segments 0 to 3. ) is the size of the largest free block in segments 0 to 3. It contains the value O representing the value. Leaf nodes 306 in segments 4 and 5 Includes 3o, which is the size of the largest free block. The leaf node 307 is Contains 4o, which is the size of the largest free block in segments 6 and 7. I'm here. Each node in the size tree is the largest free space available for its subtree. contains the size of the block, so node 302 contains 0 and node 303 contains 4o. include. The root node 301 is the size of the largest free block in the heap including 40.

In another embodiment, the size tree of the above example may have nodes 303.306 and 3. Consists of only 07. Node 303 becomes the root node. heap manager The pointer to the root node of the size tree is stored in the header area 10 of Figure 1. Maintain at 2. Segments 0 to 3 do not contain any free blocks, so , not represented in the size tree. This example of a size tree Reduces the amount of searches that need to be done to find blocks. A block When a block becomes free in segment 0, 1.2 or 3, the size tree 300 Grows to include nodes 301.302.304 and 305 and becomes the root node The pointer to the pointer is adjusted accordingly.

The heap manager described here handles and points that refer to data blocks. Supports both interfaces. During compaction, the heap manager The heap manager makes an arbitrary callback to the program issuing the request. Instructs to move a block to a new position. Program making the request then returns any pointer it can use to represent the new position of the block. can also be updated. Can be used for handle blocks during assignments If there is no handle, the heap manager handles the handle from the bottom of the master block. Gain space and expand the handle block. If the master block is too small If so, the heap manager compacts the heap and re-enters the request. Ru. Alternatively, the heap manager may Call the supplied routine. This routine is called ``compact heap.'' It is explained below under the following heading.

Data Block Request Process: Figure 4 is a flow diagram of a preferred embodiment of the present invention. be. This flow diagram allocates data blocks to the program making the request. This is an overview of the methods used by the heap manager to requested An allocation request for a data block with a specified size is passed to the heap manager. be done. The process begins at step 401, where a heap manager is required. Determine the size of the block to be used. Use the heap manager internally The size of the size field and other operational control fields can be determined by the requesting program. must be added to the size required by the program. In step 402 The heap manager determines the required block size using the size tree The value contained in the root node of (this is the size of the largest free block) It is determined whether the requirements can be satisfied by comparing with the heap manager The pointer to the root node of the size tree is stored in the header area 10 of Figure 1. Maintain at 2. The required block size is the root node of the size tree is less than or equal to the value contained in the data block request. Blocks are currently available for use.

The process continues to step 406 where the heap manager fills the heap to satisfy the request. Search the size tree using the right-hand method for blocks that are as large as the size of the block. -L address be allocated before a free block at the address or a free block at a lower address. The tree is searched in a right-handed manner to ensure that. For example, a spacer node satisfies a request. The right child node precedes the left child node if it contains a value large enough to add. selected. Similarly, both entries in the largest free block array satisfy the request. If you want to point to a free list containing blocks large enough to is selected before the left entry.

When the heap manager selects the largest free block array entry, the The process continues to step 407, where the heap manager determines the minimum usage amount that satisfies the request. to the selected entry to find and select an available free block. Therefore, the designated free list is searched. A free block like this is selected After that, in step 408, the heap manager stores the selected free Even if the block is divided into two blocks, it is large enough to satisfy the requirements. determine whether there is. One block is large enough to satisfy the request. and the other block stores the necessary pointer information and block size. An empty block is large enough to be partitioned into two blocks if it is large enough. It is a large size. If so, the process continues to step 409 where the block block is partitioned into two blocks, one of which is assigned to the program making the request. one is applied and the other is kept in the free list. Vacant The remainder of the block is inserted into the free list at the appropriate position, if necessary. For example, the size tree and max free block array will be changed to the new (smaller) max Updated with is.

Even if the selected free block is partitioned into two data blocks, the request cannot be satisfied. If it is not large enough, in step 410 the heap manager , removes the selected free block from the free list, and optionally update the size tree and largest free block array. The process is step 412 where the heap manager fills the free implicit field and the size field. Allocates the selected free block by clearing the lower bit of the field. Mark as correct. The heap manager uses selected free blocks The block identifier, which is a handle or pointer that refers to the address of send it back to the program you are using. The block identifier is just above the size field Refers to the memory location of

Referring to step 402, the size of the required data block is empty to satisfy the request if the value is greater than the value contained in the root node of the tree. block cannot be used in the block area. The heap manager is also by obtaining space from the master block, if space is available. attempt to satisfy the program issuing the request. master block support The size is stored in the master block size field and points to the master block. The pointer is stored in the header area. get space from master block Then, in step 403, the heap manager removes the master block from its master block by merging it with a free block that would be located directly above it. attempt to expand the network. Then, in step 404, the heap manager The controller determines whether the data block request can be accepted by the master block. to judge. This decision determines the size of the data block required by the master block. This is done by comparing the size of the The master block satisfies the request. If the heap manager is not large enough to then makes an out-of-memory call and returns to block 402 to try again.

Alternatively, the heap manager may be supplied by the program making the request. Call the routine that is called. This routine performs the concept of ``compacting the heap.'' It will be explained below. After compaction, the process returns to step 402 and returns, where the heap manager determines that there is enough memory to satisfy the request. Determine whether there is. Satisfy the request after compacting or expanding the heap If there is not enough memory for the requesting process, the heap manager Inform Gram of your inability to fulfill his request.

In step 404, the master block is large enough to satisfy the request. If so, the process skips to step 411 where the heap money is The jar transfers the requested amount of space from the master block and stores the new data. Form a tab lock. Data block from space transferred from master block After the lock is formed, the process ends at step 412, where each The group manager clears the lower bits of the size field. Mark the newly formed data block as allocated.

The heap manager assigns a block identifier to its newly formed block. is sent back to the requesting program. This block identifier is the block Refers to the memory immediately above the size field.

ENIEBU 3EKU 9 RELEASE: FIGS. 5A and 5B show the flow lines of the preferred embodiment of the present invention. It is a diagram. This flow diagram shows how to deallocate or free a data block. An overview of the methods used by the heap manager. data block solved When released, the free block immediately above or below it in the heap combined with The program making the request must Pass the block identifier of the lock (current block) to the heap manager.

The process begins at step 502, where the heap manager is issuing a request. The current block can be changed by adjusting the block identifier given by the program. Set the pointer to point to the beginning of the block. The size field is the block's Contains the size and is placed at the start of the block. The process continues to step 503. The heap manager uses the free implicit space for the block immediately below the current block. Check the field. The empty implied field is the last frame of each data block. field. Free implicit fields are quickly checked by the heap manager. to check if a block is free.

If the empty implied field of the block immediately below the current block contains the intelligence value, then , may be blocked or empty. Empty hint field or does not contain a hint value If so, a block is allocated. A free implied field is allocated by a block. If so, the process returns to block 510 of FIG. 5B. Click. The free hint field indicates that the block may be free. If the block is free, the heap manager performs further checks to ensure that the block is free. have to decide whether or not. The empty implied field indicates that the block is empty. There is no guarantee that the data contained in the allocated block will be , appears to be the intelligence value used by the heap manager.

The empty implied field of the block immediately below the current block (lower block) is blocked. When indicating that the heap manager may be free, the heap manager , the lower bits of the size field in its lower block must be checked. Must be. Heap money to find the starting position of its subordinate blocks The free list for the segment that currently contains the block (the current segment) search and try to find the lower block. heap manager looks at addresses below the addresses in the current block when traversing the free list. Check the address of each block in the free list until it is reached. The block I found By adding the size of the lock to the address of the block, the heap manager can determine whether a block is currently directly below it.

If the descendant block is not currently on the free list for the segment, the heap manager The manager must search the segments below the current segment.

The heap manager will continue to hold the current segment until a non-zero pointer entry is found. Search for the largest free block array entry corresponding to the segment under the do. When a non-cello pointer entry is found, the heap manager Searches for the free list pointed to by the entry, and searches for the free list that is currently blocked. Determine whether to include the free block immediately before the lock.

In steps 504-505, the heap manager stores the current block. Check the free list for the containing segment (current segment) and check the current block Determine whether there is a free data block immediately below. Currently in segment If no free block is found in the free list for the Proceed to step 506, otherwise the process skips to step 509 of FIG. 5B. . In steps 506-507, the heap manager determines whether the current segment starting from the bottom of the entry corresponding to the block entry and ending with the largest free block array. Search towards the next non-cello pointer entry. Entries like this If the process is not found, the process skips to step 510 of FIG. 5B. .

If a non-zero pointer entry is found, the process proceeds to step 5.8. , the heap manager returns the non-cello pointer in the largest free block array. Examine the free list pointed to by the contact entry and check the current block's immediate Determine whether there is a free block below. If you find a free block like this If not, the process skips to step 510 of FIG. 5B. This way If such a free block is found, the process returns to step 509 of FIG. 5B. Continue.

Referring to FIG. 5B, in step 509, the heap manager merge the empty block with the free block immediately below it, and Remove lower free blocks from the free list.

Then, in steps 510 to 5], the heap manager Check the second data block (the second block) of the lock and confirm that the block is Determine whether it is vacant. The current block size is recorded in the size field. The heap manager determines the size of the current block. address of the block immediately above the current block by adding it to the address of the block immediately above the current block. decide. Once the address is known, the heap manager determines which segments are top It can also be determined whether blocks are included. The lower bits of the size field indicate whether the block Set if the block is free and cleared if the block is allocated.

If the upper block is free, the process continues to step 512 and the heap The manager removes top blocks from its free list and and update the size tree.

When the current block is positioned at the top of the block area, the end block It will be just above the lock. The end block is marked as allocated. The heap manager currently cannot combine blocks with end blocks because do not have. An end block always has a valid block above it. ensure that it exists.

In step 513, the heap manager selects the upper block as the current block. integrate with. If the upper block is not free, the process continues at step 514. Skip to. In step 514, the heap manager Set the lower bit of field to 1 and write the intelligence value to the empty implied field. Mark the current block as free by Then heap management The controller adds the current block to the free list for the current segment, and if Update the size tree and largest free block array if necessary.

Heap compaction: The heap manager is the program issuing the request. Free data blocks in a heap large enough to satisfy allocation requests from When the heap cannot be located, the heap manager compacts the heap. , retry the request. Alternatively, the heap manager issues the request Call a routine supplied by the program that is running. This routine including making other service requests to the heap manager to free memory. Appropriate action can be taken. Usually determined by the program making the request. The routine supplied with ) or a service request to free the data block. or requests to the heap manager to compact the heap. Execute a certain combination. During compaction, the heap manager moves For each block of data that is to be If a command is supplied, call that routine and Notify the program that there is a new address for the data block. issue a request The program that is using the data block then returns the pointer it has to the data block. You can change the printer.

6A and 6B are detailed flow diagrams of a preferred embodiment of the present invention. this flow The diagram moves all allocated blocks to higher memory addresses and Forming one large free block of memory at the bottom of the data block area used by the heap manager to compact the heap. This is an overview of the method. The new free block then becomes the master block. Incorporated. Alternatively, the program making the request may make further requests to the heap. Larger or even smaller sizes can be assigned.

Referring to step 601 of FIG. 6A, the heap manager stores the Scan all data blocks and link all free blocks together. Each block The size field located at the beginning of the lock contains the size of the block and is used to position the next block. The heap manager handles data blocks. From the top of the query area (upper address) to the bottom of the data block area (lower address) Link free blocks to Scan all data blocks and remove free blocks. After linking the locks together, in step 602, the heap manager whether the requesting program allocates a new size for the heap or Please judge. The program making the request has a larger allocation on the heap. has the option of being assigned a smaller size. making a request When a program requests a small size for the heap, it The heap size given is either the requested size or includes allocated blocks. Whichever size you need is the larger one.

When the requesting program allocates the heap for a new size , the control area is moved to the top of the heap of new size. The heap is new If the size is allocated to the heap manager, the process continues to step 603 and The manager calculates the number of segments for the new size heap and then In step 604, the new position of the largest free block array and size tree is determined. Determine.

When the heap is allocated to a new smaller size, it is treated as if the heap A compaction is performed first as if had not changed size. Next and after this first stage, the entire group of compacted and allocated blocks is the loop is moved to its first position. The source and destination of this final movement The difference between them is called the downshift amount. The heap can be made larger or the same size. When the engine is forced to maintain the same position, the downshift amount becomes zero. new heap If not allocated for the size, the process continues from step 602. Skip to step 605.

In step 605, the heap manager determines the free block's linked It traverses the list and returns a value for each block representing the total amount of free space thus traversed. memorize it in the book. The total amount of free space is the free space placed within each free block. Stored in the space field. This same space is empty for implied fields and Free space is preferably used for fields. This value is Displays the amount by which each allocated block under a lock is moved during compaction. vinegar.

In steps 606-610, the heap manager Determines how far the affected blocks are moved during compaction, and Update handles to these blocks accordingly. /) The noddle is empty. or allocated, i.e. the allocated handle is Contains an indirect reference to the block that was created. The handle is shown in Figure 2B /1 is stored in the handle block 210. In step 606, the heap manager The handler traverses the handle block and selects the next assigned handle and the Select handles starting with the first one.

In step 607, the heap manager determines that all handles have been selected. judge whether If all handles are selected, the process will Continue to step 608. In step 608, the heap manager Selects the allocated block referenced by the selected handle. Step At step 609, the heap manager stores the first Attempts to locate a free block in . An empty block is placed next to the selected block. If there is no lock, the process loops back to step 606 and Manager selects the next allocated handle. The heap manager , first determine which segment contains that selected block. Position the empty block by The heap manager then segment containing the selected block or the segment containing the selected block. Search the largest free block array for non-cello pointer entries corresponding to do.

If a non-zero pointer array is found, the heap manager Searches the free list pointed to by the interface and returns the block referenced by the handle. Locate the free block at the lowest address of the lock. Free list at this time Note that is the list of free blocks already formed in step 601. I want to be. Once the free block is located, in step 601 the heap map is The manager fills the empty block at the address stored in the selected handle. by adding the value of the space field minus the downshift factor. and update its address. The heap manager manages allocated blocks Step 606 does not occur until all handles for L61 have been selected and updated. Repeat 0.

Referring to FIG. 6B, in steps 611 to 613, the heap manager moves allocated blocks to higher addresses and removes all free blocks. Accumulate blocks at the bottom of the data block area. In step 611, In the linked list generated in step 601, the group manager Select the next free block, starting with the first one. Each free block is The Free Space field contains a value that indicates the amount of free space in that seven blocks. It is included in the code. In step 612, the heap manager stores all free Determine whether a block has been scanned. all free blocks are scanned If not, in step 613 the heap manager between the selected free block and the free block below it. Move to a new higher address. The new address is selected over the old address. is calculated by adding it to the value stored in the Free Space field of the free block that was created. calculated.

The heap manager scans all free blocks and Steps 611 to 6 until the lock or other appropriate sign is moved toward E. Repeat step 13. After all free blocks have been scanned, in step 614 The heap manager then shifts all allocated blocks to If there is a number, move to the final position specified by this number. This causes The free space accumulated at the bottom of the data block area is It is added to the master block in step 615. Step 616 Smell The size tree and max free block array no longer contain free blocks in the heap. It is reinitialized so that it does not exist.

Figures 7A and 7B are schematic diagrams used to illustrate an example of the compaction process. be. FIG. 7A shows the size tree 700, maximum free block array 7101 data The block array 730 and the handle block 750 are in their state before compaction. 7B is a schematic diagram showing the size tree 7001 maximum free block. square array 710, data block array 730, master block 740 and hardware block array 710, data block array 730, master block 740 and FIG. 7 is a schematic diagram showing the handle block 750 in a state after compaction. hand Block 750 is preferably located at the bottom of segment 0, or in this example Description 1 - Shown without reference to segment numbers. Data block area 7 The dashed lines at 30 indicate segment boundaries, while the solid lines indicate block boundaries.

Data block area 730 is divided into eight segments.

In this example, the program making the request is for a block of memory of size 10. Make quota requests. Referring to FIG. 7A, this allocation request fails.

This is because, as indicated by the root node 701 of the size tree 700, the usage This is because the maximum available free block size is 6. In addition, Master Pro Tsuku is too small for the heap manager to transfer free space. data pro The storage area 730 stores empty blocks FO-F3 and allocated blocks. Equipped with AO-A8. The handle block 750 is The handles HO-H8 each identify the position of the handles HO-A8. Each block's support The size is stored in the first field of each block, the size field. example For example, the size of block AO is 6.

The purpose of compaction is to remove all free blocks in the data block area 730. merge blocks and add them to the master block. To do this, the assigned block Lock AO-A7 must be physically moved to a higher address. Allocation The moved block A8 cannot be moved because there is no empty block above it. Not moved. Determine the amount by which each allocated block must be moved To do this, the heap manager first scans all data blocks and and then move the empty blocks FO-F3 together from the top to the bottom of the data block area. form a linked list of free blocks. each vacancy The block contains a pointer to the next F free block. This point Preferably, the size field is placed after the size field. Next, heap management The manager traverses a linked list of free blocks, traversing it like this A value representing the cumulative amount of free blocks is stored in each block. This value is the free space Memorized in field.

For example, the heap manager assumes that free block F3 has size 4 and this Since the empty space scanned as follows is 4, the empty space of empty block F3 is Store 4 in the space field. The heap manager then uses the free blocks 10, which represents the sum of the size of F3 and the size of free block F2, is the size of free block F2. Store in free space field. The heap manager uses free block F1 and store 12 and 16 in the free space field of FO, respectively. empty block free space field of the last free block in a linked list of blocks The value stored in represents the total amount of free space in the data block area. ing.

After determining the beast of free space above that containing each free block, each Before moving an allocated block, the heap manager handles HO- Update H8. As mentioned above, a handle is an allocated block of memory. This is the identifier of the To update the handle to the allocated block , the heap manager handles the allocation of allocated blocks as they are moved. Calculate how much the address of the assigned block changes. empty block The value stored in the free space field of the block is the value stored in the free space field of that free block and the next Each allocated block between it and a free block must be moved It's the amount. For example, allocated blocks A3-A3 are of free block F2. The amount of downshift from the value stored in the free space field, which in this case is 0. is moved upward by 10, minus .

The heap manager has a handle to the allocated block A5. 1 Select handle H5. Heap money based on the address of block A5 determines which segment contains block A5. Block A5 is Starting at address 30, segment 3 includes block A5. then , the heap manager selects entry 723 ( This entry 723 corresponds to segment 3). Determine whether there is a block. Entry 723 is empty in segment 3. Contains a zero pointer indicating that there are no blocks.

The heap manager then starts with an entry for segment 4. search the largest free block array 710 and find the first non-cello pointer entry. Search for. Entry 724 corresponding to segment 4 is a non-cello pointer. Including entries. The heap manager uses the empty space indicated by entry 724. Start with a free block, search the linked list of free blocks, and assign The address closest to and larger than the address of the assigned block A5 is also Search for one free block. Entry 724 points to free block F2.

Empty block F2 is placed before allocated block A5. Hee The manager stores the value stored in the free space field of free block F2. Add (10) to address (30) of allocated block A5 and shift The handle H5 is updated by subtracting the amount of down. The result is 40. This is the address after the movement of the allocated block A5. This new The address is stored in the handle H5, as shown in FIG. 7B. remaining hand The process described above is repeated to update the file.

After all handles have been updated, the heap manager updates each allocated block. physically move the rack. The heap manager links free blocks Select the first free block F3 in the list and link it with free block F3. Which allocation is made between free block F2, which is the next free block in the list? Determine if there are any blocks that have been The heap manager has a free block F3. Empty all allocated blocks by the amount stored in the free space field. move in one direction between blocks F3 and F2. Therefore, the assigned blog Books A7 and A6 are moved to one side by 4 units. Then heap management The player selects the next free block F2. Empty block F2 is the empty space Since the field contains the value 10, all free blocks between F2 and Fl The allocated blocks (allocated blocks A5-A3) are 10 units. is moved upward. This process ensures that all allocated blocks are This continues until it is moved upwards. The assigned program 8 is It will not be moved because there is no free space. If the heap is made smaller, block Lock AO-A8 is moved downward by the downshift amount.

Figure 7B shows the compaction results. The data block area 730 is including allocated blocks AO-A8, and between these allocated blocks. There is no free space. Empty block F　O-F　3 in Figure 7A is the square in Figure 7B. integrated into the turret block 740. The handle block 750 is a handle H Contains 0-H8. Size tree 700 and largest free block array 710 has been reinitialized. This is because data block array 730 has empty blocks. This is because it does not include

Debugging 2 The present invention ensures that the program that is making the request is correctly updated. It also provides a method for locating pointers that are not located. The program making the request Programs sometimes use pointers to identify allocated blocks. There is. These pointers become invalid when the allocated block is moved. To ensure that the allocated blocks are updated, the invention automatically Provides a navigable debugging mode. In fact, the heap does not store any pointers. Errors are also ``shaken'' to push them to the surface. Heap storage enabled When allocated, the heap manager allocates a predetermined amount after satisfying an allocation request. only move all data blocks. Each allocated block is moved when the requesting program has access to the moved block. routine (by the program making the request) to update the pointer (supplied arbitrarily) or called.

After all blocks have been moved, these blocks will be moved back to their starting position. It will be returned. The movement space of this "heap shake" is the data block area Preferably, it is maintained in an end block located on top of the end block. The end block , never allocated to the requesting program, and the master block heap shake is never reduced beyond what is currently required to support heap shaking. Not done. During each "shake", all internal free block pointers are Updated by scanning the block and adding or subtracting a predetermined shake amount . Each data block (allocated and free) is then moved to a different position. Finally, all hands for the allocated block is updated to a new value by adding or subtracting a constant. size tree , prevents the need to update the maximum free block array and the free list for each segment. segment from a tunable base that is updated after each heapshake to address is calculated.

Although the method and system of the present invention have been described above with reference to preferred embodiments, the present invention is not limited to this example. Modifications within the scope of the invention will be apparent to those skilled in the art. It will be clear. Therefore, the scope of the invention should be limited only by the claims. To be.

Claims (14)

[Claims] 1. A computer that manages the heap in response to requests from programs that make requests. A computer system method, wherein the heap has a plurality of free blocks and a plurality of free blocks. has an allocated block and is logically divided into multiple segments, each A block has a certain size, each segment has a free list, and each free list contains the list of free blocks in the segment, and the heap has the associated It has a free block array and a size tree, and the free block array has multiple en- tree, each entry corresponds to a segment and its corresponding segment A size tree has multiple non-leaf nodes and multiple has leaf nodes, each non-leaf node has multiple child nodes, and each non-leaf node has multiple child nodes. A node is such that the value of each non-leaf node is equal to the maximum value of its child nodes. each leaf node has multiple entries in the free block array. the largest free block in a segment that corresponds to and that corresponds to multiple entries. the block size, and the above method generates a block of the requested size. The stage of selecting free blocks for allocation in response to an allocation request. Then, search the above size tree and free block array to satisfy the request. Select a segment that contains free blocks, and then select that selected segment searches the free list corresponding to the request and selects the free block that satisfies the request. a step of selecting a free block by Frees an allocated block in response to a request to free the allocated block. , in addition to the free list for the segment containing that allocated block. the allocated free blocks by updating the free block array and size tree. and releasing the block. 2. The size tree above is a binary tree, and the number of segments is a power of 2. 2. The method of claim 1. 3. 2. The method of claim 1, wherein each free list is a linked list. 4. Each free list is a linked list in some order and its linked Claim 3, wherein the largest free block in the list is placed first. The method described in. 5. The above segments are ordered from lower segment to upper segment; The above step of selecting a free block with a size large enough to satisfy the request A claim for selecting a free block from the topmost segment containing a free block with The method described in 1. 6. The above segments are ordered from upper segment to lower segment, and The above step of selecting a free block with a size large enough to satisfy the request A claim for selecting a free block from the lowest segment containing a free block with The method described in 1. 7. The above step of selecting a free block contains a value large enough to satisfy the request. Select a leaf node to select the free block corresponding to the selected leaf node. An array entry that contains free blocks large enough to satisfy the request. Select the entry that points to the free list, the free list directed by that selected free block array entry select a free block large enough to satisfy the request, and Removes the selected free block from the free list and makes the selected free block free. Update size tree and free block array to represent removal from list. 2. The method of claim 1, including the step of renewing. 8. a computer used to manage memory in a computer system a data structure, A block area containing multiple free blocks and multiple allocated blocks. , block area divided into multiple segments and free space for each segment. a list of free blocks in the segment, and a free list, which is a list of free blocks in the segment; Free block with an entry corresponding to each segment in the block area In an array, each entry points to a free list for the corresponding segment. a free block array containing data and at least one non-leaf node and a size tree containing multiple leaf nodes, where each non-leaf node has multiple child nodes, each node has a certain value, and each leaf node has the above empty corresponds to multiple entries in the block array, and has a value representing the size of the largest free block in the segment corresponding to the , the size such that the value of each non-leaf node is equal to the maximum value of its child nodes. A computer data structure comprising a tree. 9. 9. The block area is divided into 2n segments. data structure. 10. 9. The data structure of claim 8, wherein the size tree is a binary tree. 11. The data structure according to claim 8, wherein the free list is a linked list. Structure. 12. 9. The free list is ordered based on block size. Data structure described. 13. Each allocated block has a corresponding handle, which handle to map the handle to its corresponding allocated block. 9. The data structure of claim 8, comprising a dollar map table. 14. The above handle map table is a request to be stored in the allocated block. The data structure according to claim 13.