CN100590609C - A Dynamic Memory Management Method Based on Discontinuous Pages - Google Patents

Abstract

The invention relates to a dynamic memory management method. The prior memory management method influences the utilization rate and the real-time performance of the memory. The dynamic memory management method of the invention comprises the following steps of memory allocation, memory recycle and address mapping, and has the details that a memory unit is divided into memory pages with the same size, and data which are logically connected are allowed to be stored in the memory pages which are not physically connected. The invention adopts the way of combining a counter and FIFO to manage the memory pages, so as to enable the memory allocation and the memory recycle to be more flexible, and the external fragment problem during the memory allocation is eliminated, thereby the utilization rateof the memory is improved, and the allocation and the recycle of the memory have the characteristics of real-time performance and predictability.

Description

A Dynamic Memory Management Method Based on Discontinuous Pages

technical field

The invention belongs to the field of integrated circuit design, in particular to a method for allocating, storing and managing memory in a network communication chip with real-time requirements, in particular to a dynamic memory management method based on discontinuous pages.

Background technique

There are often many different ways to manage memory, depending on the pattern of data access. When the data is stored in and taken out in the same order, it is usually managed with a buffer (Buffer) structure similar to first-in-first-out (FIFO). For example, the forwarding queue in a switch is managed with different forms of Buffer. When the sequence of fetching and storing data is different, there may be a piece of free cells (Hole) in the complete memory storage unit. If these small pieces of free cells scattered in the allocated memory cannot be handled correctly, it will greatly affect Memory utilization.

The dynamic memory method implemented by software mostly adopts the method of continuous allocation, and manages free memory blocks with two doubly linked list structures. With the continuous progress of memory allocation and recovery, the free list will gradually increase, and the search time to find a suitable memory block from this free list will also increase accordingly, and this time is related to the size of the requested memory block, so it cannot Meet real-time requirements. Moreover, the memory allocation method implemented by this software, in order to reduce the fragmentation problem, has added the function of splitting and merging (coalescing) of memory, but the introduction of these methods also affects the time determination of memory management to a certain extent. Sex (Time-BoundedService).

Contents of the invention

The purpose of the present invention is to overcome the shortcomings of the prior art and provide a dynamic memory management method based on discontinuous pages.

The dynamic memory management method of the present invention divides the memory unit into memory pages of the same size according to the characteristics of the data flow in the application environment. These memory pages are the smallest unit of memory allocation and also the smallest unit of memory management. The memory management method specifically includes Memory allocation, memory reclamation and address mapping. in:

The method of memory allocation is based on allowing logically connected data to be stored in physically non-contiguous pages. The specific steps include:

1. When the host requests memory allocation, the memory management unit compares the remaining resources of the current memory (including the total amount of free pages and the data identifier DataID) with the memory size requested by the host. If the total amount of free pages is greater than the total amount of memory pages requested by the host , and there are still available data identifiers in the memory management unit, continue memory allocation, otherwise end memory allocation. The information of continuing memory allocation and ending memory allocation is returned to the host after one system clock for query by the host. If the memory allocation continues, the memory management unit will use the "first zero detection" method to find an available identifier from the binary vector storing the DataID information, and assign the identifier to this piece of data.

2. The memory allocation unit enters the substantive allocation stage, and the memory management unit closes the response to the new memory allocation request. At the same time, the memory management unit reads the page number of the available page from the free page table management unit according to the requested page number, and writes it into the data page table management unit. Available pages in the free page table come from a counter or a first-in-first-out queue (FIFO), as determined by the value in the allocation mode register. When the value in the register is 1, the free page table management unit obtains the page number of the available page from the counter; when the value in the register is 0, it obtains the page number of the available page from the first-in-first-out queue.

3. If all the memory pages allocated to the host are transferred from the free page table to the data page table, the memory allocation is completed this time, and the memory management unit re-enters the state of receiving memory allocation requests, waiting for the next request; if allocated to If all the memory pages of the host are not completely transferred from the free page table to the data page table, go to 2 to continue the memory page transfer.

The specific steps of the memory recovery method include:

1. When the host requests memory allocation, the memory management unit compares the remaining resources of the current memory with the memory size requested by the host. If the total amount of free pages is greater than the total amount of memory pages requested by the host, and there are still available data flags in the memory management unit symbol, the memory management unit starts a countdown timer corresponding to this request, the initial timing value is T0, the timing step is 1 second, and the timing reference is input from the outside.

2. If a request is successfully allocated a block of memory, and the memory resource occupied by the data has not been recovered when the timer corresponding to the request reaches zero, go to 4; if the timer counts down to zero Before, the host no longer uses the data in the memory page, and can write an instruction to reclaim memory to the memory management unit, requiring the memory management unit to reclaim the memory page and data identifier resources occupied by this piece of data. The data identifier (DataID) corresponding to the data to be recycled should be pointed out in the instruction. During this process, the memory management unit stops the countdown timer and resets it to T0.

