시간 동기화 알고리즘이 널리 사용됩니다.
예를 들어 Unix 시스템에서 Make 명령은 새로 수정된 코드 파일을 컴파일하는 데에만 사용됩니다. Make 명령은 실행 중인 클라이언트의 시계를 사용하여 어떤 파일이 수정되었는지 확인합니다. 그러나 코드가 파일 서버에 배치되어 있고 make 명령을 실행하는 호스트의 시간이 파일 서버의 시간과 다를 경우 make 명령이 제대로 작동하지 않을 수 있습니다.
예를 들어, Dota를 플레이할 때 모든 클라이언트의 영상을 일관되게 유지하려면 여러 클라이언트에 동기화된 시계가 필요합니다. , 예를 들어 PC 컴퓨터 동기화 서버 시간은 매우 높은 동기화 정확도를 달성할 수 있습니다.
시간 동기화 알고리즘
시간 동기화 알고리즘에는 다음과 같은 솔루션이 있습니다.
크리스티안의 알고리즘
Cristian 알고리즘 알고리즘의 적용 배경은 주로 프로세스 P가 시간을 요청하는 서버 S와 같을 때입니다.
1. P는 S에게 시간을 요청하기 위해 요청 패킷을 보냅니다.
2. S는 P의 요청 패킷을 수신한 후 현재 S 시간을 패킷에 추가한 다음 다시 보냅니다.
3. P는 데이터 패킷을 수신한 후 현재 시간을 T+RTT/2로 설정합니다.
RTT는 P가 데이터 패킷을 전송하는 데 걸리는 시간인 왕복 시간(Round Trip Time)을 나타냅니다. 알고리즘은 네트워크에서 패킷을 보내고 받는 데 동일한 시간이 걸린다고 가정합니다. 그리고 요청을 처리할 때 S의 시간도 무시할 수 있다고 가정합니다. 위의 가정을 바탕으로 알고리즘을 다음과 같이 개선할 수 있습니다.
P에서 S로 여러 개의 요청 패킷을 보낸 다음 가장 작은 RTT를 RTT를 2로 나눈 값을 이 패킷에 포함된 시간에 더합니다.
알고리즘 정확도 분석: min은 S에서 P까지의 최단 시간이고, T는 위에서 정의한 RTT에 포함되는 시간이라고 가정합니다. 그러면 P 설정 시간의 범위는 [T+min, T+RTT-min]이 되어야 합니다. 이러한 방식으로 시간 편차 범위는 RTT-2min 이내입니다. 개선된 알고리즘의 정확도는 RTT/2분이어야 합니다.
알고리즘 버클리 알고리즘
Berkeley 알고리즘은 Cristian 알고리즘과 사용 환경이 다릅니다. Cristian 알고리즘은 클라이언트가 서버에 정확한 시간을 요청할 때 사용됩니다. 버클리 알고리즘은 여러 클라이언트 간의 시계를 동기화하는 알고리즘입니다. 구체적인 알고리즘은 다음과 같습니다.
1. 먼저 Change와 Robert의 알고리즘을 통해 링에서 노드를 마스터로 선택합니다.
2. 마스터는 Cristian 알고리즘을 사용하여 각 노드의 시간을 요청합니다.
3. 마스터는 평균 RTT를 기록하고 편차가 큰 RTT를 제거하여 각 노드의 시간 편차를 평가합니다.
4. 마스터는 각 노드의 시간 편차를 각 노드에 전송하여 노드가 스스로 수정할 수 있도록 합니다.
클라이언트가 시간을 받은 후에는 일반적으로 현재 시간을 다시 조정하지 않습니다. 왜냐하면 이로 인해 프로그램에 설명할 수 없는 오류가 발생할 수 있기 때문입니다. 많은 알고리즘에서는 시간이 다시 조정되지 않는다는 것이 기본 가정이기 때문입니다. 예를 들어 make 명령을 실행합니다.
해결책이 있습니다. 시계가 더 느리게 작동하도록 놔두세요. 정확한 시간에 적응하는 데 시간이 좀 걸립니다.
또한 알고리즘 변경(Change)과 로버트 알고리즘(Robert's Algorithm)에 대해서도 논의할 필요가 있습니다. 이 알고리즘은 시간 동기화 알고리즘과 동일하며 Dota를 플레이할 때 필요합니다. 도타가 초기화되면 각 플레이어의 시계를 동기화해야 합니다. 오프라인 상태가 된 후에는 특정 알고리즘을 사용하여 새 호스트를 찾아야 합니다.
변화와 로버트의 알고리즘
Change와 Robert의 알고리즘 알고리즘은 각 프로세스에 UID가 있고 링 모양 네트워크에 방향 없는 통신 채널이 있을 수 있다고 가정합니다. 알고리즘은 다음과 같습니다.
1. 먼저 링의 각 노드는 자신을 비참가자로 식별합니다.
2. 프로세스가 호스트가 오프라인임을 발견하면 먼저 자신을 참가자로 식별한 다음 자신의 UID가 포함된 호스트 선택 패킷을 이웃으로 보냅니다.
3. 데이터 패킷이 이웃에 도달하면 먼저 자신의 UID와 비교하여 자신의 UID가 이 UID보다 크면 자신을 참가자로 식별하고 데이터 패킷의 UID를 수정하여 이를 전송합니다. 시계방향 데이터.
4. 프로세스가 데이터 패킷을 수신하고 데이터 패킷의 UID가 자신의 UID와 동일한 것을 발견하면 알고리즘의 두 번째 단계를 시작합니다.
5. 이 프로세스는 자신을 비참여자로 식별하고 UID 정보를 포함하여 선택한 호스트에 대한 정보를 이웃으로 보냅니다.
6. 이 주기는 프로세스가 호스트로 선택된 프로세스로 돌아올 때까지 계속됩니다. 전체 프로세스가 종료됩니다.
분산 시스템에서 호스트를 선택하는 알고리즘입니다. 물론, 특정 상황에서는 네트워크 속도가 가장 빠르거나 CPU가 가장 빠른 것을 호스트로 선택하는 등 선택 조건을 변경할 수 있습니다. 동시에 이 알고리즘은 여러 프로세스가 호스트가 동시에 오프라인 상태임을 발견하고 여러 프로세스가 동시에 호스트를 찾는 상황을 피할 수도 있습니다.
이 알고리즘의 의사코드는 다음과 같이 설명할 수 있습니다.
시작 : M:= i:
<i>를 이웃에게 보냅니다.
메시지 <j>를 받으면;
M<j이면 M:=j;
<j>를 이웃에게 보냅니다.
Elseif M=j이면 리더;
엔디프;
이 알고리즘의 자세한 복잡성 분석, 수학적 모델 및 통계표는 다음 문서를 참조하세요.
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
이 문서에서는 중앙 집중식 시스템의 여러 시간 동기화 알고리즘만 분석하고 분산 시스템의 네트워크 시간 프로토콜 및 참조 브로드캐스트 동기화 알고리즘은 분석하지 않습니다. 앞으로 시간이 나면 NTP를 공부하겠습니다.