JPH06161864A - Object storage managing method - Google Patents

Abstract

(57) [Summary] [Object] The present invention provides an object storage management method capable of efficiently referring to an object without paying attention to the operation of garbage collection when writing an application. [Arrangement] A part of the storage area of the processor elements 41, 42 is a garbage collection target area 51,
52, the access to these areas 51 and 52 is managed by a pager so that these accesses are temporarily prohibited.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an object storage management method used for a distributed database such as a network file system of a computer.

[0002]

2. Description of the Related Art Generally, incremental garbage
The basis of the collection is Baker's algorithm (Li
st Processing in Real Tim
e on a Serial Computer, Co
mmunications of the ACM, V
ol. 21, No. 4, pp. 280-294, 197
According to 8). Garbage collection in a distributed / parallel system can be realized by extending Baker's algorithm.

Here, Baker's algorithm is a copying method, and the usable storage area is roughly divided into two.
While searching for objects, the visited objects are sequentially copied to a new area.

However, in the past, as shown in FIG. 12, the object area is defined as the fromspace 131 and the tos.
It is assumed that all objects are in the space 132 and that all objects are initially located in the fromspace 131. Then, when the fromspace 131 is used up, garbage collection is started. That is, a pointer 133 that points to the beginning of an unused area (hereinafter referred to as B)
Garbage collection is started when hits a pointer 134 (hereinafter referred to as T) to the head of the object created during garbage collection. Here, 130 is a pointer that refers to another object from the cell of the object. In Fig. 13, garbage collection is started, and the object is tospace13.
It shows how the movement started in 2.

First, B133 and the pointer 1 for scanning
35 (hereinafter referred to as S) points to the head of the tospace 132, and T134 points to the bottom of the tospace 132. Then, all the objects that are the reference routes of the objects are copied to the tospace 132 from the beginning, and B133 is moved downward by that amount. Next, S13
5 downwards, and if there is a reference to fromspace131, then that object is tospace132
To copy. When this operation is continued and S135 reaches B133, the valid object tospace13
Copying to 2 is complete.

By the way, while such a garbage collection is being executed, other processing may be continued, so that it is necessary to generate a new object. In this case, the unused area pointed to by B133 is created, and B133 is not moved downward, but is placed at the position pointed to by T134, and T134 is moved upward accordingly. This recreates the newly created object in S13.
This is because the waste of scanning in 5 is omitted. Also, if a new object is placed at the location pointed to by B133, the garbage collector and other processing alternately move B133, so the newly created object will be placed in a scattered place on the storage area. This is also because the locality of data is hindered.

After the garbage collection, tos
When space 132 is used up (B133 reaches T134), this time fromspace131 and tospa
The same operation is performed by reversing ce132. Here, the reason why the garbage collection is correctly performed while the other processes are simultaneously operating during the execution of the algorithm is as follows.

Here, the "cell" is an object or a part of the object, which may have a pointer for referencing another object. First,
For the cell already scanned in S135, the cell directly pointed to has also moved to tospace 132. We will call this the "black" cell. The cell newly created under T134 is also a black cell. Also, tospace13
Cells that have been copied to 2 but not yet scanned in S135 may point to the cells in fromspace131. We will call this the "gray" cell. Despite being a valid area, fromsp still
The cell in ace131 is called the "white" cell. At this time, the processing may be advanced while observing the following three points. (1) Each cell becomes “black” in sequence and does not change to “white”. (2) Black cells never refer to white cells. (3) Only black cells and gray cells can be directly seen by processes other than the garbage collector.

It is easy for the garbage collector to protect these three points, but it is difficult for general processing. First,
When referencing the contents of an object, it is necessary to determine what color the cell to which it points and if it is a white cell, copy it to tospace 132 to make it a gray cell. This is because if this is not done, it may go against (3) above. When the white cells are visible, valid cells remain in the fromspace131, and the fromspace131 and tosp
The next garbage collection cannot be performed because it cannot be switched to the ace132.

