Abstract:
A memory allocation method comprises: providing a memory, wherein a memory block of the memory has a first side and a second side; providing a memory controller; determining a memory allocation direction, wherein the first side is a starting point of a first allocation direction when the memory allocation direction is the first allocation direction and the second side is a starting point of a second allocation direction when the memory allocation direction is the second allocation direction; the memory controller allocates a part of the memory for a client program according to a corresponding memory allocation direction.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to a memory allocation method, and more particularly to a memory allocation method reducing memory fragmenting. 
         [0003]    2. Description of the Related Art 
         [0004]    Due to the limitation of memory size, embedded system uses heap memory for dynamically allocating heap memory as needed. When a memory request of one application program is sent to the operating system, the operating system allocates a memory block to the application program and the application program returns the memory block as the program ends. If many programs send memory requests to the operating system and not return the memory at the same time, the memory is easily fragmented and the performance of the memory suffers.  FIG. 1  is a schematic diagram of memory fragmentation caused by a conventional memory allocation method. In step S 11 , memory device  10  is initialized, thus, the entire memory device  10  is free. In step S 12 , memory device  10  respectively allocates memory block  11 , memory block  12  and memory block  13  for program A, B and C in response to the memory request therefrom, thus, only memory block  14  of memory  10  is free. In step S 13 , program B returns the memory block  12  to the memory device  10 , thus, the size of free memory of memory device  10  is the sum of the sizes of memory blocks  12  and  14 . However, when the memory size requested by one program is more than the size of any one of memory blocks  12  and  14  and less than the sum of the sizes of memory blocks  12  and  14 , there is not enough memory to run the program because the allocated memory is inseparable. 
       BRIEF SUMMARY OF THE INVENTION 
       [0005]    The invention provides a memory allocation method and system reducing memory fragment. 
         [0006]    The invention provides a memory allocation method comprising the following steps: providing a memory, wherein a memory block of the memory has a first side and a second side; providing a memory controller for determining a memory allocation direction, wherein the first side is a starting point of a first allocation direction when the memory allocation direction is the first allocation direction and the second side is a starting point of a second allocation direction, when the memory allocation direction is the second allocation direction. When a memory request of one application program is sent to the memory controller, the memory controller allocates a part of the memory for a client program according to a corresponding memory allocation direction. 
         [0007]    The invention further provides a memory allocation system comprising a application program, a memory, a memory controller and a memory allocation lookup table. The memory comprising a plurality of memory blocks has a first side and a second side. When a memory request of one application program is sent to the memory controller, the memory controller searches a memory allocation direction of one application program in the memory allocation lookup table, wherein the memory allocation direction selectively begins at the first side and the second side. 
         [0008]    One embodiment of a memory allocation method for a memory having a first side and a second side is provided, comprising receiving a memory allocation request of an application program; determining an allocation direction of the application program by a usage index of the application program; wherein the allocation direction being selectively the first side and the second side. 
         [0009]    A detailed description is given in the following embodiments with reference to the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0010]    The present invention can be more fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein: 
           [0011]      FIG. 1  a schematic diagram of memory fragment caused by a conventional memory allocation method. 
           [0012]      FIG. 2  is a flow chart of an embodiment based on the principle of the invention. 
           [0013]      FIG. 3  is a memory allocation lookup table of one embodiment of the invention. 
           [0014]      FIG. 4  is a schematic diagram of the memory allocation based on the memory allocation lookup table of  FIG. 3 . 
           [0015]      FIG. 5  is a schematic diagram of another embodiment of the memory allocation based on the memory allocation lookup table of  FIG. 3 . 
           [0016]      FIG. 6  is a block diagram of one embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0017]    The following description is of the best-contemplated mode of carrying out the invention. This description is made for the purpose of illustrating the general principles of the invention and should not be taken in a limiting sense. The scope of the invention is best determined by reference to the appended claims. 
         [0018]      FIG. 2  is a flow chart of an embodiment based on the principle of the invention. When one application program sends a memory request to operating system (OS), the OS searches the memory allocation direction of the application program in a memory allocation lookup table (step S 20 ). If the memory allocation direction is available, OS allocates a memory block for the application program based on the memory allocation direction of the application program (step S 21 ). If the memory allocation direction is not available for the memory request, OS allocates a memory block for the application program based on a predetermined memory allocation direction (step S 22 ). Then, the OS determines whether the memory allocation lookup table records the usage record of the application program (step S 23 ). If not, OS ends the procedure. If so, the method jumps to step S 24 . In step S 24 , the usage time of the application program is recorded and the memory allocation direction is determined based on the usage time (step S 25 ). In step S 26 , the memory allocation direction is added to the memory allocation lookup table. 
         [0019]    The memory allocation lookup table records a plurality of memory allocation directions and usage times of the corresponding application program. In the invention, a standard time is determined in accordance with the usage times, wherein the standard time is an average, a median or any evaluating value of the usage times. When one application program is not recorded in the memory allocation lookup table, a predetermined memory allocation direction is applied, and in one embodiment of the invention, the memory allocation lookup table adds the usage time of the application program and re-evaluates the standard time dynamically. 
         [0020]    In the invention, the memory allocation direction begins at a first side or a second side of a memory, wherein the memory can be divided into a plurality of memory blocks. When the usage time of one application program exceeds the standard time, the memory block allocated for the application program begins at the first side, i.e. the memory allocation direction begins at the first side. When the usage time of one application program does not exceed the standard time, the memory block allocated for the application program begins at the second side, i.e. the memory allocation direction begins at the second side. Moreover, the predetermined memory allocation direction starts at the second side. 
         [0021]      FIG. 3  is a memory allocation lookup table of one embodiment of the invention. In  FIG. 3 , the usage times of application programs A˜J are recorded and a standard time is determined based on the usage times. When the usage time of one application program exceeds the standard time, the memory allocation direction begins at the first side. When the usage time of one application program does not exceed the standard time, the memory allocation direction begins at the second side. In one embodiment, the standard time, 47.5 minutes, is the average time of the usage times of application programs A˜J. In another embodiment, the standard time, 45 minutes, is the mean time of the usage times of application programs A˜J. Furthermore, the standard time can be preset or determined based on calculating the usage times of application programs A˜J. 
         [0022]      FIG. 4  is a schematic diagram of the memory allocation based on the memory allocation lookup table of  FIG. 3 . In  FIG. 4 , the first side is the bottom of the memory  40  and the second side is the top of the memory  40 . In step S 41 , a memory block  41  is allocated to the application program A and a memory block  42  is allocated to the application program B. In step S 42 , the application program C sends a memory request to the OS, then, the OS search the memory allocation lookup table of  FIG. 3  to determine the memory allocation direction of the application program C. According to the memory allocation lookup table of  FIG. 3 , it is found that the memory allocation direction of the application program C begins at the second side, thus, the OS allocates a memory block  43  from the top of the available memory  45  to the application program C. In step S 43 , the application program D sends a memory request to the OS, then, the OS searches the memory allocation lookup table of  FIG. 3  to determine the memory allocation direction of the application program D. According to the memory allocation lookup table of  FIG. 3 , it is found that the memory allocation direction of the application program D begins at the first side, thus, the OS allocates a memory block  44  from the top of the available memory  46  to the application program D. 
         [0023]    In step S 44 , the application program A returns the memory block  41  to the OS, thus, the memory block  41  is available. In step S 45 , the application program E sends a memory request to the OS, then, the OS searches the memory allocation lookup table of  FIG. 3  to determine the memory allocation direction of the application program E. According to the memory allocation lookup table of  FIG. 3 , it is found that the memory allocation direction of the application program E begins at the second side. If the size of the memory block requested by the application program E is smaller than the size of the memory block  41 , the OS allocates a memory block to the application program E beginning at the top of the memory block  41 . If the size of the memory block requested by the application program E is larger than the size of the memory block  41 , the OS allocates a memory block to the application program E beginning at the top of the available memory  47 . In this embodiment, the size of the memory block requested by the application program E is smaller than the size of the memory block  41 , thus, a memory block  48  from the top of the memory block  41  is allocated to the application program E. 
         [0024]    To further illustrate the invention, please refer to  FIG. 5 .  FIG. 5  is a schematic diagram of another embodiment of the memory allocation based on the memory allocation lookup table of  FIG. 3 . In this embodiment, the size of the memory  50  is 1000H×20H bytes. In step S 51 , the application program A requests a memory block of 80H×20H bytes. Because the memory allocation direction of the application program A begins at the second side of the memory  50 , i.e. the bottom of the memory  50 , the OS allocates a memory block  51  from 00H to 7FH to the application program A. In step S 51 , the application program B requests a memory block of 200H×20H bytes. Because the memory allocation direction of the application program B begins at the first side of the memory  50 , i.e. the top of the memory  50 , the OS allocates a memory block  52  from E00H to FFFH to the application program B. In step S 52 , the application program C requests a memory block of 200H×20H bytes. Because the memory allocation direction of the application program C begins at the second side of the available memory  53 , the OS allocates a memory block  54  from 80H to 27FH to the application program C. In the step S 53 , the application program B returns the memory block  52 , thus, the single largest available memory size of the memory  50  is D80H×20H. Please refer to step S 54 . Step S 54  is a schematic diagram of the memory allocation based on a conventional memory allocation method. In the step S 54 , the total available memory size is the same as the total available memory size of step S 53 , but the single largest available memory of memory  50  is B82H×20H. According to the results of step S 53  and step S 54 , it is found that the memory allocation method of the invention increases the performance of memory and reduces memory fragmenting. 
         [0025]      FIG. 6  is a block diagram of one embodiment of the invention. When the application program  61  sends a memory request to the memory controller  62 , the memory controller  62  searches the memory allocation direction of the application program  61  in the memory allocation lookup table  63  and allocates the memory  64  based on the memory allocation direction. If the memory allocation lookup table  63  does not record the memory allocation direction of the application program, a predetermined memory allocation direction is applied. In one embodiment of the invention, the memory allocation direction can begin at a first side or a second side of the memory  64 , wherein the first side is the bottom of the memory  64 , such as the most significant bit or FFFH of  FIG. 5 , and the second side is the top of the memory  64 , such as the least significant bit or 000H of  FIG. 5 . In another embodiment of the invention, the first side is the top of the memory  64 , such as the most significant bit or 000H of  FIG. 5 , and the second side is the bottom of the memory  64 , such as the least significant bit or FFFH of  FIG. 5 . 
         [0026]    While the invention has been described by way of example and in terms of preferred embodiment, it is to be understood that the invention is not limited thereto. To the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.