JPH0271342A - Memory controller - Google Patents

Abstract

PURPOSE:To decrease the useless reference actions and to realize a memory allocation control process at a high speed by performing a searching task by referencing a respective allocation bit among plural individual allocation bits and with no direct reference given to an individual control bit map. CONSTITUTION:A memory 10 consists of many unit areas for control and controls each page allocation. For this purpose, the memory 10 includes a individual control bit map 12, a primary representative control bit map 14, a secondary representative control bit map 16, and a memory allocation controller 18. The map 12 includes a gathering of individual allocation bits 13 which shows each page 11 forming the memory 10 is already allocated or not. These bits 13 are formed into one word every 8 bits and a primary representative allocation bit 15 is set every bits 13 equivalent to one word.

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to a memory management device for managing memory allocation used in computers and the like.

(Prior art) When using memory such as the main memory of a computer,
In general, management is performed such that the memory is divided into a number of areas of a fixed size, and each area is used as a unit to allocate the memory to various tasks. One unit area is called a page or block, and when there is a certain amount of data to be stored in memory, for example, by checking the free pages in memory,
A method is used in which data is sequentially stored in the empty pages.

In this way, when memory is used in page units, it is necessary to manage whether each page constituting the memory has already been allocated for storing some data. For this management, a method using a bitmap is conventionally known.

FIG. 2 shows a block diagram of a conventional memory management device.

In the figure, a memory 1 is divided into a large number of pages 2, and a bitmap 3 containing one bit of allocation information is provided for each page.

In the figure, for example, when the allocation information is 0°, it indicates that the page has been allocated, and when the allocation information is 1'', it indicates that the page is empty.

When there is a request to use memory, the memory allocation control device 4 refers to each piece of allocation information in the bitmap 3 and searches for an empty page. If an empty page is found, a read/write control device (not shown) writes data to the empty page of the memory.

(Problem to be Solved by the Invention) By the way, in the conventional memory management device as shown in FIG. , bitmap 3 is sequentially searched each time.

Therefore, there is a problem in that wasteful search operations increase especially when the number of free pages decreases.

Furthermore, as the capacity of the memory 1 progresses and the number of pages 2 increases, the number of allocation information forming the bitmap 3 also increases accordingly. Therefore, there is also the problem that the search time of the memory allocation control device becomes increasingly long.

The present invention has been made with attention to the above points, and an object of the present invention is to provide a memory management device that can manage memory allocation at high speed.

(Means for Solving the Problems) A memory management device of the present invention manages the allocation of each unit area for management that constitutes a memory, and for each unit area,
Whether or not it has been allocated is indicated by individually allocated bits, and an individual management bitmap is provided that collects these individually allocated bits, and for each of the plurality of individually allocated bits in the individual management bitmap, one of the individually allocated bits is displayed. This feature is characterized in that whether or not the assignment has been completed is indicated by one representative assigned bit, and a representative management bitmap is provided in which the representative assigned bits are collected.

(Operation) When searching for an empty page, for example, the apparatus configured as described above first refers to the representative management bitmap. By referring to one representative assigned bit constituting the representative management bitmap, the same result as referring to all individual assigned bits can be obtained when a plurality of individually assigned bits all indicate that they have been assigned. Furthermore, if any of the individually assigned bits indicates an empty page, this is recognized from the display of the representative assigned bits, and the individual management bitmap is directly searched again. As a result, especially when many pages have been allocated, it is possible to increase the speed of referring to individually allocated bits that have already been allocated, and to shorten the time required to search for empty pages.

(Example) Hereinafter, the present invention will be explained in detail using embodiments shown in the drawings.

FIG. 1 is a block diagram showing an embodiment of a memory management device of the present invention.

In the device shown in the figure, a memory 10 is composed of a large number of management unit areas, for example, pages 11, and in order to manage the allocation of each page, an individual management bitmap 12, -
A bit map 14 for managing the next representative, pins 1 to 16 for managing the secondary representative, and a memory allocation control device 18 are provided.

