JPH0528866B2 - - 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 it is possible to obtain information for specifying the location where the failure has occurred.

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 was held in May 1986.
COMPUTING SYSTEMS) Proceedings p.364−
371 of the papers en élección
An Election Algorithm for a
Distributed Clock Synchronization Program)
Clock synchronization method introduced in (Reference 1)
TEMPO is a UNIX operating system
It is installed in a network running on 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, in 1986, 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 PROCESSOR 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 ``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 article Synchronizing Clocks in the Presence of...
Faults (Synchronizing Clocks in the
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 their processor times with each other.

(Problem to be solved by the invention) The UNIX operating system mentioned above
A master node is essential for the 4.3BSD TENPO 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. Also, 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 finding the average time of all nodes increases.

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. Further, 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 Problem) According to the present invention, in a clock synchronization method for a multiprocessor system consisting of n processors, the processor is provided with a clock indicating time and means for generating a random variable; The random variable generation means selects 1 with a probability of m/n (m is a positive number smaller than n) and 0 with a probability of (1-m/n), and each processor selects a predetermined period. If the selected random variable is 1, clock information is sent to all processors when the clock indicates a predetermined time, and all processors that received the clock information A clock synchronization method in a multiprocessor system is obtained, which is characterized in that each clock is controlled based on all received clock information.

(Principle of the invention) The principle of the 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. Furthermore, each processor is equipped with means for generating a random variable v, so that v=1 is selected with a predetermined probability p, and v=0 is selected with a probability (1-p). Further, 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, processors 303 and 304 are connected by a communication path 306. In a multiprocessor system that does not have a shared memory that can be commonly accessed by processors, the clocks of each processor do not indicate the same time when the system is in its initial state. Moreover, the clock started from the same value,
Although the time is measured at roughly the same rate, the time gradually deviates 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.

In this synchronization method, each processor clocks its own processor at a predetermined time (for example, at a predetermined time such as 1:00, 2:00, or 3:00). Select the value of the variable v, and if v=1, send the own clock value to all processors. 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 using 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 Δ. Here, the total number of processors is n
If we set the probability of v=1 to be m/n, on average m processors will send their own clocks to all processors per control. Each processor adjusts its own clock value to this average value of the clock values from m processors.

For example, the operation of the present invention will be described in the case where the clock values of each processor take values as shown in FIG. At this time, each processor selects the value of the variable v and starts control when its own clock indicates 1:00. Also, v= with probability 2/5
1, choose v=0 with probability 3/5. now,
It is assumed that processors 301 and 302 select v=1, and the other processors select v=0. Ignoring communication delays, processor 301 reaches 1:00 first and sends its clock value (1:00) to all processors. 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 and 0 for processor 3.
+6 for processor 02, +4 for processor 303, +8 for processor 304, and +6 for processor 305.
It becomes 2.

Subsequently, when processor 302 reaches 1:00, it sends out a clock value, which is received by all processors. The difference values for each processor are -6 for processor 301, 0 for processor 302, and -6 for processor 303.
2.+2 for processor 304, processor 30
5 becomes -4. Therefore, each processor takes the average value of the above-mentioned difference values and sends that value to processor 3.
-3 for processor 01, +3 for processor 302, +1 for processor 303, and + for processor 304.
5. The processor 305 becomes -1. If the clock values shown above are adjusted based on the average value of the difference values, the clock of processor 301 will be delayed by 3 minutes, the clock of processor 302 will be advanced by 3 minutes, and the clock of processor 303 will be delayed by 1 minute. It can be seen that the clock of processor 304 is advanced by 5 minutes, the clock of processor 305 is delayed by 1 minute, and the clock values of all processors are adjusted to the same value.
In this example, for ease of explanation, the clock drift and transmission path delay of each processor are ignored as they are sufficiently small. The above control is repeatedly performed by all processors each time their own clock reaches a predetermined time. Of course, since the value of the variable v selected is random at each time, the processors that send their own clocks and the number of processors at each time are random as a result.

In this way, all processors are on completely equal footing and execute exactly the same algorithm.
Since only this randomly selected processor sends out its clock value, 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 the variable v takes 1.

