JPH0528864B2 - - 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,
6th International Conference on Distributed Computing Systems
DISTRIBUTED COMPUTING SYSTEMS)
The paper “An Election Algorithm for Distributed Clocks Synchronization Program (An Election Algorithm for Distributed Clocks Synchronization Program)” is published in the proceedings of
a 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.3 BSD. 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 International Symposium on Fault Tolerant Computing (Annual International Symposium on Fault Tolerant Computing)
International Symposium on FAULT−
The paper ``CLOCK SYNCHRONIZATION IN THE PRESENCE OF OMISSION AND PERFORMANCE FOULTS, AND PROCESSORS'' (CLOCK 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” is listed 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) UNIX operating system mentioned above 4.3
In the BSD 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. 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. 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, and even if the number of processors in the system increases, communication messages are not concentrated on a certain processor, and the total number of messages in the system can be reduced compared to the previous method. It is an object of the present invention to provide a clock synchronization method in a distributed control type multiprocessor system, which can reduce the number of clocks in a distributed control multiprocessor system.

(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 the clock is a predetermined clock. When indicating the time, m processors are randomly selected from among the n processors, clock information of the m processors is read out, and the clock is controlled based on the time of the m processors. A clock synchronization method in a multiprocessor system with characteristics can be obtained.

(Operation) The principle of the present 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. Further, each processor is connected to each other by a logical communication path 306 so that clock information of any processor can be read out.
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 clocks that start from the same value Although the time is measured at roughly the same rate, the time gradually deviates as time passes. Therefore, each processor adjusts the clocks of 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.

In this synchronization method, each processor clocks its own processor at a predetermined time.
Among the n processors in the system, m processors are randomly selected and the clock information of the processors is queried. Furthermore, it resets its own clock value based on the inquired clock information. For example, processor 301 randomly selects a processor from among the five processors in the system each time its own clock reaches a predetermined time such as 1:00, 2:00, and 3:00. At some point, processor 301 selects processors 302, 302, and 304, and
These processors are queried for their clock values via 06. Based on the obtained clock values of the three processors, processor 301 calculates the average value of these clock values, and resets its own clock value based on the average value. For example, if the average value of the times of three processors is δ ahead of the time indicated by the processor's own clock, the difference δ is added to the processor's own clock, and the average value of the times of the three processors is δ ahead of the time indicated by the own clock. If the time is δ behind the time indicated by the clock, the clock is stopped by δ. The above operations are repeated by all processors each time their own clock reaches a predetermined time.

In this way, all processors are on completely equal footing and execute exactly the same algorithm.
At this time, since each processor performs synchronous control based on the clock information of the m processors, the amount of communication can be reduced compared to the conventional method. Furthermore, since the m processors are selected at random at this time, the clock information of all processors in the system is reflected in the synchronization control by repeating the synchronization control. Through a simulation experiment, it was confirmed that the synchronization range of the processor clock does not depend on the value of n and converges to satisfy sufficient synchronization accuracy when m=2 to 10.

As described above, since a specific processor does not define a common time and perform synchronous control, a failure of a certain processor will not cause a fatal failure to the system.

(First Embodiment) FIGS. 1a and 1b show a first embodiment of an algorithm for realizing the clock synchronization method according to the present invention.

Figure 1a shows a synchronization control algorithm that the processor executes when its own clock indicates a predetermined time; for example, when its own clock indicates 1:00, 2:00, 3:00, etc. It is executed at every set time. FIG. 1b shows the algorithm executed when a processor executes the synchronization control algorithm and receives a message from the same processor. Note that these two algorithms may be executed in parallel, and a request to send clock information to itself may be generated.

The processor detects in control block 101 shown in FIG. 1a an interrupt from a clock that is set to occur when its own clock reaches a predetermined time. Detection of an interrupt from this clock activates the subsequent synchronous control algorithm. That is, control block 102 randomly selects m processors from n processors, and control block 103 subsequently sends a message requesting each of these processors to transmit clock information.

Each processor also executes the algorithm shown in Figure 1b in parallel.
10, it is possible to detect a reception interrupt that occurs when a clock information transmission request message is received from the processor. That is, when a certain processor transmits a message in control block 103 of FIG. 1a, the processor that received the message detects a reception interrupt in control block 110 of FIG. control block 1
At step 11, clock information is sent to the processor that sent the message. The clock information sent by the processor at this time is the value indicated by the clock itself, but if the processor requesting clock information records its own time in the request message, the difference between the clock and the requesting processor's time is recorded. You may send it as information.

In this way, the processor that sent the clock information transmission request message receives clock information from m processors. Continuing control block 1
In 04, the average clock value of the m processors is calculated based on the clock information of these m processors, and the average time of the m processors is subtracted from the time indicated by the clock of the own processor.
Find the difference δ.

Based on the difference δ from the average time of the m processors obtained as described above, the processor sets the value of its own clock as described below in control block 105 and thereafter. That is, if the time indicated by the own processor's clock is equal to the average time (δ=0), the process returns to control block 101. If the time indicated by the own clock is later than the average time (δ<0), the control block 106 adds the difference δ to the own clock to advance the time, and then the control block 10
Return to 1. Furthermore, if the time indicated by its own clock is ahead of the average time (δ>0), the control block 107 sets the error δ in a timer in its own processor, and the control block 10
At 8, the clock is stopped until the timer signals that time δ has elapsed. After delaying the time in this manner, control returns to control block 101. In either case, control block 101 detects an interrupt from the next clock occurring at a predetermined time.

The algorithm described above is executed by all processors.

(Second Embodiment) FIGS. 2a and 2b show a second embodiment of an algorithm for implementing the clock synchronization method according to the present invention.

In a communication network system, which is an example of a multiprocessor system, when processors read each other's clock information, there is a communication delay between the processors, or the time required for communication processing and average time calculation is affected by the time accuracy of the clock. It is possible that it will be larger than . In order to prevent the clock synchronization control from being adversely affected by such processing overhead, the processor time at which the clock information is read is defined using an algorithm as described below.

Figures 2a and b illustrate the same algorithm. The algorithm shown here corresponds to the control blocks 102, 103 and 104 in FIG. This figure shows control in which the requested message is repeatedly transmitted m times, and the difference δ between the time indicated by the clock of the own processor and the average time is determined based on clock information sequentially received from these m processors. Note that in the second embodiment, the second
The control procedure from Figures a and b is the same as the procedure from control block 105 in Figure 1a.

The connector 200 shown in FIG. 2a is connected to the rear of the control block 101 of FIG. 1a. In control block 201, a value 0 is assigned to a variable k that counts the number of processors to be selected, and in control block 202, processor i is randomly selected from n processors in the system. Next, in control block 203, the time indicated by the clock in its own processor at this time is substituted into variable Ti,0, and in control block 204, a message is sent to request processor i to send clock information. Thereafter, in control block 205, 1 is added to a variable k that counts the number of randomly selected processors. In the control block 206, the variable k is compared with the value m, and if k<m, the process returns to the control block 202 again, and if k=m, the process continues to the connector 207, which is connected to the next process.

Connector 207 is connected to the front of control block 208 shown in FIG. 2b. control block 208
Now, as explained in FIG. 2a, a response to the clock information request message sent to m processors is awaited. Due to variations in the transmission times of the request messages and variations in communication delays, responses from each processor also arrive at different times. When a response from a processor i arrives, a control block 209 assigns the time at which the response arrived to a variable Ti,1, and a control block 210 assigns the time of the processor i recorded in the response message to a variable Ti,1. Assign to Ti. Thereafter, 1 is subtracted from a variable k that stores the number of processors randomly selected and sent the request message, and the value of the variable k is compared in control block 212. If k>0, control block 20
The process returns to step 8 to wait for responses from other processors, and if responses from all processors are received and k=0, control block 213 is executed. Note that there may be cases where responses are not obtained from all the processors even after a certain period of time has elapsed due to message loss or the like. In this case, control block 213 may be executed based on already obtained clock information. In the same control block 213, a variable Ti,0 indicating the time when processor i was selected is set.
Based on the variable Ti,1 indicating the time when the response from processor i arrived, and the variable Ti indicating the time of processor i recorded in the response message from processor i, the own processor calculates the time Ti,0.
The time of processor i at the time is predicted, and the difference δi between the time of processor i and the time of its own processor is determined. That is, assuming that the communication delay of a message from processor a to processor i is equal to the communication delay of a message sent from processor i to processor a almost at the same time, the time of processor i is predicted according to the following equation.

Ti-(Ti, 1-Ti, 0)/2 (1) Therefore, the difference .delta.i between the time indicated by the clock of its own processor and the time indicated by the clock of processor i is expressed as follows.

δi=Ti,0−{Ti−(Ti,1−Ti,0)/2}
(2) The control block 214 calculates the average value of the m δi thus obtained, and assumes that the same value is the difference δ from the average time of m randomly selected processors. Note that the connector 215 is
It is connected to the front of the control block 105 of FIG. 1a. Based on the difference δ from the average time obtained as above, control block 1 of FIG.
Perform the steps from 05 onwards. This algorithm predicts processor time by taking into account communication delays between processors, making it possible to eliminate the effects of communication delays.

(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 within a certain range. Since there is no need for a processor that performs centralized control, a failure in a particular processor will not cause a fatal failure to the system, and high reliability can be ensured. In addition, the information required by each processor is only the time information of m processors, and according to a simulation experiment, m
= 2 to 10 provides sufficient synchronization accuracy. Therefore,
Since it is not necessary to collect clock information of all processors, the processing time required for synchronous control does not increase even when the number of processors increases. Moreover, since these processors are periodically and randomly selected, synchronization control is performed based on clock information of all processors.

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

[Brief explanation of the drawing]

Figures 1a and b are flowcharts showing a first embodiment of the present invention, and Figures 2a and b show an algorithm for determining processor time in the second embodiment when communication delays are taken into account. Figure 3 is
1 is a diagram showing an example of a multiprocessor system. In the figure, 101-111 and 201-
214 is a control block, 200, 207, 215
is a connector, 301 to 305 are processors, 306
indicates a logical communication path between processors.

Claims (1)

[Scope of Claims] 1. In a clock synchronization system for a multiprocessor system consisting of n processors, the processor is provided with a clock that indicates time, and when the clock indicates a predetermined time, the n
A multiprocessor system characterized in that m processors are randomly selected from among the m processors, clock information of the m processors is read out, and the clock is controlled based on the time of the m processors. clock synchronization method. 2. The processor is equipped with a timer that can measure the passage of arbitrary time, and if the average time of the m processors determined based on the m clock information is δ ahead of the time indicated by its own clock, Add δ to its own clock, and if the average time of the m processors is behind the time indicated by its own clock by δ, stop its own clock until the timer notifies that time δ has passed. A clock synchronization method in a multiprocessor system as claimed in claim 1.