Next, when rewriting the pointer held in the contents of the object, there is no need to worry at all. The reason is as follows. Suppose that the contents of p are changed to q. Both p and q are black cells or gray cells.
First, if p is a black cell and q is a gray cell, there is no problem because q is scanned later in S135. If q is a black cell and p is a gray cell, the unscanned contents (contents of p) are discarded in S135, but there is no problem. This is because if it was pointed to a black cell it has already been copied, otherwise it will be scanned later in S135 unless it is an invalid object. It is also clear that both p and q are black cells or gray cells.

The above algorithm is
It means that the processing of the collection itself is easy, but it imposes a heavy load on the processing other than garbage collection. Therefore, when the computer does not have sufficient performance or when real-time processing is not important. Not suitable for

Therefore, in a distributed / parallel system, it is possible to suspend all the processes for garbage collection. However, suspending all processing in this way has the problem that the work of the computer user is suspended during that time, so the method based on the following algorithm is usually adopted. Is.

Distributed garbage collection is garbage collection on a multi-processor in which a large number of processor elements are combined. 14
Shows a multi-processor architecture, connecting a plurality of processor elements 142 to a network 141,
A local storage device 143 is connected to each of the two.

By the way, each processor element 14
The reference to the second storage device 143 refers to the own storage device 143.
Since the reference of the other storage device 143 is much slower than the reference of (1), the network 141 connecting the processor elements 142 becomes a bottleneck. Since garbage collection may generate a small amount of data such as a reference between the storage devices 143, the messages to the same processor element 142 are combined as much as possible into one large message, and the data is sent to the network 141. It is considered to reduce the burden of.

One way to facilitate distributed garbage collection is to not perform garbage collection incrementally. As a method of executing garbage collection in parallel on a plurality of processor elements under this condition, Crammond (A Garb
age Collection Algorithm
or Shared Memory Parallel
Processors, Informational
Journal of Parallel Program
mming. Vol. 17, No. 6, pp. 497-
522, 1988) and KL1 (Parallel execution and evaluation of garbage collection in shared memory multiprocessor, Information Processing Society of Japan, Vol.33, No.3, p.
p. 298-305, 1992) and the like are known.

Also, as an algorithm for incremental distributed garbage collection, Rudalics' algorithm is known (Distributed Cop).
ying Garbage Collection, p
roc. of the ACM Conference
on Lisp and Functional Pr
programming 1986).

The local storage device 143, as shown in FIG. 15, has root spaces 151 and fr.
It consists of three parts, omspace131 and tospace132. root space151
Stores a pointer referenced by another processor element 142. Root is a pointer to the object body. fromspace131 and t
The osspace 132 is an area for storing objects, each of which is a normal object (normal object).
objects 152 and 154 and a pointer (remote) to the storage device 143 of the other processor element 142.
Pointer) 153 and 156 are stored. When a pointer from a cell in the storage device 143 to an object in the storage device 143 of another processor element 142 is set, it is performed via a remote pointer. In addition, 155 is a free area.

A pointer from a cell in the storage device 143 of one processor element 142 to an object in the storage device 143 of another processor element 142 makes indirect reference in three stages as shown in FIG. In the figure, 161 is a processor element that has a pointer that references another processor element 142, 161 is a processor element that has a pointer that is referenced by the other processor element 142, and 163 is another processor element from the object cell. A pointer to a reference table to the element 142, 164 is a pointer from a reference table to another processor element 142, and a pointer to another processor element 142 is a local object from a reference table from another processor element 142. Is a pointer to. And, here, it is based on the expectation that there are few references to the outside of the storage device 143.

Global garbage collection is
It is started by the processor element 142 which has a global root. First, global
Mark the roots specified in root. When garbage collection is started in a certain processor element 142, the state (State: Flip or Scan) of the processor element 142 becomes Sca.
change to n, and the object pointed by is marked tospace as in Baker's algorithm.
Copy it to 132. Here, in FIG. 15, 157 is a pointer for operating the object area for which copying has ended,
Reference numeral 158 is a pointer at the beginning of the object area for which copying has ended.

After the scanning is completed, next, remote po
remote po that has been copied out of the inter
For a pointer between the pointer 159 (T) to the beginning of the inter area and the pointer 160 (ST) that scans the remote pointer that has been copied,
It sends a request for marking to the processor element 142 to which it points. At that time, the same processor
The requirements for marking the element 142 should be combined as much as possible. Also, the MsgCount is increased by the amount of the marking message sent.