3. When the internal register of the memory management unit receives the instruction of "reclaiming memory" sent by the host, it will read all the memory pages corresponding to the data identifier in the instruction from the data page table in turn, and write them into the free memory page. page table, then go to 5. The times of reading and writing are the same as the total amount of memory pages occupied by the data corresponding to the data identifier.

4. When the countdown timer counts down to zero, and the memory resource occupied by the data corresponding to the timer has not been reclaimed, then when the data page table and the free page table are both free, the memory page occupied by the timed-out data is removed from the data The page table is sequentially read and written into the free page table, and at the same time, after all memory pages are recovered, the binary vector bit corresponding to the data identifier occupied by the data is reset again, that is, the data identifier (DataID) resource is recovered.

5. The memory recovery is completed.

The address mapping converts the logical address accessed by the user into the actual address that can access the physical memory. In the application environment of the present invention, the data in the memory is continuously written and read. For such data flow characteristics, the method steps of address mapping include:

1. When the host needs to access the memory, it first writes an instruction requesting read and write to the memory management unit. Among them, when the host reads the memory, it specifies the data identifier corresponding to the data to be read while sending a read request; and when the host needs to write the memory, it only needs to send a write request, and the identifier corresponding to the data is determined by the memory Managed automatically by the management unit, this identifier is allocated by the memory allocation unit when the host requests memory allocation.

2. When the memory management unit receives an instruction from the host that needs to access the memory, it takes the data identifier corresponding to the accessed data as the base address, offsets it to zero, combines it into a new address, and reads the header of the data storage in the data page table. The page number of a memory page is stored in the "current page number" register. Among them, when combining addresses, the data identifier is used as the high p bit of the address, and the low d bits of the address are all zeros. P is defined as wd, where w is the width of the address line in the memory, and d is the page offset of the logical address. Correspondingly, the size of each memory page is 2 ^d bytes (Byte).

3. When the host starts to access the memory, the memory management unit intercepts the low d bits of the logical address currently accessed by the host as the low d bits of the physical address, and uses the value in the "current page number" register as the high p bit of the address, Combined into physical addresses that can access memory. If the logical address accessed by the host is not the last byte in a page, turn to 4; if the logical address accessed by the host is the last byte in a page, the memory management unit intercepts the current access of the host in the same system cycle The high p bit of the logic address of the logical address, add 1 to the data of the p bit (denoted as p1) and combine it with the data identifier of the currently accessed data to form a new address, and use this address to read the page in the data page table management unit number, and in the next system cycle, update the page number obtained from the data page table to the "current page table" register.

4. If the host finishes accessing the memory, write the "end access" instruction to the memory management unit, and the memory management unit resets the "current page table" register, and waits for the next access request from the host; if the host still needs to access the memory, Then turn to 3 and continue the process of memory access.

The operations involved in the present invention (such as reading and writing memory, etc.) are basic technical common sense, and conventional technical means are adopted. The inventive point of the present invention is to provide a relatively advanced memory management process.

The present invention uses non-contiguous pages as the basic allocation and recovery unit, allowing logically connected data to be stored in non-contiguous pages. This method improves the flexibility of memory allocation, correspondingly, the external fragmentation of memory is eliminated, and the utilization rate of memory is improved.

Description of drawings

Fig. 1 application system structural diagram of the present invention;

Fig. 2 is a structural diagram of the memory allocation function of the present invention;

Fig. 3 is a flow chart of the memory allocation function of the present invention;

The sequence of Fig. 4 memory allocation process of the present invention;

Fig. 5 is an example of memory allocation results during system operation of the present invention;

Figure 6 Logical address to physical address mapping.

Detailed ways

The typical system application environment of the present invention is shown in Fig. 1, wherein the memory management unit is an example of the present invention. The present invention has three major functions: first, allocate memory and update memory record information; second, reclaim memory and update memory record information; third, address mapping. The specific implementation of each function will be further introduced below in combination with the description of the three main functional processes in the summary of the invention.

The structural diagram of the memory allocation function is shown in Figure 2, and the memory allocation process is shown in Figure 3. Among them, free page resources are managed by combining counters and FIFOs. In the initial stage of allocation, counters are used to allocate free pages, and the returned pages will be stored in FIFO. After all pages are transferred to FIFO, FIFO manages free pages. The working state of the free page table management unit is determined by the "allocation mode control" register. The introduction of counters eliminates the process of free page table initialization. The counter has another function. For the sake of the robustness of the memory management unit in practical applications, when the memory management unit is abnormal, the free page table management unit will return to the initial state ( Whether there is data in the memory can be judged according to the binary vector storing the data identifier, and when the vector is all zeros, it means that there is no valid data in the memory). At this time, it is only necessary to reset the counter and reset the free page allocation mode to the initial state. The whole process can be completed in a single clock cycle without affecting the normal work of the whole system.

