Patent Publication Number: US-8539198-B2

Title: Memory management system

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a divisional application of U.S. patent application Ser. No. 12/607,673 filed Oct. 28, 2009, now U.S. Pat. No. 8,291,192 and relates to and claims priority rights from Japanese Patent Applications: 
     No. 2008-279210, filed on Oct. 30, 2008, 
     No. 2009-020810, filed on Jan. 30, 2009, 
     No. 2009-047280, filed on Feb. 27, 2009, and 
     No. 2009-047281, filed on Feb. 27, 2009, 
     the entire disclosures of which are hereby incorporated by reference herein. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to memory management systems. 
     2. Description of the Related Art 
     Some electronic apparatuses have memory devices such semiconductor memory or magnetic disc, and the electronic apparatuses are technically required to efficiently manage memories. A memory is allocated as a required area when necessary, and released after finishing using the memory to re-use it. Repeatedly performing such allocation and release of memories results in fragmentation, that is, a state where available memory areas separately exist in an address space, and consequently, a large continuous memory area can not be allocated even though the memory usage rate is still low. 
     In ordinary techniques, data processing apparatuses such as image forming apparatus use some memory management methods as follows in order to tend not to result in fragmentation and not to cause decline of throughput due to waiting for free area in a memory, transferring data within a memory and so on. In a method, if a page detection processing unit detects the beginning of a page, then a memory resource allocation unit allocates a memory; and then the memory is divided into partitions, and memory areas for input data and processed data are allocated in the partitions. While a data processing unit generates the processed data and stores it in a memory area for the processed data, the memory resource release unit releases unnecessary memory areas. The released unnecessary memory areas will be a part of free areas in the partition specified for the processed data. 
     In another method, to provide a host device capable of writing at high speed, a management system allocates unit blocks in a memory area in turn to obtain a writing area for storing writing data, and sets a management block as some natural number of the allocates unit blocks, and allocates the management block as the writing area for a writing function call with regard to a writing speed of the management block; and then a controller provides an instruction to a memory card to write data in the unit blocks allocated by the management system. 
     SUMMARY OF THE INVENTION 
     A memory management system according to an aspect of this invention has: a logical partition management unit that manages allocation and release of a virtual memory used by an application in a logical address space; a physical partition management unit that manages allocation and release of small size parts into which a physical memory is divided in a physical address space; and a converter unit that converts an address between the logical address space and the physical address space. 
     A memory management system according to an aspect of this invention has: a memory-control-block table management unit that has memory-control-block table, and manages memory allocation in a physical address space by using the memory-control-block table, the memory-control-block table having memory-control-blocks of which each indicates an allocation position of a physical memory; and a memory-control-block control table management unit that has a memory-control-block table control table which organizes the memory-control-blocks for each application, and manages memory allocation using the memory-control-block table control table for each application. 
     A memory management system according to an aspect of this invention has: a logical partition management unit that manages allocation and release of a virtual memory used by an application in a logical address space; a physical partition management unit that manages allocation and release of small-size physical partitions into which a physical memory is divided in a physical address space; and a converter unit that converts an address between the logical address space and the physical address space. The physical partition management unit watches fragmentation rates in the physical partitions, and prohibits physical memory allocation in the physical partition in which the fragmentation rate exceeds a predetermined upper-most threshold value. 
     A memory management system according to an aspect of this invention has: a logical partition management unit that manages allocation and release of a virtual memory used by an application in a logical address space; a physical partition management unit that manages allocation and release of small-size parts into which a physical memory is divided in a physical address space; and a converter unit that converts an address between the logical address space and the physical address space. The physical partition management unit identifies sizes of parts not in use out of the small-size parts, and searches the parts not in use for a part having a size specified in a memory allocation request and selects the part having the size for the memory allocation request. 
     These and other objects, features and advantages of the present invention will become more apparent upon reading of the following detailed description along with the accompanied drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  shows a diagram for explaining an instance of ordinary partitions, and  FIG. 1B  shows a diagram for explaining an instance of partitions according to Embodiment 1 of this invention; 
         FIGS. 2A and 2B  show memory allocation to the ordinary partitions; 
         FIGS. 3A and 3B  show memory allocation to the partitions according to Embodiment 1; 
         FIG. 4  shows a functional block diagram of a memory management system in Embodiment 1; 
         FIG. 5  shows an instance of a conversion table in Embodiment 1; 
         FIGS. 6A to 6C  show diagrams for explaining usage instances of micro-partitions in Embodiment 1; F 
         FIG. 7  shows an instance of allocating micro-partitions for a certain size in Embodiment 1; 
         FIG. 8  shows a diagram for explaining micro-partitions specified as fix areas in Embodiment 1; 
         FIG. 9A  shows a diagram which indicates an instance of an ordinary memory management system, and  FIG. 9B  shows a diagram which indicates an instance of a memory management system according to Embodiment 2 of this invention; 
         FIG. 10  shows a diagram which indicates a system configuration of the memory management system according to Embodiment 2 of this invention; 
         FIGS. 11A and 11B  show a diagram which indicates a software configuration in the memory management system according to Embodiment 2 of this invention; 
         FIG. 12  shows a diagram which indicates an instance of a table configuration for collective memory release in the memory management system according to Embodiment 2 of this invention; 
         FIGS. 13A and 13B  show a flowchart of memory allocation performed by the memory management system according to Embodiment 2 of this invention; 
         FIG. 14  shows a flowchart of memory release performed by the memory management system according to Embodiment 2 of this invention; 
         FIG. 15  shows a flowchart of collective memory release performed by the memory management system according to Embodiment 2 of this invention; 
         FIG. 16  shows a flowchart of releasing an MCB control table in the collective memory release according to Embodiment 2 of this invention; 
         FIG. 17  shows a diagram that indicates a configuration of tables for collective memory release in an ordinary memory management system; 
         FIG. 18  shows a flowchart of memory allocation performed by the ordinary memory management system; 
         FIG. 19  shows a flowchart of memory release performed by the ordinary memory management system; 
         FIG. 20  shows a flowchart of collective memory release performed by the ordinary memory management system; 
         FIG. 21  shows a flowchart of releasing an MCB in the collective memory release; 
         FIG. 22  shows a diagram which indicates a relationship between a memory map and physical partitions in the ordinary memory management system; 
         FIG. 23  shows a diagram which indicates a relationship between a memory map and physical partitions in Embodiment 3 (when stopping memory allocation); 
         FIG. 24  shows a diagram which indicates a relationship between a memory map and physical partitions in Embodiment 3 (when return to waiting for memory allocation); 
         FIG. 25  shows an instance of a conversion table in Embodiment 3; 
         FIG. 26  shows a flowchart of an initialization process in Embodiment 3; 
         FIG. 27  shows a flowchart of a memory allocation process in Embodiment 3; 
         FIG. 28  shows a flowchart of a memory release process in Embodiment 3; 
         FIG. 29  shows a flowchart of a collective memory release process in Embodiment 3; 
         FIG. 30  shows a diagram of a software configuration of a memory management system in Embodiment 3; 
         FIG. 31  shows a diagram which indicates a relationship between an application and a memory map in an ordinary memory pool method # 1 ; 
         FIG. 32  shows a diagram which indicates a relationship between an application and a memory map in an ordinary memory pool method # 2 ; 
         FIG. 33  shows a diagram which indicates a relationship between an application and a memory map in an ordinary memory pool method # 3 ; 
         FIG. 34  shows a diagram which indicates a relationship between a memory map and partitions in the ordinary memory pool method # 2 ; 
         FIG. 35  shows a diagram which indicates a relationship between a memory map and partitions in the ordinary memory pool method # 3 ; 
         FIG. 36  shows a diagram which indicates a memory map of partitions to be collectively released for an application; 
         FIG. 37  shows a diagram which indicates a memory map in a memory management method having an upper-most threshold value of fragmentation; 
         FIG. 38  shows a memory map which indicates linkage between areas not in use using MCBs; 
         FIG. 39  shows a memory map which indicates grouping areas not in use for each size of the areas in each partition in Embodiment 4; 
         FIG. 40  shows a diagram foe explaining memory allocation in an ordinary memory management system; 
         FIG. 41  shows a diagram which indicates that memory blocks not in use are linked through all partitions in a list structure; 
         FIG. 42  shows a diagram which indicates that physical partitions separately have respective list structures of memory blocks not in use; 
         FIG. 43  shows a diagram which indicates that memory blocks not in use are linked through all physical partitions in a list structure; 
         FIG. 44  shows a diagram which indicates that physical partitions separately have respective list structures of memory blocks not in use; 
         FIG. 45  shows an instance of a conversion table in case that memory blocks not in use are linked through all physical partitions in a list structure; 
         FIG. 46  shows an instance of a conversion table in case that physical partitions separately have respective list structures of memory blocks not in use; 
         FIG. 47  shows a diagram which indicates a relationship between a conversion table and MCBs; 
         FIG. 48  shows an instance of a memory map in a partition with allocation by BSD malloc; 
         FIG. 49  shows an instance of a memory map in a partition with list structures corresponding to respective allocation sizes of memory blocks not in use; 
         FIG. 50  shows an instance in which list structures are used corresponding to respective allocation sizes of memory blocks not in use; 
         FIG. 51  shows an instance of a conversion table in case that list structures are used corresponding to respective allocation sizes of memory blocks not in use; 
         FIG. 52  shows an instance of linkage in a conversion table in case that list structures are used corresponding to respective allocation sizes of memory blocks not in use; 
         FIG. 53  shows a diagram which indicates a relationship between a conversion table and MCBs; 
         FIGS. 54A to 54D  show diagrams for explaining memory release in case of one list structure of memory blocks not in use; 
         FIGS. 55A and 55B  show diagrams for explaining memory release in case of a plurality of list structures of memory blocks not in use; 
         FIG. 56  shows memory maps before and after memory allocation in case that a free area remains after the memory allocation; 
         FIG. 57  shows a flowchart of memory allocation in case that a free area remains after the memory allocation; 
         FIG. 58  shows memory maps before and after memory allocation in case that a free area does not remain after the memory allocation; 
         FIG. 59  shows a flowchart of memory allocation in case that a free area does not remain after the memory allocation; 
         FIG. 60  shows memory maps before and after memory release (in case that the adjacent previous memory block is not in use and the adjacent next memory block is in use); 
         FIG. 61  shows a flowchart of memory release (in case that the adjacent previous memory block is not in use and the adjacent next memory block is in use); 
         FIG. 62  shows memory maps before and after memory release (in case that the adjacent previous memory block is in use and the adjacent next memory block is not in use); 
         FIG. 63  shows a flowchart of memory release (in case that the adjacent previous memory block is in use and the adjacent next memory block is not in use); 
         FIG. 64  shows memory maps before and after memory release (in case that the adjacent previous memory block and the adjacent next memory block are not in use); 
         FIG. 65  shows a flowchart of memory release (in case that the adjacent previous memory block and the adjacent next memory block are not in use); 
         FIG. 66  shows memory maps before and after memory release (in case that the adjacent previous memory block and the adjacent next memory block are in use); and 
         FIG. 67  shows a flowchart of memory release (in case that the adjacent previous memory block and the adjacent next memory block are in use). 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Embodiment 1 
     Partition 
       FIG. 1A  shows a diagram for explaining physical memory allocation in an address space of an ordinary memory management system. The ordinary memory management system uses the address space as a single partition, and performs physical memory allocation (malloc( )) and release (free( )) by using memory management APIs (Application Program Interfaces) in the single partition. Under such memory management, repeatedly performing physical memory allocation and release results in fragmentation, that is, areas in use and areas not in use are separately positioned as shown in  FIG. 2A  to  FIG. 2B , and therefore, it is not possible to allocate a large continuous physical memory area without transferring data within the physical memory. It takes a lot of time to transfer data within the physical memory, and the physical memory is considerably limited to be used while transferring data, and thus this would be a large problem in an electronic apparatus such as image forming apparatus performing a real-time process. 
       FIG. 1B  shows a diagram for explaining allocation of a physical address space in case of the physical address space is divided into partitions according to Embodiment 1 of this invention. As shown in  FIG. 3A , a whole physical address space is divided into a plurality of partitions and each of the partition has an ID, and then partition is assigned to an application by associating the ID of the partition with the application. In  FIG. 3B , if a collective memory release with specifying ID=2 is performed for partitions with ID=2 (that is, free_all(ID=2) in  FIG. 1B  is executed) when the application with which ID=2 is associated ends, then a large continuous address space becomes available. 
     However, in the method dividing a physical memory space into partitions, if there is a large difference between an initially defined partition size and an actually used memory size, then physical memory available within a partition may not be enough to allocate a large continuous physical address space. 
     Therefore, in Embodiment 1 of this invention, this problem is solved by converting a logical address space required by an application into a physical address space of micro-partitions into which a physical memory space is divided. 
     [Configuration] 
       FIG. 4  shows a functional block diagram of a memory management system of Embodiment 1. 
     A memory management unit M 10  has functional units: a physical partition management unit M 17 , a converter unit M 19 , and a logical partition management unit M 21 . 
     The functional units access a physical micro-partition M 11  in a physical address space, generate and delete a conversion table M 13  between the physical address space and a logical address space, and access logical partitions M 15  in the logical address space. 
     Below explained are operations of the functional units. 
     The logical partition management unit M 21  manages allocation of a virtual memory to be used by an application in a logical address space, and manages partitions (i.e. the logical partition M 15 ) into which the allocated virtual memory is divided. Each of the logical partitions has continuous logical addresses for an application. 
     The converter unit M 19  performs address conversion between the logical address space and the physical address space. In the address conversion, used is the conversion table M 13  in which a logical address in the logical address space and a physical address in the physical address space are associated with each other (detailed is mentioned below). Specifically, the converter unit M 19  obtains areas not in use in the virtual memory and the physical memory from the logical partition management unit M 19  and the physical partition management unit M 17 , respectively, and associates the physical address space with the logical address space. The converter unit M 19  generates and deletes a conversion table M 13  according to memory usage status of an application. Specifically, the converter unit M 19  generates a conversion table M 13  according to a request due to startup or an operation of an application, and deletes the conversion table M 13  according to the end of the application. 
     The physical partition management unit M 17  manages allocation and release of a physical memory based on physical micro-partitions M 11  into which the physical memory is divided in the physical address space. 
     [Conversion Table and Micro-Partition] 
     In the following part, the conversion table is explained with reference to  FIG. 5 . As shown in a conversion table T 01 , a physical address space is divided into micro-partitions, and each of the micro-partitions has a size of 0x0800 (this size is an instance, can be another size). Each of the micro-partitions has an ID, a physical address, and a logical address corresponding to the physical address. The ID in a micro-partition indicates an application which uses the micro-partition. 
     For instance, regarding micro-partitions used by an application of ID=2, the first micro-partition is a micro-partition which has the micro-partition number of 1 among micro-partitions of ID=2 as shown in a conversion table T 11 . The pointer to the linked table in the conversion table T 11  specifies the next conversion table T 31  of a micro-partition which has the micro-partition number of 3. The pointer to the linked table in the conversion table T 31  specifies the next conversion table T 61  of a micro-partition which has the micro-partition number of 6. 
     As mentioned above, the converter unit M 19  is capable of converting physical addresses separately allocated in a physical address space by the physical partition management unit M 17  to continuous logical addresses. Further, the logical partition management unit M 15  is capable of allocating the continuous logical addresses obtained from the converter unit M 19  to the virtual memory space to be used by an application. 
       FIG. 6A  shows an instance of collective physical memory release corresponding to a specified an ID. In this case, the micro-partition # 2  has been exclusively used for a graphic application, but since the graphic application ends, a physical memory of the micro-partition # 2  becomes unnecessary. Thus, the physical partition management unit M 17  performs collective memory release with specifying the ID=Graphics (i.e. the ID of the graphic application). Tracing the pointers to the linked tables and identifying positions of physical memory areas from the conversion tables such as the conversion tables T 11  to T 61 , all of the physical memories that has been allocated of ID=Graphics are released together. Consequently, the micro-partitions are released. The released micro-partitions are available for another application. 
       FIG. 6B  shows an instance of re-allocation of a physical memory partition which has been allocated. If a physical memory space originally allocated by the physical partition management unit M 17  runs short, then the micro-partition # 5  not in use is newly allocated of ID=Graphics. In this case, the physical address spaces are separately positioned, but the logical address space is still continuous. Consequently, the micro-partition is added. 
       FIG. 6C  shows an instance of allocation of a plurality of new micro-partitions. If an address space required for allocation is greater than the size of one micro-partition, then pluralities of micro-partitions (e.g. three micro-partitions # 3  to # 5  in  FIG. 6C ) can be allocated. Consequently, it is possible to allocate a memory larger than the size of one micro-partition. 
     Referring to  FIG. 7 , it will be explained that a continuous logical address space is obtained even if areas of micro-partitions in a physical address space are separately positioned. In  FIG. 7 , for instance, physical memories used by the application of ID=Interpreter are separately positioned in the micro-partitions # 1 , # 6  and # 9 . However, since the converter unit M 19  performs address conversion between physical addresses and logical addresses using the conversion table M 13 , the logical partition management unit M 21  can access a continuous memory space with the logical addresses. The same memory management is performed for applications of ID=Graphics and ID=Rendering. 
     A logical partition is a collective body of physical micro-partitions having a same ID. A logical partition of the application “Interpreter” consists of three physical micro-partitions. A logical partition of the application “Graphics” consists of four physical micro-partitions. A logical partition of the application “Rendering” consists of two physical micro-partitions. The size of a logical partition (i.e. a collective body of physical micro-partitions) can be changed dynamically. 
     Referring to  FIG. 8  as an instance, allocating micro-partitions to fixed memory areas will be explained. Some hardware such as DMA (Direct Memory Access) directly accesses an address space of a physical memory. This memory management system works well even if the hardware accesses fixed addresses. The converter unit M 19  sets the ID of a micro-partition in the conversion table M 13  as a value indicating that this micro-partition is fixed by hardware. The micro-partition with the ID of such value is a fixed area, and thus, the physical partition management unit M 17  does not use such micro-partition (i.e. fixed area) for allocation even if a memory allocation request is received from the physical partition management unit M 21 . As shown in  FIG. 8 , even if memory allocation requests are received from the physical partition management unit M 21  for the applications “Interpreter”, “Graphics” and “Rendering”, physical addresses of micro-partitions are allocated other than the fixed micro-partitions having the ID of such value. Therefore, the micro-partitions used for the applications do not compete with the micro-partitions fixed by hardware. 
     “Fixed by hardware” means requirement for fixing physical addresses to be used by specific hardware such as DMA transfer. Logical partitions (for the Interpreter, the Graphics and the Rendering) are allocated (mapped) to areas other than areas fixed by hardware. 
     [Advantages of Embodiment 1] 
     Advantages of the memory management system of Embodiment 1 are as follows. 
     It is possible to avoid fragmentation effectively. 
     Multiple partitions and dynamic movement of boundaries of partitions are used to avoid fragmentation effectively. 
     The order of releasing memories is not limited, and a memory which becomes unnecessary can be released immediately. 
     Embodiment 2 
       FIG. 9A  shows a diagram for explaining memory allocation in an address space of an ordinary memory management system. The ordinary memory management system uses the address space as a single partition, and performs memory allocation (malloc( )) and release (free( )) by using memory management APIs (Application Program Interfaces) in the single partition. Under such memory management, repeatedly performing memory allocation and release results in fragmentation, that is, areas in use and areas not in use are separately positioned as shown in  FIG. 17 , and therefore, it is not possible to allocate a large continuous memory area without transferring data within the memory. However, it takes a lot of time to transfer data within the memory, and the memory is considerably limited to be used while transferring data, and thus this would be a large problem in an electronic apparatus such as image forming apparatus performing a real-time process. 
       FIG. 9B  shows a diagram for explaining a memory management system of Embodiment 2. This invention realizes a new specific memory management system capable of collective memory release. In this memory management system, specific functions of “user_malloc( )”, “user_free( )” and “user_free_all( )” have been defined, and the specific functions call and use the predefined functions malloc( ) and free( ) according to a specific algorithm of the memory management system. In this invention, a whole physical address space is divided into a plurality of partitions and each of the partition has an ID, and then partition is assigned to an application by associating the ID of the partition with the application. In  FIG. 12 , if a collective memory release with specifying ID=2 is performed for partitions with ID=2 (that is, user_free_all(ID=2) in  FIG. 9B  is executed) when the application with which ID=2 is associated ends, then a large continuous address space becomes available. 
     [Configuration] 
     Referring to  FIG. 10 , a role of the memory management system in a whole program of Embodiment 2 will be explained. 
     An application calls and uses the APIs “user_malloc( )”, “user_free( )” and “user_free_all( )” to handle dynamic memory area in this memory management system. When the APIs are called, the memory management system manages a memory by using a management table for MCB (Memory Control Block) control tables in a static memory area, and an MCB control table and an MCB block table in a dynamic memory area. The memory management system calls system APIs of memory allocation and release, that is, malloc( ) and free( ) to perform memory allocation and release using the ordinary memory management system. 
       FIGS. 11A and 11B  show a diagram which indicates a software configuration in the memory management system according to Embodiment 2. The memory management system has API functions P 11 , a management program P 13  for the management table for MCB control tables, a management program P 15  for an MCB control table (i.e. memory-control-block control table management unit), and a management program P 17  for an MCB table (i.e. memory-control-block table management unit). 
     The API functions P 11  receive requests of memory allocation, release, and collective release for an application program. In general, a programmer writes system functions such as malloc( ) and free( ) in his/her application program to realize memory management. On the other hand, in this memory management system, since the specific API functions (user_malloc( ), user_free( ) and user_free_all( )) are used for memory management of each application, especially user_free_all( ) is used for collective memory release, programmer&#39;s burden is reduced. 
     The management program P 13  performs conversion between physical memory addresses in a physical memory address space allocated with MCBs (in a dynamic memory area) and logical memory addresses in a logical memory address (in a static memory area). Further, the management program P 13  manages a pointer to the first MCB control block (mentioned below) and a pointer to the last MCB control block (mentioned below). 
     Using an MCB control table which organizes MCB tables for respective applications, the management program P 15  (i.e. the memory-control-block control table management unit) manages memory allocation of a physical memory managed by the memory-control-block table management unit for each application. 
     Using an MCB table which indicates allocation positions of physical memories, the management program P 17  (i.e. the memory-control-block table management unit) manages memory allocation in a physical address space. 
     [MCB Table and MCB Control Table] 
     Referring  FIG. 17 , an ordinary MCB table will be explained. As shown in  FIG. 17 , a memory area for an application contains areas specified by respective memory control blocks in the MCB table. A memory control block has an identification ID that indicates the application which requests allocation, but all of memory control blocks are managed with the MCB control table. Therefore, each of all blocks in the MCB table must be checked in order to perform memory management for each application (e.g. for collective memory release when an application ends). 
     A configuration of the MCB table in the memory management system of Embodiment 2 is shown in  FIG. 12 . Each memory block in the MCB table refers to a memory area for an application, and the MCB control table refers to memory blocks in the MCB table corresponding to an application. A block (i.e. an MCB control table) among the MCB control tables is used to manage a memory area allocated by an application, and the block has a pointer to the first MCB. Each MCB has a pointer to the next MCB allocated by the same application, and consequently the MCBs concatenated by the pointer forms a list structure. Therefore, for collective memory release, a block (i.e. an MCB control table) used by an application are identified among the MCB control tables, and then the MCBs for the application are identified from the identified block, and memory areas used by the application are identified from the identified MCBs. By tracing the list structure, finally the last MCB can be found, and thus, it is possible to easily perform collective memory release. 
     [Operations of the Ordinary Memory Management System—Flowcharts] 
     Memory operations of the ordinary memory management system will be explained with reference to flowcharts shown in  FIGS. 18 to 21 . 
     Referring to  FIG. 18 , ordinary memory allocation is explained. 
     Step S 101 : A memory for an application is allocated. 
     Step S 103 : It is determined whether or not the memory allocation is successful. If the memory allocation is successful, then Step S 105  is next executed. If the memory allocation is not successful, then Step S 111  is next executed. 
     Step S 105 : An MCB is allocated for the memory allocated in Step S 101 . 
     Step S 107 : It is determined whether or not the allocation of the MCB is successful. If the allocation is successful, then a new MCB is added into the MCB table, and Step S 113  is next executed. If the allocation is not successful, then Step S 109  is next executed.
 
Step S 109 : Since the allocation of the MCB is not successful, the memory allocated in Step S 101  for the application is released.
 
Step S 111 : Since the memory allocation is failed, this process ends.
 
Step S 113 : A pointer to the first MCB is obtained from the management table for MCBs.
 
Step S 115 : It is determined whether or not the pointer to the first MCB is valid. If the pointer to the first MCB is valid, then Step S 121  is next executed. If the pointer to the first MCB is not valid (i.e. there were not MCBs before the allocation in Step S 101 ), then Step S 117  is next executed.
 
Step S 117 : The pointer to the first MCB is updated in the management table for MCBs, with the pointer to the MCB allocated in Step S 105 .
 
Step S 119 : A pointer to the last MCB is updated in the management table for MCBs, with the pointer to the MCB allocated in Step S 105 .
 
Step S 121 : A pointer to the last MCB is obtained from the management table for MCBs.
 
Step S 123 : A pointer to the next MCB is updated in the last MCB in the MCB table, with the pointer to the MCB allocated in Step S 105 .
 
Step S 125 : The pointer to the last MCB is updated in the management table for MCBs, with the pointer to the MCB allocated in Step S 105 .
 
Step S 127 : An identification ID is set in the allocated MCB, with the ID of the application.
 
Step S 129 : A memory head address and a memory size are set in the allocated MCB, with the head address and the size of the memory allocated in Step S 101 .
 
Step S 131 : A pointer to the next MCB is set as invalid in the allocated MCB, since the allocated MCB is added as the last MCB.
 
Step S 133 : Memory allocation is succeeded.
 
     By a series of the aforementioned operations in the ordinary method, a memory area for an application is allocated. 
     Next, referring to  FIG. 19 , ordinary memory release is explained. 
     Step S 201 : A pointer to the first MCB is obtained from the management table for MCBs. 
     Step S 203 : A pointer to the last MCB is obtained from the management table for MCBs. 
     Step S 205 : A memory head address and a memory size are obtained from the current MCB. At the first, the current MCB is the first MCB. 
     Step S 207 : It is determined whether or not the head address is the same as the address of the release target. If the head address is the same as the address of the release target, then Step S 215  is next executed. If the head address is not the same as the address of the release target, then Step S 209  is next executed.
 
Step S 209 : A pointer to the next MCB is obtained from the current MCB.
 
Step S 211 : It is determined whether or not the pointer to the next MCB is valid. If the pointer to the next MCB is valid (i.e. if the next MCB exists), then Step S 205  is next executed, and in and after Step S 205  the next MCB is processed as the current MCB. If the pointer to the next MCB is not valid (i.e. if the next MCB does not exist), then Step S 213  is next executed.
 
Step S 213 : Since the memory release is failed, this process ends.
 
Step S 215 : It is determined whether or not the release target is the first MCB. If the release target is the first MCB, then Step S 217  is next executed. If the release target is not the first MCB, then Step S 233  is next executed.
 
Step S 217 : The pointer to the next MCB is obtained from the current MCB (i.e. the first MCB).
 
Step S 219 : A memory for an application is released. This memory is identified from the first MCB.
 
Step S 221 : The current MCB (i.e. the first MCB) is released from the memory.
 
Step S 223 : It is determined whether or not the pointer to the next MCB is valid. If the pointer to the next MCB is valid (i.e. if the next MCB exists), then Step S 225  is next executed. If the pointer to the next MCB is not valid (if the next MCB does not exist), then Step S 227  is next executed.
 
Step S 225 : The pointer to the first MCB is updated in the management table for MCBs, with the pointer obtained in Step S 217 .
 
Step S 227 : The pointer to the first MCB is set as invalid in the management table for MCBs, since there are no MCBs.
 
Step S 229 : The pointer to the last MCB is set as invalid in the management table for MCBs, since there are no MCBs.
 
Step S 231 : Since the memory release is succeeded, this process ends.
 
Step S 233 : It is determined whether or not the release target is an MCB in the middle of the MCB table. If the release target is an MCB in the middle of the MCB table (i.e. if the release target is neither the last MCB nor the first MCB), then Step S 235  is next executed. If the release target is not MCBs in the middle of the MCB table, that is, if the release target is the last MCB, then Step S 243  is next executed.
 
Step S 235 : A pointer to the next MCB is obtained from the current MCB.
 
Step S 237 : The obtained pointer is set to a pointer to the next MCB in the previous MCB.
 
Step S 239 : A memory for an application is released. This memory is identified from the current MCB.
 
Step S 241 : The current MCB is released from the memory. After Step S 241 , through Step S 231 , then this process ends.
 
Step S 243 : A pointer to the next MCB is set as invalid in the previous MCB of the current MCB, since the previous MCB will be the last MCB after the release.
 
Step S 245 : The pointer to the last MCB is updated in the management table for MCBs, with the pointer to the previous MCB.
 
Step S 247 : A memory area for an application is released. This memory is identified from the current MCB.
 
Step S 249 : The current MCB is released from the memory. After Step S 249 , through Step S 231 , then this process ends.
 
     By a series of the aforementioned operations in the ordinary method, a memory area for an application is released. 
     Next, referring to  FIG. 20 , ordinary collective memory release is explained. 
     Step S 301 : A pointer to the first MCB is obtained from the management table for MCBs. 
     Step S 303 : It is determined whether or not the pointer to the first MCB is valid. If the pointer to the next MCB is valid (i.e. if at least one MCB exists), then Step S 305  is next executed. If the pointer to the next MCB is not valid, then this process ends.
 
Step S 305 : A pointer to the next MCB is obtained from the current MCB. At the first, the current MCB is the first MCB.
 
Step S 307 : It is determined whether or not the identification ID in the current MCB is the same as the release target&#39;s ID. If the identification ID in the current MCB is the same as the release target&#39;s ID, then Step S 311  is next executed. If the identification ID in the current MCB is not the same as the release target&#39;s ID, then Step S 309  is next executed.
 
Step S 309 : It is determined whether or not the pointer to the next MCB is valid. If the pointer to the next MCB is valid, then Step S 305  is next executed, and in and after Step S 305  the next MCB is processed as the current MCB. If the pointer to the next MCB is not valid, then this process ends.
 
Step S 311 : A memory for an application is released. This memory is identified from the current MCB.
 
Step S 313 : The current MCB is released from the memory (see  FIG. 21 ). Next to Step S 313 , Step S 309  is executed.
 
     By a series of the aforementioned operations in the ordinary method, all memory areas for an application are released together. 
     Next, referring to  FIG. 21 , releasing an MCB in the collective memory release is explained. 
     Step S 401 : A pointer to the first MCB is obtained from the management table for MCBs. 
     Step S 403 : It is determined whether or not the release target is the first MCB. If the release target is the first MCB, then Step S 405  is next executed. If the release target is not the first MCB, then Step S 417  is next executed. 
     Step S 405 : A pointer to the next MCB is obtained from the first MCB. 
     Step S 407 : It is determined whether or not the pointer to the next MCB is valid. If the pointer to the next MCB is valid, then Step S 413  is next executed. If the pointer to the next MCB is not valid, then Step S 409  is next executed. 
     Step S 409 : The pointer to the first MCB is set as invalid in the management table for MCBs, since there will be no MCBs after the release. 
     Step S 411 : The pointer to the last MCB is set as invalid in the management table for MCBs, since there will be no MCBs after the release. 
     Step S 413 : The pointer to the first MCB is updated in the management table for MCBs, with the pointer obtained in Step S 405 . 
     Step S 415 : The MCB as the release target is released, and then this process ends. 
     Step S 417 : It is determined whether or not the release target is the last MCB. If the release target is the last MCB, then Step S 423  is next executed. If the release target is not the last MCB, then Step S 419  is next executed. 
     Step S 419 : A pointer to the next MCB is obtained from the MCB as the release target. 
     Step S 421 : The obtained pointer is set to a pointer to the next MCB in the previous MCB of the release target. Next to Step S 421 , Step S 415  is executed, then this process ends. 
     Step S 423 : A pointer to the next MCB is set as invalid in the previous MCB of the release target, since the previous MCB will be the last MCB after the release. 
     Step S 425 : The pointer to the last MCB is updated in the management table for MCBs, with the pointer to the previous MCB. Next to Step S 425 , Step S 415  is executed, and then this process ends. 
     By a series of the aforementioned operations in the ordinary method, an MCB in collective memory release are released. 
     [Operations of the Memory Management System of Embodiment 2—Flowcharts] 
     Referring to  FIGS. 13A and 13B , a memory allocation process in Embodiment 2 will be explained. 
     Step S 501 : A memory for an application is allocated. 
     Step S 503 : It is determined whether or not the memory allocation in Step S 501  is successful. If the memory allocation is successful, then Step S 507  is next executed. If the memory allocation is not successful, then Step S 505  is next executed. 
     Step S 505 : Since the memory allocation is failed, this process ends. 
     Step S 507 : An MCB is allocated to manage the memory allocated in Step S 501 . 
     Step S 509 : It is determined whether or not the memory allocation in Step S 507  is successful. If the memory allocation is successful, then Step S 513  is next executed. If the memory allocation is not successful, then Step S 511  is next executed. 
     Step S 511 : The memory allocated in Step S 501  for an application is released. Next to Step S 511 , through Step S 505 , then this process ends. 
     Step S 513 : The ID specified in this allocation request is compared with IDs in the MCB control tables. 
     Step S 515 : According to the result of Step S 513 , it is determined whether or not the ID specified in this allocation request is the same as any of IDs in the MCB control tables. If the ID specified in this allocation request is the same as any of the IDs, then Step S 557  (in  FIG. 13B ) is next executed. If the ID specified in this allocation request is not the same as any of the IDs, then Step S 517  is next executed.
 
Step S 517 : A new MCB control table is allocated to manage MCBs having the specified ID.
 
Step S 519 : It is determined whether or not the memory allocation in Step S 517  is successful. If the memory allocation is successful, then Step S 525  is next executed. If the memory allocation is not successful, then Step S 521  is next executed.
 
Step S 521 : The memory allocated in Step S 501  for an application is released.
 
Step S 523 : The MCB allocated in Step S 507  is released from the memory. Next to Step S 523 , through Step S 505 , then since the memory allocation is failed, this process ends.
 
Step S 525 : A pointer to the first MCB control table is obtained from the management table for MCB control tables.
 
Step S 527 : It is determined whether or not the pointer to the first MCB control table is valid. If the pointer to the first MCB control table is valid, then Step S 549  is next executed. If the pointer to the first MCB control table is not valid (i.e. if there are no MCB control tables), then Step S 529  is next executed.
 
Step S 529 : The pointer to the first MCB control table is updated in the management table for MCB control tables, with the pointer to the MCB control table allocated in Step S 517 .
 
Step S 531 : The pointer to the last MCB control table is updated in the management table for MCB control tables, with the pointer to the MCB control table allocated in Step S 517 .
 
Step S 533 : A pointer to the previous MCB control table is set as invalid in the new MCB control table allocated in Step S 517 .
 
Step S 535 : A pointer to the first MCB is set in the new MCB control table, with the pointer to the MCB allocated in Step S 507 .
 
Step S 537 : An identification ID is set in the new MCB control table, with the ID specified in the allocation request.
 
Step S 539 : A pointer to the next MCB control table is set as invalid in the new MCB control table, since the new MCB control table is added as the last table in the list of MCB control tables.
 
Step S 541 : A pointer to the last MCB is set as the pointer to the MCB allocated in Step S 507 , in either the new MCB control table allocated in Step S 517  or the existent MCB control table having the same ID as that specified in the allocation request.
 
Step S 543 : A memory head address and a memory size are set in the allocated MCB.
 
Step S 545 : A pointer to the next MCB is set as invalid in the allocated MCB, since the allocated MCB is the last MCB.
 
Step S 547 : Since the memory allocation is succeeded, this process ends.
 
Step S 549 : A pointer to the last MCB control table is obtained from the management table for MCB control tables.
 
Step S 551 : A pointer to the next MCB control table is updated in the last MCB control table, with the pointer to the MCB control table allocated in Step S 517 .
 
Step S 553 : A pointer to the last MCB control table is updated in the management table for MCB control tables, with the pointer to the MCB control table allocated in Step S 517 .
 
Step S 555 : A pointer to the previous MCB control table is set in the last MCB control table, with the pointer obtained in Step S 549 . Next to Step S 555 , Step S 535  is executed.
 
Step S 557 : A pointer to the last MCB is obtained from the MCB control table which has the same ID as the ID specified in this allocation request.
 
Step S 559 : A pointer to the next MCB is updated in the last MCB, with the pointer to the MCB allocated in Step S 507 . Next to Step S 559 , Step S 541  is executed.
 
     By a series of the aforementioned operations in this embodiment, a process for allocating a memory area for an application is performed. 
     Next, referring  FIG. 14 , a memory release process in Embodiment 2 is explained. 
     Step S 601 : A pointer to the first MCB control table is obtained from the management table for MCB control tables. 
     Step S 603 : A pointer to the first MCB is obtained from the current MCB control table. At the first, the current MCB control table is the first MCB control table. 
     Step S 605 : A pointer to the last MCB is obtained from the current MCB control table. 
     Step S 607 : A memory head address and a memory size are obtained from the current MCB. At the first, the current MCB is the first MCB. 
     Step S 609 : It is determined whether or not the head address is the same as the address of the release target. If the head address is the same as the address of the release target, then Step S 621  is next executed. If the head address is not the same as the address of the release target, then Step S 623  is next executed.
 
Step S 611 : A pointer to the next MCB is obtained from the current MCB.
 
Step S 613 : It is determined whether or not the pointer to the next MCB is valid. If the pointer to the next MCB is valid, then Step S 607  is next executed, and in and after Step S 607  the next MCB is processed as the current MCB. If the pointer to the next MCB is not valid, then Step S 615  is next executed.
 
Step S 615 : A pointer to the next MCB control table is obtained from the current MCB control table.
 
Step S 617 : It is determined whether or not the pointer to the next MCB control table is valid. If the pointer to the next MCB control table is valid, then Step S 603  is next executed, and in and after Step S 603  the next MCB control table is processed as the current MCB control table. If the pointer to the next MCB control table is not valid, then Step S 619  is next executed.
 
Step S 619 : Since the memory release is failed, this process ends.
 
Step S 621 : It is determined whether or not the release target is the first MCB. If the release target is the first MCB, then Step S 623  is next executed. If the release target is not the first MCB, then Step S 637  is next executed.
 
Step S 623 : A pointer to the next MCB is obtained from the current MCB (i.e. the first MCB).
 
Step S 625 : A memory for an application is released. This memory is identified from the current MCB.
 
Step S 627 : The first MCB is released from the memory (see  FIG. 21 ).
 
Step S 629 : It is determined whether or not the pointer to the next MCB (i.e. the pointer obtained in Step S 623 ) is valid. If the pointer to the next MCB is valid, then Step S 631  is next executed. If the pointer to the next MCB is not valid, then Step S 635  is next executed.
 
Step S 631 : The pointer to the first MCB is updated in the current MCB control table, with the pointer obtained in Step S 623 .
 
Step S 633 : Since the memory release is succeeded, this process ends.
 
Step S 635 : The current MCB control table is released from the memory (see  FIG. 16 ), since due to the release there will be no MCBs to be managed with the current MCB control table. Next to Step S 635 , through Step S 633 , since the memory release is succeeded, this process ends.
 
Step S 637 : It is determined whether or not the release target is an MCB in the middle of the MCB table. If the release target is an MCB in the middle of the MCB table (i.e. if the release target is neither the last MCB nor the first MCB), then Step S 639  is next executed. If the release target is not MCBs in the middle of the MCB table, that is, if the release target is the last MCB, then Step S 647  is next executed.
 
Step S 639 : A pointer to the next MCB is obtained from the current MCB.
 
Step S 641 : The obtained pointer is set to a pointer to the next MCB in the previous MCB of the release target.
 
Step S 643 : A memory for an application is released. This memory is identified from the current MCB.
 
Step S 645 : The current MCB is released from the memory (see  FIG. 21 ). Next to Step S 645 , through Step S 633 , since the memory release is succeeded, this process ends.
 
Step S 647 : A pointer to the next MCB is set as invalid in the previous MCB of the release target, since the previous MCB will be the last MCB after the release.
 
Step S 649 : A pointer to the last MCB is updated in the current MCB control table, with the pointer to the previous MCB.
 
Step S 651 : A memory for an application is released. This memory is identified from the current MCB.
 
Step S 653 : The current MCB is released from the memory (see  FIG. 21 ). Next to Step S 653 , through Step S 633 , since the memory release is succeeded, this process ends.
 
     By a series of the aforementioned operations in Embodiment 2, a memory area for an application is released. 
     Referring to  FIG. 15 , a collective memory release process in Embodiment 2 will be explained. 
     Step S 701 : A pointer to the first MCB control table is obtained from the management table for MCB control tables. 
     Step S 703 : It is determined whether or not the pointer to the first MCB control table is valid. If the pointer to the first MCB control table is valid (i.e. if at least one MCB control table exists), then Step S 705  is next executed. If the pointer to the first MCB control table is not valid, then this process ends.
 
Step S 705 : It is determined whether or not the ID specified in the collective memory release request is the same as the ID of the current MCB control table. At the first, the current MCB control table is the first MCB control table. If the specified ID is the same as the ID of the current MCB control table, then Step S 707  is next executed. If the specified ID is not the same as the ID of the current MCB control table, then Step S 719  is next executed.
 
Step S 707 : A pointer to the first MCB is obtained from the current MCB control table.
 
Step S 709 : A pointer to the next MCB is obtained from the current MCB. At the first, the current MCB is the first MCB.
 
Step S 711 : A memory area for the application is released. This memory is identified from the current MCB.
 
Step S 713 : The current MCB is released from the memory (see  FIG. 21 ).
 
Step S 715 : It is determined whether or not the pointer to the next MCB (i.e. the pointer obtained in Step S 707 ) is valid. If the pointer to the next MCB is valid, then Step S 709  is next executed, and in and after Step S 709  the next MCB is processed as the current MCB. If the pointer to the next MCB is not valid, then Step S 717  is next executed.
 
Step S 717 : The current MCB control table is released from the memory (see  FIG. 16 ).
 
Step S 719 : A pointer to the next MCB control table is obtained from the current MCB control table.
 
Step S 721 : It is determined whether or not the pointer to the next MCB control table is valid. If the pointer to the next MCB control table is valid, then Step S 705  is next executed, in and after Step S 705  the next MCB control table is processed as the current MCB control table. If the pointer to the next MCB control table is not valid, then this process ends.
 
     By a series of the aforementioned operations in Embodiment 2, all memory areas for an application are released together. 
     Next, referring to  FIG. 16 , releasing an MCB control table in the collective memory release of Embodiment 2 is explained. 
     Step S 801 : A pointer to the first MCB control table is obtained from the management table for MCB control tables. 
     Step S 803 : A pointer to the last MCB control table is obtained from the management table for MCB control tables. 
     Step S 805 : It is determined whether or not the release target is the first MCB control table. If the release target is the first MCB control table, then Step S 807  is next executed. If the release target is not the first MCB control table, then Step S 821  is next executed.
 
Step S 807 : A pointer to the next MCB control table is obtained from the first MCB control table.
 
Step S 809 : It is determined whether or not the pointer to the next MCB control table is valid. If the pointer to the next MCB control table is valid, then Step S 817  is next executed. If the pointer to the next MCB control table is not valid (i.e. if only one MCB control table exists), then Step S 811  is next executed.
 
Step S 811 : The pointer to the first MCB control table is set as invalid in the management table for MCB control tables, since there will be no MCB control table after the release.
 
Step S 813 : The pointer to the last MCB control table is set as invalid in the management table for MCB control tables, since there will be no MCB control table after the release.
 
Step S 815 : The MCB control table as the release target is released from the memory, and then this process ends.
 
Step S 817 : The pointer to the first MCB control table is updated in the management table for MCB control tables, with the pointer obtained in Step S 807 .
 
Step S 819 : A pointer to the previous MCB control table is set as invalid in the next MCB control table of the first MCB control table, since the next MCB control table will be the first MCB control table after the release. Next to Step S 819 , in Step S 815 , the first MCB control table is released, and then this process ends.
 
Step S 821 : It is determined whether or not the release target is the last MCB control table. If the release target is the last MCB control table, then Step S 831  is next executed. If the release target is not the last MCB control table, then Step S 823  is next executed.
 
Step S 823 : A pointer to the next MCB control table is obtained from the MCB control table as the release target.
 
Step S 825 : A pointer to the previous MCB control table is obtained from the current MCB control table as the release target.
 
Step S 827 : The pointer obtained in Step S 823  is set to a pointer to the next MCB control table in the previous MCB control table of the release target.
 
Step S 829 : The pointer obtained in Step S 825  is set to a pointer to the previous MCB control table in the next MCB control table of the release target. Next to Step S 829 , in Step S 815 , the MCB control table as the release target is released, and then this process ends.
 
Step S 831 : A pointer to the previous MCB control table is obtained from the last MCB control table.
 
Step S 833 : A pointer to the next MCB control table is set as invalid in the previous MCB control table of the last MCB control table.
 
Step S 835 : A pointer to the last MCB control table is updated in the management table for MCB control tables, with the pointer to the previous MCB control table. Next to Step S 835 , in Step S 815 , the last MCB control table is released, and then this process ends.
 
     By a series of the aforementioned operations in Embodiment 2, an MCB in collective memory release are released. 
     [Advantages of Embodiment 2] 
     The memory management system of Embodiment 2 manages MCBs for each application by using the MCB table and the MCB control tables in two layers. 
     Therefore, memory spaces are allocated and released for each of applications, and consequently, fragmentation tends not to occur and it is possible to allocate a large continuous memory space. 
     Further, the memory management system has application program interfaces for memory management. The memory-control-block table management unit and the memory-control-block control table management unit perform memory management for each of applications. If an application program calls the application program interfaces, then the memory-control-block table management unit and the memory-control-block control table management unit perform memory management for each application. Therefore, a programmer is not required to write complex memory operations in his/her application program, and the programmer&#39;s burden is reduced. 
     Further, in the memory management system of Embodiment 2, one MCB table consists of a concatenation list in which memory control blocks only for one application are concatenated. In terms of such simple concatenate list structure, the system can reach the allocated memory areas in a short time. For example, the collective memory release is performed as simple procedures in a short time. Specifically, by calling user_free_all( ) with an ID of an application as a parameter when an instance of the application ends, all memory areas that have been used by the application are released at one time. 
     Embodiment 3 
     A configuration of a memory management system according to Embodiment 3 is the same as that of Embodiment 1 (in  FIG. 4 ). 
     In Embodiment 3, the physical partition management unit M 17  manages allocation and release of a physical memory based on physical micro-partitions M 11  into which the physical memory is divided in the physical address space. Further, the physical partition management unit M 17  watches fragmentation rates in respectives of the physical partitions, and prohibits physical memory allocation in the physical partition in which the fragmentation rate exceeds a predetermined upper-most threshold value. Further, the physical partition management unit M 17  allows physical memory allocation again in the physical partition for which physical memory allocation has been prohibited, if the fragmentation rate of the physical partition becomes less than a predetermined lower-most threshold value. Typically, the upper-most threshold value and the lower-most threshold value may be, for instance, 70 percent and 30 percent, respectively. Alternatively, the upper-most threshold value may be 99 percent, that is, a value near the maximum value. 
     Here, the fragmentation rate is derived according to the following expression.
 
Fragmentation rate (%)={[Number of fragments]/[Number of micro-partitions]−1)×100
 
     By this method that prohibits allocation in the physical partition using the upper-most threshold value, even if memory allocation is required when the fragmentation rate is equal to or greater than the upper-most threshold value, the required memory is allocated in another physical partition. 
     [Software Configuration] 
     Referring  FIG. 30 , a software configuration of the memory management system of Embodiment 3 will be explained. 
     This memory management system has a memory management initializer unit  200 , a conversion table management unit  201 , an address converter unit  221 , a memory statistic information management unit  241 , and an MCB management unit  261 . In the following part, these functional blocks are explained. 
     The memory management initializer unit  200  performs operations necessary for initialization of memory management. In the initialization, the unit  200  sets a memory area to be managed, a physical address space, a logical address space, fixed address spaces, etc. 
     The conversion table management unit  201  (an instance of the logical partition management unit and the physical partition management unit) manages allocation and release of micro-partitions into which a physical memory is divided in the physical address space. Further, the conversion table management unit  201  manages allocation and release of a virtual memory to be used by an application in a logical memory space. The conversion table management unit  201  contains some function units such as a partition management unit  211 , a partition-size management unit  213 , an address management unit  215 , an ID management unit  217 , and a flag management unit  219 . 
     The partition management unit  211  manages allocation and release of micro-partitions into which the aforementioned physical address space is divided. The partition management unit  211  manages information on the partitions by using a list structure. 
     The partition-size management unit  213  manages sizes of the partitions. The unit  213  reads-in partition size definition information  214  in its initialization. 
     The address management unit  215  performs memory allocation and release in logical addresses, and manages physical addresses corresponding to the logical addresses. 
     The ID management unit  217  manages IDs assigned to respective applications, and inserts an ID to a conversion table to identify the application which uses a memory block specified with the ID in the conversion table. 
     The flag management unit  219  manages status (e.g. waiting or stop) of each memory block. 
     The address converter unit  221  (an instance of the converter unit) performs address conversion between the logical address space and the physical address space. The address converter unit  221  contains a converter unit  231  for converting a physical address to a logical address, and a converter unit  233  for converting a logical address to a physical address. 
     The memory statistic information management unit  241  acts as a part of the physical partition management unit. The unit  241  identifies sizes of areas not in use in the physical partition, and forms list structures of the areas having respectives of the sizes, and searches for an area not in use in the list structure corresponding to an optimum size to the request. 
     A management unit  251  manages the number of memory blocks in use. 
     A management unit  253  manages the number of memory bytes in use. 
     A threshold value checking unit  255  checks the fragmentation rates of the partitions, and prohibits further memory allocation in the partition if the fragmentation rate of the partition is greater than an upper-most threshold value. After prohibiting further memory allocation in the partition, the threshold value checking unit  255  allows further memory allocation if the fragmentation rate of the partition becomes less than a lower-most threshold value. The upper-most threshold value and the lower-most threshold value may be, for instance, 70 percent and 30 percent, respectively. Alternatively, the upper-most threshold value may be 99 percent. The threshold value checking unit  255  changes a value of a flag when the fragmentation rate becomes greater than the upper-most threshold value and when the fragmentation rate becomes less than the lower-most threshold value. The threshold value checking unit  255  reads-in threshold value definition information  256  in its initialization. 
     A threshold value type management unit  257  identifies sizes of areas not in use in the physical partition, and forms groups of the areas not in use having respectives of the sizes in a physical partition. The threshold value type management unit  257  reads-in threshold value type definition information  258  in its initialization. 
     The MCB management unit  261  manages memory control blocks (MCBs). An MCB is a part which contains a pointer to the head of a physical memory block, the size of the physical memory block, and so on. The MCB will be explained below in detail. 
     [Micro-Partition] 
     In  FIG. 7 , for instance, physical memories used by the application of ID=Interpreter are isolated in the micro-partitions # 1 , # 6  and # 9 , and the number of fragments is two (i.e. one is the micro-partitions # 2  to # 5 , and the other is the micro-partitions # 7  and # 8 ). Similarly, physical memories used by the application of ID=Graphics are isolated in the micro-partitions # 2 , # 4 , # 5  and # 8 , and the number of fragments is two (i.e. one is the micro-partition # 3 , and the other is the micro-partitions # 6  and # 7 ). Similarly, physical memories used by the application of ID=Rendering are isolated in the micro-partitions # 3  and # 7 , and the number of fragment is one (i.e. the one is the micro-partitions # 4  to # 6 ). In this physical partition, the total number of fragments is five, and the total number of micro-partitions is nine, and therefore, the fragmentation rate is 62.5 percent (={5/(9−1)}×100). 
     Although the physical memories are isolated, since the converter unit M 19  performs address conversion between physical addresses and logical addresses by using the conversion table M 13 , it is possible to access the logical partition management unit M 21  with logical addresses to a regularly continuous memory space. For the applications of the Graphics and the Rendering, memory management is performed as well as that. 
     For instance, in  FIG. 7 , logical addresses for the application of ID=Interpreter are continuous over the micro-partitions # 1 , # 6  and # 9  in the order of # 1 , # 6 , # 9 . Similarly, logical addresses for the application of ID=Graphics are continuous over the micro-partitions # 2 , # 4 , # 5  and # 8  in the order of # 2 , # 4 , # 5 , # 8 ; and logical addresses for the application of ID=Rendering are continuous over the micro-partitions # 3  and # 7  in the order of # 3 , # 7 . 
       FIG. 8  shows an instance of certain micro-partitions specified as fixed memory areas. Some hardware such as DMA (Direct Memory Access) directly accesses an address space of a physical memory (i.e. without a logical address space). This memory management system works well even if the hardware accesses fixed addresses in the physical memory. If there are fixed addresses in the physical memory, then the converter M 19  sets the ID of a micro-partition in the conversion table M 13  as a value indicating that this micro-partition is fixed by hardware. The micro-partition with the ID of such value is a fixed area, and thus, the physical partition management unit M 17  does not use such micro-partition (i.e. the fixed area) for allocation even if a memory allocation request is received from the physical partition management unit M 21 . As shown in  FIG. 8 , even if memory allocation requests are received from the physical partition management unit M 21  for the applications “Interpreter”, “Graphics” and “Rendering”, physical addresses of micro-partitions are allocated other than the fixed micro-partitions having the ID of such value. Therefore, the micro-partitions used for the applications do not compete with the micro-partitions fixed by hardware. 
     [Allowance and Prohibition of Further Allocation with Reference to a Fragmentation Rate of Areas not in Use] 
     In the following part, explained is detailed operations of allowance and prohibition of further memory allocation with reference to fragmentation rates of areas not in use. 
     Although defragmentation of a memory can be performed in an ordinary memory management system using a double pointer method, the performance declines due to data transmission within the memory. Therefore, here is proposed the aforementioned memory management system using micro-partitions. This memory management system allocates a partition exclusively specified for each of applications which use memories, and releases all memories in the partition when the application finishes using all the memories. Further, this memory management system uses a logical address space for concatenating partitions, and also uses a conversion table for mutual conversion between a physical address and a logical address.  FIG. 22  shows a relationship between a memory map and physical partitions in the ordinary memory management system. In this system, while an application is using a memory, fragmentation of the memory occurs within a partition (the memory usage efficiency declines). On the other hand, an objective of the memory management system of Embodiment 3 is to efficiently reduce fragmentation in a partition while an application is using a memory. 
     To achieve the objective, here used are an “upper-most threshold value” and a “lower-most threshold value”. On each of partitions, if over the “upper-most threshold value”, it is determined that fragmentation occurs much, and then further allocation in the partition is stopped, and release can be only performed in the partition. In this situation, for memory allocation, a new partition is generated (and partition information on the new partition), and the allocation is performed in the new partition. Areas will be released gradually in the partition where further allocation is stopped, and consequently, if less than the “lower-most threshold value”, then in the partition where further allocation is stopped, further allocation is allowed again, since the fragmentation is small. As mentioned, using the “upper-most threshold value” and the “lower-most threshold value”, each of partitions is managed by identifying its status out of two statuses: the status that the partition is available for allocation (i.e. “waiting”), and the status that the partition is not available for allocation, that is, memory release is only performed (i.e. “stop”). Therefore, even if a partition is being used, defragmentation can be efficiently performed in the partition. These threshold values may be set as certain numbers of memory blocks in use, certain numbers of memory bytes in use, or the like. 
       FIG. 23  shows a relationship between a memory map and physical partitions when stopping memory allocation in some partitions in Embodiment 3. 
     In the physical partitions # 1 , # 3  and # 4 , since fragmentation reaches the upper-most threshold value, further allocation is stopped and release is only performed. Instead of these partitions, the physical partitions # 6 , # 7  and # 8  is used for further allocation. 
       FIG. 24  shows a relationship between a memory map and physical partitions when return to waiting for memory allocation in Embodiment 3. 
     After stopping further allocation in the physical partitions # 1 , # 3  and # 4 , since fragmentation reaches the lower-most threshold value due to release, further allocation is allowed again. 
     The upper-most threshold value is a threshold value for stopping further allocation in a partition. If over the upper-most threshold value, then release is only executed, and consequently, fragmentation can be gradually reduced. 
     The lower-most threshold value is a threshold value for allowing further allocation again. If less than the lower-most threshold value, then further allocation is allowed again. 
     For instance, relationships among the micro-partition number, the ID, the flag, the physical starting address (i.e. head address), the length, and the corresponding logical addresses, mentioned above, are shown in Table 1. 
                                         TABLE 1               MICRO-           PHYSICAL       CORRESPOND-       PARTITION           STARTING       ING LOGICAL       NUMBER   ID   FLAG   ADDRESS   LENGTH   ADDRESS                  1   2   WAIT-   0x3000   0x0800   (ID = 2)               ING           0x0000 TO                           0x07FF       2   3   WAIT-   0x3800   0x0800   (ID = 3)               ING           0x0000 TO                           0x07FF       3   2   STOP   0x4000   0x0800   (ID = 2)                           0x0800 TO                           0x0FFF       4   1   WAIT-   0x4800   0x0800   (ID = 1)               ING           0x0000 TO                           0x07FF       5   3   WAIT-   0x5000   0x0800   (ID = 3)               ING           0x0800 TO                           0x0FFF       6   2   WAIT-   0x5500   0x0800   (ID = 2)               ING           0x1000 TO                           0x17FF                    
[Address Conversion Method]
 
     In Embodiment 3, the partitions are concatenated under the logical address space, and therefore, memory allocation and memory release are executed through the logical address space. For example, in memory release, an address of a release target is specified as a logical address. 
     [Address Conversion Method from a Logical Address to a Physical Address] 
     In the following part, referring  FIG. 25 , explained is the address conversion from a logical address to a physical address. Here, it is assumed that the application of ID=2 releases a memory area of which the head address is the logical address 0x1234. Firstly, the conversion program in the memory management system refers to the conversion table. 
     In the first conversion table in  FIG. 25 , the corresponding logical addresses 0x0000 to 0x07FF is derived from the logical starting address 0x0000 and the length 0x0800, and it is determined that the specified address 0x1234 is out of the corresponding logical addresses 0x0000 to 0x07FF. 
     Next, the second conversion table is identified from the pointer to the linked table in the first conversion table. In the second conversion table, the corresponding logical addresses 0x0800 to 0x0FFF is derived from the logical starting address 0x0800 and the length 0x0800, and it is determined that the specified address 0x1234 is out of the corresponding logical addresses 0x0800 to 0x0FFF. 
     Next, the third conversion table is identified from the pointer to the linked table in the second conversion table. In the third conversion table, the corresponding logical addresses 0x01000 to 0x17FF is derived from the logical starting address 0x01000 and the length 0x0800, and it is determined that the specified address 0x1234 is within the corresponding logical addresses 0x1000 to 0x17FF. 
     When these corresponding logical addresses are found, the difference is calculated between the specified address 0x1234 and this logical starting address 0x1000. The difference, that is, the offset value is 0x0234. 
     Finally, by adding the offset value 0x0234 to the physical starting address 0x5500 in the third conversion table, the physical address 0x5734 is calculated as a physical address corresponding to the logical address 0x1234. 
     [Address Conversion Method from a Physical Address to a Logical Address] 
     In the following part, referring  FIG. 25 , explained is the address conversion from a physical address to a logical address. Here, it is assumed that the application of ID=2 allocates a memory area of which the head address is the physical address 0x5734. 
     Firstly, the conversion program in the memory management system refers to the conversion table. In the first conversion table in  FIG. 25 , the corresponding physical addresses 0x3000 to 0x37FF is derived from the physical starting address 0x3000 and the length 0x0800, and it is determined that the specified address 0x5734 is out of the corresponding physical addresses 0x3000 to 0x37FF. 
     Next, the second conversion table is identified from the pointer to the linked table in the first conversion table. In the second conversion table, the corresponding physical addresses 0x4000 to 0x47FF is derived from the physical starting address 0x4000 and the length 0x0800, and it is determined that the specified address 0x5734 is out of the corresponding physical addresses 0x4000 to 0x47FF. 
     Next, the third conversion table is identified from the pointer to the linked table in the second conversion table. In the third conversion table, the corresponding physical addresses 0x5500 to 0x5CFF is derived from the physical starting address 0x5500 and the length 0x0800, and it is determined that the specified address 0x5734 is within the corresponding physical addresses 0x5500 to 0x5CFF. 
     When these corresponding physical addresses are found, the difference is calculated between the head address 0x5734 of the allocation and the head physical address of this physical partition 0x5500. The difference, that is, the offset value is 0x0234. 
     Finally, by adding the offset value 0x0234 to the logical starting address 0x1000 in the third conversion table, the logical address 0x1234 is calculated as a logical address corresponding to the physical address 0x5734. 
     [Instances of Allocation, Release and Collective Release] 
     The following part shows instances of allocation, release and collective release. 
     An instance of allocation: “void *malloc(int id, size_t size)” 
     N.B. the return value is a logical address. 
     An instance of release: “void free(int id, void *pointer)” 
     N.B. “Pointer” is a logical address. 
     An instance of collective release: “void free_all(int id)” 
     When executing the aforementioned operations, the following matters must be checked. 
     (a) when DMA transmission is performed, certain areas in the physical partition must be fixed. 
     (b) when a memory access takes place by using a library function such as memcpy, strcpy, or the like, this library function must be replaced with a specific library function to which a target address is specified as a logical address. 
     [Operation Flow—Flowchart] 
     In the following part, actual operation flows are explained with reference to flowcharts. 
     Firstly, an initialization process is explained. The operation flow of “void init_memory(void)” is explained with reference to  FIG. 26 . 
     Step S 1011 : It is determined whether or not there is a partition size definition table. If there is the partition size definition table, then Step S 1015  is next executed. If there is not the partition size definition table, then Step S 1013  is next executed.
 
Step S 1013 : A default value is used for the partition size.
 
Step S 1015 : The partition size definition table is read-in.
 
Step S 1017 : It is determined whether or not there are a threshold value definition table and a threshold value type definition table. If there are both definition tables, then Step S 1023  is next executed. If there are not both definition tables, then Step S 1019  is next executed.
 
Step S 1019 : Default values are used for the threshold values.
 
Step S 1021 : A default value is used for the threshold value type.
 
Step S 1023 : The threshold values (i.e. the upper-most threshold value and the lower-most threshold value) are read-in from the definition table.
 
Step S 1025 : The threshold value type (i.e. information for selecting either number of memory blocks in use or number of memory bytes in use) is read-in from the definition table.
 
     By a series of the aforementioned operations, the initialization process is performed. 
     Next, referring to the flowchart shown in  FIG. 27 , a memory allocation process is explained. 
     Step S 1031 : A memory allocation request is received. 
     Step S 1033 : The current pointer is set as a pointer to the first MCB. The current pointer is used to specify the MCB to be processed currently. 
     Step S 1035 : It is determined whether or not there is the current MCB. If there is the MCB, then Step S 1037  is next executed. If there is not the MCB, then Step S 1061  is next executed. 
     Step S 1037 : A free area is searched for. 
     Step S 1039 : It is determined whether or not a free area is found. If a free area is found, then Step S 1041  is next executed. If any free areas are not found, then Step S 1047  is next executed. 
     Step S 1041 : The ID and the flag of the found free area in the conversion table are referred to. 
     Step S 1043 : It is determined whether or not the ID of the free area is the same as the specified ID. If the IDs are same, then Step S 1045  is next executed. If the IDs are not same, then Step S 1047  is next executed. 
     Step S 1045 : It is determined whether or not the flag is “waiting”. If the flag is “waiting”, then Step S 1049  is next executed. If the flag is not “waiting”, then Step S 1047  is next executed. 
     Step S 1047 : The current pointer is put forward to the next MCB. 
     Step S 1049 : The current MCB is updated to allocate the free area. 
     Step S 1051 : The physical address (i.e. the head address) is converted to the logical address. 
     Step S 1053 : It is determined whether or not the memory usage rate is equal to or greater than an upper-most threshold value. If the memory usage rate is equal to or greater than the upper-most threshold value, then Step S 1055  is next executed; otherwise, Step S 1057  is next executed.
 
Step S 1055 : The flag in the conversion table is changed from “waiting” to “stop”.
 
     If a partition were added here, partitions with small memories would increase. Without adding a new partition, an existent partition is used for allocation, if a memory size specified in the next memory allocation request is small. Therefore, the number of partitions is reduced here so as to easily allocate a large memory area. 
     An instance of processes related to Step S 1055  is as follows. 
     Step (a): A partition in “waiting” status is found as the first partition. 
     Step (b): In response of a request of a large memory size, the second partition is generated. 
     Step (c): In the second partition, memory allocation is performed some times. 
     Step (d): The fragmentation of the second partition becomes equal to or greater than the upper-most threshold value, and the second partition is changed to “stop” status. Here, a new partition is not generated. 
     Step (e): When a memory allocation request is received, memory allocation is performed in the first partition. 
     Step S 1057 : The head address of the allocated area (as a logical address) is returned. 
     Step S 1061 : Partition information is added in the conversion table, and the flag is set as “waiting”. 
     Step S 1063 : It is determined whether or not the partition information was added successfully. If the partition information was added successfully, then Step S 1067  is next executed; otherwise, Step S 1065  is next executed. 
     Step S 1065 : The current pointer is set as a pointer to the first MCB. 
     Step S 1067 : The partition information is concatenated. 
     Step S 1069 : It is determined whether or not there is the current MCB. If there is the MCB, then Step S 1071  is next executed. If there is not the MCB, then Step S 1087  is next executed. 
     Step S 1071 : A free area is searched for. 
     Step S 1073 : It is determined whether or not there is a free area. If there is a free area, then Step S 1075  is next executed. If there are any free areas, then Step S 1081  is next executed. 
     Step S 1075 : The ID and the flag of the found free area in the conversion table are referred to. Even if the flag of the partition corresponding to the specified ID is “waiting”, there may be a large free area (in the case that the threshold value of the partition is equal to or greater than percent or the case that the threshold value of the partition is any in the range from 30 percent to 70 percent.
 
Step S 1077 : It is determined whether or not the ID of the free area is the same as the specified ID. If the IDs are same, then Step S 1079  is next executed. If the IDs are not same, then Step S 1081  is next executed.
 
Step S 1079 : It is determined whether or not the flag is “stop”. If the flag is “stop”, then Step S 1083  is next executed. If the flag is not “stop”, then Step S 1081  is next executed.
 
Step S 1081 : The current pointer is put forward to the next MCB.
 
Step S 1083 : The current MCB is updated.
 
Step S 1085 : The physical address (i.e. the head address) is converted to the logical address.
 
Step S 1087 : NULL (i.e. allocation failure) is returned.
 
     By a series of the aforementioned operations, the memory allocation process is performed. 
     Next, referring to the flowchart shown in  FIG. 28 , a memory release process is explained. 
     Step S 1101 : A memory release request is received. 
     Step S 1103 : The logical address of the release target is converted to a physical address. 
     Step S 1105 : The current pointer is set as a pointer to the first MCB. 
     Step S 1107 : The head address of an area to be released is searched for. 
     Step S 1109 : It is determined whether or not the head address is found. If the head address is found, then Step S 1111  is next executed. If the head address is not found, then Step S 1113  is next executed. 
     Step S 1111 : The area to be released is released, and the MCBs related to the released area are updated. 
     Step S 1113 : The current pointer is put forward to the next MCB. 
     Step S 1115 : It is determined whether or not there is a memory in use in the partition. If there is a memory in use in the partition, then Step S 1119  is next executed. If there are not any memories in use in the partition, then Step S 1117  is next executed. 
     Step S 1117 : The partition information is deleted from the conversion table, and then this process ends. 
     Step S 1119 : It is determined whether or not the memory usage rate is less than the lower-most threshold value. If the memory usage rate is less than the lower-most threshold value, then Step S 1121  is next executed; otherwise, this process ends. 
     Step S 1121 : It is determined whether or not there is a partition with the same ID in “waiting”. If there is a partition with the same ID in “waiting”, then Step S 1123  is next executed; otherwise, this process ends. Only if there are no partitions with the same ID in “waiting”, the status is changed from “stop” to “waiting”. Consequently, generating unnecessary partitions in “waiting” are stopped.
 
Step S 1123 : The flag is changed from “stop” to “waiting” in the conversion table.
 
     By a series of the aforementioned operations, the memory release process is performed. 
     Next, referring to the flowchart shown in  FIG. 2 , a collective memory release process is explained. 
     Step S 1131 : A collective memory release request is received. 
     Step S 1133 : Physical partitions corresponding to the specified ID are selected. 
     Step S 1135 : The partition information of the physical partitions is deleted from the conversion table. 
     By a series of the aforementioned operations, the collective memory release process is performed. 
     [Advantages of Embodiment 3] 
     Advantages of the memory management system of Embodiment 3 are as follows. 
     It is possible to avoid fragmentation effectively. 
     Multiple partitions are used to avoid fragmentation effectively. 
     Dynamic movement of boundaries of partitions is used to avoid fragmentation effectively. 
     The order of releasing memories is not limited, and a memory which becomes unnecessary can be released immediately. 
     Fragmentation rates are watched in the physical partitions, and physical memory allocation is prohibited in the physical partition if the fragmentation rate exceeds the upper-most threshold value. Therefore, it is possible to reduce the decline of the processing rate due to using fragmented memory areas. Further, since prohibition of allocation is canceled if the fragmentation rate of the physical partition becomes less than the lower-most threshold value, a new partition is not required and consequently, memory usage efficiency becomes higher. 
     Embodiment 4 
     Comparison with an Ordinary Memory Pool System 
     As shown in  FIG. 31 , in an ordinary memory pool system, an application allocates a memory area when it is required, and releases the memory area after the end of using the memory area. Such operations result in fragmentation, and due to the fragmentation, a continuous large memory area tends not to be allocated. 
       FIG. 32  shows an improved ordinary memory pool system. In the improved ordinary memory pool system, when an application is started, the application allocates a memory area which has a predetermined size corresponding to the application. When a memory manager of the system receives a memory allocation request from the application, the manager obtains a memory within the memory area (i.e. the memory pool) allocated by the application. The method shown in  FIG. 32  is better than that shown in  FIG. 31 . In the method shown in  FIG. 32 , at the end of an application, all of the memory area allocated for the application is released at one time. Therefore, this method enables the system to allocate a large continuous memory area. 
     Since some applications handle large image data in some apparatuses such as image forming apparatus, the respective maximum memory sizes required by applications are sometimes different from each other. At the result, even if using the method shown in  FIG. 32 , that is, the method which fixes areas of memory pools for application, memory usage is not efficient. 
     [Conversion Between a Physical Address Space and a Logical Address Space with Micro-Partitions] 
     In order to solve the aforementioned problem, a physical memory space is divided into small-size areas (hereinafter, this small-size area is called as “micro-partition”), and a logical address space is converted to a physical memory space in the micro-partitions (see  FIG. 33 ). 
     According to this method, even if physical address spaces are not continuous over the micro-partitions, a continuous logical address space is allocated. As the result, a continuous large memory space is allocated. 
     For example, in the ordinary system of memory pools for applications as shown in  FIG. 32 , at first, memory areas are allocated with partition sizes specified in Table 2, and afterward, if memory areas are required for data with data sizes specified in Table 2, then since the data sizes are greater than the partition sizes, memory allocation can not be performed. The memory map in this situation is shown in  FIG. 34 . 
     
       
         
           
               
               
               
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 APPLI- 
                 PARTITION 
                 DATA 
                   
               
               
                 CATION 
                 SIZE 
                 SIZE 
                 DESCRIPTION 
               
               
                   
               
             
            
               
                 APPLI- 
                 100 KB 
                 110 KB 
                 DISABLE TO ALLOCATE 
               
               
                 CATION#1 
                   
                   
                 DUE TO FULL CAPACITY 
               
               
                 APPLI- 
                  60 KB 
                  40 KB 
                   
               
               
                 CATION#2 
                   
                   
                   
               
               
                 APPLI- 
                 140 KB 
                 130 KB 
                   
               
               
                 CATION#3 
                   
                   
                   
               
               
                 APPLI- 
                  30 KB 
                  70 KB 
                 DISABLE TO ALLOCATE 
               
               
                 CATION#4 
                   
                   
                 DUE TO FULL CAPACITY 
               
               
                 APPLI- 
                 150 KB 
                 130 KB 
                   
               
               
                 CATION#5 
                   
                   
                   
               
               
                 TOTAL 
                 480 KB 
                 480 KB 
               
               
                   
               
            
           
         
       
     
     On the other hand, in the system which performs conversion between a physical address space and a logical address space by using micro-partitions, the partition sizes are changeable, and are changed if necessary as shown in Table 3 (that is, the partition size is changed by allocating an additional micro-partition to the logical address space or releasing a micro-partition which has been allocated to the logical address space). Therefore, this solves the aforementioned problem due to the large data size (see  FIGS. 33 ,  36  and  37 ). In this method, the application is not required to allocate its memory pool when it is started, and the memory manager allocates a memory using divided physical partitions. The memory map in this situation is shown in  FIG. 35 . The physical partitions in  FIG. 35  are continuous, but the physical partitions may not be continuous. 
                                 TABLE 3               APPLI-   PARTITION   DATA           CATION   SIZE   SIZE   STATUS                  APPLI-   CHANGEABLE   110 KB   AVAILABLE TO       CATION#1           ALLOCATE DUE                   TO CHANGEABLE                   PARTITION SIZE       APPLI-   CHANGEABLE    40 KB           CATION#2                   APPLI-   CHANGEABLE   130 KB           CATION#3                   APPLI-   CHANGEABLE    70 KB   AVAILABLE TO       CATION#4           ALLOCATE DUE                   TO CHANGEABLE                   PARTITION SIZE       APPLI-   CHANGEABLE   130 KB           CATION#5                   TOTAL   480 KB   480 KB                    
[Areas not in Use in a Partition]
 
     In the method which converts a logical address space and a physical address space by using the aforementioned micro-partitions, the whole memory space is classified into (a) memory spaces used by applications and (b) memory spaces not in use. The memory spaces not in use are concatenated with a link list structure as shown in  FIG. 38 . 
     This method is adopted to search for a memory space sufficient for a memory allocation request from an application. Here, by searching for a memory space of which the size is greater than the size required in the request and as small as possible, memory usage efficiency increase, and fragmentation does not increase. In this method, at first, the size of a memory area specified by a pointer is compared with the required size; if the size of the memory area is sufficient for the required size, then this area is allocated; but if the size of the memory area is not sufficient for the required size, then the next memory area is identified with a pointer in this area, and is also checked. This link list structure is independent from the size of a memory area not in use, and simply has a series of linkages in an address space, and thus, it takes a lot of time to find an area not in use having the optimal size. 
     To solve this problem, in the memory management system of Embodiment 4, each of physical partitions has independent link list structures of areas not in use (i.e. blocks not in use), and the link list structures are formed for respective different memory ranges (i.e. size ranges) into which the sizes of areas are classified. 
     In an instance shown in  FIG. 39 , memory areas not in use are classified into three ranges: 
     (1) Memory range # 1 , that is, the range from 0x0001 to 0x00FF, 
     (2) Memory range # 2 , that is, the range from 0x0100 to 0x0FFF, and 
     (3) Memory range # 3 , that is, the range of 0x1000 or larger. 
     For each of the memory ranges, there is an independent link list structure to concatenate areas not in use. 
     [Configuration] 
     A configuration of a memory management system according to Embodiment 4 is the same as that of Embodiment 3. 
     [Explanation of Detailed Operations] 
     Comparing with the method described in “The C programming language (2nd edition)” (Authors: Karnighan and Ritchie, Prentice Hall) (hereinafter, this is called as “Literature 1”), the detailed mechanism of this system is explained below. 
       FIG. 39  shows a detailed structure of areas not in use and areas in use in the memory map. Each of the memory areas has a header which is called as MCB (Memory Control Block), and has an available area next to the MCB. The MCB has a pointer (ptr) at the head, and has area size (size). The pointer specifies the next memory area in the same group (i.e. in the same memory range). 
     The pointer (ptr) in an area in use is not used, and the pointer (ptr) in an area not in use is used to specify the next area not in use. The set of the MCB and the available area is called as “memory block”. Contents of the MCB are indicated in Table 4. 
     
       
         
           
               
               
               
             
               
                 TABLE 4 
               
               
                   
               
               
                 NAME 
                 VALUE 
                 DESCRIPTION 
               
               
                   
               
             
            
               
                 PTR 
                 POINTER 
                 INDICATE A HEAD ADDRESS OF 
               
               
                   
                 TO MCB 
                 A MEMORY BLOCK NOT IN USE 
               
               
                 SIZE 
                 NUMBER 
                 INDICATE THE SIZE OF AVAILABLE 
               
               
                   
                 OF BYTES 
                 AREA IN THE MEMORY BLOCK 
               
               
                   
               
            
           
         
       
     
     In the algorithm shown in  FIG. 40  according to Literature 1, a list structure of memory blocks not in use ranges over all the partitions. Therefore, it sometimes takes a lot of time for an allocation process. 
     Further, the mean time for an allocation process according to this algorithm is longer than that according the aforementioned algorithm that uses list structures in respective physical partitions. 
       FIG. 41  shows a list structure of memory blocks not in use through all the partitions.  FIG. 42  shows list structures of memory blocks not in use in respectives of the physical partitions. 
       FIG. 43  shows the memory map with the list structure of memory blocks not in use through all the partitions, and  FIG. 44  shows the memory map with the list structures of memory blocks not in use in respectives of the physical partitions. 
       FIG. 45  shows an instance of the conversion tables for the list structure of memory blocks not in use through all the partitions, and  FIG. 46  shows an instance of the conversion tables for the list structures of memory blocks not in use in respectives of the physical partitions. 
     Both of the conversion tables include common items: the micro-partition number, the ID, the flag, the physical starting address, the length (i.e. size), the logical starting address, and the pointer to the linked table. The ID indicates an application which uses the memory block (i.e. micro-partition). The pointer to the linked table is a pointer to the next conversion table of the next memory block not in use. 
     The conversion table shown in  FIG. 46  has the item “pointer to first MCB”, which that shown in  FIG. 45  does not have. This item is explained here. 
       FIG. 47  shows the memory map (in the upper side) and the conversion table (in the lower side) in case of the list structures of memory blocks not in use in respectives of the physical partitions, and in  FIG. 47 , the pointers to the first MCB specifies respective head addresses of memory area not in use in respective physical partitions. 
     Since this method searches for a memory area not in use only in each of the physical partitions, memories not in use are efficiently allocated. 
       FIG. 48  shows an instance of the memory map in case of memory allocation using the BSD malloc described in Literature 1. In general, in the memory allocation using the BSD malloc, blocks with pluralities of sizes are prepared in advance, and the block that has the requested memory size is allocated. This method performs high-speed memory allocation, but its memory efficiency is low. 
     On the other hand,  FIG. 49  shows a memory map and link list structures of areas not in use in case of memory allocation performed by the memory management system of Embodiment 4. In this system, since different list structures are formed corresponding to allocation sizes, the number of times of searching a block in turn is reduced. 
       FIG. 50  shows a detailed memory map in the memory management system of Embodiment 4. Memory areas not in use are classified into Memory range # 1  and Memory range # 2  according to their sizes, and one of the memory ranges has a link list structure different from that of the other. In this system, the MCB contains “prev-flag” and “self-flag” as shown in Table 5. 
     
       
         
           
               
               
               
             
               
                 TABLE 5 
               
               
                   
               
               
                 NAME 
                 VALUE 
                 DESCRIPTION 
               
               
                   
               
             
            
               
                 PTR 
                 POINTER 
                 INDICATE A HEAD ADDRESS OF 
               
               
                   
                 TO MCB 
                 THE NEXT BLOCK NOT IN USE 
               
               
                   
                   
                 IN THE SAME MEMORY RANGE, 
               
               
                   
                   
                 IF SELF-FLAG IS “NOT IN USE”. 
               
               
                   
                   
                 INDICATE A HEAD ADDRESS OF 
               
               
                   
                   
                 THE PREVIOUS BLOCK, 
               
               
                   
                   
                 IF SELF-FLAG IS “IN USE” AND THE 
               
               
                   
                   
                 PREVIOUS BLOCK IS NOT IN USE. 
               
               
                   
                   
                 IF SELF-FLAG IS “IN USE” AND THE 
               
               
                   
                   
                 PREVIOUS BLOCK IS IN USE, 
               
               
                   
                   
                 THE VALUE OF PTR IS INDEFINITE. 
               
               
                 SIZE 
                 NUMBER 
                 INDICATE THE SIZE OF 
               
               
                   
                 OF BYTES 
                 AN AVAILABLE AREA IN 
               
               
                   
                   
                 THE MEMORY BLOCK. 
               
               
                 PREV- 
                 “IN USE” OR 
                 INDICATE STATUS OF 
               
               
                 FLAG 
                 “NOT IN USE” 
                 THE PREVIOUS 
               
               
                   
                   
                 ADJACENT MEMORY BLOCK. 
               
               
                 SELF- 
                 “IN USE” OR 
                 INDICATE STATUS OF 
               
               
                 FLAG 
                 “NOT IN USE” 
                 THE MEMORY BLOCK 
               
               
                   
                   
                 CONTAINING THIS MCB. 
               
               
                   
               
            
           
         
       
     
     As shown in Table 5, the prev-flag indicates the status of the adjacent previous memory block (either “in use” or “not in use”). The self-flag indicates the status of the memory block including this self-flag itself. The status “in use” means that the memory block is now allocated, and the status “not in use” means that the memory block is not allocated now. 
     If the self-flag indicates “not in use”, then the ptr specifies the head of the next block in the same memory range. If the self-flag indicates “in use”, then the ptr specifies the head address of the previous block not in use. 
       FIG. 51  shows a conversion table in case that there are the four memory ranges # 1  to # 4  of allocation sizes, and list structures of memory blocks not in use are formed for respective memory ranges. Each of the conversion tables shown in  FIG. 46  contains one pointer to a MCB, but the conversion table shown in  FIG. 51  contains pointers to MCBs corresponding to respectives of the memory ranges. As shown in  FIG. 53 , in the memory map, four pointers for Sizes # 1  to # 4  (i.e. Memory ranges # 1  to # 4 ) specify respective heads of the first areas in the link list structures of areas not in use corresponding to the memory ranges. 
       FIG. 52  shows an instance of linkages of the conversion tables shown in  FIG. 51 . The pointer to the linked table in the conversion table specifies the next table, and the pointer to the linked table in the last conversion table indicates “END”, namely, “invalid”. 
       FIG. 53  shows a relationship between the conversion table and the MCBs. The pointers to the first MCBs for respective memory ranges specify the head addresses of the first blocks not in use in respectives of the memory ranges. 
       FIGS. 54A to 54D  show ordinary memory release of memory blocks described in Literature 1. This ordinary memory release does not use a list structure of memory blocks not in use. 
     In the instance shown in  FIG. 54A , the statuses of the memory blocks “A” to “E” are “in use”, “not in use”, “in use”, “not in use”, and “in use”, respectively, and here if the memory block “C” is released, then a continuous area not in use (“B”+“C”+“D”) is formed, and the previous area not in use is “B” and the next area not in use is “D”. 
     In the instance shown in  FIG. 54B , the statuses of the memory blocks “A” to “E” are “not in use”, “in use”, “in use”, “not in use”, and “in use”, respectively, and here if the memory block “C” is released, then a continuous area not in use (“C”+“D”) is formed, and the previous area not in use is “A” and the next area not in use is “D”. 
     In the instance shown in  FIG. 54C , the statuses of the memory blocks “A” to “E” are “in use”, “not in use”, “in use”, “in use”, and “not in use”, respectively, and here if the memory block “C” is released, then a continuous area not in use (“B”+“C”) is formed, and the previous area not in use is “B” and the next area not in use is “E”. 
     In the instance shown in  FIG. 54D , the statuses of the memory blocks “A” to “E” are “not in use”, “in use”, “in use”, “in use”, and “not in use”, respectively, and here if the memory block “C” is released, then the previous area not in use is “A” and the next area not in use is “E”. 
       FIGS. 55A and 55B  show an instance of memory release in case that link list structures corresponding to respective memory ranges in this embodiment. In  FIG. 55A , the statuses of the memory blocks “A” to “G” are “not in use”, “in use”, “not in use”, “in use”, “not in use”, “in use”, and “not in use”, respectively, and here if the memory block “D” in use is released, then as shown in  FIG. 55B , the memory block “D” changes to “not in use”, and since the size of the memory block “D” is in the range of 0x1000 or larger, the memory block “D” not in use is inserted between “A” and “G” which are in the same range. 
     Even if the algorithm of Literature 1 is applied to this memory release shown in  FIGS. 55A and 55B , not only “C” and “D” but “D” and “E” would not be connected, since the previous and the next areas not in use are “A” and “G” respectively and therefore (the address of “A”)+(the length of “A”)&lt;(the address of “D”) and (the address of “D”)+(the length of “D”)&lt;(the address of “G”). 
     In this embodiment, when the memory block “D” is released, the memory blocks “C”, “D” and “E” are concatenated using the following method. 
     The prev-flag of the memory block “D” is checked to obtain the status of the adjacent memory block “C” (“in use” or “not in use”). If the prev-flag of “D” indicates “not in use”, then the ptr of “D” specifies the head address of “C”. The self-flag of the memory block “E” is checked to obtain the status of the adjacent memory block “E” (“in use” or “not in use”). Since the head address of the memory block “E” is derived from the head address of “D” and the size of “D”, the memory block “E” can be found. 
       FIG. 56  shows memory maps before and after memory allocation in case that a free area remains after the memory allocation.  FIG. 57  shows a flowchart which indicates operations for the memory allocation. In this memory allocation, the memory block “F” is allocated. Here, the size of the memory block “F” is less than the size of the memory block “B”. In  FIG. 56 , the memory blocks “A” and “C” before the allocation are the memory blocks “D” and “F” after the allocation, respectively. 
     Each of steps in this process is explained below. 
     Step S 2011 : The prev-flag of the memory block “E” is set as “in use”. 
     Step S 2013 : The self-flag of the memory block “E” is set as “not in use”. 
     Step S 2015 : The memory size of the memory block “E” is calculated, and this memory size is set to the size of the memory block “E”. 
     Step S 2017 : The memory block “B” before the allocation is deleted from the free block list (i.e. the list of memory blocks not in use) of the memory range to which the memory block “B” belongs. 
     Step S 2019 : The memory block “E” after the allocation is inserted to the free block list of the memory range to which the memory block “E” belongs. 
     Step S 2021 : The prev-flag of the memory block “E” is set as “not in use”. 
     Step S 2023 : The self-flag of the memory block “F” is set as “in use”. 
     Step S 2025 : The ptr of the memory block “F” is set as the head address of the memory block “E” not in use. 
     Step S 2027 : The size of the memory block “F” is set. 
     Step S 2029 : The prev-flag of the memory block “G” is set as “in use”. 
     Step S 2031 : The ptr of the memory block “G” is set as NULL, since the adjacent previous memory block “F” is in use. 
     By a series of the aforementioned operations, the memory allocation process is performed in case that a free area remains after the memory allocation. 
       FIG. 58  shows memory maps before and after memory allocation in case that a free area does not remain after the memory allocation.  FIG. 59  shows a flowchart which indicates operations for the memory allocation. In this memory allocation, the memory block “F” is allocated. Here, the size of the memory block “F” is the same as the size of the memory block “B”. In  FIG. 58 , the memory blocks “A”, “B” and “C” before the allocation are the memory blocks “D”, “E” and “F” after the allocation, respectively. 
     Each of steps in this process is explained below. 
     Step S 2041 : The prev-flag of the memory block “E” is set as “in use”. 
     Step S 2043 : The self-flag of the memory block “E” is set as “in use”. 
     Step S 2045 : The ptr of the memory block “E” is set as NULL, since the adjacent previous memory block “D” is in use. 
     Step S 2047 : The memory block “B” before the allocation is deleted from the free block list of the memory range to which the memory block “B” belongs. 
     Step S 2049 : The prev-flag of the memory block “F” is set as “in use”. 
     Step S 2051 : The ptr of the memory block “F” is set as NULL, since the adjacent previous memory block “E” is in use. 
     By a series of the aforementioned operations, the memory allocation process is performed in case that a free area does not remain after the memory allocation. 
       FIG. 60  shows memory maps before and after memory release in case that the adjacent previous memory block is not in use and the adjacent next memory block is in use.  FIG. 61  shows a flowchart which indicates operations for the memory release. In this memory release, the memory block “B” is released. Since the prev-flag of the memory block “B” indicates “not in use” and the self-flag of the memory block “C” indicates “in use”, the memory block “B” is released with connecting the memory block “E” to the memory block “D”. In  FIG. 60 , the memory blocks “A”, “B” and “C” before the release are the memory blocks “D”, “E” and “F” after the release, respectively. 
     Each of steps in this process is explained below. 
     Step S 2061 : The size of the connected memory blocks “D” and “E” is calculated, and this size is set to the size of the memory block “D”. 
     Step S 2063 : The memory block “A” before the release is deleted from the free block list of the memory range to which the memory block “A” belongs. 
     Step S 2065 : The memory block generated by connecting “D” and “E” after the release is inserted to the free block list of the memory range to which the generated memory block belongs. 
     Step S 2067 : The prev-flag of the memory block “E” is set as “not in use”. 
     Step S 2069 : The ptr of the memory block “F” is set as the head address of the memory block “D” not in use. 
     By a series of the aforementioned operations, the memory release process is performed in case that the adjacent previous memory block is not in use and the adjacent next memory block is in use. 
       FIG. 62  shows memory maps before and after memory release in case that the adjacent previous memory block is in use and the adjacent next memory block is not in use.  FIG. 63  shows a flowchart which indicates operations for the memory release. In this memory release, the memory block “B” is released. Since the prev-flag of the memory block “B” indicates “in use” and the self-flag of the memory block “C” indicates “not in use”, the memory block “B” is released with connecting the memory block “G” to the memory block “F”. In  FIG. 62 , the memory blocks “A”, “B”, “C” and “D” before the release are the memory blocks “E”, “F”, “G” and “H” after the release, respectively. 
     Each of steps in this process is explained below. 
     Step S 2071 : The size of the connected memory blocks “F” and “G” is calculated, and this size is set to the size of the memory block “F”. 
     Step S 2073 : The ptr of the memory block “F” is set as the head address of the next block not in use in the same memory range. 
     Step S 2075 : The self-flag of the memory block “F” is set as “not in use”. 
     Step S 2077 : The memory block “C” before the release is deleted from the free block list of the memory range to which the memory block “C” belongs. 
     Step S 2079 : The memory block generated by connecting “F” and “G” after the release is inserted to the free block list of the memory range to which the generated memory block belongs. 
     Step S 2081 : The ptr of the memory block “H” is set as the head address of the memory block “F” not in use. 
     By a series of the aforementioned operations, the memory release process is performed in case that the adjacent previous memory block is in use and the adjacent next memory block is not in use. 
       FIG. 64  shows memory maps before and after memory release in case that the adjacent previous memory block and the adjacent next memory block are not in use.  FIG. 65  shows a flowchart which indicates operations for the memory release. In this memory release, the memory block “B” is released. Since the prev-flag of the memory block “B” indicates “not in use” and the self-flag of the memory block “C” indicates “not in use”, the memory block “B” is released with connecting the memory blocks “E”, “F” and “G”. In  FIG. 64 , the memory blocks “A”, “B”, “C” and “D” before the release are the memory blocks “E”, “F”, “G” and “H” after the release, respectively. 
     Each of steps in this process is explained below. 
     Step S 2091 : The size of the connected memory blocks “E”, “F” and “G” is calculated, and this size is set to the size of the memory block “E”. 
     Step S 2093 : The ptr of the memory block “E” is set as the head address of the next block not in use in the same memory range. 
     Step S 2095 : The memory block “A” before the release is deleted from the free block list of the memory range to which the memory block “A” belongs. 
     Step S 2097 : The memory block “C” before the release is deleted from the free block list of the memory range to which the memory block “C” belongs. 
     Step S 2099 : The memory block generated by connecting “E”, “F” and “G” after the release is inserted to the free block list of the memory range to which the generated memory block belongs. 
     Step S 2101 : The ptr of the memory block “H” is set as the head address of the memory block “E” not in use. 
     By a series of the aforementioned operations, the memory release process is performed in case that the adjacent previous memory block and the adjacent next memory block are not in use. 
       FIG. 66  shows memory maps before and after memory release in case that the adjacent previous memory block and the adjacent next memory block are in use.  FIG. 67  shows a flowchart which indicates operations for the memory release. In this memory release, the memory block “B” is released. Since the prev-flag of the memory block “B” indicates “in use” and the self-flag of the memory block “C” indicates “in use”, the memory block “E” is simply released. In  FIG. 66 , the memory blocks “A”, “B” and “C” before the release are the memory blocks “E” and “F” after the release, respectively. 
     Each of steps in this process is explained below. 
     Step S 2111 : The self-flag of the memory block “E” is set as “not in use”. 
     Step S 2113 : The memory size of the memory block “E” is set to the size of the memory block “E”. 
     Step S 2115 : The memory block “E” after the release is inserted to the free block list of the memory range to which the memory block “E” belongs. 
     Step S 2117 : The prev-flag of the memory block “E” is set as “not in use”. 
     Step S 2119 : The ptr of the memory block “F” is set as the head address of the memory block “E” not in use. 
     By a series of the aforementioned operations, the memory release process is performed in case that the adjacent previous memory block and the adjacent next memory block are in use. 
     [Advantages of Embodiment 4] 
     Advantages of the memory management system of Embodiment 4 are as follows. 
     It is possible to avoid fragmentation effectively. 
     Multiple partitions are used to avoid fragmentation effectively. 
     Dynamic movement of boundaries of partitions is used to avoid fragmentation effectively. 
     The order of releasing memories is not limited, and a memory which becomes unnecessary can be released immediately. 
     Sizes of memory areas not in use are classified into memory ranges (i.e. size ranges); and in order to retrieve for a memory area not in use having an optimum size corresponding to a memory allocation request, the system retrieves only memory areas which belong the memory range that includes the size specified by the memory allocation request. Therefore, a memory area not in use can be found in a short time. 
     In view of the embodiments described above, some aspects of the present invention are summarized as follows. 
     The memory management system according to the first aspect of this invention has: a logical partition management unit that manages allocation and release of a virtual memory used by an application in a logical address space; a physical partition management unit that manages allocation and release of small-size parts into which a physical memory is divided in a physical address space; and a converter unit that converts an address between the logical address space and the physical address space. 
     Therefore, fragmentation in the logical address space is efficiently avoided. Further, it is possible to perform allocation and release of a continuous virtual memory space at high speed, and increase or decrease the size of the allocated continuous virtual memory space. 
     Further, in the memory management system according to the first aspect of this invention, the converter unit may generate and delete a conversion table in which a logical address in the logical address space and a physical address in the physical address space are associated with each other. 
     Therefore, efficiently performed is the address conversion from the logical address space of the virtual memory used by an application to the physical address space on the physical memory. 
     Further, in the memory management system according to the first aspect of this invention, the logical partition management unit may allocate a continuous virtual memory in the logical address space for each application. 
     Therefore, the virtual memory is released at high speed by releasing the partition corresponding to an application at one time, and after the release, a large continuous logical address space can be allocated. 
     Further, in the memory management system according to the first aspect of this invention, the physical partition management unit may set an access area by hardware as a fixed area, and may not allocate the fixed area to the virtual memory. 
     Therefore, this memory management system works well even if the hardware accesses such as DMA (Direct Memory Access) occur on fixed addresses in the physical memory. 
     The memory management system according to the second aspect of this invention has: a memory-control-block table management unit that has memory-control-block table, and manages memory allocation in a physical address space by using the memory-control-block table, the memory-control-block table having memory-control-blocks of which each indicates an allocation position of a physical memory; and a memory-control-block control table management unit that has a memory-control-block table control table which organizes the memory-control-blocks for each application, and manages memory allocation using the memory-control-block table control table for each application. 
     Therefore, memory spaces are allocated and released for each of applications, and consequently, fragmentation tends not to occur and it is possible to allocate a large continuous memory space. 
     Further, the memory management system according to the second aspect of this invention may have an application program interface that receives requests of memory allocation, memory release, and collective memory release for an application program. Upon requests from the application program interface, the memory-control-block table management unit may perform memory allocation, memory release, and collective memory, and updates the memory-control-block table. Upon requests from the application program interface, the memory-control-block control table management unit may update the memory-control-block control table according to the memory-control-block table updated by the memory-control-block table management unit. 
     Therefore, if an application program calls the application program interfaces, then the memory-control-block table management unit and the memory-control-block control table management unit perform memory management for each application. Therefore, a programmer is not required to write complex memory operations in the application program, and the programmer&#39;s burden is reduced. 
     Further, in the memory management system according to the second aspect of this invention, the memory-control-block table management unit may concatenate the memory-control-blocks for each application as a concatenated list in order to manage the memory-control-blocks. The memory-control-block control table management unit may have a memory-control-block control block which has a pointer to the first memory-control-block in the concatenated list for each application. 
     Therefore, in terms of such simple concatenate list structure, the system can reach the allocated memory areas in a short time. For example, the collective memory release is performed as simple procedures in a short time. 
     The memory management system according to the third aspect of this invention has: a logical partition management unit that manages allocation and release of a virtual memory used by an application in a logical address space; a physical partition management unit that manages allocation and release of small-size parts into which a physical memory is divided in a physical address space; and a converter unit that converts an address between the logical address space and the physical address space. The physical partition management unit watches fragmentation rates in the physical partitions, and prohibits physical memory allocation in the physical partition in which the fragmentation rate exceeds a predetermined upper-most threshold value. 
     Therefore, fragmentation in the logical address space is efficiently avoided. Further, it is possible to perform allocation and release of a continuous virtual memory space at high speed, and increase or decrease the size of the allocated continuous virtual memory space. Further, when the fragmentation rate of the physical partition is greater than the upper-most threshold value, the physical partition is prohibited to be used. Thus, without collecting a lot of small memory areas in the physical partition due to fragmentation, it is possible to perform conversion between a physical memory and a logical memory at low computational cost. 
     Further, in the memory management system according to the third aspect of this invention, the physical partition management unit may allow physical memory allocation again in the physical partition for which physical memory allocation has been prohibited, if the fragmentation rate of the physical partition becomes less than a predetermined lower-most threshold value. 
     Therefore, in the physical partition where the further memory allocation has been prohibited, when the fragmentation rate becomes less than the lower-most threshold value, the further memory allocation is allowed and a large memory area can be allocated. Consequently, memory usage efficiency becomes higher without using a new physical partition. 
     Further, in the memory management system according to the third aspect of this invention, the converter unit may generate and delete a conversion table in which a logical address in the logical address space and a physical address in the physical address space are associated with each other. 
     Therefore, efficiently performed is the address conversion from the logical address space of the virtual memory used by an application to the physical address space on the physical memory. 
     Further, in the memory management system according to the third aspect of this invention, the logical partition management unit may allocate a continuous virtual memory in the logical address space for each application. 
     Therefore, the virtual memory is released at high speed by releasing the partition corresponding to an application at one time, and after the release, a large continuous logical address space can be allocated. 
     Further, in the memory management system according to the third aspect of this invention, the physical partition management unit may set an access area by hardware as a fixed area, and may not allocate the fixed area to the virtual memory. 
     Therefore, this memory management system works well even if the hardware accesses such as DMA (Direct Memory Access) occur on fixed addresses in the physical memory. 
     The memory management system according to the fourth aspect of this invention has: a logical partition management unit that manages allocation and release of a virtual memory used by an application in a logical address space; a physical partition management unit that manages allocation and release of small-size parts into which a physical memory is divided in a physical address space; and a converter unit that converts an address between the logical address space and the physical address space. The physical partition management unit identifies sizes of parts not in use out of the small-size parts, and searches the parts not in use for a part having a size specified in a memory allocation request and selects the part having the size for the memory allocation request. 
     Therefore, fragmentation in the logical address space is efficiently avoided. Further, it is possible to perform allocation and release of a continuous virtual memory space at high speed, and increase or decrease the size of the allocated continuous virtual memory space. Further, a lot of areas not in use are classified into groups according to their sizes, and a group is selected form the groups, and an area not in use is retrieved only in the selected group. Therefore, an area not in use can be found in a short time. 
     Further, in the memory management system according to the fourth aspect of this invention, the converter unit may generate and delete a conversion table in which a logical address in the logical address space and a physical address in the physical address space are associated with each other. 
     Therefore, efficiently performed is the address conversion from the logical address space of the virtual memory used by an application to the physical address space on the physical memory. 
     Further, in the memory management system according to the fourth aspect of this invention, the logical partition management unit may allocate a continuous virtual memory in the logical address space for each application. 
     Therefore, the virtual memory is released at high speed by releasing the partition corresponding to an application at one time, and after the release, a large continuous logical address space can be allocated. 
     The description of the present invention has been presented for purposes of illustration and description, and is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art.