On the other hand, the processor element 142 receiving the marking message sets State to Sca.
After the garbage collection, the completion message is sent to the processor element 142 which sent the marking message.

Upon receiving the completion message, the processor element 142 decrements MsgCount, and when it becomes 0, the Scan ends. Global r
MsgC of processor element 142 with boot
When the count reaches 0, the Flip message is sent from all the other processor elements 142 to set the State of all the processor elements to F.
Then, the garbage collection of all the processor elements 142 is completed.

In such an algorithm, garbage
Other common operations become very complex while the collection is running. For example, when releasing a remote pointer, it is necessary to send a marking message to the destination pointed to by the remote pointer, and the object should be accessed with a strong awareness of the garbage collection execution procedure.

[0024]

As described above, in the conventional object storage management method, in order to perform the incremental distributed garbage collection of the objects, the remote elements are preliminarily assigned to the respective processor elements.
Prepare an area for e pointer and
The element reference is this remote pointer
Since it is done via, it is necessary to perform processing that is aware of garbage collection, and only a specific language such as Lisp can be used.

Further, in the distributed storage management system using the single virtual memory in which the objects of all the processor elements are represented by one pointer, the mechanism for hiding the difference between the processor elements can be fully utilized. There wasn't. Also, in this case, to prepare an area for garbage collection simply sets the virtual area to 2
There is a serious problem in that not only is it required twice, but the amount of persistent objects that can be actually stored is halved.

In particular, in a computer system connected by a wide area network, an algorithm based on the premise that all the computers participate in garbage collection cannot be applied, and if the processing is not normally completed, serious data will be lost. There was a risk of loss.

The present invention has been made in view of the above circumstances, and an object of the present invention is to provide an object storage management method capable of efficiently referencing an object without paying attention to the operation of garbage collection when writing an application. .

[0028]

SUMMARY OF THE INVENTION The present invention provides a network pager as a mechanism for temporarily prohibiting access to a part of a storage area in a recording device sharing an object managed by a plurality of processor elements on a network. Is used to enable rearrangement of objects in the corresponding storage area.

Further, according to the present invention, the rearrangement is performed by comparing the time when the object is rearranged and the time when the processor having the object in each region participates in the rearrangement in a part or all of each storage area. It detects the invalidity of the pointer to the created object. Further, according to the present invention, part or all of the storage area in which the object is rearranged is temporarily moved to another storage area to rearrange the object.

[0030]

As a result, according to the present invention, as a means for referencing an object existing somewhere in a plurality of processor elements, the pager has a special operation during garbage collection, so that Lisp or Sm can be obtained.
Even if you do not use a specific language that supports garbage collection, such as alltalk, you can refer to objects efficiently without paying attention to the behavior of garbage collection when writing an application. That is,
By giving the pager a mechanism for temporarily prohibiting access to the storage area, general applications can efficiently access distributed objects without being aware of object relocation.

At this time, since access to only some objects in the storage area is prohibited, it is not necessary to stop access to other objects, and the storage area to be relocated is moved to another storage area. It can also be processed, minimizing the amount of storage that must be provided for garbage collection.

Further, by having a history of the time when the objects are relocated for each storage area, even if some information is lost due to failure or non-participation of the object relocation, serious data loss will occur. The data can be repaired without causing the error.

As a result, relocation of objects shared in a network, which has been virtually impossible in the past, can be realized, and applications can be developed without being aware of relocation.

[0034]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 shows a schematic configuration of the same embodiment.
In this case, a plurality of processor elements 2 and a processor element 4 for garbage collection are connected via a network 1. A local storage device 3 is connected to each processor element 2. The term "local" here means an area that can be accessed at high speed, and is usually a real memory, a hard disk, a CD coupled to the processor element 2.
You can think of it as a storage device such as a ROM, and
It does not matter if it can be accessed from the element.
A storage device 5 for garbage collection is connected to the processor element 4 for garbage collection.