During the memory allocation process, the state controller reads the available memory pages from the free page table and writes these memory pages into the data page table. The data page table is a SRAM structure, and the DataID is used as the base address for access to read and write. When all the memory pages corresponding to the data are transferred, the allocation ends. The timing diagram of the memory page transfer is shown in Figure 4, where RdEn is the enable signal for reading the available memory page information in the FIFO, and UpdateCEn is used to update the value of the counter to prepare for the next memory page transfer; WrDataStoreList Write enable signal for the data page table; TransFinish is used to control whether the memory page transfer is completed; FreePages is the page number of the free memory page.

Each part of data in memory has a unique ID (DataID) corresponding to it. DataID is represented by a binary array (bitmap), each bit represents a DataID, and the value of DataID is obtained by decoding the position of its corresponding bit in the bitmap. Memory allocation not only allocates available pages, but also allocates available DataIDs. DataIDs are obtained through the "first zero detector" algorithm. The input of the first zero detector is the bitmap corresponding to the DataID, and the output is the position of the first available DataID in the bitmap. The bit width of the DataID can be adjusted according to the application. For example, when 4 bits are used to represent the DataID, it means that the total number of DataIDs available in the system is ²⁴ .

The present invention supports two memory recovery methods: explicit and implicit. Both memory reclamation methods need to access the data page table and the free page table, so the conflict between the two accessing common resources must be properly handled. The explicit recovery of memory is initiated by the host. Before the countdown timer corresponding to the data expires, the host sends an instruction to request the memory management unit to reclaim the memory resources occupied by this part of the data. The instruction must include the DataID corresponding to the data to be recycled; The implicit recovery of memory is done automatically by the memory management unit without the participation of the host. When the memory allocation unit successfully allocates a piece of memory for a piece of data, it will start a countdown timer corresponding to the piece of data. The timing interval is 1 second, and the initial value T0 of timing can be configured by the user. In the embodiment of the present invention, T0 Take 4 seconds. When the countdown timer reaches zero, the memory management unit inserts a low-priority task in addition to tasks such as memory allocation and memory explicit recovery. When both the data page table and the free page table are free, the memory corresponding to the data will be timed out. Resources are reclaimed implicitly, which includes sequentially reading the memory pages occupied by the timeout data block from the data page table and writing them into the free page table. The binary vector bit corresponding to the symbol is reset, that is, the data identifier resource is reclaimed. The function of memory implicit reclamation is controlled by a dedicated state machine to change its state, avoiding the conflict problem during the access process of data page table and free page table.

In the application environment of the present invention, data is continuously read and written. When the host needs to access the memory, it first writes an instruction requesting read and write to the memory management unit. Among them, when the host reads the memory, it needs to specify the data identifier corresponding to the data to be read while sending the read request; and when the host needs to write the memory, it only needs to send a write request, and the identifier corresponding to the data is determined by Automatically managed by the memory management unit, this identifier is allocated by the memory allocation unit when the host requests memory allocation. The data identifier used in the read and write process is recorded as ID. When the memory management unit receives an instruction from the host to access the memory, it takes the data identifier corresponding to the accessed data as the base address, offsets it to zero, combines it into a new address, and reads the first memory of the data storage in the data page table. The page number of the page, and store the page number in the "current page number" register. Wherein, the manner of address combination is shown in FIG. 6 . When the host starts to access the memory, the memory management unit intercepts the low d bits of the logical address currently accessed by the host as the low d bits of the physical address, and uses the value CP in the "current page number" register as the high p bits of the address to combine The physical address of the memory that can be accessed. At the same time, when the logical address accessed by the host is the last byte in a page, the memory management unit intercepts the high p bits of the logical address currently accessed by the host in the same system cycle, and adds 1 to the data of the p bits ( Denoted as p1) and combined with the data identifier of the currently accessed data to form a new address, use this address to read the page number in the data page table management unit, and in the next system cycle, the data obtained from the data page table The page number is updated into the "current page table" register. Among them, p is defined as wd, w is the width of the address line in the memory, and d is the page offset of the logical address. Correspondingly, the size of each memory page is 2 ^d bytes (Byte). The way of address combination is shown in Figure 6.

When the host completes access to a certain block of data, it needs to write an "end access" instruction to the memory management unit, and the memory management unit resets the registers used for this access and waits for the next access request from the host.

The verification result of the present invention in the system is as shown in Figure 5, wherein the abscissa is the system time, the ordinate (left) reflects the real-time variation of the number of available memory pages in the present invention, and the ordinate (right) reflects the available data in the present invention Real-time changes in the number of IDs (DataIDs).

