JPH07117940B2 - Clock synchronization method in multiprocessor system - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial field of application] The present invention adjusts the clocks that each processor has to indicate the time in a multiprocessor system that does not have a shared memory that each processor can commonly access. The present invention relates to a clock synchronization method for performing.

[Conventional technology]

In a multiprocessor system, it is necessary to synchronize the clocks of the processors that make up the system so as to indicate a time common to the entire system. For example,
In the distributed filing system, a common time is required among the processors in order to identify the version of the file based on the creation and edit 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 faults were detected when the fault occurred, and identify the location of the fault. You can get powerful information for.

Even in a communication network system, which is an example of a multiprocessor system having no shared memory, a synchronization method is required so that clocks of respective communication nodes indicate a common time. For example, the 6th International Conference on Distributed Computing Systems (In
ternational Conference on DISTRIBUTEDCOMPUTING SYS
The paper "An Election Algorithm for Distributed Clock Synchronization Program (An Election Algorithm for a Distributed Cl
ock Syncronization Program) ”(Reference 1), the clock synchronization method TEMPO is implemented in a network operating on the UNIX operating system 4.3BSD. In the above-mentioned system, one master node inquires of all the nodes about the time every predetermined time, and calculates the average time based on the obtained time of each node. Thereafter, the clock adjustment instruction is given to all the nodes, and each node adjusts the clock according to this instruction.

In addition, the 16th Annual International Symposium on Fault Tolerant Computing (Annual International Sympo
sium on FAULT-TOLERANT COMPUTING) digest paper, pages 218-223, "Clock Synchronization in the Presence of.
Omission and Performance Faults
And Processor Joins (CLOCK SYNCHRONIZAT
ION IN THE PRESENCE OF OMISSION AND PERFORMANCE FA
ULTS, AND PROCESSOR JOINS) ”(reference 2) uses distributed control rather than master-slave control as in“ TEMPO ”described above. In the same system, the processor adjusts the clock time according to the synchronization message that indicates the earliest time among the synchronization messages that are regularly broadcast in the system. As a result, the fastest running clock will dominate the time in the system.

In addition, the Journal of Assoc for Computing Machinery (Journal of Assoc
iation for Computing Machinery), Vol.32, No.1, Janua
RY 1985, p.52-78, "Synchronizing Clocks in the Presence of
Faults) ”(Reference 3) is a synchronization method based on complete distributed control in which all processors periodically communicate with each other's time.

[Problems to be Solved by the Invention]

UNIX operating system 4.3BSD TEMPO mentioned above
A master node is indispensable in the synchronization method of. Therefore, when the master node fails, a method of acting as the master node is required so that the other nodes can function as the master node. Also, since one master node inquires about the clocks of all the nodes, if the number of nodes increases, the communication volume to the master nodes increases and the work to find the average of the time of all nodes also increases. To do.

On the other hand, in the method described in the document 2 which adopts the distributed control, although it is distributed, one processor having the fastest clock has the result of controlling the time in the system. Further, the method of Document 3 has a problem of communication overhead when applied to an actual system because all the processors communicate with each other.

An object of the present invention is that it is not necessary to provide a processor that performs centralized control, so that one processor does not control the time in the system, and the number of messages for communication increases even when the number of processors in the system increases. It is an object of the present invention to provide a clock synchronization method in a distributed control type multiprocessor system capable of reducing the total number of messages in the system as compared with the conventional method without increasing the processing overhead extremely.

[Means for Solving the Problems]

According to a first aspect of the present invention, in a clock synchronization method for a multiprocessor system including n processors, each processor generates a clock indicating a time, a timer for randomly measuring a time interval, and a time interrupt at a predetermined interval. The timer times out after measuring a random time interval within a predetermined time range, and in each of the processors, the timer is activated when the time interrupt occurs, and the timeout occurs. If the time is before the time interrupt, the time when the timeout occurs sends out the time indicated by its own clock to all the processors, and further, each processor
Each time the time interrupt occurs, the time of its own clock is controlled based on all the times arriving from other processors. In a second aspect of the invention, in the time control of the clock of each processor in the first aspect, the average time of all the times received from the other processors is advanced by Δ from the time indicated by the own clock. If it is, add Δ to the time of its own clock, and if the average time is delayed from the time indicated by its own clock by Δ, stop its own clock until the timer notifies the passage of time Δ It is characterized by

[Action]

In a multiprocessor system that does not have a shared memory that can be commonly accessed by the processors, the clocks of the processors do not show the same time when the system is in the initial state. Moreover, the clocks started from the same value measure time at about the same rate, but they gradually shift with the passage of time. Therefore, each processor must adjust the clocks by message communication with each other according to the present synchronization method described below.
As a result, the clocks of all the processors are controlled to point to the same time within a certain synchronization accuracy range.

