JPH0517584B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Object of the Invention] (Field of Industrial Application) The present invention relates to a buffer memory management method in a data processing device.

(Prior art) Conventionally, buffer memory management involves dividing the buffer memory to be managed into units of a certain size.
A method has been adopted in which these are connected in a list structure to express in-use areas, released unused areas, etc.

In buffer memory management means using such a list structure, memory usage efficiency is improved by reducing the division unit of the buffer memory to be managed, but there is a drawback that the time involved in list processing increases.

Therefore, if high-speed buffer memory management is required, it is desirable to manage the buffer memory one-dimensionally rather than in a list structure. That is,
Received data is sequentially accumulated in the buffer memory, and used data is directly released from the buffer memory.

In such a one-dimensional management method of buffer memory, it is necessary to manage the boundaries between unused areas and used areas in the buffer memory to be managed. At any location, boundaries between used and unused areas and how to combine previously released areas must be examined across the entire area.
Therefore, the time required for the above-mentioned management processing is almost the same as in the case of the above-mentioned list structure, and there is a problem that no great effect in speeding up can be expected.

(Problems to be Solved by the Invention) As mentioned above, when buffer memory is conventionally managed one-dimensionally, it is necessary to conduct a comparative inspection of all areas on the buffer memory to be managed. The problem was that it took a lot of time to process the data, making it impossible to increase the speed.

The present invention has been made in view of the above-mentioned circumstances, and uses a table that takes as a set of inputs the starting address and the final address of the freed memory area, without comparing and inspecting the entire area of the buffer memory, while the buffer memory is in use. The configuration is such that the oldest address (hereinafter referred to as the oldest address) of the area (including a partially released area) is managed, thereby realizing high-speed one-dimensional buffer memory management.

[Structure of the Invention] (Means and Effects for Solving the Problems) The present invention manages the oldest address in the buffer memory where the oldest data that has not yet been read is stored, and also manages the oldest address in which the oldest data that has not yet been read is stored, and also manages the oldest address in which the oldest data that has not yet been read is stored, and The range of areas released as areas is organized into unconnected areas and managed in the order in which the areas were released.
When releasing an area from which data has been newly read, check the connections between the oldest address and the new released area, and the new released area and the oldest released area, and release from the previous oldest address. The oldest address is updated to the next address of the final address of the continuous area, and if there is no connection between the previous oldest address and the new free area, the new free area and the oldest free area are updated. When there is a connection, the free area is managed as the entire connected area, and when there is no connection, the free area is managed as a new area.This makes it necessary to compare and inspect all areas of the buffer memory to be managed. Therefore, high-speed one-dimensional buffer memory management can be realized.

(Example) An example of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing the components in one embodiment of the present invention.

In the figure, reference numeral 1 denotes a CPU, which executes buffer area release processing control as shown in FIG. 7 using a management table 2 to be described later. 2 is a management table with a FIFO structure that holds address information for area management on the buffer memory 3 under the control of the CPU 1, and a start address that holds the start address of released data on the buffer memory 3 It consists of a holding section _2S and a final address holding section _2E that holds the same final address. 3 is buffer memory placed under the management of CPU 1, and
Data is accumulated under the control of 1, and data that is no longer needed is released. In addition, BTM in the figure is an address register (hereinafter simply referred to as BTM) that stores the oldest address indicating the beginning position of the oldest area within the area in use.
OP is an output pointer (hereinafter simply referred to as OP) indicating the oldest entry held in the management table 2, and IP is an input pointer indicating the latest entry (hereinafter simply referred to as IP). .

2 to 6 are operation explanatory diagrams showing the operating states of the above embodiment, and FIG. 7 is an explanatory diagram showing the operation state of the above embodiment.
2 is a flowchart showing a buffer area release processing flow executed under the control of CPU1.

Here, the operation of one embodiment will be explained with reference to the above-mentioned FIGS. 1 to 7.

FIG. 1 shows a state in which received data is stored in area a in buffer memory 3. As shown in FIG. At this time, BTM indicates the oldest address of the area in use on the buffer memory 3.