Each local storage device 3 is shown in FIG.
As shown in, the storage areas 201 to 205 are arranged as a single virtual storage. As a result, the same object can be referenced by a pointer having the same value from any thread (process) of any processor element, and can be referenced from a general programmer by a simple memory reference instruction. On the other hand, the storage area 207 of the storage device 5 for garbage collection is not mapped to a single virtual storage.

Storage areas 201 to 1 of the local storage device 3
205 contains the cell of the root pointer. This cell is an area that is not erased by garbage collection and exists in at least one or more local storage areas. In this case, a part of the single virtual memory may include a multi virtual memory area in which the storage area pointed to by the pointer of the same value differs depending on the thread. In that case, the access may be performed via a remote pointer as in the Rudalics algorithm. In this embodiment, the case where the multi virtual storage area is not included will be described as an example.

Generally, in order to access the local area of the storage device 3, the speed is increased by utilizing a caching area such as a physical memory. However, it is assumed that the local virtual memory method of that part uses a general method. No description will be given in this embodiment.

In the garbage collection in this embodiment, one or a plurality of storage areas are designated as the garbage collection target area, and the access to the garbage collection target area is completely stopped during the garbage collection. Accessing an area that is not subject to garbage collection is the same as a normal object access method.

In this case, as the total size of the target area for garbage collection increases, the number of times of garbage collection decreases, so that the performance of the entire distributed system improves, but the area that is temporarily inaccessible due to garbage collection. And that time gets bigger. Also, if the total size of the target area for garbage collection is too small, the processing speed of garbage collection will not catch up with the object creation speed, and the stop time for garbage collection will end up taking a long time. It is efficient to decide.

In a distributed object storage management system, object access is by address of a single virtual storage. Then, the determination as to whether or not the object of the accessed address is included in the garbage collection target area is included in the function of the pager that realizes the single virtual memory.

Normally, when a pager detects a page fault, it calls a page-in function, copies it from an appropriate storage area to a local cache (real memory, etc.), and makes it available. During execution of garbage collection, a page-in operation is prohibited by setting a flag indicating that garbage collection is being executed for an entry in the page table, and an access error or access wait state is generated.

Objects in the target area for garbage collection are not accessed during the garbage collection by this mechanism, and local garbage collection can be executed collectively. Since it is not accessed at all, the local garbage collection process may be executed by using the storage area prepared for garbage collection (faster or larger in size than the local storage area). The procedure for executing garbage collection will be described in detail below. In this case, the state of the network is shown in FIG.

This figure shows an example in which the garbage collection target areas 51 and 52 are the entire storage areas of the processor elements 41 and 42, respectively. Other than that, the connection of the network 1, the processor element 2, and the local storage device 3 is the same as described in FIG.

First, the garbage collection target area is determined. In a relatively local network, the garbage collection scheduler can appropriately determine the target area for garbage collection.
For a relatively wide area network, in response to a garbage collection start request message, some or all of the local storage area owned by the processor element attempting to clean up the storage area is subject to garbage collection. By replying that it is an area, the garbage collection target area (address of a single virtual memory) on the network is known.

Next, the processor element that has issued the garbage collection request executes page collection based on the page information that is the target area for garbage collection.
Send a table rewrite request message.

The processor element receiving the page table rewrite request message rewrites the page table so that access to the garbage collection target area is prohibited, and the page table for the subsequent garbage collection. , And sends a page table rewrite end message to the requesting processor element.

The page table rewrite request message includes a strong message and a weak message. A strong message here means that the processor element to which the message is sent always participates in the garbage collection operation. Generally, strong messages are sent by designating a specific processor element, but weak messages are usually broadcast to the network.

Upon receiving the page table rewrite request message, the processor element can reject the message. Message rejection is weakly declared by not sending a page table rewrite complete message.

The processor element which has issued the page table rewrite request message waits for a fixed time for the end message. Ignore processor elements that do not respond to weak messages. The processor element that responds will be referred to herein as the processor element that participated in the garbage collection.

If at least one processor does not respond to a strong message, garbage collection cannot be performed, and a message indicating that garbage collection cannot be started is sent to the processor elements that participated in garbage collection. . Otherwise, garbage
A message to acknowledge the start of the collection
Send to all processor elements that participated in the collection.

