JPH0528863B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention provides a multiprocessor system in which processors do not have a shared memory that can be accessed in common, so that the clocks that each processor has for indicating time can be shared with each other. This invention relates to a clock synchronization method for adjustment.

(Prior Art) In a multiprocessor system, it is necessary to synchronize the clocks of each processor making up the system so that they indicate a common time for the entire system. For example, in a distributed filing system, a common time between processors is required to identify versions of files based on the creation and editing times recorded in each file. Also, if each processor accumulates its own history information based on the time common to the system,
It is possible to know in what order the failures were detected when they occur, and useful information for identifying the location where the failure has occurred can be obtained.

Even in a communication network system, which is an example of a multiprocessor system without a shared memory, a synchronization method is required so that the clocks of each communication node indicate a common time. for example,
6th International Conference on Distributed Computing Systems
DISTRIBUTED COMPUTING SYSTEMS)
The paper “An Election Algorithm for Distributed Clocks Synchronization Program (An Election Algorithm for Distributed Clocks Synchronization Program)” is published in the proceedings of
a Distributed Clock Synchronization
The clock synchronization method TEMPO introduced in ``Program'' (Reference 1) is implemented in a network running on the UNIX operating system 4.3 BSD. In the above-mentioned system, one node serving as a master queries all nodes about the time at predetermined intervals, and calculates an average time based on the determined times of each node. Thereafter, a clock adjustment instruction is given to all nodes, and each node adjusts its clock according to this instruction.