(Detailed Description of the Invention) FIGS. 1a, 1b, and 1c show an example of a flowchart of control executed by each processor to implement the method of the present invention. FIG. 1a is an example of a flowchart showing clock information transmission control, and FIG.
1 is an example of a flowchart showing control of reception of clock information, and FIG. 1c is an example of a flowchart showing details of clock reception processing. First, the transmission control flowchart shown in FIG. 1a will be explained. In each processor, block 101 handles clock interrupt 1.
When detected, a random variable v is selected in block 102. This variable v takes 1 and 0 with probabilities p and (1-p), respectively. 10
In block 3, control is switched according to the selected value of v. If v=1, block 104 waits for clock interrupt 2, and when clock interrupt 2 is detected, block 105 sets its own clock value. The data is sent to all processors, and after the data is sent, the transmission control process ends and the process returns to block 101. If v=0, the process returns to block 101 and waits for the next cycle of clock interrupt 1. In the reception control shown in FIG. 1B, when clock interrupt 1 is detected in block 101 in each processor, clock reception processing in block 110 is executed. In addition, block 11
An example flowchart illustrating the details of the 0 clock reception process is shown in FIG. 1c, and will be explained later. When the reception process in block 110 is completed, block 111 calculates the average value Δ of the differences between all the received clock values and the own clock value. In block 112, control is switched depending on whether the calculated Δ is positive or negative. If Δ is positive, in block 113 Δ is added to the own clock value to adjust the own clock. If Δ is negative, in block 114 the own clock is stopped by Δ and the own clock is adjusted. Block 113 or 1
When the process in step 14 is completed, the process returns to block 101 and waits for clock interrupt 1 to start clock control in the next cycle.

The clock reception process shown in block 110 of FIG. 1b will now be described using the example flowchart of FIG. 1c. Upon entering the clock reception process, a timer is set in block 120. Next, in block 121, the device waits for reception of the clock sent out. Block 122 determines whether the set timer has timed out.
If a timeout occurs, the reception process is exited.
If the clock has not timed out, the clock is received at block 123 when the clock arrives. In the following block 124, the difference between the received clock and the own clock value is calculated and stored. Further, in the subsequent block 125, a timeout determination is made, and if the timeout occurs, the reception processing is terminated, and if the timeout does not occur, the process returns to the block 121 and enters the state of waiting for new clock reception.

FIG. 2 shows an example of a timing chart of the clock synchronization method of the present invention. The horizontal axis shows the change in time, and the clock control cycle of each processor is started when clock interrupt 1 is detected. As shown in the figure, a window is provided in the clock reception time domain, and the clock value of each processor is adjusted according to the clock information that arrives during that window. In the figure, the upper part of the time axis shows clock reception processing, and the lower part shows clock transmission processing.

(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 processor that performs clock synchronization control is randomly selected for each synchronization cycle, and a failure in a particular processor will not cause a fatal failure to the system, ensuring high reliability. Further, the degree of reliability can be flexibly changed by controlling the probability that the random variable v takes 1. Furthermore, instead of a fixed number of processors being selected for each synchronization period, the number of processors that send out clocks for synchronization control is also random and given as an average value for each period, so the deadlock caused by control is The situation is easy to avoid. Furthermore, since synchronous control is not performed using the clock values of all processors, but is performed using the clock values of a partial set of processors, the processing time required for synchronous control becomes extremely large even when the number of processors increases. It will not increase.

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

[Brief explanation of the drawing]

1a, b, and c 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 FIG. 3 is a flow chart showing the principle of the present invention. 1 is a diagram showing an example of a multiprocessor system for explanation. FIG. In the figure, 101-105, 110-114
and 120 to 125 are control blocks, 301 to 125 are control blocks;
305 is a processor, 306 is a processor 303
3 shows a logical communication path between the processor 304 and the processor 304.

Claims (1)

[Claims] 1. In a clock synchronization method for a multiprocessor system consisting of n processors, the processor is equipped with a clock indicating time and means for generating a random variable, and the random variable generating means is m/n. 1 with probability (m is an integer smaller than n),
0 is selected with a probability of (1-m/n), and each processor selects a random variable at predetermined intervals, and if the selected random variable is 1, the clock is A multiprocessor characterized in that clock information is sent to all processors when a predetermined time is indicated, and all processors that receive the clock information control their own clocks based on all the received clock information. Clock synchronization method in the system. 2. Each of the processors is equipped with a timer that can measure the passage of arbitrary time, and if the average time of all the received clock information is ahead of the time indicated by its own clock by Δ, it adds Δ to its own clock. However, if the average time is behind the time indicated by the own clock by Δ, the own clock is stopped until the timer notifies that the time Δ has elapsed. Clock synchronization method in the described multiprocessor system.