The principle of the present invention will be described with reference to FIGS. FIG. 3 shows a specific example of the multiprocessor system. Each of the processors 301, 302, 303, 304, 305 has a clock indicating its own time, and generates a time interrupt based on its own clock. Further, the processors are mutually connected by a logical communication path so that the time indicated by the own clock of any processor can be notified. For example, the processor 303 and the processor 304 are connected by a communication path 306. Further, each processor is provided with a timer capable of measuring a random time interval, and can measure the random time interval within a predetermined time range. FIG. 2 shows a timing chart in a certain processor i, and the principle of the clock synchronization method of the present invention will be described while explaining the operations of the time interrupt and the timer.

In FIG. 2, the time from one time interrupt to the next time interrupt is a clock synchronization control period, which is, for example, 1 hour in this example. Now, as shown in the figure, k
A time interrupt indicating the start of the th clock synchronization control period
At 0:00, the time interrupt indicating the end of the clock synchronization period at address k and the start of the (k + 1) th clock synchronization period is set to 1:00. In the processor i, when the time interrupt of 0:00 is detected, the timer is activated. For example, assume that a timer is set so that a timeout occurs at a random time of 360 minutes. In this way, the probability that a timeout will occur between the 0:00 time interrupt and the 1:00 time interrupt becomes 1/6. Since all the processors in the network independently perform the same timer activation and timeout generation processing, assuming that the number of all processors in the network is n, in the above example, n / 6 on average.
Processor will time out during the clock synchronization control period. In FIG. 2, a timeout example 1 is an example in which a timeout occurs during the clock synchronization control period, and a timeout example 2 is an example in which a timeout occurs after the (k + 1) th time interrupt. is there. However, since the timer is actually restarted at 1:00, the timer started at 0:00 does not time out after 1:00.

In the system of the present invention, as shown in the time-out example 1, the time indicated by the clock at the time when the time-out occurs is sent to all the processors only when the time-out occurs in the clock control period. On the other hand, in each processor, reception processing is performed with respect to the time from another processor that has arrived by the time each time interrupt occurs.

This synchronization method will be described using the network example of FIG. In the explanation, the time interrupt at each processor is 1:00
And When each processor detects a time interrupt of its own processor, it starts a timer, and if the time-out time is measured by its own clock before 1:00, it notifies all the processors of the time indicated by the clock at the time of the time-out. . Also, for processors that received the time before 1:00,
The difference between all the received times and the time indicated by the clock of the own processor at the time of receiving this time is taken, and the clock is adjusted by the average value Δ of the difference.
That is, if Δ is positive, Δ is added to the time indicated by the own clock, and if Δ is negative, the own clock is stopped by Δ. Assuming that each processor causes a time-out according to the time-out distribution described above, an average of n / 6 processors per control for each number of processors n sends its own clock to all the processors. Each processor will adjust its clock time to the average value of the times from this average of n / 6 processors.

For example, before the clock control according to the present invention is applied,
It is assumed that the clock of each processor has a time as shown in FIG. 3 (a). Now, assuming that the processor 301 and the processor 302 caused a timeout before 1:00 of the next clock synchronization control period, the timeout time of the processor 301 is 0:38, the timeout time of the processor 302 is determined by looking at the clock of the processor 301. The clock of the processor 302 is set to 0:46. Neglecting the clock delay caused by the communication delay and the clock inclination of each processor, first the time of the processor 301 is 0: 3.
Reach 8 and send its time (0:38) to all processors.

The time indicated by each processor when the processor 301 sends out the time indicated by the clock is shown in FIG.
As can be seen from FIG. 3B, the clocks of the respective processors all indicate the time before 1:00, and all the processors receive the time from the processor 301. When each processor receives the time of the processor 301, it takes the difference from the time indicated by its own clock.
1 for 0, processor 302 for +6, processor 303 for +4, processor 304 for +8, processor 305 for +2
Becomes Then, when the time indicated by the clock of the processor 302 reaches 0:46, the time indicated by this clock is transmitted, and all the processors receive the time. The time indicated by the clock of each processor at this time is shown in FIG. 3 (c). Also in this case, similarly, the clocks of the respective processors all show the time before 1:00, and the respective processors receive the time from the processor 302. The difference value in each processor is −6 in the processor 301, 0 in the processor 302, −2 in the processor 303,
It is +2 for 304 and -4 for processor 305. Therefore,
Each processor takes the average value of the above difference values, and the values are -3 in the processor 301, +3 in the processor 302, +1 in the processor 303, +5 in the processor 304, and -1 in the processor 305. Based on the average value of this difference value,
If the clock time shown above is adjusted, the clock of the processor 301 is delayed by 3 minutes and the clock of the processor 302 is advanced by 3 minutes when the time interrupt of 1:00 occurs in each processor. The clock of processor 303 is advanced by 1 minute and the clock of processor 304 is 5
It can be seen that the time is advanced by minutes and the times of all the processors are adjusted to have the same value.

The above control is repeatedly performed by all the processors according to the time interrupt based on the own clock. Of course, the time-out time is random in each processor for each clock synchronization period, so that the processors and the number of processors that send out the time indicated by their own clocks for each clock synchronization period will be random as a result.