When the CPU 1 releases data in a certain area stored in the buffer memory 3, it first checks whether the area (N) to be released is in contact with the BTM address, that is, the area (N) to be released is checked. Check whether the first address matches the BTM address (step S10 in Figure 7), and if the addresses match, execute the BTM address update process (steps S11 to S15 in Figure 7) to check if the addresses match. If not, the registration/change process for the management table 2 (steps S21 to S25 in FIG. 7) is executed.

2 and 3 respectively show a state in which data in a certain area b is released from the buffer memory 3, and FIG. 2 shows a state in which the start address of the released area b does not match the address of BTM, FIG. 3 shows a state in which the start address of release area b matches the address of BTM. If the start address of the release area b as shown in FIG.
In S25), the start address of release area b is held in the start address holding section 2 _S in the management table 2 indicated by IP in the management table 2, and the final address is also held in the final address holding section 2 _E. After that, the IP is updated (+1). In addition, if the start address of release area b as shown in FIG. 3 matches the BTM address, the address in the management table 2 indicated by OP is After confirming the match between the start address stored in the start address holding unit _2S and the BTM address, the BTM address is updated by the address of the release area b, and OP is further updated (+1).

When the CPU 1 recognizes that the start address of the area (N) to be released matches the address of the BTM, it updates the BTM address to the next address of the area (N) to be released (step 7 in Figure 7). S11), compare the values of OP and IP and manage table 2
is empty (see step 7 in Figure 7).
S12) When the OP value and IP value match and it is recognized that management table 2 is empty, the area is released.
The BTM address update process for (N) ends. Also, when the value of OP and the value of IP do not match and it is recognized that the management table 2 is not empty, the start address holding section 2 _S in the management table 2 indicated by OP is
It is determined whether the first address stored in the BTM address matches the BTM address (step S13 in Figure 7),
If they do not match, finish the table update process for the free area (N), and if they match, proceed as described above.
After updating the BTM address to the address next to the final address stored in the final address holding unit _2E in the management table 2 indicated by OP (step S14 in Figure 7), update the value of OP (+1) and release it. region
The BTM address update process for (N) ends.

An example of this state is shown in FIG. Figure 6 shows a case where an area is further released from the state shown in Figure 4, and the start address of the newly released area d is equal to the address of BTM, and the final address is the OP This shows the case where the address is consecutive to the start address stored in the start address holding unit _2S in the management table 2 indicated by . In this case, simply BTM as shown in Figure 3 above.
Instead of updating the address of only the newly released area, the address of BTM is updated together with the area that has already been released and accumulated in the table (b in the figure). That is, the BTM address is updated to the next address after the final address stored in the final address holding unit _2E in the management table 2 indicated by OP.
And after this update process, update the OP value (+1)
Then, the BTM address update process for the release area d is completed.

The start address of the area (N) to be released next is
Management table 2 registration/change processing when the address does not match the BTM address (step S21 in Figure 7)
S25) will be explained.

When the CPU 1 recognizes that the start address of the area (N) to be released does not match the address of the BTM (step S10 in Figure 7), it compares the values of OP and IP and determines that the management table 2 is empty. It is determined whether or not (step S21 in FIG. 7). When the OP value and the IP value match and it is recognized that the management table 2 is empty, table registration processing is performed for the released area (N) (steps S23 and S24 in Figure 7).
When you execute , and realize that the OP value and IP value do not match and management table 2 is not empty,
Update (change) the final address stored in final address holding section 2 _E in management table 2 indicated by OP
Processing (steps S22 and S25 in FIG. 7) is executed.
In other words, when the value of OP and the value of IP do not match and it is recognized that the management table 2 is not empty, release the final address stored in the final address holding section _2E in the management table 2 indicated by OP. area
Whether the first addresses of (N) are consecutive or not, that is, OP
The final address holding unit 2 in the management table 2 indicated by
It is determined whether the address next to the final address stored in _E matches the first address of the area (N) to be released (step S22 in Figure 7), and if they do not match, the table registration process (described later) is performed. Execute steps S23 and S24 in Figure 7, and if they match,
The value of the final address stored in the final address holding unit _2E in the management table 2 indicated by the above OP is updated (changed) to the value of the final address of the area (N) to be released (step 7 in Figure 7). S25), the table update process for the released area (N) is ended.

