JPH02114359A - Clock synchronizing method for multiprocessor system - Google Patents

Abstract

PURPOSE:To allow the clocks of all processors to point out the same time within the range of a certain synchronizing accuracy by mutually adjusting the clocks by message communication. CONSTITUTION:After measuring a random time within a time interruption interval, a timer generates a time-out, and at the time of generating a time interruption, each of processors 301 to 305 starts the timer. At the time of generating a time-out, m processors out of n processors are selected at random and self-clocks are sent to the m processors. Each of the processors 301 to 305 controls the clock shown in each parentheses based upon all clock information arriving every generation of a time interruption. Even when the number of processors in the system is increased, the increment of processing overhead due to the sharp increment of the number of messages is not generated and the total number of messages in the system can be reduced.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention is a multiprocessor system in which each processor does not have a shared memory that can be accessed in common, and in which each processor mutually adjusts the clocks that each processor has to indicate time. This paper relates to a clock synchronization method for

[Conventional technology]

In a multiprocessor system, it is necessary to synchronize the clocks of each processor that makes 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 file versions based on the creation and editing times recorded in each file. In addition, if each processor accumulates its own history information based on a time common to the system, it will be possible to know the order in which failures were detected when they occur, and to identify the location of the failure. You can obtain useful information for this purpose.

Even in a communication network system, which is an example of a multiprocessor system that does not have a shared memory, a synchronization method is required so that the clocks of each communication node indicate a common time. For example, at the 6th International Conference on Distributed Computing Systems held in May 1986,
e on DI STRI B UTE D CO
MPUTING SYSTEMS) Proceedings 2゜36
4-371, the paper “An Election Algorithm for Distributed Clock Synchronization Programs (An
Election Algorithm for a
Distributed C1ock 5syncron
izati'on Program) J (Reference 1
) The clock synchronization method TEMPO introduced in
It is implemented in a network running on the NIX operating system 4.3BSD. In the above-described system, one node serving as a mask queries all nodes for time at predetermined time 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.

In addition, the 16th Annual International Symposium on Fault-Tolerant Computing (Annual Intel) was held in 1986.
National Symposium on
F A U L T -T 0LERANT C
OMPUTING) Digest Paper P, 218
-223, the paper “Clock Synchronization in the Presence on Omission and Performance Faults and Processor Joins” (CLOCK 5YNCHR)
ONIZATION IN THE PRESENCE
OFO Former 5SION AND PERFORMAN
CE FAULTS, AND PROCESSOR JOI
The tarock synchronization method introduced in NS)J (Reference 2) uses a mask and a
It uses distributed control rather than slave-type control.

In this method, the processor adjusts its clock according to the synchronization message that indicates the fastest time among the synchronization messages that are periodically broadcast within the system. It will control the time of the day.

In addition, the Journal on Association for Computing Machinery (J.

Urnal of As5ocation for
Computing Machinery), Vol.
32. No, 1. January 1985. p.52
-78, the paper “Synchronizing Clocks in the Presence on Faults”
Synchronizing Clocks in th
The clock synchronization method introduced in "Presence of Faults" (Reference 3) is a synchronization method based on completely distributed control in which all processors periodically communicate the time of each other's processors. Issues to be solved] UNIX operating system 4.3BS mentioned above
In D's TEMPO 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 Document 2 that employs distributed control, although it is distributed, one processor with the fastest clock controls the time within the system. Further, in the method of Document 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, so 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 becomes extremely large. An object of the present invention is to provide a clock synchronization method in a distributed control multiprocessor system, which can reduce the total number of messages in the system compared to conventional methods without increasing processing overhead.

[Means to solve the problem]

According to the present invention, in a clock synchronization method for a multiprocessor system consisting of n processors, each processor has a clock indicating the time, a timer measuring random time, and means for generating time interrupts at predetermined intervals. The timer times out after measuring a random time within the interval of the time interrupt, and in each processor, when the time interrupt occurs, the timer starts, and at the time when the time out occurs, the n processors start the timer. Randomly select m processors from
In a multiprocessor system, the clock is transmitted to each processor, and each processor controls its own clock based on all the clock information that arrives each time the time interrupt occurs. A clock synchronization method is obtained.

[Effect]