In this way all processors are in a perfect peer position and implement the exact same algorithm. At this time, only the randomly selected processor sends the time, so that the communication amount can be reduced as compared with the conventional case. Further, not only one processor controls the system time, but the system time is controlled by the average time of a plurality of processors, so that time control with fault tolerance becomes possible. Further, the degree of fault tolerance can be flexibly controlled by changing the probability of occurrence of timeout between time interrupts. In addition, since the time of the clock to be transmitted is random within a certain range (clock synchronization control period),
It is possible to reduce the possibility that the network will be in a congestion state depending on the times sent by the plurality of processors.

〔Example〕

FIGS. 1 (a) and 1 (b) show an example of a flowchart of control executed by each processor to realize the system of the present invention. FIG. 1A is an example of a flowchart showing transmission control at the time indicated by the clock, and FIG. 1B is an example of a flowchart showing reception control of clock information.

First, the transmission control flowchart of FIG. 1A will be described. In each processor, when a time interrupt is detected in block 100, a timer is started in block 101. 1
In block 02, the occurrence of a time interrupt is detected, and if a time interrupt is detected, the transmission control in this synchronous control period is terminated (that is, the processor did not output the time during this period), Returning to block 100, the timer is started again. If block 102 does not detect a time-of-day interrupt, block 103 is entered to detect if the timer set has timed out. if,
If the time-out has not occurred, the process returns to the block 102 and the time interrupt detection is determined.

That is, the loop of block 102 and block 103 continues until either a time interrupt or a time-out is detected, and when a time-out is detected in block 103 (at this time, the time-out is detected before the time-of-day interrupt occurs. ), The time of the clock at the time when the timeout occurs in block 104 is sent to all the processors (that is, it becomes a processor that sends the time in this clock synchronization control period), and transmission control in this synchronization control period is performed. When finished, return to block 100 to wait for a time interrupt indicating the start of the next synchronization control period.

In the reception control of FIG. 1 (b), in block 111,
Receives the time sent by another processor. In the following block 112, the difference between the received time and the time indicated by the own clock is calculated and stored. At block 113, it is determined whether a time interrupt has occurred, and if the time interrupt has not occurred, the time is received again, and this loop is repeated until the reception time window ends.
When it is detected in block 113 that a time interrupt has occurred, the process proceeds to block 114, and the average value of the differences (obtained in block 112) between all the received times and the time indicated by the own clock is calculated. .

In the following block 115, control is switched depending on whether the calculated Δ is positive or negative. If Δ is positive, block 116 adjusts the own clock by adding Δ to the time indicated by the clock. If Δ is negative, at block 117,
The own clock is stopped by Δ and the own clock is adjusted. When the processing of block 116 or 117 is completed, the reception processing in this cycle control period is completed and the process returns to block 110 to start reception control in the next clock cycle control period.

〔The invention's effect〕

As described above, by using the clock synchronization method of the present invention, in a multiprocessor system, all the processors are operated equally without providing a processor for centralized control, and the clocks of the processors point to a common time. Can be controlled. A processor that performs clock synchronization control is randomly selected for each synchronization control period, and high reliability can be secured without causing a fatal failure of the system due to a failure of a specific processor. Further, the degree of reliability can be flexibly changed by controlling the probability that the timeout enters the clock synchronization control section.

Furthermore, a fixed number of processors are not selected for each synchronization control period, but the number of processors that send time for synchronization control is also random, and is given as an average value for each synchronization control period. It is easy to avoid a deadlock condition associated with control. Further, since the synchronous control is not performed using the time indicated by the clocks of all the processors, but the control is performed using the time indicated by the clock of the partial processor set, the synchronous control is performed even when the number of processors increases. The processing time required does not increase extremely.

Furthermore, since the timing for transmitting the time is randomly distributed during the clock synchronization control period, it is possible to avoid the congestion state of the network accompanying the time transmission.

As described above, the effect obtained by the present invention is great.

[Brief description of drawings]

1 (a) and 1 (b) are flowcharts showing an embodiment of the clock synchronization system according to the present invention, FIG. 2 is a control timing chart of the clock synchronization system according to the present invention, and FIGS. 3 (a) and 3 (b). , (C) are diagrams showing an example of a multiprocessor system and time examples of each processor for explaining the principle of the present invention. Control block, 301-305 ... Processor, 306 ... Logical communication path between processor 303 and processor 304.

Claims (2)

[Claims] 1. A clock synchronization method for a multiprocessor system comprising n processors, wherein each processor generates a clock indicating a time, a timer for measuring a random time interval, and means for generating a time interrupt at a predetermined interval. The timer times out after measuring a random time interval within a predetermined time range, and in each processor, when the time interrupt occurs, the timer is started, and the time when the time out occurs. Is before the time interrupt, the time indicated by its own clock is sent to all the processors at the time when the time-out occurs, and further, each processor causes another processor to execute each time the time interrupt occurs. It is characterized by controlling the time of its own clock based on all the times arrived from Clock synchronization method in a multiprocessor system. 2. In the time control of the clock of each processor, when the average time of all the times received from the other processors is advanced by Δ from the time indicated by the own clock, the time of the own clock Is added to Δ, and when the average time is delayed from the time indicated by the own clock by Δ, the own clock is stopped until the timer notifies the elapse of the time Δ. A clock synchronization method in a multiprocessor system according to claim 1.