Also, when the value of OP and the value of IP match and it is recognized that the management table 2 is empty (step S21 in Figure 7), or the final address holding section _2E in the management table 2 indicated by OP is When the next address of the stored final address and the first address of the area (N) to be released do not match (Step S22 in Figure 7)
registers the start address and end address of the area (N) to be released in the start address holding section 2 _S and end address holding section 2 _E in the management table 2 indicated by the IP (step S23 in Figure 7), and The value of is updated (+1) (step S24 in FIG. 7), and the registration process of the management table 2 is completed.

Examples of this state are shown in FIGS. 4 and 5.
Figures 4 and 5 are examples of states where the area is further released from the state shown in Figure 2 above, and in Figure 4, the start address of the newly released area c is It does not match the BTM address, and it does not connect to the previously released area b (that is, the address stored in the final address holding section 2 _E in the management table 2 indicated by the IP before the IP update) In this case, management table 2 indicated by IP is used as a new free area.
The start address and end address of the free area c are written into the start address holding section _2S and the end address holding section _2E in the free area c. In addition, Fig. 5 shows that the first address of the newly released area c is connected to the previously released area b (that is, the last address stored in the last address holding section _2E in the management table 2 indicated by the IP before the IP update). In this case, the address in the final address holding section _E in the management table 2 registered corresponding to the previously released area b is changed to the final address of the newly released area c. Rewrite to value. That is, the previous release area (b in the figure) and the new release area (c in the figure) are re-registered in the management table 2 as one continuous release area.

Such area release processing on the buffer memory 3 is repeatedly executed each time an area is released.

By having the above-mentioned area management function of the buffer memory 3, when data stored in the buffer memory 3 is released, the buffer memory can compare whether the released area and the previously released area are contiguous. The continuity of the area can be confirmed simply by comparing it with the value of the oldest entry held in the management table 2, without having to update the entire area, thereby speeding up the process of updating the oldest used address in the buffer memory 3. be able to.

In the above-described embodiment, buffer memory management during data transmission and reception was explained as an example, but the present invention is not limited to this and can be widely applied to data exchange between various devices.

[Effects of the Invention] As detailed above, according to the present invention, there is a method of temporarily holding data in order of oldest data and managing empty areas of a buffer memory from which the held data is read out in response to a request. In addition to managing the oldest address on the buffer memory where the oldest data that has not yet been read is stored,
The range of areas where data has already been read and has been released as empty space is organized into unconnected areas and managed in the order in which the areas were released, and when releasing the area where new data has been read, the oldest address Checks the connection between the new free area and the new free area and the oldest free area, and updates the oldest address from the previous oldest address to the next address of the final address of the continuous free area. At the same time, if there is no connection between the previous oldest address and the new free area, check the connection between the new free area and the oldest free area, and if there is a connection, consider all the connected areas. By being equipped with a buffer memory management function that manages the free area as a new area when there is no connection,
There is no need to compare and inspect the entire area of the buffer memory to be managed, and high-speed one-dimensional buffer memory management can be achieved.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing constituent elements for realizing an embodiment of the present invention, FIGS. 2 to 6 are explanatory diagrams of operations in the above embodiment, and FIG. 7 is a processing diagram of the above embodiment. It is a figure showing a flow. 1...CPU, 2...Buffer memory, 2 _S ...Start address holding section, 2 _E ...Last address holding section, 3...
Buffer memory, BTM...oldest address register, IP...input pointer, OP...output pointer.

Claims (1)

[Claims] 1 In a one-dimensional buffer memory management method in which data is temporarily held in chronological order and data areas at arbitrary addresses that have been read out are directly released as used areas, the oldest data in the buffer memory that has not been read out yet. In addition to managing the oldest address where data was stored, the range of areas that have already been read and released as empty areas is organized into unconnected areas, and the areas are managed in the order in which they were released, and new data is stored. When releasing the read area, check the connections between the oldest address and the new released area, and the new released area and the oldest released area, and check whether the released area is continuous from the previous oldest address. The oldest address is updated to the next address after the final address of the area to be released, and if there is no connection between the previous oldest address and the new free area, the link between the new free area and the oldest free area is checked. , a buffer memory management method characterized in that when there is a connection, the free area is managed as the entire connected area, and when there is no connection, the free area is managed as a new area.