The individual management bitmap 12 is a collection of individual allocation bits 13 that indicate, for each page 11 constituting the memory 10, whether or not that page has been allocated.

In this embodiment, the individually allocated bit 13 is 0''
If it is, it means that it has been allocated, and if it is, it is an empty page.

Further, these individually allocated bits 13 are assembled so that every 8 bits constitute one word, and one primary representative allocated bit 15 is set for each individually allocated bit for one word. This - next representative allocation bit 1
The collection of 5 is the -next representative management bitmap 14
becomes.

The primary representative assigned bit 15 is "O" when all the corresponding individually assigned bits 13 for l words are "O",
It is set to be "1" if even one l°" is included.

Further, the -th representative assigned bits 15 also constitute one word for every 8 bits, and for this one word of the primary representative assigned bits 15, one bit of the secondary representative assigned bits 1
7 is set.

A collection of these secondary representative allocation bits 17 becomes the secondary representative management bitmap 16.

The display content of the secondary representative assignment bit 17 is also the same as that of the -second representative assignment bit 15. That is, if all the primary representative assigned bits 15 for one corresponding word are O゛, then
The secondary representative assigned bit 17 also becomes O'°. In addition, if even one of the primary representative assigned bits for the corresponding l word has the content “1'', the secondary representative assigned bit 17
becomes 1′″.

When the device operates, the memory allocation control device 18:
When searching for a free page, first, the secondary representative management bitmap 16 is searched, and from the contents, the secondary representative assignment bit 17 indicating that a free page is included is recognized. Then, the corresponding primary representative allocation bit 15 is searched.

Further, the -next representative allocation bit 15 is searched, and from the contents thereof, the individual allocation bit 13 indicating that an empty page is included is recognized. This is how you find an empty page.

Although the general operation of the apparatus of the present invention is as described above, the operation of the apparatus of the present invention will be explained in more detail using FIG.

FIG. 3 is a flowchart showing the specific operation of the apparatus of the present invention.

In the figure, when a search for a free page is started, first, the secondary representative management bitmap 16 shown in FIG. 1 is referred to (step Sl). Then, it is determined whether or not the secondary representative assignment bit 17 is '1' (step S2).
If all are 0'', this indicates that all pages 11 in the memory 10 have been allocated, and it is already impossible to store data in the memory 10, so the operation ends.

On the other hand, any secondary representative assigned bit 17 is "1"
If so, the process moves to step S3. In step S3, one word of the primary representative allocation bitmap displayed by the corresponding bit is referred to. That is,
For example, in FIG. 1, since the leftmost secondary representative assignment bit 17 of the secondary representative management bitmap 16 is 1°, the leftmost 1 of the -order representative management bitmap I4 is
The primary representative allocation bit 15 for one word is referenced.

Next, the primary representative assigned bit from the word is “1”
” is searched (step S4).

That is, the primary representative assignment bitmap 14 shown in FIG.
Among them, the one whose -th representative assigned bit 15 is 1'', for example, the leftmost bit is extracted.

Then, one word of the individual management bitmap 12 displayed by the corresponding bit is referred to (step S5). That is, the individually allocated bit 13 corresponding to one word at the leftmost end of the individual management bitmap 12 shown in FIG. 1 is referred to. Then, a search is made for a position where the individually allocated bit is .degree.1.degree.' from the word (step S6).

For example, in the example shown in FIG. 1, since the second individually allocated bit 13 from the left is 1°, it is discovered that the corresponding page 1 on the memory 10 is empty. In accordance with this, the page to be displayed by the individual allocation bit 13 is allocated (step S7).

Next, the individually assigned bit 13 is changed from l°゛ to "o"
” (step S8). This means that the individual allocation bit 13 is used to indicate that the page has been allocated.

