JPH07117939B2 - 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 entitled "An Election Algorithm for a Distributed Cl" (p.364-371) is published.
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 system described above, one node that is the master is
All nodes are inquired about the time, and the average time is calculated 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 Reference 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.

In the present invention, it is not necessary to provide a processor for performing centralized control, so that one processor does not control the time in the system, and even when the number of processors in the system increases, the number of communication messages is extremely large. (EN) Provided is 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 due to the above.

[Means for Solving the Problems]

According to a first aspect of the present invention, in a clock synchronization method for a multiprocessor system consisting of n processors, each processor generates a clock indicating a time, a timer for measuring a random time interval, and a time interrupt at a predetermined interval. The timer times out after measuring a random time interval within the time interrupt interval, each processor starts the timer when the time interrupt occurs, and the time when the time out occurs. , Randomly select m processors from the n processors, and send the time indicated by its own clock to the m processors. Further, each processor generates the time interrupt. It is characterized in that the time of each clock is controlled based on all the times of arrival at each time.
Also, in the second invention, in the time control of the clocks of the respective processors in the first invention, the average time of all the received times is Δ more than the time indicated by the own clock.
If you are moving forward, add Δ to the time indicated by your own clock, and the average time is Δ than the time indicated by your own clock.
If it is delayed, it is characterized in that its clock is stopped until the timer notifies the elapse of the time Δ.

[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, it is necessary for each processor to 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 clock of any processor can be read. 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 interrupt to the next is the clock synchronization control period, for example, 1 in this example.
It's time. Now, as shown in the figure, the time interrupt indicating the start of the k-th clock synchronization control period is 0:00, K
Indicates the end of the clock synchronization period of the address and (k +
1) The second time interrupt indicating the start of the 1st clock synchronization period is 1:00. In the processor i, when the time interrupt of 0:00 is detected, the timer is activated. The timer is set so that a timeout occurs at a random time during the synchronous control period of one hour.

Since all processors in the network independently perform the same timer activation and timer out generation processing, assuming that the number of all processors in the network is n, these n processors cause a timeout during each synchronous control period. It will be. The time-out example shown in FIG. 2 is an example in which a time-out occurs during the synchronous control period.

According to the method of the present invention, m processors are randomly selected from n processors in the system at the time when a timeout occurs, and the time indicated by the clock of the own processor is sent to the m processors. is there. on the other hand,
Each processor receives the time when it arrives at itself, and at the end of each synchronization control period, the processing is performed based on the already received time.

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, at the time of timeout, it randomly selects m processors and notifies the processor of the time indicated by the clock at the time of the timeout. Further, the processor that receives the time takes the difference between all the received times and the time of the own processor that received this time, and adjusts the clock based on 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, the time is received from an average of m processors per control of each processor. Each processor will adjust its own clock value to the average value of the clock values from the average m 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. For example, looking at the time-out time of processor 301 with the clock of processor 301, 0: 5
8, processor 302 timeout time processor 302
It is set to 0:56 based on the clock. Ignoring the clock delay caused by the communication delay and the clock inclination of each processor, the time indicated by the clock of the processor 301 is 0:58.
To reach. It is assumed that, for example, three processors are randomly selected from the five processors.
302, 303, 305 are selected, and the time (0:58) indicated by the clock of the processor 301 is sent to the three processors.

The time indicated by the clock of each processor when the processor 301 transmits the time indicated by the clock is shown in FIG.
Shown in.

Upon receiving the time indicated by the clock of the processor 301, each processor takes the difference from the time indicated by its own clock. The difference value is +6 for processor 302, processor 3
It is +4 for 03 and +3 for processor 305. continue,
When the processor 302 clock reaches time 0:56,
Similarly, three processors are randomly selected.
For example, if you select processors 301, 303, 304,
The three processors are notified of the time 0:56 indicated by their own clocks.

The time indicated by the clock of each processor at this time is shown in FIG. 3 (c). The difference value in each processor is −6 in the processor 301, −2 in the processor 303, and +2 in the processor 304. Each processor adjusts the clock time shown above based on the average value of the obtained difference values.

In the above description, the clock of each processor is shown in detail only when the processors 301 and 302 have timed out, but other processors similarly perform synchronization control when a time-out occurs.

Therefore, by the end of the synchronous control period, each processor receives the time from an average of three processors.

It can be seen that the above control is periodically repeated by each processor so that the times indicated by the clocks 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, since the m processors selected by each processor at the time-out time are randomly selected, the number of times received in each clock synchronization period becomes random as a result.

In this way all processors are in a perfect peer position and implement the exact same algorithm. At this time, since the time is sent only to the randomly selected processor, 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 number of processors randomly selected. Further, since the time at which the time indicated by the clock is sent is random within a certain range (during the clock synchronization control period), it is possible to reduce the possibility that the network will be in a congestion state depending on the time sent by a plurality of processors.

〔Example〕

FIGS. 1 (a) and 1 (b) show an example of a flow chart of the control executed by each processor in order to realize the method 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 at the time.

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 timeout of the timer is detected, and if timeout is detected, block 103
Proceed to and randomly select m processors from among n processors in the system.

After that, at block 104, the time indicated by the clock at the time when the timeout occurs is sent to the m randomly selected processors, the transmission control in this synchronous control period is completed, and the process returns to block 100, and Wait for the time interrupt in the synchronous control period of. In the reception control of FIG. 1B, the block 111 receives the time sent from 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. In block 113, the time interrupt indicating the start of the next synchronous control cycle is detected, and if the time interrupt is not detected,
The time is received again. When the time interrupt is detected in block 113, the process goes to block 114 and the difference between all the received time and the time indicated by the own clock (block 112).
Calculated in step 1). Following block
At 115, the 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 own clock. If Δ is negative, in block 117, the own clock is stopped by Δ and the own clock is adjusted. When the processing of block 116 or 117 ends, the reception processing in this cycle control period ends, and the process returns to block 111 to wait for a time interrupt indicating the start of 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. Since each processor reports the time to the processor randomly selected for each synchronization control period, the failure of a specific processor does not cause a fatal failure of the system, and high reliability can be secured. Further, the degree of reliability can be flexibly changed by controlling the number m of processors randomly selected. In addition, synchronization control is not performed using the time indicated by the clocks of all processors,
Since the control is performed using the time indicated by the clock of the partial processor set, the processing time required for the synchronous control does not extremely increase even when the number of processors increases. Furthermore, since the timing for transmitting the time is randomly distributed during the synchronous 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. And the timer times out after measuring a random time interval within the time interrupt interval, and in each of the processors, the timer is started when the time interrupt occurs, and at the time when the time out occurs. At random, m processors are randomly selected from the n processors, and the time indicated by the own clock is sent to the m processors. Further, each processor receives the time interrupt every time the time interrupt occurs. Multiprocessor system characterized by controlling the time of its own clock based on all the times of arrival Clock synchronization method in the arm. 2. In the time control of the clock of each processor, if the average time of all the received times is ahead of the time indicated by its own clock by Δ, Δ is added to the time indicated by its own clock. The addition, 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 method for synchronizing a clock in a multiprocessor system according to the paragraph.