Issuing a strong rewrite request message for the page table generally means that the storage area of the processor element that issued the message is being actively used, and the message is issued. It ensures that local garbage collection of processor elements does not make the objects in that storage inaccessible.

Each processor element is
When the message of collection start disapproval is received, the access prohibition of the garbage collection target area is released, and the refusal of subsequent page table rewriting requests for garbage collection is also released.

Upon receipt of the message that acknowledges the start of garbage collection, the local storage device 3 other than the garbage collection target area is set to the garbage collection area 19 or 20 of the remote pointer table as shown in FIG. 4A. Prepare the number of processor elements that have the collection target area. Here, 18 is an area of the root pointer, 21 is an object storage area, and 22 is an unused area.

In this case, it is not necessary to perform the pointer updating process described below for a storage area in which writing is prohibited without having a pointer to another processor element. For example, a storage device such as a non-writable CD-ROM corresponds to this.

Further, the garbage collection target area 5
For 1, the area of the remote pointer table is not required for itself, as shown in FIG. In addition, the area where the object is currently stored (root /
An unused area 22 equal to or more than the pointer area 18) is prepared.

At this time, if a sufficient storage area is not secured, or if it is desired to end the garbage collection quickly using a high-speed storage device, copy it to the storage area prepared for garbage collection. You can run from In other words, in the present invention, if there is one or more storage devices 5 for garbage collection on the network, garbage collection is executed without preparing about twice as many storage areas as in the conventional method. It means that you can. Next, it is ready to receive marking request messages from other processor elements.

If we have a local root pointer, we start marking from there. When a pointer to the garbage collection target area appears during marking,
Save the pointer in the appropriate remote pointer table. However, if the pointer is already registered in the remote pointer table, it is not newly registered. At this time, since general programs other than the garbage collector are also being executed at the same time, marking is
Place in a place that does not interfere with the operation of general programs.

Further, as shown in FIG.
When marking an object in the collection target area, it is copied to a new area as shown in FIG. 5B, and a pointer 25 to the new area and a pointer 26 to the old area are set. At this time, since the address of the new area is an address to be moved after the end of the garbage collection, note that the start address of the object storage area 21 and the start address of the unused area 22 match. The address mentioned here is an address on a single virtual memory, not a logical address used by a local garbage collector. Where 23
Is an object to be marked, and 24 is a copied object.

FIG. 6 is a diagram showing a method of storing the remote pointer table. FIG. 6A shows the storage state of the remote pointer, and FIG. 6B shows the remote pointer table for this remote pointer. The state registered in the table is shown.

The reverse pointer 300 connecting the remote pointers is stored in the cell 29 registered in the remote pointer table as shown in FIG. 9B, and the value of the remote pointer (to execute garbage collection). The previous pointer value) is also stored. Here, 27 is a remote pointer, and 28 is a cell in which the remote pointer was stored.

When the remote pointer table is full or there are no more objects to mark locally, send a marking request message to the other processor elements. The marking request message has a list of remote pointers from the remote pointer table to the destination processor element to send.

Upon receipt of the marking request message, the processor element continues marking with the value of the remote pointer to itself. When marking of the marking request message is complete, the local
A marking end message is returned to the processor element that requested marking.

Each processor element stores the marking request message in the other processor elements, and terminates the local marking when the end message is replied to all the marking request messages. When the local marking is completed in all the marked processor elements, the processor element that requests garbage collection issues a global marking end message to all the processor elements.

When the processor element having no target area for garbage collection receives the global marking end message, it erases the marking from all local objects.

As shown in FIG. 7, the processor element having the garbage collection target area sends its own destination list to all the other processor elements that participated in the garbage collection. in this case,
In the header 124 of the destination list, it is declared which storage area of which processor element it is.
Since each processor element knows the address on the single virtual memory of the storage area of the other processor element, the pre-movement address 125 and the post-movement address 126 to be sent are respectively relative addresses in the local storage area. By doing so, the amount of data in the destination list can be reduced. Here, 127 is a list of destinations to be communicated. The destination list may be sent twice or more.