This completes the memory allocation process, but in order to operate the device of the present invention, after the page allocation process, the -next representative management bitmap 14 and the secondary representative management bitmap 16 must be created first. It is necessary to rewrite the content as explained. The rewriting work is performed in steps S9 to 312 shown in FIG.

That is, first, it is determined whether all other bits in the word to which the individual assigned bit 13 that has already been assigned are ``O'' (step S9). If there is a blank page in that word, there is no need to modify the corresponding primary representative allocation bitmap 14, and the process ends as is.

On the other hand, if all the bits are ``゛OO゛°'', the primary representative assigned bit 15 that displays the word is
(step 510). Further, when the -next representative assigned bit 15 becomes °゛O°°, it is determined whether all other bits in the word to which it belongs are "o" (step 511).

Then, as in step S9, all other bits are ``0''.
If it is a word, the secondary representative allocation bit 17 indicating the word is set to O°° (step 512).

Through the above processing, the individual management bitmap 12 and the primary or secondary representative management bitmap 14.16 are
Each can be modified according to the rules described above.

In the above embodiment, for example, for the rightmost word of the individual management bitmap 12, all the individually allocated bits 13 are set to °゛O''. Regarding the word on the far right,
In all cases, the primary representative assigned bit 15 is 0''. As a result, the rightmost secondary representative assignment bit 17 of the secondary representative management bitmap [6] is 0''.

Here, if the memory allocation control device 18 searches the secondary representative management bitmap 16 from the right side, in the conventional device, by referring to 64 individually allocated bits 13 of the individual management bitmap 12, , it was possible to recognize that these bits have already been allocated to a page, whereas in the device of the present invention, by referring to one of the secondary representative allocation bits 17 of the secondary representative management bitmap 16, the same information can be recognized. Get results.

Therefore, especially when the number of allocated pages increases and the number of free pages decreases, the memory allocation control device 1
8 search time can be significantly shortened. In fact, since the memory is composed of, for example, several thousand pages, the effect of shortening the search time can be said to be extremely large.

The present invention is not limited to the above embodiments.

In the above embodiment, the representative management bitmap is -
Although two stages, the next and second, are provided, it is also possible to provide only the -th-order representative management bitmap, or it is also possible to provide a third-order or higher representative management bitmap.

In addition, we have explained an example in which the representative management bitmap is configured to display 8 bits of the individual management bitmap as 1 word and display them all together. It doesn't matter if it's something.

In the case of the above embodiment, each bitmap is formed on one memory, and the contents can be rewritten by a program. Management Bitmap] It is also possible to construct a circuit configuration in which word worth of data is input to each bit of the representative management bitmap via an OR gate.

Furthermore, in the above embodiment, 1. The explanation was given using an example in which the unit area for memory management is a page, but it is also possible to manage several pages as one block and implement the present invention using this block as one unit area. Needless to say, this is a good thing.

(Effects of the Invention) According to the memory management device of the present invention as described above, the search is performed by referring to a representative allocated bit representing a plurality of individually allocated bits, without directly referring to the individual management bitmap. The operations can be reduced and fast memory allocation management can be performed even in large-capacity memories.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an embodiment of the memory management device of the present invention, FIG. 2 is a block diagram of a conventional memory management device, and FIG. 3 is a flowchart showing the operation of the device of the present invention. 10...Memory, 11...Page, 2...Individual management bitmap, 3...Individually assigned bit, 4...-Next representative management bitmap, 5...-Next representative assigned bit, 6... Bit map for secondary representative management, 7... Secondary representative allocation bit, 8... Memory allocation control device.

Claims (1)

[Claims] The allocation of each unit area for management constituting the memory is managed, and for each unit area, whether or not it has been allocated is indicated by individual allocated bits, and the individual allocated bits are aggregated. A management bitmap is provided, and for each of the plurality of individually allocated bits in the individual management bitmap, whether or not any individually allocated bit has been allocated is indicated by one representative allocated bit, and this representative allocated bit is displayed. A memory management device characterized by providing a representative management bitmap in which bits are collected.