JPH0528867B2 - - 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,
The 6th International Conference on Distributed Computing Systems was held in May 1986.
COMPUTING SYSTEMS) Proceedings p.364−
371, ``An Election Algorithm for a Distributed Clocks Synchronization Program''
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.3BSD. 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 Exhibition held in 1986
Annual International Symposium on Fault Tolerant Computing
FAULT-TOLERANT COMPUTING) Digest Paper p.218-223 CLOCK
SYNCHRONIZATION IN THE PRESENCE
OF OMISSION AND PERFORMANCE
The clock synchronization method introduced in ``FAULTS, AND PROCESSOR JOINS'' (Reference 2) uses distributed control rather than master-slave type control like ``TEMPO'' 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 paper “Synchronizing Clocks in the Presence of Faults” 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) The UNIX operating system mentioned above
A master node is essential for the 4.3BSD TEMPO synchronization method. 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, 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 can be reduced. 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 the conventional method without causing an excessive increase in processing overhead.

(Means for Solving the Problems) According to the present invention, in a clock synchronization method for a multiprocessor system consisting of n processors, each processor has a clock that indicates the time, a timer that measures random time, and a first and means for generating a second time interrupt, the timer times out after measuring a random time within a predetermined time range, and in each processor, the first time interrupt is generated. If the time when the timeout occurs is between the first time interrupt and the second time interrupt, the timer is activated every time the A clock is sent out, and each processor has a time window including the first and second time interrupts, and controls its own clock based on all clock information arriving during the time window. A clock synchronization scheme in a multiprocessor system is obtained.

(Operation) In a multiprocessor system that does not have a shared memory that can be commonly accessed by both processors, 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, it is necessary for each processor to mutually adjust their clocks 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, 30
2, 303, 304, and 305 each have a clock indicating its own time, and generate two time interrupts 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 system of the present invention while explaining the operations of the time interrupt and random timer. In Figure 2, the second
The time from the second interrupt to the next second interrupt is the clock synchronization control period, and for example, in this example,
It's time. As shown in the figure, the second time interrupt indicating the start of the k-th clock synchronization control period is set at 0:00, the first time interrupt of the k-th clock synchronization control period is set at 0:55, and the k-th clock is set at 0:55. A second time interrupt indicating the end of the synchronization period and the start of the (k+1)th clock synchronization period is set at 1:00. When processor i detects the first time interrupt at 0:55, it starts the timer. For example, suppose a timer is set to time out at a random time within 30 minutes. In this way, the probability that a timeout will occur between the first time interrupt at 0:55 and the second time interrupt at 1:00 is 1/6.
All processors in the network independently perform the same timer activation and random timeout generation processing, so if the total number of processors in the network is n, then on average n/6 processors will be the first processor in the above example. and a timeout will occur during the second time interrupt. In FIG. 2, timeout example 1 is an example in which a timeout occurs between the first and second time interrupts, and timeout example 2 is an example in which a timeout occurs between the first and second time interrupts.
This is an example of a timeout occurring after a time interrupt. In the method of the present invention, the above timeout example 1
As shown in FIG. 3, only when a timeout occurs between the first and second time interrupts, clock information at that time is sent to all processors at the time when the timeout occurs. On the other hand, each processor is provided with a clock reception time window for clock information reception processing, as shown in FIG. This is set in a time domain that includes the first and second time interrupts, and reception processing is performed only on clock information that arrives within this time window.