In order to reduce the amount of communication, the information of the pointer that does not move is not included in this communication. However, this communication can nevertheless be very heavy on systems with fine-grained pointing.

In order to solve this problem, as shown in FIG. 8, data that is to be referred to as an object node is placed in the root cell of the storage area or the head area 30 following it. The top area 30 is not the root cell, but is not moved by garbage collection. This eliminates the need for communication for updating the pointer from the other processor element to the head area 30.

Here, 115 is a cell containing a pointer pointing to a local object in the area of the root cell, 116 is a cell containing a pointer pointing to a local object in the beginning area, 117 is the root -Pointer to the local object from within the cell, 1
Reference numeral 18 is a pointer to a local object from within the cell of the head area, 119 is an object pointed from within the root cell, and 120 is an object pointed from within the cell of the head area.

Generally, most of the objects referred to by the remote processor element are large data such as files, and therefore the amount of data in the destination list to be communicated is small.

In particular, if the size of the cell to be allocated to this head area 30 is kept constant, the unnecessary area is shown in FIG.
It can be reused as shown in. In this example, the cell 116 of the pointer to the object 119 is reused as the cell 121 of the pointer to the object 122 by connecting the unnecessary head areas with the free list.

The fact that the object 123 is no longer needed can be known by not marking it at the time of garbage collection, so in reality, another object is already stored in the erased object area 123. . This reuse method can be applied to the root cell in exactly the same way.

The processor element that has received the destination list updates the value of the pointer registered in the remote pointer table based on it. First, for the pointers included in the destination list, search for the same pointer that matches the pre-movement address of the cell registered in the remote pointer table, and if there is, calculate a new address from the destination list. And reverse pointer 3
Update while tracing 00. The remote pointer area related to the storage area for which the reception of the destination list is completed is returned to the original address.

When the reception of the destination list for all the recording areas is completed, a local garbage collection end message is sent to the processor that issued the garbage collection request. The processor that issued the garbage collection request waits for all termination messages. Finally, garbage collection is terminated by sending a page table undo message to all processor elements.

Generally, not all processor elements normally end due to abnormal data or system down. In such a case, the abnormal data is prevented from being erroneously accessed and detected as an error.

Each processor element records the time when the execution of the previous garbage collection was started and the time when the execution of the previous garbage collection was completed. The garbage collection start time is common to all processor elements, and is sent first by the processor that issues the request to start garbage collection. If these data are inconsistent, for example, if you are not participating in the most recent garbage collection performed by another processor element you are referencing, then invalidate (empty) the pointer. . However, if the area pointed to by the pointer is an area secured after the garbage collection, this processing is not performed.

This process is typical of processor elements that are particularly referencing data on very distant networks and were unable to participate in their garbage collection.

If this processing is neglected, the reference objects to other processor elements will change due to the failure of global garbage collection. This strong message is used in order not to invalidate the pointer by inadvertently performing this processing.

If the self-participation in the latest garbage collection of the referenced processor element is not completed yet, the reference pointer is invalidated. This process is typical, especially when your own machine goes down during garbage collection. Further, it is possible not only to perform this processing when the memory access actually occurs, but also to detect only whether or not the pointer becomes invalid.

In the object storage management method of the present invention, since the paging system can perform garbage collection management together with page management, the programmer needs to be aware of whether or not garbage collection is being executed. There is no.

FIG. 10 shows a configuration that realizes a paging method capable of performing garbage collection management. In the figure, 401 is a network, 402 is a page table register, 403 is a page table address register, 404 is a CPU, 405 is a virtual address storage device, 406 is a page table, 407 is a physical memory, 408 is a secondary storage device, 420 is a page valid flag, 421 is an access right flag, 422 is a garbage collection executing flag, 423 is a garbage collection execution time storage device, 424 is a page frame, and 42 is a page frame.
Reference numeral 5 is a secondary storage device address storage device.