In a multiprocessor system that does not have a shared memory that can be commonly accessed by each processor, when the system is in its initial state, the clocks of each processor do not indicate the same time, and even if the clocks start from the same value, Although the time is measured at the same rate, it gradually deviates as the time passes.Therefore, each processor needs to adjust its clocks with 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.

The principle of the present invention will be explained with reference to FIGS. 2 and 3. FIG. 3 shows a specific example of a multiprocessor system. Each processor 301, 302. 303, 304.
305 is provided with a clock that indicates its own time, and generates a time interrupt based on its own clock. Furthermore, each processor is connected to each other by a logical communication path so that clock information of any processor can be read out.For example, processor 303 and processor 304 are connected by a communication path 306.

Furthermore, each processor is equipped with a timer capable of measuring random time, and can measure random time within a predetermined time range.

FIG. 2 shows a timing chart for a certain processor i, and describes the principle of the clock synchronization method of the present invention while explaining the operations of the above-mentioned time interrupt and random timer.

In Figure 2, the time from one interrupt to the next is the clock synchronization control period, and for example, in this example, 1
It's time. Now, as shown in the figure, the time interrupt indicating the start of the k-th clock synchronization control period is set to O:00.
, indicates the end of the clock synchronization period at address k, and (
The second time interrupt indicating the start of the (k+1)th clock synchronization period is set to 00. On processor i, O:00
When a time interrupt is detected, the timer is activated. The timer is set so that a timeout occurs at a random time during the one hour synchronization control period.

Since all processors in the network independently perform the same timer activation and random timeout generation processing, if the total number of processors in the network is n, these n processors will cause a timeout during each synchronization control period. In particular, the timeout example shown in FIG. 2 is an example in which a timeout occurs during the synchronous control period.

In 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 clock information of the own processor is sent to the m processors. On the other hand, each processor receives the clock information addressed to it,
At the end of each synchronization control period, processing is performed based on the clock information that has already been received.

This synchronization method will be explained using the network example shown in FIG. In the explanation, the number of time interrupts in each processor is 1:
Set to 00. Each processor starts a timer when it detects its own time interrupt, and when it times out,
m processors are selected at random, and clock information stamped with the time at which the timeout occurred is notified to the processors. Furthermore, the processor that receives the clock calculates the differences between all the received clock values and the time of its own processor that received the clock value, and adjusts the clock based on the average value Δ of the differences. That is, if Δ is positive, Δ is added to the own clock value, and if Δ is negative, the own clock is stopped by Δ. Assuming that each processor causes a timeout according to the timeout distribution described earlier, clock information will be received from an average of m processors per control of each processor.

Each processor adjusts its own clock value to the average value of the clock values from the m processors.

For example, before the clock control according to the present invention is applied,
It is assumed that each processor has a lock value as shown in FIG. 3(a). For example, check the timeout time of the processor 301 using the clock of the processor 301:
58. The timeout time of the processor 302 is set to 0:56 based on the clock of the processor 302. Ignoring communication delays and clock deviations caused by the clock inclination of each processor, it is assumed that the clock value of the processor 301 reaches O:58 and, for example, three processors are randomly selected from among the five processors. , processors 302, 303, and 305, and sends the clock value (0:5g>) to the three processors.

The time indicated by each processor when the processor 301 sends out its clock value is shown in FIG. 3(b).

When each processor receives the clock value of the processor 301, it calculates the difference between it and its own clock value. The difference value is +6 for processor 302 and +6 for processor 303.
4, the processor 305 has +3. Next, when the clock value of processor 302 reaches O:56, three processors are randomly selected on the same machine.0 For example, if processors 301, 303, and 304 are selected, Own clock value O: 5
Notify 6.

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

In the above description, the clocks of each processor were shown in detail only when the processors 301 and 302 timed out, but the other processors similarly perform synchronous control when a timeout occurs.

Thus, by the end of the concurrent control period, each processor receives clock information from an average of three processors.

It can be seen that by periodically repeating the above control for each processor, the clock values of all processors are adjusted to the same value.

The above control is repeatedly performed by all processors according to time interrupts based on their own clocks. Of course, since the m processors selected by each processor at the time-out time are randomly selected, the number of clock information received each clock synchronization period is random as a result.

In this way, all processors are on a completely equal footing and implement exactly the same algorithms.

At this time, since the clock value is sent only to randomly selected processors, the amount of communication can be reduced compared to the conventional method. Further, by controlling the system time using the average time of a plurality of processors instead of only one processor controlling the system time, fault-tolerant time control becomes possible. Furthermore, the degree of fault tolerance can be flexibly controlled by changing the number of randomly selected processors. Furthermore, since the time at which the clock information is sent out is random within a certain range (during the clock synchronization control period), it is possible to reduce the possibility that the network will become overwhelmed by the clock information sent out by a plurality of processors.

〔Example〕

FIGS. 1(a) and 1(b) show an example of a flowchart of control executed by each processor to implement the method of the present invention. FIG. 1(a) shows clock information transmission control. This is an example of a flowchart, and FIG. 1(b) is an example of a flowchart showing reception control of clock information.

First, the transmission control flowchart of FIG. 1(a) will be explained. In each processor, when a time interrupt is detected in block 100, a timer is activated in block 101. Block 102 detects the occurrence of a timeout of the timer, and if a timeout is detected, the process proceeds to block 103, where m processors are randomly selected from among the n processors in the system.

After that, in block 104, clock information stamped with the time when the timeout occurred is sent to the randomly selected m processors, and the transmission control in this synchronization control period is ended, and the process returns to block 100 and the next step is to In the reception control shown in FIG. 1(b), in which a time interrupt is waited for during the synchronization control period, block 111 receives the clock information sent from another processor, followed by block 112.
, the difference between the received clock value and its own clock value is calculated and stored. In block 113, a time interrupt indicating the start of the next synchronous control cycle is detected, and if no time interrupt is detected, clock information is received again. When a time interrupt is detected in block 113, the process goes to block 114 and calculates the average value of the differences (calculated in block 112) between all the received clock information and its own clock value. In the subsequent block 115, control is switched depending on the sign or negative of the calculated Δ, and if
If Δ is positive, the own clock is adjusted by adding Δ to the own clock value in block 116. If Δ is negative, the own clock is stopped by Δ and the own clock is adjusted in block 117. When the adjustment processing in block 116 or 117 is completed, the reception processing in this periodic control period is completed, and the process returns to block 111 to wait for a time interrupt indicating the start of reception control in the next clock periodic control period.

〔Effect 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 without providing a processor that performs airborne control, and the clocks of each processor can be set to a common time. Can be controlled to point. Since each processor notifies clock information to a randomly selected processor every synchronization control period, a failure of a particular processor will not cause a fatal failure of the system, and high reliability can be ensured. Also, the degree of reliability is
It is possible to flexibly change the number m of processors to be randomly selected by controlling it. Also, it does not perform synchronous control using the clock values of all processors,
Since control is performed using the clock values of the partial processor set, even when the number of processors increases, the processing time required for synchronization control does not increase significantly.
Since the timing of transmitting clock information is randomly distributed during the synchronization control period, it is possible to avoid network congestion caused by transmitting clock information.

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

[Brief explanation of the drawing]

FIGS. 1(a) and (b) are flowcharts showing an embodiment of the clock synchronization method according to the present invention, FIG. 2 is a control timing chart of the clock synchronization method according to the present invention, and FIGS. 3(a) and (b). , (c) are diagrams showing an example of a multiprocessor system and an example of time of each processor for detailed explanation of the present invention. 100-104.111-117... control block,
301 to 305...Processor, 306...Logical communication between processor 303 and processor 304≧Processor 36/List (EL) Free H3 sensor 31) 1 Mawari (b)

Claims (1)

[Claims] 1. In a clock synchronization system for a multiprocessor system consisting of n processors, each processor generates time interrupts at predetermined intervals using a clock indicating time and a timer measuring random time. means, the timer times out after measuring a random time within the interval of the time interrupt, and in each of the processors,
When the time interrupt occurs, the timer is started, and at the time when a timeout occurs, m processors are randomly selected from the n processors, and the own clock is sent to the m processors. Furthermore, each processor controls its own clock based on all the clock information that arrives each time the time interrupt occurs. 2. In the clock control of each processor, if the average time of all the received clock information is Δ ahead of the time indicated by its own clock, add Δ to its own clock, and set the average time to its own clock. In the multiprocessor system according to claim 1, the clock in the multiprocessor system according to claim 1 is characterized in that when the timer is delayed by Δ from the time indicated by the clock, the clock stops its own clock until the timer notifies that the time Δ has elapsed. Synchronous method.