Claims (1)

1. A dynamic memory management method based on discontinuous pages, comprising memory allocation, memory recovery and address mapping, characterized in that: The method of memory allocation is based on allowing logically connected data to be stored in physically non-contiguous pages. The specific steps include: a. When there is data requesting memory allocation from the host, the memory management unit compares the remaining resources of the current memory with the memory size requested by the host. If the total amount of free pages is greater than the total amount of memory pages requested by the host, and there are still available pages in the memory management unit If the data identifier is specified, the memory allocation will continue, otherwise the memory allocation will end; if the memory allocation continues, the memory management unit will find an available identifier from the DataID information by using the first zero detection method, and assign the identifier to the host Request the data allocated by the memory; the DataID information is the unique identifier of each part of the data in the memory, represented by a binary vector; the first zero detection method uses the bitmap corresponding to the DataID as input, and puts the first available DataID in the bitmap The position in is used as output; the remaining resources of the current memory include the total amount of free pages and data identifiers; b. The memory management unit closes the response to the new memory allocation request, and the memory management unit reads the page number of the available page from the free page table management unit according to the requested page number, and writes it into the data page table management unit; The available pages in the page table come from the counter or the first-in-first-out queue, which is determined by the value in the allocation mode register. When the value in the register is 1, the free page table management unit obtains the page number of the available page from the counter; when When the value in this register is 0, the page number of the available page is obtained from the first-in-first-out queue; c. If all the memory pages allocated to the host are transferred from the free page table to the data page table, the memory allocation is completed this time, and the memory management unit re-enters the state of receiving memory allocation requests and waits for the next request; if allocated to All the memory pages of the host are not completely transferred from the free page table to the data page table, go to step b and continue the memory page transfer; The specific steps of the memory recovery method include: d. When the host requests memory allocation, the memory management unit compares the remaining resources of the current memory with the memory size requested by the host. If the total amount of free pages is greater than the total amount of memory pages requested by the host, and there are still available data flags in the memory management unit symbol, the memory management unit starts the countdown timer corresponding to this request, the initial timing value is T0, the timing step is 1 second, and the timing reference is input from the outside; e. If the data stored in the memory page in this request is not reclaimed when the countdown timer reaches zero, go to step g; if the data stored in the memory page in this request is in the Before the countdown timer reaches zero, the host no longer uses the data in the memory page, writes an instruction to explicitly reclaim memory to the internal register of the memory management unit, and stops the countdown timer and resets it to T0; f. When the internal register of the memory management unit receives an instruction to explicitly reclaim memory, read all memory pages corresponding to the data identifier in the instruction from the data page table in turn, and write them into the free page table, Then turn to step h; the number of times of reading and writing is the same as the total amount of the memory page occupied by the data identifier; g. When the data stored in the memory page in this request is counted down to zero, and the data in the memory page has not been recovered, if both the data page table and the free page table are free, the timeout will occur The memory pages occupied by the data are sequentially read from the data page table and written into the free page table. At the same time, after all the memory pages are reclaimed, the binary vector bits corresponding to the data identifiers occupied by the data are reset again, that is, the data identifiers are recycled. resource; h. End of memory recovery; The specific steps of the method for address mapping include: i. When the host needs to access the memory, first write an instruction to the memory management unit to request reading and writing, wherein, when the host reads the memory, it specifies the data identifier corresponding to the data to be read while issuing the read request ; When the host needs to write memory, it only needs to send a write request, and the identifier corresponding to the data is automatically managed by the memory management unit, and the identifier is allocated by the memory allocation unit when the host requests memory allocation; j. When the memory management unit receives an instruction from the host to access the memory, it takes the data identifier corresponding to the accessed data as the base address, offsets it to zero, combines it into a new address, and reads the header of the data storage in the data page table. The page number of a memory page, and store the page number in the "current page number" register; k. When the host starts to access the memory, the memory management unit intercepts the low d bits of the logical address currently accessed by the host as the low d bits of the physical address, and uses the value in the "current page number" register as the high p bit of the address, Combined into a physical address that can access the memory, if the logical address accessed by the host is not the last byte in a page, go to step m; if the logical address accessed by the host is the last byte in a page, the memory management unit is in In the same system cycle, intercept the high p bit of the logical address currently accessed by the host, add 1 to the data of the p bit and combine it with the data identifier of the currently accessed data to form a new address, and use this address to read the data page table The page number in the management unit, and in the next system cycle, update the page number obtained from the data page table to the "current page table" register; where p is w-d, w is the width of the address line in the memory, and d is The page offset of the logical address; m. If the host finishes accessing the memory, write the "end access" instruction to the memory management unit, and the memory management unit resets the "current page table" register, and waits for the next access request from the host; if the host still needs to access the memory, Then turn to step k and continue the process of memory access.

Images