This synchronization method will be explained using the network example shown in FIG. In the description, it is assumed that the first time interrupt in each processor is 0:55, the second time interrupt is 1:00, and the reception time window is 0:45 to 1:10. When each processor detects its own processor's first time interrupt, it starts a timer, and if the timeout is before 1:00 as measured by its own clock, it sends clock information stamping the time at which the timeout occurred to all processors. Notice. A processor that receives a clock within the reception time window 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 using the average value Δ of the differences.
That is, if Δ is positive, add Δ to the own clock value,
If Δ is negative, the own clock is stopped by Δ. Assuming that each processor causes a timeout according to the timeout distribution mentioned earlier, the average per control for the total number of processors n is n/6.
Each processor will send its clock to all processors. Each processor adjusts its own clock value to the average value of the clock values from n/6 processors. For example, it is assumed that each processor has a clock value as shown in FIG. 3(a) before the clock control according to the present invention is applied. Assume now that the processors 301 and 302 have caused a timeout between the first and second time interrupts.
Checking the processor 301 timeout time using the processor 301 clock, it is 0:58.
The timeout time of 02 is checked by the clock of the processor 302 and is set to 0:56. Ignoring communication delays and clock shifts caused by the clock slope of each processor, the clock value of processor 301 reaches 0:58, and the clock value (0:
58) to all processors. The time indicated by each processor when processor 301 sends out its clock value is shown in FIG. 3b. Figure 3b
As can be seen, all the times indicated by each processor are within the reception time window, so all processors receive clock information from processor 301. When each processor receives the clock value of processor 301, it calculates the difference between it and its own clock value. The difference value is 0 for processor 301, +6 for processor 302, and +6 for processor 303.
4.+8 for processor 304, processor 30
5 becomes +2. Subsequently, when the clock value of processor 302 reaches 0:56, a clock value is sent out, and all processors receive that clock value. The times indicated by each processor at this time are shown in FIG. 3(c). In this case as well, all the times indicated by each processor are within the reception time window, so all processors
Receive clock information from. The difference value for each processor is -6 for processor 301, 0 for processor 302, -2 for processor 303,
In the processor 304, it is +2, and in the processor 305, it is -4. Therefore, each processor takes the average value of the above-mentioned difference values, and that value is calculated by the processor 301.
-3 for processor 302, +3 for processor 303, +1 for processor 304, +5 for processor 304,
In the processor 305, it becomes -1. If the clock value shown above is adjusted based on the average value of the difference values, when the reception time window ends in each processor, the clock of processor 301 will be delayed by 3 minutes, and the clock of processor 302 will be delayed by 3 minutes. The clock of processor 303 is advanced by 3 minutes, the clock of processor 303 is advanced by 1 minute, and the clock of processor 304 is advanced by 5 minutes.
It can be seen that the processor 305 clock is advanced by one minute, and the clock of processor 305 is delayed by one minute, so that 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 and reception time windows. Of course, since the timeout times are random for each processor for each clock synchronization period, the processors and number of processors that send out their own clocks for each clock synchronization period are random as a result.

In this way, all processors are on completely equal footing and execute exactly the same algorithm.
At this time, only the randomly selected processor sends out its clock value, so the amount of communication can be reduced compared to the conventional method. Moreover, by controlling the system time based on the average time of a plurality of processors, rather than using only one processor to control the system time, fault-tolerant time control becomes possible. Furthermore, the degree of fault tolerance can be flexibly controlled by changing the probability that a timeout will occur between time-of-day interrupts. In addition, since the times at which clock information is sent are random within a certain range (between the first time interrupt and the second time interrupt), the network is likely to be congested due to clock information sent by multiple processors. It can reduce the possibility of