Then, the processing shown in FIG. 11 is executed for such a configuration. In this case, when the process causes an exception, the area corresponding to the address causing the exception is locked (step 1101). In this case, the address that caused the exception is not the virtual address space (step 110).
2), as a segmentation violation (step 110)
3) End with an error. On the other hand, if it is the virtual address space (step 1102), it is determined whether the corresponding area is currently undergoing garbage collection (step 1104). If YES here, it is determined whether the time when the area was last garbage collected is later than the time when the running machine last participated in the garbage collection of the machine in the area (step 1105). Then, if YES here, the corresponding area is lost (step 110).
6) The process ends in error. If NO, a new page is assigned to the area (step 1107), the area is unlocked (step 1108), and the paging is terminated.

On the other hand, if NO in step 1104, the current paging mode is judged (step 1109),
Since the relevant area is under garbage collection, it is inaccessible (step 1110) or waits for the end of garbage collection (step 1111).

Therefore, in this way, by utilizing the characteristics of the garbage collection of the copy method, even if a data abnormality or system trouble should occur, the abnormal data can be detected. The present invention is not limited to the above-mentioned embodiments, and can be implemented by appropriately modifying it without changing the gist.

[0085]

As described above, according to the present invention, by providing the pager with a mechanism for temporarily prohibiting access to the storage area, a general application does not need to be aware of relocation of objects and the distributed objects can be distributed. Can be accessed efficiently. As a result, efficient object relocation can be performed without stopping the execution of the application. Also, it is possible to perform processing only on some computers on the network, and even if an abnormality occurs during processing, the abnormal pointer is deleted, so
You can do very reliable object management. Furthermore, useless storage area is not used, and it is possible to prevent inconsistency due to data access by a broken pointer.

Since access to only some objects in the storage area is prohibited, it is not necessary to stop access to other objects, and the storage area to be relocated is moved to another storage area for processing. It also minimizes the amount of storage that must be provided for garbage collection.

Further, by having a history of the time when the objects are relocated for each storage area, even if some information is lost due to failure or non-participation of the object relocation, serious data loss will occur. The data can be repaired without causing the error.

[Brief description of drawings]

FIG. 1 is a system configuration diagram to which an embodiment of the present invention is applied.

FIG. 2 is a diagram for explaining a single virtual memory according to an embodiment.

FIG. 3 is a diagram showing a network state.

FIG. 4 is an internal view of a local storage device in a garbage collection target area.

FIG. 5 is a diagram showing a storage state of a remote pointer and a state registered in a remote pointer table.

FIG. 6 is a diagram showing a method of storing a remote pointer table.

FIG. 7 is a diagram showing a movement destination list of a processor element having a garbage collection target area.

FIG. 8 is a diagram for explaining communication of a destination list.

FIG. 9 is a diagram for explaining communication of a destination list.

FIG. 10 is a diagram showing a configuration realizing a paging method capable of performing garbage collection management.

11 is a diagram for explaining the paging method shown in FIG.

FIG. 12 is a diagram showing a state example of a storage area to which a conventional Baker algorithm is applied.

FIG. 13: Garbage based on Baker's algorithm
The figure which shows a collection execution example.

FIG. 14 is a connection diagram of a distributed memory.

FIG. 15 is a diagram showing a storage area of a processor element.

FIG. 16 is a diagram showing a method of referring to an object in a remote processor element.

[Explanation of symbols]

1 ... Network, 2 ... Processor element, 3 ...
Local storage device, 4 ... Processor element for garbage collection, 5 ... Local storage device for garbage collection, 401 ... Network, 40
2 ... Page table register, 403 ... Page table address register, 404 ... CPU, 405 ... Virtual address storage device, 406 ... Page table, 407 ...
Physical memory, 408 ... Secondary storage device, 420 ... Page valid flag, 421 ... Access right flag, 422 ... Garbage collection execution flag, 423 ... Garbage collection execution time storage device, 424 ... Page frame, 425 ... Secondary Storage address storage device.

Claims (2)

[Claims] 1. In a recording device that shares an object managed by a plurality of processor elements on a network, a network pager is used as a mechanism for temporarily prohibiting access to a part of the storage area, and An object storage management method characterized by enabling relocation of objects. 2. A relocated object is obtained by comparing the time when an object is relocated in a part or all of each storage area and the time when a processor having an object in each area participates in the relocation. 2. The object storage management method according to claim 1, wherein the invalidity of the pointer is detected.