Also, the 16th Annual International Symposium on Fault Tolerant Computing (Annual
International Symposium on FAULT−
The paper ``CLOCK SYNCHRONIZATION IN THE PRESENCE OF OMISSION AND PERFORMANCE FOULTS, AND PROCESSORS'' (CLOCK SYNCHRONIZATION IN
THE PRESENCE OF OMISSION AND
PERFORMANCE FAULTS, AND
The clock synchronization method introduced in ``PROCESSOR JOINS'' (Reference 2) uses distributed control rather than master-slave type control like ``TENPO'' explained above. In this system, the processor adjusts the clock according to the synchronization message indicating the earliest time among the synchronization messages broadcast periodically within the system. As a result, the fastest running clock will control the time in the system.

In addition, the Journal of Association for Computing Machinery
Machinery) Vol.32, No.1, January 1985,
The article “Synchronizing Clocks in the Presence of Faults” is listed on p.52-78.
The clock synchronization method introduced in "Presence of Faults" (Reference 3) is a synchronization method using completely distributed control in which all processors periodically communicate the time of each other's processors.

(Problem to be solved by the invention) UNIX operating system mentioned above 4.3
In the BSD TENPO synchronization method, a master node is essential. Therefore, in the event of a failure of the master node, a method of acting as a master node is required so that another node can perform the function of the master node. In addition, since one master node queries the clocks of all nodes, as the number of nodes increases, the amount of communication to the master node increases, and the task of calculating the average time of all nodes increases. do.

On the other hand, in the method described in Reference 2 which employs distributed control, although it is distributed, one processor with the fastest clock controls the time within the system. Furthermore, in the method of Reference 3, since all processors communicate with each other, communication overhead becomes a problem when applied to an actual system.

In the present invention, there is no need to provide a processor for centralized control, and even if the number of processors in the system increases, communication messages are not concentrated on a certain processor, and the total number of messages in the system can be reduced compared to the previous method. It is an object of the present invention to provide a clock synchronization method in a distributed control type multiprocessor system that can reduce the number of clocks compared to the previous method.

(Means for Solving the Problem) According to the present invention, there is provided a clock synchronization method for a multiprocessor system consisting of n processors, wherein the processor is provided with a clock indicating time, and the clock is predetermined. when the time indicated by the clock is indicated, randomly selecting m processors from among the n processors, reading clock information of the m processors, and controlling the clock based on the time of the m processors. In the clock synchronization method in a multiprocessor system, the processor may read out the clock information when the time at which the clock information is obtained is different from the time indicated by the processor's own clock by a predetermined value or more. This provides a clock synchronization method in a multiprocessor system that is characterized in that the time is not used.

(Operation) The principle of the present invention will be explained with reference to FIG. FIG. 3 shows a specific example of a multiprocessor system. Each processor 301, 302, 30
3, 304, and 305 are equipped with clocks that indicate their own time. Further, each processor is connected to each other by a logical communication path 306 so that clock information of any processor can be read out.
In a multiprocessor system that does not have a shared memory that can be commonly accessed by each processor, the clocks of each processor do not indicate the same time when the system is in its initial state. Moreover, although clocks that start from the same value measure time at roughly the same rate, they gradually shift as time passes. Therefore, each processor adjusts the clocks of each other through message communication according to this synchronization method described below. As a result, the clocks of all processors are controlled to point to the same time within a certain synchronization accuracy.

In this synchronization method, each processor clocks its own processor at a predetermined time.
Among the n processors in the system, m processors are randomly selected and the clock information of the processors is queried. Furthermore, it resets its own clock value based on the inquired clock information. For example, processor 301 randomly selects a processor from among the five processors in the system each time its own clock reaches a predetermined time such as 1:00, 2:00, and 3:00. At some point, the processor 301 selects the processors 302, 302, 304 and uses the communication path 30.
These processors are queried for their clock values via 6. Based on the obtained clock values of the three processors, processor 301 calculates the average value of these clock values, and resets its own clock value based on the average value. In this case, if the time of the processor obtained from the clock information read from the processor is more than a predetermined value away from the time indicated by its own clock, the clock information is ignored and the average value is calculated. demand.
For example, if the determined time of the processor 301 is more than a certain value away from its own time, the processor 301 removes the clock value of the same processor and calculates the average time based on the clock values of the processors 302 and 304. calculate. Furthermore, if the average value of the times of these processors is δ ahead of the time indicated by the own clock, the difference δ is added to the own clock, and the average value of the times of these processors is ahead of the time indicated by the own clock. If it is also behind by δ, its own clock is stopped by δ. The above operations are repeated by all processors each time their own clock reaches a predetermined time.

In this way, all processors are on completely equal footing and execute exactly the same algorithm.
At this time, each processor performs synchronous control based on the clock information of m processors, which reduces the amount of communication compared to the conventional method, and also allows a processor to transmit abnormal clock information if it is in a failure state. Even in the case of a faulty processor, it is not affected by the faulty processor. Furthermore, since the m processors are selected at random at this time, by repeating the synchronization control, the clock information of all non-faulty processors in the system is reflected in the synchronization control. A simulation experiment has shown that the synchronization range of the processor clock is m independent of the value of n.
It was confirmed that the convergence satisfies sufficient synchronization accuracy when = 2 to 10.

As described above, since a specific processor does not define a common time and perform synchronous control, a failure of a certain processor will not cause a fatal failure to the system.

(First Embodiment) FIGS. 1a and 1b show a first embodiment of an algorithm for realizing the clock synchronization method according to the present invention.

Figure 1a shows a synchronous control algorithm that the processor executes when its own clock indicates a predetermined time; for example, when its own clock indicates 1:00, 2:00, 3:00, etc. It is executed at every set time. Figure 1b is
The algorithm executed when a certain processor executes the synchronous control algorithm and receives a message from the same processor is shown. Note that these two algorithms may be executed in parallel, and a request to send clock information to itself may be generated.

The processor detects in control block 101 shown in FIG. 1a an interrupt from a clock that is set to occur when its own clock reaches a predetermined time. Detection of an interrupt from this clock activates the subsequent synchronous control algorithm. That is, control block 102 randomly selects m processors from n processors, and control block 103 subsequently sends a message requesting each of these processors to transmit clock information.

Each processor also executes the algorithm shown in Figure 1b in parallel.
10, it is possible to detect a reception interrupt that occurs when a clock information transmission request message is received from the processor. That is, when a certain processor transmits a message in control block 103 of FIG. 1a, the processor that received the message detects a reception interrupt in control block 110 of FIG. control block 1
At step 11, clock information is sent to the processor that sent the message. The clock information sent by the processor at this time is the value indicated by the clock itself, but if the processor requesting clock information records its own time in the request message, the difference between the clock and the requesting processor's time is recorded. You may send it as information.

In this way, the processor that sent the clock information transmission request message receives clock information from m processors. Control block 104
In , the time of each processor is determined based on the clock information from these m processors, and compared with the own time, and from the own time,
A check is made to see if there is a time that is farther away than a predetermined value, and a time that is farther from the user's time than the predetermined value is not used in subsequent processing. In the subsequent control block 105, an average clock value is calculated based on the clock information of these processors, and the average time of the m processors is subtracted from the time indicated by the clock of the own processor to obtain a difference δ.

Based on the difference .delta. from the average time of the m processors obtained as described above, the processor sets its own clock value in the following manner from control block 106 onward. That is, if the time indicated by the own processor's clock is equal to the average time (δ=0), the process returns to control block 101. If the time indicated by the own clock is later than the average time (δ<0), the control block 107 adds the difference δ to the own clock to advance the time, and then the control block 10
Return to 1. Furthermore, if the time indicated by its own clock is ahead of the average time (δ>0), control block 108 stops its own clock by the difference δ, delays the time, and then returns to control block 101. . In either case, control block 101 detects an interrupt from the next clock occurring at a predetermined time.

The algorithm described above is executed by all processors.

(Second Embodiment) FIGS. 2a and 2b show a second embodiment of an algorithm for implementing the clock synchronization method according to the present invention.

In a communication network system, which is an example of a multiprocessor system, when processors read each other's clock information, there is a communication delay between the processors, or the time required for communication processing and average time calculation is affected by the time accuracy of the clock. It is possible that it will be larger in comparison. In order to prevent the clock synchronization control from being adversely affected by such processing overhead, the processor time at which the clock information is read is defined using an algorithm as described below.

Figures 2a and b illustrate the same algorithm. The algorithm shown here is based on the control blocks 102, 103, 1 of FIG.
This algorithm corresponds to 04 and 105. Specifically, it randomly selects a processor, repeatedly sends a message requesting the processor to send clock information m times, and then sends a message that requests the processor to send clock information m times. This figure shows control to calculate the difference δ between the time indicated by the clock of the own processor and the average time based on the clock information from the processor of the processor.
The procedure is the same as that of control block 106 and subsequent steps in FIG. 1a.

The connector 200 shown in FIG. 2a is connected to the rear of the control block 101 of FIG. 1a. In control block 201, a value O is assigned to a variable k that counts the number of processors to be selected, and in control block 202, processor i is randomly selected from n processors in the system. Next, in control block 203, the time indicated by the clock in its own processor at this time is substituted into variable Ti,0, and in control block 204, a message is sent to request processor i to send clock information. Thereafter, in control block 205, 1 is added to a variable k that counts the number of randomly selected processors. In the control block 206, the variable k is compared with the value m, and if k<m, the process returns to the control block 202, and if K=m, the process continues to the connector 207, which is connected to the next process.

Connector 207 is connected to the front of control block 208 shown in FIG. 2b. control block 208
Now, as explained in FIG. 2a, a response to the clock information request message sent to m processors is awaited. Due to variations in the transmission times of the request messages and variations in communication delays, responses from each processor also arrive at different times. When a response from a processor i arrives, a control block 209 assigns the time at which the response arrived to a variable Ti,1, and a control block 210 assigns the time of the processor i recorded in the response message to a variable Ti,1. Assign to Ti. Thereafter, 1 is subtracted from a variable k that stores the number of processors randomly selected and sent the request message, and the value of the variable k is compared in control block 212. If K>0, control block 20
The process returns to step 8 to wait for responses from other processors, and if responses from all processors are received and k=0, control block 213 is executed. Note that there may be cases where responses are not obtained from all the processors even after a certain period of time has elapsed due to message loss or the like. In this case, control block 213 may be executed based on already obtained clock information. In the same control block 213, a variable Ti,0 indicating the time when processor i was selected is set.
Based on the variable Ti,1 indicating the time when the response from processor i arrived, and the variable Ti indicating the time of processor i recorded in the response message from processor i, the own processor calculates the time Ti,0.
The time of processor i at the time is predicted, and the difference δi between the time of processor i and the time of its own processor is determined. That is, assuming that the communication delay of a message from processor a to processor i is equal to the communication delay of a message sent from processor i to processor a almost at the same time, the time of processor i is predicted according to the following equation. The time of processor i is Ti - (Ti, 1 - Ti, 0)/2 (1), so the difference between the time indicated by its own processor's clock and the time indicated by processor i's clock is δi
is shown as follows.

δi=Ti,0−{Ti−(Ti,1−Ti,0)/2}
(2) The control block 214 removes δi larger than a predetermined value from among the m δi obtained in this way.
This has the same effect as No. 4, and is intended to prevent the clock from being affected by abnormal clock information received from a processor in a faulty state. Further, in control block 215, the average value of the obtained δi is determined, and the same value is set as the difference δ from the average time of m randomly selected processors. In addition, connector 2
16 is connected to the front part of FIG. 1a, and the already explained control block 105 and subsequent steps of FIG. 1a are executed based on the calculated difference δ from the average time.
This algorithm predicts processor time by taking into account communication delays between processors, making it possible to eliminate the effects of communication delays.

(Effects of the Invention) As described above, by using the clock synchronization method of the present invention, in a multiprocessor system, all processors can be operated equally and the clocks of each processor can be synchronized. can be controlled to point to a common time within a certain range. Since there is no need for a processor that performs centralized control, a failure in a particular processor will not cause a fatal failure to the system, and high reliability can be ensured. moreover,
The information required by each processor is only the time information of m processors, and according to a simulation experiment,
Sufficient synchronization accuracy can be obtained when m=2 to 10. Therefore, since it is not necessary to collect clock information of all processors, the processing time required for synchronous control does not increase even when the number of processors increases. Furthermore, by removing values that are more than a certain value away from the own time from among the collected processor times, the processor is not affected by a processor in a faulty state. Furthermore, since these processors are periodically and randomly selected, synchronization control is performed based on clock information of all processors.

As described above, the effects obtained by the present invention are significant.

[Brief explanation of the drawing]

Figures 1a and b are flowcharts showing a first embodiment of the present invention, and Figures 2a and b show an algorithm for determining processor time in the second embodiment when communication delays are taken into account. Figure 3 is
1 is a diagram showing an example of a multiprocessor system. In the figure, 101-111 and 201-
215 is a control block, 200, 207, 216
is a connector, 301 to 305 are processors, 306
indicates a logical communication path between processors.

Claims (1)

[Claims] 1. This is a clock synchronization method for a multiprocessor system consisting of n processors, wherein the processor is equipped with a clock that indicates time, and when the clock indicates a predetermined time, one of the n processors is synchronized. A clock synchronization method in a multiprocessor system characterized in that m processors are randomly selected, clock information of the m processors is read out, and the clock is controlled based on the time of the m processors. The processor is characterized in that if the time obtained based on the read clock information is different from the time indicated by the processor's own clock by a predetermined value or more, the processor does not use the time. Clock synchronization method in multiprocessor systems.