(Detailed Description of the Invention) FIGS. 1a and 1b show an example of a flowchart of control executed by each processor to implement the method of the present invention. FIG. 1(a) is an example of a flowchart showing control of transmission of clock information, and FIG. 1b is an example of a flowchart showing control of reception of clock information. First, the transmission control flowchart shown in FIG. 1a will be explained. In each processor, block 10
When the first time interrupt is detected at time 0, a timer is started at block 101. The block 102 detects the occurrence of a second time interrupt, and if a time interrupt is detected, ends the transmission control during this synchronous control period (that is, it does not become a clock information sending processor during this period). block 100
The process returns to and waits for the first time interrupt in the next synchronous control period. If the second time interrupt is not detected in block 102, the process proceeds to block 103 to detect whether the set timer has timed out. If the timeout has not occurred, the process returns to block 102 to determine if a second time interrupt has been detected. That is, block 102 and block 103
This loop continues until either the second time interrupt or a timeout is detected, and when the timeout is detected in block 103 (at this time, the timeout is detected before the second time interrupt occurs). , in block 104, clock information stamped with the time when the timeout occurred is sent to all processors (that is, they became clock information sending processors during this clock synchronization control period), and the transmission control during this synchronization control period is completed. death,
Returning to block 100, the first
Wait for the time interrupt. In the reception control shown in Fig. 1b,
In each processor, when block 110 detects the start of the reception time window, block 111 receives clock information. In the subsequent block 112, the difference between the received clock value and the own clock value is calculated and stored. In block 113, it is determined whether the reception time window has expired or not. If not, the clock information is received again, and this loop is repeated until the reception time window has expired.
When block 113 detects that the receiving time window has ended, the block 114 goes to block 114 and calculates the difference between all the clock information received when the receiving time window was open and its own clock value (calculated in block 112). Calculate the average value of In the subsequent block 115, the control is switched depending on the sign of the calculated Δ. If Δ is positive, in block 116, Δ is added to the own clock value to adjust the own clock. If Δ is negative, in block 117 the own clock is stopped by Δ and the own clock is adjusted. When the processing in block 116 or 117 is completed, the reception processing in this synchronization control period is completed, and the process returns to block 110 to wait for the start of the reception time window for starting reception control in the next clock synchronization control period.

(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 each processor's clock can be synchronized. can be controlled to point to a common time. The processors that perform clock synchronization control are randomly selected for each synchronization control period, and a failure in a particular processor will not cause a fatal failure of the system, ensuring high reliability. Furthermore, the degree of reliability can be flexibly changed by controlling the probability that a timeout will occur between the first and second time interrupts. Furthermore, instead of a fixed number of processors being selected for each synchronous control period, the number of processors that send out clocks for synchronous control is also random and given as an average value for each synchronous control period. It is easy to avoid the resulting deadlock situation. Furthermore, since synchronous control is not performed using the clock values of all processors, but is performed using the clock values of a partial processor set, the processing time required for synchronous control becomes extremely large even when the number of processors increases. It will not increase. Furthermore, since the timing of transmitting clock information is randomly distributed between the first and second time interrupts, 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 drawings]

1a and 1b are flowcharts showing an embodiment of the clock synchronization method according to the present invention, and FIG.
Control timing charts of the clock synchronization system according to the present invention, FIGS. 3a, 3b, and 3c are diagrams showing an example of a multiprocessor system and an example of the time of each processor for explaining the principle of the invention. In the figure, 100-104, 110-117
is a control block, 301 to 305 are processors,
306 indicates a logical communication path between the processor 303 and the processor 304.

Claims (1)

[Claims] In a clock synchronization method for a multiprocessor system consisting of 1 n processors, each processor has a clock indicating time, a timer measuring random time, a first time interrupt, and a second time interrupt. , the timer times out after measuring a random time within a predetermined time range, and each processor has:
If the timer is started every time the first time interrupt occurs, and the time when the timeout occurs is between the first time interrupt and the second time interrupt,
It sends its own clock to all processors at the time when the timeout occurs, and each processor has a time window that includes the first and second time interrupts so that all processors that arrive during that time window A clock synchronization method in a multiprocessor system characterized by controlling each clock based on clock information. 2. In clock control of each processor,
The average time of all the received clock information is
If the average time is Δ ahead of the time indicated by your own clock, Δ is added to your clock; if the average time is Δ behind the time indicated by your own clock, the timer calculates the elapsed time Δ. A clock synchronization method in a multiprocessor system according to claim 1, characterized in that its own clock is stopped until notification is given.